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 #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 } SetPreHeader(BasicBlock * preHeader)52 void SetPreHeader(BasicBlock *preHeader) 53 { 54 preHeader_ = preHeader; 55 } 56 GetPreHeader()57 BasicBlock *GetPreHeader() const 58 { 59 return preHeader_; 60 } AppendBackEdge(BasicBlock * block)61 void AppendBackEdge(BasicBlock *block) 62 { 63 ASSERT(std::find(backEdges_.begin(), backEdges_.end(), block) == backEdges_.end()); 64 backEdges_.push_back(block); 65 } 66 ReplaceBackEdge(BasicBlock * block,BasicBlock * newBlock)67 void ReplaceBackEdge(BasicBlock *block, BasicBlock *newBlock) 68 { 69 ASSERT(block != newBlock); 70 ASSERT(std::find(backEdges_.begin(), backEdges_.end(), newBlock) == backEdges_.end()); 71 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 72 ASSERT(it != backEdges_.end()); 73 ASSERT(std::find(it + 1, backEdges_.end(), block) == backEdges_.end()); 74 backEdges_[std::distance(backEdges_.begin(), it)] = newBlock; 75 } 76 HasBackEdge(BasicBlock * block)77 bool HasBackEdge(BasicBlock *block) const 78 { 79 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 80 return it != backEdges_.end(); 81 } 82 RemoveBackEdge(BasicBlock * block)83 void RemoveBackEdge(BasicBlock *block) 84 { 85 auto it = std::find(backEdges_.begin(), backEdges_.end(), block); 86 ASSERT(it != backEdges_.end()); 87 ASSERT(std::find(it + 1, backEdges_.end(), block) == backEdges_.end()); 88 backEdges_[std::distance(backEdges_.begin(), it)] = backEdges_.back(); 89 backEdges_.pop_back(); 90 } 91 92 void MoveHeaderToSucc(); 93 GetBackEdges()94 const ArenaVector<BasicBlock *> &GetBackEdges() const 95 { 96 return backEdges_; 97 } 98 99 void AppendBlock(BasicBlock *block); 100 101 // NB! please use carefully, ensure that the block 102 // 1. is not a header of the loop 103 // 2. is not a back-edge of the loop 104 // 3. is not a pre-header of any inner loop 105 void RemoveBlock(BasicBlock *block); 106 GetBlocks()107 ArenaVector<BasicBlock *> &GetBlocks() 108 { 109 return blocks_; 110 } GetBlocks()111 const ArenaVector<BasicBlock *> &GetBlocks() const 112 { 113 return blocks_; 114 } AppendInnerLoop(Loop * innerLoop)115 void AppendInnerLoop(Loop *innerLoop) 116 { 117 innerLoops_.push_back(innerLoop); 118 } GetInnerLoops()119 ArenaVector<Loop *> &GetInnerLoops() 120 { 121 return innerLoops_; 122 } GetInnerLoops()123 const ArenaVector<Loop *> &GetInnerLoops() const 124 { 125 return innerLoops_; 126 } SetOuterLoop(Loop * outerLoop)127 void SetOuterLoop(Loop *outerLoop) 128 { 129 outerLoop_ = outerLoop; 130 } GetOuterLoop()131 Loop *GetOuterLoop() const 132 { 133 return outerLoop_; 134 } SetIsIrreducible(bool isIrreducible)135 void SetIsIrreducible(bool isIrreducible) 136 { 137 isIrreducible_ = isIrreducible; 138 } IsIrreducible()139 bool IsIrreducible() const 140 { 141 return isIrreducible_; 142 } IsInfinite()143 bool IsInfinite() const 144 { 145 return isInfinite_; 146 } SetIsInfinite(bool isInfinite)147 void SetIsInfinite(bool isInfinite) 148 { 149 isInfinite_ = isInfinite; 150 } SetAsRoot()151 void SetAsRoot() 152 { 153 isRoot_ = true; 154 } IsRoot()155 bool IsRoot() const 156 { 157 return isRoot_; 158 } GetId()159 uint32_t GetId() const 160 { 161 return id_; 162 } 163 164 bool IsOsrLoop() const; 165 166 bool IsTryCatchLoop() const; 167 168 bool IsInside(Loop *other); 169 GetDepth()170 auto GetDepth() const 171 { 172 return depth_; 173 } 174 175 bool IsPostExitBlock(const BasicBlock *block) const; 176 177 private: 178 void CheckInfinity(); 179 SetDepth(uint32_t depth)180 void SetDepth(uint32_t depth) 181 { 182 depth_ = depth; 183 } 184 185 template <typename T> IsEqualBlocks(const ArenaVector<T> & blocks,const ArenaVector<T> & others)186 static inline bool IsEqualBlocks(const ArenaVector<T> &blocks, const ArenaVector<T> &others) 187 { 188 return blocks.size() == others.size() && std::is_permutation(blocks.begin(), blocks.end(), others.begin()); 189 } 190 191 private: 192 BasicBlock *header_ {nullptr}; 193 BasicBlock *preHeader_ {nullptr}; 194 ArenaVector<BasicBlock *> backEdges_; 195 ArenaVector<BasicBlock *> blocks_; 196 ArenaVector<Loop *> innerLoops_; 197 Loop *outerLoop_ {nullptr}; 198 uint32_t id_ {INVALID_ID}; 199 uint32_t depth_ {0}; 200 bool isIrreducible_ {false}; 201 bool isInfinite_ {false}; 202 bool isRoot_ {false}; 203 204 friend class LoopAnalyzer; 205 }; 206 207 class LoopAnalyzer final : public Analysis { 208 public: 209 using Analysis::Analysis; 210 211 bool RunImpl() override; 212 GetPassName()213 const char *GetPassName() const override 214 { 215 return "LoopAnalysis"; 216 } 217 218 void CreateRootLoop(); 219 Loop *CreateNewLoop(BasicBlock *loopHeader); 220 221 private: 222 void ResetLoopInfo(); 223 void CollectBackEdges(); 224 void BackEdgeSearch(BasicBlock *block); 225 void ProcessNewBackEdge(BasicBlock *header, BasicBlock *backEdge); 226 void FindAndInsertPreHeaders(Loop *loop); 227 void MovePhiInputsToPreHeader(BasicBlock *header, BasicBlock *preHeader, const ArenaVector<int> &fwEdgesIndexes); 228 void UpdateControlFlowWithPreHeader(BasicBlock *header, BasicBlock *preHeader, 229 const ArenaVector<int> &fwEdgesIndexes); 230 ArenaVector<int> GetForwardEdgesIndexes(BasicBlock *header); 231 bool PreHeaderExists(Loop *loop); 232 BasicBlock *CreatePreHeader(BasicBlock *header); 233 void PopulateLoops(); 234 void PopulateIrreducibleLoop(Loop *loop); 235 void NaturalLoopSearch(Loop *loop, BasicBlock *block); 236 void SetLoopProperties(Loop *loop, uint32_t depth); 237 238 private: 239 Marker blackMarker_ {}; 240 Marker grayMarker_ {}; 241 uint32_t loopCounter_ {0}; 242 }; 243 244 BasicBlock *GetLoopOutsideSuccessor(Loop *loop); 245 // NOLINTNEXTLINE(readability-redundant-declaration) 246 bool IsLoopSingleBackEdgeExitPoint(Loop *loop); 247 248 } // namespace ark::compiler 249 250 #endif // COMPILER_OPTIMIZER_ANALYSIS_LOOP_ANALYSIS_H 251