summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/CodeGen/LiveInterval.h1
-rw-r--r--llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h22
-rw-r--r--llvm/lib/CodeGen/LiveIntervalAnalysis.cpp188
3 files changed, 180 insertions, 31 deletions
diff --git a/llvm/include/llvm/CodeGen/LiveInterval.h b/llvm/include/llvm/CodeGen/LiveInterval.h
index f61a442a066..1878b2e634c 100644
--- a/llvm/include/llvm/CodeGen/LiveInterval.h
+++ b/llvm/include/llvm/CodeGen/LiveInterval.h
@@ -584,7 +584,6 @@ namespace llvm {
/// for the Value number.
VNInfo *createValueCopy(const VNInfo *orig,
BumpPtrAllocator &VNInfoAllocator) {
-
VNInfo *VNI =
static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
alignof<VNInfo>()));
diff --git a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 337ec1ce967..18c493823bd 100644
--- a/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -65,9 +65,6 @@ namespace llvm {
AliasAnalysis *aa_;
LiveVariables* lv_;
-
-
-
/// Special pool allocator for VNInfo's (LiveInterval val#).
///
BumpPtrAllocator VNInfoAllocator;
@@ -94,9 +91,14 @@ namespace llvm {
DenseMap<MachineBasicBlock*, MachineInstrIndex> terminatorGaps;
+ /// phiJoinCopies - Copy instructions which are PHI joins.
+ SmallVector<MachineInstr*, 16> phiJoinCopies;
+
+ /// allocatableRegs_ - A bit vector of allocatable registers.
BitVector allocatableRegs_;
- std::vector<MachineInstr*> ClonedMIs;
+ /// CloneMIs - A list of clones as result of re-materialization.
+ std::vector<MachineInstr*> CloneMIs;
typedef LiveInterval::InstrSlots InstrSlots;
@@ -430,7 +432,14 @@ namespace llvm {
private:
/// computeIntervals - Compute live intervals.
void computeIntervals();
-
+
+ bool isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
+ SmallVector<MachineInstr*,16> &IdentCopies,
+ SmallVector<MachineInstr*,16> &OtherCopies,
+ bool &HaveConflict);
+
+ void performEarlyCoalescing();
+
/// handleRegisterDef - update intervals for a register def
/// (calls handlePhysicalRegisterDef and
/// handleVirtualRegisterDef)
@@ -560,7 +569,8 @@ namespace llvm {
static LiveInterval* createInterval(unsigned Reg);
- void printRegName(unsigned reg) const;
+ void printInstrs(raw_ostream &O) const;
+ void dumpInstrs() const;
};
} // End llvm namespace
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
index 0c67149b761..124ff022258 100644
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -49,19 +49,20 @@ using namespace llvm;
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);
-
static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden);
static cl::opt<bool> EnableFastSpilling("fast-spill",
cl::init(false), cl::Hidden);
-STATISTIC(numIntervals, "Number of original intervals");
-STATISTIC(numFolds , "Number of loads/stores folded into instructions");
-STATISTIC(numSplits , "Number of intervals split");
+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");
@@ -96,12 +97,13 @@ void LiveIntervals::releaseMemory() {
i2miMap_.clear();
r2iMap_.clear();
terminatorGaps.clear();
+ phiJoinCopies.clear();
// Release VNInfo memroy regions after all VNInfo objects are dtor'd.
VNInfoAllocator.Reset();
- while (!ClonedMIs.empty()) {
- MachineInstr *MI = ClonedMIs.back();
- ClonedMIs.pop_back();
+ while (!CloneMIs.empty()) {
+ MachineInstr *MI = CloneMIs.back();
+ CloneMIs.pop_back();
mf_->DeleteMachineInstr(MI);
}
}
@@ -264,6 +266,7 @@ void LiveIntervals::computeNumbering() {
mi2iMap_.clear();
i2miMap_.clear();
terminatorGaps.clear();
+ phiJoinCopies.clear();
FunctionSize = 0;
@@ -518,6 +521,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
processImplicitDefs();
computeNumbering();
computeIntervals();
+ performEarlyCoalescing();
numIntervals += getNumIntervals();
@@ -533,6 +537,10 @@ void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
OS << "\n";
}
+ printInstrs(OS);
+}
+
+void LiveIntervals::printInstrs(raw_ostream &OS) const {
OS << "********** MACHINEINSTRS **********\n";
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
@@ -545,6 +553,10 @@ void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
}
}
+void LiveIntervals::dumpInstrs() const {
+ printInstrs(errs());
+}
+
/// conflictsWithPhysRegDef - Returns true if the specified register
/// is defined during the duration of the specified interval.
bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
@@ -626,7 +638,7 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li,
}
-void LiveIntervals::printRegName(unsigned reg) const {
+static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) {
if (TargetRegisterInfo::isPhysicalRegister(reg))
errs() << tri_->getName(reg);
else
@@ -641,7 +653,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
LiveInterval &interval) {
DEBUG({
errs() << "\t\tregister: ";
- printRegName(interval.reg);
+ printRegName(interval.reg, tri_);
});
// Virtual registers may be defined multiple times (due to phi
@@ -789,12 +801,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
// 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()) {
- assert(vi.Kills.size() == 1 &&
- "PHI elimination vreg should have one kill, the PHI itself!");
-
// 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);
MachineInstrIndex Start = getMBBStartIdx(Killer->getParent());
MachineInstrIndex End =
getNextSlot(getUseIndex(getInstructionIndex(Killer)));
@@ -805,7 +815,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
});
interval.removeRange(Start, End);
assert(interval.ranges.size() == 1 &&
- "newly discovered PHI interval has >1 ranges.");
+ "Newly discovered PHI interval has >1 ranges.");
MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex());
VNI->addKill(terminatorGaps[killMBB]);
VNI->setHasPHIKill(true);
@@ -835,7 +845,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
MachineInstrIndex defIndex = getDefIndex(MIIdx);
if (MO.isEarlyClobber())
defIndex = getUseIndex(MIIdx);
-
+
VNInfo *ValNo;
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
@@ -868,7 +878,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
// lifetime must end somewhere in its defining basic block.
DEBUG({
errs() << "\t\tregister: ";
- printRegName(interval.reg);
+ printRegName(interval.reg, tri_);
});
MachineInstrIndex baseIndex = MIIdx;
@@ -977,7 +987,7 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
LiveInterval &interval, bool isAlias) {
DEBUG({
errs() << "\t\tlivein register: ";
- printRegName(interval.reg);
+ printRegName(interval.reg, tri_);
});
// Look for kills, if it reaches a def before it's killed, then it shouldn't
@@ -1039,6 +1049,138 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
DEBUG(errs() << " +" << LR << '\n');
}
+bool
+LiveIntervals::isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt,
+ SmallVector<MachineInstr*,16> &IdentCopies,
+ SmallVector<MachineInstr*,16> &OtherCopies,
+ bool &HaveConflict) {
+ HaveConflict = false;
+
+ unsigned NumIdent = 0;
+ unsigned NumSources = 0;
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(SrcInt.reg),
+ re = mri_->reg_end(); ri != re; ++ri) {
+ MachineOperand &O = ri.getOperand();
+ if (!O.isDef())
+ continue;
+
+ ++NumSources;
+ MachineInstr *MI = &*ri;
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
+ continue;
+ if (SrcReg != DstInt.reg) {
+ OtherCopies.push_back(MI);
+ HaveConflict |= DstInt.liveAt(getInstructionIndex(MI));
+ } else {
+ IdentCopies.push_back(MI);
+ ++NumIdent;
+ }
+ }
+
+ return NumSources >= 5 && (((float)NumIdent) / NumSources) > 0.20F;
+}
+
+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;
+ bool HaveConflict;
+ if (!isProfitableToCoalesce(DstInt, SrcInt, IdentCopies, OtherCopies,
+ HaveConflict))
+ continue;
+
+ DEBUG(errs() << "PHI Join: " << *Join);
+ assert(DstInt.containsOneValue() && "PHI join should have just one val#!");
+ VNInfo *VNI = DstInt.getValNumInfo(0);
+ VNInfo *NewVNI = HaveConflict
+ ? 0 : SrcInt.getNextValue(VNI->def, 0, false, VNInfoAllocator);
+ // 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);
+
+ MachineBasicBlock *PHIMBB = PHICopy->getParent();
+ MachineInstrIndex MIIndex = getInstructionIndex(PHICopy);
+ MachineInstrIndex DefIndex = getDefIndex(MIIndex);
+ LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
+ MachineInstrIndex StartIndex = HaveConflict
+ ? SLR->start : getMBBStartIdx(PHIMBB);
+ MachineInstrIndex 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);
+ if (HaveConflict) {
+ DEBUG(errs() << " added range [" << StartIndex << ','
+ << EndIndex << "] to reg" << DstInt.reg << '\n');
+ DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI));
+ // FIXME: Update uses of src to dst in this range?
+ } else {
+ DEBUG(errs() << " added range [" << StartIndex << ','
+ << SLR->start << "] to reg" << SrcInt.reg << '\n');
+ SrcInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI));
+ if (PHICopy->killsRegister(PHIDst))
+ EndIndex = DefIndex;
+ DstInt.removeRange(StartIndex, EndIndex);
+ }
+ RemoveMachineInstrFromMaps(PHICopy);
+ PHICopy->eraseFromParent();
+ }
+ if (HaveConflict) {
+ // First unset the kill.
+ for (unsigned i = 0, e = Join->getNumOperands(); i != e; ++i) {
+ MachineOperand &O = Join->getOperand(i);
+ if (!O.isReg() || O.getReg() != PHISrc)
+ continue;
+ if (O.isKill())
+ O.setIsKill(false);
+ }
+ MachineInstrIndex MIIndex = getInstructionIndex(Join);
+ MachineInstrIndex UseIndex = getUseIndex(MIIndex);
+ MachineInstrIndex DefIndex = getDefIndex(MIIndex);
+ LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
+ LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
+ SrcInt.addRange(LiveRange(DLR->start, DLR->end, SLR->valno));
+ } else {
+ SrcInt.MergeValueInAsValue(DstInt, VNI, NewVNI);
+
+ // Change all references of phi source to destination.
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(PHIDst),
+ re = mri_->reg_end(); ri != re; ) {
+ MachineOperand &O = ri.getOperand();
+ ++ri;
+ O.setReg(PHISrc);
+ }
+ removeInterval(DstInt.reg);
+
+ 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
@@ -2230,9 +2372,7 @@ addIntervalsForSpills(const LiveInterval &li,
return NewLIs;
}
- bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
- if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
- TrySplit = false;
+ bool TrySplit = !intervalIsInOneMBB(li);
if (TrySplit)
++numSplits;
bool NeedStackSlot = false;
@@ -2251,7 +2391,7 @@ addIntervalsForSpills(const LiveInterval &li,
ReMatOrigDefs[VN] = ReMatDefMI;
// Original def may be modified so we have to make a copy here.
MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
- ClonedMIs.push_back(Clone);
+ CloneMIs.push_back(Clone);
ReMatDefs[VN] = Clone;
bool CanDelete = true;
OpenPOWER on IntegriCloud