LLVM  15.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<NodeId>(RA.Id, G) << '<'
109  << Print<RegisterRef>(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<NodeId>(N, P.G);
119  OS << ',';
120  if (NodeId N = P.Obj.Addr->getReachedDef())
121  OS << Print<NodeId>(N, P.G);
122  OS << ',';
123  if (NodeId N = P.Obj.Addr->getReachedUse())
124  OS << Print<NodeId>(N, P.G);
125  OS << "):";
126  if (NodeId N = P.Obj.Addr->getSibling())
127  OS << Print<NodeId>(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<NodeId>(N, P.G);
136  OS << "):";
137  if (NodeId N = P.Obj.Addr->getSibling())
138  OS << Print<NodeId>(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<NodeId>(N, P.G);
148  OS << ',';
149  if (NodeId N = P.Obj.Addr->getPredecessor())
150  OS << Print<NodeId>(N, P.G);
151  OS << "):";
152  if (NodeId N = P.Obj.Addr->getSibling())
153  OS << Print<NodeId>(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<NodeId>(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<NodeId>(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<NodeId>(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<NodeId>(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<NodeId>(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<NodeId>(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<NodeId>(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<RegisterRef>(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<NodeId>(I->Id, P.G)
322  << '<' << Print<RegisterRef>(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, const TargetOperandInfo &toi)
652  : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi),
653  LiveIns(PRI) {
654 }
655 
656 // The implementation of the definition stack.
657 // Each register reference has its own definition stack. In particular,
658 // for a register references "Reg" and "Reg:subreg" will each have their
659 // own definition stacks.
660 
661 // Construct a stack iterator.
662 DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S,
663  bool Top) : DS(S) {
664  if (!Top) {
665  // Initialize to bottom.
666  Pos = 0;
667  return;
668  }
669  // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty).
670  Pos = DS.Stack.size();
671  while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos-1]))
672  Pos--;
673 }
674 
675 // Return the size of the stack, including block delimiters.
677  unsigned S = 0;
678  for (auto I = top(), E = bottom(); I != E; I.down())
679  S++;
680  return S;
681 }
682 
683 // Remove the top entry from the stack. Remove all intervening delimiters
684 // so that after this, the stack is either empty, or the top of the stack
685 // is a non-delimiter.
687  assert(!empty());
688  unsigned P = nextDown(Stack.size());
689  Stack.resize(P);
690 }
691 
692 // Push a delimiter for block node N on the stack.
694  assert(N != 0);
695  Stack.push_back(NodeAddr<DefNode*>(nullptr, N));
696 }
697 
698 // Remove all nodes from the top of the stack, until the delimited for
699 // block node N is encountered. Remove the delimiter as well. In effect,
700 // this will remove from the stack all definitions from block N.
702  assert(N != 0);
703  unsigned P = Stack.size();
704  while (P > 0) {
705  bool Found = isDelimiter(Stack[P-1], N);
706  P--;
707  if (Found)
708  break;
709  }
710  // This will also remove the delimiter, if found.
711  Stack.resize(P);
712 }
713 
714 // Move the stack iterator up by one.
715 unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const {
716  // Get the next valid position after P (skipping all delimiters).
717  // The input position P does not have to point to a non-delimiter.
718  unsigned SS = Stack.size();
719  bool IsDelim;
720  assert(P < SS);
721  do {
722  P++;
723  IsDelim = isDelimiter(Stack[P-1]);
724  } while (P < SS && IsDelim);
725  assert(!IsDelim);
726  return P;
727 }
728 
729 // Move the stack iterator down by one.
730 unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const {
731  // Get the preceding valid position before P (skipping all delimiters).
732  // The input position P does not have to point to a non-delimiter.
733  assert(P > 0 && P <= Stack.size());
734  bool IsDelim = isDelimiter(Stack[P-1]);
735  do {
736  if (--P == 0)
737  break;
738  IsDelim = isDelimiter(Stack[P-1]);
739  } while (P > 0 && IsDelim);
740  assert(!IsDelim);
741  return P;
742 }
743 
744 // Register information.
745 
746 RegisterSet DataFlowGraph::getLandingPadLiveIns() const {
747  RegisterSet LR;
748  const Function &F = MF.getFunction();
749  const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn()
750  : nullptr;
751  const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
752  if (RegisterId R = TLI.getExceptionPointerRegister(PF))
753  LR.insert(RegisterRef(R));
756  LR.insert(RegisterRef(R));
757  }
758  return LR;
759 }
760 
761 // Node management functions.
762 
763 // Get the pointer to the node with the id N.
765  if (N == 0)
766  return nullptr;
767  return Memory.ptr(N);
768 }
769 
770 // Get the id of the node at the address P.
772  if (P == nullptr)
773  return 0;
774  return Memory.id(P);
775 }
776 
777 // Allocate a new node and set the attributes to Attrs.
778 NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) {
779  NodeAddr<NodeBase*> P = Memory.New();
780  P.Addr->init();
781  P.Addr->setAttrs(Attrs);
782  return P;
783 }
784 
785 // Make a copy of the given node B, except for the data-flow links, which
786 // are set to 0.
787 NodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) {
788  NodeAddr<NodeBase*> NA = newNode(0);
789  memcpy(NA.Addr, B.Addr, sizeof(NodeBase));
790  // Ref nodes need to have the data-flow links reset.
791  if (NA.Addr->getType() == NodeAttrs::Ref) {
792  NodeAddr<RefNode*> RA = NA;
793  RA.Addr->setReachingDef(0);
794  RA.Addr->setSibling(0);
795  if (NA.Addr->getKind() == NodeAttrs::Def) {
796  NodeAddr<DefNode*> DA = NA;
797  DA.Addr->setReachedDef(0);
798  DA.Addr->setReachedUse(0);
799  }
800  }
801  return NA;
802 }
803 
804 // Allocation routines for specific node types/kinds.
805 
806 NodeAddr<UseNode*> DataFlowGraph::newUse(NodeAddr<InstrNode*> Owner,
807  MachineOperand &Op, uint16_t Flags) {
808  NodeAddr<UseNode*> UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
809  UA.Addr->setRegRef(&Op, *this);
810  return UA;
811 }
812 
813 NodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner,
814  RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) {
815  NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
816  assert(Flags & NodeAttrs::PhiRef);
817  PUA.Addr->setRegRef(RR, *this);
818  PUA.Addr->setPredecessor(PredB.Id);
819  return PUA;
820 }
821 
822 NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner,
823  MachineOperand &Op, uint16_t Flags) {
824  NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
825  DA.Addr->setRegRef(&Op, *this);
826  return DA;
827 }
828 
829 NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner,
830  RegisterRef RR, uint16_t Flags) {
831  NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
832  assert(Flags & NodeAttrs::PhiRef);
833  DA.Addr->setRegRef(RR, *this);
834  return DA;
835 }
836 
837 NodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) {
839  Owner.Addr->addPhi(PA, *this);
840  return PA;
841 }
842 
843 NodeAddr<StmtNode*> DataFlowGraph::newStmt(NodeAddr<BlockNode*> Owner,
844  MachineInstr *MI) {
846  SA.Addr->setCode(MI);
847  Owner.Addr->addMember(SA, *this);
848  return SA;
849 }
850 
851 NodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner,
854  BA.Addr->setCode(BB);
855  Owner.Addr->addMember(BA, *this);
856  return BA;
857 }
858 
859 NodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) {
861  FA.Addr->setCode(MF);
862  return FA;
863 }
864 
865 // Build the data flow graph.
867  reset();
868  Func = newFunc(&MF);
869 
870  if (MF.empty())
871  return;
872 
873  for (MachineBasicBlock &B : MF) {
874  NodeAddr<BlockNode*> BA = newBlock(Func, &B);
875  BlockNodes.insert(std::make_pair(&B, BA));
876  for (MachineInstr &I : B) {
877  if (I.isDebugInstr())
878  continue;
879  buildStmt(BA, I);
880  }
881  }
882 
883  NodeAddr<BlockNode*> EA = Func.Addr->getEntryBlock(*this);
884  NodeList Blocks = Func.Addr->members(*this);
885 
886  // Collect information about block references.
887  RegisterSet AllRefs;
888  for (NodeAddr<BlockNode*> BA : Blocks)
889  for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
890  for (NodeAddr<RefNode*> RA : IA.Addr->members(*this))
891  AllRefs.insert(RA.Addr->getRegRef(*this));
892 
893  // Collect function live-ins and entry block live-ins.
894  MachineRegisterInfo &MRI = MF.getRegInfo();
895  MachineBasicBlock &EntryB = *EA.Addr->getCode();
896  assert(EntryB.pred_empty() && "Function entry block has predecessors");
897  for (std::pair<unsigned,unsigned> P : MRI.liveins())
898  LiveIns.insert(RegisterRef(P.first));
899  if (MRI.tracksLiveness()) {
900  for (auto I : EntryB.liveins())
901  LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask));
902  }
903 
904  // Add function-entry phi nodes for the live-in registers.
905  //for (std::pair<RegisterId,LaneBitmask> P : LiveIns) {
906  for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) {
907  RegisterRef RR = *I;
908  NodeAddr<PhiNode*> PA = newPhi(EA);
910  NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
911  PA.Addr->addMember(DA, *this);
912  }
913 
914  // Add phis for landing pads.
915  // Landing pads, unlike usual backs blocks, are not entered through
916  // branches in the program, or fall-throughs from other blocks. They
917  // are entered from the exception handling runtime and target's ABI
918  // may define certain registers as defined on entry to such a block.
919  RegisterSet EHRegs = getLandingPadLiveIns();
920  if (!EHRegs.empty()) {
921  for (NodeAddr<BlockNode*> BA : Blocks) {
922  const MachineBasicBlock &B = *BA.Addr->getCode();
923  if (!B.isEHPad())
924  continue;
925 
926  // Prepare a list of NodeIds of the block's predecessors.
927  NodeList Preds;
928  for (MachineBasicBlock *PB : B.predecessors())
929  Preds.push_back(findBlock(PB));
930 
931  // Build phi nodes for each live-in.
932  for (RegisterRef RR : EHRegs) {
933  NodeAddr<PhiNode*> PA = newPhi(BA);
935  // Add def:
936  NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
937  PA.Addr->addMember(DA, *this);
938  // Add uses (no reaching defs for phi uses):
939  for (NodeAddr<BlockNode*> PBA : Preds) {
940  NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
941  PA.Addr->addMember(PUA, *this);
942  }
943  }
944  }
945  }
946 
947  // Build a map "PhiM" which will contain, for each block, the set
948  // of references that will require phi definitions in that block.
949  BlockRefsMap PhiM;
950  for (NodeAddr<BlockNode*> BA : Blocks)
951  recordDefsForDF(PhiM, BA);
952  for (NodeAddr<BlockNode*> BA : Blocks)
953  buildPhis(PhiM, AllRefs, BA);
954 
955  // Link all the refs. This will recursively traverse the dominator tree.
956  DefStackMap DM;
957  linkBlockRefs(DM, EA);
958 
959  // Finally, remove all unused phi nodes.
961  removeUnusedPhis();
962 }
963 
964 RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
967  assert(Reg != 0);
968  if (Sub != 0)
969  Reg = TRI.getSubReg(Reg, Sub);
970  return RegisterRef(Reg);
971 }
972 
974  assert(Op.isReg() || Op.isRegMask());
975  if (Op.isReg())
976  return makeRegRef(Op.getReg(), Op.getSubReg());
977  return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll());
978 }
979 
980 // For each stack in the map DefM, push the delimiter for block B on it.
982  // Push block delimiters.
983  for (auto &P : DefM)
984  P.second.start_block(B);
985 }
986 
987 // Remove all definitions coming from block B from each stack in DefM.
989  // Pop all defs from this block from the definition stack. Defs that were
990  // added to the map during the traversal of instructions will not have a
991  // delimiter, but for those, the whole stack will be emptied.
992  for (auto &P : DefM)
993  P.second.clear_block(B);
994 
995  // Finally, remove empty stacks from the map.
996  for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {
997  NextI = std::next(I);
998  // This preserves the validity of iterators other than I.
999  if (I->second.empty())
1000  DefM.erase(I);
1001  }
1002 }
1003 
1004 // Push all definitions from the instruction node IA to an appropriate
1005 // stack in DefM.
1007  pushClobbers(IA, DefM);
1008  pushDefs(IA, DefM);
1009 }
1010 
1011 // Push all definitions from the instruction node IA to an appropriate
1012 // stack in DefM.
1013 void DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
1014  NodeSet Visited;
1015  std::set<RegisterId> Defined;
1016 
1017  // The important objectives of this function are:
1018  // - to be able to handle instructions both while the graph is being
1019  // constructed, and after the graph has been constructed, and
1020  // - maintain proper ordering of definitions on the stack for each
1021  // register reference:
1022  // - if there are two or more related defs in IA (i.e. coming from
1023  // the same machine operand), then only push one def on the stack,
1024  // - if there are multiple unrelated defs of non-overlapping
1025  // subregisters of S, then the stack for S will have both (in an
1026  // unspecified order), but the order does not matter from the data-
1027  // -flow perspective.
1028 
1029  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
1030  if (Visited.count(DA.Id))
1031  continue;
1032  if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))
1033  continue;
1034 
1035  NodeList Rel = getRelatedRefs(IA, DA);
1036  NodeAddr<DefNode*> PDA = Rel.front();
1037  RegisterRef RR = PDA.Addr->getRegRef(*this);
1038 
1039  // Push the definition on the stack for the register and all aliases.
1040  // The def stack traversal in linkNodeUp will check the exact aliasing.
1041  DefM[RR.Reg].push(DA);
1042  Defined.insert(RR.Reg);
1043  for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
1044  // Check that we don't push the same def twice.
1045  assert(A != RR.Reg);
1046  if (!Defined.count(A))
1047  DefM[A].push(DA);
1048  }
1049  // Mark all the related defs as visited.
1050  for (NodeAddr<NodeBase*> T : Rel)
1051  Visited.insert(T.Id);
1052  }
1053 }
1054 
1055 // Push all definitions from the instruction node IA to an appropriate
1056 // stack in DefM.
1057 void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
1058  NodeSet Visited;
1059 #ifndef NDEBUG
1060  std::set<RegisterId> Defined;
1061 #endif
1062 
1063  // The important objectives of this function are:
1064  // - to be able to handle instructions both while the graph is being
1065  // constructed, and after the graph has been constructed, and
1066  // - maintain proper ordering of definitions on the stack for each
1067  // register reference:
1068  // - if there are two or more related defs in IA (i.e. coming from
1069  // the same machine operand), then only push one def on the stack,
1070  // - if there are multiple unrelated defs of non-overlapping
1071  // subregisters of S, then the stack for S will have both (in an
1072  // unspecified order), but the order does not matter from the data-
1073  // -flow perspective.
1074 
1075  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
1076  if (Visited.count(DA.Id))
1077  continue;
1078  if (DA.Addr->getFlags() & NodeAttrs::Clobbering)
1079  continue;
1080 
1081  NodeList Rel = getRelatedRefs(IA, DA);
1082  NodeAddr<DefNode*> PDA = Rel.front();
1083  RegisterRef RR = PDA.Addr->getRegRef(*this);
1084 #ifndef NDEBUG
1085  // Assert if the register is defined in two or more unrelated defs.
1086  // This could happen if there are two or more def operands defining it.
1087  if (!Defined.insert(RR.Reg).second) {
1088  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
1089  dbgs() << "Multiple definitions of register: "
1090  << Print<RegisterRef>(RR, *this) << " in\n " << *MI << "in "
1091  << printMBBReference(*MI->getParent()) << '\n';
1092  llvm_unreachable(nullptr);
1093  }
1094 #endif
1095  // Push the definition on the stack for the register and all aliases.
1096  // The def stack traversal in linkNodeUp will check the exact aliasing.
1097  DefM[RR.Reg].push(DA);
1098  for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
1099  // Check that we don't push the same def twice.
1100  assert(A != RR.Reg);
1101  DefM[A].push(DA);
1102  }
1103  // Mark all the related defs as visited.
1104  for (NodeAddr<NodeBase*> T : Rel)
1105  Visited.insert(T.Id);
1106  }
1107 }
1108 
1109 // Return the list of all reference nodes related to RA, including RA itself.
1110 // See "getNextRelated" for the meaning of a "related reference".
1112  NodeAddr<RefNode*> RA) const {
1113  assert(IA.Id != 0 && RA.Id != 0);
1114 
1115  NodeList Refs;
1116  NodeId Start = RA.Id;
1117  do {
1118  Refs.push_back(RA);
1119  RA = getNextRelated(IA, RA);
1120  } while (RA.Id != 0 && RA.Id != Start);
1121  return Refs;
1122 }
1123 
1124 // Clear all information in the graph.
1125 void DataFlowGraph::reset() {
1126  Memory.clear();
1127  BlockNodes.clear();
1128  Func = NodeAddr<FuncNode*>();
1129 }
1130 
1131 // Return the next reference node in the instruction node IA that is related
1132 // to RA. Conceptually, two reference nodes are related if they refer to the
1133 // same instance of a register access, but differ in flags or other minor
1134 // characteristics. Specific examples of related nodes are shadow reference
1135 // nodes.
1136 // Return the equivalent of nullptr if there are no more related references.
1138  NodeAddr<RefNode*> RA) const {
1139  assert(IA.Id != 0 && RA.Id != 0);
1140 
1141  auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool {
1142  if (TA.Addr->getKind() != RA.Addr->getKind())
1143  return false;
1144  if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this))
1145  return false;
1146  return true;
1147  };
1148  auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
1149  return Related(TA) &&
1150  &RA.Addr->getOp() == &TA.Addr->getOp();
1151  };
1152  auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
1153  if (!Related(TA))
1154  return false;
1155  if (TA.Addr->getKind() != NodeAttrs::Use)
1156  return true;
1157  // For phi uses, compare predecessor blocks.
1158  const NodeAddr<const PhiUseNode*> TUA = TA;
1159  const NodeAddr<const PhiUseNode*> RUA = RA;
1160  return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor();
1161  };
1162 
1163  RegisterRef RR = RA.Addr->getRegRef(*this);
1164  if (IA.Addr->getKind() == NodeAttrs::Stmt)
1165  return RA.Addr->getNextRef(RR, RelatedStmt, true, *this);
1166  return RA.Addr->getNextRef(RR, RelatedPhi, true, *this);
1167 }
1168 
1169 // Find the next node related to RA in IA that satisfies condition P.
1170 // If such a node was found, return a pair where the second element is the
1171 // located node. If such a node does not exist, return a pair where the
1172 // first element is the element after which such a node should be inserted,
1173 // and the second element is a null-address.
1174 template <typename Predicate>
1175 std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
1176 DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
1177  Predicate P) const {
1178  assert(IA.Id != 0 && RA.Id != 0);
1179 
1180  NodeAddr<RefNode*> NA;
1181  NodeId Start = RA.Id;
1182  while (true) {
1183  NA = getNextRelated(IA, RA);
1184  if (NA.Id == 0 || NA.Id == Start)
1185  break;
1186  if (P(NA))
1187  break;
1188  RA = NA;
1189  }
1190 
1191  if (NA.Id != 0 && NA.Id != Start)
1192  return std::make_pair(RA, NA);
1193  return std::make_pair(RA, NodeAddr<RefNode*>());
1194 }
1195 
1196 // Get the next shadow node in IA corresponding to RA, and optionally create
1197 // such a node if it does not exist.
1199  NodeAddr<RefNode*> RA, bool Create) {
1200  assert(IA.Id != 0 && RA.Id != 0);
1201 
1202  uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1203  auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
1204  return TA.Addr->getFlags() == Flags;
1205  };
1206  auto Loc = locateNextRef(IA, RA, IsShadow);
1207  if (Loc.second.Id != 0 || !Create)
1208  return Loc.second;
1209 
1210  // Create a copy of RA and mark is as shadow.
1211  NodeAddr<RefNode*> NA = cloneNode(RA);
1212  NA.Addr->setFlags(Flags | NodeAttrs::Shadow);
1213  IA.Addr->addMemberAfter(Loc.first, NA, *this);
1214  return NA;
1215 }
1216 
1217 // Get the next shadow node in IA corresponding to RA. Return null-address
1218 // if such a node does not exist.
1220  NodeAddr<RefNode*> RA) const {
1221  assert(IA.Id != 0 && RA.Id != 0);
1222  uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1223  auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
1224  return TA.Addr->getFlags() == Flags;
1225  };
1226  return locateNextRef(IA, RA, IsShadow).second;
1227 }
1228 
1229 // Create a new statement node in the block node BA that corresponds to
1230 // the machine instruction MI.
1231 void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) {
1232  NodeAddr<StmtNode*> SA = newStmt(BA, &In);
1233 
1234  auto isCall = [] (const MachineInstr &In) -> bool {
1235  if (In.isCall())
1236  return true;
1237  // Is tail call?
1238  if (In.isBranch()) {
1239  for (const MachineOperand &Op : In.operands())
1240  if (Op.isGlobal() || Op.isSymbol())
1241  return true;
1242  // Assume indirect branches are calls. This is for the purpose of
1243  // keeping implicit operands, and so it won't hurt on intra-function
1244  // indirect branches.
1245  if (In.isIndirectBranch())
1246  return true;
1247  }
1248  return false;
1249  };
1250 
1251  auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool {
1252  // This instruction defines DR. Check if there is a use operand that
1253  // would make DR live on entry to the instruction.
1254  for (const MachineOperand &Op : In.operands()) {
1255  if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef())
1256  continue;
1257  RegisterRef UR = makeRegRef(Op);
1258  if (PRI.alias(DR, UR))
1259  return false;
1260  }
1261  return true;
1262  };
1263 
1264  bool IsCall = isCall(In);
1265  unsigned NumOps = In.getNumOperands();
1266 
1267  // Avoid duplicate implicit defs. This will not detect cases of implicit
1268  // defs that define registers that overlap, but it is not clear how to
1269  // interpret that in the absence of explicit defs. Overlapping explicit
1270  // defs are likely illegal already.
1271  BitVector DoneDefs(TRI.getNumRegs());
1272  // Process explicit defs first.
1273  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1274  MachineOperand &Op = In.getOperand(OpN);
1275  if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
1276  continue;
1277  Register R = Op.getReg();
1278  if (!R || !Register::isPhysicalRegister(R))
1279  continue;
1280  uint16_t Flags = NodeAttrs::None;
1281  if (TOI.isPreserving(In, OpN)) {
1282  Flags |= NodeAttrs::Preserving;
1283  // If the def is preserving, check if it is also undefined.
1284  if (isDefUndef(In, makeRegRef(Op)))
1285  Flags |= NodeAttrs::Undef;
1286  }
1287  if (TOI.isClobbering(In, OpN))
1288  Flags |= NodeAttrs::Clobbering;
1289  if (TOI.isFixedReg(In, OpN))
1290  Flags |= NodeAttrs::Fixed;
1291  if (IsCall && Op.isDead())
1292  Flags |= NodeAttrs::Dead;
1293  NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1294  SA.Addr->addMember(DA, *this);
1295  assert(!DoneDefs.test(R));
1296  DoneDefs.set(R);
1297  }
1298 
1299  // Process reg-masks (as clobbers).
1300  BitVector DoneClobbers(TRI.getNumRegs());
1301  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1302  MachineOperand &Op = In.getOperand(OpN);
1303  if (!Op.isRegMask())
1304  continue;
1307  NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1308  SA.Addr->addMember(DA, *this);
1309  // Record all clobbered registers in DoneDefs.
1310  const uint32_t *RM = Op.getRegMask();
1311  for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i)
1312  if (!(RM[i/32] & (1u << (i%32))))
1313  DoneClobbers.set(i);
1314  }
1315 
1316  // Process implicit defs, skipping those that have already been added
1317  // as explicit.
1318  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1319  MachineOperand &Op = In.getOperand(OpN);
1320  if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())
1321  continue;
1322  Register R = Op.getReg();
1323  if (!R || !Register::isPhysicalRegister(R) || DoneDefs.test(R))
1324  continue;
1325  RegisterRef RR = makeRegRef(Op);
1326  uint16_t Flags = NodeAttrs::None;
1327  if (TOI.isPreserving(In, OpN)) {
1328  Flags |= NodeAttrs::Preserving;
1329  // If the def is preserving, check if it is also undefined.
1330  if (isDefUndef(In, RR))
1331  Flags |= NodeAttrs::Undef;
1332  }
1333  if (TOI.isClobbering(In, OpN))
1334  Flags |= NodeAttrs::Clobbering;
1335  if (TOI.isFixedReg(In, OpN))
1336  Flags |= NodeAttrs::Fixed;
1337  if (IsCall && Op.isDead()) {
1338  if (DoneClobbers.test(R))
1339  continue;
1340  Flags |= NodeAttrs::Dead;
1341  }
1342  NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1343  SA.Addr->addMember(DA, *this);
1344  DoneDefs.set(R);
1345  }
1346 
1347  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1348  MachineOperand &Op = In.getOperand(OpN);
1349  if (!Op.isReg() || !Op.isUse())
1350  continue;
1351  Register R = Op.getReg();
1352  if (!R || !Register::isPhysicalRegister(R))
1353  continue;
1354  uint16_t Flags = NodeAttrs::None;
1355  if (Op.isUndef())
1356  Flags |= NodeAttrs::Undef;
1357  if (TOI.isFixedReg(In, OpN))
1358  Flags |= NodeAttrs::Fixed;
1359  NodeAddr<UseNode*> UA = newUse(SA, Op, Flags);
1360  SA.Addr->addMember(UA, *this);
1361  }
1362 }
1363 
1364 // Scan all defs in the block node BA and record in PhiM the locations of
1365 // phi nodes corresponding to these defs.
1366 void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,
1367  NodeAddr<BlockNode*> BA) {
1368  // Check all defs from block BA and record them in each block in BA's
1369  // iterated dominance frontier. This information will later be used to
1370  // create phi nodes.
1371  MachineBasicBlock *BB = BA.Addr->getCode();
1372  assert(BB);
1373  auto DFLoc = MDF.find(BB);
1374  if (DFLoc == MDF.end() || DFLoc->second.empty())
1375  return;
1376 
1377  // Traverse all instructions in the block and collect the set of all
1378  // defined references. For each reference there will be a phi created
1379  // in the block's iterated dominance frontier.
1380  // This is done to make sure that each defined reference gets only one
1381  // phi node, even if it is defined multiple times.
1382  RegisterSet Defs;
1383  for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
1384  for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this))
1385  Defs.insert(RA.Addr->getRegRef(*this));
1386 
1387  // Calculate the iterated dominance frontier of BB.
1388  const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;
1389  SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end());
1390  for (unsigned i = 0; i < IDF.size(); ++i) {
1391  auto F = MDF.find(IDF[i]);
1392  if (F != MDF.end())
1393  IDF.insert(F->second.begin(), F->second.end());
1394  }
1395 
1396  // Finally, add the set of defs to each block in the iterated dominance
1397  // frontier.
1398  for (auto DB : IDF) {
1399  NodeAddr<BlockNode*> DBA = findBlock(DB);
1400  PhiM[DBA.Id].insert(Defs.begin(), Defs.end());
1401  }
1402 }
1403 
1404 // Given the locations of phi nodes in the map PhiM, create the phi nodes
1405 // that are located in the block node BA.
1406 void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
1407  NodeAddr<BlockNode*> BA) {
1408  // Check if this blocks has any DF defs, i.e. if there are any defs
1409  // that this block is in the iterated dominance frontier of.
1410  auto HasDF = PhiM.find(BA.Id);
1411  if (HasDF == PhiM.end() || HasDF->second.empty())
1412  return;
1413 
1414  // First, remove all R in Refs in such that there exists T in Refs
1415  // such that T covers R. In other words, only leave those refs that
1416  // are not covered by another ref (i.e. maximal with respect to covering).
1417 
1418  auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef {
1419  for (RegisterRef I : RRs)
1420  if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI))
1421  RR = I;
1422  return RR;
1423  };
1424 
1425  RegisterSet MaxDF;
1426  for (RegisterRef I : HasDF->second)
1427  MaxDF.insert(MaxCoverIn(I, HasDF->second));
1428 
1429  std::vector<RegisterRef> MaxRefs;
1430  for (RegisterRef I : MaxDF)
1431  MaxRefs.push_back(MaxCoverIn(I, AllRefs));
1432 
1433  // Now, for each R in MaxRefs, get the alias closure of R. If the closure
1434  // only has R in it, create a phi a def for R. Otherwise, create a phi,
1435  // and add a def for each S in the closure.
1436 
1437  // Sort the refs so that the phis will be created in a deterministic order.
1438  llvm::sort(MaxRefs);
1439  // Remove duplicates.
1440  auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end());
1441  MaxRefs.erase(NewEnd, MaxRefs.end());
1442 
1443  auto Aliased = [this,&MaxRefs](RegisterRef RR,
1444  std::vector<unsigned> &Closure) -> bool {
1445  for (unsigned I : Closure)
1446  if (PRI.alias(RR, MaxRefs[I]))
1447  return true;
1448  return false;
1449  };
1450 
1451  // Prepare a list of NodeIds of the block's predecessors.
1452  NodeList Preds;
1453  const MachineBasicBlock *MBB = BA.Addr->getCode();
1454  for (MachineBasicBlock *PB : MBB->predecessors())
1455  Preds.push_back(findBlock(PB));
1456 
1457  while (!MaxRefs.empty()) {
1458  // Put the first element in the closure, and then add all subsequent
1459  // elements from MaxRefs to it, if they alias at least one element
1460  // already in the closure.
1461  // ClosureIdx: vector of indices in MaxRefs of members of the closure.
1462  std::vector<unsigned> ClosureIdx = { 0 };
1463  for (unsigned i = 1; i != MaxRefs.size(); ++i)
1464  if (Aliased(MaxRefs[i], ClosureIdx))
1465  ClosureIdx.push_back(i);
1466 
1467  // Build a phi for the closure.
1468  unsigned CS = ClosureIdx.size();
1469  NodeAddr<PhiNode*> PA = newPhi(BA);
1470 
1471  // Add defs.
1472  for (unsigned X = 0; X != CS; ++X) {
1473  RegisterRef RR = MaxRefs[ClosureIdx[X]];
1475  NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
1476  PA.Addr->addMember(DA, *this);
1477  }
1478  // Add phi uses.
1479  for (NodeAddr<BlockNode*> PBA : Preds) {
1480  for (unsigned X = 0; X != CS; ++X) {
1481  RegisterRef RR = MaxRefs[ClosureIdx[X]];
1482  NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
1483  PA.Addr->addMember(PUA, *this);
1484  }
1485  }
1486 
1487  // Erase from MaxRefs all elements in the closure.
1488  auto Begin = MaxRefs.begin();
1489  for (unsigned Idx : llvm::reverse(ClosureIdx))
1490  MaxRefs.erase(Begin + Idx);
1491  }
1492 }
1493 
1494 // Remove any unneeded phi nodes that were created during the build process.
1495 void DataFlowGraph::removeUnusedPhis() {
1496  // This will remove unused phis, i.e. phis where each def does not reach
1497  // any uses or other defs. This will not detect or remove circular phi
1498  // chains that are otherwise dead. Unused/dead phis are created during
1499  // the build process and this function is intended to remove these cases
1500  // that are easily determinable to be unnecessary.
1501 
1502  SetVector<NodeId> PhiQ;
1503  for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) {
1504  for (auto P : BA.Addr->members_if(IsPhi, *this))
1505  PhiQ.insert(P.Id);
1506  }
1507 
1508  static auto HasUsedDef = [](NodeList &Ms) -> bool {
1509  for (NodeAddr<NodeBase*> M : Ms) {
1510  if (M.Addr->getKind() != NodeAttrs::Def)
1511  continue;
1513  if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)
1514  return true;
1515  }
1516  return false;
1517  };
1518 
1519  // Any phi, if it is removed, may affect other phis (make them dead).
1520  // For each removed phi, collect the potentially affected phis and add
1521  // them back to the queue.
1522  while (!PhiQ.empty()) {
1523  auto PA = addr<PhiNode*>(PhiQ[0]);
1524  PhiQ.remove(PA.Id);
1525  NodeList Refs = PA.Addr->members(*this);
1526  if (HasUsedDef(Refs))
1527  continue;
1528  for (NodeAddr<RefNode*> RA : Refs) {
1529  if (NodeId RD = RA.Addr->getReachingDef()) {
1530  auto RDA = addr<DefNode*>(RD);
1531  NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this);
1532  if (IsPhi(OA))
1533  PhiQ.insert(OA.Id);
1534  }
1535  if (RA.Addr->isDef())
1536  unlinkDef(RA, true);
1537  else
1538  unlinkUse(RA, true);
1539  }
1540  NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this);
1541  BA.Addr->removeMember(PA, *this);
1542  }
1543 }
1544 
1545 // For a given reference node TA in an instruction node IA, connect the
1546 // reaching def of TA to the appropriate def node. Create any shadow nodes
1547 // as appropriate.
1548 template <typename T>
1549 void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA,
1550  DefStack &DS) {
1551  if (DS.empty())
1552  return;
1553  RegisterRef RR = TA.Addr->getRegRef(*this);
1554  NodeAddr<T> TAP;
1555 
1556  // References from the def stack that have been examined so far.
1557  RegisterAggr Defs(PRI);
1558 
1559  for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {
1560  RegisterRef QR = I->Addr->getRegRef(*this);
1561 
1562  // Skip all defs that are aliased to any of the defs that we have already
1563  // seen. If this completes a cover of RR, stop the stack traversal.
1564  bool Alias = Defs.hasAliasOf(QR);
1565  bool Cover = Defs.insert(QR).hasCoverOf(RR);
1566  if (Alias) {
1567  if (Cover)
1568  break;
1569  continue;
1570  }
1571 
1572  // The reaching def.
1574 
1575  // Pick the reached node.
1576  if (TAP.Id == 0) {
1577  TAP = TA;
1578  } else {
1579  // Mark the existing ref as "shadow" and create a new shadow.
1580  TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);
1581  TAP = getNextShadow(IA, TAP, true);
1582  }
1583 
1584  // Create the link.
1585  TAP.Addr->linkToDef(TAP.Id, RDA);
1586 
1587  if (Cover)
1588  break;
1589  }
1590 }
1591 
1592 // Create data-flow links for all reference nodes in the statement node SA.
1593 template <typename Predicate>
1594 void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA,
1595  Predicate P) {
1596 #ifndef NDEBUG
1597  RegisterSet Defs;
1598 #endif
1599 
1600  // Link all nodes (upwards in the data-flow) with their reaching defs.
1601  for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) {
1602  uint16_t Kind = RA.Addr->getKind();
1604  RegisterRef RR = RA.Addr->getRegRef(*this);
1605 #ifndef NDEBUG
1606  // Do not expect multiple defs of the same reference.
1607  assert(Kind != NodeAttrs::Def || !Defs.count(RR));
1608  Defs.insert(RR);
1609 #endif
1610 
1611  auto F = DefM.find(RR.Reg);
1612  if (F == DefM.end())
1613  continue;
1614  DefStack &DS = F->second;
1615  if (Kind == NodeAttrs::Use)
1616  linkRefUp<UseNode*>(SA, RA, DS);
1617  else if (Kind == NodeAttrs::Def)
1618  linkRefUp<DefNode*>(SA, RA, DS);
1619  else
1620  llvm_unreachable("Unexpected node in instruction");
1621  }
1622 }
1623 
1624 // Create data-flow links for all instructions in the block node BA. This
1625 // will include updating any phi nodes in BA.
1626 void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) {
1627  // Push block delimiters.
1628  markBlock(BA.Id, DefM);
1629 
1630  auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool {
1631  return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);
1632  };
1633  auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool {
1634  return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);
1635  };
1636 
1637  assert(BA.Addr && "block node address is needed to create a data-flow link");
1638  // For each non-phi instruction in the block, link all the defs and uses
1639  // to their reaching defs. For any member of the block (including phis),
1640  // push the defs on the corresponding stacks.
1641  for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) {
1642  // Ignore phi nodes here. They will be linked part by part from the
1643  // predecessors.
1644  if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1645  linkStmtRefs(DefM, IA, IsUse);
1646  linkStmtRefs(DefM, IA, IsClobber);
1647  }
1648 
1649  // Push the definitions on the stack.
1650  pushClobbers(IA, DefM);
1651 
1652  if (IA.Addr->getKind() == NodeAttrs::Stmt)
1653  linkStmtRefs(DefM, IA, IsNoClobber);
1654 
1655  pushDefs(IA, DefM);
1656  }
1657 
1658  // Recursively process all children in the dominator tree.
1659  MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());
1660  for (auto I : *N) {
1661  MachineBasicBlock *SB = I->getBlock();
1662  NodeAddr<BlockNode*> SBA = findBlock(SB);
1663  linkBlockRefs(DefM, SBA);
1664  }
1665 
1666  // Link the phi uses from the successor blocks.
1667  auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool {
1668  if (NA.Addr->getKind() != NodeAttrs::Use)
1669  return false;
1671  NodeAddr<PhiUseNode*> PUA = NA;
1672  return PUA.Addr->getPredecessor() == BA.Id;
1673  };
1674 
1675  RegisterSet EHLiveIns = getLandingPadLiveIns();
1676  MachineBasicBlock *MBB = BA.Addr->getCode();
1677 
1678  for (MachineBasicBlock *SB : MBB->successors()) {
1679  bool IsEHPad = SB->isEHPad();
1680  NodeAddr<BlockNode*> SBA = findBlock(SB);
1681  for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) {
1682  // Do not link phi uses for landing pad live-ins.
1683  if (IsEHPad) {
1684  // Find what register this phi is for.
1686  assert(RA.Id != 0);
1687  if (EHLiveIns.count(RA.Addr->getRegRef(*this)))
1688  continue;
1689  }
1690  // Go over each phi use associated with MBB, and link it.
1691  for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {
1692  NodeAddr<PhiUseNode*> PUA = U;
1693  RegisterRef RR = PUA.Addr->getRegRef(*this);
1694  linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]);
1695  }
1696  }
1697  }
1698 
1699  // Pop all defs from this block from the definition stacks.
1700  releaseBlock(BA.Id, DefM);
1701 }
1702 
1703 // Remove the use node UA from any data-flow and structural links.
1704 void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) {
1705  NodeId RD = UA.Addr->getReachingDef();
1706  NodeId Sib = UA.Addr->getSibling();
1707 
1708  if (RD == 0) {
1709  assert(Sib == 0);
1710  return;
1711  }
1712 
1713  auto RDA = addr<DefNode*>(RD);
1714  auto TA = addr<UseNode*>(RDA.Addr->getReachedUse());
1715  if (TA.Id == UA.Id) {
1716  RDA.Addr->setReachedUse(Sib);
1717  return;
1718  }
1719 
1720  while (TA.Id != 0) {
1721  NodeId S = TA.Addr->getSibling();
1722  if (S == UA.Id) {
1723  TA.Addr->setSibling(UA.Addr->getSibling());
1724  return;
1725  }
1726  TA = addr<UseNode*>(S);
1727  }
1728 }
1729 
1730 // Remove the def node DA from any data-flow and structural links.
1731 void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) {
1732  //
1733  // RD
1734  // | reached
1735  // | def
1736  // :
1737  // .
1738  // +----+
1739  // ... -- | DA | -- ... -- 0 : sibling chain of DA
1740  // +----+
1741  // | | reached
1742  // | : def
1743  // | .
1744  // | ... : Siblings (defs)
1745  // |
1746  // : reached
1747  // . use
1748  // ... : sibling chain of reached uses
1749 
1750  NodeId RD = DA.Addr->getReachingDef();
1751 
1752  // Visit all siblings of the reached def and reset their reaching defs.
1753  // Also, defs reached by DA are now "promoted" to being reached by RD,
1754  // so all of them will need to be spliced into the sibling chain where
1755  // DA belongs.
1756  auto getAllNodes = [this] (NodeId N) -> NodeList {
1757  NodeList Res;
1758  while (N) {
1759  auto RA = addr<RefNode*>(N);
1760  // Keep the nodes in the exact sibling order.
1761  Res.push_back(RA);
1762  N = RA.Addr->getSibling();
1763  }
1764  return Res;
1765  };
1766  NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());
1767  NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());
1768 
1769  if (RD == 0) {
1770  for (NodeAddr<RefNode*> I : ReachedDefs)
1771  I.Addr->setSibling(0);
1772  for (NodeAddr<RefNode*> I : ReachedUses)
1773  I.Addr->setSibling(0);
1774  }
1775  for (NodeAddr<DefNode*> I : ReachedDefs)
1776  I.Addr->setReachingDef(RD);
1777  for (NodeAddr<UseNode*> I : ReachedUses)
1778  I.Addr->setReachingDef(RD);
1779 
1780  NodeId Sib = DA.Addr->getSibling();
1781  if (RD == 0) {
1782  assert(Sib == 0);
1783  return;
1784  }
1785 
1786  // Update the reaching def node and remove DA from the sibling list.
1787  auto RDA = addr<DefNode*>(RD);
1788  auto TA = addr<DefNode*>(RDA.Addr->getReachedDef());
1789  if (TA.Id == DA.Id) {
1790  // If DA is the first reached def, just update the RD's reached def
1791  // to the DA's sibling.
1792  RDA.Addr->setReachedDef(Sib);
1793  } else {
1794  // Otherwise, traverse the sibling list of the reached defs and remove
1795  // DA from it.
1796  while (TA.Id != 0) {
1797  NodeId S = TA.Addr->getSibling();
1798  if (S == DA.Id) {
1799  TA.Addr->setSibling(Sib);
1800  break;
1801  }
1802  TA = addr<DefNode*>(S);
1803  }
1804  }
1805 
1806  // Splice the DA's reached defs into the RDA's reached def chain.
1807  if (!ReachedDefs.empty()) {
1808  auto Last = NodeAddr<DefNode*>(ReachedDefs.back());
1809  Last.Addr->setSibling(RDA.Addr->getReachedDef());
1810  RDA.Addr->setReachedDef(ReachedDefs.front().Id);
1811  }
1812  // Splice the DA's reached uses into the RDA's reached use chain.
1813  if (!ReachedUses.empty()) {
1814  auto Last = NodeAddr<UseNode*>(ReachedUses.back());
1815  Last.Addr->setSibling(RDA.Addr->getReachedUse());
1816  RDA.Addr->setReachedUse(ReachedUses.front().Id);
1817  }
1818 }
llvm::rdf::Print
Definition: RDFGraph.h:923
i
i
Definition: README.txt:29
llvm::rdf::RefNode::getSibling
NodeId getSibling() const
Definition: RDFGraph.h:535
llvm::rdf::NodeAttrs::kind
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:294
llvm::SPIRV::Decoration::Aliased
@ Aliased
llvm::rdf::RegisterAggr::rr_end
rr_iterator rr_end() const
Definition: RDFRegisters.h:240
llvm::rdf::PhiUseNode::getPredecessor
NodeId getPredecessor() const
Definition: RDFGraph.h:580
llvm::rdf::NodeAttrs::Dead
@ Dead
Definition: RDFGraph.h:290
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:412
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
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:17
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:1111
llvm::rdf::CodeNode::members_if
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:908
llvm::BumpPtrAllocatorImpl::Reset
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:121
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:808
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::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
T
llvm::Function
Definition: Function.h:60
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:422
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:1185
llvm::rdf::NodeAttrs::Phi
@ Phi
Definition: RDFGraph.h:277
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
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:474
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::rdf::NodeAttrs::Shadow
@ Shadow
Definition: RDFGraph.h:284
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::rdf::DataFlowGraph::unlinkUse
void unlinkUse(NodeAddr< UseNode * > UA, bool RemoveFromOwner)
Definition: RDFGraph.h:767
llvm::rdf::DataFlowGraph::releaseBlock
void releaseBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:988
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::MachineBasicBlock::liveins
iterator_range< livein_iterator > liveins() const
Definition: MachineBasicBlock.h:422
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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:1795
llvm::rdf::DataFlowGraph::getNextRelated
NodeAddr< RefNode * > getNextRelated(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1137
llvm::rdf::DataFlowGraph::DataFlowGraph
DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi)
Definition: RDFGraph.cpp:649
llvm::rdf::NodeAttrs::Code
@ Code
Definition: RDFGraph.h:270
llvm::MachineDominanceFrontier::find
iterator find(MachineBasicBlock *B)
Definition: MachineDominanceFrontier.h:68
STLExtras.h
llvm::rdf::NodeBase::Ref_struct::Op
MachineOperand * Op
Definition: RDFGraph.h:495
llvm::rdf::PhysicalRegisterInfo::getRegMaskId
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:110
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
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:241
MachineRegisterInfo.h
llvm::rdf::NodeBase::getFlags
uint16_t getFlags() const
Definition: RDFGraph.h:456
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:594
llvm::rdf::NodeAttrs::Preserving
@ Preserving
Definition: RDFGraph.h:287
llvm::classifyEHPersonality
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Definition: EHPersonalities.cpp:22
TargetLowering.h
llvm::SetVector::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:865
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::rdf::NodeAddr
Definition: RDFGraph.h:334
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:489
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:3412
llvm::rdf::NodeAttrs::PhiRef
@ PhiRef
Definition: RDFGraph.h:286
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::PhysicalRegisterInfo::alias
bool alias(RegisterRef RA, RegisterRef RB) const
Definition: RDFRegisters.h:118
llvm::rdf::NodeAttrs::Clobbering
@ Clobbering
Definition: RDFGraph.h:285
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
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:260
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:54
llvm::PrintLaneMask
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:94
BitVector.h
llvm::rdf::DataFlowGraph::IsDef
static bool IsDef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:792
llvm::BitVector
Definition: BitVector.h:75
llvm::rdf::NodeAttrs::None
@ None
Definition: RDFGraph.h:266
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:764
llvm::rdf::NodeAddr::Addr
T Addr
Definition: RDFGraph.h:351
llvm::rdf::NodeBase::getType
uint16_t getType() const
Definition: RDFGraph.h:454
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:320
llvm::rdf::DataFlowGraph::DefStack::clear_block
void clear_block(NodeId N)
Definition: RDFGraph.cpp:701
llvm::rdf::NodeBase::getNext
NodeId getNext() const
Definition: RDFGraph.h:457
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::rdf::NodeAttrs::Ref
@ Ref
Definition: RDFGraph.h:271
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::NodeAttrs::Block
@ Block
Definition: RDFGraph.h:279
llvm::rdf::DefNode::linkToDef
void linkToDef(NodeId Self, NodeAddr< DefNode * > DA)
Definition: RDFGraph.cpp:444
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
llvm::rdf::NodeBase::Code
Code_struct Code
Definition: RDFGraph.h:503
llvm::rdf::DataFlowGraph::DefStack::pop
void pop()
Definition: RDFGraph.cpp:686
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:656
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
llvm::rdf::DataFlowGraph::makeRegRef
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:964
llvm::X86AS::SS
@ SS
Definition: X86.h:193
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:240
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:656
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::rdf::NodeAllocator::NodeMemSize
@ NodeMemSize
Definition: RDFGraph.h:375
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:746
llvm::TargetInstrInfo::isPredicated
virtual bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
Definition: TargetInstrInfo.h:1435
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:584
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::rdf::DataFlowGraph
Definition: RDFGraph.h:644
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::rdf::NodeBase::Ref_struct::PR
PackedRegisterRef PR
Definition: RDFGraph.h:496
llvm::rdf::operator<<
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:55
llvm::rdf::BuildOptions::KeepDeadPhis
@ KeepDeadPhis
Definition: RDFGraph.h:330
llvm::rdf::DataFlowGraph::markBlock
void markBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:981
llvm::MachineRegisterInfo::liveins
ArrayRef< std::pair< MCRegister, Register > > liveins() const
Definition: MachineRegisterInfo.h:966
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:802
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::IndexedInstrProf::HashT::Last
@ Last
llvm::rdf::NodeBase::Attrs
uint16_t Attrs
Definition: RDFGraph.h:472
llvm::rdf::DataFlowGraph::DefStack::top
iterator top() const
Definition: RDFGraph.h:707
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:341
llvm::rdf::DataFlowGraph::pushAllDefs
void pushAllDefs(NodeAddr< InstrNode * > IA, DefStackMap &DM)
Definition: RDFGraph.cpp:1006
llvm::rdf::DataFlowGraph::DefStack::bottom
iterator bottom() const
Definition: RDFGraph.h:708
llvm::SIInstrFlags::DS
@ DS
Definition: SIDefines.h:60
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::NodeBase::getKind
uint16_t getKind() const
Definition: RDFGraph.h:455
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:471
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:469
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:365
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:549
llvm::rdf::DataFlowGraph::DefStack
Definition: RDFGraph.h:669
RDFGraph.h
llvm::rdf::NodeAttrs::Stmt
@ Stmt
Definition: RDFGraph.h:278
llvm::rdf::NodeBase::Code_struct::FirstM
NodeId FirstM
Definition: RDFGraph.h:486
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:635
uint32_t
TargetSubtargetInfo.h
llvm::rdf::NodeAttrs::type
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:293
llvm::rdf::DataFlowGraph::IsUse
static bool IsUse(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:797
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:362
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
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:1644
llvm::rdf::NodeAttrs::Fixed
@ Fixed
Definition: RDFGraph.h:288
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:740
llvm::rdf::DataFlowGraph::build
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:866
llvm::rdf::TargetOperandInfo
Definition: RDFGraph.h:414
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:1802
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:622
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:348
MachineDominanceFrontier.h
llvm::rdf::NodeBase
Definition: RDFGraph.h:449
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:146
llvm::rdf::NodeBase::Ref
Ref_struct Ref
Definition: RDFGraph.h:502
llvm::rdf::NodeBase::Ref_struct::Sib
NodeId Sib
Definition: RDFGraph.h:489
llvm::rdf::DataFlowGraph::DefStack::size
unsigned size() const
Definition: RDFGraph.cpp:676
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
llvm::rdf::NodeBase::setFlags
void setFlags(uint16_t F)
Definition: RDFGraph.h:461
llvm::rdf::RefNode::getOwner
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:432
llvm::rdf::NodeAttrs::Undef
@ Undef
Definition: RDFGraph.h:289
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1779
llvm::rdf::NodeBase::Code_struct::LastM
NodeId LastM
Definition: RDFGraph.h:486
llvm::rdf::NodeAttrs::Use
@ Use
Definition: RDFGraph.h:276
llvm::rdf::FuncNode::getEntryBlock
NodeAddr< BlockNode * > getEntryBlock(const DataFlowGraph &G)
Definition: RDFGraph.cpp:586
llvm::rdf::NodeAddr::Id
NodeId Id
Definition: RDFGraph.h:352
llvm::rdf::RefNode::getReachingDef
NodeId getReachingDef() const
Definition: RDFGraph.h:528
llvm::MachineDominanceFrontier::DomSetType
DominanceFrontierBase< MachineBasicBlock, false >::DomSetType DomSetType
Definition: MachineDominanceFrontier.h:26
llvm::TargetSubtargetInfo::getTargetLowering
virtual const TargetLowering * getTargetLowering() const
Definition: TargetSubtargetInfo.h:97
llvm::rdf::DataFlowGraph::unlinkDef
void unlinkDef(NodeAddr< DefNode * > DA, bool RemoveFromOwner)
Definition: RDFGraph.h:773
llvm::rdf::NodeSet
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
List
const NodeList & List
Definition: RDFGraph.cpp:199
RDA
ReachingDefAnalysis & RDA
Definition: ARMLowOverheadLoops.cpp:541
N
#define N
llvm::rdf::BlockNode::getCode
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:627
llvm::rdf::NodeAttrs::flags
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:295
LaneBitmask.h
llvm::rdf::NodeBase::append
void append(NodeAddr< NodeBase * > NA)
Definition: RDFGraph.cpp:394
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:1113
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:693
llvm::NodeSet::insert
bool insert(SUnit *SU)
Definition: MachinePipeliner.h:354
llvm::rdf::DataFlowGraph::getNextShadow
NodeAddr< RefNode * > getNextShadow(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA, bool Create)
Definition: RDFGraph.cpp:1198
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
llvm::rdf::DataFlowGraph::id
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:771
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:864
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:763
llvm::rdf::NodeAttrs::Def
@ Def
Definition: RDFGraph.h:275
TargetRegisterInfo.h
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
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::NodeAttrs::Func
@ Func
Definition: RDFGraph.h:280
llvm::rdf::DataFlowGraph::DefStackMap
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:733
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