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 <cassert>
33#include <cstdint>
34#include <cstring>
35#include <iterator>
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(PersonalityFn: PF))
749 LR.insert(RR: RegisterRef(R));
750 if (!isFuncletEHPersonality(Pers: classifyEHPersonality(Pers: PF))) {
751 if (RegisterId R = TLI.getExceptionSelectorRegister(PersonalityFn: PF))
752 LR.insert(RR: RegisterRef(R));
753 }
754 return LR;
755}
756
757// Node management functions.
758
759// Get the pointer to the node with the id N.
760NodeBase *DataFlowGraph::ptr(NodeId N) const {
761 if (N == 0)
762 return nullptr;
763 return Memory.ptr(N);
764}
765
766// Get the id of the node at the address P.
767NodeId DataFlowGraph::id(const NodeBase *P) const {
768 if (P == nullptr)
769 return 0;
770 return Memory.id(P);
771}
772
773// Allocate a new node and set the attributes to Attrs.
774Node DataFlowGraph::newNode(uint16_t Attrs) {
775 Node P = Memory.New();
776 P.Addr->init();
777 P.Addr->setAttrs(Attrs);
778 return P;
779}
780
781// Make a copy of the given node B, except for the data-flow links, which
782// are set to 0.
783Node DataFlowGraph::cloneNode(const Node B) {
784 Node NA = newNode(Attrs: 0);
785 memcpy(dest: NA.Addr, src: B.Addr, n: sizeof(NodeBase));
786 // Ref nodes need to have the data-flow links reset.
787 if (NA.Addr->getType() == NodeAttrs::Ref) {
788 Ref RA = NA;
789 RA.Addr->setReachingDef(0);
790 RA.Addr->setSibling(0);
791 if (NA.Addr->getKind() == NodeAttrs::Def) {
792 Def DA = NA;
793 DA.Addr->setReachedDef(0);
794 DA.Addr->setReachedUse(0);
795 }
796 }
797 return NA;
798}
799
800// Allocation routines for specific node types/kinds.
801
802Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {
803 Use UA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Use | Flags);
804 UA.Addr->setRegRef(Op: &Op, G&: *this);
805 return UA;
806}
807
808PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,
809 uint16_t Flags) {
810 PhiUse PUA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Use | Flags);
811 assert(Flags & NodeAttrs::PhiRef);
812 PUA.Addr->setRegRef(RR, G&: *this);
813 PUA.Addr->setPredecessor(PredB.Id);
814 return PUA;
815}
816
817Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {
818 Def DA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Def | Flags);
819 DA.Addr->setRegRef(Op: &Op, G&: *this);
820 return DA;
821}
822
823Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {
824 Def DA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Def | Flags);
825 assert(Flags & NodeAttrs::PhiRef);
826 DA.Addr->setRegRef(RR, G&: *this);
827 return DA;
828}
829
830Phi DataFlowGraph::newPhi(Block Owner) {
831 Phi PA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Phi);
832 Owner.Addr->addPhi(PA, G: *this);
833 return PA;
834}
835
836Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {
837 Stmt SA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Stmt);
838 SA.Addr->setCode(MI);
839 Owner.Addr->addMember(NA: SA, G: *this);
840 return SA;
841}
842
843Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {
844 Block BA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Block);
845 BA.Addr->setCode(BB);
846 Owner.Addr->addMember(NA: BA, G: *this);
847 return BA;
848}
849
850Func DataFlowGraph::newFunc(MachineFunction *MF) {
851 Func FA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Func);
852 FA.Addr->setCode(MF);
853 return FA;
854}
855
856// Build the data flow graph.
857void DataFlowGraph::build(const Config &config) {
858 reset();
859 BuildCfg = config;
860 MachineRegisterInfo &MRI = MF.getRegInfo();
861 ReservedRegs = MRI.getReservedRegs();
862 bool SkipReserved = BuildCfg.Options & BuildOptions::OmitReserved;
863
864 auto Insert = [](auto &Set, auto &&Range) {
865 Set.insert(Range.begin(), Range.end());
866 };
867
868 if (BuildCfg.TrackRegs.empty()) {
869 std::set<RegisterId> BaseSet;
870 if (BuildCfg.Classes.empty()) {
871 // Insert every register.
872 for (unsigned R = 1, E = getPRI().getTRI().getNumRegs(); R != E; ++R)
873 BaseSet.insert(x: R);
874 } else {
875 for (const TargetRegisterClass *RC : BuildCfg.Classes) {
876 for (MCPhysReg R : *RC)
877 BaseSet.insert(x: R);
878 }
879 }
880 for (RegisterId R : BaseSet) {
881 if (SkipReserved && ReservedRegs[R])
882 continue;
883 Insert(TrackedUnits, getPRI().getUnits(RR: RegisterRef(R)));
884 }
885 } else {
886 // Track set in Config overrides everything.
887 for (unsigned R : BuildCfg.TrackRegs) {
888 if (SkipReserved && ReservedRegs[R])
889 continue;
890 Insert(TrackedUnits, getPRI().getUnits(RR: RegisterRef(R)));
891 }
892 }
893
894 TheFunc = newFunc(MF: &MF);
895
896 if (MF.empty())
897 return;
898
899 for (MachineBasicBlock &B : MF) {
900 Block BA = newBlock(Owner: TheFunc, BB: &B);
901 BlockNodes.insert(x: std::make_pair(x: &B, y&: BA));
902 for (MachineInstr &I : B) {
903 if (I.isDebugInstr())
904 continue;
905 buildStmt(BA, In&: I);
906 }
907 }
908
909 Block EA = TheFunc.Addr->getEntryBlock(G: *this);
910 NodeList Blocks = TheFunc.Addr->members(G: *this);
911
912 // Collect function live-ins and entry block live-ins.
913 MachineBasicBlock &EntryB = *EA.Addr->getCode();
914 assert(EntryB.pred_empty() && "Function entry block has predecessors");
915 for (std::pair<MCRegister, Register> P : MRI.liveins())
916 LiveIns.insert(RR: RegisterRef(P.first));
917 if (MRI.tracksLiveness()) {
918 for (auto I : EntryB.liveins())
919 LiveIns.insert(RR: RegisterRef(I.PhysReg, I.LaneMask));
920 }
921
922 // Add function-entry phi nodes for the live-in registers.
923 for (RegisterRef RR : LiveIns.refs()) {
924 if (RR.isReg() && !isTracked(RR)) // isReg is likely guaranteed
925 continue;
926 Phi PA = newPhi(Owner: EA);
927 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
928 Def DA = newDef(Owner: PA, RR, Flags: PhiFlags);
929 PA.Addr->addMember(NA: DA, G: *this);
930 }
931
932 // Add phis for landing pads.
933 // Landing pads, unlike usual backs blocks, are not entered through
934 // branches in the program, or fall-throughs from other blocks. They
935 // are entered from the exception handling runtime and target's ABI
936 // may define certain registers as defined on entry to such a block.
937 RegisterAggr EHRegs = getLandingPadLiveIns();
938 if (!EHRegs.empty()) {
939 for (Block BA : Blocks) {
940 const MachineBasicBlock &B = *BA.Addr->getCode();
941 if (!B.isEHPad())
942 continue;
943
944 // Prepare a list of NodeIds of the block's predecessors.
945 NodeList Preds;
946 for (MachineBasicBlock *PB : B.predecessors())
947 Preds.push_back(Elt: findBlock(BB: PB));
948
949 // Build phi nodes for each live-in.
950 for (RegisterRef RR : EHRegs.refs()) {
951 if (RR.isReg() && !isTracked(RR))
952 continue;
953 Phi PA = newPhi(Owner: BA);
954 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
955 // Add def:
956 Def DA = newDef(Owner: PA, RR, Flags: PhiFlags);
957 PA.Addr->addMember(NA: DA, G: *this);
958 // Add uses (no reaching defs for phi uses):
959 for (Block PBA : Preds) {
960 PhiUse PUA = newPhiUse(Owner: PA, RR, PredB: PBA);
961 PA.Addr->addMember(NA: PUA, G: *this);
962 }
963 }
964 }
965 }
966
967 // Build a map "PhiM" which will contain, for each block, the set
968 // of references that will require phi definitions in that block.
969 // "PhiClobberM" map contains references that require phis for clobbering defs
970 BlockRefsMap PhiM(getPRI());
971 BlockRefsMap PhiClobberM(getPRI());
972 for (Block BA : Blocks)
973 recordDefsForDF(PhiM, PhiClobberM, BA);
974 for (Block BA : Blocks)
975 buildPhis(PhiM, BA);
976
977 // Link all the refs. This will recursively traverse the dominator tree.
978 // Phis for clobbering defs are added here.
979 DefStackMap DM;
980 linkBlockRefs(DefM&: DM, PhiClobberM, BA: EA);
981
982 // Finally, remove all unused phi nodes.
983 if (!(BuildCfg.Options & BuildOptions::KeepDeadPhis))
984 removeUnusedPhis();
985}
986
987RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
988 assert(RegisterRef::isRegId(Reg) || RegisterRef::isMaskId(Reg));
989 assert(Reg != 0);
990 if (Sub != 0)
991 Reg = TRI.getSubReg(Reg, Idx: Sub);
992 return RegisterRef(Reg);
993}
994
995RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const {
996 assert(Op.isReg() || Op.isRegMask());
997 if (Op.isReg())
998 return makeRegRef(Reg: Op.getReg(), Sub: Op.getSubReg());
999 return RegisterRef(getPRI().getRegMaskId(RM: Op.getRegMask()),
1000 LaneBitmask::getAll());
1001}
1002
1003// For each stack in the map DefM, push the delimiter for block B on it.
1004void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) {
1005 // Push block delimiters.
1006 for (auto &P : DefM)
1007 P.second.start_block(N: B);
1008}
1009
1010// Remove all definitions coming from block B from each stack in DefM.
1011void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) {
1012 // Pop all defs from this block from the definition stack. Defs that were
1013 // added to the map during the traversal of instructions will not have a
1014 // delimiter, but for those, the whole stack will be emptied.
1015 for (auto &P : DefM)
1016 P.second.clear_block(N: B);
1017
1018 // Finally, remove empty stacks from the map.
1019 for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {
1020 NextI = std::next(x: I);
1021 // This preserves the validity of iterators other than I.
1022 if (I->second.empty())
1023 DefM.erase(position: I);
1024 }
1025}
1026
1027// Push all definitions from the instruction node IA to an appropriate
1028// stack in DefM.
1029void DataFlowGraph::pushAllDefs(Instr IA, DefStackMap &DefM) {
1030 pushClobbers(IA, DM&: DefM);
1031 pushDefs(IA, DM&: DefM);
1032}
1033
1034// Push all definitions from the instruction node IA to an appropriate
1035// stack in DefM.
1036void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) {
1037 NodeSet Visited;
1038 std::set<RegisterId> Defined;
1039
1040 // The important objectives of this function are:
1041 // - to be able to handle instructions both while the graph is being
1042 // constructed, and after the graph has been constructed, and
1043 // - maintain proper ordering of definitions on the stack for each
1044 // register reference:
1045 // - if there are two or more related defs in IA (i.e. coming from
1046 // the same machine operand), then only push one def on the stack,
1047 // - if there are multiple unrelated defs of non-overlapping
1048 // subregisters of S, then the stack for S will have both (in an
1049 // unspecified order), but the order does not matter from the data-
1050 // -flow perspective.
1051
1052 for (Def DA : IA.Addr->members_if(P: IsDef, G: *this)) {
1053 if (Visited.count(x: DA.Id))
1054 continue;
1055 if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))
1056 continue;
1057
1058 NodeList Rel = getRelatedRefs(IA, RA: DA);
1059 Def PDA = Rel.front();
1060 RegisterRef RR = PDA.Addr->getRegRef(G: *this);
1061
1062 // Push the definition on the stack for the register and all aliases.
1063 // The def stack traversal in linkNodeUp will check the exact aliasing.
1064 DefM[RR.Reg].push(DA);
1065 Defined.insert(x: RR.Reg);
1066 for (RegisterId A : getPRI().getAliasSet(Reg: RR.Reg)) {
1067 if (RegisterRef::isRegId(Id: A) && !isTracked(RR: RegisterRef(A)))
1068 continue;
1069 // Check that we don't push the same def twice.
1070 assert(A != RR.Reg);
1071 if (!Defined.count(x: A))
1072 DefM[A].push(DA);
1073 }
1074 // Mark all the related defs as visited.
1075 for (Node T : Rel)
1076 Visited.insert(x: T.Id);
1077 }
1078}
1079
1080// Push all definitions from the instruction node IA to an appropriate
1081// stack in DefM.
1082void DataFlowGraph::pushDefs(Instr IA, DefStackMap &DefM) {
1083 NodeSet Visited;
1084#ifndef NDEBUG
1085 std::set<RegisterId> Defined;
1086#endif
1087
1088 // The important objectives of this function are:
1089 // - to be able to handle instructions both while the graph is being
1090 // constructed, and after the graph has been constructed, and
1091 // - maintain proper ordering of definitions on the stack for each
1092 // register reference:
1093 // - if there are two or more related defs in IA (i.e. coming from
1094 // the same machine operand), then only push one def on the stack,
1095 // - if there are multiple unrelated defs of non-overlapping
1096 // subregisters of S, then the stack for S will have both (in an
1097 // unspecified order), but the order does not matter from the data-
1098 // -flow perspective.
1099
1100 for (Def DA : IA.Addr->members_if(P: IsDef, G: *this)) {
1101 if (Visited.count(x: DA.Id))
1102 continue;
1103 if (DA.Addr->getFlags() & NodeAttrs::Clobbering)
1104 continue;
1105
1106 NodeList Rel = getRelatedRefs(IA, RA: DA);
1107 Def PDA = Rel.front();
1108 RegisterRef RR = PDA.Addr->getRegRef(G: *this);
1109#ifndef NDEBUG
1110 // Assert if the register is defined in two or more unrelated defs.
1111 // This could happen if there are two or more def operands defining it.
1112 if (!Defined.insert(RR.Reg).second) {
1113 MachineInstr *MI = Stmt(IA).Addr->getCode();
1114 dbgs() << "Multiple definitions of register: " << Print(RR, *this)
1115 << " in\n " << *MI << "in " << printMBBReference(*MI->getParent())
1116 << '\n';
1117 llvm_unreachable(nullptr);
1118 }
1119#endif
1120 // Push the definition on the stack for the register and all aliases.
1121 // The def stack traversal in linkNodeUp will check the exact aliasing.
1122 DefM[RR.Reg].push(DA);
1123 for (RegisterId A : getPRI().getAliasSet(Reg: RR.Reg)) {
1124 if (RegisterRef::isRegId(Id: A) && !isTracked(RR: RegisterRef(A)))
1125 continue;
1126 // Check that we don't push the same def twice.
1127 assert(A != RR.Reg);
1128 DefM[A].push(DA);
1129 }
1130 // Mark all the related defs as visited.
1131 for (Node T : Rel)
1132 Visited.insert(x: T.Id);
1133 }
1134}
1135
1136// Return the list of all reference nodes related to RA, including RA itself.
1137// See "getNextRelated" for the meaning of a "related reference".
1138NodeList DataFlowGraph::getRelatedRefs(Instr IA, Ref RA) const {
1139 assert(IA.Id != 0 && RA.Id != 0);
1140
1141 NodeList Refs;
1142 NodeId Start = RA.Id;
1143 do {
1144 Refs.push_back(Elt: RA);
1145 RA = getNextRelated(IA, RA);
1146 } while (RA.Id != 0 && RA.Id != Start);
1147 return Refs;
1148}
1149
1150// Clear all information in the graph.
1151void DataFlowGraph::reset() {
1152 Memory.clear();
1153 BlockNodes.clear();
1154 TrackedUnits.clear();
1155 ReservedRegs.clear();
1156 TheFunc = Func();
1157}
1158
1159// Return the next reference node in the instruction node IA that is related
1160// to RA. Conceptually, two reference nodes are related if they refer to the
1161// same instance of a register access, but differ in flags or other minor
1162// characteristics. Specific examples of related nodes are shadow reference
1163// nodes.
1164// Return the equivalent of nullptr if there are no more related references.
1165Ref DataFlowGraph::getNextRelated(Instr IA, Ref RA) const {
1166 assert(IA.Id != 0 && RA.Id != 0);
1167
1168 auto IsRelated = [this, RA](Ref TA) -> bool {
1169 if (TA.Addr->getKind() != RA.Addr->getKind())
1170 return false;
1171 if (!getPRI().equal_to(A: TA.Addr->getRegRef(G: *this),
1172 B: RA.Addr->getRegRef(G: *this))) {
1173 return false;
1174 }
1175 return true;
1176 };
1177
1178 RegisterRef RR = RA.Addr->getRegRef(G: *this);
1179 if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1180 auto Cond = [&IsRelated, RA](Ref TA) -> bool {
1181 return IsRelated(TA) && &RA.Addr->getOp() == &TA.Addr->getOp();
1182 };
1183 return RA.Addr->getNextRef(RR, P: Cond, NextOnly: true, G: *this);
1184 }
1185
1186 assert(IA.Addr->getKind() == NodeAttrs::Phi);
1187 auto Cond = [&IsRelated, RA](Ref TA) -> bool {
1188 if (!IsRelated(TA))
1189 return false;
1190 if (TA.Addr->getKind() != NodeAttrs::Use)
1191 return true;
1192 // For phi uses, compare predecessor blocks.
1193 return PhiUse(TA).Addr->getPredecessor() ==
1194 PhiUse(RA).Addr->getPredecessor();
1195 };
1196 return RA.Addr->getNextRef(RR, P: Cond, NextOnly: true, G: *this);
1197}
1198
1199// Find the next node related to RA in IA that satisfies condition P.
1200// If such a node was found, return a pair where the second element is the
1201// located node. If such a node does not exist, return a pair where the
1202// first element is the element after which such a node should be inserted,
1203// and the second element is a null-address.
1204template <typename Predicate>
1205std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA,
1206 Predicate P) const {
1207 assert(IA.Id != 0 && RA.Id != 0);
1208
1209 Ref NA;
1210 NodeId Start = RA.Id;
1211 while (true) {
1212 NA = getNextRelated(IA, RA);
1213 if (NA.Id == 0 || NA.Id == Start)
1214 break;
1215 if (P(NA))
1216 break;
1217 RA = NA;
1218 }
1219
1220 if (NA.Id != 0 && NA.Id != Start)
1221 return std::make_pair(x&: RA, y&: NA);
1222 return std::make_pair(x&: RA, y: Ref());
1223}
1224
1225// Get the next shadow node in IA corresponding to RA, and optionally create
1226// such a node if it does not exist.
1227Ref DataFlowGraph::getNextShadow(Instr IA, Ref RA, bool Create) {
1228 assert(IA.Id != 0 && RA.Id != 0);
1229
1230 uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1231 auto IsShadow = [Flags](Ref TA) -> bool {
1232 return TA.Addr->getFlags() == Flags;
1233 };
1234 auto Loc = locateNextRef(IA, RA, P: IsShadow);
1235 if (Loc.second.Id != 0 || !Create)
1236 return Loc.second;
1237
1238 // Create a copy of RA and mark is as shadow.
1239 Ref NA = cloneNode(B: RA);
1240 NA.Addr->setFlags(Flags | NodeAttrs::Shadow);
1241 IA.Addr->addMemberAfter(MA: Loc.first, NA, G: *this);
1242 return NA;
1243}
1244
1245// Create a new statement node in the block node BA that corresponds to
1246// the machine instruction MI.
1247void DataFlowGraph::buildStmt(Block BA, MachineInstr &In) {
1248 Stmt SA = newStmt(Owner: BA, MI: &In);
1249
1250 auto isCall = [](const MachineInstr &In) -> bool {
1251 if (In.isCall())
1252 return true;
1253 // Is tail call?
1254 if (In.isBranch()) {
1255 for (const MachineOperand &Op : In.operands())
1256 if (Op.isGlobal() || Op.isSymbol())
1257 return true;
1258 // Assume indirect branches are calls. This is for the purpose of
1259 // keeping implicit operands, and so it won't hurt on intra-function
1260 // indirect branches.
1261 if (In.isIndirectBranch())
1262 return true;
1263 }
1264 return false;
1265 };
1266
1267 auto isDefUndef = [this](const MachineInstr &In, RegisterRef DR) -> bool {
1268 // This instruction defines DR. Check if there is a use operand that
1269 // would make DR live on entry to the instruction.
1270 for (const MachineOperand &Op : In.all_uses()) {
1271 if (Op.getReg() == 0 || Op.isUndef())
1272 continue;
1273 RegisterRef UR = makeRegRef(Op);
1274 if (getPRI().alias(RA: DR, RB: UR))
1275 return false;
1276 }
1277 return true;
1278 };
1279
1280 bool IsCall = isCall(In);
1281 unsigned NumOps = In.getNumOperands();
1282
1283 // Avoid duplicate implicit defs. This will not detect cases of implicit
1284 // defs that define registers that overlap, but it is not clear how to
1285 // interpret that in the absence of explicit defs. Overlapping explicit
1286 // defs are likely illegal already.
1287 BitVector DoneDefs(TRI.getNumRegs());
1288 // Process explicit defs first.
1289 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1290 MachineOperand &Op = In.getOperand(i: OpN);
1291 if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
1292 continue;
1293 Register R = Op.getReg();
1294 if (!R || !R.isPhysical() || !isTracked(RR: RegisterRef(R)))
1295 continue;
1296 uint16_t Flags = NodeAttrs::None;
1297 if (TOI.isPreserving(In, OpNum: OpN)) {
1298 Flags |= NodeAttrs::Preserving;
1299 // If the def is preserving, check if it is also undefined.
1300 if (isDefUndef(In, makeRegRef(Op)))
1301 Flags |= NodeAttrs::Undef;
1302 }
1303 if (TOI.isClobbering(In, OpNum: OpN))
1304 Flags |= NodeAttrs::Clobbering;
1305 if (TOI.isFixedReg(In, OpNum: OpN))
1306 Flags |= NodeAttrs::Fixed;
1307 if (IsCall && Op.isDead())
1308 Flags |= NodeAttrs::Dead;
1309 Def DA = newDef(Owner: SA, Op, Flags);
1310 SA.Addr->addMember(NA: DA, G: *this);
1311 assert(!DoneDefs.test(R));
1312 DoneDefs.set(R);
1313 }
1314
1315 // Process reg-masks (as clobbers).
1316 BitVector DoneClobbers(TRI.getNumRegs());
1317 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1318 MachineOperand &Op = In.getOperand(i: OpN);
1319 if (!Op.isRegMask())
1320 continue;
1321 uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | NodeAttrs::Dead;
1322 Def DA = newDef(Owner: SA, Op, Flags);
1323 SA.Addr->addMember(NA: DA, G: *this);
1324 // Record all clobbered registers in DoneDefs.
1325 const uint32_t *RM = Op.getRegMask();
1326 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
1327 if (!isTracked(RR: RegisterRef(i)))
1328 continue;
1329 if (!(RM[i / 32] & (1u << (i % 32))))
1330 DoneClobbers.set(i);
1331 }
1332 }
1333
1334 // Process implicit defs, skipping those that have already been added
1335 // as explicit.
1336 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1337 MachineOperand &Op = In.getOperand(i: OpN);
1338 if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())
1339 continue;
1340 Register R = Op.getReg();
1341 if (!R || !R.isPhysical() || !isTracked(RR: RegisterRef(R)) || DoneDefs.test(Idx: R))
1342 continue;
1343 RegisterRef RR = makeRegRef(Op);
1344 uint16_t Flags = NodeAttrs::None;
1345 if (TOI.isPreserving(In, OpNum: OpN)) {
1346 Flags |= NodeAttrs::Preserving;
1347 // If the def is preserving, check if it is also undefined.
1348 if (isDefUndef(In, RR))
1349 Flags |= NodeAttrs::Undef;
1350 }
1351 if (TOI.isClobbering(In, OpNum: OpN))
1352 Flags |= NodeAttrs::Clobbering;
1353 if (TOI.isFixedReg(In, OpNum: OpN))
1354 Flags |= NodeAttrs::Fixed;
1355 if (IsCall && Op.isDead()) {
1356 if (DoneClobbers.test(Idx: R))
1357 continue;
1358 Flags |= NodeAttrs::Dead;
1359 }
1360 Def DA = newDef(Owner: SA, Op, Flags);
1361 SA.Addr->addMember(NA: DA, G: *this);
1362 DoneDefs.set(R);
1363 }
1364
1365 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1366 MachineOperand &Op = In.getOperand(i: OpN);
1367 if (!Op.isReg() || !Op.isUse())
1368 continue;
1369 Register R = Op.getReg();
1370 if (!R || !R.isPhysical() || !isTracked(RR: RegisterRef(R)))
1371 continue;
1372 uint16_t Flags = NodeAttrs::None;
1373 if (Op.isUndef())
1374 Flags |= NodeAttrs::Undef;
1375 if (TOI.isFixedReg(In, OpNum: OpN))
1376 Flags |= NodeAttrs::Fixed;
1377 Use UA = newUse(Owner: SA, Op, Flags);
1378 SA.Addr->addMember(NA: UA, G: *this);
1379 }
1380}
1381
1382// Scan all defs in the block node BA and record in PhiM the locations of
1383// phi nodes corresponding to these defs.
1384// Clobbering defs in BA are recorded in PhiClobberM
1385void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,
1386 BlockRefsMap &PhiClobberM, Block BA) {
1387 // Check all defs from block BA and record them in each block in BA's
1388 // iterated dominance frontier. This information will later be used to
1389 // create phi nodes.
1390 MachineBasicBlock *BB = BA.Addr->getCode();
1391 assert(BB);
1392 auto DFLoc = MDF.find(B: BB);
1393 if (DFLoc == MDF.end() || DFLoc->second.empty())
1394 return;
1395
1396 // Traverse all instructions in the block and collect the set of all
1397 // defined references. For each reference there will be a phi created
1398 // in the block's iterated dominance frontier.
1399 // This is done to make sure that each defined reference gets only one
1400 // phi node, even if it is defined multiple times.
1401 RegisterAggr Defs(getPRI());
1402 RegisterAggr ClobberDefs(getPRI());
1403 for (Instr IA : BA.Addr->members(G: *this)) {
1404 for (Ref RA : IA.Addr->members_if(P: IsDef, G: *this)) {
1405 RegisterRef RR = RA.Addr->getRegRef(G: *this);
1406 if (!isTracked(RR))
1407 continue;
1408 if (RR.isReg())
1409 Defs.insert(RR);
1410 // Clobbering def
1411 else if (RR.isMask())
1412 ClobberDefs.insert(RR);
1413 }
1414 }
1415
1416 // Calculate the iterated dominance frontier of BB.
1417 const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;
1418 SetVector<MachineBasicBlock *> IDF(llvm::from_range, DF);
1419 for (unsigned i = 0; i < IDF.size(); ++i) {
1420 auto F = MDF.find(B: IDF[i]);
1421 if (F != MDF.end())
1422 IDF.insert_range(R: F->second);
1423 }
1424
1425 // Finally, add the set of defs to each block in the iterated dominance
1426 // frontier.
1427 for (auto *DB : IDF) {
1428 Block DBA = findBlock(BB: DB);
1429 PhiM[DBA.Id].insert(RG: Defs);
1430 PhiClobberM[DBA.Id].insert(RG: ClobberDefs);
1431 }
1432}
1433
1434// Given the locations of phi nodes in the map PhiM, create the phi nodes
1435// that are located in the block node BA.
1436void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block BA,
1437 const DefStackMap &DefM) {
1438 // Check if this blocks has any DF defs, i.e. if there are any defs
1439 // that this block is in the iterated dominance frontier of.
1440 auto HasDF = PhiM.find(Key: BA.Id);
1441 if (HasDF == PhiM.end() || HasDF->second.empty())
1442 return;
1443
1444 // Prepare a list of NodeIds of the block's predecessors.
1445 NodeList Preds;
1446 const MachineBasicBlock *MBB = BA.Addr->getCode();
1447 for (MachineBasicBlock *PB : MBB->predecessors())
1448 Preds.push_back(Elt: findBlock(BB: PB));
1449
1450 RegisterAggr PhiDefs(getPRI());
1451 // DefM will be non empty when we are building phis
1452 // for clobbering defs
1453 if (!DefM.empty()) {
1454 for (Instr IA : BA.Addr->members_if(P: IsPhi, G: *this)) {
1455 for (Def DA : IA.Addr->members_if(P: IsDef, G: *this)) {
1456 auto DR = DA.Addr->getRegRef(G: *this);
1457 PhiDefs.insert(RR: DR);
1458 }
1459 }
1460 }
1461
1462 MachineRegisterInfo &MRI = MF.getRegInfo();
1463 const RegisterAggr &Defs = PhiM[BA.Id];
1464 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
1465
1466 for (RegisterRef RR : Defs.refs()) {
1467 if (!DefM.empty()) {
1468 auto F = DefM.find(x: RR.Reg);
1469 // Do not create a phi for unallocatable registers, or for registers
1470 // that are never livein to BA.
1471 // If a phi exists for RR, do not create another.
1472 if (!MRI.isAllocatable(PhysReg: RR.Reg) || PhiDefs.hasCoverOf(RR) ||
1473 F == DefM.end() || F->second.empty())
1474 continue;
1475 // Do not create a phi, if all reaching defs are clobbering
1476 auto RDef = F->second.top();
1477 if (RDef->Addr->getFlags() & NodeAttrs::Clobbering)
1478 continue;
1479 PhiDefs.insert(RR);
1480 }
1481 Phi PA = newPhi(Owner: BA);
1482 PA.Addr->addMember(NA: newDef(Owner: PA, RR, Flags: PhiFlags), G: *this);
1483
1484 // Add phi uses.
1485 for (Block PBA : Preds) {
1486 PA.Addr->addMember(NA: newPhiUse(Owner: PA, RR, PredB: PBA), G: *this);
1487 }
1488 }
1489}
1490
1491// Remove any unneeded phi nodes that were created during the build process.
1492void DataFlowGraph::removeUnusedPhis() {
1493 // This will remove unused phis, i.e. phis where each def does not reach
1494 // any uses or other defs. This will not detect or remove circular phi
1495 // chains that are otherwise dead. Unused/dead phis are created during
1496 // the build process and this function is intended to remove these cases
1497 // that are easily determinable to be unnecessary.
1498
1499 SetVector<NodeId> PhiQ;
1500 for (Block BA : TheFunc.Addr->members(G: *this)) {
1501 for (auto P : BA.Addr->members_if(P: IsPhi, G: *this))
1502 PhiQ.insert(X: P.Id);
1503 }
1504
1505 static auto HasUsedDef = [](NodeList &Ms) -> bool {
1506 for (Node M : Ms) {
1507 if (M.Addr->getKind() != NodeAttrs::Def)
1508 continue;
1509 Def DA = M;
1510 if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)
1511 return true;
1512 }
1513 return false;
1514 };
1515
1516 // Any phi, if it is removed, may affect other phis (make them dead).
1517 // For each removed phi, collect the potentially affected phis and add
1518 // them back to the queue.
1519 while (!PhiQ.empty()) {
1520 auto PA = addr<PhiNode *>(N: PhiQ[0]);
1521 PhiQ.remove(X: PA.Id);
1522 NodeList Refs = PA.Addr->members(G: *this);
1523 if (HasUsedDef(Refs))
1524 continue;
1525 for (Ref RA : Refs) {
1526 if (NodeId RD = RA.Addr->getReachingDef()) {
1527 auto RDA = addr<DefNode *>(N: RD);
1528 Instr OA = RDA.Addr->getOwner(G: *this);
1529 if (IsPhi(BA: OA))
1530 PhiQ.insert(X: OA.Id);
1531 }
1532 if (RA.Addr->isDef())
1533 unlinkDef(DA: RA, RemoveFromOwner: true);
1534 else
1535 unlinkUse(UA: RA, RemoveFromOwner: true);
1536 }
1537 Block BA = PA.Addr->getOwner(G: *this);
1538 BA.Addr->removeMember(NA: PA, G: *this);
1539 }
1540}
1541
1542// For a given reference node TA in an instruction node IA, connect the
1543// reaching def of TA to the appropriate def node. Create any shadow nodes
1544// as appropriate.
1545template <typename T>
1546void DataFlowGraph::linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS) {
1547 if (DS.empty())
1548 return;
1549 RegisterRef RR = TA.Addr->getRegRef(*this);
1550 NodeAddr<T> TAP;
1551
1552 // References from the def stack that have been examined so far.
1553 RegisterAggr Defs(getPRI());
1554
1555 for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {
1556 RegisterRef QR = I->Addr->getRegRef(G: *this);
1557
1558 // Skip all defs that we have already seen.
1559 // If this completes a cover of RR, stop the stack traversal.
1560 bool Seen = Defs.hasCoverOf(RR: QR);
1561 if (Seen)
1562 continue;
1563
1564 bool Cover = Defs.insert(RR: QR).hasCoverOf(RR);
1565
1566 // The reaching def.
1567 Def RDA = *I;
1568
1569 // Pick the reached node.
1570 if (TAP.Id == 0) {
1571 TAP = TA;
1572 } else {
1573 // Mark the existing ref as "shadow" and create a new shadow.
1574 TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);
1575 TAP = getNextShadow(IA, RA: TAP, Create: true);
1576 }
1577
1578 // Create the link.
1579 TAP.Addr->linkToDef(TAP.Id, RDA);
1580
1581 if (Cover)
1582 break;
1583 }
1584}
1585
1586// Create data-flow links for all reference nodes in the statement node SA.
1587template <typename Predicate>
1588void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) {
1589#ifndef NDEBUG
1590 RegisterSet Defs(getPRI());
1591#endif
1592
1593 // Link all nodes (upwards in the data-flow) with their reaching defs.
1594 for (Ref RA : SA.Addr->members_if(P, *this)) {
1595 uint16_t Kind = RA.Addr->getKind();
1596 assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use);
1597 RegisterRef RR = RA.Addr->getRegRef(G: *this);
1598#ifndef NDEBUG
1599 // Do not expect multiple defs of the same reference.
1600 assert(Kind != NodeAttrs::Def || !Defs.count(RR));
1601 Defs.insert(RR);
1602#endif
1603
1604 auto F = DefM.find(x: RR.Reg);
1605 if (F == DefM.end())
1606 continue;
1607 DefStack &DS = F->second;
1608 if (Kind == NodeAttrs::Use)
1609 linkRefUp<UseNode *>(IA: SA, TA: RA, DS);
1610 else if (Kind == NodeAttrs::Def)
1611 linkRefUp<DefNode *>(IA: SA, TA: RA, DS);
1612 else
1613 llvm_unreachable("Unexpected node in instruction");
1614 }
1615}
1616
1617// Create data-flow links for all instructions in the block node BA. This
1618// will include updating any phi nodes in BA.
1619void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, BlockRefsMap &PhiClobberM,
1620 Block BA) {
1621 // Create phi nodes for clobbering defs.
1622 // Since a huge number of registers can get clobbered, it would result in many
1623 // phi nodes being created in the graph. Only create phi nodes that have a non
1624 // clobbering reaching def. Use DefM to get not clobbering defs reaching a
1625 // block.
1626 buildPhis(PhiM&: PhiClobberM, BA, DefM);
1627
1628 // Push block delimiters.
1629 markBlock(B: BA.Id, DefM);
1630
1631 auto IsClobber = [](Ref RA) -> bool {
1632 return IsDef(BA: RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);
1633 };
1634 auto IsNoClobber = [](Ref RA) -> bool {
1635 return IsDef(BA: RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);
1636 };
1637
1638 assert(BA.Addr && "block node address is needed to create a data-flow link");
1639 // For each non-phi instruction in the block, link all the defs and uses
1640 // to their reaching defs. For any member of the block (including phis),
1641 // push the defs on the corresponding stacks.
1642 for (Instr IA : BA.Addr->members(G: *this)) {
1643 // Ignore phi nodes here. They will be linked part by part from the
1644 // predecessors.
1645 if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1646 linkStmtRefs(DefM, SA: IA, P: IsUse);
1647 linkStmtRefs(DefM, SA: IA, P: IsClobber);
1648 }
1649
1650 // Push the definitions on the stack.
1651 pushClobbers(IA, DefM);
1652
1653 if (IA.Addr->getKind() == NodeAttrs::Stmt)
1654 linkStmtRefs(DefM, SA: IA, P: IsNoClobber);
1655
1656 pushDefs(IA, DefM);
1657 }
1658
1659 // Recursively process all children in the dominator tree.
1660 MachineDomTreeNode *N = MDT.getNode(BB: BA.Addr->getCode());
1661 for (auto *I : *N) {
1662 MachineBasicBlock *SB = I->getBlock();
1663 Block SBA = findBlock(BB: SB);
1664 linkBlockRefs(DefM, PhiClobberM, BA: SBA);
1665 }
1666
1667 // Link the phi uses from the successor blocks.
1668 auto IsUseForBA = [BA](Node NA) -> bool {
1669 if (NA.Addr->getKind() != NodeAttrs::Use)
1670 return false;
1671 assert(NA.Addr->getFlags() & NodeAttrs::PhiRef);
1672 return PhiUse(NA).Addr->getPredecessor() == BA.Id;
1673 };
1674
1675 RegisterAggr EHLiveIns = getLandingPadLiveIns();
1676 MachineBasicBlock *MBB = BA.Addr->getCode();
1677
1678 for (MachineBasicBlock *SB : MBB->successors()) {
1679 bool IsEHPad = SB->isEHPad();
1680 Block SBA = findBlock(BB: SB);
1681 for (Instr IA : SBA.Addr->members_if(P: IsPhi, G: *this)) {
1682 // Do not link phi uses for landing pad live-ins.
1683 if (IsEHPad) {
1684 // Find what register this phi is for.
1685 Ref RA = IA.Addr->getFirstMember(G: *this);
1686 assert(RA.Id != 0);
1687 if (EHLiveIns.hasCoverOf(RR: RA.Addr->getRegRef(G: *this)))
1688 continue;
1689 }
1690 // Go over each phi use associated with MBB, and link it.
1691 for (auto U : IA.Addr->members_if(P: IsUseForBA, G: *this)) {
1692 PhiUse PUA = U;
1693 RegisterRef RR = PUA.Addr->getRegRef(G: *this);
1694 linkRefUp<UseNode *>(IA, TA: PUA, DS&: DefM[RR.Reg]);
1695 }
1696 }
1697 }
1698
1699 // Pop all defs from this block from the definition stacks.
1700 releaseBlock(B: BA.Id, DefM);
1701}
1702
1703// Remove the use node UA from any data-flow and structural links.
1704void DataFlowGraph::unlinkUseDF(Use UA) {
1705 NodeId RD = UA.Addr->getReachingDef();
1706 NodeId Sib = UA.Addr->getSibling();
1707
1708 if (RD == 0) {
1709 assert(Sib == 0);
1710 return;
1711 }
1712
1713 auto RDA = addr<DefNode *>(N: RD);
1714 auto TA = addr<UseNode *>(N: RDA.Addr->getReachedUse());
1715 if (TA.Id == UA.Id) {
1716 RDA.Addr->setReachedUse(Sib);
1717 return;
1718 }
1719
1720 while (TA.Id != 0) {
1721 NodeId S = TA.Addr->getSibling();
1722 if (S == UA.Id) {
1723 TA.Addr->setSibling(UA.Addr->getSibling());
1724 return;
1725 }
1726 TA = addr<UseNode *>(N: S);
1727 }
1728}
1729
1730// Remove the def node DA from any data-flow and structural links.
1731void DataFlowGraph::unlinkDefDF(Def DA) {
1732 //
1733 // RD
1734 // | reached
1735 // | def
1736 // :
1737 // .
1738 // +----+
1739 // ... -- | DA | -- ... -- 0 : sibling chain of DA
1740 // +----+
1741 // | | reached
1742 // | : def
1743 // | .
1744 // | ... : Siblings (defs)
1745 // |
1746 // : reached
1747 // . use
1748 // ... : sibling chain of reached uses
1749
1750 NodeId RD = DA.Addr->getReachingDef();
1751
1752 // Visit all siblings of the reached def and reset their reaching defs.
1753 // Also, defs reached by DA are now "promoted" to being reached by RD,
1754 // so all of them will need to be spliced into the sibling chain where
1755 // DA belongs.
1756 auto getAllNodes = [this](NodeId N) -> NodeList {
1757 NodeList Res;
1758 while (N) {
1759 auto RA = addr<RefNode *>(N);
1760 // Keep the nodes in the exact sibling order.
1761 Res.push_back(Elt: RA);
1762 N = RA.Addr->getSibling();
1763 }
1764 return Res;
1765 };
1766 NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());
1767 NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());
1768
1769 if (RD == 0) {
1770 for (Ref I : ReachedDefs)
1771 I.Addr->setSibling(0);
1772 for (Ref I : ReachedUses)
1773 I.Addr->setSibling(0);
1774 }
1775 for (Def I : ReachedDefs)
1776 I.Addr->setReachingDef(RD);
1777 for (Use I : ReachedUses)
1778 I.Addr->setReachingDef(RD);
1779
1780 NodeId Sib = DA.Addr->getSibling();
1781 if (RD == 0) {
1782 assert(Sib == 0);
1783 return;
1784 }
1785
1786 // Update the reaching def node and remove DA from the sibling list.
1787 auto RDA = addr<DefNode *>(N: RD);
1788 auto TA = addr<DefNode *>(N: RDA.Addr->getReachedDef());
1789 if (TA.Id == DA.Id) {
1790 // If DA is the first reached def, just update the RD's reached def
1791 // to the DA's sibling.
1792 RDA.Addr->setReachedDef(Sib);
1793 } else {
1794 // Otherwise, traverse the sibling list of the reached defs and remove
1795 // DA from it.
1796 while (TA.Id != 0) {
1797 NodeId S = TA.Addr->getSibling();
1798 if (S == DA.Id) {
1799 TA.Addr->setSibling(Sib);
1800 break;
1801 }
1802 TA = addr<DefNode *>(N: S);
1803 }
1804 }
1805
1806 // Splice the DA's reached defs into the RDA's reached def chain.
1807 if (!ReachedDefs.empty()) {
1808 auto Last = Def(ReachedDefs.back());
1809 Last.Addr->setSibling(RDA.Addr->getReachedDef());
1810 RDA.Addr->setReachedDef(ReachedDefs.front().Id);
1811 }
1812 // Splice the DA's reached uses into the RDA's reached use chain.
1813 if (!ReachedUses.empty()) {
1814 auto Last = Use(ReachedUses.back());
1815 Last.Addr->setSibling(RDA.Addr->getReachedUse());
1816 RDA.Addr->setReachedUse(ReachedUses.front().Id);
1817 }
1818}
1819
1820bool DataFlowGraph::isTracked(RegisterRef RR) const {
1821 return !disjoint(A: getPRI().getUnits(RR), B: TrackedUnits);
1822}
1823
1824bool DataFlowGraph::hasUntrackedRef(Stmt S, bool IgnoreReserved) const {
1825 SmallVector<MachineOperand *> Ops;
1826
1827 for (Ref R : S.Addr->members(G: *this)) {
1828 Ops.push_back(Elt: &R.Addr->getOp());
1829 RegisterRef RR = R.Addr->getRegRef(G: *this);
1830 if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.idx()])
1831 continue;
1832 if (!isTracked(RR))
1833 return true;
1834 }
1835 for (const MachineOperand &Op : S.Addr->getCode()->operands()) {
1836 if (!Op.isReg() && !Op.isRegMask())
1837 continue;
1838 if (!llvm::is_contained(Range&: Ops, Element: &Op))
1839 return true;
1840 }
1841 return false;
1842}
1843
1844} // end namespace llvm::rdf
1845