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");
delete I->second;
r2iMap_.clear();
- phiJoinCopies.clear();
// Release VNInfo memroy regions after all VNInfo objects are dtor'd.
VNInfoAllocator.Reset();
allocatableRegs_ = tri_->getAllocatableSet(fn);
computeIntervals();
- performEarlyCoalescing();
numIntervals += getNumIntervals();
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
mbbi != mbbe; ++mbbi) {
- OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
+ OS << "BB#" << mbbi->getNumber()
+ << ":\t\t# derived from " << mbbi->getName() << "\n";
for (MachineBasicBlock::iterator mii = mbbi->begin(),
mie = mbbi->end(); mii != mie; ++mii) {
- OS << getInstructionIndex(mii) << '\t' << *mii;
+ if (mii->isDebugValue())
+ OS << " \t" << *mii;
+ else
+ OS << getInstructionIndex(mii) << '\t' << *mii;
}
}
}
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 (SlotIndex index = I->start.getBaseIndex(),
- end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
- index != end;
- index = index.getNextIndex()) {
- // skip deleted instructions
- while (index != end && !getInstructionFromIndex(index))
- index = index.getNextIndex();
- 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
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (tii_->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
+ if (SrcReg == li.reg || DstReg == 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,
+/// conflictsWithSubPhysRegRef - Similar to conflictsWithPhysRegRef except
+/// it checks for sub-register reference and it can check use as well.
+bool LiveIntervals::conflictsWithSubPhysRegRef(LiveInterval &li,
unsigned Reg, bool CheckUse,
SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
for (LiveInterval::Ranges::const_iterator
end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
index != end;
index = index.getNextIndex()) {
- // Skip deleted instructions.
- MachineInstr *MI = 0;
- while (index != end) {
- MI = getInstructionFromIndex(index);
- if (MI)
- break;
- index = index.getNextIndex();
- }
- if (index == end) break;
+ MachineInstr *MI = getInstructionFromIndex(index);
+ if (!MI)
+ continue; // skip deleted instructions
if (JoinedCopies.count(MI))
continue;
#ifndef NDEBUG
static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) {
if (TargetRegisterInfo::isPhysicalRegister(reg))
- errs() << tri_->getName(reg);
+ dbgs() << tri_->getName(reg);
else
- errs() << "%reg" << reg;
+ dbgs() << "%reg" << reg;
}
#endif
unsigned MOIdx,
LiveInterval &interval) {
DEBUG({
- errs() << "\t\tregister: ";
+ dbgs() << "\t\tregister: ";
printRegName(interval.reg, tri_);
});
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 ||
+ if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg() ||
tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
CopyMI = mi;
// Earlyclobbers move back one.
"Shouldn't be alive across any blocks!");
LiveRange LR(defIndex, killIdx, ValNo);
interval.addRange(LR);
- DEBUG(errs() << " +" << LR << "\n");
+ DEBUG(dbgs() << " +" << LR << "\n");
ValNo->addKill(killIdx);
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, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(),
- 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(mf_->getBlockNumbered(*I)),
- getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(),
- 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->addKill(indexes_->getTerminatorGap(mbb));
+ ValNo->setHasPHIKill(true);
+ } else {
+ // Iterate over all of the blocks that the variable is completely
+ // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
+ // live interval.
+ for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
+ E = vi.AliveBlocks.end(); I != E; ++I) {
+ MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
+ LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
+ interval.addRange(LR);
+ DEBUG(dbgs() << " +" << LR);
+ }
}
// Finally, this virtual register is live from the start of any killing
// block to the 'use' slot of the killing instruction.
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
- SlotIndex killIdx =
- getInstructionIndex(Kill).getDefIndex();
- 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) {
+ ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false,
+ VNInfoAllocator);
+ ValNo->setIsPHIDef(true);
+ }
+ LiveRange LR(Start, killIdx, ValNo);
interval.addRange(LR);
ValNo->addKill(killIdx);
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
}
} else {
// Value#0 is now defined by the 2-addr instruction.
OldValNo->def = RedefIndex;
OldValNo->setCopy(0);
- if (MO.isEarlyClobber())
- OldValNo->setHasRedefByEC(true);
// 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);
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);
- SlotIndex Start = getMBBStartIdx(Killer->getParent());
- SlotIndex End = getInstructionIndex(Killer).getDefIndex();
- 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(indexes_->getTerminatorGap(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(SlotIndex(getMBBStartIdx(mbb), true),
- 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_);
- });
- }
-
+ assert(lv_->isPHIJoin(interval.reg) && "Multiply defined register");
// In the case of PHI elimination, each variable definition is only
// live until the end of the block. We've already taken care of the
// rest of the live range.
+
SlotIndex defIndex = MIIdx.getDefIndex();
if (MO.isEarlyClobber())
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 ||
+ if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg()||
tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
- SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex();
+ SlotIndex killIndex = getMBBEndIdx(mbb);
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
ValNo->addKill(indexes_->getTerminatorGap(mbb));
ValNo->setHasPHIKill(true);
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " phi-join +" << LR);
}
}
- DEBUG(errs() << '\n');
+ DEBUG(dbgs() << '\n');
}
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
// A physical register cannot be live across basic block, so its
// lifetime must end somewhere in its defining basic block.
DEBUG({
- errs() << "\t\tregister: ";
+ dbgs() << "\t\tregister: ";
printRegName(interval.reg, tri_);
});
// For earlyclobbers, the defSlot was pushed back one; the extra
// advance below compensates.
if (MO.isDead()) {
- DEBUG(errs() << " dead");
+ DEBUG(dbgs() << " dead");
end = start.getStoreIndex();
goto exit;
}
baseIndex = baseIndex.getNextIndex();
while (++mi != MBB->end()) {
+ if (mi->isDebugValue())
+ continue;
if (getInstructionFromIndex(baseIndex) == 0)
baseIndex = indexes_->getNextNonNullIndex(baseIndex);
if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(errs() << " killed");
+ DEBUG(dbgs() << " killed");
end = baseIndex.getDefIndex();
goto exit;
} else {
if (mi->isRegTiedToUseOperand(DefIdx)) {
// Two-address instruction.
end = baseIndex.getDefIndex();
- assert(!mi->getOperand(DefIdx).isEarlyClobber() &&
- "Two address instruction is an early clobber?");
} else {
// Another instruction redefines the register before it is ever read.
- // Then the register is essentially dead at the instruction that defines
- // it. Hence its interval is:
+ // Then the register is essentially dead at the instruction that
+ // defines it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
- DEBUG(errs() << " dead");
+ DEBUG(dbgs() << " dead");
end = start.getStoreIndex();
}
goto exit;
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,
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 ||
+ if (MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg() ||
tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
CopyMI = MI;
handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
SlotIndex MIIdx,
LiveInterval &interval, bool isAlias) {
DEBUG({
- errs() << "\t\tlivein register: ";
+ dbgs() << "\t\tlivein register: ";
printRegName(interval.reg, tri_);
});
// Look for kills, if it reaches a def before it's killed, then it shouldn't
// be considered a livein.
MachineBasicBlock::iterator mi = MBB->begin();
+ MachineBasicBlock::iterator E = MBB->end();
+ // Skip over DBG_VALUE at the start of the MBB.
+ if (mi != E && mi->isDebugValue()) {
+ while (++mi != E && mi->isDebugValue())
+ ;
+ if (mi == E)
+ // MBB is empty except for DBG_VALUE's.
+ return;
+ }
+
SlotIndex baseIndex = MIIdx;
SlotIndex start = baseIndex;
if (getInstructionFromIndex(baseIndex) == 0)
SlotIndex end = baseIndex;
bool SeenDefUse = false;
-
- while (mi != MBB->end()) {
+
+ while (mi != E) {
if (mi->killsRegister(interval.reg, tri_)) {
- DEBUG(errs() << " killed");
+ DEBUG(dbgs() << " killed");
end = baseIndex.getDefIndex();
SeenDefUse = true;
break;
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
- DEBUG(errs() << " dead");
+ DEBUG(dbgs() << " dead");
end = start.getStoreIndex();
SeenDefUse = true;
break;
}
- ++mi;
- if (mi != MBB->end()) {
+ 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");
+ DEBUG(dbgs() << " dead");
end = MIIdx.getStoreIndex();
} else {
- DEBUG(errs() << " live through");
+ DEBUG(dbgs() << " live through");
end = baseIndex;
}
}
0, false, 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);
-
- SlotIndex MIIndex = getInstructionIndex(PHICopy);
- SlotIndex DefIndex = MIIndex.getDefIndex();
- LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- SlotIndex StartIndex = SLR->start;
- SlotIndex EndIndex = SLR->end;
-
- // Delete val# defined by the now identity copy and add the range from
- // beginning of the mbb to the end of the range.
- 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);
-
- SlotIndex MIIndex = getInstructionIndex(PHICopy);
- SlotIndex DefIndex = MIIndex.getDefIndex();
- LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- SlotIndex StartIndex = SLR->start;
- SlotIndex EndIndex = SLR->end;
-
- // Delete val# defined by the now identity copy and add the range from
- // beginning of the mbb to the end of the range.
- 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.
- SlotIndex MIIndex = getInstructionIndex(Join);
- SlotIndex UseIndex = MIIndex.getUseIndex();
- SlotIndex DefIndex = MIIndex.getDefIndex();
- LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
- LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
- DLR->valno->setCopy(0);
- 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;
- }
+ DEBUG(dbgs() << " +" << LR << '\n');
}
/// computeIntervals - computes the live intervals for virtual
/// 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"
+ 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;
+ if (MBB->empty())
+ continue;
+
// Track the index of the current machine instr.
SlotIndex MIIndex = getMBBStartIdx(MBB);
- DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
-
- MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
+ DEBUG(dbgs() << MBB->getName() << ":\n");
// Create intervals for live-ins to this BB first.
for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
if (getInstructionFromIndex(MIIndex) == 0)
MIIndex = indexes_->getNextNonNullIndex(MIIndex);
- for (; MI != miEnd; ++MI) {
- DEBUG(errs() << MIIndex << "\t" << *MI);
+ 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) {
if (!VNI->getCopy())
return 0;
- if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
+ if (VNI->getCopy()->isExtractSubreg()) {
// If it's extracting out of a physical register, return the sub-register.
unsigned Reg = VNI->getCopy()->getOperand(1).getReg();
- if (TargetRegisterInfo::isPhysicalRegister(Reg))
+ if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+ unsigned SrcSubReg = VNI->getCopy()->getOperand(2).getImm();
+ unsigned DstSubReg = VNI->getCopy()->getOperand(0).getSubReg();
+ if (SrcSubReg == DstSubReg)
+ // %reg1034:3<def> = EXTRACT_SUBREG %EDX, 3
+ // reg1034 can still be coalesced to EDX.
+ return Reg;
+ assert(DstSubReg == 0);
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)
+ } else if (VNI->getCopy()->isInsertSubreg() ||
+ VNI->getCopy()->isSubregToReg())
return VNI->getCopy()->getOperand(2).getReg();
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
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;
SlotIndex UseIdx = getInstructionIndex(UseMI);
if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
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 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();
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)
if (CreatedNewVReg) {
LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
} else {
// Extend the split live interval to this def / use.
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(index.getDefIndex(), index.getStoreIndex(),
nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
- DEBUG(errs() << " +" << LR);
+ 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;
continue;
SlotIndex KillIdx = VNI->kills[j];
- if (KillIdx > Idx && KillIdx < End)
+ if (KillIdx > Idx && KillIdx <= End)
return true;
}
return false;
MachineInstr *MI = &*ri;
MachineOperand &O = ri.getOperand();
++ri;
+ if (MI->isDebugValue()) {
+ // Remove debug info for now.
+ O.setReg(0U);
+ DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
+ continue;
+ }
assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
SlotIndex index = getInstructionIndex(MI);
if (index < start || index >= end)
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();
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;
}
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);
}
}
+float
+LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
+ // Limit the loop depth ridiculousness.
+ if (loopDepth > 200)
+ loopDepth = 200;
+
+ // 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 = powf(1 + (100.0f / (loopDepth+10)), (float)loopDepth);
+
+ return (isDef + isUse) * lc;
+}
+
+void
+LiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
+ for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
+ normalizeSpillWeight(*NewLIs[i]);
+}
+
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpillsFast(const LiveInterval &li,
const MachineLoopInfo *loopInfo,
std::vector<LiveInterval*> added;
- 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: ";
+ dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
li.dump();
- errs() << '\n';
+ dbgs() << '\n';
});
const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
// 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;
+ nI.markNotSpillable();
// Rewrite register operands to use the new vreg.
for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(),
LiveRange LR(index.getLoadIndex(), index.getUseIndex(),
nI.getNextValue(SlotIndex(), 0, false,
getVNInfoAllocator()));
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
vrm.addRestorePoint(NewVReg, MI);
}
LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
nI.getNextValue(SlotIndex(), 0, false,
getVNInfoAllocator()));
- DEBUG(errs() << " +" << LR);
+ DEBUG(dbgs() << " +" << LR);
nI.addRange(LR);
vrm.addSpillPoint(NewVReg, true, MI);
}
added.push_back(&nI);
DEBUG({
- errs() << "\t\t\t\tadded new interval: ";
+ dbgs() << "\t\t\t\tadded new interval: ";
nI.dump();
- errs() << '\n';
+ dbgs() << '\n';
});
}
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.
}
handleSpilledImpDefs(li, vrm, rc, NewLIs);
+ normalizeSpillWeights(NewLIs);
return NewLIs;
}
// Insert spills / restores if we are splitting.
if (!TrySplit) {
handleSpilledImpDefs(li, vrm, rc, NewLIs);
+ normalizeSpillWeights(NewLIs);
return NewLIs;
}
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));
}
}
}
handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
+ normalizeSpillWeights(RetNewLIs);
return RetNewLIs;
}
E = mri_->reg_end(); I != E; ++I) {
MachineOperand &O = I.getOperand();
MachineInstr *MI = O.getParent();
+ if (MI->isDebugValue())
+ continue;
SlotIndex Index = getInstructionIndex(MI);
if (pli.liveAt(Index))
++NumConflicts;
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);
SlotIndex Index = getInstructionIndex(MI);
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";
MI->print(Msg, tm_);
VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent()));
LiveRange LR(
SlotIndex(getInstructionIndex(startInst).getDefIndex()),
- getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN);
+ getMBBEndIdx(startInst->getParent()), VN);
Interval.addRange(LR);
return LR;
projects / oota-llvm.git / blobdiff