#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
#define LLVM_CODEGEN_LIVEINTERVAL_H
-#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/SmallVector.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;
-
- /// LiveIndex - An opaque wrapper around machine indexes.
- class LiveIndex {
- friend class VNInfo;
- friend class LiveInterval;
- friend class LiveIntervals;
- friend struct DenseMapInfo<LiveIndex>;
-
- public:
-
- enum Slot { LOAD, USE, DEF, STORE, NUM };
-
- private:
-
- unsigned index;
-
- static const unsigned PHI_BIT = 1 << 31;
-
- public:
-
- /// Construct a default LiveIndex pointing to a reserved index.
- LiveIndex() : index(0) {}
-
- /// Construct an index from the given index, pointing to the given slot.
- LiveIndex(LiveIndex m, Slot s)
- : index((m.index / NUM) * NUM + s) {}
-
- /// Print this index to the given raw_ostream.
- void print(raw_ostream &os) const;
-
- /// Compare two LiveIndex objects for equality.
- bool operator==(LiveIndex other) const {
- return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT));
- }
- /// Compare two LiveIndex objects for inequality.
- bool operator!=(LiveIndex other) const {
- return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT));
- }
-
- /// Compare two LiveIndex objects. Return true if the first index
- /// is strictly lower than the second.
- bool operator<(LiveIndex other) const {
- return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT));
- }
- /// Compare two LiveIndex objects. Return true if the first index
- /// is lower than, or equal to, the second.
- bool operator<=(LiveIndex other) const {
- return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT));
- }
-
- /// Compare two LiveIndex objects. Return true if the first index
- /// is greater than the second.
- bool operator>(LiveIndex other) const {
- return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT));
- }
-
- /// Compare two LiveIndex objects. Return true if the first index
- /// is greater than, or equal to, the second.
- bool operator>=(LiveIndex other) const {
- return ((index & ~PHI_BIT) >= (other.index & ~PHI_BIT));
- }
-
- /// Returns true if this index represents a load.
- bool isLoad() const {
- return ((index % NUM) == LOAD);
- }
-
- /// Returns true if this index represents a use.
- bool isUse() const {
- return ((index % NUM) == USE);
- }
-
- /// Returns true if this index represents a def.
- bool isDef() const {
- return ((index % NUM) == DEF);
- }
-
- /// Returns true if this index represents a store.
- bool isStore() const {
- return ((index % NUM) == STORE);
- }
-
- /// Returns the slot for this LiveIndex.
- Slot getSlot() const {
- return static_cast<Slot>(index % NUM);
- }
-
- /// Returns true if this index represents a non-PHI use/def.
- bool isNonPHIIndex() const {
- return ((index & PHI_BIT) == 0);
- }
-
- /// Returns true if this index represents a PHI use/def.
- bool isPHIIndex() const {
- return ((index & PHI_BIT) == PHI_BIT);
- }
-
- private:
-
- /// Construct an index from the given index, with its PHI kill marker set.
- LiveIndex(bool phi, LiveIndex o) : index(o.index) {
- if (phi)
- index |= PHI_BIT;
- else
- index &= ~PHI_BIT;
- }
-
- explicit LiveIndex(unsigned idx)
- : index(idx & ~PHI_BIT) {}
-
- LiveIndex(bool phi, unsigned idx)
- : index(idx & ~PHI_BIT) {
- if (phi)
- index |= PHI_BIT;
- }
-
- LiveIndex(bool phi, unsigned idx, Slot slot)
- : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) {
- if (phi)
- index |= PHI_BIT;
- }
-
- LiveIndex nextSlot_() const {
- assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) &&
- "Index out of bounds.");
- return LiveIndex(index + 1);
- }
-
- LiveIndex nextIndex_() const {
- assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) &&
- "Index out of bounds.");
- return LiveIndex(index + NUM);
- }
-
- LiveIndex prevSlot_() const {
- assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) &&
- "Index out of bounds.");
- return LiveIndex(index - 1);
- }
-
- LiveIndex prevIndex_() const {
- assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) &&
- "Index out of bounds.");
- return LiveIndex(index - NUM);
- }
-
- int distance(LiveIndex other) const {
- return (other.index & ~PHI_BIT) - (index & ~PHI_BIT);
- }
-
- /// Returns an unsigned number suitable as an index into a
- /// vector over all instructions.
- unsigned getVecIndex() const {
- return (index & ~PHI_BIT) / NUM;
- }
-
- /// Scale this index by the given factor.
- LiveIndex scale(unsigned factor) const {
- unsigned i = (index & ~PHI_BIT) / NUM,
- o = (index % ~PHI_BIT) % NUM;
- assert(index <= (~0U & ~PHI_BIT) / (factor * NUM) &&
- "Rescaled interval would overflow");
- return LiveIndex(i * NUM * factor, o);
- }
-
- static LiveIndex emptyKey() {
- return LiveIndex(true, 0x7fffffff);
- }
-
- static LiveIndex tombstoneKey() {
- return LiveIndex(true, 0x7ffffffe);
- }
-
- static unsigned getHashValue(const LiveIndex &v) {
- return v.index * 37;
- }
-
- };
-
- inline raw_ostream& operator<<(raw_ostream &os, LiveIndex mi) {
- mi.print(os);
- return os;
- }
-
- /// Densemap specialization for LiveIndex.
- template <>
- struct DenseMapInfo<LiveIndex> {
- static inline LiveIndex getEmptyKey() {
- return LiveIndex::emptyKey();
- }
- static inline LiveIndex getTombstoneKey() {
- return LiveIndex::tombstoneKey();
- }
- static inline unsigned getHashValue(const LiveIndex &v) {
- return LiveIndex::getHashValue(v);
- }
- static inline bool isEqual(const LiveIndex &LHS,
- const LiveIndex &RHS) {
- return (LHS == RHS);
- }
- static inline bool isPod() { return true; }
- };
-
/// VNInfo - Value Number Information.
/// This class holds information about a machine level values, including
public:
- typedef SmallVector<LiveIndex, 4> KillSet;
+ typedef SmallVector<SlotIndex, 4> KillSet;
/// The ID number of this value.
unsigned id;
/// The index of the defining instruction (if isDefAccurate() returns true).
- LiveIndex def;
+ SlotIndex def;
KillSet kills;
- VNInfo()
- : flags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+ /*
+ VNInfo(LiveIntervals &li_)
+ : defflags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+ */
/// VNInfo constructor.
/// d is presumed to point to the actual defining instr. If it doesn't
/// setIsDefAccurate(false) should be called after construction.
- VNInfo(unsigned i, LiveIndex d, MachineInstr *c)
+ VNInfo(unsigned i, SlotIndex d, MachineInstr *c)
: flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
/// VNInfo construtor, copies values from orig, except for the value number.
}
/// Returns true if the given index is a kill of this value.
- bool isKill(LiveIndex k) const {
+ bool isKill(SlotIndex k) const {
KillSet::const_iterator
i = std::lower_bound(kills.begin(), kills.end(), k);
return (i != kills.end() && *i == k);
/// addKill - Add a kill instruction index to the specified value
/// number.
- void addKill(LiveIndex k) {
+ void addKill(SlotIndex k) {
if (kills.empty()) {
kills.push_back(k);
} else {
/// Remove the specified kill index from this value's kills list.
/// Returns true if the value was present, otherwise returns false.
- bool removeKill(LiveIndex k) {
+ bool removeKill(SlotIndex k) {
KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
if (i != kills.end() && *i == k) {
kills.erase(i);
}
/// Remove all kills in the range [s, e).
- void removeKills(LiveIndex s, LiveIndex e) {
+ void removeKills(SlotIndex s, SlotIndex e) {
KillSet::iterator
si = std::lower_bound(kills.begin(), kills.end(), s),
se = std::upper_bound(kills.begin(), kills.end(), e);
/// program, with an inclusive start point and an exclusive end point.
/// These ranges are rendered as [start,end).
struct LiveRange {
- LiveIndex start; // Start point of the interval (inclusive)
- LiveIndex end; // End point of the interval (exclusive)
+ SlotIndex start; // Start point of the interval (inclusive)
+ SlotIndex end; // End point of the interval (exclusive)
VNInfo *valno; // identifier for the value contained in this interval.
- LiveRange(LiveIndex S, LiveIndex E, VNInfo *V)
+ LiveRange(SlotIndex S, SlotIndex E, VNInfo *V)
: start(S), end(E), valno(V) {
assert(S < E && "Cannot create empty or backwards range");
/// contains - Return true if the index is covered by this range.
///
- bool contains(LiveIndex I) const {
+ bool contains(SlotIndex I) const {
return start <= I && I < end;
}
/// containsRange - Return true if the given range, [S, E), is covered by
/// this range.
- bool containsRange(LiveIndex S, LiveIndex E) const {
+ bool containsRange(SlotIndex S, SlotIndex E) const {
assert((S < E) && "Backwards interval?");
return (start <= S && S < end) && (start < E && E <= end);
}
raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
- inline bool operator<(LiveIndex V, const LiveRange &LR) {
+ inline bool operator<(SlotIndex V, const LiveRange &LR) {
return V < LR.start;
}
- inline bool operator<(const LiveRange &LR, LiveIndex V) {
+ inline bool operator<(const LiveRange &LR, SlotIndex V) {
return LR.start < V;
}
/// end of the interval. If no LiveRange contains this position, but the
/// position is in a hole, this method returns an iterator pointing the the
/// LiveRange immediately after the hole.
- iterator advanceTo(iterator I, LiveIndex Pos) {
+ iterator advanceTo(iterator I, SlotIndex Pos) {
if (Pos >= endIndex())
return end();
while (I->end <= Pos) ++I;
/// getNextValue - Create a new value number and return it. MIIdx specifies
/// the instruction that defines the value number.
- VNInfo *getNextValue(LiveIndex def, MachineInstr *CopyMI,
+ VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
VNInfo *VNI =
static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
/// current interval, but are defined in the Clobbers interval, mark them
/// used with an unknown definition value. Caller must pass in reference to
/// VNInfoAllocator since it will create a new val#.
- void MergeInClobberRanges(const LiveInterval &Clobbers,
+ void MergeInClobberRanges(LiveIntervals &li_,
+ const LiveInterval &Clobbers,
BumpPtrAllocator &VNInfoAllocator);
/// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
/// single LiveRange only.
- void MergeInClobberRange(LiveIndex Start,
- LiveIndex End,
+ void MergeInClobberRange(LiveIntervals &li_,
+ SlotIndex Start,
+ SlotIndex End,
BumpPtrAllocator &VNInfoAllocator);
/// MergeValueInAsValue - Merge all of the live ranges of a specific val#
bool empty() const { return ranges.empty(); }
/// beginIndex - Return the lowest numbered slot covered by interval.
- LiveIndex beginIndex() const {
- if (empty())
- return LiveIndex();
+ SlotIndex beginIndex() const {
+ assert(!empty() && "Call to beginIndex() on empty interval.");
return ranges.front().start;
}
/// endNumber - return the maximum point of the interval of the whole,
/// exclusive.
- LiveIndex endIndex() const {
- if (empty())
- return LiveIndex();
+ SlotIndex endIndex() const {
+ assert(!empty() && "Call to endIndex() on empty interval.");
return ranges.back().end;
}
- bool expiredAt(LiveIndex index) const {
+ bool expiredAt(SlotIndex index) const {
return index >= endIndex();
}
- bool liveAt(LiveIndex index) const;
+ bool liveAt(SlotIndex index) const;
// liveBeforeAndAt - Check if the interval is live at the index and the
// index just before it. If index is liveAt, check if it starts a new live
// range.If it does, then check if the previous live range ends at index-1.
- bool liveBeforeAndAt(LiveIndex index) const;
+ bool liveBeforeAndAt(SlotIndex index) const;
/// getLiveRangeContaining - Return the live range that contains the
/// specified index, or null if there is none.
- const LiveRange *getLiveRangeContaining(LiveIndex Idx) const {
+ const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
const_iterator I = FindLiveRangeContaining(Idx);
return I == end() ? 0 : &*I;
}
/// getLiveRangeContaining - Return the live range that contains the
/// specified index, or null if there is none.
- LiveRange *getLiveRangeContaining(LiveIndex Idx) {
+ LiveRange *getLiveRangeContaining(SlotIndex 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(LiveIndex Idx) const;
+ const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
/// FindLiveRangeContaining - Return an iterator to the live range that
/// contains the specified index, or end() if there is none.
- iterator FindLiveRangeContaining(LiveIndex Idx);
+ iterator FindLiveRangeContaining(SlotIndex Idx);
/// findDefinedVNInfo - Find the by the specified
/// index (register interval) or defined
- VNInfo *findDefinedVNInfoForRegInt(LiveIndex Idx) const;
+ VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
/// findDefinedVNInfo - Find the VNInfo that's defined by the specified
/// register (stack inteval only).
/// overlaps - Return true if the live interval overlaps a range specified
/// by [Start, End).
- bool overlaps(LiveIndex Start, LiveIndex End) const;
+ bool overlaps(SlotIndex Start, SlotIndex End) const;
/// overlapsFrom - Return true if the intersection of the two live intervals
/// is not empty. The specified iterator is a hint that we can begin
/// join - Join two live intervals (this, and other) together. This applies
/// mappings to the value numbers in the LHS/RHS intervals as specified. If
/// the intervals are not joinable, this aborts.
- void join(LiveInterval &Other, const int *ValNoAssignments,
+ void join(LiveInterval &Other,
+ const int *ValNoAssignments,
const int *RHSValNoAssignments,
SmallVector<VNInfo*, 16> &NewVNInfo,
MachineRegisterInfo *MRI);
/// isInOneLiveRange - Return true if the range specified is entirely in the
/// a single LiveRange of the live interval.
- bool isInOneLiveRange(LiveIndex Start, LiveIndex End);
+ bool isInOneLiveRange(SlotIndex Start, SlotIndex End);
/// removeRange - Remove the specified range from this interval. Note that
/// the range must be a single LiveRange in its entirety.
- void removeRange(LiveIndex Start, LiveIndex End,
+ void removeRange(SlotIndex Start, SlotIndex End,
bool RemoveDeadValNo = false);
void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
void ComputeJoinedWeight(const LiveInterval &Other);
bool operator<(const LiveInterval& other) const {
- const LiveIndex &thisIndex = beginIndex();
- const LiveIndex &otherIndex = other.beginIndex();
+ const SlotIndex &thisIndex = beginIndex();
+ const SlotIndex &otherIndex = other.beginIndex();
return (thisIndex < otherIndex ||
(thisIndex == otherIndex && reg < other.reg));
}
private:
Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
- void extendIntervalEndTo(Ranges::iterator I, LiveIndex NewEnd);
- Ranges::iterator extendIntervalStartTo(Ranges::iterator I, LiveIndex NewStr);
+ void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
+ Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
+
LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
};
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include <cmath>
+#include <iterator>
namespace llvm {
class TargetInstrInfo;
class TargetRegisterClass;
class VirtRegMap;
- typedef std::pair<LiveIndex, MachineBasicBlock*> IdxMBBPair;
-
- inline bool operator<(LiveIndex V, const IdxMBBPair &IM) {
- return V < IM.first;
- }
-
- inline bool operator<(const IdxMBBPair &IM, LiveIndex V) {
- return IM.first < V;
- }
-
- struct Idx2MBBCompare {
- bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
- return LHS.first < RHS.first;
- }
- };
class LiveIntervals : public MachineFunctionPass {
MachineFunction* mf_;
const TargetInstrInfo* tii_;
AliasAnalysis *aa_;
LiveVariables* lv_;
+ SlotIndexes* indexes_;
/// Special pool allocator for VNInfo's (LiveInterval val#).
///
BumpPtrAllocator VNInfoAllocator;
- /// MBB2IdxMap - The indexes of the first and last instructions in the
- /// specified basic block.
- std::vector<std::pair<LiveIndex, LiveIndex> > MBB2IdxMap;
-
- /// Idx2MBBMap - Sorted list of pairs of index of first instruction
- /// and MBB id.
- std::vector<IdxMBBPair> Idx2MBBMap;
-
- /// FunctionSize - The number of instructions present in the function
- uint64_t FunctionSize;
-
- typedef DenseMap<const MachineInstr*, LiveIndex> Mi2IndexMap;
- Mi2IndexMap mi2iMap_;
-
- typedef std::vector<MachineInstr*> Index2MiMap;
- Index2MiMap i2miMap_;
-
typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
Reg2IntervalMap r2iMap_;
- DenseMap<MachineBasicBlock*, LiveIndex> terminatorGaps;
-
/// phiJoinCopies - Copy instructions which are PHI joins.
SmallVector<MachineInstr*, 16> phiJoinCopies;
/// CloneMIs - A list of clones as result of re-materialization.
std::vector<MachineInstr*> CloneMIs;
- typedef LiveInterval::InstrSlots InstrSlots;
-
public:
static char ID; // Pass identification, replacement for typeid
LiveIntervals() : MachineFunctionPass(&ID) {}
- LiveIndex getBaseIndex(LiveIndex index) {
- return LiveIndex(index, LiveIndex::LOAD);
- }
- LiveIndex getBoundaryIndex(LiveIndex index) {
- return LiveIndex(index,
- (LiveIndex::Slot)(LiveIndex::NUM - 1));
- }
- LiveIndex getLoadIndex(LiveIndex index) {
- return LiveIndex(index, LiveIndex::LOAD);
- }
- LiveIndex getUseIndex(LiveIndex index) {
- return LiveIndex(index, LiveIndex::USE);
- }
- LiveIndex getDefIndex(LiveIndex index) {
- return LiveIndex(index, LiveIndex::DEF);
- }
- LiveIndex getStoreIndex(LiveIndex index) {
- return LiveIndex(index, LiveIndex::STORE);
- }
-
- LiveIndex getNextSlot(LiveIndex m) const {
- return m.nextSlot_();
- }
-
- LiveIndex getNextIndex(LiveIndex m) const {
- return m.nextIndex_();
- }
-
- LiveIndex getPrevSlot(LiveIndex m) const {
- return m.prevSlot_();
- }
-
- LiveIndex getPrevIndex(LiveIndex m) const {
- return m.prevIndex_();
- }
-
static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
return (isDef + isUse) * powf(10.0F, (float)loopDepth);
}
return r2iMap_.count(reg);
}
- /// getMBBStartIdx - Return the base index of the first instruction in the
- /// specified MachineBasicBlock.
- LiveIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
- return getMBBStartIdx(MBB->getNumber());
- }
- LiveIndex getMBBStartIdx(unsigned MBBNo) const {
- assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
- return MBB2IdxMap[MBBNo].first;
- }
-
- /// getMBBEndIdx - Return the store index of the last instruction in the
- /// specified MachineBasicBlock.
- LiveIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
- return getMBBEndIdx(MBB->getNumber());
- }
- LiveIndex getMBBEndIdx(unsigned MBBNo) const {
- assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
- return MBB2IdxMap[MBBNo].second;
- }
-
/// getScaledIntervalSize - get the size of an interval in "units,"
/// where every function is composed of one thousand units. This
/// measure scales properly with empty index slots in the function.
double getScaledIntervalSize(LiveInterval& I) {
- return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+ return (1000.0 * I.getSize()) / indexes_->getIndexesLength();
}
/// getApproximateInstructionCount - computes an estimate of the number
/// of instructions in a given LiveInterval.
unsigned getApproximateInstructionCount(LiveInterval& I) {
double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
- return (unsigned)(IntervalPercentage * FunctionSize);
- }
-
- /// getMBBFromIndex - given an index in any instruction of an
- /// MBB return a pointer the MBB
- MachineBasicBlock* getMBBFromIndex(LiveIndex index) const {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
- // Take the pair containing the index
- std::vector<IdxMBBPair>::const_iterator J =
- ((I != Idx2MBBMap.end() && I->first > index) ||
- (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
-
- assert(J != Idx2MBBMap.end() && J->first <= index &&
- index <= getMBBEndIdx(J->second) &&
- "index does not correspond to an MBB");
- return J->second;
- }
-
- /// getInstructionIndex - returns the base index of instr
- LiveIndex getInstructionIndex(const MachineInstr* instr) const {
- Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
- assert(it != mi2iMap_.end() && "Invalid instruction!");
- return it->second;
- }
-
- /// getInstructionFromIndex - given an index in any slot of an
- /// instruction return a pointer the instruction
- MachineInstr* getInstructionFromIndex(LiveIndex index) const {
- // convert index to vector index
- unsigned i = index.getVecIndex();
- assert(i < i2miMap_.size() &&
- "index does not correspond to an instruction");
- return i2miMap_[i];
- }
-
- /// hasGapBeforeInstr - Return true if the previous instruction slot,
- /// i.e. Index - InstrSlots::NUM, is not occupied.
- bool hasGapBeforeInstr(LiveIndex Index) {
- Index = getBaseIndex(getPrevIndex(Index));
- return getInstructionFromIndex(Index) == 0;
- }
-
- /// hasGapAfterInstr - Return true if the successive instruction slot,
- /// i.e. Index + InstrSlots::Num, is not occupied.
- bool hasGapAfterInstr(LiveIndex Index) {
- Index = getBaseIndex(getNextIndex(Index));
- return getInstructionFromIndex(Index) == 0;
- }
-
- /// findGapBeforeInstr - Find an empty instruction slot before the
- /// specified index. If "Furthest" is true, find one that's furthest
- /// away from the index (but before any index that's occupied).
- LiveIndex findGapBeforeInstr(LiveIndex Index, bool Furthest = false) {
- Index = getBaseIndex(getPrevIndex(Index));
- if (getInstructionFromIndex(Index))
- return LiveIndex(); // No gap!
- if (!Furthest)
- return Index;
- LiveIndex PrevIndex = getBaseIndex(getPrevIndex(Index));
- while (getInstructionFromIndex(Index)) {
- Index = PrevIndex;
- PrevIndex = getBaseIndex(getPrevIndex(Index));
- }
- return Index;
- }
-
- /// InsertMachineInstrInMaps - Insert the specified machine instruction
- /// into the instruction index map at the given index.
- void InsertMachineInstrInMaps(MachineInstr *MI, LiveIndex Index) {
- i2miMap_[Index.getVecIndex()] = MI;
- Mi2IndexMap::iterator it = mi2iMap_.find(MI);
- assert(it == mi2iMap_.end() && "Already in map!");
- mi2iMap_[MI] = Index;
+ return (unsigned)(IntervalPercentage * indexes_->getFunctionSize());
}
/// conflictsWithPhysRegDef - Returns true if the specified register
bool CheckUse,
SmallPtrSet<MachineInstr*,32> &JoinedCopies);
- /// findLiveInMBBs - Given a live range, if the value of the range
- /// is live in any MBB returns true as well as the list of basic blocks
- /// in which the value is live.
- bool findLiveInMBBs(LiveIndex Start, LiveIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
- /// findReachableMBBs - Return a list MBB that can be reached via any
- /// branch or fallthroughs. Return true if the list is not empty.
- bool findReachableMBBs(LiveIndex Start, LiveIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
// Interval creation
-
LiveInterval &getOrCreateInterval(unsigned reg) {
Reg2IntervalMap::iterator I = r2iMap_.find(reg);
if (I == r2iMap_.end())
r2iMap_.erase(I);
}
+ SlotIndex getZeroIndex() const {
+ return indexes_->getZeroIndex();
+ }
+
+ SlotIndex getInvalidIndex() const {
+ return indexes_->getInvalidIndex();
+ }
+
/// isNotInMIMap - returns true if the specified machine instr has been
/// removed or was never entered in the map.
- bool isNotInMIMap(MachineInstr* instr) const {
- return !mi2iMap_.count(instr);
+ bool isNotInMIMap(const MachineInstr* Instr) const {
+ return !indexes_->hasIndex(Instr);
+ }
+
+ /// Returns the base index of the given instruction.
+ SlotIndex getInstructionIndex(const MachineInstr *instr) const {
+ return indexes_->getInstructionIndex(instr);
+ }
+
+ /// Returns the instruction associated with the given index.
+ MachineInstr* getInstructionFromIndex(SlotIndex index) const {
+ return indexes_->getInstructionFromIndex(index);
+ }
+
+ /// Return the first index in the given basic block.
+ SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
+ return indexes_->getMBBStartIdx(mbb);
+ }
+
+ /// Return the last index in the given basic block.
+ SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
+ return indexes_->getMBBEndIdx(mbb);
+ }
+
+ MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+ return indexes_->getMBBFromIndex(index);
+ }
+
+ bool hasGapBeforeInstr(SlotIndex index) {
+ return indexes_->hasGapBeforeInstr(index);
+ }
+
+ bool hasGapAfterInstr(SlotIndex index) {
+ return indexes_->hasGapAfterInstr(index);
+ }
+
+ SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
+ return indexes_->findGapBeforeInstr(index, furthest);
+ }
+
+ void InsertMachineInstrInMaps(MachineInstr *MI, SlotIndex Index) {
+ indexes_->insertMachineInstrInMaps(MI, Index);
}
- /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
- /// deleted.
void RemoveMachineInstrFromMaps(MachineInstr *MI) {
- // remove index -> MachineInstr and
- // MachineInstr -> index mappings
- Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
- if (mi2i != mi2iMap_.end()) {
- i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
- mi2iMap_.erase(mi2i);
- }
+ indexes_->removeMachineInstrFromMaps(MI);
}
- /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
- /// maps used by register allocator.
void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
- Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
- if (mi2i == mi2iMap_.end())
- return;
- i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
- Mi2IndexMap::iterator it = mi2iMap_.find(MI);
- assert(it != mi2iMap_.end() && "Invalid instruction!");
- LiveIndex Index = it->second;
- mi2iMap_.erase(it);
- mi2iMap_[NewMI] = Index;
+ indexes_->replaceMachineInstrInMaps(MI, NewMI);
+ }
+
+ bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
+ SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
+ return indexes_->findLiveInMBBs(Start, End, MBBs);
+ }
+
+ void renumber() {
+ indexes_->renumber();
}
BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
/// marker to implicit_def defs and their uses.
void processImplicitDefs();
- /// computeNumbering - Compute the index numbering.
- void computeNumbering();
-
- /// scaleNumbering - Rescale interval numbers to introduce gaps for new
- /// instructions
- void scaleNumbering(int factor);
-
/// intervalIsInOneMBB - Returns true if the specified interval is entirely
/// within a single basic block.
bool intervalIsInOneMBB(const LiveInterval &li) const;
/// handleVirtualRegisterDef)
void handleRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO, unsigned MOIdx);
/// handleVirtualRegisterDef - update intervals for a virtual
/// register def
void handleVirtualRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
- LiveIndex MIIdx, MachineOperand& MO,
+ SlotIndex MIIdx, MachineOperand& MO,
unsigned MOIdx,
LiveInterval& interval);
/// def.
void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- LiveIndex MIIdx, MachineOperand& MO,
+ SlotIndex MIIdx, MachineOperand& MO,
LiveInterval &interval,
MachineInstr *CopyMI);
/// handleLiveInRegister - Create interval for a livein register.
void handleLiveInRegister(MachineBasicBlock* mbb,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
LiveInterval &interval, bool isAlias = false);
/// getReMatImplicitUse - If the remat definition MI has one (for now, we
/// which reaches the given instruction also reaches the specified use
/// index.
bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
- LiveIndex UseIdx) const;
+ SlotIndex UseIdx) const;
/// isReMaterializable - Returns true if the definition MI of the specified
/// val# of the specified interval is re-materializable. Also returns true
/// MI. If it is successul, MI is updated with the newly created MI and
/// returns true.
bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
- MachineInstr *DefMI, LiveIndex InstrIdx,
+ MachineInstr *DefMI, SlotIndex InstrIdx,
SmallVector<unsigned, 2> &Ops,
bool isSS, int FrameIndex, unsigned Reg);
/// VNInfo that's after the specified index but is within the basic block.
bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
MachineBasicBlock *MBB,
- LiveIndex Idx) const;
+ SlotIndex Idx) const;
/// hasAllocatableSuperReg - Return true if the specified physical register
/// has any super register that's allocatable.
/// SRInfo - Spill / restore info.
struct SRInfo {
- LiveIndex index;
+ SlotIndex index;
unsigned vreg;
bool canFold;
- SRInfo(LiveIndex i, unsigned vr, bool f)
+ SRInfo(SlotIndex i, unsigned vr, bool f)
: index(i), vreg(vr), canFold(f) {}
};
- bool alsoFoldARestore(int Id, LiveIndex index, unsigned vr,
+ bool alsoFoldARestore(int Id, SlotIndex index, unsigned vr,
BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
- void eraseRestoreInfo(int Id, LiveIndex index, unsigned vr,
+ void eraseRestoreInfo(int Id, SlotIndex index, unsigned vr,
BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
/// functions for addIntervalsForSpills to rewrite uses / defs for the given
/// live range.
bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
- bool TrySplit, LiveIndex index, LiveIndex end,
+ bool TrySplit, SlotIndex index, SlotIndex end,
MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
unsigned Slot, int LdSlot,
bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
iterator begin() { return S2IMap.begin(); }
iterator end() { return S2IMap.end(); }
- void scaleNumbering(int factor);
-
unsigned getNumIntervals() const { return (unsigned)S2IMap.size(); }
LiveInterval &getOrCreateInterval(int Slot, const TargetRegisterClass *RC) {
--- /dev/null
+//===-------------- llvm/CodeGen/ProcessImplicitDefs.h ----------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
+#define LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+ class MachineInstr;
+ class TargetInstrInfo;
+
+ /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
+ /// for each use. Add isUndef marker to implicit_def defs and their uses.
+ class ProcessImplicitDefs : public MachineFunctionPass {
+ private:
+
+ bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
+ unsigned OpIdx, const TargetInstrInfo *tii_);
+
+ public:
+ static char ID;
+
+ ProcessImplicitDefs() : MachineFunctionPass(&ID) {}
+
+ virtual void getAnalysisUsage(AnalysisUsage &au) const;
+
+ virtual bool runOnMachineFunction(MachineFunction &fn);
+ };
+
+}
+
+#endif // LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
--- /dev/null
+//===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements SlotIndex and related classes. The purpuse of SlotIndex
+// is to describe a position at which a register can become live, or cease to
+// be live.
+//
+// SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which
+// is held is LiveIntervals and provides the real numbering. This allows
+// LiveIntervals to perform largely transparent renumbering. The SlotIndex
+// class does hold a PHI bit, which determines whether the index relates to a
+// PHI use or def point, or an actual instruction. See the SlotIndex class
+// description for futher information.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SLOTINDEXES_H
+#define LLVM_CODEGEN_SLOTINDEXES_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+ /// This class represents an entry in the slot index list held in the
+ /// SlotIndexes pass. It should not be used directly. See the
+ /// SlotIndex & SlotIndexes classes for the public interface to this
+ /// information.
+ class IndexListEntry {
+ friend class SlotIndex;
+ friend class SlotIndexes;
+
+ private:
+
+ IndexListEntry *next, *prev;
+ MachineInstr *mi;
+ unsigned index;
+
+ public:
+
+ IndexListEntry(MachineInstr *mi, unsigned index)
+ : mi(mi), index(index) {}
+
+ MachineInstr* getInstr() const { return mi; }
+ void setInstr(MachineInstr *mi) { this->mi = mi; }
+
+ unsigned getIndex() const { return index; }
+ void setIndex(unsigned index) { this->index = index; }
+
+ IndexListEntry* getNext() { return next; }
+ const IndexListEntry* getNext() const { return next; }
+ void setNext(IndexListEntry *next) { this->next = next; }
+
+ IndexListEntry* getPrev() { return prev; }
+ const IndexListEntry* getPrev() const { return prev; }
+ void setPrev(IndexListEntry *prev) { this->prev = prev; }
+
+ /*
+ bool operator==(const IndexListEntry &other) const {
+ assert(getIndex() != other.getIndex() || this == &other &&
+ "Non-equal index list entries compare equal.");
+ return getIndex() == other.getIndex();
+ }
+
+ bool operator!=(const IndexListEntry &other) const {
+ return getIndex() != other.getIndex();
+ }
+
+ bool operator<(const IndexListEntry &other) const {
+ return getIndex() < other.getIndex();
+ }
+
+ bool operator<=(const IndexListEntry &other) const {
+ return getIndex() <= other.getIndex();
+ }
+
+ bool operator>(const IndexListEntry &other) const {
+ return getIndex() > other.getIndex();
+ }
+
+ bool operator>=(const IndexListEntry &other) const {
+ return getIndex() >= other.getIndex();
+ }
+
+ int distance(const IndexListEntry &other) const {
+ return other.getIndex() - getIndex();
+ }
+ */
+ };
+
+ // Specialize PointerLikeTypeTraits for IndexListEntry.
+ template <>
+ class PointerLikeTypeTraits<IndexListEntry*> {
+ public:
+ static inline void* getAsVoidPointer(IndexListEntry *p) {
+ return p;
+ }
+ static inline IndexListEntry* getFromVoidPointer(void *p) {
+ return static_cast<IndexListEntry*>(p);
+ }
+ enum { NumLowBitsAvailable = 3 };
+ };
+
+ /// SlotIndex - An opaque wrapper around machine indexes.
+ class SlotIndex {
+ friend class SlotIndexes;
+ friend class DenseMapInfo<SlotIndex>;
+
+ private:
+
+ // FIXME: Is there any way to statically allocate these things and have
+ // them 8-byte aligned?
+ static std::auto_ptr<IndexListEntry> emptyKeyPtr, tombstoneKeyPtr;
+ static const unsigned PHI_BIT = 1 << 2;
+
+ PointerIntPair<IndexListEntry*, 3, unsigned> lie;
+
+ SlotIndex(IndexListEntry *entry, unsigned phiAndSlot)
+ : lie(entry, phiAndSlot) {
+ assert(entry != 0 && "Attempt to construct index with 0 pointer.");
+ }
+
+ IndexListEntry& entry() const {
+ assert(lie.getPointer() != 0 && "Use of invalid index.");
+ return *lie.getPointer();
+ }
+
+ int getIndex() const {
+ return entry().getIndex() | getSlot();
+ }
+
+ static inline unsigned getHashValue(const SlotIndex &v) {
+ IndexListEntry *ptrVal = &v.entry();
+ return (unsigned((intptr_t)ptrVal) >> 4) ^
+ (unsigned((intptr_t)ptrVal) >> 9);
+ }
+
+ public:
+
+ // FIXME: Ugh. This is public because LiveIntervalAnalysis is still using it
+ // for some spill weight stuff. Fix that, then make this private.
+ enum Slot { LOAD, USE, DEF, STORE, NUM };
+
+ static inline SlotIndex getEmptyKey() {
+ // FIXME: How do we guarantee these numbers don't get allocated to
+ // legit indexes?
+ if (emptyKeyPtr.get() == 0)
+ emptyKeyPtr.reset(new IndexListEntry(0, ~0U & ~3U));
+
+ return SlotIndex(emptyKeyPtr.get(), 0);
+ }
+
+ static inline SlotIndex getTombstoneKey() {
+ // FIXME: How do we guarantee these numbers don't get allocated to
+ // legit indexes?
+ if (tombstoneKeyPtr.get() == 0)
+ tombstoneKeyPtr.reset(new IndexListEntry(0, ~0U & ~7U));
+
+ return SlotIndex(tombstoneKeyPtr.get(), 0);
+ }
+
+ /// Construct an invalid index.
+ SlotIndex() : lie(&getEmptyKey().entry(), 0) {}
+
+ // Construct a new slot index from the given one, set the phi flag on the
+ // new index to the value of the phi parameter.
+ SlotIndex(const SlotIndex &li, bool phi)
+ : lie(&li.entry(), phi ? PHI_BIT & li.getSlot() : (unsigned)li.getSlot()){
+ assert(lie.getPointer() != 0 &&
+ "Attempt to construct index with 0 pointer.");
+ }
+
+ // Construct a new slot index from the given one, set the phi flag on the
+ // new index to the value of the phi parameter, and the slot to the new slot.
+ SlotIndex(const SlotIndex &li, bool phi, Slot s)
+ : lie(&li.entry(), phi ? PHI_BIT & s : (unsigned)s) {
+ assert(lie.getPointer() != 0 &&
+ "Attempt to construct index with 0 pointer.");
+ }
+
+ /// Returns true if this is a valid index. Invalid indicies do
+ /// not point into an index table, and cannot be compared.
+ bool isValid() const {
+ return (lie.getPointer() != 0) && (lie.getPointer()->getIndex() != 0);
+ }
+
+ /// Print this index to the given raw_ostream.
+ void print(raw_ostream &os) const;
+
+ /// Dump this index to stderr.
+ void dump() const;
+
+ /// Compare two SlotIndex objects for equality.
+ bool operator==(SlotIndex other) const {
+ return getIndex() == other.getIndex();
+ }
+ /// Compare two SlotIndex objects for inequality.
+ bool operator!=(SlotIndex other) const {
+ return getIndex() != other.getIndex();
+ }
+
+ /// Compare two SlotIndex objects. Return true if the first index
+ /// is strictly lower than the second.
+ bool operator<(SlotIndex other) const {
+ return getIndex() < other.getIndex();
+ }
+ /// Compare two SlotIndex objects. Return true if the first index
+ /// is lower than, or equal to, the second.
+ bool operator<=(SlotIndex other) const {
+ return getIndex() <= other.getIndex();
+ }
+
+ /// Compare two SlotIndex objects. Return true if the first index
+ /// is greater than the second.
+ bool operator>(SlotIndex other) const {
+ return getIndex() > other.getIndex();
+ }
+
+ /// Compare two SlotIndex objects. Return true if the first index
+ /// is greater than, or equal to, the second.
+ bool operator>=(SlotIndex other) const {
+ return getIndex() >= other.getIndex();
+ }
+
+ /// Return the distance from this index to the given one.
+ int distance(SlotIndex other) const {
+ return other.getIndex() - getIndex();
+ }
+
+ /// Returns the slot for this SlotIndex.
+ Slot getSlot() const {
+ return static_cast<Slot>(lie.getInt() & ~PHI_BIT);
+ }
+
+ /// Returns the state of the PHI bit.
+ bool isPHI() const {
+ return lie.getInt() & PHI_BIT;
+ }
+
+ /// Returns the base index for associated with this index. The base index
+ /// is the one associated with the LOAD slot for the instruction pointed to
+ /// by this index.
+ SlotIndex getBaseIndex() const {
+ return getLoadIndex();
+ }
+
+ /// Returns the boundary index for associated with this index. The boundary
+ /// index is the one associated with the LOAD slot for the instruction
+ /// pointed to by this index.
+ SlotIndex getBoundaryIndex() const {
+ return getStoreIndex();
+ }
+
+ /// Returns the index of the LOAD slot for the instruction pointed to by
+ /// this index.
+ SlotIndex getLoadIndex() const {
+ return SlotIndex(&entry(), SlotIndex::LOAD);
+ }
+
+ /// Returns the index of the USE slot for the instruction pointed to by
+ /// this index.
+ SlotIndex getUseIndex() const {
+ return SlotIndex(&entry(), SlotIndex::USE);
+ }
+
+ /// Returns the index of the DEF slot for the instruction pointed to by
+ /// this index.
+ SlotIndex getDefIndex() const {
+ return SlotIndex(&entry(), SlotIndex::DEF);
+ }
+
+ /// Returns the index of the STORE slot for the instruction pointed to by
+ /// this index.
+ SlotIndex getStoreIndex() const {
+ return SlotIndex(&entry(), SlotIndex::STORE);
+ }
+
+ /// Returns the next slot in the index list. This could be either the
+ /// next slot for the instruction pointed to by this index or, if this
+ /// index is a STORE, the first slot for the next instruction.
+ /// WARNING: This method is considerably more expensive than the methods
+ /// that return specific slots (getUseIndex(), etc). If you can - please
+ /// use one of those methods.
+ SlotIndex getNextSlot() const {
+ Slot s = getSlot();
+ if (s == SlotIndex::STORE) {
+ return SlotIndex(entry().getNext(), SlotIndex::LOAD);
+ }
+ return SlotIndex(&entry(), s + 1);
+ }
+
+ /// Returns the next index. This is the index corresponding to the this
+ /// index's slot, but for the next instruction.
+ SlotIndex getNextIndex() const {
+ return SlotIndex(entry().getNext(), getSlot());
+ }
+
+ /// Returns the previous slot in the index list. This could be either the
+ /// previous slot for the instruction pointed to by this index or, if this
+ /// index is a LOAD, the last slot for the previous instruction.
+ /// WARNING: This method is considerably more expensive than the methods
+ /// that return specific slots (getUseIndex(), etc). If you can - please
+ /// use one of those methods.
+ SlotIndex getPrevSlot() const {
+ Slot s = getSlot();
+ if (s == SlotIndex::LOAD) {
+ return SlotIndex(entry().getPrev(), SlotIndex::STORE);
+ }
+ return SlotIndex(&entry(), s - 1);
+ }
+
+ /// Returns the previous index. This is the index corresponding to this
+ /// index's slot, but for the previous instruction.
+ SlotIndex getPrevIndex() const {
+ return SlotIndex(entry().getPrev(), getSlot());
+ }
+
+ };
+
+ /// DenseMapInfo specialization for SlotIndex.
+ template <>
+ struct DenseMapInfo<SlotIndex> {
+ static inline SlotIndex getEmptyKey() {
+ return SlotIndex::getEmptyKey();
+ }
+ static inline SlotIndex getTombstoneKey() {
+ return SlotIndex::getTombstoneKey();
+ }
+ static inline unsigned getHashValue(const SlotIndex &v) {
+ return SlotIndex::getHashValue(v);
+ }
+ static inline bool isEqual(const SlotIndex &LHS, const SlotIndex &RHS) {
+ return (LHS == RHS);
+ }
+ static inline bool isPod() { return false; }
+ };
+
+ inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
+ li.print(os);
+ return os;
+ }
+
+ typedef std::pair<SlotIndex, MachineBasicBlock*> IdxMBBPair;
+
+ inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
+ return V < IM.first;
+ }
+
+ inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
+ return IM.first < V;
+ }
+
+ struct Idx2MBBCompare {
+ bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
+ return LHS.first < RHS.first;
+ }
+ };
+
+ /// SlotIndexes pass.
+ ///
+ /// This pass assigns indexes to each instruction.
+ class SlotIndexes : public MachineFunctionPass {
+ private:
+
+ MachineFunction *mf;
+ IndexListEntry *indexListHead;
+ unsigned functionSize;
+
+ typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
+ Mi2IndexMap mi2iMap;
+
+ /// MBB2IdxMap - The indexes of the first and last instructions in the
+ /// specified basic block.
+ typedef DenseMap<const MachineBasicBlock*,
+ std::pair<SlotIndex, SlotIndex> > MBB2IdxMap;
+ MBB2IdxMap mbb2IdxMap;
+
+ /// Idx2MBBMap - Sorted list of pairs of index of first instruction
+ /// and MBB id.
+ std::vector<IdxMBBPair> idx2MBBMap;
+
+ typedef DenseMap<const MachineBasicBlock*, SlotIndex> TerminatorGapsMap;
+ TerminatorGapsMap terminatorGaps;
+
+ // IndexListEntry allocator.
+ BumpPtrAllocator ileAllocator;
+
+ IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
+ IndexListEntry *entry =
+ static_cast<IndexListEntry*>(
+ ileAllocator.Allocate(sizeof(IndexListEntry),
+ alignof<IndexListEntry>()));
+
+ new (entry) IndexListEntry(mi, index);
+
+ return entry;
+ }
+
+ void initList() {
+ assert(indexListHead == 0 && "Zero entry non-null at initialisation.");
+ indexListHead = createEntry(0, ~0U);
+ indexListHead->setNext(0);
+ indexListHead->setPrev(indexListHead);
+ }
+
+ void clearList() {
+ indexListHead = 0;
+ ileAllocator.Reset();
+ }
+
+ IndexListEntry* getTail() {
+ assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
+ return indexListHead->getPrev();
+ }
+
+ const IndexListEntry* getTail() const {
+ assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
+ return indexListHead->getPrev();
+ }
+
+ // Returns true if the index list is empty.
+ bool empty() const { return (indexListHead == getTail()); }
+
+ IndexListEntry* front() {
+ assert(!empty() && "front() called on empty index list.");
+ return indexListHead;
+ }
+
+ const IndexListEntry* front() const {
+ assert(!empty() && "front() called on empty index list.");
+ return indexListHead;
+ }
+
+ IndexListEntry* back() {
+ assert(!empty() && "back() called on empty index list.");
+ return getTail()->getPrev();
+ }
+
+ const IndexListEntry* back() const {
+ assert(!empty() && "back() called on empty index list.");
+ return getTail()->getPrev();
+ }
+
+ /// Insert a new entry before itr.
+ void insert(IndexListEntry *itr, IndexListEntry *val) {
+ assert(itr != 0 && "itr should not be null.");
+ IndexListEntry *prev = itr->getPrev();
+ val->setNext(itr);
+ val->setPrev(prev);
+
+ if (itr != indexListHead) {
+ prev->setNext(val);
+ }
+ else {
+ indexListHead = val;
+ }
+ itr->setPrev(val);
+ }
+
+ /// Push a new entry on to the end of the list.
+ void push_back(IndexListEntry *val) {
+ insert(getTail(), val);
+ }
+
+ public:
+ static char ID;
+
+ SlotIndexes() : MachineFunctionPass(&ID), indexListHead(0) {}
+
+ virtual void getAnalysisUsage(AnalysisUsage &au) const;
+ virtual void releaseMemory();
+
+ virtual bool runOnMachineFunction(MachineFunction &fn);
+
+ /// Dump the indexes.
+ void dump() const;
+
+ /// Renumber the index list, providing space for new instructions.
+ void renumber();
+
+ /// Returns the zero index for this analysis.
+ SlotIndex getZeroIndex() {
+ assert(front()->getIndex() == 0 && "First index is not 0?");
+ return SlotIndex(front(), 0);
+ }
+
+ /// Returns the invalid index marker for this analysis.
+ SlotIndex getInvalidIndex() {
+ return getZeroIndex();
+ }
+
+ /// Returns the distance between the highest and lowest indexes allocated
+ /// so far.
+ unsigned getIndexesLength() const {
+ assert(front()->getIndex() == 0 &&
+ "Initial index isn't zero?");
+
+ return back()->getIndex();
+ }
+
+ /// Returns the number of instructions in the function.
+ unsigned getFunctionSize() const {
+ return functionSize;
+ }
+
+ /// Returns true if the given machine instr is mapped to an index,
+ /// otherwise returns false.
+ bool hasIndex(const MachineInstr *instr) const {
+ return (mi2iMap.find(instr) != mi2iMap.end());
+ }
+
+ /// Returns the base index for the given instruction.
+ SlotIndex getInstructionIndex(const MachineInstr *instr) const {
+ Mi2IndexMap::const_iterator itr = mi2iMap.find(instr);
+ assert(itr != mi2iMap.end() && "Instruction not found in maps.");
+ return itr->second;
+ }
+
+ /// Returns the instruction for the given index, or null if the given
+ /// index has no instruction associated with it.
+ MachineInstr* getInstructionFromIndex(SlotIndex index) const {
+ return index.entry().getInstr();
+ }
+
+ /// Returns the next non-null index.
+ SlotIndex getNextNonNullIndex(SlotIndex index) {
+ SlotIndex nextNonNull = index.getNextIndex();
+
+ while (&nextNonNull.entry() != getTail() &&
+ getInstructionFromIndex(nextNonNull) == 0) {
+ nextNonNull = nextNonNull.getNextIndex();
+ }
+
+ return nextNonNull;
+ }
+
+ /// Returns the first index in the given basic block.
+ SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
+ MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
+ assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
+ return itr->second.first;
+ }
+
+ /// Returns the last index in the given basic block.
+ SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
+ MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
+ assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
+ return itr->second.second;
+ }
+
+ /// Returns the terminator gap for the given index.
+ SlotIndex getTerminatorGap(const MachineBasicBlock *mbb) {
+ TerminatorGapsMap::iterator itr = terminatorGaps.find(mbb);
+ assert(itr != terminatorGaps.end() &&
+ "All MBBs should have terminator gaps in their indexes.");
+ return itr->second;
+ }
+
+ /// Returns the basic block which the given index falls in.
+ MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+ std::vector<IdxMBBPair>::const_iterator I =
+ std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
+ // Take the pair containing the index
+ std::vector<IdxMBBPair>::const_iterator J =
+ ((I != idx2MBBMap.end() && I->first > index) ||
+ (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
+
+ assert(J != idx2MBBMap.end() && J->first <= index &&
+ index <= getMBBEndIdx(J->second) &&
+ "index does not correspond to an MBB");
+ return J->second;
+ }
+
+ bool findLiveInMBBs(SlotIndex start, SlotIndex end,
+ SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
+ std::vector<IdxMBBPair>::const_iterator itr =
+ std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+ bool resVal = false;
+
+ while (itr != idx2MBBMap.end()) {
+ if (itr->first >= end)
+ break;
+ mbbs.push_back(itr->second);
+ resVal = true;
+ ++itr;
+ }
+ return resVal;
+ }
+
+ /// Return a list of MBBs that can be reach via any branches or
+ /// fall-throughs.
+ bool findReachableMBBs(SlotIndex start, SlotIndex end,
+ SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
+ std::vector<IdxMBBPair>::const_iterator itr =
+ std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+
+ bool resVal = false;
+ while (itr != idx2MBBMap.end()) {
+ if (itr->first > end)
+ break;
+ MachineBasicBlock *mbb = itr->second;
+ if (getMBBEndIdx(mbb) > end)
+ break;
+ for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(),
+ se = mbb->succ_end(); si != se; ++si)
+ mbbs.push_back(*si);
+ resVal = true;
+ ++itr;
+ }
+ return resVal;
+ }
+
+ /// Returns the MBB covering the given range, or null if the range covers
+ /// more than one basic block.
+ MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
+
+ assert(start < end && "Backwards ranges not allowed.");
+
+ std::vector<IdxMBBPair>::const_iterator itr =
+ std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+
+ if (itr == idx2MBBMap.end()) {
+ itr = prior(itr);
+ return itr->second;
+ }
+
+ // Check that we don't cross the boundary into this block.
+ if (itr->first < end)
+ return 0;
+
+ itr = prior(itr);
+
+ if (itr->first <= start)
+ return itr->second;
+
+ return 0;
+ }
+
+ /// Returns true if there is a gap in the numbering before the given index.
+ bool hasGapBeforeInstr(SlotIndex index) {
+ index = index.getBaseIndex();
+ SlotIndex prevIndex = index.getPrevIndex();
+
+ if (prevIndex == getZeroIndex())
+ return false;
+
+ if (getInstructionFromIndex(prevIndex) == 0)
+ return true;
+
+ if (prevIndex.distance(index) >= 2 * SlotIndex::NUM)
+ return true;
+
+ return false;
+ }
+
+ /// Returns true if there is a gap in the numbering after the given index.
+ bool hasGapAfterInstr(SlotIndex index) const {
+ // Not implemented yet.
+ assert(false &&
+ "SlotIndexes::hasGapAfterInstr(SlotIndex) not implemented yet.");
+ return false;
+ }
+
+ /// findGapBeforeInstr - Find an empty instruction slot before the
+ /// specified index. If "Furthest" is true, find one that's furthest
+ /// away from the index (but before any index that's occupied).
+ // FIXME: This whole method should go away in future. It should
+ // always be possible to insert code between existing indices.
+ SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
+ if (index == getZeroIndex())
+ return getInvalidIndex();
+
+ index = index.getBaseIndex();
+ SlotIndex prevIndex = index.getPrevIndex();
+
+ if (prevIndex == getZeroIndex())
+ return getInvalidIndex();
+
+ // Try to reuse existing index objects with null-instrs.
+ if (getInstructionFromIndex(prevIndex) == 0) {
+ if (furthest) {
+ while (getInstructionFromIndex(prevIndex) == 0 &&
+ prevIndex != getZeroIndex()) {
+ prevIndex = prevIndex.getPrevIndex();
+ }
+
+ prevIndex = prevIndex.getNextIndex();
+ }
+
+ assert(getInstructionFromIndex(prevIndex) == 0 && "Index list is broken.");
+
+ return prevIndex;
+ }
+
+ int dist = prevIndex.distance(index);
+
+ // Double check that the spacing between this instruction and
+ // the last is sane.
+ assert(dist >= SlotIndex::NUM &&
+ "Distance between indexes too small.");
+
+ // If there's no gap return an invalid index.
+ if (dist < 2*SlotIndex::NUM) {
+ return getInvalidIndex();
+ }
+
+ // Otherwise insert new index entries into the list using the
+ // gap in the numbering.
+ IndexListEntry *newEntry =
+ createEntry(0, prevIndex.entry().getIndex() + SlotIndex::NUM);
+
+ insert(&index.entry(), newEntry);
+
+ // And return a pointer to the entry at the start of the gap.
+ return index.getPrevIndex();
+ }
+
+ /// Insert the given machine instruction into the mapping at the given
+ /// index.
+ void insertMachineInstrInMaps(MachineInstr *mi, SlotIndex index) {
+ index = index.getBaseIndex();
+ IndexListEntry *miEntry = &index.entry();
+ assert(miEntry->getInstr() == 0 && "Index already in use.");
+ miEntry->setInstr(mi);
+
+ assert(mi2iMap.find(mi) == mi2iMap.end() &&
+ "MachineInstr already has an index.");
+
+ mi2iMap.insert(std::make_pair(mi, index));
+ }
+
+ /// Remove the given machine instruction from the mapping.
+ void removeMachineInstrFromMaps(MachineInstr *mi) {
+ // remove index -> MachineInstr and
+ // MachineInstr -> index mappings
+ Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
+ if (mi2iItr != mi2iMap.end()) {
+ IndexListEntry *miEntry(&mi2iItr->second.entry());
+ assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
+ // FIXME: Eventually we want to actually delete these indexes.
+ miEntry->setInstr(0);
+ mi2iMap.erase(mi2iItr);
+ }
+ }
+
+ /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
+ /// maps used by register allocator.
+ void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
+ Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
+ if (mi2iItr == mi2iMap.end())
+ return;
+ SlotIndex replaceBaseIndex = mi2iItr->second;
+ IndexListEntry *miEntry(&replaceBaseIndex.entry());
+ assert(miEntry->getInstr() == mi &&
+ "Mismatched instruction in index tables.");
+ miEntry->setInstr(newMI);
+ mi2iMap.erase(mi2iItr);
+ mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
+ }
+
+ };
+
+
+}
+
+#endif // LLVM_CODEGEN_LIVEINDEX_H
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include <algorithm>
using namespace llvm;
-// Print a LiveIndex to a raw_ostream.
-void LiveIndex::print(raw_ostream &os) const {
- os << (index & ~PHI_BIT);
-}
-
// An example for liveAt():
//
// this = [1,4), liveAt(0) will return false. The instruction defining this
// variable it represents. This is because slot 1 is used (def slot) and spans
// up to slot 3 (store slot).
//
-bool LiveInterval::liveAt(LiveIndex I) const {
+bool LiveInterval::liveAt(SlotIndex I) const {
Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
if (r == ranges.begin())
// liveBeforeAndAt - Check if the interval is live at the index and the index
// just before it. If index is liveAt, check if it starts a new live range.
// If it does, then check if the previous live range ends at index-1.
-bool LiveInterval::liveBeforeAndAt(LiveIndex I) const {
+bool LiveInterval::liveBeforeAndAt(SlotIndex I) const {
Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
if (r == ranges.begin())
/// overlaps - Return true if the live interval overlaps a range specified
/// by [Start, End).
-bool LiveInterval::overlaps(LiveIndex Start, LiveIndex End) const {
+bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
assert(Start < End && "Invalid range");
const_iterator I = begin();
const_iterator E = end();
/// specified by I to end at the specified endpoint. To do this, we should
/// merge and eliminate all ranges that this will overlap with. The iterator is
/// not invalidated.
-void LiveInterval::extendIntervalEndTo(Ranges::iterator I, LiveIndex NewEnd) {
+void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
assert(I != ranges.end() && "Not a valid interval!");
VNInfo *ValNo = I->valno;
- LiveIndex OldEnd = I->end;
+ SlotIndex OldEnd = I->end;
// Search for the first interval that we can't merge with.
Ranges::iterator MergeTo = next(I);
ranges.erase(next(I), MergeTo);
// Update kill info.
- ValNo->removeKills(OldEnd, I->end.prevSlot_());
+ ValNo->removeKills(OldEnd, I->end.getPrevSlot());
// If the newly formed range now touches the range after it and if they have
// the same value number, merge the two ranges into one range.
/// specified by I to start at the specified endpoint. To do this, we should
/// merge and eliminate all ranges that this will overlap with.
LiveInterval::Ranges::iterator
-LiveInterval::extendIntervalStartTo(Ranges::iterator I, LiveIndex NewStart) {
+LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) {
assert(I != ranges.end() && "Not a valid interval!");
VNInfo *ValNo = I->valno;
LiveInterval::iterator
LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
- LiveIndex Start = LR.start, End = LR.end;
+ SlotIndex Start = LR.start, End = LR.end;
iterator it = std::upper_bound(From, ranges.end(), Start);
// If the inserted interval starts in the middle or right at the end of
/// isInOneLiveRange - Return true if the range specified is entirely in
/// a single LiveRange of the live interval.
-bool LiveInterval::isInOneLiveRange(LiveIndex Start, LiveIndex End) {
+bool LiveInterval::isInOneLiveRange(SlotIndex Start, SlotIndex End) {
Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
if (I == ranges.begin())
return false;
/// removeRange - Remove the specified range from this interval. Note that
/// the range must be in a single LiveRange in its entirety.
-void LiveInterval::removeRange(LiveIndex Start, LiveIndex End,
+void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
bool RemoveDeadValNo) {
// Find the LiveRange containing this span.
Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
}
// Otherwise, we are splitting the LiveRange into two pieces.
- LiveIndex OldEnd = I->end;
+ SlotIndex OldEnd = I->end;
I->end = Start; // Trim the old interval.
// Insert the new one.
ValNo->setIsUnused(true);
}
}
-
-/// scaleNumbering - Renumber VNI and ranges to provide gaps for new
-/// instructions.
-
-void LiveInterval::scaleNumbering(unsigned factor) {
- // Scale ranges.
- for (iterator RI = begin(), RE = end(); RI != RE; ++RI) {
- RI->start = RI->start.scale(factor);
- RI->end = RI->end.scale(factor);
- }
-
- // Scale VNI info.
- for (vni_iterator VNI = vni_begin(), VNIE = vni_end(); VNI != VNIE; ++VNI) {
- VNInfo *vni = *VNI;
-
- if (vni->isDefAccurate())
- vni->def = vni->def.scale(factor);
-
- for (unsigned i = 0; i < vni->kills.size(); ++i) {
- if (!vni->kills[i].isPHIIndex())
- vni->kills[i] = vni->kills[i].scale(factor);
- }
- }
-}
-
/// getLiveRangeContaining - Return the live range that contains the
/// specified index, or null if there is none.
LiveInterval::const_iterator
-LiveInterval::FindLiveRangeContaining(LiveIndex Idx) const {
+LiveInterval::FindLiveRangeContaining(SlotIndex Idx) const {
const_iterator It = std::upper_bound(begin(), end(), Idx);
if (It != ranges.begin()) {
--It;
}
LiveInterval::iterator
-LiveInterval::FindLiveRangeContaining(LiveIndex Idx) {
+LiveInterval::FindLiveRangeContaining(SlotIndex Idx) {
iterator It = std::upper_bound(begin(), end(), Idx);
if (It != begin()) {
--It;
/// findDefinedVNInfo - Find the VNInfo defined by the specified
/// index (register interval).
-VNInfo *LiveInterval::findDefinedVNInfoForRegInt(LiveIndex Idx) const {
+VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const {
for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end();
i != e; ++i) {
if ((*i)->def == Idx)
/// join - Join two live intervals (this, and other) together. This applies
/// mappings to the value numbers in the LHS/RHS intervals as specified. If
/// the intervals are not joinable, this aborts.
-void LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments,
+void LiveInterval::join(LiveInterval &Other,
+ const int *LHSValNoAssignments,
const int *RHSValNoAssignments,
SmallVector<VNInfo*, 16> &NewVNInfo,
MachineRegisterInfo *MRI) {
/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
/// current interval, it will replace the value numbers of the overlaped
/// live ranges with the specified value number.
-void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
- const VNInfo *RHSValNo, VNInfo *LHSValNo) {
+void LiveInterval::MergeValueInAsValue(
+ const LiveInterval &RHS,
+ const VNInfo *RHSValNo, VNInfo *LHSValNo) {
SmallVector<VNInfo*, 4> ReplacedValNos;
iterator IP = begin();
for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
if (I->valno != RHSValNo)
continue;
- LiveIndex Start = I->start, End = I->end;
+ SlotIndex Start = I->start, End = I->end;
IP = std::upper_bound(IP, end(), Start);
// If the start of this range overlaps with an existing liverange, trim it.
if (IP != begin() && IP[-1].end > Start) {
/// MergeInClobberRanges - For any live ranges that are not defined in the
/// current interval, but are defined in the Clobbers interval, mark them
/// used with an unknown definition value.
-void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
+void LiveInterval::MergeInClobberRanges(LiveIntervals &li_,
+ const LiveInterval &Clobbers,
BumpPtrAllocator &VNInfoAllocator) {
if (Clobbers.empty()) return;
ClobberValNo = UnusedValNo;
else {
UnusedValNo = ClobberValNo =
- getNextValue(LiveIndex(), 0, false, VNInfoAllocator);
+ getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator);
ValNoMaps.insert(std::make_pair(I->valno, ClobberValNo));
}
bool Done = false;
- LiveIndex Start = I->start, End = I->end;
+ SlotIndex Start = I->start, End = I->end;
// If a clobber range starts before an existing range and ends after
// it, the clobber range will need to be split into multiple ranges.
// Loop until the entire clobber range is handled.
while (!Done) {
Done = true;
IP = std::upper_bound(IP, end(), Start);
- LiveIndex SubRangeStart = Start;
- LiveIndex SubRangeEnd = End;
+ SlotIndex SubRangeStart = Start;
+ SlotIndex SubRangeEnd = End;
// If the start of this range overlaps with an existing liverange, trim it.
if (IP != begin() && IP[-1].end > SubRangeStart) {
}
}
-void LiveInterval::MergeInClobberRange(LiveIndex Start,
- LiveIndex End,
+void LiveInterval::MergeInClobberRange(LiveIntervals &li_,
+ SlotIndex Start,
+ SlotIndex End,
BumpPtrAllocator &VNInfoAllocator) {
// Find a value # to use for the clobber ranges. If there is already a value#
// for unknown values, use it.
VNInfo *ClobberValNo =
- getNextValue(LiveIndex(), 0, false, VNInfoAllocator);
+ getNextValue(li_.getInvalidIndex(), 0, false, VNInfoAllocator);
iterator IP = begin();
IP = std::upper_bound(IP, end(), Start);
OS << "-(";
for (unsigned j = 0; j != ee; ++j) {
OS << vni->kills[j];
- if (vni->kills[j].isPHIIndex())
- OS << "*";
if (j != ee-1)
OS << " ";
}
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/ProcessImplicitDefs.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
}
AU.addRequiredID(TwoAddressInstructionPassID);
+ AU.addPreserved<ProcessImplicitDefs>();
+ AU.addRequired<ProcessImplicitDefs>();
+ AU.addPreserved<SlotIndexes>();
+ AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
E = r2iMap_.end(); I != E; ++I)
delete I->second;
- MBB2IdxMap.clear();
- Idx2MBBMap.clear();
- mi2iMap_.clear();
- i2miMap_.clear();
r2iMap_.clear();
- terminatorGaps.clear();
phiJoinCopies.clear();
// Release VNInfo memroy regions after all VNInfo objects are dtor'd.
}
}
-static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
- unsigned OpIdx, const TargetInstrInfo *tii_){
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
- Reg == SrcReg)
- return true;
-
- if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
- return true;
- if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
- return true;
- return false;
-}
-
-/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
-/// there is one implicit_def for each use. Add isUndef marker to
-/// implicit_def defs and their uses.
-void LiveIntervals::processImplicitDefs() {
- SmallSet<unsigned, 8> ImpDefRegs;
- SmallVector<MachineInstr*, 8> ImpDefMIs;
- MachineBasicBlock *Entry = mf_->begin();
- SmallPtrSet<MachineBasicBlock*,16> Visited;
- for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
- DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
- DFI != E; ++DFI) {
- MachineBasicBlock *MBB = *DFI;
- for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
- I != E; ) {
- MachineInstr *MI = &*I;
- ++I;
- if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
- unsigned Reg = MI->getOperand(0).getReg();
- ImpDefRegs.insert(Reg);
- if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
- for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
- ImpDefRegs.insert(*SS);
- }
- ImpDefMIs.push_back(MI);
- continue;
- }
-
- if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
- MachineOperand &MO = MI->getOperand(2);
- if (ImpDefRegs.count(MO.getReg())) {
- // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2
- // This is an identity copy, eliminate it now.
- if (MO.isKill()) {
- LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
- vi.removeKill(MI);
- }
- MI->eraseFromParent();
- continue;
- }
- }
-
- bool ChangedToImpDef = false;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand& MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isUse() || MO.isUndef())
- continue;
- unsigned Reg = MO.getReg();
- if (!Reg)
- continue;
- if (!ImpDefRegs.count(Reg))
- continue;
- // Use is a copy, just turn it into an implicit_def.
- if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) {
- bool isKill = MO.isKill();
- MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
- for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
- MI->RemoveOperand(j);
- if (isKill) {
- ImpDefRegs.erase(Reg);
- LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
- vi.removeKill(MI);
- }
- ChangedToImpDef = true;
- break;
- }
-
- MO.setIsUndef();
- if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
- // Make sure other uses of
- for (unsigned j = i+1; j != e; ++j) {
- MachineOperand &MOJ = MI->getOperand(j);
- if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
- MOJ.setIsUndef();
- }
- ImpDefRegs.erase(Reg);
- }
- }
-
- if (ChangedToImpDef) {
- // Backtrack to process this new implicit_def.
- --I;
- } else {
- for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
- MachineOperand& MO = MI->getOperand(i);
- if (!MO.isReg() || !MO.isDef())
- continue;
- ImpDefRegs.erase(MO.getReg());
- }
- }
- }
-
- // Any outstanding liveout implicit_def's?
- for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
- MachineInstr *MI = ImpDefMIs[i];
- unsigned Reg = MI->getOperand(0).getReg();
- if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
- !ImpDefRegs.count(Reg)) {
- // Delete all "local" implicit_def's. That include those which define
- // physical registers since they cannot be liveout.
- MI->eraseFromParent();
- continue;
- }
-
- // If there are multiple defs of the same register and at least one
- // is not an implicit_def, do not insert implicit_def's before the
- // uses.
- bool Skip = false;
- for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
- DE = mri_->def_end(); DI != DE; ++DI) {
- if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
- Skip = true;
- break;
- }
- }
- if (Skip)
- continue;
-
- // The only implicit_def which we want to keep are those that are live
- // out of its block.
- MI->eraseFromParent();
-
- for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
- UE = mri_->use_end(); UI != UE; ) {
- MachineOperand &RMO = UI.getOperand();
- MachineInstr *RMI = &*UI;
- ++UI;
- MachineBasicBlock *RMBB = RMI->getParent();
- if (RMBB == MBB)
- continue;
-
- // Turn a copy use into an implicit_def.
- unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
- if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
- Reg == SrcReg) {
- RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
- for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
- RMI->RemoveOperand(j);
- continue;
- }
-
- const TargetRegisterClass* RC = mri_->getRegClass(Reg);
- unsigned NewVReg = mri_->createVirtualRegister(RC);
- RMO.setReg(NewVReg);
- RMO.setIsUndef();
- RMO.setIsKill();
- }
- }
- ImpDefRegs.clear();
- ImpDefMIs.clear();
- }
-}
-
-
-void LiveIntervals::computeNumbering() {
- Index2MiMap OldI2MI = i2miMap_;
- std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
-
- Idx2MBBMap.clear();
- MBB2IdxMap.clear();
- mi2iMap_.clear();
- i2miMap_.clear();
- terminatorGaps.clear();
- phiJoinCopies.clear();
-
- FunctionSize = 0;
-
- // Number MachineInstrs and MachineBasicBlocks.
- // Initialize MBB indexes to a sentinal.
- MBB2IdxMap.resize(mf_->getNumBlockIDs(),
- std::make_pair(LiveIndex(),LiveIndex()));
-
- LiveIndex MIIndex;
- for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
- MBB != E; ++MBB) {
- LiveIndex StartIdx = MIIndex;
-
- // Insert an empty slot at the beginning of each block.
- MIIndex = getNextIndex(MIIndex);
- i2miMap_.push_back(0);
-
- for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
- I != E; ++I) {
-
- if (I == MBB->getFirstTerminator()) {
- // Leave a gap for before terminators, this is where we will point
- // PHI kills.
- LiveIndex tGap(true, MIIndex);
- bool inserted =
- terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second;
- assert(inserted &&
- "Multiple 'first' terminators encountered during numbering.");
- inserted = inserted; // Avoid compiler warning if assertions turned off.
- i2miMap_.push_back(0);
-
- MIIndex = getNextIndex(MIIndex);
- }
-
- bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
- assert(inserted && "multiple MachineInstr -> index mappings");
- inserted = true;
- i2miMap_.push_back(I);
- MIIndex = getNextIndex(MIIndex);
- FunctionSize++;
-
- // Insert max(1, numdefs) empty slots after every instruction.
- unsigned Slots = I->getDesc().getNumDefs();
- if (Slots == 0)
- Slots = 1;
- while (Slots--) {
- MIIndex = getNextIndex(MIIndex);
- i2miMap_.push_back(0);
- }
-
- }
-
- if (MBB->getFirstTerminator() == MBB->end()) {
- // Leave a gap for before terminators, this is where we will point
- // PHI kills.
- LiveIndex tGap(true, MIIndex);
- bool inserted =
- terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second;
- assert(inserted &&
- "Multiple 'first' terminators encountered during numbering.");
- inserted = inserted; // Avoid compiler warning if assertions turned off.
- i2miMap_.push_back(0);
-
- MIIndex = getNextIndex(MIIndex);
- }
-
- // Set the MBB2IdxMap entry for this MBB.
- MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, getPrevSlot(MIIndex));
- Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
- }
-
- std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
-
- if (!OldI2MI.empty())
- for (iterator OI = begin(), OE = end(); OI != OE; ++OI) {
- for (LiveInterval::iterator LI = OI->second->begin(),
- LE = OI->second->end(); LI != LE; ++LI) {
-
- // Remap the start index of the live range to the corresponding new
- // number, or our best guess at what it _should_ correspond to if the
- // original instruction has been erased. This is either the following
- // instruction or its predecessor.
- unsigned index = LI->start.getVecIndex();
- LiveIndex::Slot offset = LI->start.getSlot();
- if (LI->start.isLoad()) {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
- // Take the pair containing the index
- std::vector<IdxMBBPair>::const_iterator J =
- (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
-
- LI->start = getMBBStartIdx(J->second);
- } else {
- LI->start = LiveIndex(
- LiveIndex(mi2iMap_[OldI2MI[index]]),
- (LiveIndex::Slot)offset);
- }
-
- // Remap the ending index in the same way that we remapped the start,
- // except for the final step where we always map to the immediately
- // following instruction.
- index = (getPrevSlot(LI->end)).getVecIndex();
- offset = LI->end.getSlot();
- if (LI->end.isLoad()) {
- // VReg dies at end of block.
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
- --I;
-
- LI->end = getNextSlot(getMBBEndIdx(I->second));
- } else {
- unsigned idx = index;
- while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
-
- if (index != OldI2MI.size())
- LI->end =
- LiveIndex(mi2iMap_[OldI2MI[index]],
- (idx == index ? offset : LiveIndex::LOAD));
- else
- LI->end =
- LiveIndex(LiveIndex::NUM * i2miMap_.size());
- }
- }
-
- for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
- VNE = OI->second->vni_end(); VNI != VNE; ++VNI) {
- VNInfo* vni = *VNI;
-
- // Remap the VNInfo def index, which works the same as the
- // start indices above. VN's with special sentinel defs
- // don't need to be remapped.
- if (vni->isDefAccurate() && !vni->isUnused()) {
- unsigned index = vni->def.getVecIndex();
- LiveIndex::Slot offset = vni->def.getSlot();
- if (vni->def.isLoad()) {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def);
- // Take the pair containing the index
- std::vector<IdxMBBPair>::const_iterator J =
- (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
-
- vni->def = getMBBStartIdx(J->second);
- } else {
- vni->def = LiveIndex(mi2iMap_[OldI2MI[index]], offset);
- }
- }
-
- // Remap the VNInfo kill indices, which works the same as
- // the end indices above.
- for (size_t i = 0; i < vni->kills.size(); ++i) {
- unsigned index = getPrevSlot(vni->kills[i]).getVecIndex();
- LiveIndex::Slot offset = vni->kills[i].getSlot();
-
- if (vni->kills[i].isLoad()) {
- assert("Value killed at a load slot.");
- /*std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
- --I;
-
- vni->kills[i] = getMBBEndIdx(I->second);*/
- } else {
- if (vni->kills[i].isPHIIndex()) {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
- --I;
- vni->kills[i] = terminatorGaps[I->second];
- } else {
- assert(OldI2MI[index] != 0 &&
- "Kill refers to instruction not present in index maps.");
- vni->kills[i] = LiveIndex(mi2iMap_[OldI2MI[index]], offset);
- }
-
- /*
- unsigned idx = index;
- while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
-
- if (index != OldI2MI.size())
- vni->kills[i] = mi2iMap_[OldI2MI[index]] +
- (idx == index ? offset : 0);
- else
- vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
- */
- }
- }
- }
- }
-}
-
-void LiveIntervals::scaleNumbering(int factor) {
- // Need to
- // * scale MBB begin and end points
- // * scale all ranges.
- // * Update VNI structures.
- // * Scale instruction numberings
-
- // Scale the MBB indices.
- Idx2MBBMap.clear();
- for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end();
- MBB != MBBE; ++MBB) {
- std::pair<LiveIndex, LiveIndex> &mbbIndices = MBB2IdxMap[MBB->getNumber()];
- mbbIndices.first = mbbIndices.first.scale(factor);
- mbbIndices.second = mbbIndices.second.scale(factor);
- Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB));
- }
- std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
-
- // Scale terminator gaps.
- for (DenseMap<MachineBasicBlock*, LiveIndex>::iterator
- TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
- TGI != TGE; ++TGI) {
- terminatorGaps[TGI->first] = TGI->second.scale(factor);
- }
-
- // Scale the intervals.
- for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
- LI->second->scaleNumbering(factor);
- }
-
- // Scale MachineInstrs.
- Mi2IndexMap oldmi2iMap = mi2iMap_;
- LiveIndex highestSlot;
- for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end();
- MI != ME; ++MI) {
- LiveIndex newSlot = MI->second.scale(factor);
- mi2iMap_[MI->first] = newSlot;
- highestSlot = std::max(highestSlot, newSlot);
- }
-
- unsigned highestVIndex = highestSlot.getVecIndex();
- i2miMap_.clear();
- i2miMap_.resize(highestVIndex + 1);
- for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end();
- MI != ME; ++MI) {
- i2miMap_[MI->second.getVecIndex()] = const_cast<MachineInstr *>(MI->first);
- }
-
-}
-
-
/// runOnMachineFunction - Register allocate the whole function
///
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
tii_ = tm_->getInstrInfo();
aa_ = &getAnalysis<AliasAnalysis>();
lv_ = &getAnalysis<LiveVariables>();
+ indexes_ = &getAnalysis<SlotIndexes>();
allocatableRegs_ = tri_->getAllocatableSet(fn);
- processImplicitDefs();
- computeNumbering();
computeIntervals();
performEarlyCoalescing();
VirtRegMap &vrm, unsigned reg) {
for (LiveInterval::Ranges::const_iterator
I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
- for (LiveIndex index = getBaseIndex(I->start),
- end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end;
- index = getNextIndex(index)) {
+ for (SlotIndex index = I->start.getBaseIndex(),
+ end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
+ index != end;
+ index = index.getNextIndex()) {
// skip deleted instructions
while (index != end && !getInstructionFromIndex(index))
- index = getNextIndex(index);
+ index = index.getNextIndex();
if (index == end) break;
MachineInstr *MI = getInstructionFromIndex(index);
SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
for (LiveInterval::Ranges::const_iterator
I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
- for (LiveIndex index = getBaseIndex(I->start),
- end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end;
- index = getNextIndex(index)) {
+ for (SlotIndex index = I->start.getBaseIndex(),
+ end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
+ index != end;
+ index = index.getNextIndex()) {
// Skip deleted instructions.
MachineInstr *MI = 0;
while (index != end) {
MI = getInstructionFromIndex(index);
if (MI)
break;
- index = getNextIndex(index);
+ index = index.getNextIndex();
}
if (index == end) break;
void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
MachineBasicBlock::iterator mi,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
unsigned MOIdx,
LiveInterval &interval) {
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
if (interval.empty()) {
// Get the Idx of the defining instructions.
- LiveIndex defIndex = getDefIndex(MIIdx);
+ SlotIndex defIndex = MIIdx.getDefIndex();
// Earlyclobbers move back one, so that they overlap the live range
// of inputs.
if (MO.isEarlyClobber())
- defIndex = getUseIndex(MIIdx);
+ defIndex = MIIdx.getUseIndex();
VNInfo *ValNo;
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
// will be a single kill, in MBB, which comes after the definition.
if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
// FIXME: what about dead vars?
- LiveIndex killIdx;
+ SlotIndex killIdx;
if (vi.Kills[0] != mi)
- killIdx = getNextSlot(getUseIndex(getInstructionIndex(vi.Kills[0])));
- else if (MO.isEarlyClobber())
- // Earlyclobbers that die in this instruction move up one extra, to
- // compensate for having the starting point moved back one. This
- // gets them to overlap the live range of other outputs.
- killIdx = getNextSlot(getNextSlot(defIndex));
+ killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
else
- killIdx = getNextSlot(defIndex);
+ killIdx = defIndex.getStoreIndex();
// If the kill happens after the definition, we have an intra-block
// live range.
// of the defining block, potentially live across some blocks, then is
// live into some number of blocks, but gets killed. Start by adding a
// range that goes from this definition to the end of the defining block.
- LiveRange NewLR(defIndex, getNextSlot(getMBBEndIdx(mbb)), ValNo);
+ LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(),
+ ValNo);
DEBUG(errs() << " +" << NewLR);
interval.addRange(NewLR);
// live interval.
for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
E = vi.AliveBlocks.end(); I != E; ++I) {
- LiveRange LR(getMBBStartIdx(*I),
- getNextSlot(getMBBEndIdx(*I)), // MBB ends at -1.
- ValNo);
+ LiveRange LR(
+ getMBBStartIdx(mf_->getBlockNumbered(*I)),
+ getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(),
+ ValNo);
interval.addRange(LR);
DEBUG(errs() << " +" << LR);
}
// block to the 'use' slot of the killing instruction.
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
- LiveIndex killIdx =
- getNextSlot(getUseIndex(getInstructionIndex(Kill)));
+ SlotIndex killIdx =
+ getInstructionIndex(Kill).getDefIndex();
LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo);
interval.addRange(LR);
ValNo->addKill(killIdx);
// need to take the LiveRegion that defines this register and split it
// into two values.
assert(interval.containsOneValue());
- LiveIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
- LiveIndex RedefIndex = getDefIndex(MIIdx);
+ SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex();
+ SlotIndex RedefIndex = MIIdx.getDefIndex();
if (MO.isEarlyClobber())
- RedefIndex = getUseIndex(MIIdx);
+ RedefIndex = MIIdx.getUseIndex();
const LiveRange *OldLR =
- interval.getLiveRangeContaining(getPrevSlot(RedefIndex));
+ interval.getLiveRangeContaining(RedefIndex.getUseIndex());
VNInfo *OldValNo = OldLR->valno;
// Delete the initial value, which should be short and continuous,
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
if (MO.isDead())
- interval.addRange(
- LiveRange(RedefIndex, MO.isEarlyClobber() ?
- getNextSlot(getNextSlot(RedefIndex)) :
- getNextSlot(RedefIndex), OldValNo));
+ interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
+ OldValNo));
DEBUG({
errs() << " RESULT: ";
VNInfo *VNI = interval.getValNumInfo(0);
MachineInstr *Killer = vi.Kills[0];
phiJoinCopies.push_back(Killer);
- LiveIndex Start = getMBBStartIdx(Killer->getParent());
- LiveIndex End =
- getNextSlot(getUseIndex(getInstructionIndex(Killer)));
+ SlotIndex Start = getMBBStartIdx(Killer->getParent());
+ SlotIndex End = getInstructionIndex(Killer).getDefIndex();
DEBUG({
errs() << " Removing [" << Start << "," << End << "] from: ";
interval.print(errs(), tri_);
assert(interval.ranges.size() == 1 &&
"Newly discovered PHI interval has >1 ranges.");
MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex());
- VNI->addKill(terminatorGaps[killMBB]);
+ VNI->addKill(indexes_->getTerminatorGap(killMBB));
VNI->setHasPHIKill(true);
DEBUG({
errs() << " RESULT: ";
// Replace the interval with one of a NEW value number. Note that this
// value number isn't actually defined by an instruction, weird huh? :)
LiveRange LR(Start, End,
- interval.getNextValue(LiveIndex(mbb->getNumber()),
- 0, false, VNInfoAllocator));
+ interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true),
+ 0, false, VNInfoAllocator));
LR.valno->setIsPHIDef(true);
DEBUG(errs() << " replace range with " << LR);
interval.addRange(LR);
// In the case of PHI elimination, each variable definition is only
// live until the end of the block. We've already taken care of the
// rest of the live range.
- LiveIndex defIndex = getDefIndex(MIIdx);
+ SlotIndex defIndex = MIIdx.getDefIndex();
if (MO.isEarlyClobber())
- defIndex = getUseIndex(MIIdx);
+ defIndex = MIIdx.getUseIndex();
VNInfo *ValNo;
MachineInstr *CopyMI = NULL;
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
- LiveIndex killIndex = getNextSlot(getMBBEndIdx(mbb));
+ SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex();
LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
- ValNo->addKill(terminatorGaps[mbb]);
+ ValNo->addKill(indexes_->getTerminatorGap(mbb));
ValNo->setHasPHIKill(true);
DEBUG(errs() << " +" << LR);
}
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
LiveInterval &interval,
MachineInstr *CopyMI) {
printRegName(interval.reg, tri_);
});
- LiveIndex baseIndex = MIIdx;
- LiveIndex start = getDefIndex(baseIndex);
+ SlotIndex baseIndex = MIIdx;
+ SlotIndex start = baseIndex.getDefIndex();
// Earlyclobbers move back one.
if (MO.isEarlyClobber())
- start = getUseIndex(MIIdx);
- LiveIndex end = start;
+ start = MIIdx.getUseIndex();
+ SlotIndex end = start;
// If it is not used after definition, it is considered dead at
// the instruction defining it. Hence its interval is:
// advance below compensates.
if (MO.isDead()) {
DEBUG(errs() << " dead");
- if (MO.isEarlyClobber())
- end = getNextSlot(getNextSlot(start));
- else
- end = getNextSlot(start);
+ end = start.getStoreIndex();
goto exit;
}
// If it is not dead on definition, it must be killed by a
// subsequent instruction. Hence its interval is:
// [defSlot(def), useSlot(kill)+1)
- baseIndex = getNextIndex(baseIndex);
+ baseIndex = baseIndex.getNextIndex();
while (++mi != MBB->end()) {
- while (baseIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(baseIndex) == 0)
- baseIndex = getNextIndex(baseIndex);
+
+ if (getInstructionFromIndex(baseIndex) == 0)
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
if (mi->killsRegister(interval.reg, tri_)) {
DEBUG(errs() << " killed");
- end = getNextSlot(getUseIndex(baseIndex));
+ end = baseIndex.getDefIndex();
goto exit;
} else {
int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_);
if (DefIdx != -1) {
if (mi->isRegTiedToUseOperand(DefIdx)) {
// Two-address instruction.
- end = getDefIndex(baseIndex);
- if (mi->getOperand(DefIdx).isEarlyClobber())
- end = getUseIndex(baseIndex);
+ end = baseIndex.getDefIndex();
+ assert(!mi->getOperand(DefIdx).isEarlyClobber() &&
+ "Two address instruction is an early clobber?");
} else {
// Another instruction redefines the register before it is ever read.
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
DEBUG(errs() << " dead");
- end = getNextSlot(start);
+ end = start.getStoreIndex();
}
goto exit;
}
}
- baseIndex = getNextIndex(baseIndex);
+ baseIndex = baseIndex.getNextIndex();
}
// The only case we should have a dead physreg here without a killing or
// instruction where we know it's dead is if it is live-in to the function
// and never used. Another possible case is the implicit use of the
// physical register has been deleted by two-address pass.
- end = getNextSlot(start);
+ end = start.getStoreIndex();
exit:
assert(start < end && "did not find end of interval?");
void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator MI,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
MachineOperand& MO,
unsigned MOIdx) {
if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
}
void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
- LiveIndex MIIdx,
+ SlotIndex MIIdx,
LiveInterval &interval, bool isAlias) {
DEBUG({
errs() << "\t\tlivein register: ";
// Look for kills, if it reaches a def before it's killed, then it shouldn't
// be considered a livein.
MachineBasicBlock::iterator mi = MBB->begin();
- LiveIndex baseIndex = MIIdx;
- LiveIndex start = baseIndex;
- while (baseIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(baseIndex) == 0)
- baseIndex = getNextIndex(baseIndex);
- LiveIndex end = baseIndex;
+ SlotIndex baseIndex = MIIdx;
+ SlotIndex start = baseIndex;
+ if (getInstructionFromIndex(baseIndex) == 0)
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
+
+ SlotIndex end = baseIndex;
bool SeenDefUse = false;
while (mi != MBB->end()) {
if (mi->killsRegister(interval.reg, tri_)) {
DEBUG(errs() << " killed");
- end = getNextSlot(getUseIndex(baseIndex));
+ end = baseIndex.getDefIndex();
SeenDefUse = true;
break;
} else if (mi->modifiesRegister(interval.reg, tri_)) {
// it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
DEBUG(errs() << " dead");
- end = getNextSlot(getDefIndex(start));
+ end = start.getStoreIndex();
SeenDefUse = true;
break;
}
- baseIndex = getNextIndex(baseIndex);
++mi;
if (mi != MBB->end()) {
- while (baseIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(baseIndex) == 0)
- baseIndex = getNextIndex(baseIndex);
+ baseIndex = indexes_->getNextNonNullIndex(baseIndex);
}
}
if (!SeenDefUse) {
if (isAlias) {
DEBUG(errs() << " dead");
- end = getNextSlot(getDefIndex(MIIdx));
+ end = MIIdx.getStoreIndex();
} else {
DEBUG(errs() << " live through");
end = baseIndex;
}
VNInfo *vni =
- interval.getNextValue(LiveIndex(MBB->getNumber()),
+ interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true),
0, false, VNInfoAllocator);
vni->setIsPHIDef(true);
LiveRange LR(start, end, vni);
MachineInstr *PHICopy = OtherCopies[i];
DEBUG(errs() << "Moving: " << *PHICopy);
- LiveIndex MIIndex = getInstructionIndex(PHICopy);
- LiveIndex DefIndex = getDefIndex(MIIndex);
+ SlotIndex MIIndex = getInstructionIndex(PHICopy);
+ SlotIndex DefIndex = MIIndex.getDefIndex();
LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- LiveIndex StartIndex = SLR->start;
- LiveIndex EndIndex = SLR->end;
+ SlotIndex StartIndex = SLR->start;
+ SlotIndex EndIndex = SLR->end;
// Delete val# defined by the now identity copy and add the range from
// beginning of the mbb to the end of the range.
MachineInstr *PHICopy = IdentCopies[i];
DEBUG(errs() << "Coalescing: " << *PHICopy);
- LiveIndex MIIndex = getInstructionIndex(PHICopy);
- LiveIndex DefIndex = getDefIndex(MIIndex);
+ SlotIndex MIIndex = getInstructionIndex(PHICopy);
+ SlotIndex DefIndex = MIIndex.getDefIndex();
LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex);
- LiveIndex StartIndex = SLR->start;
- LiveIndex EndIndex = SLR->end;
+ SlotIndex StartIndex = SLR->start;
+ SlotIndex EndIndex = SLR->end;
// Delete val# defined by the now identity copy and add the range from
// beginning of the mbb to the end of the range.
}
// Remove the phi join and update the phi block liveness.
- LiveIndex MIIndex = getInstructionIndex(Join);
- LiveIndex UseIndex = getUseIndex(MIIndex);
- LiveIndex DefIndex = getDefIndex(MIIndex);
+ SlotIndex MIIndex = getInstructionIndex(Join);
+ SlotIndex UseIndex = MIIndex.getUseIndex();
+ SlotIndex DefIndex = MIIndex.getDefIndex();
LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex);
LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex);
DLR->valno->setCopy(0);
MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
// Track the index of the current machine instr.
- LiveIndex MIIndex = getMBBStartIdx(MBB);
+ SlotIndex MIIndex = getMBBStartIdx(MBB);
DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
}
// Skip over empty initial indices.
- while (MIIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(MIIndex) == 0)
- MIIndex = getNextIndex(MIIndex);
+ if (getInstructionFromIndex(MIIndex) == 0)
+ MIIndex = indexes_->getNextNonNullIndex(MIIndex);
for (; MI != miEnd; ++MI) {
DEBUG(errs() << MIIndex << "\t" << *MI);
else if (MO.isUndef())
UndefUses.push_back(MO.getReg());
}
-
- // Skip over the empty slots after each instruction.
- unsigned Slots = MI->getDesc().getNumDefs();
- if (Slots == 0)
- Slots = 1;
-
- while (Slots--)
- MIIndex = getNextIndex(MIIndex);
- // Skip over empty indices.
- while (MIIndex.getVecIndex() < i2miMap_.size() &&
- getInstructionFromIndex(MIIndex) == 0)
- MIIndex = getNextIndex(MIIndex);
+ // Move to the next instr slot.
+ MIIndex = indexes_->getNextNonNullIndex(MIIndex);
}
}
}
}
-bool LiveIntervals::findLiveInMBBs(
- LiveIndex Start, LiveIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
-
- bool ResVal = false;
- while (I != Idx2MBBMap.end()) {
- if (I->first >= End)
- break;
- MBBs.push_back(I->second);
- ResVal = true;
- ++I;
- }
- return ResVal;
-}
-
-bool LiveIntervals::findReachableMBBs(
- LiveIndex Start, LiveIndex End,
- SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
- std::vector<IdxMBBPair>::const_iterator I =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start);
-
- bool ResVal = false;
- while (I != Idx2MBBMap.end()) {
- if (I->first > End)
- break;
- MachineBasicBlock *MBB = I->second;
- if (getMBBEndIdx(MBB) > End)
- break;
- for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
- SE = MBB->succ_end(); SI != SE; ++SI)
- MBBs.push_back(*SI);
- ResVal = true;
- ++I;
- }
- return ResVal;
-}
-
LiveInterval* LiveIntervals::createInterval(unsigned reg) {
float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
return new LiveInterval(reg, Weight);
/// isValNoAvailableAt - Return true if the val# of the specified interval
/// which reaches the given instruction also reaches the specified use index.
bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
- LiveIndex UseIdx) const {
- LiveIndex Index = getInstructionIndex(MI);
+ SlotIndex UseIdx) const {
+ SlotIndex Index = getInstructionIndex(MI);
VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
return UI != li.end() && UI->valno == ValNo;
for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
re = mri_->use_end(); ri != re; ++ri) {
MachineInstr *UseMI = &*ri;
- LiveIndex UseIdx = getInstructionIndex(UseMI);
+ SlotIndex UseIdx = getInstructionIndex(UseMI);
if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
continue;
if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
/// returns true.
bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
VirtRegMap &vrm, MachineInstr *DefMI,
- LiveIndex InstrIdx,
+ SlotIndex InstrIdx,
SmallVector<unsigned, 2> &Ops,
bool isSS, int Slot, unsigned Reg) {
// If it is an implicit def instruction, just delete it.
vrm.transferSpillPts(MI, fmi);
vrm.transferRestorePts(MI, fmi);
vrm.transferEmergencySpills(MI, fmi);
- mi2iMap_.erase(MI);
- i2miMap_[InstrIdx.getVecIndex()] = fmi;
- mi2iMap_[fmi] = InstrIdx;
+ ReplaceMachineInstrInMaps(MI, fmi);
MI = MBB.insert(MBB.erase(MI), fmi);
++numFolds;
return true;
}
bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
- SmallPtrSet<MachineBasicBlock*, 4> MBBs;
- for (LiveInterval::Ranges::const_iterator
- I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
- std::vector<IdxMBBPair>::const_iterator II =
- std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
- if (II == Idx2MBBMap.end())
- continue;
- if (I->end > II->first) // crossing a MBB.
- return false;
- MBBs.insert(II->second);
- if (MBBs.size() > 1)
+ LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
+
+ MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+ if (mbb == 0)
+ return false;
+
+ for (++itr; itr != li.ranges.end(); ++itr) {
+ MachineBasicBlock *mbb2 =
+ indexes_->getMBBCoveringRange(itr->start, itr->end);
+
+ if (mbb2 != mbb)
return false;
}
+
return true;
}
/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
bool LiveIntervals::
rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
- bool TrySplit, LiveIndex index, LiveIndex end,
+ bool TrySplit, SlotIndex index, SlotIndex end,
MachineInstr *MI,
MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
unsigned Slot, int LdSlot,
if (HasUse) {
if (CreatedNewVReg) {
- LiveRange LR(getLoadIndex(index), getNextSlot(getUseIndex(index)),
- nI.getNextValue(LiveIndex(), 0, false,
- VNInfoAllocator));
+ LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
+ nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
DEBUG(errs() << " +" << LR);
nI.addRange(LR);
} else {
// Extend the split live interval to this def / use.
- LiveIndex End = getNextSlot(getUseIndex(index));
+ SlotIndex End = index.getDefIndex();
LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
nI.getValNumInfo(nI.getNumValNums()-1));
DEBUG(errs() << " +" << LR);
}
}
if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
- VNInfoAllocator));
+ LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
+ nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
DEBUG(errs() << " +" << LR);
nI.addRange(LR);
}
bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
const VNInfo *VNI,
MachineBasicBlock *MBB,
- LiveIndex Idx) const {
- LiveIndex End = getMBBEndIdx(MBB);
+ SlotIndex Idx) const {
+ SlotIndex End = getMBBEndIdx(MBB);
for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
- if (VNI->kills[j].isPHIIndex())
+ if (VNI->kills[j].isPHI())
continue;
- LiveIndex KillIdx = VNI->kills[j];
+ SlotIndex KillIdx = VNI->kills[j];
if (KillIdx > Idx && KillIdx < End)
return true;
}
/// during spilling.
namespace {
struct RewriteInfo {
- LiveIndex Index;
+ SlotIndex Index;
MachineInstr *MI;
bool HasUse;
bool HasDef;
- RewriteInfo(LiveIndex i, MachineInstr *mi, bool u, bool d)
+ RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d)
: Index(i), MI(mi), HasUse(u), HasDef(d) {}
};
std::vector<LiveInterval*> &NewLIs) {
bool AllCanFold = true;
unsigned NewVReg = 0;
- LiveIndex start = getBaseIndex(I->start);
- LiveIndex end = getNextIndex(getBaseIndex(getPrevSlot(I->end)));
+ SlotIndex start = I->start.getBaseIndex();
+ SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
// First collect all the def / use in this live range that will be rewritten.
// Make sure they are sorted according to instruction index.
MachineOperand &O = ri.getOperand();
++ri;
assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
- LiveIndex index = getInstructionIndex(MI);
+ SlotIndex index = getInstructionIndex(MI);
if (index < start || index >= end)
continue;
for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
RewriteInfo &rwi = RewriteMIs[i];
++i;
- LiveIndex index = rwi.Index;
+ SlotIndex index = rwi.Index;
bool MIHasUse = rwi.HasUse;
bool MIHasDef = rwi.HasDef;
MachineInstr *MI = rwi.MI;
if (MI != ReMatOrigDefMI || !CanDelete) {
bool HasKill = false;
if (!HasUse)
- HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
+ HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
else {
// If this is a two-address code, then this index starts a new VNInfo.
- const VNInfo *VNI = li.findDefinedVNInfoForRegInt(getDefIndex(index));
+ const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
if (VNI)
- HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
+ HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
}
DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
SpillIdxes.find(MBBId);
}
}
-bool LiveIntervals::alsoFoldARestore(int Id, LiveIndex index,
+bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
unsigned vr, BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
if (!RestoreMBBs[Id])
return false;
}
-void LiveIntervals::eraseRestoreInfo(int Id, LiveIndex index,
+void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
unsigned vr, BitVector &RestoreMBBs,
DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
if (!RestoreMBBs[Id])
std::vector<SRInfo> &Restores = RestoreIdxes[Id];
for (unsigned i = 0, e = Restores.size(); i != e; ++i)
if (Restores[i].index == index && Restores[i].vreg)
- Restores[i].index = LiveIndex();
+ Restores[i].index = SlotIndex();
}
/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
}
// Fill in the new live interval.
- LiveIndex index = getInstructionIndex(MI);
+ SlotIndex index = getInstructionIndex(MI);
if (HasUse) {
- LiveRange LR(getLoadIndex(index), getUseIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
+ LiveRange LR(index.getLoadIndex(), index.getUseIndex(),
+ nI.getNextValue(SlotIndex(), 0, false,
getVNInfoAllocator()));
DEBUG(errs() << " +" << LR);
nI.addRange(LR);
vrm.addRestorePoint(NewVReg, MI);
}
if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(LiveIndex(), 0, false,
+ LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
+ nI.getNextValue(SlotIndex(), 0, false,
getVNInfoAllocator()));
DEBUG(errs() << " +" << LR);
nI.addRange(LR);
if (vrm.getPreSplitReg(li.reg)) {
vrm.setIsSplitFromReg(li.reg, 0);
// Unset the split kill marker on the last use.
- LiveIndex KillIdx = vrm.getKillPoint(li.reg);
- if (KillIdx != LiveIndex()) {
+ SlotIndex KillIdx = vrm.getKillPoint(li.reg);
+ if (KillIdx != SlotIndex()) {
MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
assert(KillMI && "Last use disappeared?");
int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
while (Id != -1) {
std::vector<SRInfo> &spills = SpillIdxes[Id];
for (unsigned i = 0, e = spills.size(); i != e; ++i) {
- LiveIndex index = spills[i].index;
+ SlotIndex index = spills[i].index;
unsigned VReg = spills[i].vreg;
LiveInterval &nI = getOrCreateInterval(VReg);
bool isReMat = vrm.isReMaterialized(VReg);
if (FoundUse) {
// Also folded uses, do not issue a load.
eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
- nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+ nI.removeRange(index.getLoadIndex(), index.getDefIndex());
}
- nI.removeRange(getDefIndex(index), getStoreIndex(index));
+ nI.removeRange(index.getDefIndex(), index.getStoreIndex());
}
}
// Otherwise tell the spiller to issue a spill.
if (!Folded) {
LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
- bool isKill = LR->end == getStoreIndex(index);
+ bool isKill = LR->end == index.getStoreIndex();
if (!MI->registerDefIsDead(nI.reg))
// No need to spill a dead def.
vrm.addSpillPoint(VReg, isKill, MI);
while (Id != -1) {
std::vector<SRInfo> &restores = RestoreIdxes[Id];
for (unsigned i = 0, e = restores.size(); i != e; ++i) {
- LiveIndex index = restores[i].index;
- if (index == LiveIndex())
+ SlotIndex index = restores[i].index;
+ if (index == SlotIndex())
continue;
unsigned VReg = restores[i].vreg;
LiveInterval &nI = getOrCreateInterval(VReg);
// If folding is not possible / failed, then tell the spiller to issue a
// load / rematerialization for us.
if (Folded)
- nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index)));
+ nI.removeRange(index.getLoadIndex(), index.getDefIndex());
else
vrm.addRestorePoint(VReg, MI);
}
for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
LiveInterval *LI = NewLIs[i];
if (!LI->empty()) {
- LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI);
+ LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI);
if (!AddedKill.count(LI)) {
LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
- LiveIndex LastUseIdx = getBaseIndex(LR->end);
+ SlotIndex LastUseIdx = LR->end.getBaseIndex();
MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
assert(UseIdx != -1);
E = mri_->reg_end(); I != E; ++I) {
MachineOperand &O = I.getOperand();
MachineInstr *MI = O.getParent();
- LiveIndex Index = getInstructionIndex(MI);
+ SlotIndex Index = getInstructionIndex(MI);
if (pli.liveAt(Index))
++NumConflicts;
}
if (SeenMIs.count(MI))
continue;
SeenMIs.insert(MI);
- LiveIndex Index = getInstructionIndex(MI);
+ SlotIndex Index = getInstructionIndex(MI);
for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
unsigned PReg = PRegs[i];
LiveInterval &pli = getInterval(PReg);
if (!pli.liveAt(Index))
continue;
vrm.addEmergencySpill(PReg, MI);
- LiveIndex StartIdx = getLoadIndex(Index);
- LiveIndex EndIdx = getNextSlot(getStoreIndex(Index));
+ SlotIndex StartIdx = Index.getLoadIndex();
+ SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
pli.removeRange(StartIdx, EndIdx);
Cut = true;
continue;
LiveInterval &spli = getInterval(*AS);
if (spli.liveAt(Index))
- spli.removeRange(getLoadIndex(Index), getNextSlot(getStoreIndex(Index)));
+ spli.removeRange(Index.getLoadIndex(),
+ Index.getNextIndex().getBaseIndex());
}
}
}
MachineInstr* startInst) {
LiveInterval& Interval = getOrCreateInterval(reg);
VNInfo* VN = Interval.getNextValue(
- LiveIndex(getInstructionIndex(startInst), LiveIndex::DEF),
+ SlotIndex(getInstructionIndex(startInst).getDefIndex()),
startInst, true, getVNInfoAllocator());
VN->setHasPHIKill(true);
- VN->kills.push_back(terminatorGaps[startInst->getParent()]);
+ VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent()));
LiveRange LR(
- LiveIndex(getInstructionIndex(startInst), LiveIndex::DEF),
- getNextSlot(getMBBEndIdx(startInst->getParent())), VN);
+ SlotIndex(getInstructionIndex(startInst).getDefIndex()),
+ getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN);
Interval.addRange(LR);
return LR;
char LiveStacks::ID = 0;
static RegisterPass<LiveStacks> X("livestacks", "Live Stack Slot Analysis");
-void LiveStacks::scaleNumbering(int factor) {
- // Scale the intervals.
- for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
- LI->second.scaleNumbering(factor);
- }
-}
-
void LiveStacks::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
+ AU.addPreserved<SlotIndexes>();
+ AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
}
const TargetRegisterInfo* TRI;
MachineFrameInfo *MFI;
MachineRegisterInfo *MRI;
+ SlotIndexes *SIs;
LiveIntervals *LIs;
LiveStacks *LSs;
VirtRegMap *VRM;
MachineBasicBlock *BarrierMBB;
// Barrier - Current barrier index.
- LiveIndex BarrierIdx;
+ SlotIndex BarrierIdx;
// CurrLI - Current live interval being split.
LiveInterval *CurrLI;
DenseMap<unsigned, int> IntervalSSMap;
// Def2SpillMap - A map from a def instruction index to spill index.
- DenseMap<LiveIndex, LiveIndex> Def2SpillMap;
+ DenseMap<SlotIndex, SlotIndex> Def2SpillMap;
public:
static char ID;
- PreAllocSplitting() : MachineFunctionPass(&ID) {}
+ PreAllocSplitting()
+ : MachineFunctionPass(&ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
+ AU.addRequired<SlotIndexes>();
+ AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
AU.addRequired<LiveStacks>();
private:
MachineBasicBlock::iterator
findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
- LiveIndex&);
+ SlotIndex&);
MachineBasicBlock::iterator
findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
- SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+ SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
MachineBasicBlock::iterator
- findRestorePoint(MachineBasicBlock*, MachineInstr*, LiveIndex,
- SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+ findRestorePoint(MachineBasicBlock*, MachineInstr*, SlotIndex,
+ SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
bool IsAvailableInStack(MachineBasicBlock*, unsigned,
- LiveIndex, LiveIndex,
- LiveIndex&, int&) const;
+ SlotIndex, SlotIndex,
+ SlotIndex&, int&) const;
- void UpdateSpillSlotInterval(VNInfo*, LiveIndex, LiveIndex);
+ void UpdateSpillSlotInterval(VNInfo*, SlotIndex, SlotIndex);
bool SplitRegLiveInterval(LiveInterval*);
bool Rematerialize(unsigned vreg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- LiveIndex RestoreIdx,
+ SlotIndex RestoreIdx,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC,
MachineInstr* DefMI,
/// instruction index map. If there isn't one, return end().
MachineBasicBlock::iterator
PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI,
- LiveIndex &SpotIndex) {
+ SlotIndex &SpotIndex) {
MachineBasicBlock::iterator MII = MI;
if (++MII != MBB->end()) {
- LiveIndex Index =
+ SlotIndex Index =
LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
- if (Index != LiveIndex()) {
+ if (Index != SlotIndex()) {
SpotIndex = Index;
return MII;
}
PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI,
MachineInstr *DefMI,
SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
- LiveIndex &SpillIndex) {
+ SlotIndex &SpillIndex) {
MachineBasicBlock::iterator Pt = MBB->begin();
MachineBasicBlock::iterator MII = MI;
if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
while (MII != EndPt && !RefsInMBB.count(MII)) {
- LiveIndex Index = LIs->getInstructionIndex(MII);
+ SlotIndex Index = LIs->getInstructionIndex(MII);
// We can't insert the spill between the barrier (a call), and its
// corresponding call frame setup.
/// found.
MachineBasicBlock::iterator
PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
- LiveIndex LastIdx,
+ SlotIndex LastIdx,
SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
- LiveIndex &RestoreIndex) {
+ SlotIndex &RestoreIndex) {
// FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb
// begin index accordingly.
MachineBasicBlock::iterator Pt = MBB->end();
// FIXME: Limit the number of instructions to examine to reduce
// compile time?
while (MII != EndPt) {
- LiveIndex Index = LIs->getInstructionIndex(MII);
+ SlotIndex Index = LIs->getInstructionIndex(MII);
if (Index > LastIdx)
break;
- LiveIndex Gap = LIs->findGapBeforeInstr(Index);
+ SlotIndex Gap = LIs->findGapBeforeInstr(Index);
// We can't insert a restore between the barrier (a call) and its
// corresponding call frame teardown.
if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
++MII;
} while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode());
- } else if (Gap != LiveIndex()) {
+ } else if (Gap != SlotIndex()) {
Pt = MII;
RestoreIndex = Gap;
}
if (CurrSLI->hasAtLeastOneValue())
CurrSValNo = CurrSLI->getValNumInfo(0);
else
- CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+ CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
LSs->getVNInfoAllocator());
return SS;
}
/// slot at the specified index.
bool
PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB,
- unsigned Reg, LiveIndex DefIndex,
- LiveIndex RestoreIndex,
- LiveIndex &SpillIndex,
+ unsigned Reg, SlotIndex DefIndex,
+ SlotIndex RestoreIndex,
+ SlotIndex &SpillIndex,
int& SS) const {
if (!DefMBB)
return false;
DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
if (I == IntervalSSMap.end())
return false;
- DenseMap<LiveIndex, LiveIndex>::iterator
+ DenseMap<SlotIndex, SlotIndex>::iterator
II = Def2SpillMap.find(DefIndex);
if (II == Def2SpillMap.end())
return false;
/// interval being split, and the spill and restore indicies, update the live
/// interval of the spill stack slot.
void
-PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, LiveIndex SpillIndex,
- LiveIndex RestoreIndex) {
+PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, SlotIndex SpillIndex,
+ SlotIndex RestoreIndex) {
assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
"Expect restore in the barrier mbb");
}
SmallPtrSet<MachineBasicBlock*, 4> Processed;
- LiveIndex EndIdx = LIs->getMBBEndIdx(MBB);
- LiveRange SLR(SpillIndex, LIs->getNextSlot(EndIdx), CurrSValNo);
+ SlotIndex EndIdx = LIs->getMBBEndIdx(MBB);
+ LiveRange SLR(SpillIndex, EndIdx.getNextSlot(), CurrSValNo);
CurrSLI->addRange(SLR);
Processed.insert(MBB);
WorkList.pop_back();
if (Processed.count(MBB))
continue;
- LiveIndex Idx = LIs->getMBBStartIdx(MBB);
+ SlotIndex Idx = LIs->getMBBStartIdx(MBB);
LR = CurrLI->getLiveRangeContaining(Idx);
if (LR && LR->valno == ValNo) {
EndIdx = LIs->getMBBEndIdx(MBB);
CurrSLI->addRange(SLR);
} else if (LR->end > EndIdx) {
// Live range extends beyond end of mbb, process successors.
- LiveRange SLR(Idx, LIs->getNextIndex(EndIdx), CurrSValNo);
+ LiveRange SLR(Idx, EndIdx.getNextIndex(), CurrSValNo);
CurrSLI->addRange(SLR);
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI)
}
// Once we've found it, extend its VNInfo to our instruction.
- LiveIndex DefIndex = LIs->getInstructionIndex(Walker);
- DefIndex = LIs->getDefIndex(DefIndex);
- LiveIndex EndIndex = LIs->getMBBEndIdx(MBB);
+ SlotIndex DefIndex = LIs->getInstructionIndex(Walker);
+ DefIndex = DefIndex.getDefIndex();
+ SlotIndex EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = NewVNs[Walker];
- LI->addRange(LiveRange(DefIndex, LIs->getNextSlot(EndIndex), RetVNI));
+ LI->addRange(LiveRange(DefIndex, EndIndex.getNextSlot(), RetVNI));
} else if (!ContainsDefs && ContainsUses) {
SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
IsTopLevel, IsIntraBlock);
}
- LiveIndex UseIndex = LIs->getInstructionIndex(Walker);
- UseIndex = LIs->getUseIndex(UseIndex);
- LiveIndex EndIndex;
+ SlotIndex UseIndex = LIs->getInstructionIndex(Walker);
+ UseIndex = UseIndex.getUseIndex();
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = LIs->getUseIndex(EndIndex);
+ EndIndex = EndIndex.getUseIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
NewVNs, LiveOut, Phis, false, true);
- LI->addRange(LiveRange(UseIndex, LIs->getNextSlot(EndIndex), RetVNI));
+ LI->addRange(LiveRange(UseIndex, EndIndex.getNextSlot(), RetVNI));
// FIXME: Need to set kills properly for inter-block stuff.
if (RetVNI->isKill(UseIndex)) RetVNI->removeKill(UseIndex);
IsTopLevel, IsIntraBlock);
}
- LiveIndex StartIndex = LIs->getInstructionIndex(Walker);
- StartIndex = foundDef ? LIs->getDefIndex(StartIndex) :
- LIs->getUseIndex(StartIndex);
- LiveIndex EndIndex;
+ SlotIndex StartIndex = LIs->getInstructionIndex(Walker);
+ StartIndex = foundDef ? StartIndex.getDefIndex() : StartIndex.getUseIndex();
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = LIs->getUseIndex(EndIndex);
+ EndIndex = EndIndex.getUseIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
NewVNs, LiveOut, Phis, false, true);
- LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI));
+ LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
if (foundUse && RetVNI->isKill(StartIndex))
RetVNI->removeKill(StartIndex);
// assume that we are not intrablock here.
if (Phis.count(MBB)) return Phis[MBB];
- LiveIndex StartIndex = LIs->getMBBStartIdx(MBB);
+ SlotIndex StartIndex = LIs->getMBBStartIdx(MBB);
VNInfo *RetVNI = Phis[MBB] =
- LI->getNextValue(LiveIndex(), /*FIXME*/ 0, false,
+ LI->getNextValue(SlotIndex(), /*FIXME*/ 0, false,
LIs->getVNInfoAllocator());
if (!IsIntraBlock) LiveOut[MBB] = RetVNI;
for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I =
IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) {
I->second->setHasPHIKill(true);
- LiveIndex KillIndex = LIs->getMBBEndIdx(I->first);
+ SlotIndex KillIndex = LIs->getMBBEndIdx(I->first);
if (!I->second->isKill(KillIndex))
I->second->addKill(KillIndex);
}
}
- LiveIndex EndIndex;
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = LIs->getUseIndex(EndIndex);
+ EndIndex = EndIndex.getUseIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
- LI->addRange(LiveRange(StartIndex, LIs->getNextSlot(EndIndex), RetVNI));
+ LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
if (IsIntraBlock)
RetVNI->addKill(EndIndex);
DE = MRI->def_end(); DI != DE; ++DI) {
Defs[(*DI).getParent()].insert(&*DI);
- LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
- DefIdx = LIs->getDefIndex(DefIdx);
+ SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
+ DefIdx = DefIdx.getDefIndex();
assert(DI->getOpcode() != TargetInstrInfo::PHI &&
"Following NewVN isPHIDef flag incorrect. Fix me!");
// Add ranges for dead defs
for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg),
DE = MRI->def_end(); DI != DE; ++DI) {
- LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
- DefIdx = LIs->getDefIndex(DefIdx);
+ SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
+ DefIdx = DefIdx.getDefIndex();
if (LI->liveAt(DefIdx)) continue;
VNInfo* DeadVN = NewVNs[&*DI];
- LI->addRange(LiveRange(DefIdx, LIs->getNextSlot(DefIdx), DeadVN));
+ LI->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), DeadVN));
DeadVN->addKill(DefIdx);
}
VI != VE; ++VI) {
VNInfo* VNI = *VI;
for (unsigned i = 0, e = VNI->kills.size(); i != e; ++i) {
- LiveIndex KillIdx = VNI->kills[i];
- if (KillIdx.isPHIIndex())
+ SlotIndex KillIdx = VNI->kills[i];
+ if (KillIdx.isPHI())
continue;
MachineInstr *KillMI = LIs->getInstructionFromIndex(KillIdx);
if (KillMI) {
// Locate two-address redefinitions
for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(),
KE = OldVN->kills.end(); KI != KE; ++KI) {
- assert(!KI->isPHIIndex() &&
+ assert(!KI->isPHI() &&
"VN previously reported having no PHI kills.");
MachineInstr* MI = LIs->getInstructionFromIndex(*KI);
unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg);
if (DefIdx == ~0U) continue;
if (MI->isRegTiedToUseOperand(DefIdx)) {
VNInfo* NextVN =
- CurrLI->findDefinedVNInfoForRegInt(LIs->getDefIndex(*KI));
+ CurrLI->findDefinedVNInfoForRegInt(KI->getDefIndex());
if (NextVN == OldVN) continue;
Stack.push_back(NextVN);
}
for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
E = MRI->reg_end(); I != E; ++I) {
MachineOperand& MO = I.getOperand();
- LiveIndex InstrIdx = LIs->getInstructionIndex(&*I);
+ SlotIndex InstrIdx = LIs->getInstructionIndex(&*I);
- if ((MO.isUse() && NewLI.liveAt(LIs->getUseIndex(InstrIdx))) ||
- (MO.isDef() && NewLI.liveAt(LIs->getDefIndex(InstrIdx))))
+ if ((MO.isUse() && NewLI.liveAt(InstrIdx.getUseIndex())) ||
+ (MO.isDef() && NewLI.liveAt(InstrIdx.getDefIndex())))
OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo()));
}
bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- LiveIndex RestoreIdx,
+ SlotIndex RestoreIdx,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
MachineBasicBlock& MBB = *RestorePt->getParent();
MachineBasicBlock::iterator KillPt = BarrierMBB->end();
- LiveIndex KillIdx;
+ SlotIndex KillIdx;
if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB)
KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx);
else
LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx);
ReconstructLiveInterval(CurrLI);
- LiveIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
- RematIdx = LIs->getDefIndex(RematIdx);
+ SlotIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
+ RematIdx = RematIdx.getDefIndex();
RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx));
++NumSplits;
if (CurrSLI->hasAtLeastOneValue())
CurrSValNo = CurrSLI->getValNumInfo(0);
else
- CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+ CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
LSs->getVNInfoAllocator());
}
/// so it would not cross the barrier that's being processed. Shrink wrap
/// (minimize) the live interval to the last uses.
bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) {
+ DEBUG(errs() << "Pre-alloc splitting " << LI->reg << " for " << *Barrier
+ << " result: ");
+
CurrLI = LI;
// Find live range where current interval cross the barrier.
LiveInterval::iterator LR =
- CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx));
+ CurrLI->FindLiveRangeContaining(BarrierIdx.getUseIndex());
VNInfo *ValNo = LR->valno;
assert(!ValNo->isUnused() && "Val# is defined by a dead def?");
? LIs->getInstructionFromIndex(ValNo->def) : NULL;
// If this would create a new join point, do not split.
- if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent()))
+ if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) {
+ DEBUG(errs() << "FAILED (would create a new join point).\n");
return false;
+ }
// Find all references in the barrier mbb.
SmallPtrSet<MachineInstr*, 4> RefsInMBB;
}
// Find a point to restore the value after the barrier.
- LiveIndex RestoreIndex;
+ SlotIndex RestoreIndex;
MachineBasicBlock::iterator RestorePt =
findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex);
- if (RestorePt == BarrierMBB->end())
+ if (RestorePt == BarrierMBB->end()) {
+ DEBUG(errs() << "FAILED (could not find a suitable restore point).\n");
return false;
+ }
if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI))
if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt,
- RestoreIndex, RefsInMBB))
- return true;
+ RestoreIndex, RefsInMBB)) {
+ DEBUG(errs() << "success (remat).\n");
+ return true;
+ }
// Add a spill either before the barrier or after the definition.
MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL;
const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg);
- LiveIndex SpillIndex;
+ SlotIndex SpillIndex;
MachineInstr *SpillMI = NULL;
int SS = -1;
if (!ValNo->isDefAccurate()) {
} else {
MachineBasicBlock::iterator SpillPt =
findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex);
- if (SpillPt == BarrierMBB->begin())
+ if (SpillPt == BarrierMBB->begin()) {
+ DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
+ }
// Add spill.
SS = CreateSpillStackSlot(CurrLI->reg, RC);
RestoreIndex, SpillIndex, SS)) {
// If it's already split, just restore the value. There is no need to spill
// the def again.
- if (!DefMI)
+ if (!DefMI) {
+ DEBUG(errs() << "FAILED (def is dead).\n");
return false; // Def is dead. Do nothing.
+ }
if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier,
BarrierMBB, SS, RefsInMBB))) {
// Add spill after the def and the last use before the barrier.
SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI,
RefsInMBB, SpillIndex);
- if (SpillPt == DefMBB->begin())
+ if (SpillPt == DefMBB->begin()) {
+ DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
+ }
} else {
SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex);
- if (SpillPt == DefMBB->end())
+ if (SpillPt == DefMBB->end()) {
+ DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
+ }
}
// Add spill.
SS = CreateSpillStackSlot(CurrLI->reg, RC);
}
// Update spill stack slot live interval.
- UpdateSpillSlotInterval(ValNo, LIs->getNextSlot(LIs->getUseIndex(SpillIndex)),
- LIs->getDefIndex(RestoreIndex));
+ UpdateSpillSlotInterval(ValNo, SpillIndex.getUseIndex().getNextSlot(),
+ RestoreIndex.getDefIndex());
ReconstructLiveInterval(CurrLI);
if (!FoldedRestore) {
- LiveIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
- RestoreIdx = LIs->getDefIndex(RestoreIdx);
+ SlotIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
+ RestoreIdx = RestoreIdx.getDefIndex();
RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RestoreIdx));
}
++NumSplits;
+ DEBUG(errs() << "success.\n");
return true;
}
// reaching definition (VNInfo).
for (MachineRegisterInfo::use_iterator UI = MRI->use_begin((*LI)->reg),
UE = MRI->use_end(); UI != UE; ++UI) {
- LiveIndex index = LIs->getInstructionIndex(&*UI);
- index = LIs->getUseIndex(index);
+ SlotIndex index = LIs->getInstructionIndex(&*UI);
+ index = index.getUseIndex();
const LiveRange* LR = (*LI)->getLiveRangeContaining(index);
VNUseCount[LR->valno].insert(&*UI);
if (LR->valno->hasPHIKill())
return false;
- LiveIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
+ SlotIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
if (LR->end < MBBEnd)
return false;
TII = TM->getInstrInfo();
MFI = MF.getFrameInfo();
MRI = &MF.getRegInfo();
+ SIs = &getAnalysis<SlotIndexes>();
LIs = &getAnalysis<LiveIntervals>();
LSs = &getAnalysis<LiveStacks>();
VRM = &getAnalysis<VirtRegMap>();
--- /dev/null
+//===---------------------- ProcessImplicitDefs.cpp -----------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "processimplicitdefs"
+
+#include "llvm/CodeGen/ProcessImplicitDefs.h"
+
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+
+using namespace llvm;
+
+char ProcessImplicitDefs::ID = 0;
+static RegisterPass<ProcessImplicitDefs> X("processimpdefs",
+ "Process Implicit Definitions.");
+
+void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
+ AU.addPreserved<AliasAnalysis>();
+ AU.addPreserved<LiveVariables>();
+ AU.addRequired<LiveVariables>();
+ AU.addPreservedID(MachineLoopInfoID);
+ AU.addPreservedID(MachineDominatorsID);
+ AU.addPreservedID(TwoAddressInstructionPassID);
+ AU.addPreservedID(PHIEliminationID);
+ MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool ProcessImplicitDefs::CanTurnIntoImplicitDef(MachineInstr *MI,
+ unsigned Reg, unsigned OpIdx,
+ const TargetInstrInfo *tii_) {
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+ Reg == SrcReg)
+ return true;
+
+ if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
+ return true;
+ if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+ return true;
+ return false;
+}
+
+/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
+/// there is one implicit_def for each use. Add isUndef marker to
+/// implicit_def defs and their uses.
+bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &fn) {
+
+ DEBUG(errs() << "********** PROCESS IMPLICIT DEFS **********\n"
+ << "********** Function: "
+ << ((Value*)fn.getFunction())->getName() << '\n');
+
+ bool Changed = false;
+
+ const TargetInstrInfo *tii_ = fn.getTarget().getInstrInfo();
+ const TargetRegisterInfo *tri_ = fn.getTarget().getRegisterInfo();
+ MachineRegisterInfo *mri_ = &fn.getRegInfo();
+
+ LiveVariables *lv_ = &getAnalysis<LiveVariables>();
+
+ SmallSet<unsigned, 8> ImpDefRegs;
+ SmallVector<MachineInstr*, 8> ImpDefMIs;
+ MachineBasicBlock *Entry = fn.begin();
+ SmallPtrSet<MachineBasicBlock*,16> Visited;
+
+ for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
+ DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
+ DFI != E; ++DFI) {
+ MachineBasicBlock *MBB = *DFI;
+ for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
+ I != E; ) {
+ MachineInstr *MI = &*I;
+ ++I;
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ unsigned Reg = MI->getOperand(0).getReg();
+ ImpDefRegs.insert(Reg);
+ if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
+ for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
+ ImpDefRegs.insert(*SS);
+ }
+ ImpDefMIs.push_back(MI);
+ continue;
+ }
+
+ if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
+ MachineOperand &MO = MI->getOperand(2);
+ if (ImpDefRegs.count(MO.getReg())) {
+ // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2
+ // This is an identity copy, eliminate it now.
+ if (MO.isKill()) {
+ LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
+ vi.removeKill(MI);
+ }
+ MI->eraseFromParent();
+ Changed = true;
+ continue;
+ }
+ }
+
+ bool ChangedToImpDef = false;
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand& MO = MI->getOperand(i);
+ if (!MO.isReg() || !MO.isUse() || MO.isUndef())
+ continue;
+ unsigned Reg = MO.getReg();
+ if (!Reg)
+ continue;
+ if (!ImpDefRegs.count(Reg))
+ continue;
+ // Use is a copy, just turn it into an implicit_def.
+ if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) {
+ bool isKill = MO.isKill();
+ MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
+ for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
+ MI->RemoveOperand(j);
+ if (isKill) {
+ ImpDefRegs.erase(Reg);
+ LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
+ vi.removeKill(MI);
+ }
+ ChangedToImpDef = true;
+ Changed = true;
+ break;
+ }
+
+ Changed = true;
+ MO.setIsUndef();
+ if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
+ // Make sure other uses of
+ for (unsigned j = i+1; j != e; ++j) {
+ MachineOperand &MOJ = MI->getOperand(j);
+ if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
+ MOJ.setIsUndef();
+ }
+ ImpDefRegs.erase(Reg);
+ }
+ }
+
+ if (ChangedToImpDef) {
+ // Backtrack to process this new implicit_def.
+ --I;
+ } else {
+ for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
+ MachineOperand& MO = MI->getOperand(i);
+ if (!MO.isReg() || !MO.isDef())
+ continue;
+ ImpDefRegs.erase(MO.getReg());
+ }
+ }
+ }
+
+ // Any outstanding liveout implicit_def's?
+ for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) {
+ MachineInstr *MI = ImpDefMIs[i];
+ unsigned Reg = MI->getOperand(0).getReg();
+ if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
+ !ImpDefRegs.count(Reg)) {
+ // Delete all "local" implicit_def's. That include those which define
+ // physical registers since they cannot be liveout.
+ MI->eraseFromParent();
+ Changed = true;
+ continue;
+ }
+
+ // If there are multiple defs of the same register and at least one
+ // is not an implicit_def, do not insert implicit_def's before the
+ // uses.
+ bool Skip = false;
+ for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg),
+ DE = mri_->def_end(); DI != DE; ++DI) {
+ if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) {
+ Skip = true;
+ break;
+ }
+ }
+ if (Skip)
+ continue;
+
+ // The only implicit_def which we want to keep are those that are live
+ // out of its block.
+ MI->eraseFromParent();
+ Changed = true;
+
+ for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
+ UE = mri_->use_end(); UI != UE; ) {
+ MachineOperand &RMO = UI.getOperand();
+ MachineInstr *RMI = &*UI;
+ ++UI;
+ MachineBasicBlock *RMBB = RMI->getParent();
+ if (RMBB == MBB)
+ continue;
+
+ // Turn a copy use into an implicit_def.
+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+ if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
+ Reg == SrcReg) {
+ RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
+ for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j)
+ RMI->RemoveOperand(j);
+ continue;
+ }
+
+ const TargetRegisterClass* RC = mri_->getRegClass(Reg);
+ unsigned NewVReg = mri_->createVirtualRegister(RC);
+ RMO.setReg(NewVReg);
+ RMO.setIsUndef();
+ RMO.setIsKill();
+ }
+ }
+ ImpDefRegs.clear();
+ ImpDefMIs.clear();
+ }
+
+ return Changed;
+}
+
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<LiveIntervals>();
+ AU.addPreserved<SlotIndexes>();
if (StrongPHIElim)
AU.addRequiredID(StrongPHIEliminationID);
// Make sure PassManager knows which analyses to make available
/// processActiveIntervals - expire old intervals and move non-overlapping
/// ones to the inactive list.
- void processActiveIntervals(LiveIndex CurPoint);
+ void processActiveIntervals(SlotIndex CurPoint);
/// processInactiveIntervals - expire old intervals and move overlapping
/// ones to the active list.
- void processInactiveIntervals(LiveIndex CurPoint);
+ void processInactiveIntervals(SlotIndex CurPoint);
/// hasNextReloadInterval - Return the next liveinterval that's being
/// defined by a reload from the same SS as the specified one.
return Reg;
VNInfo *vni = cur.begin()->valno;
- if ((vni->def == LiveIndex()) ||
+ if ((vni->def == SlotIndex()) ||
vni->isUnused() || !vni->isDefAccurate())
return Reg;
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
if (!O.isKill())
continue;
MachineInstr *MI = &*I;
- if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI))))
+ if (SrcLI.liveAt(li_->getInstructionIndex(MI).getDefIndex()))
O.setIsKill(false);
}
}
for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
- mri_->setPhysRegUsed(i->second->reg);
- fixed_.push_back(std::make_pair(i->second, i->second->begin()));
- } else
- unhandled_.push(i->second);
+ if (!i->second->empty()) {
+ mri_->setPhysRegUsed(i->second->reg);
+ fixed_.push_back(std::make_pair(i->second, i->second->begin()));
+ }
+ } else {
+ if (i->second->empty()) {
+ assignRegOrStackSlotAtInterval(i->second);
+ }
+ else
+ unhandled_.push(i->second);
+ }
}
}
++NumIters;
DEBUG(errs() << "\n*** CURRENT ***: " << *cur << '\n');
- if (!cur->empty()) {
- processActiveIntervals(cur->beginIndex());
- processInactiveIntervals(cur->beginIndex());
+ assert(!cur->empty() && "Empty interval in unhandled set.");
- assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
- "Can only allocate virtual registers!");
- }
+ processActiveIntervals(cur->beginIndex());
+ processInactiveIntervals(cur->beginIndex());
+
+ assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
+ "Can only allocate virtual registers!");
// Allocating a virtual register. try to find a free
// physical register or spill an interval (possibly this one) in order to
/// processActiveIntervals - expire old intervals and move non-overlapping ones
/// to the inactive list.
-void RALinScan::processActiveIntervals(LiveIndex CurPoint)
+void RALinScan::processActiveIntervals(SlotIndex CurPoint)
{
DEBUG(errs() << "\tprocessing active intervals:\n");
/// processInactiveIntervals - expire old intervals and move overlapping
/// ones to the active list.
-void RALinScan::processInactiveIntervals(LiveIndex CurPoint)
+void RALinScan::processInactiveIntervals(SlotIndex CurPoint)
{
DEBUG(errs() << "\tprocessing inactive intervals:\n");
return IP.end();
}
-static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, LiveIndex Point){
+static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, SlotIndex Point){
for (unsigned i = 0, e = V.size(); i != e; ++i) {
RALinScan::IntervalPtr &IP = V[i];
LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
if (SI.hasAtLeastOneValue())
VNI = SI.getValNumInfo(0);
else
- VNI = SI.getNextValue(LiveIndex(), 0, false,
+ VNI = SI.getNextValue(SlotIndex(), 0, false,
ls_->getVNInfoAllocator());
LiveInterval &RI = li_->getInterval(cur->reg);
backUpRegUses();
std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
- LiveIndex StartPosition = cur->beginIndex();
+ SlotIndex StartPosition = cur->beginIndex();
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
// If start of this live interval is defined by a move instruction and its
// one, e.g. X86::mov32to32_. These move instructions are not coalescable.
if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) {
VNInfo *vni = cur->begin()->valno;
- if ((vni->def != LiveIndex()) && !vni->isUnused() &&
+ if ((vni->def != SlotIndex()) && !vni->isUnused() &&
vni->isDefAccurate()) {
MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
DowngradedRegs.clear();
assignRegOrStackSlotAtInterval(cur);
} else {
+ assert(false && "Ran out of registers during register allocation!");
llvm_report_error("Ran out of registers during register allocation!");
}
return;
LiveInterval *ReloadLi = added[i];
if (ReloadLi->weight == HUGE_VALF &&
li_->getApproximateInstructionCount(*ReloadLi) == 0) {
- LiveIndex ReloadIdx = ReloadLi->beginIndex();
+ SlotIndex ReloadIdx = ReloadLi->beginIndex();
MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
spilled.insert(sli->reg);
}
- LiveIndex earliestStart = earliestStartInterval->beginIndex();
+ SlotIndex earliestStart = earliestStartInterval->beginIndex();
DEBUG(errs() << "\t\trolling back to: " << earliestStart << '\n');
LiveInterval *ReloadLi = added[i];
if (ReloadLi->weight == HUGE_VALF &&
li_->getApproximateInstructionCount(*ReloadLi) == 0) {
- LiveIndex ReloadIdx = ReloadLi->beginIndex();
+ SlotIndex ReloadIdx = ReloadLi->beginIndex();
MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
/// PBQP analysis usage.
virtual void getAnalysisUsage(AnalysisUsage &au) const {
+ au.addRequired<SlotIndexes>();
+ au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
//au.addRequiredID(SplitCriticalEdgesID);
au.addRequired<RegisterCoalescer>();
vni = stackInterval.getValNumInfo(0);
else
vni = stackInterval.getNextValue(
- LiveIndex(), 0, false, lss->getVNInfoAllocator());
+ SlotIndex(), 0, false, lss->getVNInfoAllocator());
LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
stackInterval.MergeRangesInAsValue(rhsInterval, vni);
tm = &mf->getTarget();
tri = tm->getRegisterInfo();
tii = tm->getInstrInfo();
- mri = &mf->getRegInfo();
+ mri = &mf->getRegInfo();
lis = &getAnalysis<LiveIntervals>();
lss = &getAnalysis<LiveStacks>();
AU.addRequired<AliasAnalysis>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
+ AU.addPreserved<SlotIndexes>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineLoopInfo>();
AU.addPreservedID(MachineDominatorsID);
bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
LiveInterval &IntB,
MachineInstr *CopyMI) {
- LiveIndex CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+ SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex();
// BValNo is a value number in B that is defined by a copy from A. 'B3' in
// the example above.
assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
// AValNo is the value number in A that defines the copy, A3 in the example.
- LiveIndex CopyUseIdx = li_->getUseIndex(CopyIdx);
+ SlotIndex CopyUseIdx = CopyIdx.getUseIndex();
LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
assert(ALR != IntA.end() && "Live range not found!");
VNInfo *AValNo = ALR->valno;
// Get the LiveRange in IntB that this value number starts with.
LiveInterval::iterator ValLR =
- IntB.FindLiveRangeContaining(li_->getPrevSlot(AValNo->def));
+ IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
assert(ValLR != IntB.end() && "Live range not found!");
// Make sure that the end of the live range is inside the same block as
// CopyMI.
MachineInstr *ValLREndInst =
- li_->getInstructionFromIndex(li_->getPrevSlot(ValLR->end));
+ li_->getInstructionFromIndex(ValLR->end.getPrevSlot());
if (!ValLREndInst ||
ValLREndInst->getParent() != CopyMI->getParent()) return false;
IntB.print(errs(), tri_);
});
- LiveIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
+ SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
// We are about to delete CopyMI, so need to remove it as the 'instruction
// that defines this value #'. Update the the valnum with the new defining
// instruction #.
bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
LiveInterval &IntB,
MachineInstr *CopyMI) {
- LiveIndex CopyIdx =
- li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+ SlotIndex CopyIdx =
+ li_->getInstructionIndex(CopyMI).getDefIndex();
// FIXME: For now, only eliminate the copy by commuting its def when the
// source register is a virtual register. We want to guard against cases
// AValNo is the value number in A that defines the copy, A3 in the example.
LiveInterval::iterator ALR =
- IntA.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx));
+ IntA.FindLiveRangeContaining(CopyIdx.getUseIndex()); //
assert(ALR != IntA.end() && "Live range not found!");
VNInfo *AValNo = ALR->valno;
for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
UE = mri_->use_end(); UI != UE; ++UI) {
MachineInstr *UseMI = &*UI;
- LiveIndex UseIdx = li_->getInstructionIndex(UseMI);
+ SlotIndex UseIdx = li_->getInstructionIndex(UseMI);
LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
if (ULR == IntA.end())
continue;
bool BHasPHIKill = BValNo->hasPHIKill();
SmallVector<VNInfo*, 4> BDeadValNos;
VNInfo::KillSet BKills;
- std::map<LiveIndex, LiveIndex> BExtend;
+ std::map<SlotIndex, SlotIndex> BExtend;
// If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
// A = or A, B
++UI;
if (JoinedCopies.count(UseMI))
continue;
- LiveIndex UseIdx= li_->getUseIndex(li_->getInstructionIndex(UseMI));
+ SlotIndex UseIdx = li_->getInstructionIndex(UseMI).getUseIndex();
LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
if (ULR == IntA.end() || ULR->valno != AValNo)
continue;
if (Extended)
UseMO.setIsKill(false);
else
- BKills.push_back(li_->getNextSlot(UseIdx));
+ BKills.push_back(UseIdx.getDefIndex());
}
unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
// This copy will become a noop. If it's defining a new val#,
// remove that val# as well. However this live range is being
// extended to the end of the existing live range defined by the copy.
- LiveIndex DefIdx = li_->getDefIndex(UseIdx);
+ SlotIndex DefIdx = UseIdx.getDefIndex();
const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
BHasPHIKill |= DLR->valno->hasPHIKill();
assert(DLR->valno->def == DefIdx);
for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
AI != AE; ++AI) {
if (AI->valno != AValNo) continue;
- LiveIndex End = AI->end;
- std::map<LiveIndex, LiveIndex>::iterator
+ SlotIndex End = AI->end;
+ std::map<SlotIndex, SlotIndex>::iterator
EI = BExtend.find(End);
if (EI != BExtend.end())
End = EI->second;
if (BHasSubRegs) {
for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
LiveInterval &SRLI = li_->getInterval(*SR);
- SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator());
+ SRLI.MergeInClobberRange(*li_, AI->start, End, li_->getVNInfoAllocator());
}
}
}
/// from a physical register live interval as well as from the live intervals
/// of its sub-registers.
static void removeRange(LiveInterval &li,
- LiveIndex Start, LiveIndex End,
+ SlotIndex Start, SlotIndex End,
LiveIntervals *li_, const TargetRegisterInfo *tri_) {
li.removeRange(Start, End, true);
if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
if (!li_->hasInterval(*SR))
continue;
LiveInterval &sli = li_->getInterval(*SR);
- LiveIndex RemoveStart = Start;
- LiveIndex RemoveEnd = Start;
+ SlotIndex RemoveStart = Start;
+ SlotIndex RemoveEnd = Start;
+
while (RemoveEnd != End) {
LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart);
if (LR == sli.end())
/// as the copy instruction, trim the live interval to the last use and return
/// true.
bool
-SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(LiveIndex CopyIdx,
+SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
MachineBasicBlock *CopyMBB,
LiveInterval &li,
const LiveRange *LR) {
- LiveIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
- LiveIndex LastUseIdx;
+ SlotIndex MBBStart = li_->getMBBStartIdx(CopyMBB);
+ SlotIndex LastUseIdx;
MachineOperand *LastUse =
- lastRegisterUse(LR->start, li_->getPrevSlot(CopyIdx), li.reg, LastUseIdx);
+ lastRegisterUse(LR->start, CopyIdx.getPrevSlot(), li.reg, LastUseIdx);
if (LastUse) {
MachineInstr *LastUseMI = LastUse->getParent();
if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
// There are uses before the copy, just shorten the live range to the end
// of last use.
LastUse->setIsKill();
- removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
- LR->valno->addKill(li_->getNextSlot(LastUseIdx));
+ removeRange(li, LastUseIdx.getDefIndex(), LR->end, li_, tri_);
+ LR->valno->addKill(LastUseIdx.getDefIndex());
unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
DstReg == li.reg) {
// Is it livein?
if (LR->start <= MBBStart && LR->end > MBBStart) {
- if (LR->start == LiveIndex()) {
+ if (LR->start == li_->getZeroIndex()) {
assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
// Live-in to the function but dead. Remove it from entry live-in set.
mf_->begin()->removeLiveIn(li.reg);
unsigned DstReg,
unsigned DstSubIdx,
MachineInstr *CopyMI) {
- LiveIndex CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI));
+ SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getUseIndex();
LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
assert(SrcLR != SrcInt.end() && "Live range not found!");
VNInfo *ValNo = SrcLR->valno;
return false;
}
- LiveIndex DefIdx = li_->getDefIndex(CopyIdx);
+ SlotIndex DefIdx = CopyIdx.getDefIndex();
const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
DLR->valno->setCopy(0);
// Don't forget to update sub-register intervals.
// should mark it dead:
if (DefMI->getParent() == MBB) {
DefMI->addRegisterDead(SrcInt.reg, tri_);
- SrcLR->end = li_->getNextSlot(SrcLR->start);
+ SrcLR->end = SrcLR->start.getNextSlot();
}
}
(TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
allocatableRegs_[CopyDstReg])) {
LiveInterval &LI = li_->getInterval(CopyDstReg);
- LiveIndex DefIdx =
- li_->getDefIndex(li_->getInstructionIndex(UseMI));
+ SlotIndex DefIdx =
+ li_->getInstructionIndex(UseMI).getDefIndex();
if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) {
if (DLR->valno->def == DefIdx)
DLR->valno->setCopy(UseMI);
if (!UseMO.isKill())
continue;
MachineInstr *UseMI = UseMO.getParent();
- LiveIndex UseIdx =
- li_->getUseIndex(li_->getInstructionIndex(UseMI));
+ SlotIndex UseIdx =
+ li_->getInstructionIndex(UseMI).getUseIndex();
const LiveRange *LR = LI.getLiveRangeContaining(UseIdx);
if (!LR ||
- (!LR->valno->isKill(li_->getNextSlot(UseIdx)) &&
- LR->valno->def != li_->getNextSlot(UseIdx))) {
+ (!LR->valno->isKill(UseIdx.getDefIndex()) &&
+ LR->valno->def != UseIdx.getDefIndex())) {
// Interesting problem. After coalescing reg1027's def and kill are both
// at the same point: %reg1027,0.000000e+00 = [56,814:0) 0@70-(814)
//
/// Return true if live interval is removed.
bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
MachineInstr *CopyMI) {
- LiveIndex CopyIdx = li_->getInstructionIndex(CopyMI);
+ SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
LiveInterval::iterator MLR =
- li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
+ li.FindLiveRangeContaining(CopyIdx.getDefIndex());
if (MLR == li.end())
return false; // Already removed by ShortenDeadCopySrcLiveRange.
- LiveIndex RemoveStart = MLR->start;
- LiveIndex RemoveEnd = MLR->end;
- LiveIndex DefIdx = li_->getDefIndex(CopyIdx);
+ SlotIndex RemoveStart = MLR->start;
+ SlotIndex RemoveEnd = MLR->end;
+ SlotIndex DefIdx = CopyIdx.getDefIndex();
// Remove the liverange that's defined by this.
- if (RemoveStart == DefIdx && RemoveEnd == li_->getNextSlot(DefIdx)) {
+ if (RemoveStart == DefIdx && RemoveEnd == DefIdx.getStoreIndex()) {
removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
return removeIntervalIfEmpty(li, li_, tri_);
}
/// the val# it defines. If the live interval becomes empty, remove it as well.
bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li,
MachineInstr *DefMI) {
- LiveIndex DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI));
+ SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex();
LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx);
if (DefIdx != MLR->valno->def)
return false;
/// PropagateDeadness - Propagate the dead marker to the instruction which
/// defines the val#.
static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
- LiveIndex &LRStart, LiveIntervals *li_,
+ SlotIndex &LRStart, LiveIntervals *li_,
const TargetRegisterInfo* tri_) {
MachineInstr *DefMI =
- li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
+ li_->getInstructionFromIndex(LRStart.getDefIndex());
if (DefMI && DefMI != CopyMI) {
int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false);
if (DeadIdx != -1)
else
DefMI->addOperand(MachineOperand::CreateReg(li.reg,
/*def*/true, /*implicit*/true, /*kill*/false, /*dead*/true));
- LRStart = li_->getNextSlot(LRStart);
+ LRStart = LRStart.getNextSlot();
}
}
bool
SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
MachineInstr *CopyMI) {
- LiveIndex CopyIdx = li_->getInstructionIndex(CopyMI);
- if (CopyIdx == LiveIndex()) {
+ SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI);
+ if (CopyIdx == SlotIndex()) {
// FIXME: special case: function live in. It can be a general case if the
// first instruction index starts at > 0 value.
assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
}
LiveInterval::iterator LR =
- li.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx));
+ li.FindLiveRangeContaining(CopyIdx.getPrevIndex().getStoreIndex());
if (LR == li.end())
// Livein but defined by a phi.
return false;
- LiveIndex RemoveStart = LR->start;
- LiveIndex RemoveEnd = li_->getNextSlot(li_->getDefIndex(CopyIdx));
+ SlotIndex RemoveStart = LR->start;
+ SlotIndex RemoveEnd = CopyIdx.getStoreIndex();
if (LR->end > RemoveEnd)
// More uses past this copy? Nothing to do.
return false;
// If the live range starts in another mbb and the copy mbb is not a fall
// through mbb, then we can only cut the range from the beginning of the
// copy mbb.
- RemoveStart = li_->getNextSlot(li_->getMBBStartIdx(CopyMBB));
+ RemoveStart = li_->getMBBStartIdx(CopyMBB).getNextIndex().getBaseIndex();
if (LR->valno->def == RemoveStart) {
// If the def MI defines the val# and this copy is the only kill of the
// If the virtual register live interval extends into a loop, turn down
// aggressiveness.
- LiveIndex CopyIdx =
- li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+ SlotIndex CopyIdx =
+ li_->getInstructionIndex(CopyMI).getDefIndex();
const MachineLoop *L = loopInfo->getLoopFor(CopyMBB);
if (!L) {
// Let's see if the virtual register live interval extends into the loop.
LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx);
assert(DLR != DstInt.end() && "Live range not found!");
- DLR = DstInt.FindLiveRangeContaining(li_->getNextSlot(DLR->end));
+ DLR = DstInt.FindLiveRangeContaining(DLR->end.getNextSlot());
if (DLR != DstInt.end()) {
CopyMBB = li_->getMBBFromIndex(DLR->start);
L = loopInfo->getLoopFor(CopyMBB);
if (!L || Length <= Threshold)
return true;
- LiveIndex UseIdx = li_->getUseIndex(CopyIdx);
+ SlotIndex UseIdx = CopyIdx.getUseIndex();
LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
if (loopInfo->getLoopFor(SMBB) != L) {
if (SuccMBB == CopyMBB)
continue;
if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB),
- li_->getNextSlot(li_->getMBBEndIdx(SuccMBB))))
+ li_->getMBBEndIdx(SuccMBB).getNextIndex().getBaseIndex()))
return false;
}
}
// If the virtual register live interval is defined or cross a loop, turn
// down aggressiveness.
- LiveIndex CopyIdx =
- li_->getDefIndex(li_->getInstructionIndex(CopyMI));
- LiveIndex UseIdx = li_->getUseIndex(CopyIdx);
+ SlotIndex CopyIdx =
+ li_->getInstructionIndex(CopyMI).getDefIndex();
+ SlotIndex UseIdx = CopyIdx.getUseIndex();
LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx);
assert(SLR != SrcInt.end() && "Live range not found!");
- SLR = SrcInt.FindLiveRangeContaining(li_->getPrevSlot(SLR->start));
+ SLR = SrcInt.FindLiveRangeContaining(SLR->start.getPrevSlot());
if (SLR == SrcInt.end())
return true;
MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start);
if (PredMBB == SMBB)
continue;
if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB),
- li_->getNextSlot(li_->getMBBEndIdx(PredMBB))))
+ li_->getMBBEndIdx(PredMBB).getNextIndex().getBaseIndex()))
return false;
}
}
// Update the liveintervals of sub-registers.
for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS)
- li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
+ li_->getOrCreateInterval(*AS).MergeInClobberRanges(*li_, *ResSrcInt,
li_->getVNInfoAllocator());
}
/// is live at the given point.
bool SimpleRegisterCoalescing::ValueLiveAt(LiveInterval::iterator LRItr,
LiveInterval::iterator LREnd,
- LiveIndex defPoint) const {
+ SlotIndex defPoint) const {
for (const VNInfo *valno = LRItr->valno;
(LRItr != LREnd) && (LRItr->valno == valno); ++LRItr) {
if (LRItr->contains(defPoint))
// Update the liveintervals of sub-registers.
if (TargetRegisterInfo::isPhysicalRegister(LHS.reg))
for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS)
- li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS,
+ li_->getOrCreateInterval(*AS).MergeInClobberRanges(*li_, LHS,
li_->getVNInfoAllocator());
return true;
} else {
// It was defined as a copy from the LHS, find out what value # it is.
RHSValNoInfo =
- LHS.getLiveRangeContaining(li_->getPrevSlot(RHSValNoInfo0->def))->valno;
+ LHS.getLiveRangeContaining(RHSValNoInfo0->def.getPrevSlot())->valno;
RHSValID = RHSValNoInfo->id;
RHSVal0DefinedFromLHS = RHSValID;
}
// Figure out the value # from the RHS.
LHSValsDefinedFromRHS[VNI]=
- RHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno;
+ RHS.getLiveRangeContaining(VNI->def.getPrevSlot())->valno;
}
// Loop over the value numbers of the RHS, seeing if any are defined from
// Figure out the value # from the LHS.
RHSValsDefinedFromLHS[VNI]=
- LHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno;
+ LHS.getLiveRangeContaining(VNI->def.getPrevSlot())->valno;
}
LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
/// lastRegisterUse - Returns the last use of the specific register between
/// cycles Start and End or NULL if there are no uses.
MachineOperand *
-SimpleRegisterCoalescing::lastRegisterUse(LiveIndex Start,
- LiveIndex End,
+SimpleRegisterCoalescing::lastRegisterUse(SlotIndex Start,
+ SlotIndex End,
unsigned Reg,
- LiveIndex &UseIdx) const{
- UseIdx = LiveIndex();
+ SlotIndex &UseIdx) const{
+ UseIdx = SlotIndex();
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
MachineOperand *LastUse = NULL;
for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg),
SrcReg == DstReg)
// Ignore identity copies.
continue;
- LiveIndex Idx = li_->getInstructionIndex(UseMI);
+ SlotIndex Idx = li_->getInstructionIndex(UseMI);
+ // FIXME: Should this be Idx != UseIdx? SlotIndex() will return something
+ // that compares higher than any other interval.
if (Idx >= Start && Idx < End && Idx >= UseIdx) {
LastUse = &Use;
- UseIdx = li_->getUseIndex(Idx);
+ UseIdx = Idx.getUseIndex();
}
}
return LastUse;
}
- LiveIndex s = Start;
- LiveIndex e = li_->getBaseIndex(li_->getPrevSlot(End));
+ SlotIndex s = Start;
+ SlotIndex e = End.getPrevSlot().getBaseIndex();
while (e >= s) {
// Skip deleted instructions
MachineInstr *MI = li_->getInstructionFromIndex(e);
- while (e != LiveIndex() && li_->getPrevIndex(e) >= s && !MI) {
- e = li_->getPrevIndex(e);
+ while (e != SlotIndex() && e.getPrevIndex() >= s && !MI) {
+ e = e.getPrevIndex();
MI = li_->getInstructionFromIndex(e);
}
if (e < s || MI == NULL)
MachineOperand &Use = MI->getOperand(i);
if (Use.isReg() && Use.isUse() && Use.getReg() &&
tri_->regsOverlap(Use.getReg(), Reg)) {
- UseIdx = li_->getUseIndex(e);
+ UseIdx = e.getUseIndex();
return &Use;
}
}
- e = li_->getPrevIndex(e);
+ e = e.getPrevIndex();
}
return NULL;
static bool isZeroLengthInterval(LiveInterval *li, LiveIntervals *li_) {
for (LiveInterval::Ranges::const_iterator
i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
- if (li_->getPrevIndex(i->end) > i->start)
+ if (i->end.getPrevIndex() > i->start)
return false;
return true;
}
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
mbbi != mbbe; ++mbbi) {
MachineBasicBlock* MBB = mbbi;
- LiveIndex MBBEnd = li_->getMBBEndIdx(MBB);
+ SlotIndex MBBEnd = li_->getMBBEndIdx(MBB);
MachineLoop* loop = loopInfo->getLoopFor(MBB);
unsigned loopDepth = loop ? loop->getLoopDepth() : 0;
bool isExiting = loop ? loop->isLoopExiting(MBB) : false;
float Weight = li_->getSpillWeight(HasDef, HasUse, loopDepth);
if (HasDef && isExiting) {
// Looks like this is a loop count variable update.
- LiveIndex DefIdx = li_->getDefIndex(li_->getInstructionIndex(MI));
+ SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex();
const LiveRange *DLR =
li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
if (DLR->end > MBBEnd)
/// TrimLiveIntervalToLastUse - If there is a last use in the same basic
/// block as the copy instruction, trim the ive interval to the last use
/// and return true.
- bool TrimLiveIntervalToLastUse(LiveIndex CopyIdx,
+ bool TrimLiveIntervalToLastUse(SlotIndex CopyIdx,
MachineBasicBlock *CopyMBB,
LiveInterval &li, const LiveRange *LR);
/// iterator, or any subsequent range with the same value number,
/// is live at the given point.
bool ValueLiveAt(LiveInterval::iterator LRItr, LiveInterval::iterator LREnd,
- LiveIndex defPoint) const;
+ SlotIndex defPoint) const;
/// RangeIsDefinedByCopyFromReg - Return true if the specified live range of
/// the specified live interval is defined by a copy from the specified
/// lastRegisterUse - Returns the last use of the specific register between
/// cycles Start and End or NULL if there are no uses.
- MachineOperand *lastRegisterUse(LiveIndex Start,
- LiveIndex End, unsigned Reg,
- LiveIndex &LastUseIdx) const;
+ MachineOperand *lastRegisterUse(SlotIndex Start, SlotIndex End,
+ unsigned Reg, SlotIndex &LastUseIdx) const;
/// CalculateSpillWeights - Compute spill weights for all virtual register
/// live intervals.
--- /dev/null
+//===-- SlotIndexes.cpp - Slot Indexes Pass ------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "slotindexes"
+
+#include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+std::auto_ptr<IndexListEntry> SlotIndex::emptyKeyPtr(0),
+ SlotIndex::tombstoneKeyPtr(0);
+
+char SlotIndexes::ID = 0;
+static RegisterPass<SlotIndexes> X("slotindexes", "Slot index numbering");
+
+void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
+ au.setPreservesAll();
+ MachineFunctionPass::getAnalysisUsage(au);
+}
+
+void SlotIndexes::releaseMemory() {
+ mi2iMap.clear();
+ mbb2IdxMap.clear();
+ idx2MBBMap.clear();
+ terminatorGaps.clear();
+ clearList();
+}
+
+bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
+
+ // Compute numbering as follows:
+ // Grab an iterator to the start of the index list.
+ // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
+ // iterator in lock-step (though skipping it over indexes which have
+ // null pointers in the instruction field).
+ // At each iteration assert that the instruction pointed to in the index
+ // is the same one pointed to by the MI iterator. This
+
+ // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
+ // only need to be set up once after the first numbering is computed.
+
+ mf = &fn;
+ initList();
+
+ const unsigned gap = 1;
+
+ // Check that the list contains only the sentinal.
+ assert(indexListHead->getNext() == 0 &&
+ "Index list non-empty at initial numbering?");
+ assert(idx2MBBMap.empty() &&
+ "Index -> MBB mapping non-empty at initial numbering?");
+ assert(mbb2IdxMap.empty() &&
+ "MBB -> Index mapping non-empty at initial numbering?");
+ assert(mi2iMap.empty() &&
+ "MachineInstr -> Index mapping non-empty at initial numbering?");
+
+ functionSize = 0;
+ /*
+ for (unsigned s = 0; s < SlotIndex::NUM; ++s) {
+ indexList.push_back(createEntry(0, s));
+ }
+
+ unsigned index = gap * SlotIndex::NUM;
+ */
+
+ unsigned index = 0;
+
+ // Iterate over the the function.
+ for (MachineFunction::iterator mbbItr = mf->begin(), mbbEnd = mf->end();
+ mbbItr != mbbEnd; ++mbbItr) {
+ MachineBasicBlock *mbb = &*mbbItr;
+
+ // Insert an index for the MBB start.
+ push_back(createEntry(0, index));
+ SlotIndex blockStartIndex(back(), SlotIndex::LOAD);
+
+ index += gap * SlotIndex::NUM;
+
+ for (MachineBasicBlock::iterator miItr = mbb->begin(), miEnd = mbb->end();
+ miItr != miEnd; ++miItr) {
+ MachineInstr *mi = &*miItr;
+
+ if (miItr == mbb->getFirstTerminator()) {
+ push_back(createEntry(0, index));
+ terminatorGaps.insert(
+ std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
+ index += gap * SlotIndex::NUM;
+ }
+
+ // Insert a store index for the instr.
+ push_back(createEntry(mi, index));
+
+ // Save this base index in the maps.
+ mi2iMap.insert(
+ std::make_pair(mi, SlotIndex(back(), SlotIndex::LOAD)));
+
+ ++functionSize;
+
+ unsigned Slots = mi->getDesc().getNumDefs();
+ if (Slots == 0)
+ Slots = 1;
+
+ index += (Slots + 1) * gap * SlotIndex::NUM;
+ }
+
+ if (mbb->getFirstTerminator() == mbb->end()) {
+ push_back(createEntry(0, index));
+ terminatorGaps.insert(
+ std::make_pair(mbb, SlotIndex(back(), SlotIndex::PHI_BIT)));
+ index += gap * SlotIndex::NUM;
+ }
+
+ SlotIndex blockEndIndex(back(), SlotIndex::STORE);
+ mbb2IdxMap.insert(
+ std::make_pair(mbb, std::make_pair(blockStartIndex, blockEndIndex)));
+
+ idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, mbb));
+ }
+
+ // One blank instruction at the end.
+ push_back(createEntry(0, index));
+
+ // Sort the Idx2MBBMap
+ std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
+
+ DEBUG(dump());
+
+ // And we're done!
+ return false;
+}
+
+void SlotIndexes::renumber() {
+ assert(false && "SlotIndexes::runmuber is not fully implemented yet.");
+
+ // Compute numbering as follows:
+ // Grab an iterator to the start of the index list.
+ // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
+ // iterator in lock-step (though skipping it over indexes which have
+ // null pointers in the instruction field).
+ // At each iteration assert that the instruction pointed to in the index
+ // is the same one pointed to by the MI iterator. This
+
+ // FIXME: This can be simplified. The mi2iMap_, Idx2MBBMap, etc. should
+ // only need to be set up once - when the first numbering is computed.
+
+ assert(false && "Renumbering not supported yet.");
+}
+
+void SlotIndexes::dump() const {
+ for (const IndexListEntry *itr = front(); itr != getTail();
+ itr = itr->getNext()) {
+ errs() << itr->getIndex() << " ";
+
+ if (itr->getInstr() != 0) {
+ errs() << *itr->getInstr();
+ } else {
+ errs() << "\n";
+ }
+ }
+
+ for (MBB2IdxMap::iterator itr = mbb2IdxMap.begin();
+ itr != mbb2IdxMap.end(); ++itr) {
+ errs() << "MBB " << itr->first->getNumber() << " (" << itr->first << ") - ["
+ << itr->second.first << ", " << itr->second.second << "]\n";
+ }
+}
+
+// Print a SlotIndex to a raw_ostream.
+void SlotIndex::print(raw_ostream &os) const {
+ os << getIndex();
+ if (isPHI())
+ os << "*";
+}
+
+// Dump a SlotIndex to stderr.
+void SlotIndex::dump() const {
+ print(errs());
+ errs() << "\n";
+}
+
/// Ensures there is space before the given machine instruction, returns the
/// instruction's new number.
- LiveIndex makeSpaceBefore(MachineInstr *mi) {
+ SlotIndex makeSpaceBefore(MachineInstr *mi) {
if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
- lis->scaleNumbering(2);
- ls->scaleNumbering(2);
+ // FIXME: Should be updated to use rewrite-in-place methods when they're
+ // introduced. Currently broken.
+ //lis->scaleNumbering(2);
+ //ls->scaleNumbering(2);
}
- LiveIndex miIdx = lis->getInstructionIndex(mi);
+ SlotIndex miIdx = lis->getInstructionIndex(mi);
assert(lis->hasGapBeforeInstr(miIdx));
/// Ensure there is space after the given machine instruction, returns the
/// instruction's new number.
- LiveIndex makeSpaceAfter(MachineInstr *mi) {
+ SlotIndex makeSpaceAfter(MachineInstr *mi) {
if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
- lis->scaleNumbering(2);
- ls->scaleNumbering(2);
+ // FIXME: Should be updated to use rewrite-in-place methods when they're
+ // introduced. Currently broken.
+ // lis->scaleNumbering(2);
+ // ls->scaleNumbering(2);
}
- LiveIndex miIdx = lis->getInstructionIndex(mi);
+ SlotIndex miIdx = lis->getInstructionIndex(mi);
assert(lis->hasGapAfterInstr(miIdx));
/// after the given instruction. Returns the base index of the inserted
/// instruction. The caller is responsible for adding an appropriate
/// LiveInterval to the LiveIntervals analysis.
- LiveIndex insertStoreAfter(MachineInstr *mi, unsigned ss,
+ SlotIndex insertStoreAfter(MachineInstr *mi, unsigned ss,
unsigned vreg,
const TargetRegisterClass *trc) {
MachineBasicBlock::iterator nextInstItr(next(mi));
- LiveIndex miIdx = makeSpaceAfter(mi);
+ SlotIndex miIdx = makeSpaceAfter(mi);
tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
true, ss, trc);
MachineBasicBlock::iterator storeInstItr(next(mi));
MachineInstr *storeInst = &*storeInstItr;
- LiveIndex storeInstIdx = lis->getNextIndex(miIdx);
+ SlotIndex storeInstIdx = miIdx.getNextIndex();
assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
"Store inst index already in use.");
/// Insert a store of the given vreg to the given stack slot immediately
/// before the given instructnion. Returns the base index of the inserted
/// Instruction.
- LiveIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
+ SlotIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
unsigned vreg,
const TargetRegisterClass *trc) {
- LiveIndex miIdx = makeSpaceBefore(mi);
+ SlotIndex miIdx = makeSpaceBefore(mi);
tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
MachineBasicBlock::iterator storeInstItr(prior(mi));
MachineInstr *storeInst = &*storeInstItr;
- LiveIndex storeInstIdx = lis->getPrevIndex(miIdx);
+ SlotIndex storeInstIdx = miIdx.getPrevIndex();
assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
"Store inst index already in use.");
unsigned vreg,
const TargetRegisterClass *trc) {
- LiveIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
- LiveIndex start = lis->getDefIndex(lis->getInstructionIndex(mi)),
- end = lis->getUseIndex(storeInstIdx);
+ SlotIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
+ SlotIndex start = lis->getInstructionIndex(mi).getDefIndex(),
+ end = storeInstIdx.getUseIndex();
VNInfo *vni =
li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
/// after the given instruction. Returns the base index of the inserted
/// instruction. The caller is responsibel for adding/removing an appropriate
/// range vreg's LiveInterval.
- LiveIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
+ SlotIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
unsigned vreg,
const TargetRegisterClass *trc) {
MachineBasicBlock::iterator nextInstItr(next(mi));
- LiveIndex miIdx = makeSpaceAfter(mi);
+ SlotIndex miIdx = makeSpaceAfter(mi);
tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
MachineBasicBlock::iterator loadInstItr(next(mi));
MachineInstr *loadInst = &*loadInstItr;
- LiveIndex loadInstIdx = lis->getNextIndex(miIdx);
+ SlotIndex loadInstIdx = miIdx.getNextIndex();
assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
"Store inst index already in use.");
/// before the given instruction. Returns the base index of the inserted
/// instruction. The caller is responsible for adding an appropriate
/// LiveInterval to the LiveIntervals analysis.
- LiveIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
+ SlotIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
unsigned vreg,
const TargetRegisterClass *trc) {
- LiveIndex miIdx = makeSpaceBefore(mi);
+ SlotIndex miIdx = makeSpaceBefore(mi);
tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
MachineBasicBlock::iterator loadInstItr(prior(mi));
MachineInstr *loadInst = &*loadInstItr;
- LiveIndex loadInstIdx = lis->getPrevIndex(miIdx);
+ SlotIndex loadInstIdx = miIdx.getPrevIndex();
assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
"Load inst index already in use.");
unsigned vreg,
const TargetRegisterClass *trc) {
- LiveIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
- LiveIndex start = lis->getDefIndex(loadInstIdx),
- end = lis->getUseIndex(lis->getInstructionIndex(mi));
+ SlotIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
+ SlotIndex start = loadInstIdx.getDefIndex(),
+ end = lis->getInstructionIndex(mi).getUseIndex();
VNInfo *vni =
li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
vrm->assignVirt2StackSlot(li->reg, ss);
MachineInstr *mi = 0;
- LiveIndex storeIdx = LiveIndex();
+ SlotIndex storeIdx = SlotIndex();
if (valno->isDefAccurate()) {
// If we have an accurate def we can just grab an iterator to the instr
// after the def.
mi = lis->getInstructionFromIndex(valno->def);
- storeIdx = lis->getDefIndex(insertStoreAfter(mi, ss, li->reg, trc));
+ storeIdx = insertStoreAfter(mi, ss, li->reg, trc).getDefIndex();
} else {
// if we get here we have a PHI def.
mi = &lis->getMBBFromIndex(valno->def)->front();
- storeIdx = lis->getDefIndex(insertStoreBefore(mi, ss, li->reg, trc));
+ storeIdx = insertStoreBefore(mi, ss, li->reg, trc).getDefIndex();
}
MachineBasicBlock *defBlock = mi->getParent();
- LiveIndex loadIdx = LiveIndex();
+ SlotIndex loadIdx = SlotIndex();
// Now we need to find the load...
MachineBasicBlock::iterator useItr(mi);
if (useItr != defBlock->end()) {
MachineInstr *loadInst = useItr;
- loadIdx = lis->getUseIndex(insertLoadBefore(loadInst, ss, li->reg, trc));
+ loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc).getUseIndex();
}
else {
MachineInstr *loadInst = &defBlock->back();
- loadIdx = lis->getUseIndex(insertLoadAfter(loadInst, ss, li->reg, trc));
+ loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc).getUseIndex();
}
li->removeRange(storeIdx, loadIdx, true);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
+ AU.addRequired<SlotIndexes>();
+ AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveStacks>();
AU.addRequired<VirtRegMap>();
AU.addPreserved<VirtRegMap>();
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequired<MachineDominatorTree>();
+ AU.addRequired<SlotIndexes>();
+ AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
// TODO: Actually make this true.
static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
LiveIntervals& LI) {
LiveInterval& I = LI.getOrCreateInterval(r);
- LiveIndex idx = LI.getMBBStartIdx(MBB);
+ SlotIndex idx = LI.getMBBStartIdx(MBB);
return I.liveAt(idx);
}
}
LiveInterval& PI = LI.getOrCreateInterval(DestReg);
- LiveIndex pIdx = LI.getDefIndex(LI.getInstructionIndex(P));
+ SlotIndex pIdx = LI.getInstructionIndex(P).getDefIndex();
VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno;
PhiValueNumber.insert(std::make_pair(DestReg, PVN->id));
LiveInterval& I = LI.getInterval(curr.second);
MachineBasicBlock::iterator term = MBB->getFirstTerminator();
- LiveIndex endIdx = LiveIndex();
+ SlotIndex endIdx = SlotIndex();
if (term != MBB->end())
endIdx = LI.getInstructionIndex(term);
else
// Renumber the instructions so that we can perform the index computations
// needed to create new live intervals.
- LI.computeNumbering();
+ LI.renumber();
// For copies that we inserted at the ends of predecessors, we construct
// live intervals. This is pretty easy, since we know that the destination
InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) {
if (RegHandled.insert(I->first).second) {
LiveInterval& Int = LI.getOrCreateInterval(I->first);
- LiveIndex instrIdx = LI.getInstructionIndex(I->second);
- if (Int.liveAt(LI.getDefIndex(instrIdx)))
- Int.removeRange(LI.getDefIndex(instrIdx),
- LI.getNextSlot(LI.getMBBEndIdx(I->second->getParent())),
+ SlotIndex instrIdx = LI.getInstructionIndex(I->second);
+ if (Int.liveAt(instrIdx.getDefIndex()))
+ Int.removeRange(instrIdx.getDefIndex(),
+ LI.getMBBEndIdx(I->second->getParent()).getNextSlot(),
true);
LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second);
R.valno->setCopy(I->second);
- R.valno->def = LI.getDefIndex(LI.getInstructionIndex(I->second));
+ R.valno->def = LI.getInstructionIndex(I->second).getDefIndex();
}
}
}
Stacks[I->getOperand(i).getReg()].size()) {
// Remove the live range for the old vreg.
LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg());
- LiveInterval::iterator OldLR = OldInt.FindLiveRangeContaining(
- LI.getUseIndex(LI.getInstructionIndex(I)));
+ LiveInterval::iterator OldLR =
+ OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex());
if (OldLR != OldInt.end())
OldInt.removeRange(*OldLR, true);
VNInfo* FirstVN = *Int.vni_begin();
FirstVN->setHasPHIKill(false);
if (I->getOperand(i).isKill())
- FirstVN->addKill(
- LI.getUseIndex(LI.getInstructionIndex(I)));
+ FirstVN->addKill(LI.getInstructionIndex(I).getUseIndex());
LiveRange LR (LI.getMBBStartIdx(I->getParent()),
- LI.getNextSlot(LI.getUseIndex(LI.getInstructionIndex(I))),
+ LI.getInstructionIndex(I).getUseIndex().getNextSlot(),
FirstVN);
Int.addRange(LR);
LiveInterval& LHS = LI.getOrCreateInterval(primary);
LiveInterval& RHS = LI.getOrCreateInterval(secondary);
- LI.computeNumbering();
+ LI.renumber();
DenseMap<VNInfo*, VNInfo*> VNMap;
for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
LiveRange R = *I;
- LiveIndex Start = R.start;
- LiveIndex End = R.end;
+ SlotIndex Start = R.start;
+ SlotIndex End = R.end;
if (LHS.getLiveRangeContaining(Start))
return false;
TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(),
I->first, SI->first, RC, RC);
- LI.computeNumbering();
+ LI.renumber();
LiveInterval& Int = LI.getOrCreateInterval(I->first);
- LiveIndex instrIdx =
+ SlotIndex instrIdx =
LI.getInstructionIndex(--SI->second->getFirstTerminator());
- if (Int.liveAt(LI.getDefIndex(instrIdx)))
- Int.removeRange(LI.getDefIndex(instrIdx),
- LI.getNextSlot(LI.getMBBEndIdx(SI->second)), true);
+ if (Int.liveAt(instrIdx.getDefIndex()))
+ Int.removeRange(instrIdx.getDefIndex(),
+ LI.getMBBEndIdx(SI->second).getNextSlot(), true);
LiveRange R = LI.addLiveRangeToEndOfBlock(I->first,
--SI->second->getFirstTerminator());
R.valno->setCopy(--SI->second->getFirstTerminator());
- R.valno->def = LI.getDefIndex(instrIdx);
+ R.valno->def = instrIdx.getDefIndex();
DEBUG(errs() << "Renaming failed: " << SI->first << " -> "
<< I->first << "\n");
if (PI.containsOneValue()) {
LI.removeInterval(DestReg);
} else {
- LiveIndex idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+ SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
PI.removeRange(*PI.getLiveRangeContaining(idx), true);
}
} else {
LiveInterval& InputI = LI.getInterval(reg);
if (MBB != PInstr->getParent() &&
InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) &&
- InputI.expiredAt(LI.getNextIndex(LI.getInstructionIndex(PInstr))))
+ InputI.expiredAt(LI.getInstructionIndex(PInstr).getNextIndex()))
InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()),
LI.getInstructionIndex(PInstr),
true);
// If the PHI is not dead, then the valno defined by the PHI
// now has an unknown def.
- LiveIndex idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+ SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
const LiveRange* PLR = PI.getLiveRangeContaining(idx);
PLR->valno->setIsPHIDef(true);
LiveRange R (LI.getMBBStartIdx(PInstr->getParent()),
PInstr->eraseFromParent();
}
- LI.computeNumbering();
+ LI.renumber();
return true;
}
TII = mf.getTarget().getInstrInfo();
TRI = mf.getTarget().getRegisterInfo();
MF = &mf;
-
+
ReMatId = MAX_STACK_SLOT+1;
LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
/// Virt2SplitKillMap - This is splitted virtual register to its last use
/// (kill) index mapping.
- IndexedMap<LiveIndex> Virt2SplitKillMap;
+ IndexedMap<SlotIndex> Virt2SplitKillMap;
/// ReMatMap - This is virtual register to re-materialized instruction
/// mapping. Each virtual register whose definition is going to be
VirtRegMap() : MachineFunctionPass(&ID), Virt2PhysMap(NO_PHYS_REG),
Virt2StackSlotMap(NO_STACK_SLOT),
Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
- Virt2SplitKillMap(LiveIndex()), ReMatMap(NULL),
+ Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL),
ReMatId(MAX_STACK_SLOT+1),
LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
virtual bool runOnMachineFunction(MachineFunction &MF);
}
/// @brief record the last use (kill) of a split virtual register.
- void addKillPoint(unsigned virtReg, LiveIndex index) {
+ void addKillPoint(unsigned virtReg, SlotIndex index) {
Virt2SplitKillMap[virtReg] = index;
}
- LiveIndex getKillPoint(unsigned virtReg) const {
+ SlotIndex getKillPoint(unsigned virtReg) const {
return Virt2SplitKillMap[virtReg];
}
/// @brief remove the last use (kill) of a split virtual register.
void removeKillPoint(unsigned virtReg) {
- Virt2SplitKillMap[virtReg] = LiveIndex();
+ Virt2SplitKillMap[virtReg] = SlotIndex();
}
/// @brief returns true if the specified MachineInstr is a spill point.
projects / oota-llvm.git / commitdiff