//
//===----------------------------------------------------------------------===//
-#include "LiveInterval.h"
+#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/Target/MRegisterInfo.h"
+#include <algorithm>
#include <iostream>
#include <map>
using namespace llvm;
//
bool LiveInterval::liveAt(unsigned I) const {
Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
-
+
if (r == ranges.begin())
return false;
return r->contains(I);
}
+// overlaps - Return true if the intersection of the two live intervals is
+// not empty.
+//
// An example for overlaps():
//
// 0: A = ...
//
// A->overlaps(C) should return false since we want to be able to join
// A and C.
-bool LiveInterval::overlaps(const LiveInterval& other) const {
- Ranges::const_iterator i = ranges.begin();
- Ranges::const_iterator ie = ranges.end();
- Ranges::const_iterator j = other.ranges.begin();
- Ranges::const_iterator je = other.ranges.end();
+//
+bool LiveInterval::overlapsFrom(const LiveInterval& other,
+ const_iterator StartPos) const {
+ const_iterator i = begin();
+ const_iterator ie = end();
+ const_iterator j = StartPos;
+ const_iterator je = other.end();
+
+ assert((StartPos->start <= i->start || StartPos == other.begin()) &&
+ StartPos != other.end() && "Bogus start position hint!");
if (i->start < j->start) {
i = std::upper_bound(i, ie, j->start);
if (i != ranges.begin()) --i;
} else if (j->start < i->start) {
- j = std::upper_bound(j, je, i->start);
- if (j != other.ranges.begin()) --j;
+ ++StartPos;
+ if (StartPos != other.end() && StartPos->start <= i->start) {
+ assert(StartPos < other.end() && i < end());
+ j = std::upper_bound(j, je, i->start);
+ if (j != other.ranges.begin()) --j;
+ }
} else {
return true;
}
- while (i != ie && j != je) {
- if (i->start == j->start)
- return true;
+ if (j == je) return false;
+ while (i != ie) {
if (i->start > j->start) {
std::swap(i, j);
std::swap(ie, je);
}
- assert(i->start < j->start);
if (i->end > j->start)
return true;
return false;
}
+/// NontrivialOverlap - Check to see if the two live ranges specified by i and j
+/// overlap. If so, check to see if they have value numbers that are not
+/// iIdx/jIdx respectively. If both conditions are true, return true.
+static inline bool NontrivialOverlap(const LiveRange &I, const LiveRange &J,
+ unsigned iIdx, unsigned jIdx) {
+ if (I.start == J.start) {
+ // If this is not the allowed value merge, we cannot join.
+ if (I.ValId != iIdx || J.ValId != jIdx)
+ return true;
+ } else if (I.start < J.start) {
+ if (I.end > J.start && (I.ValId != iIdx || J.ValId != jIdx)) {
+ return true;
+ }
+ } else {
+ if (J.end > I.start && (I.ValId != iIdx || J.ValId != jIdx))
+ return true;
+ }
+
+ return false;
+}
+
/// joinable - Two intervals are joinable if the either don't overlap at all
/// or if the destination of the copy is a single assignment value, and it
/// only overlaps with one value in the source interval.
}
while (i != ie && j != je) {
- if (i->start == j->start) {
- // If this is not the allowed value merge, we cannot join.
- if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
- return false;
- } else if (i->start < j->start) {
- if (i->end > j->start) {
- if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
- return false;
- }
- } else {
- if (j->end > i->start) {
- if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
- return false;
- }
- }
+ if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx))
+ return false;
+
if (i->end < j->end)
++i;
else
return true;
}
+/// getOverlapingRanges - Given another live interval which is defined as a
+/// copy from this one, return a list of all of the live ranges where the
+/// two overlap and have different value numbers.
+void LiveInterval::getOverlapingRanges(const LiveInterval &other,
+ unsigned CopyIdx,
+ std::vector<LiveRange*> &Ranges) {
+ const LiveRange *SourceLR = getLiveRangeContaining(CopyIdx-1);
+ const LiveRange *DestLR = other.getLiveRangeContaining(CopyIdx);
+ assert(SourceLR && DestLR && "Not joining due to a copy?");
+ unsigned OtherValIdx = SourceLR->ValId;
+ unsigned ThisValIdx = DestLR->ValId;
+
+ Ranges::iterator i = ranges.begin();
+ Ranges::iterator ie = ranges.end();
+ Ranges::const_iterator j = other.ranges.begin();
+ Ranges::const_iterator je = other.ranges.end();
+
+ if (i->start < j->start) {
+ i = std::upper_bound(i, ie, j->start);
+ if (i != ranges.begin()) --i;
+ } else if (j->start < i->start) {
+ j = std::upper_bound(j, je, i->start);
+ if (j != other.ranges.begin()) --j;
+ }
+
+ while (i != ie && j != je) {
+ if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx))
+ Ranges.push_back(&*i);
+
+ if (i->end < j->end)
+ ++i;
+ else
+ ++j;
+ }
+}
+
+
/// extendIntervalEndTo - This method is used when we want to extend the range
/// specified by I to end at the specified endpoint. To do this, we should
// If NewEnd was in the middle of an interval, make sure to get its endpoint.
I->end = std::max(NewEnd, prior(MergeTo)->end);
- // Erase any dead ranges
+ // Erase any dead ranges.
ranges.erase(next(I), MergeTo);
+
+ // If the newly formed range now touches the range after it and if they have
+ // the same value number, merge the two ranges into one range.
+ Ranges::iterator Next = next(I);
+ if (Next != ranges.end() && Next->start <= I->end && Next->ValId == ValId) {
+ I->end = Next->end;
+ ranges.erase(Next);
+ }
}
/// extendIntervalStartTo - This method is used when we want to extend the range
/// specified by I to start at the specified endpoint. To do this, we should
/// merge and eliminate all ranges that this will overlap with.
-LiveInterval::Ranges::iterator
+LiveInterval::Ranges::iterator
LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
assert(I != ranges.end() && "Not a valid interval!");
unsigned ValId = I->ValId;
// Check to make sure that we are not overlapping two live ranges with
// different ValId's.
assert(B->end <= Start &&
- "Cannot overlap two LiveRanges with differing ValID's");
+ "Cannot overlap two LiveRanges with differing ValID's"
+ " (did you def the same reg twice in a MachineInstr?)");
}
}
std::cerr << *this << "\n";
}
-
-std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
- os << "%reg" << li.reg << ',' << li.weight;
- if (li.empty())
- return os << "EMPTY";
-
- os << " = ";
- for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(),
- e = li.ranges.end(); i != e; ++i)
- os << *i;
- return os;
+void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
+ if (MRI && MRegisterInfo::isPhysicalRegister(reg))
+ OS << MRI->getName(reg);
+ else
+ OS << "%reg" << reg;
+
+ OS << ',' << weight;
+
+ if (empty())
+ OS << "EMPTY";
+ else {
+ OS << " = ";
+ for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
+ E = ranges.end(); I != E; ++I)
+ OS << *I;
+ }
}
void LiveInterval::dump() const {
projects / oota-llvm.git / blobdiff