#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "RegisterCoalescer.h"
#include <algorithm>
using namespace llvm;
return VNI;
}
-/// killedInRange - Return true if the interval has kills in [Start,End).
-bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
- Ranges::const_iterator r =
- std::lower_bound(ranges.begin(), ranges.end(), End);
-
- // Now r points to the first interval with start >= End, or ranges.end().
- if (r == ranges.begin())
- return false;
-
- --r;
- // Now r points to the last interval with end <= End.
- // r->end is the kill point.
- return r->end >= Start && r->end < End;
-}
-
// overlaps - Return true if the intersection of the two live intervals is
// not empty.
//
return false;
}
+bool LiveInterval::overlaps(const LiveInterval &Other,
+ const CoalescerPair &CP,
+ const SlotIndexes &Indexes) const {
+ assert(!empty() && "empty interval");
+ if (Other.empty())
+ return false;
+
+ // Use binary searches to find initial positions.
+ const_iterator I = find(Other.beginIndex());
+ const_iterator IE = end();
+ if (I == IE)
+ return false;
+ const_iterator J = Other.find(I->start);
+ const_iterator JE = Other.end();
+ if (J == JE)
+ return false;
+
+ for (;;) {
+ // J has just been advanced to satisfy:
+ assert(J->end >= I->start);
+ // Check for an overlap.
+ if (J->start < I->end) {
+ // I and J are overlapping. Find the later start.
+ SlotIndex Def = std::max(I->start, J->start);
+ // Allow the overlap if Def is a coalescable copy.
+ if (Def.isBlock() ||
+ !CP.isCoalescable(Indexes.getInstructionFromIndex(Def)))
+ return true;
+ }
+ // Advance the iterator that ends first to check for more overlaps.
+ if (J->end > I->end) {
+ std::swap(I, J);
+ std::swap(IE, JE);
+ }
+ // Advance J until J->end >= I->start.
+ do
+ if (++J == JE)
+ return false;
+ while (J->end < I->start);
+ }
+}
+
/// overlaps - Return true if the live interval overlaps a range specified
/// by [Start, End).
bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
valnos.pop_back();
} while (!valnos.empty() && valnos.back()->isUnused());
} else {
- ValNo->setIsUnused(true);
+ ValNo->markUnused();
}
}
// If we have to apply a mapping to our base interval assignment, rewrite it
// now.
- if (MustMapCurValNos) {
+ if (MustMapCurValNos && !empty()) {
// Map the first live range.
iterator OutIt = begin();
valnos.resize(NumNewVals); // shrinkify
// Okay, now insert the RHS live ranges into the LHS.
- iterator InsertPos = begin();
unsigned RangeNo = 0;
for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
// Map the valno in the other live range to the current live range.
I->valno = NewVNInfo[OtherAssignments[RangeNo]];
assert(I->valno && "Adding a dead range?");
- InsertPos = addRangeFrom(*I, InsertPos);
}
+ mergeIntervalRanges(Other);
verify();
}
/// This is a helper routine implementing an efficient merge of another
/// LiveIntervals ranges into the current interval.
///
-/// \param LHSValNo Set as the new value number for every range from RHS which
-/// is merged into the LHS.
+/// \param LHSValNo If non-NULL, set as the new value number for every range
+/// from RHS which is merged into the LHS.
/// \param RHSValNo If non-NULL, then only ranges in RHS whose original value
/// number maches this value number will be merged into LHS.
void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
if (RHS.empty())
return;
- // Ensure we're starting with valid ranges.
+ // Ensure we're starting with a valid range. Note that we don't verify RHS
+ // because it may have had its value numbers adjusted in preparation for
+ // merging.
verify();
- RHS.verify();
// The strategy for merging these efficiently is as follows:
//
if (*RI < R) {
R = *RI;
++RI;
- R.valno = LHSValNo;
+ if (LHSValNo)
+ R.valno = LHSValNo;
} else {
++LI;
}
ranges.insert(LI, NRI, NRE);
// And finally insert any trailing end of RHS (if we have one).
- for (; RI != RE; ++RI)
+ for (; RI != RE; ++RI) {
+ LiveRange R = *RI;
+ if (LHSValNo)
+ R.valno = LHSValNo;
if (!ranges.empty() &&
- ranges.back().valno == LHSValNo && RI->start <= ranges.back().end) {
- ranges.back().end = std::max(ranges.back().end, RI->end);
- } else {
- ranges.push_back(*RI);
- ranges.back().valno = LHSValNo;
- }
+ ranges.back().valno == R.valno && R.start <= ranges.back().end)
+ ranges.back().end = std::max(ranges.back().end, R.end);
+ else
+ ranges.push_back(R);
+ }
// Ensure we finished with a valid new sequence of ranges.
verify();
}
}
- // Merge the relevant flags.
- V2->mergeFlags(V1);
-
// Now that V1 is dead, remove it.
markValNoForDeletion(V1);
return V2;
}
-void LiveInterval::Copy(const LiveInterval &RHS,
- MachineRegisterInfo *MRI,
- VNInfo::Allocator &VNInfoAllocator) {
- ranges.clear();
- valnos.clear();
- std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg);
- MRI->setRegAllocationHint(reg, Hint.first, Hint.second);
-
- weight = RHS.weight;
- for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
- const VNInfo *VNI = RHS.getValNumInfo(i);
- createValueCopy(VNI, VNInfoAllocator);
- }
- for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
- const LiveRange &LR = RHS.ranges[i];
- addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
- }
-
- verify();
-}
-
unsigned LiveInterval::getSize() const {
unsigned Sum = 0;
for (const_iterator I = begin(), E = end(); I != E; ++I)
return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")";
}
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void LiveRange::dump() const {
dbgs() << *this << "\n";
}
+#endif
void LiveInterval::print(raw_ostream &OS) const {
if (empty())
} else {
OS << vni->def;
if (vni->isPHIDef())
- OS << "-phidef";
- if (vni->hasPHIKill())
- OS << "-phikill";
+ OS << "-phi";
}
}
}
}
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void LiveInterval::dump() const {
dbgs() << *this << "\n";
}
+#endif
#ifndef NDEBUG
void LiveInterval::verify() const {
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);
- // FIXME: We should be able to assert(VNI) here, but the coalescer leaves
- // dangling defs around.
+ LiveRangeQuery LRQ(LI, LIS.getInstructionIndex(MI));
+ const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined();
+ // In the case of an <undef> use that isn't tied to any def, VNI will be
+ // NULL. If the use is tied to a def, VNI will be the defined value.
if (!VNI)
continue;
MO.setReg(LIV[getEqClass(VNI)]->reg);
projects / oota-llvm.git / blobdiff