annotate llvm/lib/Target/Hexagon/RDFDeadCode.cpp @ 266:00f31e85ec16 default tip

Added tag current for changeset 31d058e83c98
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 14 Oct 2023 10:13:55 +0900
parents 1f2b6ac9f198
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
150
anatofuz
parents:
diff changeset
1 //===--- RDFDeadCode.cpp --------------------------------------------------===//
anatofuz
parents:
diff changeset
2 //
anatofuz
parents:
diff changeset
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
anatofuz
parents:
diff changeset
4 // See https://llvm.org/LICENSE.txt for license information.
anatofuz
parents:
diff changeset
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
anatofuz
parents:
diff changeset
6 //
anatofuz
parents:
diff changeset
7 //===----------------------------------------------------------------------===//
anatofuz
parents:
diff changeset
8 //
anatofuz
parents:
diff changeset
9 // RDF-based generic dead code elimination.
anatofuz
parents:
diff changeset
10
anatofuz
parents:
diff changeset
11 #include "RDFDeadCode.h"
anatofuz
parents:
diff changeset
12
anatofuz
parents:
diff changeset
13 #include "llvm/ADT/SetVector.h"
anatofuz
parents:
diff changeset
14 #include "llvm/CodeGen/MachineBasicBlock.h"
anatofuz
parents:
diff changeset
15 #include "llvm/CodeGen/MachineFunction.h"
anatofuz
parents:
diff changeset
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
173
0572611fdcc8 reorgnization done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 150
diff changeset
17 #include "llvm/CodeGen/RDFGraph.h"
0572611fdcc8 reorgnization done
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 150
diff changeset
18 #include "llvm/CodeGen/RDFLiveness.h"
150
anatofuz
parents:
diff changeset
19 #include "llvm/Support/Debug.h"
anatofuz
parents:
diff changeset
20
anatofuz
parents:
diff changeset
21 #include <queue>
anatofuz
parents:
diff changeset
22
anatofuz
parents:
diff changeset
23 using namespace llvm;
anatofuz
parents:
diff changeset
24 using namespace rdf;
anatofuz
parents:
diff changeset
25
anatofuz
parents:
diff changeset
26 // This drastically improves execution time in "collect" over using
anatofuz
parents:
diff changeset
27 // SetVector as a work queue, and popping the first element from it.
anatofuz
parents:
diff changeset
28 template<typename T> struct DeadCodeElimination::SetQueue {
anatofuz
parents:
diff changeset
29 SetQueue() : Set(), Queue() {}
anatofuz
parents:
diff changeset
30
anatofuz
parents:
diff changeset
31 bool empty() const {
anatofuz
parents:
diff changeset
32 return Queue.empty();
anatofuz
parents:
diff changeset
33 }
anatofuz
parents:
diff changeset
34 T pop_front() {
anatofuz
parents:
diff changeset
35 T V = Queue.front();
anatofuz
parents:
diff changeset
36 Queue.pop();
anatofuz
parents:
diff changeset
37 Set.erase(V);
anatofuz
parents:
diff changeset
38 return V;
anatofuz
parents:
diff changeset
39 }
anatofuz
parents:
diff changeset
40 void push_back(T V) {
anatofuz
parents:
diff changeset
41 if (Set.count(V))
anatofuz
parents:
diff changeset
42 return;
anatofuz
parents:
diff changeset
43 Queue.push(V);
anatofuz
parents:
diff changeset
44 Set.insert(V);
anatofuz
parents:
diff changeset
45 }
anatofuz
parents:
diff changeset
46
anatofuz
parents:
diff changeset
47 private:
anatofuz
parents:
diff changeset
48 DenseSet<T> Set;
anatofuz
parents:
diff changeset
49 std::queue<T> Queue;
anatofuz
parents:
diff changeset
50 };
anatofuz
parents:
diff changeset
51
anatofuz
parents:
diff changeset
52
anatofuz
parents:
diff changeset
53 // Check if the given instruction has observable side-effects, i.e. if
anatofuz
parents:
diff changeset
54 // it should be considered "live". It is safe for this function to be
anatofuz
parents:
diff changeset
55 // overly conservative (i.e. return "true" for all instructions), but it
anatofuz
parents:
diff changeset
56 // is not safe to return "false" for an instruction that should not be
anatofuz
parents:
diff changeset
57 // considered removable.
252
1f2b6ac9f198 LLVM16-1
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 221
diff changeset
58 bool DeadCodeElimination::isLiveInstr(NodeAddr<StmtNode *> S) const {
1f2b6ac9f198 LLVM16-1
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 221
diff changeset
59 const MachineInstr *MI = S.Addr->getCode();
150
anatofuz
parents:
diff changeset
60 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
anatofuz
parents:
diff changeset
61 return true;
anatofuz
parents:
diff changeset
62 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||
anatofuz
parents:
diff changeset
63 MI->isPosition())
anatofuz
parents:
diff changeset
64 return true;
anatofuz
parents:
diff changeset
65 if (MI->isPHI())
anatofuz
parents:
diff changeset
66 return false;
anatofuz
parents:
diff changeset
67 for (auto &Op : MI->operands()) {
anatofuz
parents:
diff changeset
68 if (Op.isReg() && MRI.isReserved(Op.getReg()))
anatofuz
parents:
diff changeset
69 return true;
anatofuz
parents:
diff changeset
70 if (Op.isRegMask()) {
anatofuz
parents:
diff changeset
71 const uint32_t *BM = Op.getRegMask();
anatofuz
parents:
diff changeset
72 for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN; ++R) {
anatofuz
parents:
diff changeset
73 if (BM[R/32] & (1u << (R%32)))
anatofuz
parents:
diff changeset
74 continue;
anatofuz
parents:
diff changeset
75 if (MRI.isReserved(R))
anatofuz
parents:
diff changeset
76 return true;
anatofuz
parents:
diff changeset
77 }
anatofuz
parents:
diff changeset
78 }
anatofuz
parents:
diff changeset
79 }
anatofuz
parents:
diff changeset
80 return false;
anatofuz
parents:
diff changeset
81 }
anatofuz
parents:
diff changeset
82
anatofuz
parents:
diff changeset
83 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
anatofuz
parents:
diff changeset
84 SetQueue<NodeId> &WorkQ) {
anatofuz
parents:
diff changeset
85 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
anatofuz
parents:
diff changeset
86 return;
252
1f2b6ac9f198 LLVM16-1
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 221
diff changeset
87 if (!isLiveInstr(IA))
150
anatofuz
parents:
diff changeset
88 return;
anatofuz
parents:
diff changeset
89 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
anatofuz
parents:
diff changeset
90 if (!LiveNodes.count(RA.Id))
anatofuz
parents:
diff changeset
91 WorkQ.push_back(RA.Id);
anatofuz
parents:
diff changeset
92 }
anatofuz
parents:
diff changeset
93 }
anatofuz
parents:
diff changeset
94
anatofuz
parents:
diff changeset
95 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
anatofuz
parents:
diff changeset
96 SetQueue<NodeId> &WorkQ) {
anatofuz
parents:
diff changeset
97 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
anatofuz
parents:
diff changeset
98 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
anatofuz
parents:
diff changeset
99 if (!LiveNodes.count(UA.Id))
anatofuz
parents:
diff changeset
100 WorkQ.push_back(UA.Id);
anatofuz
parents:
diff changeset
101 }
anatofuz
parents:
diff changeset
102 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
anatofuz
parents:
diff changeset
103 LiveNodes.insert(TA.Id);
anatofuz
parents:
diff changeset
104 }
anatofuz
parents:
diff changeset
105
anatofuz
parents:
diff changeset
106 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
anatofuz
parents:
diff changeset
107 SetQueue<NodeId> &WorkQ) {
anatofuz
parents:
diff changeset
108 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
anatofuz
parents:
diff changeset
109 if (!LiveNodes.count(DA.Id))
anatofuz
parents:
diff changeset
110 WorkQ.push_back(DA.Id);
anatofuz
parents:
diff changeset
111 }
anatofuz
parents:
diff changeset
112 }
anatofuz
parents:
diff changeset
113
anatofuz
parents:
diff changeset
114 // Traverse the DFG and collect the set dead RefNodes and the set of
anatofuz
parents:
diff changeset
115 // dead instructions. Return "true" if any of these sets is non-empty,
anatofuz
parents:
diff changeset
116 // "false" otherwise.
anatofuz
parents:
diff changeset
117 bool DeadCodeElimination::collect() {
anatofuz
parents:
diff changeset
118 // This function works by first finding all live nodes. The dead nodes
anatofuz
parents:
diff changeset
119 // are then the complement of the set of live nodes.
anatofuz
parents:
diff changeset
120 //
anatofuz
parents:
diff changeset
121 // Assume that all nodes are dead. Identify instructions which must be
anatofuz
parents:
diff changeset
122 // considered live, i.e. instructions with observable side-effects, such
anatofuz
parents:
diff changeset
123 // as calls and stores. All arguments of such instructions are considered
anatofuz
parents:
diff changeset
124 // live. For each live def, all operands used in the corresponding
anatofuz
parents:
diff changeset
125 // instruction are considered live. For each live use, all its reaching
anatofuz
parents:
diff changeset
126 // defs are considered live.
anatofuz
parents:
diff changeset
127 LiveNodes.clear();
anatofuz
parents:
diff changeset
128 SetQueue<NodeId> WorkQ;
anatofuz
parents:
diff changeset
129 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
anatofuz
parents:
diff changeset
130 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
anatofuz
parents:
diff changeset
131 scanInstr(IA, WorkQ);
anatofuz
parents:
diff changeset
132
anatofuz
parents:
diff changeset
133 while (!WorkQ.empty()) {
anatofuz
parents:
diff changeset
134 NodeId N = WorkQ.pop_front();
anatofuz
parents:
diff changeset
135 LiveNodes.insert(N);
anatofuz
parents:
diff changeset
136 auto RA = DFG.addr<RefNode*>(N);
anatofuz
parents:
diff changeset
137 if (DFG.IsDef(RA))
anatofuz
parents:
diff changeset
138 processDef(RA, WorkQ);
anatofuz
parents:
diff changeset
139 else
anatofuz
parents:
diff changeset
140 processUse(RA, WorkQ);
anatofuz
parents:
diff changeset
141 }
anatofuz
parents:
diff changeset
142
anatofuz
parents:
diff changeset
143 if (trace()) {
anatofuz
parents:
diff changeset
144 dbgs() << "Live nodes:\n";
anatofuz
parents:
diff changeset
145 for (NodeId N : LiveNodes) {
anatofuz
parents:
diff changeset
146 auto RA = DFG.addr<RefNode*>(N);
anatofuz
parents:
diff changeset
147 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
anatofuz
parents:
diff changeset
148 }
anatofuz
parents:
diff changeset
149 }
anatofuz
parents:
diff changeset
150
anatofuz
parents:
diff changeset
151 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
anatofuz
parents:
diff changeset
152 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
anatofuz
parents:
diff changeset
153 if (LiveNodes.count(DA.Id))
anatofuz
parents:
diff changeset
154 return false;
anatofuz
parents:
diff changeset
155 return true;
anatofuz
parents:
diff changeset
156 };
anatofuz
parents:
diff changeset
157
anatofuz
parents:
diff changeset
158 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
anatofuz
parents:
diff changeset
159 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
anatofuz
parents:
diff changeset
160 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
anatofuz
parents:
diff changeset
161 if (!LiveNodes.count(RA.Id))
anatofuz
parents:
diff changeset
162 DeadNodes.insert(RA.Id);
anatofuz
parents:
diff changeset
163 if (DFG.IsCode<NodeAttrs::Stmt>(IA))
252
1f2b6ac9f198 LLVM16-1
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 221
diff changeset
164 if (isLiveInstr(IA) || DFG.hasUntrackedRef(IA))
150
anatofuz
parents:
diff changeset
165 continue;
anatofuz
parents:
diff changeset
166 if (IsDead(IA)) {
anatofuz
parents:
diff changeset
167 DeadInstrs.insert(IA.Id);
anatofuz
parents:
diff changeset
168 if (trace())
anatofuz
parents:
diff changeset
169 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
anatofuz
parents:
diff changeset
170 }
anatofuz
parents:
diff changeset
171 }
anatofuz
parents:
diff changeset
172 }
anatofuz
parents:
diff changeset
173
anatofuz
parents:
diff changeset
174 return !DeadNodes.empty();
anatofuz
parents:
diff changeset
175 }
anatofuz
parents:
diff changeset
176
anatofuz
parents:
diff changeset
177 // Erase the nodes given in the Nodes set from DFG. In addition to removing
anatofuz
parents:
diff changeset
178 // them from the DFG, if a node corresponds to a statement, the corresponding
anatofuz
parents:
diff changeset
179 // machine instruction is erased from the function.
anatofuz
parents:
diff changeset
180 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
anatofuz
parents:
diff changeset
181 if (Nodes.empty())
anatofuz
parents:
diff changeset
182 return false;
anatofuz
parents:
diff changeset
183
anatofuz
parents:
diff changeset
184 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
anatofuz
parents:
diff changeset
185 // are included directly, for each InstrNode in Nodes, include the set
anatofuz
parents:
diff changeset
186 // of all RefNodes from it.
anatofuz
parents:
diff changeset
187 NodeList DRNs, DINs;
anatofuz
parents:
diff changeset
188 for (auto I : Nodes) {
anatofuz
parents:
diff changeset
189 auto BA = DFG.addr<NodeBase*>(I);
anatofuz
parents:
diff changeset
190 uint16_t Type = BA.Addr->getType();
anatofuz
parents:
diff changeset
191 if (Type == NodeAttrs::Ref) {
anatofuz
parents:
diff changeset
192 DRNs.push_back(DFG.addr<RefNode*>(I));
anatofuz
parents:
diff changeset
193 continue;
anatofuz
parents:
diff changeset
194 }
anatofuz
parents:
diff changeset
195
anatofuz
parents:
diff changeset
196 // If it's a code node, add all ref nodes from it.
anatofuz
parents:
diff changeset
197 uint16_t Kind = BA.Addr->getKind();
anatofuz
parents:
diff changeset
198 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {
221
79ff65ed7e25 LLVM12 Original
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
199 append_range(DRNs, NodeAddr<CodeNode*>(BA).Addr->members(DFG));
150
anatofuz
parents:
diff changeset
200 DINs.push_back(DFG.addr<InstrNode*>(I));
anatofuz
parents:
diff changeset
201 } else {
anatofuz
parents:
diff changeset
202 llvm_unreachable("Unexpected code node");
anatofuz
parents:
diff changeset
203 return false;
anatofuz
parents:
diff changeset
204 }
anatofuz
parents:
diff changeset
205 }
anatofuz
parents:
diff changeset
206
anatofuz
parents:
diff changeset
207 // Sort the list so that use nodes are removed first. This makes the
anatofuz
parents:
diff changeset
208 // "unlink" functions a bit faster.
anatofuz
parents:
diff changeset
209 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {
anatofuz
parents:
diff changeset
210 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
anatofuz
parents:
diff changeset
211 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)
anatofuz
parents:
diff changeset
212 return true;
anatofuz
parents:
diff changeset
213 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
anatofuz
parents:
diff changeset
214 return false;
anatofuz
parents:
diff changeset
215 return A.Id < B.Id;
anatofuz
parents:
diff changeset
216 };
anatofuz
parents:
diff changeset
217 llvm::sort(DRNs, UsesFirst);
anatofuz
parents:
diff changeset
218
anatofuz
parents:
diff changeset
219 if (trace())
anatofuz
parents:
diff changeset
220 dbgs() << "Removing dead ref nodes:\n";
anatofuz
parents:
diff changeset
221 for (NodeAddr<RefNode*> RA : DRNs) {
anatofuz
parents:
diff changeset
222 if (trace())
anatofuz
parents:
diff changeset
223 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
anatofuz
parents:
diff changeset
224 if (DFG.IsUse(RA))
anatofuz
parents:
diff changeset
225 DFG.unlinkUse(RA, true);
anatofuz
parents:
diff changeset
226 else if (DFG.IsDef(RA))
anatofuz
parents:
diff changeset
227 DFG.unlinkDef(RA, true);
anatofuz
parents:
diff changeset
228 }
anatofuz
parents:
diff changeset
229
anatofuz
parents:
diff changeset
230 // Now, remove all dead instruction nodes.
anatofuz
parents:
diff changeset
231 for (NodeAddr<InstrNode*> IA : DINs) {
anatofuz
parents:
diff changeset
232 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
anatofuz
parents:
diff changeset
233 BA.Addr->removeMember(IA, DFG);
anatofuz
parents:
diff changeset
234 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
anatofuz
parents:
diff changeset
235 continue;
anatofuz
parents:
diff changeset
236
anatofuz
parents:
diff changeset
237 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
anatofuz
parents:
diff changeset
238 if (trace())
anatofuz
parents:
diff changeset
239 dbgs() << "erasing: " << *MI;
anatofuz
parents:
diff changeset
240 MI->eraseFromParent();
anatofuz
parents:
diff changeset
241 }
anatofuz
parents:
diff changeset
242 return true;
anatofuz
parents:
diff changeset
243 }