1 /* 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_LINEAR_SCAN_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_LINEAR_SCAN_H 18 19 #include "utils/arena_containers.h" 20 #include "optimizer/analysis/liveness_analyzer.h" 21 #include "optimizer/code_generator/registers_description.h" 22 #include "reg_alloc_base.h" 23 #include "reg_map.h" 24 #include "compiler_logger.h" 25 26 namespace ark::compiler { 27 class BasicBlock; 28 class Graph; 29 class LifeIntervals; 30 31 using InstructionsIntervals = ArenaList<LifeIntervals *>; 32 using EmptyRegMask = std::bitset<0>; 33 34 /** 35 * Algorithm is based on paper "Linear Scan Register Allocation" by Christian Wimmer 36 * 37 * LinearScan works with instructions lifetime intervals, computed by the LivenessAnalyzer. 38 * It scans forward through the intervals, ordered by increasing starting point and assign registers while the number of 39 * the active intervals at the point is less then the number of available registers. When there are no available 40 * registers for some interval, LinearScan assigns one of the blocked ones. Previous holder of this blocked register is 41 * spilled to the memory at this point. Blocked register to be assigned is selected according to the usage information, 42 * LinearScan selects register with the most distant use point from the current one. 43 */ 44 class RegAllocLinearScan : public RegAllocBase { 45 struct WorkingIntervals { WorkingIntervalsWorkingIntervals46 explicit WorkingIntervals(ArenaAllocator *allocator) 47 : active(allocator->Adapter()), 48 inactive(allocator->Adapter()), 49 stack(allocator->Adapter()), 50 handled(allocator->Adapter()), 51 fixed(allocator->Adapter()) 52 { 53 } 54 ClearWorkingIntervals55 void Clear() 56 { 57 active.clear(); 58 inactive.clear(); 59 stack.clear(); 60 handled.clear(); 61 fixed.clear(); 62 } 63 64 InstructionsIntervals active; // NOLINT(misc-non-private-member-variables-in-classes) 65 InstructionsIntervals inactive; // NOLINT(misc-non-private-member-variables-in-classes) 66 InstructionsIntervals stack; // NOLINT(misc-non-private-member-variables-in-classes) 67 InstructionsIntervals handled; // NOLINT(misc-non-private-member-variables-in-classes) 68 ArenaVector<LifeIntervals *> fixed; // NOLINT(misc-non-private-member-variables-in-classes) 69 }; 70 71 struct PendingIntervals { PendingIntervalsPendingIntervals72 explicit PendingIntervals(ArenaAllocator *allocator) 73 : regular(allocator->Adapter()), fixed(allocator->Adapter()) 74 { 75 } 76 InstructionsIntervals regular; // NOLINT(misc-non-private-member-variables-in-classes) 77 ArenaVector<LifeIntervals *> fixed; // NOLINT(misc-non-private-member-variables-in-classes) 78 }; 79 80 public: 81 explicit RegAllocLinearScan(Graph *graph); 82 RegAllocLinearScan(Graph *graph, [[maybe_unused]] EmptyRegMask mask); 83 ~RegAllocLinearScan() override = default; 84 NO_MOVE_SEMANTIC(RegAllocLinearScan); 85 NO_COPY_SEMANTIC(RegAllocLinearScan); 86 GetPassName()87 const char *GetPassName() const override 88 { 89 return "RegAllocLinearScan"; 90 } 91 AbortIfFailed()92 bool AbortIfFailed() const override 93 { 94 return true; 95 } 96 97 protected: 98 bool Allocate() override; 99 void InitIntervals() override; 100 void PrepareInterval(LifeIntervals *interval) override; 101 102 private: 103 template <bool IS_FP> GetLocationMask()104 const LocationMask &GetLocationMask() const 105 { 106 return IS_FP ? GetVRegMask() : GetRegMask(); 107 } 108 109 template <bool IS_FP> GetIntervals()110 PendingIntervals &GetIntervals() 111 { 112 return IS_FP ? vectorIntervals_ : generalIntervals_; 113 } 114 115 template <bool IS_FP> 116 void AssignLocations(); 117 template <bool IS_FP> 118 void PreprocessPreassignedIntervals(); 119 template <bool IS_FP> 120 void ExpireIntervals(LifeNumber currentPosition); 121 template <bool IS_FP> 122 void WalkIntervals(); 123 template <bool IS_FP> 124 bool TryToAssignRegister(LifeIntervals *currentInterval); 125 template <bool IS_FP> 126 void SplitAndSpill(const InstructionsIntervals *intervals, const LifeIntervals *currentInterval); 127 template <bool IS_FP> 128 void SplitActiveInterval(LifeIntervals *interval, LifeNumber splitPos); 129 template <bool IS_FP> 130 void AddToQueue(LifeIntervals *interval); 131 template <bool IS_FP> 132 void SplitBeforeUse(LifeIntervals *currentInterval, LifeNumber usePos); 133 bool IsIntervalRegFree(const LifeIntervals *currentInterval, Register reg) const; 134 void AssignStackSlot(LifeIntervals *interval); 135 void RemapRegallocReg(LifeIntervals *interval); 136 void RemapRegistersIntervals(); 137 template <bool IS_FP> 138 void AddFixedIntervalsToWorkingIntervals(); 139 template <bool IS_FP> 140 void HandleFixedIntervalIntersection(LifeIntervals *currentInterval); 141 142 Register GetSuitableRegister(const LifeIntervals *currentInterval); 143 Register GetFreeRegister(const LifeIntervals *currentInterval); 144 std::pair<Register, LifeNumber> GetBlockedRegister(const LifeIntervals *currentInterval); 145 146 template <class T, class Callback> IterateIntervalsWithErasion(T & intervals,const Callback & callback)147 void IterateIntervalsWithErasion(T &intervals, const Callback &callback) const 148 { 149 for (auto it = intervals.begin(); it != intervals.end();) { 150 auto interval = *it; 151 if (callback(interval)) { 152 it = intervals.erase(it); 153 } else { 154 ++it; 155 } 156 } 157 } 158 159 template <class T, class Callback> EnumerateIntervals(const T & intervals,const Callback & callback)160 void EnumerateIntervals(const T &intervals, const Callback &callback) const 161 { 162 for (const auto &interval : intervals) { 163 if (interval == nullptr || interval->GetReg() >= regMap_.GetAvailableRegsCount()) { 164 continue; 165 } 166 callback(interval); 167 } 168 } 169 170 template <class T, class Callback> EnumerateIntersectedIntervals(const T & intervals,const LifeIntervals * current,const Callback & callback)171 void EnumerateIntersectedIntervals(const T &intervals, const LifeIntervals *current, const Callback &callback) const 172 { 173 for (const auto &interval : intervals) { 174 if (interval == nullptr || interval->GetReg() >= regMap_.GetAvailableRegsCount()) { 175 continue; 176 } 177 auto intersection = interval->GetFirstIntersectionWith(current); 178 if (intersection != INVALID_LIFE_NUMBER) { 179 callback(interval, intersection); 180 } 181 } 182 } 183 184 void BlockOverlappedRegisters(const LifeIntervals *currentInterval); 185 void BlockIndirectCallRegisters(const LifeIntervals *currentInterval); 186 bool IsNonSpillableConstInterval(LifeIntervals *interval); 187 void BeforeConstantIntervalSpill(LifeIntervals *interval, LifeNumber splitPos); 188 189 private: 190 WorkingIntervals workingIntervals_; 191 ArenaVector<LifeNumber> regsUsePositions_; 192 PendingIntervals generalIntervals_; 193 PendingIntervals vectorIntervals_; 194 RegisterMap regMap_; 195 bool rematConstants_; 196 bool success_ {true}; 197 }; 198 } // namespace ark::compiler 199 200 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_LINEAR_SCAN_H 201