X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FRegisterPressure.h;h=9bbdf3e071bd641ceafb9cc220c06666e7f11f3b;hp=bbc8ca5d28f485b9c2a4545a09c5dfb5360c3d8c;hb=HEAD;hpb=13372886a6d387c8847143744f26790a250f4360 diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h index bbc8ca5d28f..9bbdf3e071b 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; @@ -35,21 +35,6 @@ struct RegisterPressure { SmallVector LiveInRegs; SmallVector LiveOutRegs; - /// Increase register pressure for each pressure set impacted by this register - /// class. Normally called by RegPressureTracker, but may be called manually - /// to account for live through (global liveness). - /// - /// \param Reg is either a virtual register number or register unit number. - void increase(unsigned Reg, const TargetRegisterInfo *TRI, - const MachineRegisterInfo *MRI); - - /// Decrease register pressure for each pressure set impacted by this register - /// class. This is only useful to account for spilling or rematerialization. - /// - /// \param Reg is either a virtual register number or register unit number. - void decrease(unsigned Reg, const TargetRegisterInfo *TRI, - const MachineRegisterInfo *MRI); - void dump(const TargetRegisterInfo *TRI) const; }; @@ -89,20 +74,119 @@ 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; } + + void setUnitInc(int Inc) { UnitInc = Inc; } + + bool operator==(const PressureChange &RHS) const { + return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; + } +}; + +template <> struct isPodLike { + 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]; + + typedef PressureChange* iterator; + iterator nonconst_begin() { return &PressureChanges[0]; } + iterator nonconst_end() { return &PressureChanges[MaxPSets]; } + +public: + typedef const PressureChange* const_iterator; + const_iterator begin() const { return &PressureChanges[0]; } + const_iterator end() const { return &PressureChanges[MaxPSets]; } + + void addPressureChange(unsigned RegUnit, bool IsDec, + const MachineRegisterInfo *MRI); + + LLVM_DUMP_METHOD void dump(const TargetRegisterInfo &TRI) const; +}; + +/// List of registers defined and used by a machine instruction. +class RegisterOperands { +public: + /// List of virtual regiserts and register units read by the instruction. + SmallVector Uses; + /// \brief List of virtual registers and register units defined by the + /// instruction which are not dead. + SmallVector Defs; + /// \brief List of virtual registers and register units defined by the + /// instruction but dead. + SmallVector DeadDefs; + + /// Analyze the given instruction \p MI and fill in the Uses, Defs and + /// DeadDefs list based on the MachineOperand flags. + void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, + const MachineRegisterInfo &MRI, bool IgnoreDead = false); + + /// Use liveness information to find dead defs not marked with a dead flag + /// and move them to the DeadDefs vector. + void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS); +}; + +/// Array of PressureDiffs. +class PressureDiffs { + PressureDiff *PDiffArray; + unsigned Size; + unsigned Max; +public: + PressureDiffs(): PDiffArray(nullptr), Size(0), Max(0) {} + ~PressureDiffs() { free(PDiffArray); } - PressureElement(): PSetID(~0U), UnitIncrease(0) {} - PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {} + void clear() { Size = 0; } - bool isValid() const { return PSetID != ~0U; } + void init(unsigned N); - // 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; } + PressureDiff &operator[](unsigned Idx) { + assert(Idx < Size && "PressureDiff index out of bounds"); + return PDiffArray[Idx]; + } + const PressureDiff &operator[](unsigned Idx) const { + return const_cast(this)->operator[](Idx); + } + /// \brief Record pressure difference induced by the given operand list to + /// node with index \p Idx. + void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, + const MachineRegisterInfo &MRI); }; /// Store the effects of a change in pressure on things that MI scheduler cares @@ -120,37 +204,71 @@ 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. +/// A set of live virtual registers and physical register units. /// -/// Virtual and physical register numbers require separate sparse sets, but most -/// of the RegisterPressureTracker handles them uniformly. -struct LiveRegSet { - SparseSet PhysRegs; - SparseSet VirtRegs; - - bool contains(unsigned Reg) { +/// This is a wrapper around a SparseSet which deals with mapping register unit +/// and virtual register indexes to an index usable by the sparse set. +class LiveRegSet { +private: + SparseSet Regs; + unsigned NumRegUnits; + + unsigned getSparseIndexFromReg(unsigned Reg) const { if (TargetRegisterInfo::isVirtualRegister(Reg)) - return VirtRegs.count(Reg); - return PhysRegs.count(Reg); + return TargetRegisterInfo::virtReg2Index(Reg) + NumRegUnits; + assert(Reg < NumRegUnits); + return Reg; + } + unsigned getRegFromSparseIndex(unsigned SparseIndex) const { + if (SparseIndex >= NumRegUnits) + return TargetRegisterInfo::index2VirtReg(SparseIndex-NumRegUnits); + return SparseIndex; + } + +public: + void clear(); + void init(const MachineRegisterInfo &MRI); + + bool contains(unsigned Reg) const { + unsigned SparseIndex = getSparseIndexFromReg(Reg); + return Regs.count(SparseIndex); } bool insert(unsigned Reg) { - if (TargetRegisterInfo::isVirtualRegister(Reg)) - return VirtRegs.insert(Reg).second; - return PhysRegs.insert(Reg).second; + unsigned SparseIndex = getSparseIndexFromReg(Reg); + return Regs.insert(SparseIndex).second; } bool erase(unsigned Reg) { - if (TargetRegisterInfo::isVirtualRegister(Reg)) - return VirtRegs.erase(Reg); - return PhysRegs.erase(Reg); + unsigned SparseIndex = getSparseIndexFromReg(Reg); + return Regs.erase(SparseIndex); + } + + size_t size() const { + return Regs.size(); + } + + template + void appendTo(ContainerT &To) const { + for (unsigned I : Regs) { + unsigned Reg = getRegFromSparseIndex(I); + To.push_back(Reg); + } } }; @@ -187,6 +305,9 @@ class RegPressureTracker { /// or RegisterPressure. If requireIntervals is false, LIS are ignored. bool RequireIntervals; + /// True if UntiedDefs will be populated. + bool TrackUntiedDefs; + /// Register pressure corresponds to liveness before this instruction /// iterator. It may point to the end of the block or a DebugValue rather than /// an instruction. @@ -198,16 +319,26 @@ class RegPressureTracker { /// Set of live registers. LiveRegSet LiveRegs; + /// Set of vreg defs that start a live range. + SparseSet UntiedDefs; + /// Live-through pressure. + std::vector LiveThruPressure; + public: RegPressureTracker(IntervalPressure &rp) : - MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true) {} + MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp), + RequireIntervals(true), TrackUntiedDefs(false) {} RegPressureTracker(RegionPressure &rp) : - MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false) {} + MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), 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); + MachineBasicBlock::const_iterator pos, + bool ShouldTrackUntiedDefs = false); /// Force liveness of virtual registers or physical register /// units. Particularly useful to initialize the livein/out state of the @@ -223,31 +354,46 @@ public: // position changes while pressure does not. void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } - /// \brief Get the SlotIndex for the first nondebug instruction including or - /// after the current position. - SlotIndex getCurrSlot() const; + /// Recede across the previous instruction. + void recede(SmallVectorImpl *LiveUses = nullptr); /// Recede across the previous instruction. - bool recede(); + /// This "low-level" variant assumes that recedeSkipDebugValues() was + /// called previously and takes precomputed RegisterOperands for the + /// instruction. + void recede(const RegisterOperands &RegOpers, + SmallVectorImpl *LiveUses = nullptr); + + /// Recede until we find an instruction which is not a DebugValue. + void recedeSkipDebugValues(); /// Advance across the current instruction. - bool advance(); + void advance(); /// Finalize the region boundaries and recored live ins and live outs. void closeRegion(); + /// Initialize the LiveThru pressure set based on the untied defs found in + /// RPTracker. + void initLiveThru(const RegPressureTracker &RPTracker); + + /// Copy an existing live thru pressure result. + void initLiveThru(ArrayRef PressureSet) { + LiveThruPressure.assign(PressureSet.begin(), PressureSet.end()); + } + + ArrayRef getLiveThru() const { return LiveThruPressure; } + /// Get the resulting register pressure over the traversed region. - /// This result is complete if either advance() or recede() has returned true, - /// or if closeRegion() was explicitly invoked. + /// This result is complete if closeRegion() was explicitly invoked. RegisterPressure &getPressure() { return P; } const RegisterPressure &getPressure() const { return P; } /// Get the register set pressure at the current position, which may be less /// than the pressure across the traversed region. - std::vector &getRegSetPressureAtPos() { return CurrSetPressure; } - - void discoverLiveOut(unsigned Reg); - void discoverLiveIn(unsigned Reg); + const std::vector &getRegSetPressureAtPos() const { + return CurrSetPressure; + } bool isTopClosed() const; bool isBottomClosed() const; @@ -260,31 +406,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 CriticalPSets, + ArrayRef CriticalPSets, ArrayRef MaxPressureLimit); + void getUpwardPressureDelta(const MachineInstr *MI, + /*const*/ PressureDiff &PDiff, + RegPressureDelta &Delta, + ArrayRef CriticalPSets, + ArrayRef 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 CriticalPSets, + ArrayRef CriticalPSets, ArrayRef 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 CriticalPSets, + void getMaxPressureDelta(const MachineInstr *MI, + RegPressureDelta &Delta, + ArrayRef CriticalPSets, ArrayRef MaxPressureLimit) { if (isTopClosed()) return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, MaxPressureLimit); assert(isBottomClosed() && "Uninitialized pressure tracker"); - return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, + return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets, MaxPressureLimit); } @@ -308,10 +462,19 @@ public: return getDownwardPressure(MI, PressureResult, MaxPressureResult); } + bool hasUntiedDef(unsigned VirtReg) const { + return UntiedDefs.count(VirtReg); + } + void dump() const; protected: - const LiveInterval *getInterval(unsigned Reg) const; + void discoverLiveOut(unsigned Reg); + void discoverLiveIn(unsigned Reg); + + /// \brief Get the SlotIndex for the first nondebug instruction including or + /// after the current position. + SlotIndex getCurrSlot() const; void increaseRegPressure(ArrayRef Regs); void decreaseRegPressure(ArrayRef Regs); @@ -319,6 +482,9 @@ protected: void bumpUpwardPressure(const MachineInstr *MI); void bumpDownwardPressure(const MachineInstr *MI); }; + +void dumpRegSetPressure(ArrayRef SetPressure, + const TargetRegisterInfo *TRI); } // end namespace llvm #endif