#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
+#include "llvm/Support/AlignOf.h"
#include <iosfwd>
#include <cassert>
#include <climits>
/// Care must be taken in interpreting the def index of the value. The
/// following rules apply:
///
- /// If the isDefAccurate() method returns false then the def index does not
- /// actually point to the defining MachineInstr, or even (necessarily) a
- /// valid MachineInstr at all. In general such a def index should not be
- /// used as an index to obtain a MachineInstr. The exception is Values
- /// defined by PHI instructions, after PHI elimination has occured. In this
- /// case the def should point to the start of the block in which the PHI
- /// existed. This fact can be used to insert code dealing with the PHI value
- /// at the merge point (e.g. to spill or split it).
+ /// If the isDefAccurate() method returns false then def does not contain the
+ /// index of the defining MachineInstr, or even (necessarily) to a
+ /// MachineInstr at all. In general such a def index is not meaningful
+ /// and should not be used. The exception is that, for values originally
+ /// defined by PHI instructions, after PHI elimination def will contain the
+ /// index of the MBB in which the PHI originally existed. This can be used
+ /// to insert code (spills or copies) which deals with the value, which will
+ /// be live in to the block.
class VNInfo {
private:
unsigned char flags;
public:
+ /// Holds information about individual kills.
+ struct KillInfo {
+ bool isPHIKill : 1;
+ unsigned killIdx : 31;
+
+ KillInfo(bool isPHIKill, unsigned killIdx)
+ : isPHIKill(isPHIKill), killIdx(killIdx) {
+
+ assert(killIdx != 0 && "Zero kill indices are no longer permitted.");
+ }
+
+ };
+
+ typedef SmallVector<KillInfo, 4> KillSet;
+
/// The ID number of this value.
unsigned id;
/// The index of the defining instruction (if isDefAccurate() returns true).
unsigned def;
MachineInstr *copy;
- SmallVector<unsigned, 4> kills;
+ KillSet kills;
VNInfo()
: flags(IS_UNUSED), id(~1U), def(0), copy(0) {}
};
+ inline bool operator<(const VNInfo::KillInfo &k1, const VNInfo::KillInfo &k2) {
+ return k1.killIdx < k2.killIdx;
+ }
+
+ inline bool operator<(const VNInfo::KillInfo &k, unsigned idx) {
+ return k.killIdx < idx;
+ }
+
+ inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) {
+ return idx < k.killIdx;
+ }
+
/// LiveRange structure - This represents a simple register range in the
/// program, with an inclusive start point and an exclusive end point.
/// These ranges are rendered as [start,end).
/// LiveInterval - This class represents some number of live ranges for a
/// register or value. This class also contains a bit of register allocator
/// state.
- struct LiveInterval {
+ class LiveInterval {
+ public:
+
typedef SmallVector<LiveRange,4> Ranges;
typedef SmallVector<VNInfo*,4> VNInfoList;
float weight; // weight of this interval
Ranges ranges; // the ranges in which this register is live
VNInfoList valnos; // value#'s
-
- public:
struct InstrSlots {
enum {
assert(MIIdx != ~0u && MIIdx != ~1u &&
"PHI def / unused flags should now be passed explicitly.");
-#ifdef __GNUC__
- unsigned Alignment = (unsigned)__alignof__(VNInfo);
-#else
- // FIXME: ugly.
- unsigned Alignment = 8;
-#endif
VNInfo *VNI =
static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
- Alignment));
+ alignof<VNInfo>()));
new (VNI) VNInfo((unsigned)valnos.size(), MIIdx, CopyMI);
VNI->setIsDefAccurate(isDefAccurate);
valnos.push_back(VNI);
/// for the Value number.
VNInfo *createValueCopy(const VNInfo *orig, BumpPtrAllocator &VNInfoAllocator) {
-#ifdef __GNUC__
- unsigned Alignment = (unsigned)__alignof__(VNInfo);
-#else
- // FIXME: ugly.
- unsigned Alignment = 8;
-#endif
VNInfo *VNI =
static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
- Alignment));
+ alignof<VNInfo>()));
new (VNI) VNInfo((unsigned)valnos.size(), *orig);
valnos.push_back(VNI);
/// addKill - Add a kill instruction index to the specified value
/// number.
- static void addKill(VNInfo *VNI, unsigned KillIdx) {
- SmallVector<unsigned, 4> &kills = VNI->kills;
+ static void addKill(VNInfo *VNI, unsigned KillIdx, bool phiKill) {
+ VNInfo::KillSet &kills = VNI->kills;
+ VNInfo::KillInfo newKill(phiKill, KillIdx);
if (kills.empty()) {
- kills.push_back(KillIdx);
+ kills.push_back(newKill);
} else {
- SmallVector<unsigned, 4>::iterator
- I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
- kills.insert(I, KillIdx);
+ VNInfo::KillSet::iterator
+ I = std::lower_bound(kills.begin(), kills.end(), newKill);
+ kills.insert(I, newKill);
}
}
/// addKills - Add a number of kills into the VNInfo kill vector. If this
/// interval is live at a kill point, then the kill is not added.
- void addKills(VNInfo *VNI, const SmallVector<unsigned, 4> &kills) {
+ void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
i != e; ++i) {
- unsigned KillIdx = kills[i];
- if (!liveBeforeAndAt(KillIdx)) {
- SmallVector<unsigned, 4>::iterator
- I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), KillIdx);
- VNI->kills.insert(I, KillIdx);
+ const VNInfo::KillInfo &Kill = kills[i];
+ if (!liveBeforeAndAt(Kill.killIdx)) {
+ VNInfo::KillSet::iterator
+ I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
+ VNI->kills.insert(I, Kill);
}
}
}
/// removeKill - Remove the specified kill from the list of kills of
/// the specified val#.
static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
- SmallVector<unsigned, 4> &kills = VNI->kills;
- SmallVector<unsigned, 4>::iterator
+ VNInfo::KillSet &kills = VNI->kills;
+ VNInfo::KillSet::iterator
I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
- if (I != kills.end() && *I == KillIdx) {
+ if (I != kills.end() && I->killIdx == KillIdx) {
kills.erase(I);
return true;
}
/// removeKills - Remove all the kills in specified range
/// [Start, End] of the specified val#.
static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
- SmallVector<unsigned, 4> &kills = VNI->kills;
- SmallVector<unsigned, 4>::iterator
+ VNInfo::KillSet &kills = VNI->kills;
+
+ VNInfo::KillSet::iterator
I = std::lower_bound(kills.begin(), kills.end(), Start);
- SmallVector<unsigned, 4>::iterator
+ VNInfo::KillSet::iterator
E = std::upper_bound(kills.begin(), kills.end(), End);
kills.erase(I, E);
}
/// isKill - Return true if the specified index is a kill of the
/// specified val#.
static bool isKill(const VNInfo *VNI, unsigned KillIdx) {
- const SmallVector<unsigned, 4> &kills = VNI->kills;
- SmallVector<unsigned, 4>::const_iterator
+ const VNInfo::KillSet &kills = VNI->kills;
+ VNInfo::KillSet::const_iterator
I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
- return I != kills.end() && *I == KillIdx;
+ return I != kills.end() && I->killIdx == KillIdx;
}
/// isOnlyLROfValNo - Return true if the specified live range is the only
/// one defined by the its val#.
- bool isOnlyLROfValNo( const LiveRange *LR) {
+ 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 I == end() ? 0 : &*I;
}
+ /// getLiveRangeContaining - Return the live range that contains the
+ /// specified index, or null if there is none.
+ LiveRange *getLiveRangeContaining(unsigned Idx) {
+ iterator I = FindLiveRangeContaining(Idx);
+ return I == end() ? 0 : &*I;
+ }
+
/// FindLiveRangeContaining - Return an iterator to the live range that
/// contains the specified index, or end() if there is none.
const_iterator FindLiveRangeContaining(unsigned Idx) const;
void dump() const;
private:
+
Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
+
};
inline std::ostream &operator<<(std::ostream &OS, const LiveInterval &LI) {
projects / oota-llvm.git / blobdiff