diff options
Diffstat (limited to 'include/llvm/CodeGen')
23 files changed, 1022 insertions, 526 deletions
diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index 62d0679..a0bd330 100644 --- a/include/llvm/CodeGen/AsmPrinter.h +++ b/include/llvm/CodeGen/AsmPrinter.h @@ -22,6 +22,7 @@ #include "llvm/ADT/DenseMap.h" namespace llvm { + class BlockAddress; class GCStrategy; class Constant; class ConstantArray; @@ -334,6 +335,12 @@ namespace llvm { /// block label. MCSymbol *GetMBBSymbol(unsigned MBBID) const; + /// GetBlockAddressSymbol - Return the MCSymbol used to satisfy BlockAddress + /// uses of the specified basic block. + MCSymbol *GetBlockAddressSymbol(const BlockAddress *BA) const; + MCSymbol *GetBlockAddressSymbol(const Function *F, + const BasicBlock *BB) const; + /// EmitBasicBlockStart - This method prints the label for the specified /// MachineBasicBlock, an alignment (if present) and a comment describing /// it if appropriate. diff --git a/include/llvm/CodeGen/BinaryObject.h b/include/llvm/CodeGen/BinaryObject.h index 2d4bd73..9e2ef18 100644 --- a/include/llvm/CodeGen/BinaryObject.h +++ b/include/llvm/CodeGen/BinaryObject.h @@ -15,7 +15,7 @@ #ifndef LLVM_CODEGEN_BINARYOBJECT_H #define LLVM_CODEGEN_BINARYOBJECT_H -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include <string> #include <vector> diff --git a/include/llvm/CodeGen/ELFRelocation.h b/include/llvm/CodeGen/ELFRelocation.h index c3f88f1..e58b8df 100644 --- a/include/llvm/CodeGen/ELFRelocation.h +++ b/include/llvm/CodeGen/ELFRelocation.h @@ -14,7 +14,7 @@ #ifndef LLVM_CODEGEN_ELF_RELOCATION_H #define LLVM_CODEGEN_ELF_RELOCATION_H -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" namespace llvm { diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h index 180783a..792fb59 100644 --- a/include/llvm/CodeGen/JITCodeEmitter.h +++ b/include/llvm/CodeGen/JITCodeEmitter.h @@ -18,7 +18,7 @@ #define LLVM_CODEGEN_JITCODEEMITTER_H #include <string> -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include "llvm/Support/MathExtras.h" #include "llvm/CodeGen/MachineCodeEmitter.h" diff --git a/include/llvm/CodeGen/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h index 71fae2a..a7cebee 100644 --- a/include/llvm/CodeGen/LatencyPriorityQueue.h +++ b/include/llvm/CodeGen/LatencyPriorityQueue.h @@ -39,12 +39,21 @@ namespace llvm { /// predecessor for. This is used as a tie-breaker heuristic for better /// mobility. std::vector<unsigned> NumNodesSolelyBlocking; - + + /// IgnoreAntiDep - Ignore anti-dependencies + bool IgnoreAntiDep; + + /// Queue - The queue. PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; + public: - LatencyPriorityQueue() : Queue(latency_sort(this)) { + LatencyPriorityQueue() : IgnoreAntiDep(false), Queue(latency_sort(this)) { } - + + void setIgnoreAntiDep(bool ignore) { + IgnoreAntiDep = ignore; + } + void initNodes(std::vector<SUnit> &sunits) { SUnits = &sunits; NumNodesSolelyBlocking.resize(SUnits->size(), 0); @@ -63,7 +72,7 @@ public: unsigned getLatency(unsigned NodeNum) const { assert(NodeNum < (*SUnits).size()); - return (*SUnits)[NodeNum].getHeight(); + return (*SUnits)[NodeNum].getHeight(IgnoreAntiDep); } unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 05bd173..e31a7f0 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -21,221 +21,19 @@ #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 @@ -270,23 +68,25 @@ namespace llvm { 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. @@ -377,7 +177,7 @@ namespace llvm { } /// 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); @@ -385,7 +185,7 @@ namespace llvm { /// 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 { @@ -397,7 +197,7 @@ namespace llvm { /// 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); @@ -407,7 +207,7 @@ namespace llvm { } /// 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); @@ -421,11 +221,11 @@ namespace llvm { /// 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"); @@ -433,13 +233,13 @@ namespace llvm { /// 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); } @@ -461,11 +261,11 @@ namespace llvm { 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; } @@ -522,7 +322,7 @@ namespace llvm { /// 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; @@ -569,7 +369,7 @@ namespace llvm { /// 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), @@ -625,13 +425,15 @@ namespace llvm { /// 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# @@ -657,56 +459,54 @@ namespace llvm { 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). @@ -721,7 +521,7 @@ namespace llvm { /// 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 @@ -738,18 +538,19 @@ namespace llvm { /// 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) { @@ -773,8 +574,8 @@ namespace llvm { 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)); } @@ -785,8 +586,9 @@ namespace llvm { 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 }; diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 511db6d..efb4a03 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -23,12 +23,14 @@ #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 { @@ -40,21 +42,6 @@ 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_; @@ -64,33 +51,15 @@ namespace llvm { 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; @@ -100,48 +69,10 @@ namespace llvm { /// 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); } @@ -170,111 +101,18 @@ namespace llvm { 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 @@ -288,19 +126,7 @@ namespace llvm { 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()) @@ -325,36 +151,75 @@ namespace llvm { 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; } @@ -417,13 +282,6 @@ namespace llvm { /// 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; @@ -443,14 +301,14 @@ namespace llvm { /// 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); @@ -458,13 +316,13 @@ namespace llvm { /// 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 @@ -477,7 +335,7 @@ namespace llvm { /// 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 @@ -492,7 +350,7 @@ namespace llvm { /// 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); @@ -506,7 +364,7 @@ namespace llvm { /// 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. @@ -514,17 +372,17 @@ namespace llvm { /// 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); @@ -543,7 +401,7 @@ namespace llvm { /// 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, diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h index d63a222..e01d1ae 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -48,8 +48,6 @@ namespace llvm { 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) { diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 2a9e86a..585ee14 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -76,6 +76,10 @@ class MachineBasicBlock : public ilist_node<MachineBasicBlock> { /// exception handler. bool IsLandingPad; + /// AddressTaken - Indicate that this basic block is potentially the + /// target of an indirect branch. + bool AddressTaken; + // Intrusive list support MachineBasicBlock() {} @@ -92,6 +96,14 @@ public: /// const BasicBlock *getBasicBlock() const { return BB; } + /// hasAddressTaken - Test whether this block is potentially the target + /// of an indirect branch. + bool hasAddressTaken() const { return AddressTaken; } + + /// setHasAddressTaken - Set this block to reflect that it potentially + /// is the target of an indirect branch. + void setHasAddressTaken() { AddressTaken = true; } + /// getParent - Return the MachineFunction containing this basic block. /// const MachineFunction *getParent() const { return xParent; } diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h index abb6dd9..c55a9e6 100644 --- a/include/llvm/CodeGen/MachineCodeEmitter.h +++ b/include/llvm/CodeGen/MachineCodeEmitter.h @@ -17,7 +17,7 @@ #ifndef LLVM_CODEGEN_MACHINECODEEMITTER_H #define LLVM_CODEGEN_MACHINECODEEMITTER_H -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include "llvm/Support/DebugLoc.h" namespace llvm { diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index a04189c..07c1eca 100644 --- a/include/llvm/CodeGen/MachineFrameInfo.h +++ b/include/llvm/CodeGen/MachineFrameInfo.h @@ -16,7 +16,7 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include <cassert> #include <vector> diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h index 7f681d7..6ca63f0 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -108,13 +108,6 @@ public: return *this; } - const MachineInstrBuilder &addMetadata(MDNode *N, - int64_t Offset = 0, - unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateMDNode(N, Offset, TargetFlags)); - return *this; - } - const MachineInstrBuilder &addExternalSymbol(const char *FnName, unsigned char TargetFlags = 0) const { MI->addOperand(MachineOperand::CreateES(FnName, TargetFlags)); diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index 1b924f2..f2b027b 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -32,7 +32,7 @@ #define LLVM_CODEGEN_MACHINEMODULEINFO_H #include "llvm/Support/Dwarf.h" -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/UniqueVector.h" diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index f715c44..eede2cc 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -14,15 +14,15 @@ #ifndef LLVM_CODEGEN_MACHINEOPERAND_H #define LLVM_CODEGEN_MACHINEOPERAND_H -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include <cassert> namespace llvm { class ConstantFP; +class BlockAddress; class MachineBasicBlock; class GlobalValue; -class MDNode; class MachineInstr; class TargetMachine; class MachineRegisterInfo; @@ -42,7 +42,7 @@ public: MO_JumpTableIndex, ///< Address of indexed Jump Table for switch MO_ExternalSymbol, ///< Name of external global symbol MO_GlobalAddress, ///< Address of a global value - MO_Metadata ///< Metadata info + MO_BlockAddress ///< Address of a basic block }; private: @@ -108,7 +108,7 @@ private: int Index; // For MO_*Index - The index itself. const char *SymbolName; // For MO_ExternalSymbol. GlobalValue *GV; // For MO_GlobalAddress. - MDNode *Node; // For MO_Metadata. + BlockAddress *BA; // For MO_BlockAddress. } Val; int64_t Offset; // An offset from the object. } OffsetedInfo; @@ -156,8 +156,8 @@ public: bool isGlobal() const { return OpKind == MO_GlobalAddress; } /// isSymbol - Tests if this is a MO_ExternalSymbol operand. bool isSymbol() const { return OpKind == MO_ExternalSymbol; } - /// isMetadata - Tests if this is a MO_Metadata operand. - bool isMetadata() const { return OpKind == MO_Metadata; } + /// isBlockAddress - Tests if this is a MO_BlockAddress operand. + bool isBlockAddress() const { return OpKind == MO_BlockAddress; } //===--------------------------------------------------------------------===// // Accessors for Register Operands @@ -293,15 +293,16 @@ public: assert(isGlobal() && "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Val.GV; } - - MDNode *getMDNode() const { - return Contents.OffsetedInfo.Val.Node; + + BlockAddress *getBlockAddress() const { + assert(isBlockAddress() && "Wrong MachineOperand accessor"); + return Contents.OffsetedInfo.Val.BA; } /// getOffset - Return the offset from the symbol in this operand. This always /// returns 0 for ExternalSymbol operands. int64_t getOffset() const { - assert((isGlobal() || isSymbol() || isCPI()) && + assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) && "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Offset; } @@ -321,7 +322,7 @@ public: } void setOffset(int64_t Offset) { - assert((isGlobal() || isSymbol() || isCPI() || isMetadata()) && + assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) && "Wrong MachineOperand accessor"); Contents.OffsetedInfo.Offset = Offset; } @@ -426,14 +427,6 @@ public: Op.setTargetFlags(TargetFlags); return Op; } - static MachineOperand CreateMDNode(MDNode *N, int64_t Offset, - unsigned char TargetFlags = 0) { - MachineOperand Op(MachineOperand::MO_Metadata); - Op.Contents.OffsetedInfo.Val.Node = N; - Op.setOffset(Offset); - Op.setTargetFlags(TargetFlags); - return Op; - } static MachineOperand CreateES(const char *SymName, unsigned char TargetFlags = 0) { MachineOperand Op(MachineOperand::MO_ExternalSymbol); @@ -442,6 +435,12 @@ public: Op.setTargetFlags(TargetFlags); return Op; } + static MachineOperand CreateBA(BlockAddress *BA) { + MachineOperand Op(MachineOperand::MO_BlockAddress); + Op.Contents.OffsetedInfo.Val.BA = BA; + Op.setOffset(0); // Offset is always 0. + return Op; + } friend class MachineInstr; friend class MachineRegisterInfo; diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h index c539781..6ea8f07 100644 --- a/include/llvm/CodeGen/MachineRelocation.h +++ b/include/llvm/CodeGen/MachineRelocation.h @@ -14,7 +14,7 @@ #ifndef LLVM_CODEGEN_MACHINERELOCATION_H #define LLVM_CODEGEN_MACHINERELOCATION_H -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include <cassert> namespace llvm { diff --git a/include/llvm/CodeGen/ProcessImplicitDefs.h b/include/llvm/CodeGen/ProcessImplicitDefs.h new file mode 100644 index 0000000..cec867f --- /dev/null +++ b/include/llvm/CodeGen/ProcessImplicitDefs.h @@ -0,0 +1,41 @@ +//===-------------- 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 diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index 7a9122d..26392f5 100644 --- a/include/llvm/CodeGen/PseudoSourceValue.h +++ b/include/llvm/CodeGen/PseudoSourceValue.h @@ -43,6 +43,10 @@ namespace llvm { /// PseudoSourceValue may also be pointed to by an LLVM IR Value. virtual bool isAliased(const MachineFrameInfo *) const; + /// mayAlias - Return true if the memory pointed to by this + /// PseudoSourceValue can ever alias a LLVM IR Value. + virtual bool mayAlias(const MachineFrameInfo *) const; + /// classof - Methods for support type inquiry through isa, cast, and /// dyn_cast: /// diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index fdbbb1e..d5e7020 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -340,28 +340,34 @@ namespace llvm { void removePred(const SDep &D); /// getDepth - Return the depth of this node, which is the length of the - /// maximum path up to any node with has no predecessors. - unsigned getDepth() const { - if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth(); + /// maximum path up to any node with has no predecessors. If IgnoreAntiDep + /// is true, ignore anti-dependence edges. + unsigned getDepth(bool IgnoreAntiDep=false) const { + if (!isDepthCurrent) + const_cast<SUnit *>(this)->ComputeDepth(IgnoreAntiDep); return Depth; } /// getHeight - Return the height of this node, which is the length of the - /// maximum path down to any node with has no successors. - unsigned getHeight() const { - if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight(); + /// maximum path down to any node with has no successors. If IgnoreAntiDep + /// is true, ignore anti-dependence edges. + unsigned getHeight(bool IgnoreAntiDep=false) const { + if (!isHeightCurrent) + const_cast<SUnit *>(this)->ComputeHeight(IgnoreAntiDep); return Height; } - /// setDepthToAtLeast - If NewDepth is greater than this node's depth - /// value, set it to be the new depth value. This also recursively - /// marks successor nodes dirty. - void setDepthToAtLeast(unsigned NewDepth); + /// setDepthToAtLeast - If NewDepth is greater than this node's + /// depth value, set it to be the new depth value. This also + /// recursively marks successor nodes dirty. If IgnoreAntiDep is + /// true, ignore anti-dependence edges. + void setDepthToAtLeast(unsigned NewDepth, bool IgnoreAntiDep=false); - /// setDepthToAtLeast - If NewDepth is greater than this node's depth - /// value, set it to be the new height value. This also recursively - /// marks predecessor nodes dirty. - void setHeightToAtLeast(unsigned NewHeight); + /// setDepthToAtLeast - If NewDepth is greater than this node's + /// depth value, set it to be the new height value. This also + /// recursively marks predecessor nodes dirty. If IgnoreAntiDep is + /// true, ignore anti-dependence edges. + void setHeightToAtLeast(unsigned NewHeight, bool IgnoreAntiDep=false); /// setDepthDirty - Set a flag in this node to indicate that its /// stored Depth value will require recomputation the next time @@ -394,8 +400,8 @@ namespace llvm { void print(raw_ostream &O, const ScheduleDAG *G) const; private: - void ComputeDepth(); - void ComputeHeight(); + void ComputeDepth(bool IgnoreAntiDep); + void ComputeHeight(bool IgnoreAntiDep); }; //===--------------------------------------------------------------------===// diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index e0198ef..8400e86 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -326,6 +326,8 @@ public: unsigned Line, unsigned Col, MDNode *CU); SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root, unsigned LabelID); + SDValue getBlockAddress(BlockAddress *BA, DebugLoc dl, + bool isTarget = false); SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index 2b713f1..5d33224 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -110,6 +110,14 @@ protected: bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const; + // Calls to these functions are generated by tblgen. + SDNode *Select_INLINEASM(SDValue N); + SDNode *Select_UNDEF(const SDValue &N); + SDNode *Select_DBG_LABEL(const SDValue &N); + SDNode *Select_EH_LABEL(const SDValue &N); + void CannotYetSelect(SDValue N); + void CannotYetSelectIntrinsic(SDValue N); + private: void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, MachineModuleInfo *MMI, diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index d7c8f1c..f960851 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -28,7 +28,7 @@ #include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/Support/MathExtras.h" -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include "llvm/Support/DebugLoc.h" #include <cassert> @@ -97,7 +97,7 @@ namespace ISD { BasicBlock, VALUETYPE, CONDCODE, Register, Constant, ConstantFP, GlobalAddress, GlobalTLSAddress, FrameIndex, - JumpTable, ConstantPool, ExternalSymbol, + JumpTable, ConstantPool, ExternalSymbol, BlockAddress, // The address of the GOT GLOBAL_OFFSET_TABLE, @@ -146,6 +146,7 @@ namespace ISD { TargetJumpTable, TargetConstantPool, TargetExternalSymbol, + TargetBlockAddress, /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) /// This node represents a target intrinsic function with no side effects. @@ -2026,11 +2027,27 @@ public: } }; +class BlockAddressSDNode : public SDNode { + BlockAddress *BA; + friend class SelectionDAG; + BlockAddressSDNode(unsigned NodeTy, DebugLoc dl, EVT VT, BlockAddress *ba) + : SDNode(NodeTy, dl, getSDVTList(VT)), BA(ba) { + } +public: + BlockAddress *getBlockAddress() const { return BA; } + + static bool classof(const BlockAddressSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::BlockAddress || + N->getOpcode() == ISD::TargetBlockAddress; + } +}; + class LabelSDNode : public SDNode { SDUse Chain; unsigned LabelID; friend class SelectionDAG; -LabelSDNode(unsigned NodeTy, DebugLoc dl, SDValue ch, unsigned id) + LabelSDNode(unsigned NodeTy, DebugLoc dl, SDValue ch, unsigned id) : SDNode(NodeTy, dl, getSDVTList(MVT::Other)), LabelID(id) { InitOperands(&Chain, ch); } diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h new file mode 100644 index 0000000..3f175a7 --- /dev/null +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -0,0 +1,740 @@ +//===- 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 { + 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; } + }; + + // 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 diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index 1f0dd21..45ef9b9 100644 --- a/include/llvm/CodeGen/ValueTypes.h +++ b/include/llvm/CodeGen/ValueTypes.h @@ -18,7 +18,7 @@ #include <cassert> #include <string> -#include "llvm/Support/DataTypes.h" +#include "llvm/System/DataTypes.h" #include "llvm/Support/MathExtras.h" namespace llvm { |
