X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=1ca2d46cc295db6a0f3e251999a58890b233267c;hb=08368387a450dc2b5681000e2728ec702a8f1197;hp=5b899e082b311c330abdc45467b5b0a7acd74d56;hpb=8dd26253f54247e77e5accfdd70e7b4bf27b39c2;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 5b899e082b3..1ca2d46cc29 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -17,39 +17,35 @@ #define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/Value.h" +#include "LiveRangeCalc.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/IR/Value.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" #include -#include #include +#include using namespace llvm; -// Hidden options for help debugging. -static cl::opt DisableReMat("disable-rematerialization", - cl::init(false), cl::Hidden); - -STATISTIC(numIntervals , "Number of original intervals"); - char LiveIntervals::ID = 0; +char &llvm::LiveIntervalsID = LiveIntervals::ID; INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis", false, false) INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_PASS_DEPENDENCY(LiveVariables) -INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_DEPENDENCY(SlotIndexes) INITIALIZE_PASS_END(LiveIntervals, "liveintervals", @@ -59,27 +55,41 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); + // LiveVariables isn't really required by this analysis, it is only required + // here to make sure it is live during TwoAddressInstructionPass and + // PHIElimination. This is temporary. AU.addRequired(); AU.addPreserved(); - AU.addRequired(); - AU.addPreserved(); + AU.addPreservedID(MachineLoopInfoID); + AU.addRequiredTransitiveID(MachineDominatorsID); AU.addPreservedID(MachineDominatorsID); AU.addPreserved(); AU.addRequiredTransitive(); 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::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(); } @@ -87,19 +97,23 @@ void LiveIntervals::releaseMemory() { /// 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(); - lv_ = &getAnalysis(); - indexes_ = &getAnalysis(); - allocatableRegs_ = tri_->getAllocatableSet(fn); - - computeIntervals(); - - numIntervals += getNumIntervals(); + MF = &fn; + MRI = &MF->getRegInfo(); + TM = &fn.getTarget(); + TRI = TM->getRegisterInfo(); + TII = TM->getInstrInfo(); + AA = &getAnalysis(); + Indexes = &getAnalysis(); + DomTree = &getAnalysis(); + if (!LRCalc) + LRCalc = new LiveRangeCalc(); + + // Allocate space for all virtual registers. + VirtRegIntervals.resize(MRI->getNumVirtRegs()); + + computeVirtRegs(); + computeRegMasks(); + computeLiveInRegUnits(); DEBUG(dump()); return true; @@ -108,500 +122,179 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { /// print - Implement the dump method. void LiveIntervals::print(raw_ostream &OS, const Module* ) const { OS << "********** INTERVALS **********\n"; - for (const_iterator I = begin(), E = end(); I != E; ++I) { - I->second->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 i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (hasInterval(Reg)) + OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n'; } + OS << "RegMasks:"; + for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) + OS << ' ' << RegMaskSlots[i]; + OS << '\n'; + printInstrs(OS); } void LiveIntervals::printInstrs(raw_ostream &OS) const { OS << "********** MACHINEINSTRS **********\n"; - mf_->print(OS, indexes_); + 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) { - unsigned Reg = MI.getOperand(MOIdx).getReg(); - for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { - const MachineOperand &MO = MI.getOperand(i); - if (!MO.isReg()) - continue; - if (MO.getReg() == Reg && MO.isDef()) { - assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && - MI.getOperand(MOIdx).getSubReg() && - (MO.getSubReg() || MO.isImplicit())); - return true; - } - } - return false; +LiveInterval* LiveIntervals::createInterval(unsigned reg) { + float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; + return new LiveInterval(reg, Weight); } -/// isPartialRedef - Return true if the specified def at the specific index is -/// partially re-defining the specified live interval. A common case of this is -/// a definition of the sub-register. -bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, - LiveInterval &interval) { - if (!MO.getSubReg() || MO.isEarlyClobber()) - return false; - SlotIndex RedefIndex = MIIdx.getRegSlot(); - const LiveRange *OldLR = - interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); - MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); - if (DefMI != 0) { - return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; - } - return false; +/// 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::handleVirtualRegisterDef(MachineBasicBlock *mbb, - MachineBasicBlock::iterator mi, - SlotIndex MIIdx, - MachineOperand& MO, - unsigned MOIdx, - LiveInterval &interval) { - 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); - 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 - // of the full register. - // FIXME: LiveIntervals shouldn't modify the code like this. Whoever - // created the machine instruction should annotate it with 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 . - 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(); - } - } - - VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); - assert(ValNo->id == 0 && "First value in interval is not 0?"); - - // Loop over all of the blocks that the vreg is defined in. There are - // two cases we have to handle here. The most common case is a vreg - // whose lifetime is contained within a basic block. In this case there - // will be a single kill, in MBB, which comes after the definition. - if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { - // FIXME: what about dead vars? - SlotIndex killIdx; - if (vi.Kills[0] != mi) - killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); - else - killIdx = defIndex.getDeadSlot(); - - // If the kill happens after the definition, we have an intra-block - // live range. - if (killIdx > defIndex) { - assert(vi.AliveBlocks.empty() && - "Shouldn't be alive across any blocks!"); - LiveRange LR(defIndex, killIdx, ValNo); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR << "\n"); - return; - } - } - - // The other case we handle is when a virtual register lives to the end - // of the defining block, potentially live across some blocks, then is - // live into some number of blocks, but gets killed. Start by adding a - // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); - DEBUG(dbgs() << " +" << NewLR); - interval.addRange(NewLR); - - 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. - 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 - // 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); - interval.addRange(LR); - DEBUG(dbgs() << " +" << LR); - } - } - - // Finally, this virtual register is live from the start of any killing - // block to the 'use' slot of the killing instruction. - for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { - MachineInstr *Kill = vi.Kills[i]; - SlotIndex Start = getMBBStartIdx(Kill->getParent()); - SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); - - // Create interval with one of a NEW value number. Note that this value - // number isn't actually defined by an instruction, weird huh? :) - if (PHIJoin) { - 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); - DEBUG(dbgs() << " +" << LR); - } - - } else { - if (MultipleDefsBySameMI(*mi, MOIdx)) - // Multiple defs of the same virtual register by the same instruction. - // e.g. %reg1031:5, %reg1031:6 = VLD1q16 %reg1024, ... - // This is likely due to elimination of REG_SEQUENCE instructions. Return - // here since there is nothing to do. - return; - - // If this is the second time we see a virtual register definition, it - // must be due to phi elimination or two addr elimination. If this is - // the result of two address elimination, then the vreg is one of the - // def-and-use register operand. - - // It may also be partial redef like this: - // 80 %reg1041:6 = VSHRNv4i16 %reg1034, 12, pred:14, pred:%reg0 - // 120 %reg1041:5 = VSHRNv4i16 %reg1039, 12, pred:14, pred:%reg0 - bool PartReDef = isPartialRedef(MIIdx, MO, interval); - if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { - // If this is a two-address definition, then we have already processed - // the live range. The only problem is that we didn't realize there - // are actually two values in the live interval. Because of this we - // need to take the LiveRegion that defines this register and split it - // into two values. - SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); - - const LiveRange *OldLR = - interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); - VNInfo *OldValNo = OldLR->valno; - SlotIndex DefIndex = OldValNo->def.getRegSlot(); - - // Delete the previous value, which should be short and continuous, - // because the 2-addr copy must be in the same MBB as the redef. - interval.removeRange(DefIndex, RedefIndex); - - // The new value number (#1) is defined by the instruction we claimed - // defined value #0. - VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); - - // Value#0 is now defined by the 2-addr instruction. - OldValNo->def = RedefIndex; - - // Add the new live interval which replaces the range for the input copy. - LiveRange LR(DefIndex, RedefIndex, ValNo); - DEBUG(dbgs() << " replace range with " << LR); - interval.addRange(LR); - - // If this redefinition is dead, we need to add a dummy unit live - // range covering the def slot. - if (MO.isDead()) - interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), - OldValNo)); - - DEBUG({ - dbgs() << " RESULT: "; - interval.print(dbgs(), tri_); - }); - } 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. - - SlotIndex defIndex = MIIdx.getRegSlot(); - if (MO.isEarlyClobber()) - defIndex = MIIdx.getRegSlot(true); - - VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); - - 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"); - } +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); } - - DEBUG(dbgs() << '\n'); } -void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator mi, - SlotIndex MIIdx, - MachineOperand& MO, - LiveInterval &interval) { - // A physical register cannot be live across basic block, so its - // lifetime must end somewhere in its defining basic block. - 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()) { +void LiveIntervals::computeRegMasks() { + RegMaskBlocks.resize(MF->getNumBlockIDs()); - 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; + // Find all instructions with regmask operands. + for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = MBBI; + std::pair &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()); } - } - - baseIndex = baseIndex.getNextIndex(); + // Compute the number of register mask instructions in this block. + RMB.second = RegMaskSlots.size() - RMB.first; } - - // The only case we should have a dead physreg here without a killing or - // instruction where we know it's dead is if it is live-in to the function - // and never used. Another possible case is the implicit use of the - // physical register has been deleted by two-address pass. - end = start.getDeadSlot(); - -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, - MachineOperand& MO, - unsigned MOIdx) { - 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) { - 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; - } +//===----------------------------------------------------------------------===// +// 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. +// - 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->definesRegister(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; +/// 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) { + for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); + Supers.isValid(); ++Supers) { + if (!MRI->reg_empty(*Supers)) + LRCalc->createDeadDefs(LI, *Supers); } - - 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) { - DEBUG(dbgs() << " live through"); - end = getMBBEndIdx(MBB); + // 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) { + for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); + Supers.isValid(); ++Supers) { + unsigned Reg = *Supers; + if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) + LRCalc->extendToUses(LI, Reg); + } } - - 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 -/// registers. for some ordering of the machine instructions [1,N] a -/// live interval is an interval [i, j) where 1 <= i <= j < N for -/// which a variable is live -void LiveIntervals::computeIntervals() { - DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" - << "********** Function: " - << ((Value*)mf_->getFunction())->getName() << '\n'); - RegMaskBlocks.resize(mf_->getNumBlockIDs()); - - SmallVector UndefUses; - for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); - MBBI != E; ++MBBI) { - MachineBasicBlock *MBB = MBBI; - RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); - - if (MBB->empty()) - continue; - - // Track the index of the current machine instr. - SlotIndex MIIndex = getMBBStartIdx(MBB); - 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)); - } +/// 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"); - // Skip over empty initial indices. - if (getInstructionFromIndex(MIIndex) == 0) - MIIndex = indexes_->getNextNonNullIndex(MIIndex); + // Keep track of the intervals allocated. + SmallVector NewIntvs; - 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 && - "Lost SlotIndex synchronization"); + // Check all basic blocks for live-ins. + for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); + MFI != MFE; ++MFI) { + const MachineBasicBlock *MBB = MFI; - // Handle defs. - for (int i = MI->getNumOperands() - 1; i >= 0; --i) { - MachineOperand &MO = MI->getOperand(i); + // We only care about ABI blocks: Entry + landing pads. + if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty()) + continue; - // Collect register masks. - if (MO.isRegMask()) { - RegMaskSlots.push_back(MIIndex.getRegSlot()); - RegMaskBits.push_back(MO.getRegMask()); - 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); } - - if (!MO.isReg() || !MO.getReg()) - continue; - - // handle register defs - build intervals - if (MO.isDef()) - handleRegisterDef(MBB, MI, MIIndex, MO, i); - else if (MO.isUndef()) - UndefUses.push_back(MO.getReg()); + VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator()); + (void)VNI; + DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); } - - // Move to the next instr slot. - MIIndex = indexes_->getNextNonNullIndex(MIIndex); } - - // Compute the number of register mask instructions in this block. - std::pair &RMB = RegMaskBlocks[MBB->getNumber()]; - RMB.second = RegMaskSlots.size() - RMB.first;; + DEBUG(dbgs() << '\n'); } + DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n"); - // Create empty intervals for registers defined by implicit_def's (except - // for those implicit_def that define values which are liveout of their - // blocks. - for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { - unsigned UndefReg = UndefUses[i]; - (void)getOrCreateInterval(UndefReg); - } + // Compute the 'normal' part of the intervals. + for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i) + computeRegUnitInterval(NewIntvs[i]); } -LiveInterval* LiveIntervals::createInterval(unsigned reg) { - float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; - 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; -} /// shrinkToUses - After removing some uses of a register, shrink its live /// range to just the remaining uses. This method does not compute reaching @@ -618,14 +311,13 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, SmallPtrSet 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 flags @@ -636,13 +328,10 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, 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)); } @@ -716,7 +405,7 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, 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; @@ -724,7 +413,7 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, // 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); @@ -738,19 +427,100 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, return CanSeparate; } +void LiveIntervals::extendToIndices(LiveInterval *LI, + ArrayRef Indices) { + assert(LRCalc && "LRCalc not initialized."); + LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); + for (unsigned i = 0, e = Indices.size(); i != e; ++i) + LRCalc->extend(LI, Indices[i]); +} + +void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, + SmallVectorImpl *EndPoints) { + LiveRangeQuery LRQ(*LI, Kill); + VNInfo *VNI = LRQ.valueOut(); + if (!VNI) + return; + + MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); + SlotIndex MBBStart, MBBEnd; + tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); + + // If VNI isn't live out from KillMBB, the value is trivially pruned. + if (LRQ.endPoint() < MBBEnd) { + LI->removeRange(Kill, LRQ.endPoint()); + if (EndPoints) EndPoints->push_back(LRQ.endPoint()); + return; + } + + // VNI is live out of KillMBB. + LI->removeRange(Kill, MBBEnd); + if (EndPoints) EndPoints->push_back(MBBEnd); + + // Find all blocks that are reachable from KillMBB without leaving VNI's live + // range. It is possible that KillMBB itself is reachable, so start a DFS + // from each successor. + typedef SmallPtrSet VisitedTy; + VisitedTy Visited; + for (MachineBasicBlock::succ_iterator + SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end(); + SuccI != SuccE; ++SuccI) { + for (df_ext_iterator + I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); + I != E;) { + MachineBasicBlock *MBB = *I; + + // Check if VNI is live in to MBB. + tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); + LiveRangeQuery LRQ(*LI, MBBStart); + if (LRQ.valueIn() != VNI) { + // This block isn't part of the VNI live range. Prune the search. + I.skipChildren(); + continue; + } + + // Prune the search if VNI is killed in MBB. + if (LRQ.endPoint() < MBBEnd) { + LI->removeRange(MBBStart, LRQ.endPoint()); + if (EndPoints) EndPoints->push_back(LRQ.endPoint()); + I.skipChildren(); + continue; + } + + // VNI is live through MBB. + LI->removeRange(MBBStart, MBBEnd); + if (EndPoints) EndPoints->push_back(MBBEnd); + ++I; + } + } +} //===----------------------------------------------------------------------===// // Register allocator hooks. // -void LiveIntervals::addKillFlags() { - for (iterator I = begin(), E = end(); I != E; ++I) { - unsigned Reg = I->first; - if (TargetRegisterInfo::isPhysicalRegister(Reg)) +void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { + // Keep track of regunit ranges. + SmallVector, 8> RU; + + 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)) + LiveInterval *LI = &getInterval(Reg); + if (LI->empty()) continue; - LiveInterval *LI = I->second; + + // 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; @@ -761,321 +531,34 @@ void LiveIntervals::addKillFlags() { MachineInstr *MI = getInstructionFromIndex(RI->end); if (!MI) continue; - MI->addRegisterKilled(Reg, NULL); - } - } -} - -#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 -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 -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 -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 -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::moveInstr(MachineBasicBlock::iterator insertPt, - MachineInstr *mi) { - MachineBasicBlock* mbb = mi->getParent(); - assert((insertPt == mbb->end() || insertPt->getParent() == mbb) && - "Cannot handle moves across basic block boundaries."); - assert(&*insertPt != mi && "No-op move requested?"); - assert(!mi->isBundled() && "Can't handle bundled instructions yet."); - - // Grab the original instruction index. - SlotIndex origIdx = indexes_->getInstructionIndex(mi); - - // Move the machine instr and obtain its new index. - indexes_->removeMachineInstrFromMaps(mi); - mbb->splice(insertPt, mbb, mi); - SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi); - - // Pick the direction. - bool movingUp = miIdx < origIdx; - - // Collect the operands. - DenseSet 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); + // 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 + // + // 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); } } - - BitVector reservedRegs(tri_->getReservedRegs(*mbb->getParent())); - - 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) && - !allocatableRegs_[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 *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 *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* @@ -1097,11 +580,30 @@ LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { // 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; } +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. @@ -1126,7 +628,6 @@ LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, VNInfo* VN = Interval.getNextValue( SlotIndex(getInstructionIndex(startInst).getRegSlot()), getVNInfoAllocator()); - VN->setHasPHIKill(true); LiveRange LR( SlotIndex(getInstructionIndex(startInst).getRegSlot()), getMBBEndIdx(startInst->getParent()), VN); @@ -1176,7 +677,7 @@ bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 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. @@ -1194,3 +695,474 @@ bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 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 OldIdx; + SlotIndex NewIdx; + SmallPtrSet Updated; + bool UpdateFlags; + +public: + HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, + const TargetRegisterInfo& TRI, + SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) + : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), + UpdateFlags(UpdateFlags) {} + + // FIXME: UpdateFlags is a workaround that creates live intervals for all + // 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. + LiveInterval *getRegUnitLI(unsigned Unit) { + if (UpdateFlags) + return &LIS.getRegUnit(Unit); + return LIS.getCachedRegUnit(Unit); + } + + /// Update all live ranges touched by MI, assuming a move from OldIdx to + /// NewIdx. + void updateAllRanges(MachineInstr *MI) { + DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); + bool hasRegMask = false; + for (MIOperands MO(MI); MO.isValid(); ++MO) { + if (MO->isRegMask()) + hasRegMask = true; + if (!MO->isReg()) + continue; + // Aggressively clear all kill flags. + // They are reinserted by VirtRegRewriter. + if (MO->isUse()) + MO->setIsKill(false); + + unsigned Reg = MO->getReg(); + if (!Reg) + continue; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + updateRange(LIS.getInterval(Reg)); + continue; + } + + // For physregs, only update the regunits that actually have a + // precomputed live range. + for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) + if (LiveInterval *LI = getRegUnitLI(*Units)) + updateRange(*LI); + } + if (hasRegMask) + updateRegMaskSlots(); + } + +private: + /// Update a single live range, assuming an instruction has been moved from + /// OldIdx to NewIdx. + void updateRange(LiveInterval &LI) { + if (!Updated.insert(&LI)) + return; + DEBUG({ + dbgs() << " "; + if (TargetRegisterInfo::isVirtualRegister(LI.reg)) + dbgs() << PrintReg(LI.reg); + else + dbgs() << PrintRegUnit(LI.reg, &TRI); + dbgs() << ":\t" << LI << '\n'; + }); + if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) + handleMoveDown(LI); + else + handleMoveUp(LI); + DEBUG(dbgs() << " -->\t" << LI << '\n'); + LI.verify(); + } + + /// Update LI to reflect an instruction has been moved downwards from OldIdx + /// to NewIdx. + /// + /// 1. Live def at OldIdx: + /// Move def to NewIdx, assert endpoint after NewIdx. + /// + /// 2. Live def at OldIdx, killed at NewIdx: + /// Change to dead def at NewIdx. + /// (Happens when bundling def+kill together). + /// + /// 3. Dead def at OldIdx: + /// Move def to NewIdx, possibly across another live value. + /// + /// 4. Def at OldIdx AND at NewIdx: + /// Remove live range [OldIdx;NewIdx) and value defined at OldIdx. + /// (Happens when bundling multiple defs together). + /// + /// 5. Value read at OldIdx, killed before NewIdx: + /// Extend kill to NewIdx. + /// + void handleMoveDown(LiveInterval &LI) { + // First look for a kill at OldIdx. + LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); + LiveInterval::iterator E = LI.end(); + // Is LI even live at OldIdx? + if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) + return; + + // Handle a live-in value. + if (!SlotIndex::isSameInstr(I->start, OldIdx)) { + bool isKill = SlotIndex::isSameInstr(OldIdx, I->end); + // If the live-in value already extends to NewIdx, there is nothing to do. + if (!SlotIndex::isEarlierInstr(I->end, NewIdx)) + return; + // Aggressively remove all kill flags from the old kill point. + // Kill flags shouldn't be used while live intervals exist, they will be + // reinserted by VirtRegRewriter. + if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end)) + for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) + if (MO->isReg() && MO->isUse()) + MO->setIsKill(false); + // Adjust I->end to reach NewIdx. This may temporarily make LI invalid by + // 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. + if (!isKill) + return; + ++I; + } + + // Check for a def at OldIdx. + if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start)) + return; + // We have a def at OldIdx. + VNInfo *DefVNI = I->valno; + assert(DefVNI->def == I->start && "Inconsistent def"); + DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); + // If the defined value extends beyond NewIdx, just move the def down. + // This is case 1 above. + if (SlotIndex::isEarlierInstr(NewIdx, I->end)) { + I->start = DefVNI->def; + return; + } + // The remaining possibilities are now: + // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx). + // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot(). + // In either case, it is possible that there is an existing def at NewIdx. + assert((I->end == OldIdx.getDeadSlot() || + SlotIndex::isSameInstr(I->end, NewIdx)) && + "Cannot move def below kill"); + LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot()); + 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?"); + LI.removeValNo(DefVNI); + return; + } + // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. + // If the def at OldIdx was dead, we allow it to be moved across other LI + // 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) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); + } + + /// Update LI to reflect an instruction has been moved upwards from OldIdx + /// to NewIdx. + /// + /// 1. Live def at OldIdx: + /// Hoist def to NewIdx. + /// + /// 2. Dead def at OldIdx: + /// Hoist def+end to NewIdx, possibly move across other values. + /// + /// 3. Dead def at OldIdx AND existing def at NewIdx: + /// Remove value defined at OldIdx, coalescing it with existing value. + /// + /// 4. Live def at OldIdx AND existing def at NewIdx: + /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx. + /// (Happens when bundling multiple defs together). + /// + /// 5. Value killed at OldIdx: + /// Hoist kill to NewIdx, then scan for last kill between NewIdx and + /// OldIdx. + /// + void handleMoveUp(LiveInterval &LI) { + // First look for a kill at OldIdx. + LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); + LiveInterval::iterator E = LI.end(); + // Is LI even live at OldIdx? + if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) + return; + + // Handle a live-in value. + if (!SlotIndex::isSameInstr(I->start, OldIdx)) { + // If the live-in value isn't killed here, there is nothing to do. + if (!SlotIndex::isSameInstr(OldIdx, I->end)) + return; + // Adjust I->end to end at NewIdx. If we are hoisting a kill above + // another use, we need to search for that use. Case 5 above. + I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); + ++I; + // If OldIdx also defines a value, there couldn't have been another use. + 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. + llvm::prior(I)->end = findLastUseBefore(LI.reg).getRegSlot(); + return; + } + } + + // Now deal with the def at OldIdx. + assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?"); + VNInfo *DefVNI = I->valno; + assert(DefVNI->def == I->start && "Inconsistent def"); + DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); + + // Check for an existing def at NewIdx. + LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot()); + 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. + LI.removeValNo(DefVNI); + return; + } + // Case 4: Replace def at NewIdx with live def at OldIdx. + I->start = DefVNI->def; + LI.removeValNo(NewI->valno); + return; + } + + // There is no existing def at NewIdx. Hoist DefVNI. + if (!I->end.isDead()) { + // Leave the end point of a live def. + I->start = DefVNI->def; + return; + } + + // DefVNI is a dead def. It may have been moved across other values in LI, + // so move I up to NewI. Slide [NewI;I) down one position. + std::copy_backward(NewI, I, llvm::next(I)); + *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); + } + + void updateRegMaskSlots() { + SmallVectorImpl::iterator RI = + std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), + OldIdx); + assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && + "No RegMask at OldIdx."); + *RI = NewIdx.getRegSlot(); + assert((RI == LIS.RegMaskSlots.begin() || + SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) && + "Cannot move regmask instruction above another call"); + assert((llvm::next(RI) == LIS.RegMaskSlots.end() || + SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) && + "Cannot move regmask instruction below another call"); + } + + // Return the last use of reg between NewIdx and OldIdx. + SlotIndex findLastUseBefore(unsigned Reg) { + + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + 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; + } + + // This is a regunit interval, so scanning the use list could be very + // expensive. Scan upwards from OldIdx instead. + assert(NewIdx < OldIdx && "Expected upwards move"); + SlotIndexes *Indexes = LIS.getSlotIndexes(); + MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); + + // OldIdx may not correspond to an instruction any longer, so set MII to + // point to the next instruction after OldIdx, or MBB->end(). + MachineBasicBlock::iterator MII = MBB->end(); + if (MachineInstr *MI = Indexes->getInstructionFromIndex( + Indexes->getNextNonNullIndex(OldIdx))) + if (MI->getParent() == MBB) + MII = MI; + + MachineBasicBlock::iterator Begin = MBB->begin(); + while (MII != Begin) { + if ((--MII)->isDebugValue()) + continue; + SlotIndex Idx = Indexes->getInstructionIndex(MII); + + // Stop searching when NewIdx is reached. + if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) + return NewIdx; + + // Check if MII uses Reg. + for (MIBundleOperands MO(MII); MO.isValid(); ++MO) + if (MO->isReg() && + TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && + TRI.hasRegUnit(MO->getReg(), Reg)) + return Idx; + } + // Didn't reach NewIdx. It must be the first instruction in the block. + return NewIdx; + } +}; + +void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) { + assert(!MI->isBundled() && "Can't handle bundled instructions yet."); + SlotIndex OldIndex = Indexes->getInstructionIndex(MI); + Indexes->removeMachineInstrFromMaps(MI); + SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); + assert(getMBBStartIdx(MI->getParent()) <= OldIndex && + OldIndex < getMBBEndIdx(MI->getParent()) && + "Cannot handle moves across basic block boundaries."); + + HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); + HME.updateAllRanges(MI); +} + +void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, + MachineInstr* BundleStart, + bool UpdateFlags) { + SlotIndex OldIndex = Indexes->getInstructionIndex(MI); + SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); + HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); + HME.updateAllRanges(MI); +} + +void +LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef OrigRegs) { + // Find anchor points, which are at the beginning/end of blocks or at + // instructions that already have indexes. + while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) + --Begin; + while (End != MBB->end() && !Indexes->hasIndex(End)) + ++End; + + SlotIndex endIdx; + if (End == MBB->end()) + endIdx = getMBBEndIdx(MBB).getPrevSlot(); + else + endIdx = getInstructionIndex(End); + + Indexes->repairIndexesInRange(MBB, Begin, End); + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; + for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + if (MOI->isReg() && + TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && + !hasInterval(MOI->getReg())) { + LiveInterval &LI = getOrCreateInterval(MOI->getReg()); + computeVirtRegInterval(&LI); + } + } + } + + for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { + unsigned Reg = OrigRegs[i]; + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + + LiveInterval &LI = getInterval(Reg); + // FIXME: Should we support undefs that gain defs? + if (!LI.hasAtLeastOneValue()) + continue; + + LiveInterval::iterator LII = LI.find(endIdx); + SlotIndex lastUseIdx; + if (LII != LI.end() && LII->start < endIdx) + lastUseIdx = LII->end; + else + --LII; + + for (MachineBasicBlock::iterator I = End; I != Begin;) { + --I; + MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; + + SlotIndex instrIdx = getInstructionIndex(MI); + bool isStartValid = getInstructionFromIndex(LII->start); + bool isEndValid = getInstructionFromIndex(LII->end); + + // FIXME: This doesn't currently handle early-clobber or multiple removed + // defs inside of the region to repair. + for (MachineInstr::mop_iterator OI = MI->operands_begin(), + OE = MI->operands_end(); OI != OE; ++OI) { + const MachineOperand &MO = *OI; + if (!MO.isReg() || MO.getReg() != Reg) + continue; + + if (MO.isDef()) { + if (!isStartValid) { + if (LII->end.isDead()) { + SlotIndex prevStart; + if (LII != LI.begin()) + prevStart = llvm::prior(LII)->start; + + // FIXME: This could be more efficient if there was a removeRange + // method that returned an iterator. + LI.removeRange(*LII, true); + if (prevStart.isValid()) + LII = LI.find(prevStart); + else + LII = LI.begin(); + } else { + LII->start = instrIdx.getRegSlot(); + LII->valno->def = instrIdx.getRegSlot(); + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + continue; + } + } + + if (!lastUseIdx.isValid()) { + VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), + VNInfoAllocator); + LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI); + LII = LI.addRange(LR); + } else if (LII->start != instrIdx.getRegSlot()) { + VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), + VNInfoAllocator); + LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI); + LII = LI.addRange(LR); + } + + if (MO.getSubReg() && !MO.isUndef()) + lastUseIdx = instrIdx.getRegSlot(); + else + lastUseIdx = SlotIndex(); + } else if (MO.isUse()) { + // FIXME: This should probably be handled outside of this branch, + // either as part of the def case (for defs inside of the region) or + // after the loop over the region. + if (!isEndValid && !LII->end.isBlock()) + LII->end = instrIdx.getRegSlot(); + if (!lastUseIdx.isValid()) + lastUseIdx = instrIdx.getRegSlot(); + } + } + } + } +}