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_LINEAR_ORDER_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_LINEAR_ORDER_H 18 19 #include "optimizer/ir/marker.h" 20 #include "optimizer/pass.h" 21 #include "utils/arena_containers.h" 22 23 namespace ark::compiler { 24 class BasicBlock; 25 class Graph; 26 27 /* 28 * For each `If` block place its false-successor in the next position of the `linear_blocks_` vector: 29 * - inverse type of IfInst if true-successor is placed first; 30 * - marks `If` block with `JumpFlag` (so `Codegen` could insert `jmp`) if there are no `If` successors 31 * placed just after it; 32 */ 33 class LinearOrder : public Analysis { 34 public: 35 explicit LinearOrder(Graph *graph); 36 37 bool RunImpl() override; 38 GetPassName()39 const char *GetPassName() const override 40 { 41 return "BlocksLinearOrder"; 42 } 43 GetBlocks()44 ArenaVector<BasicBlock *> &GetBlocks() 45 { 46 return linearBlocks_; 47 } 48 GetBlocks()49 const ArenaVector<BasicBlock *> &GetBlocks() const 50 { 51 return linearBlocks_; 52 } 53 54 NO_MOVE_SEMANTIC(LinearOrder); 55 NO_COPY_SEMANTIC(LinearOrder); 56 ~LinearOrder() override = default; 57 58 private: 59 void HandlePrevInstruction(BasicBlock *block, BasicBlock *prevBlock); 60 void HandleIfBlock(BasicBlock *ifTrueBlock, BasicBlock *nextBlock); 61 template <class T> 62 void MakeLinearOrder(const T &blocks); 63 void DumpUnreachableBlocks(); 64 65 private: 66 BasicBlock *LeastLikelySuccessor(const BasicBlock *block); 67 BasicBlock *LeastLikelySuccessorByBranchCounter(const BasicBlock *block); 68 BasicBlock *LeastLikelySuccessorByPreference(const BasicBlock *block); 69 // mark pre exit blocks without Retrurn and ReturnVoid instructions 70 void MarkSideExitsBlocks(); 71 int64_t GetBranchCounter(const BasicBlock *block, bool trueSucc); 72 bool IsConditionChainCounter(const BasicBlock *block); 73 int64_t GetConditionChainCounter(const BasicBlock *block, bool trueSucc); 74 int64_t GetConditionChainTrueSuccessorCounter(const BasicBlock *block); 75 int64_t GetConditionChainFalseSuccessorCounter(const BasicBlock *block); 76 // similar to DFS but move least frequent branch to the end 77 template <bool DEFER_LEAST_FREQUENT> 78 void DFSAndDeferLeastFrequentBranches(BasicBlock *block, size_t *blocksCount); 79 Marker marker_ {UNDEF_MARKER}; 80 Marker blocksMarker_ {UNDEF_MARKER}; 81 ArenaVector<BasicBlock *> linearBlocks_; 82 ArenaList<BasicBlock *> rpoBlocks_; 83 ArenaVector<BasicBlock *> reorderedBlocks_; 84 }; 85 } // namespace ark::compiler 86 #endif // COMPILER_OPTIMIZER_ANALYSIS_LINEAR_ORDER_H 87