1 /* 2 * Copyright (c) 2021-2023 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_OPTIMIZATIONS_BRANCH_ELIMINATION_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_BRANCH_ELIMINATION_H 18 19 #include "optimizer/ir/graph.h" 20 #include "optimizer/pass.h" 21 #include "utils/arena_containers.h" 22 23 namespace panda::compiler { 24 class BranchElimination : public Optimization { 25 struct ConditionOps { 26 Inst *lhs; 27 Inst *rhs; 28 }; 29 30 struct CcEqual { operatorCcEqual31 bool operator()(const ConditionOps &obj1, const ConditionOps &obj2) const 32 { 33 return std::tie(obj1.lhs, obj1.rhs) == std::tie(obj2.lhs, obj2.rhs) || 34 std::tie(obj1.lhs, obj1.rhs) == std::tie(obj2.rhs, obj2.lhs); 35 } 36 }; 37 38 struct CcHash { operatorCcHash39 uint32_t operator()(const ConditionOps &obj) const 40 { 41 uint32_t hash = std::hash<Inst *> {}(obj.lhs); 42 hash += std::hash<Inst *> {}(obj.rhs); 43 return hash; 44 } 45 }; 46 47 public: 48 explicit BranchElimination(Graph *graph); 49 50 NO_MOVE_SEMANTIC(BranchElimination); 51 NO_COPY_SEMANTIC(BranchElimination); 52 ~BranchElimination() override = default; 53 54 bool RunImpl() override; 55 IsEnable()56 bool IsEnable() const override 57 { 58 return g_options.IsCompilerBranchElimination(); 59 } 60 GetPassName()61 const char *GetPassName() const override 62 { 63 return "BranchElimination"; 64 } 65 void InvalidateAnalyses() override; 66 67 private: 68 bool SkipForOsr(const BasicBlock *block); 69 void VisitBlock(BasicBlock *ifBlock); 70 void EliminateBranch(BasicBlock *ifBlock, BasicBlock *eliminatedBlock); 71 void MarkUnreachableBlocks(BasicBlock *block); 72 void DisconnectBlocks(); 73 std::optional<bool> GetConditionResult(Inst *condition); 74 std::optional<bool> TryResolveResult(Inst *condition, Inst *dominantCondition, IfImmInst *ifImmBlock); 75 void BranchEliminationConst(BasicBlock *ifBlock); 76 void BranchEliminationCompare(BasicBlock *ifBlock); 77 void BranchEliminationCompareAnyType(BasicBlock *ifBlock); 78 std::optional<bool> GetCompareAnyTypeResult(IfImmInst *ifImm); 79 std::optional<bool> TryResolveCompareAnyTypeResult(CompareAnyTypeInst *compareAny, 80 CompareAnyTypeInst *domCompareAny, IfImmInst *ifImmDomBlock); 81 82 private: 83 bool isApplied_ {false}; 84 Marker rmBlockMarker_ {UNDEF_MARKER}; 85 ArenaUnorderedMap<ConditionOps, InstVector, CcHash, CcEqual> sameInputCompares_; 86 ArenaUnorderedMap<Inst *, ArenaVector<CompareAnyTypeInst *>> sameInputCompareAnyType_; 87 }; 88 89 } // namespace panda::compiler 90 91 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_BRANCH_ELIMINATION_H 92