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