Bug Summary

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

Annotated Source Code

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