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