OLD | NEW |
1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// | 1 //===- subzero/src/IceRegAlloc.h - Linear-scan reg. allocation --*- C++ -*-===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 /// | 9 /// |
10 /// \file | 10 /// \file |
11 /// \brief Declares the LinearScan data structure used during linear-scan | 11 /// \brief Declares the LinearScan data structure used during linear-scan |
12 /// register allocation. | 12 /// register allocation. |
13 /// | 13 /// |
14 /// This holds the various work queues for the linear-scan algorithm. | 14 /// This holds the various work queues for the linear-scan algorithm. |
15 /// | 15 /// |
16 //===----------------------------------------------------------------------===// | 16 //===----------------------------------------------------------------------===// |
17 | 17 |
18 #ifndef SUBZERO_SRC_ICEREGALLOC_H | 18 #ifndef SUBZERO_SRC_ICEREGALLOC_H |
19 #define SUBZERO_SRC_ICEREGALLOC_H | 19 #define SUBZERO_SRC_ICEREGALLOC_H |
20 | 20 |
21 #include "IceDefs.h" | 21 #include "IceDefs.h" |
| 22 #include "IceBitVector.h" |
22 #include "IceOperand.h" | 23 #include "IceOperand.h" |
23 #include "IceTypes.h" | 24 #include "IceTypes.h" |
24 | 25 |
25 namespace Ice { | 26 namespace Ice { |
26 | 27 |
27 class LinearScan { | 28 class LinearScan { |
28 LinearScan() = delete; | 29 LinearScan() = delete; |
29 LinearScan(const LinearScan &) = delete; | 30 LinearScan(const LinearScan &) = delete; |
30 LinearScan &operator=(const LinearScan &) = delete; | 31 LinearScan &operator=(const LinearScan &) = delete; |
31 | 32 |
32 public: | 33 public: |
33 explicit LinearScan(Cfg *Func); | 34 explicit LinearScan(Cfg *Func); |
34 void init(RegAllocKind Kind); | 35 void init(RegAllocKind Kind); |
35 void scan(const llvm::SmallBitVector &RegMask, bool Randomized); | 36 void scan(const SmallBitVector &RegMask, bool Randomized); |
36 // Returns the number of times some variable has been assigned a register but | 37 // Returns the number of times some variable has been assigned a register but |
37 // later evicted because of a higher-priority allocation. The idea is that we | 38 // later evicted because of a higher-priority allocation. The idea is that we |
38 // can implement "second-chance bin-packing" by rerunning register allocation | 39 // can implement "second-chance bin-packing" by rerunning register allocation |
39 // until there are no more evictions. | 40 // until there are no more evictions. |
40 SizeT getNumEvictions() const { return Evicted.size(); } | 41 SizeT getNumEvictions() const { return Evicted.size(); } |
41 bool hasEvictions() const { return !Evicted.empty(); } | 42 bool hasEvictions() const { return !Evicted.empty(); } |
42 void dump(Cfg *Func) const; | 43 void dump(Cfg *Func) const; |
43 | 44 |
44 // TODO(stichnot): Statically choose the size based on the target being | 45 // TODO(stichnot): Statically choose the size based on the target being |
45 // compiled. | 46 // compiled. |
46 static constexpr size_t REGS_SIZE = 32; | 47 static constexpr size_t REGS_SIZE = 32; |
47 | 48 |
48 private: | 49 private: |
49 using OrderedRanges = CfgVector<Variable *>; | 50 using OrderedRanges = CfgVector<Variable *>; |
50 using UnorderedRanges = CfgVector<Variable *>; | 51 using UnorderedRanges = CfgVector<Variable *>; |
51 using DefUseErrorList = llvm::SmallVector<SizeT, 10>; | 52 using DefUseErrorList = llvm::SmallVector<SizeT, 10>; |
52 | 53 |
53 class IterationState { | 54 class IterationState { |
54 IterationState(const IterationState &) = delete; | 55 IterationState(const IterationState &) = delete; |
55 IterationState operator=(const IterationState &) = delete; | 56 IterationState operator=(const IterationState &) = delete; |
56 | 57 |
57 public: | 58 public: |
58 IterationState() = default; | 59 IterationState() = default; |
59 Variable *Cur = nullptr; | 60 Variable *Cur = nullptr; |
60 Variable *Prefer = nullptr; | 61 Variable *Prefer = nullptr; |
61 RegNumT PreferReg; | 62 RegNumT PreferReg; |
62 bool AllowOverlap = false; | 63 bool AllowOverlap = false; |
63 llvm::SmallBitVector RegMask; | 64 SmallBitVector RegMask; |
64 llvm::SmallBitVector RegMaskUnfiltered; | 65 SmallBitVector RegMaskUnfiltered; |
65 llvm::SmallBitVector Free; | 66 SmallBitVector Free; |
66 llvm::SmallBitVector FreeUnfiltered; | 67 SmallBitVector FreeUnfiltered; |
67 llvm::SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping | 68 SmallBitVector PrecoloredUnhandledMask; // Note: only used for dumping |
68 llvm::SmallVector<RegWeight, REGS_SIZE> Weights; | 69 llvm::SmallVector<RegWeight, REGS_SIZE> Weights; |
69 }; | 70 }; |
70 | 71 |
71 bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses, | 72 bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses, |
72 const DefUseErrorList &UsesBeforeDefs, | 73 const DefUseErrorList &UsesBeforeDefs, |
73 const CfgVector<InstNumberT> &LRBegin, | 74 const CfgVector<InstNumberT> &LRBegin, |
74 const CfgVector<InstNumberT> &LREnd) const; | 75 const CfgVector<InstNumberT> &LREnd) const; |
75 void initForGlobal(); | 76 void initForGlobal(); |
76 void initForInfOnly(); | 77 void initForInfOnly(); |
77 void initForSecondChance(); | 78 void initForSecondChance(); |
(...skipping 17 matching lines...) Expand all Loading... |
95 void handleActiveRangeExpiredOrInactive(const Variable *Cur); | 96 void handleActiveRangeExpiredOrInactive(const Variable *Cur); |
96 /// Check for inactive ranges that have expired or reactivated. | 97 /// Check for inactive ranges that have expired or reactivated. |
97 void handleInactiveRangeExpiredOrReactivated(const Variable *Cur); | 98 void handleInactiveRangeExpiredOrReactivated(const Variable *Cur); |
98 void findRegisterPreference(IterationState &Iter); | 99 void findRegisterPreference(IterationState &Iter); |
99 void filterFreeWithInactiveRanges(IterationState &Iter); | 100 void filterFreeWithInactiveRanges(IterationState &Iter); |
100 void filterFreeWithPrecoloredRanges(IterationState &Iter); | 101 void filterFreeWithPrecoloredRanges(IterationState &Iter); |
101 void allocatePrecoloredRegister(Variable *Cur); | 102 void allocatePrecoloredRegister(Variable *Cur); |
102 void allocatePreferredRegister(IterationState &Iter); | 103 void allocatePreferredRegister(IterationState &Iter); |
103 void allocateFreeRegister(IterationState &Iter, bool Filtered); | 104 void allocateFreeRegister(IterationState &Iter, bool Filtered); |
104 void handleNoFreeRegisters(IterationState &Iter); | 105 void handleNoFreeRegisters(IterationState &Iter); |
105 void assignFinalRegisters(const llvm::SmallBitVector &RegMaskFull, | 106 void assignFinalRegisters(const SmallBitVector &RegMaskFull, |
106 const llvm::SmallBitVector &PreDefinedRegisters, | 107 const SmallBitVector &PreDefinedRegisters, |
107 bool Randomized); | 108 bool Randomized); |
108 /// @} | 109 /// @} |
109 | 110 |
110 void dumpLiveRangeTrace(const char *Label, const Variable *Item); | 111 void dumpLiveRangeTrace(const char *Label, const Variable *Item); |
111 | 112 |
112 Cfg *const Func; | 113 Cfg *const Func; |
113 GlobalContext *const Ctx; | 114 GlobalContext *const Ctx; |
114 TargetLowering *const Target; | 115 TargetLowering *const Target; |
115 | 116 |
116 OrderedRanges Unhandled; | 117 OrderedRanges Unhandled; |
117 /// UnhandledPrecolored is a subset of Unhandled, specially collected for | 118 /// UnhandledPrecolored is a subset of Unhandled, specially collected for |
118 /// faster processing. | 119 /// faster processing. |
119 OrderedRanges UnhandledPrecolored; | 120 OrderedRanges UnhandledPrecolored; |
120 UnorderedRanges Active, Inactive, Handled; | 121 UnorderedRanges Active, Inactive, Handled; |
121 UnorderedRanges Evicted; | 122 UnorderedRanges Evicted; |
122 CfgVector<InstNumberT> Kills; | 123 CfgVector<InstNumberT> Kills; |
123 RegAllocKind Kind = RAK_Unknown; | 124 RegAllocKind Kind = RAK_Unknown; |
124 /// RegUses[I] is the number of live ranges (variables) that register I is | 125 /// RegUses[I] is the number of live ranges (variables) that register I is |
125 /// currently assigned to. It can be greater than 1 as a result of | 126 /// currently assigned to. It can be greater than 1 as a result of |
126 /// AllowOverlap inference. | 127 /// AllowOverlap inference. |
127 llvm::SmallVector<int32_t, REGS_SIZE> RegUses; | 128 llvm::SmallVector<int32_t, REGS_SIZE> RegUses; |
128 // TODO(jpp): for some architectures a SmallBitVector might not be big | 129 llvm::SmallVector<const SmallBitVector *, REGS_SIZE> RegAliases; |
129 // enough. Evaluate what the performance impact on those architectures is. | |
130 llvm::SmallVector<const llvm::SmallBitVector *, REGS_SIZE> RegAliases; | |
131 bool FindPreference = false; | 130 bool FindPreference = false; |
132 bool FindOverlap = false; | 131 bool FindOverlap = false; |
133 | 132 |
134 const bool Verbose; | 133 const bool Verbose; |
135 const bool UseReserve; | 134 const bool UseReserve; |
136 }; | 135 }; |
137 | 136 |
138 } // end of namespace Ice | 137 } // end of namespace Ice |
139 | 138 |
140 #endif // SUBZERO_SRC_ICEREGALLOC_H | 139 #endif // SUBZERO_SRC_ICEREGALLOC_H |
OLD | NEW |