diff options
Diffstat (limited to 'include/llvm/CodeGen')
39 files changed, 2057 insertions, 1098 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index ce9ca0a..b2cc704 100644 --- a/include/llvm/CodeGen/Analysis.h +++ b/include/llvm/CodeGen/Analysis.h @@ -26,6 +26,7 @@ namespace llvm { class GlobalVariable; class TargetLowering; +class TargetLoweringBase; class SDNode; class SDValue; class SelectionDAG; @@ -88,6 +89,14 @@ ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred); /// This function only tests target-independent requirements. bool isInTailCallPosition(ImmutableCallSite CS, const TargetLowering &TLI); +/// Test if given that the input instruction is in the tail call position if the +/// return type or any attributes of the function will inhibit tail call +/// optimization. +bool returnTypeIsEligibleForTailCall(const Function *F, + const Instruction *I, + const ReturnInst *Ret, + const TargetLoweringBase &TLI); + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index 677331b..4bda0f1 100644 --- a/include/llvm/CodeGen/AsmPrinter.h +++ b/include/llvm/CodeGen/AsmPrinter.h @@ -41,6 +41,7 @@ namespace llvm { class MCAsmInfo; class MCCFIInstruction; class MCContext; + class MCInstrInfo; class MCSection; class MCStreamer; class MCSymbol; @@ -64,6 +65,7 @@ namespace llvm { /// const MCAsmInfo *MAI; + const MCInstrInfo *MII; /// OutContext - This is the context for the output file that we are /// streaming. This owns all of the global MC-related objects for the /// generated translation unit. @@ -143,6 +145,7 @@ namespace llvm { /// getCurrentSection() - Return the current section we are emitting to. const MCSection *getCurrentSection() const; + MCSymbol *getSymbol(const GlobalValue *GV) const; //===------------------------------------------------------------------===// // MachineFunctionPass Implementation. @@ -284,6 +287,10 @@ namespace llvm { virtual bool isBlockOnlyReachableByFallthrough(const MachineBasicBlock *MBB) const; + /// emitImplicitDef - Targets can override this to customize the output of + /// IMPLICIT_DEF instructions in verbose mode. + virtual void emitImplicitDef(const MachineInstr *MI) const; + //===------------------------------------------------------------------===// // Symbol Lowering Routines. //===------------------------------------------------------------------===// @@ -359,13 +366,15 @@ namespace llvm { /// where the size in bytes of the directive is specified by Size and Label /// specifies the label. This implicitly uses .set if it is available. void EmitLabelPlusOffset(const MCSymbol *Label, uint64_t Offset, - unsigned Size) const; + unsigned Size, + bool IsSectionRelative = false) const; /// EmitLabelReference - Emit something like ".long Label" /// where the size in bytes of the directive is specified by Size and Label /// specifies the label. - void EmitLabelReference(const MCSymbol *Label, unsigned Size) const { - EmitLabelPlusOffset(Label, 0, Size); + void EmitLabelReference(const MCSymbol *Label, unsigned Size, + bool IsSectionRelative = false) const { + EmitLabelPlusOffset(Label, 0, Size, IsSectionRelative); } //===------------------------------------------------------------------===// @@ -449,8 +458,7 @@ namespace llvm { /// return true if the operand is erroneous. virtual bool PrintAsmMemoryOperand(const MachineInstr *MI, unsigned OpNo, unsigned AsmVariant, - const char *ExtraCode, - raw_ostream &OS); + const char *ExtraCode, raw_ostream &OS); private: /// Private state for PrintSpecial() @@ -462,7 +470,8 @@ namespace llvm { /// EmitInlineAsm - Emit a blob of inline asm to the output streamer. void EmitInlineAsm(StringRef Str, const MDNode *LocMDNode = 0, - InlineAsm::AsmDialect AsmDialect = InlineAsm::AD_ATT) const; + InlineAsm::AsmDialect AsmDialect = + InlineAsm::AD_ATT) const; /// EmitInlineAsm - This method formats and emits the specified machine /// instruction that is an inline asm. @@ -477,12 +486,13 @@ namespace llvm { void EmitVisibility(MCSymbol *Sym, unsigned Visibility, bool IsDefinition = true) const; - void EmitLinkage(unsigned Linkage, MCSymbol *GVSym) const; + void EmitLinkage(const GlobalValue *GV, MCSymbol *GVSym) const; void EmitJumpTableEntry(const MachineJumpTableInfo *MJTI, - const MachineBasicBlock *MBB, - unsigned uid) const; + const MachineBasicBlock *MBB, unsigned uid) const; void EmitLLVMUsedList(const ConstantArray *InitList); + /// Emit llvm.ident metadata in an '.ident' directive. + void EmitModuleIdents(Module &M); void EmitXXStructorList(const Constant *List, bool isCtor); GCMetadataPrinter *GetOrCreateGCPrinter(GCStrategy *C); }; diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h index c8ec764..0d79b1d 100644 --- a/include/llvm/CodeGen/CalcSpillWeights.h +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -21,7 +21,9 @@ namespace llvm { class MachineBlockFrequencyInfo; class MachineLoopInfo; - /// normalizeSpillWeight - The spill weight of a live interval is computed as: + /// \brief Normalize the spill weight of a live interval + /// + /// The spill weight of a live interval is computed as: /// /// (sum(use freq) + sum(def freq)) / (K + size) /// @@ -38,44 +40,38 @@ namespace llvm { return UseDefFreq / (Size + 25*SlotIndex::InstrDist); } - /// VirtRegAuxInfo - Calculate auxiliary information for a virtual - /// register such as its spill weight and allocation hint. + /// \brief Calculate auxiliary information for a virtual register such as its + /// spill weight and allocation hint. class VirtRegAuxInfo { + public: + typedef float (*NormalizingFn)(float, unsigned); + + private: MachineFunction &MF; LiveIntervals &LIS; const MachineLoopInfo &Loops; const MachineBlockFrequencyInfo &MBFI; DenseMap<unsigned, float> Hint; + NormalizingFn normalize; + public: VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, const MachineLoopInfo &loops, - const MachineBlockFrequencyInfo &mbfi) - : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi) {} + const MachineBlockFrequencyInfo &mbfi, + NormalizingFn norm = normalizeSpillWeight) + : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi), normalize(norm) {} - /// CalculateWeightAndHint - (re)compute li's spill weight and allocation - /// hint. - void CalculateWeightAndHint(LiveInterval &li); + /// \brief (re)compute li's spill weight and allocation hint. + void calculateSpillWeightAndHint(LiveInterval &li); }; - /// CalculateSpillWeights - Compute spill weights for all virtual register + /// \brief Compute spill weights and allocation hints for all virtual register /// live intervals. - class CalculateSpillWeights : public MachineFunctionPass { - public: - static char ID; - - CalculateSpillWeights() : MachineFunctionPass(ID) { - initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); - } - - virtual void getAnalysisUsage(AnalysisUsage &au) const; - - virtual bool runOnMachineFunction(MachineFunction &fn); - - private: - /// Returns true if the given live interval is zero length. - bool isZeroLengthInterval(LiveInterval *li) const; - }; - + void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, + const MachineLoopInfo &MLI, + const MachineBlockFrequencyInfo &MBFI, + VirtRegAuxInfo::NormalizingFn norm = + normalizeSpillWeight); } #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h index 0c21e76..bc8dce3 100644 --- a/include/llvm/CodeGen/CommandFlags.h +++ b/include/llvm/CodeGen/CommandFlags.h @@ -150,7 +150,7 @@ FloatABIForCalls("float-abi", cl::opt<llvm::FPOpFusion::FPOpFusionMode> FuseFPOps("fp-contract", - cl::desc("Enable aggresive formation of fused FP ops"), + cl::desc("Enable aggressive formation of fused FP ops"), cl::init(FPOpFusion::Standard), cl::values( clEnumValN(FPOpFusion::Fast, "fast", diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 0063474..1e0ef6b 100644 --- a/include/llvm/CodeGen/FastISel.h +++ b/include/llvm/CodeGen/FastISel.h @@ -358,6 +358,15 @@ protected: return 0; } + /// \brief Check if \c Add is an add that can be safely folded into \c GEP. + /// + /// \c Add can be folded into \c GEP if: + /// - \c Add is an add, + /// - \c Add's size matches \c GEP's, + /// - \c Add is in the same basic block as \c GEP, and + /// - \c Add has a constant operand. + bool canFoldAddIntoGEP(const User *GEP, const Value *Add); + private: bool SelectBinaryOp(const User *I, unsigned ISDOpcode); diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 9466b90..48a0523 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -419,6 +419,10 @@ namespace ISD { /// getNode(). BITCAST, + /// ADDRSPACECAST - This operator converts between pointers of different + /// address spaces. + ADDRSPACECAST, + /// CONVERT_RNDSAT - This operator is used to support various conversions /// between various types (float, signed, unsigned and vectors of those /// types) with rounding and saturation. NOTE: Avoid using this operator as @@ -440,11 +444,11 @@ namespace ISD { /// FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, /// FLOG, FLOG2, FLOG10, FEXP, FEXP2, - /// FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR - Perform various unary + /// FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR - Perform various unary /// floating point operations. These are inspired by libm. FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, FLOG, FLOG2, FLOG10, FEXP, FEXP2, - FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR, + FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR, /// FSINCOS - Compute both fsin and fcos as a single operation. FSINCOS, @@ -604,11 +608,17 @@ namespace ISD { ATOMIC_STORE, /// Val, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmp, swap) + /// For double-word atomic operations: + /// ValLo, ValHi, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmpLo, cmpHi, + /// swapLo, swapHi) /// This corresponds to the cmpxchg instruction. ATOMIC_CMP_SWAP, /// Val, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amt) /// Val, OUTCHAIN = ATOMIC_LOAD_[OpName](INCHAIN, ptr, amt) + /// For double-word atomic operations: + /// ValLo, ValHi, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amtLo, amtHi) + /// ValLo, ValHi, OUTCHAIN = ATOMIC_LOAD_[OpName](INCHAIN, ptr, amtLo, amtHi) /// These correspond to the atomicrmw instruction. ATOMIC_SWAP, ATOMIC_LOAD_ADD, diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index efad0c6..3a9fef6 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -9,12 +9,12 @@ // // This file implements the LiveRange and LiveInterval classes. Given some // numbering of each the machine instructions an interval [i, j) is said to be a -// live interval for register v if there is no instruction with number j' >= j +// live range for register v if there is no instruction with number j' >= j // such that v is live at j' and there is no instruction with number i' < i such -// that v is live at i'. In this implementation intervals can have holes, -// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each -// individual range is represented as an instance of LiveRange, and the whole -// interval is represented as an instance of LiveInterval. +// that v is live at i'. In this implementation ranges can have holes, +// i.e. a range might look like [1,20), [50,65), [1000,1001). Each +// individual segment is represented as an instance of LiveRange::Segment, +// and the whole range is represented as an instance of LiveRange. // //===----------------------------------------------------------------------===// @@ -35,6 +35,7 @@ namespace llvm { class MachineRegisterInfo; class TargetRegisterInfo; class raw_ostream; + template <typename T, unsigned Small> class SmallPtrSet; /// VNInfo - Value Number Information. /// This class holds information about a machine level values, including @@ -66,7 +67,7 @@ namespace llvm { } /// Returns true if this value is defined by a PHI instruction (or was, - /// PHI instrucions may have been eliminated). + /// PHI instructions may have been eliminated). /// PHI-defs begin at a block boundary, all other defs begin at register or /// EC slots. bool isPHIDef() const { return def.isBlock(); } @@ -78,107 +79,136 @@ namespace llvm { void markUnused() { def = SlotIndex(); } }; - /// LiveRange structure - This represents a simple register range in the - /// program, with an inclusive start point and an exclusive end point. - /// These ranges are rendered as [start,end). - struct LiveRange { - 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. + /// Result of a LiveRange query. This class hides the implementation details + /// of live ranges, and it should be used as the primary interface for + /// examining live ranges around instructions. + class LiveQueryResult { + VNInfo *const EarlyVal; + VNInfo *const LateVal; + const SlotIndex EndPoint; + const bool Kill; - LiveRange() : valno(0) {} + public: + LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, + bool Kill) + : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) + {} - LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) - : start(S), end(E), valno(V) { - assert(S < E && "Cannot create empty or backwards range"); + /// Return the value that is live-in to the instruction. This is the value + /// that will be read by the instruction's use operands. Return NULL if no + /// value is live-in. + VNInfo *valueIn() const { + return EarlyVal; } - /// contains - Return true if the index is covered by this range. - /// - bool contains(SlotIndex I) const { - return start <= I && I < end; + /// Return true if the live-in value is killed by this instruction. This + /// means that either the live range ends at the instruction, or it changes + /// value. + bool isKill() const { + return Kill; } - /// containsRange - Return true if the given range, [S, E), is covered by - /// this range. - bool containsRange(SlotIndex S, SlotIndex E) const { - assert((S < E) && "Backwards interval?"); - return (start <= S && S < end) && (start < E && E <= end); + /// Return true if this instruction has a dead def. + bool isDeadDef() const { + return EndPoint.isDead(); } - bool operator<(const LiveRange &LR) const { - return start < LR.start || (start == LR.start && end < LR.end); + /// Return the value leaving the instruction, if any. This can be a + /// live-through value, or a live def. A dead def returns NULL. + VNInfo *valueOut() const { + return isDeadDef() ? 0 : LateVal; } - bool operator==(const LiveRange &LR) const { - return start == LR.start && end == LR.end; + + /// Return the value defined by this instruction, if any. This includes + /// dead defs, it is the value created by the instruction's def operands. + VNInfo *valueDefined() const { + return EarlyVal == LateVal ? 0 : LateVal; } - void dump() const; - void print(raw_ostream &os) const; + /// Return the end point of the last live range segment to interact with + /// the instruction, if any. + /// + /// The end point is an invalid SlotIndex only if the live range doesn't + /// intersect the instruction at all. + /// + /// The end point may be at or past the end of the instruction's basic + /// block. That means the value was live out of the block. + SlotIndex endPoint() const { + return EndPoint; + } }; - template <> struct isPodLike<LiveRange> { static const bool value = true; }; - - raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); - + /// This class represents the liveness of a register, stack slot, etc. + /// It manages an ordered list of Segment objects. + /// The Segments are organized in a static single assignment form: At places + /// where a new value is defined or different values reach a CFG join a new + /// segment with a new value number is used. + class LiveRange { + public: - inline bool operator<(SlotIndex V, const LiveRange &LR) { - return V < LR.start; - } + /// This represents a simple continuous liveness interval for a value. + /// The start point is inclusive, the end point exclusive. These intervals + /// are rendered as [start,end). + struct Segment { + 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 segment. - inline bool operator<(const LiveRange &LR, SlotIndex V) { - return LR.start < V; - } + Segment() : valno(0) {} - /// LiveInterval - This class represents some number of live ranges for a - /// register or value. This class also contains a bit of register allocator - /// state. - class LiveInterval { - public: + Segment(SlotIndex S, SlotIndex E, VNInfo *V) + : start(S), end(E), valno(V) { + assert(S < E && "Cannot create empty or backwards segment"); + } - typedef SmallVector<LiveRange,4> Ranges; - typedef SmallVector<VNInfo*,4> VNInfoList; + /// Return true if the index is covered by this segment. + bool contains(SlotIndex I) const { + return start <= I && I < end; + } - const unsigned reg; // the register or stack slot of this interval. - float weight; // weight of this interval - Ranges ranges; // the ranges in which this register is live - VNInfoList valnos; // value#'s + /// Return true if the given interval, [S, E), is covered by this segment. + bool containsInterval(SlotIndex S, SlotIndex E) const { + assert((S < E) && "Backwards interval?"); + return (start <= S && S < end) && (start < E && E <= end); + } - struct InstrSlots { - enum { - LOAD = 0, - USE = 1, - DEF = 2, - STORE = 3, - NUM = 4 - }; + bool operator<(const Segment &Other) const { + return start < Other.start || (start == Other.start && end < Other.end); + } + bool operator==(const Segment &Other) const { + return start == Other.start && end == Other.end; + } + void dump() const; }; - LiveInterval(unsigned Reg, float Weight) - : reg(Reg), weight(Weight) {} + typedef SmallVector<Segment,4> Segments; + typedef SmallVector<VNInfo*,4> VNInfoList; + + Segments segments; // the liveness segments + VNInfoList valnos; // value#'s - typedef Ranges::iterator iterator; - iterator begin() { return ranges.begin(); } - iterator end() { return ranges.end(); } + typedef Segments::iterator iterator; + iterator begin() { return segments.begin(); } + iterator end() { return segments.end(); } - typedef Ranges::const_iterator const_iterator; - const_iterator begin() const { return ranges.begin(); } - const_iterator end() const { return ranges.end(); } + typedef Segments::const_iterator const_iterator; + const_iterator begin() const { return segments.begin(); } + const_iterator end() const { return segments.end(); } typedef VNInfoList::iterator vni_iterator; vni_iterator vni_begin() { return valnos.begin(); } - vni_iterator vni_end() { return valnos.end(); } + vni_iterator vni_end() { return valnos.end(); } typedef VNInfoList::const_iterator const_vni_iterator; const_vni_iterator vni_begin() const { return valnos.begin(); } - const_vni_iterator vni_end() const { return valnos.end(); } + const_vni_iterator vni_end() const { return valnos.end(); } - /// advanceTo - Advance the specified iterator to point to the LiveRange + /// advanceTo - Advance the specified iterator to point to the Segment /// containing the specified position, or end() if the position is past the - /// end of the interval. If no LiveRange contains this position, but the + /// end of the range. If no Segment contains this position, but the /// position is in a hole, this method returns an iterator pointing to the - /// LiveRange immediately after the hole. + /// Segment immediately after the hole. iterator advanceTo(iterator I, SlotIndex Pos) { assert(I != end()); if (Pos >= endIndex()) @@ -187,22 +217,26 @@ namespace llvm { return I; } - /// find - Return an iterator pointing to the first range that ends after + /// find - Return an iterator pointing to the first segment that ends after /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster - /// when searching large intervals. + /// when searching large ranges. /// - /// If Pos is contained in a LiveRange, that range is returned. - /// If Pos is in a hole, the following LiveRange is returned. + /// If Pos is contained in a Segment, that segment is returned. + /// If Pos is in a hole, the following Segment is returned. /// If Pos is beyond endIndex, end() is returned. iterator find(SlotIndex Pos); const_iterator find(SlotIndex Pos) const { - return const_cast<LiveInterval*>(this)->find(Pos); + return const_cast<LiveRange*>(this)->find(Pos); } void clear() { valnos.clear(); - ranges.clear(); + segments.clear(); + } + + size_t size() const { + return segments.size(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -220,7 +254,7 @@ namespace llvm { return valnos[ValNo]; } - /// containsValue - Returns true if VNI belongs to this interval. + /// containsValue - Returns true if VNI belongs to this range. bool containsValue(const VNInfo *VNI) const { return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); } @@ -234,7 +268,7 @@ namespace llvm { return VNI; } - /// createDeadDef - Make sure the interval has a value defined at Def. + /// createDeadDef - Make sure the range has a value defined at Def. /// If one already exists, return it. Otherwise allocate a new value and /// add liveness for a dead def. VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); @@ -251,42 +285,42 @@ namespace llvm { /// RenumberValues - Renumber all values in order of appearance and remove /// unused values. - void RenumberValues(LiveIntervals &lis); + void RenumberValues(); - /// MergeValueNumberInto - This method is called when two value nubmers + /// MergeValueNumberInto - This method is called when two value numbers /// are found to be equivalent. This eliminates V1, replacing all - /// LiveRanges with the V1 value number with the V2 value number. This can + /// segments with the V1 value number with the V2 value number. This can /// cause merging of V1/V2 values numbers and compaction of the value space. VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// 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 MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); - - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, but only if the overlapping LiveRanges have the + /// Merge all of the live segments of a specific val# in RHS into this live + /// range as the specified value number. The segments in RHS are allowed + /// to overlap with segments in the current range, it will replace the + /// value numbers of the overlaped live segments with the specified value + /// number. + void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); + + /// MergeValueInAsValue - Merge all of the segments of a specific val# + /// in RHS into this live range as the specified value number. + /// The segments in RHS are allowed to overlap with segments in the + /// current range, but only if the overlapping segments have the /// specified value number. - void MergeValueInAsValue(const LiveInterval &RHS, + void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo); - bool empty() const { return ranges.empty(); } + bool empty() const { return segments.empty(); } - /// beginIndex - Return the lowest numbered slot covered by interval. + /// beginIndex - Return the lowest numbered slot covered. SlotIndex beginIndex() const { - assert(!empty() && "Call to beginIndex() on empty interval."); - return ranges.front().start; + assert(!empty() && "Call to beginIndex() on empty range."); + return segments.front().start; } - /// endNumber - return the maximum point of the interval of the whole, + /// endNumber - return the maximum point of the range of the whole, /// exclusive. SlotIndex endIndex() const { - assert(!empty() && "Call to endIndex() on empty interval."); - return ranges.back().end; + assert(!empty() && "Call to endIndex() on empty range."); + return segments.back().end; } bool expiredAt(SlotIndex index) const { @@ -298,31 +332,23 @@ namespace llvm { return r != end() && r->start <= index; } - /// killedAt - Return true if a live range ends at index. Note that the kill - /// point is not contained in the half-open live range. It is usually the - /// getDefIndex() slot following its last use. - bool killedAt(SlotIndex index) const { - const_iterator r = find(index.getRegSlot(true)); - return r != end() && r->end == index; - } - - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); + /// Return the segment that contains the specified index, or null if there + /// is none. + const Segment *getSegmentContaining(SlotIndex Idx) const { + const_iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : &*I; } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - LiveRange *getLiveRangeContaining(SlotIndex Idx) { - iterator I = FindLiveRangeContaining(Idx); + /// Return the live segment that contains the specified index, or null if + /// there is none. + Segment *getSegmentContaining(SlotIndex Idx) { + iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : &*I; } /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. VNInfo *getVNInfoAt(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); + const_iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : I->valno; } @@ -330,76 +356,68 @@ namespace llvm { /// necessarilly including Idx, or NULL. Use this to find the reaching def /// used by an instruction at this SlotIndex position. VNInfo *getVNInfoBefore(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); + const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); return I == end() ? 0 : I->valno; } - /// FindLiveRangeContaining - Return an iterator to the live range that - /// contains the specified index, or end() if there is none. - iterator FindLiveRangeContaining(SlotIndex Idx) { + /// Return an iterator to the segment that contains the specified index, or + /// end() if there is none. + iterator FindSegmentContaining(SlotIndex Idx) { iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - const_iterator FindLiveRangeContaining(SlotIndex Idx) const { + const_iterator FindSegmentContaining(SlotIndex Idx) const { const_iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - /// overlaps - Return true if the intersection of the two live intervals is + /// overlaps - Return true if the intersection of the two live ranges is /// not empty. - bool overlaps(const LiveInterval& other) const { + bool overlaps(const LiveRange &other) const { if (other.empty()) return false; return overlapsFrom(other, other.begin()); } - /// overlaps - Return true if the two intervals have overlapping segments + /// overlaps - Return true if the two ranges have overlapping segments /// that are not coalescable according to CP. /// - /// Overlapping segments where one interval is defined by a coalescable + /// Overlapping segments where one range is defined by a coalescable /// copy are allowed. - bool overlaps(const LiveInterval &Other, const CoalescerPair &CP, + bool overlaps(const LiveRange &Other, const CoalescerPair &CP, const SlotIndexes&) const; - /// overlaps - Return true if the live interval overlaps a range specified + /// overlaps - Return true if the live range overlaps an interval specified /// by [Start, End). bool overlaps(SlotIndex Start, SlotIndex End) const; - /// overlapsFrom - Return true if the intersection of the two live intervals + /// overlapsFrom - Return true if the intersection of the two live ranges /// is not empty. The specified iterator is a hint that we can begin - /// scanning the Other interval starting at I. - bool overlapsFrom(const LiveInterval& other, const_iterator I) const; + /// scanning the Other range starting at I. + bool overlapsFrom(const LiveRange &Other, const_iterator I) const; - /// addRange - Add the specified LiveRange to this interval, merging - /// intervals as appropriate. This returns an iterator to the inserted live - /// range (which may have grown since it was inserted. - iterator addRange(LiveRange LR) { - return addRangeFrom(LR, ranges.begin()); + /// Add the specified Segment to this range, merging segments as + /// appropriate. This returns an iterator to the inserted segment (which + /// may have grown since it was inserted). + iterator addSegment(Segment S) { + return addSegmentFrom(S, segments.begin()); } - /// extendInBlock - If this interval is live before Kill in the basic block + /// extendInBlock - If this range is live before Kill in the basic block /// that starts at StartIdx, extend it to be live up to Kill, and return - /// the value. If there is no live range before Kill, return NULL. + /// the value. If there is no segment before Kill, return NULL. VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); - /// 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, + /// join - Join two live ranges (this, and other) together. This applies + /// mappings to the value numbers in the LHS/RHS ranges as specified. If + /// the ranges are not joinable, this aborts. + void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, - SmallVectorImpl<VNInfo *> &NewVNInfo, - MachineRegisterInfo *MRI); + SmallVectorImpl<VNInfo *> &NewVNInfo); - /// isInOneLiveRange - Return true if the range specified is entirely in the - /// a single LiveRange of the live interval. - bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { - const_iterator r = find(Start); - return r != end() && r->containsRange(Start, End); - } - - /// True iff this live range is a single segment that lies between the + /// True iff this segment is a single segment that lies between the /// specified boundaries, exclusively. Vregs live across a backedge are not /// considered local. The boundaries are expected to lie within an extended /// basic block, so vregs that are not live out should contain no holes. @@ -408,25 +426,63 @@ namespace llvm { endIndex() < End.getBoundaryIndex(); } - /// removeRange - Remove the specified range from this interval. Note that - /// the range must be a single LiveRange in its entirety. - void removeRange(SlotIndex Start, SlotIndex End, - bool RemoveDeadValNo = false); + /// Remove the specified segment from this range. Note that the segment + /// must be a single Segment in its entirety. + void removeSegment(SlotIndex Start, SlotIndex End, + bool RemoveDeadValNo = false); - void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { - removeRange(LR.start, LR.end, RemoveDeadValNo); + void removeSegment(Segment S, bool RemoveDeadValNo = false) { + removeSegment(S.start, S.end, RemoveDeadValNo); } - /// removeValNo - Remove all the ranges defined by the specified value#. + /// Query Liveness at Idx. + /// The sub-instruction slot of Idx doesn't matter, only the instruction + /// it refers to is considered. + LiveQueryResult Query(SlotIndex Idx) const { + // Find the segment that enters the instruction. + const_iterator I = find(Idx.getBaseIndex()); + const_iterator E = end(); + if (I == E) + return LiveQueryResult(0, 0, SlotIndex(), false); + + // Is this an instruction live-in segment? + // If Idx is the start index of a basic block, include live-in segments + // that start at Idx.getBaseIndex(). + VNInfo *EarlyVal = 0; + VNInfo *LateVal = 0; + SlotIndex EndPoint; + bool Kill = false; + if (I->start <= Idx.getBaseIndex()) { + EarlyVal = I->valno; + EndPoint = I->end; + // Move to the potentially live-out segment. + if (SlotIndex::isSameInstr(Idx, I->end)) { + Kill = true; + if (++I == E) + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + // Special case: A PHIDef value can have its def in the middle of a + // segment if the value happens to be live out of the layout + // predecessor. + // Such a value is not live-in. + if (EarlyVal->def == Idx.getBaseIndex()) + EarlyVal = 0; + } + // I now points to the segment that may be live-through, or defined by + // this instr. Ignore segments starting after the current instr. + if (!SlotIndex::isEarlierInstr(Idx, I->start)) { + LateVal = I->valno; + EndPoint = I->end; + } + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + + /// removeValNo - Remove all the segments defined by the specified value#. /// Also remove the value# from value# list. void removeValNo(VNInfo *ValNo); - /// getSize - Returns the sum of sizes of all the LiveRange's. - /// - unsigned getSize() const; - - /// Returns true if the live interval is zero length, i.e. no live ranges - /// span instructions. It doesn't pay to spill such an interval. + /// Returns true if the live range is zero length, i.e. no live segments + /// span instructions. It doesn't pay to spill such a range. bool isZeroLength(SlotIndexes *Indexes) const { for (const_iterator i = begin(), e = end(); i != e; ++i) if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < @@ -435,27 +491,16 @@ namespace llvm { return true; } - /// isSpillable - Can this interval be spilled? - bool isSpillable() const { - return weight != HUGE_VALF; - } - - /// markNotSpillable - Mark interval as not spillable - void markNotSpillable() { - weight = HUGE_VALF; - } - - bool operator<(const LiveInterval& other) const { + bool operator<(const LiveRange& other) const { const SlotIndex &thisIndex = beginIndex(); const SlotIndex &otherIndex = other.beginIndex(); - return (thisIndex < otherIndex || - (thisIndex == otherIndex && reg < other.reg)); + return thisIndex < otherIndex; } void print(raw_ostream &OS) const; void dump() const; - /// \brief Walk the interval and assert if any invariants fail to hold. + /// \brief Walk the range and assert if any invariants fail to hold. /// /// Note that this is a no-op when asserts are disabled. #ifdef NDEBUG @@ -466,11 +511,55 @@ namespace llvm { private: - Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); - void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); - Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); + iterator addSegmentFrom(Segment S, iterator From); + void extendSegmentEndTo(iterator I, SlotIndex NewEnd); + iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); void markValNoForDeletion(VNInfo *V); + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { + LR.print(OS); + return OS; + } + + /// LiveInterval - This class represents the liveness of a register, + /// or stack slot. + class LiveInterval : public LiveRange { + public: + typedef LiveRange super; + + const unsigned reg; // the register or stack slot of this interval. + float weight; // weight of this interval + + LiveInterval(unsigned Reg, float Weight) + : reg(Reg), weight(Weight) {} + + /// getSize - Returns the sum of sizes of all the LiveRange's. + /// + unsigned getSize() const; + + /// isSpillable - Can this interval be spilled? + bool isSpillable() const { + return weight != llvm::huge_valf; + } + + /// markNotSpillable - Mark interval as not spillable + void markNotSpillable() { + weight = llvm::huge_valf; + } + + bool operator<(const LiveInterval& other) const { + const SlotIndex &thisIndex = beginIndex(); + const SlotIndex &otherIndex = other.beginIndex(); + return thisIndex < otherIndex || + (thisIndex == otherIndex && reg < other.reg); + } + + void print(raw_ostream &OS) const; + void dump() const; + + private: LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; }; @@ -480,54 +569,65 @@ namespace llvm { return OS; } - /// Helper class for performant LiveInterval bulk updates. + raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); + + inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { + return V < S.start; + } + + inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { + return S.start < V; + } + + /// Helper class for performant LiveRange bulk updates. /// - /// Calling LiveInterval::addRange() repeatedly can be expensive on large + /// Calling LiveRange::addSegment() repeatedly can be expensive on large /// live ranges because segments after the insertion point may need to be /// shifted. The LiveRangeUpdater class can defer the shifting when adding /// many segments in order. /// - /// The LiveInterval will be in an invalid state until flush() is called. + /// The LiveRange will be in an invalid state until flush() is called. class LiveRangeUpdater { - LiveInterval *LI; + LiveRange *LR; SlotIndex LastStart; - LiveInterval::iterator WriteI; - LiveInterval::iterator ReadI; - SmallVector<LiveRange, 16> Spills; + LiveRange::iterator WriteI; + LiveRange::iterator ReadI; + SmallVector<LiveRange::Segment, 16> Spills; void mergeSpills(); public: - /// Create a LiveRangeUpdater for adding segments to LI. - /// LI will temporarily be in an invalid state until flush() is called. - LiveRangeUpdater(LiveInterval *li = 0) : LI(li) {} + /// Create a LiveRangeUpdater for adding segments to LR. + /// LR will temporarily be in an invalid state until flush() is called. + LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {} ~LiveRangeUpdater() { flush(); } - /// Add a segment to LI and coalesce when possible, just like LI.addRange(). - /// Segments should be added in increasing start order for best performance. - void add(LiveRange); + /// Add a segment to LR and coalesce when possible, just like + /// LR.addSegment(). Segments should be added in increasing start order for + /// best performance. + void add(LiveRange::Segment); void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { - add(LiveRange(Start, End, VNI)); + add(LiveRange::Segment(Start, End, VNI)); } - /// Return true if the LI is currently in an invalid state, and flush() + /// Return true if the LR is currently in an invalid state, and flush() /// needs to be called. bool isDirty() const { return LastStart.isValid(); } - /// Flush the updater state to LI so it is valid and contains all added + /// Flush the updater state to LR so it is valid and contains all added /// segments. void flush(); /// Select a different destination live range. - void setDest(LiveInterval *li) { - if (LI != li && isDirty()) + void setDest(LiveRange *lr) { + if (LR != lr && isDirty()) flush(); - LI = li; + LR = lr; } /// Get the current destination live range. - LiveInterval *getDest() const { return LI; } + LiveRange *getDest() const { return LR; } void dump() const; void print(raw_ostream&) const; @@ -538,99 +638,6 @@ namespace llvm { return OS; } - /// LiveRangeQuery - Query information about a live range around a given - /// instruction. This class hides the implementation details of live ranges, - /// and it should be used as the primary interface for examining live ranges - /// around instructions. - /// - class LiveRangeQuery { - VNInfo *EarlyVal; - VNInfo *LateVal; - SlotIndex EndPoint; - bool Kill; - - public: - /// Create a LiveRangeQuery for the given live range and instruction index. - /// The sub-instruction slot of Idx doesn't matter, only the instruction it - /// refers to is considered. - LiveRangeQuery(const LiveInterval &LI, SlotIndex Idx) - : EarlyVal(0), LateVal(0), Kill(false) { - // Find the segment that enters the instruction. - LiveInterval::const_iterator I = LI.find(Idx.getBaseIndex()); - LiveInterval::const_iterator E = LI.end(); - if (I == E) - return; - // Is this an instruction live-in segment? - // If Idx is the start index of a basic block, include live-in segments - // that start at Idx.getBaseIndex(). - if (I->start <= Idx.getBaseIndex()) { - EarlyVal = I->valno; - EndPoint = I->end; - // Move to the potentially live-out segment. - if (SlotIndex::isSameInstr(Idx, I->end)) { - Kill = true; - if (++I == E) - return; - } - // Special case: A PHIDef value can have its def in the middle of a - // segment if the value happens to be live out of the layout - // predecessor. - // Such a value is not live-in. - if (EarlyVal->def == Idx.getBaseIndex()) - EarlyVal = 0; - } - // I now points to the segment that may be live-through, or defined by - // this instr. Ignore segments starting after the current instr. - if (SlotIndex::isEarlierInstr(Idx, I->start)) - return; - LateVal = I->valno; - EndPoint = I->end; - } - - /// Return the value that is live-in to the instruction. This is the value - /// that will be read by the instruction's use operands. Return NULL if no - /// value is live-in. - VNInfo *valueIn() const { - return EarlyVal; - } - - /// Return true if the live-in value is killed by this instruction. This - /// means that either the live range ends at the instruction, or it changes - /// value. - bool isKill() const { - return Kill; - } - - /// Return true if this instruction has a dead def. - bool isDeadDef() const { - return EndPoint.isDead(); - } - - /// Return the value leaving the instruction, if any. This can be a - /// live-through value, or a live def. A dead def returns NULL. - VNInfo *valueOut() const { - return isDeadDef() ? 0 : LateVal; - } - - /// Return the value defined by this instruction, if any. This includes - /// dead defs, it is the value created by the instruction's def operands. - VNInfo *valueDefined() const { - return EarlyVal == LateVal ? 0 : LateVal; - } - - /// Return the end point of the last live range segment to interact with - /// the instruction, if any. - /// - /// The end point is an invalid SlotIndex only if the live range doesn't - /// intersect the instruction at all. - /// - /// The end point may be at or past the end of the instruction's basic - /// block. That means the value was live out of the block. - SlotIndex endPoint() const { - return EndPoint; - } - }; - /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a /// LiveInterval into equivalence clases of connected components. A /// LiveInterval that has multiple connected components can be broken into diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index ffb07a5..d8437f0 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -90,9 +90,9 @@ namespace llvm { /// block. SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks; - /// RegUnitIntervals - Keep a live interval for each register unit as a way - /// of tracking fixed physreg interference. - SmallVector<LiveInterval*, 0> RegUnitIntervals; + /// Keeps a live range set for each register unit to track fixed physreg + /// interference. + SmallVector<LiveRange*, 0> RegUnitRanges; public: static char ID; // Pass identification, replacement for typeid @@ -103,9 +103,10 @@ namespace llvm { static float getSpillWeight(bool isDef, bool isUse, BlockFrequency freq); LiveInterval &getInterval(unsigned Reg) { - LiveInterval *LI = VirtRegIntervals[Reg]; - assert(LI && "Interval does not exist for virtual register"); - return *LI; + if (hasInterval(Reg)) + return *VirtRegIntervals[Reg]; + else + return createAndComputeVirtRegInterval(Reg); } const LiveInterval &getInterval(unsigned Reg) const { @@ -117,12 +118,17 @@ namespace llvm { } // Interval creation. - LiveInterval &getOrCreateInterval(unsigned Reg) { - if (!hasInterval(Reg)) { - VirtRegIntervals.grow(Reg); - VirtRegIntervals[Reg] = createInterval(Reg); - } - return getInterval(Reg); + LiveInterval &createEmptyInterval(unsigned Reg) { + assert(!hasInterval(Reg) && "Interval already exists!"); + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + return *VirtRegIntervals[Reg]; + } + + LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { + LiveInterval &LI = createEmptyInterval(Reg); + computeVirtRegInterval(LI); + return LI; } // Interval removal. @@ -131,10 +137,10 @@ namespace llvm { VirtRegIntervals[Reg] = 0; } - /// addLiveRangeToEndOfBlock - Given a register and an instruction, - /// adds a live range from that instruction to the end of its MBB. - LiveRange addLiveRangeToEndOfBlock(unsigned reg, - MachineInstr* startInst); + /// Given a register and an instruction, adds a live segment from that + /// instruction to the end of its MBB. + LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, + MachineInstr* startInst); /// shrinkToUses - After removing some uses of a register, shrink its live /// range to just the remaining uses. This method does not compute reaching @@ -154,7 +160,7 @@ namespace llvm { /// extended to be live out of the basic block. /// /// See also LiveRangeCalc::extend(). - void extendToIndices(LiveInterval *LI, ArrayRef<SlotIndex> Indices); + void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices); /// pruneValue - If an LI value is live at Kill, prune its live range by /// removing any liveness reachable from Kill. Add live range end points to @@ -200,14 +206,14 @@ namespace llvm { return Indexes->getMBBEndIdx(mbb); } - bool isLiveInToMBB(const LiveInterval &li, + bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBStartIdx(mbb)); + return LR.liveAt(getMBBStartIdx(mbb)); } - bool isLiveOutOfMBB(const LiveInterval &li, + bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); + return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); } MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { @@ -225,6 +231,12 @@ namespace llvm { return Indexes->insertMachineInstrInMaps(MI); } + void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) { + for (MachineBasicBlock::iterator I = B; I != E; ++I) + Indexes->insertMachineInstrInMaps(I); + } + void RemoveMachineInstrFromMaps(MachineInstr *MI) { Indexes->removeMachineInstrFromMaps(MI); } @@ -352,24 +364,24 @@ namespace llvm { /// getRegUnit - Return the live range for Unit. /// It will be computed if it doesn't exist. - LiveInterval &getRegUnit(unsigned Unit) { - LiveInterval *LI = RegUnitIntervals[Unit]; - if (!LI) { + LiveRange &getRegUnit(unsigned Unit) { + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { // Compute missing ranges on demand. - RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); - computeRegUnitInterval(LI); + RegUnitRanges[Unit] = LR = new LiveRange(); + computeRegUnitRange(*LR, Unit); } - return *LI; + return *LR; } /// getCachedRegUnit - Return the live range for Unit if it has already /// been computed, or NULL if it hasn't been computed yet. - LiveInterval *getCachedRegUnit(unsigned Unit) { - return RegUnitIntervals[Unit]; + LiveRange *getCachedRegUnit(unsigned Unit) { + return RegUnitRanges[Unit]; } - const LiveInterval *getCachedRegUnit(unsigned Unit) const { - return RegUnitIntervals[Unit]; + const LiveRange *getCachedRegUnit(unsigned Unit) const { + return RegUnitRanges[Unit]; } private: @@ -385,8 +397,8 @@ namespace llvm { void dumpInstrs() const; void computeLiveInRegUnits(); - void computeRegUnitInterval(LiveInterval*); - void computeVirtRegInterval(LiveInterval*); + void computeRegUnitRange(LiveRange&, unsigned Unit); + void computeVirtRegInterval(LiveInterval&); class HMEditor; }; diff --git a/include/llvm/CodeGen/LiveIntervalUnion.h b/include/llvm/CodeGen/LiveIntervalUnion.h index 615b339..95933d1 100644 --- a/include/llvm/CodeGen/LiveIntervalUnion.h +++ b/include/llvm/CodeGen/LiveIntervalUnion.h @@ -32,7 +32,7 @@ typedef SparseBitVector<128> LiveVirtRegBitSet; /// Compare a live virtual register segment to a LiveIntervalUnion segment. inline bool -overlap(const LiveRange &VRSeg, +overlap(const LiveInterval::Segment &VRSeg, const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; } diff --git a/include/llvm/CodeGen/LiveRangeEdit.h b/include/llvm/CodeGen/LiveRangeEdit.h index a8749da..7edf67c 100644 --- a/include/llvm/CodeGen/LiveRangeEdit.h +++ b/include/llvm/CodeGen/LiveRangeEdit.h @@ -22,6 +22,7 @@ #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Target/TargetMachine.h" namespace llvm { @@ -30,10 +31,9 @@ class AliasAnalysis; class LiveIntervals; class MachineBlockFrequencyInfo; class MachineLoopInfo; -class MachineRegisterInfo; class VirtRegMap; -class LiveRangeEdit { +class LiveRangeEdit : private MachineRegisterInfo::Delegate { public: /// Callback methods for LiveRangeEdit owners. class Delegate { @@ -58,7 +58,7 @@ public: private: LiveInterval *Parent; - SmallVectorImpl<LiveInterval*> &NewRegs; + SmallVectorImpl<unsigned> &NewRegs; MachineRegisterInfo &MRI; LiveIntervals &LIS; VirtRegMap *VRM; @@ -97,6 +97,10 @@ private: /// Helper for eliminateDeadDefs. void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink); + /// MachineRegisterInfo callback to notify when new virtual + /// registers are created. + void MRI_NoteNewVirtualRegister(unsigned VReg); + public: /// Create a LiveRangeEdit for breaking down parent into smaller pieces. /// @param parent The register being spilled or split. @@ -108,7 +112,7 @@ public: /// function. If NULL, no virtual register map updates will /// be done. This could be the case if called before Regalloc. LiveRangeEdit(LiveInterval *parent, - SmallVectorImpl<LiveInterval*> &newRegs, + SmallVectorImpl<unsigned> &newRegs, MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, @@ -118,7 +122,9 @@ public: TII(*MF.getTarget().getInstrInfo()), TheDelegate(delegate), FirstNew(newRegs.size()), - ScannedRemattable(false) {} + ScannedRemattable(false) { MRI.setDelegate(this); } + + ~LiveRangeEdit() { MRI.resetDelegate(this); } LiveInterval &getParent() const { assert(Parent && "No parent LiveInterval"); @@ -127,23 +133,30 @@ public: unsigned getReg() const { return getParent().reg; } /// Iterator for accessing the new registers added by this edit. - typedef SmallVectorImpl<LiveInterval*>::const_iterator iterator; + typedef SmallVectorImpl<unsigned>::const_iterator iterator; iterator begin() const { return NewRegs.begin()+FirstNew; } iterator end() const { return NewRegs.end(); } unsigned size() const { return NewRegs.size()-FirstNew; } bool empty() const { return size() == 0; } - LiveInterval *get(unsigned idx) const { return NewRegs[idx+FirstNew]; } + unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } - ArrayRef<LiveInterval*> regs() const { + ArrayRef<unsigned> regs() const { return makeArrayRef(NewRegs).slice(FirstNew); } + /// createEmptyIntervalFrom - Create a new empty interval based on OldReg. + LiveInterval &createEmptyIntervalFrom(unsigned OldReg); + /// createFrom - Create a new virtual register based on OldReg. - LiveInterval &createFrom(unsigned OldReg); + unsigned createFrom(unsigned OldReg); /// create - Create a new register with the same class and original slot as /// parent. - LiveInterval &create() { + LiveInterval &createEmptyInterval() { + return createEmptyIntervalFrom(getReg()); + } + + unsigned create() { return createFrom(getReg()); } diff --git a/include/llvm/CodeGen/LiveRegUnits.h b/include/llvm/CodeGen/LiveRegUnits.h new file mode 100644 index 0000000..02b9c55 --- /dev/null +++ b/include/llvm/CodeGen/LiveRegUnits.h @@ -0,0 +1,88 @@ +//===-- llvm/CodeGen/LiveRegUnits.h - Live register unit set ----*- 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 a Set of live register units. This can be used for ad +// hoc liveness tracking after register allocation. You can start with the +// live-ins/live-outs at the beginning/end of a block and update the information +// while walking the instructions inside the block. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEREGUNITS_H +#define LLVM_CODEGEN_LIVEREGUNITS_H + +#include "llvm/ADT/SparseSet.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include <cassert> + +namespace llvm { + +class MachineInstr; + +/// A set of live register units with functions to track liveness when walking +/// backward/forward through a basic block. +class LiveRegUnits { + SparseSet<unsigned> LiveUnits; + + LiveRegUnits(const LiveRegUnits&) LLVM_DELETED_FUNCTION; + LiveRegUnits &operator=(const LiveRegUnits&) LLVM_DELETED_FUNCTION; +public: + /// \brief Constructs a new empty LiveRegUnits set. + LiveRegUnits() {} + + void init(const TargetRegisterInfo *TRI) { + LiveUnits.clear(); + LiveUnits.setUniverse(TRI->getNumRegs()); + } + + void clear() { LiveUnits.clear(); } + + bool empty() const { return LiveUnits.empty(); } + + /// \brief Adds a register to the set. + void addReg(unsigned Reg, const MCRegisterInfo &MCRI) { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) + LiveUnits.insert(*RUnits); + } + + /// \brief Removes a register from the set. + void removeReg(unsigned Reg, const MCRegisterInfo &MCRI) { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) + LiveUnits.erase(*RUnits); + } + + /// \brief Removes registers clobbered by the regmask operand @p Op. + void removeRegsInMask(const MachineOperand &Op, const MCRegisterInfo &MCRI); + + /// \brief Returns true if register @p Reg (or one of its super register) is + /// contained in the set. + bool contains(unsigned Reg, const MCRegisterInfo &MCRI) const { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) { + if (LiveUnits.count(*RUnits)) + return true; + } + return false; + } + + /// \brief Simulates liveness when stepping backwards over an + /// instruction(bundle): Remove Defs, add uses. + void stepBackward(const MachineInstr &MI, const MCRegisterInfo &MCRI); + + /// \brief Simulates liveness when stepping forward over an + /// instruction(bundle): Remove killed-uses, add defs. + void stepForward(const MachineInstr &MI, const MCRegisterInfo &MCRI); + + /// \brief Adds all registers in the live-in list of block @p BB. + void addLiveIns(const MachineBasicBlock *MBB, const MCRegisterInfo &MCRI); +}; + +} // namespace llvm + +#endif diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index d6f5883..7717809 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -410,8 +410,8 @@ public: /// branch to do so (e.g., a table jump). True is a conservative answer. bool canFallThrough(); - /// Returns a pointer to the first instructon in this block that is not a - /// PHINode instruction. When adding instruction to the beginning of the + /// Returns a pointer to the first instruction in this block that is not a + /// PHINode instruction. When adding instructions to the beginning of the /// basic block, they should be added before the returned value, not before /// the first instruction, which might be PHI. /// Returns end() is there's no non-PHI instruction. @@ -733,6 +733,31 @@ template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { } }; + + +/// MachineInstrSpan provides an interface to get an iteration range +/// containing the instruction it was initialized with, along with all +/// those instructions inserted prior to or following that instruction +/// at some point after the MachineInstrSpan is constructed. +class MachineInstrSpan { + MachineBasicBlock &MBB; + MachineBasicBlock::iterator I, B, E; +public: + MachineInstrSpan(MachineBasicBlock::iterator I) + : MBB(*I->getParent()), + I(I), + B(I == MBB.begin() ? MBB.end() : llvm::prior(I)), + E(llvm::next(I)) {} + + MachineBasicBlock::iterator begin() { + return B == MBB.end() ? MBB.begin() : llvm::next(B); + } + MachineBasicBlock::iterator end() { return E; } + bool empty() { return begin() == end(); } + + MachineBasicBlock::iterator getInitial() { return I; } +}; + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 98dd03b..c59948f 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -1,4 +1,4 @@ -//==- MachineBranchProbabilityInfo.h - Machine Branch Probability Analysis -==// +//=- MachineBranchProbabilityInfo.h - Branch Probability Analysis -*- C++ -*-=// // // The LLVM Compiler Infrastructure // diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index cf5e7e2..cccab81 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -397,8 +397,8 @@ public: return isBranch(Type) & isBarrier(Type) & !isIndirectBranch(Type); } - // isPredicable - Return true if this instruction has a predicate operand that - // controls execution. It may be set to 'always', or may be set to other + /// Return true if this instruction has a predicate operand that + /// controls execution. It may be set to 'always', or may be set to other /// values. There are various methods in TargetInstrInfo that can be used to /// control and modify the predicate in this instruction. bool isPredicable(QueryType Type = AllInBundle) const { @@ -637,6 +637,13 @@ public: bool isEHLabel() const { return getOpcode() == TargetOpcode::EH_LABEL; } bool isGCLabel() const { return getOpcode() == TargetOpcode::GC_LABEL; } bool isDebugValue() const { return getOpcode() == TargetOpcode::DBG_VALUE; } + /// A DBG_VALUE is indirect iff the first operand is a register and + /// the second operand is an immediate. + bool isIndirectDebugValue() const { + return isDebugValue() + && getOperand(0).isReg() + && getOperand(1).isImm(); + } bool isPHI() const { return getOpcode() == TargetOpcode::PHI; } bool isKill() const { return getOpcode() == TargetOpcode::KILL; } @@ -886,13 +893,12 @@ public: /// Look for the operand that defines it and mark it as IsDead. If /// AddIfNotFound is true, add a implicit operand if it's not found. Returns /// true if the operand exists / is added. - bool addRegisterDead(unsigned IncomingReg, const TargetRegisterInfo *RegInfo, + bool addRegisterDead(unsigned Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound = false); /// addRegisterDefined - We have determined MI defines a register. Make sure /// there is an operand defining Reg. - void addRegisterDefined(unsigned IncomingReg, - const TargetRegisterInfo *RegInfo = 0); + void addRegisterDefined(unsigned Reg, const TargetRegisterInfo *RegInfo = 0); /// setPhysRegsDeadExcept - Mark every physreg used by this instruction as /// dead except those in the UsedRegs list. diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index 186017c..460c08c 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -234,7 +234,7 @@ public: /// \brief Returns a reference to a list of cfi instructions in the current /// function's prologue. Used to construct frame maps for debug and exception /// handling comsumers. - const std::vector<MCCFIInstruction> &getFrameInstructions() { + const std::vector<MCCFIInstruction> &getFrameInstructions() const { return FrameInstructions; } diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index 57b28fe..40f3580 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -564,6 +564,8 @@ public: unsigned SubReg = 0, bool isDebug = false, bool isInternalRead = false) { + assert(!(isDead && !isDef) && "Dead flag on non-def"); + assert(!(isKill && isDef) && "Kill flag on def"); MachineOperand Op(MachineOperand::MO_Register); Op.IsDef = isDef; Op.IsImp = isImp; diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index 7a6dcd0..58ca907 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -22,12 +22,24 @@ #include <vector> namespace llvm { +class PSetIterator; /// MachineRegisterInfo - Keep track of information for virtual and physical /// registers, including vreg register classes, use/def chains for registers, /// etc. class MachineRegisterInfo { +public: + class Delegate { + virtual void anchor(); + public: + virtual void MRI_NoteNewVirtualRegister(unsigned Reg) = 0; + + virtual ~Delegate() {} + }; + +private: const TargetMachine &TM; + Delegate *TheDelegate; /// IsSSA - True when the machine function is in SSA form and virtual /// registers have a single def. @@ -116,6 +128,23 @@ public: return TM.getRegisterInfo(); } + void resetDelegate(Delegate *delegate) { + // Ensure another delegate does not take over unless the current + // delegate first unattaches itself. If we ever need to multicast + // notifications, we will need to change to using a list. + assert(TheDelegate == delegate && + "Only the current delegate can perform reset!"); + TheDelegate = 0; + } + + void setDelegate(Delegate *delegate) { + assert(delegate && !TheDelegate && + "Attempted to set delegate to null, or to change it without " + "first resetting it!"); + + TheDelegate = delegate; + } + //===--------------------------------------------------------------------===// // Function State //===--------------------------------------------------------------------===// @@ -299,6 +328,11 @@ public: /// a physreg. bool isConstantPhysReg(unsigned PhysReg, const MachineFunction &MF) const; + /// Get an iterator over the pressure sets affected by the given physical or + /// virtual register. If RegUnit is physical, it must be a register unit (from + /// MCRegUnitIterator). + PSetIterator getPressureSets(unsigned RegUnit) const; + //===--------------------------------------------------------------------===// // Virtual Register Info //===--------------------------------------------------------------------===// @@ -620,9 +654,49 @@ public: return Op->getParent(); } }; +}; + +/// Iterate over the pressure sets affected by the given physical or virtual +/// register. If Reg is physical, it must be a register unit (from +/// MCRegUnitIterator). +class PSetIterator { + const int *PSet; + unsigned Weight; +public: + PSetIterator(): PSet(0), Weight(0) {} + PSetIterator(unsigned RegUnit, const MachineRegisterInfo *MRI) { + const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); + if (TargetRegisterInfo::isVirtualRegister(RegUnit)) { + const TargetRegisterClass *RC = MRI->getRegClass(RegUnit); + PSet = TRI->getRegClassPressureSets(RC); + Weight = TRI->getRegClassWeight(RC).RegWeight; + } + else { + PSet = TRI->getRegUnitPressureSets(RegUnit); + Weight = TRI->getRegUnitWeight(RegUnit); + } + if (*PSet == -1) + PSet = 0; + } + bool isValid() const { return PSet; } + + unsigned getWeight() const { return Weight; } + + unsigned operator*() const { return *PSet; } + void operator++() { + assert(isValid() && "Invalid PSetIterator."); + ++PSet; + if (*PSet == -1) + PSet = 0; + } }; +inline PSetIterator MachineRegisterInfo:: +getPressureSets(unsigned RegUnit) const { + return PSetIterator(RegUnit, this); +} + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h index 244b466..e778457 100644 --- a/include/llvm/CodeGen/MachineRelocation.h +++ b/include/llvm/CodeGen/MachineRelocation.h @@ -57,7 +57,7 @@ class MachineRelocation { union { void *Result; // If this has been resolved to a resolved pointer GlobalValue *GV; // If this is a pointer to a GV or an indirect ref. - MachineBasicBlock *MBB; // If this is a pointer to a LLVM BB + MachineBasicBlock *MBB; // If this is a pointer to an LLVM BB const char *ExtSym; // If this is a pointer to a named symbol unsigned Index; // Constant pool / jump table index unsigned GOTIndex; // Index in the GOT of this symbol/global diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index d110ea1..7782895 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -7,8 +7,48 @@ // //===----------------------------------------------------------------------===// // -// This file provides a MachineSchedRegistry for registering alternative machine -// schedulers. A Target may provide an alternative scheduler implementation by +// This file provides an interface for customizing the standard MachineScheduler +// pass. Note that the entire pass may be replaced as follows: +// +// <Target>TargetMachine::createPassConfig(PassManagerBase &PM) { +// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); +// ...} +// +// The MachineScheduler pass is only responsible for choosing the regions to be +// scheduled. Targets can override the DAG builder and scheduler without +// replacing the pass as follows: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new CustomMachineScheduler(C); +// } +// +// The default scheduler, ScheduleDAGMI, builds the DAG and drives list +// scheduling while updating the instruction stream, register pressure, and live +// intervals. Most targets don't need to override the DAG builder and list +// schedulier, but subtargets that require custom scheduling heuristics may +// plugin an alternate MachineSchedStrategy. The strategy is responsible for +// selecting the highest priority node from the list: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new ScheduleDAGMI(C, CustomStrategy(C)); +// } +// +// The DAG builder can also be customized in a sense by adding DAG mutations +// that will run after DAG building and before list scheduling. DAG mutations +// can adjust dependencies based on target-specific knowledge or add weak edges +// to aid heuristics: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C)); +// DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI)); +// return DAG; +// } +// +// A target that supports alternative schedulers can use the +// MachineSchedRegistry to allow command line selection. This can be done by // implementing the following boilerplate: // // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { @@ -18,9 +58,19 @@ // SchedCustomRegistry("custom", "Run my target's custom scheduler", // createCustomMachineSched); // -// Inside <Target>PassConfig: -// enablePass(&MachineSchedulerID); -// MachineSchedRegistry::setDefault(createCustomMachineSched); +// +// Finally, subtargets that don't need to implement custom heuristics but would +// like to configure the GenericScheduler's policy for a given scheduler region, +// including scheduling direction and register pressure tracking policy, can do +// this: +// +// void <SubTarget>Subtarget:: +// overrideSchedPolicy(MachineSchedPolicy &Policy, +// MachineInstr *begin, +// MachineInstr *end, +// unsigned NumRegionInstrs) const { +// Policy.<Flag> = true; +// } // //===----------------------------------------------------------------------===// @@ -85,15 +135,6 @@ public: static MachineSchedRegistry *getList() { return (MachineSchedRegistry *)Registry.getList(); } - static ScheduleDAGCtor getDefault() { - return (ScheduleDAGCtor)Registry.getDefault(); - } - static void setDefault(ScheduleDAGCtor C) { - Registry.setDefault((MachinePassCtor)C); - } - static void setDefault(StringRef Name) { - Registry.setDefault(Name); - } static void setListener(MachinePassRegistryListener *L) { Registry.setListener(L); } @@ -101,12 +142,41 @@ public: class ScheduleDAGMI; +/// Define a generic scheduling policy for targets that don't provide their own +/// MachineSchedStrategy. This can be overriden for each scheduling region +/// before building the DAG. +struct MachineSchedPolicy { + // Allow the scheduler to disable register pressure tracking. + bool ShouldTrackPressure; + + // Allow the scheduler to force top-down or bottom-up scheduling. If neither + // is true, the scheduler runs in both directions and converges. + bool OnlyTopDown; + bool OnlyBottomUp; + + MachineSchedPolicy(): + ShouldTrackPressure(false), OnlyTopDown(false), OnlyBottomUp(false) {} +}; + /// MachineSchedStrategy - Interface to the scheduling algorithm used by /// ScheduleDAGMI. +/// +/// Initialization sequence: +/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots class MachineSchedStrategy { + virtual void anchor(); public: virtual ~MachineSchedStrategy() {} + /// Optionally override the per-region scheduling policy. + virtual void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) {} + + /// Check if pressure tracking is needed before building the DAG and + /// initializing this strategy. Called after initPolicy. + virtual bool shouldTrackPressure() const { return true; } + /// Initialize the strategy after building the DAG for a new region. virtual void initialize(ScheduleDAGMI *DAG) = 0; @@ -193,6 +263,7 @@ public: /// Mutate the DAG as a postpass after normal DAG building. class ScheduleDAGMutation { + virtual void anchor(); public: virtual ~ScheduleDAGMutation() {} @@ -221,14 +292,20 @@ protected: MachineBasicBlock::iterator LiveRegionEnd; - /// Register pressure in this region computed by buildSchedGraph. + // Map each SU to its summary of pressure changes. This array is updated for + // liveness during bottom-up scheduling. Top-down scheduling may proceed but + // has no affect on the pressure diffs. + PressureDiffs SUPressureDiffs; + + /// Register pressure in this region computed by initRegPressure. + bool ShouldTrackPressure; IntervalPressure RegPressure; RegPressureTracker RPTracker; /// List of pressure sets that exceed the target's pressure limit before /// scheduling, listed in increasing set ID order. Each pressure set is paired /// with its max pressure in the currently scheduled regions. - std::vector<PressureElement> RegionCriticalPSets; + std::vector<PressureChange> RegionCriticalPSets; /// The top of the unscheduled zone. MachineBasicBlock::iterator CurrentTop; @@ -254,8 +331,9 @@ public: ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), - Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), - TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), + Topo(SUnits, &ExitSU), ShouldTrackPressure(false), + RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), + CurrentBottom(), BotRPTracker(BotPressure), NextClusterPred(NULL), NextClusterSucc(NULL) { #ifndef NDEBUG NumInstrsScheduled = 0; @@ -264,6 +342,9 @@ public: virtual ~ScheduleDAGMI(); + /// \brief Return true if register pressure tracking is enabled. + bool isTrackingPressure() const { return ShouldTrackPressure; } + /// Add a postprocessing step to the DAG builder. /// Mutations are applied in the order that they are added after normal DAG /// building and before MachineSchedStrategy initialization. @@ -293,8 +374,7 @@ public: void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); - + unsigned regioninstrs) LLVM_OVERRIDE; /// Implement ScheduleDAGInstrs interface for scheduling a sequence of /// reorderable instructions. @@ -315,10 +395,14 @@ public: /// Get register pressure for the entire scheduling region before scheduling. const IntervalPressure &getRegPressure() const { return RegPressure; } - const std::vector<PressureElement> &getRegionCriticalPSets() const { + const std::vector<PressureChange> &getRegionCriticalPSets() const { return RegionCriticalPSets; } + PressureDiff &getPressureDiff(const SUnit *SU) { + return SUPressureDiffs[SU->NodeNum]; + } + const SUnit *getNextClusterPred() const { return NextClusterPred; } const SUnit *getNextClusterSucc() const { return NextClusterSucc; } @@ -332,6 +416,9 @@ public: BitVector &getScheduledTrees() { return ScheduledTrees; } + /// Compute the cyclic critical path through the DAG. + unsigned computeCyclicCriticalPath(); + void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; void viewGraph() LLVM_OVERRIDE; @@ -367,7 +454,10 @@ protected: void initRegPressure(); - void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); + void updatePressureDiffs(ArrayRef<unsigned> LiveUses); + + void updateScheduledPressure(const SUnit *SU, + const std::vector<unsigned> &NewMaxPressure); bool checkSchedLimit(); diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index b57abca..aca0a91 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -20,79 +20,63 @@ #include "llvm/ADT/ilist_node.h" #include <list> #include <map> +#include <set> namespace PBQP { /// PBQP Graph class. /// Instances of this class describe PBQP problems. class Graph { - private: - - // ----- TYPEDEFS ----- - class NodeEntry; - class EdgeEntry; - - typedef llvm::ilist<NodeEntry> NodeList; - typedef llvm::ilist<EdgeEntry> EdgeList; - public: - typedef NodeList::iterator NodeItr; - typedef NodeList::const_iterator ConstNodeItr; - - typedef EdgeList::iterator EdgeItr; - typedef EdgeList::const_iterator ConstEdgeItr; + typedef unsigned NodeId; + typedef unsigned EdgeId; private: - typedef std::list<EdgeItr> AdjEdgeList; - + typedef std::set<NodeId> AdjEdgeList; + public: typedef AdjEdgeList::iterator AdjEdgeItr; private: - class NodeEntry : public llvm::ilist_node<NodeEntry> { - friend struct llvm::ilist_sentinel_traits<NodeEntry>; + class NodeEntry { private: - Vector costs; + Vector costs; AdjEdgeList adjEdges; - unsigned degree; void *data; NodeEntry() : costs(0, 0) {} public: - NodeEntry(const Vector &costs) : costs(costs), degree(0) {} + NodeEntry(const Vector &costs) : costs(costs), data(0) {} Vector& getCosts() { return costs; } const Vector& getCosts() const { return costs; } - unsigned getDegree() const { return degree; } + unsigned getDegree() const { return adjEdges.size(); } AdjEdgeItr edgesBegin() { return adjEdges.begin(); } AdjEdgeItr edgesEnd() { return adjEdges.end(); } - AdjEdgeItr addEdge(EdgeItr e) { - ++degree; + AdjEdgeItr addEdge(EdgeId e) { return adjEdges.insert(adjEdges.end(), e); } void removeEdge(AdjEdgeItr ae) { - --degree; adjEdges.erase(ae); } void setData(void *data) { this->data = data; } void* getData() { return data; } }; - class EdgeEntry : public llvm::ilist_node<EdgeEntry> { - friend struct llvm::ilist_sentinel_traits<EdgeEntry>; + class EdgeEntry { private: - NodeItr node1, node2; + NodeId node1, node2; Matrix costs; AdjEdgeItr node1AEItr, node2AEItr; void *data; - EdgeEntry() : costs(0, 0, 0) {} + EdgeEntry() : costs(0, 0, 0), data(0) {} public: - EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) + EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs) : node1(node1), node2(node2), costs(costs) {} - NodeItr getNode1() const { return node1; } - NodeItr getNode2() const { return node2; } + NodeId getNode1() const { return node1; } + NodeId getNode2() const { return node2; } Matrix& getCosts() { return costs; } const Matrix& getCosts() const { return costs; } void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } @@ -105,254 +89,305 @@ namespace PBQP { // ----- MEMBERS ----- - NodeList nodes; - unsigned numNodes; + typedef std::vector<NodeEntry> NodeVector; + typedef std::vector<NodeId> FreeNodeVector; + NodeVector nodes; + FreeNodeVector freeNodes; - EdgeList edges; - unsigned numEdges; + typedef std::vector<EdgeEntry> EdgeVector; + typedef std::vector<EdgeId> FreeEdgeVector; + EdgeVector edges; + FreeEdgeVector freeEdges; // ----- INTERNAL METHODS ----- - NodeEntry& getNode(NodeItr nItr) { return *nItr; } - const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; } - - EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; } - const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; } - - NodeItr addConstructedNode(const NodeEntry &n) { - ++numNodes; - return nodes.insert(nodes.end(), n); + NodeEntry& getNode(NodeId nId) { return nodes[nId]; } + const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; } + + EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; } + const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; } + + NodeId addConstructedNode(const NodeEntry &n) { + NodeId nodeId = 0; + if (!freeNodes.empty()) { + nodeId = freeNodes.back(); + freeNodes.pop_back(); + nodes[nodeId] = n; + } else { + nodeId = nodes.size(); + nodes.push_back(n); + } + return nodeId; } - EdgeItr addConstructedEdge(const EdgeEntry &e) { - assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && + EdgeId addConstructedEdge(const EdgeEntry &e) { + assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() && "Attempt to add duplicate edge."); - ++numEdges; - EdgeItr edgeItr = edges.insert(edges.end(), e); - EdgeEntry &ne = getEdge(edgeItr); + EdgeId edgeId = 0; + if (!freeEdges.empty()) { + edgeId = freeEdges.back(); + freeEdges.pop_back(); + edges[edgeId] = e; + } else { + edgeId = edges.size(); + edges.push_back(e); + } + + EdgeEntry &ne = getEdge(edgeId); NodeEntry &n1 = getNode(ne.getNode1()); NodeEntry &n2 = getNode(ne.getNode2()); + // Sanity check on matrix dimensions: assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && (n2.getCosts().getLength() == ne.getCosts().getCols()) && "Edge cost dimensions do not match node costs dimensions."); - ne.setNode1AEItr(n1.addEdge(edgeItr)); - ne.setNode2AEItr(n2.addEdge(edgeItr)); - return edgeItr; + + ne.setNode1AEItr(n1.addEdge(edgeId)); + ne.setNode2AEItr(n2.addEdge(edgeId)); + return edgeId; } - inline void copyFrom(const Graph &other); + Graph(const Graph &other) {} + void operator=(const Graph &other) {} + public: - /// \brief Construct an empty PBQP graph. - Graph() : numNodes(0), numEdges(0) {} + class NodeItr { + public: + NodeItr(NodeId nodeId, const Graph &g) + : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) { + this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId + } - /// \brief Copy construct this graph from "other". Note: Does not copy node - /// and edge data, only graph structure and costs. - /// @param other Source graph to copy from. - Graph(const Graph &other) : numNodes(0), numEdges(0) { - copyFrom(other); - } + bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; } + bool operator!=(const NodeItr& n) const { return !(*this == n); } + NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; } + NodeId operator*() const { return nodeId; } - /// \brief Make this graph a copy of "other". Note: Does not copy node and - /// edge data, only graph structure and costs. - /// @param other The graph to copy from. - /// @return A reference to this graph. - /// - /// This will clear the current graph, erasing any nodes and edges added, - /// before copying from other. - Graph& operator=(const Graph &other) { - clear(); - copyFrom(other); - return *this; - } + private: + NodeId findNextInUse(NodeId n) const { + while (n < endNodeId && + std::find(freeNodes.begin(), freeNodes.end(), n) != + freeNodes.end()) { + ++n; + } + return n; + } + + NodeId nodeId, endNodeId; + const FreeNodeVector& freeNodes; + }; + + class EdgeItr { + public: + EdgeItr(EdgeId edgeId, const Graph &g) + : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) { + this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId + } + + bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; } + bool operator!=(const EdgeItr& n) const { return !(*this == n); } + EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; } + EdgeId operator*() const { return edgeId; } + + private: + EdgeId findNextInUse(EdgeId n) const { + while (n < endEdgeId && + std::find(freeEdges.begin(), freeEdges.end(), n) != + freeEdges.end()) { + ++n; + } + return n; + } + + EdgeId edgeId, endEdgeId; + const FreeEdgeVector& freeEdges; + }; + + /// \brief Construct an empty PBQP graph. + Graph() {} /// \brief Add a node with the given costs. /// @param costs Cost vector for the new node. /// @return Node iterator for the added node. - NodeItr addNode(const Vector &costs) { + NodeId addNode(const Vector &costs) { return addConstructedNode(NodeEntry(costs)); } /// \brief Add an edge between the given nodes with the given costs. - /// @param n1Itr First node. - /// @param n2Itr Second node. + /// @param n1Id First node. + /// @param n2Id Second node. /// @return Edge iterator for the added edge. - EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, - const Matrix &costs) { - assert(getNodeCosts(n1Itr).getLength() == costs.getRows() && - getNodeCosts(n2Itr).getLength() == costs.getCols() && + EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) { + assert(getNodeCosts(n1Id).getLength() == costs.getRows() && + getNodeCosts(n2Id).getLength() == costs.getCols() && "Matrix dimensions mismatch."); - return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); + return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); } /// \brief Get the number of nodes in the graph. /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return numNodes; } + unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); } /// \brief Get the number of edges in the graph. /// @return Number of edges in the graph. - unsigned getNumEdges() const { return numEdges; } + unsigned getNumEdges() const { return edges.size() - freeEdges.size(); } /// \brief Get a node's cost vector. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } + Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); } /// \brief Get a node's cost vector (const version). - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - const Vector& getNodeCosts(ConstNodeItr nItr) const { - return getNode(nItr).getCosts(); + const Vector& getNodeCosts(NodeId nId) const { + return getNode(nId).getCosts(); } /// \brief Set a node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @param data Pointer to node data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); } + void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); } /// \brief Get the node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Pointer to node data. - void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } - + void* getNodeData(NodeId nId) { return getNode(nId).getData(); } + /// \brief Get an edge's cost matrix. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } + Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); } /// \brief Get an edge's cost matrix (const version). - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { - return getEdge(eItr).getCosts(); + const Matrix& getEdgeCosts(EdgeId eId) const { + return getEdge(eId).getCosts(); } /// \brief Set an edge's data pointer. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @param data Pointer to edge data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); } + void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); } /// \brief Get an edge's data pointer. - /// @param eItr Edge iterator. - /// @return Pointer to edge data. - void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } + /// @param eId Edge id. + /// @return Pointer to edge data. + void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); } /// \brief Get a node's degree. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return The degree of the node. - unsigned getNodeDegree(NodeItr nItr) const { - return getNode(nItr).getDegree(); + unsigned getNodeDegree(NodeId nId) const { + return getNode(nId).getDegree(); } /// \brief Begin iterator for node set. - NodeItr nodesBegin() { return nodes.begin(); } - - /// \brief Begin const iterator for node set. - ConstNodeItr nodesBegin() const { return nodes.begin(); } + NodeItr nodesBegin() const { return NodeItr(0, *this); } /// \brief End iterator for node set. - NodeItr nodesEnd() { return nodes.end(); } - - /// \brief End const iterator for node set. - ConstNodeItr nodesEnd() const { return nodes.end(); } + NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); } /// \brief Begin iterator for edge set. - EdgeItr edgesBegin() { return edges.begin(); } + EdgeItr edgesBegin() const { return EdgeItr(0, *this); } /// \brief End iterator for edge set. - EdgeItr edgesEnd() { return edges.end(); } + EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); } /// \brief Get begin iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Begin iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesBegin(NodeItr nItr) { - return getNode(nItr).edgesBegin(); + AdjEdgeItr adjEdgesBegin(NodeId nId) { + return getNode(nId).edgesBegin(); } /// \brief Get end iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return End iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesEnd(NodeItr nItr) { - return getNode(nItr).edgesEnd(); + AdjEdgeItr adjEdgesEnd(NodeId nId) { + return getNode(nId).edgesEnd(); } /// \brief Get the first node connected to this edge. - /// @param eItr Edge iterator. - /// @return The first node connected to the given edge. - NodeItr getEdgeNode1(EdgeItr eItr) { - return getEdge(eItr).getNode1(); + /// @param eId Edge id. + /// @return The first node connected to the given edge. + NodeId getEdgeNode1(EdgeId eId) { + return getEdge(eId).getNode1(); } /// \brief Get the second node connected to this edge. - /// @param eItr Edge iterator. - /// @return The second node connected to the given edge. - NodeItr getEdgeNode2(EdgeItr eItr) { - return getEdge(eItr).getNode2(); - } + /// @param eId Edge id. + /// @return The second node connected to the given edge. + NodeId getEdgeNode2(EdgeId eId) { + return getEdge(eId).getNode2(); + } /// \brief Get the "other" node connected to this edge. - /// @param eItr Edge iterator. - /// @param nItr Node iterator for the "given" node. - /// @return The iterator for the "other" node connected to this edge. - NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) { - EdgeEntry &e = getEdge(eItr); - if (e.getNode1() == nItr) { + /// @param eId Edge id. + /// @param nId Node id for the "given" node. + /// @return The iterator for the "other" node connected to this edge. + NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) { + EdgeEntry &e = getEdge(eId); + if (e.getNode1() == nId) { return e.getNode2(); } // else return e.getNode1(); } + EdgeId invalidEdgeId() const { + return std::numeric_limits<EdgeId>::max(); + } + /// \brief Get the edge connecting two nodes. - /// @param n1Itr First node iterator. - /// @param n2Itr Second node iterator. - /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists, - /// otherwise returns edgesEnd(). - EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) { - for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr); + /// @param n1Id First node id. + /// @param n2Id Second node id. + /// @return An id for edge (n1Id, n2Id) if such an edge exists, + /// otherwise returns an invalid edge id. + EdgeId findEdge(NodeId n1Id, NodeId n2Id) { + for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id); aeItr != aeEnd; ++aeItr) { - if ((getEdgeNode1(*aeItr) == n2Itr) || - (getEdgeNode2(*aeItr) == n2Itr)) { + if ((getEdgeNode1(*aeItr) == n2Id) || + (getEdgeNode2(*aeItr) == n2Id)) { return *aeItr; } } - return edges.end(); + return invalidEdgeId(); } /// \brief Remove a node from the graph. - /// @param nItr Node iterator. - void removeNode(NodeItr nItr) { - NodeEntry &n = getNode(nItr); - for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) { - EdgeItr eItr = *itr; - ++itr; - removeEdge(eItr); + /// @param nId Node id. + void removeNode(NodeId nId) { + NodeEntry &n = getNode(nId); + for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) { + EdgeId eId = *itr; + removeEdge(eId); } - nodes.erase(nItr); - --numNodes; + freeNodes.push_back(nId); } /// \brief Remove an edge from the graph. - /// @param eItr Edge iterator. - void removeEdge(EdgeItr eItr) { - EdgeEntry &e = getEdge(eItr); + /// @param eId Edge id. + void removeEdge(EdgeId eId) { + EdgeEntry &e = getEdge(eId); NodeEntry &n1 = getNode(e.getNode1()); NodeEntry &n2 = getNode(e.getNode2()); n1.removeEdge(e.getNode1AEItr()); n2.removeEdge(e.getNode2AEItr()); - edges.erase(eItr); - --numEdges; + freeEdges.push_back(eId); } /// \brief Remove all nodes and edges from the graph. void clear() { nodes.clear(); + freeNodes.clear(); edges.clear(); - numNodes = numEdges = 0; + freeEdges.clear(); } /// \brief Dump a graph to an output stream. @@ -362,7 +397,7 @@ namespace PBQP { for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { - const Vector& v = getNodeCosts(nodeItr); + const Vector& v = getNodeCosts(*nodeItr); os << "\n" << v.getLength() << "\n"; assert(v.getLength() != 0 && "Empty vector in graph."); os << v[0]; @@ -374,10 +409,10 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr)); - unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr)); + NodeId n1 = getEdgeNode1(*edgeItr); + NodeId n2 = getEdgeNode2(*edgeItr); assert(n1 != n2 && "PBQP graphs shound not have self-edges."); - const Matrix& m = getEdgeCosts(edgeItr); + const Matrix& m = getEdgeCosts(*edgeItr); os << "\n" << n1 << " " << n2 << "\n" << m.getRows() << " " << m.getCols() << "\n"; assert(m.getRows() != 0 && "No rows in matrix."); @@ -396,14 +431,14 @@ namespace PBQP { /// @param os Output stream to print on. template <typename OStream> void printDot(OStream &os) { - + os << "graph {\n"; for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { os << " node" << nodeItr << " [ label=\"" - << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n"; + << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n"; } os << " edge [ len=" << getNumNodes() << " ]\n"; @@ -411,11 +446,11 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - os << " node" << getEdgeNode1(edgeItr) - << " -- node" << getEdgeNode2(edgeItr) + os << " node" << getEdgeNode1(*edgeItr) + << " -- node" << getEdgeNode2(*edgeItr) << " [ label=\""; - const Matrix &edgeCosts = getEdgeCosts(edgeItr); + const Matrix &edgeCosts = getEdgeCosts(*edgeItr); for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { os << edgeCosts.getRowAsVector(i) << "\\n"; @@ -427,39 +462,16 @@ namespace PBQP { }; - class NodeItrComparator { - public: - bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const { - return &*n1 < &*n2; - } - - bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const { - return &*n1 < &*n2; - } - }; - - class EdgeItrCompartor { - public: - bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const { - return &*e1 < &*e2; - } - - bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const { - return &*e1 < &*e2; - } - }; - - void Graph::copyFrom(const Graph &other) { - std::map<Graph::ConstNodeItr, Graph::NodeItr, - NodeItrComparator> nodeMap; +// void Graph::copyFrom(const Graph &other) { +// std::map<Graph::ConstNodeItr, Graph::NodeItr, +// NodeItrComparator> nodeMap; - for (Graph::ConstNodeItr nItr = other.nodesBegin(), - nEnd = other.nodesEnd(); - nItr != nEnd; ++nItr) { - nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); - } - - } +// for (Graph::ConstNodeItr nItr = other.nodesBegin(), +// nEnd = other.nodesEnd(); +// nItr != nEnd; ++nItr) { +// nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); +// } +// } } diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h index 0c1fcb7..8bcbb9e 100644 --- a/include/llvm/CodeGen/PBQP/HeuristicBase.h +++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h @@ -27,7 +27,7 @@ namespace PBQP { /// <li> void heuristicReduce() : Perform a single heuristic reduction. /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent) /// change to the cost matrix on the given edge (by R2). - /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new + /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new /// costs on the given edge. /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new /// edge into the PBQP graph (by R2). @@ -39,7 +39,7 @@ namespace PBQP { /// /// These methods are implemented in this class for documentation purposes, /// but will assert if called. - /// + /// /// Note that this class uses the curiously recursive template idiom to /// forward calls to the derived class. These methods need not be made /// virtual, and indeed probably shouldn't for performance reasons. @@ -52,7 +52,7 @@ namespace PBQP { class HeuristicBase { private: - typedef std::list<Graph::NodeItr> OptimalList; + typedef std::list<Graph::NodeId> OptimalList; HeuristicSolverImpl<HImpl> &s; Graph &g; @@ -62,9 +62,9 @@ namespace PBQP { HImpl& impl() { return static_cast<HImpl&>(*this); } // Add the given node to the optimal reductions list. Keep an iterator to - // its location for fast removal. - void addToOptimalReductionList(Graph::NodeItr nItr) { - optimalList.insert(optimalList.end(), nItr); + // its location for fast removal. + void addToOptimalReductionList(Graph::NodeId nId) { + optimalList.insert(optimalList.end(), nId); } public: @@ -94,7 +94,7 @@ namespace PBQP { /// behaviour. bool solverRunSimplify() const { return true; } - /// \brief Decide whether a node should be optimally or heuristically + /// \brief Decide whether a node should be optimally or heuristically /// reduced. /// @return Whether or not the given node should be listed for optimal /// reduction (via R0, R1 or R2). @@ -105,21 +105,21 @@ namespace PBQP { /// criteria. Note however that your criteria for selecting optimal nodes /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or /// higher should not be selected under any circumstances. - bool shouldOptimallyReduce(Graph::NodeItr nItr) { - if (g.getNodeDegree(nItr) < 3) + bool shouldOptimallyReduce(Graph::NodeId nId) { + if (g.getNodeDegree(nId) < 3) return true; // else return false; } /// \brief Add the given node to the list of nodes to be optimally reduced. - /// @param nItr Node iterator to be added. + /// @param nId Node id to be added. /// /// You probably don't want to over-ride this, except perhaps to record /// statistics before calling this implementation. HeuristicBase relies on /// its behaviour. - void addToOptimalReduceList(Graph::NodeItr nItr) { - optimalList.push_back(nItr); + void addToOptimalReduceList(Graph::NodeId nId) { + optimalList.push_back(nId); } /// \brief Initialise the heuristic. @@ -132,10 +132,10 @@ namespace PBQP { void setup() { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { - if (impl().shouldOptimallyReduce(nItr)) { - addToOptimalReduceList(nItr); + if (impl().shouldOptimallyReduce(*nItr)) { + addToOptimalReduceList(*nItr); } else { - impl().addToHeuristicReduceList(nItr); + impl().addToHeuristicReduceList(*nItr); } } } @@ -150,13 +150,13 @@ namespace PBQP { if (optimalList.empty()) return false; - Graph::NodeItr nItr = optimalList.front(); + Graph::NodeId nId = optimalList.front(); optimalList.pop_front(); - switch (s.getSolverDegree(nItr)) { - case 0: s.applyR0(nItr); break; - case 1: s.applyR1(nItr); break; - case 2: s.applyR2(nItr); break; + switch (s.getSolverDegree(nId)) { + case 0: s.applyR0(nId); break; + case 1: s.applyR1(nId); break; + case 2: s.applyR2(nId); break; default: llvm_unreachable( "Optimal reductions of degree > 2 nodes is invalid."); } @@ -184,8 +184,8 @@ namespace PBQP { } /// \brief Add a node to the heuristic reduce list. - /// @param nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicList(Graph::NodeItr nItr) { + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicList(Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } @@ -199,31 +199,31 @@ namespace PBQP { } /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCostts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void postUpdateEdgeCostts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. - void handleAddEdge(Graph::EdgeItr eItr) { + /// @param eId Edge id for the added edge. + void handleAddEdge(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator for the node being disconnected from. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id for the node being disconnected from. /// /// Edges are frequently removed due to the removal of a node. This /// method allows for the effect to be computed only for the remaining /// node in the graph. - void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { + void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h index 47e15b2..e26ca02 100644 --- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -9,7 +9,7 @@ // // Heuristic PBQP solver. This solver is able to perform optimal reductions for // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is -// used to select a node for reduction. +// used to select a node for reduction. // //===----------------------------------------------------------------------===// @@ -40,10 +40,10 @@ namespace PBQP { typedef typename HImpl::NodeData HeuristicNodeData; typedef typename HImpl::EdgeData HeuristicEdgeData; - typedef std::list<Graph::EdgeItr> SolverEdges; + typedef std::list<Graph::EdgeId> SolverEdges; public: - + /// \brief Iterator type for edges in the solver graph. typedef SolverEdges::iterator SolverEdgeItr; @@ -55,9 +55,9 @@ namespace PBQP { HeuristicNodeData& getHeuristicData() { return hData; } - SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) { + SolverEdgeItr addSolverEdge(Graph::EdgeId eId) { ++solverDegree; - return solverEdges.insert(solverEdges.end(), eItr); + return solverEdges.insert(solverEdges.end(), eId); } void removeSolverEdge(SolverEdgeItr seItr) { @@ -70,15 +70,15 @@ namespace PBQP { unsigned getSolverDegree() const { return solverDegree; } void clearSolverEdges() { solverDegree = 0; - solverEdges.clear(); + solverEdges.clear(); } - + private: HeuristicNodeData hData; unsigned solverDegree; SolverEdges solverEdges; }; - + class EdgeData { public: HeuristicEdgeData& getHeuristicData() { return hData; } @@ -104,7 +104,7 @@ namespace PBQP { Graph &g; HImpl h; Solution s; - std::vector<Graph::NodeItr> stack; + std::vector<Graph::NodeId> stack; typedef std::list<NodeData> NodeDataList; NodeDataList nodeDataList; @@ -117,7 +117,7 @@ namespace PBQP { /// \brief Construct a heuristic solver implementation to solve the given /// graph. /// @param g The graph representing the problem instance to be solved. - HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} + HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} /// \brief Get the graph being solved by this solver. /// @return The graph representing the problem instance being solved by this @@ -125,46 +125,46 @@ namespace PBQP { Graph& getGraph() { return g; } /// \brief Get the heuristic data attached to the given node. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return The heuristic data attached to the given node. - HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getHeuristicData(); + HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolverNodeData(nId).getHeuristicData(); } /// \brief Get the heuristic data attached to the given edge. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return The heuristic data attached to the given node. - HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolverEdgeData(eItr).getHeuristicData(); + HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolverEdgeData(eId).getHeuristicData(); } /// \brief Begin iterator for the set of edges adjacent to the given node in /// the solver graph. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Begin iterator for the set of edges adjacent to the given node - /// in the solver graph. - SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesBegin(); + /// in the solver graph. + SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesBegin(); } /// \brief End iterator for the set of edges adjacent to the given node in /// the solver graph. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return End iterator for the set of edges adjacent to the given node in - /// the solver graph. - SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesEnd(); + /// the solver graph. + SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesEnd(); } /// \brief Remove a node from the solver graph. - /// @param eItr Edge iterator for edge to be removed. + /// @param eId Edge id for edge to be removed. /// /// Does <i>not</i> notify the heuristic of the removal. That should be /// done manually if necessary. - void removeSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); + void removeSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); n1Data.removeSolverEdge(eData.getN1SolverEdgeItr()); n2Data.removeSolverEdge(eData.getN2SolverEdgeItr()); @@ -188,66 +188,66 @@ namespace PBQP { } /// \brief Add to the end of the stack. - /// @param nItr Node iterator to add to the reduction stack. - void pushToStack(Graph::NodeItr nItr) { - getSolverNodeData(nItr).clearSolverEdges(); - stack.push_back(nItr); + /// @param nId Node id to add to the reduction stack. + void pushToStack(Graph::NodeId nId) { + getSolverNodeData(nId).clearSolverEdges(); + stack.push_back(nId); } /// \brief Returns the solver degree of the given node. - /// @param nItr Node iterator for which degree is requested. + /// @param nId Node id for which degree is requested. /// @return Node degree in the <i>solver</i> graph (not the original graph). - unsigned getSolverDegree(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getSolverDegree(); + unsigned getSolverDegree(Graph::NodeId nId) { + return getSolverNodeData(nId).getSolverDegree(); } /// \brief Set the solution of the given node. - /// @param nItr Node iterator to set solution for. + /// @param nId Node id to set solution for. /// @param selection Selection for node. - void setSolution(const Graph::NodeItr &nItr, unsigned selection) { - s.setSelection(nItr, selection); + void setSolution(const Graph::NodeId &nId, unsigned selection) { + s.setSelection(nId, selection); - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - Graph::EdgeItr eItr(*aeItr); - Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr)); - getSolverNodeData(anItr).addSolverEdge(eItr); + Graph::EdgeId eId(*aeItr); + Graph::NodeId anId(g.getEdgeOtherNode(eId, nId)); + getSolverNodeData(anId).addSolverEdge(eId); } } /// \brief Apply rule R0. - /// @param nItr Node iterator for node to apply R0 to. + /// @param nId Node id for node to apply R0 to. /// /// Node will be automatically pushed to the solver stack. - void applyR0(Graph::NodeItr nItr) { - assert(getSolverNodeData(nItr).getSolverDegree() == 0 && + void applyR0(Graph::NodeId nId) { + assert(getSolverNodeData(nId).getSolverDegree() == 0 && "R0 applied to node with degree != 0."); // Nothing to do. Just push the node onto the reduction stack. - pushToStack(nItr); + pushToStack(nId); s.recordR0(); } /// \brief Apply rule R1. - /// @param xnItr Node iterator for node to apply R1 to. + /// @param xnId Node id for node to apply R1 to. /// /// Node will be automatically pushed to the solver stack. - void applyR1(Graph::NodeItr xnItr) { - NodeData &nd = getSolverNodeData(xnItr); + void applyR1(Graph::NodeId xnId) { + NodeData &nd = getSolverNodeData(xnId); assert(nd.getSolverDegree() == 1 && "R1 applied to node with degree != 1."); - Graph::EdgeItr eItr = *nd.solverEdgesBegin(); + Graph::EdgeId eId = *nd.solverEdgesBegin(); + + const Matrix &eCosts = g.getEdgeCosts(eId); + const Vector &xCosts = g.getNodeCosts(xnId); - const Matrix &eCosts = g.getEdgeCosts(eItr); - const Vector &xCosts = g.getNodeCosts(xnItr); - // Duplicate a little to avoid transposing matrices. - if (xnItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr ynItr = g.getEdgeNode2(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); + if (xnId == g.getEdgeNode1(eId)) { + Graph::NodeId ynId = g.getEdgeNode2(eId); + Vector &yCosts = g.getNodeCosts(ynId); for (unsigned j = 0; j < yCosts.getLength(); ++j) { PBQPNum min = eCosts[0][j] + xCosts[0]; for (unsigned i = 1; i < xCosts.getLength(); ++i) { @@ -257,10 +257,10 @@ namespace PBQP { } yCosts[j] += min; } - h.handleRemoveEdge(eItr, ynItr); + h.handleRemoveEdge(eId, ynId); } else { - Graph::NodeItr ynItr = g.getEdgeNode1(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); + Graph::NodeId ynId = g.getEdgeNode1(eId); + Vector &yCosts = g.getNodeCosts(ynId); for (unsigned i = 0; i < yCosts.getLength(); ++i) { PBQPNum min = eCosts[i][0] + xCosts[0]; for (unsigned j = 1; j < xCosts.getLength(); ++j) { @@ -270,48 +270,48 @@ namespace PBQP { } yCosts[i] += min; } - h.handleRemoveEdge(eItr, ynItr); + h.handleRemoveEdge(eId, ynId); } - removeSolverEdge(eItr); + removeSolverEdge(eId); assert(nd.getSolverDegree() == 0 && "Degree 1 with edge removed should be 0."); - pushToStack(xnItr); + pushToStack(xnId); s.recordR1(); } /// \brief Apply rule R2. - /// @param xnItr Node iterator for node to apply R2 to. + /// @param xnId Node id for node to apply R2 to. /// /// Node will be automatically pushed to the solver stack. - void applyR2(Graph::NodeItr xnItr) { - assert(getSolverNodeData(xnItr).getSolverDegree() == 2 && + void applyR2(Graph::NodeId xnId) { + assert(getSolverNodeData(xnId).getSolverDegree() == 2 && "R2 applied to node with degree != 2."); - NodeData &nd = getSolverNodeData(xnItr); - const Vector &xCosts = g.getNodeCosts(xnItr); + NodeData &nd = getSolverNodeData(xnId); + const Vector &xCosts = g.getNodeCosts(xnId); SolverEdgeItr aeItr = nd.solverEdgesBegin(); - Graph::EdgeItr yxeItr = *aeItr, - zxeItr = *(++aeItr); + Graph::EdgeId yxeId = *aeItr, + zxeId = *(++aeItr); - Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr), - znItr = g.getEdgeOtherNode(zxeItr, xnItr); + Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId), + znId = g.getEdgeOtherNode(zxeId, xnId); - bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr), - flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr); + bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId), + flipEdge2 = (g.getEdgeNode1(zxeId) == xnId); const Matrix *yxeCosts = flipEdge1 ? - new Matrix(g.getEdgeCosts(yxeItr).transpose()) : - &g.getEdgeCosts(yxeItr); + new Matrix(g.getEdgeCosts(yxeId).transpose()) : + &g.getEdgeCosts(yxeId); const Matrix *zxeCosts = flipEdge2 ? - new Matrix(g.getEdgeCosts(zxeItr).transpose()) : - &g.getEdgeCosts(zxeItr); + new Matrix(g.getEdgeCosts(zxeId).transpose()) : + &g.getEdgeCosts(zxeId); unsigned xLen = xCosts.getLength(), yLen = yxeCosts->getRows(), zLen = zxeCosts->getRows(); - + Matrix delta(yLen, zLen); for (unsigned i = 0; i < yLen; ++i) { @@ -333,79 +333,79 @@ namespace PBQP { if (flipEdge2) delete zxeCosts; - Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr); + Graph::EdgeId yzeId = g.findEdge(ynId, znId); bool addedEdge = false; - if (yzeItr == g.edgesEnd()) { - yzeItr = g.addEdge(ynItr, znItr, delta); + if (yzeId == g.invalidEdgeId()) { + yzeId = g.addEdge(ynId, znId, delta); addedEdge = true; } else { - Matrix &yzeCosts = g.getEdgeCosts(yzeItr); - h.preUpdateEdgeCosts(yzeItr); - if (ynItr == g.getEdgeNode1(yzeItr)) { + Matrix &yzeCosts = g.getEdgeCosts(yzeId); + h.preUpdateEdgeCosts(yzeId); + if (ynId == g.getEdgeNode1(yzeId)) { yzeCosts += delta; } else { yzeCosts += delta.transpose(); } } - bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr); + bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId); if (!addedEdge) { // If we modified the edge costs let the heuristic know. - h.postUpdateEdgeCosts(yzeItr); + h.postUpdateEdgeCosts(yzeId); } - + if (nullCostEdge) { // If this edge ended up null remove it. if (!addedEdge) { // We didn't just add it, so we need to notify the heuristic // and remove it from the solver. - h.handleRemoveEdge(yzeItr, ynItr); - h.handleRemoveEdge(yzeItr, znItr); - removeSolverEdge(yzeItr); + h.handleRemoveEdge(yzeId, ynId); + h.handleRemoveEdge(yzeId, znId); + removeSolverEdge(yzeId); } - g.removeEdge(yzeItr); + g.removeEdge(yzeId); } else if (addedEdge) { // If the edge was added, and non-null, finish setting it up, add it to // the solver & notify heuristic. edgeDataList.push_back(EdgeData()); - g.setEdgeData(yzeItr, &edgeDataList.back()); - addSolverEdge(yzeItr); - h.handleAddEdge(yzeItr); + g.setEdgeData(yzeId, &edgeDataList.back()); + addSolverEdge(yzeId); + h.handleAddEdge(yzeId); } - h.handleRemoveEdge(yxeItr, ynItr); - removeSolverEdge(yxeItr); - h.handleRemoveEdge(zxeItr, znItr); - removeSolverEdge(zxeItr); + h.handleRemoveEdge(yxeId, ynId); + removeSolverEdge(yxeId); + h.handleRemoveEdge(zxeId, znId); + removeSolverEdge(zxeId); - pushToStack(xnItr); + pushToStack(xnId); s.recordR2(); } /// \brief Record an application of the RN rule. /// /// For use by the HeuristicBase. - void recordRN() { s.recordRN(); } + void recordRN() { s.recordRN(); } private: - NodeData& getSolverNodeData(Graph::NodeItr nItr) { - return *static_cast<NodeData*>(g.getNodeData(nItr)); + NodeData& getSolverNodeData(Graph::NodeId nId) { + return *static_cast<NodeData*>(g.getNodeData(nId)); } - EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) { - return *static_cast<EdgeData*>(g.getEdgeData(eItr)); + EdgeData& getSolverEdgeData(Graph::EdgeId eId) { + return *static_cast<EdgeData*>(g.getEdgeData(eId)); } - void addSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); + void addSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); - eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr)); - eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr)); + eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId)); + eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId)); } void setup() { @@ -417,15 +417,15 @@ namespace PBQP { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { nodeDataList.push_back(NodeData()); - g.setNodeData(nItr, &nodeDataList.back()); + g.setNodeData(*nItr, &nodeDataList.back()); } // Create edge data objects. for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); eItr != eEnd; ++eItr) { edgeDataList.push_back(EdgeData()); - g.setEdgeData(eItr, &edgeDataList.back()); - addSolverEdge(eItr); + g.setEdgeData(*eItr, &edgeDataList.back()); + addSolverEdge(*eItr); } } @@ -441,28 +441,30 @@ namespace PBQP { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { - if (g.getNodeCosts(nItr).getLength() == 1) { + Graph::NodeId nId = *nItr; + + if (g.getNodeCosts(nId).getLength() == 1) { - std::vector<Graph::EdgeItr> edgesToRemove; + std::vector<Graph::EdgeId> edgesToRemove; - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - Graph::EdgeItr eItr = *aeItr; + Graph::EdgeId eId = *aeItr; - if (g.getEdgeNode1(eItr) == nItr) { - Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getRowAsVector(0); + if (g.getEdgeNode1(eId) == nId) { + Graph::NodeId otherNodeId = g.getEdgeNode2(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getRowAsVector(0); } else { - Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getColAsVector(0); + Graph::NodeId otherNodeId = g.getEdgeNode1(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getColAsVector(0); } - edgesToRemove.push_back(eItr); + edgesToRemove.push_back(eId); } if (!edgesToRemove.empty()) @@ -477,12 +479,12 @@ namespace PBQP { } void eliminateIndependentEdges() { - std::vector<Graph::EdgeItr> edgesToProcess; + std::vector<Graph::EdgeId> edgesToProcess; unsigned numEliminated = 0; for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); eItr != eEnd; ++eItr) { - edgesToProcess.push_back(eItr); + edgesToProcess.push_back(*eItr); } while (!edgesToProcess.empty()) { @@ -492,21 +494,21 @@ namespace PBQP { } } - bool tryToEliminateEdge(Graph::EdgeItr eItr) { - if (tryNormaliseEdgeMatrix(eItr)) { - g.removeEdge(eItr); - return true; + bool tryToEliminateEdge(Graph::EdgeId eId) { + if (tryNormaliseEdgeMatrix(eId)) { + g.removeEdge(eId); + return true; } return false; } - bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { + bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) { const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); - Matrix &edgeCosts = g.getEdgeCosts(eItr); - Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)), - &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr)); + Matrix &edgeCosts = g.getEdgeCosts(eId); + Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)), + &vCosts = g.getNodeCosts(g.getEdgeNode2(eId)); for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { PBQPNum rowMin = infinity; @@ -554,34 +556,34 @@ namespace PBQP { } } - void computeSolution(Graph::NodeItr nItr) { + void computeSolution(Graph::NodeId nId) { - NodeData &nodeData = getSolverNodeData(nItr); + NodeData &nodeData = getSolverNodeData(nId); - Vector v(g.getNodeCosts(nItr)); + Vector v(g.getNodeCosts(nId)); // Solve based on existing solved edges. for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), solvedEdgeEnd = nodeData.solverEdgesEnd(); solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { - Graph::EdgeItr eItr(*solvedEdgeItr); - Matrix &edgeCosts = g.getEdgeCosts(eItr); + Graph::EdgeId eId(*solvedEdgeItr); + Matrix &edgeCosts = g.getEdgeCosts(eId); - if (nItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr adjNode(g.getEdgeNode2(eItr)); + if (nId == g.getEdgeNode1(eId)) { + Graph::NodeId adjNode(g.getEdgeNode2(eId)); unsigned adjSolution = s.getSelection(adjNode); v += edgeCosts.getColAsVector(adjSolution); } else { - Graph::NodeItr adjNode(g.getEdgeNode1(eItr)); + Graph::NodeId adjNode(g.getEdgeNode1(eId)); unsigned adjSolution = s.getSelection(adjNode); v += edgeCosts.getRowAsVector(adjSolution); } } - setSolution(nItr, v.minIndex()); + setSolution(nId, v.minIndex()); } void cleanup() { diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h index 307d81e..c355c2c 100644 --- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -27,7 +27,7 @@ namespace PBQP { /// \brief PBQP Heuristic which applies an allocability test based on /// Briggs. - /// + /// /// This heuristic assumes that the elements of cost vectors in the PBQP /// problem represent storage options, with the first being the spill /// option and subsequent elements representing legal registers for the @@ -39,16 +39,16 @@ namespace PBQP { /// solver stack. If no nodes can be proven allocable then the node with /// the lowest estimated spill cost is selected and push to the solver stack /// instead. - /// - /// This implementation is built on top of HeuristicBase. + /// + /// This implementation is built on top of HeuristicBase. class Briggs : public HeuristicBase<Briggs> { private: class LinkDegreeComparator { public: LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr)) + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id)) return true; return false; } @@ -60,12 +60,12 @@ namespace PBQP { public: SpillCostComparator(HeuristicSolverImpl<Briggs> &s) : s(&s), g(&s.getGraph()) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr); - const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr); + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + const PBQP::Vector &cv1 = g->getNodeCosts(n1Id); + const PBQP::Vector &cv2 = g->getNodeCosts(n2Id); - PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); - PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); + PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id); + PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id); if (cost1 < cost2) return true; @@ -77,10 +77,10 @@ namespace PBQP { Graph *g; }; - typedef std::list<Graph::NodeItr> RNAllocableList; + typedef std::list<Graph::NodeId> RNAllocableList; typedef RNAllocableList::iterator RNAllocableListItr; - typedef std::list<Graph::NodeItr> RNUnallocableList; + typedef std::list<Graph::NodeId> RNUnallocableList; typedef RNUnallocableList::iterator RNUnallocableListItr; public: @@ -114,7 +114,7 @@ namespace PBQP { /// \brief Determine whether a node should be reduced using optimal /// reduction. - /// @param nItr Node iterator to be considered. + /// @param nId Node id to be considered. /// @return True if the given node should be optimally reduced, false /// otherwise. /// @@ -123,8 +123,8 @@ namespace PBQP { /// infinite are checked for allocability first. Allocable nodes may be /// optimally reduced, but nodes whose allocability cannot be proven are /// selected for heuristic reduction instead. - bool shouldOptimallyReduce(Graph::NodeItr nItr) { - if (getSolver().getSolverDegree(nItr) < 3) { + bool shouldOptimallyReduce(Graph::NodeId nId) { + if (getSolver().getSolverDegree(nId) < 3) { return true; } // else @@ -132,15 +132,15 @@ namespace PBQP { } /// \brief Add a node to the heuristic reduce list. - /// @param nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicReduceList(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - initializeNode(nItr); + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicReduceList(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + initializeNode(nId); nd.isHeuristic = true; if (nd.isAllocable) { - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId); } else { - nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); + nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId); } } @@ -159,19 +159,19 @@ namespace PBQP { RNAllocableListItr rnaItr = min_element(rnAllocableList.begin(), rnAllocableList.end(), LinkDegreeComparator(getSolver())); - Graph::NodeItr nItr = *rnaItr; + Graph::NodeId nId = *rnaItr; rnAllocableList.erase(rnaItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); return true; } else if (!rnUnallocableList.empty()) { RNUnallocableListItr rnuItr = min_element(rnUnallocableList.begin(), rnUnallocableList.end(), SpillCostComparator(getSolver())); - Graph::NodeItr nItr = *rnuItr; + Graph::NodeId nId = *rnuItr; rnUnallocableList.erase(rnuItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); return true; } // else @@ -179,43 +179,43 @@ namespace PBQP { } /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); if (n1.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); + subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId)); if (n2.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); + subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId)); - EdgeData &ed = getHeuristicEdgeData(eItr); + EdgeData &ed = getHeuristicEdgeData(eId); ed.isUpToDate = false; } /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void postUpdateEdgeCosts(Graph::EdgeId eId) { // This is effectively the same as adding a new edge now, since // we've factored out the costs of the old one. - handleAddEdge(eItr); + handleAddEdge(eId); } /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. + /// @param eId Edge id for the added edge. /// /// Updates allocability of any nodes connected by this edge which are /// being managed by the heuristic. If allocability changes they are /// moved to the appropriate list. - void handleAddEdge(Graph::EdgeItr eItr) { + void handleAddEdge(Graph::EdgeId eId) { Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); // If neither node is managed by the heuristic there's nothing to be // done. @@ -223,60 +223,60 @@ namespace PBQP { return; // Ok - we need to update at least one node. - computeEdgeContributions(eItr); + computeEdgeContributions(eId); // Update node 1 if it's managed by the heuristic. if (n1.isHeuristic) { bool n1WasAllocable = n1.isAllocable; - addEdgeContributions(eItr, n1Itr); - updateAllocability(n1Itr); + addEdgeContributions(eId, n1Id); + updateAllocability(n1Id); if (n1WasAllocable && !n1.isAllocable) { rnAllocableList.erase(n1.rnaItr); n1.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); + rnUnallocableList.insert(rnUnallocableList.end(), n1Id); } } // Likewise for node 2. if (n2.isHeuristic) { bool n2WasAllocable = n2.isAllocable; - addEdgeContributions(eItr, n2Itr); - updateAllocability(n2Itr); + addEdgeContributions(eId, n2Id); + updateAllocability(n2Id); if (n2WasAllocable && !n2.isAllocable) { rnAllocableList.erase(n2.rnaItr); n2.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); + rnUnallocableList.insert(rnUnallocableList.end(), n2Id); } } } /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator for the node being disconnected from. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id for the node being disconnected from. /// /// Updates allocability of the given node and, if appropriate, moves the /// node to a new list. - void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); + void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) { + NodeData &nd =getHeuristicNodeData(nId); // If the node is not managed by the heuristic there's nothing to be // done. if (!nd.isHeuristic) return; - EdgeData &ed = getHeuristicEdgeData(eItr); + EdgeData &ed = getHeuristicEdgeData(eId); (void)ed; assert(ed.isUpToDate && "Edge data is not up to date."); // Update node. bool ndWasAllocable = nd.isAllocable; - subtractEdgeContributions(eItr, nItr); - updateAllocability(nItr); + subtractEdgeContributions(eId, nId); + updateAllocability(nId); // If the node has gone optimal... - if (shouldOptimallyReduce(nItr)) { + if (shouldOptimallyReduce(nId)) { nd.isHeuristic = false; - addToOptimalReduceList(nItr); + addToOptimalReduceList(nId); if (ndWasAllocable) { rnAllocableList.erase(nd.rnaItr); } else { @@ -287,36 +287,36 @@ namespace PBQP { // from "unallocable" to "allocable". if (!ndWasAllocable && nd.isAllocable) { rnUnallocableList.erase(nd.rnuItr); - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId); } } } private: - NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolver().getHeuristicNodeData(nItr); + NodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolver().getHeuristicNodeData(nId); } - EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolver().getHeuristicEdgeData(eItr); + EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolver().getHeuristicEdgeData(eId); } // Work out what this edge will contribute to the allocability of the // nodes connected to it. - void computeEdgeContributions(Graph::EdgeItr eItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void computeEdgeContributions(Graph::EdgeId eId) { + EdgeData &ed = getHeuristicEdgeData(eId); if (ed.isUpToDate) return; // Edge data is already up to date. - Matrix &eCosts = getGraph().getEdgeCosts(eItr); + Matrix &eCosts = getGraph().getEdgeCosts(eId); unsigned numRegs = eCosts.getRows() - 1, numReverseRegs = eCosts.getCols() - 1; std::vector<unsigned> rowInfCounts(numRegs, 0), - colInfCounts(numReverseRegs, 0); + colInfCounts(numReverseRegs, 0); ed.worst = 0; ed.reverseWorst = 0; @@ -348,19 +348,19 @@ namespace PBQP { ed.isUpToDate = true; } - // Add the contributions of the given edge to the given node's + // Add the contributions of the given edge to the given node's // numDenied and safe members. No action is taken other than to update // these member values. Once updated these numbers can be used by clients // to update the node's allocability. - void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); assert(ed.isUpToDate && "Using out-of-date edge numbers."); - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); EdgeData::UnsafeArray &unsafe = nIsNode1 ? ed.unsafe : ed.reverseUnsafe; nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst; @@ -375,25 +375,25 @@ namespace PBQP { } } - // Subtract the contributions of the given edge to the given node's + // Subtract the contributions of the given edge to the given node's // numDenied and safe members. No action is taken other than to update // these member values. Once updated these numbers can be used by clients // to update the node's allocability. - void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); assert(ed.isUpToDate && "Using out-of-date edge numbers."); - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); EdgeData::UnsafeArray &unsafe = nIsNode1 ? ed.unsafe : ed.reverseUnsafe; nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst; for (unsigned r = 0; r < numRegs; ++r) { - if (unsafe[r]) { + if (unsafe[r]) { if (nd.unsafeDegrees[r] == 1) { ++nd.numSafe; } @@ -402,22 +402,22 @@ namespace PBQP { } } - void updateAllocability(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + void updateAllocability(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; } - void initializeNode(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); + void initializeNode(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); if (nd.isInitialized) return; // Node data is already up to date. - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; nd.numDenied = 0; - const Vector& nCosts = getGraph().getNodeCosts(nItr); + const Vector& nCosts = getGraph().getNodeCosts(nId); for (unsigned i = 1; i < nCosts.getLength(); ++i) { if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity()) ++nd.numDenied; @@ -428,27 +428,27 @@ namespace PBQP { typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), - aeEnd = getSolver().solverEdgesEnd(nItr); + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId), + aeEnd = getSolver().solverEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - - Graph::EdgeItr eItr = *aeItr; - computeEdgeContributions(eItr); - addEdgeContributions(eItr, nItr); + + Graph::EdgeId eId = *aeItr; + computeEdgeContributions(eId); + addEdgeContributions(eId, nId); } - updateAllocability(nItr); + updateAllocability(nId); nd.isInitialized = true; } - void handleRemoveNode(Graph::NodeItr xnItr) { + void handleRemoveNode(Graph::NodeId xnId) { typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - std::vector<Graph::EdgeItr> edgesToRemove; - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), - aeEnd = getSolver().solverEdgesEnd(xnItr); + std::vector<Graph::EdgeId> edgesToRemove; + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId), + aeEnd = getSolver().solverEdgesEnd(xnId); aeItr != aeEnd; ++aeItr) { - Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); - handleRemoveEdge(*aeItr, ynItr); + Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId); + handleRemoveEdge(*aeItr, ynId); edgesToRemove.push_back(*aeItr); } while (!edgesToRemove.empty()) { diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h index b9f288b..091805d 100644 --- a/include/llvm/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -26,8 +26,7 @@ namespace PBQP { class Solution { private: - typedef std::map<Graph::ConstNodeItr, unsigned, - NodeItrComparator> SelectionsMap; + typedef std::map<Graph::NodeId, unsigned> SelectionsMap; SelectionsMap selections; unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; @@ -71,17 +70,17 @@ namespace PBQP { unsigned numRNReductions() const { return rNReductions; } /// \brief Set the selection for a given node. - /// @param nItr Node iterator. - /// @param selection Selection for nItr. - void setSelection(Graph::NodeItr nItr, unsigned selection) { - selections[nItr] = selection; + /// @param nodeId Node id. + /// @param selection Selection for nodeId. + void setSelection(Graph::NodeId nodeId, unsigned selection) { + selections[nodeId] = selection; } /// \brief Get a node's selection. - /// @param nItr Node iterator. - /// @return The selection for nItr; - unsigned getSelection(Graph::ConstNodeItr nItr) const { - SelectionsMap::const_iterator sItr = selections.find(nItr); + /// @param nodeId Node id. + /// @return The selection for nodeId; + unsigned getSelection(Graph::NodeId nodeId) const { + SelectionsMap::const_iterator sItr = selections.find(nodeId); assert(sItr != selections.end() && "No selection for node."); return sItr->second; } diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 9b6f61e..ae4a2fa 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -21,19 +21,22 @@ namespace llvm { - class FunctionPass; - class MachineFunctionPass; - class PassInfo; - class PassManagerBase; - class TargetLoweringBase; - class TargetLowering; - class TargetRegisterClass; - class raw_ostream; -} - -namespace llvm { - +class FunctionPass; +class MachineFunctionPass; class PassConfigImpl; +class PassInfo; +class ScheduleDAGInstrs; +class TargetLowering; +class TargetLoweringBase; +class TargetRegisterClass; +class raw_ostream; +struct MachineSchedContext; + +// The old pass manager infrastructure is hidden in a legacy namespace now. +namespace legacy { +class PassManagerBase; +} +using legacy::PassManagerBase; /// Discriminated union of Pass ID types. /// @@ -204,6 +207,20 @@ public: /// Fully developed targets will not generally override this. virtual void addMachinePasses(); + /// createTargetScheduler - Create an instance of ScheduleDAGInstrs to be run + /// within the standard MachineScheduler pass for this function and target at + /// the current optimization level. + /// + /// This can also be used to plug a new MachineSchedStrategy into an instance + /// of the standard ScheduleDAGMI: + /// return new ScheduleDAGMI(C, new MyStrategy(C)) + /// + /// Return NULL to select the default (generic) machine scheduler. + virtual ScheduleDAGInstrs * + createMachineScheduler(MachineSchedContext *C) const { + return 0; + } + protected: // Helper to verify the analysis is really immutable. void setOpt(bool &Opt, bool Val); @@ -365,14 +382,6 @@ namespace llvm { /// these register allocator like this: AU.addRequiredID(PHIEliminationID); extern char &PHIEliminationID; - /// StrongPHIElimination - This pass eliminates machine instruction PHI - /// nodes by inserting copy instructions. This destroys SSA information, but - /// is the desired input for some register allocators. This pass is - /// "required" by these register allocator like this: - /// AU.addRequiredID(PHIEliminationID); - /// This pass is still in development - extern char &StrongPHIEliminationID; - /// LiveIntervals - This analysis keeps track of the live ranges of virtual /// and physical registers. extern char &LiveIntervalsID; diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index df74d088..705086c 100644 --- a/include/llvm/CodeGen/PseudoSourceValue.h +++ b/include/llvm/CodeGen/PseudoSourceValue.h @@ -44,7 +44,7 @@ namespace llvm { virtual bool isAliased(const MachineFrameInfo *) const; /// mayAlias - Return true if the memory pointed to by this - /// PseudoSourceValue can ever alias a LLVM IR Value. + /// PseudoSourceValue can ever alias an LLVM IR Value. virtual bool mayAlias(const MachineFrameInfo *) const; /// classof - Methods for support type inquiry through isa, cast, and diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index 6f2d139..7472e5a 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -52,22 +52,22 @@ namespace llvm { /// PBQPBuilder you are unlikely to need this: Nodes and options for all /// vregs will already have been set up for you by the base class. template <typename AllowedRegsItr> - void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node, + void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId, AllowedRegsItr arBegin, AllowedRegsItr arEnd) { - assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node."); + assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node."); assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg."); assert(allowedSets[vreg].empty() && "vreg already has pregs."); - node2VReg[node] = vreg; - vreg2Node[vreg] = node; + node2VReg[nodeId] = vreg; + vreg2Node[vreg] = nodeId; std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg])); } /// Get the virtual register corresponding to the given PBQP node. - unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const; + unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const; /// Get the PBQP node corresponding to the given virtual register. - PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; + PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const; /// Returns true if the given PBQP option represents a physical register, /// false otherwise. @@ -92,9 +92,8 @@ namespace llvm { private: - typedef std::map<PBQP::Graph::ConstNodeItr, unsigned, - PBQP::NodeItrComparator> Node2VReg; - typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node; + typedef std::map<PBQP::Graph::NodeId, unsigned> Node2VReg; + typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node; typedef DenseMap<unsigned, AllowedSet> AllowedSetMap; PBQP::Graph graph; diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h index 8a0a8f3..a801d1d 100644 --- a/include/llvm/CodeGen/RegisterPressure.h +++ b/include/llvm/CodeGen/RegisterPressure.h @@ -22,7 +22,7 @@ namespace llvm { class LiveIntervals; -class LiveInterval; +class LiveRange; class RegisterClassInfo; class MachineInstr; @@ -89,20 +89,89 @@ struct RegionPressure : RegisterPressure { void openBottom(MachineBasicBlock::const_iterator PrevBottom); }; -/// An element of pressure difference that identifies the pressure set and -/// amount of increase or decrease in units of pressure. -struct PressureElement { - unsigned PSetID; - int UnitIncrease; +/// Capture a change in pressure for a single pressure set. UnitInc may be +/// expressed in terms of upward or downward pressure depending on the client +/// and will be dynamically adjusted for current liveness. +/// +/// Pressure increments are tiny, typically 1-2 units, and this is only for +/// heuristics, so we don't check UnitInc overflow. Instead, we may have a +/// higher level assert that pressure is consistent within a region. We also +/// effectively ignore dead defs which don't affect heuristics much. +class PressureChange { + uint16_t PSetID; // ID+1. 0=Invalid. + int16_t UnitInc; +public: + PressureChange(): PSetID(0), UnitInc(0) {} + PressureChange(unsigned id): PSetID(id+1), UnitInc(0) { + assert(id < UINT16_MAX && "PSetID overflow."); + } + + bool isValid() const { return PSetID > 0; } + + unsigned getPSet() const { + assert(isValid() && "invalid PressureChange"); + return PSetID - 1; + } + // If PSetID is invalid, return UINT16_MAX to give it lowest priority. + unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; } + + int getUnitInc() const { return UnitInc; } - PressureElement(): PSetID(~0U), UnitIncrease(0) {} - PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {} + void setUnitInc(int Inc) { UnitInc = Inc; } - bool isValid() const { return PSetID != ~0U; } + bool operator==(const PressureChange &RHS) const { + return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; + } +}; - // If signed PSetID is negative, it is invalid; convert it to INT_MAX to give - // it lowest priority. - int PSetRank() const { return PSetID & INT_MAX; } +template <> struct isPodLike<PressureChange> { + static const bool value = true; +}; + +/// List of PressureChanges in order of increasing, unique PSetID. +/// +/// Use a small fixed number, because we can fit more PressureChanges in an +/// empty SmallVector than ever need to be tracked per register class. If more +/// PSets are affected, then we only track the most constrained. +class PressureDiff { + // The initial design was for MaxPSets=4, but that requires PSet partitions, + // which are not yet implemented. (PSet partitions are equivalent PSets given + // the register classes actually in use within the scheduling region.) + enum { MaxPSets = 16 }; + + PressureChange PressureChanges[MaxPSets]; +public: + typedef PressureChange* iterator; + typedef const PressureChange* const_iterator; + iterator begin() { return &PressureChanges[0]; } + iterator end() { return &PressureChanges[MaxPSets]; } + const_iterator begin() const { return &PressureChanges[0]; } + const_iterator end() const { return &PressureChanges[MaxPSets]; } + + void addPressureChange(unsigned RegUnit, bool IsDec, + const MachineRegisterInfo *MRI); +}; + +/// Array of PressureDiffs. +class PressureDiffs { + PressureDiff *PDiffArray; + unsigned Size; + unsigned Max; +public: + PressureDiffs(): PDiffArray(0), Size(0), Max(0) {} + ~PressureDiffs() { free(PDiffArray); } + + void clear() { Size = 0; } + + void init(unsigned N); + + PressureDiff &operator[](unsigned Idx) { + assert(Idx < Size && "PressureDiff index out of bounds"); + return PDiffArray[Idx]; + } + const PressureDiff &operator[](unsigned Idx) const { + return const_cast<PressureDiffs*>(this)->operator[](Idx); + } }; /// Store the effects of a change in pressure on things that MI scheduler cares @@ -120,11 +189,19 @@ struct PressureElement { /// CurrentMax records the largest increase in the tracker's max pressure that /// exceeds the current limit for some pressure set determined by the client. struct RegPressureDelta { - PressureElement Excess; - PressureElement CriticalMax; - PressureElement CurrentMax; + PressureChange Excess; + PressureChange CriticalMax; + PressureChange CurrentMax; RegPressureDelta() {} + + bool operator==(const RegPressureDelta &RHS) const { + return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax + && CurrentMax == RHS.CurrentMax; + } + bool operator!=(const RegPressureDelta &RHS) const { + return !operator==(RHS); + } }; /// \brief A set of live virtual registers and physical register units. @@ -135,7 +212,7 @@ struct LiveRegSet { SparseSet<unsigned> PhysRegs; SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs; - bool contains(unsigned Reg) { + bool contains(unsigned Reg) const { if (TargetRegisterInfo::isVirtualRegister(Reg)) return VirtRegs.count(Reg); return PhysRegs.count(Reg); @@ -215,6 +292,8 @@ public: MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false), TrackUntiedDefs(false) {} + void reset(); + void init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos, @@ -239,7 +318,7 @@ public: SlotIndex getCurrSlot() const; /// Recede across the previous instruction. - bool recede(); + bool recede(SmallVectorImpl<unsigned> *LiveUses = 0, PressureDiff *PDiff = 0); /// Advance across the current instruction. bool advance(); @@ -282,31 +361,39 @@ public: /// limit based on the tracker's current pressure, and record the number of /// excess register units of that pressure set introduced by this instruction. void getMaxUpwardPressureDelta(const MachineInstr *MI, + PressureDiff *PDiff, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit); + void getUpwardPressureDelta(const MachineInstr *MI, + /*const*/ PressureDiff &PDiff, + RegPressureDelta &Delta, + ArrayRef<PressureChange> CriticalPSets, + ArrayRef<unsigned> MaxPressureLimit) const; + /// Consider the pressure increase caused by traversing this instruction /// top-down. Find the pressure set with the most change beyond its pressure /// limit based on the tracker's current pressure, and record the number of /// excess register units of that pressure set introduced by this instruction. void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit); /// Find the pressure set with the most change beyond its pressure limit after /// traversing this instruction either upward or downward depending on the /// closed end of the current region. - void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + void getMaxPressureDelta(const MachineInstr *MI, + RegPressureDelta &Delta, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit) { if (isTopClosed()) return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, MaxPressureLimit); assert(isBottomClosed() && "Uninitialized pressure tracker"); - return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, + return getMaxUpwardPressureDelta(MI, 0, Delta, CriticalPSets, MaxPressureLimit); } @@ -337,7 +424,7 @@ public: void dump() const; protected: - const LiveInterval *getInterval(unsigned Reg) const; + const LiveRange *getLiveRange(unsigned Reg) const; void increaseRegPressure(ArrayRef<unsigned> Regs); void decreaseRegPressure(ArrayRef<unsigned> Regs); diff --git a/include/llvm/CodeGen/RuntimeLibcalls.h b/include/llvm/CodeGen/RuntimeLibcalls.h index 41289a4..009b8a0 100644 --- a/include/llvm/CodeGen/RuntimeLibcalls.h +++ b/include/llvm/CodeGen/RuntimeLibcalls.h @@ -1,4 +1,4 @@ -//===-- CodeGen/RuntimeLibcall.h - Runtime Library Calls --------*- C++ -*-===// +//===-- CodeGen/RuntimeLibcalls.h - Runtime Library Calls -------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -188,6 +188,11 @@ namespace RTLIB { NEARBYINT_F80, NEARBYINT_F128, NEARBYINT_PPCF128, + ROUND_F32, + ROUND_F64, + ROUND_F80, + ROUND_F128, + ROUND_PPCF128, FLOOR_F32, FLOOR_F64, FLOOR_F80, @@ -320,34 +325,65 @@ namespace RTLIB { SYNC_VAL_COMPARE_AND_SWAP_2, SYNC_VAL_COMPARE_AND_SWAP_4, SYNC_VAL_COMPARE_AND_SWAP_8, + SYNC_VAL_COMPARE_AND_SWAP_16, SYNC_LOCK_TEST_AND_SET_1, SYNC_LOCK_TEST_AND_SET_2, SYNC_LOCK_TEST_AND_SET_4, SYNC_LOCK_TEST_AND_SET_8, + SYNC_LOCK_TEST_AND_SET_16, SYNC_FETCH_AND_ADD_1, SYNC_FETCH_AND_ADD_2, SYNC_FETCH_AND_ADD_4, SYNC_FETCH_AND_ADD_8, + SYNC_FETCH_AND_ADD_16, SYNC_FETCH_AND_SUB_1, SYNC_FETCH_AND_SUB_2, SYNC_FETCH_AND_SUB_4, SYNC_FETCH_AND_SUB_8, + SYNC_FETCH_AND_SUB_16, SYNC_FETCH_AND_AND_1, SYNC_FETCH_AND_AND_2, SYNC_FETCH_AND_AND_4, SYNC_FETCH_AND_AND_8, + SYNC_FETCH_AND_AND_16, SYNC_FETCH_AND_OR_1, SYNC_FETCH_AND_OR_2, SYNC_FETCH_AND_OR_4, SYNC_FETCH_AND_OR_8, + SYNC_FETCH_AND_OR_16, SYNC_FETCH_AND_XOR_1, SYNC_FETCH_AND_XOR_2, SYNC_FETCH_AND_XOR_4, SYNC_FETCH_AND_XOR_8, + SYNC_FETCH_AND_XOR_16, SYNC_FETCH_AND_NAND_1, SYNC_FETCH_AND_NAND_2, SYNC_FETCH_AND_NAND_4, SYNC_FETCH_AND_NAND_8, + SYNC_FETCH_AND_NAND_16, + SYNC_FETCH_AND_MAX_1, + SYNC_FETCH_AND_MAX_2, + SYNC_FETCH_AND_MAX_4, + SYNC_FETCH_AND_MAX_8, + SYNC_FETCH_AND_MAX_16, + SYNC_FETCH_AND_UMAX_1, + SYNC_FETCH_AND_UMAX_2, + SYNC_FETCH_AND_UMAX_4, + SYNC_FETCH_AND_UMAX_8, + SYNC_FETCH_AND_UMAX_16, + SYNC_FETCH_AND_MIN_1, + SYNC_FETCH_AND_MIN_2, + SYNC_FETCH_AND_MIN_4, + SYNC_FETCH_AND_MIN_8, + SYNC_FETCH_AND_MIN_16, + SYNC_FETCH_AND_UMIN_1, + SYNC_FETCH_AND_UMIN_2, + SYNC_FETCH_AND_UMIN_4, + SYNC_FETCH_AND_UMIN_8, + SYNC_FETCH_AND_UMIN_16, + + // Stack Protector Fail. + STACKPROTECTOR_CHECK_FAIL, UNKNOWN_LIBCALL }; diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 371ac6c..ccba1b0 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -248,7 +248,7 @@ namespace llvm { /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: - enum { BoundaryID = ~0u }; + enum LLVM_ENUM_INT_TYPE(unsigned) { BoundaryID = ~0u }; SDNode *Node; // Representative node. MachineInstr *Instr; // Alternatively, a MachineInstr. diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index 9ab1013..fe4f3c2 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -28,6 +28,7 @@ namespace llvm { class MachineDominatorTree; class LiveIntervals; class RegPressureTracker; + class PressureDiffs; /// An individual mapping from virtual register number to SUnit. struct VReg2SUnit { @@ -56,7 +57,8 @@ namespace llvm { /// Use a SparseMultiSet to track physical registers. Storage is only /// allocated once for the pass. It can be cleared in constant time and reused /// without any frees. - typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> Reg2SUnitsMap; + typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> + Reg2SUnitsMap; /// Use SparseSet as a SparseMap by relying on the fact that it never /// compares ValueT's, only unsigned keys. This allows the set to be cleared @@ -64,6 +66,11 @@ namespace llvm { /// require a destructor. typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; + /// Track local uses of virtual registers. These uses are gathered by the DAG + /// builder and may be consulted by the scheduler to avoid iterating an entire + /// vreg use list. + typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap; + /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of /// MachineInstrs. class ScheduleDAGInstrs : public ScheduleDAG { @@ -81,10 +88,6 @@ namespace llvm { /// isPostRA flag indicates vregs cannot be present. bool IsPostRA; - /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using - /// the def-side latency only. - bool UnitLatencies; - /// The standard DAG builder does not normally include terminators as DAG /// nodes because it does not create the necessary dependencies to prevent /// reordering. A specialized scheduler can overide @@ -104,17 +107,18 @@ namespace llvm { /// The end of the range to be scheduled. MachineBasicBlock::iterator RegionEnd; - /// The index in BB of RegionEnd. - /// - /// This is the instruction number from the top of the current block, not - /// the SlotIndex. It is only used by the AntiDepBreaker and should be - /// removed once that client is obsolete. - unsigned EndIndex; + /// Instructions in this region (distance(RegionBegin, RegionEnd)). + unsigned NumRegionInstrs; /// After calling BuildSchedGraph, each machine instruction in the current /// scheduling region is mapped to an SUnit. DenseMap<MachineInstr*, SUnit*> MISUnitMap; + /// After calling BuildSchedGraph, each vreg used in the scheduling region + /// is mapped to a set of SUnits. These include all local vreg uses, not + /// just the uses for a singly defined vreg. + VReg2UseMap VRegUses; + /// State internal to DAG building. /// ------------------------------- @@ -125,7 +129,7 @@ namespace llvm { Reg2SUnitsMap Defs; Reg2SUnitsMap Uses; - /// Track the last instructon in this region defining each virtual register. + /// Track the last instruction in this region defining each virtual register. VReg2SUnitMap VRegDefs; /// PendingLoads - Remember where unknown loads are after the most recent @@ -185,14 +189,15 @@ namespace llvm { virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); + unsigned regioninstrs); /// Notify that the scheduler has finished scheduling the current region. virtual void exitRegion(); /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are /// input. - void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0); + void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0, + PressureDiffs *PDiffs = 0); /// addSchedBarrierDeps - Add dependencies from instructions in the current /// list of instructions being scheduled to scheduling barrier. We want to diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 79e533e..82becca 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -38,6 +38,45 @@ class TargetLowering; class TargetSelectionDAGInfo; class TargetTransformInfo; +class SDVTListNode : public FoldingSetNode { + friend struct FoldingSetTrait<SDVTListNode>; + /// FastID - A reference to an Interned FoldingSetNodeID for this node. + /// The Allocator in SelectionDAG holds the data. + /// SDVTList contains all types which are frequently accessed in SelectionDAG. + /// The size of this list is not expected big so it won't introduce memory penalty. + FoldingSetNodeIDRef FastID; + const EVT *VTs; + unsigned int NumVTs; + /// The hash value for SDVTList is fixed so cache it to avoid hash calculation + unsigned HashValue; +public: + SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) : + FastID(ID), VTs(VT), NumVTs(Num) { + HashValue = ID.ComputeHash(); + } + SDVTList getSDVTList() { + SDVTList result = {VTs, NumVTs}; + return result; + } +}; + +// Specialize FoldingSetTrait for SDVTListNode +// To avoid computing temp FoldingSetNodeID and hash value. +template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> { + static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) { + ID = X.FastID; + } + static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID, + unsigned IDHash, FoldingSetNodeID &TempID) { + if (X.HashValue != IDHash) + return false; + return ID == X.FastID; + } + static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) { + return X.HashValue; + } +}; + template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { private: mutable ilist_half_node<SDNode> Sentinel; @@ -131,6 +170,7 @@ class SelectionDAG { const TargetMachine &TM; const TargetSelectionDAGInfo &TSI; const TargetTransformInfo *TTI; + const TargetLowering *TLI; MachineFunction *MF; LLVMContext *Context; CodeGenOpt::Level OptLevel; @@ -197,6 +237,13 @@ public: virtual void NodeUpdated(SDNode *N); }; + /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to + /// ensure that getConstant() and similar functions return DAG nodes that + /// have legal types. This is important after type legalization since + /// any illegally typed nodes generated after this point will not experience + /// type legalization. + bool NewNodesMustHaveLegalTypes; + private: /// DAGUpdateListener is a friend so it can manipulate the listener stack. friend struct DAGUpdateListener; @@ -222,7 +269,8 @@ public: /// init - Prepare this SelectionDAG to process code in the given /// MachineFunction. /// - void init(MachineFunction &mf, const TargetTransformInfo *TTI); + void init(MachineFunction &mf, const TargetTransformInfo *TTI, + const TargetLowering *TLI); /// clear - Clear state and free memory necessary to make this /// SelectionDAG ready to process a new block. @@ -231,9 +279,7 @@ public: MachineFunction &getMachineFunction() const { return *MF; } const TargetMachine &getTarget() const { return TM; } - const TargetLowering &getTargetLoweringInfo() const { - return *TM.getTargetLowering(); - } + const TargetLowering &getTargetLoweringInfo() const { return *TLI; } const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; } const TargetTransformInfo *getTargetTransformInfo() const { return TTI; } LLVMContext *getContext() const {return Context; } @@ -677,6 +723,13 @@ public: AtomicOrdering Ordering, SynchronizationScope SynchScope); + /// getAtomic - Gets a node for an atomic op, produces result and chain and + /// takes N operands. + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList, + SDValue* Ops, unsigned NumOps, MachineMemOperand *MMO, + AtomicOrdering Ordering, + SynchronizationScope SynchScope); + /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not @@ -708,11 +761,16 @@ public: MachinePointerInfo PtrInfo, bool isVolatile, bool isNonTemporal, bool isInvariant, unsigned Alignment, const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0); + SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, + MachineMemOperand *MMO); SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, bool isVolatile, bool isNonTemporal, unsigned Alignment, const MDNode *TBAAInfo = 0); + SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, + SDValue Chain, SDValue Ptr, EVT MemVT, + MachineMemOperand *MMO); SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base, SDValue Offset, ISD::MemIndexedMode AM); SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, @@ -751,6 +809,10 @@ public: /// getMDNode - Return an MDNodeSDNode which holds an MDNode. SDValue getMDNode(const MDNode *MD); + /// getAddrSpaceCast - Return an AddrSpaceCastSDNode. + SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr, + unsigned SrcAS, unsigned DestAS); + /// getShiftAmountOperand - Return the specified value casted to /// the target's desired shift amount type. SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); @@ -1068,6 +1130,30 @@ public: /// it cannot be inferred. unsigned InferPtrAlignment(SDValue Ptr) const; + /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type + /// which is split (or expanded) into two not necessarily identical pieces. + std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; + + /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides + /// VTs and return the low/high part. + std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, + const EVT &LoVT, const EVT &HiVT); + + /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the + /// low/high part. + std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { + EVT LoVT, HiVT; + llvm::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); + return SplitVector(N, DL, LoVT, HiVT); + } + + /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and + /// return the low/high part. + std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) + { + return SplitVector(N->getOperand(OpNo), SDLoc(N)); + } + private: bool RemoveNodeFromCSEMaps(SDNode *N); void AddModifiedNodeToCSEMaps(SDNode *N); @@ -1086,7 +1172,7 @@ private: void allnodes_clear(); /// VTList - List of non-single value types. - std::vector<SDVTList> VTList; + FoldingSet<SDVTListNode> VTListMap; /// CondCodeNodes - Maps to auto-CSE operations. std::vector<CondCodeSDNode*> CondCodeNodes; diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index 3d55d3a..b5ec8cb 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -113,6 +113,8 @@ public: OPC_MoveChild, OPC_MoveParent, OPC_CheckSame, + OPC_CheckChild0Same, OPC_CheckChild1Same, + OPC_CheckChild2Same, OPC_CheckChild3Same, OPC_CheckPatternPredicate, OPC_CheckPredicate, OPC_CheckOpcode, diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 987f290..70c15e6 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -372,7 +372,7 @@ public: /// \<target\>ISD namespace). bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; } - /// isTargetMemoryOpcode - Test if this node has a target-specific + /// isTargetMemoryOpcode - Test if this node has a target-specific /// memory-referencing opcode (in the \<target\>ISD namespace and /// greater than FIRST_TARGET_MEMORY_OPCODE). bool isTargetMemoryOpcode() const { @@ -520,7 +520,9 @@ public: /// isPredecessorOf - Return true if this node is a predecessor of N. /// NOTE: Implemented on top of hasPredecessor and every bit as /// expensive. Use carefully. - bool isPredecessorOf(const SDNode *N) const { return N->hasPredecessor(this); } + bool isPredecessorOf(const SDNode *N) const { + return N->hasPredecessor(this); + } /// hasPredecessor - Return true if N is a predecessor of this node. /// N is either an operand of this node, or can be reached by recursively @@ -901,7 +903,8 @@ inline void SDUse::setNode(SDNode *N) { class UnarySDNode : public SDNode { SDUse Op; public: - UnarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X) + UnarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X) : SDNode(Opc, Order, dl, VTs) { InitOperands(&Op, X); } @@ -912,7 +915,8 @@ public: class BinarySDNode : public SDNode { SDUse Ops[2]; public: - BinarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X, SDValue Y) + BinarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X, SDValue Y) : SDNode(Opc, Order, dl, VTs) { InitOperands(Ops, X, Y); } @@ -938,13 +942,7 @@ public: class HandleSDNode : public SDNode { SDUse Op; public: - // FIXME: Remove the "noinline" attribute once <rdar://problem/5852746> is - // fixed. -#if __GNUC__==4 && __GNUC_MINOR__==2 && defined(__APPLE__) && !defined(__llvm__) - explicit __attribute__((__noinline__)) HandleSDNode(SDValue X) -#else explicit HandleSDNode(SDValue X) -#endif : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) { InitOperands(&Op, X); } @@ -952,6 +950,23 @@ public: const SDValue &getValue() const { return Op; } }; +class AddrSpaceCastSDNode : public UnarySDNode { +private: + unsigned SrcAddrSpace; + unsigned DestAddrSpace; + +public: + AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT, SDValue X, + unsigned SrcAS, unsigned DestAS); + + unsigned getSrcAddressSpace() const { return SrcAddrSpace; } + unsigned getDestAddressSpace() const { return DestAddrSpace; } + + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::ADDRSPACECAST; + } +}; + /// Abstact virtual class for operations for memory operations class MemSDNode : public SDNode { private: @@ -966,14 +981,15 @@ public: MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, EVT MemoryVT, MachineMemOperand *MMO); - MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, const SDValue *Ops, + MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + const SDValue *Ops, unsigned NumOps, EVT MemoryVT, MachineMemOperand *MMO); bool readMem() const { return MMO->isLoad(); } bool writeMem() const { return MMO->isStore(); } /// Returns alignment and volatility of the memory access - unsigned getOriginalAlignment() const { + unsigned getOriginalAlignment() const { return MMO->getBaseAlignment(); } unsigned getAlignment() const { @@ -1090,7 +1106,8 @@ public: // Swp: swap value // SrcVal: address to update as a Value (used for MemOperand) // Align: alignment of memory - AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) @@ -1098,7 +1115,8 @@ public: InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr, Cmp, Swp); } - AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Val, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) @@ -1106,7 +1124,8 @@ public: InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr, Val); } - AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) @@ -1114,6 +1133,16 @@ public: InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr); } + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT, + SDValue* AllOps, SDUse *DynOps, unsigned NumOps, + MachineMemOperand *MMO, + AtomicOrdering Ordering, SynchronizationScope SynchScope) + : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) { + InitAtomic(Ordering, SynchScope); + assert((DynOps || NumOps <= array_lengthof(Ops)) && + "Too many ops for internal storage!"); + InitOperands(DynOps ? DynOps : Ops, AllOps, NumOps); + } const SDValue &getBasePtr() const { return getOperand(1); } const SDValue &getVal() const { return getOperand(2); } @@ -1286,8 +1315,9 @@ class GlobalAddressSDNode : public SDNode { int64_t Offset; unsigned char TargetFlags; friend class SelectionDAG; - GlobalAddressSDNode(unsigned Opc, unsigned Order, DebugLoc DL, const GlobalValue *GA, EVT VT, - int64_t o, unsigned char TargetFlags); + GlobalAddressSDNode(unsigned Opc, unsigned Order, DebugLoc DL, + const GlobalValue *GA, EVT VT, int64_t o, + unsigned char TargetFlags); public: const GlobalValue *getGlobal() const { return TheGlobal; } @@ -1351,21 +1381,22 @@ class ConstantPoolSDNode : public SDNode { friend class SelectionDAG; ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o, unsigned Align, unsigned char TF) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(), - getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, + DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), + TargetFlags(TF) { assert(Offset >= 0 && "Offset is too large"); Val.ConstVal = c; } ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, EVT VT, int o, unsigned Align, unsigned char TF) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(), - getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, + DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), + TargetFlags(TF) { assert(Offset >= 0 && "Offset is too large"); Val.MachineCPVal = v; Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1); } public: - bool isMachineConstantPoolEntry() const { return Offset < 0; @@ -1427,8 +1458,8 @@ class BasicBlockSDNode : public SDNode { /// blocks out of order when they're jumped to, which makes it a bit /// harder. Let's see if we need it first. explicit BasicBlockSDNode(MachineBasicBlock *mbb) - : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) { - } + : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) + {} public: MachineBasicBlock *getBasicBlock() const { return MBB; } @@ -1481,22 +1512,22 @@ public: return N->getOpcode() == ISD::SRCVALUE; } }; - + class MDNodeSDNode : public SDNode { const MDNode *MD; friend class SelectionDAG; explicit MDNodeSDNode(const MDNode *md) - : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md) {} + : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md) + {} public: - + const MDNode *getMD() const { return MD; } - + static bool classof(const SDNode *N) { return N->getOpcode() == ISD::MDNODE_SDNODE; } }; - class RegisterSDNode : public SDNode { unsigned Reg; friend class SelectionDAG; @@ -1568,7 +1599,7 @@ public: class ExternalSymbolSDNode : public SDNode { const char *Symbol; unsigned char TargetFlags; - + friend class SelectionDAG; ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT) : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, @@ -1600,14 +1631,15 @@ public: return N->getOpcode() == ISD::CONDCODE; } }; - + /// CvtRndSatSDNode - NOTE: avoid using this node as this may disappear in the /// future and most targets don't support it. class CvtRndSatSDNode : public SDNode { ISD::CvtCode CvtCode; friend class SelectionDAG; - explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl, const SDValue *Ops, - unsigned NumOps, ISD::CvtCode Code) + explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl, + const SDValue *Ops, unsigned NumOps, + ISD::CvtCode Code) : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops, NumOps), CvtCode(Code) { assert(NumOps == 5 && "wrong number of operations"); @@ -1649,9 +1681,10 @@ class LSBaseSDNode : public MemSDNode { */ SDUse Ops[4]; public: - LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl, SDValue *Operands, - unsigned numOperands, SDVTList VTs, ISD::MemIndexedMode AM, - EVT MemVT, MachineMemOperand *MMO) + LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl, + SDValue *Operands, unsigned numOperands, + SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT, + MachineMemOperand *MMO) : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) { SubclassData |= AM << 2; assert(getAddressingMode() == AM && "MemIndexedMode encoding error!"); @@ -1840,7 +1873,7 @@ template <> struct GraphTraits<SDNode*> { /// LargestSDNode - The largest SDNode class. /// -typedef LoadSDNode LargestSDNode; +typedef AtomicSDNode LargestSDNode; /// MostAlignedSDNode - The SDNode class with the greatest alignment /// requirement. diff --git a/include/llvm/CodeGen/StackMaps.h b/include/llvm/CodeGen/StackMaps.h new file mode 100644 index 0000000..e90f22e --- /dev/null +++ b/include/llvm/CodeGen/StackMaps.h @@ -0,0 +1,175 @@ +//===------------------- StackMaps.h - StackMaps ----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_STACKMAPS +#define LLVM_STACKMAPS + +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/MachineInstr.h" +#include <map> +#include <vector> + +namespace llvm { + +class AsmPrinter; +class MCExpr; + +/// \brief MI-level patchpoint operands. +/// +/// MI patchpoint operations take the form: +/// [<def>], <id>, <numBytes>, <target>, <numArgs>, <cc>, ... +/// +/// IR patchpoint intrinsics do not have the <cc> operand because calling +/// convention is part of the subclass data. +/// +/// SD patchpoint nodes do not have a def operand because it is part of the +/// SDValue. +/// +/// Patchpoints following the anyregcc convention are handled specially. For +/// these, the stack map also records the location of the return value and +/// arguments. +class PatchPointOpers { +public: + /// Enumerate the meta operands. + enum { IDPos, NBytesPos, TargetPos, NArgPos, CCPos, MetaEnd }; +private: + const MachineInstr *MI; + bool HasDef; + bool IsAnyReg; +public: + explicit PatchPointOpers(const MachineInstr *MI); + + bool isAnyReg() const { return IsAnyReg; } + bool hasDef() const { return HasDef; } + + unsigned getMetaIdx(unsigned Pos = 0) const { + assert(Pos < MetaEnd && "Meta operand index out of range."); + return (HasDef ? 1 : 0) + Pos; + } + + const MachineOperand &getMetaOper(unsigned Pos) { + return MI->getOperand(getMetaIdx(Pos)); + } + + unsigned getArgIdx() const { return getMetaIdx() + MetaEnd; } + + /// Get the operand index of the variable list of non-argument operands. + /// These hold the "live state". + unsigned getVarIdx() const { + return getMetaIdx() + MetaEnd + + MI->getOperand(getMetaIdx(NArgPos)).getImm(); + } + + /// Get the index at which stack map locations will be recorded. + /// Arguments are not recorded unless the anyregcc convention is used. + unsigned getStackMapStartIdx() const { + if (IsAnyReg) + return getArgIdx(); + return getVarIdx(); + } + + /// \brief Get the next scratch register operand index. + unsigned getNextScratchIdx(unsigned StartIdx = 0) const; +}; + +class StackMaps { +public: + struct Location { + enum LocationType { Unprocessed, Register, Direct, Indirect, Constant, + ConstantIndex }; + LocationType LocType; + unsigned Size; + unsigned Reg; + int64_t Offset; + Location() : LocType(Unprocessed), Size(0), Reg(0), Offset(0) {} + Location(LocationType LocType, unsigned Size, unsigned Reg, int64_t Offset) + : LocType(LocType), Size(Size), Reg(Reg), Offset(Offset) {} + }; + + // Typedef a function pointer for functions that parse sequences of operands + // and return a Location, plus a new "next" operand iterator. + typedef std::pair<Location, MachineInstr::const_mop_iterator> + (*OperandParser)(MachineInstr::const_mop_iterator, + MachineInstr::const_mop_iterator, const TargetMachine&); + + // OpTypes are used to encode information about the following logical + // operand (which may consist of several MachineOperands) for the + // OpParser. + typedef enum { DirectMemRefOp, IndirectMemRefOp, ConstantOp } OpType; + + StackMaps(AsmPrinter &AP, OperandParser OpParser) + : AP(AP), OpParser(OpParser) {} + + /// \brief Generate a stackmap record for a stackmap instruction. + /// + /// MI must be a raw STACKMAP, not a PATCHPOINT. + void recordStackMap(const MachineInstr &MI); + + /// \brief Generate a stackmap record for a patchpoint instruction. + void recordPatchPoint(const MachineInstr &MI); + + /// If there is any stack map data, create a stack map section and serialize + /// the map info into it. This clears the stack map data structures + /// afterwards. + void serializeToStackMapSection(); + +private: + typedef SmallVector<Location, 8> LocationVec; + + struct CallsiteInfo { + const MCExpr *CSOffsetExpr; + unsigned ID; + LocationVec Locations; + CallsiteInfo() : CSOffsetExpr(0), ID(0) {} + CallsiteInfo(const MCExpr *CSOffsetExpr, unsigned ID, + LocationVec Locations) + : CSOffsetExpr(CSOffsetExpr), ID(ID), Locations(Locations) {} + }; + + typedef std::vector<CallsiteInfo> CallsiteInfoList; + + struct ConstantPool { + private: + typedef std::map<int64_t, size_t> ConstantsMap; + std::vector<int64_t> ConstantsList; + ConstantsMap ConstantIndexes; + + public: + size_t getNumConstants() const { return ConstantsList.size(); } + int64_t getConstant(size_t Idx) const { return ConstantsList[Idx]; } + size_t getConstantIndex(int64_t ConstVal) { + size_t NextIdx = ConstantsList.size(); + ConstantsMap::const_iterator I = + ConstantIndexes.insert(ConstantIndexes.end(), + std::make_pair(ConstVal, NextIdx)); + if (I->second == NextIdx) + ConstantsList.push_back(ConstVal); + return I->second; + } + }; + + AsmPrinter &AP; + OperandParser OpParser; + CallsiteInfoList CSInfos; + ConstantPool ConstPool; + + /// This should be called by the MC lowering code _immediately_ before + /// lowering the MI to an MCInst. It records where the operands for the + /// instruction are stored, and outputs a label to record the offset of + /// the call from the start of the text section. In special cases (e.g. AnyReg + /// calling convention) the return register is also recorded if requested. + void recordStackMapOpers(const MachineInstr &MI, uint32_t ID, + MachineInstr::const_mop_iterator MOI, + MachineInstr::const_mop_iterator MOE, + bool recordResult = false); +}; + +} + +#endif // LLVM_STACKMAPS diff --git a/include/llvm/CodeGen/StackProtector.h b/include/llvm/CodeGen/StackProtector.h new file mode 100644 index 0000000..d09a933 --- /dev/null +++ b/include/llvm/CodeGen/StackProtector.h @@ -0,0 +1,127 @@ +//===-- StackProtector.h - Stack Protector Insertion ----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass inserts stack protectors into functions which need them. A variable +// with a random value in it is stored onto the stack before the local variables +// are allocated. Upon exiting the block, the stored value is checked. If it's +// changed, then there was some sort of violation and the program aborts. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_STACKPROTECTOR_H +#define LLVM_CODEGEN_STACKPROTECTOR_H + +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Triple.h" +#include "llvm/ADT/ValueMap.h" +#include "llvm/Pass.h" +#include "llvm/Target/TargetLowering.h" + +namespace llvm { +class DominatorTree; +class Function; +class Module; +class PHINode; + +class StackProtector : public FunctionPass { +public: + /// SSPLayoutKind. Stack Smashing Protection (SSP) rules require that + /// vulnerable stack allocations are located close the stack protector. + enum SSPLayoutKind { + SSPLK_None, ///< Did not trigger a stack protector. No effect on data + ///< layout. + SSPLK_LargeArray, ///< Array or nested array >= SSP-buffer-size. Closest + ///< to the stack protector. + SSPLK_SmallArray, ///< Array or nested array < SSP-buffer-size. 2nd closest + ///< to the stack protector. + SSPLK_AddrOf ///< The address of this allocation is exposed and + ///< triggered protection. 3rd closest to the protector. + }; + + /// A mapping of AllocaInsts to their required SSP layout. + typedef ValueMap<const AllocaInst *, SSPLayoutKind> SSPLayoutMap; + +private: + const TargetMachine *TM; + + /// TLI - Keep a pointer of a TargetLowering to consult for determining + /// target type sizes. + const TargetLoweringBase *TLI; + const Triple Trip; + + Function *F; + Module *M; + + DominatorTree *DT; + + /// Layout - Mapping of allocations to the required SSPLayoutKind. + /// StackProtector analysis will update this map when determining if an + /// AllocaInst triggers a stack protector. + SSPLayoutMap Layout; + + /// \brief The minimum size of buffers that will receive stack smashing + /// protection when -fstack-protection is used. + unsigned SSPBufferSize; + + /// VisitedPHIs - The set of PHI nodes visited when determining + /// if a variable's reference has been taken. This set + /// is maintained to ensure we don't visit the same PHI node multiple + /// times. + SmallPtrSet<const PHINode *, 16> VisitedPHIs; + + /// InsertStackProtectors - Insert code into the prologue and epilogue of + /// the function. + /// + /// - The prologue code loads and stores the stack guard onto the stack. + /// - The epilogue checks the value stored in the prologue against the + /// original value. It calls __stack_chk_fail if they differ. + bool InsertStackProtectors(); + + /// CreateFailBB - Create a basic block to jump to when the stack protector + /// check fails. + BasicBlock *CreateFailBB(); + + /// ContainsProtectableArray - Check whether the type either is an array or + /// contains an array of sufficient size so that we need stack protectors + /// for it. + /// \param [out] IsLarge is set to true if a protectable array is found and + /// it is "large" ( >= ssp-buffer-size). In the case of a structure with + /// multiple arrays, this gets set if any of them is large. + bool ContainsProtectableArray(Type *Ty, bool &IsLarge, bool Strong = false, + bool InStruct = false) const; + + /// \brief Check whether a stack allocation has its address taken. + bool HasAddressTaken(const Instruction *AI); + + /// RequiresStackProtector - Check whether or not this function needs a + /// stack protector based upon the stack protector level. + bool RequiresStackProtector(); + +public: + static char ID; // Pass identification, replacement for typeid. + StackProtector() : FunctionPass(ID), TM(0), TLI(0), SSPBufferSize(0) { + initializeStackProtectorPass(*PassRegistry::getPassRegistry()); + } + StackProtector(const TargetMachine *TM) + : FunctionPass(ID), TM(TM), TLI(0), Trip(TM->getTargetTriple()), + SSPBufferSize(8) { + initializeStackProtectorPass(*PassRegistry::getPassRegistry()); + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreserved<DominatorTree>(); + } + + SSPLayoutKind getSSPLayout(const AllocaInst *AI) const; + + virtual bool runOnFunction(Function &Fn); +}; +} // end namespace llvm + +#endif // LLVM_CODEGEN_STACKPROTECTOR_H diff --git a/include/llvm/CodeGen/TargetSchedule.h b/include/llvm/CodeGen/TargetSchedule.h index f2adcf8..8ef26b7 100644 --- a/include/llvm/CodeGen/TargetSchedule.h +++ b/include/llvm/CodeGen/TargetSchedule.h @@ -152,7 +152,13 @@ public: /// Compute and return the expected latency of this instruction independent of /// a particular use. computeOperandLatency is the prefered API, but this is /// occasionally useful to help estimate instruction cost. - unsigned computeInstrLatency(const MachineInstr *MI) const; + /// + /// If UseDefaultDefLatency is false and no new machine sched model is + /// present this method falls back to TII->getInstrLatency with an empty + /// instruction itinerary (this is so we preserve the previous behavior of the + /// if converter after moving it to TargetSchedModel). + unsigned computeInstrLatency(const MachineInstr *MI, + bool UseDefaultDefLatency = true) const; /// \brief Output dependency latency of a pair of defs of the same register. /// diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index b7b3d73..79f3233 100644 --- a/include/llvm/CodeGen/ValueTypes.h +++ b/include/llvm/CodeGen/ValueTypes.h @@ -27,9 +27,9 @@ namespace llvm { class LLVMContext; struct EVT; - /// MVT - Machine Value Type. Every type that is supported natively by some - /// processor targeted by LLVM occurs here. This means that any legal value - /// type can be represented by a MVT. + /// MVT - Machine Value Type. Every type that is supported natively by some + /// processor targeted by LLVM occurs here. This means that any legal value + /// type can be represented by an MVT. class MVT { public: enum SimpleValueType { @@ -67,40 +67,45 @@ namespace llvm { v32i1 = 17, // 32 x i1 v64i1 = 18, // 64 x i1 - v2i8 = 19, // 2 x i8 - v4i8 = 20, // 4 x i8 - v8i8 = 21, // 8 x i8 - v16i8 = 22, // 16 x i8 - v32i8 = 23, // 32 x i8 - v64i8 = 24, // 64 x i8 - v1i16 = 25, // 1 x i16 - v2i16 = 26, // 2 x i16 - v4i16 = 27, // 4 x i16 - v8i16 = 28, // 8 x i16 - v16i16 = 29, // 16 x i16 - v32i16 = 30, // 32 x i16 - v1i32 = 31, // 1 x i32 - v2i32 = 32, // 2 x i32 - v4i32 = 33, // 4 x i32 - v8i32 = 34, // 8 x i32 - v16i32 = 35, // 16 x i32 - v1i64 = 36, // 1 x i64 - v2i64 = 37, // 2 x i64 - v4i64 = 38, // 4 x i64 - v8i64 = 39, // 8 x i64 - v16i64 = 40, // 16 x i64 + v1i8 = 19, // 1 x i8 + v2i8 = 20, // 2 x i8 + v4i8 = 21, // 4 x i8 + v8i8 = 22, // 8 x i8 + v16i8 = 23, // 16 x i8 + v32i8 = 24, // 32 x i8 + v64i8 = 25, // 64 x i8 + v1i16 = 26, // 1 x i16 + v2i16 = 27, // 2 x i16 + v4i16 = 28, // 4 x i16 + v8i16 = 29, // 8 x i16 + v16i16 = 30, // 16 x i16 + v32i16 = 31, // 32 x i16 + v1i32 = 32, // 1 x i32 + v2i32 = 33, // 2 x i32 + v4i32 = 34, // 4 x i32 + v8i32 = 35, // 8 x i32 + v16i32 = 36, // 16 x i32 + v1i64 = 37, // 1 x i64 + v2i64 = 38, // 2 x i64 + v4i64 = 39, // 4 x i64 + v8i64 = 40, // 8 x i64 + v16i64 = 41, // 16 x i64 FIRST_INTEGER_VECTOR_VALUETYPE = v2i1, LAST_INTEGER_VECTOR_VALUETYPE = v16i64, - v2f16 = 41, // 2 x f16 - v2f32 = 42, // 2 x f32 - v4f32 = 43, // 4 x f32 - v8f32 = 44, // 8 x f32 - v16f32 = 45, // 16 x f32 - v2f64 = 46, // 2 x f64 - v4f64 = 47, // 4 x f64 - v8f64 = 48, // 8 x f64 + v2f16 = 42, // 2 x f16 + v4f16 = 43, // 4 x f16 + v8f16 = 44, // 8 x f16 + v1f32 = 45, // 1 x f32 + v2f32 = 46, // 2 x f32 + v4f32 = 47, // 4 x f32 + v8f32 = 48, // 8 x f32 + v16f32 = 49, // 16 x f32 + v1f64 = 50, // 1 x f64 + v2f64 = 51, // 2 x f64 + v4f64 = 52, // 4 x f64 + v8f64 = 53, // 8 x f64 FIRST_FP_VECTOR_VALUETYPE = v2f16, LAST_FP_VECTOR_VALUETYPE = v8f64, @@ -108,17 +113,17 @@ namespace llvm { FIRST_VECTOR_VALUETYPE = v2i1, LAST_VECTOR_VALUETYPE = v8f64, - x86mmx = 49, // This is an X86 MMX value + x86mmx = 54, // This is an X86 MMX value - Glue = 50, // This glues nodes together during pre-RA sched + Glue = 55, // This glues nodes together during pre-RA sched - isVoid = 51, // This has no value + isVoid = 56, // This has no value - Untyped = 52, // This value takes a register, but has + Untyped = 57, // This value takes a register, but has // unspecified type. The register class // will be determined by the opcode. - LAST_VALUETYPE = 53, // This always remains at the end of the list. + LAST_VALUETYPE = 58, // This always remains at the end of the list. // This is the current maximum for LAST_VALUETYPE. // MVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors @@ -203,7 +208,7 @@ namespace llvm { bool is64BitVector() const { return (SimpleTy == MVT::v8i8 || SimpleTy == MVT::v4i16 || SimpleTy == MVT::v2i32 || SimpleTy == MVT::v1i64 || - SimpleTy == MVT::v2f32); + SimpleTy == MVT::v1f64 || SimpleTy == MVT::v2f32); } /// is128BitVector - Return true if this is a 128-bit vector type. @@ -265,6 +270,7 @@ namespace llvm { case v16i1 : case v32i1 : case v64i1: return i1; + case v1i8 : case v2i8 : case v4i8 : case v8i8 : @@ -287,11 +293,15 @@ namespace llvm { case v4i64: case v8i64: case v16i64: return i64; - case v2f16: return f16; + case v2f16: + case v4f16: + case v8f16: return f16; + case v1f32: case v2f32: case v4f32: case v8f32: case v16f32: return f32; + case v1f64: case v2f64: case v4f64: case v8f64: return f64; @@ -318,6 +328,7 @@ namespace llvm { case v8i16: case v8i32: case v8i64: + case v8f16: case v8f32: case v8f64: return 8; case v4i1: @@ -325,6 +336,7 @@ namespace llvm { case v4i16: case v4i32: case v4i64: + case v4f16: case v4f32: case v4f64: return 4; case v2i1: @@ -335,9 +347,12 @@ namespace llvm { case v2f16: case v2f32: case v2f64: return 2; + case v1i8: case v1i16: case v1i32: - case v1i64: return 1; + case v1i64: + case v1f32: + case v1f64: return 1; } } @@ -360,6 +375,7 @@ namespace llvm { case v2i1: return 2; case v4i1: return 4; case i8 : + case v1i8: case v8i1: return 8; case i16 : case f16: @@ -372,6 +388,7 @@ namespace llvm { case v4i8: case v2i16: case v2f16: + case v1f32: case v1i32: return 32; case x86mmx: case f64 : @@ -381,7 +398,9 @@ namespace llvm { case v4i16: case v2i32: case v1i64: - case v2f32: return 64; + case v4f16: + case v2f32: + case v1f64: return 64; case f80 : return 80; case f128: case ppcf128: @@ -390,6 +409,7 @@ namespace llvm { case v8i16: case v4i32: case v2i64: + case v8f16: case v4f32: case v2f64: return 128; case v32i8: @@ -490,6 +510,7 @@ namespace llvm { if (NumElements == 64) return MVT::v64i1; break; case MVT::i8: + if (NumElements == 1) return MVT::v1i8; if (NumElements == 2) return MVT::v2i8; if (NumElements == 4) return MVT::v4i8; if (NumElements == 8) return MVT::v8i8; @@ -521,14 +542,18 @@ namespace llvm { break; case MVT::f16: if (NumElements == 2) return MVT::v2f16; + if (NumElements == 4) return MVT::v4f16; + if (NumElements == 8) return MVT::v8f16; break; case MVT::f32: + if (NumElements == 1) return MVT::v1f32; if (NumElements == 2) return MVT::v2f32; if (NumElements == 4) return MVT::v4f32; if (NumElements == 8) return MVT::v8f32; if (NumElements == 16) return MVT::v16f32; break; case MVT::f64: + if (NumElements == 1) return MVT::v1f64; if (NumElements == 2) return MVT::v2f64; if (NumElements == 4) return MVT::v4f64; if (NumElements == 8) return MVT::v8f64; diff --git a/include/llvm/CodeGen/ValueTypes.td b/include/llvm/CodeGen/ValueTypes.td index da26985..b5fa0e8 100644 --- a/include/llvm/CodeGen/ValueTypes.td +++ b/include/llvm/CodeGen/ValueTypes.td @@ -26,7 +26,7 @@ def i16 : ValueType<16 , 3>; // 16-bit integer value def i32 : ValueType<32 , 4>; // 32-bit integer value def i64 : ValueType<64 , 5>; // 64-bit integer value def i128 : ValueType<128, 6>; // 128-bit integer value -def f16 : ValueType<16 , 7>; // 32-bit floating point value +def f16 : ValueType<16 , 7>; // 16-bit floating point value def f32 : ValueType<32 , 8>; // 32-bit floating point value def f64 : ValueType<64 , 9>; // 64-bit floating point value def f80 : ValueType<80 , 10>; // 80-bit floating point value @@ -39,43 +39,48 @@ def v8i1 : ValueType<8 , 15>; // 8 x i1 vector value def v16i1 : ValueType<16, 16>; // 16 x i1 vector value def v32i1 : ValueType<32 , 17>; // 32 x i1 vector value def v64i1 : ValueType<64 , 18>; // 64 x i1 vector value -def v2i8 : ValueType<16 , 19>; // 2 x i8 vector value -def v4i8 : ValueType<32 , 20>; // 4 x i8 vector value -def v8i8 : ValueType<64 , 21>; // 8 x i8 vector value -def v16i8 : ValueType<128, 22>; // 16 x i8 vector value -def v32i8 : ValueType<256, 23>; // 32 x i8 vector value -def v64i8 : ValueType<512, 24>; // 64 x i8 vector value -def v1i16 : ValueType<16 , 25>; // 1 x i16 vector value -def v2i16 : ValueType<32 , 26>; // 2 x i16 vector value -def v4i16 : ValueType<64 , 27>; // 4 x i16 vector value -def v8i16 : ValueType<128, 28>; // 8 x i16 vector value -def v16i16 : ValueType<256, 29>; // 16 x i16 vector value -def v32i16 : ValueType<512, 30>; // 32 x i16 vector value -def v1i32 : ValueType<32 , 31>; // 1 x i32 vector value -def v2i32 : ValueType<64 , 32>; // 2 x i32 vector value -def v4i32 : ValueType<128, 33>; // 4 x i32 vector value -def v8i32 : ValueType<256, 34>; // 8 x i32 vector value -def v16i32 : ValueType<512, 35>; // 16 x i32 vector value -def v1i64 : ValueType<64 , 36>; // 1 x i64 vector value -def v2i64 : ValueType<128, 37>; // 2 x i64 vector value -def v4i64 : ValueType<256, 38>; // 4 x i64 vector value -def v8i64 : ValueType<512, 39>; // 8 x i64 vector value -def v16i64 : ValueType<1024,40>; // 16 x i64 vector value +def v1i8 : ValueType<16, 19>; // 1 x i8 vector value +def v2i8 : ValueType<16 , 20>; // 2 x i8 vector value +def v4i8 : ValueType<32 , 21>; // 4 x i8 vector value +def v8i8 : ValueType<64 , 22>; // 8 x i8 vector value +def v16i8 : ValueType<128, 23>; // 16 x i8 vector value +def v32i8 : ValueType<256, 24>; // 32 x i8 vector value +def v64i8 : ValueType<512, 25>; // 64 x i8 vector value +def v1i16 : ValueType<16 , 26>; // 1 x i16 vector value +def v2i16 : ValueType<32 , 27>; // 2 x i16 vector value +def v4i16 : ValueType<64 , 28>; // 4 x i16 vector value +def v8i16 : ValueType<128, 29>; // 8 x i16 vector value +def v16i16 : ValueType<256, 30>; // 16 x i16 vector value +def v32i16 : ValueType<512, 31>; // 32 x i16 vector value +def v1i32 : ValueType<32 , 32>; // 1 x i32 vector value +def v2i32 : ValueType<64 , 33>; // 2 x i32 vector value +def v4i32 : ValueType<128, 34>; // 4 x i32 vector value +def v8i32 : ValueType<256, 35>; // 8 x i32 vector value +def v16i32 : ValueType<512, 36>; // 16 x i32 vector value +def v1i64 : ValueType<64 , 37>; // 1 x i64 vector value +def v2i64 : ValueType<128, 38>; // 2 x i64 vector value +def v4i64 : ValueType<256, 39>; // 4 x i64 vector value +def v8i64 : ValueType<512, 40>; // 8 x i64 vector value +def v16i64 : ValueType<1024,41>; // 16 x i64 vector value -def v2f16 : ValueType<32 , 41>; // 2 x f16 vector value -def v2f32 : ValueType<64 , 42>; // 2 x f32 vector value -def v4f32 : ValueType<128, 43>; // 4 x f32 vector value -def v8f32 : ValueType<256, 44>; // 8 x f32 vector value -def v16f32 : ValueType<512, 45>; // 16 x f32 vector value -def v2f64 : ValueType<128, 46>; // 2 x f64 vector value -def v4f64 : ValueType<256, 47>; // 4 x f64 vector value -def v8f64 : ValueType<512, 48>; // 8 x f64 vector value +def v2f16 : ValueType<32 , 42>; // 2 x f16 vector value +def v4f16 : ValueType<64 , 43>; // 4 x f16 vector value +def v8f16 : ValueType<128, 44>; // 8 x f16 vector value +def v1f32 : ValueType<32 , 45>; // 1 x f32 vector value +def v2f32 : ValueType<64 , 46>; // 2 x f32 vector value +def v4f32 : ValueType<128, 47>; // 4 x f32 vector value +def v8f32 : ValueType<256, 48>; // 8 x f32 vector value +def v16f32 : ValueType<512, 49>; // 16 x f32 vector value +def v1f64 : ValueType<64, 50>; // 1 x f64 vector value +def v2f64 : ValueType<128, 51>; // 2 x f64 vector value +def v4f64 : ValueType<256, 52>; // 4 x f64 vector value +def v8f64 : ValueType<512, 53>; // 8 x f64 vector value -def x86mmx : ValueType<64 , 49>; // X86 MMX value -def FlagVT : ValueType<0 , 50>; // Pre-RA sched glue -def isVoid : ValueType<0 , 51>; // Produces no value -def untyped: ValueType<8 , 52>; // Produces an untyped value +def x86mmx : ValueType<64 , 54>; // X86 MMX value +def FlagVT : ValueType<0 , 55>; // Pre-RA sched glue +def isVoid : ValueType<0 , 56>; // Produces no value +def untyped: ValueType<8 , 57>; // Produces an untyped value def MetadataVT: ValueType<0, 250>; // Metadata // Pseudo valuetype mapped to the current pointer size to any address space. |