1 /* 2 * Copyright (c) 2021-2025 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 #ifndef COMPILER_OPTIMIZER_ANALYSIS_LOOP_ANALYSIS_H 16 #define COMPILER_OPTIMIZER_ANALYSIS_LOOP_ANALYSIS_H 17 18 #include "optimizer/ir/inst.h" 19 #include "optimizer/pass.h" 20 #include "optimizer/analysis/countable_loop_parser.h" 21 22 namespace ark::compiler { 23 class BasicBlock; 24 class Graph; 25 26 class Loop final { 27 public: Loop(ArenaAllocator * allocator,BasicBlock * header,uint32_t id)28 Loop(ArenaAllocator *allocator, BasicBlock *header, uint32_t id) 29 : header_(header), 30 backEdges_(allocator->Adapter()), 31 blocks_(allocator->Adapter()), 32 innerLoops_(allocator->Adapter()), 33 id_(id) 34 { 35 } 36 37 DEFAULT_MOVE_SEMANTIC(Loop); 38 DEFAULT_COPY_SEMANTIC(Loop); 39 ~Loop() = default; 40 41 bool operator==(const Loop &other) const 42 { 43 return std::tie(header_, preHeader_, isIrreducible_, isRoot_, isInfinite_) == 44 std::tie(other.header_, other.preHeader_, other.isIrreducible_, other.isRoot_, other.isInfinite_) && 45 IsEqualBlocks(blocks_, other.blocks_) && IsEqualBlocks(backEdges_, other.backEdges_); 46 } 47 GetHeader()48 BasicBlock *GetHeader() const 49 { 50 return header_; 51 } 52 void SetPreHeader(BasicBlock *preHeader); 53 void SetPreHeader(std::nullptr_t preHeader); 54 PANDA_PUBLIC_API BasicBlock *GetPreHeader() const; 55 AppendBackEdge(BasicBlock * block)56 void AppendBackEdge(BasicBlock *block) 57 { 58 ASSERT(std::find(backEdges_.begin(), backEdges_.end(), block) == backEdges_.end()); 59 backEdges_.push_back(block); 60 } 61 ReplaceBackEdge(BasicBlock * block,BasicBlock * newBlock)62 void ReplaceBackEdge(BasicBlock *block, BasicBlock *newBlock) 63 { 64 ASSERT(block != newBlock); 65 ASSERT(std::find(backEdges_.begin(), backEdges_.end(), newBlock) == backEdges_.end()); 66 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 67 ASSERT(it != backEdges_.end()); 68 ASSERT(std::find(it + 1, backEdges_.end(), block) == backEdges_.end()); 69 backEdges_[std::distance(backEdges_.begin(), it)] = newBlock; 70 } 71 HasBackEdge(BasicBlock * block)72 bool HasBackEdge(BasicBlock *block) const 73 { 74 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 75 return it != backEdges_.end(); 76 } 77 RemoveBackEdge(BasicBlock * block)78 void RemoveBackEdge(BasicBlock *block) 79 { 80 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 81 ASSERT(it != backEdges_.end()); 82 ASSERT(std::find(it + 1, backEdges_.end(), block) == backEdges_.end()); 83 backEdges_[std::distance(backEdges_.begin(), it)] = backEdges_.back(); 84 backEdges_.pop_back(); 85 } 86 87 void MoveHeaderToSucc(); 88 GetBackEdges()89 const ArenaVector<BasicBlock *> &GetBackEdges() const 90 { 91 return backEdges_; 92 } 93 94 void AppendBlock(BasicBlock *block); 95 96 // NB! please use carefully, ensure that the block 97 // 1. is not a header of the loop 98 // 2. is not a back-edge of the loop 99 // 3. is not a pre-header of any inner loop 100 void RemoveBlock(BasicBlock *block); 101 GetBlocks()102 ArenaVector<BasicBlock *> &GetBlocks() 103 { 104 return blocks_; 105 } GetBlocks()106 const ArenaVector<BasicBlock *> &GetBlocks() const 107 { 108 return blocks_; 109 } AppendInnerLoop(Loop * innerLoop)110 void AppendInnerLoop(Loop *innerLoop) 111 { 112 innerLoops_.push_back(innerLoop); 113 } GetInnerLoops()114 ArenaVector<Loop *> &GetInnerLoops() 115 { 116 return innerLoops_; 117 } GetInnerLoops()118 const ArenaVector<Loop *> &GetInnerLoops() const 119 { 120 return innerLoops_; 121 } SetOuterLoop(Loop * outerLoop)122 void SetOuterLoop(Loop *outerLoop) 123 { 124 outerLoop_ = outerLoop; 125 } GetOuterLoop()126 Loop *GetOuterLoop() const 127 { 128 return outerLoop_; 129 } SetIsIrreducible(bool isIrreducible)130 void SetIsIrreducible(bool isIrreducible) 131 { 132 isIrreducible_ = isIrreducible; 133 } IsIrreducible()134 bool IsIrreducible() const 135 { 136 return isIrreducible_; 137 } IsInfinite()138 bool IsInfinite() const 139 { 140 return isInfinite_; 141 } SetIsInfinite(bool isInfinite)142 void SetIsInfinite(bool isInfinite) 143 { 144 isInfinite_ = isInfinite; 145 } SetAsRoot()146 void SetAsRoot() 147 { 148 isRoot_ = true; 149 } IsRoot()150 bool IsRoot() const 151 { 152 return isRoot_; 153 } 154 155 void CheckActualLengthAsLoopInitOrBound(); 156 SetArrayIndexVariable(Inst * inst)157 void SetArrayIndexVariable(Inst *inst) 158 { 159 arrayIndexVariable_ = inst; 160 } 161 GetArrayIndexVariable()162 Inst *GetArrayIndexVariable() const 163 { 164 return arrayIndexVariable_; 165 } 166 SetArrayOriginRef(Inst * inst)167 void SetArrayOriginRef(Inst *inst) 168 { 169 arrayOriginRef_ = inst; 170 } 171 GetArrayOriginRef()172 Inst *GetArrayOriginRef() const 173 { 174 return arrayOriginRef_; 175 } 176 GetId()177 uint32_t GetId() const 178 { 179 return id_; 180 } 181 182 bool IsOsrLoop() const; 183 184 bool IsTryCatchLoop() const; 185 186 bool IsInside(Loop *other); 187 GetDepth()188 auto GetDepth() const 189 { 190 return depth_; 191 } 192 193 bool IsPostExitBlock(const BasicBlock *block) const; 194 195 private: 196 void CheckInfinity(); 197 bool CheckUpdateAndInitForBound(CompareInst *cmpInst, PhiInst *phiInst); 198 void CheckActualLengthAsLoopBound(Inst *&loadObject, CompareInst *cmpInst, PhiInst *phiInst); 199 void CheckActualLengthVariantAsLoopInit(Inst *&loadObject, CompareInst *cmpInst, PhiInst *phiInst); 200 void CheckActualLengthVariantAsLoopBound(Inst *&loadObject, CompareInst *cmpInst, PhiInst *phiInst); 201 bool PrecheckInst(CompareInst *&cmpInst, PhiInst *&phiInst); 202 SetDepth(uint32_t depth)203 void SetDepth(uint32_t depth) 204 { 205 depth_ = depth; 206 } 207 208 template <typename T> IsEqualBlocks(const ArenaVector<T> & blocks,const ArenaVector<T> & others)209 static inline bool IsEqualBlocks(const ArenaVector<T> &blocks, const ArenaVector<T> &others) 210 { 211 return blocks.size() == others.size() && std::is_permutation(blocks.begin(), blocks.end(), others.begin()); 212 } 213 214 private: 215 BasicBlock *header_ {nullptr}; 216 BasicBlock *preHeader_ {nullptr}; 217 ArenaVector<BasicBlock *> backEdges_; 218 ArenaVector<BasicBlock *> blocks_; 219 ArenaVector<Loop *> innerLoops_; 220 Loop *outerLoop_ {nullptr}; 221 uint32_t id_ {INVALID_ID}; 222 uint32_t depth_ {0}; 223 bool isIrreducible_ {false}; 224 bool isInfinite_ {false}; 225 bool isRoot_ {false}; 226 Inst *arrayIndexVariable_ {nullptr}; 227 Inst *arrayOriginRef_ {nullptr}; 228 229 friend class LoopAnalyzer; 230 }; 231 232 class LoopAnalyzer final : public Analysis { 233 public: 234 using Analysis::Analysis; 235 236 bool RunImpl() override; 237 GetPassName()238 const char *GetPassName() const override 239 { 240 return "LoopAnalysis"; 241 } 242 243 void CreateRootLoop(); 244 Loop *CreateNewLoop(BasicBlock *loopHeader); 245 246 private: 247 void ResetLoopInfo(); 248 void CollectBackEdges(); 249 void BackEdgeSearch(BasicBlock *block); 250 void ProcessNewBackEdge(BasicBlock *header, BasicBlock *backEdge); 251 void FindAndInsertPreHeaders(Loop *loop); 252 void MovePhiInputsToPreHeader(BasicBlock *header, BasicBlock *preHeader, const ArenaVector<int> &fwEdgesIndexes); 253 void UpdateControlFlowWithPreHeader(BasicBlock *header, BasicBlock *preHeader, 254 const ArenaVector<int> &fwEdgesIndexes); 255 ArenaVector<int> GetForwardEdgesIndexes(BasicBlock *header); 256 bool PreHeaderExists(Loop *loop); 257 BasicBlock *CreatePreHeader(BasicBlock *header); 258 void PopulateLoops(); 259 void PopulateIrreducibleLoop(Loop *loop); 260 void NaturalLoopSearch(Loop *loop, BasicBlock *block); 261 void SetLoopProperties(Loop *loop, uint32_t depth); 262 void CheckActualLengthAsLoopInitOrBound(Loop *loop); 263 264 private: 265 Marker blackMarker_ {}; 266 Marker grayMarker_ {}; 267 uint32_t loopCounter_ {0}; 268 }; 269 270 BasicBlock *GetLoopOutsideSuccessor(Loop *loop); 271 // NOLINTNEXTLINE(readability-redundant-declaration) 272 bool IsLoopSingleBackEdgeExitPoint(Loop *loop); 273 274 } // namespace ark::compiler 275 276 #endif // COMPILER_OPTIMIZER_ANALYSIS_LOOP_ANALYSIS_H 277