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