#include <cmath>
using namespace llvm;
-namespace {
- // Hidden options for help debugging.
- cl::opt<bool> DisableReMat("disable-rematerialization",
- cl::init(false), cl::Hidden);
-
- cl::opt<bool> SplitAtBB("split-intervals-at-bb",
- cl::init(true), cl::Hidden);
- cl::opt<int> SplitLimit("split-limit",
- cl::init(-1), cl::Hidden);
-}
+// Hidden options for help debugging.
+static cl::opt<bool> DisableReMat("disable-rematerialization",
+ cl::init(false), cl::Hidden);
+
+static cl::opt<bool> SplitAtBB("split-intervals-at-bb",
+ cl::init(true), cl::Hidden);
+static cl::opt<int> SplitLimit("split-limit",
+ cl::init(-1), cl::Hidden);
STATISTIC(numIntervals, "Number of original intervals");
STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
STATISTIC(numSplits , "Number of intervals split");
char LiveIntervals::ID = 0;
-namespace {
- RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
-}
+static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<LiveVariables>();
delete ClonedMIs[i];
}
-/// runOnMachineFunction - Register allocate the whole function
-///
-bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
- mf_ = &fn;
- mri_ = &mf_->getRegInfo();
- tm_ = &fn.getTarget();
- tri_ = tm_->getRegisterInfo();
- tii_ = tm_->getInstrInfo();
- lv_ = &getAnalysis<LiveVariables>();
- allocatableRegs_ = tri_->getAllocatableSet(fn);
-
+void LiveIntervals::computeNumbering() {
+ Index2MiMap OldI2MI = i2miMap_;
+
+ Idx2MBBMap.clear();
+ MBB2IdxMap.clear();
+ mi2iMap_.clear();
+ i2miMap_.clear();
+
// Number MachineInstrs and MachineBasicBlocks.
// Initialize MBB indexes to a sentinal.
MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
}
// Set the MBB2IdxMap entry for this MBB.
- MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
+ MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex)
+ ? std::make_pair(StartIdx, StartIdx) // Empty MBB
+ : std::make_pair(StartIdx, MIIndex - 1);
Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
}
std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
+
+ if (!OldI2MI.empty())
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end();
+ LI != LE; ++LI) {
+ LI->start = mi2iMap_[OldI2MI[LI->start]];
+ LI->end = mi2iMap_[OldI2MI[LI->end]];
+
+ VNInfo* vni = LI->valno;
+ vni->def = mi2iMap_[OldI2MI[vni->def]];
+
+ for (size_t i = 0; i < vni->kills.size(); ++i)
+ vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i]]];
+ }
+}
+/// runOnMachineFunction - Register allocate the whole function
+///
+bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
+ mf_ = &fn;
+ mri_ = &mf_->getRegInfo();
+ tm_ = &fn.getTarget();
+ tri_ = tm_->getRegisterInfo();
+ tii_ = tm_->getInstrInfo();
+ lv_ = &getAnalysis<LiveVariables>();
+ allocatableRegs_ = tri_->getAllocatableSet(fn);
+
+ computeNumbering();
computeIntervals();
numIntervals += getNumIntervals();
DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
+ if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ DOUT << "is a implicit_def\n";
+ return;
+ }
+
// Virtual registers may be defined multiple times (due to phi
// elimination and 2-addr elimination). Much of what we do only has to be
// done once for the vreg. We use an empty interval to detect the first
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*MI, SrcReg, DstReg))
CopyMI = MI;
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
return VNI->copy->getOperand(1).getReg();
+ if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+ return VNI->copy->getOperand(2).getReg();
unsigned SrcReg, DstReg;
if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
return SrcReg;
if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
return false;
- // Can't fold a load from fixed stack slot into a two address instruction.
- if (isSS && DefMI && (MRInfo & VirtRegMap::isMod))
+ // The only time it's safe to fold into a two address instruction is when
+ // it's folding reload and spill from / into a spill stack slot.
+ if (DefMI && (MRInfo & VirtRegMap::isMod))
return false;
MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
/// folding is possible.
bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
SmallVector<unsigned, 2> &Ops,
- bool ReMatLoad) const {
+ bool ReMat) const {
// Filter the list of operand indexes that are to be folded. Abort if
// any operand will prevent folding.
unsigned MRInfo = 0;
if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
return false;
- // Can't fold a remat'ed load into a two address instruction.
- if (ReMatLoad && (MRInfo & VirtRegMap::isMod))
+ // It's only legal to remat for a use, not a def.
+ if (ReMat && (MRInfo & VirtRegMap::isMod))
return false;
return tii_->canFoldMemoryOperand(MI, FoldOps);
if (MI == ReMatOrigDefMI && CanDelete) {
DOUT << "\t\t\t\tErasing re-materlizable def: ";
DOUT << MI << '\n';
- unsigned ImpUse = getReMatImplicitUse(li, MI);
- if (ImpUse) {
- // To be deleted MI has a virtual register operand, update the
- // spill weight of the register interval.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
- LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight -=
- getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
- }
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
HasUse = false;
HasDef = false;
CanFold = false;
+ if (isRemoved(MI))
+ break;
goto RestartInstruction;
}
} else {
- CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat && isLoad);
+ CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
}
} else
CanFold = false;
/// RewriteInfo - Keep track of machine instrs that will be rewritten
/// during spilling.
-struct RewriteInfo {
- unsigned Index;
- MachineInstr *MI;
- bool HasUse;
- bool HasDef;
- RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
- : Index(i), MI(mi), HasUse(u), HasDef(d) {}
-};
-
-struct RewriteInfoCompare {
- bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
- return LHS.Index < RHS.Index;
- }
-};
+namespace {
+ struct RewriteInfo {
+ unsigned Index;
+ MachineInstr *MI;
+ bool HasUse;
+ bool HasDef;
+ RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
+ : Index(i), MI(mi), HasUse(u), HasDef(d) {}
+ };
+
+ struct RewriteInfoCompare {
+ bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
+ return LHS.Index < RHS.Index;
+ }
+ };
+}
void LiveIntervals::
rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
// First collect all the def / use in this live range that will be rewritten.
- // Make sure they are sorted according instruction index.
+ // Make sure they are sorted according to instruction index.
std::vector<RewriteInfo> RewriteMIs;
for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
re = mri_->reg_end(); ri != re; ) {
- MachineInstr *MI = &(*ri);
+ MachineInstr *MI = &*ri;
MachineOperand &O = ri.getOperand();
++ri;
+ assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
unsigned index = getInstructionIndex(MI);
if (index < start || index >= end)
continue;
if (ImpUse && MI != ReMatDefMI) {
// Re-matting an instruction with virtual register use. Update the
- // register interval's spill weight.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
+ // register interval's spill weight to HUGE_VALF to prevent it from
+ // being spilled.
LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight +=
- getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize();
+ ImpLi.weight = HUGE_VALF;
}
unsigned MBBId = MBB->getNumber();
Restores[i].index = -1;
}
+/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
+/// spilled and create empty intervals for their uses.
+void
+LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
+ const TargetRegisterClass* rc,
+ std::vector<LiveInterval*> &NewLIs) {
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
+ re = mri_->reg_end(); ri != re; ) {
+ MachineOperand &O = ri.getOperand();
+ MachineInstr *MI = &*ri;
+ ++ri;
+ if (O.isDef()) {
+ assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
+ "Register def was not rewritten?");
+ RemoveMachineInstrFromMaps(MI);
+ vrm.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ } else {
+ // This must be an use of an implicit_def so it's not part of the live
+ // interval. Create a new empty live interval for it.
+ // FIXME: Can we simply erase some of the instructions? e.g. Stores?
+ unsigned NewVReg = mri_->createVirtualRegister(rc);
+ vrm.grow();
+ vrm.setIsImplicitlyDefined(NewVReg);
+ NewLIs.push_back(&getOrCreateInterval(NewVReg));
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (MO.isReg() && MO.getReg() == li.reg)
+ MO.setReg(NewVReg);
+ }
+ }
+ }
+}
+
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li,
}
IsFirstRange = false;
}
+
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
}
}
// Insert spills / restores if we are splitting.
- if (!TrySplit)
+ if (!TrySplit) {
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
+ }
SmallPtrSet<LiveInterval*, 4> AddedKill;
SmallVector<unsigned, 2> Ops;
}
}
- // Else tell the spiller to issue a spill.
+ // Otherwise tell the spiller to issue a spill.
if (!Folded) {
LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
bool isKill = LR->end == getStoreIndex(index);
- vrm.addSpillPoint(VReg, isKill, MI);
+ if (!MI->registerDefIsDead(nI.reg))
+ // No need to spill a dead def.
+ vrm.addSpillPoint(VReg, isKill, MI);
if (isKill)
AddedKill.insert(&nI);
}
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.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
+ // interval's spill weight to HUGE_VALF to prevent it from being
+ // spilled.
LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight +=
- getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
-
+ ImpLi.weight = HUGE_VALF;
MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
}
}
}
}
+ handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
return RetNewLIs;
}
projects / oota-llvm.git / blobdiff