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