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