Add support for inactive intervals. This effectively reuses registers
for live ranges that fall into assigned registers' holes.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10566 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 74426d5..2a0ab9e 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -32,6 +32,7 @@
#include "Support/Debug.h"
#include "Support/DepthFirstIterator.h"
#include "Support/Statistic.h"
+#include <limits>
#include <iostream>
using namespace llvm;
@@ -278,13 +279,20 @@
if (!mop.isRegister())
continue;
+ unsigned reg = mop.getAllocatedRegNum();
+ // handle defs - build intervals
if (mop.isDef()) {
- unsigned reg = mop.getAllocatedRegNum();
if (reg < MRegisterInfo::FirstVirtualRegister)
handlePhysicalRegisterDef(mbb, mi, reg);
else
handleVirtualRegisterDef(mbb, mi, reg);
}
+
+ // update weights
+ Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
+ if (r2iit != r2iMap_.end() &&
+ reg >= MRegisterInfo::FirstVirtualRegister)
+ ++intervals_[r2iit->second].weight;
}
}
}
@@ -294,6 +302,14 @@
std::ostream_iterator<Interval>(std::cerr, "\n")));
}
+LiveIntervals::Interval::Interval(unsigned r)
+ : reg(r),
+ weight((r < MRegisterInfo::FirstVirtualRegister ?
+ std::numeric_limits<unsigned>::max() : 0))
+{
+
+}
+
void LiveIntervals::Interval::addRange(unsigned start, unsigned end)
{
DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n");
@@ -330,10 +346,39 @@
}
}
+bool LiveIntervals::Interval::liveAt(unsigned index) const
+{
+ Ranges::const_iterator r = ranges.begin();
+ while (r != ranges.end() && index < r->second) {
+ if (index >= r->first)
+ return true;
+ ++r;
+ }
+ return false;
+}
+
+bool LiveIntervals::Interval::overlaps(const Interval& other) const
+{
+ std::vector<bool> bitMap(end(), false);
+ for (Ranges::const_iterator r = ranges.begin(); r != ranges.end(); ++r) {
+ for (unsigned i = r->first; i < r->second; ++i)
+ bitMap[i] = true;
+ }
+ for (Ranges::const_iterator r = other.ranges.begin();
+ r != other.ranges.end(); ++r) {
+ for (unsigned i = r->first;
+ i < r->second && i < bitMap.size(); ++i)
+ if (bitMap[i])
+ return true;
+ }
+
+ return false;
+}
+
std::ostream& llvm::operator<<(std::ostream& os,
const LiveIntervals::Interval& li)
{
- os << "%reg" << li.reg << " = ";
+ os << "%reg" << li.reg << ',' << li.weight << " = ";
for (LiveIntervals::Interval::Ranges::const_iterator
i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
os << "[" << i->first << "," << i->second << "]";