using namespace llvm;
// Merge a LiveInterval's segments. Guarantee no overlaps.
+//
+// Consider coalescing adjacent segments to save space, even though it makes
+// extraction more complicated.
void LiveIntervalUnion::unify(LiveInterval &lvr) {
// Add this live virtual register to the union
LiveVirtRegs::iterator pos = std::upper_bound(lvrs_.begin(), lvrs_.end(),
LiveSegment segment(lvrI->start, lvrI->end, lvr);
segPos = segments_.insert(segPos, segment);
assert(*segPos == segment && "need equal val for equal key");
+#ifndef NDEBUG
+ // check for overlap (inductively)
+ if (segPos != segments_.begin()) {
+ SegmentIter prevPos = segPos;
+ --prevPos;
+ assert(prevPos->end <= segment.start && "overlapping segments" );
+ }
+ SegmentIter nextPos = segPos;
+ ++nextPos;
+ if (nextPos != segments_.end())
+ assert(segment.end <= nextPos->start && "overlapping segments" );
+#endif // NDEBUG
}
}
-namespace {
-
-// Keep LVRs sorted for fast membership test and extraction.
-struct LessReg
- : public std::binary_function<LiveInterval*, LiveInterval*, bool> {
- bool operator()(const LiveInterval *left, const LiveInterval *right) const {
- return left->reg < right->reg;
- }
-};
-
// Low-level helper to find the first segment in the range [segI,segEnd) that
// intersects with a live virtual register segment, or segI.start >= lvr.end
//
// Assuming intervals are disjoint, if an intersection exists, it must be the
// segment found or immediately behind it. We continue reverse iterating to
// return the first overlap.
-//
-// FIXME: support extract(), handle tombstones of extracted lvrs.
typedef LiveIntervalUnion::SegmentIter SegmentIter;
-SegmentIter upperBound(SegmentIter segBegin,
+static SegmentIter upperBound(SegmentIter segBegin,
SegmentIter segEnd,
const LiveRange &lvrSeg) {
assert(lvrSeg.end > segBegin->start && "segment iterator precondition");
}
return segI;
}
-} // end anonymous namespace
// Private interface accessed by Query.
//
namespace llvm {
-// A LiveSegment is a copy of a LiveRange object used within
-// LiveIntervalUnion. LiveSegment additionally contains a pointer to its
-// original live virtual register (LiveInterval). This allows quick lookup of
-// the live virtual register as we iterate over live segments in a union. Note
-// that LiveRange is misnamed and actually represents only a single contiguous
-// interval within a virtual register's liveness. To limit confusion, in this
-// file we refer it as a live segment.
+/// A LiveSegment is a copy of a LiveRange object used within
+/// LiveIntervalUnion. LiveSegment additionally contains a pointer to its
+/// original live virtual register (LiveInterval). This allows quick lookup of
+/// the live virtual register as we iterate over live segments in a union. Note
+/// that LiveRange is misnamed and actually represents only a single contiguous
+/// interval within a virtual register's liveness. To limit confusion, in this
+/// file we refer it as a live segment.
+///
+/// Note: This currently represents a half-open interval [start,end).
+/// If LiveRange is modified to represent a closed interval, so should this.
struct LiveSegment {
SlotIndex start;
SlotIndex end;
return !operator==(ls);
}
- bool operator<(const LiveSegment &ls) const {
- return start < ls.start || (start == ls.start && end < ls.end);
- }
+ // Order segments by starting point only--we expect them to be disjoint.
+ bool operator<(const LiveSegment &ls) const { return start < ls.start; }
};
-/// Compare a live virtual register segment to a LiveIntervalUnion segment.
-inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) {
- return lvrSeg.start < liuSeg.end && liuSeg.start < lvrSeg.end;
-}
-
inline bool operator<(SlotIndex V, const LiveSegment &ls) {
return V < ls.start;
}
return ls.start < V;
}
+/// Compare a live virtual register segment to a LiveIntervalUnion segment.
+inline bool overlap(const LiveRange &lvrSeg, const LiveSegment &liuSeg) {
+ return lvrSeg.start < liuSeg.end && liuSeg.start < lvrSeg.end;
+}
+
/// Union of live intervals that are strong candidates for coalescing into a
/// single register (either physical or virtual depending on the context). We
/// expect the constituent live intervals to be disjoint, although we may
public:
// default ctor avoids placement new
LiveIntervalUnion() : repReg_(0) {}
-
+
+ // Initialize the union by associating it with a representative register
+ // number.
void init(unsigned repReg) { repReg_ = repReg; }
+ // Iterate over all segments in the union of live virtual registers ordered
+ // by their starting position.
SegmentIter begin() { return segments_.begin(); }
SegmentIter end() { return segments_.end(); }
- /// FIXME: !!!!!!!!!!! Keeps a non-const ref
+ // Add a live virtual register to this union and merge its segments.
+ // Holds a nonconst reference to the LVR for later maniplution.
void unify(LiveInterval &lvr);
// FIXME: needed by RegAllocGreedy
#ifndef LLVM_CODEGEN_REGALLOCBASE
#define LLVM_CODEGEN_REGALLOCBASE
-#include "LiveIntervalUnion.h"
-#include "VirtRegMap.h"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/OwningPtr.h"
-#include <vector>
-#include <queue>
namespace llvm {
+template<typename T> class SmallVectorImpl;
+class TargetRegisterInfo;
class VirtRegMap;
+class LiveIntervals;
+
+// Heuristic that determines the priority of assigning virtual to physical
+// registers. The main impact of the heuristic is expected to be compile time.
+// The default is to simply compare spill weights.
+struct LessSpillWeightPriority
+ : public std::binary_function<LiveInterval,LiveInterval, bool> {
+ bool operator()(const LiveInterval *left, const LiveInterval *right) const {
+ return left->weight < right->weight;
+ }
+};
+
+// Forward declare a priority queue of live virtual registers. If an
+// implementation needs to prioritize by anything other than spill weight, then
+// this will become an abstract base class with virtual calls to push/get.
+class LiveVirtRegQueue;
/// RegAllocBase provides the register allocation driver and interface that can
/// be extended to add interesting heuristics.
/// standard comparator.
class RegAllocBase {
protected:
- typedef SmallVector<LiveInterval*, 4> LiveVirtRegs;
- typedef LiveVirtRegs::iterator LVRIter;
-
// Array of LiveIntervalUnions indexed by physical register.
class LIUArray {
unsigned nRegs_;
// A RegAlloc pass should call this before allocatePhysRegs.
void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis);
- // The top-level driver. Specialize with the comparator that determines the
- // priority of assigning live virtual registers. The output is a VirtRegMap
- // that us updated with physical register assignments.
- template<typename LICompare>
- void allocatePhysRegs(LICompare liCompare);
+ // The top-level driver. The output is a VirtRegMap that us updated with
+ // physical register assignments.
+ //
+ // If an implementation wants to override the LiveInterval comparator, we
+ // should modify this interface to allow passing in an instance derived from
+ // LiveVirtRegQueue.
+ void allocatePhysRegs();
// A RegAlloc pass should override this to provide the allocation heuristics.
- // Each call must guarantee forward progess by returning an available
- // PhysReg or new set of split LiveVirtRegs. It is up to the splitter to
+ // Each call must guarantee forward progess by returning an available PhysReg
+ // or new set of split live virtual registers. It is up to the splitter to
// converge quickly toward fully spilled live ranges.
virtual unsigned selectOrSplit(LiveInterval &lvr,
- LiveVirtRegs &splitLVRs) = 0;
+ SmallVectorImpl<LiveInterval*> &splitLVRs) = 0;
// A RegAlloc pass should call this when PassManager releases its memory.
virtual void releaseMemory();
bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg);
private:
- template<typename PQ>
- void seedLiveVirtRegs(PQ &lvrQ);
+ void seedLiveVirtRegs(LiveVirtRegQueue &lvrQ);
};
-// Heuristic that determines the priority of assigning virtual to physical
-// registers. The main impact of the heuristic is expected to be compile time.
-// The default is to simply compare spill weights.
-struct LessSpillWeightPriority
- : public std::binary_function<LiveInterval,LiveInterval, bool> {
- bool operator()(const LiveInterval *left, const LiveInterval *right) const {
- return left->weight < right->weight;
- }
-};
-
-// Visit all the live virtual registers. If they are already assigned to a
-// physical register, unify them with the corresponding LiveIntervalUnion,
-// otherwise push them on the priority queue for later assignment.
-template<typename PQ>
-void RegAllocBase::seedLiveVirtRegs(PQ &lvrQ) {
- for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
- liItr != liEnd; ++liItr) {
- unsigned reg = liItr->first;
- LiveInterval &li = *liItr->second;
- if (TargetRegisterInfo::isPhysicalRegister(reg)) {
- physReg2liu_[reg].unify(li);
- }
- else {
- lvrQ.push(&li);
- }
- }
-}
-
-// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
-// selectOrSplit implementation.
-template<typename LICompare>
-void RegAllocBase::allocatePhysRegs(LICompare liCompare) {
- typedef std::priority_queue
- <LiveInterval*, std::vector<LiveInterval*>, LICompare> LiveVirtRegQueue;
-
- LiveVirtRegQueue lvrQ(liCompare);
- seedLiveVirtRegs(lvrQ);
- while (!lvrQ.empty()) {
- LiveInterval *lvr = lvrQ.top();
- lvrQ.pop();
- LiveVirtRegs splitLVRs;
- unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
- if (availablePhysReg) {
- assert(splitLVRs.empty() && "inconsistent splitting");
- assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
- vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
- physReg2liu_[availablePhysReg].unify(*lvr);
- }
- else {
- for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
- lvrI != lvrEnd; ++lvrI ) {
- assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
- "expect split value in virtual register");
- lvrQ.push(*lvrI);
- }
- }
- }
-}
-
} // end namespace llvm
#endif // !defined(LLVM_CODEGEN_REGALLOCBASE)
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
+#include "LiveIntervalUnion.h"
#include "RegAllocBase.h"
#include "RenderMachineFunction.h"
#include "Spiller.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "VirtRegMap.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+
+#include <vector>
+#include <queue>
+
using namespace llvm;
static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
virtual void releaseMemory();
- virtual unsigned selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs);
+ virtual unsigned selectOrSplit(LiveInterval &lvr,
+ SmallVectorImpl<LiveInterval*> &splitLVRs);
/// Perform register allocation.
virtual bool runOnMachineFunction(MachineFunction &mf);
#endif
INITIALIZE_PASS_END(RABasic, "basic-regalloc",
"Basic Register Allocator", false, false)
-#endif // INITIALIZE_PASS
+#endif // disable INITIALIZE_PASS
RABasic::RABasic(): MachineFunctionPass(ID) {
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
physReg2liu_.clear();
}
+namespace llvm {
+/// This class defines a queue of live virtual registers prioritized by spill
+/// weight. The heaviest vreg is popped first.
+///
+/// Currently, this is trivial wrapper that gives us an opaque type in the
+/// header, but we may later give it a virtual interface for register allocators
+/// to override the priority queue comparator.
+class LiveVirtRegQueue {
+ typedef std::priority_queue
+ <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
+ PQ pq_;
+
+public:
+ // Is the queue empty?
+ bool empty() { return pq_.empty(); }
+
+ // Get the highest priority lvr (top + pop)
+ LiveInterval *get() {
+ LiveInterval *lvr = pq_.top();
+ pq_.pop();
+ return lvr;
+ }
+ // Add this lvr to the queue
+ void push(LiveInterval *lvr) {
+ pq_.push(lvr);
+ }
+};
+} // end namespace llvm
+
+// Visit all the live virtual registers. If they are already assigned to a
+// physical register, unify them with the corresponding LiveIntervalUnion,
+// otherwise push them on the priority queue for later assignment.
+void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
+ for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
+ liItr != liEnd; ++liItr) {
+ unsigned reg = liItr->first;
+ LiveInterval &li = *liItr->second;
+ if (TargetRegisterInfo::isPhysicalRegister(reg)) {
+ physReg2liu_[reg].unify(li);
+ }
+ else {
+ lvrQ.push(&li);
+ }
+ }
+}
+
+// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
+// selectOrSplit implementation.
+void RegAllocBase::allocatePhysRegs() {
+ LiveVirtRegQueue lvrQ;
+ seedLiveVirtRegs(lvrQ);
+ while (!lvrQ.empty()) {
+ LiveInterval *lvr = lvrQ.get();
+ typedef SmallVector<LiveInterval*, 4> LVRVec;
+ LVRVec splitLVRs;
+ unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
+ if (availablePhysReg) {
+ assert(splitLVRs.empty() && "inconsistent splitting");
+ assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
+ vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
+ physReg2liu_[availablePhysReg].unify(*lvr);
+ }
+ else {
+ for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
+ lvrI != lvrEnd; ++lvrI) {
+ assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
+ "expect split value in virtual register");
+ lvrQ.push(*lvrI);
+ }
+ }
+ }
+}
+
// Check if this live virtual reg interferes with a physical register. If not,
// then check for interference on each register that aliases with the physical
// register.
// available register. So, the number of interference tests in the worst case is
// |vregs| * |machineregs|. And since the number of interference tests is
// minimal, there is no value in caching them.
-unsigned RABasic::selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs) {
+unsigned RABasic::selectOrSplit(LiveInterval &lvr,
+ SmallVectorImpl<LiveInterval*> &splitLVRs) {
// Check for an available reg in this class.
const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
spiller_.reset(createSpiller(*this, *mf_, *vrm_));
- allocatePhysRegs(LessSpillWeightPriority());
+ allocatePhysRegs();
// Diagnostic output before rewriting
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
// Run rewriter
std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
+
+ // The pass output is in VirtRegMap. Release all the transient data.
+ releaseMemory();
return true;
}
projects / oota-llvm.git / commitdiff