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_ANALYSIS_REG_ALLOC_VERIFIER_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_REG_ALLOC_VERIFIER_H 18 19 #include "optimizer/pass.h" 20 #include "optimizer/ir/graph.h" 21 #include "optimizer/ir/inst.h" 22 #include "optimizer/ir/basicblock.h" 23 24 namespace ark::compiler { 25 class BlockState; 26 class LocationState; 27 /* 28 Analysis aimed to check correctness of registers and stack slots assignment. 29 To verify correctness the analysis stores a state for each possible location 30 (GP register, FP register, stack slot or immediate table slot for spilled constants). 31 The state represents knowledge about a value stored in a location: it could be unknown, 32 known or invalid (conflicting). The "known" state is augmented with instruction id 33 whose value the location is holding. 34 During verification process verifier iterates through all basic blocks and for each 35 instruction within basic block performs following actions: 36 1) checks that each instruction's input register holds known value and corresponding 37 instruction id (from the input location) is the same as the input's id; 38 2) updates instruction's output location with its id (if an instruction has destination). 39 If any input location contains unknown or conflicting value then verification fails. 40 41 When block analysis is complete the state at the block's end have to be propagated to 42 successor blocks. Propagation step perform following actions: 43 1) process all successor's locations corresponding to phi instructions by checking that 44 phi's location at the end of predecessor block holds result of the exact instruction 45 that will be selected by the phi when control flows from the predecessor to successor. 46 If this condition holds then phi's id will be written to successor's location. 47 2) merge all locations (that were not updated at (1)) at the end of predecessor block 48 to the same locations at the beginning of successor block. 49 3) if any location was updated during two previous steps then successor block is marked 50 as updated and should be verified. 51 52 Merge action (2) updates destination (successor block's) location with data from 53 source (predecessor block's) location using following rules: 54 1) if source or destination has conflicting value then destination will have conflicting value; 55 2) if both values are unknown then destination value will remain unknown; 56 3) if either destination or source value is known (but not both values simultaneously) then 57 destination will either remain known or will be updated to known value; 58 4) if both source and destination values are known and holds result of the same instruction 59 then the destination remain known; 60 5) if both source and destination values are known but holds results of different instructions 61 then destination will be updated to conflicting value. 62 63 Verification process continues until there are no more blocks updated during value propagation. 64 If there are no such blocks and there were no errors then verification passes. 65 */ 66 class RegAllocVerifier : public Analysis { 67 public: 68 explicit RegAllocVerifier(Graph *graph, bool saveLiveRegsOnCall = true); 69 NO_COPY_SEMANTIC(RegAllocVerifier); 70 NO_MOVE_SEMANTIC(RegAllocVerifier); 71 ~RegAllocVerifier() override = default; 72 73 bool RunImpl() override; 74 GetPassName()75 const char *GetPassName() const override 76 { 77 return "RegAllocVerifier"; 78 } 79 80 private: 81 BasicBlock *currentBlock_ {nullptr}; 82 BlockState *currentState_ {nullptr}; 83 ArenaVector<LocationState> immediates_; 84 // required to support Save/RestoreRegisters intrinsics 85 ArenaVector<LocationState> savedRegs_; 86 ArenaVector<LocationState> savedVregs_; 87 bool success_ {true}; 88 Marker implicitNullCheckHandledMarker_ {}; 89 bool saveLiveRegs_ {false}; 90 91 void InitImmediates(); 92 bool IsZeroReg(Register reg, DataType::Type type) const; 93 void HandleDest(Inst *inst); 94 LocationState &GetLocationState(Location location); 95 void UpdateLocation(Location location, DataType::Type type, uint32_t instId); 96 template <typename T> 97 bool ForEachLocation(Location location, DataType::Type type, T callback); 98 void ProcessCurrentBlock(); 99 void HandleParameter(ParameterInst *inst); 100 void HandleSpillFill(SpillFillInst *inst); 101 void HandleConst(ConstantInst *inst); 102 void HandleInst(Inst *inst); 103 #ifdef PANDA_WITH_IRTOC 104 bool IsSaveRestoreRegisters(Inst *inst); 105 void HandleSaveRestoreRegisters(Inst *inst); 106 #endif 107 void TryHandleImplicitNullCheck(Inst *inst); 108 void RestoreLiveRegisters(Inst *inst); 109 }; 110 111 class LocationState { 112 public: 113 enum class State : uint8_t { UNKNOWN, KNOWN, CONFLICT }; 114 static auto constexpr ZERO_INST = INVALID_ID; 115 116 LocationState() = default; LocationState(LocationState::State state,uint32_t id)117 LocationState(LocationState::State state, uint32_t id) : state_(state), id_(id) {} 118 ~LocationState() = default; 119 DEFAULT_COPY_SEMANTIC(LocationState); 120 DEFAULT_MOVE_SEMANTIC(LocationState); 121 GetState()122 State GetState() const 123 { 124 return state_; 125 } 126 SetState(State state)127 void SetState(State state) 128 { 129 state_ = state; 130 } 131 SetId(uint32_t id)132 void SetId(uint32_t id) 133 { 134 state_ = State::KNOWN; 135 id_ = id; 136 } 137 GetId()138 uint32_t GetId() const 139 { 140 return id_; 141 } 142 143 bool Merge(const LocationState &other); 144 ShouldSkip()145 bool ShouldSkip() const 146 { 147 return skip_; 148 } 149 SetSkip(bool skip)150 void SetSkip(bool skip) 151 { 152 skip_ = skip; 153 } 154 IsValid(const Inst * inst)155 bool IsValid(const Inst *inst) const 156 { 157 return GetId() == inst->GetId() || (GetId() == ZERO_INST && inst->IsZeroRegInst()); 158 } 159 160 private: 161 State state_ {UNKNOWN}; 162 uint32_t id_ {INVALID_ID}; 163 bool skip_ {false}; 164 }; 165 166 class BlockState { 167 public: 168 BlockState(size_t regs, size_t vregs, size_t stackSlots, size_t stackParams, ArenaAllocator *alloc); 169 ~BlockState() = default; 170 NO_COPY_SEMANTIC(BlockState); 171 NO_MOVE_SEMANTIC(BlockState); GetReg(Register reg)172 LocationState &GetReg(Register reg) 173 { 174 ASSERT(reg < regs_.size()); 175 return regs_[reg]; 176 } GetReg(Register reg)177 const LocationState &GetReg(Register reg) const 178 { 179 ASSERT(reg < regs_.size()); 180 return regs_[reg]; 181 } GetVReg(Register reg)182 LocationState &GetVReg(Register reg) 183 { 184 ASSERT(reg < vregs_.size()); 185 return vregs_[reg]; 186 } GetVReg(Register reg)187 const LocationState &GetVReg(Register reg) const 188 { 189 ASSERT(reg < vregs_.size()); 190 return vregs_[reg]; 191 } GetStack(StackSlot slot)192 const LocationState &GetStack(StackSlot slot) const 193 { 194 ASSERT(slot < stack_.size()); 195 return stack_[slot]; 196 } GetStack(StackSlot slot)197 LocationState &GetStack(StackSlot slot) 198 { 199 ASSERT(slot < stack_.size()); 200 return stack_[slot]; 201 } GetStackArg(StackSlot slot)202 const LocationState &GetStackArg(StackSlot slot) const 203 { 204 ASSERT(slot < stackArg_.size()); 205 return stackArg_[slot]; 206 } GetStackArg(StackSlot slot)207 LocationState &GetStackArg(StackSlot slot) 208 { 209 if (slot >= stackArg_.size()) { 210 stackArg_.resize(slot + 1); 211 } 212 return stackArg_[slot]; 213 } GetStackParam(StackSlot slot)214 const LocationState &GetStackParam(StackSlot slot) const 215 { 216 ASSERT(slot < stackParam_.size()); 217 return stackParam_[slot]; 218 } GetStackParam(StackSlot slot)219 LocationState &GetStackParam(StackSlot slot) 220 { 221 if (slot >= stackParam_.size()) { 222 stackParam_.resize(slot + 1); 223 } 224 return stackParam_[slot]; 225 } 226 227 bool Merge(const BlockState &state, const PhiInstSafeIter &phis, BasicBlock *pred, 228 const ArenaVector<LocationState> &immediates, const LivenessAnalyzer &la); 229 void Copy(BlockState *state); 230 231 private: 232 ArenaVector<LocationState> regs_; 233 ArenaVector<LocationState> vregs_; 234 ArenaVector<LocationState> stack_; 235 ArenaVector<LocationState> stackParam_; 236 ArenaVector<LocationState> stackArg_; 237 }; 238 } // namespace ark::compiler 239 240 #endif // COMPILER_OPTIMIZER_ANALYSIS_REG_ALLOC_VERIFIER_H 241