1 //===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
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 /// \file This file implements the LiveInterval analysis pass which is used
10 /// by the Linear Scan Register allocator. This pass linearizes the
11 /// basic blocks of the function in DFS order and computes live intervals for
12 /// each virtual and physical register.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/CodeGen/LiveIntervals.h"
17 #include "LiveRangeCalc.h"
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/iterator_range.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/CodeGen/LiveInterval.h"
25 #include "llvm/CodeGen/LiveVariables.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/MachineInstrBundle.h"
32 #include "llvm/CodeGen/MachineOperand.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/CodeGen/Passes.h"
35 #include "llvm/CodeGen/SlotIndexes.h"
36 #include "llvm/CodeGen/TargetRegisterInfo.h"
37 #include "llvm/CodeGen/TargetSubtargetInfo.h"
38 #include "llvm/CodeGen/VirtRegMap.h"
39 #include "llvm/Config/llvm-config.h"
40 #include "llvm/MC/LaneBitmask.h"
41 #include "llvm/MC/MCRegisterInfo.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/BlockFrequency.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Compiler.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/MathExtras.h"
48 #include "llvm/Support/raw_ostream.h"
58 #define DEBUG_TYPE "regalloc"
60 char LiveIntervals::ID
= 0;
61 char &llvm::LiveIntervalsID
= LiveIntervals::ID
;
62 INITIALIZE_PASS_BEGIN(LiveIntervals
, "liveintervals",
63 "Live Interval Analysis", false, false)
64 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
)
65 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
67 INITIALIZE_PASS_END(LiveIntervals
, "liveintervals",
68 "Live Interval Analysis", false, false)
71 static cl::opt
<bool> EnablePrecomputePhysRegs(
72 "precompute-phys-liveness", cl::Hidden
,
73 cl::desc("Eagerly compute live intervals for all physreg units."));
75 static bool EnablePrecomputePhysRegs
= false;
80 cl::opt
<bool> UseSegmentSetForPhysRegs(
81 "use-segment-set-for-physregs", cl::Hidden
, cl::init(true),
83 "Use segment set for the computation of the live ranges of physregs."));
85 } // end namespace llvm
87 void LiveIntervals::getAnalysisUsage(AnalysisUsage
&AU
) const {
89 AU
.addRequired
<AAResultsWrapperPass
>();
90 AU
.addPreserved
<AAResultsWrapperPass
>();
91 AU
.addPreserved
<LiveVariables
>();
92 AU
.addPreservedID(MachineLoopInfoID
);
93 AU
.addRequiredTransitiveID(MachineDominatorsID
);
94 AU
.addPreservedID(MachineDominatorsID
);
95 AU
.addPreserved
<SlotIndexes
>();
96 AU
.addRequiredTransitive
<SlotIndexes
>();
97 MachineFunctionPass::getAnalysisUsage(AU
);
100 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID
) {
101 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
104 LiveIntervals::~LiveIntervals() {
108 void LiveIntervals::releaseMemory() {
109 // Free the live intervals themselves.
110 for (unsigned i
= 0, e
= VirtRegIntervals
.size(); i
!= e
; ++i
)
111 delete VirtRegIntervals
[Register::index2VirtReg(i
)];
112 VirtRegIntervals
.clear();
113 RegMaskSlots
.clear();
115 RegMaskBlocks
.clear();
117 for (LiveRange
*LR
: RegUnitRanges
)
119 RegUnitRanges
.clear();
121 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
122 VNInfoAllocator
.Reset();
125 bool LiveIntervals::runOnMachineFunction(MachineFunction
&fn
) {
127 MRI
= &MF
->getRegInfo();
128 TRI
= MF
->getSubtarget().getRegisterInfo();
129 TII
= MF
->getSubtarget().getInstrInfo();
130 AA
= &getAnalysis
<AAResultsWrapperPass
>().getAAResults();
131 Indexes
= &getAnalysis
<SlotIndexes
>();
132 DomTree
= &getAnalysis
<MachineDominatorTree
>();
135 LRCalc
= new LiveRangeCalc();
137 // Allocate space for all virtual registers.
138 VirtRegIntervals
.resize(MRI
->getNumVirtRegs());
142 computeLiveInRegUnits();
144 if (EnablePrecomputePhysRegs
) {
145 // For stress testing, precompute live ranges of all physical register
146 // units, including reserved registers.
147 for (unsigned i
= 0, e
= TRI
->getNumRegUnits(); i
!= e
; ++i
)
154 void LiveIntervals::print(raw_ostream
&OS
, const Module
* ) const {
155 OS
<< "********** INTERVALS **********\n";
157 // Dump the regunits.
158 for (unsigned Unit
= 0, UnitE
= RegUnitRanges
.size(); Unit
!= UnitE
; ++Unit
)
159 if (LiveRange
*LR
= RegUnitRanges
[Unit
])
160 OS
<< printRegUnit(Unit
, TRI
) << ' ' << *LR
<< '\n';
162 // Dump the virtregs.
163 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
164 unsigned Reg
= Register::index2VirtReg(i
);
165 if (hasInterval(Reg
))
166 OS
<< getInterval(Reg
) << '\n';
170 for (SlotIndex Idx
: RegMaskSlots
)
177 void LiveIntervals::printInstrs(raw_ostream
&OS
) const {
178 OS
<< "********** MACHINEINSTRS **********\n";
179 MF
->print(OS
, Indexes
);
182 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
183 LLVM_DUMP_METHOD
void LiveIntervals::dumpInstrs() const {
188 LiveInterval
* LiveIntervals::createInterval(unsigned reg
) {
189 float Weight
= Register::isPhysicalRegister(reg
) ? huge_valf
: 0.0F
;
190 return new LiveInterval(reg
, Weight
);
193 /// Compute the live interval of a virtual register, based on defs and uses.
194 void LiveIntervals::computeVirtRegInterval(LiveInterval
&LI
) {
195 assert(LRCalc
&& "LRCalc not initialized.");
196 assert(LI
.empty() && "Should only compute empty intervals.");
197 LRCalc
->reset(MF
, getSlotIndexes(), DomTree
, &getVNInfoAllocator());
198 LRCalc
->calculate(LI
, MRI
->shouldTrackSubRegLiveness(LI
.reg
));
199 computeDeadValues(LI
, nullptr);
202 void LiveIntervals::computeVirtRegs() {
203 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
204 unsigned Reg
= Register::index2VirtReg(i
);
205 if (MRI
->reg_nodbg_empty(Reg
))
207 createAndComputeVirtRegInterval(Reg
);
211 void LiveIntervals::computeRegMasks() {
212 RegMaskBlocks
.resize(MF
->getNumBlockIDs());
214 // Find all instructions with regmask operands.
215 for (const MachineBasicBlock
&MBB
: *MF
) {
216 std::pair
<unsigned, unsigned> &RMB
= RegMaskBlocks
[MBB
.getNumber()];
217 RMB
.first
= RegMaskSlots
.size();
219 // Some block starts, such as EH funclets, create masks.
220 if (const uint32_t *Mask
= MBB
.getBeginClobberMask(TRI
)) {
221 RegMaskSlots
.push_back(Indexes
->getMBBStartIdx(&MBB
));
222 RegMaskBits
.push_back(Mask
);
225 for (const MachineInstr
&MI
: MBB
) {
226 for (const MachineOperand
&MO
: MI
.operands()) {
229 RegMaskSlots
.push_back(Indexes
->getInstructionIndex(MI
).getRegSlot());
230 RegMaskBits
.push_back(MO
.getRegMask());
234 // Some block ends, such as funclet returns, create masks. Put the mask on
235 // the last instruction of the block, because MBB slot index intervals are
237 if (const uint32_t *Mask
= MBB
.getEndClobberMask(TRI
)) {
238 assert(!MBB
.empty() && "empty return block?");
239 RegMaskSlots
.push_back(
240 Indexes
->getInstructionIndex(MBB
.back()).getRegSlot());
241 RegMaskBits
.push_back(Mask
);
244 // Compute the number of register mask instructions in this block.
245 RMB
.second
= RegMaskSlots
.size() - RMB
.first
;
249 //===----------------------------------------------------------------------===//
250 // Register Unit Liveness
251 //===----------------------------------------------------------------------===//
253 // Fixed interference typically comes from ABI boundaries: Function arguments
254 // and return values are passed in fixed registers, and so are exception
255 // pointers entering landing pads. Certain instructions require values to be
256 // present in specific registers. That is also represented through fixed
260 /// Compute the live range of a register unit, based on the uses and defs of
261 /// aliasing registers. The range should be empty, or contain only dead
262 /// phi-defs from ABI blocks.
263 void LiveIntervals::computeRegUnitRange(LiveRange
&LR
, unsigned Unit
) {
264 assert(LRCalc
&& "LRCalc not initialized.");
265 LRCalc
->reset(MF
, getSlotIndexes(), DomTree
, &getVNInfoAllocator());
267 // The physregs aliasing Unit are the roots and their super-registers.
268 // Create all values as dead defs before extending to uses. Note that roots
269 // may share super-registers. That's OK because createDeadDefs() is
270 // idempotent. It is very rare for a register unit to have multiple roots, so
271 // uniquing super-registers is probably not worthwhile.
272 bool IsReserved
= false;
273 for (MCRegUnitRootIterator
Root(Unit
, TRI
); Root
.isValid(); ++Root
) {
274 bool IsRootReserved
= true;
275 for (MCSuperRegIterator
Super(*Root
, TRI
, /*IncludeSelf=*/true);
276 Super
.isValid(); ++Super
) {
277 unsigned Reg
= *Super
;
278 if (!MRI
->reg_empty(Reg
))
279 LRCalc
->createDeadDefs(LR
, Reg
);
280 // A register unit is considered reserved if all its roots and all their
281 // super registers are reserved.
282 if (!MRI
->isReserved(Reg
))
283 IsRootReserved
= false;
285 IsReserved
|= IsRootReserved
;
287 assert(IsReserved
== MRI
->isReservedRegUnit(Unit
) &&
288 "reserved computation mismatch");
290 // Now extend LR to reach all uses.
291 // Ignore uses of reserved registers. We only track defs of those.
293 for (MCRegUnitRootIterator
Root(Unit
, TRI
); Root
.isValid(); ++Root
) {
294 for (MCSuperRegIterator
Super(*Root
, TRI
, /*IncludeSelf=*/true);
295 Super
.isValid(); ++Super
) {
296 unsigned Reg
= *Super
;
297 if (!MRI
->reg_empty(Reg
))
298 LRCalc
->extendToUses(LR
, Reg
);
303 // Flush the segment set to the segment vector.
304 if (UseSegmentSetForPhysRegs
)
305 LR
.flushSegmentSet();
308 /// Precompute the live ranges of any register units that are live-in to an ABI
309 /// block somewhere. Register values can appear without a corresponding def when
310 /// entering the entry block or a landing pad.
311 void LiveIntervals::computeLiveInRegUnits() {
312 RegUnitRanges
.resize(TRI
->getNumRegUnits());
313 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
315 // Keep track of the live range sets allocated.
316 SmallVector
<unsigned, 8> NewRanges
;
318 // Check all basic blocks for live-ins.
319 for (const MachineBasicBlock
&MBB
: *MF
) {
320 // We only care about ABI blocks: Entry + landing pads.
321 if ((&MBB
!= &MF
->front() && !MBB
.isEHPad()) || MBB
.livein_empty())
324 // Create phi-defs at Begin for all live-in registers.
325 SlotIndex Begin
= Indexes
->getMBBStartIdx(&MBB
);
326 LLVM_DEBUG(dbgs() << Begin
<< "\t" << printMBBReference(MBB
));
327 for (const auto &LI
: MBB
.liveins()) {
328 for (MCRegUnitIterator
Units(LI
.PhysReg
, TRI
); Units
.isValid(); ++Units
) {
329 unsigned Unit
= *Units
;
330 LiveRange
*LR
= RegUnitRanges
[Unit
];
332 // Use segment set to speed-up initial computation of the live range.
333 LR
= RegUnitRanges
[Unit
] = new LiveRange(UseSegmentSetForPhysRegs
);
334 NewRanges
.push_back(Unit
);
336 VNInfo
*VNI
= LR
->createDeadDef(Begin
, getVNInfoAllocator());
338 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit
, TRI
) << '#' << VNI
->id
);
341 LLVM_DEBUG(dbgs() << '\n');
343 LLVM_DEBUG(dbgs() << "Created " << NewRanges
.size() << " new intervals.\n");
345 // Compute the 'normal' part of the ranges.
346 for (unsigned Unit
: NewRanges
)
347 computeRegUnitRange(*RegUnitRanges
[Unit
], Unit
);
350 static void createSegmentsForValues(LiveRange
&LR
,
351 iterator_range
<LiveInterval::vni_iterator
> VNIs
) {
352 for (VNInfo
*VNI
: VNIs
) {
355 SlotIndex Def
= VNI
->def
;
356 LR
.addSegment(LiveRange::Segment(Def
, Def
.getDeadSlot(), VNI
));
360 void LiveIntervals::extendSegmentsToUses(LiveRange
&Segments
,
361 ShrinkToUsesWorkList
&WorkList
,
362 unsigned Reg
, LaneBitmask LaneMask
) {
363 // Keep track of the PHIs that are in use.
364 SmallPtrSet
<VNInfo
*, 8> UsedPHIs
;
365 // Blocks that have already been added to WorkList as live-out.
366 SmallPtrSet
<const MachineBasicBlock
*, 16> LiveOut
;
368 auto getSubRange
= [](const LiveInterval
&I
, LaneBitmask M
)
369 -> const LiveRange
& {
372 for (const LiveInterval::SubRange
&SR
: I
.subranges()) {
373 if ((SR
.LaneMask
& M
).any()) {
374 assert(SR
.LaneMask
== M
&& "Expecting lane masks to match exactly");
378 llvm_unreachable("Subrange for mask not found");
381 const LiveInterval
&LI
= getInterval(Reg
);
382 const LiveRange
&OldRange
= getSubRange(LI
, LaneMask
);
384 // Extend intervals to reach all uses in WorkList.
385 while (!WorkList
.empty()) {
386 SlotIndex Idx
= WorkList
.back().first
;
387 VNInfo
*VNI
= WorkList
.back().second
;
389 const MachineBasicBlock
*MBB
= Indexes
->getMBBFromIndex(Idx
.getPrevSlot());
390 SlotIndex BlockStart
= Indexes
->getMBBStartIdx(MBB
);
392 // Extend the live range for VNI to be live at Idx.
393 if (VNInfo
*ExtVNI
= Segments
.extendInBlock(BlockStart
, Idx
)) {
394 assert(ExtVNI
== VNI
&& "Unexpected existing value number");
396 // Is this a PHIDef we haven't seen before?
397 if (!VNI
->isPHIDef() || VNI
->def
!= BlockStart
||
398 !UsedPHIs
.insert(VNI
).second
)
400 // The PHI is live, make sure the predecessors are live-out.
401 for (const MachineBasicBlock
*Pred
: MBB
->predecessors()) {
402 if (!LiveOut
.insert(Pred
).second
)
404 SlotIndex Stop
= Indexes
->getMBBEndIdx(Pred
);
405 // A predecessor is not required to have a live-out value for a PHI.
406 if (VNInfo
*PVNI
= OldRange
.getVNInfoBefore(Stop
))
407 WorkList
.push_back(std::make_pair(Stop
, PVNI
));
412 // VNI is live-in to MBB.
413 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart
<< '\n');
414 Segments
.addSegment(LiveRange::Segment(BlockStart
, Idx
, VNI
));
416 // Make sure VNI is live-out from the predecessors.
417 for (const MachineBasicBlock
*Pred
: MBB
->predecessors()) {
418 if (!LiveOut
.insert(Pred
).second
)
420 SlotIndex Stop
= Indexes
->getMBBEndIdx(Pred
);
421 if (VNInfo
*OldVNI
= OldRange
.getVNInfoBefore(Stop
)) {
422 assert(OldVNI
== VNI
&& "Wrong value out of predecessor");
424 WorkList
.push_back(std::make_pair(Stop
, VNI
));
427 // There was no old VNI. Verify that Stop is jointly dominated
428 // by <undef>s for this live range.
429 assert(LaneMask
.any() &&
430 "Missing value out of predecessor for main range");
431 SmallVector
<SlotIndex
,8> Undefs
;
432 LI
.computeSubRangeUndefs(Undefs
, LaneMask
, *MRI
, *Indexes
);
433 assert(LiveRangeCalc::isJointlyDominated(Pred
, Undefs
, *Indexes
) &&
434 "Missing value out of predecessor for subrange");
441 bool LiveIntervals::shrinkToUses(LiveInterval
*li
,
442 SmallVectorImpl
<MachineInstr
*> *dead
) {
443 LLVM_DEBUG(dbgs() << "Shrink: " << *li
<< '\n');
444 assert(Register::isVirtualRegister(li
->reg
) &&
445 "Can only shrink virtual registers");
447 // Shrink subregister live ranges.
448 bool NeedsCleanup
= false;
449 for (LiveInterval::SubRange
&S
: li
->subranges()) {
450 shrinkToUses(S
, li
->reg
);
455 li
->removeEmptySubRanges();
457 // Find all the values used, including PHI kills.
458 ShrinkToUsesWorkList WorkList
;
460 // Visit all instructions reading li->reg.
461 unsigned Reg
= li
->reg
;
462 for (MachineInstr
&UseMI
: MRI
->reg_instructions(Reg
)) {
463 if (UseMI
.isDebugValue() || !UseMI
.readsVirtualRegister(Reg
))
465 SlotIndex Idx
= getInstructionIndex(UseMI
).getRegSlot();
466 LiveQueryResult LRQ
= li
->Query(Idx
);
467 VNInfo
*VNI
= LRQ
.valueIn();
469 // This shouldn't happen: readsVirtualRegister returns true, but there is
470 // no live value. It is likely caused by a target getting <undef> flags
473 dbgs() << Idx
<< '\t' << UseMI
474 << "Warning: Instr claims to read non-existent value in "
478 // Special case: An early-clobber tied operand reads and writes the
479 // register one slot early.
480 if (VNInfo
*DefVNI
= LRQ
.valueDefined())
483 WorkList
.push_back(std::make_pair(Idx
, VNI
));
486 // Create new live ranges with only minimal live segments per def.
488 createSegmentsForValues(NewLR
, make_range(li
->vni_begin(), li
->vni_end()));
489 extendSegmentsToUses(NewLR
, WorkList
, Reg
, LaneBitmask::getNone());
491 // Move the trimmed segments back.
492 li
->segments
.swap(NewLR
.segments
);
494 // Handle dead values.
495 bool CanSeparate
= computeDeadValues(*li
, dead
);
496 LLVM_DEBUG(dbgs() << "Shrunk: " << *li
<< '\n');
500 bool LiveIntervals::computeDeadValues(LiveInterval
&LI
,
501 SmallVectorImpl
<MachineInstr
*> *dead
) {
502 bool MayHaveSplitComponents
= false;
503 for (VNInfo
*VNI
: LI
.valnos
) {
506 SlotIndex Def
= VNI
->def
;
507 LiveRange::iterator I
= LI
.FindSegmentContaining(Def
);
508 assert(I
!= LI
.end() && "Missing segment for VNI");
510 // Is the register live before? Otherwise we may have to add a read-undef
511 // flag for subregister defs.
512 unsigned VReg
= LI
.reg
;
513 if (MRI
->shouldTrackSubRegLiveness(VReg
)) {
514 if ((I
== LI
.begin() || std::prev(I
)->end
< Def
) && !VNI
->isPHIDef()) {
515 MachineInstr
*MI
= getInstructionFromIndex(Def
);
516 MI
->setRegisterDefReadUndef(VReg
);
520 if (I
->end
!= Def
.getDeadSlot())
522 if (VNI
->isPHIDef()) {
523 // This is a dead PHI. Remove it.
526 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def
<< " may separate interval\n");
527 MayHaveSplitComponents
= true;
529 // This is a dead def. Make sure the instruction knows.
530 MachineInstr
*MI
= getInstructionFromIndex(Def
);
531 assert(MI
&& "No instruction defining live value");
532 MI
->addRegisterDead(LI
.reg
, TRI
);
533 if (dead
&& MI
->allDefsAreDead()) {
534 LLVM_DEBUG(dbgs() << "All defs dead: " << Def
<< '\t' << *MI
);
539 return MayHaveSplitComponents
;
542 void LiveIntervals::shrinkToUses(LiveInterval::SubRange
&SR
, unsigned Reg
) {
543 LLVM_DEBUG(dbgs() << "Shrink: " << SR
<< '\n');
544 assert(Register::isVirtualRegister(Reg
) &&
545 "Can only shrink virtual registers");
546 // Find all the values used, including PHI kills.
547 ShrinkToUsesWorkList WorkList
;
549 // Visit all instructions reading Reg.
551 for (MachineOperand
&MO
: MRI
->use_nodbg_operands(Reg
)) {
552 // Skip "undef" uses.
555 // Maybe the operand is for a subregister we don't care about.
556 unsigned SubReg
= MO
.getSubReg();
558 LaneBitmask LaneMask
= TRI
->getSubRegIndexLaneMask(SubReg
);
559 if ((LaneMask
& SR
.LaneMask
).none())
562 // We only need to visit each instruction once.
563 MachineInstr
*UseMI
= MO
.getParent();
564 SlotIndex Idx
= getInstructionIndex(*UseMI
).getRegSlot();
569 LiveQueryResult LRQ
= SR
.Query(Idx
);
570 VNInfo
*VNI
= LRQ
.valueIn();
571 // For Subranges it is possible that only undef values are left in that
572 // part of the subregister, so there is no real liverange at the use
576 // Special case: An early-clobber tied operand reads and writes the
577 // register one slot early.
578 if (VNInfo
*DefVNI
= LRQ
.valueDefined())
581 WorkList
.push_back(std::make_pair(Idx
, VNI
));
584 // Create a new live ranges with only minimal live segments per def.
586 createSegmentsForValues(NewLR
, make_range(SR
.vni_begin(), SR
.vni_end()));
587 extendSegmentsToUses(NewLR
, WorkList
, Reg
, SR
.LaneMask
);
589 // Move the trimmed ranges back.
590 SR
.segments
.swap(NewLR
.segments
);
592 // Remove dead PHI value numbers
593 for (VNInfo
*VNI
: SR
.valnos
) {
596 const LiveRange::Segment
*Segment
= SR
.getSegmentContaining(VNI
->def
);
597 assert(Segment
!= nullptr && "Missing segment for VNI");
598 if (Segment
->end
!= VNI
->def
.getDeadSlot())
600 if (VNI
->isPHIDef()) {
601 // This is a dead PHI. Remove it.
602 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI
->def
603 << " may separate interval\n");
605 SR
.removeSegment(*Segment
);
609 LLVM_DEBUG(dbgs() << "Shrunk: " << SR
<< '\n');
612 void LiveIntervals::extendToIndices(LiveRange
&LR
,
613 ArrayRef
<SlotIndex
> Indices
,
614 ArrayRef
<SlotIndex
> Undefs
) {
615 assert(LRCalc
&& "LRCalc not initialized.");
616 LRCalc
->reset(MF
, getSlotIndexes(), DomTree
, &getVNInfoAllocator());
617 for (SlotIndex Idx
: Indices
)
618 LRCalc
->extend(LR
, Idx
, /*PhysReg=*/0, Undefs
);
621 void LiveIntervals::pruneValue(LiveRange
&LR
, SlotIndex Kill
,
622 SmallVectorImpl
<SlotIndex
> *EndPoints
) {
623 LiveQueryResult LRQ
= LR
.Query(Kill
);
624 VNInfo
*VNI
= LRQ
.valueOutOrDead();
628 MachineBasicBlock
*KillMBB
= Indexes
->getMBBFromIndex(Kill
);
629 SlotIndex MBBEnd
= Indexes
->getMBBEndIdx(KillMBB
);
631 // If VNI isn't live out from KillMBB, the value is trivially pruned.
632 if (LRQ
.endPoint() < MBBEnd
) {
633 LR
.removeSegment(Kill
, LRQ
.endPoint());
634 if (EndPoints
) EndPoints
->push_back(LRQ
.endPoint());
638 // VNI is live out of KillMBB.
639 LR
.removeSegment(Kill
, MBBEnd
);
640 if (EndPoints
) EndPoints
->push_back(MBBEnd
);
642 // Find all blocks that are reachable from KillMBB without leaving VNI's live
643 // range. It is possible that KillMBB itself is reachable, so start a DFS
644 // from each successor.
645 using VisitedTy
= df_iterator_default_set
<MachineBasicBlock
*,9>;
647 for (MachineBasicBlock
*Succ
: KillMBB
->successors()) {
648 for (df_ext_iterator
<MachineBasicBlock
*, VisitedTy
>
649 I
= df_ext_begin(Succ
, Visited
), E
= df_ext_end(Succ
, Visited
);
651 MachineBasicBlock
*MBB
= *I
;
653 // Check if VNI is live in to MBB.
654 SlotIndex MBBStart
, MBBEnd
;
655 std::tie(MBBStart
, MBBEnd
) = Indexes
->getMBBRange(MBB
);
656 LiveQueryResult LRQ
= LR
.Query(MBBStart
);
657 if (LRQ
.valueIn() != VNI
) {
658 // This block isn't part of the VNI segment. Prune the search.
663 // Prune the search if VNI is killed in MBB.
664 if (LRQ
.endPoint() < MBBEnd
) {
665 LR
.removeSegment(MBBStart
, LRQ
.endPoint());
666 if (EndPoints
) EndPoints
->push_back(LRQ
.endPoint());
671 // VNI is live through MBB.
672 LR
.removeSegment(MBBStart
, MBBEnd
);
673 if (EndPoints
) EndPoints
->push_back(MBBEnd
);
679 //===----------------------------------------------------------------------===//
680 // Register allocator hooks.
683 void LiveIntervals::addKillFlags(const VirtRegMap
*VRM
) {
684 // Keep track of regunit ranges.
685 SmallVector
<std::pair
<const LiveRange
*, LiveRange::const_iterator
>, 8> RU
;
686 // Keep track of subregister ranges.
687 SmallVector
<std::pair
<const LiveInterval::SubRange
*,
688 LiveRange::const_iterator
>, 4> SRs
;
690 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
691 unsigned Reg
= Register::index2VirtReg(i
);
692 if (MRI
->reg_nodbg_empty(Reg
))
694 const LiveInterval
&LI
= getInterval(Reg
);
698 // Find the regunit intervals for the assigned register. They may overlap
699 // the virtual register live range, cancelling any kills.
701 for (MCRegUnitIterator
Unit(VRM
->getPhys(Reg
), TRI
); Unit
.isValid();
703 const LiveRange
&RURange
= getRegUnit(*Unit
);
706 RU
.push_back(std::make_pair(&RURange
, RURange
.find(LI
.begin()->end
)));
709 if (MRI
->subRegLivenessEnabled()) {
711 for (const LiveInterval::SubRange
&SR
: LI
.subranges()) {
712 SRs
.push_back(std::make_pair(&SR
, SR
.find(LI
.begin()->end
)));
716 // Every instruction that kills Reg corresponds to a segment range end
718 for (LiveInterval::const_iterator RI
= LI
.begin(), RE
= LI
.end(); RI
!= RE
;
720 // A block index indicates an MBB edge.
721 if (RI
->end
.isBlock())
723 MachineInstr
*MI
= getInstructionFromIndex(RI
->end
);
727 // Check if any of the regunits are live beyond the end of RI. That could
728 // happen when a physreg is defined as a copy of a virtreg:
731 // FOO %5 <--- MI, cancel kill because %eax is live.
734 // There should be no kill flag on FOO when %5 is rewritten as %eax.
735 for (auto &RUP
: RU
) {
736 const LiveRange
&RURange
= *RUP
.first
;
737 LiveRange::const_iterator
&I
= RUP
.second
;
738 if (I
== RURange
.end())
740 I
= RURange
.advanceTo(I
, RI
->end
);
741 if (I
== RURange
.end() || I
->start
>= RI
->end
)
743 // I is overlapping RI.
747 if (MRI
->subRegLivenessEnabled()) {
748 // When reading a partial undefined value we must not add a kill flag.
749 // The regalloc might have used the undef lane for something else.
751 // %1 = ... ; R32: %1
752 // %2:high16 = ... ; R64: %2
753 // = read killed %2 ; R64: %2
754 // = read %1 ; R32: %1
755 // The <kill> flag is correct for %2, but the register allocator may
756 // assign R0L to %1, and R0 to %2 because the low 32bits of R0
757 // are actually never written by %2. After assignment the <kill>
758 // flag at the read instruction is invalid.
759 LaneBitmask DefinedLanesMask
;
761 // Compute a mask of lanes that are defined.
762 DefinedLanesMask
= LaneBitmask::getNone();
763 for (auto &SRP
: SRs
) {
764 const LiveInterval::SubRange
&SR
= *SRP
.first
;
765 LiveRange::const_iterator
&I
= SRP
.second
;
768 I
= SR
.advanceTo(I
, RI
->end
);
769 if (I
== SR
.end() || I
->start
>= RI
->end
)
771 // I is overlapping RI
772 DefinedLanesMask
|= SR
.LaneMask
;
775 DefinedLanesMask
= LaneBitmask::getAll();
777 bool IsFullWrite
= false;
778 for (const MachineOperand
&MO
: MI
->operands()) {
779 if (!MO
.isReg() || MO
.getReg() != Reg
)
782 // Reading any undefined lanes?
783 LaneBitmask UseMask
= TRI
->getSubRegIndexLaneMask(MO
.getSubReg());
784 if ((UseMask
& ~DefinedLanesMask
).any())
786 } else if (MO
.getSubReg() == 0) {
787 // Writing to the full register?
793 // If an instruction writes to a subregister, a new segment starts in
794 // the LiveInterval. But as this is only overriding part of the register
795 // adding kill-flags is not correct here after registers have been
798 // Next segment has to be adjacent in the subregister write case.
799 LiveRange::const_iterator N
= std::next(RI
);
800 if (N
!= LI
.end() && N
->start
== RI
->end
)
805 MI
->addRegisterKilled(Reg
, nullptr);
808 MI
->clearRegisterKills(Reg
, nullptr);
814 LiveIntervals::intervalIsInOneMBB(const LiveInterval
&LI
) const {
815 // A local live range must be fully contained inside the block, meaning it is
816 // defined and killed at instructions, not at block boundaries. It is not
817 // live in or out of any block.
819 // It is technically possible to have a PHI-defined live range identical to a
820 // single block, but we are going to return false in that case.
822 SlotIndex Start
= LI
.beginIndex();
826 SlotIndex Stop
= LI
.endIndex();
830 // getMBBFromIndex doesn't need to search the MBB table when both indexes
831 // belong to proper instructions.
832 MachineBasicBlock
*MBB1
= Indexes
->getMBBFromIndex(Start
);
833 MachineBasicBlock
*MBB2
= Indexes
->getMBBFromIndex(Stop
);
834 return MBB1
== MBB2
? MBB1
: nullptr;
838 LiveIntervals::hasPHIKill(const LiveInterval
&LI
, const VNInfo
*VNI
) const {
839 for (const VNInfo
*PHI
: LI
.valnos
) {
840 if (PHI
->isUnused() || !PHI
->isPHIDef())
842 const MachineBasicBlock
*PHIMBB
= getMBBFromIndex(PHI
->def
);
843 // Conservatively return true instead of scanning huge predecessor lists.
844 if (PHIMBB
->pred_size() > 100)
846 for (const MachineBasicBlock
*Pred
: PHIMBB
->predecessors())
847 if (VNI
== LI
.getVNInfoBefore(Indexes
->getMBBEndIdx(Pred
)))
853 float LiveIntervals::getSpillWeight(bool isDef
, bool isUse
,
854 const MachineBlockFrequencyInfo
*MBFI
,
855 const MachineInstr
&MI
) {
856 return getSpillWeight(isDef
, isUse
, MBFI
, MI
.getParent());
859 float LiveIntervals::getSpillWeight(bool isDef
, bool isUse
,
860 const MachineBlockFrequencyInfo
*MBFI
,
861 const MachineBasicBlock
*MBB
) {
862 BlockFrequency Freq
= MBFI
->getBlockFreq(MBB
);
863 const float Scale
= 1.0f
/ MBFI
->getEntryFreq();
864 return (isDef
+ isUse
) * (Freq
.getFrequency() * Scale
);
868 LiveIntervals::addSegmentToEndOfBlock(unsigned reg
, MachineInstr
&startInst
) {
869 LiveInterval
& Interval
= createEmptyInterval(reg
);
870 VNInfo
*VN
= Interval
.getNextValue(
871 SlotIndex(getInstructionIndex(startInst
).getRegSlot()),
872 getVNInfoAllocator());
873 LiveRange::Segment
S(SlotIndex(getInstructionIndex(startInst
).getRegSlot()),
874 getMBBEndIdx(startInst
.getParent()), VN
);
875 Interval
.addSegment(S
);
880 //===----------------------------------------------------------------------===//
881 // Register mask functions
882 //===----------------------------------------------------------------------===//
884 bool LiveIntervals::checkRegMaskInterference(LiveInterval
&LI
,
885 BitVector
&UsableRegs
) {
888 LiveInterval::iterator LiveI
= LI
.begin(), LiveE
= LI
.end();
890 // Use a smaller arrays for local live ranges.
891 ArrayRef
<SlotIndex
> Slots
;
892 ArrayRef
<const uint32_t*> Bits
;
893 if (MachineBasicBlock
*MBB
= intervalIsInOneMBB(LI
)) {
894 Slots
= getRegMaskSlotsInBlock(MBB
->getNumber());
895 Bits
= getRegMaskBitsInBlock(MBB
->getNumber());
897 Slots
= getRegMaskSlots();
898 Bits
= getRegMaskBits();
901 // We are going to enumerate all the register mask slots contained in LI.
902 // Start with a binary search of RegMaskSlots to find a starting point.
903 ArrayRef
<SlotIndex
>::iterator SlotI
= llvm::lower_bound(Slots
, LiveI
->start
);
904 ArrayRef
<SlotIndex
>::iterator SlotE
= Slots
.end();
906 // No slots in range, LI begins after the last call.
912 assert(*SlotI
>= LiveI
->start
);
913 // Loop over all slots overlapping this segment.
914 while (*SlotI
< LiveI
->end
) {
915 // *SlotI overlaps LI. Collect mask bits.
917 // This is the first overlap. Initialize UsableRegs to all ones.
919 UsableRegs
.resize(TRI
->getNumRegs(), true);
922 // Remove usable registers clobbered by this mask.
923 UsableRegs
.clearBitsNotInMask(Bits
[SlotI
-Slots
.begin()]);
924 if (++SlotI
== SlotE
)
927 // *SlotI is beyond the current LI segment.
928 LiveI
= LI
.advanceTo(LiveI
, *SlotI
);
931 // Advance SlotI until it overlaps.
932 while (*SlotI
< LiveI
->start
)
933 if (++SlotI
== SlotE
)
938 //===----------------------------------------------------------------------===//
939 // IntervalUpdate class.
940 //===----------------------------------------------------------------------===//
942 /// Toolkit used by handleMove to trim or extend live intervals.
943 class LiveIntervals::HMEditor
{
946 const MachineRegisterInfo
& MRI
;
947 const TargetRegisterInfo
& TRI
;
950 SmallPtrSet
<LiveRange
*, 8> Updated
;
954 HMEditor(LiveIntervals
& LIS
, const MachineRegisterInfo
& MRI
,
955 const TargetRegisterInfo
& TRI
,
956 SlotIndex OldIdx
, SlotIndex NewIdx
, bool UpdateFlags
)
957 : LIS(LIS
), MRI(MRI
), TRI(TRI
), OldIdx(OldIdx
), NewIdx(NewIdx
),
958 UpdateFlags(UpdateFlags
) {}
960 // FIXME: UpdateFlags is a workaround that creates live intervals for all
961 // physregs, even those that aren't needed for regalloc, in order to update
962 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
963 // flags, and postRA passes will use a live register utility instead.
964 LiveRange
*getRegUnitLI(unsigned Unit
) {
965 if (UpdateFlags
&& !MRI
.isReservedRegUnit(Unit
))
966 return &LIS
.getRegUnit(Unit
);
967 return LIS
.getCachedRegUnit(Unit
);
970 /// Update all live ranges touched by MI, assuming a move from OldIdx to
972 void updateAllRanges(MachineInstr
*MI
) {
973 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx
<< " -> " << NewIdx
<< ": "
975 bool hasRegMask
= false;
976 for (MachineOperand
&MO
: MI
->operands()) {
984 // Aggressively clear all kill flags.
985 // They are reinserted by VirtRegRewriter.
989 Register Reg
= MO
.getReg();
992 if (Register::isVirtualRegister(Reg
)) {
993 LiveInterval
&LI
= LIS
.getInterval(Reg
);
994 if (LI
.hasSubRanges()) {
995 unsigned SubReg
= MO
.getSubReg();
996 LaneBitmask LaneMask
= SubReg
? TRI
.getSubRegIndexLaneMask(SubReg
)
997 : MRI
.getMaxLaneMaskForVReg(Reg
);
998 for (LiveInterval::SubRange
&S
: LI
.subranges()) {
999 if ((S
.LaneMask
& LaneMask
).none())
1001 updateRange(S
, Reg
, S
.LaneMask
);
1004 updateRange(LI
, Reg
, LaneBitmask::getNone());
1008 // For physregs, only update the regunits that actually have a
1009 // precomputed live range.
1010 for (MCRegUnitIterator
Units(Reg
, &TRI
); Units
.isValid(); ++Units
)
1011 if (LiveRange
*LR
= getRegUnitLI(*Units
))
1012 updateRange(*LR
, *Units
, LaneBitmask::getNone());
1015 updateRegMaskSlots();
1019 /// Update a single live range, assuming an instruction has been moved from
1020 /// OldIdx to NewIdx.
1021 void updateRange(LiveRange
&LR
, unsigned Reg
, LaneBitmask LaneMask
) {
1022 if (!Updated
.insert(&LR
).second
)
1026 if (Register::isVirtualRegister(Reg
)) {
1027 dbgs() << printReg(Reg
);
1029 dbgs() << " L" << PrintLaneMask(LaneMask
);
1031 dbgs() << printRegUnit(Reg
, &TRI
);
1033 dbgs() << ":\t" << LR
<< '\n';
1035 if (SlotIndex::isEarlierInstr(OldIdx
, NewIdx
))
1038 handleMoveUp(LR
, Reg
, LaneMask
);
1039 LLVM_DEBUG(dbgs() << " -->\t" << LR
<< '\n');
1043 /// Update LR to reflect an instruction has been moved downwards from OldIdx
1044 /// to NewIdx (OldIdx < NewIdx).
1045 void handleMoveDown(LiveRange
&LR
) {
1046 LiveRange::iterator E
= LR
.end();
1047 // Segment going into OldIdx.
1048 LiveRange::iterator OldIdxIn
= LR
.find(OldIdx
.getBaseIndex());
1050 // No value live before or after OldIdx? Nothing to do.
1051 if (OldIdxIn
== E
|| SlotIndex::isEarlierInstr(OldIdx
, OldIdxIn
->start
))
1054 LiveRange::iterator OldIdxOut
;
1055 // Do we have a value live-in to OldIdx?
1056 if (SlotIndex::isEarlierInstr(OldIdxIn
->start
, OldIdx
)) {
1057 // If the live-in value already extends to NewIdx, there is nothing to do.
1058 if (SlotIndex::isEarlierEqualInstr(NewIdx
, OldIdxIn
->end
))
1060 // Aggressively remove all kill flags from the old kill point.
1061 // Kill flags shouldn't be used while live intervals exist, they will be
1062 // reinserted by VirtRegRewriter.
1063 if (MachineInstr
*KillMI
= LIS
.getInstructionFromIndex(OldIdxIn
->end
))
1064 for (MIBundleOperands
MO(*KillMI
); MO
.isValid(); ++MO
)
1065 if (MO
->isReg() && MO
->isUse())
1066 MO
->setIsKill(false);
1068 // Is there a def before NewIdx which is not OldIdx?
1069 LiveRange::iterator Next
= std::next(OldIdxIn
);
1070 if (Next
!= E
&& !SlotIndex::isSameInstr(OldIdx
, Next
->start
) &&
1071 SlotIndex::isEarlierInstr(Next
->start
, NewIdx
)) {
1072 // If we are here then OldIdx was just a use but not a def. We only have
1073 // to ensure liveness extends to NewIdx.
1074 LiveRange::iterator NewIdxIn
=
1075 LR
.advanceTo(Next
, NewIdx
.getBaseIndex());
1076 // Extend the segment before NewIdx if necessary.
1077 if (NewIdxIn
== E
||
1078 !SlotIndex::isEarlierInstr(NewIdxIn
->start
, NewIdx
)) {
1079 LiveRange::iterator Prev
= std::prev(NewIdxIn
);
1080 Prev
->end
= NewIdx
.getRegSlot();
1083 OldIdxIn
->end
= Next
->start
;
1087 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1088 // invalid by overlapping ranges.
1089 bool isKill
= SlotIndex::isSameInstr(OldIdx
, OldIdxIn
->end
);
1090 OldIdxIn
->end
= NewIdx
.getRegSlot(OldIdxIn
->end
.isEarlyClobber());
1091 // If this was not a kill, then there was no def and we're done.
1095 // Did we have a Def at OldIdx?
1097 if (OldIdxOut
== E
|| !SlotIndex::isSameInstr(OldIdx
, OldIdxOut
->start
))
1100 OldIdxOut
= OldIdxIn
;
1103 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1104 // to the segment starting there.
1105 assert(OldIdxOut
!= E
&& SlotIndex::isSameInstr(OldIdx
, OldIdxOut
->start
) &&
1107 VNInfo
*OldIdxVNI
= OldIdxOut
->valno
;
1108 assert(OldIdxVNI
->def
== OldIdxOut
->start
&& "Inconsistent def");
1110 // If the defined value extends beyond NewIdx, just move the beginning
1111 // of the segment to NewIdx.
1112 SlotIndex NewIdxDef
= NewIdx
.getRegSlot(OldIdxOut
->start
.isEarlyClobber());
1113 if (SlotIndex::isEarlierInstr(NewIdxDef
, OldIdxOut
->end
)) {
1114 OldIdxVNI
->def
= NewIdxDef
;
1115 OldIdxOut
->start
= OldIdxVNI
->def
;
1119 // If we are here then we have a Definition at OldIdx which ends before
1122 // Is there an existing Def at NewIdx?
1123 LiveRange::iterator AfterNewIdx
1124 = LR
.advanceTo(OldIdxOut
, NewIdx
.getRegSlot());
1125 bool OldIdxDefIsDead
= OldIdxOut
->end
.isDead();
1126 if (!OldIdxDefIsDead
&&
1127 SlotIndex::isEarlierInstr(OldIdxOut
->end
, NewIdxDef
)) {
1128 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1130 if (OldIdxOut
!= LR
.begin() &&
1131 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut
)->end
,
1132 OldIdxOut
->start
)) {
1133 // There is no gap between OldIdxOut and its predecessor anymore,
1135 LiveRange::iterator IPrev
= std::prev(OldIdxOut
);
1137 IPrev
->end
= OldIdxOut
->end
;
1139 // The value is live in to OldIdx
1140 LiveRange::iterator INext
= std::next(OldIdxOut
);
1141 assert(INext
!= E
&& "Must have following segment");
1142 // We merge OldIdxOut and its successor. As we're dealing with subreg
1143 // reordering, there is always a successor to OldIdxOut in the same BB
1144 // We don't need INext->valno anymore and will reuse for the new segment
1147 INext
->start
= OldIdxOut
->end
;
1148 INext
->valno
->def
= INext
->start
;
1150 // If NewIdx is behind the last segment, extend that and append a new one.
1151 if (AfterNewIdx
== E
) {
1152 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1154 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1155 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1156 std::copy(std::next(OldIdxOut
), E
, OldIdxOut
);
1157 // The last segment is undefined now, reuse it for a dead def.
1158 LiveRange::iterator NewSegment
= std::prev(E
);
1159 *NewSegment
= LiveRange::Segment(NewIdxDef
, NewIdxDef
.getDeadSlot(),
1161 DefVNI
->def
= NewIdxDef
;
1163 LiveRange::iterator Prev
= std::prev(NewSegment
);
1164 Prev
->end
= NewIdxDef
;
1166 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1168 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1169 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1170 std::copy(std::next(OldIdxOut
), std::next(AfterNewIdx
), OldIdxOut
);
1171 LiveRange::iterator Prev
= std::prev(AfterNewIdx
);
1172 // We have two cases:
1173 if (SlotIndex::isEarlierInstr(Prev
->start
, NewIdxDef
)) {
1174 // Case 1: NewIdx is inside a liverange. Split this liverange at
1175 // NewIdxDef into the segment "Prev" followed by "NewSegment".
1176 LiveRange::iterator NewSegment
= AfterNewIdx
;
1177 *NewSegment
= LiveRange::Segment(NewIdxDef
, Prev
->end
, Prev
->valno
);
1178 Prev
->valno
->def
= NewIdxDef
;
1180 *Prev
= LiveRange::Segment(Prev
->start
, NewIdxDef
, DefVNI
);
1181 DefVNI
->def
= Prev
->start
;
1183 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1184 // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1185 *Prev
= LiveRange::Segment(NewIdxDef
, AfterNewIdx
->start
, DefVNI
);
1186 DefVNI
->def
= NewIdxDef
;
1187 assert(DefVNI
!= AfterNewIdx
->valno
);
1193 if (AfterNewIdx
!= E
&&
1194 SlotIndex::isSameInstr(AfterNewIdx
->start
, NewIdxDef
)) {
1195 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1197 assert(AfterNewIdx
->valno
!= OldIdxVNI
&& "Multiple defs of value?");
1198 LR
.removeValNo(OldIdxVNI
);
1200 // There was no existing def at NewIdx. We need to create a dead def
1201 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1202 // a new segment at the place where we want to construct the dead def.
1203 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1204 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1205 assert(AfterNewIdx
!= OldIdxOut
&& "Inconsistent iterators");
1206 std::copy(std::next(OldIdxOut
), AfterNewIdx
, OldIdxOut
);
1207 // We can reuse OldIdxVNI now.
1208 LiveRange::iterator NewSegment
= std::prev(AfterNewIdx
);
1209 VNInfo
*NewSegmentVNI
= OldIdxVNI
;
1210 NewSegmentVNI
->def
= NewIdxDef
;
1211 *NewSegment
= LiveRange::Segment(NewIdxDef
, NewIdxDef
.getDeadSlot(),
1216 /// Update LR to reflect an instruction has been moved upwards from OldIdx
1217 /// to NewIdx (NewIdx < OldIdx).
1218 void handleMoveUp(LiveRange
&LR
, unsigned Reg
, LaneBitmask LaneMask
) {
1219 LiveRange::iterator E
= LR
.end();
1220 // Segment going into OldIdx.
1221 LiveRange::iterator OldIdxIn
= LR
.find(OldIdx
.getBaseIndex());
1223 // No value live before or after OldIdx? Nothing to do.
1224 if (OldIdxIn
== E
|| SlotIndex::isEarlierInstr(OldIdx
, OldIdxIn
->start
))
1227 LiveRange::iterator OldIdxOut
;
1228 // Do we have a value live-in to OldIdx?
1229 if (SlotIndex::isEarlierInstr(OldIdxIn
->start
, OldIdx
)) {
1230 // If the live-in value isn't killed here, then we have no Def at
1231 // OldIdx, moreover the value must be live at NewIdx so there is nothing
1233 bool isKill
= SlotIndex::isSameInstr(OldIdx
, OldIdxIn
->end
);
1237 // At this point we have to move OldIdxIn->end back to the nearest
1238 // previous use or (dead-)def but no further than NewIdx.
1239 SlotIndex DefBeforeOldIdx
1240 = std::max(OldIdxIn
->start
.getDeadSlot(),
1241 NewIdx
.getRegSlot(OldIdxIn
->end
.isEarlyClobber()));
1242 OldIdxIn
->end
= findLastUseBefore(DefBeforeOldIdx
, Reg
, LaneMask
);
1244 // Did we have a Def at OldIdx? If not we are done now.
1245 OldIdxOut
= std::next(OldIdxIn
);
1246 if (OldIdxOut
== E
|| !SlotIndex::isSameInstr(OldIdx
, OldIdxOut
->start
))
1249 OldIdxOut
= OldIdxIn
;
1250 OldIdxIn
= OldIdxOut
!= LR
.begin() ? std::prev(OldIdxOut
) : E
;
1253 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1254 // to the segment starting there.
1255 assert(OldIdxOut
!= E
&& SlotIndex::isSameInstr(OldIdx
, OldIdxOut
->start
) &&
1257 VNInfo
*OldIdxVNI
= OldIdxOut
->valno
;
1258 assert(OldIdxVNI
->def
== OldIdxOut
->start
&& "Inconsistent def");
1259 bool OldIdxDefIsDead
= OldIdxOut
->end
.isDead();
1261 // Is there an existing def at NewIdx?
1262 SlotIndex NewIdxDef
= NewIdx
.getRegSlot(OldIdxOut
->start
.isEarlyClobber());
1263 LiveRange::iterator NewIdxOut
= LR
.find(NewIdx
.getRegSlot());
1264 if (SlotIndex::isSameInstr(NewIdxOut
->start
, NewIdx
)) {
1265 assert(NewIdxOut
->valno
!= OldIdxVNI
&&
1266 "Same value defined more than once?");
1267 // If OldIdx was a dead def remove it.
1268 if (!OldIdxDefIsDead
) {
1269 // Remove segment starting at NewIdx and move begin of OldIdxOut to
1270 // NewIdx so it can take its place.
1271 OldIdxVNI
->def
= NewIdxDef
;
1272 OldIdxOut
->start
= NewIdxDef
;
1273 LR
.removeValNo(NewIdxOut
->valno
);
1275 // Simply remove the dead def at OldIdx.
1276 LR
.removeValNo(OldIdxVNI
);
1279 // Previously nothing was live after NewIdx, so all we have to do now is
1280 // move the begin of OldIdxOut to NewIdx.
1281 if (!OldIdxDefIsDead
) {
1282 // Do we have any intermediate Defs between OldIdx and NewIdx?
1283 if (OldIdxIn
!= E
&&
1284 SlotIndex::isEarlierInstr(NewIdxDef
, OldIdxIn
->start
)) {
1285 // OldIdx is not a dead def and NewIdx is before predecessor start.
1286 LiveRange::iterator NewIdxIn
= NewIdxOut
;
1287 assert(NewIdxIn
== LR
.find(NewIdx
.getBaseIndex()));
1288 const SlotIndex SplitPos
= NewIdxDef
;
1289 OldIdxVNI
= OldIdxIn
->valno
;
1291 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1292 OldIdxOut
->valno
->def
= OldIdxIn
->start
;
1293 *OldIdxOut
= LiveRange::Segment(OldIdxIn
->start
, OldIdxOut
->end
,
1295 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1296 // We Slide [NewIdxIn, OldIdxIn) down one position.
1297 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1298 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1299 std::copy_backward(NewIdxIn
, OldIdxIn
, OldIdxOut
);
1300 // NewIdxIn is now considered undef so we can reuse it for the moved
1302 LiveRange::iterator NewSegment
= NewIdxIn
;
1303 LiveRange::iterator Next
= std::next(NewSegment
);
1304 if (SlotIndex::isEarlierInstr(Next
->start
, NewIdx
)) {
1305 // There is no gap between NewSegment and its predecessor.
1306 *NewSegment
= LiveRange::Segment(Next
->start
, SplitPos
,
1308 *Next
= LiveRange::Segment(SplitPos
, Next
->end
, OldIdxVNI
);
1309 Next
->valno
->def
= SplitPos
;
1311 // There is a gap between NewSegment and its predecessor
1312 // Value becomes live in.
1313 *NewSegment
= LiveRange::Segment(SplitPos
, Next
->start
, OldIdxVNI
);
1314 NewSegment
->valno
->def
= SplitPos
;
1317 // Leave the end point of a live def.
1318 OldIdxOut
->start
= NewIdxDef
;
1319 OldIdxVNI
->def
= NewIdxDef
;
1320 if (OldIdxIn
!= E
&& SlotIndex::isEarlierInstr(NewIdx
, OldIdxIn
->end
))
1321 OldIdxIn
->end
= NewIdx
.getRegSlot();
1323 } else if (OldIdxIn
!= E
1324 && SlotIndex::isEarlierInstr(NewIdxOut
->start
, NewIdx
)
1325 && SlotIndex::isEarlierInstr(NewIdx
, NewIdxOut
->end
)) {
1326 // OldIdxVNI is a dead def that has been moved into the middle of
1327 // another value in LR. That can happen when LR is a whole register,
1328 // but the dead def is a write to a subreg that is dead at NewIdx.
1329 // The dead def may have been moved across other values
1330 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1331 // down one position.
1332 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1333 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1334 std::copy_backward(NewIdxOut
, OldIdxOut
, std::next(OldIdxOut
));
1335 // Modify the segment at NewIdxOut and the following segment to meet at
1336 // the point of the dead def, with the following segment getting
1337 // OldIdxVNI as its value number.
1338 *NewIdxOut
= LiveRange::Segment(
1339 NewIdxOut
->start
, NewIdxDef
.getRegSlot(), NewIdxOut
->valno
);
1340 *(NewIdxOut
+ 1) = LiveRange::Segment(
1341 NewIdxDef
.getRegSlot(), (NewIdxOut
+ 1)->end
, OldIdxVNI
);
1342 OldIdxVNI
->def
= NewIdxDef
;
1343 // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1344 for (auto Idx
= NewIdxOut
+ 2; Idx
<= OldIdxOut
; ++Idx
)
1345 Idx
->valno
= OldIdxVNI
;
1346 // Aggressively remove all dead flags from the former dead definition.
1347 // Kill/dead flags shouldn't be used while live intervals exist; they
1348 // will be reinserted by VirtRegRewriter.
1349 if (MachineInstr
*KillMI
= LIS
.getInstructionFromIndex(NewIdx
))
1350 for (MIBundleOperands
MO(*KillMI
); MO
.isValid(); ++MO
)
1351 if (MO
->isReg() && !MO
->isUse())
1352 MO
->setIsDead(false);
1354 // OldIdxVNI is a dead def. It may have been moved across other values
1355 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1356 // down one position.
1357 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1358 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1359 std::copy_backward(NewIdxOut
, OldIdxOut
, std::next(OldIdxOut
));
1360 // OldIdxVNI can be reused now to build a new dead def segment.
1361 LiveRange::iterator NewSegment
= NewIdxOut
;
1362 VNInfo
*NewSegmentVNI
= OldIdxVNI
;
1363 *NewSegment
= LiveRange::Segment(NewIdxDef
, NewIdxDef
.getDeadSlot(),
1365 NewSegmentVNI
->def
= NewIdxDef
;
1370 void updateRegMaskSlots() {
1371 SmallVectorImpl
<SlotIndex
>::iterator RI
=
1372 llvm::lower_bound(LIS
.RegMaskSlots
, OldIdx
);
1373 assert(RI
!= LIS
.RegMaskSlots
.end() && *RI
== OldIdx
.getRegSlot() &&
1374 "No RegMask at OldIdx.");
1375 *RI
= NewIdx
.getRegSlot();
1376 assert((RI
== LIS
.RegMaskSlots
.begin() ||
1377 SlotIndex::isEarlierInstr(*std::prev(RI
), *RI
)) &&
1378 "Cannot move regmask instruction above another call");
1379 assert((std::next(RI
) == LIS
.RegMaskSlots
.end() ||
1380 SlotIndex::isEarlierInstr(*RI
, *std::next(RI
))) &&
1381 "Cannot move regmask instruction below another call");
1384 // Return the last use of reg between NewIdx and OldIdx.
1385 SlotIndex
findLastUseBefore(SlotIndex Before
, unsigned Reg
,
1386 LaneBitmask LaneMask
) {
1387 if (Register::isVirtualRegister(Reg
)) {
1388 SlotIndex LastUse
= Before
;
1389 for (MachineOperand
&MO
: MRI
.use_nodbg_operands(Reg
)) {
1392 unsigned SubReg
= MO
.getSubReg();
1393 if (SubReg
!= 0 && LaneMask
.any()
1394 && (TRI
.getSubRegIndexLaneMask(SubReg
) & LaneMask
).none())
1397 const MachineInstr
&MI
= *MO
.getParent();
1398 SlotIndex InstSlot
= LIS
.getSlotIndexes()->getInstructionIndex(MI
);
1399 if (InstSlot
> LastUse
&& InstSlot
< OldIdx
)
1400 LastUse
= InstSlot
.getRegSlot();
1405 // This is a regunit interval, so scanning the use list could be very
1406 // expensive. Scan upwards from OldIdx instead.
1407 assert(Before
< OldIdx
&& "Expected upwards move");
1408 SlotIndexes
*Indexes
= LIS
.getSlotIndexes();
1409 MachineBasicBlock
*MBB
= Indexes
->getMBBFromIndex(Before
);
1411 // OldIdx may not correspond to an instruction any longer, so set MII to
1412 // point to the next instruction after OldIdx, or MBB->end().
1413 MachineBasicBlock::iterator MII
= MBB
->end();
1414 if (MachineInstr
*MI
= Indexes
->getInstructionFromIndex(
1415 Indexes
->getNextNonNullIndex(OldIdx
)))
1416 if (MI
->getParent() == MBB
)
1419 MachineBasicBlock::iterator Begin
= MBB
->begin();
1420 while (MII
!= Begin
) {
1421 if ((--MII
)->isDebugInstr())
1423 SlotIndex Idx
= Indexes
->getInstructionIndex(*MII
);
1425 // Stop searching when Before is reached.
1426 if (!SlotIndex::isEarlierInstr(Before
, Idx
))
1429 // Check if MII uses Reg.
1430 for (MIBundleOperands
MO(*MII
); MO
.isValid(); ++MO
)
1431 if (MO
->isReg() && !MO
->isUndef() &&
1432 Register::isPhysicalRegister(MO
->getReg()) &&
1433 TRI
.hasRegUnit(MO
->getReg(), Reg
))
1434 return Idx
.getRegSlot();
1436 // Didn't reach Before. It must be the first instruction in the block.
1441 void LiveIntervals::handleMove(MachineInstr
&MI
, bool UpdateFlags
) {
1442 // It is fine to move a bundle as a whole, but not an individual instruction
1444 assert((!MI
.isBundled() || MI
.getOpcode() == TargetOpcode::BUNDLE
) &&
1445 "Cannot move instruction in bundle");
1446 SlotIndex OldIndex
= Indexes
->getInstructionIndex(MI
);
1447 Indexes
->removeMachineInstrFromMaps(MI
);
1448 SlotIndex NewIndex
= Indexes
->insertMachineInstrInMaps(MI
);
1449 assert(getMBBStartIdx(MI
.getParent()) <= OldIndex
&&
1450 OldIndex
< getMBBEndIdx(MI
.getParent()) &&
1451 "Cannot handle moves across basic block boundaries.");
1453 HMEditor
HME(*this, *MRI
, *TRI
, OldIndex
, NewIndex
, UpdateFlags
);
1454 HME
.updateAllRanges(&MI
);
1457 void LiveIntervals::handleMoveIntoBundle(MachineInstr
&MI
,
1458 MachineInstr
&BundleStart
,
1460 SlotIndex OldIndex
= Indexes
->getInstructionIndex(MI
);
1461 SlotIndex NewIndex
= Indexes
->getInstructionIndex(BundleStart
);
1462 HMEditor
HME(*this, *MRI
, *TRI
, OldIndex
, NewIndex
, UpdateFlags
);
1463 HME
.updateAllRanges(&MI
);
1466 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin
,
1467 const MachineBasicBlock::iterator End
,
1468 const SlotIndex endIdx
,
1469 LiveRange
&LR
, const unsigned Reg
,
1470 LaneBitmask LaneMask
) {
1471 LiveInterval::iterator LII
= LR
.find(endIdx
);
1472 SlotIndex lastUseIdx
;
1473 if (LII
== LR
.begin()) {
1474 // This happens when the function is called for a subregister that only
1475 // occurs _after_ the range that is to be repaired.
1478 if (LII
!= LR
.end() && LII
->start
< endIdx
)
1479 lastUseIdx
= LII
->end
;
1483 for (MachineBasicBlock::iterator I
= End
; I
!= Begin
;) {
1485 MachineInstr
&MI
= *I
;
1486 if (MI
.isDebugInstr())
1489 SlotIndex instrIdx
= getInstructionIndex(MI
);
1490 bool isStartValid
= getInstructionFromIndex(LII
->start
);
1491 bool isEndValid
= getInstructionFromIndex(LII
->end
);
1493 // FIXME: This doesn't currently handle early-clobber or multiple removed
1494 // defs inside of the region to repair.
1495 for (MachineInstr::mop_iterator OI
= MI
.operands_begin(),
1496 OE
= MI
.operands_end();
1498 const MachineOperand
&MO
= *OI
;
1499 if (!MO
.isReg() || MO
.getReg() != Reg
)
1502 unsigned SubReg
= MO
.getSubReg();
1503 LaneBitmask Mask
= TRI
->getSubRegIndexLaneMask(SubReg
);
1504 if ((Mask
& LaneMask
).none())
1508 if (!isStartValid
) {
1509 if (LII
->end
.isDead()) {
1510 SlotIndex prevStart
;
1511 if (LII
!= LR
.begin())
1512 prevStart
= std::prev(LII
)->start
;
1514 // FIXME: This could be more efficient if there was a
1515 // removeSegment method that returned an iterator.
1516 LR
.removeSegment(*LII
, true);
1517 if (prevStart
.isValid())
1518 LII
= LR
.find(prevStart
);
1522 LII
->start
= instrIdx
.getRegSlot();
1523 LII
->valno
->def
= instrIdx
.getRegSlot();
1524 if (MO
.getSubReg() && !MO
.isUndef())
1525 lastUseIdx
= instrIdx
.getRegSlot();
1527 lastUseIdx
= SlotIndex();
1532 if (!lastUseIdx
.isValid()) {
1533 VNInfo
*VNI
= LR
.getNextValue(instrIdx
.getRegSlot(), VNInfoAllocator
);
1534 LiveRange::Segment
S(instrIdx
.getRegSlot(),
1535 instrIdx
.getDeadSlot(), VNI
);
1536 LII
= LR
.addSegment(S
);
1537 } else if (LII
->start
!= instrIdx
.getRegSlot()) {
1538 VNInfo
*VNI
= LR
.getNextValue(instrIdx
.getRegSlot(), VNInfoAllocator
);
1539 LiveRange::Segment
S(instrIdx
.getRegSlot(), lastUseIdx
, VNI
);
1540 LII
= LR
.addSegment(S
);
1543 if (MO
.getSubReg() && !MO
.isUndef())
1544 lastUseIdx
= instrIdx
.getRegSlot();
1546 lastUseIdx
= SlotIndex();
1547 } else if (MO
.isUse()) {
1548 // FIXME: This should probably be handled outside of this branch,
1549 // either as part of the def case (for defs inside of the region) or
1550 // after the loop over the region.
1551 if (!isEndValid
&& !LII
->end
.isBlock())
1552 LII
->end
= instrIdx
.getRegSlot();
1553 if (!lastUseIdx
.isValid())
1554 lastUseIdx
= instrIdx
.getRegSlot();
1561 LiveIntervals::repairIntervalsInRange(MachineBasicBlock
*MBB
,
1562 MachineBasicBlock::iterator Begin
,
1563 MachineBasicBlock::iterator End
,
1564 ArrayRef
<unsigned> OrigRegs
) {
1565 // Find anchor points, which are at the beginning/end of blocks or at
1566 // instructions that already have indexes.
1567 while (Begin
!= MBB
->begin() && !Indexes
->hasIndex(*Begin
))
1569 while (End
!= MBB
->end() && !Indexes
->hasIndex(*End
))
1573 if (End
== MBB
->end())
1574 endIdx
= getMBBEndIdx(MBB
).getPrevSlot();
1576 endIdx
= getInstructionIndex(*End
);
1578 Indexes
->repairIndexesInRange(MBB
, Begin
, End
);
1580 for (MachineBasicBlock::iterator I
= End
; I
!= Begin
;) {
1582 MachineInstr
&MI
= *I
;
1583 if (MI
.isDebugInstr())
1585 for (MachineInstr::const_mop_iterator MOI
= MI
.operands_begin(),
1586 MOE
= MI
.operands_end();
1587 MOI
!= MOE
; ++MOI
) {
1588 if (MOI
->isReg() && Register::isVirtualRegister(MOI
->getReg()) &&
1589 !hasInterval(MOI
->getReg())) {
1590 createAndComputeVirtRegInterval(MOI
->getReg());
1595 for (unsigned Reg
: OrigRegs
) {
1596 if (!Register::isVirtualRegister(Reg
))
1599 LiveInterval
&LI
= getInterval(Reg
);
1600 // FIXME: Should we support undefs that gain defs?
1601 if (!LI
.hasAtLeastOneValue())
1604 for (LiveInterval::SubRange
&S
: LI
.subranges())
1605 repairOldRegInRange(Begin
, End
, endIdx
, S
, Reg
, S
.LaneMask
);
1607 repairOldRegInRange(Begin
, End
, endIdx
, LI
, Reg
);
1611 void LiveIntervals::removePhysRegDefAt(unsigned Reg
, SlotIndex Pos
) {
1612 for (MCRegUnitIterator
Unit(Reg
, TRI
); Unit
.isValid(); ++Unit
) {
1613 if (LiveRange
*LR
= getCachedRegUnit(*Unit
))
1614 if (VNInfo
*VNI
= LR
->getVNInfoAt(Pos
))
1615 LR
->removeValNo(VNI
);
1619 void LiveIntervals::removeVRegDefAt(LiveInterval
&LI
, SlotIndex Pos
) {
1620 // LI may not have the main range computed yet, but its subranges may
1622 VNInfo
*VNI
= LI
.getVNInfoAt(Pos
);
1623 if (VNI
!= nullptr) {
1624 assert(VNI
->def
.getBaseIndex() == Pos
.getBaseIndex());
1625 LI
.removeValNo(VNI
);
1628 // Also remove the value defined in subranges.
1629 for (LiveInterval::SubRange
&S
: LI
.subranges()) {
1630 if (VNInfo
*SVNI
= S
.getVNInfoAt(Pos
))
1631 if (SVNI
->def
.getBaseIndex() == Pos
.getBaseIndex())
1632 S
.removeValNo(SVNI
);
1634 LI
.removeEmptySubRanges();
1637 void LiveIntervals::splitSeparateComponents(LiveInterval
&LI
,
1638 SmallVectorImpl
<LiveInterval
*> &SplitLIs
) {
1639 ConnectedVNInfoEqClasses
ConEQ(*this);
1640 unsigned NumComp
= ConEQ
.Classify(LI
);
1643 LLVM_DEBUG(dbgs() << " Split " << NumComp
<< " components: " << LI
<< '\n');
1644 unsigned Reg
= LI
.reg
;
1645 const TargetRegisterClass
*RegClass
= MRI
->getRegClass(Reg
);
1646 for (unsigned I
= 1; I
< NumComp
; ++I
) {
1647 Register NewVReg
= MRI
->createVirtualRegister(RegClass
);
1648 LiveInterval
&NewLI
= createEmptyInterval(NewVReg
);
1649 SplitLIs
.push_back(&NewLI
);
1651 ConEQ
.Distribute(LI
, SplitLIs
.data(), *MRI
);
1654 void LiveIntervals::constructMainRangeFromSubranges(LiveInterval
&LI
) {
1655 assert(LRCalc
&& "LRCalc not initialized.");
1656 LRCalc
->reset(MF
, getSlotIndexes(), DomTree
, &getVNInfoAllocator());
1657 LRCalc
->constructMainRangeFromSubranges(LI
);