1 /** 2 * Copyright (c) 2021-2022 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 <algorithm> 20 #include "utils/arena_containers.h" 21 #include "optimizer/ir/marker.h" 22 #include "optimizer/pass.h" 23 24 namespace panda::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 * rm_block)48 void RemoveBasicBlock(BasicBlock *rm_block) 49 { 50 ASSERT_PRINT(IsValid(), "RPO is invalid"); 51 auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), rm_block); 52 if (it != rpo_vector_.end()) { 53 rpo_vector_.erase(it); 54 } 55 } 56 AddBasicBlockAfter(BasicBlock * cur_block,BasicBlock * new_block)57 void AddBasicBlockAfter(BasicBlock *cur_block, BasicBlock *new_block) 58 { 59 ASSERT_PRINT(IsValid(), "RPO is invalid"); 60 auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block); 61 rpo_vector_.insert(it + 1, new_block); 62 } 63 AddBasicBlockBefore(BasicBlock * cur_block,BasicBlock * new_block)64 void AddBasicBlockBefore(BasicBlock *cur_block, BasicBlock *new_block) 65 { 66 ASSERT_PRINT(IsValid(), "RPO is invalid"); 67 auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block); 68 rpo_vector_.insert(it, new_block); 69 } 70 AddVectorAfter(BasicBlock * cur_block,const ArenaVector<BasicBlock * > & new_vector)71 void AddVectorAfter(BasicBlock *cur_block, const ArenaVector<BasicBlock *> &new_vector) 72 { 73 ASSERT_PRINT(IsValid(), "RPO is invalid"); 74 auto it = std::find(rpo_vector_.begin(), rpo_vector_.end(), cur_block); 75 rpo_vector_.insert(it + 1, new_vector.begin(), new_vector.end()); 76 } 77 GetBlocks()78 const ArenaVector<BasicBlock *> &GetBlocks() const 79 { 80 return rpo_vector_; 81 } 82 83 private: 84 bool RunImpl() override; 85 86 void DFS(BasicBlock *block, size_t *blocks_count); 87 88 private: 89 Marker marker_ {UNDEF_MARKER}; 90 ArenaVector<BasicBlock *> rpo_vector_; 91 }; 92 } // namespace panda::compiler 93 94 #endif // COMPILER_OPTIMIZER_ANALYSIS_RPO_H 95