//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "simpleregistercoalescing"
+#define DEBUG_TYPE "regcoalescing"
#include "llvm/CodeGen/SimpleRegisterCoalescing.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "VirtRegMap.h"
namespace {
static cl::opt<bool>
EnableJoining("join-liveintervals",
- cl::desc("Coallesce copies (default=true)"),
+ cl::desc("Coalesce copies (default=true)"),
cl::init(true));
RegisterPass<SimpleRegisterCoalescing>
- X("simple-register-coalescing",
- "Simple register coalescing to eliminate all possible register copies");
+ X("simple-register-coalescing", "Simple Register Coalescing");
}
const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo();
MachineFunctionPass::getAnalysisUsage(AU);
}
-/// AdjustCopiesBackFrom - We found a non-trivially-coallescable copy with IntA
+/// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
/// being the source and IntB being the dest, thus this defines a value number
/// in IntB. If the source value number (in IntA) is defined by a copy from B,
/// see if we can merge these two pieces of B into a single value number,
// Get the location that B is defined at. Two options: either this value has
// an unknown definition point or it is defined at CopyIdx. If unknown, we
// can't process it.
- unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo);
- if (BValNoDefIdx == ~0U) return false;
+ unsigned BValNoDefIdx = IntB.getDefForValNum(BValNo);
+ if (!IntB.getSrcRegForValNum(BValNo)) return false;
assert(BValNoDefIdx == CopyIdx &&
"Copy doesn't define the value?");
if (rep(SrcReg) != IntB.reg) return false;
// Get the LiveRange in IntB that this value number starts with.
- unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo);
+ unsigned AValNoInstIdx = IntA.getDefForValNum(AValNo);
LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1);
// Make sure that the end of the live range is inside the same block as
DOUT << "\nExtending: "; IntB.print(DOUT, mri_);
+ unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
// We are about to delete CopyMI, so need to remove it as the 'instruction
- // that defines this value #'.
- IntB.setValueNumberInfo(BValNo, std::make_pair(~0U, 0));
+ // that defines this value #'. Update the the valnum with the new defining
+ // instruction #.
+ IntB.setDefForValNum(BValNo, FillerStart);
+ IntB.setSrcRegForValNum(BValNo, 0);
// Okay, we can merge them. We need to insert a new liverange:
// [ValLR.end, BLR.begin) of either value number, then we merge the
// two value numbers.
- unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
// If the IntB live range is assigned to a physical register, and if that
for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) {
LiveInterval &AliasLI = li_->getInterval(*AS);
AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
- AliasLI.getNextValue(~0U, 0)));
+ AliasLI.getNextValue(FillerStart, 0)));
}
}
/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
/// which are the src/dst of the copy instruction CopyMI. This returns true
-/// if the copy was successfully coallesced away, or if it is never possible
-/// to coallesce this copy, due to register constraints. It returns
-/// false if it is not currently possible to coallesce this interval, but
-/// it may be possible if other things get coallesced.
+/// if the copy was successfully coalesced away, or if it is never possible
+/// to coalesce this copy, due to register constraints. It returns
+/// false if it is not currently possible to coalesce this interval, but
+/// it may be possible if other things get coalesced.
bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
unsigned SrcReg, unsigned DstReg, bool PhysOnly) {
DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
// If they are already joined we continue.
if (repSrcReg == repDstReg) {
- DOUT << "\tCopy already coallesced.\n";
- return true; // Not coallescable.
+ DOUT << "\tCopy already coalesced.\n";
+ return true; // Not coalescable.
}
bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg);
// If they are both physical registers, we cannot join them.
if (SrcIsPhys && DstIsPhys) {
- DOUT << "\tCan not coallesce physregs.\n";
- return true; // Not coallescable.
+ DOUT << "\tCan not coalesce physregs.\n";
+ return true; // Not coalescable.
}
// We only join virtual registers with allocatable physical registers.
if (SrcIsPhys && !allocatableRegs_[repSrcReg]) {
DOUT << "\tSrc reg is unallocatable physreg.\n";
- return true; // Not coallescable.
+ return true; // Not coalescable.
}
if (DstIsPhys && !allocatableRegs_[repDstReg]) {
DOUT << "\tDst reg is unallocatable physreg.\n";
- return true; // Not coallescable.
+ return true; // Not coalescable.
}
// If they are not of the same register class, we cannot join them.
if (differingRegisterClasses(repSrcReg, repDstReg)) {
DOUT << "\tSrc/Dest are different register classes.\n";
- return true; // Not coallescable.
+ return true; // Not coalescable.
}
LiveInterval &SrcInt = li_->getInterval(repSrcReg);
}
if (isShorten || isDead) {
- // Shorten the live interval.
- LiveInterval &LiveInInt = (repSrcReg == DstInt.reg) ? DstInt : SrcInt;
- LiveInInt.removeRange(RemoveStart, RemoveEnd);
+ // Shorten the destination live interval.
+ if (repSrcReg == DstInt.reg)
+ DstInt.removeRange(RemoveStart, RemoveEnd);
}
} else {
- // Coallescing failed.
+ // Coalescing failed.
// If we can eliminate the copy without merging the live ranges, do so now.
if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI))
// If the intervals were swapped by Join, swap them back so that the register
// mapping (in the r2i map) is correct.
if (Swapped) SrcInt.swap(DstInt);
+
+ // repSrcReg is guarateed to be the register whose live interval that is
+ // being merged.
li_->removeInterval(repSrcReg);
r2rMap_[repSrcReg] = repDstReg;
/// contains the value number the copy is from.
///
static unsigned ComputeUltimateVN(unsigned VN,
- SmallVector<std::pair<unsigned,
- unsigned>, 16> &ValueNumberInfo,
+ SmallVector<LiveInterval::VNInfo, 16> &ValueNumberInfo,
SmallVector<int, 16> &ThisFromOther,
SmallVector<int, 16> &OtherFromThis,
SmallVector<int, 16> &ThisValNoAssignments,
// interval may be defined as copies from the RHS. Scan the overlapping
// portions of the LHS and RHS, keeping track of this and looking for
// overlapping live ranges that are NOT defined as copies. If these exist, we
- // cannot coallesce.
+ // cannot coalesce.
LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end();
LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end();
// If the live intervals overlap, there are two interesting cases: if the
// LHS interval is defined by a copy from the RHS, it's ok and we record
// that the LHS value # is the same as the RHS. If it's not, then we cannot
- // coallesce these live ranges and we bail out.
+ // coalesce these live ranges and we bail out.
if (Overlaps) {
// If we haven't already recorded that this value # is safe, check it.
if (!InVector(LHSIt->ValId, EliminatedLHSVals)) {
// One interesting case to check here. It's possible that we have
// something like "X3 = Y" which defines a new value number in the LHS,
// and is the last use of this liverange of the RHS. In this case, we
- // want to notice this copy (so that it gets coallesced away) even though
+ // want to notice this copy (so that it gets coalesced away) even though
// the live ranges don't actually overlap.
if (LHSIt->start == RHSIt->end) {
if (InVector(LHSIt->ValId, EliminatedLHSVals)) {
// We already know that this value number is going to be merged in
- // if coallescing succeeds. Just skip the liverange.
+ // if coalescing succeeds. Just skip the liverange.
if (++LHSIt == LHSEnd) break;
} else {
// Otherwise, if this is a copy from the RHS, mark it as being merged
}
}
- // If we got here, we know that the coallescing will be successful and that
+ // If we got here, we know that the coalescing will be successful and that
// the value numbers in EliminatedLHSVals will all be merged together. Since
// the most common case is that EliminatedLHSVals has a single number, we
// optimize for it: if there is more than one value, we merge them all into
// Okay, now that there is a single LHS value number that we're merging the
// RHS into, update the value number info for the LHS to indicate that the
// value number is defined where the RHS value number was.
- LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0));
+ const LiveInterval::VNInfo VNI = RHS.getValNumInfo(0);
+ LHS.setDefForValNum(LHSValNo, VNI.def);
+ LHS.setSrcRegForValNum(LHSValNo, VNI.reg);
// Okay, the final step is to loop over the RHS live intervals, adding them to
// the LHS.
LHS.MergeRangesInAsValue(RHS, LHSValNo);
+ LHS.addKillsForValNum(LHSValNo, VNI.kills);
LHS.weight += RHS.weight;
if (RHS.preference && !LHS.preference)
LHS.preference = RHS.preference;
/// below to update aliases.
bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) {
// Compute the final value assignment, assuming that the live ranges can be
- // coallesced.
+ // coalesced.
SmallVector<int, 16> LHSValNoAssignments;
SmallVector<int, 16> RHSValNoAssignments;
- SmallVector<std::pair<unsigned,unsigned>, 16> ValueNumberInfo;
+ SmallVector<int, 16> LHSValsDefinedFromRHS;
+ SmallVector<int, 16> RHSValsDefinedFromLHS;
+ SmallVector<LiveInterval::VNInfo, 16> ValueNumberInfo;
// If a live interval is a physical register, conservatively check if any
// of its sub-registers is overlapping the live interval of the virtual
// often RHS is small and LHS is large (e.g. a physreg).
// Find out if the RHS is defined as a copy from some value in the LHS.
+ int RHSVal0DefinedFromLHS = -1;
int RHSValID = -1;
- std::pair<unsigned,unsigned> RHSValNoInfo;
+ LiveInterval::VNInfo RHSValNoInfo;
unsigned RHSSrcReg = RHS.getSrcRegForValNum(0);
if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) {
// If RHS is not defined as a copy from the LHS, we can use simpler and
- // faster checks to see if the live ranges are coallescable. This joiner
+ // faster checks to see if the live ranges are coalescable. This joiner
// can't swap the LHS/RHS intervals though.
if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) {
return SimpleJoin(LHS, RHS);
}
} else {
// It was defined as a copy from the LHS, find out what value # it is.
- unsigned ValInst = RHS.getInstForValNum(0);
+ unsigned ValInst = RHS.getDefForValNum(0);
RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId;
RHSValNoInfo = LHS.getValNumInfo(RHSValID);
+ RHSVal0DefinedFromLHS = RHSValID;
}
LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) {
if (rep(LHSSrcReg) != RHS.reg) {
// If this is not a copy from the RHS, its value number will be
- // unmodified by the coallescing.
+ // unmodified by the coalescing.
ValueNumberInfo[VN] = LHS.getValNumInfo(VN);
LHSValNoAssignments[VN] = VN;
} else if (RHSValID == -1) {
// value# for it. Keep the current value number, but remember it.
LHSValNoAssignments[VN] = RHSValID = VN;
ValueNumberInfo[VN] = RHSValNoInfo;
+ RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN));
} else {
// Otherwise, use the specified value #.
LHSValNoAssignments[VN] = RHSValID;
if (VN != (unsigned)RHSValID)
- ValueNumberInfo[VN].first = ~1U;
- else
+ ValueNumberInfo[VN].def = ~1U; // Now this val# is dead.
+ else {
ValueNumberInfo[VN] = RHSValNoInfo;
+ RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN));
+ }
}
} else {
ValueNumberInfo[VN] = LHS.getValNumInfo(VN);
assert(RHSValID != -1 && "Didn't find value #?");
RHSValNoAssignments[0] = RHSValID;
-
+ if (RHSVal0DefinedFromLHS != -1) {
+ int LHSValId = LHSValNoAssignments[RHSVal0DefinedFromLHS];
+ LHS.addKills(ValueNumberInfo[LHSValId], RHS.getKillsForValNum(0));
+ }
} else {
// Loop over the value numbers of the LHS, seeing if any are defined from
// the RHS.
- SmallVector<int, 16> LHSValsDefinedFromRHS;
LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1);
for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
unsigned ValSrcReg = LHS.getSrcRegForValNum(VN);
continue;
// Figure out the value # from the RHS.
- unsigned ValInst = LHS.getInstForValNum(VN);
+ unsigned ValInst = LHS.getDefForValNum(VN);
LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId;
}
// Loop over the value numbers of the RHS, seeing if any are defined from
// the LHS.
- SmallVector<int, 16> RHSValsDefinedFromLHS;
RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1);
for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
unsigned ValSrcReg = RHS.getSrcRegForValNum(VN);
continue;
// Figure out the value # from the LHS.
- unsigned ValInst = RHS.getInstForValNum(VN);
+ unsigned ValInst = RHS.getDefForValNum(VN);
RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId;
}
ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
- if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~2U)
+ if (LHSValNoAssignments[VN] >= 0 || LHS.getDefForValNum(VN) == ~1U)
continue;
ComputeUltimateVN(VN, ValueNumberInfo,
LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
LHSValNoAssignments, RHSValNoAssignments, LHS, RHS);
}
for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
- if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~2U)
+ if (RHSValNoAssignments[VN] >= 0 || RHS.getDefForValNum(VN) == ~1U)
continue;
// If this value number isn't a copy from the LHS, it's a new number.
if (RHSValsDefinedFromLHS[VN] == -1) {
}
// Armed with the mappings of LHS/RHS values to ultimate values, walk the
- // interval lists to see if these intervals are coallescable.
+ // interval lists to see if these intervals are coalescable.
LiveInterval::const_iterator I = LHS.begin();
LiveInterval::const_iterator IE = LHS.end();
LiveInterval::const_iterator J = RHS.begin();
// If so, check value # info to determine if they are really different.
if (Overlaps) {
// If the live range overlap will map to the same value number in the
- // result liverange, we can still coallesce them. If not, we can't.
+ // result liverange, we can still coalesce them. If not, we can't.
if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId])
return false;
}
}
}
- // If we get here, we know that we can coallesce the live ranges. Ask the
- // intervals to coallesce themselves now.
+ // Update kill info. Some live ranges are extended due to copy coalescing.
+ for (unsigned i = 0, e = RHSValsDefinedFromLHS.size(); i != e; ++i) {
+ int LHSValId = RHSValsDefinedFromLHS[i];
+ if (LHSValId == -1)
+ continue;
+ unsigned RHSValId = RHSValNoAssignments[i];
+ LHS.addKills(ValueNumberInfo[RHSValId], RHS.getKillsForValNum(i));
+ }
+ for (unsigned i = 0, e = LHSValsDefinedFromRHS.size(); i != e; ++i) {
+ int RHSValId = LHSValsDefinedFromRHS[i];
+ if (RHSValId == -1)
+ continue;
+ unsigned LHSValId = LHSValNoAssignments[i];
+ RHS.addKills(ValueNumberInfo[LHSValId], LHS.getKillsForValNum(i));
+ }
+
+ // If we get here, we know that we can coalesce the live ranges. Ask the
+ // intervals to coalesce themselves now.
LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
ValueNumberInfo);
return true;
};
}
-void SimpleRegisterCoalescing::CopyCoallesceInMBB(MachineBasicBlock *MBB,
+void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
std::vector<CopyRec> *TryAgain, bool PhysOnly) {
DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
// If there are no loops in the function, join intervals in function order.
for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
I != E; ++I)
- CopyCoallesceInMBB(I, &TryAgainList);
+ CopyCoalesceInMBB(I, &TryAgainList);
} else {
// Otherwise, join intervals in inner loops before other intervals.
// Unfortunately we can't just iterate over loop hierarchy here because
// Finally, join intervals in loop nest order.
for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
- CopyCoallesceInMBB(MBBs[i].second, NULL, true);
+ CopyCoalesceInMBB(MBBs[i].second, NULL, true);
for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
- CopyCoallesceInMBB(MBBs[i].second, &TryAgainList, false);
+ CopyCoalesceInMBB(MBBs[i].second, &TryAgainList, false);
}
// Joining intervals can allow other intervals to be joined. Iteratively join
void SimpleRegisterCoalescing::unsetRegisterKill(MachineInstr *MI, unsigned Reg) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
- if (MO.isReg() && MO.isUse() && MO.isKill() && MO.getReg() &&
+ if (MO.isReg() && MO.isKill() && MO.getReg() &&
mri_->regsOverlap(rep(MO.getReg()), Reg))
MO.unsetIsKill();
}
for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
MachineOperand &MO = MI->getOperand(i);
- if (MO.isReg() && MO.isUse() && MO.isKill() && MO.getReg() &&
+ if (MO.isReg() && MO.isKill() && MO.getReg() &&
mri_->regsOverlap(rep(MO.getReg()), Reg)) {
MO.unsetIsKill();
}
r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
- // Join (coallesce) intervals if requested.
+ // Join (coalesce) intervals if requested.
if (EnableJoining) {
joinIntervals();
DOUT << "********** INTERVALS POST JOINING **********\n";
continue;
LiveInterval &RegInt = li_->getInterval(reg);
float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth);
- // If the definition instruction is re-materializable, its spill
- // weight is half of what it would have been normally unless it's
- // a load from fixed stack slot.
- int Dummy;
- if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy))
- w /= 2;
RegInt.weight += w;
UniqueUses.insert(reg);
}
projects / oota-llvm.git / blobdiff