- for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
- delete RegUnitIntervals[i];
- RegUnitIntervals.clear();
+ for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
+ delete RegUnitRanges[i];
+ RegUnitRanges.clear();
- for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
- if (LiveInterval *LI = RegUnitIntervals[i])
- OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
+ for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
+ if (LiveRange *LR = RegUnitRanges[i])
+ OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n';
// Dump the virtregs.
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (hasInterval(Reg))
// Dump the virtregs.
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (hasInterval(Reg))
return new LiveInterval(reg, Weight);
}
/// computeVirtRegInterval - Compute the live interval of a virtual register,
/// based on defs and uses.
return new LiveInterval(reg, Weight);
}
/// computeVirtRegInterval - Compute the live interval of a virtual register,
/// based on defs and uses.
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
LRCalc->createDeadDefs(LI);
LRCalc->extendToUses(LI);
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
LRCalc->createDeadDefs(LI);
LRCalc->extendToUses(LI);
-/// computeRegUnitInterval - Compute the live interval of a register unit, based
-/// on the uses and defs of aliasing registers. The interval should be empty,
+/// computeRegUnitInterval - Compute the live range of a register unit, based
+/// on the uses and defs of aliasing registers. The range should be empty,
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
Supers.isValid(); ++Supers) {
if (!MRI->reg_empty(*Supers))
for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
Supers.isValid(); ++Supers) {
if (!MRI->reg_empty(*Supers))
// Ignore uses of reserved registers. We only track defs of those.
for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
Supers.isValid(); ++Supers) {
unsigned Reg = *Supers;
if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
// Ignore uses of reserved registers. We only track defs of those.
for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
Supers.isValid(); ++Supers) {
unsigned Reg = *Supers;
if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
/// without a corresponding def when entering the entry block or a landing pad.
///
void LiveIntervals::computeLiveInRegUnits() {
/// without a corresponding def when entering the entry block or a landing pad.
///
void LiveIntervals::computeLiveInRegUnits() {
- // Keep track of the intervals allocated.
- SmallVector<LiveInterval*, 8> NewIntvs;
+ // Keep track of the live range sets allocated.
+ SmallVector<unsigned, 8> NewRanges;
// Check all basic blocks for live-ins.
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
// Check all basic blocks for live-ins.
for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
LIE = MBB->livein_end(); LII != LIE; ++LII) {
for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
unsigned Unit = *Units;
LIE = MBB->livein_end(); LII != LIE; ++LII) {
for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
unsigned Unit = *Units;
- LiveInterval *Intv = RegUnitIntervals[Unit];
- if (!Intv) {
- Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF);
- NewIntvs.push_back(Intv);
+ LiveRange *LR = RegUnitRanges[Unit];
+ if (!LR) {
+ LR = RegUnitRanges[Unit] = new LiveRange();
+ NewRanges.push_back(Unit);
- // Compute the 'normal' part of the intervals.
- for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
- computeRegUnitInterval(NewIntvs[i]);
+ // Compute the 'normal' part of the ranges.
+ for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
+ unsigned Unit = NewRanges[i];
+ computeRegUnitRange(*RegUnitRanges[Unit], Unit);
+ }
if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
continue;
SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
continue;
SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
VNInfo *VNI = LRQ.valueIn();
if (!VNI) {
// This shouldn't happen: readsVirtualRegister returns true, but there is
VNInfo *VNI = LRQ.valueIn();
if (!VNI) {
// This shouldn't happen: readsVirtualRegister returns true, but there is
(void)ExtVNI;
assert(ExtVNI == VNI && "Unexpected existing value number");
// Is this a PHIDef we haven't seen before?
(void)ExtVNI;
assert(ExtVNI == VNI && "Unexpected existing value number");
// Is this a PHIDef we haven't seen before?
// Make sure VNI is live-out from the predecessors.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
// Make sure VNI is live-out from the predecessors.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
- LiveInterval::iterator LII = NewLI.FindSegmentContaining(VNI->def);
- assert(LII != NewLI.end() && "Missing segment for PHI");
- if (LII->end != VNI->def.getDeadSlot())
+ LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def);
+ assert(LRI != NewLR.end() && "Missing segment for PHI");
+ if (LRI->end != VNI->def.getDeadSlot())
ArrayRef<SlotIndex> Indices) {
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
for (unsigned i = 0, e = Indices.size(); i != e; ++i)
ArrayRef<SlotIndex> Indices) {
assert(LRCalc && "LRCalc not initialized.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
for (unsigned i = 0, e = Indices.size(); i != e; ++i)
}
void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
SmallVectorImpl<SlotIndex> *EndPoints) {
}
void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
SmallVectorImpl<SlotIndex> *EndPoints) {
// Check if VNI is live in to MBB.
tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
// Check if VNI is live in to MBB.
tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
// There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
bool CancelKill = false;
for (unsigned u = 0, e = RU.size(); u != e; ++u) {
// There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
bool CancelKill = false;
for (unsigned u = 0, e = RU.size(); u != e; ++u) {
- LiveInterval *RInt = RU[u].first;
- LiveInterval::iterator &I = RU[u].second;
- if (I == RInt->end())
+ LiveRange &RRanges = *RU[u].first;
+ LiveRange::iterator &I = RU[u].second;
+ if (I == RRanges.end())
- I = RInt->advanceTo(I, RI->end);
- if (I == RInt->end() || I->start >= RI->end)
+ I = RRanges.advanceTo(I, RI->end);
+ if (I == RRanges.end() || I->start >= RI->end)
LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
LiveInterval& Interval = createEmptyInterval(reg);
VNInfo* VN = Interval.getNextValue(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getVNInfoAllocator());
LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
LiveInterval& Interval = createEmptyInterval(reg);
VNInfo* VN = Interval.getNextValue(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getVNInfoAllocator());
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getMBBEndIdx(startInst->getParent()), VN);
Interval.addSegment(S);
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getMBBEndIdx(startInst->getParent()), VN);
Interval.addSegment(S);
// physregs, even those that aren't needed for regalloc, in order to update
// kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
// flags, and postRA passes will use a live register utility instead.
// physregs, even those that aren't needed for regalloc, in order to update
// kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
// flags, and postRA passes will use a live register utility instead.
continue;
}
// For physregs, only update the regunits that actually have a
// precomputed live range.
for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
continue;
}
// For physregs, only update the regunits that actually have a
// precomputed live range.
for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
- void updateRange(LiveInterval &LI) {
- if (!Updated.insert(&LI))
+ void updateRange(LiveRange &LR, unsigned Reg) {
+ if (!Updated.insert(&LR))
- dbgs() << PrintRegUnit(LI.reg, &TRI);
- dbgs() << ":\t" << LI << '\n';
+ dbgs() << PrintRegUnit(Reg, &TRI);
+ dbgs() << ":\t" << LR << '\n';
/// 5. Value read at OldIdx, killed before NewIdx:
/// Extend kill to NewIdx.
///
/// 5. Value read at OldIdx, killed before NewIdx:
/// Extend kill to NewIdx.
///
- LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
- LiveInterval::iterator E = LI.end();
- // Is LI even live at OldIdx?
+ LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
+ LiveRange::iterator E = LR.end();
+ // Is LR even live at OldIdx?
// overlapping ranges. Case 5 above.
I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
// If this was a kill, there may also be a def. Otherwise we're done.
// overlapping ranges. Case 5 above.
I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
// If this was a kill, there may also be a def. Otherwise we're done.
assert((I->end == OldIdx.getDeadSlot() ||
SlotIndex::isSameInstr(I->end, NewIdx)) &&
"Cannot move def below kill");
assert((I->end == OldIdx.getDeadSlot() ||
SlotIndex::isSameInstr(I->end, NewIdx)) &&
"Cannot move def below kill");
if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
// There is an existing def at NewIdx, case 4 above. The def at OldIdx is
// coalesced into that value.
assert(NewI->valno != DefVNI && "Multiple defs of value?");
if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
// There is an existing def at NewIdx, case 4 above. The def at OldIdx is
// coalesced into that value.
assert(NewI->valno != DefVNI && "Multiple defs of value?");
// values. The new range should be placed immediately before NewI, move any
// intermediate ranges up.
assert(NewI != I && "Inconsistent iterators");
std::copy(llvm::next(I), NewI, I);
*llvm::prior(NewI)
// values. The new range should be placed immediately before NewI, move any
// intermediate ranges up.
assert(NewI != I && "Inconsistent iterators");
std::copy(llvm::next(I), NewI, I);
*llvm::prior(NewI)
- LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
- LiveInterval::iterator E = LI.end();
- // Is LI even live at OldIdx?
+ LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
+ LiveRange::iterator E = LR.end();
+ // Is LR even live at OldIdx?
if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
// No def, search for the new kill.
// This can never be an early clobber kill since there is no def.
if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
// No def, search for the new kill.
// This can never be an early clobber kill since there is no def.
if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
assert(NewI->valno != DefVNI && "Same value defined more than once?");
// There is an existing def at NewIdx.
if (I->end.isDead()) {
// Case 3: Remove the dead def at OldIdx.
if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
assert(NewI->valno != DefVNI && "Same value defined more than once?");
// There is an existing def at NewIdx.
if (I->end.isDead()) {
// Case 3: Remove the dead def at OldIdx.
// so move I up to NewI. Slide [NewI;I) down one position.
std::copy_backward(NewI, I, llvm::next(I));
// so move I up to NewI. Slide [NewI;I) down one position.
std::copy_backward(NewI, I, llvm::next(I));
if (!lastUseIdx.isValid()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);
if (!lastUseIdx.isValid()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);
- LiveInterval::Segment S(instrIdx.getRegSlot(),
- instrIdx.getDeadSlot(), VNI);
+ LiveRange::Segment S(instrIdx.getRegSlot(),
+ instrIdx.getDeadSlot(), VNI);
LII = LI.addSegment(S);
} else if (LII->start != instrIdx.getRegSlot()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);
LII = LI.addSegment(S);
} else if (LII->start != instrIdx.getRegSlot()) {
VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
VNInfoAllocator);