diff options
Diffstat (limited to 'lib/CodeGen/LiveIntervalAnalysis.cpp')
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 793 |
1 files changed, 158 insertions, 635 deletions
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 79f46f3395..2a93a35b3f 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -28,6 +28,7 @@ #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/ProcessImplicitDefs.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -80,6 +81,10 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { } AU.addRequiredID(TwoAddressInstructionPassID); + AU.addPreserved<ProcessImplicitDefs>(); + AU.addRequired<ProcessImplicitDefs>(); + AU.addPreserved<SlotIndexes>(); + AU.addRequiredTransitive<SlotIndexes>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -89,12 +94,7 @@ void LiveIntervals::releaseMemory() { E = r2iMap_.end(); I != E; ++I) delete I->second; - MBB2IdxMap.clear(); - Idx2MBBMap.clear(); - mi2iMap_.clear(); - i2miMap_.clear(); r2iMap_.clear(); - terminatorGaps.clear(); phiJoinCopies.clear(); // Release VNInfo memroy regions after all VNInfo objects are dtor'd. @@ -106,422 +106,6 @@ void LiveIntervals::releaseMemory() { } } -static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg, - unsigned OpIdx, const TargetInstrInfo *tii_){ - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - Reg == SrcReg) - return true; - - if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) - return true; - if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) - return true; - return false; -} - -/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure -/// there is one implicit_def for each use. Add isUndef marker to -/// implicit_def defs and their uses. -void LiveIntervals::processImplicitDefs() { - SmallSet<unsigned, 8> ImpDefRegs; - SmallVector<MachineInstr*, 8> ImpDefMIs; - MachineBasicBlock *Entry = mf_->begin(); - SmallPtrSet<MachineBasicBlock*,16> Visited; - for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > - DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); - DFI != E; ++DFI) { - MachineBasicBlock *MBB = *DFI; - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ) { - MachineInstr *MI = &*I; - ++I; - if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { - unsigned Reg = MI->getOperand(0).getReg(); - ImpDefRegs.insert(Reg); - if (TargetRegisterInfo::isPhysicalRegister(Reg)) { - for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) - ImpDefRegs.insert(*SS); - } - ImpDefMIs.push_back(MI); - continue; - } - - if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { - MachineOperand &MO = MI->getOperand(2); - if (ImpDefRegs.count(MO.getReg())) { - // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2 - // This is an identity copy, eliminate it now. - if (MO.isKill()) { - LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); - vi.removeKill(MI); - } - MI->eraseFromParent(); - continue; - } - } - - bool ChangedToImpDef = false; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse() || MO.isUndef()) - continue; - unsigned Reg = MO.getReg(); - if (!Reg) - continue; - if (!ImpDefRegs.count(Reg)) - continue; - // Use is a copy, just turn it into an implicit_def. - if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) { - bool isKill = MO.isKill(); - MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); - for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) - MI->RemoveOperand(j); - if (isKill) { - ImpDefRegs.erase(Reg); - LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); - vi.removeKill(MI); - } - ChangedToImpDef = true; - break; - } - - MO.setIsUndef(); - if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { - // Make sure other uses of - for (unsigned j = i+1; j != e; ++j) { - MachineOperand &MOJ = MI->getOperand(j); - if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) - MOJ.setIsUndef(); - } - ImpDefRegs.erase(Reg); - } - } - - if (ChangedToImpDef) { - // Backtrack to process this new implicit_def. - --I; - } else { - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isDef()) - continue; - ImpDefRegs.erase(MO.getReg()); - } - } - } - - // Any outstanding liveout implicit_def's? - for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { - MachineInstr *MI = ImpDefMIs[i]; - unsigned Reg = MI->getOperand(0).getReg(); - if (TargetRegisterInfo::isPhysicalRegister(Reg) || - !ImpDefRegs.count(Reg)) { - // Delete all "local" implicit_def's. That include those which define - // physical registers since they cannot be liveout. - MI->eraseFromParent(); - continue; - } - - // If there are multiple defs of the same register and at least one - // is not an implicit_def, do not insert implicit_def's before the - // uses. - bool Skip = false; - for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), - DE = mri_->def_end(); DI != DE; ++DI) { - if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { - Skip = true; - break; - } - } - if (Skip) - continue; - - // The only implicit_def which we want to keep are those that are live - // out of its block. - MI->eraseFromParent(); - - for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), - UE = mri_->use_end(); UI != UE; ) { - MachineOperand &RMO = UI.getOperand(); - MachineInstr *RMI = &*UI; - ++UI; - MachineBasicBlock *RMBB = RMI->getParent(); - if (RMBB == MBB) - continue; - - // Turn a copy use into an implicit_def. - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && - Reg == SrcReg) { - RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); - for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j) - RMI->RemoveOperand(j); - continue; - } - - const TargetRegisterClass* RC = mri_->getRegClass(Reg); - unsigned NewVReg = mri_->createVirtualRegister(RC); - RMO.setReg(NewVReg); - RMO.setIsUndef(); - RMO.setIsKill(); - } - } - ImpDefRegs.clear(); - ImpDefMIs.clear(); - } -} - - -void LiveIntervals::computeNumbering() { - Index2MiMap OldI2MI = i2miMap_; - std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; - - Idx2MBBMap.clear(); - MBB2IdxMap.clear(); - mi2iMap_.clear(); - i2miMap_.clear(); - terminatorGaps.clear(); - phiJoinCopies.clear(); - - FunctionSize = 0; - - // Number MachineInstrs and MachineBasicBlocks. - // Initialize MBB indexes to a sentinal. - MBB2IdxMap.resize(mf_->getNumBlockIDs(), - std::make_pair(LiveIndex(),LiveIndex())); - - LiveIndex MIIndex; - for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); - MBB != E; ++MBB) { - LiveIndex StartIdx = MIIndex; - - // Insert an empty slot at the beginning of each block. - MIIndex = getNextIndex(MIIndex); - i2miMap_.push_back(0); - - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - - if (I == MBB->getFirstTerminator()) { - // Leave a gap for before terminators, this is where we will point - // PHI kills. - LiveIndex tGap(true, MIIndex); - bool inserted = - terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; - assert(inserted && - "Multiple 'first' terminators encountered during numbering."); - inserted = inserted; // Avoid compiler warning if assertions turned off. - i2miMap_.push_back(0); - - MIIndex = getNextIndex(MIIndex); - } - - bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; - assert(inserted && "multiple MachineInstr -> index mappings"); - inserted = true; - i2miMap_.push_back(I); - MIIndex = getNextIndex(MIIndex); - FunctionSize++; - - // Insert max(1, numdefs) empty slots after every instruction. - unsigned Slots = I->getDesc().getNumDefs(); - if (Slots == 0) - Slots = 1; - while (Slots--) { - MIIndex = getNextIndex(MIIndex); - i2miMap_.push_back(0); - } - - } - - if (MBB->getFirstTerminator() == MBB->end()) { - // Leave a gap for before terminators, this is where we will point - // PHI kills. - LiveIndex tGap(true, MIIndex); - bool inserted = - terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; - assert(inserted && - "Multiple 'first' terminators encountered during numbering."); - inserted = inserted; // Avoid compiler warning if assertions turned off. - i2miMap_.push_back(0); - - MIIndex = getNextIndex(MIIndex); - } - - // Set the MBB2IdxMap entry for this MBB. - MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, getPrevSlot(MIIndex)); - Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); - } - - std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); - - if (!OldI2MI.empty()) - for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { - for (LiveInterval::iterator LI = OI->second->begin(), - LE = OI->second->end(); LI != LE; ++LI) { - - // Remap the start index of the live range to the corresponding new - // number, or our best guess at what it _should_ correspond to if the - // original instruction has been erased. This is either the following - // instruction or its predecessor. - unsigned index = LI->start.getVecIndex(); - LiveIndex::Slot offset = LI->start.getSlot(); - if (LI->start.isLoad()) { - std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); - // Take the pair containing the index - std::vector<IdxMBBPair>::const_iterator J = - (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; - - LI->start = getMBBStartIdx(J->second); - } else { - LI->start = LiveIndex( - LiveIndex(mi2iMap_[OldI2MI[index]]), - (LiveIndex::Slot)offset); - } - - // Remap the ending index in the same way that we remapped the start, - // except for the final step where we always map to the immediately - // following instruction. - index = (getPrevSlot(LI->end)).getVecIndex(); - offset = LI->end.getSlot(); - if (LI->end.isLoad()) { - // VReg dies at end of block. - std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); - --I; - - LI->end = getNextSlot(getMBBEndIdx(I->second)); - } else { - unsigned idx = index; - while (index < OldI2MI.size() && !OldI2MI[index]) ++index; - - if (index != OldI2MI.size()) - LI->end = - LiveIndex(mi2iMap_[OldI2MI[index]], - (idx == index ? offset : LiveIndex::LOAD)); - else - LI->end = - LiveIndex(LiveIndex::NUM * i2miMap_.size()); - } - } - - for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), - VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { - VNInfo* vni = *VNI; - - // Remap the VNInfo def index, which works the same as the - // start indices above. VN's with special sentinel defs - // don't need to be remapped. - if (vni->isDefAccurate() && !vni->isUnused()) { - unsigned index = vni->def.getVecIndex(); - LiveIndex::Slot offset = vni->def.getSlot(); - if (vni->def.isLoad()) { - std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); - // Take the pair containing the index - std::vector<IdxMBBPair>::const_iterator J = - (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; - - vni->def = getMBBStartIdx(J->second); - } else { - vni->def = LiveIndex(mi2iMap_[OldI2MI[index]], offset); - } - } - - // Remap the VNInfo kill indices, which works the same as - // the end indices above. - for (size_t i = 0; i < vni->kills.size(); ++i) { - unsigned index = getPrevSlot(vni->kills[i]).getVecIndex(); - LiveIndex::Slot offset = vni->kills[i].getSlot(); - - if (vni->kills[i].isLoad()) { - assert("Value killed at a load slot."); - /*std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); - --I; - - vni->kills[i] = getMBBEndIdx(I->second);*/ - } else { - if (vni->kills[i].isPHIIndex()) { - std::vector<IdxMBBPair>::const_iterator I = - std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); - --I; - vni->kills[i] = terminatorGaps[I->second]; - } else { - assert(OldI2MI[index] != 0 && - "Kill refers to instruction not present in index maps."); - vni->kills[i] = LiveIndex(mi2iMap_[OldI2MI[index]], offset); - } - - /* - unsigned idx = index; - while (index < OldI2MI.size() && !OldI2MI[index]) ++index; - - if (index != OldI2MI.size()) - vni->kills[i] = mi2iMap_[OldI2MI[index]] + - (idx == index ? offset : 0); - else - vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); - */ - } - } - } - } -} - -void LiveIntervals::scaleNumbering(int factor) { - // Need to - // * scale MBB begin and end points - // * scale all ranges. - // * Update VNI structures. - // * Scale instruction numberings - - // Scale the MBB indices. - Idx2MBBMap.clear(); - for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end(); - MBB != MBBE; ++MBB) { - std::pair<LiveIndex, LiveIndex> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; - mbbIndices.first = mbbIndices.first.scale(factor); - mbbIndices.second = mbbIndices.second.scale(factor); - Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); - } - std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); - - // Scale terminator gaps. - for (DenseMap<MachineBasicBlock*, LiveIndex>::iterator - TGI = terminatorGaps.begin(), TGE = terminatorGaps.end(); - TGI != TGE; ++TGI) { - terminatorGaps[TGI->first] = TGI->second.scale(factor); - } - - // Scale the intervals. - for (iterator LI = begin(), LE = end(); LI != LE; ++LI) { - LI->second->scaleNumbering(factor); - } - - // Scale MachineInstrs. - Mi2IndexMap oldmi2iMap = mi2iMap_; - LiveIndex highestSlot; - for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end(); - MI != ME; ++MI) { - LiveIndex newSlot = MI->second.scale(factor); - mi2iMap_[MI->first] = newSlot; - highestSlot = std::max(highestSlot, newSlot); - } - - unsigned highestVIndex = highestSlot.getVecIndex(); - i2miMap_.clear(); - i2miMap_.resize(highestVIndex + 1); - for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end(); - MI != ME; ++MI) { - i2miMap_[MI->second.getVecIndex()] = const_cast<MachineInstr *>(MI->first); - } - -} - - /// runOnMachineFunction - Register allocate the whole function /// bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { @@ -532,10 +116,9 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { tii_ = tm_->getInstrInfo(); aa_ = &getAnalysis<AliasAnalysis>(); lv_ = &getAnalysis<LiveVariables>(); + indexes_ = &getAnalysis<SlotIndexes>(); allocatableRegs_ = tri_->getAllocatableSet(fn); - processImplicitDefs(); - computeNumbering(); computeIntervals(); performEarlyCoalescing(); @@ -579,12 +162,13 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - for (LiveIndex index = getBaseIndex(I->start), - end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end; - index = getNextIndex(index)) { + for (SlotIndex index = I->start.getBaseIndex(), + end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); + index != end; + index = index.getNextIndex()) { // skip deleted instructions while (index != end && !getInstructionFromIndex(index)) - index = getNextIndex(index); + index = index.getNextIndex(); if (index == end) break; MachineInstr *MI = getInstructionFromIndex(index); @@ -620,16 +204,17 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, SmallPtrSet<MachineInstr*,32> &JoinedCopies) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - for (LiveIndex index = getBaseIndex(I->start), - end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end; - index = getNextIndex(index)) { + for (SlotIndex index = I->start.getBaseIndex(), + end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); + index != end; + index = index.getNextIndex()) { // Skip deleted instructions. MachineInstr *MI = 0; while (index != end) { MI = getInstructionFromIndex(index); if (MI) break; - index = getNextIndex(index); + index = index.getNextIndex(); } if (index == end) break; @@ -664,7 +249,7 @@ static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, - LiveIndex MIIdx, + SlotIndex MIIdx, MachineOperand& MO, unsigned MOIdx, LiveInterval &interval) { @@ -680,11 +265,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); if (interval.empty()) { // Get the Idx of the defining instructions. - LiveIndex defIndex = getDefIndex(MIIdx); + SlotIndex defIndex = MIIdx.getDefIndex(); // Earlyclobbers move back one, so that they overlap the live range // of inputs. if (MO.isEarlyClobber()) - defIndex = getUseIndex(MIIdx); + defIndex = MIIdx.getUseIndex(); VNInfo *ValNo; MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; @@ -704,16 +289,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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? - LiveIndex killIdx; + SlotIndex killIdx; if (vi.Kills[0] != mi) - killIdx = getNextSlot(getUseIndex(getInstructionIndex(vi.Kills[0]))); - else if (MO.isEarlyClobber()) - // Earlyclobbers that die in this instruction move up one extra, to - // compensate for having the starting point moved back one. This - // gets them to overlap the live range of other outputs. - killIdx = getNextSlot(getNextSlot(defIndex)); + killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); else - killIdx = getNextSlot(defIndex); + killIdx = defIndex.getStoreIndex(); // If the kill happens after the definition, we have an intra-block // live range. @@ -732,7 +312,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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, getNextSlot(getMBBEndIdx(mbb)), ValNo); + LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(), + ValNo); DEBUG(errs() << " +" << NewLR); interval.addRange(NewLR); @@ -741,9 +322,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // live interval. for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), E = vi.AliveBlocks.end(); I != E; ++I) { - LiveRange LR(getMBBStartIdx(*I), - getNextSlot(getMBBEndIdx(*I)), // MBB ends at -1. - ValNo); + LiveRange LR( + getMBBStartIdx(mf_->getBlockNumbered(*I)), + getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(), + ValNo); interval.addRange(LR); DEBUG(errs() << " +" << LR); } @@ -752,8 +334,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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]; - LiveIndex killIdx = - getNextSlot(getUseIndex(getInstructionIndex(Kill))); + SlotIndex killIdx = + getInstructionIndex(Kill).getDefIndex(); LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); interval.addRange(LR); ValNo->addKill(killIdx); @@ -772,13 +354,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // need to take the LiveRegion that defines this register and split it // into two values. assert(interval.containsOneValue()); - LiveIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def); - LiveIndex RedefIndex = getDefIndex(MIIdx); + SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); + SlotIndex RedefIndex = MIIdx.getDefIndex(); if (MO.isEarlyClobber()) - RedefIndex = getUseIndex(MIIdx); + RedefIndex = MIIdx.getUseIndex(); const LiveRange *OldLR = - interval.getLiveRangeContaining(getPrevSlot(RedefIndex)); + interval.getLiveRangeContaining(RedefIndex.getUseIndex()); VNInfo *OldValNo = OldLR->valno; // Delete the initial value, which should be short and continuous, @@ -811,10 +393,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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, MO.isEarlyClobber() ? - getNextSlot(getNextSlot(RedefIndex)) : - getNextSlot(RedefIndex), OldValNo)); + interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), + OldValNo)); DEBUG({ errs() << " RESULT: "; @@ -829,9 +409,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, VNInfo *VNI = interval.getValNumInfo(0); MachineInstr *Killer = vi.Kills[0]; phiJoinCopies.push_back(Killer); - LiveIndex Start = getMBBStartIdx(Killer->getParent()); - LiveIndex End = - getNextSlot(getUseIndex(getInstructionIndex(Killer))); + SlotIndex Start = getMBBStartIdx(Killer->getParent()); + SlotIndex End = getInstructionIndex(Killer).getDefIndex(); DEBUG({ errs() << " Removing [" << Start << "," << End << "] from: "; interval.print(errs(), tri_); @@ -841,7 +420,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, assert(interval.ranges.size() == 1 && "Newly discovered PHI interval has >1 ranges."); MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); - VNI->addKill(terminatorGaps[killMBB]); + VNI->addKill(indexes_->getTerminatorGap(killMBB)); VNI->setHasPHIKill(true); DEBUG({ errs() << " RESULT: "; @@ -851,8 +430,8 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Replace the interval with one of a NEW value number. Note that this // value number isn't actually defined by an instruction, weird huh? :) LiveRange LR(Start, End, - interval.getNextValue(LiveIndex(mbb->getNumber()), - 0, false, VNInfoAllocator)); + interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), + 0, false, VNInfoAllocator)); LR.valno->setIsPHIDef(true); DEBUG(errs() << " replace range with " << LR); interval.addRange(LR); @@ -866,9 +445,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // 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. - LiveIndex defIndex = getDefIndex(MIIdx); + SlotIndex defIndex = MIIdx.getDefIndex(); if (MO.isEarlyClobber()) - defIndex = getUseIndex(MIIdx); + defIndex = MIIdx.getUseIndex(); VNInfo *ValNo; MachineInstr *CopyMI = NULL; @@ -880,10 +459,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, CopyMI = mi; ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); - LiveIndex killIndex = getNextSlot(getMBBEndIdx(mbb)); + SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex(); LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); - ValNo->addKill(terminatorGaps[mbb]); + ValNo->addKill(indexes_->getTerminatorGap(mbb)); ValNo->setHasPHIKill(true); DEBUG(errs() << " +" << LR); } @@ -894,7 +473,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi, - LiveIndex MIIdx, + SlotIndex MIIdx, MachineOperand& MO, LiveInterval &interval, MachineInstr *CopyMI) { @@ -905,12 +484,12 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, printRegName(interval.reg, tri_); }); - LiveIndex baseIndex = MIIdx; - LiveIndex start = getDefIndex(baseIndex); + SlotIndex baseIndex = MIIdx; + SlotIndex start = baseIndex.getDefIndex(); // Earlyclobbers move back one. if (MO.isEarlyClobber()) - start = getUseIndex(MIIdx); - LiveIndex end = start; + start = MIIdx.getUseIndex(); + SlotIndex end = start; // If it is not used after definition, it is considered dead at // the instruction defining it. Hence its interval is: @@ -919,53 +498,51 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // advance below compensates. if (MO.isDead()) { DEBUG(errs() << " dead"); - if (MO.isEarlyClobber()) - end = getNextSlot(getNextSlot(start)); - else - end = getNextSlot(start); + end = start.getStoreIndex(); 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 = getNextIndex(baseIndex); + baseIndex = baseIndex.getNextIndex(); while (++mi != MBB->end()) { - while (baseIndex.getVecIndex() < i2miMap_.size() && - getInstructionFromIndex(baseIndex) == 0) - baseIndex = getNextIndex(baseIndex); + + if (getInstructionFromIndex(baseIndex) == 0) + baseIndex = indexes_->getNextNonNullIndex(baseIndex); + if (mi->killsRegister(interval.reg, tri_)) { DEBUG(errs() << " killed"); - end = getNextSlot(getUseIndex(baseIndex)); + end = baseIndex.getDefIndex(); goto exit; } else { int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); if (DefIdx != -1) { if (mi->isRegTiedToUseOperand(DefIdx)) { // Two-address instruction. - end = getDefIndex(baseIndex); - if (mi->getOperand(DefIdx).isEarlyClobber()) - end = getUseIndex(baseIndex); + end = baseIndex.getDefIndex(); + assert(!mi->getOperand(DefIdx).isEarlyClobber() && + "Two address instruction is an early clobber?"); } 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(errs() << " dead"); - end = getNextSlot(start); + end = start.getStoreIndex(); } goto exit; } } - baseIndex = getNextIndex(baseIndex); + baseIndex = baseIndex.getNextIndex(); } // 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 = getNextSlot(start); + end = start.getStoreIndex(); exit: assert(start < end && "did not find end of interval?"); @@ -985,7 +562,7 @@ exit: void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI, - LiveIndex MIIdx, + SlotIndex MIIdx, MachineOperand& MO, unsigned MOIdx) { if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) @@ -1012,7 +589,7 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, } void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, - LiveIndex MIIdx, + SlotIndex MIIdx, LiveInterval &interval, bool isAlias) { DEBUG({ errs() << "\t\tlivein register: "; @@ -1022,18 +599,18 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, // 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(); - LiveIndex baseIndex = MIIdx; - LiveIndex start = baseIndex; - while (baseIndex.getVecIndex() < i2miMap_.size() && - getInstructionFromIndex(baseIndex) == 0) - baseIndex = getNextIndex(baseIndex); - LiveIndex end = baseIndex; + SlotIndex baseIndex = MIIdx; + SlotIndex start = baseIndex; + if (getInstructionFromIndex(baseIndex) == 0) + baseIndex = indexes_->getNextNonNullIndex(baseIndex); + + SlotIndex end = baseIndex; bool SeenDefUse = false; while (mi != MBB->end()) { if (mi->killsRegister(interval.reg, tri_)) { DEBUG(errs() << " killed"); - end = getNextSlot(getUseIndex(baseIndex)); + end = baseIndex.getDefIndex(); SeenDefUse = true; break; } else if (mi->modifiesRegister(interval.reg, tri_)) { @@ -1042,17 +619,14 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, // it. Hence its interval is: // [defSlot(def), defSlot(def)+1) DEBUG(errs() << " dead"); - end = getNextSlot(getDefIndex(start)); + end = start.getStoreIndex(); SeenDefUse = true; break; } - baseIndex = getNextIndex(baseIndex); ++mi; if (mi != MBB->end()) { - while (baseIndex.getVecIndex() < i2miMap_.size() && - getInstructionFromIndex(baseIndex) == 0) - baseIndex = getNextIndex(baseIndex); + baseIndex = indexes_->getNextNonNullIndex(baseIndex); } } @@ -1060,7 +634,7 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, if (!SeenDefUse) { if (isAlias) { DEBUG(errs() << " dead"); - end = getNextSlot(getDefIndex(MIIdx)); + end = MIIdx.getStoreIndex(); } else { DEBUG(errs() << " live through"); end = baseIndex; @@ -1068,7 +642,7 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, } VNInfo *vni = - interval.getNextValue(LiveIndex(MBB->getNumber()), + interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 0, false, VNInfoAllocator); vni->setIsPHIDef(true); LiveRange LR(start, end, vni); @@ -1139,11 +713,11 @@ void LiveIntervals::performEarlyCoalescing() { MachineInstr *PHICopy = OtherCopies[i]; DEBUG(errs() << "Moving: " << *PHICopy); - LiveIndex MIIndex = getInstructionIndex(PHICopy); - LiveIndex DefIndex = getDefIndex(MIIndex); + SlotIndex MIIndex = getInstructionIndex(PHICopy); + SlotIndex DefIndex = MIIndex.getDefIndex(); LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); - LiveIndex StartIndex = SLR->start; - LiveIndex EndIndex = SLR->end; + SlotIndex StartIndex = SLR->start; + SlotIndex EndIndex = SLR->end; // Delete val# defined by the now identity copy and add the range from // beginning of the mbb to the end of the range. @@ -1169,11 +743,11 @@ void LiveIntervals::performEarlyCoalescing() { MachineInstr *PHICopy = IdentCopies[i]; DEBUG(errs() << "Coalescing: " << *PHICopy); - LiveIndex MIIndex = getInstructionIndex(PHICopy); - LiveIndex DefIndex = getDefIndex(MIIndex); + SlotIndex MIIndex = getInstructionIndex(PHICopy); + SlotIndex DefIndex = MIIndex.getDefIndex(); LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); - LiveIndex StartIndex = SLR->start; - LiveIndex EndIndex = SLR->end; + SlotIndex StartIndex = SLR->start; + SlotIndex EndIndex = SLR->end; // Delete val# defined by the now identity copy and add the range from // beginning of the mbb to the end of the range. @@ -1186,9 +760,9 @@ void LiveIntervals::performEarlyCoalescing() { } // Remove the phi join and update the phi block liveness. - LiveIndex MIIndex = getInstructionIndex(Join); - LiveIndex UseIndex = getUseIndex(MIIndex); - LiveIndex DefIndex = getDefIndex(MIIndex); + SlotIndex MIIndex = getInstructionIndex(Join); + SlotIndex UseIndex = MIIndex.getUseIndex(); + SlotIndex DefIndex = MIIndex.getDefIndex(); LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex); LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex); DLR->valno->setCopy(0); @@ -1218,7 +792,7 @@ void LiveIntervals::computeIntervals() { MBBI != E; ++MBBI) { MachineBasicBlock *MBB = MBBI; // Track the index of the current machine instr. - LiveIndex MIIndex = getMBBStartIdx(MBB); + SlotIndex MIIndex = getMBBStartIdx(MBB); DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); @@ -1235,9 +809,8 @@ void LiveIntervals::computeIntervals() { } // Skip over empty initial indices. - while (MIIndex.getVecIndex() < i2miMap_.size() && - getInstructionFromIndex(MIIndex) == 0) - MIIndex = getNextIndex(MIIndex); + if (getInstructionFromIndex(MIIndex) == 0) + MIIndex = indexes_->getNextNonNullIndex(MIIndex); |