1 //===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains the SplitAnalysis class as well as mutator functions for
10 // live range splitting.
12 //===----------------------------------------------------------------------===//
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/None.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/CodeGen/LiveInterval.h"
23 #include "llvm/CodeGen/LiveIntervals.h"
24 #include "llvm/CodeGen/LiveRangeCalc.h"
25 #include "llvm/CodeGen/LiveRangeEdit.h"
26 #include "llvm/CodeGen/MachineBasicBlock.h"
27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28 #include "llvm/CodeGen/MachineDominators.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineInstr.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineOperand.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/SlotIndexes.h"
36 #include "llvm/CodeGen/TargetInstrInfo.h"
37 #include "llvm/CodeGen/TargetOpcodes.h"
38 #include "llvm/CodeGen/TargetRegisterInfo.h"
39 #include "llvm/CodeGen/TargetSubtargetInfo.h"
40 #include "llvm/CodeGen/VirtRegMap.h"
41 #include "llvm/Config/llvm-config.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/MC/LaneBitmask.h"
44 #include "llvm/Support/Allocator.h"
45 #include "llvm/Support/BlockFrequency.h"
46 #include "llvm/Support/Compiler.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Support/ErrorHandling.h"
49 #include "llvm/Support/raw_ostream.h"
59 #define DEBUG_TYPE "regalloc"
61 STATISTIC(NumFinished
, "Number of splits finished");
62 STATISTIC(NumSimple
, "Number of splits that were simple");
63 STATISTIC(NumCopies
, "Number of copies inserted for splitting");
64 STATISTIC(NumRemats
, "Number of rematerialized defs for splitting");
65 STATISTIC(NumRepairs
, "Number of invalid live ranges repaired");
67 //===----------------------------------------------------------------------===//
68 // Last Insert Point Analysis
69 //===----------------------------------------------------------------------===//
71 InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals
&lis
,
73 : LIS(lis
), LastInsertPoint(BBNum
) {}
76 InsertPointAnalysis::computeLastInsertPoint(const LiveInterval
&CurLI
,
77 const MachineBasicBlock
&MBB
) {
78 unsigned Num
= MBB
.getNumber();
79 std::pair
<SlotIndex
, SlotIndex
> &LIP
= LastInsertPoint
[Num
];
80 SlotIndex MBBEnd
= LIS
.getMBBEndIdx(&MBB
);
82 SmallVector
<const MachineBasicBlock
*, 1> EHPadSuccessors
;
83 for (const MachineBasicBlock
*SMBB
: MBB
.successors())
85 EHPadSuccessors
.push_back(SMBB
);
87 // Compute insert points on the first call. The pair is independent of the
88 // current live interval.
89 if (!LIP
.first
.isValid()) {
90 MachineBasicBlock::const_iterator FirstTerm
= MBB
.getFirstTerminator();
91 if (FirstTerm
== MBB
.end())
94 LIP
.first
= LIS
.getInstructionIndex(*FirstTerm
);
96 // If there is a landing pad successor, also find the call instruction.
97 if (EHPadSuccessors
.empty())
99 // There may not be a call instruction (?) in which case we ignore LPad.
100 LIP
.second
= LIP
.first
;
101 for (MachineBasicBlock::const_iterator I
= MBB
.end(), E
= MBB
.begin();
105 LIP
.second
= LIS
.getInstructionIndex(*I
);
111 // If CurLI is live into a landing pad successor, move the last insert point
112 // back to the call that may throw.
116 if (none_of(EHPadSuccessors
, [&](const MachineBasicBlock
*EHPad
) {
117 return LIS
.isLiveInToMBB(CurLI
, EHPad
);
121 // Find the value leaving MBB.
122 const VNInfo
*VNI
= CurLI
.getVNInfoBefore(MBBEnd
);
126 // If the value leaving MBB was defined after the call in MBB, it can't
127 // really be live-in to the landing pad. This can happen if the landing pad
128 // has a PHI, and this register is undef on the exceptional edge.
129 // <rdar://problem/10664933>
130 if (!SlotIndex::isEarlierInstr(VNI
->def
, LIP
.second
) && VNI
->def
< MBBEnd
)
133 // Value is properly live-in to the landing pad.
134 // Only allow inserts before the call.
138 MachineBasicBlock::iterator
139 InsertPointAnalysis::getLastInsertPointIter(const LiveInterval
&CurLI
,
140 MachineBasicBlock
&MBB
) {
141 SlotIndex LIP
= getLastInsertPoint(CurLI
, MBB
);
142 if (LIP
== LIS
.getMBBEndIdx(&MBB
))
144 return LIS
.getInstructionFromIndex(LIP
);
147 //===----------------------------------------------------------------------===//
149 //===----------------------------------------------------------------------===//
151 SplitAnalysis::SplitAnalysis(const VirtRegMap
&vrm
, const LiveIntervals
&lis
,
152 const MachineLoopInfo
&mli
)
153 : MF(vrm
.getMachineFunction()), VRM(vrm
), LIS(lis
), Loops(mli
),
154 TII(*MF
.getSubtarget().getInstrInfo()), IPA(lis
, MF
.getNumBlockIDs()) {}
156 void SplitAnalysis::clear() {
159 ThroughBlocks
.clear();
161 DidRepairRange
= false;
164 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
165 void SplitAnalysis::analyzeUses() {
166 assert(UseSlots
.empty() && "Call clear first");
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
);
174 // Get use slots form the use-def chain.
175 const MachineRegisterInfo
&MRI
= MF
.getRegInfo();
176 for (MachineOperand
&MO
: MRI
.use_nodbg_operands(CurLI
->reg
))
178 UseSlots
.push_back(LIS
.getInstructionIndex(*MO
.getParent()).getRegSlot());
180 array_pod_sort(UseSlots
.begin(), UseSlots
.end());
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(),
185 SlotIndex::isSameInstr
),
188 // Compute per-live block info.
189 if (!calcLiveBlockInfo()) {
190 // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
191 // I am looking at you, RegisterCoalescer!
192 DidRepairRange
= true;
194 LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
195 const_cast<LiveIntervals
&>(LIS
)
196 .shrinkToUses(const_cast<LiveInterval
*>(CurLI
));
198 ThroughBlocks
.clear();
199 bool fixed
= calcLiveBlockInfo();
201 assert(fixed
&& "Couldn't fix broken live interval");
204 LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots
.size() << " instrs in "
205 << UseBlocks
.size() << " blocks, through "
206 << NumThroughBlocks
<< " blocks.\n");
209 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
210 /// where CurLI is live.
211 bool SplitAnalysis::calcLiveBlockInfo() {
212 ThroughBlocks
.resize(MF
.getNumBlockIDs());
213 NumThroughBlocks
= NumGapBlocks
= 0;
217 LiveInterval::const_iterator LVI
= CurLI
->begin();
218 LiveInterval::const_iterator LVE
= CurLI
->end();
220 SmallVectorImpl
<SlotIndex
>::const_iterator UseI
, UseE
;
221 UseI
= UseSlots
.begin();
222 UseE
= UseSlots
.end();
224 // Loop over basic blocks where CurLI is live.
225 MachineFunction::iterator MFI
=
226 LIS
.getMBBFromIndex(LVI
->start
)->getIterator();
230 SlotIndex Start
, Stop
;
231 std::tie(Start
, Stop
) = LIS
.getSlotIndexes()->getMBBRange(BI
.MBB
);
233 // If the block contains no uses, the range must be live through. At one
234 // point, RegisterCoalescer could create dangling ranges that ended
236 if (UseI
== UseE
|| *UseI
>= Stop
) {
238 ThroughBlocks
.set(BI
.MBB
->getNumber());
239 // The range shouldn't end mid-block if there are no uses. This shouldn't
244 // This block has uses. Find the first and last uses in the block.
245 BI
.FirstInstr
= *UseI
;
246 assert(BI
.FirstInstr
>= Start
);
248 while (UseI
!= UseE
&& *UseI
< Stop
);
249 BI
.LastInstr
= UseI
[-1];
250 assert(BI
.LastInstr
< Stop
);
252 // LVI is the first live segment overlapping MBB.
253 BI
.LiveIn
= LVI
->start
<= Start
;
255 // When not live in, the first use should be a def.
257 assert(LVI
->start
== LVI
->valno
->def
&& "Dangling Segment start");
258 assert(LVI
->start
== BI
.FirstInstr
&& "First instr should be a def");
259 BI
.FirstDef
= BI
.FirstInstr
;
262 // Look for gaps in the live range.
264 while (LVI
->end
< Stop
) {
265 SlotIndex LastStop
= LVI
->end
;
266 if (++LVI
== LVE
|| LVI
->start
>= Stop
) {
268 BI
.LastInstr
= LastStop
;
272 if (LastStop
< LVI
->start
) {
273 // There is a gap in the live range. Create duplicate entries for the
274 // live-in snippet and the live-out snippet.
277 // Push the Live-in part.
279 UseBlocks
.push_back(BI
);
280 UseBlocks
.back().LastInstr
= LastStop
;
282 // Set up BI for the live-out part.
285 BI
.FirstInstr
= BI
.FirstDef
= LVI
->start
;
288 // A Segment that starts in the middle of the block must be a def.
289 assert(LVI
->start
== LVI
->valno
->def
&& "Dangling Segment start");
291 BI
.FirstDef
= LVI
->start
;
294 UseBlocks
.push_back(BI
);
296 // LVI is now at LVE or LVI->end >= Stop.
301 // Live segment ends exactly at Stop. Move to the next segment.
302 if (LVI
->end
== Stop
&& ++LVI
== LVE
)
305 // Pick the next basic block.
306 if (LVI
->start
< Stop
)
309 MFI
= LIS
.getMBBFromIndex(LVI
->start
)->getIterator();
312 assert(getNumLiveBlocks() == countLiveBlocks(CurLI
) && "Bad block count");
316 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval
*cli
) const {
319 LiveInterval
*li
= const_cast<LiveInterval
*>(cli
);
320 LiveInterval::iterator LVI
= li
->begin();
321 LiveInterval::iterator LVE
= li
->end();
324 // Loop over basic blocks where li is live.
325 MachineFunction::const_iterator MFI
=
326 LIS
.getMBBFromIndex(LVI
->start
)->getIterator();
327 SlotIndex Stop
= LIS
.getMBBEndIdx(&*MFI
);
330 LVI
= li
->advanceTo(LVI
, Stop
);
335 Stop
= LIS
.getMBBEndIdx(&*MFI
);
336 } while (Stop
<= LVI
->start
);
340 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx
) const {
341 unsigned OrigReg
= VRM
.getOriginal(CurLI
->reg
);
342 const LiveInterval
&Orig
= LIS
.getInterval(OrigReg
);
343 assert(!Orig
.empty() && "Splitting empty interval?");
344 LiveInterval::const_iterator I
= Orig
.find(Idx
);
346 // Range containing Idx should begin at Idx.
347 if (I
!= Orig
.end() && I
->start
<= Idx
)
348 return I
->start
== Idx
;
350 // Range does not contain Idx, previous must end at Idx.
351 return I
!= Orig
.begin() && (--I
)->end
== Idx
;
354 void SplitAnalysis::analyze(const LiveInterval
*li
) {
360 //===----------------------------------------------------------------------===//
362 //===----------------------------------------------------------------------===//
364 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
365 SplitEditor::SplitEditor(SplitAnalysis
&sa
, AliasAnalysis
&aa
,
366 LiveIntervals
&lis
, VirtRegMap
&vrm
,
367 MachineDominatorTree
&mdt
,
368 MachineBlockFrequencyInfo
&mbfi
)
369 : SA(sa
), AA(aa
), LIS(lis
), VRM(vrm
),
370 MRI(vrm
.getMachineFunction().getRegInfo()), MDT(mdt
),
371 TII(*vrm
.getMachineFunction().getSubtarget().getInstrInfo()),
372 TRI(*vrm
.getMachineFunction().getSubtarget().getRegisterInfo()),
373 MBFI(mbfi
), RegAssign(Allocator
) {}
375 void SplitEditor::reset(LiveRangeEdit
&LRE
, ComplementSpillMode SM
) {
382 // Reset the LiveRangeCalc instances needed for this spill mode.
383 LRCalc
[0].reset(&VRM
.getMachineFunction(), LIS
.getSlotIndexes(), &MDT
,
384 &LIS
.getVNInfoAllocator());
386 LRCalc
[1].reset(&VRM
.getMachineFunction(), LIS
.getSlotIndexes(), &MDT
,
387 &LIS
.getVNInfoAllocator());
389 // We don't need an AliasAnalysis since we will only be performing
390 // cheap-as-a-copy remats anyway.
391 Edit
->anyRematerializable(nullptr);
394 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
395 LLVM_DUMP_METHOD
void SplitEditor::dump() const {
396 if (RegAssign
.empty()) {
397 dbgs() << " empty\n";
401 for (RegAssignMap::const_iterator I
= RegAssign
.begin(); I
.valid(); ++I
)
402 dbgs() << " [" << I
.start() << ';' << I
.stop() << "):" << I
.value();
407 LiveInterval::SubRange
&SplitEditor::getSubRangeForMask(LaneBitmask LM
,
409 for (LiveInterval::SubRange
&S
: LI
.subranges())
410 if (S
.LaneMask
== LM
)
412 llvm_unreachable("SubRange for this mask not found");
415 void SplitEditor::addDeadDef(LiveInterval
&LI
, VNInfo
*VNI
, bool Original
) {
416 if (!LI
.hasSubRanges()) {
417 LI
.createDeadDef(VNI
);
421 SlotIndex Def
= VNI
->def
;
423 // If we are transferring a def from the original interval, make sure
424 // to only update the subranges for which the original subranges had
425 // a def at this location.
426 for (LiveInterval::SubRange
&S
: LI
.subranges()) {
427 auto &PS
= getSubRangeForMask(S
.LaneMask
, Edit
->getParent());
428 VNInfo
*PV
= PS
.getVNInfoAt(Def
);
429 if (PV
!= nullptr && PV
->def
== Def
)
430 S
.createDeadDef(Def
, LIS
.getVNInfoAllocator());
433 // This is a new def: either from rematerialization, or from an inserted
434 // copy. Since rematerialization can regenerate a definition of a sub-
435 // register, we need to check which subranges need to be updated.
436 const MachineInstr
*DefMI
= LIS
.getInstructionFromIndex(Def
);
437 assert(DefMI
!= nullptr);
439 for (const MachineOperand
&DefOp
: DefMI
->defs()) {
440 Register R
= DefOp
.getReg();
443 if (unsigned SR
= DefOp
.getSubReg())
444 LM
|= TRI
.getSubRegIndexLaneMask(SR
);
446 LM
= MRI
.getMaxLaneMaskForVReg(R
);
450 for (LiveInterval::SubRange
&S
: LI
.subranges())
451 if ((S
.LaneMask
& LM
).any())
452 S
.createDeadDef(Def
, LIS
.getVNInfoAllocator());
456 VNInfo
*SplitEditor::defValue(unsigned RegIdx
,
457 const VNInfo
*ParentVNI
,
460 assert(ParentVNI
&& "Mapping NULL value");
461 assert(Idx
.isValid() && "Invalid SlotIndex");
462 assert(Edit
->getParent().getVNInfoAt(Idx
) == ParentVNI
&& "Bad Parent VNI");
463 LiveInterval
*LI
= &LIS
.getInterval(Edit
->get(RegIdx
));
465 // Create a new value.
466 VNInfo
*VNI
= LI
->getNextValue(Idx
, LIS
.getVNInfoAllocator());
468 bool Force
= LI
->hasSubRanges();
469 ValueForcePair
FP(Force
? nullptr : VNI
, Force
);
470 // Use insert for lookup, so we can add missing values with a second lookup.
471 std::pair
<ValueMap::iterator
, bool> InsP
=
472 Values
.insert(std::make_pair(std::make_pair(RegIdx
, ParentVNI
->id
), FP
));
474 // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
475 // forced. Keep it as a simple def without any liveness.
476 if (!Force
&& InsP
.second
)
479 // If the previous value was a simple mapping, add liveness for it now.
480 if (VNInfo
*OldVNI
= InsP
.first
->second
.getPointer()) {
481 addDeadDef(*LI
, OldVNI
, Original
);
483 // No longer a simple mapping. Switch to a complex mapping. If the
484 // interval has subranges, make it a forced mapping.
485 InsP
.first
->second
= ValueForcePair(nullptr, Force
);
488 // This is a complex mapping, add liveness for VNI
489 addDeadDef(*LI
, VNI
, Original
);
493 void SplitEditor::forceRecompute(unsigned RegIdx
, const VNInfo
&ParentVNI
) {
494 ValueForcePair
&VFP
= Values
[std::make_pair(RegIdx
, ParentVNI
.id
)];
495 VNInfo
*VNI
= VFP
.getPointer();
497 // ParentVNI was either unmapped or already complex mapped. Either way, just
498 // set the force bit.
504 // This was previously a single mapping. Make sure the old def is represented
505 // by a trivial live range.
506 addDeadDef(LIS
.getInterval(Edit
->get(RegIdx
)), VNI
, false);
508 // Mark as complex mapped, forced.
509 VFP
= ValueForcePair(nullptr, true);
512 SlotIndex
SplitEditor::buildSingleSubRegCopy(unsigned FromReg
, unsigned ToReg
,
513 MachineBasicBlock
&MBB
, MachineBasicBlock::iterator InsertBefore
,
514 unsigned SubIdx
, LiveInterval
&DestLI
, bool Late
, SlotIndex Def
) {
515 const MCInstrDesc
&Desc
= TII
.get(TargetOpcode::COPY
);
516 bool FirstCopy
= !Def
.isValid();
517 MachineInstr
*CopyMI
= BuildMI(MBB
, InsertBefore
, DebugLoc(), Desc
)
518 .addReg(ToReg
, RegState::Define
| getUndefRegState(FirstCopy
)
519 | getInternalReadRegState(!FirstCopy
), SubIdx
)
520 .addReg(FromReg
, 0, SubIdx
);
522 BumpPtrAllocator
&Allocator
= LIS
.getVNInfoAllocator();
523 SlotIndexes
&Indexes
= *LIS
.getSlotIndexes();
525 Def
= Indexes
.insertMachineInstrInMaps(*CopyMI
, Late
).getRegSlot();
527 CopyMI
->bundleWithPred();
529 LaneBitmask LaneMask
= TRI
.getSubRegIndexLaneMask(SubIdx
);
530 DestLI
.refineSubRanges(Allocator
, LaneMask
,
531 [Def
, &Allocator
](LiveInterval::SubRange
&SR
) {
532 SR
.createDeadDef(Def
, Allocator
);
538 SlotIndex
SplitEditor::buildCopy(unsigned FromReg
, unsigned ToReg
,
539 LaneBitmask LaneMask
, MachineBasicBlock
&MBB
,
540 MachineBasicBlock::iterator InsertBefore
, bool Late
, unsigned RegIdx
) {
541 const MCInstrDesc
&Desc
= TII
.get(TargetOpcode::COPY
);
542 if (LaneMask
.all() || LaneMask
== MRI
.getMaxLaneMaskForVReg(FromReg
)) {
543 // The full vreg is copied.
544 MachineInstr
*CopyMI
=
545 BuildMI(MBB
, InsertBefore
, DebugLoc(), Desc
, ToReg
).addReg(FromReg
);
546 SlotIndexes
&Indexes
= *LIS
.getSlotIndexes();
547 return Indexes
.insertMachineInstrInMaps(*CopyMI
, Late
).getRegSlot();
550 // Only a subset of lanes needs to be copied. The following is a simple
551 // heuristic to construct a sequence of COPYs. We could add a target
552 // specific callback if this turns out to be suboptimal.
553 LiveInterval
&DestLI
= LIS
.getInterval(Edit
->get(RegIdx
));
555 // First pass: Try to find a perfectly matching subregister index. If none
556 // exists find the one covering the most lanemask bits.
557 SmallVector
<unsigned, 8> PossibleIndexes
;
558 unsigned BestIdx
= 0;
559 unsigned BestCover
= 0;
560 const TargetRegisterClass
*RC
= MRI
.getRegClass(FromReg
);
561 assert(RC
== MRI
.getRegClass(ToReg
) && "Should have same reg class");
562 for (unsigned Idx
= 1, E
= TRI
.getNumSubRegIndices(); Idx
< E
; ++Idx
) {
563 // Is this index even compatible with the given class?
564 if (TRI
.getSubClassWithSubReg(RC
, Idx
) != RC
)
566 LaneBitmask SubRegMask
= TRI
.getSubRegIndexLaneMask(Idx
);
567 // Early exit if we found a perfect match.
568 if (SubRegMask
== LaneMask
) {
573 // The index must not cover any lanes outside \p LaneMask.
574 if ((SubRegMask
& ~LaneMask
).any())
577 unsigned PopCount
= SubRegMask
.getNumLanes();
578 PossibleIndexes
.push_back(Idx
);
579 if (PopCount
> BestCover
) {
580 BestCover
= PopCount
;
585 // Abort if we cannot possibly implement the COPY with the given indexes.
587 report_fatal_error("Impossible to implement partial COPY");
589 SlotIndex Def
= buildSingleSubRegCopy(FromReg
, ToReg
, MBB
, InsertBefore
,
590 BestIdx
, DestLI
, Late
, SlotIndex());
592 // Greedy heuristic: Keep iterating keeping the best covering subreg index
594 LaneBitmask LanesLeft
= LaneMask
& ~(TRI
.getSubRegIndexLaneMask(BestIdx
));
595 while (LanesLeft
.any()) {
596 unsigned BestIdx
= 0;
597 int BestCover
= std::numeric_limits
<int>::min();
598 for (unsigned Idx
: PossibleIndexes
) {
599 LaneBitmask SubRegMask
= TRI
.getSubRegIndexLaneMask(Idx
);
600 // Early exit if we found a perfect match.
601 if (SubRegMask
== LanesLeft
) {
606 // Try to cover as much of the remaining lanes as possible but
607 // as few of the already covered lanes as possible.
608 int Cover
= (SubRegMask
& LanesLeft
).getNumLanes()
609 - (SubRegMask
& ~LanesLeft
).getNumLanes();
610 if (Cover
> BestCover
) {
617 report_fatal_error("Impossible to implement partial COPY");
619 buildSingleSubRegCopy(FromReg
, ToReg
, MBB
, InsertBefore
, BestIdx
,
621 LanesLeft
&= ~TRI
.getSubRegIndexLaneMask(BestIdx
);
627 VNInfo
*SplitEditor::defFromParent(unsigned RegIdx
,
630 MachineBasicBlock
&MBB
,
631 MachineBasicBlock::iterator I
) {
633 LiveInterval
*LI
= &LIS
.getInterval(Edit
->get(RegIdx
));
635 // We may be trying to avoid interference that ends at a deleted instruction,
636 // so always begin RegIdx 0 early and all others late.
637 bool Late
= RegIdx
!= 0;
639 // Attempt cheap-as-a-copy rematerialization.
640 unsigned Original
= VRM
.getOriginal(Edit
->get(RegIdx
));
641 LiveInterval
&OrigLI
= LIS
.getInterval(Original
);
642 VNInfo
*OrigVNI
= OrigLI
.getVNInfoAt(UseIdx
);
644 unsigned Reg
= LI
->reg
;
645 bool DidRemat
= false;
647 LiveRangeEdit::Remat
RM(ParentVNI
);
648 RM
.OrigMI
= LIS
.getInstructionFromIndex(OrigVNI
->def
);
649 if (Edit
->canRematerializeAt(RM
, OrigVNI
, UseIdx
, true)) {
650 Def
= Edit
->rematerializeAt(MBB
, I
, Reg
, RM
, TRI
, Late
);
656 LaneBitmask LaneMask
;
657 if (LI
->hasSubRanges()) {
658 LaneMask
= LaneBitmask::getNone();
659 for (LiveInterval::SubRange
&S
: LI
->subranges())
660 LaneMask
|= S
.LaneMask
;
662 LaneMask
= LaneBitmask::getAll();
666 Def
= buildCopy(Edit
->getReg(), Reg
, LaneMask
, MBB
, I
, Late
, RegIdx
);
669 // Define the value in Reg.
670 return defValue(RegIdx
, ParentVNI
, Def
, false);
673 /// Create a new virtual register and live interval.
674 unsigned SplitEditor::openIntv() {
675 // Create the complement as index 0.
677 Edit
->createEmptyInterval();
679 // Create the open interval.
680 OpenIdx
= Edit
->size();
681 Edit
->createEmptyInterval();
685 void SplitEditor::selectIntv(unsigned Idx
) {
686 assert(Idx
!= 0 && "Cannot select the complement interval");
687 assert(Idx
< Edit
->size() && "Can only select previously opened interval");
688 LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx
<< " -> " << Idx
<< '\n');
692 SlotIndex
SplitEditor::enterIntvBefore(SlotIndex Idx
) {
693 assert(OpenIdx
&& "openIntv not called before enterIntvBefore");
694 LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx
);
695 Idx
= Idx
.getBaseIndex();
696 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Idx
);
698 LLVM_DEBUG(dbgs() << ": not live\n");
701 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI
->id
<< '\n');
702 MachineInstr
*MI
= LIS
.getInstructionFromIndex(Idx
);
703 assert(MI
&& "enterIntvBefore called with invalid index");
705 VNInfo
*VNI
= defFromParent(OpenIdx
, ParentVNI
, Idx
, *MI
->getParent(), MI
);
709 SlotIndex
SplitEditor::enterIntvAfter(SlotIndex Idx
) {
710 assert(OpenIdx
&& "openIntv not called before enterIntvAfter");
711 LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx
);
712 Idx
= Idx
.getBoundaryIndex();
713 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Idx
);
715 LLVM_DEBUG(dbgs() << ": not live\n");
718 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI
->id
<< '\n');
719 MachineInstr
*MI
= LIS
.getInstructionFromIndex(Idx
);
720 assert(MI
&& "enterIntvAfter called with invalid index");
722 VNInfo
*VNI
= defFromParent(OpenIdx
, ParentVNI
, Idx
, *MI
->getParent(),
723 std::next(MachineBasicBlock::iterator(MI
)));
727 SlotIndex
SplitEditor::enterIntvAtEnd(MachineBasicBlock
&MBB
) {
728 assert(OpenIdx
&& "openIntv not called before enterIntvAtEnd");
729 SlotIndex End
= LIS
.getMBBEndIdx(&MBB
);
730 SlotIndex Last
= End
.getPrevSlot();
731 LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB
) << ", "
733 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Last
);
735 LLVM_DEBUG(dbgs() << ": not live\n");
738 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI
->id
);
739 VNInfo
*VNI
= defFromParent(OpenIdx
, ParentVNI
, Last
, MBB
,
740 SA
.getLastSplitPointIter(&MBB
));
741 RegAssign
.insert(VNI
->def
, End
, OpenIdx
);
746 /// useIntv - indicate that all instructions in MBB should use OpenLI.
747 void SplitEditor::useIntv(const MachineBasicBlock
&MBB
) {
748 useIntv(LIS
.getMBBStartIdx(&MBB
), LIS
.getMBBEndIdx(&MBB
));
751 void SplitEditor::useIntv(SlotIndex Start
, SlotIndex End
) {
752 assert(OpenIdx
&& "openIntv not called before useIntv");
753 LLVM_DEBUG(dbgs() << " useIntv [" << Start
<< ';' << End
<< "):");
754 RegAssign
.insert(Start
, End
, OpenIdx
);
758 SlotIndex
SplitEditor::leaveIntvAfter(SlotIndex Idx
) {
759 assert(OpenIdx
&& "openIntv not called before leaveIntvAfter");
760 LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx
);
762 // The interval must be live beyond the instruction at Idx.
763 SlotIndex Boundary
= Idx
.getBoundaryIndex();
764 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Boundary
);
766 LLVM_DEBUG(dbgs() << ": not live\n");
767 return Boundary
.getNextSlot();
769 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI
->id
<< '\n');
770 MachineInstr
*MI
= LIS
.getInstructionFromIndex(Boundary
);
771 assert(MI
&& "No instruction at index");
773 // In spill mode, make live ranges as short as possible by inserting the copy
774 // before MI. This is only possible if that instruction doesn't redefine the
775 // value. The inserted COPY is not a kill, and we don't need to recompute
776 // the source live range. The spiller also won't try to hoist this copy.
777 if (SpillMode
&& !SlotIndex::isSameInstr(ParentVNI
->def
, Idx
) &&
778 MI
->readsVirtualRegister(Edit
->getReg())) {
779 forceRecompute(0, *ParentVNI
);
780 defFromParent(0, ParentVNI
, Idx
, *MI
->getParent(), MI
);
784 VNInfo
*VNI
= defFromParent(0, ParentVNI
, Boundary
, *MI
->getParent(),
785 std::next(MachineBasicBlock::iterator(MI
)));
789 SlotIndex
SplitEditor::leaveIntvBefore(SlotIndex Idx
) {
790 assert(OpenIdx
&& "openIntv not called before leaveIntvBefore");
791 LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx
);
793 // The interval must be live into the instruction at Idx.
794 Idx
= Idx
.getBaseIndex();
795 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Idx
);
797 LLVM_DEBUG(dbgs() << ": not live\n");
798 return Idx
.getNextSlot();
800 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI
->id
<< '\n');
802 MachineInstr
*MI
= LIS
.getInstructionFromIndex(Idx
);
803 assert(MI
&& "No instruction at index");
804 VNInfo
*VNI
= defFromParent(0, ParentVNI
, Idx
, *MI
->getParent(), MI
);
808 SlotIndex
SplitEditor::leaveIntvAtTop(MachineBasicBlock
&MBB
) {
809 assert(OpenIdx
&& "openIntv not called before leaveIntvAtTop");
810 SlotIndex Start
= LIS
.getMBBStartIdx(&MBB
);
811 LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB
) << ", "
814 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Start
);
816 LLVM_DEBUG(dbgs() << ": not live\n");
820 VNInfo
*VNI
= defFromParent(0, ParentVNI
, Start
, MBB
,
821 MBB
.SkipPHIsLabelsAndDebug(MBB
.begin()));
822 RegAssign
.insert(Start
, VNI
->def
, OpenIdx
);
827 void SplitEditor::overlapIntv(SlotIndex Start
, SlotIndex End
) {
828 assert(OpenIdx
&& "openIntv not called before overlapIntv");
829 const VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(Start
);
830 assert(ParentVNI
== Edit
->getParent().getVNInfoBefore(End
) &&
831 "Parent changes value in extended range");
832 assert(LIS
.getMBBFromIndex(Start
) == LIS
.getMBBFromIndex(End
) &&
833 "Range cannot span basic blocks");
835 // The complement interval will be extended as needed by LRCalc.extend().
837 forceRecompute(0, *ParentVNI
);
838 LLVM_DEBUG(dbgs() << " overlapIntv [" << Start
<< ';' << End
<< "):");
839 RegAssign
.insert(Start
, End
, OpenIdx
);
843 //===----------------------------------------------------------------------===//
845 //===----------------------------------------------------------------------===//
847 void SplitEditor::removeBackCopies(SmallVectorImpl
<VNInfo
*> &Copies
) {
848 LiveInterval
*LI
= &LIS
.getInterval(Edit
->get(0));
849 LLVM_DEBUG(dbgs() << "Removing " << Copies
.size() << " back-copies.\n");
850 RegAssignMap::iterator AssignI
;
851 AssignI
.setMap(RegAssign
);
853 for (unsigned i
= 0, e
= Copies
.size(); i
!= e
; ++i
) {
854 SlotIndex Def
= Copies
[i
]->def
;
855 MachineInstr
*MI
= LIS
.getInstructionFromIndex(Def
);
856 assert(MI
&& "No instruction for back-copy");
858 MachineBasicBlock
*MBB
= MI
->getParent();
859 MachineBasicBlock::iterator
MBBI(MI
);
861 do AtBegin
= MBBI
== MBB
->begin();
862 while (!AtBegin
&& (--MBBI
)->isDebugInstr());
864 LLVM_DEBUG(dbgs() << "Removing " << Def
<< '\t' << *MI
);
865 LIS
.removeVRegDefAt(*LI
, Def
);
866 LIS
.RemoveMachineInstrFromMaps(*MI
);
867 MI
->eraseFromParent();
869 // Adjust RegAssign if a register assignment is killed at Def. We want to
870 // avoid calculating the live range of the source register if possible.
871 AssignI
.find(Def
.getPrevSlot());
872 if (!AssignI
.valid() || AssignI
.start() >= Def
)
874 // If MI doesn't kill the assigned register, just leave it.
875 if (AssignI
.stop() != Def
)
877 unsigned RegIdx
= AssignI
.value();
878 if (AtBegin
|| !MBBI
->readsVirtualRegister(Edit
->getReg())) {
879 LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx
881 forceRecompute(RegIdx
, *Edit
->getParent().getVNInfoAt(Def
));
883 SlotIndex Kill
= LIS
.getInstructionIndex(*MBBI
).getRegSlot();
884 LLVM_DEBUG(dbgs() << " move kill to " << Kill
<< '\t' << *MBBI
);
885 AssignI
.setStop(Kill
);
891 SplitEditor::findShallowDominator(MachineBasicBlock
*MBB
,
892 MachineBasicBlock
*DefMBB
) {
895 assert(MDT
.dominates(DefMBB
, MBB
) && "MBB must be dominated by the def.");
897 const MachineLoopInfo
&Loops
= SA
.Loops
;
898 const MachineLoop
*DefLoop
= Loops
.getLoopFor(DefMBB
);
899 MachineDomTreeNode
*DefDomNode
= MDT
[DefMBB
];
901 // Best candidate so far.
902 MachineBasicBlock
*BestMBB
= MBB
;
903 unsigned BestDepth
= std::numeric_limits
<unsigned>::max();
906 const MachineLoop
*Loop
= Loops
.getLoopFor(MBB
);
908 // MBB isn't in a loop, it doesn't get any better. All dominators have a
909 // higher frequency by definition.
911 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB
)
912 << " dominates " << printMBBReference(*MBB
)
917 // We'll never be able to exit the DefLoop.
918 if (Loop
== DefLoop
) {
919 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB
)
920 << " dominates " << printMBBReference(*MBB
)
921 << " in the same loop\n");
925 // Least busy dominator seen so far.
926 unsigned Depth
= Loop
->getLoopDepth();
927 if (Depth
< BestDepth
) {
930 LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB
)
931 << " dominates " << printMBBReference(*MBB
)
932 << " at depth " << Depth
<< '\n');
935 // Leave loop by going to the immediate dominator of the loop header.
936 // This is a bigger stride than simply walking up the dominator tree.
937 MachineDomTreeNode
*IDom
= MDT
[Loop
->getHeader()]->getIDom();
939 // Too far up the dominator tree?
940 if (!IDom
|| !MDT
.dominates(DefDomNode
, IDom
))
943 MBB
= IDom
->getBlock();
947 void SplitEditor::computeRedundantBackCopies(
948 DenseSet
<unsigned> &NotToHoistSet
, SmallVectorImpl
<VNInfo
*> &BackCopies
) {
949 LiveInterval
*LI
= &LIS
.getInterval(Edit
->get(0));
950 LiveInterval
*Parent
= &Edit
->getParent();
951 SmallVector
<SmallPtrSet
<VNInfo
*, 8>, 8> EqualVNs(Parent
->getNumValNums());
952 SmallPtrSet
<VNInfo
*, 8> DominatedVNIs
;
954 // Aggregate VNIs having the same value as ParentVNI.
955 for (VNInfo
*VNI
: LI
->valnos
) {
958 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(VNI
->def
);
959 EqualVNs
[ParentVNI
->id
].insert(VNI
);
962 // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
963 // redundant VNIs to BackCopies.
964 for (unsigned i
= 0, e
= Parent
->getNumValNums(); i
!= e
; ++i
) {
965 VNInfo
*ParentVNI
= Parent
->getValNumInfo(i
);
966 if (!NotToHoistSet
.count(ParentVNI
->id
))
968 SmallPtrSetIterator
<VNInfo
*> It1
= EqualVNs
[ParentVNI
->id
].begin();
969 SmallPtrSetIterator
<VNInfo
*> It2
= It1
;
970 for (; It1
!= EqualVNs
[ParentVNI
->id
].end(); ++It1
) {
972 for (++It2
; It2
!= EqualVNs
[ParentVNI
->id
].end(); ++It2
) {
973 if (DominatedVNIs
.count(*It1
) || DominatedVNIs
.count(*It2
))
976 MachineBasicBlock
*MBB1
= LIS
.getMBBFromIndex((*It1
)->def
);
977 MachineBasicBlock
*MBB2
= LIS
.getMBBFromIndex((*It2
)->def
);
979 DominatedVNIs
.insert((*It1
)->def
< (*It2
)->def
? (*It2
) : (*It1
));
980 } else if (MDT
.dominates(MBB1
, MBB2
)) {
981 DominatedVNIs
.insert(*It2
);
982 } else if (MDT
.dominates(MBB2
, MBB1
)) {
983 DominatedVNIs
.insert(*It1
);
987 if (!DominatedVNIs
.empty()) {
988 forceRecompute(0, *ParentVNI
);
989 for (auto VNI
: DominatedVNIs
) {
990 BackCopies
.push_back(VNI
);
992 DominatedVNIs
.clear();
997 /// For SM_Size mode, find a common dominator for all the back-copies for
998 /// the same ParentVNI and hoist the backcopies to the dominator BB.
999 /// For SM_Speed mode, if the common dominator is hot and it is not beneficial
1000 /// to do the hoisting, simply remove the dominated backcopies for the same
1002 void SplitEditor::hoistCopies() {
1003 // Get the complement interval, always RegIdx 0.
1004 LiveInterval
*LI
= &LIS
.getInterval(Edit
->get(0));
1005 LiveInterval
*Parent
= &Edit
->getParent();
1007 // Track the nearest common dominator for all back-copies for each ParentVNI,
1008 // indexed by ParentVNI->id.
1009 using DomPair
= std::pair
<MachineBasicBlock
*, SlotIndex
>;
1010 SmallVector
<DomPair
, 8> NearestDom(Parent
->getNumValNums());
1011 // The total cost of all the back-copies for each ParentVNI.
1012 SmallVector
<BlockFrequency
, 8> Costs(Parent
->getNumValNums());
1013 // The ParentVNI->id set for which hoisting back-copies are not beneficial
1015 DenseSet
<unsigned> NotToHoistSet
;
1017 // Find the nearest common dominator for parent values with multiple
1018 // back-copies. If a single back-copy dominates, put it in DomPair.second.
1019 for (VNInfo
*VNI
: LI
->valnos
) {
1020 if (VNI
->isUnused())
1022 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(VNI
->def
);
1023 assert(ParentVNI
&& "Parent not live at complement def");
1025 // Don't hoist remats. The complement is probably going to disappear
1026 // completely anyway.
1027 if (Edit
->didRematerialize(ParentVNI
))
1030 MachineBasicBlock
*ValMBB
= LIS
.getMBBFromIndex(VNI
->def
);
1032 DomPair
&Dom
= NearestDom
[ParentVNI
->id
];
1034 // Keep directly defined parent values. This is either a PHI or an
1035 // instruction in the complement range. All other copies of ParentVNI
1036 // should be eliminated.
1037 if (VNI
->def
== ParentVNI
->def
) {
1038 LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI
->def
<< '\n');
1039 Dom
= DomPair(ValMBB
, VNI
->def
);
1042 // Skip the singly mapped values. There is nothing to gain from hoisting a
1043 // single back-copy.
1044 if (Values
.lookup(std::make_pair(0, ParentVNI
->id
)).getPointer()) {
1045 LLVM_DEBUG(dbgs() << "Single complement def at " << VNI
->def
<< '\n');
1050 // First time we see ParentVNI. VNI dominates itself.
1051 Dom
= DomPair(ValMBB
, VNI
->def
);
1052 } else if (Dom
.first
== ValMBB
) {
1053 // Two defs in the same block. Pick the earlier def.
1054 if (!Dom
.second
.isValid() || VNI
->def
< Dom
.second
)
1055 Dom
.second
= VNI
->def
;
1057 // Different basic blocks. Check if one dominates.
1058 MachineBasicBlock
*Near
=
1059 MDT
.findNearestCommonDominator(Dom
.first
, ValMBB
);
1061 // Def ValMBB dominates.
1062 Dom
= DomPair(ValMBB
, VNI
->def
);
1063 else if (Near
!= Dom
.first
)
1064 // None dominate. Hoist to common dominator, need new def.
1065 Dom
= DomPair(Near
, SlotIndex());
1066 Costs
[ParentVNI
->id
] += MBFI
.getBlockFreq(ValMBB
);
1069 LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI
->id
<< '@'
1070 << VNI
->def
<< " for parent " << ParentVNI
->id
<< '@'
1071 << ParentVNI
->def
<< " hoist to "
1072 << printMBBReference(*Dom
.first
) << ' ' << Dom
.second
1076 // Insert the hoisted copies.
1077 for (unsigned i
= 0, e
= Parent
->getNumValNums(); i
!= e
; ++i
) {
1078 DomPair
&Dom
= NearestDom
[i
];
1079 if (!Dom
.first
|| Dom
.second
.isValid())
1081 // This value needs a hoisted copy inserted at the end of Dom.first.
1082 VNInfo
*ParentVNI
= Parent
->getValNumInfo(i
);
1083 MachineBasicBlock
*DefMBB
= LIS
.getMBBFromIndex(ParentVNI
->def
);
1084 // Get a less loopy dominator than Dom.first.
1085 Dom
.first
= findShallowDominator(Dom
.first
, DefMBB
);
1086 if (SpillMode
== SM_Speed
&&
1087 MBFI
.getBlockFreq(Dom
.first
) > Costs
[ParentVNI
->id
]) {
1088 NotToHoistSet
.insert(ParentVNI
->id
);
1091 SlotIndex Last
= LIS
.getMBBEndIdx(Dom
.first
).getPrevSlot();
1093 defFromParent(0, ParentVNI
, Last
, *Dom
.first
,
1094 SA
.getLastSplitPointIter(Dom
.first
))->def
;
1097 // Remove redundant back-copies that are now known to be dominated by another
1098 // def with the same value.
1099 SmallVector
<VNInfo
*, 8> BackCopies
;
1100 for (VNInfo
*VNI
: LI
->valnos
) {
1101 if (VNI
->isUnused())
1103 VNInfo
*ParentVNI
= Edit
->getParent().getVNInfoAt(VNI
->def
);
1104 const DomPair
&Dom
= NearestDom
[ParentVNI
->id
];
1105 if (!Dom
.first
|| Dom
.second
== VNI
->def
||
1106 NotToHoistSet
.count(ParentVNI
->id
))
1108 BackCopies
.push_back(VNI
);
1109 forceRecompute(0, *ParentVNI
);
1112 // If it is not beneficial to hoist all the BackCopies, simply remove
1113 // redundant BackCopies in speed mode.
1114 if (SpillMode
== SM_Speed
&& !NotToHoistSet
.empty())
1115 computeRedundantBackCopies(NotToHoistSet
, BackCopies
);
1117 removeBackCopies(BackCopies
);
1120 /// transferValues - Transfer all possible values to the new live ranges.
1121 /// Values that were rematerialized are left alone, they need LRCalc.extend().
1122 bool SplitEditor::transferValues() {
1123 bool Skipped
= false;
1124 RegAssignMap::const_iterator AssignI
= RegAssign
.begin();
1125 for (const LiveRange::Segment
&S
: Edit
->getParent()) {
1126 LLVM_DEBUG(dbgs() << " blit " << S
<< ':');
1127 VNInfo
*ParentVNI
= S
.valno
;
1128 // RegAssign has holes where RegIdx 0 should be used.
1129 SlotIndex Start
= S
.start
;
1130 AssignI
.advanceTo(Start
);
1133 SlotIndex End
= S
.end
;
1134 if (!AssignI
.valid()) {
1136 } else if (AssignI
.start() <= Start
) {
1137 RegIdx
= AssignI
.value();
1138 if (AssignI
.stop() < End
) {
1139 End
= AssignI
.stop();
1144 End
= std::min(End
, AssignI
.start());
1147 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1148 LLVM_DEBUG(dbgs() << " [" << Start
<< ';' << End
<< ")=" << RegIdx
<< '('
1149 << printReg(Edit
->get(RegIdx
)) << ')');
1150 LiveInterval
&LI
= LIS
.getInterval(Edit
->get(RegIdx
));
1152 // Check for a simply defined value that can be blitted directly.
1153 ValueForcePair VFP
= Values
.lookup(std::make_pair(RegIdx
, ParentVNI
->id
));
1154 if (VNInfo
*VNI
= VFP
.getPointer()) {
1155 LLVM_DEBUG(dbgs() << ':' << VNI
->id
);
1156 LI
.addSegment(LiveInterval::Segment(Start
, End
, VNI
));
1161 // Skip values with forced recomputation.
1163 LLVM_DEBUG(dbgs() << "(recalc)");
1169 LiveRangeCalc
&LRC
= getLRCalc(RegIdx
);
1171 // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1172 // so the live range is accurate. Add live-in blocks in [Start;End) to the
1174 MachineFunction::iterator MBB
= LIS
.getMBBFromIndex(Start
)->getIterator();
1175 SlotIndex BlockStart
, BlockEnd
;
1176 std::tie(BlockStart
, BlockEnd
) = LIS
.getSlotIndexes()->getMBBRange(&*MBB
);
1178 // The first block may be live-in, or it may have its own def.
1179 if (Start
!= BlockStart
) {
1180 VNInfo
*VNI
= LI
.extendInBlock(BlockStart
, std::min(BlockEnd
, End
));
1181 assert(VNI
&& "Missing def for complex mapped value");
1182 LLVM_DEBUG(dbgs() << ':' << VNI
->id
<< "*" << printMBBReference(*MBB
));
1183 // MBB has its own def. Is it also live-out?
1184 if (BlockEnd
<= End
)
1185 LRC
.setLiveOutValue(&*MBB
, VNI
);
1187 // Skip to the next block for live-in.
1189 BlockStart
= BlockEnd
;
1192 // Handle the live-in blocks covered by [Start;End).
1193 assert(Start
<= BlockStart
&& "Expected live-in block");
1194 while (BlockStart
< End
) {
1195 LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB
));
1196 BlockEnd
= LIS
.getMBBEndIdx(&*MBB
);
1197 if (BlockStart
== ParentVNI
->def
) {
1198 // This block has the def of a parent PHI, so it isn't live-in.
1199 assert(ParentVNI
->isPHIDef() && "Non-phi defined at block start?");
1200 VNInfo
*VNI
= LI
.extendInBlock(BlockStart
, std::min(BlockEnd
, End
));
1201 assert(VNI
&& "Missing def for complex mapped parent PHI");
1202 if (End
>= BlockEnd
)
1203 LRC
.setLiveOutValue(&*MBB
, VNI
); // Live-out as well.
1205 // This block needs a live-in value. The last block covered may not
1208 LRC
.addLiveInBlock(LI
, MDT
[&*MBB
], End
);
1210 // Live-through, and we don't know the value.
1211 LRC
.addLiveInBlock(LI
, MDT
[&*MBB
]);
1212 LRC
.setLiveOutValue(&*MBB
, nullptr);
1215 BlockStart
= BlockEnd
;
1219 } while (Start
!= S
.end
);
1220 LLVM_DEBUG(dbgs() << '\n');
1223 LRCalc
[0].calculateValues();
1225 LRCalc
[1].calculateValues();
1230 static bool removeDeadSegment(SlotIndex Def
, LiveRange
&LR
) {
1231 const LiveRange::Segment
*Seg
= LR
.getSegmentContaining(Def
);
1234 if (Seg
->end
!= Def
.getDeadSlot())
1236 // This is a dead PHI. Remove it.
1237 LR
.removeSegment(*Seg
, true);
1241 void SplitEditor::extendPHIRange(MachineBasicBlock
&B
, LiveRangeCalc
&LRC
,
1242 LiveRange
&LR
, LaneBitmask LM
,
1243 ArrayRef
<SlotIndex
> Undefs
) {
1244 for (MachineBasicBlock
*P
: B
.predecessors()) {
1245 SlotIndex End
= LIS
.getMBBEndIdx(P
);
1246 SlotIndex LastUse
= End
.getPrevSlot();
1247 // The predecessor may not have a live-out value. That is OK, like an
1248 // undef PHI operand.
1249 LiveInterval
&PLI
= Edit
->getParent();
1250 // Need the cast because the inputs to ?: would otherwise be deemed
1251 // "incompatible": SubRange vs LiveInterval.
1252 LiveRange
&PSR
= !LM
.all() ? getSubRangeForMask(LM
, PLI
)
1253 : static_cast<LiveRange
&>(PLI
);
1254 if (PSR
.liveAt(LastUse
))
1255 LRC
.extend(LR
, End
, /*PhysReg=*/0, Undefs
);
1259 void SplitEditor::extendPHIKillRanges() {
1260 // Extend live ranges to be live-out for successor PHI values.
1262 // Visit each PHI def slot in the parent live interval. If the def is dead,
1263 // remove it. Otherwise, extend the live interval to reach the end indexes
1264 // of all predecessor blocks.
1266 LiveInterval
&ParentLI
= Edit
->getParent();
1267 for (const VNInfo
*V
: ParentLI
.valnos
) {
1268 if (V
->isUnused() || !V
->isPHIDef())
1271 unsigned RegIdx
= RegAssign
.lookup(V
->def
);
1272 LiveInterval
&LI
= LIS
.getInterval(Edit
->get(RegIdx
));
1273 LiveRangeCalc
&LRC
= getLRCalc(RegIdx
);
1274 MachineBasicBlock
&B
= *LIS
.getMBBFromIndex(V
->def
);
1275 if (!removeDeadSegment(V
->def
, LI
))
1276 extendPHIRange(B
, LRC
, LI
, LaneBitmask::getAll(), /*Undefs=*/{});
1279 SmallVector
<SlotIndex
, 4> Undefs
;
1280 LiveRangeCalc SubLRC
;
1282 for (LiveInterval::SubRange
&PS
: ParentLI
.subranges()) {
1283 for (const VNInfo
*V
: PS
.valnos
) {
1284 if (V
->isUnused() || !V
->isPHIDef())
1286 unsigned RegIdx
= RegAssign
.lookup(V
->def
);
1287 LiveInterval
&LI
= LIS
.getInterval(Edit
->get(RegIdx
));
1288 LiveInterval::SubRange
&S
= getSubRangeForMask(PS
.LaneMask
, LI
);
1289 if (removeDeadSegment(V
->def
, S
))
1292 MachineBasicBlock
&B
= *LIS
.getMBBFromIndex(V
->def
);
1293 SubLRC
.reset(&VRM
.getMachineFunction(), LIS
.getSlotIndexes(), &MDT
,
1294 &LIS
.getVNInfoAllocator());
1296 LI
.computeSubRangeUndefs(Undefs
, PS
.LaneMask
, MRI
, *LIS
.getSlotIndexes());
1297 extendPHIRange(B
, SubLRC
, S
, PS
.LaneMask
, Undefs
);
1302 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1303 void SplitEditor::rewriteAssigned(bool ExtendRanges
) {
1305 ExtPoint(const MachineOperand
&O
, unsigned R
, SlotIndex N
)
1306 : MO(O
), RegIdx(R
), Next(N
) {}
1313 SmallVector
<ExtPoint
,4> ExtPoints
;
1315 for (MachineRegisterInfo::reg_iterator RI
= MRI
.reg_begin(Edit
->getReg()),
1316 RE
= MRI
.reg_end(); RI
!= RE
;) {
1317 MachineOperand
&MO
= *RI
;
1318 MachineInstr
*MI
= MO
.getParent();
1320 // LiveDebugVariables should have handled all DBG_VALUE instructions.
1321 if (MI
->isDebugValue()) {
1322 LLVM_DEBUG(dbgs() << "Zapping " << *MI
);
1327 // <undef> operands don't really read the register, so it doesn't matter
1328 // which register we choose. When the use operand is tied to a def, we must
1329 // use the same register as the def, so just do that always.
1330 SlotIndex Idx
= LIS
.getInstructionIndex(*MI
);
1331 if (MO
.isDef() || MO
.isUndef())
1332 Idx
= Idx
.getRegSlot(MO
.isEarlyClobber());
1334 // Rewrite to the mapped register at Idx.
1335 unsigned RegIdx
= RegAssign
.lookup(Idx
);
1336 LiveInterval
&LI
= LIS
.getInterval(Edit
->get(RegIdx
));
1338 LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI
->getParent())
1339 << '\t' << Idx
<< ':' << RegIdx
<< '\t' << *MI
);
1341 // Extend liveness to Idx if the instruction reads reg.
1342 if (!ExtendRanges
|| MO
.isUndef())
1345 // Skip instructions that don't read Reg.
1347 if (!MO
.getSubReg() && !MO
.isEarlyClobber())
1349 // We may want to extend a live range for a partial redef, or for a use
1350 // tied to an early clobber.
1351 Idx
= Idx
.getPrevSlot();
1352 if (!Edit
->getParent().liveAt(Idx
))
1355 Idx
= Idx
.getRegSlot(true);
1357 SlotIndex Next
= Idx
.getNextSlot();
1358 if (LI
.hasSubRanges()) {
1359 // We have to delay extending subranges until we have seen all operands
1360 // defining the register. This is because a <def,read-undef> operand
1361 // will create an "undef" point, and we cannot extend any subranges
1362 // until all of them have been accounted for.
1364 ExtPoints
.push_back(ExtPoint(MO
, RegIdx
, Next
));
1366 LiveRangeCalc
&LRC
= getLRCalc(RegIdx
);
1367 LRC
.extend(LI
, Next
, 0, ArrayRef
<SlotIndex
>());
1371 for (ExtPoint
&EP
: ExtPoints
) {
1372 LiveInterval
&LI
= LIS
.getInterval(Edit
->get(EP
.RegIdx
));
1373 assert(LI
.hasSubRanges());
1375 LiveRangeCalc SubLRC
;
1376 Register Reg
= EP
.MO
.getReg(), Sub
= EP
.MO
.getSubReg();
1377 LaneBitmask LM
= Sub
!= 0 ? TRI
.getSubRegIndexLaneMask(Sub
)
1378 : MRI
.getMaxLaneMaskForVReg(Reg
);
1379 for (LiveInterval::SubRange
&S
: LI
.subranges()) {
1380 if ((S
.LaneMask
& LM
).none())
1382 // The problem here can be that the new register may have been created
1383 // for a partially defined original register. For example:
1384 // %0:subreg_hireg<def,read-undef> = ...
1389 SubLRC
.reset(&VRM
.getMachineFunction(), LIS
.getSlotIndexes(), &MDT
,
1390 &LIS
.getVNInfoAllocator());
1391 SmallVector
<SlotIndex
, 4> Undefs
;
1392 LI
.computeSubRangeUndefs(Undefs
, S
.LaneMask
, MRI
, *LIS
.getSlotIndexes());
1393 SubLRC
.extend(S
, EP
.Next
, 0, Undefs
);
1397 for (unsigned R
: *Edit
) {
1398 LiveInterval
&LI
= LIS
.getInterval(R
);
1399 if (!LI
.hasSubRanges())
1402 LI
.removeEmptySubRanges();
1403 LIS
.constructMainRangeFromSubranges(LI
);
1407 void SplitEditor::deleteRematVictims() {
1408 SmallVector
<MachineInstr
*, 8> Dead
;
1409 for (LiveRangeEdit::iterator I
= Edit
->begin(), E
= Edit
->end(); I
!= E
; ++I
){
1410 LiveInterval
*LI
= &LIS
.getInterval(*I
);
1411 for (const LiveRange::Segment
&S
: LI
->segments
) {
1412 // Dead defs end at the dead slot.
1413 if (S
.end
!= S
.valno
->def
.getDeadSlot())
1415 if (S
.valno
->isPHIDef())
1417 MachineInstr
*MI
= LIS
.getInstructionFromIndex(S
.valno
->def
);
1418 assert(MI
&& "Missing instruction for dead def");
1419 MI
->addRegisterDead(LI
->reg
, &TRI
);
1421 if (!MI
->allDefsAreDead())
1424 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI
);
1432 Edit
->eliminateDeadDefs(Dead
, None
, &AA
);
1435 void SplitEditor::forceRecomputeVNI(const VNInfo
&ParentVNI
) {
1436 // Fast-path for common case.
1437 if (!ParentVNI
.isPHIDef()) {
1438 for (unsigned I
= 0, E
= Edit
->size(); I
!= E
; ++I
)
1439 forceRecompute(I
, ParentVNI
);
1443 // Trace value through phis.
1444 SmallPtrSet
<const VNInfo
*, 8> Visited
; ///< whether VNI was/is in worklist.
1445 SmallVector
<const VNInfo
*, 4> WorkList
;
1446 Visited
.insert(&ParentVNI
);
1447 WorkList
.push_back(&ParentVNI
);
1449 const LiveInterval
&ParentLI
= Edit
->getParent();
1450 const SlotIndexes
&Indexes
= *LIS
.getSlotIndexes();
1452 const VNInfo
&VNI
= *WorkList
.back();
1453 WorkList
.pop_back();
1454 for (unsigned I
= 0, E
= Edit
->size(); I
!= E
; ++I
)
1455 forceRecompute(I
, VNI
);
1456 if (!VNI
.isPHIDef())
1459 MachineBasicBlock
&MBB
= *Indexes
.getMBBFromIndex(VNI
.def
);
1460 for (const MachineBasicBlock
*Pred
: MBB
.predecessors()) {
1461 SlotIndex PredEnd
= Indexes
.getMBBEndIdx(Pred
);
1462 VNInfo
*PredVNI
= ParentLI
.getVNInfoBefore(PredEnd
);
1463 assert(PredVNI
&& "Value available in PhiVNI predecessor");
1464 if (Visited
.insert(PredVNI
).second
)
1465 WorkList
.push_back(PredVNI
);
1467 } while(!WorkList
.empty());
1470 void SplitEditor::finish(SmallVectorImpl
<unsigned> *LRMap
) {
1473 // At this point, the live intervals in Edit contain VNInfos corresponding to
1474 // the inserted copies.
1476 // Add the original defs from the parent interval.
1477 for (const VNInfo
*ParentVNI
: Edit
->getParent().valnos
) {
1478 if (ParentVNI
->isUnused())
1480 unsigned RegIdx
= RegAssign
.lookup(ParentVNI
->def
);
1481 defValue(RegIdx
, ParentVNI
, ParentVNI
->def
, true);
1483 // Force rematted values to be recomputed everywhere.
1484 // The new live ranges may be truncated.
1485 if (Edit
->didRematerialize(ParentVNI
))
1486 forceRecomputeVNI(*ParentVNI
);
1489 // Hoist back-copies to the complement interval when in spill mode.
1490 switch (SpillMode
) {
1492 // Leave all back-copies as is.
1496 // hoistCopies will behave differently between size and speed.
1500 // Transfer the simply mapped values, check if any are skipped.
1501 bool Skipped
= transferValues();
1503 // Rewrite virtual registers, possibly extending ranges.
1504 rewriteAssigned(Skipped
);
1507 extendPHIKillRanges();
1511 // Delete defs that were rematted everywhere.
1513 deleteRematVictims();
1515 // Get rid of unused values and set phi-kill flags.
1516 for (unsigned Reg
: *Edit
) {
1517 LiveInterval
&LI
= LIS
.getInterval(Reg
);
1518 LI
.removeEmptySubRanges();
1519 LI
.RenumberValues();
1522 // Provide a reverse mapping from original indices to Edit ranges.
1525 for (unsigned i
= 0, e
= Edit
->size(); i
!= e
; ++i
)
1526 LRMap
->push_back(i
);
1529 // Now check if any registers were separated into multiple components.
1530 ConnectedVNInfoEqClasses
ConEQ(LIS
);
1531 for (unsigned i
= 0, e
= Edit
->size(); i
!= e
; ++i
) {
1532 // Don't use iterators, they are invalidated by create() below.
1533 unsigned VReg
= Edit
->get(i
);
1534 LiveInterval
&LI
= LIS
.getInterval(VReg
);
1535 SmallVector
<LiveInterval
*, 8> SplitLIs
;
1536 LIS
.splitSeparateComponents(LI
, SplitLIs
);
1537 unsigned Original
= VRM
.getOriginal(VReg
);
1538 for (LiveInterval
*SplitLI
: SplitLIs
)
1539 VRM
.setIsSplitFromReg(SplitLI
->reg
, Original
);
1541 // The new intervals all map back to i.
1543 LRMap
->resize(Edit
->size(), i
);
1546 // Calculate spill weight and allocation hints for new intervals.
1547 Edit
->calculateRegClassAndHint(VRM
.getMachineFunction(), SA
.Loops
, MBFI
);
1549 assert(!LRMap
|| LRMap
->size() == Edit
->size());
1552 //===----------------------------------------------------------------------===//
1553 // Single Block Splitting
1554 //===----------------------------------------------------------------------===//
1556 bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo
&BI
,
1557 bool SingleInstrs
) const {
1558 // Always split for multiple instructions.
1559 if (!BI
.isOneInstr())
1561 // Don't split for single instructions unless explicitly requested.
1564 // Splitting a live-through range always makes progress.
1565 if (BI
.LiveIn
&& BI
.LiveOut
)
1567 // No point in isolating a copy. It has no register class constraints.
1568 if (LIS
.getInstructionFromIndex(BI
.FirstInstr
)->isCopyLike())
1570 // Finally, don't isolate an end point that was created by earlier splits.
1571 return isOriginalEndpoint(BI
.FirstInstr
);
1574 void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo
&BI
) {
1576 SlotIndex LastSplitPoint
= SA
.getLastSplitPoint(BI
.MBB
->getNumber());
1577 SlotIndex SegStart
= enterIntvBefore(std::min(BI
.FirstInstr
,
1579 if (!BI
.LiveOut
|| BI
.LastInstr
< LastSplitPoint
) {
1580 useIntv(SegStart
, leaveIntvAfter(BI
.LastInstr
));
1582 // The last use is after the last valid split point.
1583 SlotIndex SegStop
= leaveIntvBefore(LastSplitPoint
);
1584 useIntv(SegStart
, SegStop
);
1585 overlapIntv(SegStop
, BI
.LastInstr
);
1589 //===----------------------------------------------------------------------===//
1590 // Global Live Range Splitting Support
1591 //===----------------------------------------------------------------------===//
1593 // These methods support a method of global live range splitting that uses a
1594 // global algorithm to decide intervals for CFG edges. They will insert split
1595 // points and color intervals in basic blocks while avoiding interference.
1597 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1598 // are on the stack.
1600 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum
,
1601 unsigned IntvIn
, SlotIndex LeaveBefore
,
1602 unsigned IntvOut
, SlotIndex EnterAfter
){
1603 SlotIndex Start
, Stop
;
1604 std::tie(Start
, Stop
) = LIS
.getSlotIndexes()->getMBBRange(MBBNum
);
1606 LLVM_DEBUG(dbgs() << "%bb." << MBBNum
<< " [" << Start
<< ';' << Stop
1607 << ") intf " << LeaveBefore
<< '-' << EnterAfter
1608 << ", live-through " << IntvIn
<< " -> " << IntvOut
);
1610 assert((IntvIn
|| IntvOut
) && "Use splitSingleBlock for isolated blocks");
1612 assert((!LeaveBefore
|| LeaveBefore
< Stop
) && "Interference after block");
1613 assert((!IntvIn
|| !LeaveBefore
|| LeaveBefore
> Start
) && "Impossible intf");
1614 assert((!EnterAfter
|| EnterAfter
>= Start
) && "Interference before block");
1616 MachineBasicBlock
*MBB
= VRM
.getMachineFunction().getBlockNumbered(MBBNum
);
1619 LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1621 // <<<<<<<<< Possible LeaveBefore interference.
1622 // |-----------| Live through.
1623 // -____________ Spill on entry.
1626 SlotIndex Idx
= leaveIntvAtTop(*MBB
);
1627 assert((!LeaveBefore
|| Idx
<= LeaveBefore
) && "Interference");
1633 LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1635 // >>>>>>> Possible EnterAfter interference.
1636 // |-----------| Live through.
1637 // ___________-- Reload on exit.
1639 selectIntv(IntvOut
);
1640 SlotIndex Idx
= enterIntvAtEnd(*MBB
);
1641 assert((!EnterAfter
|| Idx
>= EnterAfter
) && "Interference");
1646 if (IntvIn
== IntvOut
&& !LeaveBefore
&& !EnterAfter
) {
1647 LLVM_DEBUG(dbgs() << ", straight through.\n");
1649 // |-----------| Live through.
1650 // ------------- Straight through, same intv, no interference.
1652 selectIntv(IntvOut
);
1653 useIntv(Start
, Stop
);
1657 // We cannot legally insert splits after LSP.
1658 SlotIndex LSP
= SA
.getLastSplitPoint(MBBNum
);
1659 assert((!IntvOut
|| !EnterAfter
|| EnterAfter
< LSP
) && "Impossible intf");
1661 if (IntvIn
!= IntvOut
&& (!LeaveBefore
|| !EnterAfter
||
1662 LeaveBefore
.getBaseIndex() > EnterAfter
.getBoundaryIndex())) {
1663 LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1665 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference.
1666 // |-----------| Live through.
1667 // ------======= Switch intervals between interference.
1669 selectIntv(IntvOut
);
1671 if (LeaveBefore
&& LeaveBefore
< LSP
) {
1672 Idx
= enterIntvBefore(LeaveBefore
);
1675 Idx
= enterIntvAtEnd(*MBB
);
1678 useIntv(Start
, Idx
);
1679 assert((!LeaveBefore
|| Idx
<= LeaveBefore
) && "Interference");
1680 assert((!EnterAfter
|| Idx
>= EnterAfter
) && "Interference");
1684 LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1686 // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference.
1687 // |-----------| Live through.
1688 // ==---------== Switch intervals before/after interference.
1690 assert(LeaveBefore
<= EnterAfter
&& "Missed case");
1692 selectIntv(IntvOut
);
1693 SlotIndex Idx
= enterIntvAfter(EnterAfter
);
1695 assert((!EnterAfter
|| Idx
>= EnterAfter
) && "Interference");
1698 Idx
= leaveIntvBefore(LeaveBefore
);
1699 useIntv(Start
, Idx
);
1700 assert((!LeaveBefore
|| Idx
<= LeaveBefore
) && "Interference");
1703 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo
&BI
,
1704 unsigned IntvIn
, SlotIndex LeaveBefore
) {
1705 SlotIndex Start
, Stop
;
1706 std::tie(Start
, Stop
) = LIS
.getSlotIndexes()->getMBBRange(BI
.MBB
);
1708 LLVM_DEBUG(dbgs() << printMBBReference(*BI
.MBB
) << " [" << Start
<< ';'
1709 << Stop
<< "), uses " << BI
.FirstInstr
<< '-'
1710 << BI
.LastInstr
<< ", reg-in " << IntvIn
1711 << ", leave before " << LeaveBefore
1712 << (BI
.LiveOut
? ", stack-out" : ", killed in block"));
1714 assert(IntvIn
&& "Must have register in");
1715 assert(BI
.LiveIn
&& "Must be live-in");
1716 assert((!LeaveBefore
|| LeaveBefore
> Start
) && "Bad interference");
1718 if (!BI
.LiveOut
&& (!LeaveBefore
|| LeaveBefore
>= BI
.LastInstr
)) {
1719 LLVM_DEBUG(dbgs() << " before interference.\n");
1721 // <<< Interference after kill.
1722 // |---o---x | Killed in block.
1723 // ========= Use IntvIn everywhere.
1726 useIntv(Start
, BI
.LastInstr
);
1730 SlotIndex LSP
= SA
.getLastSplitPoint(BI
.MBB
->getNumber());
1732 if (!LeaveBefore
|| LeaveBefore
> BI
.LastInstr
.getBoundaryIndex()) {
1734 // <<< Possible interference after last use.
1735 // |---o---o---| Live-out on stack.
1736 // =========____ Leave IntvIn after last use.
1738 // < Interference after last use.
1739 // |---o---o--o| Live-out on stack, late last use.
1740 // ============ Copy to stack after LSP, overlap IntvIn.
1741 // \_____ Stack interval is live-out.
1743 if (BI
.LastInstr
< LSP
) {
1744 LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1746 SlotIndex Idx
= leaveIntvAfter(BI
.LastInstr
);
1747 useIntv(Start
, Idx
);
1748 assert((!LeaveBefore
|| Idx
<= LeaveBefore
) && "Interference");
1750 LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1752 SlotIndex Idx
= leaveIntvBefore(LSP
);
1753 overlapIntv(Idx
, BI
.LastInstr
);
1754 useIntv(Start
, Idx
);
1755 assert((!LeaveBefore
|| Idx
<= LeaveBefore
) && "Interference");
1760 // The interference is overlapping somewhere we wanted to use IntvIn. That
1761 // means we need to create a local interval that can be allocated a
1762 // different register.
1763 unsigned LocalIntv
= openIntv();
1765 LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv
<< ".\n");
1767 if (!BI
.LiveOut
|| BI
.LastInstr
< LSP
) {
1769 // <<<<<<< Interference overlapping uses.
1770 // |---o---o---| Live-out on stack.
1771 // =====----____ Leave IntvIn before interference, then spill.
1773 SlotIndex To
= leaveIntvAfter(BI
.LastInstr
);
1774 SlotIndex From
= enterIntvBefore(LeaveBefore
);
1777 useIntv(Start
, From
);
1778 assert((!LeaveBefore
|| From
<= LeaveBefore
) && "Interference");
1782 // <<<<<<< Interference overlapping uses.
1783 // |---o---o--o| Live-out on stack, late last use.
1784 // =====------- Copy to stack before LSP, overlap LocalIntv.
1785 // \_____ Stack interval is live-out.
1787 SlotIndex To
= leaveIntvBefore(LSP
);
1788 overlapIntv(To
, BI
.LastInstr
);
1789 SlotIndex From
= enterIntvBefore(std::min(To
, LeaveBefore
));
1792 useIntv(Start
, From
);
1793 assert((!LeaveBefore
|| From
<= LeaveBefore
) && "Interference");
1796 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo
&BI
,
1797 unsigned IntvOut
, SlotIndex EnterAfter
) {
1798 SlotIndex Start
, Stop
;
1799 std::tie(Start
, Stop
) = LIS
.getSlotIndexes()->getMBBRange(BI
.MBB
);
1801 LLVM_DEBUG(dbgs() << printMBBReference(*BI
.MBB
) << " [" << Start
<< ';'
1802 << Stop
<< "), uses " << BI
.FirstInstr
<< '-'
1803 << BI
.LastInstr
<< ", reg-out " << IntvOut
1804 << ", enter after " << EnterAfter
1805 << (BI
.LiveIn
? ", stack-in" : ", defined in block"));
1807 SlotIndex LSP
= SA
.getLastSplitPoint(BI
.MBB
->getNumber());
1809 assert(IntvOut
&& "Must have register out");
1810 assert(BI
.LiveOut
&& "Must be live-out");
1811 assert((!EnterAfter
|| EnterAfter
< LSP
) && "Bad interference");
1813 if (!BI
.LiveIn
&& (!EnterAfter
|| EnterAfter
<= BI
.FirstInstr
)) {
1814 LLVM_DEBUG(dbgs() << " after interference.\n");
1816 // >>>> Interference before def.
1817 // | o---o---| Defined in block.
1818 // ========= Use IntvOut everywhere.
1820 selectIntv(IntvOut
);
1821 useIntv(BI
.FirstInstr
, Stop
);
1825 if (!EnterAfter
|| EnterAfter
< BI
.FirstInstr
.getBaseIndex()) {
1826 LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1828 // >>>> Interference before def.
1829 // |---o---o---| Live-through, stack-in.
1830 // ____========= Enter IntvOut before first use.
1832 selectIntv(IntvOut
);
1833 SlotIndex Idx
= enterIntvBefore(std::min(LSP
, BI
.FirstInstr
));
1835 assert((!EnterAfter
|| Idx
>= EnterAfter
) && "Interference");
1839 // The interference is overlapping somewhere we wanted to use IntvOut. That
1840 // means we need to create a local interval that can be allocated a
1841 // different register.
1842 LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1844 // >>>>>>> Interference overlapping uses.
1845 // |---o---o---| Live-through, stack-in.
1846 // ____---====== Create local interval for interference range.
1848 selectIntv(IntvOut
);
1849 SlotIndex Idx
= enterIntvAfter(EnterAfter
);
1851 assert((!EnterAfter
|| Idx
>= EnterAfter
) && "Interference");
1854 SlotIndex From
= enterIntvBefore(std::min(Idx
, BI
.FirstInstr
));