| //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// |
| // |
| // The Subzero Code Generator |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// \brief Declares the LinearScan data structure used during linear-scan |
| /// register allocation. |
| /// |
| /// This holds the various work queues for the linear-scan algorithm. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SUBZERO_SRC_ICEREGALLOC_H |
| #define SUBZERO_SRC_ICEREGALLOC_H |
| |
| #include "IceDefs.h" |
| #include "IceBitVector.h" |
| #include "IceOperand.h" |
| #include "IceTypes.h" |
| |
| namespace Ice { |
| |
| class LinearScan { |
| LinearScan() = delete; |
| LinearScan(const LinearScan &) = delete; |
| LinearScan &operator=(const LinearScan &) = delete; |
| |
| public: |
| explicit LinearScan(Cfg *Func); |
| void init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars); |
| void scan(const SmallBitVector &RegMask, bool Randomized); |
| // Returns the number of times some variable has been assigned a register but |
| // later evicted because of a higher-priority allocation. The idea is that we |
| // can implement "second-chance bin-packing" by rerunning register allocation |
| // until there are no more evictions. |
| SizeT getNumEvictions() const { return Evicted.size(); } |
| bool hasEvictions() const { return !Evicted.empty(); } |
| void dump(Cfg *Func) const; |
| |
| // TODO(stichnot): Statically choose the size based on the target being |
| // compiled. For now, choose a value large enough to fit into the |
| // SmallVector's fixed portion, which is 32 for x86-32, 84 for x86-64, and 102 |
| // for ARM32. |
| static constexpr size_t REGS_SIZE = 128; |
| |
| private: |
| using OrderedRanges = CfgVector<Variable *>; |
| using UnorderedRanges = CfgVector<Variable *>; |
| using DefUseErrorList = llvm::SmallVector<SizeT, 10>; |
| |
| class IterationState { |
| IterationState(const IterationState &) = delete; |
| IterationState operator=(const IterationState &) = delete; |
| |
| public: |
| IterationState() = default; |
| Variable *Cur = nullptr; |
| Variable *Prefer = nullptr; |
| RegNumT PreferReg; |
| bool AllowOverlap = false; |
| SmallBitVector RegMask; |
| SmallBitVector RegMaskUnfiltered; |
| SmallBitVector Free; |
| SmallBitVector FreeUnfiltered; |
| SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping |
| llvm::SmallVector<RegWeight, REGS_SIZE> Weights; |
| }; |
| |
| bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses, |
| const DefUseErrorList &UsesBeforeDefs, |
| const CfgVector<InstNumberT> &LRBegin, |
| const CfgVector<InstNumberT> &LREnd) const; |
| void initForGlobal(); |
| void initForInfOnly(); |
| void initForSecondChance(); |
| /// Move an item from the From set to the To set. From[Index] is pushed onto |
| /// the end of To[], then the item is efficiently removed from From[] by |
| /// effectively swapping it with the last item in From[] and then popping it |
| /// from the back. As such, the caller is best off iterating over From[] in |
| /// reverse order to avoid the need for special handling of the iterator. |
| void moveItem(UnorderedRanges &From, SizeT Index, UnorderedRanges &To) { |
| To.push_back(From[Index]); |
| From[Index] = From.back(); |
| From.pop_back(); |
| } |
| |
| /// \name scan helper functions. |
| /// @{ |
| /// Free up a register for infinite-weight Cur by spilling and reloading some |
| /// register that isn't used during Cur's live range. |
| void addSpillFill(IterationState &Iter); |
| /// Check for active ranges that have expired or become inactive. |
| void handleActiveRangeExpiredOrInactive(const Variable *Cur); |
| /// Check for inactive ranges that have expired or reactivated. |
| void handleInactiveRangeExpiredOrReactivated(const Variable *Cur); |
| void findRegisterPreference(IterationState &Iter); |
| void filterFreeWithInactiveRanges(IterationState &Iter); |
| void filterFreeWithPrecoloredRanges(IterationState &Iter); |
| void allocatePrecoloredRegister(Variable *Cur); |
| void allocatePreferredRegister(IterationState &Iter); |
| void allocateFreeRegister(IterationState &Iter, bool Filtered); |
| void handleNoFreeRegisters(IterationState &Iter); |
| void assignFinalRegisters(const SmallBitVector &RegMaskFull, |
| const SmallBitVector &PreDefinedRegisters, |
| bool Randomized); |
| /// @} |
| |
| void dumpLiveRangeTrace(const char *Label, const Variable *Item); |
| |
| Cfg *const Func; |
| GlobalContext *const Ctx; |
| TargetLowering *const Target; |
| |
| OrderedRanges Unhandled; |
| /// UnhandledPrecolored is a subset of Unhandled, specially collected for |
| /// faster processing. |
| OrderedRanges UnhandledPrecolored; |
| UnorderedRanges Active, Inactive, Handled; |
| UnorderedRanges Evicted; |
| CfgVector<InstNumberT> Kills; |
| RegAllocKind Kind = RAK_Unknown; |
| /// RegUses[I] is the number of live ranges (variables) that register I is |
| /// currently assigned to. It can be greater than 1 as a result of |
| /// AllowOverlap inference. |
| llvm::SmallVector<int32_t, REGS_SIZE> RegUses; |
| llvm::SmallVector<const SmallBitVector *, REGS_SIZE> RegAliases; |
| bool FindPreference = false; |
| bool FindOverlap = false; |
| const bool Verbose; |
| const bool UseReserve; |
| CfgVector<Variable *> Vars; |
| }; |
| |
| } // end of namespace Ice |
| |
| #endif // SUBZERO_SRC_ICEREGALLOC_H |