1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// 2 // 3 // The Subzero Code Generator 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// \brief Declares the LinearScan data structure used during linear-scan 12 /// register allocation. 13 /// 14 /// This holds the various work queues for the linear-scan algorithm. 15 /// 16 //===----------------------------------------------------------------------===// 17 18 #ifndef SUBZERO_SRC_ICEREGALLOC_H 19 #define SUBZERO_SRC_ICEREGALLOC_H 20 21 #include "IceBitVector.h" 22 #include "IceDefs.h" 23 #include "IceOperand.h" 24 #include "IceTypes.h" 25 26 namespace Ice { 27 28 class LinearScan { 29 LinearScan() = delete; 30 LinearScan(const LinearScan &) = delete; 31 LinearScan &operator=(const LinearScan &) = delete; 32 33 public: 34 explicit LinearScan(Cfg *Func); 35 void init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars); 36 void scan(const SmallBitVector &RegMask); 37 // Returns the number of times some variable has been assigned a register but 38 // later evicted because of a higher-priority allocation. The idea is that we 39 // can implement "second-chance bin-packing" by rerunning register allocation 40 // until there are no more evictions. getNumEvictions()41 SizeT getNumEvictions() const { return Evicted.size(); } hasEvictions()42 bool hasEvictions() const { return !Evicted.empty(); } 43 void dump(Cfg *Func) const; 44 45 // TODO(stichnot): Statically choose the size based on the target being 46 // compiled. For now, choose a value large enough to fit into the 47 // SmallVector's fixed portion, which is 32 for x86-32, 84 for x86-64, and 102 48 // for ARM32. 49 static constexpr size_t REGS_SIZE = 128; 50 51 private: 52 using OrderedRanges = CfgVector<Variable *>; 53 using UnorderedRanges = CfgVector<Variable *>; 54 using DefUseErrorList = llvm::SmallVector<SizeT, 10>; 55 56 class IterationState { 57 IterationState(const IterationState &) = delete; 58 IterationState operator=(const IterationState &) = delete; 59 60 public: 61 IterationState() = default; 62 Variable *Cur = nullptr; 63 Variable *Prefer = nullptr; 64 RegNumT PreferReg; 65 bool AllowOverlap = false; 66 SmallBitVector RegMask; 67 SmallBitVector RegMaskUnfiltered; 68 SmallBitVector Free; 69 SmallBitVector FreeUnfiltered; 70 SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping 71 llvm::SmallVector<RegWeight, REGS_SIZE> Weights; 72 }; 73 74 bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses, 75 const DefUseErrorList &UsesBeforeDefs, 76 const CfgVector<InstNumberT> &LRBegin, 77 const CfgVector<InstNumberT> &LREnd) const; 78 void initForGlobal(); 79 void initForInfOnly(); 80 void initForSecondChance(); 81 /// Move an item from the From set to the To set. From[Index] is pushed onto 82 /// the end of To[], then the item is efficiently removed from From[] by 83 /// effectively swapping it with the last item in From[] and then popping it 84 /// from the back. As such, the caller is best off iterating over From[] in 85 /// reverse order to avoid the need for special handling of the iterator. moveItem(UnorderedRanges & From,SizeT Index,UnorderedRanges & To)86 void moveItem(UnorderedRanges &From, SizeT Index, UnorderedRanges &To) { 87 To.push_back(From[Index]); 88 From[Index] = From.back(); 89 From.pop_back(); 90 } 91 92 /// \name scan helper functions. 93 /// @{ 94 /// Free up a register for infinite-weight Cur by spilling and reloading some 95 /// register that isn't used during Cur's live range. 96 void addSpillFill(IterationState &Iter); 97 /// Check for active ranges that have expired or become inactive. 98 void handleActiveRangeExpiredOrInactive(const Variable *Cur); 99 /// Check for inactive ranges that have expired or reactivated. 100 void handleInactiveRangeExpiredOrReactivated(const Variable *Cur); 101 void findRegisterPreference(IterationState &Iter); 102 void filterFreeWithInactiveRanges(IterationState &Iter); 103 void filterFreeWithPrecoloredRanges(IterationState &Iter); 104 void allocatePrecoloredRegister(Variable *Cur); 105 void allocatePreferredRegister(IterationState &Iter); 106 void allocateFreeRegister(IterationState &Iter, bool Filtered); 107 void handleNoFreeRegisters(IterationState &Iter); 108 void assignFinalRegisters(const SmallBitVector &RegMaskFull); 109 /// @} 110 111 void dumpLiveRangeTrace(const char *Label, const Variable *Item); 112 113 Cfg *const Func; 114 GlobalContext *const Ctx; 115 TargetLowering *const Target; 116 117 OrderedRanges Unhandled; 118 /// UnhandledPrecolored is a subset of Unhandled, specially collected for 119 /// faster processing. 120 OrderedRanges UnhandledPrecolored; 121 UnorderedRanges Active, Inactive, Handled; 122 UnorderedRanges Evicted; 123 CfgVector<InstNumberT> Kills; 124 RegAllocKind Kind = RAK_Unknown; 125 /// RegUses[I] is the number of live ranges (variables) that register I is 126 /// currently assigned to. It can be greater than 1 as a result of 127 /// AllowOverlap inference. 128 llvm::SmallVector<int32_t, REGS_SIZE> RegUses; 129 llvm::SmallVector<const SmallBitVector *, REGS_SIZE> RegAliases; 130 bool FindPreference = false; 131 bool FindOverlap = false; 132 const bool Verbose; 133 const bool UseReserve; 134 CfgVector<Variable *> Vars; 135 }; 136 137 } // end of namespace Ice 138 139 #endif // SUBZERO_SRC_ICEREGALLOC_H 140