X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveInterval.cpp;h=ac18843ac30d41e3d355c9ccda78a6b93e50f73a;hb=68675c6c5b173021807e4e12cd250eeba63f6d0d;hp=2ed4d124972ebdcb5b61a1bc1eb2457d41280df6;hpb=0253df9a897ce541d56146699cedd79c464bda5e;p=oota-llvm.git diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 2ed4d124972..ac18843ac30 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -30,19 +30,22 @@ #include 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). @@ -145,7 +148,6 @@ void LiveInterval::markValNoForDeletion(VNInfo *ValNo) { /// remaining unused values. void LiveInterval::RenumberValues(LiveIntervals &lis) { SmallPtrSet Seen; - bool seenPHIDef = false; valnos.clear(); for (const_iterator I = begin(), E = end(); I != E; ++I) { VNInfo *VNI = I->valno; @@ -154,26 +156,6 @@ void LiveInterval::RenumberValues(LiveIntervals &lis) { 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); - } } } @@ -291,6 +273,22 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) { 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. @@ -383,37 +381,40 @@ void LiveInterval::join(LiveInterval &Other, 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()); } @@ -476,60 +477,19 @@ void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, void LiveInterval::MergeValueInAsValue( const LiveInterval &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo) { - SmallVector 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 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 @@ -650,14 +610,9 @@ void LiveRange::dump() const { } 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"; @@ -687,8 +642,6 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { OS << "-phidef"; if (vni->hasPHIKill()) OS << "-phikill"; - if (vni->hasRedefByEC()) - OS << "-ec"; } } } @@ -703,92 +656,79 @@ void LiveRange::print(raw_ostream &os) const { 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) { - // Add new eq classes as needed. - for (unsigned i = eqClass_.size(), m = std::max(a, b); i <= m; ++i) - eqClass_.push_back(i); - - unsigned eqa = eqClass_[a]; - unsigned eqb = eqClass_[b]; - if (eqa == eqb) - return; - if (eqa > eqb) - std::swap(eqa, eqb); - // Now, eqa < eqb. Switch all eqb members over to eqa. - for (unsigned i = eqb, e = eqClass_.size(); i != e; ++i) - if (eqClass_[i] == eqb) - eqClass_[i] = eqa; -} - -unsigned ConnectedVNInfoEqClasses::Renumber() { - // No values at all. - if (eqClass_.empty()) - return 0; - - // Common case: A single connected component. - if (eqClass_.back() == 0) - return 1; - - // Renumber classes. We use the fact that eqClass_[i] == i for class leaders. - unsigned count = 0; - for (unsigned i = 0, e = eqClass_.size(); i != e; ++i) { - unsigned q = eqClass_[i]; - if (q == i) - eqClass_[i] = count++; - else - eqClass_[i] = eqClass_[q]; - } +unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { + // Create initial equivalence classes. + EqClass.clear(); + EqClass.grow(LI->getNumValNums()); - return count; -} + const VNInfo *used = 0, *unused = 0; -unsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { // Determine connections. - eqClass_.clear(); for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); I != E; ++I) { const VNInfo *VNI = *I; - if (VNI->id == eqClass_.size()) - eqClass_.push_back(VNI->id); - 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]) { - assert(LIV[eq]->empty() || LIV[eq]->expiredAt(I->start) && + 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); } else @@ -798,11 +738,11 @@ void ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[]) { // 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 {