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