File: | lib/Target/Hexagon/RDFGraph.cpp |
Location: | line 1552, column 34 |
Description: | Called C++ object pointer is null |
1 | //===--- RDFGraph.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 | // Target-independent, SSA-based data flow graph for register data flow (RDF). | |||
11 | // | |||
12 | #include "RDFGraph.h" | |||
13 | ||||
14 | #include "llvm/ADT/SetVector.h" | |||
15 | #include "llvm/CodeGen/MachineBasicBlock.h" | |||
16 | #include "llvm/CodeGen/MachineDominanceFrontier.h" | |||
17 | #include "llvm/CodeGen/MachineDominators.h" | |||
18 | #include "llvm/CodeGen/MachineFunction.h" | |||
19 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
20 | #include "llvm/Target/TargetInstrInfo.h" | |||
21 | #include "llvm/Target/TargetRegisterInfo.h" | |||
22 | ||||
23 | using namespace llvm; | |||
24 | using namespace rdf; | |||
25 | ||||
26 | // Printing functions. Have them here first, so that the rest of the code | |||
27 | // can use them. | |||
28 | namespace rdf { | |||
29 | ||||
30 | template<> | |||
31 | raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterRef> &P) { | |||
32 | auto &TRI = P.G.getTRI(); | |||
33 | if (P.Obj.Reg > 0 && P.Obj.Reg < TRI.getNumRegs()) | |||
34 | OS << TRI.getName(P.Obj.Reg); | |||
35 | else | |||
36 | OS << '#' << P.Obj.Reg; | |||
37 | if (P.Obj.Sub > 0) { | |||
38 | OS << ':'; | |||
39 | if (P.Obj.Sub < TRI.getNumSubRegIndices()) | |||
40 | OS << TRI.getSubRegIndexName(P.Obj.Sub); | |||
41 | else | |||
42 | OS << '#' << P.Obj.Sub; | |||
43 | } | |||
44 | return OS; | |||
45 | } | |||
46 | ||||
47 | template<> | |||
48 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeId> &P) { | |||
49 | auto NA = P.G.addr<NodeBase*>(P.Obj); | |||
50 | uint16_t Attrs = NA.Addr->getAttrs(); | |||
51 | uint16_t Kind = NodeAttrs::kind(Attrs); | |||
52 | uint16_t Flags = NodeAttrs::flags(Attrs); | |||
53 | switch (NodeAttrs::type(Attrs)) { | |||
54 | case NodeAttrs::Code: | |||
55 | switch (Kind) { | |||
56 | case NodeAttrs::Func: OS << 'f'; break; | |||
57 | case NodeAttrs::Block: OS << 'b'; break; | |||
58 | case NodeAttrs::Stmt: OS << 's'; break; | |||
59 | case NodeAttrs::Phi: OS << 'p'; break; | |||
60 | default: OS << "c?"; break; | |||
61 | } | |||
62 | break; | |||
63 | case NodeAttrs::Ref: | |||
64 | if (Flags & NodeAttrs::Preserving) | |||
65 | OS << '+'; | |||
66 | if (Flags & NodeAttrs::Clobbering) | |||
67 | OS << '~'; | |||
68 | switch (Kind) { | |||
69 | case NodeAttrs::Use: OS << 'u'; break; | |||
70 | case NodeAttrs::Def: OS << 'd'; break; | |||
71 | case NodeAttrs::Block: OS << 'b'; break; | |||
72 | default: OS << "r?"; break; | |||
73 | } | |||
74 | break; | |||
75 | default: | |||
76 | OS << '?'; | |||
77 | break; | |||
78 | } | |||
79 | OS << P.Obj; | |||
80 | if (Flags & NodeAttrs::Shadow) | |||
81 | OS << '"'; | |||
82 | return OS; | |||
83 | } | |||
84 | ||||
85 | namespace { | |||
86 | void printRefHeader(raw_ostream &OS, const NodeAddr<RefNode*> RA, | |||
87 | const DataFlowGraph &G) { | |||
88 | OS << Print<NodeId>(RA.Id, G) << '<' | |||
89 | << Print<RegisterRef>(RA.Addr->getRegRef(), G) << '>'; | |||
90 | if (RA.Addr->getFlags() & NodeAttrs::Fixed) | |||
91 | OS << '!'; | |||
92 | } | |||
93 | } | |||
94 | ||||
95 | template<> | |||
96 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<DefNode*>> &P) { | |||
97 | printRefHeader(OS, P.Obj, P.G); | |||
98 | OS << '('; | |||
99 | if (NodeId N = P.Obj.Addr->getReachingDef()) | |||
100 | OS << Print<NodeId>(N, P.G); | |||
101 | OS << ','; | |||
102 | if (NodeId N = P.Obj.Addr->getReachedDef()) | |||
103 | OS << Print<NodeId>(N, P.G); | |||
104 | OS << ','; | |||
105 | if (NodeId N = P.Obj.Addr->getReachedUse()) | |||
106 | OS << Print<NodeId>(N, P.G); | |||
107 | OS << "):"; | |||
108 | if (NodeId N = P.Obj.Addr->getSibling()) | |||
109 | OS << Print<NodeId>(N, P.G); | |||
110 | return OS; | |||
111 | } | |||
112 | ||||
113 | template<> | |||
114 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) { | |||
115 | printRefHeader(OS, P.Obj, P.G); | |||
116 | OS << '('; | |||
117 | if (NodeId N = P.Obj.Addr->getReachingDef()) | |||
118 | OS << Print<NodeId>(N, P.G); | |||
119 | OS << "):"; | |||
120 | if (NodeId N = P.Obj.Addr->getSibling()) | |||
121 | OS << Print<NodeId>(N, P.G); | |||
122 | return OS; | |||
123 | } | |||
124 | ||||
125 | template<> | |||
126 | raw_ostream &operator<< (raw_ostream &OS, | |||
127 | const Print<NodeAddr<PhiUseNode*>> &P) { | |||
128 | printRefHeader(OS, P.Obj, P.G); | |||
129 | OS << '('; | |||
130 | if (NodeId N = P.Obj.Addr->getReachingDef()) | |||
131 | OS << Print<NodeId>(N, P.G); | |||
132 | OS << ','; | |||
133 | if (NodeId N = P.Obj.Addr->getPredecessor()) | |||
134 | OS << Print<NodeId>(N, P.G); | |||
135 | OS << "):"; | |||
136 | if (NodeId N = P.Obj.Addr->getSibling()) | |||
137 | OS << Print<NodeId>(N, P.G); | |||
138 | return OS; | |||
139 | } | |||
140 | ||||
141 | template<> | |||
142 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<RefNode*>> &P) { | |||
143 | switch (P.Obj.Addr->getKind()) { | |||
144 | case NodeAttrs::Def: | |||
145 | OS << PrintNode<DefNode*>(P.Obj, P.G); | |||
146 | break; | |||
147 | case NodeAttrs::Use: | |||
148 | if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef) | |||
149 | OS << PrintNode<PhiUseNode*>(P.Obj, P.G); | |||
150 | else | |||
151 | OS << PrintNode<UseNode*>(P.Obj, P.G); | |||
152 | break; | |||
153 | } | |||
154 | return OS; | |||
155 | } | |||
156 | ||||
157 | template<> | |||
158 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeList> &P) { | |||
159 | unsigned N = P.Obj.size(); | |||
160 | for (auto I : P.Obj) { | |||
161 | OS << Print<NodeId>(I.Id, P.G); | |||
162 | if (--N) | |||
163 | OS << ' '; | |||
164 | } | |||
165 | return OS; | |||
166 | } | |||
167 | ||||
168 | template<> | |||
169 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) { | |||
170 | unsigned N = P.Obj.size(); | |||
171 | for (auto I : P.Obj) { | |||
172 | OS << Print<NodeId>(I, P.G); | |||
173 | if (--N) | |||
174 | OS << ' '; | |||
175 | } | |||
176 | return OS; | |||
177 | } | |||
178 | ||||
179 | namespace { | |||
180 | template <typename T> | |||
181 | struct PrintListV { | |||
182 | PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} | |||
183 | typedef T Type; | |||
184 | const NodeList &List; | |||
185 | const DataFlowGraph &G; | |||
186 | }; | |||
187 | ||||
188 | template <typename T> | |||
189 | raw_ostream &operator<< (raw_ostream &OS, const PrintListV<T> &P) { | |||
190 | unsigned N = P.List.size(); | |||
191 | for (NodeAddr<T> A : P.List) { | |||
192 | OS << PrintNode<T>(A, P.G); | |||
193 | if (--N) | |||
194 | OS << ", "; | |||
195 | } | |||
196 | return OS; | |||
197 | } | |||
198 | } | |||
199 | ||||
200 | template<> | |||
201 | raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<PhiNode*>> &P) { | |||
202 | OS << Print<NodeId>(P.Obj.Id, P.G) << ": phi [" | |||
203 | << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; | |||
204 | return OS; | |||
205 | } | |||
206 | ||||
207 | template<> | |||
208 | raw_ostream &operator<< (raw_ostream &OS, | |||
209 | const Print<NodeAddr<StmtNode*>> &P) { | |||
210 | unsigned Opc = P.Obj.Addr->getCode()->getOpcode(); | |||
211 | OS << Print<NodeId>(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc) | |||
212 | << " [" << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; | |||
213 | return OS; | |||
214 | } | |||
215 | ||||
216 | template<> | |||
217 | raw_ostream &operator<< (raw_ostream &OS, | |||
218 | const Print<NodeAddr<InstrNode*>> &P) { | |||
219 | switch (P.Obj.Addr->getKind()) { | |||
220 | case NodeAttrs::Phi: | |||
221 | OS << PrintNode<PhiNode*>(P.Obj, P.G); | |||
222 | break; | |||
223 | case NodeAttrs::Stmt: | |||
224 | OS << PrintNode<StmtNode*>(P.Obj, P.G); | |||
225 | break; | |||
226 | default: | |||
227 | OS << "instr? " << Print<NodeId>(P.Obj.Id, P.G); | |||
228 | break; | |||
229 | } | |||
230 | return OS; | |||
231 | } | |||
232 | ||||
233 | template<> | |||
234 | raw_ostream &operator<< (raw_ostream &OS, | |||
235 | const Print<NodeAddr<BlockNode*>> &P) { | |||
236 | auto *BB = P.Obj.Addr->getCode(); | |||
237 | unsigned NP = BB->pred_size(); | |||
238 | std::vector<int> Ns; | |||
239 | auto PrintBBs = [&OS,&P] (std::vector<int> Ns) -> void { | |||
240 | unsigned N = Ns.size(); | |||
241 | for (auto I : Ns) { | |||
242 | OS << "BB#" << I; | |||
243 | if (--N) | |||
244 | OS << ", "; | |||
245 | } | |||
246 | }; | |||
247 | ||||
248 | OS << Print<NodeId>(P.Obj.Id, P.G) << ": === BB#" << BB->getNumber() | |||
249 | << " === preds(" << NP << "): "; | |||
250 | for (auto I : BB->predecessors()) | |||
251 | Ns.push_back(I->getNumber()); | |||
252 | PrintBBs(Ns); | |||
253 | ||||
254 | unsigned NS = BB->succ_size(); | |||
255 | OS << " succs(" << NS << "): "; | |||
256 | Ns.clear(); | |||
257 | for (auto I : BB->successors()) | |||
258 | Ns.push_back(I->getNumber()); | |||
259 | PrintBBs(Ns); | |||
260 | OS << '\n'; | |||
261 | ||||
262 | for (auto I : P.Obj.Addr->members(P.G)) | |||
263 | OS << PrintNode<InstrNode*>(I, P.G) << '\n'; | |||
264 | return OS; | |||
265 | } | |||
266 | ||||
267 | template<> | |||
268 | raw_ostream &operator<< (raw_ostream &OS, | |||
269 | const Print<NodeAddr<FuncNode*>> &P) { | |||
270 | OS << "DFG dump:[\n" << Print<NodeId>(P.Obj.Id, P.G) << ": Function: " | |||
271 | << P.Obj.Addr->getCode()->getName() << '\n'; | |||
272 | for (auto I : P.Obj.Addr->members(P.G)) | |||
273 | OS << PrintNode<BlockNode*>(I, P.G) << '\n'; | |||
274 | OS << "]\n"; | |||
275 | return OS; | |||
276 | } | |||
277 | ||||
278 | template<> | |||
279 | raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) { | |||
280 | OS << '{'; | |||
281 | for (auto I : P.Obj) | |||
282 | OS << ' ' << Print<RegisterRef>(I, P.G); | |||
283 | OS << " }"; | |||
284 | return OS; | |||
285 | } | |||
286 | ||||
287 | template<> | |||
288 | raw_ostream &operator<< (raw_ostream &OS, | |||
289 | const Print<DataFlowGraph::DefStack> &P) { | |||
290 | for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) { | |||
291 | OS << Print<NodeId>(I->Id, P.G) | |||
292 | << '<' << Print<RegisterRef>(I->Addr->getRegRef(), P.G) << '>'; | |||
293 | I.down(); | |||
294 | if (I != E) | |||
295 | OS << ' '; | |||
296 | } | |||
297 | return OS; | |||
298 | } | |||
299 | ||||
300 | } // namespace rdf | |||
301 | ||||
302 | // Node allocation functions. | |||
303 | // | |||
304 | // Node allocator is like a slab memory allocator: it allocates blocks of | |||
305 | // memory in sizes that are multiples of the size of a node. Each block has | |||
306 | // the same size. Nodes are allocated from the currently active block, and | |||
307 | // when it becomes full, a new one is created. | |||
308 | // There is a mapping scheme between node id and its location in a block, | |||
309 | // and within that block is described in the header file. | |||
310 | // | |||
311 | void NodeAllocator::startNewBlock() { | |||
312 | void *T = MemPool.Allocate(NodesPerBlock*NodeMemSize, NodeMemSize); | |||
313 | char *P = static_cast<char*>(T); | |||
314 | Blocks.push_back(P); | |||
315 | // Check if the block index is still within the allowed range, i.e. less | |||
316 | // than 2^N, where N is the number of bits in NodeId for the block index. | |||
317 | // BitsPerIndex is the number of bits per node index. | |||
318 | assert((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) &&(((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex ))) && "Out of bits for block index") ? static_cast< void> (0) : __assert_fail ("(Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) && \"Out of bits for block index\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 319, __PRETTY_FUNCTION__)) | |||
319 | "Out of bits for block index")(((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex ))) && "Out of bits for block index") ? static_cast< void> (0) : __assert_fail ("(Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) && \"Out of bits for block index\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 319, __PRETTY_FUNCTION__)); | |||
320 | ActiveEnd = P; | |||
321 | } | |||
322 | ||||
323 | bool NodeAllocator::needNewBlock() { | |||
324 | if (Blocks.empty()) | |||
325 | return true; | |||
326 | ||||
327 | char *ActiveBegin = Blocks.back(); | |||
328 | uint32_t Index = (ActiveEnd-ActiveBegin)/NodeMemSize; | |||
329 | return Index >= NodesPerBlock; | |||
330 | } | |||
331 | ||||
332 | NodeAddr<NodeBase*> NodeAllocator::New() { | |||
333 | if (needNewBlock()) | |||
334 | startNewBlock(); | |||
335 | ||||
336 | uint32_t ActiveB = Blocks.size()-1; | |||
337 | uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize; | |||
338 | NodeAddr<NodeBase*> NA = { reinterpret_cast<NodeBase*>(ActiveEnd), | |||
339 | makeId(ActiveB, Index) }; | |||
340 | ActiveEnd += NodeMemSize; | |||
341 | return NA; | |||
342 | } | |||
343 | ||||
344 | NodeId NodeAllocator::id(const NodeBase *P) const { | |||
345 | uintptr_t A = reinterpret_cast<uintptr_t>(P); | |||
346 | for (unsigned i = 0, n = Blocks.size(); i != n; ++i) { | |||
347 | uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]); | |||
348 | if (A < B || A >= B + NodesPerBlock*NodeMemSize) | |||
349 | continue; | |||
350 | uint32_t Idx = (A-B)/NodeMemSize; | |||
351 | return makeId(i, Idx); | |||
352 | } | |||
353 | llvm_unreachable("Invalid node address")::llvm::llvm_unreachable_internal("Invalid node address", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 353); | |||
354 | } | |||
355 | ||||
356 | void NodeAllocator::clear() { | |||
357 | MemPool.Reset(); | |||
358 | Blocks.clear(); | |||
359 | ActiveEnd = nullptr; | |||
360 | } | |||
361 | ||||
362 | ||||
363 | // Insert node NA after "this" in the circular chain. | |||
364 | void NodeBase::append(NodeAddr<NodeBase*> NA) { | |||
365 | NodeId Nx = Next; | |||
366 | // If NA is already "next", do nothing. | |||
367 | if (Next != NA.Id) { | |||
368 | Next = NA.Id; | |||
369 | NA.Addr->Next = Nx; | |||
370 | } | |||
371 | } | |||
372 | ||||
373 | ||||
374 | // Fundamental node manipulator functions. | |||
375 | ||||
376 | // Obtain the register reference from a reference node. | |||
377 | RegisterRef RefNode::getRegRef() const { | |||
378 | assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref)((NodeAttrs::type(Attrs) == NodeAttrs::Ref) ? static_cast< void> (0) : __assert_fail ("NodeAttrs::type(Attrs) == NodeAttrs::Ref" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 378, __PRETTY_FUNCTION__)); | |||
379 | if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef) | |||
380 | return Ref.RR; | |||
381 | assert(Ref.Op != nullptr)((Ref.Op != nullptr) ? static_cast<void> (0) : __assert_fail ("Ref.Op != nullptr", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 381, __PRETTY_FUNCTION__)); | |||
382 | return { Ref.Op->getReg(), Ref.Op->getSubReg() }; | |||
383 | } | |||
384 | ||||
385 | // Set the register reference in the reference node directly (for references | |||
386 | // in phi nodes). | |||
387 | void RefNode::setRegRef(RegisterRef RR) { | |||
388 | assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref)((NodeAttrs::type(Attrs) == NodeAttrs::Ref) ? static_cast< void> (0) : __assert_fail ("NodeAttrs::type(Attrs) == NodeAttrs::Ref" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 388, __PRETTY_FUNCTION__)); | |||
389 | assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)((NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef) ? static_cast <void> (0) : __assert_fail ("NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 389, __PRETTY_FUNCTION__)); | |||
390 | Ref.RR = RR; | |||
391 | } | |||
392 | ||||
393 | // Set the register reference in the reference node based on a machine | |||
394 | // operand (for references in statement nodes). | |||
395 | void RefNode::setRegRef(MachineOperand *Op) { | |||
396 | assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref)((NodeAttrs::type(Attrs) == NodeAttrs::Ref) ? static_cast< void> (0) : __assert_fail ("NodeAttrs::type(Attrs) == NodeAttrs::Ref" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 396, __PRETTY_FUNCTION__)); | |||
397 | assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef))((!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)) ? static_cast <void> (0) : __assert_fail ("!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 397, __PRETTY_FUNCTION__)); | |||
398 | Ref.Op = Op; | |||
399 | } | |||
400 | ||||
401 | // Get the owner of a given reference node. | |||
402 | NodeAddr<NodeBase*> RefNode::getOwner(const DataFlowGraph &G) { | |||
403 | NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); | |||
404 | ||||
405 | while (NA.Addr != this) { | |||
406 | if (NA.Addr->getType() == NodeAttrs::Code) | |||
407 | return NA; | |||
408 | NA = G.addr<NodeBase*>(NA.Addr->getNext()); | |||
409 | } | |||
410 | llvm_unreachable("No owner in circular list")::llvm::llvm_unreachable_internal("No owner in circular list" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 410); | |||
411 | } | |||
412 | ||||
413 | // Connect the def node to the reaching def node. | |||
414 | void DefNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { | |||
415 | Ref.RD = DA.Id; | |||
416 | Ref.Sib = DA.Addr->getReachedDef(); | |||
417 | DA.Addr->setReachedDef(Self); | |||
418 | } | |||
419 | ||||
420 | // Connect the use node to the reaching def node. | |||
421 | void UseNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { | |||
422 | Ref.RD = DA.Id; | |||
423 | Ref.Sib = DA.Addr->getReachedUse(); | |||
424 | DA.Addr->setReachedUse(Self); | |||
425 | } | |||
426 | ||||
427 | // Get the first member of the code node. | |||
428 | NodeAddr<NodeBase*> CodeNode::getFirstMember(const DataFlowGraph &G) const { | |||
429 | if (Code.FirstM == 0) | |||
430 | return NodeAddr<NodeBase*>(); | |||
431 | return G.addr<NodeBase*>(Code.FirstM); | |||
432 | } | |||
433 | ||||
434 | // Get the last member of the code node. | |||
435 | NodeAddr<NodeBase*> CodeNode::getLastMember(const DataFlowGraph &G) const { | |||
436 | if (Code.LastM == 0) | |||
437 | return NodeAddr<NodeBase*>(); | |||
438 | return G.addr<NodeBase*>(Code.LastM); | |||
439 | } | |||
440 | ||||
441 | // Add node NA at the end of the member list of the given code node. | |||
442 | void CodeNode::addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { | |||
443 | auto ML = getLastMember(G); | |||
444 | if (ML.Id != 0) { | |||
445 | ML.Addr->append(NA); | |||
446 | } else { | |||
447 | Code.FirstM = NA.Id; | |||
448 | NodeId Self = G.id(this); | |||
449 | NA.Addr->setNext(Self); | |||
450 | } | |||
451 | Code.LastM = NA.Id; | |||
452 | } | |||
453 | ||||
454 | // Add node NA after member node MA in the given code node. | |||
455 | void CodeNode::addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA, | |||
456 | const DataFlowGraph &G) { | |||
457 | MA.Addr->append(NA); | |||
458 | if (Code.LastM == MA.Id) | |||
459 | Code.LastM = NA.Id; | |||
460 | } | |||
461 | ||||
462 | // Remove member node NA from the given code node. | |||
463 | void CodeNode::removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { | |||
464 | auto MA = getFirstMember(G); | |||
465 | assert(MA.Id != 0)((MA.Id != 0) ? static_cast<void> (0) : __assert_fail ( "MA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 465, __PRETTY_FUNCTION__)); | |||
466 | ||||
467 | // Special handling if the member to remove is the first member. | |||
468 | if (MA.Id == NA.Id) { | |||
469 | if (Code.LastM == MA.Id) { | |||
470 | // If it is the only member, set both first and last to 0. | |||
471 | Code.FirstM = Code.LastM = 0; | |||
472 | } else { | |||
473 | // Otherwise, advance the first member. | |||
474 | Code.FirstM = MA.Addr->getNext(); | |||
475 | } | |||
476 | return; | |||
477 | } | |||
478 | ||||
479 | while (MA.Addr != this) { | |||
480 | NodeId MX = MA.Addr->getNext(); | |||
481 | if (MX == NA.Id) { | |||
482 | MA.Addr->setNext(NA.Addr->getNext()); | |||
483 | // If the member to remove happens to be the last one, update the | |||
484 | // LastM indicator. | |||
485 | if (Code.LastM == NA.Id) | |||
486 | Code.LastM = MA.Id; | |||
487 | return; | |||
488 | } | |||
489 | MA = G.addr<NodeBase*>(MX); | |||
490 | } | |||
491 | llvm_unreachable("No such member")::llvm::llvm_unreachable_internal("No such member", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 491); | |||
492 | } | |||
493 | ||||
494 | // Return the list of all members of the code node. | |||
495 | NodeList CodeNode::members(const DataFlowGraph &G) const { | |||
496 | static auto True = [] (NodeAddr<NodeBase*>) -> bool { return true; }; | |||
497 | return members_if(True, G); | |||
498 | } | |||
499 | ||||
500 | // Return the owner of the given instr node. | |||
501 | NodeAddr<NodeBase*> InstrNode::getOwner(const DataFlowGraph &G) { | |||
502 | NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); | |||
503 | ||||
504 | while (NA.Addr != this) { | |||
505 | assert(NA.Addr->getType() == NodeAttrs::Code)((NA.Addr->getType() == NodeAttrs::Code) ? static_cast< void> (0) : __assert_fail ("NA.Addr->getType() == NodeAttrs::Code" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 505, __PRETTY_FUNCTION__)); | |||
506 | if (NA.Addr->getKind() == NodeAttrs::Block) | |||
507 | return NA; | |||
508 | NA = G.addr<NodeBase*>(NA.Addr->getNext()); | |||
509 | } | |||
510 | llvm_unreachable("No owner in circular list")::llvm::llvm_unreachable_internal("No owner in circular list" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 510); | |||
511 | } | |||
512 | ||||
513 | // Add the phi node PA to the given block node. | |||
514 | void BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G) { | |||
515 | auto M = getFirstMember(G); | |||
516 | if (M.Id == 0) { | |||
517 | addMember(PA, G); | |||
518 | return; | |||
519 | } | |||
520 | ||||
521 | assert(M.Addr->getType() == NodeAttrs::Code)((M.Addr->getType() == NodeAttrs::Code) ? static_cast<void > (0) : __assert_fail ("M.Addr->getType() == NodeAttrs::Code" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 521, __PRETTY_FUNCTION__)); | |||
522 | if (M.Addr->getKind() == NodeAttrs::Stmt) { | |||
523 | // If the first member of the block is a statement, insert the phi as | |||
524 | // the first member. | |||
525 | Code.FirstM = PA.Id; | |||
526 | PA.Addr->setNext(M.Id); | |||
527 | } else { | |||
528 | // If the first member is a phi, find the last phi, and append PA to it. | |||
529 | assert(M.Addr->getKind() == NodeAttrs::Phi)((M.Addr->getKind() == NodeAttrs::Phi) ? static_cast<void > (0) : __assert_fail ("M.Addr->getKind() == NodeAttrs::Phi" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 529, __PRETTY_FUNCTION__)); | |||
530 | NodeAddr<NodeBase*> MN = M; | |||
531 | do { | |||
532 | M = MN; | |||
533 | MN = G.addr<NodeBase*>(M.Addr->getNext()); | |||
534 | assert(MN.Addr->getType() == NodeAttrs::Code)((MN.Addr->getType() == NodeAttrs::Code) ? static_cast< void> (0) : __assert_fail ("MN.Addr->getType() == NodeAttrs::Code" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 534, __PRETTY_FUNCTION__)); | |||
535 | } while (MN.Addr->getKind() == NodeAttrs::Phi); | |||
536 | ||||
537 | // M is the last phi. | |||
538 | addMemberAfter(M, PA, G); | |||
539 | } | |||
540 | } | |||
541 | ||||
542 | // Find the block node corresponding to the machine basic block BB in the | |||
543 | // given func node. | |||
544 | NodeAddr<BlockNode*> FuncNode::findBlock(const MachineBasicBlock *BB, | |||
545 | const DataFlowGraph &G) const { | |||
546 | auto EqBB = [BB] (NodeAddr<NodeBase*> NA) -> bool { | |||
547 | return NodeAddr<BlockNode*>(NA).Addr->getCode() == BB; | |||
548 | }; | |||
549 | NodeList Ms = members_if(EqBB, G); | |||
550 | if (!Ms.empty()) | |||
551 | return Ms[0]; | |||
552 | return NodeAddr<BlockNode*>(); | |||
553 | } | |||
554 | ||||
555 | // Get the block node for the entry block in the given function. | |||
556 | NodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) { | |||
557 | MachineBasicBlock *EntryB = &getCode()->front(); | |||
558 | return findBlock(EntryB, G); | |||
559 | } | |||
560 | ||||
561 | ||||
562 | // Register aliasing information. | |||
563 | // | |||
564 | // In theory, the lane information could be used to determine register | |||
565 | // covering (and aliasing), but depending on the sub-register structure, | |||
566 | // the lane mask information may be missing. The covering information | |||
567 | // must be available for this framework to work, so relying solely on | |||
568 | // the lane data is not sufficient. | |||
569 | ||||
570 | // Determine whether RA covers RB. | |||
571 | bool RegisterAliasInfo::covers(RegisterRef RA, RegisterRef RB) const { | |||
572 | if (RA == RB) | |||
573 | return true; | |||
574 | if (TargetRegisterInfo::isVirtualRegister(RA.Reg)) { | |||
575 | assert(TargetRegisterInfo::isVirtualRegister(RB.Reg))((TargetRegisterInfo::isVirtualRegister(RB.Reg)) ? static_cast <void> (0) : __assert_fail ("TargetRegisterInfo::isVirtualRegister(RB.Reg)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 575, __PRETTY_FUNCTION__)); | |||
576 | if (RA.Reg != RB.Reg) | |||
577 | return false; | |||
578 | if (RA.Sub == 0) | |||
579 | return true; | |||
580 | return TRI.composeSubRegIndices(RA.Sub, RB.Sub) == RA.Sub; | |||
581 | } | |||
582 | ||||
583 | assert(TargetRegisterInfo::isPhysicalRegister(RA.Reg) &&((TargetRegisterInfo::isPhysicalRegister(RA.Reg) && TargetRegisterInfo ::isPhysicalRegister(RB.Reg)) ? static_cast<void> (0) : __assert_fail ("TargetRegisterInfo::isPhysicalRegister(RA.Reg) && TargetRegisterInfo::isPhysicalRegister(RB.Reg)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 584, __PRETTY_FUNCTION__)) | |||
584 | TargetRegisterInfo::isPhysicalRegister(RB.Reg))((TargetRegisterInfo::isPhysicalRegister(RA.Reg) && TargetRegisterInfo ::isPhysicalRegister(RB.Reg)) ? static_cast<void> (0) : __assert_fail ("TargetRegisterInfo::isPhysicalRegister(RA.Reg) && TargetRegisterInfo::isPhysicalRegister(RB.Reg)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 584, __PRETTY_FUNCTION__)); | |||
585 | unsigned A = RA.Sub != 0 ? TRI.getSubReg(RA.Reg, RA.Sub) : RA.Reg; | |||
586 | unsigned B = RB.Sub != 0 ? TRI.getSubReg(RB.Reg, RB.Sub) : RB.Reg; | |||
587 | return TRI.isSubRegister(A, B); | |||
588 | } | |||
589 | ||||
590 | // Determine whether RR is covered by the set of references RRs. | |||
591 | bool RegisterAliasInfo::covers(const RegisterSet &RRs, RegisterRef RR) const { | |||
592 | if (RRs.count(RR)) | |||
593 | return true; | |||
594 | ||||
595 | // For virtual registers, we cannot accurately determine covering based | |||
596 | // on subregisters. If RR itself is not present in RRs, but it has a sub- | |||
597 | // register reference, check for the super-register alone. Otherwise, | |||
598 | // assume non-covering. | |||
599 | if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) { | |||
600 | if (RR.Sub != 0) | |||
601 | return RRs.count({RR.Reg, 0}); | |||
602 | return false; | |||
603 | } | |||
604 | ||||
605 | // If any super-register of RR is present, then RR is covered. | |||
606 | unsigned Reg = RR.Sub == 0 ? RR.Reg : TRI.getSubReg(RR.Reg, RR.Sub); | |||
607 | for (MCSuperRegIterator SR(Reg, &TRI); SR.isValid(); ++SR) | |||
608 | if (RRs.count({*SR, 0})) | |||
609 | return true; | |||
610 | ||||
611 | return false; | |||
612 | } | |||
613 | ||||
614 | // Get the list of references aliased to RR. | |||
615 | std::vector<RegisterRef> RegisterAliasInfo::getAliasSet(RegisterRef RR) const { | |||
616 | // Do not include RR in the alias set. For virtual registers return an | |||
617 | // empty set. | |||
618 | std::vector<RegisterRef> AS; | |||
619 | if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) | |||
620 | return AS; | |||
621 | assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg))((TargetRegisterInfo::isPhysicalRegister(RR.Reg)) ? static_cast <void> (0) : __assert_fail ("TargetRegisterInfo::isPhysicalRegister(RR.Reg)" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 621, __PRETTY_FUNCTION__)); | |||
622 | unsigned R = RR.Reg; | |||
623 | if (RR.Sub) | |||
624 | R = TRI.getSubReg(RR.Reg, RR.Sub); | |||
625 | ||||
626 | for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) | |||
627 | AS.push_back(RegisterRef({*AI, 0})); | |||
628 | return AS; | |||
629 | } | |||
630 | ||||
631 | // Check whether RA and RB are aliased. | |||
632 | bool RegisterAliasInfo::alias(RegisterRef RA, RegisterRef RB) const { | |||
633 | bool VirtA = TargetRegisterInfo::isVirtualRegister(RA.Reg); | |||
634 | bool VirtB = TargetRegisterInfo::isVirtualRegister(RB.Reg); | |||
635 | bool PhysA = TargetRegisterInfo::isPhysicalRegister(RA.Reg); | |||
636 | bool PhysB = TargetRegisterInfo::isPhysicalRegister(RB.Reg); | |||
637 | ||||
638 | if (VirtA != VirtB) | |||
639 | return false; | |||
640 | ||||
641 | if (VirtA) { | |||
642 | if (RA.Reg != RB.Reg) | |||
643 | return false; | |||
644 | // RA and RB refer to the same register. If any of them refer to the | |||
645 | // whole register, they must be aliased. | |||
646 | if (RA.Sub == 0 || RB.Sub == 0) | |||
647 | return true; | |||
648 | unsigned SA = TRI.getSubRegIdxSize(RA.Sub); | |||
649 | unsigned OA = TRI.getSubRegIdxOffset(RA.Sub); | |||
650 | unsigned SB = TRI.getSubRegIdxSize(RB.Sub); | |||
651 | unsigned OB = TRI.getSubRegIdxOffset(RB.Sub); | |||
652 | if (OA <= OB && OA+SA > OB) | |||
653 | return true; | |||
654 | if (OB <= OA && OB+SB > OA) | |||
655 | return true; | |||
656 | return false; | |||
657 | } | |||
658 | ||||
659 | assert(PhysA && PhysB)((PhysA && PhysB) ? static_cast<void> (0) : __assert_fail ("PhysA && PhysB", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 659, __PRETTY_FUNCTION__)); | |||
660 | (void)PhysA, (void)PhysB; | |||
661 | unsigned A = RA.Sub ? TRI.getSubReg(RA.Reg, RA.Sub) : RA.Reg; | |||
662 | unsigned B = RB.Sub ? TRI.getSubReg(RB.Reg, RB.Sub) : RB.Reg; | |||
663 | for (MCRegAliasIterator I(A, &TRI, true); I.isValid(); ++I) | |||
664 | if (B == *I) | |||
665 | return true; | |||
666 | return false; | |||
667 | } | |||
668 | ||||
669 | ||||
670 | // Target operand information. | |||
671 | // | |||
672 | ||||
673 | // For a given instruction, check if there are any bits of RR that can remain | |||
674 | // unchanged across this def. | |||
675 | bool TargetOperandInfo::isPreserving(const MachineInstr &In, unsigned OpNum) | |||
676 | const { | |||
677 | return TII.isPredicated(In); | |||
678 | } | |||
679 | ||||
680 | // Check if the definition of RR produces an unspecified value. | |||
681 | bool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum) | |||
682 | const { | |||
683 | if (In.isCall()) | |||
684 | if (In.getOperand(OpNum).isImplicit()) | |||
685 | return true; | |||
686 | return false; | |||
687 | } | |||
688 | ||||
689 | // Check if the given instruction specifically requires | |||
690 | bool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum) | |||
691 | const { | |||
692 | if (In.isCall() || In.isReturn()) | |||
693 | return true; | |||
694 | const MCInstrDesc &D = In.getDesc(); | |||
695 | if (!D.getImplicitDefs() && !D.getImplicitUses()) | |||
696 | return false; | |||
697 | const MachineOperand &Op = In.getOperand(OpNum); | |||
698 | // If there is a sub-register, treat the operand as non-fixed. Currently, | |||
699 | // fixed registers are those that are listed in the descriptor as implicit | |||
700 | // uses or defs, and those lists do not allow sub-registers. | |||
701 | if (Op.getSubReg() != 0) | |||
702 | return false; | |||
703 | unsigned Reg = Op.getReg(); | |||
704 | const MCPhysReg *ImpR = Op.isDef() ? D.getImplicitDefs() | |||
705 | : D.getImplicitUses(); | |||
706 | if (!ImpR) | |||
707 | return false; | |||
708 | while (*ImpR) | |||
709 | if (*ImpR++ == Reg) | |||
710 | return true; | |||
711 | return false; | |||
712 | } | |||
713 | ||||
714 | ||||
715 | // | |||
716 | // The data flow graph construction. | |||
717 | // | |||
718 | ||||
719 | DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, | |||
720 | const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, | |||
721 | const MachineDominanceFrontier &mdf, const RegisterAliasInfo &rai, | |||
722 | const TargetOperandInfo &toi) | |||
723 | : TimeG("rdf"), MF(mf), TII(tii), TRI(tri), MDT(mdt), MDF(mdf), RAI(rai), | |||
724 | TOI(toi) { | |||
725 | } | |||
726 | ||||
727 | ||||
728 | // The implementation of the definition stack. | |||
729 | // Each register reference has its own definition stack. In particular, | |||
730 | // for a register references "Reg" and "Reg:subreg" will each have their | |||
731 | // own definition stacks. | |||
732 | ||||
733 | // Construct a stack iterator. | |||
734 | DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S, | |||
735 | bool Top) : DS(S) { | |||
736 | if (!Top) { | |||
737 | // Initialize to bottom. | |||
738 | Pos = 0; | |||
739 | return; | |||
740 | } | |||
741 | // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty). | |||
742 | Pos = DS.Stack.size(); | |||
743 | while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos-1])) | |||
744 | Pos--; | |||
745 | } | |||
746 | ||||
747 | // Return the size of the stack, including block delimiters. | |||
748 | unsigned DataFlowGraph::DefStack::size() const { | |||
749 | unsigned S = 0; | |||
750 | for (auto I = top(), E = bottom(); I != E; I.down()) | |||
751 | S++; | |||
752 | return S; | |||
753 | } | |||
754 | ||||
755 | // Remove the top entry from the stack. Remove all intervening delimiters | |||
756 | // so that after this, the stack is either empty, or the top of the stack | |||
757 | // is a non-delimiter. | |||
758 | void DataFlowGraph::DefStack::pop() { | |||
759 | assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 759, __PRETTY_FUNCTION__)); | |||
760 | unsigned P = nextDown(Stack.size()); | |||
761 | Stack.resize(P); | |||
762 | } | |||
763 | ||||
764 | // Push a delimiter for block node N on the stack. | |||
765 | void DataFlowGraph::DefStack::start_block(NodeId N) { | |||
766 | assert(N != 0)((N != 0) ? static_cast<void> (0) : __assert_fail ("N != 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 766, __PRETTY_FUNCTION__)); | |||
767 | Stack.push_back(NodeAddr<DefNode*>(nullptr, N)); | |||
768 | } | |||
769 | ||||
770 | // Remove all nodes from the top of the stack, until the delimited for | |||
771 | // block node N is encountered. Remove the delimiter as well. In effect, | |||
772 | // this will remove from the stack all definitions from block N. | |||
773 | void DataFlowGraph::DefStack::clear_block(NodeId N) { | |||
774 | assert(N != 0)((N != 0) ? static_cast<void> (0) : __assert_fail ("N != 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 774, __PRETTY_FUNCTION__)); | |||
775 | unsigned P = Stack.size(); | |||
776 | while (P > 0) { | |||
777 | bool Found = isDelimiter(Stack[P-1], N); | |||
778 | P--; | |||
779 | if (Found) | |||
780 | break; | |||
781 | } | |||
782 | // This will also remove the delimiter, if found. | |||
783 | Stack.resize(P); | |||
784 | } | |||
785 | ||||
786 | // Move the stack iterator up by one. | |||
787 | unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const { | |||
788 | // Get the next valid position after P (skipping all delimiters). | |||
789 | // The input position P does not have to point to a non-delimiter. | |||
790 | unsigned SS = Stack.size(); | |||
791 | bool IsDelim; | |||
792 | assert(P < SS)((P < SS) ? static_cast<void> (0) : __assert_fail ("P < SS" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 792, __PRETTY_FUNCTION__)); | |||
793 | do { | |||
794 | P++; | |||
795 | IsDelim = isDelimiter(Stack[P-1]); | |||
796 | } while (P < SS && IsDelim); | |||
797 | assert(!IsDelim)((!IsDelim) ? static_cast<void> (0) : __assert_fail ("!IsDelim" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 797, __PRETTY_FUNCTION__)); | |||
798 | return P; | |||
799 | } | |||
800 | ||||
801 | // Move the stack iterator down by one. | |||
802 | unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { | |||
803 | // Get the preceding valid position before P (skipping all delimiters). | |||
804 | // The input position P does not have to point to a non-delimiter. | |||
805 | assert(P > 0 && P <= Stack.size())((P > 0 && P <= Stack.size()) ? static_cast< void> (0) : __assert_fail ("P > 0 && P <= Stack.size()" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 805, __PRETTY_FUNCTION__)); | |||
806 | bool IsDelim = isDelimiter(Stack[P-1]); | |||
807 | do { | |||
808 | if (--P == 0) | |||
809 | break; | |||
810 | IsDelim = isDelimiter(Stack[P-1]); | |||
811 | } while (P > 0 && IsDelim); | |||
812 | assert(!IsDelim)((!IsDelim) ? static_cast<void> (0) : __assert_fail ("!IsDelim" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 812, __PRETTY_FUNCTION__)); | |||
813 | return P; | |||
814 | } | |||
815 | ||||
816 | // Node management functions. | |||
817 | ||||
818 | // Get the pointer to the node with the id N. | |||
819 | NodeBase *DataFlowGraph::ptr(NodeId N) const { | |||
820 | if (N == 0) | |||
821 | return nullptr; | |||
822 | return Memory.ptr(N); | |||
823 | } | |||
824 | ||||
825 | // Get the id of the node at the address P. | |||
826 | NodeId DataFlowGraph::id(const NodeBase *P) const { | |||
827 | if (P == nullptr) | |||
828 | return 0; | |||
829 | return Memory.id(P); | |||
830 | } | |||
831 | ||||
832 | // Allocate a new node and set the attributes to Attrs. | |||
833 | NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) { | |||
834 | NodeAddr<NodeBase*> P = Memory.New(); | |||
835 | P.Addr->init(); | |||
836 | P.Addr->setAttrs(Attrs); | |||
837 | return P; | |||
838 | } | |||
839 | ||||
840 | // Make a copy of the given node B, except for the data-flow links, which | |||
841 | // are set to 0. | |||
842 | NodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) { | |||
843 | NodeAddr<NodeBase*> NA = newNode(0); | |||
844 | memcpy(NA.Addr, B.Addr, sizeof(NodeBase)); | |||
845 | // Ref nodes need to have the data-flow links reset. | |||
846 | if (NA.Addr->getType() == NodeAttrs::Ref) { | |||
847 | NodeAddr<RefNode*> RA = NA; | |||
848 | RA.Addr->setReachingDef(0); | |||
849 | RA.Addr->setSibling(0); | |||
850 | if (NA.Addr->getKind() == NodeAttrs::Def) { | |||
851 | NodeAddr<DefNode*> DA = NA; | |||
852 | DA.Addr->setReachedDef(0); | |||
853 | DA.Addr->setReachedUse(0); | |||
854 | } | |||
855 | } | |||
856 | return NA; | |||
857 | } | |||
858 | ||||
859 | ||||
860 | // Allocation routines for specific node types/kinds. | |||
861 | ||||
862 | NodeAddr<UseNode*> DataFlowGraph::newUse(NodeAddr<InstrNode*> Owner, | |||
863 | MachineOperand &Op, uint16_t Flags) { | |||
864 | NodeAddr<UseNode*> UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); | |||
865 | UA.Addr->setRegRef(&Op); | |||
866 | return UA; | |||
867 | } | |||
868 | ||||
869 | NodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner, | |||
870 | RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) { | |||
871 | NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); | |||
872 | assert(Flags & NodeAttrs::PhiRef)((Flags & NodeAttrs::PhiRef) ? static_cast<void> (0 ) : __assert_fail ("Flags & NodeAttrs::PhiRef", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 872, __PRETTY_FUNCTION__)); | |||
873 | PUA.Addr->setRegRef(RR); | |||
874 | PUA.Addr->setPredecessor(PredB.Id); | |||
875 | return PUA; | |||
876 | } | |||
877 | ||||
878 | NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, | |||
879 | MachineOperand &Op, uint16_t Flags) { | |||
880 | NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); | |||
881 | DA.Addr->setRegRef(&Op); | |||
882 | return DA; | |||
883 | } | |||
884 | ||||
885 | NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, | |||
886 | RegisterRef RR, uint16_t Flags) { | |||
887 | NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); | |||
888 | assert(Flags & NodeAttrs::PhiRef)((Flags & NodeAttrs::PhiRef) ? static_cast<void> (0 ) : __assert_fail ("Flags & NodeAttrs::PhiRef", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 888, __PRETTY_FUNCTION__)); | |||
889 | DA.Addr->setRegRef(RR); | |||
890 | return DA; | |||
891 | } | |||
892 | ||||
893 | NodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) { | |||
894 | NodeAddr<PhiNode*> PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); | |||
895 | Owner.Addr->addPhi(PA, *this); | |||
896 | return PA; | |||
897 | } | |||
898 | ||||
899 | NodeAddr<StmtNode*> DataFlowGraph::newStmt(NodeAddr<BlockNode*> Owner, | |||
900 | MachineInstr *MI) { | |||
901 | NodeAddr<StmtNode*> SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt); | |||
902 | SA.Addr->setCode(MI); | |||
903 | Owner.Addr->addMember(SA, *this); | |||
904 | return SA; | |||
905 | } | |||
906 | ||||
907 | NodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner, | |||
908 | MachineBasicBlock *BB) { | |||
909 | NodeAddr<BlockNode*> BA = newNode(NodeAttrs::Code | NodeAttrs::Block); | |||
910 | BA.Addr->setCode(BB); | |||
911 | Owner.Addr->addMember(BA, *this); | |||
912 | return BA; | |||
913 | } | |||
914 | ||||
915 | NodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) { | |||
916 | NodeAddr<FuncNode*> FA = newNode(NodeAttrs::Code | NodeAttrs::Func); | |||
917 | FA.Addr->setCode(MF); | |||
918 | return FA; | |||
919 | } | |||
920 | ||||
921 | // Build the data flow graph. | |||
922 | void DataFlowGraph::build() { | |||
923 | reset(); | |||
924 | Func = newFunc(&MF); | |||
925 | ||||
926 | if (MF.empty()) | |||
| ||||
927 | return; | |||
928 | ||||
929 | for (auto &B : MF) { | |||
930 | auto BA = newBlock(Func, &B); | |||
931 | for (auto &I : B) { | |||
932 | if (I.isDebugValue()) | |||
933 | continue; | |||
934 | buildStmt(BA, I); | |||
935 | } | |||
936 | } | |||
937 | ||||
938 | // Collect information about block references. | |||
939 | NodeAddr<BlockNode*> EA = Func.Addr->getEntryBlock(*this); | |||
940 | BlockRefsMap RefM; | |||
941 | buildBlockRefs(EA, RefM); | |||
942 | ||||
943 | // Add function-entry phi nodes. | |||
944 | MachineRegisterInfo &MRI = MF.getRegInfo(); | |||
945 | for (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I) { | |||
946 | NodeAddr<PhiNode*> PA = newPhi(EA); | |||
947 | RegisterRef RR = { I->first, 0 }; | |||
948 | uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; | |||
949 | NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); | |||
950 | PA.Addr->addMember(DA, *this); | |||
951 | } | |||
952 | ||||
953 | // Build a map "PhiM" which will contain, for each block, the set | |||
954 | // of references that will require phi definitions in that block. | |||
955 | BlockRefsMap PhiM; | |||
956 | auto Blocks = Func.Addr->members(*this); | |||
957 | for (NodeAddr<BlockNode*> BA : Blocks) | |||
958 | recordDefsForDF(PhiM, RefM, BA); | |||
959 | for (NodeAddr<BlockNode*> BA : Blocks) | |||
960 | buildPhis(PhiM, RefM, BA); | |||
961 | ||||
962 | // Link all the refs. This will recursively traverse the dominator tree. | |||
963 | DefStackMap DM; | |||
964 | linkBlockRefs(DM, EA); | |||
965 | ||||
966 | // Finally, remove all unused phi nodes. | |||
967 | removeUnusedPhis(); | |||
968 | } | |||
969 | ||||
970 | // For each stack in the map DefM, push the delimiter for block B on it. | |||
971 | void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) { | |||
972 | // Push block delimiters. | |||
973 | for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) | |||
974 | I->second.start_block(B); | |||
975 | } | |||
976 | ||||
977 | // Remove all definitions coming from block B from each stack in DefM. | |||
978 | void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { | |||
979 | // Pop all defs from this block from the definition stack. Defs that were | |||
980 | // added to the map during the traversal of instructions will not have a | |||
981 | // delimiter, but for those, the whole stack will be emptied. | |||
982 | for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) | |||
983 | I->second.clear_block(B); | |||
984 | ||||
985 | // Finally, remove empty stacks from the map. | |||
986 | for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) { | |||
987 | NextI = std::next(I); | |||
988 | // This preserves the validity of iterators other than I. | |||
989 | if (I->second.empty()) | |||
990 | DefM.erase(I); | |||
991 | } | |||
992 | } | |||
993 | ||||
994 | // Push all definitions from the instruction node IA to an appropriate | |||
995 | // stack in DefM. | |||
996 | void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { | |||
997 | NodeList Defs = IA.Addr->members_if(IsDef, *this); | |||
998 | NodeSet Visited; | |||
999 | #ifndef NDEBUG | |||
1000 | RegisterSet Defined; | |||
1001 | #endif | |||
1002 | ||||
1003 | // The important objectives of this function are: | |||
1004 | // - to be able to handle instructions both while the graph is being | |||
1005 | // constructed, and after the graph has been constructed, and | |||
1006 | // - maintain proper ordering of definitions on the stack for each | |||
1007 | // register reference: | |||
1008 | // - if there are two or more related defs in IA (i.e. coming from | |||
1009 | // the same machine operand), then only push one def on the stack, | |||
1010 | // - if there are multiple unrelated defs of non-overlapping | |||
1011 | // subregisters of S, then the stack for S will have both (in an | |||
1012 | // unspecified order), but the order does not matter from the data- | |||
1013 | // -flow perspective. | |||
1014 | ||||
1015 | for (NodeAddr<DefNode*> DA : Defs) { | |||
1016 | if (Visited.count(DA.Id)) | |||
1017 | continue; | |||
1018 | NodeList Rel = getRelatedRefs(IA, DA); | |||
1019 | NodeAddr<DefNode*> PDA = Rel.front(); | |||
1020 | // Push the definition on the stack for the register and all aliases. | |||
1021 | RegisterRef RR = PDA.Addr->getRegRef(); | |||
1022 | #ifndef NDEBUG | |||
1023 | // Assert if the register is defined in two or more unrelated defs. | |||
1024 | // This could happen if there are two or more def operands defining it. | |||
1025 | if (!Defined.insert(RR).second) { | |||
1026 | auto *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); | |||
1027 | dbgs() << "Multiple definitions of register: " | |||
1028 | << Print<RegisterRef>(RR, *this) << " in\n " << *MI | |||
1029 | << "in BB#" << MI->getParent()->getNumber() << '\n'; | |||
1030 | llvm_unreachable(nullptr)::llvm::llvm_unreachable_internal(nullptr, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1030); | |||
1031 | } | |||
1032 | #endif | |||
1033 | DefM[RR].push(DA); | |||
1034 | for (auto A : RAI.getAliasSet(RR)) { | |||
1035 | assert(A != RR)((A != RR) ? static_cast<void> (0) : __assert_fail ("A != RR" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1035, __PRETTY_FUNCTION__)); | |||
1036 | DefM[A].push(DA); | |||
1037 | } | |||
1038 | // Mark all the related defs as visited. | |||
1039 | for (auto T : Rel) | |||
1040 | Visited.insert(T.Id); | |||
1041 | } | |||
1042 | } | |||
1043 | ||||
1044 | // Return the list of all reference nodes related to RA, including RA itself. | |||
1045 | // See "getNextRelated" for the meaning of a "related reference". | |||
1046 | NodeList DataFlowGraph::getRelatedRefs(NodeAddr<InstrNode*> IA, | |||
1047 | NodeAddr<RefNode*> RA) const { | |||
1048 | assert(IA.Id != 0 && RA.Id != 0)((IA.Id != 0 && RA.Id != 0) ? static_cast<void> (0) : __assert_fail ("IA.Id != 0 && RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1048, __PRETTY_FUNCTION__)); | |||
1049 | ||||
1050 | NodeList Refs; | |||
1051 | NodeId Start = RA.Id; | |||
1052 | do { | |||
1053 | Refs.push_back(RA); | |||
1054 | RA = getNextRelated(IA, RA); | |||
1055 | } while (RA.Id != 0 && RA.Id != Start); | |||
1056 | return Refs; | |||
1057 | } | |||
1058 | ||||
1059 | ||||
1060 | // Clear all information in the graph. | |||
1061 | void DataFlowGraph::reset() { | |||
1062 | Memory.clear(); | |||
1063 | Func = NodeAddr<FuncNode*>(); | |||
1064 | } | |||
1065 | ||||
1066 | ||||
1067 | // Return the next reference node in the instruction node IA that is related | |||
1068 | // to RA. Conceptually, two reference nodes are related if they refer to the | |||
1069 | // same instance of a register access, but differ in flags or other minor | |||
1070 | // characteristics. Specific examples of related nodes are shadow reference | |||
1071 | // nodes. | |||
1072 | // Return the equivalent of nullptr if there are no more related references. | |||
1073 | NodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA, | |||
1074 | NodeAddr<RefNode*> RA) const { | |||
1075 | assert(IA.Id != 0 && RA.Id != 0)((IA.Id != 0 && RA.Id != 0) ? static_cast<void> (0) : __assert_fail ("IA.Id != 0 && RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1075, __PRETTY_FUNCTION__)); | |||
1076 | ||||
1077 | auto Related = [RA](NodeAddr<RefNode*> TA) -> bool { | |||
1078 | if (TA.Addr->getKind() != RA.Addr->getKind()) | |||
1079 | return false; | |||
1080 | if (TA.Addr->getRegRef() != RA.Addr->getRegRef()) | |||
1081 | return false; | |||
1082 | return true; | |||
1083 | }; | |||
1084 | auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { | |||
1085 | return Related(TA) && | |||
1086 | &RA.Addr->getOp() == &TA.Addr->getOp(); | |||
1087 | }; | |||
1088 | auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { | |||
1089 | if (!Related(TA)) | |||
1090 | return false; | |||
1091 | if (TA.Addr->getKind() != NodeAttrs::Use) | |||
1092 | return true; | |||
1093 | // For phi uses, compare predecessor blocks. | |||
1094 | const NodeAddr<const PhiUseNode*> TUA = TA; | |||
1095 | const NodeAddr<const PhiUseNode*> RUA = RA; | |||
1096 | return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor(); | |||
1097 | }; | |||
1098 | ||||
1099 | RegisterRef RR = RA.Addr->getRegRef(); | |||
1100 | if (IA.Addr->getKind() == NodeAttrs::Stmt) | |||
1101 | return RA.Addr->getNextRef(RR, RelatedStmt, true, *this); | |||
1102 | return RA.Addr->getNextRef(RR, RelatedPhi, true, *this); | |||
1103 | } | |||
1104 | ||||
1105 | // Find the next node related to RA in IA that satisfies condition P. | |||
1106 | // If such a node was found, return a pair where the second element is the | |||
1107 | // located node. If such a node does not exist, return a pair where the | |||
1108 | // first element is the element after which such a node should be inserted, | |||
1109 | // and the second element is a null-address. | |||
1110 | template <typename Predicate> | |||
1111 | std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>> | |||
1112 | DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, | |||
1113 | Predicate P) const { | |||
1114 | assert(IA.Id != 0 && RA.Id != 0)((IA.Id != 0 && RA.Id != 0) ? static_cast<void> (0) : __assert_fail ("IA.Id != 0 && RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1114, __PRETTY_FUNCTION__)); | |||
1115 | ||||
1116 | NodeAddr<RefNode*> NA; | |||
1117 | NodeId Start = RA.Id; | |||
1118 | while (true) { | |||
1119 | NA = getNextRelated(IA, RA); | |||
1120 | if (NA.Id == 0 || NA.Id == Start) | |||
1121 | break; | |||
1122 | if (P(NA)) | |||
1123 | break; | |||
1124 | RA = NA; | |||
1125 | } | |||
1126 | ||||
1127 | if (NA.Id != 0 && NA.Id != Start) | |||
1128 | return std::make_pair(RA, NA); | |||
1129 | return std::make_pair(RA, NodeAddr<RefNode*>()); | |||
1130 | } | |||
1131 | ||||
1132 | // Get the next shadow node in IA corresponding to RA, and optionally create | |||
1133 | // such a node if it does not exist. | |||
1134 | NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, | |||
1135 | NodeAddr<RefNode*> RA, bool Create) { | |||
1136 | assert(IA.Id != 0 && RA.Id != 0)((IA.Id != 0 && RA.Id != 0) ? static_cast<void> (0) : __assert_fail ("IA.Id != 0 && RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1136, __PRETTY_FUNCTION__)); | |||
1137 | ||||
1138 | uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; | |||
1139 | auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { | |||
1140 | return TA.Addr->getFlags() == Flags; | |||
1141 | }; | |||
1142 | auto Loc = locateNextRef(IA, RA, IsShadow); | |||
1143 | if (Loc.second.Id != 0 || !Create) | |||
1144 | return Loc.second; | |||
1145 | ||||
1146 | // Create a copy of RA and mark is as shadow. | |||
1147 | NodeAddr<RefNode*> NA = cloneNode(RA); | |||
1148 | NA.Addr->setFlags(Flags | NodeAttrs::Shadow); | |||
1149 | IA.Addr->addMemberAfter(Loc.first, NA, *this); | |||
1150 | return NA; | |||
1151 | } | |||
1152 | ||||
1153 | // Get the next shadow node in IA corresponding to RA. Return null-address | |||
1154 | // if such a node does not exist. | |||
1155 | NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, | |||
1156 | NodeAddr<RefNode*> RA) const { | |||
1157 | assert(IA.Id != 0 && RA.Id != 0)((IA.Id != 0 && RA.Id != 0) ? static_cast<void> (0) : __assert_fail ("IA.Id != 0 && RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1157, __PRETTY_FUNCTION__)); | |||
1158 | uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; | |||
1159 | auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { | |||
1160 | return TA.Addr->getFlags() == Flags; | |||
1161 | }; | |||
1162 | return locateNextRef(IA, RA, IsShadow).second; | |||
1163 | } | |||
1164 | ||||
1165 | // Create a new statement node in the block node BA that corresponds to | |||
1166 | // the machine instruction MI. | |||
1167 | void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { | |||
1168 | auto SA = newStmt(BA, &In); | |||
1169 | ||||
1170 | // Collect a set of registers that this instruction implicitly uses | |||
1171 | // or defines. Implicit operands from an instruction will be ignored | |||
1172 | // unless they are listed here. | |||
1173 | RegisterSet ImpUses, ImpDefs; | |||
1174 | if (const uint16_t *ImpD = In.getDesc().getImplicitDefs()) | |||
1175 | while (uint16_t R = *ImpD++) | |||
1176 | ImpDefs.insert({R, 0}); | |||
1177 | if (const uint16_t *ImpU = In.getDesc().getImplicitUses()) | |||
1178 | while (uint16_t R = *ImpU++) | |||
1179 | ImpUses.insert({R, 0}); | |||
1180 | ||||
1181 | bool IsCall = In.isCall(), IsReturn = In.isReturn(); | |||
1182 | bool IsPredicated = TII.isPredicated(In); | |||
1183 | unsigned NumOps = In.getNumOperands(); | |||
1184 | ||||
1185 | // Avoid duplicate implicit defs. This will not detect cases of implicit | |||
1186 | // defs that define registers that overlap, but it is not clear how to | |||
1187 | // interpret that in the absence of explicit defs. Overlapping explicit | |||
1188 | // defs are likely illegal already. | |||
1189 | RegisterSet DoneDefs; | |||
1190 | // Process explicit defs first. | |||
1191 | for (unsigned OpN = 0; OpN < NumOps; ++OpN) { | |||
1192 | MachineOperand &Op = In.getOperand(OpN); | |||
1193 | if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) | |||
1194 | continue; | |||
1195 | RegisterRef RR = { Op.getReg(), Op.getSubReg() }; | |||
1196 | uint16_t Flags = NodeAttrs::None; | |||
1197 | if (TOI.isPreserving(In, OpN)) | |||
1198 | Flags |= NodeAttrs::Preserving; | |||
1199 | if (TOI.isClobbering(In, OpN)) | |||
1200 | Flags |= NodeAttrs::Clobbering; | |||
1201 | if (TOI.isFixedReg(In, OpN)) | |||
1202 | Flags |= NodeAttrs::Fixed; | |||
1203 | NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); | |||
1204 | SA.Addr->addMember(DA, *this); | |||
1205 | DoneDefs.insert(RR); | |||
1206 | } | |||
1207 | ||||
1208 | // Process implicit defs, skipping those that have already been added | |||
1209 | // as explicit. | |||
1210 | for (unsigned OpN = 0; OpN < NumOps; ++OpN) { | |||
1211 | MachineOperand &Op = In.getOperand(OpN); | |||
1212 | if (!Op.isReg() || !Op.isDef() || !Op.isImplicit()) | |||
1213 | continue; | |||
1214 | RegisterRef RR = { Op.getReg(), Op.getSubReg() }; | |||
1215 | if (!IsCall && !ImpDefs.count(RR)) | |||
1216 | continue; | |||
1217 | if (DoneDefs.count(RR)) | |||
1218 | continue; | |||
1219 | uint16_t Flags = NodeAttrs::None; | |||
1220 | if (TOI.isPreserving(In, OpN)) | |||
1221 | Flags |= NodeAttrs::Preserving; | |||
1222 | if (TOI.isClobbering(In, OpN)) | |||
1223 | Flags |= NodeAttrs::Clobbering; | |||
1224 | if (TOI.isFixedReg(In, OpN)) | |||
1225 | Flags |= NodeAttrs::Fixed; | |||
1226 | NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); | |||
1227 | SA.Addr->addMember(DA, *this); | |||
1228 | DoneDefs.insert(RR); | |||
1229 | } | |||
1230 | ||||
1231 | for (unsigned OpN = 0; OpN < NumOps; ++OpN) { | |||
1232 | MachineOperand &Op = In.getOperand(OpN); | |||
1233 | if (!Op.isReg() || !Op.isUse()) | |||
1234 | continue; | |||
1235 | RegisterRef RR = { Op.getReg(), Op.getSubReg() }; | |||
1236 | // Add implicit uses on return and call instructions, and on predicated | |||
1237 | // instructions regardless of whether or not they appear in the instruction | |||
1238 | // descriptor's list. | |||
1239 | bool Implicit = Op.isImplicit(); | |||
1240 | bool TakeImplicit = IsReturn || IsCall || IsPredicated; | |||
1241 | if (Implicit && !TakeImplicit && !ImpUses.count(RR)) | |||
1242 | continue; | |||
1243 | uint16_t Flags = NodeAttrs::None; | |||
1244 | if (TOI.isFixedReg(In, OpN)) | |||
1245 | Flags |= NodeAttrs::Fixed; | |||
1246 | NodeAddr<UseNode*> UA = newUse(SA, Op, Flags); | |||
1247 | SA.Addr->addMember(UA, *this); | |||
1248 | } | |||
1249 | } | |||
1250 | ||||
1251 | // Build a map that for each block will have the set of all references from | |||
1252 | // that block, and from all blocks dominated by it. | |||
1253 | void DataFlowGraph::buildBlockRefs(NodeAddr<BlockNode*> BA, | |||
1254 | BlockRefsMap &RefM) { | |||
1255 | auto &Refs = RefM[BA.Id]; | |||
1256 | MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); | |||
1257 | assert(N)((N) ? static_cast<void> (0) : __assert_fail ("N", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1257, __PRETTY_FUNCTION__)); | |||
1258 | for (auto I : *N) { | |||
1259 | MachineBasicBlock *SB = I->getBlock(); | |||
1260 | auto SBA = Func.Addr->findBlock(SB, *this); | |||
1261 | buildBlockRefs(SBA, RefM); | |||
1262 | const auto &SRs = RefM[SBA.Id]; | |||
1263 | Refs.insert(SRs.begin(), SRs.end()); | |||
1264 | } | |||
1265 | ||||
1266 | for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) | |||
1267 | for (NodeAddr<RefNode*> RA : IA.Addr->members(*this)) | |||
1268 | Refs.insert(RA.Addr->getRegRef()); | |||
1269 | } | |||
1270 | ||||
1271 | // Scan all defs in the block node BA and record in PhiM the locations of | |||
1272 | // phi nodes corresponding to these defs. | |||
1273 | void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM, | |||
1274 | NodeAddr<BlockNode*> BA) { | |||
1275 | // Check all defs from block BA and record them in each block in BA's | |||
1276 | // iterated dominance frontier. This information will later be used to | |||
1277 | // create phi nodes. | |||
1278 | MachineBasicBlock *BB = BA.Addr->getCode(); | |||
1279 | assert(BB)((BB) ? static_cast<void> (0) : __assert_fail ("BB", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1279, __PRETTY_FUNCTION__)); | |||
1280 | auto DFLoc = MDF.find(BB); | |||
1281 | if (DFLoc == MDF.end() || DFLoc->second.empty()) | |||
1282 | return; | |||
1283 | ||||
1284 | // Traverse all instructions in the block and collect the set of all | |||
1285 | // defined references. For each reference there will be a phi created | |||
1286 | // in the block's iterated dominance frontier. | |||
1287 | // This is done to make sure that each defined reference gets only one | |||
1288 | // phi node, even if it is defined multiple times. | |||
1289 | RegisterSet Defs; | |||
1290 | for (auto I : BA.Addr->members(*this)) { | |||
1291 | assert(I.Addr->getType() == NodeAttrs::Code)((I.Addr->getType() == NodeAttrs::Code) ? static_cast<void > (0) : __assert_fail ("I.Addr->getType() == NodeAttrs::Code" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1291, __PRETTY_FUNCTION__)); | |||
1292 | assert(I.Addr->getKind() == NodeAttrs::Phi ||((I.Addr->getKind() == NodeAttrs::Phi || I.Addr->getKind () == NodeAttrs::Stmt) ? static_cast<void> (0) : __assert_fail ("I.Addr->getKind() == NodeAttrs::Phi || I.Addr->getKind() == NodeAttrs::Stmt" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1293, __PRETTY_FUNCTION__)) | |||
1293 | I.Addr->getKind() == NodeAttrs::Stmt)((I.Addr->getKind() == NodeAttrs::Phi || I.Addr->getKind () == NodeAttrs::Stmt) ? static_cast<void> (0) : __assert_fail ("I.Addr->getKind() == NodeAttrs::Phi || I.Addr->getKind() == NodeAttrs::Stmt" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1293, __PRETTY_FUNCTION__)); | |||
1294 | NodeAddr<InstrNode*> IA = I; | |||
1295 | for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this)) | |||
1296 | Defs.insert(RA.Addr->getRegRef()); | |||
1297 | } | |||
1298 | ||||
1299 | // Finally, add the set of defs to each block in the iterated dominance | |||
1300 | // frontier. | |||
1301 | const MachineDominanceFrontier::DomSetType &DF = DFLoc->second; | |||
1302 | SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end()); | |||
1303 | for (unsigned i = 0; i < IDF.size(); ++i) { | |||
1304 | auto F = MDF.find(IDF[i]); | |||
1305 | if (F != MDF.end()) | |||
1306 | IDF.insert(F->second.begin(), F->second.end()); | |||
1307 | } | |||
1308 | ||||
1309 | // Get the register references that are reachable from this block. | |||
1310 | RegisterSet &Refs = RefM[BA.Id]; | |||
1311 | for (auto DB : IDF) { | |||
1312 | auto DBA = Func.Addr->findBlock(DB, *this); | |||
1313 | const auto &Rs = RefM[DBA.Id]; | |||
1314 | Refs.insert(Rs.begin(), Rs.end()); | |||
1315 | } | |||
1316 | ||||
1317 | for (auto DB : IDF) { | |||
1318 | auto DBA = Func.Addr->findBlock(DB, *this); | |||
1319 | PhiM[DBA.Id].insert(Defs.begin(), Defs.end()); | |||
1320 | } | |||
1321 | } | |||
1322 | ||||
1323 | // Given the locations of phi nodes in the map PhiM, create the phi nodes | |||
1324 | // that are located in the block node BA. | |||
1325 | void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM, | |||
1326 | NodeAddr<BlockNode*> BA) { | |||
1327 | // Check if this blocks has any DF defs, i.e. if there are any defs | |||
1328 | // that this block is in the iterated dominance frontier of. | |||
1329 | auto HasDF = PhiM.find(BA.Id); | |||
1330 | if (HasDF == PhiM.end() || HasDF->second.empty()) | |||
1331 | return; | |||
1332 | ||||
1333 | // First, remove all R in Refs in such that there exists T in Refs | |||
1334 | // such that T covers R. In other words, only leave those refs that | |||
1335 | // are not covered by another ref (i.e. maximal with respect to covering). | |||
1336 | ||||
1337 | auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef { | |||
1338 | for (auto I : RRs) | |||
1339 | if (I != RR && RAI.covers(I, RR)) | |||
1340 | RR = I; | |||
1341 | return RR; | |||
1342 | }; | |||
1343 | ||||
1344 | RegisterSet MaxDF; | |||
1345 | for (auto I : HasDF->second) | |||
1346 | MaxDF.insert(MaxCoverIn(I, HasDF->second)); | |||
1347 | ||||
1348 | std::vector<RegisterRef> MaxRefs; | |||
1349 | auto &RefB = RefM[BA.Id]; | |||
1350 | for (auto I : MaxDF) | |||
1351 | MaxRefs.push_back(MaxCoverIn(I, RefB)); | |||
1352 | ||||
1353 | // Now, for each R in MaxRefs, get the alias closure of R. If the closure | |||
1354 | // only has R in it, create a phi a def for R. Otherwise, create a phi, | |||
1355 | // and add a def for each S in the closure. | |||
1356 | ||||
1357 | // Sort the refs so that the phis will be created in a deterministic order. | |||
1358 | std::sort(MaxRefs.begin(), MaxRefs.end()); | |||
1359 | // Remove duplicates. | |||
1360 | auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); | |||
1361 | MaxRefs.erase(NewEnd, MaxRefs.end()); | |||
1362 | ||||
1363 | auto Aliased = [this,&MaxRefs](RegisterRef RR, | |||
1364 | std::vector<unsigned> &Closure) -> bool { | |||
1365 | for (auto I : Closure) | |||
1366 | if (RAI.alias(RR, MaxRefs[I])) | |||
1367 | return true; | |||
1368 | return false; | |||
1369 | }; | |||
1370 | ||||
1371 | // Prepare a list of NodeIds of the block's predecessors. | |||
1372 | std::vector<NodeId> PredList; | |||
1373 | const MachineBasicBlock *MBB = BA.Addr->getCode(); | |||
1374 | for (auto PB : MBB->predecessors()) { | |||
1375 | auto B = Func.Addr->findBlock(PB, *this); | |||
1376 | PredList.push_back(B.Id); | |||
1377 | } | |||
1378 | ||||
1379 | while (!MaxRefs.empty()) { | |||
1380 | // Put the first element in the closure, and then add all subsequent | |||
1381 | // elements from MaxRefs to it, if they alias at least one element | |||
1382 | // already in the closure. | |||
1383 | // ClosureIdx: vector of indices in MaxRefs of members of the closure. | |||
1384 | std::vector<unsigned> ClosureIdx = { 0 }; | |||
1385 | for (unsigned i = 1; i != MaxRefs.size(); ++i) | |||
1386 | if (Aliased(MaxRefs[i], ClosureIdx)) | |||
1387 | ClosureIdx.push_back(i); | |||
1388 | ||||
1389 | // Build a phi for the closure. | |||
1390 | unsigned CS = ClosureIdx.size(); | |||
1391 | NodeAddr<PhiNode*> PA = newPhi(BA); | |||
1392 | ||||
1393 | // Add defs. | |||
1394 | for (unsigned X = 0; X != CS; ++X) { | |||
1395 | RegisterRef RR = MaxRefs[ClosureIdx[X]]; | |||
1396 | uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; | |||
1397 | NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); | |||
1398 | PA.Addr->addMember(DA, *this); | |||
1399 | } | |||
1400 | // Add phi uses. | |||
1401 | for (auto P : PredList) { | |||
1402 | auto PBA = addr<BlockNode*>(P); | |||
1403 | for (unsigned X = 0; X != CS; ++X) { | |||
1404 | RegisterRef RR = MaxRefs[ClosureIdx[X]]; | |||
1405 | NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA); | |||
1406 | PA.Addr->addMember(PUA, *this); | |||
1407 | } | |||
1408 | } | |||
1409 | ||||
1410 | // Erase from MaxRefs all elements in the closure. | |||
1411 | auto Begin = MaxRefs.begin(); | |||
1412 | for (unsigned i = ClosureIdx.size(); i != 0; --i) | |||
1413 | MaxRefs.erase(Begin + ClosureIdx[i-1]); | |||
1414 | } | |||
1415 | } | |||
1416 | ||||
1417 | // Remove any unneeded phi nodes that were created during the build process. | |||
1418 | void DataFlowGraph::removeUnusedPhis() { | |||
1419 | // This will remove unused phis, i.e. phis where each def does not reach | |||
1420 | // any uses or other defs. This will not detect or remove circular phi | |||
1421 | // chains that are otherwise dead. Unused/dead phis are created during | |||
1422 | // the build process and this function is intended to remove these cases | |||
1423 | // that are easily determinable to be unnecessary. | |||
1424 | ||||
1425 | SetVector<NodeId> PhiQ; | |||
1426 | for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) { | |||
1427 | for (auto P : BA.Addr->members_if(IsPhi, *this)) | |||
1428 | PhiQ.insert(P.Id); | |||
1429 | } | |||
1430 | ||||
1431 | static auto HasUsedDef = [](NodeList &Ms) -> bool { | |||
1432 | for (auto M : Ms) { | |||
1433 | if (M.Addr->getKind() != NodeAttrs::Def) | |||
1434 | continue; | |||
1435 | NodeAddr<DefNode*> DA = M; | |||
1436 | if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0) | |||
1437 | return true; | |||
1438 | } | |||
1439 | return false; | |||
1440 | }; | |||
1441 | ||||
1442 | // Any phi, if it is removed, may affect other phis (make them dead). | |||
1443 | // For each removed phi, collect the potentially affected phis and add | |||
1444 | // them back to the queue. | |||
1445 | while (!PhiQ.empty()) { | |||
1446 | auto PA = addr<PhiNode*>(PhiQ[0]); | |||
1447 | PhiQ.remove(PA.Id); | |||
1448 | NodeList Refs = PA.Addr->members(*this); | |||
1449 | if (HasUsedDef(Refs)) | |||
1450 | continue; | |||
1451 | for (NodeAddr<RefNode*> RA : Refs) { | |||
1452 | if (NodeId RD = RA.Addr->getReachingDef()) { | |||
1453 | auto RDA = addr<DefNode*>(RD); | |||
1454 | NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this); | |||
1455 | if (IsPhi(OA)) | |||
1456 | PhiQ.insert(OA.Id); | |||
1457 | } | |||
1458 | if (RA.Addr->isDef()) | |||
1459 | unlinkDef(RA, true); | |||
1460 | else | |||
1461 | unlinkUse(RA, true); | |||
1462 | } | |||
1463 | NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this); | |||
1464 | BA.Addr->removeMember(PA, *this); | |||
1465 | } | |||
1466 | } | |||
1467 | ||||
1468 | // For a given reference node TA in an instruction node IA, connect the | |||
1469 | // reaching def of TA to the appropriate def node. Create any shadow nodes | |||
1470 | // as appropriate. | |||
1471 | template <typename T> | |||
1472 | void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA, | |||
1473 | DefStack &DS) { | |||
1474 | if (DS.empty()) | |||
1475 | return; | |||
1476 | RegisterRef RR = TA.Addr->getRegRef(); | |||
1477 | NodeAddr<T> TAP; | |||
1478 | ||||
1479 | // References from the def stack that have been examined so far. | |||
1480 | RegisterSet Defs; | |||
1481 | ||||
1482 | for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) { | |||
1483 | RegisterRef QR = I->Addr->getRegRef(); | |||
1484 | auto AliasQR = [QR,this] (RegisterRef RR) -> bool { | |||
1485 | return RAI.alias(QR, RR); | |||
1486 | }; | |||
1487 | bool PrecUp = RAI.covers(QR, RR); | |||
1488 | // Skip all defs that are aliased to any of the defs that we have already | |||
1489 | // seen. If we encounter a covering def, stop the stack traversal early. | |||
1490 | if (std::any_of(Defs.begin(), Defs.end(), AliasQR)) { | |||
1491 | if (PrecUp) | |||
1492 | break; | |||
1493 | continue; | |||
1494 | } | |||
1495 | // The reaching def. | |||
1496 | NodeAddr<DefNode*> RDA = *I; | |||
1497 | ||||
1498 | // Pick the reached node. | |||
1499 | if (TAP.Id == 0) { | |||
1500 | TAP = TA; | |||
1501 | } else { | |||
1502 | // Mark the existing ref as "shadow" and create a new shadow. | |||
1503 | TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow); | |||
1504 | TAP = getNextShadow(IA, TAP, true); | |||
1505 | } | |||
1506 | ||||
1507 | // Create the link. | |||
1508 | TAP.Addr->linkToDef(TAP.Id, RDA); | |||
1509 | ||||
1510 | if (PrecUp) | |||
1511 | break; | |||
1512 | Defs.insert(QR); | |||
1513 | } | |||
1514 | } | |||
1515 | ||||
1516 | // Create data-flow links for all reference nodes in the statement node SA. | |||
1517 | void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA) { | |||
1518 | RegisterSet Defs; | |||
1519 | ||||
1520 | // Link all nodes (upwards in the data-flow) with their reaching defs. | |||
1521 | for (NodeAddr<RefNode*> RA : SA.Addr->members(*this)) { | |||
1522 | uint16_t Kind = RA.Addr->getKind(); | |||
1523 | assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use)((Kind == NodeAttrs::Def || Kind == NodeAttrs::Use) ? static_cast <void> (0) : __assert_fail ("Kind == NodeAttrs::Def || Kind == NodeAttrs::Use" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1523, __PRETTY_FUNCTION__)); | |||
1524 | RegisterRef RR = RA.Addr->getRegRef(); | |||
1525 | // Do not process multiple defs of the same reference. | |||
1526 | if (Kind == NodeAttrs::Def && Defs.count(RR)) | |||
1527 | continue; | |||
1528 | Defs.insert(RR); | |||
1529 | ||||
1530 | auto F = DefM.find(RR); | |||
1531 | if (F == DefM.end()) | |||
1532 | continue; | |||
1533 | DefStack &DS = F->second; | |||
1534 | if (Kind == NodeAttrs::Use) | |||
1535 | linkRefUp<UseNode*>(SA, RA, DS); | |||
1536 | else if (Kind == NodeAttrs::Def) | |||
1537 | linkRefUp<DefNode*>(SA, RA, DS); | |||
1538 | else | |||
1539 | llvm_unreachable("Unexpected node in instruction")::llvm::llvm_unreachable_internal("Unexpected node in instruction" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1539); | |||
1540 | } | |||
1541 | } | |||
1542 | ||||
1543 | // Create data-flow links for all instructions in the block node BA. This | |||
1544 | // will include updating any phi nodes in BA. | |||
1545 | void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) { | |||
1546 | // Push block delimiters. | |||
1547 | markBlock(BA.Id, DefM); | |||
1548 | ||||
1549 | // For each non-phi instruction in the block, link all the defs and uses | |||
1550 | // to their reaching defs. For any member of the block (including phis), | |||
1551 | // push the defs on the corresponding stacks. | |||
1552 | for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) { | |||
| ||||
1553 | // Ignore phi nodes here. They will be linked part by part from the | |||
1554 | // predecessors. | |||
1555 | if (IA.Addr->getKind() == NodeAttrs::Stmt) | |||
1556 | linkStmtRefs(DefM, IA); | |||
1557 | ||||
1558 | // Push the definitions on the stack. | |||
1559 | pushDefs(IA, DefM); | |||
1560 | } | |||
1561 | ||||
1562 | // Recursively process all children in the dominator tree. | |||
1563 | MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); | |||
1564 | for (auto I : *N) { | |||
1565 | MachineBasicBlock *SB = I->getBlock(); | |||
1566 | auto SBA = Func.Addr->findBlock(SB, *this); | |||
1567 | linkBlockRefs(DefM, SBA); | |||
1568 | } | |||
1569 | ||||
1570 | // Link the phi uses from the successor blocks. | |||
1571 | auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool { | |||
1572 | if (NA.Addr->getKind() != NodeAttrs::Use) | |||
1573 | return false; | |||
1574 | assert(NA.Addr->getFlags() & NodeAttrs::PhiRef)((NA.Addr->getFlags() & NodeAttrs::PhiRef) ? static_cast <void> (0) : __assert_fail ("NA.Addr->getFlags() & NodeAttrs::PhiRef" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1574, __PRETTY_FUNCTION__)); | |||
1575 | NodeAddr<PhiUseNode*> PUA = NA; | |||
1576 | return PUA.Addr->getPredecessor() == BA.Id; | |||
1577 | }; | |||
1578 | MachineBasicBlock *MBB = BA.Addr->getCode(); | |||
1579 | for (auto SB : MBB->successors()) { | |||
1580 | auto SBA = Func.Addr->findBlock(SB, *this); | |||
1581 | for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) { | |||
1582 | // Go over each phi use associated with MBB, and link it. | |||
1583 | for (auto U : IA.Addr->members_if(IsUseForBA, *this)) { | |||
1584 | NodeAddr<PhiUseNode*> PUA = U; | |||
1585 | RegisterRef RR = PUA.Addr->getRegRef(); | |||
1586 | linkRefUp<UseNode*>(IA, PUA, DefM[RR]); | |||
1587 | } | |||
1588 | } | |||
1589 | } | |||
1590 | ||||
1591 | // Pop all defs from this block from the definition stacks. | |||
1592 | releaseBlock(BA.Id, DefM); | |||
1593 | } | |||
1594 | ||||
1595 | // Remove the use node UA from any data-flow and structural links. | |||
1596 | void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { | |||
1597 | NodeId RD = UA.Addr->getReachingDef(); | |||
1598 | NodeId Sib = UA.Addr->getSibling(); | |||
1599 | ||||
1600 | if (RD == 0) { | |||
1601 | assert(Sib == 0)((Sib == 0) ? static_cast<void> (0) : __assert_fail ("Sib == 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1601, __PRETTY_FUNCTION__)); | |||
1602 | return; | |||
1603 | } | |||
1604 | ||||
1605 | auto RDA = addr<DefNode*>(RD); | |||
1606 | auto TA = addr<UseNode*>(RDA.Addr->getReachedUse()); | |||
1607 | if (TA.Id == UA.Id) { | |||
1608 | RDA.Addr->setReachedUse(Sib); | |||
1609 | return; | |||
1610 | } | |||
1611 | ||||
1612 | while (TA.Id != 0) { | |||
1613 | NodeId S = TA.Addr->getSibling(); | |||
1614 | if (S == UA.Id) { | |||
1615 | TA.Addr->setSibling(UA.Addr->getSibling()); | |||
1616 | return; | |||
1617 | } | |||
1618 | TA = addr<UseNode*>(S); | |||
1619 | } | |||
1620 | } | |||
1621 | ||||
1622 | // Remove the def node DA from any data-flow and structural links. | |||
1623 | void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { | |||
1624 | // | |||
1625 | // RD | |||
1626 | // | reached | |||
1627 | // | def | |||
1628 | // : | |||
1629 | // . | |||
1630 | // +----+ | |||
1631 | // ... -- | DA | -- ... -- 0 : sibling chain of DA | |||
1632 | // +----+ | |||
1633 | // | | reached | |||
1634 | // | : def | |||
1635 | // | . | |||
1636 | // | ... : Siblings (defs) | |||
1637 | // | | |||
1638 | // : reached | |||
1639 | // . use | |||
1640 | // ... : sibling chain of reached uses | |||
1641 | ||||
1642 | NodeId RD = DA.Addr->getReachingDef(); | |||
1643 | ||||
1644 | // Visit all siblings of the reached def and reset their reaching defs. | |||
1645 | // Also, defs reached by DA are now "promoted" to being reached by RD, | |||
1646 | // so all of them will need to be spliced into the sibling chain where | |||
1647 | // DA belongs. | |||
1648 | auto getAllNodes = [this] (NodeId N) -> NodeList { | |||
1649 | NodeList Res; | |||
1650 | while (N) { | |||
1651 | auto RA = addr<RefNode*>(N); | |||
1652 | // Keep the nodes in the exact sibling order. | |||
1653 | Res.push_back(RA); | |||
1654 | N = RA.Addr->getSibling(); | |||
1655 | } | |||
1656 | return Res; | |||
1657 | }; | |||
1658 | NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef()); | |||
1659 | NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse()); | |||
1660 | ||||
1661 | if (RD == 0) { | |||
1662 | for (NodeAddr<RefNode*> I : ReachedDefs) | |||
1663 | I.Addr->setSibling(0); | |||
1664 | for (NodeAddr<RefNode*> I : ReachedUses) | |||
1665 | I.Addr->setSibling(0); | |||
1666 | } | |||
1667 | for (NodeAddr<DefNode*> I : ReachedDefs) | |||
1668 | I.Addr->setReachingDef(RD); | |||
1669 | for (NodeAddr<UseNode*> I : ReachedUses) | |||
1670 | I.Addr->setReachingDef(RD); | |||
1671 | ||||
1672 | NodeId Sib = DA.Addr->getSibling(); | |||
1673 | if (RD == 0) { | |||
1674 | assert(Sib == 0)((Sib == 0) ? static_cast<void> (0) : __assert_fail ("Sib == 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn267387/lib/Target/Hexagon/RDFGraph.cpp" , 1674, __PRETTY_FUNCTION__)); | |||
1675 | return; | |||
1676 | } | |||
1677 | ||||
1678 | // Update the reaching def node and remove DA from the sibling list. | |||
1679 | auto RDA = addr<DefNode*>(RD); | |||
1680 | auto TA = addr<DefNode*>(RDA.Addr->getReachedDef()); | |||
1681 | if (TA.Id == DA.Id) { | |||
1682 | // If DA is the first reached def, just update the RD's reached def | |||
1683 | // to the DA's sibling. | |||
1684 | RDA.Addr->setReachedDef(Sib); | |||
1685 | } else { | |||
1686 | // Otherwise, traverse the sibling list of the reached defs and remove | |||
1687 | // DA from it. | |||
1688 | while (TA.Id != 0) { | |||
1689 | NodeId S = TA.Addr->getSibling(); | |||
1690 | if (S == DA.Id) { | |||
1691 | TA.Addr->setSibling(Sib); | |||
1692 | break; | |||
1693 | } | |||
1694 | TA = addr<DefNode*>(S); | |||
1695 | } | |||
1696 | } | |||
1697 | ||||
1698 | // Splice the DA's reached defs into the RDA's reached def chain. | |||
1699 | if (!ReachedDefs.empty()) { | |||
1700 | auto Last = NodeAddr<DefNode*>(ReachedDefs.back()); | |||
1701 | Last.Addr->setSibling(RDA.Addr->getReachedDef()); | |||
1702 | RDA.Addr->setReachedDef(ReachedDefs.front().Id); | |||
1703 | } | |||
1704 | // Splice the DA's reached uses into the RDA's reached use chain. | |||
1705 | if (!ReachedUses.empty()) { | |||
1706 | auto Last = NodeAddr<UseNode*>(ReachedUses.back()); | |||
1707 | Last.Addr->setSibling(RDA.Addr->getReachedUse()); | |||
1708 | RDA.Addr->setReachedUse(ReachedUses.front().Id); | |||
1709 | } | |||
1710 | } |