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