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/SetVector.h"
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "regalloc"
22 
23 // Reserve an address that indicates a value that is known to be "undef".
24 static VNInfo UndefVNI(0xbad, SlotIndex());
25 
26 void LiveRangeCalc::resetLiveOutMap() {
27  unsigned NumBlocks = MF->getNumBlockIDs();
28  Seen.clear();
29  Seen.resize(NumBlocks);
30  EntryInfos.clear();
31  Map.resize(NumBlocks);
32 }
33 
35  SlotIndexes *SI,
37  VNInfo::Allocator *VNIA) {
38  MF = mf;
39  MRI = &MF->getRegInfo();
40  Indexes = SI;
41  DomTree = MDT;
42  Alloc = VNIA;
43  resetLiveOutMap();
44  LiveIn.clear();
45 }
46 
47 
48 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
49  LiveRange &LR, const MachineOperand &MO) {
50  const MachineInstr &MI = *MO.getParent();
51  SlotIndex DefIdx =
53 
54  // Create the def in LR. This may find an existing def.
55  LR.createDeadDef(DefIdx, Alloc);
56 }
57 
58 void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
59  assert(MRI && Indexes && "call reset() first");
60 
61  // Step 1: Create minimal live segments for every definition of Reg.
62  // Visit all def operands. If the same instruction has multiple defs of Reg,
63  // createDeadDef() will deduplicate.
64  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
65  unsigned Reg = LI.reg;
66  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
67  if (!MO.isDef() && !MO.readsReg())
68  continue;
69 
70  unsigned SubReg = MO.getSubReg();
71  if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
72  LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
73  : MRI->getMaxLaneMaskForVReg(Reg);
74  // If this is the first time we see a subregister def, initialize
75  // subranges by creating a copy of the main range.
76  if (!LI.hasSubRanges() && !LI.empty()) {
77  LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
78  LI.createSubRangeFrom(*Alloc, ClassMask, LI);
79  }
80 
81  LI.refineSubRanges(*Alloc, SubMask,
82  [&MO, this](LiveInterval::SubRange &SR) {
83  if (MO.isDef())
84  createDeadDef(*Indexes, *Alloc, SR, MO);
85  });
86  }
87 
88  // Create the def in the main liverange. We do not have to do this if
89  // subranges are tracked as we recreate the main range later in this case.
90  if (MO.isDef() && !LI.hasSubRanges())
91  createDeadDef(*Indexes, *Alloc, LI, MO);
92  }
93 
94  // We may have created empty live ranges for partially undefined uses, we
95  // can't keep them because we won't find defs in them later.
97 
98  // Step 2: Extend live segments to all uses, constructing SSA form as
99  // necessary.
100  if (LI.hasSubRanges()) {
101  for (LiveInterval::SubRange &S : LI.subranges()) {
102  LiveRangeCalc SubLRC;
103  SubLRC.reset(MF, Indexes, DomTree, Alloc);
104  SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
105  }
106  LI.clear();
108  } else {
109  resetLiveOutMap();
110  extendToUses(LI, Reg, LaneBitmask::getAll());
111  }
112 }
113 
115  // First create dead defs at all defs found in subranges.
116  LiveRange &MainRange = LI;
117  assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
118  "Expect empty main liverange");
119 
120  for (const LiveInterval::SubRange &SR : LI.subranges()) {
121  for (const VNInfo *VNI : SR.valnos) {
122  if (!VNI->isUnused() && !VNI->isPHIDef())
123  MainRange.createDeadDef(VNI->def, *Alloc);
124  }
125  }
126  resetLiveOutMap();
127  extendToUses(MainRange, LI.reg, LaneBitmask::getAll(), &LI);
128 }
129 
131  assert(MRI && Indexes && "call reset() first");
132 
133  // Visit all def operands. If the same instruction has multiple defs of Reg,
134  // LR.createDeadDef() will deduplicate.
135  for (MachineOperand &MO : MRI->def_operands(Reg))
136  createDeadDef(*Indexes, *Alloc, LR, MO);
137 }
138 
139 
140 void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
141  LiveInterval *LI) {
143  if (LI != nullptr)
144  LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
145 
146  // Visit all operands that read Reg. This may include partial defs.
147  bool IsSubRange = !Mask.all();
148  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
149  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
150  // Clear all kill flags. They will be reinserted after register allocation
151  // by LiveIntervalAnalysis::addKillFlags().
152  if (MO.isUse())
153  MO.setIsKill(false);
154  // MO::readsReg returns "true" for subregister defs. This is for keeping
155  // liveness of the entire register (i.e. for the main range of the live
156  // interval). For subranges, definitions of non-overlapping subregisters
157  // do not count as uses.
158  if (!MO.readsReg() || (IsSubRange && MO.isDef()))
159  continue;
160 
161  unsigned SubReg = MO.getSubReg();
162  if (SubReg != 0) {
163  LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
164  if (MO.isDef())
165  SLM = ~SLM;
166  // Ignore uses not reading the current (sub)range.
167  if ((SLM & Mask).none())
168  continue;
169  }
170 
171  // Determine the actual place of the use.
172  const MachineInstr *MI = MO.getParent();
173  unsigned OpNo = (&MO - &MI->getOperand(0));
174  SlotIndex UseIdx;
175  if (MI->isPHI()) {
176  assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
177  // The actual place where a phi operand is used is the end of the pred
178  // MBB. PHI operands are paired: (Reg, PredMBB).
179  UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
180  } else {
181  // Check for early-clobber redefs.
182  bool isEarlyClobber = false;
183  unsigned DefIdx;
184  if (MO.isDef())
185  isEarlyClobber = MO.isEarlyClobber();
186  else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
187  // FIXME: This would be a lot easier if tied early-clobber uses also
188  // had an early-clobber flag.
189  isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
190  }
191  UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
192  }
193 
194  // MI is reading Reg. We may have visited MI before if it happens to be
195  // reading Reg multiple times. That is OK, extend() is idempotent.
196  extend(LR, UseIdx, Reg, Undefs);
197  }
198 }
199 
200 
201 void LiveRangeCalc::updateFromLiveIns() {
202  LiveRangeUpdater Updater;
203  for (const LiveInBlock &I : LiveIn) {
204  if (!I.DomNode)
205  continue;
206  MachineBasicBlock *MBB = I.DomNode->getBlock();
207  assert(I.Value && "No live-in value found");
208  SlotIndex Start, End;
209  std::tie(Start, End) = Indexes->getMBBRange(MBB);
210 
211  if (I.Kill.isValid())
212  // Value is killed inside this block.
213  End = I.Kill;
214  else {
215  // The value is live-through, update LiveOut as well.
216  // Defer the Domtree lookup until it is needed.
217  assert(Seen.test(MBB->getNumber()));
218  Map[MBB] = LiveOutPair(I.Value, nullptr);
219  }
220  Updater.setDest(&I.LR);
221  Updater.add(Start, End, I.Value);
222  }
223  LiveIn.clear();
224 }
225 
226 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
227  ArrayRef<SlotIndex> Undefs) {
228  assert(Use.isValid() && "Invalid SlotIndex");
229  assert(Indexes && "Missing SlotIndexes");
230  assert(DomTree && "Missing dominator tree");
231 
232  MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
233  assert(UseMBB && "No MBB at Use");
234 
235  // Is there a def in the same MBB we can extend?
236  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
237  if (EP.first != nullptr || EP.second)
238  return;
239 
240  // Find the single reaching def, or determine if Use is jointly dominated by
241  // multiple values, and we may need to create even more phi-defs to preserve
242  // VNInfo SSA form. Perform a search for all predecessor blocks where we
243  // know the dominating VNInfo.
244  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
245  return;
246 
247  // When there were multiple different values, we may need new PHIs.
248  calculateValues();
249 }
250 
251 
252 // This function is called by a client after using the low-level API to add
253 // live-out and live-in blocks. The unique value optimization is not
254 // available, SplitEditor::transferValues handles that case directly anyway.
256  assert(Indexes && "Missing SlotIndexes");
257  assert(DomTree && "Missing dominator tree");
258  updateSSA();
259  updateFromLiveIns();
260 }
261 
262 
263 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
264  MachineBasicBlock &MBB, BitVector &DefOnEntry,
265  BitVector &UndefOnEntry) {
266  unsigned BN = MBB.getNumber();
267  if (DefOnEntry[BN])
268  return true;
269  if (UndefOnEntry[BN])
270  return false;
271 
272  auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
273  for (MachineBasicBlock *S : B.successors())
274  DefOnEntry[S->getNumber()] = true;
275  DefOnEntry[BN] = true;
276  return true;
277  };
278 
279  SetVector<unsigned> WorkList;
280  // Checking if the entry of MBB is reached by some def: add all predecessors
281  // that are potentially defined-on-exit to the work list.
282  for (MachineBasicBlock *P : MBB.predecessors())
283  WorkList.insert(P->getNumber());
284 
285  for (unsigned i = 0; i != WorkList.size(); ++i) {
286  // Determine if the exit from the block is reached by some def.
287  unsigned N = WorkList[i];
289  if (Seen[N]) {
290  const LiveOutPair &LOB = Map[&B];
291  if (LOB.first != nullptr && LOB.first != &UndefVNI)
292  return MarkDefined(B);
293  }
294  SlotIndex Begin, End;
295  std::tie(Begin, End) = Indexes->getMBBRange(&B);
296  // Treat End as not belonging to B.
297  // If LR has a segment S that starts at the next block, i.e. [End, ...),
298  // std::upper_bound will return the segment following S. Instead,
299  // S should be treated as the first segment that does not overlap B.
300  LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
301  End.getPrevSlot());
302  if (UB != LR.begin()) {
303  LiveRange::Segment &Seg = *std::prev(UB);
304  if (Seg.end > Begin) {
305  // There is a segment that overlaps B. If the range is not explicitly
306  // undefined between the end of the segment and the end of the block,
307  // treat the block as defined on exit. If it is, go to the next block
308  // on the work list.
309  if (LR.isUndefIn(Undefs, Seg.end, End))
310  continue;
311  return MarkDefined(B);
312  }
313  }
314 
315  // No segment overlaps with this block. If this block is not defined on
316  // entry, or it undefines the range, do not process its predecessors.
317  if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
318  UndefOnEntry[N] = true;
319  continue;
320  }
321  if (DefOnEntry[N])
322  return MarkDefined(B);
323 
324  // Still don't know: add all predecessors to the work list.
325  for (MachineBasicBlock *P : B.predecessors())
326  WorkList.insert(P->getNumber());
327  }
328 
329  UndefOnEntry[BN] = true;
330  return false;
331 }
332 
333 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
334  SlotIndex Use, unsigned PhysReg,
335  ArrayRef<SlotIndex> Undefs) {
336  unsigned UseMBBNum = UseMBB.getNumber();
337 
338  // Block numbers where LR should be live-in.
339  SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
340 
341  // Remember if we have seen more than one value.
342  bool UniqueVNI = true;
343  VNInfo *TheVNI = nullptr;
344 
345  bool FoundUndef = false;
346 
347  // Using Seen as a visited set, perform a BFS for all reaching defs.
348  for (unsigned i = 0; i != WorkList.size(); ++i) {
349  MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
350 
351 #ifndef NDEBUG
352  if (MBB->pred_empty()) {
353  MBB->getParent()->verify();
354  errs() << "Use of " << PrintReg(PhysReg)
355  << " does not have a corresponding definition on every path:\n";
356  const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
357  if (MI != nullptr)
358  errs() << Use << " " << *MI;
359  report_fatal_error("Use not jointly dominated by defs.");
360  }
361 
363  !MBB->isLiveIn(PhysReg)) {
364  MBB->getParent()->verify();
365  const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
366  errs() << "The register " << PrintReg(PhysReg, TRI)
367  << " needs to be live in to BB#" << MBB->getNumber()
368  << ", but is missing from the live-in list.\n";
369  report_fatal_error("Invalid global physical register");
370  }
371 #endif
372  FoundUndef |= MBB->pred_empty();
373 
374  for (MachineBasicBlock *Pred : MBB->predecessors()) {
375  // Is this a known live-out block?
376  if (Seen.test(Pred->getNumber())) {
377  if (VNInfo *VNI = Map[Pred].first) {
378  if (TheVNI && TheVNI != VNI)
379  UniqueVNI = false;
380  TheVNI = VNI;
381  }
382  continue;
383  }
384 
385  SlotIndex Start, End;
386  std::tie(Start, End) = Indexes->getMBBRange(Pred);
387 
388  // First time we see Pred. Try to determine the live-out value, but set
389  // it as null if Pred is live-through with an unknown value.
390  auto EP = LR.extendInBlock(Undefs, Start, End);
391  VNInfo *VNI = EP.first;
392  FoundUndef |= EP.second;
393  setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
394  if (VNI) {
395  if (TheVNI && TheVNI != VNI)
396  UniqueVNI = false;
397  TheVNI = VNI;
398  }
399  if (VNI || EP.second)
400  continue;
401 
402  // No, we need a live-in value for Pred as well
403  if (Pred != &UseMBB)
404  WorkList.push_back(Pred->getNumber());
405  else
406  // Loopback to UseMBB, so value is really live through.
407  Use = SlotIndex();
408  }
409  }
410 
411  LiveIn.clear();
412  FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
413  if (Undefs.size() > 0 && FoundUndef)
414  UniqueVNI = false;
415 
416  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
417  // neither require it. Skip the sorting overhead for small updates.
418  if (WorkList.size() > 4)
419  array_pod_sort(WorkList.begin(), WorkList.end());
420 
421  // If a unique reaching def was found, blit in the live ranges immediately.
422  if (UniqueVNI) {
423  assert(TheVNI != nullptr && TheVNI != &UndefVNI);
424  LiveRangeUpdater Updater(&LR);
425  for (unsigned BN : WorkList) {
426  SlotIndex Start, End;
427  std::tie(Start, End) = Indexes->getMBBRange(BN);
428  // Trim the live range in UseMBB.
429  if (BN == UseMBBNum && Use.isValid())
430  End = Use;
431  else
432  Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
433  Updater.add(Start, End, TheVNI);
434  }
435  return true;
436  }
437 
438  // Prepare the defined/undefined bit vectors.
440  bool DidInsert;
441  std::tie(Entry, DidInsert) = EntryInfos.insert(
442  std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
443  if (DidInsert) {
444  // Initialize newly inserted entries.
445  unsigned N = MF->getNumBlockIDs();
446  Entry->second.first.resize(N);
447  Entry->second.second.resize(N);
448  }
449  BitVector &DefOnEntry = Entry->second.first;
450  BitVector &UndefOnEntry = Entry->second.second;
451 
452  // Multiple values were found, so transfer the work list to the LiveIn array
453  // where UpdateSSA will use it as a work list.
454  LiveIn.reserve(WorkList.size());
455  for (unsigned BN : WorkList) {
456  MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
457  if (Undefs.size() > 0 &&
458  !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
459  continue;
460  addLiveInBlock(LR, DomTree->getNode(MBB));
461  if (MBB == &UseMBB)
462  LiveIn.back().Kill = Use;
463  }
464 
465  return false;
466 }
467 
468 
469 // This is essentially the same iterative algorithm that SSAUpdater uses,
470 // except we already have a dominator tree, so we don't have to recompute it.
471 void LiveRangeCalc::updateSSA() {
472  assert(Indexes && "Missing SlotIndexes");
473  assert(DomTree && "Missing dominator tree");
474 
475  // Interate until convergence.
476  bool Changed;
477  do {
478  Changed = false;
479  // Propagate live-out values down the dominator tree, inserting phi-defs
480  // when necessary.
481  for (LiveInBlock &I : LiveIn) {
482  MachineDomTreeNode *Node = I.DomNode;
483  // Skip block if the live-in value has already been determined.
484  if (!Node)
485  continue;
486  MachineBasicBlock *MBB = Node->getBlock();
487  MachineDomTreeNode *IDom = Node->getIDom();
488  LiveOutPair IDomValue;
489 
490  // We need a live-in value to a block with no immediate dominator?
491  // This is probably an unreachable block that has survived somehow.
492  bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
493 
494  // IDom dominates all of our predecessors, but it may not be their
495  // immediate dominator. Check if any of them have live-out values that are
496  // properly dominated by IDom. If so, we need a phi-def here.
497  if (!needPHI) {
498  IDomValue = Map[IDom->getBlock()];
499 
500  // Cache the DomTree node that defined the value.
501  if (IDomValue.first && IDomValue.first != &UndefVNI &&
502  !IDomValue.second) {
503  Map[IDom->getBlock()].second = IDomValue.second =
504  DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
505  }
506 
507  for (MachineBasicBlock *Pred : MBB->predecessors()) {
508  LiveOutPair &Value = Map[Pred];
509  if (!Value.first || Value.first == IDomValue.first)
510  continue;
511  if (Value.first == &UndefVNI) {
512  needPHI = true;
513  break;
514  }
515 
516  // Cache the DomTree node that defined the value.
517  if (!Value.second)
518  Value.second =
519  DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
520 
521  // This predecessor is carrying something other than IDomValue.
522  // It could be because IDomValue hasn't propagated yet, or it could be
523  // because MBB is in the dominance frontier of that value.
524  if (DomTree->dominates(IDom, Value.second)) {
525  needPHI = true;
526  break;
527  }
528  }
529  }
530 
531  // The value may be live-through even if Kill is set, as can happen when
532  // we are called from extendRange. In that case LiveOutSeen is true, and
533  // LiveOut indicates a foreign or missing value.
534  LiveOutPair &LOP = Map[MBB];
535 
536  // Create a phi-def if required.
537  if (needPHI) {
538  Changed = true;
539  assert(Alloc && "Need VNInfo allocator to create PHI-defs");
540  SlotIndex Start, End;
541  std::tie(Start, End) = Indexes->getMBBRange(MBB);
542  LiveRange &LR = I.LR;
543  VNInfo *VNI = LR.getNextValue(Start, *Alloc);
544  I.Value = VNI;
545  // This block is done, we know the final value.
546  I.DomNode = nullptr;
547 
548  // Add liveness since updateFromLiveIns now skips this node.
549  if (I.Kill.isValid()) {
550  if (VNI)
551  LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
552  } else {
553  if (VNI)
554  LR.addSegment(LiveInterval::Segment(Start, End, VNI));
555  LOP = LiveOutPair(VNI, Node);
556  }
557  } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
558  // No phi-def here. Remember incoming value.
559  I.Value = IDomValue.first;
560 
561  // If the IDomValue is killed in the block, don't propagate through.
562  if (I.Kill.isValid())
563  continue;
564 
565  // Propagate IDomValue if it isn't killed:
566  // MBB is live-out and doesn't define its own value.
567  if (LOP.first == IDomValue.first)
568  continue;
569  Changed = true;
570  LOP = IDomValue;
571  }
572  }
573  } while (Changed);
574 }
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
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:103
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:77
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:792
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:176
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.
void reset(const MachineFunction *MF, SlotIndexes *, MachineDominatorTree *, VNInfo::Allocator *)
reset - Prepare caches for a new set of non-overlapping live ranges.
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:771
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
const TargetRegisterInfo * getTargetRegisterInfo() const
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.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
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
#define B
Definition: LargeTest.cpp:24
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
const size_t N
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
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:284
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...