Bug Summary

File:lib/Target/Hexagon/RDFGraph.cpp
Warning:line 923, column 29
Called C++ object pointer is null

Annotated Source Code

/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.cpp

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

/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h

1//===- RDFGraph.h -----------------------------------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Target-independent, SSA-based data flow graph for register data flow (RDF)
11// for a non-SSA program representation (e.g. post-RA machine code).
12//
13//
14// *** Introduction
15//
16// The RDF graph is a collection of nodes, each of which denotes some element
17// of the program. There are two main types of such elements: code and refe-
18// rences. Conceptually, "code" is something that represents the structure
19// of the program, e.g. basic block or a statement, while "reference" is an
20// instance of accessing a register, e.g. a definition or a use. Nodes are
21// connected with each other based on the structure of the program (such as
22// blocks, instructions, etc.), and based on the data flow (e.g. reaching
23// definitions, reached uses, etc.). The single-reaching-definition principle
24// of SSA is generally observed, although, due to the non-SSA representation
25// of the program, there are some differences between the graph and a "pure"
26// SSA representation.
27//
28//
29// *** Implementation remarks
30//
31// Since the graph can contain a large number of nodes, memory consumption
32// was one of the major design considerations. As a result, there is a single
33// base class NodeBase which defines all members used by all possible derived
34// classes. The members are arranged in a union, and a derived class cannot
35// add any data members of its own. Each derived class only defines the
36// functional interface, i.e. member functions. NodeBase must be a POD,
37// which implies that all of its members must also be PODs.
38// Since nodes need to be connected with other nodes, pointers have been
39// replaced with 32-bit identifiers: each node has an id of type NodeId.
40// There are mapping functions in the graph that translate between actual
41// memory addresses and the corresponding identifiers.
42// A node id of 0 is equivalent to nullptr.
43//
44//
45// *** Structure of the graph
46//
47// A code node is always a collection of other nodes. For example, a code
48// node corresponding to a basic block will contain code nodes corresponding
49// to instructions. In turn, a code node corresponding to an instruction will
50// contain a list of reference nodes that correspond to the definitions and
51// uses of registers in that instruction. The members are arranged into a
52// circular list, which is yet another consequence of the effort to save
53// memory: for each member node it should be possible to obtain its owner,
54// and it should be possible to access all other members. There are other
55// ways to accomplish that, but the circular list seemed the most natural.
56//
57// +- CodeNode -+
58// | | <---------------------------------------------------+
59// +-+--------+-+ |
60// |FirstM |LastM |
61// | +-------------------------------------+ |
62// | | |
63// V V |
64// +----------+ Next +----------+ Next Next +----------+ Next |
65// | |----->| |-----> ... ----->| |----->-+
66// +- Member -+ +- Member -+ +- Member -+
67//
68// The order of members is such that related reference nodes (see below)
69// should be contiguous on the member list.
70//
71// A reference node is a node that encapsulates an access to a register,
72// in other words, data flowing into or out of a register. There are two
73// major kinds of reference nodes: defs and uses. A def node will contain
74// the id of the first reached use, and the id of the first reached def.
75// Each def and use will contain the id of the reaching def, and also the
76// id of the next reached def (for def nodes) or use (for use nodes).
77// The "next node sharing the same reaching def" is denoted as "sibling".
78// In summary:
79// - Def node contains: reaching def, sibling, first reached def, and first
80// reached use.
81// - Use node contains: reaching def and sibling.
82//
83// +-- DefNode --+
84// | R2 = ... | <---+--------------------+
85// ++---------+--+ | |
86// |Reached |Reached | |
87// |Def |Use | |
88// | | |Reaching |Reaching
89// | V |Def |Def
90// | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib
91// | | ... = R2 |----->| ... = R2 |----> ... ----> 0
92// | +-------------+ +-------------+
93// V
94// +-- DefNode --+ Sib
95// | R2 = ... |----> ...
96// ++---------+--+
97// | |
98// | |
99// ... ...
100//
101// To get a full picture, the circular lists connecting blocks within a
102// function, instructions within a block, etc. should be superimposed with
103// the def-def, def-use links shown above.
104// To illustrate this, consider a small example in a pseudo-assembly:
105// foo:
106// add r2, r0, r1 ; r2 = r0+r1
107// addi r0, r2, 1 ; r0 = r2+1
108// ret r0 ; return value in r0
109//
110// The graph (in a format used by the debugging functions) would look like:
111//
112// DFG dump:[
113// f1: Function foo
114// b2: === BB#0 === preds(0), succs(0):
115// p3: phi [d4<r0>(,d12,u9):]
116// p5: phi [d6<r1>(,,u10):]
117// s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
118// s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
119// s14: ret [u15<r0>(d12):]
120// ]
121//
122// The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
123// kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
124// ment, d - def, u - use).
125// The format of a def node is:
126// dN<R>(rd,d,u):sib,
127// where
128// N - numeric node id,
129// R - register being defined
130// rd - reaching def,
131// d - reached def,
132// u - reached use,
133// sib - sibling.
134// The format of a use node is:
135// uN<R>[!](rd):sib,
136// where
137// N - numeric node id,
138// R - register being used,
139// rd - reaching def,
140// sib - sibling.
141// Possible annotations (usually preceding the node id):
142// + - preserving def,
143// ~ - clobbering def,
144// " - shadow ref (follows the node id),
145// ! - fixed register (appears after register name).
146//
147// The circular lists are not explicit in the dump.
148//
149//
150// *** Node attributes
151//
152// NodeBase has a member "Attrs", which is the primary way of determining
153// the node's characteristics. The fields in this member decide whether
154// the node is a code node or a reference node (i.e. node's "type"), then
155// within each type, the "kind" determines what specifically this node
156// represents. The remaining bits, "flags", contain additional information
157// that is even more detailed than the "kind".
158// CodeNode's kinds are:
159// - Phi: Phi node, members are reference nodes.
160// - Stmt: Statement, members are reference nodes.
161// - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
162// - Func: The whole function. The members are basic block nodes.
163// RefNode's kinds are:
164// - Use.
165// - Def.
166//
167// Meaning of flags:
168// - Preserving: applies only to defs. A preserving def is one that can
169// preserve some of the original bits among those that are included in
170// the register associated with that def. For example, if R0 is a 32-bit
171// register, but a def can only change the lower 16 bits, then it will
172// be marked as preserving.
173// - Shadow: a reference that has duplicates holding additional reaching
174// defs (see more below).
175// - Clobbering: applied only to defs, indicates that the value generated
176// by this def is unspecified. A typical example would be volatile registers
177// after function calls.
178// - Fixed: the register in this def/use cannot be replaced with any other
179// register. A typical case would be a parameter register to a call, or
180// the register with the return value from a function.
181// - Undef: the register in this reference the register is assumed to have
182// no pre-existing value, even if it appears to be reached by some def.
183// This is typically used to prevent keeping registers artificially live
184// in cases when they are defined via predicated instructions. For example:
185// r0 = add-if-true cond, r10, r11 (1)
186// r0 = add-if-false cond, r12, r13, r0<imp-use> (2)
187// ... = r0 (3)
188// Before (1), r0 is not intended to be live, and the use of r0 in (3) is
189// not meant to be reached by any def preceding (1). However, since the
190// defs in (1) and (2) are both preserving, these properties alone would
191// imply that the use in (3) may indeed be reached by some prior def.
192// Adding Undef flag to the def in (1) prevents that. The Undef flag
193// may be applied to both defs and uses.
194// - Dead: applies only to defs. The value coming out of a "dead" def is
195// assumed to be unused, even if the def appears to be reaching other defs
196// or uses. The motivation for this flag comes from dead defs on function
197// calls: there is no way to determine if such a def is dead without
198// analyzing the target's ABI. Hence the graph should contain this info,
199// as it is unavailable otherwise. On the other hand, a def without any
200// uses on a typical instruction is not the intended target for this flag.
201//
202// *** Shadow references
203//
204// It may happen that a super-register can have two (or more) non-overlapping
205// sub-registers. When both of these sub-registers are defined and followed
206// by a use of the super-register, the use of the super-register will not
207// have a unique reaching def: both defs of the sub-registers need to be
208// accounted for. In such cases, a duplicate use of the super-register is
209// added and it points to the extra reaching def. Both uses are marked with
210// a flag "shadow". Example:
211// Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
212// set r0, 1 ; r0 = 1
213// set r1, 1 ; r1 = 1
214// addi t1, t0, 1 ; t1 = t0+1
215//
216// The DFG:
217// s1: set [d2<r0>(,,u9):]
218// s3: set [d4<r1>(,,u10):]
219// s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
220//
221// The statement s5 has two use nodes for t0: u7" and u9". The quotation
222// mark " indicates that the node is a shadow.
223//
224
225#ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
226#define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
227
228#include "RDFRegisters.h"
229#include "llvm/ADT/SmallVector.h"
230#include "llvm/MC/LaneBitmask.h"
231#include "llvm/Support/Allocator.h"
232#include "llvm/Support/MathExtras.h"
233#include <cassert>
234#include <cstdint>
235#include <cstring>
236#include <map>
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.
245static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
246
247namespace llvm {
248
249class MachineBasicBlock;
250class MachineDominanceFrontier;
251class MachineDominatorTree;
252class MachineFunction;
253class MachineInstr;
254class MachineOperand;
255class raw_ostream;
256class TargetInstrInfo;
257class TargetRegisterInfo;
258
259namespace 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))(((Addr == NA.Addr) == (Id == NA.Id)) ? static_cast<void>
(0) : __assert_fail ("(Addr == NA.Addr) == (Id == NA.Id)", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 345, __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))((isPowerOf2_32(NPB)) ? static_cast<void> (0) : __assert_fail
("isPowerOf2_32(NPB)", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 381, __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())((LM.any()) ? static_cast<void> (0) : __assert_fail ("LM.any()"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 440, __PRETTY_FUNCTION__))
;
441 return LM.all() ? 0 : insert(LM);
442 }
443
444 uint32_t getIndexForLaneMask(LaneBitmask LM) const {
445 assert(LM.any())((LM.any()) ? static_cast<void> (0) : __assert_fail ("LM.any()"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 445, __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))((!(getFlags() & NodeAttrs::PhiRef)) ? static_cast<void
> (0) : __assert_fail ("!(getFlags() & NodeAttrs::PhiRef)"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 522, __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)((getType() == NodeAttrs::Ref) ? static_cast<void> (0) :
__assert_fail ("getType() == NodeAttrs::Ref", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 544, __PRETTY_FUNCTION__))
;
545 return getKind() == NodeAttrs::Use;
546 }
547
548 bool isDef() const {
549 assert(getType() == NodeAttrs::Ref)((getType() == NodeAttrs::Ref) ? static_cast<void> (0) :
__assert_fail ("getType() == NodeAttrs::Ref", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 549, __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)((getFlags() & NodeAttrs::PhiRef) ? static_cast<void>
(0) : __assert_fail ("getFlags() & NodeAttrs::PhiRef", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 582, __PRETTY_FUNCTION__))
;
583 return Ref.PhiU.PredB;
584 }
585 void setPredecessor(NodeId B) {
586 assert(getFlags() & NodeAttrs::PhiRef)((getFlags() & NodeAttrs::PhiRef) ? static_cast<void>
(0) : __assert_fail ("getFlags() & NodeAttrs::PhiRef", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 586, __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, const TargetOperandInfo &toi);
649
650 NodeBase *ptr(NodeId N) const;
651 template <typename T> T ptr(NodeId N) const {
652 return static_cast<T>(ptr(N));
653 }
654
655 NodeId id(const NodeBase *P) const;
656
657 template <typename T> NodeAddr<T> addr(NodeId N) const {
658 return { ptr<T>(N), N };
659 }
660
661 NodeAddr<FuncNode*> getFunc() const { return Func; }
662 MachineFunction &getMF() const { return MF; }
663 const TargetInstrInfo &getTII() const { return TII; }
664 const TargetRegisterInfo &getTRI() const { return TRI; }
665 const PhysicalRegisterInfo &getPRI() const { return PRI; }
666 const MachineDominatorTree &getDT() const { return MDT; }
667 const MachineDominanceFrontier &getDF() const { return MDF; }
668 const RegisterAggr &getLiveIns() const { return LiveIns; }
669
670 struct DefStack {
671 DefStack() = default;
672
673 bool empty() const { return Stack.empty() || top() == bottom(); }
674
675 private:
676 using value_type = NodeAddr<DefNode *>;
677 struct Iterator {
678 using value_type = DefStack::value_type;
679
680 Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
681 Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
682
683 value_type operator*() const {
684 assert(Pos >= 1)((Pos >= 1) ? static_cast<void> (0) : __assert_fail (
"Pos >= 1", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 684, __PRETTY_FUNCTION__))
;
685 return DS.Stack[Pos-1];
686 }
687 const value_type *operator->() const {
688 assert(Pos >= 1)((Pos >= 1) ? static_cast<void> (0) : __assert_fail (
"Pos >= 1", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 688, __PRETTY_FUNCTION__))
;
689 return &DS.Stack[Pos-1];
690 }
691 bool operator==(const Iterator &It) const { return Pos == It.Pos; }
692 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
693
694 private:
695 friend struct DefStack;
696
697 Iterator(const DefStack &S, bool Top);
698
699 // Pos-1 is the index in the StorageType object that corresponds to
700 // the top of the DefStack.
701 const DefStack &DS;
702 unsigned Pos;
703 };
704
705 public:
706 using iterator = Iterator;
707
708 iterator top() const { return Iterator(*this, true); }
709 iterator bottom() const { return Iterator(*this, false); }
710 unsigned size() const;
711
712 void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
713 void pop();
714 void start_block(NodeId N);
715 void clear_block(NodeId N);
716
717 private:
718 friend struct Iterator;
719
720 using StorageType = std::vector<value_type>;
721
722 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
723 return (P.Addr == nullptr) && (N == 0 || P.Id == N);
724 }
725
726 unsigned nextUp(unsigned P) const;
727 unsigned nextDown(unsigned P) const;
728
729 StorageType Stack;
730 };
731
732 // Make this std::unordered_map for speed of accessing elements.
733 // Map: Register (physical or virtual) -> DefStack
734 using DefStackMap = std::unordered_map<RegisterId, DefStack>;
735
736 void build(unsigned Options = BuildOptions::None);
737 void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
738 void markBlock(NodeId B, DefStackMap &DefM);
739 void releaseBlock(NodeId B, DefStackMap &DefM);
740
741 PackedRegisterRef pack(RegisterRef RR) {
742 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
743 }
744 PackedRegisterRef pack(RegisterRef RR) const {
745 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
746 }
747 RegisterRef unpack(PackedRegisterRef PR) const {
748 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
749 }
750
751 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
752 RegisterRef makeRegRef(const MachineOperand &Op) const;
753 RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
754
755 NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
756 NodeAddr<RefNode*> RA) const;
757 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
758 NodeAddr<RefNode*> RA, bool Create);
759 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
760 NodeAddr<RefNode*> RA) const;
761 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
762 NodeAddr<RefNode*> RA, bool Create);
763 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
764 NodeAddr<RefNode*> RA) const;
765
766 NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
767 NodeAddr<RefNode*> RA) const;
768
769 NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
770 return BlockNodes.at(BB);
771 }
772
773 void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
774 unlinkUseDF(UA);
775 if (RemoveFromOwner)
776 removeFromOwner(UA);
777 }
778
779 void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
780 unlinkDefDF(DA);
781 if (RemoveFromOwner)
782 removeFromOwner(DA);
783 }
784
785 // Some useful filters.
786 template <uint16_t Kind>
787 static bool IsRef(const NodeAddr<NodeBase*> BA) {
788 return BA.Addr->getType() == NodeAttrs::Ref &&
789 BA.Addr->getKind() == Kind;
790 }
791
792 template <uint16_t Kind>
793 static bool IsCode(const NodeAddr<NodeBase*> BA) {
794 return BA.Addr->getType() == NodeAttrs::Code &&
795 BA.Addr->getKind() == Kind;
796 }
797
798 static bool IsDef(const NodeAddr<NodeBase*> BA) {
799 return BA.Addr->getType() == NodeAttrs::Ref &&
800 BA.Addr->getKind() == NodeAttrs::Def;
801 }
802
803 static bool IsUse(const NodeAddr<NodeBase*> BA) {
804 return BA.Addr->getType() == NodeAttrs::Ref &&
805 BA.Addr->getKind() == NodeAttrs::Use;
806 }
807
808 static bool IsPhi(const NodeAddr<NodeBase*> BA) {
809 return BA.Addr->getType() == NodeAttrs::Code &&
810 BA.Addr->getKind() == NodeAttrs::Phi;
811 }
812
813 static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
814 uint16_t Flags = DA.Addr->getFlags();
815 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
816 }
817
818 private:
819 void reset();
820
821 RegisterSet getLandingPadLiveIns() const;
822
823 NodeAddr<NodeBase*> newNode(uint16_t Attrs);
824 NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
825 NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
826 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
827 NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
828 RegisterRef RR, NodeAddr<BlockNode*> PredB,
829 uint16_t Flags = NodeAttrs::PhiRef);
830 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
831 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
832 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
833 RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
834 NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
835 NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
836 MachineInstr *MI);
837 NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
838 MachineBasicBlock *BB);
839 NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
840
841 template <typename Predicate>
842 std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
843 locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
844 Predicate P) const;
845
846 using BlockRefsMap = std::map<NodeId, RegisterSet>;
847
848 void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
849 void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
850 void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
851 NodeAddr<BlockNode*> BA);
852 void removeUnusedPhis();
853
854 void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
855 void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
856 template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
857 NodeAddr<T> TA, DefStack &DS);
858 template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
859 NodeAddr<StmtNode*> SA, Predicate P);
860 void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
861
862 void unlinkUseDF(NodeAddr<UseNode*> UA);
863 void unlinkDefDF(NodeAddr<DefNode*> DA);
864
865 void removeFromOwner(NodeAddr<RefNode*> RA) {
866 NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
867 IA.Addr->removeMember(RA, *this);
868 }
869
870 MachineFunction &MF;
871 const TargetInstrInfo &TII;
872 const TargetRegisterInfo &TRI;
873 const PhysicalRegisterInfo PRI;
874 const MachineDominatorTree &MDT;
875 const MachineDominanceFrontier &MDF;
876 const TargetOperandInfo &TOI;
877
878 RegisterAggr LiveIns;
879 NodeAddr<FuncNode*> Func;
880 NodeAllocator Memory;
881 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
882 std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
883 // Lane mask map.
884 LaneMaskIndex LMI;
885 }; // struct DataFlowGraph
886
887 template <typename Predicate>
888 NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
889 bool NextOnly, const DataFlowGraph &G) {
890 // Get the "Next" reference in the circular list that references RR and
891 // satisfies predicate "Pred".
892 auto NA = G.addr<NodeBase*>(getNext());
893
894 while (NA.Addr != this) {
895 if (NA.Addr->getType() == NodeAttrs::Ref) {
896 NodeAddr<RefNode*> RA = NA;
897 if (RA.Addr->getRegRef(G) == RR && P(NA))
898 return NA;
899 if (NextOnly)
900 break;
901 NA = G.addr<NodeBase*>(NA.Addr->getNext());
902 } else {
903 // We've hit the beginning of the chain.
904 assert(NA.Addr->getType() == NodeAttrs::Code)((NA.Addr->getType() == NodeAttrs::Code) ? static_cast<
void> (0) : __assert_fail ("NA.Addr->getType() == NodeAttrs::Code"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/Target/Hexagon/RDFGraph.h"
, 904, __PRETTY_FUNCTION__))
;
905 NodeAddr<CodeNode*> CA = NA;
906 NA = CA.Addr->getFirstMember(G);
907 }
908 }
909 // Return the equivalent of "nullptr" if such a node was not found.
910 return NodeAddr<RefNode*>();
911 }
912
913 template <typename Predicate>
914 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
915 NodeList MM;
916 auto M = getFirstMember(G);
917 if (M.Id == 0)
23
Assuming the condition is false
24
Taking false branch
918 return MM;
919
920 while (M.Addr != this) {
25
Assuming the condition is true
26
Loop condition is true. Entering loop body
29
Loop condition is true. Entering loop body
921 if (P(M))
27
Taking true branch
30
Taking true branch
922 MM.push_back(M);
923 M = G.addr<NodeBase*>(M.Addr->getNext());
28
Null pointer value stored to 'M.Addr'
31
Called C++ object pointer is null
924 }
925 return MM;
926 }
927
928 template <typename T> struct Print;
929 template <typename T>
930 raw_ostream &operator<< (raw_ostream &OS, const Print<T> &P);
931
932 template <typename T>
933 struct Print {
934 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
935
936 const T &Obj;
937 const DataFlowGraph &G;
938 };
939
940 template <typename T>
941 struct PrintNode : Print<NodeAddr<T>> {
942 PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
943 : Print<NodeAddr<T>>(x, g) {}
944 };
945
946} // end namespace rdf
947
948} // end namespace llvm
949
950#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H