/// 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 UseIdx in the basic
-/// block that starts at StartIdx, extend it to be live at UseIdx and return
-/// the value. If there is no live range before UseIdx, return NULL.
-VNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex UseIdx) {
+/// 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(), UseIdx);
+ iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot());
if (I == begin())
return 0;
--I;
if (I->end <= StartIdx)
return 0;
- if (I->end <= UseIdx)
- extendIntervalEndTo(I, UseIdx.getNextSlot());
+ if (I->end < Kill)
+ extendIntervalEndTo(I, Kill);
return I->valno;
}
for (unsigned i = 0; i != NumVals; ++i) {
unsigned LHSValID = LHSValNoAssignments[i];
if (i != LHSValID ||
- (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i)))
+ (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) {
MustMapCurValNos = true;
+ break;
+ }
}
// If we have to apply a mapping to our base interval assignment, rewrite it
// now.
if (MustMapCurValNos) {
// Map the first live range.
+
iterator OutIt = begin();
OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
- ++OutIt;
- for (iterator I = OutIt, E = end(); I != E; ++I) {
- OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]];
+ for (iterator I = next(OutIt), E = end(); I != E; ++I) {
+ VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
+ assert(nextValNo != 0 && "Huh?");
// If this live range has the same value # as its immediate predecessor,
// and if they are neighbors, remove one LiveRange. This happens when we
- // have [0,3:0)[4,7:1) and map 0/1 onto the same value #.
- if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) {
- (OutIt-1)->end = OutIt->end;
+ // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
+ if (OutIt->valno == nextValNo && OutIt->end == I->start) {
+ OutIt->end = I->end;
} else {
- if (I != OutIt) {
+ // Didn't merge. Move OutIt to the next interval,
+ ++OutIt;
+ OutIt->valno = nextValNo;
+ if (OutIt != I) {
OutIt->start = I->start;
OutIt->end = I->end;
}
-
- // Didn't merge, on to the next one.
- ++OutIt;
}
}
-
// If we merge some live ranges, chop off the end.
+ ++OutIt;
ranges.erase(OutIt, end());
}
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
OS << "-phidef";
if (vni->hasPHIKill())
OS << "-phikill";
- if (vni->hasRedefByEC())
- OS << "-ec";
}
}
}
// 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()))
+ 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?
// Note that VNI->def may be a use slot for an early clobber def.
- if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getPrevSlot()))
+ if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def))
EqClass.join(VNI->id, UVNI->id);
}
}
continue;
// DBG_VALUE instructions should have been eliminated earlier.
SlotIndex Idx = LIS.getInstructionIndex(MI);
- Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
+ Idx = Idx.getRegSlot(MO.isUse());
const VNInfo *VNI = LI.getVNInfoAt(Idx);
assert(VNI && "Interval not live at use.");
MO.setReg(LIV[getEqClass(VNI)]->reg);