1 //===- ARCOptAddrMode.cpp ---------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file 10 /// This pass folds LD/ST + ADD pairs into Pre/Post-increment form of 11 /// load/store instructions. 12 //===----------------------------------------------------------------------===// 13 14 #include "ARC.h" 15 #define GET_INSTRMAP_INFO 16 #include "ARCInstrInfo.h" 17 #include "ARCTargetMachine.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/MachineDominators.h" 20 #include "llvm/CodeGen/MachineFunctionPass.h" 21 #include "llvm/CodeGen/MachineInstr.h" 22 #include "llvm/CodeGen/MachineInstrBuilder.h" 23 #include "llvm/CodeGen/TargetRegisterInfo.h" 24 #include "llvm/IR/Function.h" 25 #include "llvm/InitializePasses.h" 26 #include "llvm/Support/CommandLine.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/raw_ostream.h" 29 30 using namespace llvm; 31 32 #define OPTADDRMODE_DESC "ARC load/store address mode" 33 #define OPTADDRMODE_NAME "arc-addr-mode" 34 #define DEBUG_TYPE "arc-addr-mode" 35 36 namespace llvm { 37 38 static cl::opt<unsigned> ArcKillAddrMode("arc-kill-addr-mode", cl::init(0), 39 cl::ReallyHidden); 40 41 #define DUMP_BEFORE() ((ArcKillAddrMode & 0x0001) != 0) 42 #define DUMP_AFTER() ((ArcKillAddrMode & 0x0002) != 0) 43 #define VIEW_BEFORE() ((ArcKillAddrMode & 0x0004) != 0) 44 #define VIEW_AFTER() ((ArcKillAddrMode & 0x0008) != 0) 45 #define KILL_PASS() ((ArcKillAddrMode & 0x0010) != 0) 46 47 FunctionPass *createARCOptAddrMode(); 48 void initializeARCOptAddrModePass(PassRegistry &); 49 } // end namespace llvm 50 51 namespace { 52 class ARCOptAddrMode : public MachineFunctionPass { 53 public: 54 static char ID; 55 56 ARCOptAddrMode() : MachineFunctionPass(ID) {} 57 58 StringRef getPassName() const override { return OPTADDRMODE_DESC; } 59 60 void getAnalysisUsage(AnalysisUsage &AU) const override { 61 AU.setPreservesCFG(); 62 MachineFunctionPass::getAnalysisUsage(AU); 63 AU.addRequired<MachineDominatorTree>(); 64 AU.addPreserved<MachineDominatorTree>(); 65 } 66 67 bool runOnMachineFunction(MachineFunction &MF) override; 68 69 private: 70 const ARCSubtarget *AST = nullptr; 71 const ARCInstrInfo *AII = nullptr; 72 MachineRegisterInfo *MRI = nullptr; 73 MachineDominatorTree *MDT = nullptr; 74 75 // Tries to combine \p Ldst with increment of its base register to form 76 // single post-increment instruction. 77 MachineInstr *tryToCombine(MachineInstr &Ldst); 78 79 // Returns true if result of \p Add is not used before \p Ldst 80 bool noUseOfAddBeforeLoadOrStore(const MachineInstr *Add, 81 const MachineInstr *Ldst); 82 83 // Returns true if load/store instruction \p Ldst can be hoisted up to 84 // instruction \p To 85 bool canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To); 86 87 // // Returns true if load/store instruction \p Ldst can be sunk down 88 // // to instruction \p To 89 // bool canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To); 90 91 // Check if instructions \p Ldst and \p Add can be moved to become adjacent 92 // If they can return instruction which need not to move. 93 // If \p Uses is not null, fill it with instructions after \p Ldst which use 94 // \p Ldst's base register 95 MachineInstr *canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add, 96 SmallVectorImpl<MachineInstr *> *Uses); 97 98 // Returns true if all instruction in \p Uses array can be adjusted 99 // to accomodate increment of register \p BaseReg by \p Incr 100 bool canFixPastUses(const ArrayRef<MachineInstr *> &Uses, 101 MachineOperand &Incr, unsigned BaseReg); 102 103 // Update all instructions in \p Uses to accomodate increment 104 // of \p BaseReg by \p Offset 105 void fixPastUses(ArrayRef<MachineInstr *> Uses, unsigned BaseReg, 106 int64_t Offset); 107 108 // Change instruction \p Ldst to postincrement form. 109 // \p NewBase is register to hold update base value 110 // \p NewOffset is instruction's new offset 111 void changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode, 112 unsigned NewBase, MachineOperand &NewOffset); 113 114 bool processBasicBlock(MachineBasicBlock &MBB); 115 }; 116 117 } // end anonymous namespace 118 119 char ARCOptAddrMode::ID = 0; 120 INITIALIZE_PASS_BEGIN(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false, 121 false) 122 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 123 INITIALIZE_PASS_END(ARCOptAddrMode, OPTADDRMODE_NAME, OPTADDRMODE_DESC, false, 124 false) 125 126 // Return true if \p Off can be used as immediate offset 127 // operand of load/store instruction (S9 literal) 128 static bool isValidLoadStoreOffset(int64_t Off) { return isInt<9>(Off); } 129 130 // Return true if \p Off can be used as immediate operand of 131 // ADD/SUB instruction (U6 literal) 132 static bool isValidIncrementOffset(int64_t Off) { return isUInt<6>(Off); } 133 134 static bool isAddConstantOp(const MachineInstr &MI, int64_t &Amount) { 135 int64_t Sign = 1; 136 switch (MI.getOpcode()) { 137 case ARC::SUB_rru6: 138 Sign = -1; 139 [[fallthrough]]; 140 case ARC::ADD_rru6: 141 assert(MI.getOperand(2).isImm() && "Expected immediate operand"); 142 Amount = Sign * MI.getOperand(2).getImm(); 143 return true; 144 default: 145 return false; 146 } 147 } 148 149 // Return true if \p MI dominates of uses of virtual register \p VReg 150 static bool dominatesAllUsesOf(const MachineInstr *MI, unsigned VReg, 151 MachineDominatorTree *MDT, 152 MachineRegisterInfo *MRI) { 153 154 assert(Register::isVirtualRegister(VReg) && "Expected virtual register!"); 155 156 for (const MachineOperand &Use : MRI->use_nodbg_operands(VReg)) { 157 const MachineInstr *User = Use.getParent(); 158 if (User->isPHI()) { 159 unsigned BBOperandIdx = Use.getOperandNo() + 1; 160 MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB(); 161 if (MBB->empty()) { 162 const MachineBasicBlock *InstBB = MI->getParent(); 163 assert(InstBB != MBB && "Instruction found in empty MBB"); 164 if (!MDT->dominates(InstBB, MBB)) 165 return false; 166 continue; 167 } 168 User = &*MBB->rbegin(); 169 } 170 171 if (!MDT->dominates(MI, User)) 172 return false; 173 } 174 return true; 175 } 176 177 // Return true if \p MI is load/store instruction with immediate offset 178 // which can be adjusted by \p Disp 179 static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII, 180 const MachineInstr &MI, 181 int64_t Disp) { 182 unsigned BasePos, OffPos; 183 if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos)) 184 return false; 185 const MachineOperand &MO = MI.getOperand(OffPos); 186 if (!MO.isImm()) 187 return false; 188 int64_t Offset = MO.getImm() + Disp; 189 return isValidLoadStoreOffset(Offset); 190 } 191 192 bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add, 193 const MachineInstr *Ldst) { 194 Register R = Add->getOperand(0).getReg(); 195 return dominatesAllUsesOf(Ldst, R, MDT, MRI); 196 } 197 198 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) { 199 assert(Ldst.mayLoadOrStore() && "LD/ST instruction expected"); 200 201 unsigned BasePos, OffsetPos; 202 203 LLVM_DEBUG(dbgs() << "[ABAW] tryToCombine " << Ldst); 204 if (!AII->getBaseAndOffsetPosition(Ldst, BasePos, OffsetPos)) { 205 LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n"); 206 return nullptr; 207 } 208 209 MachineOperand &Base = Ldst.getOperand(BasePos); 210 MachineOperand &Offset = Ldst.getOperand(OffsetPos); 211 212 assert(Base.isReg() && "Base operand must be register"); 213 if (!Offset.isImm()) { 214 LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n"); 215 return nullptr; 216 } 217 218 Register B = Base.getReg(); 219 if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) { 220 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n"); 221 return nullptr; 222 } 223 224 // TODO: try to generate address preincrement 225 if (Offset.getImm() != 0) { 226 LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n"); 227 return nullptr; 228 } 229 230 for (auto &Add : MRI->use_nodbg_instructions(B)) { 231 int64_t Incr; 232 if (!isAddConstantOp(Add, Incr)) 233 continue; 234 if (!isValidLoadStoreOffset(Incr)) 235 continue; 236 237 SmallVector<MachineInstr *, 8> Uses; 238 MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses); 239 240 if (!MoveTo) 241 continue; 242 243 if (!canFixPastUses(Uses, Add.getOperand(2), B)) 244 continue; 245 246 LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add; 247 if (MDT->dominates(Last, First)) std::swap(First, Last); 248 dbgs() << "[ABAW] Instructions " << *First << " and " << *Last 249 << " combined\n"; 250 251 ); 252 253 MachineInstr *Result = Ldst.getNextNode(); 254 if (MoveTo == &Add) { 255 Ldst.removeFromParent(); 256 Add.getParent()->insertAfter(Add.getIterator(), &Ldst); 257 } 258 if (Result == &Add) 259 Result = Result->getNextNode(); 260 261 fixPastUses(Uses, B, Incr); 262 263 int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode()); 264 assert(NewOpcode > 0 && "No postincrement form found"); 265 unsigned NewBaseReg = Add.getOperand(0).getReg(); 266 changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2)); 267 Add.eraseFromParent(); 268 269 return Result; 270 } 271 return nullptr; 272 } 273 274 MachineInstr * 275 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add, 276 SmallVectorImpl<MachineInstr *> *Uses) { 277 assert(Ldst && Add && "NULL instruction passed"); 278 279 MachineInstr *First = Add; 280 MachineInstr *Last = Ldst; 281 if (MDT->dominates(Ldst, Add)) 282 std::swap(First, Last); 283 else if (!MDT->dominates(Add, Ldst)) 284 return nullptr; 285 286 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last); 287 288 unsigned BasePos, OffPos; 289 290 if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) { 291 LLVM_DEBUG( 292 dbgs() 293 << "[canJoinInstructions] Cannot determine base/offset position\n"); 294 return nullptr; 295 } 296 297 Register BaseReg = Ldst->getOperand(BasePos).getReg(); 298 299 // prohibit this: 300 // v1 = add v0, c 301 // st v1, [v0, 0] 302 // and this 303 // st v0, [v0, 0] 304 // v1 = add v0, c 305 if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) { 306 Register StReg = Ldst->getOperand(0).getReg(); 307 if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) { 308 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n"); 309 return nullptr; 310 } 311 } 312 313 SmallVector<MachineInstr *, 4> UsesAfterLdst; 314 SmallVector<MachineInstr *, 4> UsesAfterAdd; 315 for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) { 316 if (&MI == Ldst || &MI == Add) 317 continue; 318 if (&MI != Add && MDT->dominates(Ldst, &MI)) 319 UsesAfterLdst.push_back(&MI); 320 else if (!MDT->dominates(&MI, Ldst)) 321 return nullptr; 322 if (MDT->dominates(Add, &MI)) 323 UsesAfterAdd.push_back(&MI); 324 } 325 326 MachineInstr *Result = nullptr; 327 328 if (First == Add) { 329 // n = add b, i 330 // ... 331 // x = ld [b, o] or x = ld [n, o] 332 333 if (noUseOfAddBeforeLoadOrStore(First, Last)) { 334 Result = Last; 335 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n"); 336 } else if (canHoistLoadStoreTo(Ldst, Add)) { 337 Result = First; 338 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n"); 339 } 340 } else { 341 // x = ld [b, o] 342 // ... 343 // n = add b, i 344 Result = First; 345 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n"); 346 } 347 if (Result && Uses) 348 *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd; 349 return Result; 350 } 351 352 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses, 353 MachineOperand &Incr, unsigned BaseReg) { 354 355 assert(Incr.isImm() && "Expected immediate increment"); 356 int64_t NewOffset = Incr.getImm(); 357 for (MachineInstr *MI : Uses) { 358 int64_t Dummy; 359 if (isAddConstantOp(*MI, Dummy)) { 360 if (isValidIncrementOffset(Dummy + NewOffset)) 361 continue; 362 return false; 363 } 364 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset)) 365 continue; 366 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset 367 << ": " << *MI); 368 return false; 369 } 370 return true; 371 } 372 373 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses, 374 unsigned NewBase, int64_t NewOffset) { 375 376 for (MachineInstr *MI : Uses) { 377 int64_t Amount; 378 unsigned BasePos, OffPos; 379 if (isAddConstantOp(*MI, Amount)) { 380 NewOffset += Amount; 381 assert(isValidIncrementOffset(NewOffset) && 382 "New offset won't fit into ADD instr"); 383 BasePos = 1; 384 OffPos = 2; 385 } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) { 386 MachineOperand &MO = MI->getOperand(OffPos); 387 assert(MO.isImm() && "expected immediate operand"); 388 NewOffset += MO.getImm(); 389 assert(isValidLoadStoreOffset(NewOffset) && 390 "New offset won't fit into LD/ST"); 391 } else 392 llvm_unreachable("unexpected instruction"); 393 394 MI->getOperand(BasePos).setReg(NewBase); 395 MI->getOperand(OffPos).setImm(NewOffset); 396 } 397 } 398 399 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { 400 if (Ldst->getParent() != To->getParent()) 401 return false; 402 MachineBasicBlock::const_iterator MI(To), ME(Ldst), 403 End(Ldst->getParent()->end()); 404 405 bool IsStore = Ldst->mayStore(); 406 for (; MI != ME && MI != End; ++MI) { 407 if (MI->isDebugValue()) 408 continue; 409 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || 410 MI->hasUnmodeledSideEffects()) 411 return false; 412 if (IsStore && MI->mayLoad()) 413 return false; 414 } 415 416 for (auto &O : Ldst->explicit_operands()) { 417 if (!O.isReg() || !O.isUse()) 418 continue; 419 MachineInstr *OpDef = MRI->getVRegDef(O.getReg()); 420 if (!OpDef || !MDT->dominates(OpDef, To)) 421 return false; 422 } 423 return true; 424 } 425 426 // bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { 427 // // Can only sink load/store within same BB 428 // if (Ldst->getParent() != To->getParent()) 429 // return false; 430 // MachineBasicBlock::const_iterator MI(Ldst), ME(To), 431 // End(Ldst->getParent()->end()); 432 433 // bool IsStore = Ldst->mayStore(); 434 // bool IsLoad = Ldst->mayLoad(); 435 436 // Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register(); 437 // for (; MI != ME && MI != End; ++MI) { 438 // if (MI->isDebugValue()) 439 // continue; 440 // if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || 441 // MI->hasUnmodeledSideEffects()) 442 // return false; 443 // if (IsStore && MI->mayLoad()) 444 // return false; 445 // if (ValReg && MI->readsVirtualRegister(ValReg)) 446 // return false; 447 // } 448 // return true; 449 // } 450 451 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode, 452 unsigned NewBase, 453 MachineOperand &NewOffset) { 454 bool IsStore = Ldst.mayStore(); 455 unsigned BasePos, OffPos; 456 MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF); 457 AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos); 458 459 Register BaseReg = Ldst.getOperand(BasePos).getReg(); 460 461 Ldst.removeOperand(OffPos); 462 Ldst.removeOperand(BasePos); 463 464 if (IsStore) { 465 Src = Ldst.getOperand(BasePos - 1); 466 Ldst.removeOperand(BasePos - 1); 467 } 468 469 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode)); 470 Ldst.addOperand(MachineOperand::CreateReg(NewBase, true)); 471 if (IsStore) 472 Ldst.addOperand(Src); 473 Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false)); 474 Ldst.addOperand(NewOffset); 475 LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst); 476 } 477 478 bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) { 479 bool Changed = false; 480 for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) { 481 if (MI->isDebugValue()) 482 continue; 483 if (!MI->mayLoad() && !MI->mayStore()) 484 continue; 485 if (ARC::getPostIncOpcode(MI->getOpcode()) < 0) 486 continue; 487 MachineInstr *Res = tryToCombine(*MI); 488 if (Res) { 489 Changed = true; 490 // Res points to the next instruction. Rewind to process it 491 MI = std::prev(Res->getIterator()); 492 } 493 } 494 return Changed; 495 } 496 497 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) { 498 if (skipFunction(MF.getFunction()) || KILL_PASS()) 499 return false; 500 501 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 502 if (DUMP_BEFORE()) 503 MF.dump(); 504 #endif 505 if (VIEW_BEFORE()) 506 MF.viewCFG(); 507 508 AST = &MF.getSubtarget<ARCSubtarget>(); 509 AII = AST->getInstrInfo(); 510 MRI = &MF.getRegInfo(); 511 MDT = &getAnalysis<MachineDominatorTree>(); 512 513 bool Changed = false; 514 for (auto &MBB : MF) 515 Changed |= processBasicBlock(MBB); 516 517 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 518 if (DUMP_AFTER()) 519 MF.dump(); 520 #endif 521 if (VIEW_AFTER()) 522 MF.viewCFG(); 523 return Changed; 524 } 525 526 //===----------------------------------------------------------------------===// 527 // Public Constructor Functions 528 //===----------------------------------------------------------------------===// 529 530 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); } 531