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