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/IR/Module.h"
29#include "llvm/MC/LaneBitmask.h"
30#include "llvm/MC/MCInstrDesc.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/raw_ostream.h"
33#include "llvm/Target/TargetMachine.h"
34#include <cassert>
35#include <cstdint>
36#include <cstring>
37#include <set>
38#include <utility>
39#include <vector>
40
41// Printing functions. Have them here first, so that the rest of the code
42// can use them.
43namespace llvm::rdf {
44
45raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P) {
46 P.G.getPRI().print(OS, A: P.Obj);
47 return OS;
48}
49
50raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P) {
51 if (P.Obj == 0)
52 return OS << "null";
53 auto NA = P.G.addr<NodeBase *>(N: P.Obj);
54 uint16_t Attrs = NA.Addr->getAttrs();
55 uint16_t Kind = NodeAttrs::kind(T: Attrs);
56 uint16_t Flags = NodeAttrs::flags(T: Attrs);
57 switch (NodeAttrs::type(T: Attrs)) {
58 case NodeAttrs::Code:
59 switch (Kind) {
60 case NodeAttrs::Func:
61 OS << 'f';
62 break;
63 case NodeAttrs::Block:
64 OS << 'b';
65 break;
66 case NodeAttrs::Stmt:
67 OS << 's';
68 break;
69 case NodeAttrs::Phi:
70 OS << 'p';
71 break;
72 default:
73 OS << "c?";
74 break;
75 }
76 break;
77 case NodeAttrs::Ref:
78 if (Flags & NodeAttrs::Undef)
79 OS << '/';
80 if (Flags & NodeAttrs::Dead)
81 OS << '\\';
82 if (Flags & NodeAttrs::Preserving)
83 OS << '+';
84 if (Flags & NodeAttrs::Clobbering)
85 OS << '~';
86 switch (Kind) {
87 case NodeAttrs::Use:
88 OS << 'u';
89 break;
90 case NodeAttrs::Def:
91 OS << 'd';
92 break;
93 case NodeAttrs::Block:
94 OS << 'b';
95 break;
96 default:
97 OS << "r?";
98 break;
99 }
100 break;
101 default:
102 OS << '?';
103 break;
104 }
105 OS << P.Obj;
106 if (Flags & NodeAttrs::Shadow)
107 OS << '"';
108 return OS;
109}
110
111static void printRefHeader(raw_ostream &OS, const Ref RA,
112 const DataFlowGraph &G) {
113 OS << Print(RA.Id, G) << '<' << Print(RA.Addr->getRegRef(G), G) << '>';
114 if (RA.Addr->getFlags() & NodeAttrs::Fixed)
115 OS << '!';
116}
117
118raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P) {
119 printRefHeader(OS, RA: P.Obj, G: P.G);
120 OS << '(';
121 if (NodeId N = P.Obj.Addr->getReachingDef())
122 OS << Print(N, P.G);
123 OS << ',';
124 if (NodeId N = P.Obj.Addr->getReachedDef())
125 OS << Print(N, P.G);
126 OS << ',';
127 if (NodeId N = P.Obj.Addr->getReachedUse())
128 OS << Print(N, P.G);
129 OS << "):";
130 if (NodeId N = P.Obj.Addr->getSibling())
131 OS << Print(N, P.G);
132 return OS;
133}
134
135raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P) {
136 printRefHeader(OS, RA: P.Obj, G: P.G);
137 OS << '(';
138 if (NodeId N = P.Obj.Addr->getReachingDef())
139 OS << Print(N, P.G);
140 OS << "):";
141 if (NodeId N = P.Obj.Addr->getSibling())
142 OS << Print(N, P.G);
143 return OS;
144}
145
146raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P) {
147 printRefHeader(OS, RA: P.Obj, G: P.G);
148 OS << '(';
149 if (NodeId N = P.Obj.Addr->getReachingDef())
150 OS << Print(N, P.G);
151 OS << ',';
152 if (NodeId N = P.Obj.Addr->getPredecessor())
153 OS << Print(N, P.G);
154 OS << "):";
155 if (NodeId N = P.Obj.Addr->getSibling())
156 OS << Print(N, P.G);
157 return OS;
158}
159
160raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &P) {
161 switch (P.Obj.Addr->getKind()) {
162 case NodeAttrs::Def:
163 OS << PrintNode<DefNode *>(P.Obj, P.G);
164 break;
165 case NodeAttrs::Use:
166 if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef)
167 OS << PrintNode<PhiUseNode *>(P.Obj, P.G);
168 else
169 OS << PrintNode<UseNode *>(P.Obj, P.G);
170 break;
171 }
172 return OS;
173}
174
175raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P) {
176 unsigned N = P.Obj.size();
177 for (auto I : P.Obj) {
178 OS << Print(I.Id, P.G);
179 if (--N)
180 OS << ' ';
181 }
182 return OS;
183}
184
185raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P) {
186 unsigned N = P.Obj.size();
187 for (auto I : P.Obj) {
188 OS << Print(I, P.G);
189 if (--N)
190 OS << ' ';
191 }
192 return OS;
193}
194
195namespace {
196
197template <typename T> struct PrintListV {
198 PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {}
199
200 using Type = T;
201 const NodeList &List;
202 const DataFlowGraph &G;
203};
204
205template <typename T>
206raw_ostream &operator<<(raw_ostream &OS, const PrintListV<T> &P) {
207 unsigned N = P.List.size();
208 for (NodeAddr<T> A : P.List) {
209 OS << PrintNode<T>(A, P.G);
210 if (--N)
211 OS << ", ";
212 }
213 return OS;
214}
215
216} // end anonymous namespace
217
218raw_ostream &operator<<(raw_ostream &OS, const Print<Phi> &P) {
219 OS << Print(P.Obj.Id, P.G) << ": phi ["
220 << PrintListV<RefNode *>(P.Obj.Addr->members(G: P.G), P.G) << ']';
221 return OS;
222}
223
224raw_ostream &operator<<(raw_ostream &OS, const Print<Stmt> &P) {
225 const MachineInstr &MI = *P.Obj.Addr->getCode();
226 unsigned Opc = MI.getOpcode();
227 OS << Print(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opcode: Opc);
228 // Print the target for calls and branches (for readability).
229 if (MI.isCall() || MI.isBranch()) {
230 MachineInstr::const_mop_iterator T =
231 llvm::find_if(Range: MI.operands(), P: [](const MachineOperand &Op) -> bool {
232 return Op.isMBB() || Op.isGlobal() || Op.isSymbol();
233 });
234 if (T != MI.operands_end()) {
235 OS << ' ';
236 if (T->isMBB())
237 OS << printMBBReference(MBB: *T->getMBB());
238 else if (T->isGlobal())
239 OS << T->getGlobal()->getName();
240 else if (T->isSymbol())
241 OS << T->getSymbolName();
242 }
243 }
244 OS << " [" << PrintListV<RefNode *>(P.Obj.Addr->members(G: P.G), P.G) << ']';
245 return OS;
246}
247
248raw_ostream &operator<<(raw_ostream &OS, const Print<Instr> &P) {
249 switch (P.Obj.Addr->getKind()) {
250 case NodeAttrs::Phi:
251 OS << PrintNode<PhiNode *>(P.Obj, P.G);
252 break;
253 case NodeAttrs::Stmt:
254 OS << PrintNode<StmtNode *>(P.Obj, P.G);
255 break;
256 default:
257 OS << "instr? " << Print(P.Obj.Id, P.G);
258 break;
259 }
260 return OS;
261}
262
263raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &P) {
264 MachineBasicBlock *BB = P.Obj.Addr->getCode();
265 unsigned NP = BB->pred_size();
266 std::vector<int> Ns;
267 auto PrintBBs = [&OS](const std::vector<int> &Ns) -> void {
268 unsigned N = Ns.size();
269 for (int I : Ns) {
270 OS << "%bb." << I;
271 if (--N)
272 OS << ", ";
273 }
274 };
275
276 OS << Print(P.Obj.Id, P.G) << ": --- " << printMBBReference(MBB: *BB)
277 << " --- preds(" << NP << "): ";
278 for (MachineBasicBlock *B : BB->predecessors())
279 Ns.push_back(x: B->getNumber());
280 PrintBBs(Ns);
281
282 unsigned NS = BB->succ_size();
283 OS << " succs(" << NS << "): ";
284 Ns.clear();
285 for (MachineBasicBlock *B : BB->successors())
286 Ns.push_back(x: B->getNumber());
287 PrintBBs(Ns);
288 OS << '\n';
289
290 for (auto I : P.Obj.Addr->members(G: P.G))
291 OS << PrintNode<InstrNode *>(I, P.G) << '\n';
292 return OS;
293}
294
295raw_ostream &operator<<(raw_ostream &OS, const Print<Func> &P) {
296 OS << "DFG dump:[\n"
297 << Print(P.Obj.Id, P.G)
298 << ": Function: " << P.Obj.Addr->getCode()->getName() << '\n';
299 for (auto I : P.Obj.Addr->members(G: P.G))
300 OS << PrintNode<BlockNode *>(I, P.G) << '\n';
301 OS << "]\n";
302 return OS;
303}
304
305raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P) {
306 OS << '{';
307 for (auto I : P.Obj)
308 OS << ' ' << Print(I, P.G);
309 OS << " }";
310 return OS;
311}
312
313raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P) {
314 OS << P.Obj;
315 return OS;
316}
317
318raw_ostream &operator<<(raw_ostream &OS,
319 const Print<DataFlowGraph::DefStack> &P) {
320 for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E;) {
321 OS << Print(I->Id, P.G) << '<' << Print(I->Addr->getRegRef(G: P.G), P.G)
322 << '>';
323 I.down();
324 if (I != E)
325 OS << ' ';
326 }
327 return OS;
328}
329
330// Node allocation functions.
331//
332// Node allocator is like a slab memory allocator: it allocates blocks of
333// memory in sizes that are multiples of the size of a node. Each block has
334// the same size. Nodes are allocated from the currently active block, and
335// when it becomes full, a new one is created.
336// There is a mapping scheme between node id and its location in a block,
337// and within that block is described in the header file.
338//
339void NodeAllocator::startNewBlock() {
340 void *T = MemPool.Allocate(Size: NodesPerBlock * NodeMemSize, Alignment: NodeMemSize);
341 char *P = static_cast<char *>(T);
342 Blocks.push_back(x: P);
343 // Check if the block index is still within the allowed range, i.e. less
344 // than 2^N, where N is the number of bits in NodeId for the block index.
345 // BitsPerIndex is the number of bits per node index.
346 assert((Blocks.size() < ((size_t)1 << (8 * sizeof(NodeId) - BitsPerIndex))) &&
347 "Out of bits for block index");
348 ActiveEnd = P;
349}
350
351bool NodeAllocator::needNewBlock() {
352 if (Blocks.empty())
353 return true;
354
355 char *ActiveBegin = Blocks.back();
356 uint32_t Index = (ActiveEnd - ActiveBegin) / NodeMemSize;
357 return Index >= NodesPerBlock;
358}
359
360Node NodeAllocator::New() {
361 if (needNewBlock())
362 startNewBlock();
363
364 uint32_t ActiveB = Blocks.size() - 1;
365 uint32_t Index = (ActiveEnd - Blocks[ActiveB]) / NodeMemSize;
366 Node NA = {reinterpret_cast<NodeBase *>(ActiveEnd), makeId(Block: ActiveB, Index)};
367 ActiveEnd += NodeMemSize;
368 return NA;
369}
370
371NodeId NodeAllocator::id(const NodeBase *P) const {
372 uintptr_t A = reinterpret_cast<uintptr_t>(P);
373 for (unsigned i = 0, n = Blocks.size(); i != n; ++i) {
374 uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]);
375 if (A < B || A >= B + NodesPerBlock * NodeMemSize)
376 continue;
377 uint32_t Idx = (A - B) / NodeMemSize;
378 return makeId(Block: i, Index: Idx);
379 }
380 llvm_unreachable("Invalid node address");
381}
382
383void NodeAllocator::clear() {
384 MemPool.Reset();
385 Blocks.clear();
386 ActiveEnd = nullptr;
387}
388
389// Insert node NA after "this" in the circular chain.
390void NodeBase::append(Node NA) {
391 NodeId Nx = Next;
392 // If NA is already "next", do nothing.
393 if (Next != NA.Id) {
394 Next = NA.Id;
395 NA.Addr->Next = Nx;
396 }
397}
398
399// Fundamental node manipulator functions.
400
401// Obtain the register reference from a reference node.
402RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const {
403 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
404 if (NodeAttrs::flags(T: Attrs) & NodeAttrs::PhiRef)
405 return G.unpack(PR: RefData.PR);
406 assert(RefData.Op != nullptr);
407 return G.makeRegRef(Op: *RefData.Op);
408}
409
410// Set the register reference in the reference node directly (for references
411// in phi nodes).
412void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) {
413 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
414 assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef);
415 RefData.PR = G.pack(RR);
416}
417
418// Set the register reference in the reference node based on a machine
419// operand (for references in statement nodes).
420void RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) {
421 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
422 assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef));
423 (void)G;
424 RefData.Op = Op;
425}
426
427// Get the owner of a given reference node.
428Node RefNode::getOwner(const DataFlowGraph &G) {
429 Node NA = G.addr<NodeBase *>(N: getNext());
430
431 while (NA.Addr != this) {
432 if (NA.Addr->getType() == NodeAttrs::Code)
433 return NA;
434 NA = G.addr<NodeBase *>(N: NA.Addr->getNext());
435 }
436 llvm_unreachable("No owner in circular list");
437}
438
439// Connect the def node to the reaching def node.
440void DefNode::linkToDef(NodeId Self, Def DA) {
441 RefData.RD = DA.Id;
442 RefData.Sib = DA.Addr->getReachedDef();
443 DA.Addr->setReachedDef(Self);
444}
445
446// Connect the use node to the reaching def node.
447void UseNode::linkToDef(NodeId Self, Def DA) {
448 RefData.RD = DA.Id;
449 RefData.Sib = DA.Addr->getReachedUse();
450 DA.Addr->setReachedUse(Self);
451}
452
453// Get the first member of the code node.
454Node CodeNode::getFirstMember(const DataFlowGraph &G) const {
455 if (CodeData.FirstM == 0)
456 return Node();
457 return G.addr<NodeBase *>(N: CodeData.FirstM);
458}
459
460// Get the last member of the code node.
461Node CodeNode::getLastMember(const DataFlowGraph &G) const {
462 if (CodeData.LastM == 0)
463 return Node();
464 return G.addr<NodeBase *>(N: CodeData.LastM);
465}
466
467// Add node NA at the end of the member list of the given code node.
468void CodeNode::addMember(Node NA, const DataFlowGraph &G) {
469 Node ML = getLastMember(G);
470 if (ML.Id != 0) {
471 ML.Addr->append(NA);
472 } else {
473 CodeData.FirstM = NA.Id;
474 NodeId Self = G.id(P: this);
475 NA.Addr->setNext(Self);
476 }
477 CodeData.LastM = NA.Id;
478}
479
480// Add node NA after member node MA in the given code node.
481void CodeNode::addMemberAfter(Node MA, Node NA, const DataFlowGraph &G) {
482 MA.Addr->append(NA);
483 if (CodeData.LastM == MA.Id)
484 CodeData.LastM = NA.Id;
485}
486
487// Remove member node NA from the given code node.
488void CodeNode::removeMember(Node NA, const DataFlowGraph &G) {
489 Node MA = getFirstMember(G);
490 assert(MA.Id != 0);
491
492 // Special handling if the member to remove is the first member.
493 if (MA.Id == NA.Id) {
494 if (CodeData.LastM == MA.Id) {
495 // If it is the only member, set both first and last to 0.
496 CodeData.FirstM = CodeData.LastM = 0;
497 } else {
498 // Otherwise, advance the first member.
499 CodeData.FirstM = MA.Addr->getNext();
500 }
501 return;
502 }
503
504 while (MA.Addr != this) {
505 NodeId MX = MA.Addr->getNext();
506 if (MX == NA.Id) {
507 MA.Addr->setNext(NA.Addr->getNext());
508 // If the member to remove happens to be the last one, update the
509 // LastM indicator.
510 if (CodeData.LastM == NA.Id)
511 CodeData.LastM = MA.Id;
512 return;
513 }
514 MA = G.addr<NodeBase *>(N: MX);
515 }
516 llvm_unreachable("No such member");
517}
518
519// Return the list of all members of the code node.
520NodeList CodeNode::members(const DataFlowGraph &G) const {
521 static auto True = [](Node) -> bool { return true; };
522 return members_if(P: True, G);
523}
524
525// Return the owner of the given instr node.
526Node InstrNode::getOwner(const DataFlowGraph &G) {
527 Node NA = G.addr<NodeBase *>(N: getNext());
528
529 while (NA.Addr != this) {
530 assert(NA.Addr->getType() == NodeAttrs::Code);
531 if (NA.Addr->getKind() == NodeAttrs::Block)
532 return NA;
533 NA = G.addr<NodeBase *>(N: NA.Addr->getNext());
534 }
535 llvm_unreachable("No owner in circular list");
536}
537
538// Add the phi node PA to the given block node.
539void BlockNode::addPhi(Phi PA, const DataFlowGraph &G) {
540 Node M = getFirstMember(G);
541 if (M.Id == 0) {
542 addMember(NA: PA, G);
543 return;
544 }
545
546 assert(M.Addr->getType() == NodeAttrs::Code);
547 if (M.Addr->getKind() == NodeAttrs::Stmt) {
548 // If the first member of the block is a statement, insert the phi as
549 // the first member.
550 CodeData.FirstM = PA.Id;
551 PA.Addr->setNext(M.Id);
552 } else {
553 // If the first member is a phi, find the last phi, and append PA to it.
554 assert(M.Addr->getKind() == NodeAttrs::Phi);
555 Node MN = M;
556 do {
557 M = MN;
558 MN = G.addr<NodeBase *>(N: M.Addr->getNext());
559 assert(MN.Addr->getType() == NodeAttrs::Code);
560 } while (MN.Addr->getKind() == NodeAttrs::Phi);
561
562 // M is the last phi.
563 addMemberAfter(MA: M, NA: PA, G);
564 }
565}
566
567// Find the block node corresponding to the machine basic block BB in the
568// given func node.
569Block FuncNode::findBlock(const MachineBasicBlock *BB,
570 const DataFlowGraph &G) const {
571 auto EqBB = [BB](Node NA) -> bool { return Block(NA).Addr->getCode() == BB; };
572 NodeList Ms = members_if(P: EqBB, G);
573 if (!Ms.empty())
574 return Ms[0];
575 return Block();
576}
577
578// Get the block node for the entry block in the given function.
579Block FuncNode::getEntryBlock(const DataFlowGraph &G) {
580 MachineBasicBlock *EntryB = &getCode()->front();
581 return findBlock(BB: EntryB, G);
582}
583
584// Target operand information.
585//
586
587// For a given instruction, check if there are any bits of RR that can remain
588// unchanged across this def.
589bool TargetOperandInfo::isPreserving(const MachineInstr &In,
590 unsigned OpNum) const {
591 return TII.isPredicated(MI: In);
592}
593
594// Check if the definition of RR produces an unspecified value.
595bool TargetOperandInfo::isClobbering(const MachineInstr &In,
596 unsigned OpNum) const {
597 const MachineOperand &Op = In.getOperand(i: OpNum);
598 if (Op.isRegMask())
599 return true;
600 assert(Op.isReg());
601 if (In.isCall())
602 if (Op.isDef() && Op.isDead())
603 return true;
604 return false;
605}
606
607// Check if the given instruction specifically requires
608bool TargetOperandInfo::isFixedReg(const MachineInstr &In,
609 unsigned OpNum) const {
610 if (In.isCall() || In.isReturn() || In.isInlineAsm())
611 return true;
612 // Check for a tail call.
613 if (In.isBranch())
614 for (const MachineOperand &O : In.operands())
615 if (O.isGlobal() || O.isSymbol())
616 return true;
617
618 const MCInstrDesc &D = In.getDesc();
619 if (D.implicit_defs().empty() && D.implicit_uses().empty())
620 return false;
621 const MachineOperand &Op = In.getOperand(i: OpNum);
622 // If there is a sub-register, treat the operand as non-fixed. Currently,
623 // fixed registers are those that are listed in the descriptor as implicit
624 // uses or defs, and those lists do not allow sub-registers.
625 if (Op.getSubReg() != 0)
626 return false;
627 Register Reg = Op.getReg();
628 ArrayRef<MCPhysReg> ImpOps =
629 Op.isDef() ? D.implicit_defs() : D.implicit_uses();
630 return is_contained(Range&: ImpOps, Element: Reg);
631}
632
633//
634// The data flow graph construction.
635//
636
637DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
638 const TargetRegisterInfo &tri,
639 const MachineDominatorTree &mdt,
640 const MachineDominanceFrontier &mdf)
641 : DefaultTOI(std::make_unique<TargetOperandInfo>(args: tii)), MF(mf), TII(tii),
642 TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(*DefaultTOI),
643 LiveIns(PRI) {}
644
645DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
646 const TargetRegisterInfo &tri,
647 const MachineDominatorTree &mdt,
648 const MachineDominanceFrontier &mdf,
649 const TargetOperandInfo &toi)
650 : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi),
651 LiveIns(PRI) {}
652
653// The implementation of the definition stack.
654// Each register reference has its own definition stack. In particular,
655// for a register references "Reg" and "Reg:subreg" will each have their
656// own definition stacks.
657
658// Construct a stack iterator.
659DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S,
660 bool Top)
661 : DS(S) {
662 if (!Top) {
663 // Initialize to bottom.
664 Pos = 0;
665 return;
666 }
667 // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty).
668 Pos = DS.Stack.size();
669 while (Pos > 0 && DS.isDelimiter(P: DS.Stack[Pos - 1]))
670 Pos--;
671}
672
673// Return the size of the stack, including block delimiters.
674unsigned DataFlowGraph::DefStack::size() const {
675 unsigned S = 0;
676 for (auto I = top(), E = bottom(); I != E; I.down())
677 S++;
678 return S;
679}
680
681// Remove the top entry from the stack. Remove all intervening delimiters
682// so that after this, the stack is either empty, or the top of the stack
683// is a non-delimiter.
684void DataFlowGraph::DefStack::pop() {
685 assert(!empty());
686 unsigned P = nextDown(P: Stack.size());
687 Stack.resize(new_size: P);
688}
689
690// Push a delimiter for block node N on the stack.
691void DataFlowGraph::DefStack::start_block(NodeId N) {
692 assert(N != 0);
693 Stack.push_back(x: Def(nullptr, N));
694}
695
696// Remove all nodes from the top of the stack, until the delimited for
697// block node N is encountered. Remove the delimiter as well. In effect,
698// this will remove from the stack all definitions from block N.
699void DataFlowGraph::DefStack::clear_block(NodeId N) {
700 assert(N != 0);
701 unsigned P = Stack.size();
702 while (P > 0) {
703 bool Found = isDelimiter(P: Stack[P - 1], N);
704 P--;
705 if (Found)
706 break;
707 }
708 // This will also remove the delimiter, if found.
709 Stack.resize(new_size: P);
710}
711
712// Move the stack iterator up by one.
713unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const {
714 // Get the next valid position after P (skipping all delimiters).
715 // The input position P does not have to point to a non-delimiter.
716 unsigned SS = Stack.size();
717 bool IsDelim;
718 assert(P < SS);
719 do {
720 P++;
721 IsDelim = isDelimiter(P: Stack[P - 1]);
722 } while (P < SS && IsDelim);
723 assert(!IsDelim);
724 return P;
725}
726
727// Move the stack iterator down by one.
728unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const {
729 // Get the preceding valid position before P (skipping all delimiters).
730 // The input position P does not have to point to a non-delimiter.
731 assert(P > 0 && P <= Stack.size());
732 bool IsDelim = isDelimiter(P: Stack[P - 1]);
733 do {
734 if (--P == 0)
735 break;
736 IsDelim = isDelimiter(P: Stack[P - 1]);
737 } while (P > 0 && IsDelim);
738 assert(!IsDelim);
739 return P;
740}
741
742// Register information.
743
744RegisterAggr DataFlowGraph::getLandingPadLiveIns() const {
745 RegisterAggr LR(getPRI());
746 const Function &F = MF.getFunction();
747 const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() : nullptr;
748 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
749 // Prefer the "exception-model" module flag, else the TargetOptions default.
750 ExceptionHandling EH = F.getParent()->getExceptionModel();
751 if (EH == ExceptionHandling::Default)
752 EH = TLI.getTargetMachine().getExceptionModel();
753 if (RegisterId R = TLI.getExceptionPointerRegister(EH, PersonalityFn: PF))
754 LR.insert(RR: RegisterRef(R));
755 if (!isFuncletEHPersonality(Pers: classifyEHPersonality(Pers: PF))) {
756 if (RegisterId R = TLI.getExceptionSelectorRegister(EH, PersonalityFn: PF))
757 LR.insert(RR: RegisterRef(R));
758 }
759 return LR;
760}
761
762// Node management functions.
763
764// Get the pointer to the node with the id N.
765NodeBase *DataFlowGraph::ptr(NodeId N) const {
766 if (N == 0)
767 return nullptr;
768 return Memory.ptr(N);
769}
770
771// Get the id of the node at the address P.
772NodeId DataFlowGraph::id(const NodeBase *P) const {
773 if (P == nullptr)
774 return 0;
775 return Memory.id(P);
776}
777
778// Allocate a new node and set the attributes to Attrs.
779Node DataFlowGraph::newNode(uint16_t Attrs) {
780 Node P = Memory.New();
781 P.Addr->init();
782 P.Addr->setAttrs(Attrs);
783 return P;
784}
785
786// Make a copy of the given node B, except for the data-flow links, which
787// are set to 0.
788Node DataFlowGraph::cloneNode(const Node B) {
789 Node NA = newNode(Attrs: 0);
790 memcpy(dest: NA.Addr, src: B.Addr, n: sizeof(NodeBase));
791 // Ref nodes need to have the data-flow links reset.
792 if (NA.Addr->getType() == NodeAttrs::Ref) {
793 Ref RA = NA;
794 RA.Addr->setReachingDef(0);
795 RA.Addr->setSibling(0);
796 if (NA.Addr->getKind() == NodeAttrs::Def) {
797 Def DA = NA;
798 DA.Addr->setReachedDef(0);
799 DA.Addr->setReachedUse(0);
800 }
801 }
802 return NA;
803}
804
805// Allocation routines for specific node types/kinds.
806
807Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {
808 Use UA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Use | Flags);
809 UA.Addr->setRegRef(Op: &Op, G&: *this);
810 return UA;
811}
812
813PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,
814 uint16_t Flags) {
815 PhiUse PUA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Use | Flags);
816 assert(Flags & NodeAttrs::PhiRef);
817 PUA.Addr->setRegRef(RR, G&: *this);
818 PUA.Addr->setPredecessor(PredB.Id);
819 return PUA;
820}
821
822Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {
823 Def DA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Def | Flags);
824 DA.Addr->setRegRef(Op: &Op, G&: *this);
825 return DA;
826}
827
828Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {
829 Def DA = newNode(Attrs: NodeAttrs::Ref | NodeAttrs::Def | Flags);
830 assert(Flags & NodeAttrs::PhiRef);
831 DA.Addr->setRegRef(RR, G&: *this);
832 return DA;
833}
834
835Phi DataFlowGraph::newPhi(Block Owner) {
836 Phi PA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Phi);
837 Owner.Addr->addPhi(PA, G: *this);
838 return PA;
839}
840
841Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {
842 Stmt SA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Stmt);
843 SA.Addr->setCode(MI);
844 Owner.Addr->addMember(NA: SA, G: *this);
845 return SA;
846}
847
848Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {
849 Block BA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Block);
850 BA.Addr->setCode(BB);
851 Owner.Addr->addMember(NA: BA, G: *this);
852 return BA;
853}
854
855Func DataFlowGraph::newFunc(MachineFunction *MF) {
856 Func FA = newNode(Attrs: NodeAttrs::Code | NodeAttrs::Func);
857 FA.Addr->setCode(MF);
858 return FA;
859}
860
861// Build the data flow graph.
862void DataFlowGraph::build(const Config &config) {
863 reset();
864 BuildCfg = config;
865 MachineRegisterInfo &MRI = MF.getRegInfo();
866 ReservedRegs = MRI.getReservedRegs();
867 bool SkipReserved = BuildCfg.Options & BuildOptions::OmitReserved;
868
869 auto Insert = [](auto &Set, auto &&Range) {
870 Set.insert(Range.begin(), Range.end());
871 };
872
873 if (BuildCfg.TrackRegs.empty()) {
874 std::set<RegisterId> BaseSet;
875 if (BuildCfg.Classes.empty()) {
876 // Insert every register.
877 for (unsigned R = 1, E = getPRI().getTRI().getNumRegs(); R != E; ++R)
878 BaseSet.insert(x: R);
879 } else {
880 for (const TargetRegisterClass *RC : BuildCfg.Classes) {
881 for (MCPhysReg R : *RC)
882 BaseSet.insert(x: R);
883 }
884 }
885 for (RegisterId R : BaseSet) {
886 if (SkipReserved && ReservedRegs[R])
887 continue;
888 Insert(TrackedUnits, getPRI().getUnits(RR: RegisterRef(R)));
889 }
890 } else {
891 // Track set in Config overrides everything.
892 for (unsigned R : BuildCfg.TrackRegs) {
893 if (SkipReserved && ReservedRegs[R])
894 continue;
895 Insert(TrackedUnits, getPRI().getUnits(RR: RegisterRef(R)));
896 }
897 }
898
899 TheFunc = newFunc(MF: &MF);
900
901 if (MF.empty())
902 return;
903
904 for (MachineBasicBlock &B : MF) {
905 Block BA = newBlock(Owner: TheFunc, BB: &B);
906 BlockNodes.insert(x: std::make_pair(x: &B, y&: BA));
907 for (MachineInstr &I : B) {
908 if (I.isDebugInstr())
909 continue;
910 buildStmt(BA, In&: I);
911 }
912 }
913
914 Block EA = TheFunc.Addr->getEntryBlock(G: *this);
915 NodeList Blocks = TheFunc.Addr->members(G: *this);
916
917 // Collect function live-ins and entry block live-ins.
918 MachineBasicBlock &EntryB = *EA.Addr->getCode();
919 assert(EntryB.pred_empty() && "Function entry block has predecessors");
920 for (std::pair<MCRegister, Register> P : MRI.liveins())
921 LiveIns.insert(RR: RegisterRef(P.first));
922 if (MRI.tracksLiveness()) {
923 for (auto I : EntryB.liveins())
924 LiveIns.insert(RR: RegisterRef(I.PhysReg, I.LaneMask));
925 }
926
927 // Add function-entry phi nodes for the live-in registers.
928 for (RegisterRef RR : LiveIns.refs()) {
929 if (RR.isReg() && !isTracked(RR)) // isReg is likely guaranteed
930 continue;
931 Phi PA = newPhi(Owner: EA);
932 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
933 Def DA = newDef(Owner: PA, RR, Flags: PhiFlags);
934 PA.Addr->addMember(NA: DA, G: *this);
935 }
936
937 // Add phis for landing pads.
938 // Landing pads, unlike usual backs blocks, are not entered through
939 // branches in the program, or fall-throughs from other blocks. They
940 // are entered from the exception handling runtime and target's ABI
941 // may define certain registers as defined on entry to such a block.
942 RegisterAggr EHRegs = getLandingPadLiveIns();
943 if (!EHRegs.empty()) {
944 for (Block BA : Blocks) {
945 const MachineBasicBlock &B = *BA.Addr->getCode();
946 if (!B.isEHPad())
947 continue;
948
949 // Prepare a list of NodeIds of the block's predecessors.
950 NodeList Preds;
951 for (MachineBasicBlock *PB : B.predecessors())
952 Preds.push_back(Elt: findBlock(BB: PB));
953
954 // Build phi nodes for each live-in.
955 for (RegisterRef RR : EHRegs.refs()) {
956 if (RR.isReg() && !isTracked(RR))
957 continue;
958 Phi PA = newPhi(Owner: BA);
959 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
960 // Add def:
961 Def DA = newDef(Owner: PA, RR, Flags: PhiFlags);
962 PA.Addr->addMember(NA: DA, G: *this);
963 // Add uses (no reaching defs for phi uses):
964 for (Block PBA : Preds) {
965 PhiUse PUA = newPhiUse(Owner: PA, RR, PredB: PBA);
966 PA.Addr->addMember(NA: PUA, G: *this);
967 }
968 }
969 }
970 }
971
972 // Build a map "PhiM" which will contain, for each block, the set
973 // of references that will require phi definitions in that block.
974 // "PhiClobberM" map contains references that require phis for clobbering defs
975 BlockRefsMap PhiM(getPRI());
976 BlockRefsMap PhiClobberM(getPRI());
977 for (Block BA : Blocks)
978 recordDefsForDF(PhiM, PhiClobberM, BA);
979 for (Block BA : Blocks)
980 buildPhis(PhiM, BA);
981
982 // Link all the refs. This will recursively traverse the dominator tree.
983 // Phis for clobbering defs are added here.
984 DefStackMap DM;
985 linkBlockRefs(DefM&: DM, PhiClobberM, BA: EA);
986
987 // Finally, remove all unused phi nodes.
988 if (!(BuildCfg.Options & BuildOptions::KeepDeadPhis))
989 removeUnusedPhis();
990}
991
992RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
993 assert(RegisterRef::isRegId(Reg) || RegisterRef::isMaskId(Reg));
994 assert(Reg != 0);
995 if (Sub != 0)
996 Reg = TRI.getSubReg(Reg, Idx: Sub);
997 return RegisterRef(Reg);
998}
999
1000RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const {
1001 assert(Op.isReg() || Op.isRegMask());
1002 if (Op.isReg())
1003 return makeRegRef(Reg: Op.getReg(), Sub: Op.getSubReg());
1004 return RegisterRef(getPRI().getRegMaskId(RM: Op.getRegMask()),
1005 LaneBitmask::getAll());
1006}
1007
1008// For each stack in the map DefM, push the delimiter for block B on it.
1009void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) {
1010 // Push block delimiters.
1011 for (auto &P : DefM)
1012 P.second.start_block(N: B);
1013}
1014
1015// Remove all definitions coming from block B from each stack in DefM.
1016void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) {
1017 // Pop all defs from this block from the definition stack. Defs that were
1018 // added to the map during the traversal of instructions will not have a
1019 // delimiter, but for those, the whole stack will be emptied.
1020 for (auto &P : DefM)
1021 P.second.clear_block(N: B);
1022
1023 // Finally, remove empty stacks from the map.
1024 DefM.remove_if(Pred: [](const auto &P) { return P.second.empty(); });
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.Id].push(DA);
1065 Defined.insert(x: RR.Id);
1066 for (RegisterId A : getPRI().getAliasSet(RR)) {
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.Id);
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.Id).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.Id].push(DA);
1123 for (RegisterId A : getPRI().getAliasSet(RR)) {
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.Id);
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(Val: RR.Id);
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.asMCReg()) || 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(Val: RR.Id);
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.Id]);
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.asMCReg().id()])
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