LLVM 19.0.0git
RDFGraph.cpp
Go to the documentation of this file.
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/ADT/BitVector.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/SetVector.h"
27#include "llvm/IR/Function.h"
28#include "llvm/MC/LaneBitmask.h"
29#include "llvm/MC/MCInstrDesc.h"
32#include <algorithm>
33#include <cassert>
34#include <cstdint>
35#include <cstring>
36#include <iterator>
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
46 P.G.getPRI().print(OS, P.Obj);
47 return OS;
48}
49
51 if (P.Obj == 0)
52 return OS << "null";
53 auto NA = P.G.addr<NodeBase *>(P.Obj);
54 uint16_t Attrs = NA.Addr->getAttrs();
55 uint16_t Kind = NodeAttrs::kind(Attrs);
56 uint16_t Flags = NodeAttrs::flags(Attrs);
57 switch (NodeAttrs::type(Attrs)) {
58 case NodeAttrs::Code:
59 switch (Kind) {
60 case NodeAttrs::Func:
61 OS << 'f';
62 break;
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;
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
119 printRefHeader(OS, P.Obj, 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
136 printRefHeader(OS, P.Obj, 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
147 printRefHeader(OS, P.Obj, 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
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
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
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;
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
219 OS << Print(P.Obj.Id, P.G) << ": phi ["
220 << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']';
221 return OS;
222}
223
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(Opc);
228 // Print the target for calls and branches (for readability).
229 if (MI.isCall() || MI.isBranch()) {
231 llvm::find_if(MI.operands(), [](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(*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(P.G), P.G) << ']';
245 return OS;
246}
247
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
264 MachineBasicBlock *BB = P.Obj.Addr->getCode();
265 unsigned NP = BB->pred_size();
266 std::vector<int> Ns;
267 auto PrintBBs = [&OS](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(*BB)
277 << " --- preds(" << NP << "): ";
278 for (MachineBasicBlock *B : BB->predecessors())
279 Ns.push_back(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(B->getNumber());
287 PrintBBs(Ns);
288 OS << '\n';
289
290 for (auto I : P.Obj.Addr->members(P.G))
291 OS << PrintNode<InstrNode *>(I, P.G) << '\n';
292 return OS;
293}
294
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(P.G))
300 OS << PrintNode<BlockNode *>(I, P.G) << '\n';
301 OS << "]\n";
302 return OS;
303}
304
306 OS << '{';
307 for (auto I : P.Obj)
308 OS << ' ' << Print(I, P.G);
309 OS << " }";
310 return OS;
311}
312
314 OS << P.Obj;
315 return OS;
316}
317
320 for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E;) {
321 OS << Print(I->Id, P.G) << '<' << Print(I->Addr->getRegRef(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(NodesPerBlock * NodeMemSize, NodeMemSize);
341 char *P = static_cast<char *>(T);
342 Blocks.push_back(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
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(ActiveB, Index)};
367 ActiveEnd += NodeMemSize;
368 return NA;
369}
370
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(i, Idx);
379 }
380 llvm_unreachable("Invalid node address");
381}
382
384 MemPool.Reset();
385 Blocks.clear();
386 ActiveEnd = nullptr;
387}
388
389// Insert node NA after "this" in the circular chain.
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.
405 return G.unpack(RefData.PR);
406 assert(RefData.Op != nullptr);
407 return G.makeRegRef(*RefData.Op);
408}
409
410// Set the register reference in the reference node directly (for references
411// in phi nodes).
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).
423 (void)G;
424 RefData.Op = Op;
425}
426
427// Get the owner of a given reference node.
429 Node NA = G.addr<NodeBase *>(getNext());
430
431 while (NA.Addr != this) {
432 if (NA.Addr->getType() == NodeAttrs::Code)
433 return NA;
434 NA = G.addr<NodeBase *>(NA.Addr->getNext());
435 }
436 llvm_unreachable("No owner in circular list");
437}
438
439// Connect the def node to the reaching def node.
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.
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.
455 if (CodeData.FirstM == 0)
456 return Node();
457 return G.addr<NodeBase *>(CodeData.FirstM);
458}
459
460// Get the last member of the code node.
462 if (CodeData.LastM == 0)
463 return Node();
464 return G.addr<NodeBase *>(CodeData.LastM);
465}
466
467// Add node NA at the end of the member list of the given code node.
470 if (ML.Id != 0) {
471 ML.Addr->append(NA);
472 } else {
473 CodeData.FirstM = NA.Id;
474 NodeId Self = G.id(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.
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.
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.
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 *>(MX);
515 }
516 llvm_unreachable("No such member");
517}
518
519// Return the list of all members of the code node.
521 static auto True = [](Node) -> bool { return true; };
522 return members_if(True, G);
523}
524
525// Return the owner of the given instr node.
527 Node NA = G.addr<NodeBase *>(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 *>(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.
540 Node M = getFirstMember(G);
541 if (M.Id == 0) {
542 addMember(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 *>(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(M, PA, G);
564 }
565}
566
567// Find the block node corresponding to the machine basic block BB in the
568// given func node.
570 const DataFlowGraph &G) const {
571 auto EqBB = [BB](Node NA) -> bool { return Block(NA).Addr->getCode() == BB; };
572 NodeList Ms = members_if(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.
580 MachineBasicBlock *EntryB = &getCode()->front();
581 return findBlock(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.
590 unsigned OpNum) const {
591 return TII.isPredicated(In);
592}
593
594// Check if the definition of RR produces an unspecified value.
596 unsigned OpNum) const {
597 const MachineOperand &Op = In.getOperand(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
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(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(ImpOps, Reg);
631}
632
633//
634// The data flow graph construction.
635//
636
638 const TargetRegisterInfo &tri,
639 const MachineDominatorTree &mdt,
640 const MachineDominanceFrontier &mdf)
641 : DefaultTOI(std::make_unique<TargetOperandInfo>(tii)), MF(mf), TII(tii),
642 TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(*DefaultTOI),
643 LiveIns(PRI) {}
644
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(DS.Stack[Pos - 1]))
670 Pos--;
671}
672
673// Return the size of the stack, including block delimiters.
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.
685 assert(!empty());
686 unsigned P = nextDown(Stack.size());
687 Stack.resize(P);
688}
689
690// Push a delimiter for block node N on the stack.
692 assert(N != 0);
693 Stack.push_back(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.
700 assert(N != 0);
701 unsigned P = Stack.size();
702 while (P > 0) {
703 bool Found = isDelimiter(Stack[P - 1], N);
704 P--;
705 if (Found)
706 break;
707 }
708 // This will also remove the delimiter, if found.
709 Stack.resize(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(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(Stack[P - 1]);
733 do {
734 if (--P == 0)
735 break;
736 IsDelim = isDelimiter(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 if (RegisterId R = TLI.getExceptionPointerRegister(PF))
750 LR.insert(RegisterRef(R));
752 if (RegisterId R = TLI.getExceptionSelectorRegister(PF))
753 LR.insert(RegisterRef(R));
754 }
755 return LR;
756}
757
758// Node management functions.
759
760// Get the pointer to the node with the id N.
762 if (N == 0)
763 return nullptr;
764 return Memory.ptr(N);
765}
766
767// Get the id of the node at the address P.
769 if (P == nullptr)
770 return 0;
771 return Memory.id(P);
772}
773
774// Allocate a new node and set the attributes to Attrs.
775Node DataFlowGraph::newNode(uint16_t Attrs) {
776 Node P = Memory.New();
777 P.Addr->init();
778 P.Addr->setAttrs(Attrs);
779 return P;
780}
781
782// Make a copy of the given node B, except for the data-flow links, which
783// are set to 0.
784Node DataFlowGraph::cloneNode(const Node B) {
785 Node NA = newNode(0);
786 memcpy(NA.Addr, B.Addr, sizeof(NodeBase));
787 // Ref nodes need to have the data-flow links reset.
788 if (NA.Addr->getType() == NodeAttrs::Ref) {
789 Ref RA = NA;
790 RA.Addr->setReachingDef(0);
791 RA.Addr->setSibling(0);
792 if (NA.Addr->getKind() == NodeAttrs::Def) {
793 Def DA = NA;
794 DA.Addr->setReachedDef(0);
795 DA.Addr->setReachedUse(0);
796 }
797 }
798 return NA;
799}
800
801// Allocation routines for specific node types/kinds.
802
803Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {
804 Use UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
805 UA.Addr->setRegRef(&Op, *this);
806 return UA;
807}
808
809PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,
810 uint16_t Flags) {
811 PhiUse PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
812 assert(Flags & NodeAttrs::PhiRef);
813 PUA.Addr->setRegRef(RR, *this);
814 PUA.Addr->setPredecessor(PredB.Id);
815 return PUA;
816}
817
818Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {
819 Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
820 DA.Addr->setRegRef(&Op, *this);
821 return DA;
822}
823
824Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {
825 Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
826 assert(Flags & NodeAttrs::PhiRef);
827 DA.Addr->setRegRef(RR, *this);
828 return DA;
829}
830
831Phi DataFlowGraph::newPhi(Block Owner) {
832 Phi PA = newNode(NodeAttrs::Code | NodeAttrs::Phi);
833 Owner.Addr->addPhi(PA, *this);
834 return PA;
835}
836
837Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {
838 Stmt SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt);
839 SA.Addr->setCode(MI);
840 Owner.Addr->addMember(SA, *this);
841 return SA;
842}
843
844Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {
845 Block BA = newNode(NodeAttrs::Code | NodeAttrs::Block);
846 BA.Addr->setCode(BB);
847 Owner.Addr->addMember(BA, *this);
848 return BA;
849}
850
851Func DataFlowGraph::newFunc(MachineFunction *MF) {
852 Func FA = newNode(NodeAttrs::Code | NodeAttrs::Func);
853 FA.Addr->setCode(MF);
854 return FA;
855}
856
857// Build the data flow graph.
858void DataFlowGraph::build(const Config &config) {
859 reset();
860 BuildCfg = config;
861 MachineRegisterInfo &MRI = MF.getRegInfo();
862 ReservedRegs = MRI.getReservedRegs();
863 bool SkipReserved = BuildCfg.Options & BuildOptions::OmitReserved;
864
865 auto Insert = [](auto &Set, auto &&Range) {
866 Set.insert(Range.begin(), Range.end());
867 };
868
869 if (BuildCfg.TrackRegs.empty()) {
870 std::set<RegisterId> BaseSet;
871 if (BuildCfg.Classes.empty()) {
872 // Insert every register.
873 for (unsigned R = 1, E = getPRI().getTRI().getNumRegs(); R != E; ++R)
874 BaseSet.insert(R);
875 } else {
876 for (const TargetRegisterClass *RC : BuildCfg.Classes) {
877 for (MCPhysReg R : *RC)
878 BaseSet.insert(R);
879 }
880 }
881 for (RegisterId R : BaseSet) {
882 if (SkipReserved && ReservedRegs[R])
883 continue;
884 Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));
885 }
886 } else {
887 // Track set in Config overrides everything.
888 for (unsigned R : BuildCfg.TrackRegs) {
889 if (SkipReserved && ReservedRegs[R])
890 continue;
891 Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));
892 }
893 }
894
895 TheFunc = newFunc(&MF);
896
897 if (MF.empty())
898 return;
899
900 for (MachineBasicBlock &B : MF) {
901 Block BA = newBlock(TheFunc, &B);
902 BlockNodes.insert(std::make_pair(&B, BA));
903 for (MachineInstr &I : B) {
904 if (I.isDebugInstr())
905 continue;
906 buildStmt(BA, I);
907 }
908 }
909
910 Block EA = TheFunc.Addr->getEntryBlock(*this);
911 NodeList Blocks = TheFunc.Addr->members(*this);
912
913 // Collect function live-ins and entry block live-ins.
914 MachineBasicBlock &EntryB = *EA.Addr->getCode();
915 assert(EntryB.pred_empty() && "Function entry block has predecessors");
916 for (std::pair<unsigned, unsigned> P : MRI.liveins())
917 LiveIns.insert(RegisterRef(P.first));
918 if (MRI.tracksLiveness()) {
919 for (auto I : EntryB.liveins())
920 LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask));
921 }
922
923 // Add function-entry phi nodes for the live-in registers.
924 for (RegisterRef RR : LiveIns.refs()) {
925 if (RR.isReg() && !isTracked(RR)) // isReg is likely guaranteed
926 continue;
927 Phi PA = newPhi(EA);
929 Def DA = newDef(PA, RR, PhiFlags);
930 PA.Addr->addMember(DA, *this);
931 }
932
933 // Add phis for landing pads.
934 // Landing pads, unlike usual backs blocks, are not entered through
935 // branches in the program, or fall-throughs from other blocks. They
936 // are entered from the exception handling runtime and target's ABI
937 // may define certain registers as defined on entry to such a block.
938 RegisterAggr EHRegs = getLandingPadLiveIns();
939 if (!EHRegs.empty()) {
940 for (Block BA : Blocks) {
941 const MachineBasicBlock &B = *BA.Addr->getCode();
942 if (!B.isEHPad())
943 continue;
944
945 // Prepare a list of NodeIds of the block's predecessors.
946 NodeList Preds;
947 for (MachineBasicBlock *PB : B.predecessors())
948 Preds.push_back(findBlock(PB));
949
950 // Build phi nodes for each live-in.
951 for (RegisterRef RR : EHRegs.refs()) {
952 if (RR.isReg() && !isTracked(RR))
953 continue;
954 Phi PA = newPhi(BA);
956 // Add def:
957 Def DA = newDef(PA, RR, PhiFlags);
958 PA.Addr->addMember(DA, *this);
959 // Add uses (no reaching defs for phi uses):
960 for (Block PBA : Preds) {
961 PhiUse PUA = newPhiUse(PA, RR, PBA);
962 PA.Addr->addMember(PUA, *this);
963 }
964 }
965 }
966 }
967
968 // Build a map "PhiM" which will contain, for each block, the set
969 // of references that will require phi definitions in that block.
970 BlockRefsMap PhiM(getPRI());
971 for (Block BA : Blocks)
972 recordDefsForDF(PhiM, BA);
973 for (Block BA : Blocks)
974 buildPhis(PhiM, BA);
975
976 // Link all the refs. This will recursively traverse the dominator tree.
978 linkBlockRefs(DM, EA);
979
980 // Finally, remove all unused phi nodes.
981 if (!(BuildCfg.Options & BuildOptions::KeepDeadPhis))
982 removeUnusedPhis();
983}
984
985RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
987 assert(Reg != 0);
988 if (Sub != 0)
989 Reg = TRI.getSubReg(Reg, Sub);
990 return RegisterRef(Reg);
991}
992
994 assert(Op.isReg() || Op.isRegMask());
995 if (Op.isReg())
996 return makeRegRef(Op.getReg(), Op.getSubReg());
997 return RegisterRef(getPRI().getRegMaskId(Op.getRegMask()),
999}
1000
1001// For each stack in the map DefM, push the delimiter for block B on it.
1003 // Push block delimiters.
1004 for (auto &P : DefM)
1005 P.second.start_block(B);
1006}
1007
1008// Remove all definitions coming from block B from each stack in DefM.
1010 // Pop all defs from this block from the definition stack. Defs that were
1011 // added to the map during the traversal of instructions will not have a
1012 // delimiter, but for those, the whole stack will be emptied.
1013 for (auto &P : DefM)
1014 P.second.clear_block(B);
1015
1016 // Finally, remove empty stacks from the map.
1017 for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {
1018 NextI = std::next(I);
1019 // This preserves the validity of iterators other than I.
1020 if (I->second.empty())
1021 DefM.erase(I);
1022 }
1023}
1024
1025// Push all definitions from the instruction node IA to an appropriate
1026// stack in DefM.
1028 pushClobbers(IA, DefM);
1029 pushDefs(IA, DefM);
1030}
1031
1032// Push all definitions from the instruction node IA to an appropriate
1033// stack in DefM.
1034void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) {
1035 NodeSet Visited;
1036 std::set<RegisterId> Defined;
1037
1038 // The important objectives of this function are:
1039 // - to be able to handle instructions both while the graph is being
1040 // constructed, and after the graph has been constructed, and
1041 // - maintain proper ordering of definitions on the stack for each
1042 // register reference:
1043 // - if there are two or more related defs in IA (i.e. coming from
1044 // the same machine operand), then only push one def on the stack,
1045 // - if there are multiple unrelated defs of non-overlapping
1046 // subregisters of S, then the stack for S will have both (in an
1047 // unspecified order), but the order does not matter from the data-
1048 // -flow perspective.
1049
1050 for (Def DA : IA.Addr->members_if(IsDef, *this)) {
1051 if (Visited.count(DA.Id))
1052 continue;
1053 if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))
1054 continue;
1055
1056 NodeList Rel = getRelatedRefs(IA, DA);
1057 Def PDA = Rel.front();
1058 RegisterRef RR = PDA.Addr->getRegRef(*this);
1059
1060 // Push the definition on the stack for the register and all aliases.
1061 // The def stack traversal in linkNodeUp will check the exact aliasing.
1062 DefM[RR.Reg].push(DA);
1063 Defined.insert(RR.Reg);
1064 for (RegisterId A : getPRI().getAliasSet(RR.Reg)) {
1066 continue;
1067 // Check that we don't push the same def twice.
1068 assert(A != RR.Reg);
1069 if (!Defined.count(A))
1070 DefM[A].push(DA);
1071 }
1072 // Mark all the related defs as visited.
1073 for (Node T : Rel)
1074 Visited.insert(T.Id);
1075 }
1076}
1077
1078// Push all definitions from the instruction node IA to an appropriate
1079// stack in DefM.
1080void DataFlowGraph::pushDefs(Instr IA, DefStackMap &DefM) {
1081 NodeSet Visited;
1082#ifndef NDEBUG
1083 std::set<RegisterId> Defined;
1084#endif
1085
1086 // The important objectives of this function are:
1087 // - to be able to handle instructions both while the graph is being
1088 // constructed, and after the graph has been constructed, and
1089 // - maintain proper ordering of definitions on the stack for each
1090 // register reference:
1091 // - if there are two or more related defs in IA (i.e. coming from
1092 // the same machine operand), then only push one def on the stack,
1093 // - if there are multiple unrelated defs of non-overlapping
1094 // subregisters of S, then the stack for S will have both (in an
1095 // unspecified order), but the order does not matter from the data-
1096 // -flow perspective.
1097
1098 for (Def DA : IA.Addr->members_if(IsDef, *this)) {
1099 if (Visited.count(DA.Id))
1100 continue;
1101 if (DA.Addr->getFlags() & NodeAttrs::Clobbering)
1102 continue;
1103
1104 NodeList Rel = getRelatedRefs(IA, DA);
1105 Def PDA = Rel.front();
1106 RegisterRef RR = PDA.Addr->getRegRef(*this);
1107#ifndef NDEBUG
1108 // Assert if the register is defined in two or more unrelated defs.
1109 // This could happen if there are two or more def operands defining it.
1110 if (!Defined.insert(RR.Reg).second) {
1111 MachineInstr *MI = Stmt(IA).Addr->getCode();
1112 dbgs() << "Multiple definitions of register: " << Print(RR, *this)
1113 << " in\n " << *MI << "in " << printMBBReference(*MI->getParent())
1114 << '\n';
1115 llvm_unreachable(nullptr);
1116 }
1117#endif
1118 // Push the definition on the stack for the register and all aliases.
1119 // The def stack traversal in linkNodeUp will check the exact aliasing.
1120 DefM[RR.Reg].push(DA);
1121 for (RegisterId A : getPRI().getAliasSet(RR.Reg)) {
1122 if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A)))
1123 continue;
1124 // Check that we don't push the same def twice.
1125 assert(A != RR.Reg);
1126 DefM[A].push(DA);
1127 }
1128 // Mark all the related defs as visited.
1129 for (Node T : Rel)
1130 Visited.insert(T.Id);
1131 }
1132}
1133
1134// Return the list of all reference nodes related to RA, including RA itself.
1135// See "getNextRelated" for the meaning of a "related reference".
1137 assert(IA.Id != 0 && RA.Id != 0);
1138
1139 NodeList Refs;
1140 NodeId Start = RA.Id;
1141 do {
1142 Refs.push_back(RA);
1143 RA = getNextRelated(IA, RA);
1144 } while (RA.Id != 0 && RA.Id != Start);
1145 return Refs;
1146}
1147
1148// Clear all information in the graph.
1149void DataFlowGraph::reset() {
1150 Memory.clear();
1151 BlockNodes.clear();
1152 TrackedUnits.clear();
1153 ReservedRegs.clear();
1154 TheFunc = Func();
1155}
1156
1157// Return the next reference node in the instruction node IA that is related
1158// to RA. Conceptually, two reference nodes are related if they refer to the
1159// same instance of a register access, but differ in flags or other minor
1160// characteristics. Specific examples of related nodes are shadow reference
1161// nodes.
1162// Return the equivalent of nullptr if there are no more related references.
1164 assert(IA.Id != 0 && RA.Id != 0);
1165
1166 auto IsRelated = [this, RA](Ref TA) -> bool {
1167 if (TA.Addr->getKind() != RA.Addr->getKind())
1168 return false;
1169 if (!getPRI().equal_to(TA.Addr->getRegRef(*this),
1170 RA.Addr->getRegRef(*this))) {
1171 return false;
1172 }
1173 return true;
1174 };
1175
1176 RegisterRef RR = RA.Addr->getRegRef(*this);
1177 if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1178 auto Cond = [&IsRelated, RA](Ref TA) -> bool {
1179 return IsRelated(TA) && &RA.Addr->getOp() == &TA.Addr->getOp();
1180 };
1181 return RA.Addr->getNextRef(RR, Cond, true, *this);
1182 }
1183
1184 assert(IA.Addr->getKind() == NodeAttrs::Phi);
1185 auto Cond = [&IsRelated, RA](Ref TA) -> bool {
1186 if (!IsRelated(TA))
1187 return false;
1188 if (TA.Addr->getKind() != NodeAttrs::Use)
1189 return true;
1190 // For phi uses, compare predecessor blocks.
1191 return PhiUse(TA).Addr->getPredecessor() ==
1192 PhiUse(RA).Addr->getPredecessor();
1193 };
1194 return RA.Addr->getNextRef(RR, Cond, true, *this);
1195}
1196
1197// Find the next node related to RA in IA that satisfies condition P.
1198// If such a node was found, return a pair where the second element is the
1199// located node. If such a node does not exist, return a pair where the
1200// first element is the element after which such a node should be inserted,
1201// and the second element is a null-address.
1202template <typename Predicate>
1203std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA,
1204 Predicate P) const {
1205 assert(IA.Id != 0 && RA.Id != 0);
1206
1207 Ref NA;
1208 NodeId Start = RA.Id;
1209 while (true) {
1210 NA = getNextRelated(IA, RA);
1211 if (NA.Id == 0 || NA.Id == Start)
1212 break;
1213 if (P(NA))
1214 break;
1215 RA = NA;
1216 }
1217
1218 if (NA.Id != 0 && NA.Id != Start)
1219 return std::make_pair(RA, NA);
1220 return std::make_pair(RA, Ref());
1221}
1222
1223// Get the next shadow node in IA corresponding to RA, and optionally create
1224// such a node if it does not exist.
1226 assert(IA.Id != 0 && RA.Id != 0);
1227
1228 uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1229 auto IsShadow = [Flags](Ref TA) -> bool {
1230 return TA.Addr->getFlags() == Flags;
1231 };
1232 auto Loc = locateNextRef(IA, RA, IsShadow);
1233 if (Loc.second.Id != 0 || !Create)
1234 return Loc.second;
1235
1236 // Create a copy of RA and mark is as shadow.
1237 Ref NA = cloneNode(RA);
1238 NA.Addr->setFlags(Flags | NodeAttrs::Shadow);
1239 IA.Addr->addMemberAfter(Loc.first, NA, *this);
1240 return NA;
1241}
1242
1243// Create a new statement node in the block node BA that corresponds to
1244// the machine instruction MI.
1245void DataFlowGraph::buildStmt(Block BA, MachineInstr &In) {
1246 Stmt SA = newStmt(BA, &In);
1247
1248 auto isCall = [](const MachineInstr &In) -> bool {
1249 if (In.isCall())
1250 return true;
1251 // Is tail call?
1252 if (In.isBranch()) {
1253 for (const MachineOperand &Op : In.operands())
1254 if (Op.isGlobal() || Op.isSymbol())
1255 return true;
1256 // Assume indirect branches are calls. This is for the purpose of
1257 // keeping implicit operands, and so it won't hurt on intra-function
1258 // indirect branches.
1259 if (In.isIndirectBranch())
1260 return true;
1261 }
1262 return false;
1263 };
1264
1265 auto isDefUndef = [this](const MachineInstr &In, RegisterRef DR) -> bool {
1266 // This instruction defines DR. Check if there is a use operand that
1267 // would make DR live on entry to the instruction.
1268 for (const MachineOperand &Op : In.all_uses()) {
1269 if (Op.getReg() == 0 || Op.isUndef())
1270 continue;
1271 RegisterRef UR = makeRegRef(Op);
1272 if (getPRI().alias(DR, UR))
1273 return false;
1274 }
1275 return true;
1276 };
1277
1278 bool IsCall = isCall(In);
1279 unsigned NumOps = In.getNumOperands();
1280
1281 // Avoid duplicate implicit defs. This will not detect cases of implicit
1282 // defs that define registers that overlap, but it is not clear how to
1283 // interpret that in the absence of explicit defs. Overlapping explicit
1284 // defs are likely illegal already.
1285 BitVector DoneDefs(TRI.getNumRegs());
1286 // Process explicit defs first.
1287 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1288 MachineOperand &Op = In.getOperand(OpN);
1289 if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
1290 continue;
1291 Register R = Op.getReg();
1292 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)))
1293 continue;
1295 if (TOI.isPreserving(In, OpN)) {
1297 // If the def is preserving, check if it is also undefined.
1298 if (isDefUndef(In, makeRegRef(Op)))
1300 }
1301 if (TOI.isClobbering(In, OpN))
1303 if (TOI.isFixedReg(In, OpN))
1305 if (IsCall && Op.isDead())
1307 Def DA = newDef(SA, Op, Flags);
1308 SA.Addr->addMember(DA, *this);
1309 assert(!DoneDefs.test(R));
1310 DoneDefs.set(R);
1311 }
1312
1313 // Process reg-masks (as clobbers).
1314 BitVector DoneClobbers(TRI.getNumRegs());
1315 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1316 MachineOperand &Op = In.getOperand(OpN);
1317 if (!Op.isRegMask())
1318 continue;
1320 Def DA = newDef(SA, Op, Flags);
1321 SA.Addr->addMember(DA, *this);
1322 // Record all clobbered registers in DoneDefs.
1323 const uint32_t *RM = Op.getRegMask();
1324 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
1325 if (!isTracked(RegisterRef(i)))
1326 continue;
1327 if (!(RM[i / 32] & (1u << (i % 32))))
1328 DoneClobbers.set(i);
1329 }
1330 }
1331
1332 // Process implicit defs, skipping those that have already been added
1333 // as explicit.
1334 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1335 MachineOperand &Op = In.getOperand(OpN);
1336 if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())
1337 continue;
1338 Register R = Op.getReg();
1339 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)) || DoneDefs.test(R))
1340 continue;
1341 RegisterRef RR = makeRegRef(Op);
1343 if (TOI.isPreserving(In, OpN)) {
1345 // If the def is preserving, check if it is also undefined.
1346 if (isDefUndef(In, RR))
1348 }
1349 if (TOI.isClobbering(In, OpN))
1351 if (TOI.isFixedReg(In, OpN))
1353 if (IsCall && Op.isDead()) {
1354 if (DoneClobbers.test(R))
1355 continue;
1357 }
1358 Def DA = newDef(SA, Op, Flags);
1359 SA.Addr->addMember(DA, *this);
1360 DoneDefs.set(R);
1361 }
1362
1363 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1364 MachineOperand &Op = In.getOperand(OpN);
1365 if (!Op.isReg() || !Op.isUse())
1366 continue;
1367 Register R = Op.getReg();
1368 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)))
1369 continue;
1371 if (Op.isUndef())
1373 if (TOI.isFixedReg(In, OpN))
1375 Use UA = newUse(SA, Op, Flags);
1376 SA.Addr->addMember(UA, *this);
1377 }
1378}
1379
1380// Scan all defs in the block node BA and record in PhiM the locations of
1381// phi nodes corresponding to these defs.
1382void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, Block BA) {
1383 // Check all defs from block BA and record them in each block in BA's
1384 // iterated dominance frontier. This information will later be used to
1385 // create phi nodes.
1386 MachineBasicBlock *BB = BA.Addr->getCode();
1387 assert(BB);
1388 auto DFLoc = MDF.find(BB);
1389 if (DFLoc == MDF.end() || DFLoc->second.empty())
1390 return;
1391
1392 // Traverse all instructions in the block and collect the set of all
1393 // defined references. For each reference there will be a phi created
1394 // in the block's iterated dominance frontier.
1395 // This is done to make sure that each defined reference gets only one
1396 // phi node, even if it is defined multiple times.
1397 RegisterAggr Defs(getPRI());
1398 for (Instr IA : BA.Addr->members(*this)) {
1399 for (Ref RA : IA.Addr->members_if(IsDef, *this)) {
1400 RegisterRef RR = RA.Addr->getRegRef(*this);
1401 if (RR.isReg() && isTracked(RR))
1402 Defs.insert(RR);
1403 }
1404 }
1405
1406 // Calculate the iterated dominance frontier of BB.
1407 const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;
1408 SetVector<MachineBasicBlock *> IDF(DF.begin(), DF.end());
1409 for (unsigned i = 0; i < IDF.size(); ++i) {
1410 auto F = MDF.find(IDF[i]);
1411 if (F != MDF.end())
1412 IDF.insert(F->second.begin(), F->second.end());
1413 }
1414
1415 // Finally, add the set of defs to each block in the iterated dominance
1416 // frontier.
1417 for (auto *DB : IDF) {
1418 Block DBA = findBlock(DB);
1419 PhiM[DBA.Id].insert(Defs);
1420 }
1421}
1422
1423// Given the locations of phi nodes in the map PhiM, create the phi nodes
1424// that are located in the block node BA.
1425void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block BA) {
1426 // Check if this blocks has any DF defs, i.e. if there are any defs
1427 // that this block is in the iterated dominance frontier of.
1428 auto HasDF = PhiM.find(BA.Id);
1429 if (HasDF == PhiM.end() || HasDF->second.empty())
1430 return;
1431
1432 // Prepare a list of NodeIds of the block's predecessors.
1433 NodeList Preds;
1434 const MachineBasicBlock *MBB = BA.Addr->getCode();
1435 for (MachineBasicBlock *PB : MBB->predecessors())
1436 Preds.push_back(findBlock(PB));
1437
1438 const RegisterAggr &Defs = PhiM[BA.Id];
1440
1441 for (RegisterRef RR : Defs.refs()) {
1442 Phi PA = newPhi(BA);
1443 PA.Addr->addMember(newDef(PA, RR, PhiFlags), *this);
1444
1445 // Add phi uses.
1446 for (Block PBA : Preds) {
1447 PA.Addr->addMember(newPhiUse(PA, RR, PBA), *this);
1448 }
1449 }
1450}
1451
1452// Remove any unneeded phi nodes that were created during the build process.
1453void DataFlowGraph::removeUnusedPhis() {
1454 // This will remove unused phis, i.e. phis where each def does not reach
1455 // any uses or other defs. This will not detect or remove circular phi
1456 // chains that are otherwise dead. Unused/dead phis are created during
1457 // the build process and this function is intended to remove these cases
1458 // that are easily determinable to be unnecessary.
1459
1460 SetVector<NodeId> PhiQ;
1461 for (Block BA : TheFunc.Addr->members(*this)) {
1462 for (auto P : BA.Addr->members_if(IsPhi, *this))
1463 PhiQ.insert(P.Id);
1464 }
1465
1466 static auto HasUsedDef = [](NodeList &Ms) -> bool {
1467 for (Node M : Ms) {
1468 if (M.Addr->getKind() != NodeAttrs::Def)
1469 continue;
1470 Def DA = M;
1471 if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)
1472 return true;
1473 }
1474 return false;
1475 };
1476
1477 // Any phi, if it is removed, may affect other phis (make them dead).
1478 // For each removed phi, collect the potentially affected phis and add
1479 // them back to the queue.
1480 while (!PhiQ.empty()) {
1481 auto PA = addr<PhiNode *>(PhiQ[0]);
1482 PhiQ.remove(PA.Id);
1483 NodeList Refs = PA.Addr->members(*this);
1484 if (HasUsedDef(Refs))
1485 continue;
1486 for (Ref RA : Refs) {
1487 if (NodeId RD = RA.Addr->getReachingDef()) {
1488 auto RDA = addr<DefNode *>(RD);
1489 Instr OA = RDA.Addr->getOwner(*this);
1490 if (IsPhi(OA))
1491 PhiQ.insert(OA.Id);
1492 }
1493 if (RA.Addr->isDef())
1494 unlinkDef(RA, true);
1495 else
1496 unlinkUse(RA, true);
1497 }
1498 Block BA = PA.Addr->getOwner(*this);
1499 BA.Addr->removeMember(PA, *this);
1500 }
1501}
1502
1503// For a given reference node TA in an instruction node IA, connect the
1504// reaching def of TA to the appropriate def node. Create any shadow nodes
1505// as appropriate.
1506template <typename T>
1507void DataFlowGraph::linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS) {
1508 if (DS.empty())
1509 return;
1510 RegisterRef RR = TA.Addr->getRegRef(*this);
1511 NodeAddr<T> TAP;
1512
1513 // References from the def stack that have been examined so far.
1514 RegisterAggr Defs(getPRI());
1515
1516 for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {
1517 RegisterRef QR = I->Addr->getRegRef(*this);
1518
1519 // Skip all defs that are aliased to any of the defs that we have already
1520 // seen. If this completes a cover of RR, stop the stack traversal.
1521 bool Alias = Defs.hasAliasOf(QR);
1522 bool Cover = Defs.insert(QR).hasCoverOf(RR);
1523 if (Alias) {
1524 if (Cover)
1525 break;
1526 continue;
1527 }
1528
1529 // The reaching def.
1530 Def RDA = *I;
1531
1532 // Pick the reached node.
1533 if (TAP.Id == 0) {
1534 TAP = TA;
1535 } else {
1536 // Mark the existing ref as "shadow" and create a new shadow.
1537 TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);
1538 TAP = getNextShadow(IA, TAP, true);
1539 }
1540
1541 // Create the link.
1542 TAP.Addr->linkToDef(TAP.Id, RDA);
1543
1544 if (Cover)
1545 break;
1546 }
1547}
1548
1549// Create data-flow links for all reference nodes in the statement node SA.
1550template <typename Predicate>
1551void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) {
1552#ifndef NDEBUG
1553 RegisterSet Defs(getPRI());
1554#endif
1555
1556 // Link all nodes (upwards in the data-flow) with their reaching defs.
1557 for (Ref RA : SA.Addr->members_if(P, *this)) {
1558 uint16_t Kind = RA.Addr->getKind();
1559 assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use);
1560 RegisterRef RR = RA.Addr->getRegRef(*this);
1561#ifndef NDEBUG
1562 // Do not expect multiple defs of the same reference.
1563 assert(Kind != NodeAttrs::Def || !Defs.count(RR));
1564 Defs.insert(RR);
1565#endif
1566
1567 auto F = DefM.find(RR.Reg);
1568 if (F == DefM.end())
1569 continue;
1570 DefStack &DS = F->second;
1571 if (Kind == NodeAttrs::Use)
1572 linkRefUp<UseNode *>(SA, RA, DS);
1573 else if (Kind == NodeAttrs::Def)
1574 linkRefUp<DefNode *>(SA, RA, DS);
1575 else
1576 llvm_unreachable("Unexpected node in instruction");
1577 }
1578}
1579
1580// Create data-flow links for all instructions in the block node BA. This
1581// will include updating any phi nodes in BA.
1582void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, Block BA) {
1583 // Push block delimiters.
1584 markBlock(BA.Id, DefM);
1585
1586 auto IsClobber = [](Ref RA) -> bool {
1587 return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);
1588 };
1589 auto IsNoClobber = [](Ref RA) -> bool {
1590 return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);
1591 };
1592
1593 assert(BA.Addr && "block node address is needed to create a data-flow link");
1594 // For each non-phi instruction in the block, link all the defs and uses
1595 // to their reaching defs. For any member of the block (including phis),
1596 // push the defs on the corresponding stacks.
1597 for (Instr IA : BA.Addr->members(*this)) {
1598 // Ignore phi nodes here. They will be linked part by part from the
1599 // predecessors.
1600 if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1601 linkStmtRefs(DefM, IA, IsUse);
1602 linkStmtRefs(DefM, IA, IsClobber);
1603 }
1604
1605 // Push the definitions on the stack.
1606 pushClobbers(IA, DefM);
1607
1608 if (IA.Addr->getKind() == NodeAttrs::Stmt)
1609 linkStmtRefs(DefM, IA, IsNoClobber);
1610
1611 pushDefs(IA, DefM);
1612 }
1613
1614 // Recursively process all children in the dominator tree.
1615 MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());
1616 for (auto *I : *N) {
1617 MachineBasicBlock *SB = I->getBlock();
1618 Block SBA = findBlock(SB);
1619 linkBlockRefs(DefM, SBA);
1620 }
1621
1622 // Link the phi uses from the successor blocks.
1623 auto IsUseForBA = [BA](Node NA) -> bool {
1624 if (NA.Addr->getKind() != NodeAttrs::Use)
1625 return false;
1626 assert(NA.Addr->getFlags() & NodeAttrs::PhiRef);
1627 return PhiUse(NA).Addr->getPredecessor() == BA.Id;
1628 };
1629
1630 RegisterAggr EHLiveIns = getLandingPadLiveIns();
1631 MachineBasicBlock *MBB = BA.Addr->getCode();
1632
1633 for (MachineBasicBlock *SB : MBB->successors()) {
1634 bool IsEHPad = SB->isEHPad();
1635 Block SBA = findBlock(SB);
1636 for (Instr IA : SBA.Addr->members_if(IsPhi, *this)) {
1637 // Do not link phi uses for landing pad live-ins.
1638 if (IsEHPad) {
1639 // Find what register this phi is for.
1640 Ref RA = IA.Addr->getFirstMember(*this);
1641 assert(RA.Id != 0);
1642 if (EHLiveIns.hasCoverOf(RA.Addr->getRegRef(*this)))
1643 continue;
1644 }
1645 // Go over each phi use associated with MBB, and link it.
1646 for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {
1647 PhiUse PUA = U;
1648 RegisterRef RR = PUA.Addr->getRegRef(*this);
1649 linkRefUp<UseNode *>(IA, PUA, DefM[RR.Reg]);
1650 }
1651 }
1652 }
1653
1654 // Pop all defs from this block from the definition stacks.
1655 releaseBlock(BA.Id, DefM);
1656}
1657
1658// Remove the use node UA from any data-flow and structural links.
1659void DataFlowGraph::unlinkUseDF(Use UA) {
1660 NodeId RD = UA.Addr->getReachingDef();
1661 NodeId Sib = UA.Addr->getSibling();
1662
1663 if (RD == 0) {
1664 assert(Sib == 0);
1665 return;
1666 }
1667
1668 auto RDA = addr<DefNode *>(RD);
1669 auto TA = addr<UseNode *>(RDA.Addr->getReachedUse());
1670 if (TA.Id == UA.Id) {
1671 RDA.Addr->setReachedUse(Sib);
1672 return;
1673 }
1674
1675 while (TA.Id != 0) {
1676 NodeId S = TA.Addr->getSibling();
1677 if (S == UA.Id) {
1678 TA.Addr->setSibling(UA.Addr->getSibling());
1679 return;
1680 }
1681 TA = addr<UseNode *>(S);
1682 }
1683}
1684
1685// Remove the def node DA from any data-flow and structural links.
1686void DataFlowGraph::unlinkDefDF(Def DA) {
1687 //
1688 // RD
1689 // | reached
1690 // | def
1691 // :
1692 // .
1693 // +----+
1694 // ... -- | DA | -- ... -- 0 : sibling chain of DA
1695 // +----+
1696 // | | reached
1697 // | : def
1698 // | .
1699 // | ... : Siblings (defs)
1700 // |
1701 // : reached
1702 // . use
1703 // ... : sibling chain of reached uses
1704
1705 NodeId RD = DA.Addr->getReachingDef();
1706
1707 // Visit all siblings of the reached def and reset their reaching defs.
1708 // Also, defs reached by DA are now "promoted" to being reached by RD,
1709 // so all of them will need to be spliced into the sibling chain where
1710 // DA belongs.
1711 auto getAllNodes = [this](NodeId N) -> NodeList {
1712 NodeList Res;
1713 while (N) {
1714 auto RA = addr<RefNode *>(N);
1715 // Keep the nodes in the exact sibling order.
1716 Res.push_back(RA);
1717 N = RA.Addr->getSibling();
1718 }
1719 return Res;
1720 };
1721 NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());
1722 NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());
1723
1724 if (RD == 0) {
1725 for (Ref I : ReachedDefs)
1726 I.Addr->setSibling(0);
1727 for (Ref I : ReachedUses)
1728 I.Addr->setSibling(0);
1729 }
1730 for (Def I : ReachedDefs)
1731 I.Addr->setReachingDef(RD);
1732 for (Use I : ReachedUses)
1733 I.Addr->setReachingDef(RD);
1734
1735 NodeId Sib = DA.Addr->getSibling();
1736 if (RD == 0) {
1737 assert(Sib == 0);
1738 return;
1739 }
1740
1741 // Update the reaching def node and remove DA from the sibling list.
1742 auto RDA = addr<DefNode *>(RD);
1743 auto TA = addr<DefNode *>(RDA.Addr->getReachedDef());
1744 if (TA.Id == DA.Id) {
1745 // If DA is the first reached def, just update the RD's reached def
1746 // to the DA's sibling.
1747 RDA.Addr->setReachedDef(Sib);
1748 } else {
1749 // Otherwise, traverse the sibling list of the reached defs and remove
1750 // DA from it.
1751 while (TA.Id != 0) {
1752 NodeId S = TA.Addr->getSibling();
1753 if (S == DA.Id) {
1754 TA.Addr->setSibling(Sib);
1755 break;
1756 }
1757 TA = addr<DefNode *>(S);
1758 }
1759 }
1760
1761 // Splice the DA's reached defs into the RDA's reached def chain.
1762 if (!ReachedDefs.empty()) {
1763 auto Last = Def(ReachedDefs.back());
1764 Last.Addr->setSibling(RDA.Addr->getReachedDef());
1765 RDA.Addr->setReachedDef(ReachedDefs.front().Id);
1766 }
1767 // Splice the DA's reached uses into the RDA's reached use chain.
1768 if (!ReachedUses.empty()) {
1769 auto Last = Use(ReachedUses.back());
1770 Last.Addr->setSibling(RDA.Addr->getReachedUse());
1771 RDA.Addr->setReachedUse(ReachedUses.front().Id);
1772 }
1773}
1774
1776 return !disjoint(getPRI().getUnits(RR), TrackedUnits);
1777}
1778
1779bool DataFlowGraph::hasUntrackedRef(Stmt S, bool IgnoreReserved) const {
1781
1782 for (Ref R : S.Addr->members(*this)) {
1783 Ops.push_back(&R.Addr->getOp());
1784 RegisterRef RR = R.Addr->getRegRef(*this);
1785 if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.idx()])
1786 continue;
1787 if (!isTracked(RR))
1788 return true;
1789 }
1790 for (const MachineOperand &Op : S.Addr->getCode()->operands()) {
1791 if (!Op.isReg() && !Op.isRegMask())
1792 continue;
1793 if (!llvm::is_contained(Ops, &Op))
1794 return true;
1795 }
1796 return false;
1797}
1798
1799} // end namespace llvm::rdf
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
ReachingDefAnalysis & RDA
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
static RegisterPass< DebugifyModulePass > DM("debugify", "Attach debug info to everything")
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
unsigned const TargetRegisterInfo * TRI
unsigned Reg
#define T
#define P(N)
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
const NodeList & List
Definition: RDFGraph.cpp:201
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file describes how to lower LLVM code to machine code.
Kind getKind() const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:335
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
This class represents an Operation in the Expression.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
unsigned pred_size() const
iterator_range< livein_iterator > liveins() const
unsigned succ_size() const
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
iterator find(MachineBasicBlock *B)
DominanceFrontierBase< MachineBasicBlock, false >::DomSetType DomSetType
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & front() const
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetInstrInfo - Interface to description of machine instruction set.
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
virtual const TargetLowering * getTargetLowering() const
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
NodeAddr< InstrNode * > Instr
Definition: RDFGraph.h:389
NodeAddr< StmtNode * > Stmt
Definition: RDFGraph.h:391
NodeAddr< RefNode * > Ref
Definition: RDFGraph.h:383
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:450
Print(const T &, const DataFlowGraph &) -> Print< T >
NodeAddr< PhiUseNode * > PhiUse
Definition: RDFGraph.h:386
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
uint32_t NodeId
Definition: RDFGraph.h:262
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
NodeAddr< BlockNode * > Block
Definition: RDFGraph.h:392
NodeAddr< NodeBase * > Node
Definition: RDFGraph.h:381
static void printRefHeader(raw_ostream &OS, const Ref RA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:111
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:45
uint32_t RegisterId
Definition: RDFRegisters.h:32
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
bool disjoint(const std::set< T > &A, const std::set< T > &B)
Definition: RDFRegisters.h:35
std::set< NodeId > NodeSet
Definition: RDFGraph.h:551
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
bool isFuncletEHPersonality(EHPersonality Pers)
Returns true if this is a personality function that invokes handler funclets (which must return to it...
DWARFExpression::Operation Op
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1758
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
void addPhi(Phi PA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:539
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:946
void removeMember(Node NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:488
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:520
void addMember(Node NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:468
Node getFirstMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:454
void addMemberAfter(Node MA, Node NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:481
Node getLastMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:461
SmallVector< const TargetRegisterClass * > Classes
Definition: RDFGraph.h:678
std::set< RegisterId > TrackRegs
Definition: RDFGraph.h:679
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:768
void unlinkUse(Use UA, bool RemoveFromOwner)
Definition: RDFGraph.h:801
void releaseBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:1009
Ref getNextRelated(Instr IA, Ref RA) const
Definition: RDFGraph.cpp:1163
bool isTracked(RegisterRef RR) const
Definition: RDFGraph.cpp:1775
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:985
static bool IsDef(const Node BA)
Definition: RDFGraph.h:825
DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, const MachineDominanceFrontier &mdf)
Definition: RDFGraph.cpp:637
Ref getNextShadow(Instr IA, Ref RA, bool Create)
Definition: RDFGraph.cpp:1225
static bool IsPhi(const Node BA)
Definition: RDFGraph.h:835
NodeList getRelatedRefs(Instr IA, Ref RA) const
Definition: RDFGraph.cpp:1136
void unlinkDef(Def DA, bool RemoveFromOwner)
Definition: RDFGraph.h:807
static bool IsUse(const Node BA)
Definition: RDFGraph.h:830
const PhysicalRegisterInfo & getPRI() const
Definition: RDFGraph.h:697
void markBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:1002
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.cpp:761
Block findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:799
bool hasUntrackedRef(Stmt S, bool IgnoreReserved=true) const
Definition: RDFGraph.cpp:1779
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:772
void pushAllDefs(Instr IA, DefStackMap &DM)
Definition: RDFGraph.cpp:1027
void linkToDef(NodeId Self, Def DA)
Definition: RDFGraph.cpp:440
MachineFunction * getCode() const
Definition: RDFGraph.h:652
Block findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const
Definition: RDFGraph.cpp:569
Block getEntryBlock(const DataFlowGraph &G)
Definition: RDFGraph.cpp:579
Node getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:526
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:371
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:303
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:300
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:297
NodeId getNext() const
Definition: RDFGraph.h:495
Ref_struct RefData
Definition: RDFGraph.h:540
void append(Node NA)
Definition: RDFGraph.cpp:390
Code_struct CodeData
Definition: RDFGraph.h:541
const TargetRegisterInfo & getTRI() const
Definition: RDFRegisters.h:173
bool equal_to(RegisterRef A, RegisterRef B) const
void setRegRef(RegisterRef RR, DataFlowGraph &G)
Definition: RDFGraph.cpp:412
RegisterRef getRegRef(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:402
Node getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:428
iterator_range< ref_iterator > refs() const
Definition: RDFRegisters.h:276
RegisterAggr & insert(RegisterRef RR)
constexpr unsigned idx() const
Definition: RDFRegisters.h:102
constexpr bool isReg() const
Definition: RDFRegisters.h:98
static constexpr bool isMaskId(unsigned Id)
Definition: RDFRegisters.h:119
static constexpr bool isRegId(unsigned Id)
Definition: RDFRegisters.h:113
virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:608
const TargetInstrInfo & TII
Definition: RDFGraph.h:460
virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:589
virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:595
void linkToDef(NodeId Self, Def DA)
Definition: RDFGraph.cpp:447