#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
cl::desc("Avoid coalescing cross register class copies"),
cl::init(false), cl::Hidden);
-static cl::opt<bool>
-PhysJoinTweak("tweak-phys-join-heuristics",
- cl::desc("Tweak heuristics for joining phys reg with vr"),
- cl::init(false), cl::Hidden);
-
static RegisterPass<SimpleRegisterCoalescing>
X("simple-register-coalescing", "Simple Register Coalescing");
if (!tii_->isTriviallyReMaterializable(DefMI, AA))
return false;
bool SawStore = false;
- if (!DefMI->isSafeToMove(tii_, SawStore, AA))
+ if (!DefMI->isSafeToMove(tii_, AA, SawStore))
return false;
if (TID.getNumDefs() != 1)
return false;
for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) {
if (!li_->hasInterval(*SR))
continue;
- DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx);
+ const LiveRange *DLR =
+ li_->getInterval(*SR).getLiveRangeContaining(DefIdx);
if (DLR && DLR->valno->getCopy() == CopyMI)
DLR->valno->setCopy(0);
}
NewMI->addOperand(MO);
if (MO.isDef() && li_->hasInterval(MO.getReg())) {
unsigned Reg = MO.getReg();
- DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
+ const LiveRange *DLR =
+ li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
if (DLR && DLR->valno->getCopy() == CopyMI)
DLR->valno->setCopy(0);
+ // Handle subregs as well
+ if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+ for (const unsigned* SR = tri_->getSubRegisters(Reg); *SR; ++SR) {
+ if (!li_->hasInterval(*SR))
+ continue;
+ const LiveRange *DLR =
+ li_->getInterval(*SR).getLiveRangeContaining(DefIdx);
+ if (DLR && DLR->valno->getCopy() == CopyMI)
+ DLR->valno->setCopy(0);
+ }
+ }
}
}
CopyMI->eraseFromParent();
ReMatCopies.insert(CopyMI);
ReMatDefs.insert(DefMI);
+ DEBUG(dbgs() << "Remat: " << *NewMI);
++NumReMats;
return true;
}
SubIdx = 0;
}
+ // Copy the register use-list before traversing it. We may be adding operands
+ // and invalidating pointers.
+ SmallVector<std::pair<MachineInstr*, unsigned>, 32> reglist;
for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
- E = mri_->reg_end(); I != E; ) {
- MachineOperand &O = I.getOperand();
- MachineInstr *UseMI = &*I;
- ++I;
+ E = mri_->reg_end(); I != E; ++I)
+ reglist.push_back(std::make_pair(&*I, I.getOperandNo()));
+
+ for (unsigned N=0; N != reglist.size(); ++N) {
+ MachineInstr *UseMI = reglist[N].first;
+ MachineOperand &O = UseMI->getOperand(reglist[N].second);
unsigned OldSubIdx = O.getSubReg();
if (DstIsPhys) {
unsigned UseDstReg = DstReg;
O.setReg(UseDstReg);
O.setSubReg(0);
+ if (OldSubIdx) {
+ // Def and kill of subregister of a virtual register actually defs and
+ // kills the whole register. Add imp-defs and imp-kills as needed.
+ if (O.isDef()) {
+ if(O.isDead())
+ UseMI->addRegisterDead(DstReg, tri_, true);
+ else
+ UseMI->addRegisterDefined(DstReg, tri_);
+ } else if (!O.isUndef() &&
+ (O.isKill() ||
+ UseMI->isRegTiedToDefOperand(&O-&UseMI->getOperand(0))))
+ UseMI->addRegisterKilled(DstReg, tri_, true);
+ }
continue;
}
LiveInterval &SmallInt = li_->getInterval(SmallReg);
unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt);
unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt);
- if (SmallSize > Threshold || LargeSize > Threshold)
- if ((float)std::distance(mri_->use_nodbg_begin(SmallReg),
- mri_->use_nodbg_end()) / SmallSize <
- (float)std::distance(mri_->use_nodbg_begin(LargeReg),
- mri_->use_nodbg_end()) / LargeSize)
+ if (LargeSize > Threshold) {
+ unsigned SmallUses = std::distance(mri_->use_nodbg_begin(SmallReg),
+ mri_->use_nodbg_end());
+ unsigned LargeUses = std::distance(mri_->use_nodbg_begin(LargeReg),
+ mri_->use_nodbg_end());
+ if (SmallUses*LargeSize < LargeUses*SmallSize)
return false;
+ }
return true;
}
RealDstReg = tri_->getMatchingSuperReg(DstReg, SubIdx, RC);
assert(RealDstReg && "Invalid extract_subreg instruction!");
+ LiveInterval &RHS = li_->getInterval(SrcReg);
// For this type of EXTRACT_SUBREG, conservatively
// check if the live interval of the source register interfere with the
// actual super physical register we are trying to coalesce with.
- LiveInterval &RHS = li_->getInterval(SrcReg);
if (li_->hasInterval(RealDstReg) &&
RHS.overlaps(li_->getInterval(RealDstReg))) {
DEBUG({
return false; // Not coalescable
}
for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR)
- if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
+ // Do not check DstReg or its sub-register. JoinIntervals() will take care
+ // of that.
+ if (*SR != DstReg &&
+ !tri_->isSubRegister(DstReg, *SR) &&
+ li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
DEBUG({
dbgs() << "Interfere with sub-register ";
li_->getInterval(*SR).print(dbgs(), tri_);
RealSrcReg = tri_->getMatchingSuperReg(SrcReg, SubIdx, RC);
assert(RealSrcReg && "Invalid extract_subreg instruction!");
- LiveInterval &RHS = li_->getInterval(DstReg);
+ LiveInterval &LHS = li_->getInterval(DstReg);
if (li_->hasInterval(RealSrcReg) &&
- RHS.overlaps(li_->getInterval(RealSrcReg))) {
+ LHS.overlaps(li_->getInterval(RealSrcReg))) {
DEBUG({
dbgs() << "Interfere with register ";
li_->getInterval(RealSrcReg).print(dbgs(), tri_);
return false; // Not coalescable
}
for (const unsigned* SR = tri_->getSubRegisters(RealSrcReg); *SR; ++SR)
- if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
+ // Do not check SrcReg or its sub-register. JoinIntervals() will take care
+ // of that.
+ if (*SR != SrcReg &&
+ !tri_->isSubRegister(SrcReg, *SR) &&
+ li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) {
DEBUG({
dbgs() << "Interfere with sub-register ";
li_->getInterval(*SR).print(dbgs(), tri_);
const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg);
const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg);
const TargetRegisterClass *NewRC = NULL;
- MachineBasicBlock *CopyMBB = CopyMI->getParent();
unsigned RealDstReg = 0;
unsigned RealSrcReg = 0;
if (isExtSubReg || isInsSubReg || isSubRegToReg) {
return false; // Not coalescable.
}
+ // FIXME: The following checks are somewhat conservative. Perhaps a better
+ // way to implement this is to treat this as coalescing a vr with the
+ // super physical register.
if (isExtSubReg) {
if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg))
return false; // Not coalescable
(isExtSubReg || DstRC->isASubClass()) &&
!isWinToJoinCrossClass(LargeReg, SmallReg,
allocatableRCRegs_[NewRC].count())) {
- DEBUG(dbgs() << "\tSrc/Dest are different register classes.\n");
+ DEBUG(dbgs() << "\tSrc/Dest are different register classes: "
+ << SrcRC->getName() << "/"
+ << DstRC->getName() << " -> "
+ << NewRC->getName() << ".\n");
// Allow the coalescer to try again in case either side gets coalesced to
// a physical register that's compatible with the other side. e.g.
// r1024 = MOV32to32_ r1025
// Save a copy of the virtual register live interval. We'll manually
// merge this into the "real" physical register live interval this is
// coalesced with.
- LiveInterval *SavedLI = 0;
+ OwningPtr<LiveInterval> SavedLI;
if (RealDstReg)
- SavedLI = li_->dupInterval(&SrcInt);
+ SavedLI.reset(li_->dupInterval(&SrcInt));
else if (RealSrcReg)
- SavedLI = li_->dupInterval(&DstInt);
+ SavedLI.reset(li_->dupInterval(&DstInt));
- // Check if it is necessary to propagate "isDead" property.
if (!isExtSubReg && !isInsSubReg && !isSubRegToReg) {
+ // Check if it is necessary to propagate "isDead" property.
MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
bool isDead = mopd->isDead();
// these are not spillable! If the destination interval uses are far away,
// think twice about coalescing them!
if (!isDead && (SrcIsPhys || DstIsPhys)) {
- // If the copy is in a loop, take care not to coalesce aggressively if the
- // src is coming in from outside the loop (or the dst is out of the loop).
- // If it's not in a loop, then determine whether to join them base purely
- // by the length of the interval.
- if (PhysJoinTweak) {
- if (SrcIsPhys) {
- if (!isWinToJoinVRWithSrcPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) {
- mri_->setRegAllocationHint(DstInt.reg, 0, SrcReg);
- ++numAborts;
- DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
- Again = true; // May be possible to coalesce later.
- return false;
- }
- } else {
- if (!isWinToJoinVRWithDstPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) {
- mri_->setRegAllocationHint(SrcInt.reg, 0, DstReg);
- ++numAborts;
- DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
- Again = true; // May be possible to coalesce later.
- return false;
- }
- }
- } else {
- // If the virtual register live interval is long but it has low use
- // density, do not join them, instead mark the physical register as its
- // allocation preference.
- LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
- unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
- unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
- const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg);
- unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
- unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
- float Ratio = 1.0 / Threshold;
- if (Length > Threshold &&
- (((float)std::distance(mri_->use_nodbg_begin(JoinVReg),
- mri_->use_nodbg_end()) / Length) < Ratio)) {
- mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg);
- ++numAborts;
- DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
- Again = true; // May be possible to coalesce later.
- return false;
- }
+ // If the virtual register live interval is long but it has low use
+ // density, do not join them, instead mark the physical register as its
+ // allocation preference.
+ LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
+ LiveInterval &JoinPInt = SrcIsPhys ? SrcInt : DstInt;
+ unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
+ unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
+
+ // Don't join with physregs that have a ridiculous number of live
+ // ranges. The data structure performance is really bad when that
+ // happens.
+ if (JoinPInt.ranges.size() > 1000) {
+ mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg);
+ ++numAborts;
+ DEBUG(dbgs()
+ << "\tPhysical register live interval too complicated, abort!\n");
+ return false;
+ }
+
+ const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg);
+ unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
+ unsigned Length = li_->getApproximateInstructionCount(JoinVInt);
+ float Ratio = 1.0 / Threshold;
+ if (Length > Threshold &&
+ (((float)std::distance(mri_->use_nodbg_begin(JoinVReg),
+ mri_->use_nodbg_end()) / Length) < Ratio)) {
+ // Before giving up coalescing, if definition of source is defined by
+ // trivial computation, try rematerializing it.
+ if (ReMaterializeTrivialDef(SrcInt, DstReg, DstSubIdx, CopyMI))
+ return true;
+
+ mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg);
+ ++numAborts;
+ DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n");
+ Again = true; // May be possible to coalesce later.
+ return false;
}
}
}
// been modified, so we can use this information below to update aliases.
bool Swapped = false;
// If SrcInt is implicitly defined, it's safe to coalesce.
- bool isEmpty = SrcInt.empty();
- if (isEmpty && !CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) {
- // Only coalesce an empty interval (defined by implicit_def) with
- // another interval which has a valno defined by the CopyMI and the CopyMI
- // is a kill of the implicit def.
- DEBUG(dbgs() << "Not profitable!\n");
- return false;
- }
-
- if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) {
+ if (SrcInt.empty()) {
+ if (!CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) {
+ // Only coalesce an empty interval (defined by implicit_def) with
+ // another interval which has a valno defined by the CopyMI and the CopyMI
+ // is a kill of the implicit def.
+ DEBUG(dbgs() << "Not profitable!\n");
+ return false;
+ }
+ } else if (!JoinIntervals(DstInt, SrcInt, Swapped)) {
// Coalescing failed.
// If definition of source is defined by trivial computation, try
(AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) ||
RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) {
JoinedCopies.insert(CopyMI);
+ DEBUG(dbgs() << "Trivial!\n");
return true;
}
// Manually deleted the live interval copy.
if (SavedLI) {
SavedLI->clear();
- delete SavedLI;
+ SavedLI.reset();
}
// If resulting interval has a preference that no longer fits because of subreg
// If the VN has already been computed, just return it.
if (ThisValNoAssignments[VN] >= 0)
return ThisValNoAssignments[VN];
-// assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?");
+ assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers");
// If this val is not a copy from the other val, then it must be a new value
// number in the destination.
li_->intervalIsInOneMBB(RHS) &&
li_->getApproximateInstructionCount(RHS) <= 10) {
// Perform a more exhaustive check for some common cases.
- if (li_->conflictsWithPhysRegRef(RHS, LHS.reg, true, JoinedCopies))
+ if (li_->conflictsWithSubPhysRegRef(RHS, LHS.reg, true, JoinedCopies))
return false;
} else {
for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR)
if (LHS.containsOneValue() &&
li_->getApproximateInstructionCount(LHS) <= 10) {
// Perform a more exhaustive check for some common cases.
- if (li_->conflictsWithPhysRegRef(LHS, RHS.reg, false, JoinedCopies))
+ if (li_->conflictsWithSubPhysRegRef(LHS, RHS.reg, false, JoinedCopies))
return false;
} else {
for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR)
if (MO.isDead())
continue;
if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
- !mri_->use_empty(Reg)) {
+ !mri_->use_nodbg_empty(Reg)) {
isDead = false;
break;
}
projects / oota-llvm.git / blobdiff