#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/PseudoSourceValue.h"
+#include "llvm/CodeGen/ProcessImplicitDefs.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
using namespace llvm;
// Hidden options for help debugging.
-static cl::opt<bool> DisableReMat("disable-rematerialization",
+static cl::opt<bool> DisableReMat("disable-rematerialization",
cl::init(false), cl::Hidden);
-static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
-
-static cl::opt<bool> EnableFastSpilling("fast-spill",
- cl::init(false), cl::Hidden);
-
-static cl::opt<bool> EarlyCoalescing("early-coalescing", cl::init(false));
-
-static cl::opt<int> CoalescingLimit("early-coalescing-limit",
- cl::init(-1), cl::Hidden);
-
STATISTIC(numIntervals , "Number of original intervals");
STATISTIC(numFolds , "Number of loads/stores folded into instructions");
STATISTIC(numSplits , "Number of intervals split");
-STATISTIC(numCoalescing, "Number of early coalescing performed");
char LiveIntervals::ID = 0;
-static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
+INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
+ "Live Interval Analysis", false, false)
+INITIALIZE_PASS_DEPENDENCY(LiveVariables)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(PHIElimination)
+INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
+INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
+ "Live Interval Analysis", false, false)
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<AliasAnalysis>();
AU.addPreserved<AliasAnalysis>();
- AU.addPreserved<LiveVariables>();
AU.addRequired<LiveVariables>();
- AU.addPreservedID(MachineLoopInfoID);
+ AU.addPreserved<LiveVariables>();
+ AU.addRequired<MachineLoopInfo>();
+ AU.addPreserved<MachineLoopInfo>();
AU.addPreservedID(MachineDominatorsID);
-
+
if (!StrongPHIElim) {
AU.addPreservedID(PHIEliminationID);
AU.addRequiredID(PHIEliminationID);
}
-
+
AU.addRequiredID(TwoAddressInstructionPassID);
+ AU.addPreserved<ProcessImplicitDefs>();
+ AU.addRequired<ProcessImplicitDefs>();
+ AU.addPreserved<SlotIndexes>();
+ AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
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.
+ // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
VNInfoAllocator.Reset();
while (!CloneMIs.empty()) {
MachineInstr *MI = CloneMIs.back();
}
}
-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(),MachineInstrIndex()));
-
- 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(MachineInstrIndex::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, MachineInstrIndex> &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) {
tii_ = tm_->getInstrInfo();
aa_ = &getAnalysis<AliasAnalysis>();
lv_ = &getAnalysis<LiveVariables>();
+ indexes_ = &getAnalysis<SlotIndexes>();
allocatableRegs_ = tri_->getAllocatableSet(fn);
- processImplicitDefs();
- computeNumbering();
computeIntervals();
- performEarlyCoalescing();
numIntervals += getNumIntervals();
void LiveIntervals::printInstrs(raw_ostream &OS) const {
OS << "********** MACHINEINSTRS **********\n";
-
- for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
- mbbi != mbbe; ++mbbi) {
- OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
- for (MachineBasicBlock::iterator mii = mbbi->begin(),
- mie = mbbi->end(); mii != mie; ++mii) {
- OS << getInstructionIndex(mii) << '\t' << *mii;
- }
- }
+ mf_->print(OS, indexes_);
}
void LiveIntervals::dumpInstrs() const {
- printInstrs(errs());
+ printInstrs(dbgs());
}
-/// conflictsWithPhysRegDef - Returns true if the specified register
-/// is defined during the duration of the specified interval.
-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)) {
- // skip deleted instructions
- while (index != end && !getInstructionFromIndex(index))
- index = getNextIndex(index);
- if (index == end) break;
+bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,
+ VirtRegMap &vrm, unsigned reg) {
+ // We don't handle fancy stuff crossing basic block boundaries
+ if (li.ranges.size() != 1)
+ return true;
+ const LiveRange &range = li.ranges.front();
+ SlotIndex idx = range.start.getBaseIndex();
+ SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();
+
+ // Skip deleted instructions
+ MachineInstr *firstMI = getInstructionFromIndex(idx);
+ while (!firstMI && idx != end) {
+ idx = idx.getNextIndex();
+ firstMI = getInstructionFromIndex(idx);
+ }
+ if (!firstMI)
+ return false;
- MachineInstr *MI = getInstructionFromIndex(index);
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
- if (SrcReg == li.reg || DstReg == li.reg)
- continue;
- for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
- MachineOperand& mop = MI->getOperand(i);
- if (!mop.isReg())
- continue;
- unsigned PhysReg = mop.getReg();
- if (PhysReg == 0 || PhysReg == li.reg)
+ // Find last instruction in range
+ SlotIndex lastIdx = end.getPrevIndex();
+ MachineInstr *lastMI = getInstructionFromIndex(lastIdx);
+ while (!lastMI && lastIdx != idx) {
+ lastIdx = lastIdx.getPrevIndex();
+ lastMI = getInstructionFromIndex(lastIdx);
+ }
+ if (!lastMI)
+ return false;
+
+ // Range cannot cross basic block boundaries or terminators
+ MachineBasicBlock *MBB = firstMI->getParent();
+ if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())
+ return true;
+
+ MachineBasicBlock::const_iterator E = lastMI;
+ ++E;
+ for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {
+ const MachineInstr &MI = *I;
+
+ // Allow copies to and from li.reg
+ if (MI.isCopy())
+ if (MI.getOperand(0).getReg() == li.reg ||
+ MI.getOperand(1).getReg() == li.reg)
+ continue;
+
+ // Check for operands using reg
+ for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+ const MachineOperand& mop = MI.getOperand(i);
+ if (!mop.isReg())
+ continue;
+ unsigned PhysReg = mop.getReg();
+ if (PhysReg == 0 || PhysReg == li.reg)
+ continue;
+ if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
+ if (!vrm.hasPhys(PhysReg))
continue;
- if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
- if (!vrm.hasPhys(PhysReg))
- continue;
- PhysReg = vrm.getPhys(PhysReg);
- }
- if (PhysReg && tri_->regsOverlap(PhysReg, reg))
- return true;
+ PhysReg = vrm.getPhys(PhysReg);
}
+ if (PhysReg && tri_->regsOverlap(PhysReg, reg))
+ return true;
}
}
+ // No conflicts found.
return false;
}
-/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except
-/// it can check use as well.
-bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
- unsigned Reg, bool CheckUse,
+bool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg,
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)) {
- // Skip deleted instructions.
- MachineInstr *MI = 0;
- while (index != end) {
- MI = getInstructionFromIndex(index);
- if (MI)
- break;
- index = getNextIndex(index);
- }
- if (index == end) break;
+ for (SlotIndex index = I->start.getBaseIndex(),
+ end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
+ index != end;
+ index = index.getNextIndex()) {
+ MachineInstr *MI = getInstructionFromIndex(index);
+ if (!MI)
+ continue; // skip deleted instructions
if (JoinedCopies.count(MI))
continue;
MachineOperand& MO = MI->getOperand(i);
if (!MO.isReg())
continue;
- if (MO.isUse() && !CheckUse)
- continue;
unsigned PhysReg = MO.getReg();
- if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg))
+ if (PhysReg == 0 || PhysReg == Reg ||
+ TargetRegisterInfo::isVirtualRegister(PhysReg))
continue;
- if (tri_->isSubRegister(Reg, PhysReg))
+ if (tri_->regsOverlap(Reg, PhysReg))
return true;
}
}
return false;
}
-#ifndef NDEBUG
-static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) {
- if (TargetRegisterInfo::isPhysicalRegister(reg))
- errs() << tri_->getName(reg);
- else
- errs() << "%reg" << reg;
+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;
+}
+
+/// 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.getDefIndex();
+ const LiveRange *OldLR =
+ interval.getLiveRangeContaining(RedefIndex.getUseIndex());
+ MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
+ if (DefMI != 0) {
+ return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
+ }
+ return false;
}
-#endif
void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
MachineBasicBlock::iterator mi,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
unsigned MOIdx,
LiveInterval &interval) {
- DEBUG({
- errs() << "\t\tregister: ";
- printRegName(interval.reg, tri_);
- });
+ DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
// Virtual registers may be defined multiple times (due to phi
// elimination and 2-addr elimination). Much of what we do only has to be
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);
- VNInfo *ValNo;
+ defIndex = MIIdx.getUseIndex();
+
+ // Make sure the first definition is not a partial redefinition. Add an
+ // <imp-def> of the full register.
+ if (MO.getSubReg())
+ mi->addRegisterDefined(interval.reg);
+
MachineInstr *CopyMI = NULL;
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
- mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
- mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
- tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
+ if (mi->isCopyLike()) {
CopyMI = mi;
- // Earlyclobbers move back one.
- ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
+ }
+ VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, 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
// 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.
"Shouldn't be alive across any blocks!");
LiveRange LR(defIndex, killIdx, ValNo);
interval.addRange(LR);
- DEBUG(errs() << " +" << LR << "\n");
- ValNo->addKill(killIdx);
+ DEBUG(dbgs() << " +" << LR << "\n");
return;
}
}
// 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);
- DEBUG(errs() << " +" << NewLR);
+ LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
+ DEBUG(dbgs() << " +" << NewLR);
interval.addRange(NewLR);
- // 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) {
- LiveRange LR(getMBBStartIdx(*I),
- getNextSlot(getMBBEndIdx(*I)), // MBB ends at -1.
- ValNo);
- interval.addRange(LR);
- DEBUG(errs() << " +" << LR);
+ 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];
- LiveIndex killIdx =
- getNextSlot(getUseIndex(getInstructionIndex(Kill)));
- LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo);
+ SlotIndex Start = getMBBStartIdx(Kill->getParent());
+ SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
+
+ // 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, 0, VNInfoAllocator);
+ ValNo->setIsPHIDef(true);
+ }
+ LiveRange LR(Start, killIdx, ValNo);
interval.addRange(LR);
- ValNo->addKill(killIdx);
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
}
} else {
+ if (MultipleDefsBySameMI(*mi, MOIdx))
+ // Multiple defs of the same virtual register by the same instruction.
+ // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
+ // 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.
- if (mi->isRegTiedToUseOperand(MOIdx)) {
+
+ // It may also be partial redef like this:
+ // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
+ // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 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.
- assert(interval.containsOneValue());
- LiveIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
- LiveIndex RedefIndex = getDefIndex(MIIdx);
+ 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;
+ SlotIndex DefIndex = OldValNo->def.getDefIndex();
- // Delete the initial value, which should be short and continuous,
+ // 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);
- // Two-address vregs should always only be redefined once. This means
- // that at this point, there should be exactly one value number in it.
- assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
-
// The new value number (#1) is defined by the instruction we claimed
// defined value #0.
- VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(),
- false, // update at *
- VNInfoAllocator);
- ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
+ VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
// Value#0 is now defined by the 2-addr instruction.
OldValNo->def = RedefIndex;
OldValNo->setCopy(0);
- if (MO.isEarlyClobber())
- OldValNo->setHasRedefByEC(true);
-
+
+ // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
+ if (PartReDef && mi->isCopyLike())
+ OldValNo->setCopy(&*mi);
+
// Add the new live interval which replaces the range for the input copy.
LiveRange LR(DefIndex, RedefIndex, ValNo);
- DEBUG(errs() << " replace range with " << LR);
+ DEBUG(dbgs() << " replace range with " << LR);
interval.addRange(LR);
- ValNo->addKill(RedefIndex);
// 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: ";
- interval.print(errs(), tri_);
+ dbgs() << " RESULT: ";
+ interval.print(dbgs(), tri_);
});
- } else {
- // Otherwise, this must be because of phi elimination. If this is the
- // first redefinition of the vreg that we have seen, go back and change
- // the live range in the PHI block to be a different value number.
- if (interval.containsOneValue()) {
- // Remove the old range that we now know has an incorrect number.
- 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)));
- DEBUG({
- errs() << " Removing [" << Start << "," << End << "] from: ";
- interval.print(errs(), tri_);
- errs() << "\n";
- });
- interval.removeRange(Start, End);
- assert(interval.ranges.size() == 1 &&
- "Newly discovered PHI interval has >1 ranges.");
- MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex());
- VNI->addKill(terminatorGaps[killMBB]);
- VNI->setHasPHIKill(true);
- DEBUG({
- errs() << " RESULT: ";
- interval.print(errs(), tri_);
- });
-
- // 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));
- LR.valno->setIsPHIDef(true);
- DEBUG(errs() << " replace range with " << LR);
- interval.addRange(LR);
- LR.valno->addKill(End);
- DEBUG({
- errs() << " RESULT: ";
- interval.print(errs(), 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.
- LiveIndex defIndex = getDefIndex(MIIdx);
+
+ SlotIndex defIndex = MIIdx.getDefIndex();
if (MO.isEarlyClobber())
- defIndex = getUseIndex(MIIdx);
+ defIndex = MIIdx.getUseIndex();
VNInfo *ValNo;
MachineInstr *CopyMI = NULL;
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
- mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
- mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
- tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
+ if (mi->isCopyLike())
CopyMI = mi;
- ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
-
- LiveIndex killIndex = getNextSlot(getMBBEndIdx(mbb));
+ ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
+
+ SlotIndex killIndex = getMBBEndIdx(mbb);
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
- ValNo->addKill(terminatorGaps[mbb]);
ValNo->setHasPHIKill(true);
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " phi-join +" << LR);
+ } else {
+ llvm_unreachable("Multiply defined register");
}
}
- DEBUG(errs() << '\n');
+ DEBUG(dbgs() << '\n');
}
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
LiveInterval &interval,
MachineInstr *CopyMI) {
// A physical register cannot be live across basic block, so its
// lifetime must end somewhere in its defining basic block.
- DEBUG({
- errs() << "\t\tregister: ";
- printRegName(interval.reg, tri_);
- });
+ DEBUG(dbgs() << "\t\tregister: " << PrintReg(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:
// For earlyclobbers, the defSlot was pushed back one; the extra
// advance below compensates.
if (MO.isDead()) {
- DEBUG(errs() << " dead");
- if (MO.isEarlyClobber())
- end = getNextSlot(getNextSlot(start));
- else
- end = getNextSlot(start);
+ DEBUG(dbgs() << " dead");
+ 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 (mi->isDebugValue())
+ continue;
+ if (getInstructionFromIndex(baseIndex) == 0)
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(errs() << " killed");
- end = getNextSlot(getUseIndex(baseIndex));
+ DEBUG(dbgs() << " killed");
+ end = baseIndex.getDefIndex();
goto exit;
} else {
- int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
+ int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,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();
} 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:
+ // 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);
+ DEBUG(dbgs() << " dead");
+ 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?");
// Already exists? Extend old live interval.
- LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
- bool Extend = OldLR != interval.end();
- VNInfo *ValNo = Extend
- ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
- if (MO.isEarlyClobber() && Extend)
+ VNInfo *ValNo = interval.getVNInfoAt(start);
+ bool Extend = ValNo != 0;
+ if (!Extend)
+ ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
+ if (Extend && MO.isEarlyClobber())
ValNo->setHasRedefByEC(true);
LiveRange LR(start, end, ValNo);
interval.addRange(LR);
- LR.valno->addKill(end);
- DEBUG(errs() << " +" << LR << '\n');
+ DEBUG(dbgs() << " +" << LR << '\n');
}
void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
unsigned MOIdx) {
if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
getOrCreateInterval(MO.getReg()));
else if (allocatableRegs_[MO.getReg()]) {
MachineInstr *CopyMI = NULL;
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
- MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
- MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG ||
- tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
+ if (MI->isCopyLike())
CopyMI = MI;
handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
getOrCreateInterval(MO.getReg()), CopyMI);
for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
// If MI also modifies the sub-register explicitly, avoid processing it
// more than once. Do not pass in TRI here so it checks for exact match.
- if (!MI->modifiesRegister(*AS))
+ if (!MI->definesRegister(*AS))
handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
getOrCreateInterval(*AS), 0);
}
}
void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
LiveInterval &interval, bool isAlias) {
- DEBUG({
- errs() << "\t\tlivein register: ";
- printRegName(interval.reg, tri_);
- });
+ 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();
- LiveIndex baseIndex = MIIdx;
- LiveIndex start = baseIndex;
- while (baseIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(baseIndex) == 0)
- baseIndex = getNextIndex(baseIndex);
- LiveIndex end = baseIndex;
+ MachineBasicBlock::iterator E = MBB->end();
+ // Skip over DBG_VALUE at the start of the MBB.
+ if (mi != E && mi->isDebugValue()) {
+ while (++mi != E && mi->isDebugValue())
+ ;
+ if (mi == E)
+ // MBB is empty except for DBG_VALUE's.
+ return;
+ }
+
+ SlotIndex baseIndex = MIIdx;
+ SlotIndex start = baseIndex;
+ if (getInstructionFromIndex(baseIndex) == 0)
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
+ SlotIndex end = baseIndex;
bool SeenDefUse = false;
-
- while (mi != MBB->end()) {
+
+ while (mi != E) {
if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(errs() << " killed");
- end = getNextSlot(getUseIndex(baseIndex));
+ DEBUG(dbgs() << " killed");
+ end = baseIndex.getDefIndex();
SeenDefUse = true;
break;
- } else if (mi->modifiesRegister(interval.reg, tri_)) {
+ } 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(errs() << " dead");
- end = getNextSlot(getDefIndex(start));
+ DEBUG(dbgs() << " dead");
+ 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);
- }
+ while (++mi != E && mi->isDebugValue())
+ // Skip over DBG_VALUE.
+ ;
+ if (mi != E)
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
}
// Live-in register might not be used at all.
if (!SeenDefUse) {
if (isAlias) {
- DEBUG(errs() << " dead");
- end = getNextSlot(getDefIndex(MIIdx));
+ DEBUG(dbgs() << " dead");
+ end = MIIdx.getStoreIndex();
} else {
- DEBUG(errs() << " live through");
+ DEBUG(dbgs() << " live through");
end = baseIndex;
}
}
+ SlotIndex defIdx = getMBBStartIdx(MBB);
+ assert(getInstructionFromIndex(defIdx) == 0 &&
+ "PHI def index points at actual instruction.");
VNInfo *vni =
- interval.getNextValue(LiveIndex(MBB->getNumber()),
- 0, false, VNInfoAllocator);
+ interval.getNextValue(defIdx, 0, VNInfoAllocator);
vni->setIsPHIDef(true);
LiveRange LR(start, end, vni);
-
- interval.addRange(LR);
- LR.valno->addKill(end);
- DEBUG(errs() << " +" << LR << '\n');
-}
-
-bool
-LiveIntervals::isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
- SmallVector<MachineInstr*,16> &IdentCopies,
- SmallVector<MachineInstr*,16> &OtherCopies) {
- bool HaveConflict = false;
- unsigned NumIdent = 0;
- for (MachineRegisterInfo::def_iterator ri = mri_->def_begin(SrcInt.reg),
- re = mri_->def_end(); ri != re; ++ri) {
- MachineInstr *MI = &*ri;
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
- return false;
- if (SrcReg != DstInt.reg) {
- OtherCopies.push_back(MI);
- HaveConflict |= DstInt.liveAt(getInstructionIndex(MI));
- } else {
- IdentCopies.push_back(MI);
- ++NumIdent;
- }
- }
- if (!HaveConflict)
- return false; // Let coalescer handle it
- return IdentCopies.size() > OtherCopies.size();
-}
-
-void LiveIntervals::performEarlyCoalescing() {
- if (!EarlyCoalescing)
- return;
-
- /// Perform early coalescing: eliminate copies which feed into phi joins
- /// and whose sources are defined by the phi joins.
- for (unsigned i = 0, e = phiJoinCopies.size(); i != e; ++i) {
- MachineInstr *Join = phiJoinCopies[i];
- if (CoalescingLimit != -1 && (int)numCoalescing == CoalescingLimit)
- break;
-
- unsigned PHISrc, PHIDst, SrcSubReg, DstSubReg;
- bool isMove= tii_->isMoveInstr(*Join, PHISrc, PHIDst, SrcSubReg, DstSubReg);
-#ifndef NDEBUG
- assert(isMove && "PHI join instruction must be a move!");
-#else
- isMove = isMove;
-#endif
-
- LiveInterval &DstInt = getInterval(PHIDst);
- LiveInterval &SrcInt = getInterval(PHISrc);
- SmallVector<MachineInstr*, 16> IdentCopies;
- SmallVector<MachineInstr*, 16> OtherCopies;
- if (!isProfitableToCoalesce(DstInt, SrcInt, IdentCopies, OtherCopies))
- continue;
-
- DEBUG(errs() << "PHI Join: " << *Join);
- assert(DstInt.containsOneValue() && "PHI join should have just one val#!");
- VNInfo *VNI = DstInt.getValNumInfo(0);
-
- // Change the non-identity copies to directly target the phi destination.
- for (unsigned i = 0, e = OtherCopies.size(); i != e; ++i) {
- MachineInstr *PHICopy = OtherCopies[i];
- DEBUG(errs() << "Moving: " << *PHICopy);
-
- LiveIndex MIIndex = getInstructionIndex(PHICopy);
- LiveIndex DefIndex = getDefIndex(MIIndex);
- LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- LiveIndex StartIndex = SLR->start;
- LiveIndex 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.
- SrcInt.removeValNo(SLR->valno);
- DEBUG(errs() << " added range [" << StartIndex << ','
- << EndIndex << "] to reg" << DstInt.reg << '\n');
- if (DstInt.liveAt(StartIndex))
- DstInt.removeRange(StartIndex, EndIndex);
- VNInfo *NewVNI = DstInt.getNextValue(DefIndex, PHICopy, true,
- VNInfoAllocator);
- NewVNI->setHasPHIKill(true);
- DstInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI));
- for (unsigned j = 0, ee = PHICopy->getNumOperands(); j != ee; ++j) {
- MachineOperand &MO = PHICopy->getOperand(j);
- if (!MO.isReg() || MO.getReg() != PHISrc)
- continue;
- MO.setReg(PHIDst);
- }
- }
-
- // Now let's eliminate all the would-be identity copies.
- for (unsigned i = 0, e = IdentCopies.size(); i != e; ++i) {
- MachineInstr *PHICopy = IdentCopies[i];
- DEBUG(errs() << "Coalescing: " << *PHICopy);
-
- LiveIndex MIIndex = getInstructionIndex(PHICopy);
- LiveIndex DefIndex = getDefIndex(MIIndex);
- LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- LiveIndex StartIndex = SLR->start;
- LiveIndex 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.
- SrcInt.removeValNo(SLR->valno);
- RemoveMachineInstrFromMaps(PHICopy);
- PHICopy->eraseFromParent();
- DEBUG(errs() << " added range [" << StartIndex << ','
- << EndIndex << "] to reg" << DstInt.reg << '\n');
- DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI));
- }
-
- // Remove the phi join and update the phi block liveness.
- LiveIndex MIIndex = getInstructionIndex(Join);
- LiveIndex UseIndex = getUseIndex(MIIndex);
- LiveIndex DefIndex = getDefIndex(MIIndex);
- LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
- LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
- DLR->valno->setCopy(0);
- DLR->valno->setIsDefAccurate(false);
- DstInt.addRange(LiveRange(SLR->start, SLR->end, DLR->valno));
- SrcInt.removeRange(SLR->start, SLR->end);
- assert(SrcInt.empty());
- removeInterval(PHISrc);
- RemoveMachineInstrFromMaps(Join);
- Join->eraseFromParent();
-
- ++numCoalescing;
- }
+ 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(errs() << "********** COMPUTING LIVE INTERVALS **********\n"
+void LiveIntervals::computeIntervals() {
+ DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
<< "********** Function: "
<< ((Value*)mf_->getFunction())->getName() << '\n');
for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
- // Track the index of the current machine instr.
- LiveIndex MIIndex = getMBBStartIdx(MBB);
- DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
+ if (MBB->empty())
+ continue;
- MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
+ // 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::const_livein_iterator LI = MBB->livein_begin(),
+ for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
LE = MBB->livein_end(); LI != LE; ++LI) {
handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
// Multiple live-ins can alias the same register.
handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
true);
}
-
+
// Skip over empty initial indices.
- while (MIIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(MIIndex) == 0)
- MIIndex = getNextIndex(MIIndex);
-
- for (; MI != miEnd; ++MI) {
- DEBUG(errs() << MIIndex << "\t" << *MI);
+ if (getInstructionFromIndex(MIIndex) == 0)
+ MIIndex = indexes_->getNextNonNullIndex(MIIndex);
+
+ for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
+ MI != miEnd; ++MI) {
+ DEBUG(dbgs() << MIIndex << "\t" << *MI);
+ if (MI->isDebugValue())
+ continue;
// Handle defs.
for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
UndefUses.push_back(MO.getReg());
}
- // Skip over the empty slots after each instruction.
- unsigned Slots = MI->getDesc().getNumDefs();
- if (Slots == 0)
- Slots = 1;
-
- while (Slots--)
- MIIndex = getNextIndex(MIIndex);
-
- // Skip over empty indices.
- while (MIIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(MIIndex) == 0)
- MIIndex = getNextIndex(MIIndex);
+ // Move to the next instr slot.
+ MIIndex = indexes_->getNextNonNullIndex(MIIndex);
}
}
}
}
-bool LiveIntervals::findLiveInMBBs(
- LiveIndex Start, MachineInstrIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
-
- bool ResVal = false;
- while (I != Idx2MBBMap.end()) {
- if (I->first >= End)
- break;
- MBBs.push_back(I->second);
- ResVal = true;
- ++I;
- }
- return ResVal;
-}
-
-bool LiveIntervals::findReachableMBBs(
- LiveIndex Start, MachineInstrIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
-
- bool ResVal = false;
- while (I != Idx2MBBMap.end()) {
- if (I->first > End)
- break;
- MachineBasicBlock *MBB = I->second;
- if (getMBBEndIdx(MBB) > End)
- break;
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI)
- MBBs.push_back(*SI);
- ResVal = true;
- ++I;
- }
- return ResVal;
-}
-
LiveInterval* LiveIntervals::createInterval(unsigned reg) {
float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
return new LiveInterval(reg, Weight);
return NewLI;
}
-/// getVNInfoSourceReg - Helper function that parses the specified VNInfo
-/// copy field and returns the source register that defines it.
-unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
- if (!VNI->getCopy())
- return 0;
-
- if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
- // If it's extracting out of a physical register, return the sub-register.
- unsigned Reg = VNI->getCopy()->getOperand(1).getReg();
- if (TargetRegisterInfo::isPhysicalRegister(Reg))
- Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm());
- return Reg;
- } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
- VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
- return VNI->getCopy()->getOperand(2).getReg();
-
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg))
- return SrcReg;
- llvm_unreachable("Unrecognized copy instruction!");
- return 0;
-}
-
//===----------------------------------------------------------------------===//
// Register allocator hooks.
//
+MachineBasicBlock::iterator
+LiveIntervals::getLastSplitPoint(const LiveInterval &li,
+ MachineBasicBlock *mbb) {
+ const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
+
+ // If li is not live into a landing pad, we can insert spill code before the
+ // first terminator.
+ if (!lpad || !isLiveInToMBB(li, lpad))
+ return mbb->getFirstTerminator();
+
+ // When there is a landing pad, spill code must go before the call instruction
+ // that can throw.
+ MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
+ while (I != B) {
+ --I;
+ if (I->getDesc().isCall())
+ return I;
+ }
+ assert(0 && "Block with landing pad successor contains no call instruction");
+ return mbb->getFirstTerminator();
+}
+
/// 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 Reg = MO.getReg();
if (Reg == 0 || Reg == li.reg)
continue;
-
+
if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
!allocatableRegs_[Reg])
continue;
/// 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,
- LiveIndex UseIdx) const {
- LiveIndex Index = getInstructionIndex(MI);
- VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
- LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
- return UI != li.end() && UI->valno == ValNo;
+ 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,
- SmallVectorImpl<LiveInterval*> &SpillIs,
- bool &isLoad) {
+bool
+LiveIntervals::isReMaterializable(const LiveInterval &li,
+ const VNInfo *ValNo, MachineInstr *MI,
+ const SmallVectorImpl<LiveInterval*> &SpillIs,
+ bool &isLoad) {
if (DisableReMat)
return false;
- if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
- return true;
-
- int FrameIdx = 0;
- if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
- mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
- // FIXME: Let target specific isReallyTriviallyReMaterializable determines
- // this but remember this is not safe to fold into a two-address
- // instruction.
- // This is a load from fixed stack slot. It can be rematerialized.
- return true;
-
- // If the target-specific rules don't identify an instruction as
- // being trivially rematerializable, use some target-independent
- // rules.
- if (!MI->getDesc().isRematerializable() ||
- !tii_->isTriviallyReMaterializable(MI)) {
- if (!EnableAggressiveRemat)
- return false;
-
- // If the instruction accesses memory but the memoperands have been lost,
- // we can't analyze it.
- const TargetInstrDesc &TID = MI->getDesc();
- if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty())
- return false;
-
- // Avoid instructions obviously unsafe for remat.
- if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable())
- return false;
-
- // If the instruction accesses memory and the memory could be non-constant,
- // assume the instruction is not rematerializable.
- for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
- E = MI->memoperands_end(); I != E; ++I){
- const MachineMemOperand *MMO = *I;
- if (MMO->isVolatile() || MMO->isStore())
- return false;
- const Value *V = MMO->getValue();
- if (!V)
- return false;
- if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
- if (!PSV->isConstant(mf_->getFrameInfo()))
- return false;
- } else if (!aa_->pointsToConstantMemory(V))
- return false;
- }
-
- // If any of the registers accessed are non-constant, conservatively assume
- // the instruction is not rematerializable.
- unsigned ImpUse = 0;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = MI->getOperand(i);
- if (MO.isReg()) {
- unsigned Reg = MO.getReg();
- if (Reg == 0)
- continue;
- if (TargetRegisterInfo::isPhysicalRegister(Reg))
- return false;
-
- // Only allow one def, and that in the first operand.
- if (MO.isDef() != (i == 0))
- return false;
-
- // Only allow constant-valued registers.
- bool IsLiveIn = mri_->isLiveIn(Reg);
- MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg),
- E = mri_->def_end();
-
- // For the def, it should be the only def of that register.
- if (MO.isDef() && (next(I) != E || IsLiveIn))
- return false;
-
- if (MO.isUse()) {
- // Only allow one use other register use, as that's all the
- // remat mechanisms support currently.
- if (Reg != li.reg) {
- if (ImpUse == 0)
- ImpUse = Reg;
- else if (Reg != ImpUse)
- return false;
- }
- // For the use, there should be only one associated def.
- if (I != E && (next(I) != E || IsLiveIn))
- 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_iterator ri = mri_->use_begin(li.reg),
- re = mri_->use_end(); ri != re; ++ri) {
+ for (MachineRegisterInfo::use_nodbg_iterator
+ ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
+ ri != re; ++ri) {
MachineInstr *UseMI = &*ri;
- LiveIndex UseIdx = getInstructionIndex(UseMI);
- if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
+ SlotIndex UseIdx = getInstructionIndex(UseMI);
+ if (li.getVNInfoAt(UseIdx) != ValNo)
continue;
if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
return false;
/// isReMaterializable - Returns true if every definition of MI of every
/// val# of the specified interval is re-materializable.
-bool LiveIntervals::isReMaterializable(const LiveInterval &li,
- SmallVectorImpl<LiveInterval*> &SpillIs,
- bool &isLoad) {
+bool
+LiveIntervals::isReMaterializable(const LiveInterval &li,
+ const SmallVectorImpl<LiveInterval*> &SpillIs,
+ bool &isLoad) {
isLoad = false;
for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
i != e; ++i) {
if (VNI->isUnused())
continue; // Dead val#.
// Is the def for the val# rematerializable?
- if (!VNI->isDefAccurate())
- return false;
MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
+ if (!ReMatDefMI)
+ return false;
bool DefIsLoad = false;
if (!ReMatDefMI ||
!isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
}
return false;
}
-
+
/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
/// slot / to reg or any rematerialized load into ith operand of specified
/// returns true.
bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
VirtRegMap &vrm, MachineInstr *DefMI,
- LiveIndex InstrIdx,
+ SlotIndex InstrIdx,
SmallVector<unsigned, 2> &Ops,
bool isSS, int Slot, unsigned Reg) {
// If it is an implicit def instruction, just delete it.
- if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ if (MI->isImplicitDef()) {
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
if (DefMI && (MRInfo & VirtRegMap::isMod))
return false;
- MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
- : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
+ MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
+ : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
if (fmi) {
// Remember this instruction uses the spill slot.
if (isSS) vrm.addSpillSlotUse(Slot, fmi);
// Attempt to fold the memory reference into the instruction. If
// we can do this, we don't need to insert spill code.
- MachineBasicBlock &MBB = *MI->getParent();
if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
vrm.transferSpillPts(MI, fmi);
vrm.transferRestorePts(MI, fmi);
vrm.transferEmergencySpills(MI, fmi);
- mi2iMap_.erase(MI);
- i2miMap_[InstrIdx.getVecIndex()] = fmi;
- mi2iMap_[fmi] = InstrIdx;
- MI = MBB.insert(MBB.erase(MI), fmi);
+ ReplaceMachineInstrInMaps(MI, fmi);
+ MI->eraseFromParent();
+ MI = fmi;
++numFolds;
return true;
}
}
bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
- SmallPtrSet<MachineBasicBlock*, 4> MBBs;
- for (LiveInterval::Ranges::const_iterator
- I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
- std::vector<IdxMBBPair>::const_iterator II =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
- if (II == Idx2MBBMap.end())
- continue;
- if (I->end > II->first) // crossing a MBB.
- return false;
- MBBs.insert(II->second);
- if (MBBs.size() > 1)
+ LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
+
+ MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+ if (mbb == 0)
+ return false;
+
+ for (++itr; itr != li.ranges.end(); ++itr) {
+ MachineBasicBlock *mbb2 =
+ indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+ if (mbb2 != mbb)
return false;
}
+
return true;
}
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
- if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
+ if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
if (!vrm.isReMaterialized(Reg))
continue;
/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
bool LiveIntervals::
rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
- bool TrySplit, LiveIndex index, MachineInstrIndex end,
+ bool TrySplit, SlotIndex index, SlotIndex end,
MachineInstr *MI,
MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
unsigned Slot, int LdSlot,
if (!mop.isReg())
continue;
unsigned Reg = mop.getReg();
- unsigned RegI = Reg;
- if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
+ if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
if (Reg != li.reg)
continue;
// If this is the rematerializable definition MI itself and
// all of its uses are rematerialized, simply delete it.
if (MI == ReMatOrigDefMI && CanDelete) {
- DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: "
- << MI << '\n');
+ DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
+ << *MI << '\n');
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
// keep the src/dst regs pinned.
//
// Keep track of whether we replace a use and/or def so that we can
- // create the spill interval with the appropriate range.
-
- HasUse = mop.isUse();
- HasDef = mop.isDef();
+ // create the spill interval with the appropriate range.
SmallVector<unsigned, 2> Ops;
- Ops.push_back(i);
- for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
- const MachineOperand &MOj = MI->getOperand(j);
- if (!MOj.isReg())
- continue;
- unsigned RegJ = MOj.getReg();
- if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
- continue;
- if (RegJ == RegI) {
- Ops.push_back(j);
- if (!MOj.isUndef()) {
- HasUse |= MOj.isUse();
- HasDef |= MOj.isDef();
- }
- }
- }
+ tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
// Create a new virtual register for the spill interval.
// Create the new register now so we can map the fold instruction
NewVReg = mri_->createVirtualRegister(rc);
vrm.grow();
CreatedNewVReg = true;
+
+ // The new virtual register should get the same allocation hints as the
+ // old one.
+ std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
+ if (Hint.first || Hint.second)
+ mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
}
if (!TryFold)
rewriteImplicitOps(li, MI, NewVReg, vrm);
// Reuse NewVReg for other reads.
+ bool HasEarlyClobber = false;
for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
MachineOperand &mopj = MI->getOperand(Ops[j]);
mopj.setReg(NewVReg);
if (mopj.isImplicit())
rewriteImplicitOps(li, MI, NewVReg, vrm);
+ if (mopj.isEarlyClobber())
+ HasEarlyClobber = true;
}
-
+
if (CreatedNewVReg) {
if (DefIsReMat) {
vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
if (HasUse) {
if (CreatedNewVReg) {
- LiveRange LR(getLoadIndex(index), getNextSlot(getUseIndex(index)),
- nI.getNextValue(LiveIndex(), 0, false,
- VNInfoAllocator));
- DEBUG(errs() << " +" << LR);
+ LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
+ nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
} else {
// Extend the split live interval to this def / use.
- LiveIndex End = getNextSlot(getUseIndex(index));
+ SlotIndex End = index.getDefIndex();
LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
nI.getValNumInfo(nI.getNumValNums()-1));
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
}
}
if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
- VNInfoAllocator));
- DEBUG(errs() << " +" << LR);
+ // An early clobber starts at the use slot, except for an early clobber
+ // tied to a use operand (yes, that is a thing).
+ LiveRange LR(HasEarlyClobber && !HasUse ?
+ index.getUseIndex() : index.getDefIndex(),
+ index.getStoreIndex(),
+ nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
}
DEBUG({
- errs() << "\t\t\t\tAdded new interval: ";
- nI.print(errs(), tri_);
- errs() << '\n';
+ dbgs() << "\t\t\t\tAdded new interval: ";
+ nI.print(dbgs(), tri_);
+ dbgs() << '\n';
});
}
return CanFold;
bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
const VNInfo *VNI,
MachineBasicBlock *MBB,
- LiveIndex Idx) const {
- LiveIndex End = getMBBEndIdx(MBB);
- for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
- if (VNI->kills[j].isPHIIndex())
- continue;
-
- LiveIndex KillIdx = VNI->kills[j];
- if (KillIdx > Idx && KillIdx < End)
- return true;
- }
- return false;
+ SlotIndex Idx) const {
+ return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
}
/// RewriteInfo - Keep track of machine instrs that will be rewritten
/// during spilling.
namespace {
struct RewriteInfo {
- LiveIndex Index;
+ SlotIndex Index;
MachineInstr *MI;
- bool HasUse;
- bool HasDef;
- RewriteInfo(LiveIndex i, MachineInstr *mi, bool u, bool d)
- : Index(i), MI(mi), HasUse(u), HasDef(d) {}
+ RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
};
struct RewriteInfoCompare {
std::vector<LiveInterval*> &NewLIs) {
bool AllCanFold = true;
unsigned NewVReg = 0;
- LiveIndex start = getBaseIndex(I->start);
- LiveIndex end = getNextIndex(getBaseIndex(getPrevSlot(I->end)));
+ SlotIndex start = I->start.getBaseIndex();
+ SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
// First collect all the def / use in this live range that will be rewritten.
// Make sure they are sorted according to instruction index.
MachineInstr *MI = &*ri;
MachineOperand &O = ri.getOperand();
++ri;
- assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
- LiveIndex index = getInstructionIndex(MI);
+ if (MI->isDebugValue()) {
+ // Modify DBG_VALUE now that the value is in a spill slot.
+ if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
+ uint64_t Offset = MI->getOperand(1).getImm();
+ const MDNode *MDPtr = MI->getOperand(2).getMetadata();
+ DebugLoc DL = MI->getDebugLoc();
+ int FI = isLoadSS ? LdSlot : (int)Slot;
+ if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
+ Offset, MDPtr, DL)) {
+ DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
+ ReplaceMachineInstrInMaps(MI, NewDV);
+ MachineBasicBlock *MBB = MI->getParent();
+ MBB->insert(MBB->erase(MI), NewDV);
+ continue;
+ }
+ }
+
+ DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
+ RemoveMachineInstrFromMaps(MI);
+ vrm.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ continue;
+ }
+ assert(!(O.isImplicit() && O.isUse()) &&
+ "Spilling register that's used as implicit use?");
+ SlotIndex index = getInstructionIndex(MI);
if (index < start || index >= end)
continue;
// easily see a situation where both registers are reloaded before
// the INSERT_SUBREG and both target registers that would overlap.
continue;
- RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
+ RewriteMIs.push_back(RewriteInfo(index, MI));
}
std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
RewriteInfo &rwi = RewriteMIs[i];
++i;
- LiveIndex index = rwi.Index;
- bool MIHasUse = rwi.HasUse;
- bool MIHasDef = rwi.HasDef;
+ SlotIndex index = rwi.Index;
MachineInstr *MI = rwi.MI;
// If MI def and/or use the same register multiple times, then there
// are multiple entries.
- unsigned NumUses = MIHasUse;
while (i != e && RewriteMIs[i].MI == MI) {
assert(RewriteMIs[i].Index == index);
- bool isUse = RewriteMIs[i].HasUse;
- if (isUse) ++NumUses;
- MIHasUse |= isUse;
- MIHasDef |= RewriteMIs[i].HasDef;
++i;
}
MachineBasicBlock *MBB = MI->getParent();
if (ImpUse && MI != ReMatDefMI) {
- // Re-matting an instruction with virtual register use. Update the
- // register interval's spill weight to HUGE_VALF to prevent it from
- // being spilled.
- LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight = HUGE_VALF;
+ // Re-matting an instruction with virtual register use. Prevent interval
+ // from being spilled.
+ getInterval(ImpUse).markNotSpillable();
}
unsigned MBBId = MBB->getNumber();
// = use
// It's better to start a new interval to avoid artifically
// extend the new interval.
- if (MIHasDef && !MIHasUse) {
+ if (MI->readsWritesVirtualRegister(li.reg) ==
+ std::make_pair(false,true)) {
MBBVRegsMap.erase(MBB->getNumber());
ThisVReg = 0;
}
LiveInterval &nI = getOrCreateInterval(NewVReg);
if (!TrySplit) {
// The spill weight is now infinity as it cannot be spilled again.
- nI.weight = HUGE_VALF;
+ nI.markNotSpillable();
continue;
}
if (MI != ReMatOrigDefMI || !CanDelete) {
bool HasKill = false;
if (!HasUse)
- HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
+ HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
else {
// If this is a two-address code, then this index starts a new VNInfo.
- const VNInfo *VNI = li.findDefinedVNInfoForRegInt(getDefIndex(index));
+ const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
if (VNI)
- HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
+ HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
}
DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
SpillIdxes.find(MBBId);
}
}
-bool LiveIntervals::alsoFoldARestore(int Id, LiveIndex index,
+bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
unsigned vr, BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
if (!RestoreMBBs[Id])
return false;
}
-void LiveIntervals::eraseRestoreInfo(int Id, LiveIndex index,
+void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
unsigned vr, BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
if (!RestoreMBBs[Id])
std::vector<SRInfo> &Restores = RestoreIdxes[Id];
for (unsigned i = 0, e = Restores.size(); i != e; ++i)
if (Restores[i].index == index && Restores[i].vreg)
- Restores[i].index = LiveIndex();
+ Restores[i].index = SlotIndex();
}
/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
MachineOperand &O = ri.getOperand();
MachineInstr *MI = &*ri;
++ri;
+ if (MI->isDebugValue()) {
+ // Remove debug info for now.
+ O.setReg(0U);
+ DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
+ continue;
+ }
if (O.isDef()) {
- assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
+ assert(MI->isImplicitDef() &&
"Register def was not rewritten?");
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
}
}
-std::vector<LiveInterval*> LiveIntervals::
-addIntervalsForSpillsFast(const LiveInterval &li,
- const MachineLoopInfo *loopInfo,
- VirtRegMap &vrm) {
- unsigned slot = vrm.assignVirt2StackSlot(li.reg);
-
- std::vector<LiveInterval*> added;
+float
+LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
+ // Limit the loop depth ridiculousness.
+ if (loopDepth > 200)
+ loopDepth = 200;
- assert(li.weight != HUGE_VALF &&
- "attempt to spill already spilled interval!");
-
- DEBUG({
- errs() << "\t\t\t\tadding intervals for spills for interval: ";
- li.dump();
- errs() << '\n';
- });
-
- const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
+ // The loop depth is used to roughly estimate the number of times the
+ // instruction is executed. Something like 10^d is simple, but will quickly
+ // overflow a float. This expression behaves like 10^d for small d, but is
+ // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
+ // headroom before overflow.
+ float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth);
- MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg);
- while (RI != mri_->reg_end()) {
- MachineInstr* MI = &*RI;
-
- SmallVector<unsigned, 2> Indices;
- bool HasUse = false;
- bool HasDef = false;
-
- for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
- MachineOperand& mop = MI->getOperand(i);
- if (!mop.isReg() || mop.getReg() != li.reg) continue;
-
- HasUse |= MI->getOperand(i).isUse();
- HasDef |= MI->getOperand(i).isDef();
-
- Indices.push_back(i);
- }
-
- if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI),
- Indices, true, slot, li.reg)) {
- unsigned NewVReg = mri_->createVirtualRegister(rc);
- vrm.grow();
- vrm.assignVirt2StackSlot(NewVReg, slot);
-
- // create a new register for this spill
- LiveInterval &nI = getOrCreateInterval(NewVReg);
-
- // the spill weight is now infinity as it
- // cannot be spilled again
- nI.weight = HUGE_VALF;
-
- // Rewrite register operands to use the new vreg.
- for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
- E = Indices.end(); I != E; ++I) {
- MI->getOperand(*I).setReg(NewVReg);
-
- if (MI->getOperand(*I).isUse())
- MI->getOperand(*I).setIsKill(true);
- }
-
- // Fill in the new live interval.
- LiveIndex index = getInstructionIndex(MI);
- if (HasUse) {
- LiveRange LR(getLoadIndex(index), getUseIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
- getVNInfoAllocator()));
- DEBUG(errs() << " +" << LR);
- nI.addRange(LR);
- vrm.addRestorePoint(NewVReg, MI);
- }
- if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
- getVNInfoAllocator()));
- DEBUG(errs() << " +" << LR);
- nI.addRange(LR);
- vrm.addSpillPoint(NewVReg, true, MI);
- }
-
- added.push_back(&nI);
-
- DEBUG({
- errs() << "\t\t\t\tadded new interval: ";
- nI.dump();
- errs() << '\n';
- });
- }
-
-
- RI = mri_->reg_begin(li.reg);
- }
+ return (isDef + isUse) * lc;
+}
- return added;
+void
+LiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
+ for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
+ normalizeSpillWeight(*NewLIs[i]);
}
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li,
- SmallVectorImpl<LiveInterval*> &SpillIs,
+ const SmallVectorImpl<LiveInterval*> &SpillIs,
const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
-
- if (EnableFastSpilling)
- return addIntervalsForSpillsFast(li, loopInfo, vrm);
-
- assert(li.weight != HUGE_VALF &&
- "attempt to spill already spilled interval!");
+ assert(li.isSpillable() && "attempt to spill already spilled interval!");
DEBUG({
- errs() << "\t\t\t\tadding intervals for spills for interval: ";
- li.print(errs(), tri_);
- errs() << '\n';
+ dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
+ li.print(dbgs(), tri_);
+ dbgs() << '\n';
});
// Each bit specify whether a spill is required in the MBB.
if (vrm.getPreSplitReg(li.reg)) {
vrm.setIsSplitFromReg(li.reg, 0);
// Unset the split kill marker on the last use.
- LiveIndex KillIdx = vrm.getKillPoint(li.reg);
- if (KillIdx != LiveIndex()) {
+ SlotIndex KillIdx = vrm.getKillPoint(li.reg);
+ if (KillIdx != SlotIndex()) {
MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
assert(KillMI && "Last use disappeared?");
int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
}
handleSpilledImpDefs(li, vrm, rc, NewLIs);
+ normalizeSpillWeights(NewLIs);
return NewLIs;
}
if (VNI->isUnused())
continue; // Dead val#.
// Is the def for the val# rematerializable?
- MachineInstr *ReMatDefMI = VNI->isDefAccurate()
- ? getInstructionFromIndex(VNI->def) : 0;
+ MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
bool dummy;
if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
// Remember how to remat the def of this val#.
if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
Slot = vrm.assignVirt2StackSlot(li.reg);
-
+
// This case only occurs when the prealloc splitter has already assigned
// a stack slot to this vreg.
else
// Insert spills / restores if we are splitting.
if (!TrySplit) {
handleSpilledImpDefs(li, vrm, rc, NewLIs);
+ normalizeSpillWeights(NewLIs);
return NewLIs;
}
while (Id != -1) {
std::vector<SRInfo> &spills = SpillIdxes[Id];
for (unsigned i = 0, e = spills.size(); i != e; ++i) {
- LiveIndex index = spills[i].index;
+ SlotIndex index = spills[i].index;
unsigned VReg = spills[i].vreg;
LiveInterval &nI = getOrCreateInterval(VReg);
bool isReMat = vrm.isReMaterialized(VReg);
Ops.push_back(j);
if (MO.isDef())
continue;
- if (isReMat ||
+ if (isReMat ||
(!FoundUse && !alsoFoldARestore(Id, index, VReg,
RestoreMBBs, RestoreIdxes))) {
// MI has two-address uses of the same register. If the use
if (FoundUse) {
// Also folded uses, do not issue a load.
eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
- nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+ nI.removeRange(index.getLoadIndex(), index.getDefIndex());
}
- nI.removeRange(getDefIndex(index), getStoreIndex(index));
+ nI.removeRange(index.getDefIndex(), index.getStoreIndex());
}
}
// Otherwise tell the spiller to issue a spill.
if (!Folded) {
LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
- bool isKill = LR->end == getStoreIndex(index);
+ bool isKill = LR->end == index.getStoreIndex();
if (!MI->registerDefIsDead(nI.reg))
// No need to spill a dead def.
vrm.addSpillPoint(VReg, isKill, MI);
while (Id != -1) {
std::vector<SRInfo> &restores = RestoreIdxes[Id];
for (unsigned i = 0, e = restores.size(); i != e; ++i) {
- LiveIndex index = restores[i].index;
- if (index == LiveIndex())
+ SlotIndex index = restores[i].index;
+ if (index == SlotIndex())
continue;
unsigned VReg = restores[i].vreg;
LiveInterval &nI = getOrCreateInterval(VReg);
unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
if (ImpUse) {
// Re-matting an instruction with virtual register use. Add the
- // register as an implicit use on the use MI and update the register
- // interval's spill weight to HUGE_VALF to prevent it from being
- // spilled.
+ // register as an implicit use on the use MI and mark the register
+ // interval as unspillable.
LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight = HUGE_VALF;
+ ImpLi.markNotSpillable();
MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
}
}
// If folding is not possible / failed, then tell the spiller to issue a
// load / rematerialization for us.
if (Folded)
- nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+ nI.removeRange(index.getLoadIndex(), index.getDefIndex());
else
vrm.addRestorePoint(VReg, MI);
}
for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
LiveInterval *LI = NewLIs[i];
if (!LI->empty()) {
- LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
if (!AddedKill.count(LI)) {
LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
- LiveIndex LastUseIdx = getBaseIndex(LR->end);
+ SlotIndex LastUseIdx = LR->end.getBaseIndex();
MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
assert(UseIdx != -1);
}
handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
+ normalizeSpillWeights(RetNewLIs);
return RetNewLIs;
}
/// getRepresentativeReg - Find the largest super register of the specified
/// physical register.
unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
- // Find the largest super-register that is allocatable.
+ // Find the largest super-register that is allocatable.
unsigned BestReg = Reg;
for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
unsigned SuperReg = *AS;
E = mri_->reg_end(); I != E; ++I) {
MachineOperand &O = I.getOperand();
MachineInstr *MI = O.getParent();
- LiveIndex Index = getInstructionIndex(MI);
+ if (MI->isDebugValue())
+ continue;
+ SlotIndex Index = getInstructionIndex(MI);
if (pli.liveAt(Index))
++NumConflicts;
}
unsigned PhysReg, VirtRegMap &vrm) {
unsigned SpillReg = getRepresentativeReg(PhysReg);
+ DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
+ << " represented by " << tri_->getName(SpillReg) << '\n');
+
for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
// If there are registers which alias PhysReg, but which are not a
// sub-register of the chosen representative super register. Assert
tri_->isSuperRegister(*AS, SpillReg));
bool Cut = false;
- LiveInterval &pli = getInterval(SpillReg);
+ SmallVector<unsigned, 4> PRegs;
+ if (hasInterval(SpillReg))
+ PRegs.push_back(SpillReg);
+ for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
+ if (hasInterval(*SR))
+ PRegs.push_back(*SR);
+
+ DEBUG({
+ dbgs() << "Trying to spill:";
+ for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
+ dbgs() << ' ' << tri_->getName(PRegs[i]);
+ dbgs() << '\n';
+ });
+
SmallPtrSet<MachineInstr*, 8> SeenMIs;
for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
E = mri_->reg_end(); I != E; ++I) {
MachineOperand &O = I.getOperand();
MachineInstr *MI = O.getParent();
- if (SeenMIs.count(MI))
+ if (MI->isDebugValue() || SeenMIs.count(MI))
continue;
SeenMIs.insert(MI);
- LiveIndex Index = getInstructionIndex(MI);
- if (pli.liveAt(Index)) {
- vrm.addEmergencySpill(SpillReg, MI);
- LiveIndex StartIdx = getLoadIndex(Index);
- LiveIndex EndIdx = getNextSlot(getStoreIndex(Index));
- if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
- pli.removeRange(StartIdx, EndIdx);
- Cut = true;
- } else {
+ SlotIndex Index = getInstructionIndex(MI);
+ bool LiveReg = false;
+ for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
+ unsigned PReg = PRegs[i];
+ LiveInterval &pli = getInterval(PReg);
+ if (!pli.liveAt(Index))
+ continue;
+ LiveReg = true;
+ SlotIndex StartIdx = Index.getLoadIndex();
+ SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
+ if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
std::string msg;
raw_string_ostream Msg(msg);
Msg << "Ran out of registers during register allocation!";
- if (MI->getOpcode() == TargetInstrInfo::INLINEASM) {
+ if (MI->isInlineAsm()) {
Msg << "\nPlease check your inline asm statement for invalid "
- << "constraints:\n";
+ << "constraints:\n";
MI->print(Msg, tm_);
}
- llvm_report_error(Msg.str());
- }
- for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
- if (!hasInterval(*AS))
- continue;
- LiveInterval &spli = getInterval(*AS);
- if (spli.liveAt(Index))
- spli.removeRange(getLoadIndex(Index), getNextSlot(getStoreIndex(Index)));
+ report_fatal_error(Msg.str());
}
+ pli.removeRange(StartIdx, EndIdx);
+ LiveReg = true;
}
+ if (!LiveReg)
+ continue;
+ DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
+ vrm.addEmergencySpill(SpillReg, MI);
+ Cut = true;
}
return Cut;
}
MachineInstr* startInst) {
LiveInterval& Interval = getOrCreateInterval(reg);
VNInfo* VN = Interval.getNextValue(
- LiveIndex(getInstructionIndex(startInst), MachineInstrIndex::DEF),
- startInst, true, getVNInfoAllocator());
+ SlotIndex(getInstructionIndex(startInst).getDefIndex()),
+ startInst, getVNInfoAllocator());
VN->setHasPHIKill(true);
- VN->kills.push_back(terminatorGaps[startInst->getParent()]);
LiveRange LR(
- LiveIndex(getInstructionIndex(startInst), MachineInstrIndex::DEF),
- getNextSlot(getMBBEndIdx(startInst->getParent())), VN);
+ SlotIndex(getInstructionIndex(startInst).getDefIndex()),
+ getMBBEndIdx(startInst->getParent()), VN);
Interval.addRange(LR);
-
+
return LR;
}
projects / oota-llvm.git / blobdiff