1 /* 2 * Copyright (c) 2021-2025 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_LOWERING_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_LOWERING_H 18 19 #include "compiler_logger.h" 20 #include "compiler_options.h" 21 #include "optimizer/ir/analysis.h" 22 #include "optimizer/ir/graph.h" 23 #include "optimizer/ir/graph_visitor.h" 24 25 namespace ark::compiler { 26 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 27 class PANDA_PUBLIC_API Lowering : public Optimization, public GraphVisitor { 28 using Optimization::Optimization; 29 30 public: Lowering(Graph * graph)31 explicit Lowering(Graph *graph) : Optimization(graph) {} 32 33 bool RunImpl() override; 34 IsEnable()35 bool IsEnable() const override 36 { 37 return g_options.IsCompilerLowering(); 38 } 39 GetPassName()40 const char *GetPassName() const override 41 { 42 return "Lowering"; 43 } 44 45 void InvalidateAnalyses() override; 46 47 static constexpr uint8_t HALF_SIZE = 32; 48 static constexpr uint8_t WORD_SIZE = 64; 49 50 private: 51 /** 52 * Utility template classes aimed to simplify pattern matching over IR-graph. 53 * Patterns are trees declared as a type using Any, UnaryOp, BinaryOp and Operand composition. 54 * Then IR-subtree could be tested for matching by calling static Capture method. 55 * To capture operands from matched subtree Operand<Index> should be used, where 56 * Index is an operand's index within OperandsCapture. 57 * 58 * For example, suppose that we want to test if IR-subtree rooted by some Inst matches add or sub instruction 59 * pattern: 60 * 61 * Inst* inst = ...; 62 * using Predicate = Any<BinaryOp<Opcode::Add, Operand<0>, Operand<1>, 63 * BinaryOp<Opcode::Sub, Operand<0>, Operand<1>>; 64 * OperandsCapture<2> capture{}; 65 * bool is_add_or_sub = Predicate::Capture(inst, capture); 66 * 67 * If inst is a binary instruction with opcode Add or Sub then Capture will return `true`, 68 * capture.Get(0) will return left inst's input and capture.Get(1) will return right inst's input. 69 */ 70 71 // Flags altering matching behavior. 72 enum Flags { 73 NONE = 0, 74 COMMUTATIVE = 1, // binary operation is commutative 75 C = COMMUTATIVE, 76 SINGLE_USER = 2, // operation must have only single user 77 S = SINGLE_USER 78 }; 79 IsSet(uint64_t flags,Flags flag)80 static bool IsSet(uint64_t flags, Flags flag) 81 { 82 return (flags & flag) != 0; 83 } 84 IsNotSet(uint64_t flags,Flags flag)85 static bool IsNotSet(uint64_t flags, Flags flag) 86 { 87 return (flags & flag) == 0; 88 } 89 90 template <size_t MAX_OPERANDS> 91 class OperandsCapture { 92 public: Get(size_t i)93 Inst *Get(size_t i) 94 { 95 ASSERT(i < MAX_OPERANDS); 96 return operands_[i]; 97 } 98 Set(size_t i,Inst * inst)99 void Set(size_t i, Inst *inst) 100 { 101 ASSERT(i < MAX_OPERANDS); 102 #pragma GCC diagnostic push 103 // CC-OFFNXT(warning_suppression) GCC false positive 104 #pragma GCC diagnostic ignored "-Warray-bounds" 105 operands_[i] = inst; 106 #pragma GCC diagnostic pop 107 } 108 109 // Returns true if all non-constant operands have the same common type (obtained using GetCommonType) as all 110 // other operands. HaveCommonType()111 bool HaveCommonType() const 112 { 113 auto nonConstType = DataType::LAST; 114 for (size_t i = 0; i < MAX_OPERANDS; i++) { 115 if (operands_[i]->GetOpcode() != Opcode::Constant) { 116 nonConstType = GetCommonType(operands_[i]->GetType()); 117 break; 118 } 119 } 120 // all operands are constants 121 if (nonConstType == DataType::LAST) { 122 nonConstType = operands_[0]->GetType(); 123 } 124 for (size_t i = 0; i < MAX_OPERANDS; i++) { 125 if (operands_[i]->GetOpcode() == Opcode::Constant) { 126 if (GetCommonType(operands_[i]->GetType()) != GetCommonType(nonConstType)) { 127 return false; 128 } 129 } else if (nonConstType != GetCommonType(operands_[i]->GetType())) { 130 return false; 131 } 132 } 133 return true; 134 } 135 136 private: 137 std::array<Inst *, MAX_OPERANDS> operands_; 138 }; 139 140 template <size_t MAX_INSTS> 141 class InstructionsCapture { 142 public: Add(Inst * inst)143 void Add(Inst *inst) 144 { 145 ASSERT(currentIdx_ < MAX_INSTS); 146 insts_[currentIdx_++] = inst; 147 } 148 GetCurrentIndex()149 size_t GetCurrentIndex() const 150 { 151 return currentIdx_; 152 } 153 SetCurrentIndex(size_t idx)154 void SetCurrentIndex(size_t idx) 155 { 156 ASSERT(idx < MAX_INSTS); 157 currentIdx_ = idx; 158 } 159 160 // Returns true if all non-constant operands have exactly the same type and all 161 // constant arguments have the same common type (obtained using GetCommonType) as all other operands. HaveSameType()162 bool HaveSameType() const 163 { 164 ASSERT(currentIdx_ == MAX_INSTS); 165 auto nonConstType = DataType::LAST; 166 for (size_t i = 0; i < MAX_INSTS; i++) { 167 if (insts_[i]->GetOpcode() != Opcode::Constant) { 168 nonConstType = insts_[i]->GetType(); 169 break; 170 } 171 } 172 // all operands are constants 173 if (nonConstType == DataType::LAST) { 174 nonConstType = insts_[0]->GetType(); 175 } 176 for (size_t i = 0; i < MAX_INSTS; i++) { 177 if (insts_[i]->GetOpcode() == Opcode::Constant) { 178 if (GetCommonType(insts_[i]->GetType()) != GetCommonType(nonConstType)) { 179 return false; 180 } 181 } else if (nonConstType != insts_[i]->GetType()) { 182 return false; 183 } 184 } 185 return true; 186 } 187 ResetIndex()188 InstructionsCapture &ResetIndex() 189 { 190 currentIdx_ = 0; 191 return *this; 192 } 193 194 private: 195 std::array<Inst *, MAX_INSTS> insts_ {}; 196 size_t currentIdx_ = 0; 197 }; 198 199 template <Opcode OPCODE, typename L, typename R, uint64_t FLAGS = Flags::NONE> 200 struct BinaryOp { 201 template <size_t MAX_OPERANDS, size_t MAX_INSTS> CaptureBinaryOp202 static bool Capture(Inst *inst, OperandsCapture<MAX_OPERANDS> &args, InstructionsCapture<MAX_INSTS> &insts) 203 { 204 constexpr auto INPUTS_NUM = 2; 205 // NOLINTNEXTLINE(readability-magic-numbers) 206 if (inst->GetOpcode() != OPCODE || inst->GetInputsCount() != INPUTS_NUM || 207 (IsSet(FLAGS, Flags::SINGLE_USER) && !inst->HasSingleUser())) { 208 return false; 209 } 210 if (L::Capture(inst->GetInput(0).GetInst(), args, insts) && 211 R::Capture(inst->GetInput(1).GetInst(), args, insts)) { 212 insts.Add(inst); 213 return true; 214 } 215 if (IsSet(FLAGS, Flags::COMMUTATIVE) && L::Capture(inst->GetInput(1).GetInst(), args, insts) && 216 R::Capture(inst->GetInput(0).GetInst(), args, insts)) { 217 insts.Add(inst); 218 return true; 219 } 220 return false; 221 } 222 }; 223 224 template <Opcode OPCODE, typename T, uint64_t FLAGS = Flags::NONE> 225 struct UnaryOp { 226 template <size_t MAX_OPERANDS, size_t MAX_INSTS> CaptureUnaryOp227 static bool Capture(Inst *inst, OperandsCapture<MAX_OPERANDS> &args, InstructionsCapture<MAX_INSTS> &insts) 228 { 229 // NOLINTNEXTLINE(readability-magic-numbers) 230 bool matched = inst->GetOpcode() == OPCODE && inst->GetInputsCount() == 1 && 231 (IsNotSet(FLAGS, Flags::SINGLE_USER) || inst->HasSingleUser()) && 232 T::Capture(inst->GetInput(0).GetInst(), args, insts); 233 if (matched) { 234 insts.Add(inst); 235 } 236 return matched; 237 } 238 }; 239 240 template <size_t IDX> 241 struct Operand { 242 template <size_t MAX_OPERANDS, size_t MAX_INSTS> CaptureOperand243 static bool Capture(Inst *inst, OperandsCapture<MAX_OPERANDS> &args, 244 [[maybe_unused]] InstructionsCapture<MAX_INSTS> &insts) 245 { 246 static_assert(IDX < MAX_OPERANDS, "Operand's index should not exceed OperandsCapture size"); 247 248 args.Set(IDX, inst); 249 return true; 250 } 251 }; 252 253 template <typename T, typename... Args> 254 struct AnyOf { 255 template <size_t MAX_OPERANDS, size_t MAX_INSTS> CaptureAnyOf256 static bool Capture(Inst *inst, OperandsCapture<MAX_OPERANDS> &args, InstructionsCapture<MAX_INSTS> &insts) 257 { 258 size_t instIdx = insts.GetCurrentIndex(); 259 if (T::Capture(inst, args, insts)) { 260 return true; 261 } 262 insts.SetCurrentIndex(instIdx); 263 return AnyOf<Args...>::Capture(inst, args, insts); 264 } 265 }; 266 267 template <typename T> 268 struct AnyOf<T> { 269 template <size_t MAX_OPERANDS, size_t MAX_INSTS> 270 static bool Capture(Inst *inst, OperandsCapture<MAX_OPERANDS> &args, InstructionsCapture<MAX_INSTS> &insts) 271 { 272 return T::Capture(inst, args, insts); 273 } 274 }; 275 276 template <bool ENABLED, typename T> 277 struct MatchIf : public T { 278 }; 279 280 template <typename T> 281 struct MatchIf<false, T> { 282 template <size_t MAX_OPERANDS, size_t MAX_INSTS> 283 // NOLINTNEXTLINE(readability-named-parameter) 284 static bool Capture(Inst *, OperandsCapture<MAX_OPERANDS> &, InstructionsCapture<MAX_INSTS> &) 285 { 286 return false; 287 } 288 }; 289 290 using SRC0 = Operand<0>; 291 using SRC1 = Operand<1>; 292 using SRC2 = Operand<2U>; 293 294 template <typename L, typename R, uint64_t F = Flags::NONE> 295 using ADD = BinaryOp<Opcode::Add, L, R, F | Flags::COMMUTATIVE>; 296 template <typename L, typename R, uint64_t F = Flags::NONE> 297 using SUB = BinaryOp<Opcode::Sub, L, R, F>; 298 template <typename L, typename R, uint64_t F = Flags::NONE> 299 using MUL = BinaryOp<Opcode::Mul, L, R, F | Flags::COMMUTATIVE>; 300 template <typename T, uint64_t F = Flags::NONE> 301 using NEG = UnaryOp<Opcode::Neg, T, F>; 302 template <typename T, uint64_t F = Flags::SINGLE_USER> 303 using NOT = UnaryOp<Opcode::Not, T, F>; 304 template <typename T, uint64_t F = Flags::SINGLE_USER> 305 using SHRI = UnaryOp<Opcode::ShrI, T, F>; 306 template <typename T, uint64_t F = Flags::SINGLE_USER> 307 using ASHRI = UnaryOp<Opcode::AShrI, T, F>; 308 template <typename T, uint64_t F = Flags::SINGLE_USER> 309 using SHLI = UnaryOp<Opcode::ShlI, T, F>; 310 311 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override 312 { 313 return GetGraph()->GetBlocksRPO(); 314 } 315 316 static void VisitAdd([[maybe_unused]] GraphVisitor *v, Inst *inst); 317 static void VisitSub([[maybe_unused]] GraphVisitor *v, Inst *inst); 318 static void VisitCast([[maybe_unused]] GraphVisitor *v, Inst *inst); 319 static void VisitCastValueToAnyType([[maybe_unused]] GraphVisitor *v, Inst *inst); 320 321 template <Opcode OPC> 322 static void VisitBitwiseBinaryOperation([[maybe_unused]] GraphVisitor *v, Inst *inst); 323 static void VisitOr(GraphVisitor *v, Inst *inst); 324 static void VisitAnd(GraphVisitor *v, Inst *inst); 325 static void VisitXor(GraphVisitor *v, Inst *inst); 326 327 static void VisitAndNot([[maybe_unused]] GraphVisitor *v, Inst *inst); 328 static void VisitXorNot([[maybe_unused]] GraphVisitor *v, Inst *inst); 329 static void VisitOrNot([[maybe_unused]] GraphVisitor *v, Inst *inst); 330 static void VisitSaveState([[maybe_unused]] GraphVisitor *v, Inst *inst); 331 static void VisitSafePoint([[maybe_unused]] GraphVisitor *v, Inst *inst); 332 static void VisitSaveStateOsr([[maybe_unused]] GraphVisitor *v, Inst *inst); 333 static void VisitSaveStateDeoptimize([[maybe_unused]] GraphVisitor *v, Inst *inst); 334 static void VisitBoundsCheck([[maybe_unused]] GraphVisitor *v, Inst *inst); 335 static void VisitLoadArray([[maybe_unused]] GraphVisitor *v, Inst *inst); 336 static void VisitLoadCompressedStringChar([[maybe_unused]] GraphVisitor *v, Inst *inst); 337 static void VisitStoreArray([[maybe_unused]] GraphVisitor *v, Inst *inst); 338 static void VisitLoad([[maybe_unused]] GraphVisitor *v, Inst *inst); 339 static void VisitLoadNative([[maybe_unused]] GraphVisitor *v, Inst *inst); 340 static void VisitStore([[maybe_unused]] GraphVisitor *v, Inst *inst); 341 static void VisitStoreNative([[maybe_unused]] GraphVisitor *v, Inst *inst); 342 static void VisitReturn([[maybe_unused]] GraphVisitor *v, Inst *inst); 343 static void VisitShr([[maybe_unused]] GraphVisitor *v, Inst *inst); 344 static void VisitAShr([[maybe_unused]] GraphVisitor *v, Inst *inst); 345 static void VisitShl([[maybe_unused]] GraphVisitor *v, Inst *inst); 346 static void VisitIfImm([[maybe_unused]] GraphVisitor *v, Inst *inst); 347 static void VisitMul([[maybe_unused]] GraphVisitor *v, Inst *inst); 348 static void VisitDiv([[maybe_unused]] GraphVisitor *v, Inst *inst); 349 static void VisitMod([[maybe_unused]] GraphVisitor *v, Inst *inst); 350 static void VisitNeg([[maybe_unused]] GraphVisitor *v, Inst *inst); 351 static void VisitDeoptimizeIf(GraphVisitor *v, Inst *inst); 352 static void VisitLoadFromConstantPool(GraphVisitor *v, Inst *inst); 353 static void VisitCompare(GraphVisitor *v, Inst *inst); 354 355 #include "optimizer/ir/visitor.inc" 356 357 static void InsertInstruction(Inst *inst, Inst *newInst) 358 { 359 inst->InsertBefore(newInst); 360 inst->ReplaceUsers(newInst); 361 newInst->GetBasicBlock()->GetGraph()->GetEventWriter().EventLowering(GetOpcodeString(inst->GetOpcode()), 362 inst->GetId(), inst->GetPc()); 363 COMPILER_LOG(DEBUG, LOWERING) << "Lowering is applied for " << GetOpcodeString(inst->GetOpcode()); 364 } 365 366 template <size_t MAX_OPERANDS> 367 static void SetInputsAndInsertInstruction(OperandsCapture<MAX_OPERANDS> &operands, Inst *inst, Inst *newInst); 368 369 static constexpr Opcode GetInstructionWithShiftedOperand(Opcode opcode); 370 static constexpr Opcode GetInstructionWithInvertedOperand(Opcode opcode); 371 static ShiftType GetShiftTypeByOpcode(Opcode opcode); 372 static Inst *GetCheckInstAndGetConstInput(Inst *inst); 373 static ShiftOpcode ConvertOpcode(Opcode newOpcode); 374 375 static void LowerMemInstScale(Inst *inst); 376 static void LowerShift(Inst *inst); 377 static bool ConstantFitsCompareImm(Inst *cst, uint32_t size, ConditionCode cc); 378 static Inst *LowerAddSub(Inst *inst); 379 template <Opcode OPCODE> 380 static void LowerMulDivMod(Inst *inst); 381 static Inst *LowerMultiplyAddSub(Inst *inst); 382 static Inst *LowerNegateMultiply(Inst *inst); 383 static void LowerLogicWithInvertedOperand(Inst *inst); 384 static bool LowerCastValueToAnyTypeWithConst(Inst *inst); 385 template <typename T, size_t MAX_OPERANDS> 386 static Inst *LowerOperationWithShiftedOperand(Inst *inst, OperandsCapture<MAX_OPERANDS> &operands, Inst *shiftInst, 387 Opcode newOpcode); 388 template <Opcode OPCODE, bool IS_COMMUTATIVE = true> 389 static Inst *LowerBinaryOperationWithShiftedOperand(Inst *inst); 390 template <Opcode OPCODE> 391 static void LowerUnaryOperationWithShiftedOperand(Inst *inst); 392 static Inst *LowerLogic(Inst *inst); 393 template <typename LowLevelType> 394 static void LowerConstArrayIndex(Inst *inst, Opcode lowLevelOpcode); 395 static void LowerStateInst(SaveStateInst *saveState); 396 static void LowerReturnInst(FixedInputsInst1 *ret); 397 // We'd like to swap only to make second operand immediate 398 static bool BetterToSwapCompareInputs(Inst *cmp); 399 // Optimize order of input arguments for decreasing using accumulator (Bytecodeoptimizer only). 400 static void OptimizeIfInput(compiler::Inst *ifInst); 401 static void JoinFcmpInst(IfImmInst *inst, CmpInst *input); 402 void LowerIf(IfImmInst *inst); 403 static void InPlaceLowerIfImm(IfImmInst *inst, Inst *input, Inst *cst, ConditionCode cc, DataType::Type inputType); 404 static void LowerIfImmToIf(IfImmInst *inst, Inst *input, ConditionCode cc, DataType::Type inputType); 405 static void LowerToDeoptimizeCompare(Inst *inst); 406 static bool SatisfyReplaceDivMovConditions(Inst *inst); 407 static bool TryReplaceDivPowerOfTwo(GraphVisitor *v, Inst *inst); 408 static bool TryReplaceDivModNonPowerOfTwo(GraphVisitor *v, Inst *inst); 409 static bool TryReplaceModPowerOfTwo(GraphVisitor *v, Inst *inst); 410 static void ReplaceSignedModPowerOfTwo(GraphVisitor *v, Inst *inst, uint64_t absValue); 411 static void ReplaceUnsignedModPowerOfTwo(GraphVisitor *v, Inst *inst, uint64_t absValue); 412 static void ReplaceSignedDivPowerOfTwo(GraphVisitor *v, Inst *inst, int64_t sValue); 413 static void ReplaceUnsignedDivPowerOfTwo(GraphVisitor *v, Inst *inst, uint64_t uValue); 414 415 private: 416 SaveStateBridgesBuilder ssb_; 417 }; 418 } // namespace ark::compiler 419 420 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_LOWERING_H 421