1 /* 2 * Copyright (c) 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 MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_GLOBAL_H 17 #define MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_GLOBAL_H 18 19 #include "global.h" 20 #include "aarch64_operand.h" 21 22 namespace maplebe { 23 using namespace maple; 24 25 class AArch64GlobalOpt : public GlobalOpt { 26 public: AArch64GlobalOpt(CGFunc & func,LoopAnalysis & loop)27 explicit AArch64GlobalOpt(CGFunc &func, LoopAnalysis &loop) : GlobalOpt(func, loop) {} 28 ~AArch64GlobalOpt() override = default; 29 void Run() override; 30 }; 31 32 class OptimizeManager { 33 public: OptimizeManager(CGFunc & cgFunc,LoopAnalysis & loop)34 explicit OptimizeManager(CGFunc &cgFunc, LoopAnalysis &loop) : cgFunc(cgFunc), loopInfo(loop) {} 35 ~OptimizeManager() = default; 36 template <typename OptimizePattern> Optimize()37 void Optimize() 38 { 39 OptimizePattern optPattern(cgFunc, loopInfo); 40 optPattern.Run(); 41 } 42 43 private: 44 CGFunc &cgFunc; 45 LoopAnalysis &loopInfo; 46 }; 47 48 class OptimizePattern { 49 public: OptimizePattern(CGFunc & cgFunc,LoopAnalysis & loop)50 explicit OptimizePattern(CGFunc &cgFunc, LoopAnalysis &loop) : cgFunc(cgFunc), loopInfo(loop) {} 51 virtual ~OptimizePattern() = default; 52 virtual bool CheckCondition(Insn &insn) = 0; 53 virtual void Optimize(Insn &insn) = 0; 54 virtual void Run() = 0; 55 bool OpndDefByOne(Insn &insn, int32 useIdx) const; 56 bool OpndDefByZero(Insn &insn, int32 useIdx) const; 57 bool OpndDefByOneOrZero(Insn &insn, int32 useIdx) const; 58 void ReplaceAllUsedOpndWithNewOpnd(const InsnSet &useInsnSet, uint32 regNO, Operand &newOpnd, 59 bool updateInfo) const; 60 61 static bool InsnDefOne(const Insn &insn); 62 static bool InsnDefZero(const Insn &insn); 63 static bool InsnDefOneOrZero(const Insn &insn); 64 PhaseName()65 std::string PhaseName() const 66 { 67 return "globalopt"; 68 } 69 70 protected: 71 virtual void Init() = 0; 72 CGFunc &cgFunc; 73 LoopAnalysis &loopInfo; 74 }; 75 76 /* 77 * Do Forward prop when insn is mov 78 * mov xx, x1 79 * ... // BBs and x1 is live 80 * mOp yy, xx 81 * 82 * => 83 * mov x1, x1 84 * ... // BBs and x1 is live 85 * mOp yy, x1 86 */ 87 class ForwardPropPattern : public OptimizePattern { 88 public: ForwardPropPattern(CGFunc & cgFunc,LoopAnalysis & loop)89 explicit ForwardPropPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} 90 ~ForwardPropPattern() override = default; 91 bool CheckCondition(Insn &insn) final; 92 void Optimize(Insn &insn) final; 93 void Run() final; 94 95 protected: 96 void Init() final; 97 98 private: 99 InsnSet firstRegUseInsnSet; 100 void RemoveMopUxtwToMov(Insn &insn); 101 std::set<BB *, BBIdCmp> modifiedBB; 102 }; 103 104 /* 105 * Do back propagate of vreg/preg when encount following insn: 106 * 107 * mov vreg/preg1, vreg2 108 * 109 * back propagate reg1 to all vreg2's use points and def points, when all of them is in same bb 110 */ 111 class BackPropPattern : public OptimizePattern { 112 public: BackPropPattern(CGFunc & cgFunc,LoopAnalysis & loop)113 explicit BackPropPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~BackPropPattern()114 ~BackPropPattern() override 115 { 116 firstRegOpnd = nullptr; 117 secondRegOpnd = nullptr; 118 defInsnForSecondOpnd = nullptr; 119 } 120 bool CheckCondition(Insn &insn) final; 121 void Optimize(Insn &insn) final; 122 void Run() final; 123 124 protected: 125 void Init() final; 126 127 private: 128 bool CheckAndGetOpnd(const Insn &insn); 129 bool DestOpndHasUseInsns(Insn &insn); 130 bool CheckSrcOpndDefAndUseInsns(Insn &insn); 131 bool CheckSrcOpndDefAndUseInsnsGlobal(Insn &insn); 132 bool CheckPredefineInsn(Insn &insn); 133 bool CheckRedefineInsn(Insn &insn); 134 bool CheckReplacedUseInsn(Insn &insn); 135 RegOperand *firstRegOpnd = nullptr; 136 RegOperand *secondRegOpnd = nullptr; 137 uint32 firstRegNO = 0; 138 uint32 secondRegNO = 0; 139 InsnSet srcOpndUseInsnSet; 140 Insn *defInsnForSecondOpnd = nullptr; 141 bool globalProp = false; 142 }; 143 144 /* 145 * when w0 has only one valid bit, these tranformation will be done 146 * cmp w0, #0 147 * cset w1, NE --> mov w1, w0 148 * 149 * cmp w0, #0 150 * cset w1, EQ --> eor w1, w0, 1 151 * 152 * cmp w0, #1 153 * cset w1, NE --> eor w1, w0, 1 154 * 155 * cmp w0, #1 156 * cset w1, EQ --> mov w1, w0 157 * 158 * cmp w0, #0 159 * cset w0, NE -->null 160 * 161 * cmp w0, #1 162 * cset w0, EQ -->null 163 * 164 * condition: 165 * 1. the first operand of cmp instruction must has only one valid bit 166 * 2. the second operand of cmp instruction must be 0 or 1 167 * 3. flag register of cmp isntruction must not be used later 168 */ 169 class CmpCsetPattern : public OptimizePattern { 170 public: CmpCsetPattern(CGFunc & cgFunc,LoopAnalysis & loop)171 explicit CmpCsetPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~CmpCsetPattern()172 ~CmpCsetPattern() override 173 { 174 nextInsn = nullptr; 175 cmpFirstOpnd = nullptr; 176 cmpSecondOpnd = nullptr; 177 csetFirstOpnd = nullptr; 178 } 179 bool CheckCondition(Insn &insn) final; 180 void Optimize(Insn &insn) final; 181 void Run() final; 182 183 protected: 184 void Init() final; 185 186 private: 187 Insn *nextInsn = nullptr; 188 int64 cmpConstVal = 0; 189 Operand *cmpFirstOpnd = nullptr; 190 Operand *cmpSecondOpnd = nullptr; 191 Operand *csetFirstOpnd = nullptr; 192 }; 193 194 /* 195 * mov w5, #1 196 * ... --> cset w5, NE 197 * mov w0, #0 198 * csel w5, w5, w0, NE 199 * 200 * mov w5, #0 201 * ... --> cset w5,EQ 202 * mov w0, #1 203 * csel w5, w5, w0, NE 204 * 205 * condition: 206 * 1.all define points of w5 are defined by: mov w5, #1(#0) 207 * 2.all define points of w0 are defined by: mov w0, #0(#1) 208 * 3.w0 will not be used after: csel w5, w5, w0, NE(EQ) 209 */ 210 class CselPattern : public OptimizePattern { 211 public: CselPattern(CGFunc & cgFunc,LoopAnalysis & loop)212 explicit CselPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} 213 ~CselPattern() override = default; 214 bool CheckCondition(Insn &insn) final; 215 void Optimize(Insn &insn) final; 216 void Run() final; 217 218 protected: Init()219 void Init() final {} 220 }; 221 222 /* 223 * uxtb w0, w0 --> null 224 * uxth w0, w0 --> null 225 * 226 * condition: 227 * 1. validbits(w0)<=8,16,32 228 * 2. the first operand is same as the second operand 229 * 230 * uxtb w0, w1 --> null 231 * uxth w0, w1 --> null 232 * 233 * condition: 234 * 1. validbits(w1)<=8,16,32 235 * 2. the use points of w0 has only one define point, that is uxt w0, w1 236 */ 237 class RedundantUxtPattern : public OptimizePattern { 238 public: RedundantUxtPattern(CGFunc & cgFunc,LoopAnalysis & loop)239 explicit RedundantUxtPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~RedundantUxtPattern()240 ~RedundantUxtPattern() override 241 { 242 secondOpnd = nullptr; 243 } 244 bool CheckCondition(Insn &insn) final; 245 void Optimize(Insn &insn) final; 246 void Run() final; 247 248 protected: 249 void Init() final; 250 251 private: 252 uint32 GetMaximumValidBit(Insn &insn, uint8 udIdx, InsnSet &insnChecked) const; 253 static uint32 GetInsnValidBit(const Insn &insn); 254 InsnSet useInsnSet; 255 uint32 firstRegNO = 0; 256 Operand *secondOpnd = nullptr; 257 }; 258 259 /* 260 * bl MCC_NewObj_flexible_cname bl MCC_NewObj_flexible_cname 261 * mov x21, x0 // [R203] 262 * str x0, [x29,#16] // local var: Reg0_R6340 [R203] --> str x0, [x29,#16] // local var: Reg0_R6340 [R203] 263 * ... (has call) ... (has call) 264 * mov x2, x21 // use of x21 ldr x2, [x29, #16] 265 * bl *** bl *** 266 */ 267 class LocalVarSaveInsnPattern : public OptimizePattern { 268 public: LocalVarSaveInsnPattern(CGFunc & cgFunc,LoopAnalysis & loop)269 explicit LocalVarSaveInsnPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~LocalVarSaveInsnPattern()270 ~LocalVarSaveInsnPattern() override 271 { 272 firstInsnSrcOpnd = nullptr; 273 firstInsnDestOpnd = nullptr; 274 secondInsnSrcOpnd = nullptr; 275 secondInsnDestOpnd = nullptr; 276 useInsn = nullptr; 277 secondInsn = nullptr; 278 } 279 bool CheckCondition(Insn &insn) final; 280 void Optimize(Insn &insn) final; 281 void Run() final; 282 283 protected: 284 void Init() final; 285 286 private: 287 bool CheckFirstInsn(const Insn &firstInsn); 288 bool CheckSecondInsn(); 289 bool CheckAndGetUseInsn(Insn &firstInsn); 290 bool CheckLiveRange(const Insn &firstInsn); 291 Operand *firstInsnSrcOpnd = nullptr; 292 Operand *firstInsnDestOpnd = nullptr; 293 Operand *secondInsnSrcOpnd = nullptr; 294 Operand *secondInsnDestOpnd = nullptr; 295 Insn *useInsn = nullptr; 296 Insn *secondInsn = nullptr; 297 }; 298 299 class ExtendShiftOptPattern : public OptimizePattern { 300 public: ExtendShiftOptPattern(CGFunc & cgFunc,LoopAnalysis & loop)301 explicit ExtendShiftOptPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~ExtendShiftOptPattern()302 ~ExtendShiftOptPattern() override 303 { 304 defInsn = nullptr; 305 newInsn = nullptr; 306 } 307 bool CheckCondition(Insn &insn) final; 308 void Optimize(Insn &insn) final; 309 void Run() final; 310 void DoExtendShiftOpt(Insn &insn); 311 312 enum ExMOpType : uint8 { 313 kExUndef, 314 kExAdd, /* MOP_xaddrrr | MOP_xxwaddrrre | MOP_xaddrrrs */ 315 kEwAdd, /* MOP_waddrrr | MOP_wwwaddrrre | MOP_waddrrrs */ 316 kExSub, /* MOP_xsubrrr | MOP_xxwsubrrre | MOP_xsubrrrs */ 317 kEwSub, /* MOP_wsubrrr | MOP_wwwsubrrre | MOP_wsubrrrs */ 318 kExCmn, /* MOP_xcmnrr | MOP_xwcmnrre | MOP_xcmnrrs */ 319 kEwCmn, /* MOP_wcmnrr | MOP_wwcmnrre | MOP_wcmnrrs */ 320 kExCmp, /* MOP_xcmprr | MOP_xwcmprre | MOP_xcmprrs */ 321 kEwCmp, /* MOP_wcmprr | MOP_wwcmprre | MOP_wcmprrs */ 322 }; 323 324 enum LsMOpType : uint8 { 325 kLsUndef, 326 kLxAdd, /* MOP_xaddrrr | MOP_xaddrrrs */ 327 kLwAdd, /* MOP_waddrrr | MOP_waddrrrs */ 328 kLxSub, /* MOP_xsubrrr | MOP_xsubrrrs */ 329 kLwSub, /* MOP_wsubrrr | MOP_wsubrrrs */ 330 kLxCmn, /* MOP_xcmnrr | MOP_xcmnrrs */ 331 kLwCmn, /* MOP_wcmnrr | MOP_wcmnrrs */ 332 kLxCmp, /* MOP_xcmprr | MOP_xcmprrs */ 333 kLwCmp, /* MOP_wcmprr | MOP_wcmprrs */ 334 kLxEor, /* MOP_xeorrrr | MOP_xeorrrrs */ 335 kLwEor, /* MOP_weorrrr | MOP_weorrrrs */ 336 kLxNeg, /* MOP_xinegrr | MOP_xinegrrs */ 337 kLwNeg, /* MOP_winegrr | MOP_winegrrs */ 338 kLxIor, /* MOP_xiorrrr | MOP_xiorrrrs */ 339 kLwIor, /* MOP_wiorrrr | MOP_wiorrrrs */ 340 }; 341 342 enum SuffixType : uint8 { 343 kNoSuffix, /* no suffix or do not perform the optimization. */ 344 kLSL, /* logical shift left */ 345 kLSR, /* logical shift right */ 346 kASR, /* arithmetic shift right */ 347 kExten /* ExtendOp */ 348 }; 349 350 protected: 351 void Init() final; 352 353 private: 354 void SelectExtendOrShift(const Insn &def); 355 bool CheckDefUseInfo(Insn &use, uint32 size); 356 SuffixType CheckOpType(const Operand &lastOpnd) const; 357 void ReplaceUseInsn(Insn &use, const Insn &def, uint32 amount); 358 void SetExMOpType(const Insn &use); 359 void SetLsMOpType(const Insn &use); 360 361 MOperator replaceOp; 362 uint32 replaceIdx; 363 ExtendShiftOperand::ExtendOp extendOp; 364 BitShiftOperand::ShiftOp shiftOp; 365 Insn *defInsn = nullptr; 366 Insn *newInsn = nullptr; 367 bool optSuccess; 368 bool removeDefInsn; 369 ExMOpType exMOpType; 370 LsMOpType lsMOpType; 371 }; 372 373 /* 374 * This pattern do: 375 * 1) 376 * uxtw vreg:Rm validBitNum:[64], vreg:Rn validBitNum:[32] 377 * ------> 378 * mov vreg:Rm validBitNum:[64], vreg:Rn validBitNum:[32] 379 * 2) 380 * ldrh R201, [...] 381 * and R202, R201, #65520 382 * uxth R203, R202 383 * -------> 384 * ldrh R201, [...] 385 * and R202, R201, #65520 386 * mov R203, R202 387 */ 388 class ExtenToMovPattern : public OptimizePattern { 389 public: ExtenToMovPattern(CGFunc & cgFunc,LoopAnalysis & loop)390 explicit ExtenToMovPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} 391 ~ExtenToMovPattern() override = default; 392 bool CheckCondition(Insn &insn) final; 393 void Optimize(Insn &insn) final; 394 void Run() final; 395 396 protected: 397 void Init() final; 398 399 private: 400 bool CheckHideUxtw(const Insn &insn, regno_t regno) const; 401 bool CheckUxtw(Insn &insn); 402 bool BitNotAffected(Insn &insn, uint32 validNum); /* check whether significant bits are affected */ 403 bool CheckSrcReg(Insn &insn, regno_t srcRegNo, uint32 validNum); 404 405 MOperator replaceMop = MOP_undef; 406 }; 407 408 class SameDefPattern : public OptimizePattern { 409 public: SameDefPattern(CGFunc & cgFunc,LoopAnalysis & loop)410 explicit SameDefPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~SameDefPattern()411 ~SameDefPattern() override 412 { 413 currInsn = nullptr; 414 sameInsn = nullptr; 415 } 416 bool CheckCondition(Insn &insn) final; 417 void Optimize(Insn &insn) final; 418 void Run() final; 419 420 protected: 421 void Init() final; 422 423 private: 424 bool IsSameDef(); 425 bool SrcRegIsRedefined(regno_t regNo); 426 bool IsSameOperand(Operand &opnd0, Operand &opnd1); 427 428 Insn *currInsn = nullptr; 429 Insn *sameInsn = nullptr; 430 }; 431 432 /* 433 * and r0, r0, #4 (the imm is n power of 2) 434 * ... (r0 is not used) 435 * cbz r0, .Label 436 * ===> tbz r0, #2, .Label 437 * 438 * and r0, r0, #4 (the imm is n power of 2) 439 * ... (r0 is not used) 440 * cbnz r0, .Label 441 * ===> tbnz r0, #2, .Label 442 */ 443 class AndCbzPattern : public OptimizePattern { 444 public: AndCbzPattern(CGFunc & cgFunc,LoopAnalysis & loop)445 explicit AndCbzPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~AndCbzPattern()446 ~AndCbzPattern() override 447 { 448 prevInsn = nullptr; 449 } 450 bool CheckCondition(Insn &insn) final; 451 void Optimize(Insn &insn) final; 452 void Run() final; 453 454 protected: 455 void Init() final; 456 457 private: 458 int64 CalculateLogValue(int64 val) const; 459 bool IsAdjacentArea(Insn &prev, Insn &curr) const; 460 Insn *prevInsn = nullptr; 461 }; 462 463 /* 464 * [arithmetic operation] 465 * add/sub/ R202, R201, #1 add/sub/ R202, R201, #1 466 * ... ... 467 * add/sub/ R203, R201, #1 ---> mov R203, R202 468 * 469 * [copy operation] 470 * mov R201, #1 mov R201, #1 471 * ... ... 472 * mov R202, #1 ---> mov R202, R201 473 * 474 * The pattern finds the insn with the same rvalue as the current insn, 475 * then prop its lvalue, and replaces the current insn with movrr insn. 476 * The mov can be prop in forwardprop or backprop. 477 * 478 * conditions: 479 * 1. in same BB 480 * 2. rvalue is not defined between two insns 481 * 3. lvalue is not defined between two insns 482 */ 483 class SameRHSPropPattern : public OptimizePattern { 484 public: SameRHSPropPattern(CGFunc & cgFunc,LoopAnalysis & loop)485 explicit SameRHSPropPattern(CGFunc &cgFunc, LoopAnalysis &loop) : OptimizePattern(cgFunc, loop) {} ~SameRHSPropPattern()486 ~SameRHSPropPattern() override 487 { 488 prevInsn = nullptr; 489 } 490 bool CheckCondition(Insn &insn) final; 491 void Optimize(Insn &insn) final; 492 void Run() final; 493 494 protected: 495 void Init() final; 496 497 private: 498 bool IsSameOperand(Operand *opnd1, Operand *opnd2) const; 499 bool FindSameRHSInsnInBB(Insn &insn); 500 Insn *prevInsn = nullptr; 501 std::vector<MOperator> candidates; 502 }; 503 } /* namespace maplebe */ 504 505 #endif /* MAPLEBE_INCLUDE_CG_AARCH64_AARCH64_GLOBAL_H */ 506