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