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 } 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 } GetId()154 uint32_t GetId() const 155 { 156 return id_; 157 } 158 159 bool IsOsrLoop() const; 160 161 bool IsTryCatchLoop() const; 162 163 bool IsInside(Loop *other); 164 GetDepth()165 auto GetDepth() const 166 { 167 return depth_; 168 } 169 170 bool IsPostExitBlock(const BasicBlock *block) const; 171 172 private: 173 void CheckInfinity(); 174 SetDepth(uint32_t depth)175 void SetDepth(uint32_t depth) 176 { 177 depth_ = depth; 178 } 179 180 template <typename T> IsEqualBlocks(const ArenaVector<T> & blocks,const ArenaVector<T> & others)181 static inline bool IsEqualBlocks(const ArenaVector<T> &blocks, const ArenaVector<T> &others) 182 { 183 return blocks.size() == others.size() && std::is_permutation(blocks.begin(), blocks.end(), others.begin()); 184 } 185 186 private: 187 BasicBlock *header_ {nullptr}; 188 BasicBlock *preHeader_ {nullptr}; 189 ArenaVector<BasicBlock *> backEdges_; 190 ArenaVector<BasicBlock *> blocks_; 191 ArenaVector<Loop *> innerLoops_; 192 Loop *outerLoop_ {nullptr}; 193 uint32_t id_ {INVALID_ID}; 194 uint32_t depth_ {0}; 195 bool isIrreducible_ {false}; 196 bool isInfinite_ {false}; 197 bool isRoot_ {false}; 198 199 friend class LoopAnalyzer; 200 }; 201 202 class LoopAnalyzer final : public Analysis { 203 public: 204 using Analysis::Analysis; 205 206 bool RunImpl() override; 207 GetPassName()208 const char *GetPassName() const override 209 { 210 return "LoopAnalysis"; 211 } 212 213 void CreateRootLoop(); 214 Loop *CreateNewLoop(BasicBlock *loopHeader); 215 216 private: 217 void ResetLoopInfo(); 218 void CollectBackEdges(); 219 void BackEdgeSearch(BasicBlock *block); 220 void ProcessNewBackEdge(BasicBlock *header, BasicBlock *backEdge); 221 void FindAndInsertPreHeaders(Loop *loop); 222 void MovePhiInputsToPreHeader(BasicBlock *header, BasicBlock *preHeader, const ArenaVector<int> &fwEdgesIndexes); 223 void UpdateControlFlowWithPreHeader(BasicBlock *header, BasicBlock *preHeader, 224 const ArenaVector<int> &fwEdgesIndexes); 225 ArenaVector<int> GetForwardEdgesIndexes(BasicBlock *header); 226 bool PreHeaderExists(Loop *loop); 227 BasicBlock *CreatePreHeader(BasicBlock *header); 228 void PopulateLoops(); 229 void PopulateIrreducibleLoop(Loop *loop); 230 void NaturalLoopSearch(Loop *loop, BasicBlock *block); 231 void SetLoopProperties(Loop *loop, uint32_t depth); 232 233 private: 234 Marker blackMarker_ {}; 235 Marker grayMarker_ {}; 236 uint32_t loopCounter_ {0}; 237 }; 238 239 BasicBlock *GetLoopOutsideSuccessor(Loop *loop); 240 // NOLINTNEXTLINE(readability-redundant-declaration) 241 bool IsLoopSingleBackEdgeExitPoint(Loop *loop); 242 243 } // namespace ark::compiler 244 245 #endif // COMPILER_OPTIMIZER_ANALYSIS_LOOP_ANALYSIS_H 246