LiveIntervalUnion.h [plain text]
#ifndef LLVM_CODEGEN_LIVEINTERVALUNION
#define LLVM_CODEGEN_LIVEINTERVALUNION
#include "llvm/ADT/IntervalMap.h"
#include "llvm/CodeGen/LiveInterval.h"
#include <algorithm>
namespace llvm {
class MachineLoopRange;
class TargetRegisterInfo;
#ifndef NDEBUG
template <unsigned Element> class SparseBitVector;
typedef SparseBitVector<128> LiveVirtRegBitSet;
#endif
inline bool
overlap(const LiveRange &VRSeg,
const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) {
return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end;
}
class LiveIntervalUnion {
typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments;
public:
typedef LiveSegments::iterator SegmentIter;
typedef LiveSegments::Allocator Allocator;
class InterferenceResult;
class Query;
private:
const unsigned RepReg; unsigned Tag; LiveSegments Segments;
public:
LiveIntervalUnion(unsigned r, Allocator &a) : RepReg(r), Tag(0), Segments(a)
{}
SegmentIter begin() { return Segments.begin(); }
SegmentIter end() { return Segments.end(); }
SegmentIter find(SlotIndex x) { return Segments.find(x); }
bool empty() const { return Segments.empty(); }
SlotIndex startIndex() const { return Segments.start(); }
typedef LiveSegments Map;
const Map &getMap() { return Segments; }
unsigned getTag() const { return Tag; }
bool changedSince(unsigned tag) const { return tag != Tag; }
void unify(LiveInterval &VirtReg);
void extract(LiveInterval &VirtReg);
void clear() { Segments.clear(); ++Tag; }
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
#ifndef NDEBUG
void verify(LiveVirtRegBitSet& VisitedVRegs);
#endif
class InterferenceResult {
friend class Query;
LiveInterval::iterator VirtRegI; SegmentIter LiveUnionI;
InterferenceResult(LiveInterval::iterator VRegI, SegmentIter UnionI)
: VirtRegI(VRegI), LiveUnionI(UnionI) {}
public:
InterferenceResult(): VirtRegI(), LiveUnionI() {}
SlotIndex start() const {
return std::max(VirtRegI->start, LiveUnionI.start());
}
SlotIndex stop() const {
return std::min(VirtRegI->end, LiveUnionI.stop());
}
LiveInterval *interference() const { return LiveUnionI.value(); }
LiveInterval::iterator virtRegPos() const { return VirtRegI; }
const SegmentIter &liveUnionPos() const { return LiveUnionI; }
bool operator==(const InterferenceResult &IR) const {
return VirtRegI == IR.VirtRegI && LiveUnionI == IR.LiveUnionI;
}
bool operator!=(const InterferenceResult &IR) const {
return !operator==(IR);
}
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
};
class Query {
LiveIntervalUnion *LiveUnion;
LiveInterval *VirtReg;
InterferenceResult FirstInterference;
SmallVector<LiveInterval*,4> InterferingVRegs;
bool CheckedFirstInterference;
bool SeenAllInterferences;
bool SeenUnspillableVReg;
unsigned Tag, UserTag;
public:
Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {}
Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false),
SeenAllInterferences(false), SeenUnspillableVReg(false)
{}
void clear() {
LiveUnion = NULL;
VirtReg = NULL;
InterferingVRegs.clear();
CheckedFirstInterference = false;
SeenAllInterferences = false;
SeenUnspillableVReg = false;
Tag = 0;
UserTag = 0;
}
void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) {
assert(VReg && LIU && "Invalid arguments");
if (UserTag == UTag && VirtReg == VReg &&
LiveUnion == LIU && !LIU->changedSince(Tag)) {
return;
}
clear();
LiveUnion = LIU;
VirtReg = VReg;
Tag = LIU->getTag();
UserTag = UTag;
}
LiveInterval &virtReg() const {
assert(VirtReg && "uninitialized");
return *VirtReg;
}
bool isInterference(const InterferenceResult &IR) const {
if (IR.VirtRegI != VirtReg->end()) {
assert(overlap(*IR.VirtRegI, IR.LiveUnionI) &&
"invalid segment iterators");
return true;
}
return false;
}
bool checkInterference() { return isInterference(firstInterference()); }
const InterferenceResult &firstInterference();
bool nextInterference(InterferenceResult &IR) const;
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX,
float MaxWeight = HUGE_VALF);
bool isSeenInterference(LiveInterval *VReg) const;
bool seenAllInterferences() const { return SeenAllInterferences; }
bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
return InterferingVRegs;
}
bool checkLoopInterference(MachineLoopRange*);
void print(raw_ostream &OS, const TargetRegisterInfo *TRI);
private:
Query(const Query&); void operator=(const Query&);
void findIntersection(InterferenceResult &IR) const;
};
};
}
#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)