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_OPTIMIZATIONS_CHECKSELIMINATION_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_CHECKSELIMINATION_H 18 19 #include "optimizer/ir/graph.h" 20 #include "optimizer/pass.h" 21 22 #include "compiler_logger.h" 23 #include "object_type_check_elimination.h" 24 #include "optimizer/analysis/bounds_analysis.h" 25 #include "optimizer/analysis/countable_loop_parser.h" 26 #include "optimizer/analysis/dominators_tree.h" 27 #include "optimizer/analysis/loop_analyzer.h" 28 #include "optimizer/analysis/object_type_propagation.h" 29 #include "optimizer/ir/graph_visitor.h" 30 31 namespace ark::compiler { 32 // {parent_index, Vector<bound_check>, max_val, min_val} 33 using GroupedBoundsChecks = ArenaVector<std::tuple<Inst *, InstVector, int64_t, int64_t>>; 34 // loop->len_array->GroupedBoundsChecks 35 using LoopNotFullyRedundantBoundsCheck = ArenaVector<std::pair<Inst *, GroupedBoundsChecks>>; 36 using NotFullyRedundantBoundsCheck = ArenaVector<std::pair<Loop *, LoopNotFullyRedundantBoundsCheck>>; 37 38 // {CountableLoopInfo; savestate; lower value; upper value; cond code for Deoptimize; head is loop exit; has pre-header 39 // compare} 40 using LoopInfo = std::tuple<CountableLoopInfo, Inst *, Inst *, Inst *, ConditionCode, bool, bool>; 41 42 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 43 class ChecksElimination : public Optimization, public GraphVisitor { 44 using Optimization::Optimization; 45 46 public: ChecksElimination(Graph * graph)47 explicit ChecksElimination(Graph *graph) 48 : Optimization(graph), 49 boundsChecks_(graph->GetLocalAllocator()->Adapter()), 50 checksForMoveOutOfLoop_(graph->GetLocalAllocator()->Adapter()), 51 checksMustThrow_(graph->GetLocalAllocator()->Adapter()) 52 { 53 } 54 55 NO_MOVE_SEMANTIC(ChecksElimination); 56 NO_COPY_SEMANTIC(ChecksElimination); 57 ~ChecksElimination() override = default; 58 59 bool RunImpl() override; 60 GetPassName()61 const char *GetPassName() const override 62 { 63 return "ChecksElimination"; 64 } 65 IsApplied()66 bool IsApplied() const 67 { 68 return isApplied_; 69 } SetApplied()70 void SetApplied() 71 { 72 isApplied_ = true; 73 } 74 IsLoopDeleted()75 bool IsLoopDeleted() const 76 { 77 return isLoopDeleted_; 78 } SetLoopDeleted()79 void SetLoopDeleted() 80 { 81 isLoopDeleted_ = true; 82 } 83 IsEnable()84 bool IsEnable() const override 85 { 86 return g_options.IsCompilerChecksElimination(); 87 } 88 89 void InvalidateAnalyses() override; 90 GetBlocksToVisit()91 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override 92 { 93 return GetGraph()->GetBlocksRPO(); 94 } 95 96 template <bool CHECK_FULL_DOM = false> 97 static void VisitNullCheck(GraphVisitor *v, Inst *inst); 98 static void VisitNegativeCheck(GraphVisitor *v, Inst *inst); 99 static void VisitNotPositiveCheck(GraphVisitor *v, Inst *inst); 100 static void VisitZeroCheck(GraphVisitor *v, Inst *inst); 101 static void VisitRefTypeCheck(GraphVisitor *v, Inst *inst); 102 static void VisitBoundsCheck(GraphVisitor *v, Inst *inst); 103 static void VisitCheckCast(GraphVisitor *v, Inst *inst); 104 static void VisitIsInstance(GraphVisitor *v, Inst *inst); 105 static void VisitAnyTypeCheck(GraphVisitor *v, Inst *inst); 106 static void VisitHclassCheck(GraphVisitor *v, Inst *inst); 107 static void VisitAddOverflowCheck(GraphVisitor *v, Inst *inst); 108 static void VisitSubOverflowCheck(GraphVisitor *v, Inst *inst); 109 static void VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst); 110 111 #include "optimizer/ir/visitor.inc" 112 private: 113 bool TryToEliminateAnyTypeCheck(Inst *inst, Inst *instToReplace, AnyBaseType type, AnyBaseType prevType); 114 void UpdateHclassChecks(Inst *inst); 115 std::optional<Inst *> GetHclassCheckFromLoads(Inst *loadClass); 116 void ReplaceUsersAndRemoveCheck(Inst *instDel, Inst *instRep); PushNewCheckForMoveOutOfLoop(Inst * anyTypeCheck)117 void PushNewCheckForMoveOutOfLoop(Inst *anyTypeCheck) 118 { 119 checksForMoveOutOfLoop_.push_back(anyTypeCheck); 120 } 121 PushNewCheckMustThrow(Inst * inst)122 void PushNewCheckMustThrow(Inst *inst) 123 { 124 checksMustThrow_.push_back(inst); 125 } 126 127 static bool IsInstIncOrDec(Inst *inst); 128 static int64_t GetInc(Inst *inst); 129 static Loop *GetLoopForBoundsCheck(BasicBlock *block, Inst *lenArray, Inst *index); 130 void InitItemForNewIndex(GroupedBoundsChecks *place, Inst *index, Inst *inst, bool checkUpper, bool checkLower); 131 void PushNewBoundsCheck(Loop *loop, Inst *lenArray, Inst *index, Inst *inst, bool checkUpper, bool checkLower); 132 void PushNewBoundsCheckAtExistingIndexes(GroupedBoundsChecks *indexes, Inst *index, Inst *inst, bool checkUpper, 133 bool checkLower); 134 void TryRemoveDominatedNullChecks(Inst *inst, Inst *ref); 135 void TryRemoveDominatedHclassCheck(Inst *inst); 136 template <Opcode OPC, bool CHECK_FULL_DOM, typename CheckInputs> 137 void TryRemoveDominatedCheck(Inst *inst, Inst *userInst, CheckInputs checkInputs); 138 template <Opcode OPC, bool CHECK_FULL_DOM = false, typename CheckInputs = bool (*)(Inst *)> 139 void TryRemoveDominatedChecks( 140 Inst *inst, CheckInputs checkInputs = [](Inst * /*unused*/) { return true; }); 141 template <Opcode OPC> 142 void TryRemoveConsecutiveChecks(Inst *inst); 143 template <Opcode OPC> 144 bool TryRemoveCheckByBounds(Inst *inst, Inst *input); 145 template <Opcode OPC, bool CHECK_FULL_DOM = false> 146 bool TryRemoveCheck(Inst *inst); 147 template <Opcode OPC> 148 void TryOptimizeOverflowCheck(Inst *inst); 149 150 bool TryInsertDeoptimizationForLargeStep(ConditionCode cc, Inst *resultLenArray, Inst *lower, Inst *upper, 151 int64_t maxAdd, Inst *insertDeoptAfter, Inst *ss, uint64_t constStep); 152 bool TryInsertDeoptimization(LoopInfo loopInfo, Inst *lenArray, int64_t maxAdd, int64_t minAdd, 153 bool hasCheckInHeader); 154 155 Inst *InsertNewLenArray(Inst *lenArray, Inst *ss); 156 bool NeedUpperDeoptimization(BasicBlock *header, Inst *lenArray, BoundsRange lenArrayRange, Inst *upper, 157 BoundsRange upperRange, int64_t maxAdd, ConditionCode cc, bool *insertNewLenArray); 158 void InsertDeoptimizationForIndexOverflow(CountableLoopInfo *countableLoopInfo, BoundsRange indexUpperRange, 159 Inst *ss); 160 void ProcessingLoop(Loop *loop, LoopNotFullyRedundantBoundsCheck *lenarrIndexChecks); 161 void ProcessingGroupBoundsCheck(GroupedBoundsChecks *indexBoundschecks, LoopInfo loopInfo, Inst *lenArray); 162 void ReplaceBoundsCheckToDeoptimizationBeforeLoop(); 163 void HoistLoopInvariantBoundsChecks(Inst *lenArray, GroupedBoundsChecks *indexBoundschecks, Loop *loop); 164 Inst *FindSaveState(const InstVector &instsToDelete); 165 void ReplaceBoundsCheckToDeoptimizationInLoop(); 166 void ReplaceOneBoundsCheckToDeoptimizationInLoop(std::pair<Loop *, LoopNotFullyRedundantBoundsCheck> &item); 167 168 void ReplaceCheckMustThrowByUnconditionalDeoptimize(); 169 void MoveCheckOutOfLoop(); 170 171 void InsertInstAfter(Inst *inst, Inst *after, BasicBlock *block); 172 void InsertBoundsCheckDeoptimization(ConditionCode cc, Inst *left, int64_t val, Inst *right, Inst *ss, 173 Inst *insertAfter, Opcode newLeftOpcode = Opcode::Add); 174 Inst *InsertDeoptimization(ConditionCode cc, Inst *left, Inst *right, Inst *ss, Inst *insertAfter, 175 DeoptimizeType deoptType); 176 177 std::optional<LoopInfo> FindLoopInfo(Loop *loop); 178 Inst *FindSaveState(Loop *loop); 179 Inst *FindOptimalSaveStateForHoist(Inst *inst, Inst **optimalInsertAfter); 180 static bool IsInlinedCallLoadMethod(Inst *inst); 181 182 private: 183 NotFullyRedundantBoundsCheck boundsChecks_; 184 InstVector checksForMoveOutOfLoop_; 185 InstVector checksMustThrow_; 186 187 bool isApplied_ {false}; 188 bool isLoopDeleted_ {false}; 189 }; 190 } // namespace ark::compiler 191 192 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_CHECKSELIMINATION_H 193