#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) {
+
+ // 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 offset = LI->start % InstrSlots::NUM;
+ if (OldI2MI[LI->start / InstrSlots::NUM])
+ LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[LI->start / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ MachineInstr* preceding = i2miMap_[(mi2iMap_[newInstr] -
+ InstrSlots::NUM) / InstrSlots::NUM];
+ if (preceding->getParent() == newInstr->getParent() &&
+ preceding->modifiesRegister(I->second.reg))
+ LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
+ else
+ LI->start = mi2iMap_[newInstr];
+ }
+
+ // 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.
+ if (LI->end / InstrSlots::NUM < OldI2MI.size()) {
+ offset = LI->end % InstrSlots::NUM;
+ if (OldI2MI[LI->end / InstrSlots::NUM])
+ LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[LI->end / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ LI->end = mi2iMap_[newInstr];
+ }
+ } else {
+ LI->end = i2miMap_.size() * InstrSlots::NUM;
+ }
+
+ // Remap the VNInfo def index, which works the same as the
+ // start indices above.
+ VNInfo* vni = LI->valno;
+ offset = vni->def % InstrSlots::NUM;
+ if (OldI2MI[vni->def / InstrSlots::NUM])
+ vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset;
+ else {
+ unsigned i = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[vni->def / InstrSlots::NUM + i];
+ i++;
+ } while (!newInstr);
+
+ MachineInstr* preceding = i2miMap_[(mi2iMap_[newInstr] -
+ InstrSlots::NUM) / InstrSlots::NUM];
+ if (preceding->getParent() == newInstr->getParent() &&
+ preceding->modifiesRegister(I->second.reg))
+ vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
+ else
+ vni->def = mi2iMap_[newInstr];
+ }
+
+ // Remap the VNInfo kill indices, which works the same as
+ // the end indices above.
+ for (size_t i = 0; i < vni->kills.size(); ++i) {
+ offset = vni->kills[i] % InstrSlots::NUM;
+ if (OldI2MI[vni->kills[i] / InstrSlots::NUM])
+ vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] +
+ offset;
+ else {
+ unsigned e = 0;
+ MachineInstr* newInstr = 0;
+ do {
+ newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e];
+ e++;
+ } while (!newInstr);
+
+ vni->kills[i] = mi2iMap_[newInstr];
+ }
+ }
+ }
+}
+/// 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();
/// 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,
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);
}
projects / oota-llvm.git / blobdiff