#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 "VirtRegMap.h"
#include <algorithm>
#include <limits>
#include <cmath>
using namespace llvm;
-// Temporary option to enable regunit liveness.
-static cl::opt<bool> LiveRegUnits("live-regunits", cl::Hidden, cl::init(true));
-
-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;
+char &llvm::LiveIntervalsID = LiveIntervals::ID;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
"Live Interval Analysis", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
AU.addRequired<LiveVariables>();
AU.addPreserved<LiveVariables>();
AU.addPreservedID(MachineLoopInfoID);
- if (LiveRegUnits)
- AU.addRequiredTransitiveID(MachineDominatorsID);
+ AU.addRequiredTransitiveID(MachineDominatorsID);
AU.addPreservedID(MachineDominatorsID);
AU.addPreserved<SlotIndexes>();
AU.addRequiredTransitive<SlotIndexes>();
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();
AA = &getAnalysis<AliasAnalysis>();
LV = &getAnalysis<LiveVariables>();
Indexes = &getAnalysis<SlotIndexes>();
- if (LiveRegUnits)
- DomTree = &getAnalysis<MachineDominatorTree>();
- if (LiveRegUnits && !LRCalc)
+ DomTree = &getAnalysis<MachineDominatorTree>();
+ if (!LRCalc)
LRCalc = new LiveRangeCalc();
AllocatableRegs = TRI->getAllocatableSet(fn);
ReservedRegs = TRI->getReservedRegs(fn);
- computeIntervals();
+ // Allocate space for all virtual registers.
+ VirtRegIntervals.resize(MRI->getNumVirtRegs());
- numIntervals += getNumIntervals();
-
- if (LiveRegUnits) {
- computeLiveInRegUnits();
+ if (NewLiveIntervals) {
+ // This is the new way of computing live intervals.
+ // It is independent of LiveVariables, and it can run at any time.
+ computeVirtRegs();
+ computeRegMasks();
+ } 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))
- OS << PrintReg(Reg, TRI) << '\t' << *LI << '\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)))
- OS << PrintReg(LI->reg) << '\t' << *LI << '\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);
}
MF->print(OS, Indexes);
}
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void LiveIntervals::dumpInstrs() const {
printInstrs(dbgs());
}
+#endif
static
bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
// new valno in the killing blocks.
assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
DEBUG(dbgs() << " phi-join");
- ValNo->setHasPHIKill(true);
} else {
// Iterate over all of the blocks that the variable is completely
// live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
assert(getInstructionFromIndex(Start) == 0 &&
"PHI def index points at actual instruction.");
ValNo = interval.getNextValue(Start, VNInfoAllocator);
- ValNo->setIsPHIDef(true);
}
LiveRange LR(Start, killIdx, ValNo);
interval.addRange(LR);
SlotIndex killIndex = getMBBEndIdx(mbb);
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
- ValNo->setHasPHIKill(true);
DEBUG(dbgs() << " phi-join +" << LR);
} else {
llvm_unreachable("Multiply defined register");
DEBUG(dbgs() << '\n');
}
-static bool isRegLiveIntoSuccessor(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;
-}
-
-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)) {
- end = start.getDeadSlot();
- } else {
- // Unreserved, unallocable registers like EFLAGS can be live across basic
- // block boundaries.
- assert(isRegLiveIntoSuccessor(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) ||
- !isRegLiveIntoSuccessor(MBB, interval.reg)) {
- // Allocatable registers are never live through.
- // Non-allocatable registers that aren't live into any successors also
- // aren't live through.
- DEBUG(dbgs() << " dead");
- return;
- } else {
- // If we get here the register is non-allocatable and live into some
- // successor. We'll conservatively assume it's 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
/// which a variable is live
void LiveIntervals::computeIntervals() {
DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
- << "********** Function: "
- << ((Value*)MF->getFunction())->getName() << '\n');
+ << "********** Function: " << MF->getName() << '\n');
RegMaskBlocks.resize(MF->getNumBlockIDs());
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);
continue;
}
- if (!MO.isReg() || !MO.getReg())
+ if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
continue;
// handle register defs - build intervals
// Compute the number of register mask instructions in this block.
std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
- RMB.second = RegMaskSlots.size() - RMB.first;;
+ RMB.second = RegMaskSlots.size() - RMB.first;
}
// Create empty intervals for registers defined by implicit_def's (except
}
+/// 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);
+}
+
+void LiveIntervals::computeVirtRegs() {
+ 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);
+ }
+}
+
+void LiveIntervals::computeRegMasks() {
+ RegMaskBlocks.resize(MF->getNumBlockIDs());
+
+ // Find all instructions with regmask operands.
+ for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
+ MBBI != E; ++MBBI) {
+ MachineBasicBlock *MBB = MBBI;
+ std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
+ RMB.first = RegMaskSlots.size();
+ for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
+ MI != ME; ++MI)
+ for (MIOperands MO(MI); MO.isValid(); ++MO) {
+ if (!MO->isRegMask())
+ continue;
+ RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
+ RegMaskBits.push_back(MO->getRegMask());
+ }
+ // Compute the number of register mask instructions in this block.
+ RMB.second = RegMaskSlots.size() - RMB.first;
+ }
+}
+
//===----------------------------------------------------------------------===//
// Register Unit Liveness
//===----------------------------------------------------------------------===//
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
- VNI->setIsUnused(true);
+ VNI->markUnused();
NewLI.removeRange(*LII);
DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
CanSeparate = true;
// Register allocator hooks.
//
-void LiveIntervals::addKillFlags() {
+void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
+ // Keep track of regunit ranges.
+ SmallVector<std::pair<LiveInterval*, LiveInterval::iterator>, 8> RU;
+
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (MRI->reg_nodbg_empty(Reg))
continue;
LiveInterval *LI = &getInterval(Reg);
+ if (LI->empty())
+ continue;
+
+ // Find the regunit intervals for the assigned register. They may overlap
+ // the virtual register live range, cancelling any kills.
+ RU.clear();
+ for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
+ ++Units) {
+ LiveInterval *RUInt = &getRegUnit(*Units);
+ if (RUInt->empty())
+ continue;
+ RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end)));
+ }
// Every instruction that kills Reg corresponds to a live range end point.
for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
MachineInstr *MI = getInstructionFromIndex(RI->end);
if (!MI)
continue;
- MI->addRegisterKilled(Reg, NULL);
+
+ // Check if any of the reguints are live beyond the end of RI. That could
+ // happen when a physreg is defined as a copy of a virtreg:
+ //
+ // %EAX = COPY %vreg5
+ // FOO %vreg5 <--- MI, cancel kill because %EAX is live.
+ // BAR %EAX<kill>
+ //
+ // 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())
+ continue;
+ I = RInt->advanceTo(I, RI->end);
+ if (I == RInt->end() || I->start >= RI->end)
+ continue;
+ // I is overlapping RI.
+ CancelKill = true;
+ break;
+ }
+ if (CancelKill)
+ MI->clearRegisterKills(Reg, NULL);
+ else
+ MI->addRegisterKilled(Reg, NULL);
}
}
}
return MBB1 == MBB2 ? MBB1 : NULL;
}
+bool
+LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
+ for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
+ I != E; ++I) {
+ const VNInfo *PHI = *I;
+ if (PHI->isUnused() || !PHI->isPHIDef())
+ continue;
+ const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
+ // Conservatively return true instead of scanning huge predecessor lists.
+ if (PHIMBB->pred_size() > 100)
+ return true;
+ for (MachineBasicBlock::const_pred_iterator
+ PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
+ if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
+ return true;
+ }
+ return false;
+}
+
float
LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
// Limit the loop depth ridiculousness.
VNInfo* VN = Interval.getNextValue(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getVNInfoAllocator());
- VN->setHasPHIKill(true);
LiveRange LR(
SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getMBBEndIdx(startInst->getParent()), VN);
// 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) && LIS.trackingRegUnits())
+ 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);
-
- // Collect ranges for individual registers.
- if (LIS.hasInterval(Reg))
+ } else {
+ // Collect ranges for individual virtual registers.
collectRanges(MO, &LIS.getInterval(Reg),
Entering, Internal, Exiting, OldIdx);
+ }
}
}
// 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;
+
+ if (TargetRegisterInfo::isVirtualRegister(Reg)) {
+ 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;
+ }
+ } else {
+ MachineInstr* MI = LIS.getSlotIndexes()->getInstructionFromIndex(NewIdx);
+ MachineBasicBlock::iterator MII(MI);
+ ++MII;
+ MachineBasicBlock* MBB = MI->getParent();
+ for (; MII != MBB->end() && LIS.getInstructionIndex(MII) < OldIdx; ++MII){
+ for (MachineInstr::mop_iterator MOI = MII->operands_begin(),
+ MOE = MII->operands_end();
+ MOI != MOE; ++MOI) {
+ const MachineOperand& mop = *MOI;
+ if (!mop.isReg() || mop.getReg() == 0 ||
+ TargetRegisterInfo::isVirtualRegister(mop.getReg()))
+ continue;
+
+ if (TRI.hasRegUnit(mop.getReg(), Reg))
+ LastUse = LIS.getInstructionIndex(MII);
+ }
+ }
}
return LastUse;
}
SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
if (LastUse != NewIdx)
moveKillFlags(LI->reg, NewIdx, LastUse);
- LR->end = LastUse.getRegSlot();
+ LR->end = LastUse.getRegSlot(LR->end.isEarlyClobber());
}
void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
assert(LR->end > OldIdx && "LiveRange does not cover original slot");
moveKillFlags(LI->reg, LR->end, NewIdx);
}
- LR->end = NewIdx.getRegSlot();
+ LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
}
}