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_RPO_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_RPO_H 18 19 #include "utils/arena_containers.h" 20 #include "optimizer/ir/marker.h" 21 #include "optimizer/pass.h" 22 #include <algorithm> 23 24 namespace ark::compiler { 25 class BasicBlock; 26 class Graph; 27 28 /** 29 * This class builds blocks list for reverse postorder traversal. 30 * There is an option to invalidate blocks list. In this case the list 31 * will be build from scratch after the next request for it. 32 * Also it provides methods for updating an existing tree. 33 */ 34 class Rpo : public Analysis { 35 public: 36 explicit Rpo(Graph *graph); 37 38 NO_MOVE_SEMANTIC(Rpo); 39 NO_COPY_SEMANTIC(Rpo); 40 ~Rpo() override = default; 41 GetPassName()42 const char *GetPassName() const override 43 { 44 return "RPO"; 45 } 46 47 public: RemoveBasicBlock(BasicBlock * rmBlock)48 void RemoveBasicBlock(BasicBlock *rmBlock) 49 { 50 ASSERT_PRINT(IsValid(), "RPO is invalid"); 51 auto it = std::find(rpoVector_.begin(), rpoVector_.end(), rmBlock); 52 if (it != rpoVector_.end()) { 53 rpoVector_.erase(it); 54 } 55 } 56 AddBasicBlockAfter(BasicBlock * curBlock,BasicBlock * newBlock)57 void AddBasicBlockAfter(BasicBlock *curBlock, BasicBlock *newBlock) 58 { 59 ASSERT_PRINT(IsValid(), "RPO is invalid"); 60 auto it = std::find(rpoVector_.begin(), rpoVector_.end(), curBlock); 61 rpoVector_.insert(it + 1, newBlock); 62 } 63 AddBasicBlockBefore(BasicBlock * curBlock,BasicBlock * newBlock)64 void AddBasicBlockBefore(BasicBlock *curBlock, BasicBlock *newBlock) 65 { 66 ASSERT_PRINT(IsValid(), "RPO is invalid"); 67 auto it = std::find(rpoVector_.begin(), rpoVector_.end(), curBlock); 68 rpoVector_.insert(it, newBlock); 69 } 70 AddVectorAfter(BasicBlock * curBlock,const ArenaVector<BasicBlock * > & newVector)71 void AddVectorAfter(BasicBlock *curBlock, const ArenaVector<BasicBlock *> &newVector) 72 { 73 ASSERT_PRINT(IsValid(), "RPO is invalid"); 74 auto it = std::find(rpoVector_.begin(), rpoVector_.end(), curBlock); 75 rpoVector_.insert(it + 1, newVector.begin(), newVector.end()); 76 } 77 GetBlocks()78 const ArenaVector<BasicBlock *> &GetBlocks() const 79 { 80 return rpoVector_; 81 } 82 83 private: 84 bool RunImpl() override; 85 86 void DFS(BasicBlock *block, size_t *blocksCount); 87 88 private: 89 Marker marker_ {UNDEF_MARKER}; 90 ArenaVector<BasicBlock *> rpoVector_; 91 }; 92 } // namespace ark::compiler 93 94 #endif // COMPILER_OPTIMIZER_ANALYSIS_RPO_H 95