#include <algorithm>
using namespace llvm;
-// CompEnd - Compare LiveRange ends.
-namespace {
-struct CompEnd {
- bool operator()(const LiveRange &A, const LiveRange &B) const {
- return A.end < B.end;
- }
-};
-}
-
LiveInterval::iterator LiveInterval::find(SlotIndex Pos) {
- assert(Pos.isValid() && "Cannot search for an invalid index");
- return std::upper_bound(begin(), end(), LiveRange(SlotIndex(), Pos, 0),
- CompEnd());
+ // This algorithm is basically std::upper_bound.
+ // Unfortunately, std::upper_bound cannot be used with mixed types until we
+ // adopt C++0x. Many libraries can do it, but not all.
+ if (empty() || Pos >= endIndex())
+ return end();
+ iterator I = begin();
+ size_t Len = ranges.size();
+ do {
+ size_t Mid = Len >> 1;
+ if (Pos < I[Mid].end)
+ Len = Mid;
+ else
+ I += Mid + 1, Len -= Mid + 1;
+ } while (Len);
+ return I;
}
/// killedInRange - Return true if the interval has kills in [Start,End).
/// remaining unused values.
void LiveInterval::RenumberValues(LiveIntervals &lis) {
SmallPtrSet<VNInfo*, 8> Seen;
- bool seenPHIDef = false;
valnos.clear();
for (const_iterator I = begin(), E = end(); I != E; ++I) {
VNInfo *VNI = I->valno;
assert(!VNI->isUnused() && "Unused valno used by live range");
VNI->id = (unsigned)valnos.size();
valnos.push_back(VNI);
- VNI->setHasPHIKill(false);
- if (VNI->isPHIDef())
- seenPHIDef = true;
- }
-
- // Recompute phi kill flags.
- if (!seenPHIDef)
- return;
- for (const_vni_iterator I = vni_begin(), E = vni_end(); I != E; ++I) {
- VNInfo *VNI = *I;
- if (!VNI->isPHIDef())
- continue;
- const MachineBasicBlock *PHIBB = lis.getMBBFromIndex(VNI->def);
- assert(PHIBB && "No basic block for phi-def");
- for (MachineBasicBlock::const_pred_iterator PI = PHIBB->pred_begin(),
- PE = PHIBB->pred_end(); PI != PE; ++PI) {
- VNInfo *KVNI = getVNInfoAt(lis.getMBBEndIdx(*PI).getPrevSlot());
- if (KVNI)
- KVNI->setHasPHIKill(true);
- }
}
}
return ranges.insert(it, LR);
}
+/// extendInBlock - If this interval is live before Kill in the basic
+/// block that starts at StartIdx, extend it to be live up to Kill and return
+/// the value. If there is no live range before Kill, return NULL.
+VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
+ if (empty())
+ return 0;
+ iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
+ if (I == begin())
+ return 0;
+ --I;
+ if (I->end <= StartIdx)
+ return 0;
+ if (I->end < Kill)
+ extendIntervalEndTo(I, Kill);
+ return I->valno;
+}
/// removeRange - Remove the specified range from this interval. Note that
/// the range must be in a single LiveRange in its entirety.
void LiveInterval::MergeValueInAsValue(
const LiveInterval &RHS,
const VNInfo *RHSValNo, VNInfo *LHSValNo) {
- SmallVector<VNInfo*, 4> ReplacedValNos;
- iterator IP = begin();
+ // TODO: Make this more efficient.
+ iterator InsertPos = begin();
for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
- assert(I->valno == RHS.getValNumInfo(I->valno->id) && "Bad VNInfo");
if (I->valno != RHSValNo)
continue;
- SlotIndex Start = I->start, End = I->end;
- IP = std::upper_bound(IP, end(), Start);
- // If the start of this range overlaps with an existing liverange, trim it.
- if (IP != begin() && IP[-1].end > Start) {
- if (IP[-1].valno != LHSValNo) {
- ReplacedValNos.push_back(IP[-1].valno);
- IP[-1].valno = LHSValNo; // Update val#.
- }
- Start = IP[-1].end;
- // Trimmed away the whole range?
- if (Start >= End) continue;
- }
- // If the end of this range overlaps with an existing liverange, trim it.
- if (IP != end() && End > IP->start) {
- if (IP->valno != LHSValNo) {
- ReplacedValNos.push_back(IP->valno);
- IP->valno = LHSValNo; // Update val#.
- }
- End = IP->start;
- // If this trimmed away the whole range, ignore it.
- if (Start == End) continue;
- }
-
// Map the valno in the other live range to the current live range.
- IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP);
- }
-
-
- SmallSet<VNInfo*, 4> Seen;
- for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) {
- VNInfo *V1 = ReplacedValNos[i];
- if (Seen.insert(V1)) {
- bool isDead = true;
- for (const_iterator I = begin(), E = end(); I != E; ++I)
- if (I->valno == V1) {
- isDead = false;
- break;
- }
- if (isDead) {
- // Now that V1 is dead, remove it.
- markValNoForDeletion(V1);
- }
- }
+ LiveRange Tmp = *I;
+ Tmp.valno = LHSValNo;
+ InsertPos = addRangeFrom(Tmp, InsertPos);
}
}
-
/// MergeValueNumberInto - This method is called when two value nubmers
/// are found to be equivalent. This eliminates V1, replacing all
/// LiveRanges with the V1 value number with the V2 value number. This can
}
void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
- if (isStackSlot())
- OS << "SS#" << getStackSlotIndex();
- else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg))
- OS << TRI->getName(reg);
- else
- OS << "%reg" << reg;
-
- OS << ',' << weight;
+ OS << PrintReg(reg, TRI);
+ if (weight != 0)
+ OS << ',' << weight;
if (empty())
OS << " EMPTY";
os << *this;
}
-/// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
-/// LiveInterval into equivalence clases of connected components. A
-/// LiveInterval that has multiple connected components can be broken into
-/// multiple LiveIntervals.
-
-void ConnectedVNInfoEqClasses::Connect(unsigned a, unsigned b) {
- while (eqClass_[a] != eqClass_[b]) {
- if (eqClass_[a] > eqClass_[b])
- std::swap(a, b);
- unsigned t = eqClass_[b];
- assert(t <= b && "Invariant broken");
- eqClass_[b] = eqClass_[a];
- b = t;
- }
-}
-
-unsigned ConnectedVNInfoEqClasses::Renumber() {
- // Assign final class numbers.
- // We use the fact that eqClass_[i] == i for class leaders.
- // For others, eqClass_[i] points to an earlier value in the same class.
- unsigned count = 0;
- for (unsigned i = 0, e = eqClass_.size(); i != e; ++i) {
- unsigned q = eqClass_[i];
- assert(q <= i && "Invariant broken");
- eqClass_[i] = q == i ? count++ : eqClass_[q];
- }
-
- return count;
-}
-
unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) {
// Create initial equivalence classes.
- eqClass_.clear();
- eqClass_.reserve(LI->getNumValNums());
- for (unsigned i = 0, e = LI->getNumValNums(); i != e; ++i)
- eqClass_.push_back(i);
+ EqClass.clear();
+ EqClass.grow(LI->getNumValNums());
+
+ const VNInfo *used = 0, *unused = 0;
// Determine connections.
for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end();
I != E; ++I) {
const VNInfo *VNI = *I;
- assert(!VNI->isUnused() && "Cannot handle unused values");
+ // Group all unused values into one class.
+ if (VNI->isUnused()) {
+ if (unused)
+ EqClass.join(unused->id, VNI->id);
+ unused = VNI;
+ continue;
+ }
+ used = VNI;
if (VNI->isPHIDef()) {
- const MachineBasicBlock *MBB = lis_.getMBBFromIndex(VNI->def);
+ const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
assert(MBB && "Phi-def has no defining MBB");
// Connect to values live out of predecessors.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI)
- if (const VNInfo *PVNI =
- LI->getVNInfoAt(lis_.getMBBEndIdx(*PI).getPrevSlot()))
- Connect(VNI->id, PVNI->id);
+ if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
+ EqClass.join(VNI->id, PVNI->id);
} else {
// Normal value defined by an instruction. Check for two-addr redef.
// FIXME: This could be coincidental. Should we really check for a tied
// operand constraint?
- if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getUseIndex()))
- Connect(VNI->id, UVNI->id);
+ // Note that VNI->def may be a use slot for an early clobber def.
+ if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def))
+ EqClass.join(VNI->id, UVNI->id);
}
}
- return Renumber();
+
+ // Lump all the unused values in with the last used value.
+ if (used && unused)
+ EqClass.join(used->id, unused->id);
+
+ EqClass.compress();
+ return EqClass.getNumClasses();
}
-void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[]) {
+void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[],
+ MachineRegisterInfo &MRI) {
assert(LIV[0] && "LIV[0] must be set");
LiveInterval &LI = *LIV[0];
- // Check that they likely ran Classify() on LIV[0] first.
- assert(eqClass_.size() == LI.getNumValNums() && "Bad classification data");
- // First move runs to new intervals.
+ // Rewrite instructions.
+ for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
+ RE = MRI.reg_end(); RI != RE;) {
+ MachineOperand &MO = RI.getOperand();
+ MachineInstr *MI = MO.getParent();
+ ++RI;
+ if (MO.isUse() && MO.isUndef())
+ continue;
+ // DBG_VALUE instructions should have been eliminated earlier.
+ SlotIndex Idx = LIS.getInstructionIndex(MI);
+ Idx = Idx.getRegSlot(MO.isUse());
+ const VNInfo *VNI = LI.getVNInfoAt(Idx);
+ assert(VNI && "Interval not live at use.");
+ MO.setReg(LIV[getEqClass(VNI)]->reg);
+ }
+
+ // Move runs to new intervals.
LiveInterval::iterator J = LI.begin(), E = LI.end();
- while (J != E && eqClass_[J->valno->id] == 0)
+ while (J != E && EqClass[J->valno->id] == 0)
++J;
for (LiveInterval::iterator I = J; I != E; ++I) {
- if (unsigned eq = eqClass_[I->valno->id]) {
+ if (unsigned eq = EqClass[I->valno->id]) {
assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) &&
"New intervals should be empty");
LIV[eq]->ranges.push_back(*I);
// Transfer VNInfos to their new owners and renumber them.
unsigned j = 0, e = LI.getNumValNums();
- while (j != e && eqClass_[j] == 0)
+ while (j != e && EqClass[j] == 0)
++j;
for (unsigned i = j; i != e; ++i) {
VNInfo *VNI = LI.getValNumInfo(i);
- if (unsigned eq = eqClass_[i]) {
+ if (unsigned eq = EqClass[i]) {
VNI->id = LIV[eq]->getNumValNums();
LIV[eq]->valnos.push_back(VNI);
} else {