LLVM  13.0.0git
SplitKit.cpp
Go to the documentation of this file.
1 //===- SplitKit.cpp - Toolkit for splitting 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 // This file contains the SplitAnalysis class as well as mutator functions for
10 // live range splitting.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "SplitKit.h"
15 #include "llvm/ADT/None.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Config/llvm-config.h"
33 #include "llvm/IR/DebugLoc.h"
34 #include "llvm/Support/Allocator.h"
36 #include "llvm/Support/Debug.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <iterator>
42 #include <limits>
43 #include <tuple>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "regalloc"
48 
49 STATISTIC(NumFinished, "Number of splits finished");
50 STATISTIC(NumSimple, "Number of splits that were simple");
51 STATISTIC(NumCopies, "Number of copies inserted for splitting");
52 STATISTIC(NumRemats, "Number of rematerialized defs for splitting");
53 STATISTIC(NumRepairs, "Number of invalid live ranges repaired");
54 
55 //===----------------------------------------------------------------------===//
56 // Last Insert Point Analysis
57 //===----------------------------------------------------------------------===//
58 
60  unsigned BBNum)
61  : LIS(lis), LastInsertPoint(BBNum) {}
62 
64 InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
65  const MachineBasicBlock &MBB) {
66  unsigned Num = MBB.getNumber();
67  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
68  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
69 
70  SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors;
71  bool EHPadSuccessor = false;
72  for (const MachineBasicBlock *SMBB : MBB.successors()) {
73  if (SMBB->isEHPad()) {
74  ExceptionalSuccessors.push_back(SMBB);
75  EHPadSuccessor = true;
76  } else if (SMBB->isInlineAsmBrIndirectTarget())
77  ExceptionalSuccessors.push_back(SMBB);
78  }
79 
80  // Compute insert points on the first call. The pair is independent of the
81  // current live interval.
82  if (!LIP.first.isValid()) {
84  if (FirstTerm == MBB.end())
85  LIP.first = MBBEnd;
86  else
87  LIP.first = LIS.getInstructionIndex(*FirstTerm);
88 
89  // If there is a landing pad or inlineasm_br successor, also find the
90  // instruction. If there is no such instruction, we don't need to do
91  // anything special. We assume there cannot be multiple instructions that
92  // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we
93  // assume that if there are any, they will be after any other call
94  // instructions in the block.
95  if (ExceptionalSuccessors.empty())
96  return LIP.first;
97  for (const MachineInstr &MI : llvm::reverse(MBB)) {
98  if ((EHPadSuccessor && MI.isCall()) ||
99  MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
100  LIP.second = LIS.getInstructionIndex(MI);
101  break;
102  }
103  }
104  }
105 
106  // If CurLI is live into a landing pad successor, move the last insert point
107  // back to the call that may throw.
108  if (!LIP.second)
109  return LIP.first;
110 
111  if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) {
112  return LIS.isLiveInToMBB(CurLI, EHPad);
113  }))
114  return LIP.first;
115 
116  // Find the value leaving MBB.
117  const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
118  if (!VNI)
119  return LIP.first;
120 
121  // If the value leaving MBB was defined after the call in MBB, it can't
122  // really be live-in to the landing pad. This can happen if the landing pad
123  // has a PHI, and this register is undef on the exceptional edge.
124  // <rdar://problem/10664933>
125  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
126  return LIP.first;
127 
128  // Value is properly live-in to the landing pad.
129  // Only allow inserts before the call.
130  return LIP.second;
131 }
132 
136  SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
137  if (LIP == LIS.getMBBEndIdx(&MBB))
138  return MBB.end();
139  return LIS.getInstructionFromIndex(LIP);
140 }
141 
142 //===----------------------------------------------------------------------===//
143 // Split Analysis
144 //===----------------------------------------------------------------------===//
145 
147  const MachineLoopInfo &mli)
148  : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
149  TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
150 
152  UseSlots.clear();
153  UseBlocks.clear();
154  ThroughBlocks.clear();
155  CurLI = nullptr;
156  DidRepairRange = false;
157 }
158 
159 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
160 void SplitAnalysis::analyzeUses() {
161  assert(UseSlots.empty() && "Call clear first");
162 
163  // First get all the defs from the interval values. This provides the correct
164  // slots for early clobbers.
165  for (const VNInfo *VNI : CurLI->valnos)
166  if (!VNI->isPHIDef() && !VNI->isUnused())
167  UseSlots.push_back(VNI->def);
168 
169  // Get use slots form the use-def chain.
171  for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg()))
172  if (!MO.isUndef())
173  UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
174 
175  array_pod_sort(UseSlots.begin(), UseSlots.end());
176 
177  // Remove duplicates, keeping the smaller slot for each instruction.
178  // That is what we want for early clobbers.
179  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
181  UseSlots.end());
182 
183  // Compute per-live block info.
184  if (!calcLiveBlockInfo()) {
185  // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
186  // I am looking at you, RegisterCoalescer!
187  DidRepairRange = true;
188  ++NumRepairs;
189  LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
190  const_cast<LiveIntervals&>(LIS)
191  .shrinkToUses(const_cast<LiveInterval*>(CurLI));
192  UseBlocks.clear();
193  ThroughBlocks.clear();
194  bool fixed = calcLiveBlockInfo();
195  (void)fixed;
196  assert(fixed && "Couldn't fix broken live interval");
197  }
198 
199  LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "
200  << UseBlocks.size() << " blocks, through "
201  << NumThroughBlocks << " blocks.\n");
202 }
203 
204 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
205 /// where CurLI is live.
206 bool SplitAnalysis::calcLiveBlockInfo() {
207  ThroughBlocks.resize(MF.getNumBlockIDs());
208  NumThroughBlocks = NumGapBlocks = 0;
209  if (CurLI->empty())
210  return true;
211 
212  LiveInterval::const_iterator LVI = CurLI->begin();
213  LiveInterval::const_iterator LVE = CurLI->end();
214 
216  UseI = UseSlots.begin();
217  UseE = UseSlots.end();
218 
219  // Loop over basic blocks where CurLI is live.
221  LIS.getMBBFromIndex(LVI->start)->getIterator();
222  while (true) {
223  BlockInfo BI;
224  BI.MBB = &*MFI;
225  SlotIndex Start, Stop;
226  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
227 
228  // If the block contains no uses, the range must be live through. At one
229  // point, RegisterCoalescer could create dangling ranges that ended
230  // mid-block.
231  if (UseI == UseE || *UseI >= Stop) {
232  ++NumThroughBlocks;
233  ThroughBlocks.set(BI.MBB->getNumber());
234  // The range shouldn't end mid-block if there are no uses. This shouldn't
235  // happen.
236  if (LVI->end < Stop)
237  return false;
238  } else {
239  // This block has uses. Find the first and last uses in the block.
240  BI.FirstInstr = *UseI;
241  assert(BI.FirstInstr >= Start);
242  do ++UseI;
243  while (UseI != UseE && *UseI < Stop);
244  BI.LastInstr = UseI[-1];
245  assert(BI.LastInstr < Stop);
246 
247  // LVI is the first live segment overlapping MBB.
248  BI.LiveIn = LVI->start <= Start;
249 
250  // When not live in, the first use should be a def.
251  if (!BI.LiveIn) {
252  assert(LVI->start == LVI->valno->def && "Dangling Segment start");
253  assert(LVI->start == BI.FirstInstr && "First instr should be a def");
254  BI.FirstDef = BI.FirstInstr;
255  }
256 
257  // Look for gaps in the live range.
258  BI.LiveOut = true;
259  while (LVI->end < Stop) {
260  SlotIndex LastStop = LVI->end;
261  if (++LVI == LVE || LVI->start >= Stop) {
262  BI.LiveOut = false;
263  BI.LastInstr = LastStop;
264  break;
265  }
266 
267  if (LastStop < LVI->start) {
268  // There is a gap in the live range. Create duplicate entries for the
269  // live-in snippet and the live-out snippet.
270  ++NumGapBlocks;
271 
272  // Push the Live-in part.
273  BI.LiveOut = false;
274  UseBlocks.push_back(BI);
275  UseBlocks.back().LastInstr = LastStop;
276 
277  // Set up BI for the live-out part.
278  BI.LiveIn = false;
279  BI.LiveOut = true;
280  BI.FirstInstr = BI.FirstDef = LVI->start;
281  }
282 
283  // A Segment that starts in the middle of the block must be a def.
284  assert(LVI->start == LVI->valno->def && "Dangling Segment start");
285  if (!BI.FirstDef)
286  BI.FirstDef = LVI->start;
287  }
288 
289  UseBlocks.push_back(BI);
290 
291  // LVI is now at LVE or LVI->end >= Stop.
292  if (LVI == LVE)
293  break;
294  }
295 
296  // Live segment ends exactly at Stop. Move to the next segment.
297  if (LVI->end == Stop && ++LVI == LVE)
298  break;
299 
300  // Pick the next basic block.
301  if (LVI->start < Stop)
302  ++MFI;
303  else
304  MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
305  }
306 
307  assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
308  return true;
309 }
310 
311 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
312  if (cli->empty())
313  return 0;
314  LiveInterval *li = const_cast<LiveInterval*>(cli);
315  LiveInterval::iterator LVI = li->begin();
316  LiveInterval::iterator LVE = li->end();
317  unsigned Count = 0;
318 
319  // Loop over basic blocks where li is live.
321  LIS.getMBBFromIndex(LVI->start)->getIterator();
322  SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
323  while (true) {
324  ++Count;
325  LVI = li->advanceTo(LVI, Stop);
326  if (LVI == LVE)
327  return Count;
328  do {
329  ++MFI;
330  Stop = LIS.getMBBEndIdx(&*MFI);
331  } while (Stop <= LVI->start);
332  }
333 }
334 
336  unsigned OrigReg = VRM.getOriginal(CurLI->reg());
337  const LiveInterval &Orig = LIS.getInterval(OrigReg);
338  assert(!Orig.empty() && "Splitting empty interval?");
339  LiveInterval::const_iterator I = Orig.find(Idx);
340 
341  // Range containing Idx should begin at Idx.
342  if (I != Orig.end() && I->start <= Idx)
343  return I->start == Idx;
344 
345  // Range does not contain Idx, previous must end at Idx.
346  return I != Orig.begin() && (--I)->end == Idx;
347 }
348 
350  clear();
351  CurLI = li;
352  analyzeUses();
353 }
354 
355 //===----------------------------------------------------------------------===//
356 // Split Editor
357 //===----------------------------------------------------------------------===//
358 
359 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
361  LiveIntervals &LIS, VirtRegMap &VRM,
364  : SA(SA), AA(AA), LIS(LIS), VRM(VRM),
365  MRI(VRM.getMachineFunction().getRegInfo()), MDT(MDT),
366  TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()),
367  TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()),
368  MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {}
369 
371  Edit = &LRE;
372  SpillMode = SM;
373  OpenIdx = 0;
374  RegAssign.clear();
375  Values.clear();
376 
377  // Reset the LiveIntervalCalc instances needed for this spill mode.
378  LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
379  &LIS.getVNInfoAllocator());
380  if (SpillMode)
381  LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
382  &LIS.getVNInfoAllocator());
383 
384  // We don't need an AliasAnalysis since we will only be performing
385  // cheap-as-a-copy remats anyway.
386  Edit->anyRematerializable(nullptr);
387 }
388 
389 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
391  if (RegAssign.empty()) {
392  dbgs() << " empty\n";
393  return;
394  }
395 
396  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
397  dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
398  dbgs() << '\n';
399 }
400 #endif
401 
402 LiveInterval::SubRange &SplitEditor::getSubRangeForMaskExact(LaneBitmask LM,
403  LiveInterval &LI) {
404  for (LiveInterval::SubRange &S : LI.subranges())
405  if (S.LaneMask == LM)
406  return S;
407  llvm_unreachable("SubRange for this mask not found");
408 }
409 
410 LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
411  LiveInterval &LI) {
412  for (LiveInterval::SubRange &S : LI.subranges())
413  if ((S.LaneMask & LM) == LM)
414  return S;
415  llvm_unreachable("SubRange for this mask not found");
416 }
417 
418 void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
419  if (!LI.hasSubRanges()) {
420  LI.createDeadDef(VNI);
421  return;
422  }
423 
424  SlotIndex Def = VNI->def;
425  if (Original) {
426  // If we are transferring a def from the original interval, make sure
427  // to only update the subranges for which the original subranges had
428  // a def at this location.
429  for (LiveInterval::SubRange &S : LI.subranges()) {
430  auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
431  VNInfo *PV = PS.getVNInfoAt(Def);
432  if (PV != nullptr && PV->def == Def)
433  S.createDeadDef(Def, LIS.getVNInfoAllocator());
434  }
435  } else {
436  // This is a new def: either from rematerialization, or from an inserted
437  // copy. Since rematerialization can regenerate a definition of a sub-
438  // register, we need to check which subranges need to be updated.
440  assert(DefMI != nullptr);
441  LaneBitmask LM;
442  for (const MachineOperand &DefOp : DefMI->defs()) {
443  Register R = DefOp.getReg();
444  if (R != LI.reg())
445  continue;
446  if (unsigned SR = DefOp.getSubReg())
447  LM |= TRI.getSubRegIndexLaneMask(SR);
448  else {
449  LM = MRI.getMaxLaneMaskForVReg(R);
450  break;
451  }
452  }
453  for (LiveInterval::SubRange &S : LI.subranges())
454  if ((S.LaneMask & LM).any())
455  S.createDeadDef(Def, LIS.getVNInfoAllocator());
456  }
457 }
458 
459 VNInfo *SplitEditor::defValue(unsigned RegIdx,
460  const VNInfo *ParentVNI,
461  SlotIndex Idx,
462  bool Original) {
463  assert(ParentVNI && "Mapping NULL value");
464  assert(Idx.isValid() && "Invalid SlotIndex");
465  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
466  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
467 
468  // Create a new value.
469  VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
470 
471  bool Force = LI->hasSubRanges();
472  ValueForcePair FP(Force ? nullptr : VNI, Force);
473  // Use insert for lookup, so we can add missing values with a second lookup.
474  std::pair<ValueMap::iterator, bool> InsP =
475  Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
476 
477  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
478  // forced. Keep it as a simple def without any liveness.
479  if (!Force && InsP.second)
480  return VNI;
481 
482  // If the previous value was a simple mapping, add liveness for it now.
483  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
484  addDeadDef(*LI, OldVNI, Original);
485 
486  // No longer a simple mapping. Switch to a complex mapping. If the
487  // interval has subranges, make it a forced mapping.
488  InsP.first->second = ValueForcePair(nullptr, Force);
489  }
490 
491  // This is a complex mapping, add liveness for VNI
492  addDeadDef(*LI, VNI, Original);
493  return VNI;
494 }
495 
496 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
497  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
498  VNInfo *VNI = VFP.getPointer();
499 
500  // ParentVNI was either unmapped or already complex mapped. Either way, just
501  // set the force bit.
502  if (!VNI) {
503  VFP.setInt(true);
504  return;
505  }
506 
507  // This was previously a single mapping. Make sure the old def is represented
508  // by a trivial live range.
509  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
510 
511  // Mark as complex mapped, forced.
512  VFP = ValueForcePair(nullptr, true);
513 }
514 
515 SlotIndex SplitEditor::buildSingleSubRegCopy(Register FromReg, Register ToReg,
517  unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
518  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
519  bool FirstCopy = !Def.isValid();
520  MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
521  .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
522  | getInternalReadRegState(!FirstCopy), SubIdx)
523  .addReg(FromReg, 0, SubIdx);
524 
525  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
526  SlotIndexes &Indexes = *LIS.getSlotIndexes();
527  if (FirstCopy) {
528  Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
529  } else {
530  CopyMI->bundleWithPred();
531  }
532  LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
533  DestLI.refineSubRanges(Allocator, LaneMask,
534  [Def, &Allocator](LiveInterval::SubRange &SR) {
535  SR.createDeadDef(Def, Allocator);
536  },
537  Indexes, TRI);
538  return Def;
539 }
540 
541 SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg,
542  LaneBitmask LaneMask, MachineBasicBlock &MBB,
543  MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
544  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
545  if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {
546  // The full vreg is copied.
547  MachineInstr *CopyMI =
548  BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
549  SlotIndexes &Indexes = *LIS.getSlotIndexes();
550  return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
551  }
552 
553  // Only a subset of lanes needs to be copied. The following is a simple
554  // heuristic to construct a sequence of COPYs. We could add a target
555  // specific callback if this turns out to be suboptimal.
556  LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
557 
558  // First pass: Try to find a perfectly matching subregister index. If none
559  // exists find the one covering the most lanemask bits.
560  const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
561  assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
562 
563  SmallVector<unsigned, 8> Indexes;
564 
565  // Abort if we cannot possibly implement the COPY with the given indexes.
566  if (!TRI.getCoveringSubRegIndexes(MRI, RC, LaneMask, Indexes))
567  report_fatal_error("Impossible to implement partial COPY");
568 
569  SlotIndex Def;
570  for (unsigned BestIdx : Indexes) {
571  Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
572  DestLI, Late, Def);
573  }
574 
575  return Def;
576 }
577 
578 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
579  VNInfo *ParentVNI,
580  SlotIndex UseIdx,
583  SlotIndex Def;
584  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
585 
586  // We may be trying to avoid interference that ends at a deleted instruction,
587  // so always begin RegIdx 0 early and all others late.
588  bool Late = RegIdx != 0;
589 
590  // Attempt cheap-as-a-copy rematerialization.
591  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
592  LiveInterval &OrigLI = LIS.getInterval(Original);
593  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
594 
595  Register Reg = LI->reg();
596  bool DidRemat = false;
597  if (OrigVNI) {
598  LiveRangeEdit::Remat RM(ParentVNI);
599  RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
600  if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
601  Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
602  ++NumRemats;
603  DidRemat = true;
604  }
605  }
606  if (!DidRemat) {
607  LaneBitmask LaneMask;
608  if (OrigLI.hasSubRanges()) {
609  LaneMask = LaneBitmask::getNone();
610  for (LiveInterval::SubRange &S : OrigLI.subranges()) {
611  if (S.liveAt(UseIdx))
612  LaneMask |= S.LaneMask;
613  }
614  } else {
615  LaneMask = LaneBitmask::getAll();
616  }
617 
618  if (LaneMask.none()) {
619  const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF);
620  MachineInstr *ImplicitDef = BuildMI(MBB, I, DebugLoc(), Desc, Reg);
621  SlotIndexes &Indexes = *LIS.getSlotIndexes();
622  Def = Indexes.insertMachineInstrInMaps(*ImplicitDef, Late).getRegSlot();
623  } else {
624  ++NumCopies;
625  Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
626  }
627  }
628 
629  // Define the value in Reg.
630  return defValue(RegIdx, ParentVNI, Def, false);
631 }
632 
633 /// Create a new virtual register and live interval.
635  // Create the complement as index 0.
636  if (Edit->empty())
637  Edit->createEmptyInterval();
638 
639  // Create the open interval.
640  OpenIdx = Edit->size();
641  Edit->createEmptyInterval();
642  return OpenIdx;
643 }
644 
645 void SplitEditor::selectIntv(unsigned Idx) {
646  assert(Idx != 0 && "Cannot select the complement interval");
647  assert(Idx < Edit->size() && "Can only select previously opened interval");
648  LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n');
649  OpenIdx = Idx;
650 }
651 
653  assert(OpenIdx && "openIntv not called before enterIntvBefore");
654  LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx);
655  Idx = Idx.getBaseIndex();
656  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
657  if (!ParentVNI) {
658  LLVM_DEBUG(dbgs() << ": not live\n");
659  return Idx;
660  }
661  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
663  assert(MI && "enterIntvBefore called with invalid index");
664 
665  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
666  return VNI->def;
667 }
668 
670  assert(OpenIdx && "openIntv not called before enterIntvAfter");
671  LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx);
672  Idx = Idx.getBoundaryIndex();
673  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
674  if (!ParentVNI) {
675  LLVM_DEBUG(dbgs() << ": not live\n");
676  return Idx;
677  }
678  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
680  assert(MI && "enterIntvAfter called with invalid index");
681 
682  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
683  std::next(MachineBasicBlock::iterator(MI)));
684  return VNI->def;
685 }
686 
688  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
689  SlotIndex End = LIS.getMBBEndIdx(&MBB);
690  SlotIndex Last = End.getPrevSlot();
691  LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "
692  << Last);
693  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
694  if (!ParentVNI) {
695  LLVM_DEBUG(dbgs() << ": not live\n");
696  return End;
697  }
698  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);
699  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
701  RegAssign.insert(VNI->def, End, OpenIdx);
702  LLVM_DEBUG(dump());
703  return VNI->def;
704 }
705 
706 /// useIntv - indicate that all instructions in MBB should use OpenLI.
708  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
709 }
710 
712  assert(OpenIdx && "openIntv not called before useIntv");
713  LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
714  RegAssign.insert(Start, End, OpenIdx);
715  LLVM_DEBUG(dump());
716 }
717 
719  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
720  LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx);
721 
722  // The interval must be live beyond the instruction at Idx.
723  SlotIndex Boundary = Idx.getBoundaryIndex();
724  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
725  if (!ParentVNI) {
726  LLVM_DEBUG(dbgs() << ": not live\n");
727  return Boundary.getNextSlot();
728  }
729  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
730  MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
731  assert(MI && "No instruction at index");
732 
733  // In spill mode, make live ranges as short as possible by inserting the copy
734  // before MI. This is only possible if that instruction doesn't redefine the
735  // value. The inserted COPY is not a kill, and we don't need to recompute
736  // the source live range. The spiller also won't try to hoist this copy.
737  if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
738  MI->readsVirtualRegister(Edit->getReg())) {
739  forceRecompute(0, *ParentVNI);
740  defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
741  return Idx;
742  }
743 
744  VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
745  std::next(MachineBasicBlock::iterator(MI)));
746  return VNI->def;
747 }
748 
750  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
751  LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx);
752 
753  // The interval must be live into the instruction at Idx.
754  Idx = Idx.getBaseIndex();
755  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
756  if (!ParentVNI) {
757  LLVM_DEBUG(dbgs() << ": not live\n");
758  return Idx.getNextSlot();
759  }
760  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
761 
763  assert(MI && "No instruction at index");
764  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
765  return VNI->def;
766 }
767 
769  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
770  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
771  LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "
772  << Start);
773 
774  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
775  if (!ParentVNI) {
776  LLVM_DEBUG(dbgs() << ": not live\n");
777  return Start;
778  }
779 
780  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
782  RegAssign.insert(Start, VNI->def, OpenIdx);
783  LLVM_DEBUG(dump());
784  return VNI->def;
785 }
786 
788  assert(OpenIdx && "openIntv not called before overlapIntv");
789  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
790  assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
791  "Parent changes value in extended range");
792  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
793  "Range cannot span basic blocks");
794 
795  // The complement interval will be extended as needed by LICalc.extend().
796  if (ParentVNI)
797  forceRecompute(0, *ParentVNI);
798  LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
799  RegAssign.insert(Start, End, OpenIdx);
800  LLVM_DEBUG(dump());
801 }
802 
803 //===----------------------------------------------------------------------===//
804 // Spill modes
805 //===----------------------------------------------------------------------===//
806 
807 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
808  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
809  LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
810  RegAssignMap::iterator AssignI;
811  AssignI.setMap(RegAssign);
812 
813  for (const VNInfo *C : Copies) {
814  SlotIndex Def = C->def;
816  assert(MI && "No instruction for back-copy");
817 
818  MachineBasicBlock *MBB = MI->getParent();
820  bool AtBegin;
821  do AtBegin = MBBI == MBB->begin();
822  while (!AtBegin && (--MBBI)->isDebugInstr());
823 
824  LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
825  LIS.removeVRegDefAt(*LI, Def);
827  MI->eraseFromParent();
828 
829  // Adjust RegAssign if a register assignment is killed at Def. We want to
830  // avoid calculating the live range of the source register if possible.
831  AssignI.find(Def.getPrevSlot());
832  if (!AssignI.valid() || AssignI.start() >= Def)
833  continue;
834  // If MI doesn't kill the assigned register, just leave it.
835  if (AssignI.stop() != Def)
836  continue;
837  unsigned RegIdx = AssignI.value();
838  if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
839  LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx
840  << '\n');
841  forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
842  } else {
844  LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI);
845  AssignI.setStop(Kill);
846  }
847  }
848 }
849 
851 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
852  MachineBasicBlock *DefMBB) {
853  if (MBB == DefMBB)
854  return MBB;
855  assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
856 
857  const MachineLoopInfo &Loops = SA.Loops;
858  const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
859  MachineDomTreeNode *DefDomNode = MDT[DefMBB];
860 
861  // Best candidate so far.
862  MachineBasicBlock *BestMBB = MBB;
863  unsigned BestDepth = std::numeric_limits<unsigned>::max();
864 
865  while (true) {
866  const MachineLoop *Loop = Loops.getLoopFor(MBB);
867 
868  // MBB isn't in a loop, it doesn't get any better. All dominators have a
869  // higher frequency by definition.
870  if (!Loop) {
871  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
872  << " dominates " << printMBBReference(*MBB)
873  << " at depth 0\n");
874  return MBB;
875  }
876 
877  // We'll never be able to exit the DefLoop.
878  if (Loop == DefLoop) {
879  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
880  << " dominates " << printMBBReference(*MBB)
881  << " in the same loop\n");
882  return MBB;
883  }
884 
885  // Least busy dominator seen so far.
886  unsigned Depth = Loop->getLoopDepth();
887  if (Depth < BestDepth) {
888  BestMBB = MBB;
889  BestDepth = Depth;
890  LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
891  << " dominates " << printMBBReference(*MBB)
892  << " at depth " << Depth << '\n');
893  }
894 
895  // Leave loop by going to the immediate dominator of the loop header.
896  // This is a bigger stride than simply walking up the dominator tree.
897  MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
898 
899  // Too far up the dominator tree?
900  if (!IDom || !MDT.dominates(DefDomNode, IDom))
901  return BestMBB;
902 
903  MBB = IDom->getBlock();
904  }
905 }
906 
907 void SplitEditor::computeRedundantBackCopies(
908  DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
909  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
910  LiveInterval *Parent = &Edit->getParent();
911  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
912  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
913 
914  // Aggregate VNIs having the same value as ParentVNI.
915  for (VNInfo *VNI : LI->valnos) {
916  if (VNI->isUnused())
917  continue;
918  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
919  EqualVNs[ParentVNI->id].insert(VNI);
920  }
921 
922  // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
923  // redundant VNIs to BackCopies.
924  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
925  VNInfo *ParentVNI = Parent->getValNumInfo(i);
926  if (!NotToHoistSet.count(ParentVNI->id))
927  continue;
928  SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
930  for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) {
931  It2 = It1;
932  for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) {
933  if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2))
934  continue;
935 
936  MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
937  MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
938  if (MBB1 == MBB2) {
939  DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
940  } else if (MDT.dominates(MBB1, MBB2)) {
941  DominatedVNIs.insert(*It2);
942  } else if (MDT.dominates(MBB2, MBB1)) {
943  DominatedVNIs.insert(*It1);
944  }
945  }
946  }
947  if (!DominatedVNIs.empty()) {
948  forceRecompute(0, *ParentVNI);
949  append_range(BackCopies, DominatedVNIs);
950  DominatedVNIs.clear();
951  }
952  }
953 }
954 
955 /// For SM_Size mode, find a common dominator for all the back-copies for
956 /// the same ParentVNI and hoist the backcopies to the dominator BB.
957 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
958 /// to do the hoisting, simply remove the dominated backcopies for the same
959 /// ParentVNI.
960 void SplitEditor::hoistCopies() {
961  // Get the complement interval, always RegIdx 0.
962  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
963  LiveInterval *Parent = &Edit->getParent();
964 
965  // Track the nearest common dominator for all back-copies for each ParentVNI,
966  // indexed by ParentVNI->id.
967  using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
968  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
969  // The total cost of all the back-copies for each ParentVNI.
971  // The ParentVNI->id set for which hoisting back-copies are not beneficial
972  // for Speed.
973  DenseSet<unsigned> NotToHoistSet;
974 
975  // Find the nearest common dominator for parent values with multiple
976  // back-copies. If a single back-copy dominates, put it in DomPair.second.
977  for (VNInfo *VNI : LI->valnos) {
978  if (VNI->isUnused())
979  continue;
980  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
981  assert(ParentVNI && "Parent not live at complement def");
982 
983  // Don't hoist remats. The complement is probably going to disappear
984  // completely anyway.
985  if (Edit->didRematerialize(ParentVNI))
986  continue;
987 
988  MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
989 
990  DomPair &Dom = NearestDom[ParentVNI->id];
991 
992  // Keep directly defined parent values. This is either a PHI or an
993  // instruction in the complement range. All other copies of ParentVNI
994  // should be eliminated.
995  if (VNI->def == ParentVNI->def) {
996  LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
997  Dom = DomPair(ValMBB, VNI->def);
998  continue;
999  }
1000  // Skip the singly mapped values. There is nothing to gain from hoisting a
1001  // single back-copy.
1002  if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1003  LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1004  continue;
1005  }
1006 
1007  if (!Dom.first) {
1008  // First time we see ParentVNI. VNI dominates itself.
1009  Dom = DomPair(ValMBB, VNI->def);
1010  } else if (Dom.first == ValMBB) {
1011  // Two defs in the same block. Pick the earlier def.
1012  if (!Dom.second.isValid() || VNI->def < Dom.second)
1013  Dom.second = VNI->def;
1014  } else {
1015  // Different basic blocks. Check if one dominates.
1017  MDT.findNearestCommonDominator(Dom.first, ValMBB);
1018  if (Near == ValMBB)
1019  // Def ValMBB dominates.
1020  Dom = DomPair(ValMBB, VNI->def);
1021  else if (Near != Dom.first)
1022  // None dominate. Hoist to common dominator, need new def.
1023  Dom = DomPair(Near, SlotIndex());
1024  Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1025  }
1026 
1027  LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
1028  << VNI->def << " for parent " << ParentVNI->id << '@'
1029  << ParentVNI->def << " hoist to "
1030  << printMBBReference(*Dom.first) << ' ' << Dom.second
1031  << '\n');
1032  }
1033 
1034  // Insert the hoisted copies.
1035  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
1036  DomPair &Dom = NearestDom[i];
1037  if (!Dom.first || Dom.second.isValid())
1038  continue;
1039  // This value needs a hoisted copy inserted at the end of Dom.first.
1040  VNInfo *ParentVNI = Parent->getValNumInfo(i);
1041  MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1042  // Get a less loopy dominator than Dom.first.
1043  Dom.first = findShallowDominator(Dom.first, DefMBB);
1044  if (SpillMode == SM_Speed &&
1045  MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1046  NotToHoistSet.insert(ParentVNI->id);
1047  continue;
1048  }
1049  SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
1050  Dom.second =
1051  defFromParent(0, ParentVNI, Last, *Dom.first,
1052  SA.getLastSplitPointIter(Dom.first))->def;
1053  }
1054 
1055  // Remove redundant back-copies that are now known to be dominated by another
1056  // def with the same value.
1057  SmallVector<VNInfo*, 8> BackCopies;
1058  for (VNInfo *VNI : LI->valnos) {
1059  if (VNI->isUnused())
1060  continue;
1061  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1062  const DomPair &Dom = NearestDom[ParentVNI->id];
1063  if (!Dom.first || Dom.second == VNI->def ||
1064  NotToHoistSet.count(ParentVNI->id))
1065  continue;
1066  BackCopies.push_back(VNI);
1067  forceRecompute(0, *ParentVNI);
1068  }
1069 
1070  // If it is not beneficial to hoist all the BackCopies, simply remove
1071  // redundant BackCopies in speed mode.
1072  if (SpillMode == SM_Speed && !NotToHoistSet.empty())
1073  computeRedundantBackCopies(NotToHoistSet, BackCopies);
1074 
1075  removeBackCopies(BackCopies);
1076 }
1077 
1078 /// transferValues - Transfer all possible values to the new live ranges.
1079 /// Values that were rematerialized are left alone, they need LICalc.extend().
1080 bool SplitEditor::transferValues() {
1081  bool Skipped = false;
1082  RegAssignMap::const_iterator AssignI = RegAssign.begin();
1083  for (const LiveRange::Segment &S : Edit->getParent()) {
1084  LLVM_DEBUG(dbgs() << " blit " << S << ':');
1085  VNInfo *ParentVNI = S.valno;
1086  // RegAssign has holes where RegIdx 0 should be used.
1087  SlotIndex Start = S.start;
1088  AssignI.advanceTo(Start);
1089  do {
1090  unsigned RegIdx;
1091  SlotIndex End = S.end;
1092  if (!AssignI.valid()) {
1093  RegIdx = 0;
1094  } else if (AssignI.start() <= Start) {
1095  RegIdx = AssignI.value();
1096  if (AssignI.stop() < End) {
1097  End = AssignI.stop();
1098  ++AssignI;
1099  }
1100  } else {
1101  RegIdx = 0;
1102  End = std::min(End, AssignI.start());
1103  }
1104 
1105  // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1106  LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
1107  << printReg(Edit->get(RegIdx)) << ')');
1108  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1109 
1110  // Check for a simply defined value that can be blitted directly.
1111  ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1112  if (VNInfo *VNI = VFP.getPointer()) {
1113  LLVM_DEBUG(dbgs() << ':' << VNI->id);
1114  LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1115  Start = End;
1116  continue;
1117  }
1118 
1119  // Skip values with forced recomputation.
1120  if (VFP.getInt()) {
1121  LLVM_DEBUG(dbgs() << "(recalc)");
1122  Skipped = true;
1123  Start = End;
1124  continue;
1125  }
1126 
1127  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1128 
1129  // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1130  // so the live range is accurate. Add live-in blocks in [Start;End) to the
1131  // LiveInBlocks.
1133  SlotIndex BlockStart, BlockEnd;
1134  std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1135 
1136  // The first block may be live-in, or it may have its own def.
1137  if (Start != BlockStart) {
1138  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1139  assert(VNI && "Missing def for complex mapped value");
1140  LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
1141  // MBB has its own def. Is it also live-out?
1142  if (BlockEnd <= End)
1143  LIC.setLiveOutValue(&*MBB, VNI);
1144 
1145  // Skip to the next block for live-in.
1146  ++MBB;
1147  BlockStart = BlockEnd;
1148  }
1149 
1150  // Handle the live-in blocks covered by [Start;End).
1151  assert(Start <= BlockStart && "Expected live-in block");
1152  while (BlockStart < End) {
1153  LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
1154  BlockEnd = LIS.getMBBEndIdx(&*MBB);
1155  if (BlockStart == ParentVNI->def) {
1156  // This block has the def of a parent PHI, so it isn't live-in.
1157  assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1158  VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1159  assert(VNI && "Missing def for complex mapped parent PHI");
1160  if (End >= BlockEnd)
1161  LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1162  } else {
1163  // This block needs a live-in value. The last block covered may not
1164  // be live-out.
1165  if (End < BlockEnd)
1166  LIC.addLiveInBlock(LI, MDT[&*MBB], End);
1167  else {
1168  // Live-through, and we don't know the value.
1169  LIC.addLiveInBlock(LI, MDT[&*MBB]);
1170  LIC.setLiveOutValue(&*MBB, nullptr);
1171  }
1172  }
1173  BlockStart = BlockEnd;
1174  ++MBB;
1175  }
1176  Start = End;
1177  } while (Start != S.end);
1178  LLVM_DEBUG(dbgs() << '\n');
1179  }
1180 
1181  LICalc[0].calculateValues();
1182  if (SpillMode)
1183  LICalc[1].calculateValues();
1184 
1185  return Skipped;
1186 }
1187 
1189  const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1190  if (Seg == nullptr)
1191  return true;
1192  if (Seg->end != Def.getDeadSlot())
1193  return false;
1194  // This is a dead PHI. Remove it.
1195  LR.removeSegment(*Seg, true);
1196  return true;
1197 }
1198 
1199 void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
1200  LiveRange &LR, LaneBitmask LM,
1201  ArrayRef<SlotIndex> Undefs) {
1202  for (MachineBasicBlock *P : B.predecessors()) {
1203  SlotIndex End = LIS.getMBBEndIdx(P);
1204  SlotIndex LastUse = End.getPrevSlot();
1205  // The predecessor may not have a live-out value. That is OK, like an
1206  // undef PHI operand.
1207  LiveInterval &PLI = Edit->getParent();
1208  // Need the cast because the inputs to ?: would otherwise be deemed
1209  // "incompatible": SubRange vs LiveInterval.
1210  LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI)
1211  : static_cast<LiveRange &>(PLI);
1212  if (PSR.liveAt(LastUse))
1213  LIC.extend(LR, End, /*PhysReg=*/0, Undefs);
1214  }
1215 }
1216 
1217 void SplitEditor::extendPHIKillRanges() {
1218  // Extend live ranges to be live-out for successor PHI values.
1219 
1220  // Visit each PHI def slot in the parent live interval. If the def is dead,
1221  // remove it. Otherwise, extend the live interval to reach the end indexes
1222  // of all predecessor blocks.
1223 
1224  LiveInterval &ParentLI = Edit->getParent();
1225  for (const VNInfo *V : ParentLI.valnos) {
1226  if (V->isUnused() || !V->isPHIDef())
1227  continue;
1228 
1229  unsigned RegIdx = RegAssign.lookup(V->def);
1230  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1231  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1232  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1233  if (!removeDeadSegment(V->def, LI))
1234  extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1235  }
1236 
1238  LiveIntervalCalc SubLIC;
1239 
1240  for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1241  for (const VNInfo *V : PS.valnos) {
1242  if (V->isUnused() || !V->isPHIDef())
1243  continue;
1244  unsigned RegIdx = RegAssign.lookup(V->def);
1245  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1246  LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI);
1247  if (removeDeadSegment(V->def, S))
1248  continue;
1249 
1250  MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1251  SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1252  &LIS.getVNInfoAllocator());
1253  Undefs.clear();
1254  LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1255  extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);
1256  }
1257  }
1258 }
1259 
1260 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1261 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1262  struct ExtPoint {
1263  ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1264  : MO(O), RegIdx(R), Next(N) {}
1265 
1266  MachineOperand MO;
1267  unsigned RegIdx;
1268  SlotIndex Next;
1269  };
1270 
1271  SmallVector<ExtPoint,4> ExtPoints;
1272 
1273  for (MachineOperand &MO :
1275  MachineInstr *MI = MO.getParent();
1276  // LiveDebugVariables should have handled all DBG_VALUE instructions.
1277  if (MI->isDebugValue()) {
1278  LLVM_DEBUG(dbgs() << "Zapping " << *MI);
1279  MO.setReg(0);
1280  continue;
1281  }
1282 
1283  // <undef> operands don't really read the register, so it doesn't matter
1284  // which register we choose. When the use operand is tied to a def, we must
1285  // use the same register as the def, so just do that always.
1286  SlotIndex Idx = LIS.getInstructionIndex(*MI);
1287  if (MO.isDef() || MO.isUndef())
1288  Idx = Idx.getRegSlot(MO.isEarlyClobber());
1289 
1290  // Rewrite to the mapped register at Idx.
1291  unsigned RegIdx = RegAssign.lookup(Idx);
1292  LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1293  MO.setReg(LI.reg());
1294  LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())
1295  << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
1296 
1297  // Extend liveness to Idx if the instruction reads reg.
1298  if (!ExtendRanges || MO.isUndef())
1299  continue;
1300 
1301  // Skip instructions that don't read Reg.
1302  if (MO.isDef()) {
1303  if (!MO.getSubReg() && !MO.isEarlyClobber())
1304  continue;
1305  // We may want to extend a live range for a partial redef, or for a use
1306  // tied to an early clobber.
1307  Idx = Idx.getPrevSlot();
1308  if (!Edit->getParent().liveAt(Idx))
1309  continue;
1310  } else
1311  Idx = Idx.getRegSlot(true);
1312 
1313  SlotIndex Next = Idx.getNextSlot();
1314  if (LI.hasSubRanges()) {
1315  // We have to delay extending subranges until we have seen all operands
1316  // defining the register. This is because a <def,read-undef> operand
1317  // will create an "undef" point, and we cannot extend any subranges
1318  // until all of them have been accounted for.
1319  if (MO.isUse())
1320  ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1321  } else {
1322  LiveIntervalCalc &LIC = getLICalc(RegIdx);
1323  LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1324  }
1325  }
1326 
1327  for (ExtPoint &EP : ExtPoints) {
1328  LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1329  assert(LI.hasSubRanges());
1330 
1331  LiveIntervalCalc SubLIC;
1332  Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1333  LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
1335  for (LiveInterval::SubRange &S : LI.subranges()) {
1336  if ((S.LaneMask & LM).none())
1337  continue;
1338  // The problem here can be that the new register may have been created
1339  // for a partially defined original register. For example:
1340  // %0:subreg_hireg<def,read-undef> = ...
1341  // ...
1342  // %1 = COPY %0
1343  if (S.empty())
1344  continue;
1345  SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1346  &LIS.getVNInfoAllocator());
1348  LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1349  SubLIC.extend(S, EP.Next, 0, Undefs);
1350  }
1351  }
1352 
1353  for (Register R : *Edit) {
1354  LiveInterval &LI = LIS.getInterval(R);
1355  if (!LI.hasSubRanges())
1356  continue;
1357  LI.clear();
1358  LI.removeEmptySubRanges();
1360  }
1361 }
1362 
1363 void SplitEditor::deleteRematVictims() {
1365  for (const Register &R : *Edit) {
1366  LiveInterval *LI = &LIS.getInterval(R);
1367  for (const LiveRange::Segment &S : LI->segments) {
1368  // Dead defs end at the dead slot.
1369  if (S.end != S.valno->def.getDeadSlot())
1370  continue;
1371  if (S.valno->isPHIDef())
1372  continue;
1373  MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1374  assert(MI && "Missing instruction for dead def");
1375  MI->addRegisterDead(LI->reg(), &TRI);
1376 
1377  if (!MI->allDefsAreDead())
1378  continue;
1379 
1380  LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
1381  Dead.push_back(MI);
1382  }
1383  }
1384 
1385  if (Dead.empty())
1386  return;
1387 
1388  Edit->eliminateDeadDefs(Dead, None, &AA);
1389 }
1390 
1391 void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
1392  // Fast-path for common case.
1393  if (!ParentVNI.isPHIDef()) {
1394  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1395  forceRecompute(I, ParentVNI);
1396  return;
1397  }
1398 
1399  // Trace value through phis.
1400  SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
1402  Visited.insert(&ParentVNI);
1403  WorkList.push_back(&ParentVNI);
1404 
1405  const LiveInterval &ParentLI = Edit->getParent();
1406  const SlotIndexes &Indexes = *LIS.getSlotIndexes();
1407  do {
1408  const VNInfo &VNI = *WorkList.back();
1409  WorkList.pop_back();
1410  for (unsigned I = 0, E = Edit->size(); I != E; ++I)
1411  forceRecompute(I, VNI);
1412  if (!VNI.isPHIDef())
1413  continue;
1414 
1415  MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
1416  for (const MachineBasicBlock *Pred : MBB.predecessors()) {
1417  SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
1418  VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
1419  assert(PredVNI && "Value available in PhiVNI predecessor");
1420  if (Visited.insert(PredVNI).second)
1421  WorkList.push_back(PredVNI);
1422  }
1423  } while(!WorkList.empty());
1424 }
1425 
1427  ++NumFinished;
1428 
1429  // At this point, the live intervals in Edit contain VNInfos corresponding to
1430  // the inserted copies.
1431 
1432  // Add the original defs from the parent interval.
1433  for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1434  if (ParentVNI->isUnused())
1435  continue;
1436  unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1437  defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1438 
1439  // Force rematted values to be recomputed everywhere.
1440  // The new live ranges may be truncated.
1441  if (Edit->didRematerialize(ParentVNI))
1442  forceRecomputeVNI(*ParentVNI);
1443  }
1444 
1445  // Hoist back-copies to the complement interval when in spill mode.
1446  switch (SpillMode) {
1447  case SM_Partition:
1448  // Leave all back-copies as is.
1449  break;
1450  case SM_Size:
1451  case SM_Speed:
1452  // hoistCopies will behave differently between size and speed.
1453  hoistCopies();
1454  }
1455 
1456  // Transfer the simply mapped values, check if any are skipped.
1457  bool Skipped = transferValues();
1458 
1459  // Rewrite virtual registers, possibly extending ranges.
1460  rewriteAssigned(Skipped);
1461 
1462  if (Skipped)
1463  extendPHIKillRanges();
1464  else
1465  ++NumSimple;
1466 
1467  // Delete defs that were rematted everywhere.
1468  if (Skipped)
1469  deleteRematVictims();
1470 
1471  // Get rid of unused values and set phi-kill flags.
1472  for (Register Reg : *Edit) {
1473  LiveInterval &LI = LIS.getInterval(Reg);
1474  LI.removeEmptySubRanges();
1475  LI.RenumberValues();
1476  }
1477 
1478  // Provide a reverse mapping from original indices to Edit ranges.
1479  if (LRMap) {
1480  LRMap->clear();
1481  for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1482  LRMap->push_back(i);
1483  }
1484 
1485  // Now check if any registers were separated into multiple components.
1486  ConnectedVNInfoEqClasses ConEQ(LIS);
1487  for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1488  // Don't use iterators, they are invalidated by create() below.
1489  Register VReg = Edit->get(i);
1490  LiveInterval &LI = LIS.getInterval(VReg);
1492  LIS.splitSeparateComponents(LI, SplitLIs);
1493  Register Original = VRM.getOriginal(VReg);
1494  for (LiveInterval *SplitLI : SplitLIs)
1495  VRM.setIsSplitFromReg(SplitLI->reg(), Original);
1496 
1497  // The new intervals all map back to i.
1498  if (LRMap)
1499  LRMap->resize(Edit->size(), i);
1500  }
1501 
1502  // Calculate spill weight and allocation hints for new intervals.
1503  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI);
1504 
1505  assert(!LRMap || LRMap->size() == Edit->size());
1506 }
1507 
1508 //===----------------------------------------------------------------------===//
1509 // Single Block Splitting
1510 //===----------------------------------------------------------------------===//
1511 
1513  bool SingleInstrs) const {
1514  // Always split for multiple instructions.
1515  if (!BI.isOneInstr())
1516  return true;
1517  // Don't split for single instructions unless explicitly requested.
1518  if (!SingleInstrs)
1519  return false;
1520  // Splitting a live-through range always makes progress.
1521  if (BI.LiveIn && BI.LiveOut)
1522  return true;
1523  // No point in isolating a copy. It has no register class constraints.
1525  return false;
1526  // Finally, don't isolate an end point that was created by earlier splits.
1527  return isOriginalEndpoint(BI.FirstInstr);
1528 }
1529 
1531  openIntv();
1532  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB);
1534  LastSplitPoint));
1535  if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1536  useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1537  } else {
1538  // The last use is after the last valid split point.
1539  SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1540  useIntv(SegStart, SegStop);
1541  overlapIntv(SegStop, BI.LastInstr);
1542  }
1543 }
1544 
1545 //===----------------------------------------------------------------------===//
1546 // Global Live Range Splitting Support
1547 //===----------------------------------------------------------------------===//
1548 
1549 // These methods support a method of global live range splitting that uses a
1550 // global algorithm to decide intervals for CFG edges. They will insert split
1551 // points and color intervals in basic blocks while avoiding interference.
1552 //
1553 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1554 // are on the stack.
1555 
1557  unsigned IntvIn, SlotIndex LeaveBefore,
1558  unsigned IntvOut, SlotIndex EnterAfter){
1559  SlotIndex Start, Stop;
1560  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1561 
1562  LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
1563  << ") intf " << LeaveBefore << '-' << EnterAfter
1564  << ", live-through " << IntvIn << " -> " << IntvOut);
1565 
1566  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1567 
1568  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1569  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1570  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1571 
1573 
1574  if (!IntvOut) {
1575  LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1576  //
1577  // <<<<<<<<< Possible LeaveBefore interference.
1578  // |-----------| Live through.
1579  // -____________ Spill on entry.
1580  //
1581  selectIntv(IntvIn);
1582  SlotIndex Idx = leaveIntvAtTop(*MBB);
1583  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1584  (void)Idx;
1585  return;
1586  }
1587 
1588  if (!IntvIn) {
1589  LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1590  //
1591  // >>>>>>> Possible EnterAfter interference.
1592  // |-----------| Live through.
1593  // ___________-- Reload on exit.
1594  //
1595  selectIntv(IntvOut);
1596  SlotIndex Idx = enterIntvAtEnd(*MBB);
1597  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1598  (void)Idx;
1599  return;
1600  }
1601 
1602  if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1603  LLVM_DEBUG(dbgs() << ", straight through.\n");
1604  //
1605  // |-----------| Live through.
1606  // ------------- Straight through, same intv, no interference.
1607  //
1608  selectIntv(IntvOut);
1609  useIntv(Start, Stop);
1610  return;
1611  }
1612 
1613  // We cannot legally insert splits after LSP.
1614  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1615  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1616 
1617  if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1618  LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1619  LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1620  //
1621  // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.
1622  // |-----------| Live through.
1623  // ------======= Switch intervals between interference.
1624  //
1625  selectIntv(IntvOut);
1626  SlotIndex Idx;
1627  if (LeaveBefore && LeaveBefore < LSP) {
1628  Idx = enterIntvBefore(LeaveBefore);
1629  useIntv(Idx, Stop);
1630  } else {
1631  Idx = enterIntvAtEnd(*MBB);
1632  }
1633  selectIntv(IntvIn);
1634  useIntv(Start, Idx);
1635  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1636  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1637  return;
1638  }
1639 
1640  LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1641  //
1642  // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.
1643  // |-----------| Live through.
1644  // ==---------== Switch intervals before/after interference.
1645  //
1646  assert(LeaveBefore <= EnterAfter && "Missed case");
1647 
1648  selectIntv(IntvOut);
1649  SlotIndex Idx = enterIntvAfter(EnterAfter);
1650  useIntv(Idx, Stop);
1651  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1652 
1653  selectIntv(IntvIn);
1654  Idx = leaveIntvBefore(LeaveBefore);
1655  useIntv(Start, Idx);
1656  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1657 }
1658 
1660  unsigned IntvIn, SlotIndex LeaveBefore) {
1661  SlotIndex Start, Stop;
1662  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1663 
1664  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1665  << Stop << "), uses " << BI.FirstInstr << '-'
1666  << BI.LastInstr << ", reg-in " << IntvIn
1667  << ", leave before " << LeaveBefore
1668  << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1669 
1670  assert(IntvIn && "Must have register in");
1671  assert(BI.LiveIn && "Must be live-in");
1672  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1673 
1674  if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1675  LLVM_DEBUG(dbgs() << " before interference.\n");
1676  //
1677  // <<< Interference after kill.
1678  // |---o---x | Killed in block.
1679  // ========= Use IntvIn everywhere.
1680  //
1681  selectIntv(IntvIn);
1682  useIntv(Start, BI.LastInstr);
1683  return;
1684  }
1685 
1686  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);
1687 
1688  if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1689  //
1690  // <<< Possible interference after last use.
1691  // |---o---o---| Live-out on stack.
1692  // =========____ Leave IntvIn after last use.
1693  //
1694  // < Interference after last use.
1695  // |---o---o--o| Live-out on stack, late last use.
1696  // ============ Copy to stack after LSP, overlap IntvIn.
1697  // \_____ Stack interval is live-out.
1698  //
1699  if (BI.LastInstr < LSP) {
1700  LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1701  selectIntv(IntvIn);
1703  useIntv(Start, Idx);
1704  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1705  } else {
1706  LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1707  selectIntv(IntvIn);
1708  SlotIndex Idx = leaveIntvBefore(LSP);
1709  overlapIntv(Idx, BI.LastInstr);
1710  useIntv(Start, Idx);
1711  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1712  }
1713  return;
1714  }
1715 
1716  // The interference is overlapping somewhere we wanted to use IntvIn. That
1717  // means we need to create a local interval that can be allocated a
1718  // different register.
1719  unsigned LocalIntv = openIntv();
1720  (void)LocalIntv;
1721  LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1722 
1723  if (!BI.LiveOut || BI.LastInstr < LSP) {
1724  //
1725  // <<<<<<< Interference overlapping uses.
1726  // |---o---o---| Live-out on stack.
1727  // =====----____ Leave IntvIn before interference, then spill.
1728  //
1730  SlotIndex From = enterIntvBefore(LeaveBefore);
1731  useIntv(From, To);
1732  selectIntv(IntvIn);
1733  useIntv(Start, From);
1734  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1735  return;
1736  }
1737 
1738  // <<<<<<< Interference overlapping uses.
1739  // |---o---o--o| Live-out on stack, late last use.
1740  // =====------- Copy to stack before LSP, overlap LocalIntv.
1741  // \_____ Stack interval is live-out.
1742  //
1743  SlotIndex To = leaveIntvBefore(LSP);
1744  overlapIntv(To, BI.LastInstr);
1745  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1746  useIntv(From, To);
1747  selectIntv(IntvIn);
1748  useIntv(Start, From);
1749  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1750 }
1751 
1753  unsigned IntvOut, SlotIndex EnterAfter) {
1754  SlotIndex Start, Stop;
1755  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1756 
1757  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1758  << Stop << "), uses " << BI.FirstInstr << '-'
1759  << BI.LastInstr << ", reg-out " << IntvOut
1760  << ", enter after " << EnterAfter
1761  << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1762 
1763  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB);
1764 
1765  assert(IntvOut && "Must have register out");
1766  assert(BI.LiveOut && "Must be live-out");
1767  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1768 
1769  if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1770  LLVM_DEBUG(dbgs() << " after interference.\n");
1771  //
1772  // >>>> Interference before def.
1773  // | o---o---| Defined in block.
1774  // ========= Use IntvOut everywhere.
1775  //
1776  selectIntv(IntvOut);
1777  useIntv(BI.FirstInstr, Stop);
1778  return;
1779  }
1780 
1781  if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1782  LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1783  //
1784  // >>>> Interference before def.
1785  // |---o---o---| Live-through, stack-in.
1786  // ____========= Enter IntvOut before first use.
1787  //
1788  selectIntv(IntvOut);
1789  SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1790  useIntv(Idx, Stop);
1791  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1792  return;
1793  }
1794 
1795  // The interference is overlapping somewhere we wanted to use IntvOut. That
1796  // means we need to create a local interval that can be allocated a
1797  // different register.
1798  LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1799  //
1800  // >>>>>>> Interference overlapping uses.
1801  // |---o---o---| Live-through, stack-in.
1802  // ____---====== Create local interval for interference range.
1803  //
1804  selectIntv(IntvOut);
1805  SlotIndex Idx = enterIntvAfter(EnterAfter);
1806  useIntv(Idx, Stop);
1807  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1808 
1809  openIntv();
1811  useIntv(From, Idx);
1812 }
1813 
1815  OS << "{" << printMBBReference(*MBB) << ", "
1816  << "uses " << FirstInstr << " to " << LastInstr << ", "
1817  << "1st def " << FirstDef << ", "
1818  << (LiveIn ? "live in" : "dead in") << ", "
1819  << (LiveOut ? "live out" : "dead out") << "}";
1820 }
1821 
1823  print(dbgs());
1824  dbgs() << "\n";
1825 }
llvm::MachineDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Definition: MachineDominators.h:149
llvm::LiveRange::find
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
Definition: LiveInterval.cpp:350
llvm::LaneBitmask
Definition: LaneBitmask.h:39
llvm::SplitAnalysis::getNumLiveBlocks
unsigned getNumLiveBlocks() const
getNumLiveBlocks - Return the number of blocks where CurLI is live.
Definition: SplitKit.h:217
i
i
Definition: README.txt:29
llvm::InsertPointAnalysis::InsertPointAnalysis
InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum)
Definition: SplitKit.cpp:59
llvm::LiveRangeEdit::Remat
Remat - Information needed to rematerialize at a specific location.
Definition: LiveRangeEdit.h:202
llvm::array_pod_sort
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:1404
llvm::LiveInterval::computeSubRangeUndefs
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 ...
Definition: LiveInterval.cpp:976
llvm::SplitEditor::splitSingleBlock
void splitSingleBlock(const SplitAnalysis::BlockInfo &BI)
splitSingleBlock - Split CurLI into a separate live interval around the uses in a single block.
Definition: SplitKit.cpp:1530
llvm::SlotIndexes::getMBBRange
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:455
llvm::SplitEditor::enterIntvAtEnd
SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB)
enterIntvAtEnd - Enter the open interval at the end of MBB.
Definition: SplitKit.cpp:687
llvm::SplitAnalysis::BlockInfo::LiveIn
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:127
llvm::IntervalMap::clear
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1284
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:499
llvm
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::SplitAnalysis::BlockInfo::FirstInstr
SlotIndex FirstInstr
First instr accessing current reg.
Definition: SplitKit.h:124
llvm::IntervalMap::insert
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
Definition: IntervalMap.h:1083
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1519
llvm::SplitEditor::openIntv
unsigned openIntv()
Create a new virtual register and live interval.
Definition: SplitKit.cpp:634
llvm::LiveIntervals::getSlotIndexes
SlotIndexes * getSlotIndexes() const
Definition: LiveIntervals.h:211
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::LiveIntervals::isLiveInToMBB
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
Definition: LiveIntervals.h:245
llvm::SlotIndex::isValid
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:151
llvm::SplitAnalysis::BlockInfo::isOneInstr
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
Definition: SplitKit.h:132
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::DenseMapBase::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:327
llvm::SlotIndex::getBoundaryIndex
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
Definition: SlotIndexes.h:248
llvm::SplitEditor::SplitEditor
SplitEditor(SplitAnalysis &SA, AAResults &AA, LiveIntervals &LIS, VirtRegMap &VRM, MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)
Create a new SplitEditor for editing the LiveInterval analyzed by SA.
Definition: SplitKit.cpp:360
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:51
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::VirtRegAuxInfo
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
Definition: CalcSpillWeights.h:46
llvm::LiveRange::advanceTo
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
Definition: LiveInterval.h:263
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
llvm::VirtRegMap::getOriginal
Register getOriginal(Register VirtReg) const
getOriginal - Return the original virtual register that VirtReg descends from through splitting.
Definition: VirtRegMap.h:170
llvm::LiveIntervals::getInstructionFromIndex
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
Definition: LiveIntervals.h:231
ErrorHandling.h
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::LiveRangeCalc::extend
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
Definition: LiveRangeCalc.cpp:89
Allocator.h
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
llvm::MachineInstr::bundleWithPred
void bundleWithPred()
Bundle this instruction with its predecessor.
Definition: MachineInstr.cpp:759
llvm::VNInfo::def
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
llvm::MachineInstr::defs
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:644
llvm::SplitAnalysis::BlockInfo
Additional information about basic blocks where the current variable is live.
Definition: SplitKit.h:122
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:682
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
BlockFrequency.h
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:333
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
TargetInstrInfo.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::VirtRegMap::getMachineFunction
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:88
llvm::SmallPtrSetIterator
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:266
llvm::SplitEditor::useIntv
void useIntv(const MachineBasicBlock &MBB)
useIntv - indicate that all instructions in MBB should use OpenLI.
Definition: SplitKit.cpp:707
llvm::SplitAnalysis::countLiveBlocks
unsigned countLiveBlocks(const LiveInterval *li) const
countLiveBlocks - Return the number of blocks where li is live.
Definition: SplitKit.cpp:311
llvm::IntervalMap::empty
bool empty() const
empty - Return true when no intervals are mapped.
Definition: IntervalMap.h:1055
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SlotIndexes::getMBBEndIdx
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:476
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:109
STLExtras.h
llvm::SplitEditor::splitRegInBlock
void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvIn, SlotIndex LeaveBefore)
splitRegInBlock - Split CurLI in the given block such that it enters the block in IntvIn and leaves i...
Definition: SplitKit.cpp:1659
llvm::LiveRangeEdit::getReg
Register getReg() const
Definition: LiveRangeEdit.h:156
llvm::LiveRangeCalc::calculateValues
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
Definition: LiveRangeCalc.cpp:117
llvm::SplitAnalysis::BlockInfo::FirstDef
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
Definition: SplitKit.h:126
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::LiveRangeEdit::didRematerialize
bool didRematerialize(const VNInfo *ParentVNI) const
didRematerialize - Return true if ParentVNI was rematerialized anywhere.
Definition: LiveRangeEdit.h:232
llvm::LiveIntervals::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Definition: LiveIntervals.h:255
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:228
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::SplitAnalysis::isOriginalEndpoint
bool isOriginalEndpoint(SlotIndex Idx) const
isOriginalEndpoint - Return true if the original live range was killed or (re-)defined at Idx.
Definition: SplitKit.cpp:335
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:226
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:129
llvm::SplitAnalysis::shouldSplitSingleBlock
bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const
shouldSplitSingleBlock - Returns true if it would help to create a local live range for the instructi...
Definition: SplitKit.cpp:1512
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::getUndefRegState
unsigned getUndefRegState(bool B)
Definition: MachineInstrBuilder.h:515
llvm::SplitEditor::reset
void reset(LiveRangeEdit &, ComplementSpillMode=SM_Partition)
reset - Prepare for a new split.
Definition: SplitKit.cpp:370
MachineRegisterInfo.h
llvm::LiveRange::extendInBlock
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
Definition: LiveInterval.cpp:564
llvm::SplitAnalysis::SplitAnalysis
SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, const MachineLoopInfo &mli)
Definition: SplitKit.cpp:146
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::SplitEditor::SM_Size
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
Definition: SplitKit.h:297
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
llvm::SplitAnalysis::LIS
const LiveIntervals & LIS
Definition: SplitKit.h:101
llvm::MachineRegisterInfo::use_nodbg_operands
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:526
MachineLoopInfo.h
llvm::SplitAnalysis::Loops
const MachineLoopInfo & Loops
Definition: SplitKit.h:102
llvm::LiveRangeEdit::get
Register get(unsigned idx) const
Definition: LiveRangeEdit.h:164
llvm::LiveRange::liveAt
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:393
llvm::LiveIntervalCalc
Definition: LiveIntervalCalc.h:28
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::LiveRange::begin
iterator begin()
Definition: LiveInterval.h:215
llvm::TargetRegisterInfo::getSubRegIndexLaneMask
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
Definition: TargetRegisterInfo.h:361
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::LiveIntervals::getMBBStartIdx
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Definition: LiveIntervals.h:236
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveRangeEdit::anyRematerializable
bool anyRematerializable(AAResults *)
anyRematerializable - Return true if any parent values may be rematerializable.
Definition: LiveRangeEdit.cpp:98
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::SlotIndex::isEarlierInstr
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:203
llvm::SplitEditor::SM_Partition
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
Definition: SplitKit.h:290
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::LiveRange::const_iterator
Segments::const_iterator const_iterator
Definition: LiveInterval.h:213
llvm::LaneBitmask::getNone
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:82
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::SplitAnalysis::getLastSplitPointIter
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
Definition: SplitKit.h:246
llvm::SplitEditor::splitLiveThroughBlock
void splitLiveThroughBlock(unsigned MBBNum, unsigned IntvIn, SlotIndex LeaveBefore, unsigned IntvOut, SlotIndex EnterAfter)
splitLiveThroughBlock - Split CurLI in the given block such that it enters the block in IntvIn and le...
Definition: SplitKit.cpp:1556
SplitKit.h
TargetOpcodes.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::SplitEditor::leaveIntvBefore
SlotIndex leaveIntvBefore(SlotIndex Idx)
leaveIntvBefore - Leave the open interval before the instruction at Idx.
Definition: SplitKit.cpp:749
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:196
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::LiveRangeEdit
Definition: LiveRangeEdit.h:46
llvm::LiveRange::valnos
VNInfoList valnos
Definition: LiveInterval.h:204
llvm::report_fatal_error
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:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::RegState::Define
@ Define
Register definition.
Definition: MachineInstrBuilder.h:45
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
DebugLoc.h
Copies
SI Lower i1 Copies
Definition: SILowerI1Copies.cpp:406
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::IntervalMap< SlotIndex, unsigned >::iterator
friend class iterator
Definition: IntervalMap.h:1098
llvm::SplitEditor::splitRegOutBlock
void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvOut, SlotIndex EnterAfter)
splitRegOutBlock - Split CurLI in the given block such that it enters the block on the stack (or isn'...
Definition: SplitKit.cpp:1752
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::None
const NoneType None
Definition: None.h:23
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:49
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::SplitEditor::enterIntvBefore
SlotIndex enterIntvBefore(SlotIndex Idx)
enterIntvBefore - Enter the open interval before the instruction at Idx.
Definition: SplitKit.cpp:652
llvm::SlotIndexes::insertMachineInstrInMaps
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:535
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::SplitAnalysis::BlockInfo::dump
void dump() const
Definition: SplitKit.cpp:1822
llvm::LiveRangeEdit::getParent
LiveInterval & getParent() const
Definition: LiveRangeEdit.h:151
llvm::VirtRegMap::setIsSplitFromReg
void setIsSplitFromReg(Register virtReg, Register SReg)
records virtReg is a split live interval from SReg.
Definition: VirtRegMap.h:154
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:59
llvm::DenseSet< unsigned >
llvm::SlotIndex::getBaseIndex
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:241
llvm::SplitEditor::overlapIntv
void overlapIntv(SlotIndex Start, SlotIndex End)
overlapIntv - Indicate that all instructions in range should use the open interval,...
Definition: SplitKit.cpp:787
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:128
llvm::LiveRange::RenumberValues
void RenumberValues()
RenumberValues - Renumber all values in order of appearance and remove unused values.
Definition: LiveInterval.cpp:531
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::LiveRange::getVNInfoBefore
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:421
llvm::LiveInterval::removeEmptySubRanges
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Definition: LiveInterval.cpp:853
llvm::LiveInterval::refineSubRanges
void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
Definition: LiveInterval.cpp:930
llvm::SplitAnalysis::BlockInfo::LastInstr
SlotIndex LastInstr
Last instr accessing current reg.
Definition: SplitKit.h:125
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::SplitAnalysis::BlockInfo::LiveOut
bool LiveOut
Current reg is live out.
Definition: SplitKit.h:128
llvm::LiveRangeCalc::addLiveInBlock
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
Definition: LiveRangeCalc.h:244
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::SplitAnalysis::VRM
const VirtRegMap & VRM
Definition: SplitKit.h:100
llvm::LiveIntervals::getMBBEndIdx
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
Definition: LiveIntervals.h:241
VirtRegMap.h
llvm::VNInfo::id
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::SplitEditor::dump
void dump() const
dump - print the current interval mapping to dbgs().
Definition: SplitKit.cpp:390
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::LiveRangeEdit::createEmptyInterval
LiveInterval & createEmptyInterval()
create - Create a new register with the same class and original slot as parent.
Definition: LiveRangeEdit.h:185
llvm::LiveRange::getNumValNums
unsigned getNumValNums() const
Definition: LiveInterval.h:305
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:581
llvm::FramePointer::FP
FP
Definition: CodeGen.h:71
llvm::SlotIndex::isSameInstr
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:197
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:323
llvm::IntervalMap::lookup
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
Definition: IntervalMap.h:1073
llvm::MachineRegisterInfo::reg_operands
iterator_range< reg_iterator > reg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:286
llvm::MachineBasicBlock::SkipPHIsLabelsAndDebug
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
Definition: MachineBasicBlock.cpp:224
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:96
llvm::SplitEditor::enterIntvAfter
SlotIndex enterIntvAfter(SlotIndex Idx)
enterIntvAfter - Enter the open interval after the instruction at Idx.
Definition: SplitKit.cpp:669
llvm::IndexedInstrProf::HashT::Last
@ Last
llvm::InsertPointAnalysis::getLastInsertPoint
SlotIndex getLastInsertPoint(const LiveInterval &CurLI, const MachineBasicBlock &MBB)
Return the base index of the last valid insert point for \pCurLI in \pMBB.
Definition: SplitKit.h:68
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:514
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:98
llvm::LiveRangeEdit::canRematerializeAt
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, bool cheapAsAMove)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
Definition: LiveRangeEdit.cpp:140
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::SplitAnalysis::MF
const MachineFunction & MF
Definition: SplitKit.h:99
llvm::SlotIndex::getRegSlot
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
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:114
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1486
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:467
llvm::MachineBasicBlock::getFirstTerminator
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
Definition: MachineBasicBlock.cpp:239
llvm::LiveRange::createDeadDef
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
Definition: LiveInterval.cpp:370
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
None.h
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:965
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::LiveRangeEdit::rematerializeAt
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
Definition: LiveRangeEdit.cpp:164
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::LaneBitmask::none
constexpr bool none() const
Definition: LaneBitmask.h:51
MBBI
MachineBasicBlock MachineBasicBlock::iterator MBBI
Definition: AArch64SLSHardening.cpp:75
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::TargetRegisterInfo::getCoveringSubRegIndexes
bool getCoveringSubRegIndexes(const MachineRegisterInfo &MRI, const TargetRegisterClass *RC, LaneBitmask LaneMask, SmallVectorImpl< unsigned > &Indexes) const
Try to find one or more subregister indexes to cover LaneMask.
Definition: TargetRegisterInfo.cpp:505
llvm::SplitEditor::SM_Speed
@ SM_Speed
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies.
Definition: SplitKit.h:302
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1690
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
TargetSubtargetInfo.h
llvm::SlotIndex::getNextSlot
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:269
llvm::SplitAnalysis::clear
void clear()
clear - clear all data structures so SplitAnalysis is ready to analyze a new interval.
Definition: SplitKit.cpp:151
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::SplitAnalysis::BlockInfo::MBB
MachineBasicBlock * MBB
Definition: SplitKit.h:123
llvm::LiveRangeEdit::empty
bool empty() const
Definition: LiveRangeEdit.h:163
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::LiveRange::Segment::end
SlotIndex end
Definition: LiveInterval.h:164
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::SplitEditor::finish
void finish(SmallVectorImpl< unsigned > *LRMap=nullptr)
finish - after all the new live ranges have been created, compute the remaining live range,...
Definition: SplitKit.cpp:1426
llvm::LiveInterval::SubRange
A live range for subregisters.
Definition: LiveInterval.h:687
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
LiveRangeEdit.h
llvm::VNInfo::isPHIDef
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
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::SplitEditor::leaveIntvAtTop
SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB)
leaveIntvAtTop - Leave the interval at the top of MBB.
Definition: SplitKit.cpp:768
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:672
llvm::LiveRange::iterator
Segments::iterator iterator
Definition: LiveInterval.h:212
llvm::MachineRegisterInfo::getMaxLaneMaskForVReg
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
Definition: MachineRegisterInfo.cpp:493
llvm::SplitEditor::ComplementSpillMode
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
Definition: SplitKit.h:285
llvm::MachineInstr::isCopyLike
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:1293
llvm::codeview::LabelType::Near
@ Near
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::SlotIndex::getPrevSlot
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:289
llvm::ISD::INLINEASM_BR
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:968
llvm::LaneBitmask::all
constexpr bool all() const
Definition: LaneBitmask.h:53
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::LiveRange::getValNumInfo
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
Definition: LiveInterval.h:309
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::LiveRange::getVNInfoAt
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:413
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
removeDeadSegment
static bool removeDeadSegment(SlotIndex Def, LiveRange &LR)
Definition: SplitKit.cpp:1188
llvm::LiveRange::removeSegment
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
Definition: LiveInterval.cpp:583
llvm::LiveIntervals::constructMainRangeFromSubranges
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
Definition: LiveIntervals.cpp:1750
llvm::SplitEditor::leaveIntvAfter
SlotIndex leaveIntvAfter(SlotIndex Idx)
leaveIntvAfter - Leave the open interval after the instruction at Idx.
Definition: SplitKit.cpp:718
llvm::SplitAnalysis::BlockInfo::print
void print(raw_ostream &OS) const
Definition: SplitKit.cpp:1814
llvm::SplitAnalysis::analyze
void analyze(const LiveInterval *li)
analyze - set CurLI to the specified interval, and analyze how it may be split.
Definition: SplitKit.cpp:349
llvm::SplitAnalysis::getLastSplitPoint
SlotIndex getLastSplitPoint(unsigned Num)
Definition: SplitKit.h:238
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
MachineInstrBuilder.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:329
llvm::LiveRangeEdit::size
unsigned size() const
Definition: LiveRangeEdit.h:162
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
N
#define N
llvm::LiveIntervals::RemoveMachineInstrFromMaps
void RemoveMachineInstrFromMaps(MachineInstr &MI)
Definition: LiveIntervals.h:276
llvm::LiveIntervals::splitSeparateComponents
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
Definition: LiveIntervals.cpp:1733
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:101
llvm::IntervalMap::begin
const_iterator begin() const
Definition: IntervalMap.h:1100
llvm::LiveRange::segments
Segments segments
Definition: LiveInterval.h:203
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:711
llvm::LiveRange::getSegmentContaining
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:400
llvm::LiveInterval::hasSubRanges
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:797
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
llvm::LiveRange::clear
void clear()
Definition: LiveInterval.h:292
llvm::LiveRangeCalc::reset
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
Definition: LiveRangeCalc.cpp:51
llvm::IntervalMap< SlotIndex, unsigned >::const_iterator
friend class const_iterator
Definition: IntervalMap.h:1096
llvm::SmallVectorImpl< VNInfo * >
MachineOperand.h
llvm::MCInstrInfo::get
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:62
llvm::VNInfo::isUnused
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
llvm::LiveRangeCalc::setLiveOutValue
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Definition: LiveRangeCalc.h:230
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::getInternalReadRegState
unsigned getInternalReadRegState(bool B)
Definition: MachineInstrBuilder.h:518
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:110
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::ConnectedVNInfoEqClasses
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:992
llvm::SplitEditor::selectIntv
void selectIntv(unsigned Idx)
selectIntv - Select a previously opened interval index.
Definition: SplitKit.cpp:645
llvm::LiveIntervals::removeVRegDefAt
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
Definition: LiveIntervals.cpp:1715
MachineBlockFrequencyInfo.h
TargetRegisterInfo.h
llvm::InsertPointAnalysis::getLastInsertPointIter
MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)
Returns the last insert point as an iterator for \pCurLI in \pMBB.
Definition: SplitKit.cpp:134
Debug.h
llvm::SplitAnalysis
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
Definition: SplitKit.h:97
shrinkToUses
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
Definition: WebAssemblyRegStackify.cpp:509
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:83
llvm::LiveIntervals::getVNInfoAllocator
VNInfo::Allocator & getVNInfoAllocator()
Definition: LiveIntervals.h:284
llvm::LiveRange::end
iterator end()
Definition: LiveInterval.h:216
MachineDominators.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::LiveInterval::subranges
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:769