LLVM  6.0.0svn
LiveRangeCalc.cpp
Go to the documentation of this file.
1 //===- LiveRangeCalc.cpp - Calculate live ranges --------------------------===//
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 // Implementation of the LiveRangeCalc class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "LiveRangeCalc.h"
15 #include "llvm/ADT/BitVector.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/MC/LaneBitmask.h"
31 #include <algorithm>
32 #include <cassert>
33 #include <iterator>
34 #include <tuple>
35 #include <utility>
36 
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "regalloc"
40 
41 // Reserve an address that indicates a value that is known to be "undef".
42 static VNInfo UndefVNI(0xbad, SlotIndex());
43 
44 void LiveRangeCalc::resetLiveOutMap() {
45  unsigned NumBlocks = MF->getNumBlockIDs();
46  Seen.clear();
47  Seen.resize(NumBlocks);
48  EntryInfos.clear();
49  Map.resize(NumBlocks);
50 }
51 
53  SlotIndexes *SI,
55  VNInfo::Allocator *VNIA) {
56  MF = mf;
57  MRI = &MF->getRegInfo();
58  Indexes = SI;
59  DomTree = MDT;
60  Alloc = VNIA;
61  resetLiveOutMap();
62  LiveIn.clear();
63 }
64 
65 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
66  LiveRange &LR, const MachineOperand &MO) {
67  const MachineInstr &MI = *MO.getParent();
68  SlotIndex DefIdx =
70 
71  // Create the def in LR. This may find an existing def.
72  LR.createDeadDef(DefIdx, Alloc);
73 }
74 
75 void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
76  assert(MRI && Indexes && "call reset() first");
77 
78  // Step 1: Create minimal live segments for every definition of Reg.
79  // Visit all def operands. If the same instruction has multiple defs of Reg,
80  // createDeadDef() will deduplicate.
81  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
82  unsigned Reg = LI.reg;
83  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
84  if (!MO.isDef() && !MO.readsReg())
85  continue;
86 
87  unsigned SubReg = MO.getSubReg();
88  if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
89  LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
90  : MRI->getMaxLaneMaskForVReg(Reg);
91  // If this is the first time we see a subregister def, initialize
92  // subranges by creating a copy of the main range.
93  if (!LI.hasSubRanges() && !LI.empty()) {
94  LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
95  LI.createSubRangeFrom(*Alloc, ClassMask, LI);
96  }
97 
98  LI.refineSubRanges(*Alloc, SubMask,
99  [&MO, this](LiveInterval::SubRange &SR) {
100  if (MO.isDef())
101  createDeadDef(*Indexes, *Alloc, SR, MO);
102  });
103  }
104 
105  // Create the def in the main liverange. We do not have to do this if
106  // subranges are tracked as we recreate the main range later in this case.
107  if (MO.isDef() && !LI.hasSubRanges())
108  createDeadDef(*Indexes, *Alloc, LI, MO);
109  }
110 
111  // We may have created empty live ranges for partially undefined uses, we
112  // can't keep them because we won't find defs in them later.
114 
115  // Step 2: Extend live segments to all uses, constructing SSA form as
116  // necessary.
117  if (LI.hasSubRanges()) {
118  for (LiveInterval::SubRange &S : LI.subranges()) {
119  LiveRangeCalc SubLRC;
120  SubLRC.reset(MF, Indexes, DomTree, Alloc);
121  SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
122  }
123  LI.clear();
125  } else {
126  resetLiveOutMap();
127  extendToUses(LI, Reg, LaneBitmask::getAll());
128  }
129 }
130 
132  // First create dead defs at all defs found in subranges.
133  LiveRange &MainRange = LI;
134  assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
135  "Expect empty main liverange");
136 
137  for (const LiveInterval::SubRange &SR : LI.subranges()) {
138  for (const VNInfo *VNI : SR.valnos) {
139  if (!VNI->isUnused() && !VNI->isPHIDef())
140  MainRange.createDeadDef(VNI->def, *Alloc);
141  }
142  }
143  resetLiveOutMap();
144  extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
145 }
146 
148  assert(MRI && Indexes && "call reset() first");
149 
150  // Visit all def operands. If the same instruction has multiple defs of Reg,
151  // LR.createDeadDef() will deduplicate.
152  for (MachineOperand &MO : MRI->def_operands(Reg))
153  createDeadDef(*Indexes, *Alloc, LR, MO);
154 }
155 
156 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
157  LiveInterval *LI) {
159  if (LI != nullptr)
160  LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
161 
162  // Visit all operands that read Reg. This may include partial defs.
163  bool IsSubRange = !Mask.all();
164  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
165  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
166  // Clear all kill flags. They will be reinserted after register allocation
167  // by LiveIntervalAnalysis::addKillFlags().
168  if (MO.isUse())
169  MO.setIsKill(false);
170  // MO::readsReg returns "true" for subregister defs. This is for keeping
171  // liveness of the entire register (i.e. for the main range of the live
172  // interval). For subranges, definitions of non-overlapping subregisters
173  // do not count as uses.
174  if (!MO.readsReg() || (IsSubRange && MO.isDef()))
175  continue;
176 
177  unsigned SubReg = MO.getSubReg();
178  if (SubReg != 0) {
179  LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
180  if (MO.isDef())
181  SLM = ~SLM;
182  // Ignore uses not reading the current (sub)range.
183  if ((SLM & Mask).none())
184  continue;
185  }
186 
187  // Determine the actual place of the use.
188  const MachineInstr *MI = MO.getParent();
189  unsigned OpNo = (&MO - &MI->getOperand(0));
190  SlotIndex UseIdx;
191  if (MI->isPHI()) {
192  assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
193  // The actual place where a phi operand is used is the end of the pred
194  // MBB. PHI operands are paired: (Reg, PredMBB).
195  UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
196  } else {
197  // Check for early-clobber redefs.
198  bool isEarlyClobber = false;
199  unsigned DefIdx;
200  if (MO.isDef())
201  isEarlyClobber = MO.isEarlyClobber();
202  else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
203  // FIXME: This would be a lot easier if tied early-clobber uses also
204  // had an early-clobber flag.
205  isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
206  }
207  UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
208  }
209 
210  // MI is reading Reg. We may have visited MI before if it happens to be
211  // reading Reg multiple times. That is OK, extend() is idempotent.
212  extend(LR, UseIdx, Reg, Undefs);
213  }
214 }
215 
216 void LiveRangeCalc::updateFromLiveIns() {
217  LiveRangeUpdater Updater;
218  for (const LiveInBlock &I : LiveIn) {
219  if (!I.DomNode)
220  continue;
221  MachineBasicBlock *MBB = I.DomNode->getBlock();
222  assert(I.Value && "No live-in value found");
223  SlotIndex Start, End;
224  std::tie(Start, End) = Indexes->getMBBRange(MBB);
225 
226  if (I.Kill.isValid())
227  // Value is killed inside this block.
228  End = I.Kill;
229  else {
230  // The value is live-through, update LiveOut as well.
231  // Defer the Domtree lookup until it is needed.
232  assert(Seen.test(MBB->getNumber()));
233  Map[MBB] = LiveOutPair(I.Value, nullptr);
234  }
235  Updater.setDest(&I.LR);
236  Updater.add(Start, End, I.Value);
237  }
238  LiveIn.clear();
239 }
240 
241 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
242  ArrayRef<SlotIndex> Undefs) {
243  assert(Use.isValid() && "Invalid SlotIndex");
244  assert(Indexes && "Missing SlotIndexes");
245  assert(DomTree && "Missing dominator tree");
246 
247  MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
248  assert(UseMBB && "No MBB at Use");
249 
250  // Is there a def in the same MBB we can extend?
251  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
252  if (EP.first != nullptr || EP.second)
253  return;
254 
255  // Find the single reaching def, or determine if Use is jointly dominated by
256  // multiple values, and we may need to create even more phi-defs to preserve
257  // VNInfo SSA form. Perform a search for all predecessor blocks where we
258  // know the dominating VNInfo.
259  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
260  return;
261 
262  // When there were multiple different values, we may need new PHIs.
263  calculateValues();
264 }
265 
266 // This function is called by a client after using the low-level API to add
267 // live-out and live-in blocks. The unique value optimization is not
268 // available, SplitEditor::transferValues handles that case directly anyway.
270  assert(Indexes && "Missing SlotIndexes");
271  assert(DomTree && "Missing dominator tree");
272  updateSSA();
273  updateFromLiveIns();
274 }
275 
276 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
277  MachineBasicBlock &MBB, BitVector &DefOnEntry,
278  BitVector &UndefOnEntry) {
279  unsigned BN = MBB.getNumber();
280  if (DefOnEntry[BN])
281  return true;
282  if (UndefOnEntry[BN])
283  return false;
284 
285  auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
286  for (MachineBasicBlock *S : B.successors())
287  DefOnEntry[S->getNumber()] = true;
288  DefOnEntry[BN] = true;
289  return true;
290  };
291 
292  SetVector<unsigned> WorkList;
293  // Checking if the entry of MBB is reached by some def: add all predecessors
294  // that are potentially defined-on-exit to the work list.
295  for (MachineBasicBlock *P : MBB.predecessors())
296  WorkList.insert(P->getNumber());
297 
298  for (unsigned i = 0; i != WorkList.size(); ++i) {
299  // Determine if the exit from the block is reached by some def.
300  unsigned N = WorkList[i];
302  if (Seen[N]) {
303  const LiveOutPair &LOB = Map[&B];
304  if (LOB.first != nullptr && LOB.first != &UndefVNI)
305  return MarkDefined(B);
306  }
307  SlotIndex Begin, End;
308  std::tie(Begin, End) = Indexes->getMBBRange(&B);
309  // Treat End as not belonging to B.
310  // If LR has a segment S that starts at the next block, i.e. [End, ...),
311  // std::upper_bound will return the segment following S. Instead,
312  // S should be treated as the first segment that does not overlap B.
313  LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
314  End.getPrevSlot());
315  if (UB != LR.begin()) {
316  LiveRange::Segment &Seg = *std::prev(UB);
317  if (Seg.end > Begin) {
318  // There is a segment that overlaps B. If the range is not explicitly
319  // undefined between the end of the segment and the end of the block,
320  // treat the block as defined on exit. If it is, go to the next block
321  // on the work list.
322  if (LR.isUndefIn(Undefs, Seg.end, End))
323  continue;
324  return MarkDefined(B);
325  }
326  }
327 
328  // No segment overlaps with this block. If this block is not defined on
329  // entry, or it undefines the range, do not process its predecessors.
330  if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
331  UndefOnEntry[N] = true;
332  continue;
333  }
334  if (DefOnEntry[N])
335  return MarkDefined(B);
336 
337  // Still don't know: add all predecessors to the work list.
338  for (MachineBasicBlock *P : B.predecessors())
339  WorkList.insert(P->getNumber());
340  }
341 
342  UndefOnEntry[BN] = true;
343  return false;
344 }
345 
346 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
347  SlotIndex Use, unsigned PhysReg,
348  ArrayRef<SlotIndex> Undefs) {
349  unsigned UseMBBNum = UseMBB.getNumber();
350 
351  // Block numbers where LR should be live-in.
352  SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
353 
354  // Remember if we have seen more than one value.
355  bool UniqueVNI = true;
356  VNInfo *TheVNI = nullptr;
357 
358  bool FoundUndef = false;
359 
360  // Using Seen as a visited set, perform a BFS for all reaching defs.
361  for (unsigned i = 0; i != WorkList.size(); ++i) {
362  MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
363 
364 #ifndef NDEBUG
365  if (MBB->pred_empty()) {
366  MBB->getParent()->verify();
367  errs() << "Use of " << PrintReg(PhysReg)
368  << " does not have a corresponding definition on every path:\n";
369  const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
370  if (MI != nullptr)
371  errs() << Use << " " << *MI;
372  report_fatal_error("Use not jointly dominated by defs.");
373  }
374 
376  !MBB->isLiveIn(PhysReg)) {
377  MBB->getParent()->verify();
378  const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
379  errs() << "The register " << PrintReg(PhysReg, TRI)
380  << " needs to be live in to BB#" << MBB->getNumber()
381  << ", but is missing from the live-in list.\n";
382  report_fatal_error("Invalid global physical register");
383  }
384 #endif
385  FoundUndef |= MBB->pred_empty();
386 
387  for (MachineBasicBlock *Pred : MBB->predecessors()) {
388  // Is this a known live-out block?
389  if (Seen.test(Pred->getNumber())) {
390  if (VNInfo *VNI = Map[Pred].first) {
391  if (TheVNI && TheVNI != VNI)
392  UniqueVNI = false;
393  TheVNI = VNI;
394  }
395  continue;
396  }
397 
398  SlotIndex Start, End;
399  std::tie(Start, End) = Indexes->getMBBRange(Pred);
400 
401  // First time we see Pred. Try to determine the live-out value, but set
402  // it as null if Pred is live-through with an unknown value.
403  auto EP = LR.extendInBlock(Undefs, Start, End);
404  VNInfo *VNI = EP.first;
405  FoundUndef |= EP.second;
406  setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
407  if (VNI) {
408  if (TheVNI && TheVNI != VNI)
409  UniqueVNI = false;
410  TheVNI = VNI;
411  }
412  if (VNI || EP.second)
413  continue;
414 
415  // No, we need a live-in value for Pred as well
416  if (Pred != &UseMBB)
417  WorkList.push_back(Pred->getNumber());
418  else
419  // Loopback to UseMBB, so value is really live through.
420  Use = SlotIndex();
421  }
422  }
423 
424  LiveIn.clear();
425  FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
426  if (!Undefs.empty() && FoundUndef)
427  UniqueVNI = false;
428 
429  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
430  // neither require it. Skip the sorting overhead for small updates.
431  if (WorkList.size() > 4)
432  array_pod_sort(WorkList.begin(), WorkList.end());
433 
434  // If a unique reaching def was found, blit in the live ranges immediately.
435  if (UniqueVNI) {
436  assert(TheVNI != nullptr && TheVNI != &UndefVNI);
437  LiveRangeUpdater Updater(&LR);
438  for (unsigned BN : WorkList) {
439  SlotIndex Start, End;
440  std::tie(Start, End) = Indexes->getMBBRange(BN);
441  // Trim the live range in UseMBB.
442  if (BN == UseMBBNum && Use.isValid())
443  End = Use;
444  else
445  Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
446  Updater.add(Start, End, TheVNI);
447  }
448  return true;
449  }
450 
451  // Prepare the defined/undefined bit vectors.
453  bool DidInsert;
454  std::tie(Entry, DidInsert) = EntryInfos.insert(
455  std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
456  if (DidInsert) {
457  // Initialize newly inserted entries.
458  unsigned N = MF->getNumBlockIDs();
459  Entry->second.first.resize(N);
460  Entry->second.second.resize(N);
461  }
462  BitVector &DefOnEntry = Entry->second.first;
463  BitVector &UndefOnEntry = Entry->second.second;
464 
465  // Multiple values were found, so transfer the work list to the LiveIn array
466  // where UpdateSSA will use it as a work list.
467  LiveIn.reserve(WorkList.size());
468  for (unsigned BN : WorkList) {
469  MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
470  if (!Undefs.empty() &&
471  !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
472  continue;
473  addLiveInBlock(LR, DomTree->getNode(MBB));
474  if (MBB == &UseMBB)
475  LiveIn.back().Kill = Use;
476  }
477 
478  return false;
479 }
480 
481 // This is essentially the same iterative algorithm that SSAUpdater uses,
482 // except we already have a dominator tree, so we don't have to recompute it.
483 void LiveRangeCalc::updateSSA() {
484  assert(Indexes && "Missing SlotIndexes");
485  assert(DomTree && "Missing dominator tree");
486 
487  // Interate until convergence.
488  bool Changed;
489  do {
490  Changed = false;
491  // Propagate live-out values down the dominator tree, inserting phi-defs
492  // when necessary.
493  for (LiveInBlock &I : LiveIn) {
494  MachineDomTreeNode *Node = I.DomNode;
495  // Skip block if the live-in value has already been determined.
496  if (!Node)
497  continue;
498  MachineBasicBlock *MBB = Node->getBlock();
499  MachineDomTreeNode *IDom = Node->getIDom();
500  LiveOutPair IDomValue;
501 
502  // We need a live-in value to a block with no immediate dominator?
503  // This is probably an unreachable block that has survived somehow.
504  bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
505 
506  // IDom dominates all of our predecessors, but it may not be their
507  // immediate dominator. Check if any of them have live-out values that are
508  // properly dominated by IDom. If so, we need a phi-def here.
509  if (!needPHI) {
510  IDomValue = Map[IDom->getBlock()];
511 
512  // Cache the DomTree node that defined the value.
513  if (IDomValue.first && IDomValue.first != &UndefVNI &&
514  !IDomValue.second) {
515  Map[IDom->getBlock()].second = IDomValue.second =
516  DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
517  }
518 
519  for (MachineBasicBlock *Pred : MBB->predecessors()) {
520  LiveOutPair &Value = Map[Pred];
521  if (!Value.first || Value.first == IDomValue.first)
522  continue;
523  if (Value.first == &UndefVNI) {
524  needPHI = true;
525  break;
526  }
527 
528  // Cache the DomTree node that defined the value.
529  if (!Value.second)
530  Value.second =
531  DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
532 
533  // This predecessor is carrying something other than IDomValue.
534  // It could be because IDomValue hasn't propagated yet, or it could be
535  // because MBB is in the dominance frontier of that value.
536  if (DomTree->dominates(IDom, Value.second)) {
537  needPHI = true;
538  break;
539  }
540  }
541  }
542 
543  // The value may be live-through even if Kill is set, as can happen when
544  // we are called from extendRange. In that case LiveOutSeen is true, and
545  // LiveOut indicates a foreign or missing value.
546  LiveOutPair &LOP = Map[MBB];
547 
548  // Create a phi-def if required.
549  if (needPHI) {
550  Changed = true;
551  assert(Alloc && "Need VNInfo allocator to create PHI-defs");
552  SlotIndex Start, End;
553  std::tie(Start, End) = Indexes->getMBBRange(MBB);
554  LiveRange &LR = I.LR;
555  VNInfo *VNI = LR.getNextValue(Start, *Alloc);
556  I.Value = VNI;
557  // This block is done, we know the final value.
558  I.DomNode = nullptr;
559 
560  // Add liveness since updateFromLiveIns now skips this node.
561  if (I.Kill.isValid()) {
562  if (VNI)
563  LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
564  } else {
565  if (VNI)
566  LR.addSegment(LiveInterval::Segment(Start, End, VNI));
567  LOP = LiveOutPair(VNI, Node);
568  }
569  } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
570  // No phi-def here. Remember incoming value.
571  I.Value = IDomValue.first;
572 
573  // If the IDomValue is killed in the block, don't propagate through.
574  if (I.Kill.isValid())
575  continue;
576 
577  // Propagate IDomValue if it isn't killed:
578  // MBB is live-out and doesn't define its own value.
579  if (LOP.first == IDomValue.first)
580  continue;
581  Changed = true;
582  LOP = IDomValue;
583  }
584  }
585  } while (Changed);
586 }
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:372
bool empty() const
Definition: LiveInterval.h:370
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:78
void push_back(const T &Elt)
Definition: SmallVector.h:212
A common definition of LaneBitmask for use in TableGen and CodeGen.
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
const unsigned reg
Definition: LiveInterval.h:667
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Mod)
Refines the subranges to support LaneMask.
MachineBasicBlock * getMBB() const
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
void createDeadDefs(LiveRange &LR, unsigned Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
LaneBitmask getMaxLaneMaskForVReg(unsigned Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Segments::iterator iterator
Definition: LiveInterval.h:208
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
Definition: LiveInterval.h:595
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(unsigned Reg) const
bool test(unsigned Idx) const
Definition: BitVector.h:502
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range...
A live range for subregisters.
Definition: LiveInterval.h:645
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
void reserve(size_type N)
Definition: SmallVector.h:380
SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...
Definition: LiveInterval.h:742
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
bool isPHI() const
Definition: MachineInstr.h:826
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
bool isEarlyClobber() const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:367
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
iterator end()
Definition: LiveInterval.h:212
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:723
unsigned SubReg
Reg
All possible values of the reg field in the ModR/M byte.
SlotIndex getInstructionIndex(const MachineInstr &MI) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:414
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:751
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:533
SlotIndexes pass.
Definition: SlotIndexes.h:331
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:255
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments segments
Definition: LiveInterval.h:199
iterator_range< def_iterator > def_operands(unsigned Reg) const
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
NodeT * getBlock() const
#define P(N)
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:424
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:759
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
const TargetRegisterInfo * getTargetRegisterInfo() const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Use)
Attempt to extend a value defined after StartIdx to include Use.
DomTreeNodeBase * getIDom() const
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:887
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:487
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
static const unsigned End
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
constexpr bool all() const
Definition: LaneBitmask.h:54
iterator_range< pred_iterator > predecessors()
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:497
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
unsigned first
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
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
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
VNInfoList valnos
Definition: LiveInterval.h:200
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
Representation of each machine instruction.
Definition: MachineInstr.h:59
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:290
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
createDeadDef - Make sure the range has a value defined at Def.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, LiveRange &LR, const MachineOperand &MO)
iterator begin()
Definition: LiveInterval.h:211
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:854
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:476
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:319
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static VNInfo UndefVNI(0xbad, SlotIndex())
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
IRTranslator LLVM IR MI
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144