#include "llvm/Value.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
+#include "LiveRangeCalc.h"
#include <algorithm>
#include <limits>
#include <cmath>
using namespace llvm;
-// Hidden options for help debugging.
-static cl::opt<bool> DisableReMat("disable-rematerialization",
- cl::init(false), cl::Hidden);
-
-STATISTIC(numIntervals , "Number of original intervals");
+// Switch to the new experimental algorithm for computing live intervals.
+static cl::opt<bool>
+NewLiveIntervals("new-live-intervals", cl::Hidden,
+ cl::desc("Use new algorithm forcomputing live intervals"));
char LiveIntervals::ID = 0;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
AU.addRequired<LiveVariables>();
AU.addPreserved<LiveVariables>();
AU.addPreservedID(MachineLoopInfoID);
+ AU.addRequiredTransitiveID(MachineDominatorsID);
AU.addPreservedID(MachineDominatorsID);
AU.addPreserved<SlotIndexes>();
AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
+LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
+ DomTree(0), LRCalc(0) {
+ initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+}
+
+LiveIntervals::~LiveIntervals() {
+ delete LRCalc;
+}
+
void LiveIntervals::releaseMemory() {
// Free the live intervals themselves.
- for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
- E = r2iMap_.end(); I != E; ++I)
- delete I->second;
-
- r2iMap_.clear();
+ for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
+ delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
+ VirtRegIntervals.clear();
RegMaskSlots.clear();
RegMaskBits.clear();
RegMaskBlocks.clear();
+ for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
+ delete RegUnitIntervals[i];
+ RegUnitIntervals.clear();
+
// Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
VNInfoAllocator.Reset();
}
/// runOnMachineFunction - Register allocate the whole function
///
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
- mf_ = &fn;
- mri_ = &mf_->getRegInfo();
- tm_ = &fn.getTarget();
- tri_ = tm_->getRegisterInfo();
- tii_ = tm_->getInstrInfo();
- aa_ = &getAnalysis<AliasAnalysis>();
- lv_ = &getAnalysis<LiveVariables>();
- indexes_ = &getAnalysis<SlotIndexes>();
- allocatableRegs_ = tri_->getAllocatableSet(fn);
- reservedRegs_ = tri_->getReservedRegs(fn);
-
- computeIntervals();
-
- numIntervals += getNumIntervals();
+ MF = &fn;
+ MRI = &MF->getRegInfo();
+ TM = &fn.getTarget();
+ TRI = TM->getRegisterInfo();
+ TII = TM->getInstrInfo();
+ AA = &getAnalysis<AliasAnalysis>();
+ LV = &getAnalysis<LiveVariables>();
+ Indexes = &getAnalysis<SlotIndexes>();
+ DomTree = &getAnalysis<MachineDominatorTree>();
+ if (!LRCalc)
+ LRCalc = new LiveRangeCalc();
+ AllocatableRegs = TRI->getAllocatableSet(fn);
+ ReservedRegs = TRI->getReservedRegs(fn);
+
+ // Allocate space for all virtual registers.
+ VirtRegIntervals.resize(MRI->getNumVirtRegs());
+
+ if (NewLiveIntervals) {
+ // This is the new way of computing live intervals.
+ // It is independent of LiveVariables, and it can run at any time.
+ for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+ unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+ if (MRI->reg_nodbg_empty(Reg))
+ continue;
+ LiveInterval *LI = createInterval(Reg);
+ VirtRegIntervals[Reg] = LI;
+ computeVirtRegInterval(LI);
+ }
+ } else {
+ // This is the old way of computing live intervals.
+ // It depends on LiveVariables.
+ computeIntervals();
+ }
+ computeLiveInRegUnits();
DEBUG(dump());
return true;
void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
OS << "********** INTERVALS **********\n";
- // Dump the physregs.
- for (unsigned Reg = 1, RegE = tri_->getNumRegs(); Reg != RegE; ++Reg)
- if (const LiveInterval *LI = r2iMap_.lookup(Reg)) {
- LI->print(OS, tri_);
- OS << '\n';
- }
+ // Dump the regunits.
+ for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
+ if (LiveInterval *LI = RegUnitIntervals[i])
+ OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
// Dump the virtregs.
- for (unsigned Reg = 0, RegE = mri_->getNumVirtRegs(); Reg != RegE; ++Reg)
- if (const LiveInterval *LI =
- r2iMap_.lookup(TargetRegisterInfo::index2VirtReg(Reg))) {
- LI->print(OS, tri_);
- OS << '\n';
- }
+ for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+ unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+ if (hasInterval(Reg))
+ OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
+ }
printInstrs(OS);
}
void LiveIntervals::printInstrs(raw_ostream &OS) const {
OS << "********** MACHINEINSTRS **********\n";
- mf_->print(OS, indexes_);
+ MF->print(OS, Indexes);
}
void LiveIntervals::dumpInstrs() const {
MachineOperand& MO,
unsigned MOIdx,
LiveInterval &interval) {
- DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
+ DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, TRI));
// Virtual registers may be defined multiple times (due to phi
// elimination and 2-addr elimination). Much of what we do only has to be
// done once for the vreg. We use an empty interval to detect the first
// time we see a vreg.
- LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
+ LiveVariables::VarInfo& vi = LV->getVarInfo(interval.reg);
if (interval.empty()) {
// Get the Idx of the defining instructions.
SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
- // Make sure the first definition is not a partial redefinition. Add an
- // <imp-def> of the full register.
- // FIXME: LiveIntervals shouldn't modify the code like this. Whoever
- // created the machine instruction should annotate it with <undef> flags
- // as needed. Then we can simply assert here. The REG_SEQUENCE lowering
- // is the main suspect.
- if (MO.getSubReg()) {
- mi->addRegisterDefined(interval.reg);
- // Mark all defs of interval.reg on this instruction as reading <undef>.
- for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) {
- MachineOperand &MO2 = mi->getOperand(i);
- if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg())
- MO2.setIsUndef();
- }
- }
+ // Make sure the first definition is not a partial redefinition.
+ assert(!MO.readsReg() && "First def cannot also read virtual register "
+ "missing <undef> flag?");
VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
assert(ValNo->id == 0 && "First value in interval is not 0?");
DEBUG(dbgs() << " +" << NewLR);
interval.addRange(NewLR);
- bool PHIJoin = lv_->isPHIJoin(interval.reg);
+ bool PHIJoin = LV->isPHIJoin(interval.reg);
if (PHIJoin) {
- // A phi join register is killed at the end of the MBB and revived as a new
- // valno in the killing blocks.
+ // A phi join register is killed at the end of the MBB and revived as a
+ // new valno in the killing blocks.
assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
DEBUG(dbgs() << " phi-join");
ValNo->setHasPHIKill(true);
// live interval.
for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
E = vi.AliveBlocks.end(); I != E; ++I) {
- MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
- LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
+ MachineBasicBlock *aliveBlock = MF->getBlockNumbered(*I);
+ LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock),
+ ValNo);
interval.addRange(LR);
DEBUG(dbgs() << " +" << LR);
}
interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(),
OldValNo));
- DEBUG({
- dbgs() << " RESULT: ";
- interval.print(dbgs(), tri_);
- });
- } else if (lv_->isPHIJoin(interval.reg)) {
+ DEBUG(dbgs() << " RESULT: " << interval);
+ } else if (LV->isPHIJoin(interval.reg)) {
// In the case of PHI elimination, each variable definition is only
// live until the end of the block. We've already taken care of the
// rest of the live range.
DEBUG(dbgs() << '\n');
}
-#ifndef NDEBUG
-static bool isRegLiveOutOf(const MachineBasicBlock *MBB, unsigned Reg) {
- for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end();
- SI != SE; ++SI) {
- const MachineBasicBlock* succ = *SI;
- if (succ->isLiveIn(Reg))
- return true;
- }
- return false;
-}
-#endif
-
-void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
- MachineBasicBlock::iterator mi,
- SlotIndex MIIdx,
- MachineOperand& MO,
- LiveInterval &interval) {
- DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
-
- SlotIndex baseIndex = MIIdx;
- SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber());
- SlotIndex end = start;
-
- // If it is not used after definition, it is considered dead at
- // the instruction defining it. Hence its interval is:
- // [defSlot(def), defSlot(def)+1)
- // For earlyclobbers, the defSlot was pushed back one; the extra
- // advance below compensates.
- if (MO.isDead()) {
- DEBUG(dbgs() << " dead");
- end = start.getDeadSlot();
- goto exit;
- }
-
- // If it is not dead on definition, it must be killed by a
- // subsequent instruction. Hence its interval is:
- // [defSlot(def), useSlot(kill)+1)
- baseIndex = baseIndex.getNextIndex();
- while (++mi != MBB->end()) {
-
- if (mi->isDebugValue())
- continue;
- if (getInstructionFromIndex(baseIndex) == 0)
- baseIndex = indexes_->getNextNonNullIndex(baseIndex);
-
- if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(dbgs() << " killed");
- end = baseIndex.getRegSlot();
- goto exit;
- } else {
- int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
- if (DefIdx != -1) {
- if (mi->isRegTiedToUseOperand(DefIdx)) {
- // Two-address instruction.
- end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber());
- } else {
- // Another instruction redefines the register before it is ever read.
- // Then the register is essentially dead at the instruction that
- // defines it. Hence its interval is:
- // [defSlot(def), defSlot(def)+1)
- DEBUG(dbgs() << " dead");
- end = start.getDeadSlot();
- }
- goto exit;
- }
- }
-
- baseIndex = baseIndex.getNextIndex();
- }
-
- // If we get here the register *should* be live out.
- assert(!isAllocatable(interval.reg) && "Physregs shouldn't be live out!");
-
- // FIXME: We need saner rules for reserved regs.
- if (isReserved(interval.reg)) {
- assert(!isRegLiveOutOf(MBB, interval.reg) && "Reserved reg live-out?");
- end = start.getDeadSlot();
- } else {
- // Unreserved, unallocable registers like EFLAGS can be live across basic
- // block boundaries.
- assert(isRegLiveOutOf(MBB, interval.reg) && "Unreserved reg not live-out?");
- end = getMBBEndIdx(MBB);
- }
-exit:
- assert(start < end && "did not find end of interval?");
-
- // Already exists? Extend old live interval.
- VNInfo *ValNo = interval.getVNInfoAt(start);
- bool Extend = ValNo != 0;
- if (!Extend)
- ValNo = interval.getNextValue(start, VNInfoAllocator);
- LiveRange LR(start, end, ValNo);
- interval.addRange(LR);
- DEBUG(dbgs() << " +" << LR << '\n');
-}
-
void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
SlotIndex MIIdx,
if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
getOrCreateInterval(MO.getReg()));
- else
- handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
- getOrCreateInterval(MO.getReg()));
-}
-
-void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
- SlotIndex MIIdx,
- LiveInterval &interval) {
- assert(TargetRegisterInfo::isPhysicalRegister(interval.reg) &&
- "Only physical registers can be live in.");
- assert((!isAllocatable(interval.reg) || MBB->getParent()->begin() ||
- MBB->isLandingPad()) &&
- "Allocatable live-ins only valid for entry blocks and landing pads.");
-
- DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
-
- // Look for kills, if it reaches a def before it's killed, then it shouldn't
- // be considered a livein.
- MachineBasicBlock::iterator mi = MBB->begin();
- MachineBasicBlock::iterator E = MBB->end();
- // Skip over DBG_VALUE at the start of the MBB.
- if (mi != E && mi->isDebugValue()) {
- while (++mi != E && mi->isDebugValue())
- ;
- if (mi == E)
- // MBB is empty except for DBG_VALUE's.
- return;
- }
-
- SlotIndex baseIndex = MIIdx;
- SlotIndex start = baseIndex;
- if (getInstructionFromIndex(baseIndex) == 0)
- baseIndex = indexes_->getNextNonNullIndex(baseIndex);
-
- SlotIndex end = baseIndex;
- bool SeenDefUse = false;
-
- while (mi != E) {
- if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(dbgs() << " killed");
- end = baseIndex.getRegSlot();
- SeenDefUse = true;
- break;
- } else if (mi->modifiesRegister(interval.reg, tri_)) {
- // Another instruction redefines the register before it is ever read.
- // Then the register is essentially dead at the instruction that defines
- // it. Hence its interval is:
- // [defSlot(def), defSlot(def)+1)
- DEBUG(dbgs() << " dead");
- end = start.getDeadSlot();
- SeenDefUse = true;
- break;
- }
-
- while (++mi != E && mi->isDebugValue())
- // Skip over DBG_VALUE.
- ;
- if (mi != E)
- baseIndex = indexes_->getNextNonNullIndex(baseIndex);
- }
-
- // Live-in register might not be used at all.
- if (!SeenDefUse) {
- if (isAllocatable(interval.reg) || isReserved(interval.reg)) {
- // This must be an entry block or landing pad - we asserted so on entry
- // to the function. For these blocks the interval is dead on entry.
- DEBUG(dbgs() << " dead");
- end = start.getDeadSlot();
- } else {
- assert(isRegLiveOutOf(MBB, interval.reg) &&
- "Live in reg untouched in block should be be live through.");
- DEBUG(dbgs() << " live through");
- end = getMBBEndIdx(MBB);
- }
- }
-
- SlotIndex defIdx = getMBBStartIdx(MBB);
- assert(getInstructionFromIndex(defIdx) == 0 &&
- "PHI def index points at actual instruction.");
- VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator);
- vni->setIsPHIDef(true);
- LiveRange LR(start, end, vni);
-
- interval.addRange(LR);
- DEBUG(dbgs() << " +" << LR << '\n');
}
/// computeIntervals - computes the live intervals for virtual
void LiveIntervals::computeIntervals() {
DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
<< "********** Function: "
- << ((Value*)mf_->getFunction())->getName() << '\n');
+ << ((Value*)MF->getFunction())->getName() << '\n');
- RegMaskBlocks.resize(mf_->getNumBlockIDs());
+ RegMaskBlocks.resize(MF->getNumBlockIDs());
SmallVector<unsigned, 8> UndefUses;
- for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
+ for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size();
DEBUG(dbgs() << "BB#" << MBB->getNumber()
<< ":\t\t# derived from " << MBB->getName() << "\n");
- // Create intervals for live-ins to this BB first.
- for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
- LE = MBB->livein_end(); LI != LE; ++LI) {
- handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
- }
-
// Skip over empty initial indices.
if (getInstructionFromIndex(MIIndex) == 0)
- MIIndex = indexes_->getNextNonNullIndex(MIIndex);
+ MIIndex = Indexes->getNextNonNullIndex(MIIndex);
for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
MI != miEnd; ++MI) {
DEBUG(dbgs() << MIIndex << "\t" << *MI);
if (MI->isDebugValue())
continue;
- assert(indexes_->getInstructionFromIndex(MIIndex) == MI &&
+ assert(Indexes->getInstructionFromIndex(MIIndex) == MI &&
"Lost SlotIndex synchronization");
// Handle defs.
continue;
}
- if (!MO.isReg() || !MO.getReg())
+ if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
continue;
// handle register defs - build intervals
}
// Move to the next instr slot.
- MIIndex = indexes_->getNextNonNullIndex(MIIndex);
+ MIIndex = Indexes->getNextNonNullIndex(MIIndex);
}
// Compute the number of register mask instructions in this block.
return new LiveInterval(reg, Weight);
}
-/// dupInterval - Duplicate a live interval. The caller is responsible for
-/// managing the allocated memory.
-LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
- LiveInterval *NewLI = createInterval(li->reg);
- NewLI->Copy(*li, mri_, getVNInfoAllocator());
- return NewLI;
+
+/// computeVirtRegInterval - Compute the live interval of a virtual register,
+/// based on defs and uses.
+void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) {
+ assert(LRCalc && "LRCalc not initialized.");
+ assert(LI->empty() && "Should only compute empty intervals.");
+ LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
+ LRCalc->createDeadDefs(LI);
+ LRCalc->extendToUses(LI);
+}
+
+
+//===----------------------------------------------------------------------===//
+// Register Unit Liveness
+//===----------------------------------------------------------------------===//
+//
+// Fixed interference typically comes from ABI boundaries: Function arguments
+// and return values are passed in fixed registers, and so are exception
+// pointers entering landing pads. Certain instructions require values to be
+// present in specific registers. That is also represented through fixed
+// interference.
+//
+
+/// computeRegUnitInterval - Compute the live interval of a register unit, based
+/// on the uses and defs of aliasing registers. The interval should be empty,
+/// or contain only dead phi-defs from ABI blocks.
+void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
+ unsigned Unit = LI->reg;
+
+ assert(LRCalc && "LRCalc not initialized.");
+ LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
+
+ // The physregs aliasing Unit are the roots and their super-registers.
+ // Create all values as dead defs before extending to uses. Note that roots
+ // may share super-registers. That's OK because createDeadDefs() is
+ // idempotent. It is very rare for a register unit to have multiple roots, so
+ // uniquing super-registers is probably not worthwhile.
+ for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
+ unsigned Root = *Roots;
+ if (!MRI->reg_empty(Root))
+ LRCalc->createDeadDefs(LI, Root);
+ for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
+ if (!MRI->reg_empty(*Supers))
+ LRCalc->createDeadDefs(LI, *Supers);
+ }
+ }
+
+ // Now extend LI to reach all uses.
+ // Ignore uses of reserved registers. We only track defs of those.
+ for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
+ unsigned Root = *Roots;
+ if (!isReserved(Root) && !MRI->reg_empty(Root))
+ LRCalc->extendToUses(LI, Root);
+ for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
+ unsigned Reg = *Supers;
+ if (!isReserved(Reg) && !MRI->reg_empty(Reg))
+ LRCalc->extendToUses(LI, Reg);
+ }
+ }
+}
+
+
+/// computeLiveInRegUnits - Precompute the live ranges of any register units
+/// that are live-in to an ABI block somewhere. Register values can appear
+/// without a corresponding def when entering the entry block or a landing pad.
+///
+void LiveIntervals::computeLiveInRegUnits() {
+ RegUnitIntervals.resize(TRI->getNumRegUnits());
+ DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
+
+ // Keep track of the intervals allocated.
+ SmallVector<LiveInterval*, 8> NewIntvs;
+
+ // Check all basic blocks for live-ins.
+ for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
+ MFI != MFE; ++MFI) {
+ const MachineBasicBlock *MBB = MFI;
+
+ // We only care about ABI blocks: Entry + landing pads.
+ if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
+ continue;
+
+ // Create phi-defs at Begin for all live-in registers.
+ SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
+ DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
+ for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
+ 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);
+ }
+ VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
+ (void)VNI;
+ DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
+ }
+ }
+ DEBUG(dbgs() << '\n');
+ }
+ DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
+
+ // Compute the 'normal' part of the intervals.
+ for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
+ computeRegUnitInterval(NewIntvs[i]);
}
+
/// shrinkToUses - After removing some uses of a register, shrink its live
/// range to just the remaining uses. This method does not compute reaching
/// defs for new uses, and it doesn't remove dead defs.
SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
// Visit all instructions reading li->reg.
- for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
+ for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
MachineInstr *UseMI = I.skipInstruction();) {
if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
continue;
SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
- // Note: This intentionally picks up the wrong VNI in case of an EC redef.
- // See below.
- VNInfo *VNI = li->getVNInfoBefore(Idx);
+ LiveRangeQuery LRQ(*li, Idx);
+ VNInfo *VNI = LRQ.valueIn();
if (!VNI) {
// This shouldn't happen: readsVirtualRegister returns true, but there is
// no live value. It is likely caused by a target getting <undef> flags
continue;
}
// Special case: An early-clobber tied operand reads and writes the
- // register one slot early. The getVNInfoBefore call above would have
- // picked up the value defined by UseMI. Adjust the kill slot and value.
- if (SlotIndex::isSameInstr(VNI->def, Idx)) {
- Idx = VNI->def;
- VNI = li->getVNInfoBefore(Idx);
- assert(VNI && "Early-clobber tied value not available");
- }
+ // register one slot early.
+ if (VNInfo *DefVNI = LRQ.valueDefined())
+ Idx = DefVNI->def;
+
WorkList.push_back(std::make_pair(Idx, VNI));
}
// This is a dead def. Make sure the instruction knows.
MachineInstr *MI = getInstructionFromIndex(VNI->def);
assert(MI && "No instruction defining live value");
- MI->addRegisterDead(li->reg, tri_);
+ MI->addRegisterDead(li->reg, TRI);
if (dead && MI->allDefsAreDead()) {
DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
dead->push_back(MI);
//
void LiveIntervals::addKillFlags() {
- for (iterator I = begin(), E = end(); I != E; ++I) {
- unsigned Reg = I->first;
- if (TargetRegisterInfo::isPhysicalRegister(Reg))
+ for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+ unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+ if (MRI->reg_nodbg_empty(Reg))
continue;
- if (mri_->reg_nodbg_empty(Reg))
- continue;
- LiveInterval *LI = I->second;
+ LiveInterval *LI = &getInterval(Reg);
// Every instruction that kills Reg corresponds to a live range end point.
for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
}
}
-#ifndef NDEBUG
-static bool intervalRangesSane(const LiveInterval& li) {
- if (li.empty()) {
- return true;
- }
-
- SlotIndex lastEnd = li.begin()->start;
- for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end();
- lrItr != lrEnd; ++lrItr) {
- const LiveRange& lr = *lrItr;
- if (lastEnd > lr.start || lr.start >= lr.end)
- return false;
- lastEnd = lr.end;
- }
-
- return true;
-}
-#endif
-
-template <typename DefSetT>
-static void handleMoveDefs(LiveIntervals& lis, SlotIndex origIdx,
- SlotIndex miIdx, const DefSetT& defs) {
- for (typename DefSetT::const_iterator defItr = defs.begin(),
- defEnd = defs.end();
- defItr != defEnd; ++defItr) {
- unsigned def = *defItr;
- LiveInterval& li = lis.getInterval(def);
- LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
- assert(lr != 0 && "No range for def?");
- lr->start = miIdx.getRegSlot();
- lr->valno->def = miIdx.getRegSlot();
- assert(intervalRangesSane(li) && "Broke live interval moving def.");
- }
-}
-
-template <typename DeadDefSetT>
-static void handleMoveDeadDefs(LiveIntervals& lis, SlotIndex origIdx,
- SlotIndex miIdx, const DeadDefSetT& deadDefs) {
- for (typename DeadDefSetT::const_iterator deadDefItr = deadDefs.begin(),
- deadDefEnd = deadDefs.end();
- deadDefItr != deadDefEnd; ++deadDefItr) {
- unsigned deadDef = *deadDefItr;
- LiveInterval& li = lis.getInterval(deadDef);
- LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
- assert(lr != 0 && "No range for dead def?");
- assert(lr->start == origIdx.getRegSlot() && "Bad dead range start?");
- assert(lr->end == origIdx.getDeadSlot() && "Bad dead range end?");
- assert(lr->valno->def == origIdx.getRegSlot() && "Bad dead valno def.");
- LiveRange t(*lr);
- t.start = miIdx.getRegSlot();
- t.valno->def = miIdx.getRegSlot();
- t.end = miIdx.getDeadSlot();
- li.removeRange(*lr);
- li.addRange(t);
- assert(intervalRangesSane(li) && "Broke live interval moving dead def.");
- }
-}
-
-template <typename ECSetT>
-static void handleMoveECs(LiveIntervals& lis, SlotIndex origIdx,
- SlotIndex miIdx, const ECSetT& ecs) {
- for (typename ECSetT::const_iterator ecItr = ecs.begin(), ecEnd = ecs.end();
- ecItr != ecEnd; ++ecItr) {
- unsigned ec = *ecItr;
- LiveInterval& li = lis.getInterval(ec);
- LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot(true));
- assert(lr != 0 && "No range for early clobber?");
- assert(lr->start == origIdx.getRegSlot(true) && "Bad EC range start?");
- assert(lr->end == origIdx.getRegSlot() && "Bad EC range end.");
- assert(lr->valno->def == origIdx.getRegSlot(true) && "Bad EC valno def.");
- LiveRange t(*lr);
- t.start = miIdx.getRegSlot(true);
- t.valno->def = miIdx.getRegSlot(true);
- t.end = miIdx.getRegSlot();
- li.removeRange(*lr);
- li.addRange(t);
- assert(intervalRangesSane(li) && "Broke live interval moving EC.");
- }
-}
-
-static void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newIdx,
- LiveIntervals& lis,
- const TargetRegisterInfo& tri) {
- MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx);
- MachineInstr* newKillMI = lis.getInstructionFromIndex(newIdx);
- assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
- assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill.");
- oldKillMI->clearRegisterKills(reg, &tri);
- newKillMI->addRegisterKilled(reg, &tri);
-}
-
-template <typename UseSetT>
-static void handleMoveUses(const MachineBasicBlock *mbb,
- const MachineRegisterInfo& mri,
- const TargetRegisterInfo& tri,
- const BitVector& reservedRegs, LiveIntervals &lis,
- SlotIndex origIdx, SlotIndex miIdx,
- const UseSetT &uses) {
- bool movingUp = miIdx < origIdx;
- for (typename UseSetT::const_iterator usesItr = uses.begin(),
- usesEnd = uses.end();
- usesItr != usesEnd; ++usesItr) {
- unsigned use = *usesItr;
- if (!lis.hasInterval(use))
- continue;
- if (TargetRegisterInfo::isPhysicalRegister(use) && reservedRegs.test(use))
- continue;
- LiveInterval& li = lis.getInterval(use);
- LiveRange* lr = li.getLiveRangeBefore(origIdx.getRegSlot());
- assert(lr != 0 && "No range for use?");
- bool liveThrough = lr->end > origIdx.getRegSlot();
-
- if (movingUp) {
- // If moving up and liveThrough - nothing to do.
- // If not live through we need to extend the range to the last use
- // between the old location and the new one.
- if (!liveThrough) {
- SlotIndex lastUseInRange = miIdx.getRegSlot();
- for (MachineRegisterInfo::use_iterator useI = mri.use_begin(use),
- useE = mri.use_end();
- useI != useE; ++useI) {
- const MachineInstr* mopI = &*useI;
- const MachineOperand& mop = useI.getOperand();
- SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI);
- SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber());
- if (opSlot > lastUseInRange && opSlot < origIdx)
- lastUseInRange = opSlot;
- }
-
- // If we found a new instr endpoint update the kill flags.
- if (lastUseInRange != miIdx.getRegSlot())
- moveKillFlags(use, miIdx, lastUseInRange, lis, tri);
-
- // Fix up the range end.
- lr->end = lastUseInRange;
- }
- } else {
- // Moving down is easy - the existing live range end tells us where
- // the last kill is.
- if (!liveThrough) {
- // Easy fix - just update the range endpoint.
- lr->end = miIdx.getRegSlot();
- } else {
- bool liveOut = lr->end >= lis.getSlotIndexes()->getMBBEndIdx(mbb);
- if (!liveOut && miIdx.getRegSlot() > lr->end) {
- moveKillFlags(use, lr->end, miIdx, lis, tri);
- lr->end = miIdx.getRegSlot();
- }
- }
- }
- assert(intervalRangesSane(li) && "Broke live interval moving use.");
- }
-}
-
-void LiveIntervals::handleMove(MachineInstr *mi) {
- SlotIndex origIdx = indexes_->getInstructionIndex(mi);
- indexes_->removeMachineInstrFromMaps(mi);
- SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi);
-
- MachineBasicBlock* mbb = mi->getParent();
-
- assert(getMBBFromIndex(origIdx) == mbb &&
- "Cannot handle moves across basic block boundaries.");
- assert(!mi->isBundled() && "Can't handle bundled instructions yet.");
-
- // Pick the direction.
- bool movingUp = miIdx < origIdx;
-
- // Collect the operands.
- DenseSet<unsigned> uses, defs, deadDefs, ecs;
- for (MachineInstr::mop_iterator mopItr = mi->operands_begin(),
- mopEnd = mi->operands_end();
- mopItr != mopEnd; ++mopItr) {
- const MachineOperand& mop = *mopItr;
-
- if (!mop.isReg() || mop.getReg() == 0)
- continue;
- unsigned reg = mop.getReg();
-
- if (mop.readsReg() && !ecs.count(reg)) {
- uses.insert(reg);
- }
- if (mop.isDef()) {
- if (mop.isDead()) {
- assert(!defs.count(reg) && "Can't mix defs with dead-defs.");
- deadDefs.insert(reg);
- } else if (mop.isEarlyClobber()) {
- uses.erase(reg);
- ecs.insert(reg);
- } else {
- assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs.");
- defs.insert(reg);
- }
- }
- }
-
- if (movingUp) {
- handleMoveUses(mbb, *mri_, *tri_, reservedRegs_, *this, origIdx, miIdx, uses);
- handleMoveECs(*this, origIdx, miIdx, ecs);
- handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
- handleMoveDefs(*this, origIdx, miIdx, defs);
- } else {
- handleMoveDefs(*this, origIdx, miIdx, defs);
- handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
- handleMoveECs(*this, origIdx, miIdx, ecs);
- handleMoveUses(mbb, *mri_, *tri_, reservedRegs_, *this, origIdx, miIdx, uses);
- }
-}
-
-/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
-/// allow one) virtual register operand, then its uses are implicitly using
-/// the register. Returns the virtual register.
-unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
- MachineInstr *MI) const {
- unsigned RegOp = 0;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse())
- continue;
- unsigned Reg = MO.getReg();
- if (Reg == 0 || Reg == li.reg)
- continue;
-
- if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isAllocatable(Reg))
- continue;
- RegOp = MO.getReg();
- break; // Found vreg operand - leave the loop.
- }
- return RegOp;
-}
-
-/// isValNoAvailableAt - Return true if the val# of the specified interval
-/// which reaches the given instruction also reaches the specified use index.
-bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
- SlotIndex UseIdx) const {
- VNInfo *UValNo = li.getVNInfoAt(UseIdx);
- return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
-}
-
-/// isReMaterializable - Returns true if the definition MI of the specified
-/// val# of the specified interval is re-materializable.
-bool
-LiveIntervals::isReMaterializable(const LiveInterval &li,
- const VNInfo *ValNo, MachineInstr *MI,
- const SmallVectorImpl<LiveInterval*> *SpillIs,
- bool &isLoad) {
- if (DisableReMat)
- return false;
-
- if (!tii_->isTriviallyReMaterializable(MI, aa_))
- return false;
-
- // Target-specific code can mark an instruction as being rematerializable
- // if it has one virtual reg use, though it had better be something like
- // a PIC base register which is likely to be live everywhere.
- unsigned ImpUse = getReMatImplicitUse(li, MI);
- if (ImpUse) {
- const LiveInterval &ImpLi = getInterval(ImpUse);
- for (MachineRegisterInfo::use_nodbg_iterator
- ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
- ri != re; ++ri) {
- MachineInstr *UseMI = &*ri;
- SlotIndex UseIdx = getInstructionIndex(UseMI);
- if (li.getVNInfoAt(UseIdx) != ValNo)
- continue;
- if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
- return false;
- }
-
- // If a register operand of the re-materialized instruction is going to
- // be spilled next, then it's not legal to re-materialize this instruction.
- if (SpillIs)
- for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
- if (ImpUse == (*SpillIs)[i]->reg)
- return false;
- }
- return true;
-}
-
-/// isReMaterializable - Returns true if every definition of MI of every
-/// val# of the specified interval is re-materializable.
-bool
-LiveIntervals::isReMaterializable(const LiveInterval &li,
- const SmallVectorImpl<LiveInterval*> *SpillIs,
- bool &isLoad) {
- isLoad = false;
- for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
- i != e; ++i) {
- const VNInfo *VNI = *i;
- if (VNI->isUnused())
- continue; // Dead val#.
- // Is the def for the val# rematerializable?
- MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
- if (!ReMatDefMI)
- return false;
- bool DefIsLoad = false;
- if (!ReMatDefMI ||
- !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
- return false;
- isLoad |= DefIsLoad;
- }
- return true;
-}
-
MachineBasicBlock*
LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
// A local live range must be fully contained inside the block, meaning it is
// getMBBFromIndex doesn't need to search the MBB table when both indexes
// belong to proper instructions.
- MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start);
- MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop);
+ MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
+ MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
return MBB1 == MBB2 ? MBB1 : NULL;
}
if (!Found) {
// This is the first overlap. Initialize UsableRegs to all ones.
UsableRegs.clear();
- UsableRegs.resize(tri_->getNumRegs(), true);
+ UsableRegs.resize(TRI->getNumRegs(), true);
Found = true;
}
// Remove usable registers clobbered by this mask.
return Found;
}
}
+
+//===----------------------------------------------------------------------===//
+// IntervalUpdate class.
+//===----------------------------------------------------------------------===//
+
+// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
+class LiveIntervals::HMEditor {
+private:
+ LiveIntervals& LIS;
+ const MachineRegisterInfo& MRI;
+ const TargetRegisterInfo& TRI;
+ SlotIndex NewIdx;
+
+ typedef std::pair<LiveInterval*, LiveRange*> IntRangePair;
+ typedef DenseSet<IntRangePair> RangeSet;
+
+ struct RegRanges {
+ LiveRange* Use;
+ LiveRange* EC;
+ LiveRange* Dead;
+ LiveRange* Def;
+ RegRanges() : Use(0), EC(0), Dead(0), Def(0) {}
+ };
+ typedef DenseMap<unsigned, RegRanges> BundleRanges;
+
+public:
+ HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
+ const TargetRegisterInfo& TRI, SlotIndex NewIdx)
+ : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {}
+
+ // Update intervals for all operands of MI from OldIdx to NewIdx.
+ // This assumes that MI used to be at OldIdx, and now resides at
+ // NewIdx.
+ void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) {
+ assert(NewIdx != OldIdx && "No-op move? That's a bit strange.");
+
+ // Collect the operands.
+ RangeSet Entering, Internal, Exiting;
+ bool hasRegMaskOp = false;
+ collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
+
+ // To keep the LiveRanges valid within an interval, move the ranges closest
+ // to the destination first. This prevents ranges from overlapping, to that
+ // APIs like removeRange still work.
+ if (NewIdx < OldIdx) {
+ moveAllEnteringFrom(OldIdx, Entering);
+ moveAllInternalFrom(OldIdx, Internal);
+ moveAllExitingFrom(OldIdx, Exiting);
+ }
+ else {
+ moveAllExitingFrom(OldIdx, Exiting);
+ moveAllInternalFrom(OldIdx, Internal);
+ moveAllEnteringFrom(OldIdx, Entering);
+ }
+
+ if (hasRegMaskOp)
+ updateRegMaskSlots(OldIdx);
+
+#ifndef NDEBUG
+ LIValidator validator;
+ validator = std::for_each(Entering.begin(), Entering.end(), validator);
+ validator = std::for_each(Internal.begin(), Internal.end(), validator);
+ validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
+ assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness.");
+#endif
+
+ }
+
+ // Update intervals for all operands of MI to refer to BundleStart's
+ // SlotIndex.
+ void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) {
+ if (MI == BundleStart)
+ return; // Bundling instr with itself - nothing to do.
+
+ SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI);
+ assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI &&
+ "SlotIndex <-> Instruction mapping broken for MI");
+
+ // Collect all ranges already in the bundle.
+ MachineBasicBlock::instr_iterator BII(BundleStart);
+ RangeSet Entering, Internal, Exiting;
+ bool hasRegMaskOp = false;
+ collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
+ assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
+ for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) {
+ if (&*BII == MI)
+ continue;
+ collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
+ assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
+ }
+
+ BundleRanges BR = createBundleRanges(Entering, Internal, Exiting);
+
+ Entering.clear();
+ Internal.clear();
+ Exiting.clear();
+ collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
+ assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
+
+ DEBUG(dbgs() << "Entering: " << Entering.size() << "\n");
+ DEBUG(dbgs() << "Internal: " << Internal.size() << "\n");
+ DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n");
+
+ moveAllEnteringFromInto(OldIdx, Entering, BR);
+ moveAllInternalFromInto(OldIdx, Internal, BR);
+ moveAllExitingFromInto(OldIdx, Exiting, BR);
+
+
+#ifndef NDEBUG
+ LIValidator validator;
+ validator = std::for_each(Entering.begin(), Entering.end(), validator);
+ validator = std::for_each(Internal.begin(), Internal.end(), validator);
+ validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
+ assert(validator.rangesOk() && "moveAllOperandsInto broke liveness.");
+#endif
+ }
+
+private:
+
+#ifndef NDEBUG
+ class LIValidator {
+ private:
+ DenseSet<const LiveInterval*> Checked, Bogus;
+ public:
+ void operator()(const IntRangePair& P) {
+ const LiveInterval* LI = P.first;
+ if (Checked.count(LI))
+ return;
+ Checked.insert(LI);
+ if (LI->empty())
+ return;
+ SlotIndex LastEnd = LI->begin()->start;
+ for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end();
+ LRI != LRE; ++LRI) {
+ const LiveRange& LR = *LRI;
+ if (LastEnd > LR.start || LR.start >= LR.end)
+ Bogus.insert(LI);
+ LastEnd = LR.end;
+ }
+ }
+
+ bool rangesOk() const {
+ return Bogus.empty();
+ }
+ };
+#endif
+
+ // Collect IntRangePairs for all operands of MI that may need fixing.
+ // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes'
+ // maps).
+ void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal,
+ RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) {
+ hasRegMaskOp = false;
+ for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
+ MOE = MI->operands_end();
+ MOI != MOE; ++MOI) {
+ const MachineOperand& MO = *MOI;
+
+ if (MO.isRegMask()) {
+ hasRegMaskOp = true;
+ continue;
+ }
+
+ if (!MO.isReg() || MO.getReg() == 0)
+ continue;
+
+ unsigned Reg = MO.getReg();
+
+ // TODO: Currently we're skipping uses that are reserved or have no
+ // interval, but we're not updating their kills. This should be
+ // fixed.
+ if (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))
+ continue;
+
+ // Collect ranges for register units. These live ranges are computed on
+ // demand, so just skip any that haven't been computed yet.
+ if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+ for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
+ if (LiveInterval *LI = LIS.getCachedRegUnit(*Units))
+ collectRanges(MO, LI, Entering, Internal, Exiting, OldIdx);
+ } else {
+ // Collect ranges for individual virtual registers.
+ collectRanges(MO, &LIS.getInterval(Reg),
+ Entering, Internal, Exiting, OldIdx);
+ }
+ }
+ }
+
+ void collectRanges(const MachineOperand &MO, LiveInterval *LI,
+ RangeSet &Entering, RangeSet &Internal, RangeSet &Exiting,
+ SlotIndex OldIdx) {
+ if (MO.readsReg()) {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx);
+ if (LR != 0)
+ Entering.insert(std::make_pair(LI, LR));
+ }
+ if (MO.isDef()) {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot());
+ assert(LR != 0 && "No live range for def?");
+ if (LR->end > OldIdx.getDeadSlot())
+ Exiting.insert(std::make_pair(LI, LR));
+ else
+ Internal.insert(std::make_pair(LI, LR));
+ }
+ }
+
+ BundleRanges createBundleRanges(RangeSet& Entering,
+ RangeSet& Internal,
+ RangeSet& Exiting) {
+ BundleRanges BR;
+
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI) {
+ LiveInterval* LI = EI->first;
+ LiveRange* LR = EI->second;
+ BR[LI->reg].Use = LR;
+ }
+
+ for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
+ II != IE; ++II) {
+ LiveInterval* LI = II->first;
+ LiveRange* LR = II->second;
+ if (LR->end.isDead()) {
+ BR[LI->reg].Dead = LR;
+ } else {
+ BR[LI->reg].EC = LR;
+ }
+ }
+
+ for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
+ EI != EE; ++EI) {
+ LiveInterval* LI = EI->first;
+ LiveRange* LR = EI->second;
+ BR[LI->reg].Def = LR;
+ }
+
+ return BR;
+ }
+
+ void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) {
+ MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx);
+ if (!OldKillMI->killsRegister(reg))
+ return; // Bail out if we don't have kill flags on the old register.
+ MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx);
+ assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
+ assert(!NewKillMI->killsRegister(reg) &&
+ "New kill instr is already a kill.");
+ OldKillMI->clearRegisterKills(reg, &TRI);
+ NewKillMI->addRegisterKilled(reg, &TRI);
+ }
+
+ void updateRegMaskSlots(SlotIndex OldIdx) {
+ SmallVectorImpl<SlotIndex>::iterator RI =
+ std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
+ OldIdx);
+ assert(*RI == OldIdx && "No RegMask at OldIdx.");
+ *RI = NewIdx;
+ assert(*prior(RI) < *RI && *RI < *next(RI) &&
+ "RegSlots out of order. Did you move one call across another?");
+ }
+
+ // Return the last use of reg between NewIdx and OldIdx.
+ SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {
+ SlotIndex LastUse = NewIdx;
+ for (MachineRegisterInfo::use_nodbg_iterator
+ UI = MRI.use_nodbg_begin(Reg),
+ UE = MRI.use_nodbg_end();
+ UI != UE; UI.skipInstruction()) {
+ const MachineInstr* MI = &*UI;
+ SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
+ if (InstSlot > LastUse && InstSlot < OldIdx)
+ LastUse = InstSlot;
+ }
+ return LastUse;
+ }
+
+ void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ bool LiveThrough = LR->end > OldIdx.getRegSlot();
+ if (LiveThrough)
+ return;
+ SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
+ if (LastUse != NewIdx)
+ moveKillFlags(LI->reg, NewIdx, LastUse);
+ LR->end = LastUse.getRegSlot();
+ }
+
+ void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ // Extend the LiveRange if NewIdx is past the end.
+ if (NewIdx > LR->end) {
+ // Move kill flags if OldIdx was not originally the end
+ // (otherwise LR->end points to an invalid slot).
+ if (LR->end.getRegSlot() != OldIdx.getRegSlot()) {
+ assert(LR->end > OldIdx && "LiveRange does not cover original slot");
+ moveKillFlags(LI->reg, LR->end, NewIdx);
+ }
+ LR->end = NewIdx.getRegSlot();
+ }
+ }
+
+ void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) {
+ bool GoingUp = NewIdx < OldIdx;
+
+ if (GoingUp) {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringUpFrom(OldIdx, *EI);
+ } else {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringDownFrom(OldIdx, *EI);
+ }
+ }
+
+ void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+ LR->end <= OldIdx.getDeadSlot() &&
+ "Range should be internal to OldIdx.");
+ LiveRange Tmp(*LR);
+ Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+ Tmp.valno->def = Tmp.start;
+ Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot();
+ LI->removeRange(*LR);
+ LI->addRange(Tmp);
+ }
+
+ void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) {
+ for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
+ II != IE; ++II)
+ moveInternalFrom(OldIdx, *II);
+ }
+
+ void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveRange* LR = P.second;
+ assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+ "Range should start in OldIdx.");
+ assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx.");
+ SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+ LR->start = NewStart;
+ LR->valno->def = NewStart;
+ }
+
+ void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) {
+ for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
+ EI != EE; ++EI)
+ moveExitingFrom(OldIdx, *EI);
+ }
+
+ void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P,
+ BundleRanges& BR) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ bool LiveThrough = LR->end > OldIdx.getRegSlot();
+ if (LiveThrough) {
+ assert((LR->start < NewIdx || BR[LI->reg].Def == LR) &&
+ "Def in bundle should be def range.");
+ assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
+ "If bundle has use for this reg it should be LR.");
+ BR[LI->reg].Use = LR;
+ return;
+ }
+
+ SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
+ moveKillFlags(LI->reg, OldIdx, LastUse);
+
+ if (LR->start < NewIdx) {
+ // Becoming a new entering range.
+ assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 &&
+ "Bundle shouldn't be re-defining reg mid-range.");
+ assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
+ "Bundle shouldn't have different use range for same reg.");
+ LR->end = LastUse.getRegSlot();
+ BR[LI->reg].Use = LR;
+ } else {
+ // Becoming a new Dead-def.
+ assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) &&
+ "Live range starting at unexpected slot.");
+ assert(BR[LI->reg].Def == LR && "Reg should have def range.");
+ assert(BR[LI->reg].Dead == 0 &&
+ "Can't have def and dead def of same reg in a bundle.");
+ LR->end = LastUse.getDeadSlot();
+ BR[LI->reg].Dead = BR[LI->reg].Def;
+ BR[LI->reg].Def = 0;
+ }
+ }
+
+ void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P,
+ BundleRanges& BR) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ if (NewIdx > LR->end) {
+ // Range extended to bundle. Add to bundle uses.
+ // Note: Currently adds kill flags to bundle start.
+ assert(BR[LI->reg].Use == 0 &&
+ "Bundle already has use range for reg.");
+ moveKillFlags(LI->reg, LR->end, NewIdx);
+ LR->end = NewIdx.getRegSlot();
+ BR[LI->reg].Use = LR;
+ } else {
+ assert(BR[LI->reg].Use != 0 &&
+ "Bundle should already have a use range for reg.");
+ }
+ }
+
+ void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering,
+ BundleRanges& BR) {
+ bool GoingUp = NewIdx < OldIdx;
+
+ if (GoingUp) {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringUpFromInto(OldIdx, *EI, BR);
+ } else {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringDownFromInto(OldIdx, *EI, BR);
+ }
+ }
+
+ void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P,
+ BundleRanges& BR) {
+ // TODO: Sane rules for moving ranges into bundles.
+ }
+
+ void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal,
+ BundleRanges& BR) {
+ for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
+ II != IE; ++II)
+ moveInternalFromInto(OldIdx, *II, BR);
+ }
+
+ void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P,
+ BundleRanges& BR) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+
+ assert(LR->start.isRegister() &&
+ "Don't know how to merge exiting ECs into bundles yet.");
+
+ if (LR->end > NewIdx.getDeadSlot()) {
+ // This range is becoming an exiting range on the bundle.
+ // If there was an old dead-def of this reg, delete it.
+ if (BR[LI->reg].Dead != 0) {
+ LI->removeRange(*BR[LI->reg].Dead);
+ BR[LI->reg].Dead = 0;
+ }
+ assert(BR[LI->reg].Def == 0 &&
+ "Can't have two defs for the same variable exiting a bundle.");
+ LR->start = NewIdx.getRegSlot();
+ LR->valno->def = LR->start;
+ BR[LI->reg].Def = LR;
+ } else {
+ // This range is becoming internal to the bundle.
+ assert(LR->end == NewIdx.getRegSlot() &&
+ "Can't bundle def whose kill is before the bundle");
+ if (BR[LI->reg].Dead || BR[LI->reg].Def) {
+ // Already have a def for this. Just delete range.
+ LI->removeRange(*LR);
+ } else {
+ // Make range dead, record.
+ LR->end = NewIdx.getDeadSlot();
+ BR[LI->reg].Dead = LR;
+ assert(BR[LI->reg].Use == LR &&
+ "Range becoming dead should currently be use.");
+ }
+ // In both cases the range is no longer a use on the bundle.
+ BR[LI->reg].Use = 0;
+ }
+ }
+
+ void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting,
+ BundleRanges& BR) {
+ for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
+ EI != EE; ++EI)
+ moveExitingFromInto(OldIdx, *EI, BR);
+ }
+
+};
+
+void LiveIntervals::handleMove(MachineInstr* MI) {
+ SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
+ Indexes->removeMachineInstrFromMaps(MI);
+ SlotIndex NewIndex = MI->isInsideBundle() ?
+ Indexes->getInstructionIndex(MI) :
+ Indexes->insertMachineInstrInMaps(MI);
+ assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
+ OldIndex < getMBBEndIdx(MI->getParent()) &&
+ "Cannot handle moves across basic block boundaries.");
+ assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
+
+ HMEditor HME(*this, *MRI, *TRI, NewIndex);
+ HME.moveAllRangesFrom(MI, OldIndex);
+}
+
+void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
+ MachineInstr* BundleStart) {
+ SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
+ HMEditor HME(*this, *MRI, *TRI, NewIndex);
+ HME.moveAllRangesInto(MI, BundleStart);
+}
projects / oota-llvm.git / blobdiff