#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
#define LLVM_CODEGEN_LIVEINTERVAL_H
#include "llvm/ADT/IntEqClasses.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include <cassert>
#include <climits>
namespace llvm {
class LiveIntervals;
class MachineInstr;
class MachineRegisterInfo;
class TargetRegisterInfo;
class raw_ostream;
class VNInfo {
private:
enum {
HAS_PHI_KILL = 1,
IS_PHI_DEF = 1 << 1,
IS_UNUSED = 1 << 2
};
unsigned char flags;
public:
typedef BumpPtrAllocator Allocator;
unsigned id;
SlotIndex def;
VNInfo(unsigned i, SlotIndex d)
: flags(0), id(i), def(d)
{ }
VNInfo(unsigned i, const VNInfo &orig)
: flags(orig.flags), id(i), def(orig.def)
{ }
void copyFrom(VNInfo &src) {
flags = src.flags;
def = src.def;
}
unsigned getFlags() const { return flags; }
void setFlags(unsigned flags) { this->flags = flags; }
void mergeFlags(const VNInfo *VNI) {
flags = (flags | VNI->flags) & ~IS_UNUSED;
}
bool hasPHIKill() const { return flags & HAS_PHI_KILL; }
void setHasPHIKill(bool hasKill) {
if (hasKill)
flags |= HAS_PHI_KILL;
else
flags &= ~HAS_PHI_KILL;
}
bool isPHIDef() const { return flags & IS_PHI_DEF; }
void setIsPHIDef(bool phiDef) {
if (phiDef)
flags |= IS_PHI_DEF;
else
flags &= ~IS_PHI_DEF;
}
bool isUnused() const { return flags & IS_UNUSED; }
void setIsUnused(bool unused) {
if (unused)
flags |= IS_UNUSED;
else
flags &= ~IS_UNUSED;
}
};
struct LiveRange {
SlotIndex start; SlotIndex end; VNInfo *valno;
LiveRange(SlotIndex S, SlotIndex E, VNInfo *V)
: start(S), end(E), valno(V) {
assert(S < E && "Cannot create empty or backwards range");
}
bool contains(SlotIndex I) const {
return start <= I && I < end;
}
bool containsRange(SlotIndex S, SlotIndex E) const {
assert((S < E) && "Backwards interval?");
return (start <= S && S < end) && (start < E && E <= end);
}
bool operator<(const LiveRange &LR) const {
return start < LR.start || (start == LR.start && end < LR.end);
}
bool operator==(const LiveRange &LR) const {
return start == LR.start && end == LR.end;
}
void dump() const;
void print(raw_ostream &os) const;
private:
LiveRange(); };
template <> struct isPodLike<LiveRange> { static const bool value = true; };
raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
inline bool operator<(SlotIndex V, const LiveRange &LR) {
return V < LR.start;
}
inline bool operator<(const LiveRange &LR, SlotIndex V) {
return LR.start < V;
}
class LiveInterval {
public:
typedef SmallVector<LiveRange,4> Ranges;
typedef SmallVector<VNInfo*,4> VNInfoList;
const unsigned reg; float weight; Ranges ranges; VNInfoList valnos;
struct InstrSlots {
enum {
LOAD = 0,
USE = 1,
DEF = 2,
STORE = 3,
NUM = 4
};
};
LiveInterval(unsigned Reg, float Weight)
: reg(Reg), weight(Weight) {}
typedef Ranges::iterator iterator;
iterator begin() { return ranges.begin(); }
iterator end() { return ranges.end(); }
typedef Ranges::const_iterator const_iterator;
const_iterator begin() const { return ranges.begin(); }
const_iterator end() const { return ranges.end(); }
typedef VNInfoList::iterator vni_iterator;
vni_iterator vni_begin() { return valnos.begin(); }
vni_iterator vni_end() { return valnos.end(); }
typedef VNInfoList::const_iterator const_vni_iterator;
const_vni_iterator vni_begin() const { return valnos.begin(); }
const_vni_iterator vni_end() const { return valnos.end(); }
iterator advanceTo(iterator I, SlotIndex Pos) {
assert(I != end());
if (Pos >= endIndex())
return end();
while (I->end <= Pos) ++I;
return I;
}
iterator find(SlotIndex Pos);
const_iterator find(SlotIndex Pos) const {
return const_cast<LiveInterval*>(this)->find(Pos);
}
void clear() {
valnos.clear();
ranges.clear();
}
bool hasAtLeastOneValue() const { return !valnos.empty(); }
bool containsOneValue() const { return valnos.size() == 1; }
unsigned getNumValNums() const { return (unsigned)valnos.size(); }
inline VNInfo *getValNumInfo(unsigned ValNo) {
return valnos[ValNo];
}
inline const VNInfo *getValNumInfo(unsigned ValNo) const {
return valnos[ValNo];
}
bool containsValue(const VNInfo *VNI) const {
return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id);
}
VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) {
VNInfo *VNI =
new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def);
valnos.push_back(VNI);
return VNI;
}
VNInfo *createValueCopy(const VNInfo *orig,
VNInfo::Allocator &VNInfoAllocator) {
VNInfo *VNI =
new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
valnos.push_back(VNI);
return VNI;
}
void RenumberValues(LiveIntervals &lis);
bool isOnlyLROfValNo(const LiveRange *LR) {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
const LiveRange *Tmp = I;
if (Tmp != LR && Tmp->valno == LR->valno)
return false;
}
return true;
}
VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2);
void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo);
void MergeValueInAsValue(const LiveInterval &RHS,
const VNInfo *RHSValNo, VNInfo *LHSValNo);
void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
VNInfo::Allocator &VNInfoAllocator);
bool empty() const { return ranges.empty(); }
SlotIndex beginIndex() const {
assert(!empty() && "Call to beginIndex() on empty interval.");
return ranges.front().start;
}
SlotIndex endIndex() const {
assert(!empty() && "Call to endIndex() on empty interval.");
return ranges.back().end;
}
bool expiredAt(SlotIndex index) const {
return index >= endIndex();
}
bool liveAt(SlotIndex index) const {
const_iterator r = find(index);
return r != end() && r->start <= index;
}
bool killedAt(SlotIndex index) const {
const_iterator r = find(index.getRegSlot(true));
return r != end() && r->end == index;
}
bool killedInRange(SlotIndex Start, SlotIndex End) const;
const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
const_iterator I = FindLiveRangeContaining(Idx);
return I == end() ? 0 : &*I;
}
LiveRange *getLiveRangeContaining(SlotIndex Idx) {
iterator I = FindLiveRangeContaining(Idx);
return I == end() ? 0 : &*I;
}
const LiveRange *getLiveRangeBefore(SlotIndex Idx) const {
return getLiveRangeContaining(Idx.getPrevSlot());
}
LiveRange *getLiveRangeBefore(SlotIndex Idx) {
return getLiveRangeContaining(Idx.getPrevSlot());
}
VNInfo *getVNInfoAt(SlotIndex Idx) const {
const_iterator I = FindLiveRangeContaining(Idx);
return I == end() ? 0 : I->valno;
}
VNInfo *getVNInfoBefore(SlotIndex Idx) const {
const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot());
return I == end() ? 0 : I->valno;
}
iterator FindLiveRangeContaining(SlotIndex Idx) {
iterator I = find(Idx);
return I != end() && I->start <= Idx ? I : end();
}
const_iterator FindLiveRangeContaining(SlotIndex Idx) const {
const_iterator I = find(Idx);
return I != end() && I->start <= Idx ? I : end();
}
VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
bool overlaps(const LiveInterval& other) const {
if (other.empty())
return false;
return overlapsFrom(other, other.begin());
}
bool overlaps(SlotIndex Start, SlotIndex End) const;
bool overlapsFrom(const LiveInterval& other, const_iterator I) const;
void addRange(LiveRange LR) {
addRangeFrom(LR, ranges.begin());
}
VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
void join(LiveInterval &Other,
const int *ValNoAssignments,
const int *RHSValNoAssignments,
SmallVector<VNInfo*, 16> &NewVNInfo,
MachineRegisterInfo *MRI);
bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const {
const_iterator r = find(Start);
return r != end() && r->containsRange(Start, End);
}
void removeRange(SlotIndex Start, SlotIndex End,
bool RemoveDeadValNo = false);
void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
removeRange(LR.start, LR.end, RemoveDeadValNo);
}
void removeValNo(VNInfo *ValNo);
unsigned getSize() const;
bool isZeroLength(SlotIndexes *Indexes) const {
for (const_iterator i = begin(), e = end(); i != e; ++i)
if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() <
i->end.getBaseIndex())
return false;
return true;
}
bool isSpillable() const {
return weight != HUGE_VALF;
}
void markNotSpillable() {
weight = HUGE_VALF;
}
void ComputeJoinedWeight(const LiveInterval &Other);
bool operator<(const LiveInterval& other) const {
const SlotIndex &thisIndex = beginIndex();
const SlotIndex &otherIndex = other.beginIndex();
return (thisIndex < otherIndex ||
(thisIndex == otherIndex && reg < other.reg));
}
void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const;
void dump() const;
private:
Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
void markValNoForDeletion(VNInfo *V);
LiveInterval& operator=(const LiveInterval& rhs);
};
inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {
LI.print(OS);
return OS;
}
class ConnectedVNInfoEqClasses {
LiveIntervals &LIS;
IntEqClasses EqClass;
void Connect(unsigned a, unsigned b);
unsigned Renumber();
public:
explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {}
unsigned Classify(const LiveInterval *LI);
unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; }
void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI);
};
}
#endif