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;
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;
-
MachineInstr *MI = getInstructionFromIndex(index);
+ if (!MI)
+ continue; // skip deleted instructions
+
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
if (SrcReg == li.reg || DstReg == li.reg)
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;
// 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);
// 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({
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
DEBUG(errs() << " +" << LR << '\n');
}
-bool LiveIntervals::
-isSafeAndProfitableToCoalesce(LiveInterval &DstInt,
- LiveInterval &SrcInt,
- SmallVector<MachineInstr*,16> &IdentCopies,
- SmallVector<MachineInstr*,16> &OtherCopies) {
- 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) {
- // Non-identity copy - we cannot handle overlapping intervals
- if (DstInt.liveAt(getInstructionIndex(MI)))
- return false;
- OtherCopies.push_back(MI);
- } else {
- IdentCopies.push_back(MI);
- ++NumIdent;
- }
- }
-
- 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 (!isSafeAndProfitableToCoalesce(DstInt, SrcInt,
- IdentCopies, OtherCopies))
- continue;
-
- DEBUG(errs() << "PHI Join: " << *Join);
- assert(DstInt.containsOneValue() && "PHI join should have just one val#!");
- assert(std::distance(mri_->use_begin(PHISrc), mri_->use_end()) == 1 &&
- "PHI join src should not be used elsewhere");
- 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];
- SlotIndex MIIndex = getInstructionIndex(PHICopy);
- DEBUG(errs() << "Moving: " << MIIndex << ' ' << *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');
- assert (!DstInt.liveAt(StartIndex) && "Cannot coalesce when dst live!");
- 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;
- }
-}
-
/// 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
MachineBasicBlock *MBB = MBBI;
// Track the index of the current machine instr.
SlotIndex MIIndex = getMBBStartIdx(MBB);
- DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
+ DEBUG(errs() << MBB->getName() << ":\n");
MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
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)
projects / oota-llvm.git / blobdiff