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