1 //===--- RDFDeadCode.cpp --------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // RDF-based generic dead code elimination.
11
12 #include "RDFGraph.h"
13 #include "RDFLiveness.h"
14 #include "RDFDeadCode.h"
15
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.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 {
SetQueueDeadCodeElimination::SetQueue29 SetQueue() : Set(), Queue() {}
30
emptyDeadCodeElimination::SetQueue31 bool empty() const {
32 return Queue.empty();
33 }
pop_frontDeadCodeElimination::SetQueue34 T pop_front() {
35 T V = Queue.front();
36 Queue.pop();
37 Set.erase(V);
38 return V;
39 }
push_backDeadCodeElimination::SetQueue40 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.
isLiveInstr(const MachineInstr * MI) const58 bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
59 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
60 return true;
61 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects())
62 return true;
63 if (MI->isPHI())
64 return false;
65 for (auto &Op : MI->operands())
66 if (Op.isReg() && MRI.isReserved(Op.getReg()))
67 return true;
68 return false;
69 }
70
scanInstr(NodeAddr<InstrNode * > IA,SetQueue<NodeId> & WorkQ)71 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
72 SetQueue<NodeId> &WorkQ) {
73 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
74 return;
75 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
76 return;
77 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
78 if (!LiveNodes.count(RA.Id))
79 WorkQ.push_back(RA.Id);
80 }
81 }
82
processDef(NodeAddr<DefNode * > DA,SetQueue<NodeId> & WorkQ)83 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
84 SetQueue<NodeId> &WorkQ) {
85 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
86 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
87 if (!LiveNodes.count(UA.Id))
88 WorkQ.push_back(UA.Id);
89 }
90 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
91 LiveNodes.insert(TA.Id);
92 }
93
processUse(NodeAddr<UseNode * > UA,SetQueue<NodeId> & WorkQ)94 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
95 SetQueue<NodeId> &WorkQ) {
96 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
97 if (!LiveNodes.count(DA.Id))
98 WorkQ.push_back(DA.Id);
99 }
100 }
101
102 // Traverse the DFG and collect the set dead RefNodes and the set of
103 // dead instructions. Return "true" if any of these sets is non-empty,
104 // "false" otherwise.
collect()105 bool DeadCodeElimination::collect() {
106 // This function works by first finding all live nodes. The dead nodes
107 // are then the complement of the set of live nodes.
108 //
109 // Assume that all nodes are dead. Identify instructions which must be
110 // considered live, i.e. instructions with observable side-effects, such
111 // as calls and stores. All arguments of such instructions are considered
112 // live. For each live def, all operands used in the corresponding
113 // instruction are considered live. For each live use, all its reaching
114 // defs are considered live.
115 LiveNodes.clear();
116 SetQueue<NodeId> WorkQ;
117 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
118 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
119 scanInstr(IA, WorkQ);
120
121 while (!WorkQ.empty()) {
122 NodeId N = WorkQ.pop_front();
123 LiveNodes.insert(N);
124 auto RA = DFG.addr<RefNode*>(N);
125 if (DFG.IsDef(RA))
126 processDef(RA, WorkQ);
127 else
128 processUse(RA, WorkQ);
129 }
130
131 if (trace()) {
132 dbgs() << "Live nodes:\n";
133 for (NodeId N : LiveNodes) {
134 auto RA = DFG.addr<RefNode*>(N);
135 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
136 }
137 }
138
139 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
140 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
141 if (LiveNodes.count(DA.Id))
142 return false;
143 return true;
144 };
145
146 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
147 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
148 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
149 if (!LiveNodes.count(RA.Id))
150 DeadNodes.insert(RA.Id);
151 if (DFG.IsCode<NodeAttrs::Stmt>(IA))
152 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
153 continue;
154 if (IsDead(IA)) {
155 DeadInstrs.insert(IA.Id);
156 if (trace())
157 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
158 }
159 }
160 }
161
162 return !DeadNodes.empty();
163 }
164
165 // Erase the nodes given in the Nodes set from DFG. In addition to removing
166 // them from the DFG, if a node corresponds to a statement, the corresponding
167 // machine instruction is erased from the function.
erase(const SetVector<NodeId> & Nodes)168 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
169 if (Nodes.empty())
170 return false;
171
172 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
173 // are included directly, for each InstrNode in Nodes, include the set
174 // of all RefNodes from it.
175 NodeList DRNs, DINs;
176 for (auto I : Nodes) {
177 auto BA = DFG.addr<NodeBase*>(I);
178 uint16_t Type = BA.Addr->getType();
179 if (Type == NodeAttrs::Ref) {
180 DRNs.push_back(DFG.addr<RefNode*>(I));
181 continue;
182 }
183
184 // If it's a code node, add all ref nodes from it.
185 uint16_t Kind = BA.Addr->getKind();
186 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {
187 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
188 DRNs.push_back(N);
189 DINs.push_back(DFG.addr<InstrNode*>(I));
190 } else {
191 llvm_unreachable("Unexpected code node");
192 return false;
193 }
194 }
195
196 // Sort the list so that use nodes are removed first. This makes the
197 // "unlink" functions a bit faster.
198 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {
199 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
200 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)
201 return true;
202 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
203 return false;
204 return A.Id < B.Id;
205 };
206 std::sort(DRNs.begin(), DRNs.end(), UsesFirst);
207
208 if (trace())
209 dbgs() << "Removing dead ref nodes:\n";
210 for (NodeAddr<RefNode*> RA : DRNs) {
211 if (trace())
212 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
213 if (DFG.IsUse(RA))
214 DFG.unlinkUse(RA, true);
215 else if (DFG.IsDef(RA))
216 DFG.unlinkDef(RA, true);
217 }
218
219 // Now, remove all dead instruction nodes.
220 for (NodeAddr<InstrNode*> IA : DINs) {
221 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
222 BA.Addr->removeMember(IA, DFG);
223 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
224 continue;
225
226 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
227 if (trace())
228 dbgs() << "erasing: " << *MI;
229 MI->eraseFromParent();
230 }
231 return true;
232 }
233