LLVM  10.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 
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  *Indexes, TRI);
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();
165  for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
166  // Clear all kill flags. They will be reinserted after register allocation
167  // by LiveIntervals::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.
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, MRI->getTargetRegisterInfo())
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 
375  if (Register::isPhysicalRegister(PhysReg) && !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:373
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:708
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:211
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:598
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:679
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:686
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
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void reserve(size_type N)
Definition: SmallVector.h:369
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:783
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:195
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.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
iterator end()
Definition: LiveInterval.h:215
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:764
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:390
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:792
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:517
SlotIndexes pass.
Definition: SlotIndexes.h:314
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:202
iterator_range< def_iterator > def_operands(unsigned Reg) const
Base class for the actual dominator tree node.
Definition: LiveRangeCalc.h:37
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.
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI)
Refines the subranges to support LaneMask.
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:406
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:1062
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:141
DomTreeNodeBase * getIDom() const
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:935
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:469
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()
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:479
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:837
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:203
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
Representation of each machine instruction.
Definition: MachineInstr.h:64
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)
iterator begin()
Definition: LiveInterval.h:214
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:902
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:458
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:322
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:74
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:416
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
auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1276