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_PEEPHOLES_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_PEEPHOLES_H 18 19 #include "optimizer/ir/graph.h" 20 #include "optimizer/pass.h" 21 22 #include "compiler_logger.h" 23 #include "optimizer/ir/analysis.h" 24 #include "optimizer/ir/graph_visitor.h" 25 26 namespace panda::compiler { 27 28 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage) 29 #define PEEPHOLE_IS_APPLIED(visitor, inst) (visitor)->SetIsApplied((inst), true, __FILE__, __LINE__) 30 31 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 32 class Peepholes : public Optimization, public GraphVisitor { 33 using Optimization::Optimization; 34 35 public: Peepholes(Graph * graph)36 explicit Peepholes(Graph *graph) : Optimization(graph) {} 37 38 NO_MOVE_SEMANTIC(Peepholes); 39 NO_COPY_SEMANTIC(Peepholes); 40 ~Peepholes() override = default; 41 42 bool RunImpl() override; 43 GetPassName()44 const char *GetPassName() const override 45 { 46 return "Peepholes"; 47 } 48 IsApplied()49 bool IsApplied() const 50 { 51 return isApplied_; 52 } 53 54 void InvalidateAnalyses() override; 55 GetBlocksToVisit()56 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override 57 { 58 return GetGraph()->GetBlocksRPO(); 59 } 60 #include "intrinsics_peephole.inl.h" 61 62 static void VisitSafePoint([[maybe_unused]] GraphVisitor *v, Inst *inst); 63 static void VisitNeg([[maybe_unused]] GraphVisitor *v, Inst *inst); 64 static void VisitAbs([[maybe_unused]] GraphVisitor *v, Inst *inst); 65 static void VisitNot([[maybe_unused]] GraphVisitor *v, Inst *inst); 66 static void VisitAdd([[maybe_unused]] GraphVisitor *v, Inst *inst); 67 static void VisitAddFinalize([[maybe_unused]] GraphVisitor *v, Inst *inst, Inst *input0, Inst *input1); 68 static void VisitSub([[maybe_unused]] GraphVisitor *v, Inst *inst); 69 static void VisitSubFinalize([[maybe_unused]] GraphVisitor *v, Inst *inst, Inst *input0, Inst *input1); 70 static void VisitMulOneConst([[maybe_unused]] GraphVisitor *v, Inst *inst, Inst *input0, Inst *input1); 71 static void VisitMul([[maybe_unused]] GraphVisitor *v, Inst *inst); 72 static void VisitDiv([[maybe_unused]] GraphVisitor *v, Inst *inst); 73 static void VisitMin([[maybe_unused]] GraphVisitor *v, Inst *inst); 74 static void VisitMax([[maybe_unused]] GraphVisitor *v, Inst *inst); 75 static void VisitMod([[maybe_unused]] GraphVisitor *v, Inst *inst); 76 static void VisitShl([[maybe_unused]] GraphVisitor *v, Inst *inst); 77 static void VisitShr([[maybe_unused]] GraphVisitor *v, Inst *inst); 78 static void VisitAShr([[maybe_unused]] GraphVisitor *v, Inst *inst); 79 static void VisitAnd([[maybe_unused]] GraphVisitor *v, Inst *inst); 80 static void VisitOr([[maybe_unused]] GraphVisitor *v, Inst *inst); 81 static void VisitXor([[maybe_unused]] GraphVisitor *v, Inst *inst); 82 static void VisitCmp(GraphVisitor *v, Inst *inst); 83 static void VisitCompare([[maybe_unused]] GraphVisitor *v, Inst *inst); 84 static void VisitIf(GraphVisitor *v, Inst *inst); 85 static void VisitCast([[maybe_unused]] GraphVisitor *v, Inst *inst); 86 static void VisitCastCase1([[maybe_unused]] GraphVisitor *v, Inst *inst); 87 static void VisitCastCase2([[maybe_unused]] GraphVisitor *v, Inst *inst); 88 static void VisitCastCase3([[maybe_unused]] GraphVisitor *v, Inst *inst); 89 static void VisitLenArray(GraphVisitor *v, Inst *inst); 90 static void VisitPhi([[maybe_unused]] GraphVisitor *v, Inst *inst); 91 static void VisitSqrt([[maybe_unused]] GraphVisitor *v, Inst *inst); 92 static void VisitIsInstance(GraphVisitor *v, Inst *inst); 93 static void VisitCastAnyTypeValue(GraphVisitor *v, Inst *inst); 94 static void VisitCastValueToAnyType(GraphVisitor *v, Inst *inst); 95 static void VisitCompareAnyType(GraphVisitor *v, Inst *inst); 96 static void VisitStore([[maybe_unused]] GraphVisitor *v, Inst *inst); 97 static void VisitStoreObject([[maybe_unused]] GraphVisitor *v, Inst *inst); 98 static void VisitStoreStatic([[maybe_unused]] GraphVisitor *v, Inst *inst); 99 static void VisitAddOverflowCheck([[maybe_unused]] GraphVisitor *v, Inst *inst); 100 static void VisitSubOverflowCheck([[maybe_unused]] GraphVisitor *v, Inst *inst); 101 static void VisitNegOverflowAndZeroCheck([[maybe_unused]] GraphVisitor *v, Inst *inst); 102 static void VisitGetInstanceClass([[maybe_unused]] GraphVisitor *v, Inst *inst); 103 static void VisitLoadAndInitClass([[maybe_unused]] GraphVisitor *v, Inst *inst); 104 static void VisitInitClass([[maybe_unused]] GraphVisitor *v, Inst *inst); 105 static void VisitIntrinsic([[maybe_unused]] GraphVisitor *v, Inst *inst); 106 static void VisitLoadClass([[maybe_unused]] GraphVisitor *v, Inst *inst); 107 static void VisitLoadConstantPool([[maybe_unused]] GraphVisitor *v, Inst *inst); 108 static void VisitLoadFromConstantPool([[maybe_unused]] GraphVisitor *v, Inst *inst); 109 110 #include "optimizer/ir/visitor.inc" 111 112 private: 113 void SetIsApplied(Inst *inst, bool altFormat = false, const char *file = nullptr, int line = 0) 114 { 115 isApplied_ = true; 116 if (altFormat) { 117 COMPILER_LOG(DEBUG, PEEPHOLE) << "Peephole (" << file << ":" << line << ") is applied for " << *inst; 118 } else { 119 COMPILER_LOG(DEBUG, PEEPHOLE) << "Peephole is applied for " << GetOpcodeString(inst->GetOpcode()); 120 } 121 inst->GetBasicBlock()->GetGraph()->GetEventWriter().EventPeephole(GetOpcodeString(inst->GetOpcode()), 122 inst->GetId(), inst->GetPc()); 123 if (g_options.IsCompilerDumpPeepholes()) { 124 std::string name(GetPassName()); 125 name += "_" + std::to_string(applyIndex_); 126 GetGraph()->GetPassManager()->DumpGraph(name.c_str()); 127 applyIndex_++; 128 } 129 } 130 131 // This function check that we can merge two Phi instructions in one basic block. 132 static bool IsPhiUnionPossible(PhiInst *phi1, PhiInst *phi2); 133 134 // Get power of 2 135 // if n not power of 2 return -1; 136 static int64_t GetPowerOfTwo(uint64_t n); 137 138 // Create new instruction instead of current inst 139 static Inst *CreateAndInsertInst(Opcode newOpc, Inst *currInst, Inst *input0, Inst *input1 = nullptr); 140 141 // Try put constant in second input 142 void TrySwapInputs(Inst *inst); 143 144 // Try to remove redundant cast 145 void TrySimplifyCastToOperandsType(Inst *inst); 146 void TrySimplifyShifts(Inst *inst); 147 bool TrySimplifyAddSubWithZeroInput(Inst *inst); 148 bool TrySimplifyAddSubWithConstInput(Inst *inst); 149 template <Opcode OPC, int IDX> 150 void TrySimplifyAddSub(Inst *inst, Inst *input0, Inst *input1); 151 bool TrySimplifyAddSubAdd(Inst *inst, Inst *input0, Inst *input1); 152 bool TrySimplifyAddSubSub(Inst *inst, Inst *input0, Inst *input1); 153 bool TrySimplifySubAddAdd(Inst *inst, Inst *input0, Inst *input1); 154 bool TrySimplifyShlShlAdd(Inst *inst); 155 bool TryReassociateShlShlAddSub(Inst *inst); 156 void TrySimplifyNeg(Inst *inst); 157 void TryReplaceDivByShrAndAshr(Inst *inst, uint64_t unsignedVal, Inst *input0); 158 void TryReplaceDivByShift(Inst *inst); 159 bool TrySimplifyCompareCaseInputInv(Inst *inst, Inst *input); 160 bool TrySimplifyCompareWithBoolInput(Inst *inst, bool *isOsrBlocked); 161 bool TrySimplifyCmpCompareWithZero(Inst *inst, bool *isOsrBlocked); 162 bool TrySimplifyTestEqualInputs(Inst *inst); 163 void TryRemoveOverflowCheck(Inst *inst); 164 static bool TrySimplifyCompareAndZero(Inst *inst, bool *isOsrBlocked); 165 static bool TrySimplifyCompareAnyType(Inst *inst); 166 static bool TrySimplifyCompareAnyTypeCase1(Inst *inst, Inst *input0, Inst *input1); 167 static bool TrySimplifyCompareAnyTypeCase2(Inst *inst, Inst *input0, Inst *input1); 168 static bool TrySimplifyCompareLenArrayWithZero(Inst *inst); 169 // Try to combine constants when arithmetic operations with constants are repeated 170 template <typename T> 171 static bool TryCombineConst(Inst *inst, ConstantInst *cnst1, T combine, bool *isOsrBlocked); 172 static bool TryCombineAddSubConst(Inst *inst, ConstantInst *cnst1, bool *isOsrBlocked); 173 static bool TryCombineShiftConst(Inst *inst, ConstantInst *cnst1, bool *isOsrBlocked); 174 static bool TryCombineMulConst(Inst *inst, ConstantInst *cnst1, bool *isOsrBlocked); 175 176 static bool GetInputsOfCompareWithConst(const Inst *inst, Inst **input, ConstantInst **constInput, 177 bool *inputsSwapped); 178 179 static bool CreateCompareInsteadOfXorAdd(Inst *oldInst); 180 181 bool OptimizeLenArrayForMultiArray(Inst *lenArray, Inst *inst, size_t indexSize); 182 static bool TryEliminatePhi(PhiInst *phi); 183 // It is check can we use this peephole in OSR or not 184 static bool SkipThisPeepholeInOSR(Inst *inst, Inst *newInput); 185 186 // Table for eliminating 'Compare <CC> <INPUT>, <CONST>' 187 enum InputCode { 188 INPUT_TRUE, // Result of compare is TRUE whatever the INPUT is 189 INPUT_ORIG, // Result of compare is equal to the INPUT itself 190 INPUT_INV, // Result of compare is a negation of the INPUT 191 INPUT_FALSE, // Result of compare is FALSE whatever the INPUT is 192 INPUT_UNDEF // Result of compare is undefined 193 }; 194 // clang-format off 195 static constexpr std::array<std::array<InputCode, 4>, CC_LAST + 1> VALUES = {{ 196 /* CONST < 0 CONST == 0 CONST == 1 CONST > 1 CC */ 197 {INPUT_FALSE, INPUT_INV, INPUT_ORIG, INPUT_FALSE}, /* CC_EQ */ 198 {INPUT_TRUE, INPUT_ORIG, INPUT_INV, INPUT_TRUE}, /* CC_NE */ 199 {INPUT_FALSE, INPUT_FALSE, INPUT_INV, INPUT_TRUE}, /* CC_LT */ 200 {INPUT_FALSE, INPUT_INV, INPUT_TRUE, INPUT_TRUE}, /* CC_LE */ 201 {INPUT_TRUE, INPUT_ORIG, INPUT_FALSE, INPUT_FALSE}, /* CC_GT */ 202 {INPUT_TRUE, INPUT_TRUE, INPUT_ORIG, INPUT_FALSE}, /* CC_GE */ 203 /* For unsigned comparison 'CONST < 0' equals to 'CONST > 1' */ 204 {INPUT_TRUE, INPUT_FALSE, INPUT_INV, INPUT_TRUE}, /* CC_B */ 205 {INPUT_TRUE, INPUT_INV, INPUT_TRUE, INPUT_TRUE}, /* CC_BE */ 206 {INPUT_FALSE, INPUT_ORIG, INPUT_FALSE, INPUT_FALSE}, /* CC_A */ 207 {INPUT_FALSE, INPUT_TRUE, INPUT_ORIG, INPUT_FALSE} /* CC_AE */ 208 }}; 209 // clang-format on GetInputCode(const ConstantInst * inst,ConditionCode cc)210 static InputCode GetInputCode(const ConstantInst *inst, ConditionCode cc) 211 { 212 if (inst->GetType() == DataType::INT32) { 213 auto i = std::min<int32_t>(std::max<int32_t>(-1, static_cast<int32_t>(inst->GetInt32Value())), 2U) + 1; 214 return VALUES[cc][i]; 215 } 216 if (inst->GetType() == DataType::INT64) { 217 auto i = std::min<int64_t>(std::max<int64_t>(-1, static_cast<int64_t>(inst->GetIntValue())), 2U) + 1; 218 return VALUES[cc][i]; 219 } 220 UNREACHABLE(); 221 return InputCode::INPUT_UNDEF; 222 } 223 template <typename T> 224 static void EliminateInstPrecedingStore(GraphVisitor *v, Inst *inst); 225 bool TrySimplifyCompareNegation(Inst *inst); 226 bool IsNegationPattern(Inst *inst); 227 bool TrySimplifyNegationPattern(Inst *inst); 228 bool IsCastWithNagationPattern(Inst *inst); 229 230 private: 231 // Each peephole application has own unique index, it will be used in peepholes dumps 232 uint32_t applyIndex_ {0}; 233 234 bool isApplied_ {false}; 235 }; 236 } // namespace panda::compiler 237 238 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_PEEPHOLES_H 239