/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
Line | Count | Source (jump to first uncovered line) |
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 "RDFDeadCode.h" |
13 | | #include "RDFGraph.h" |
14 | | #include "RDFLiveness.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 { |
29 | 859 | SetQueue() : Set(), Queue() {} |
30 | | |
31 | 31.5k | bool empty() const { |
32 | 31.5k | return Queue.empty(); |
33 | 31.5k | } |
34 | 30.7k | T pop_front() { |
35 | 30.7k | T V = Queue.front(); |
36 | 30.7k | Queue.pop(); |
37 | 30.7k | Set.erase(V); |
38 | 30.7k | return V; |
39 | 30.7k | } |
40 | 42.4k | void push_back(T V) { |
41 | 42.4k | if (Set.count(V)) |
42 | 11.7k | return; |
43 | 30.7k | Queue.push(V); |
44 | 30.7k | Set.insert(V); |
45 | 30.7k | } |
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. |
58 | 23.4k | bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const { |
59 | 23.4k | if (MI->mayStore() || 23.4k MI->isBranch()19.2k || MI->isCall()15.0k || MI->isReturn()14.6k ) |
60 | 8.81k | return true; |
61 | 14.6k | if (14.6k MI->hasOrderedMemoryRef() || 14.6k MI->hasUnmodeledSideEffects()13.2k ) |
62 | 1.37k | return true; |
63 | 13.2k | if (13.2k MI->isPHI()13.2k ) |
64 | 0 | return false; |
65 | 13.2k | for (auto &Op : MI->operands()) 13.2k { |
66 | 38.7k | if (Op.isReg() && 38.7k MRI.isReserved(Op.getReg())27.5k ) |
67 | 1.41k | return true; |
68 | 37.3k | if (37.3k Op.isRegMask()37.3k ) { |
69 | 0 | const uint32_t *BM = Op.getRegMask(); |
70 | 0 | for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN0 ; ++R0 ) { |
71 | 0 | if (BM[R/32] & (1u << (R%32))) |
72 | 0 | continue; |
73 | 0 | if (0 MRI.isReserved(R)0 ) |
74 | 0 | return true; |
75 | 0 | } |
76 | 0 | } |
77 | 38.7k | } |
78 | 11.8k | return false; |
79 | 23.4k | } |
80 | | |
81 | | void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA, |
82 | 15.8k | SetQueue<NodeId> &WorkQ) { |
83 | 15.8k | if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) |
84 | 4.14k | return; |
85 | 11.7k | if (11.7k !isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())11.7k ) |
86 | 5.92k | return; |
87 | 5.80k | for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 5.80k { |
88 | 13.6k | if (!LiveNodes.count(RA.Id)) |
89 | 13.6k | WorkQ.push_back(RA.Id); |
90 | 13.6k | } |
91 | 15.8k | } |
92 | | |
93 | | void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA, |
94 | 14.3k | SetQueue<NodeId> &WorkQ) { |
95 | 14.3k | NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); |
96 | 18.3k | for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { |
97 | 18.3k | if (!LiveNodes.count(UA.Id)) |
98 | 18.2k | WorkQ.push_back(UA.Id); |
99 | 18.3k | } |
100 | 14.3k | for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA)) |
101 | 17.3k | LiveNodes.insert(TA.Id); |
102 | 14.3k | } |
103 | | |
104 | | void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA, |
105 | 16.3k | SetQueue<NodeId> &WorkQ) { |
106 | 15.5k | for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) { |
107 | 15.5k | if (!LiveNodes.count(DA.Id)) |
108 | 10.6k | WorkQ.push_back(DA.Id); |
109 | 15.5k | } |
110 | 16.3k | } |
111 | | |
112 | | // Traverse the DFG and collect the set dead RefNodes and the set of |
113 | | // dead instructions. Return "true" if any of these sets is non-empty, |
114 | | // "false" otherwise. |
115 | 859 | bool DeadCodeElimination::collect() { |
116 | 859 | // This function works by first finding all live nodes. The dead nodes |
117 | 859 | // are then the complement of the set of live nodes. |
118 | 859 | // |
119 | 859 | // Assume that all nodes are dead. Identify instructions which must be |
120 | 859 | // considered live, i.e. instructions with observable side-effects, such |
121 | 859 | // as calls and stores. All arguments of such instructions are considered |
122 | 859 | // live. For each live def, all operands used in the corresponding |
123 | 859 | // instruction are considered live. For each live use, all its reaching |
124 | 859 | // defs are considered live. |
125 | 859 | LiveNodes.clear(); |
126 | 859 | SetQueue<NodeId> WorkQ; |
127 | 859 | for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) |
128 | 2.05k | for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) |
129 | 15.8k | scanInstr(IA, WorkQ); |
130 | 859 | |
131 | 31.5k | while (!WorkQ.empty()31.5k ) { |
132 | 30.7k | NodeId N = WorkQ.pop_front(); |
133 | 30.7k | LiveNodes.insert(N); |
134 | 30.7k | auto RA = DFG.addr<RefNode*>(N); |
135 | 30.7k | if (DFG.IsDef(RA)) |
136 | 14.3k | processDef(RA, WorkQ); |
137 | 30.7k | else |
138 | 16.3k | processUse(RA, WorkQ); |
139 | 30.7k | } |
140 | 859 | |
141 | 859 | if (trace()859 ) { |
142 | 0 | dbgs() << "Live nodes:\n"; |
143 | 0 | for (NodeId N : LiveNodes) { |
144 | 0 | auto RA = DFG.addr<RefNode*>(N); |
145 | 0 | dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n"; |
146 | 0 | } |
147 | 0 | } |
148 | 859 | |
149 | 10.0k | auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool { |
150 | 10.0k | for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) |
151 | 10.0k | if (10.0k LiveNodes.count(DA.Id)10.0k ) |
152 | 8.11k | return false; |
153 | 1.94k | return true; |
154 | 1.94k | }; |
155 | 859 | |
156 | 2.05k | for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { |
157 | 15.8k | for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { |
158 | 15.8k | for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) |
159 | 36.9k | if (36.9k !LiveNodes.count(RA.Id)36.9k ) |
160 | 6.12k | DeadNodes.insert(RA.Id); |
161 | 15.8k | if (DFG.IsCode<NodeAttrs::Stmt>(IA)) |
162 | 11.7k | if (11.7k isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())11.7k ) |
163 | 5.80k | continue; |
164 | 10.0k | if (10.0k IsDead(IA)10.0k ) { |
165 | 1.94k | DeadInstrs.insert(IA.Id); |
166 | 1.94k | if (trace()) |
167 | 0 | dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n"; |
168 | 1.94k | } |
169 | 15.8k | } |
170 | 2.05k | } |
171 | 859 | |
172 | 859 | return !DeadNodes.empty(); |
173 | 859 | } |
174 | | |
175 | | // Erase the nodes given in the Nodes set from DFG. In addition to removing |
176 | | // them from the DFG, if a node corresponds to a statement, the corresponding |
177 | | // machine instruction is erased from the function. |
178 | 180 | bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) { |
179 | 180 | if (Nodes.empty()) |
180 | 0 | return false; |
181 | 180 | |
182 | 180 | // Prepare the actual set of ref nodes to remove: ref nodes from Nodes |
183 | 180 | // are included directly, for each InstrNode in Nodes, include the set |
184 | 180 | // of all RefNodes from it. |
185 | 180 | NodeList DRNs, DINs; |
186 | 1.94k | for (auto I : Nodes) { |
187 | 1.94k | auto BA = DFG.addr<NodeBase*>(I); |
188 | 1.94k | uint16_t Type = BA.Addr->getType(); |
189 | 1.94k | if (Type == NodeAttrs::Ref1.94k ) { |
190 | 2 | DRNs.push_back(DFG.addr<RefNode*>(I)); |
191 | 2 | continue; |
192 | 2 | } |
193 | 1.94k | |
194 | 1.94k | // If it's a code node, add all ref nodes from it. |
195 | 1.94k | uint16_t Kind = BA.Addr->getKind(); |
196 | 1.94k | if (Kind == NodeAttrs::Stmt || 1.94k Kind == NodeAttrs::Phi1.88k ) { |
197 | 1.94k | for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG)) |
198 | 6.12k | DRNs.push_back(N); |
199 | 1.94k | DINs.push_back(DFG.addr<InstrNode*>(I)); |
200 | 0 | } else { |
201 | 0 | llvm_unreachable("Unexpected code node"); |
202 | 0 | return false; |
203 | 180 | } |
204 | 1.94k | } |
205 | 180 | |
206 | 180 | // Sort the list so that use nodes are removed first. This makes the |
207 | 180 | // "unlink" functions a bit faster. |
208 | 180 | auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool 180 { |
209 | 40.7k | uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind(); |
210 | 40.7k | if (KindA == NodeAttrs::Use && 40.7k KindB == NodeAttrs::Def30.1k ) |
211 | 4.57k | return true; |
212 | 36.1k | if (36.1k KindA == NodeAttrs::Def && 36.1k KindB == NodeAttrs::Use10.6k ) |
213 | 745 | return false; |
214 | 35.4k | return A.Id < B.Id; |
215 | 35.4k | }; |
216 | 180 | std::sort(DRNs.begin(), DRNs.end(), UsesFirst); |
217 | 180 | |
218 | 180 | if (trace()) |
219 | 0 | dbgs() << "Removing dead ref nodes:\n"; |
220 | 6.12k | for (NodeAddr<RefNode*> RA : DRNs) { |
221 | 6.12k | if (trace()) |
222 | 0 | dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n'; |
223 | 6.12k | if (DFG.IsUse(RA)) |
224 | 4.17k | DFG.unlinkUse(RA, true); |
225 | 1.95k | else if (1.95k DFG.IsDef(RA)1.95k ) |
226 | 1.95k | DFG.unlinkDef(RA, true); |
227 | 6.12k | } |
228 | 180 | |
229 | 180 | // Now, remove all dead instruction nodes. |
230 | 1.94k | for (NodeAddr<InstrNode*> IA : DINs) { |
231 | 1.94k | NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); |
232 | 1.94k | BA.Addr->removeMember(IA, DFG); |
233 | 1.94k | if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) |
234 | 1.88k | continue; |
235 | 58 | |
236 | 58 | MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); |
237 | 58 | if (trace()) |
238 | 0 | dbgs() << "erasing: " << *MI; |
239 | 1.94k | MI->eraseFromParent(); |
240 | 1.94k | } |
241 | 180 | return true; |
242 | 180 | } |