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 LLVM_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 (auto it = MRI->use_nodbg_begin(VReg), end = MRI->use_nodbg_end(); 157 it != end; ++it) { 158 MachineInstr *User = it->getParent(); 159 if (User->isPHI()) { 160 unsigned BBOperandIdx = User->getOperandNo(&*it) + 1; 161 MachineBasicBlock *MBB = User->getOperand(BBOperandIdx).getMBB(); 162 if (MBB->empty()) { 163 const MachineBasicBlock *InstBB = MI->getParent(); 164 assert(InstBB != MBB && "Instruction found in empty MBB"); 165 if (!MDT->dominates(InstBB, MBB)) 166 return false; 167 continue; 168 } 169 User = &*MBB->rbegin(); 170 } 171 172 if (!MDT->dominates(MI, User)) 173 return false; 174 } 175 return true; 176 } 177 178 // Return true if \p MI is load/store instruction with immediate offset 179 // which can be adjusted by \p Disp 180 static bool isLoadStoreThatCanHandleDisplacement(const TargetInstrInfo *TII, 181 const MachineInstr &MI, 182 int64_t Disp) { 183 unsigned BasePos, OffPos; 184 if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffPos)) 185 return false; 186 const MachineOperand &MO = MI.getOperand(OffPos); 187 if (!MO.isImm()) 188 return false; 189 int64_t Offset = MO.getImm() + Disp; 190 return isValidLoadStoreOffset(Offset); 191 } 192 193 bool ARCOptAddrMode::noUseOfAddBeforeLoadOrStore(const MachineInstr *Add, 194 const MachineInstr *Ldst) { 195 Register R = Add->getOperand(0).getReg(); 196 return dominatesAllUsesOf(Ldst, R, MDT, MRI); 197 } 198 199 MachineInstr *ARCOptAddrMode::tryToCombine(MachineInstr &Ldst) { 200 assert(Ldst.mayLoadOrStore() && "LD/ST instruction expected"); 201 202 unsigned BasePos, OffsetPos; 203 204 LLVM_DEBUG(dbgs() << "[ABAW] tryToCombine " << Ldst); 205 if (!AII->getBaseAndOffsetPosition(Ldst, BasePos, OffsetPos)) { 206 LLVM_DEBUG(dbgs() << "[ABAW] Not a recognized load/store\n"); 207 return nullptr; 208 } 209 210 MachineOperand &Base = Ldst.getOperand(BasePos); 211 MachineOperand &Offset = Ldst.getOperand(OffsetPos); 212 213 assert(Base.isReg() && "Base operand must be register"); 214 if (!Offset.isImm()) { 215 LLVM_DEBUG(dbgs() << "[ABAW] Offset is not immediate\n"); 216 return nullptr; 217 } 218 219 Register B = Base.getReg(); 220 if (Register::isStackSlot(B) || !Register::isVirtualRegister(B)) { 221 LLVM_DEBUG(dbgs() << "[ABAW] Base is not VReg\n"); 222 return nullptr; 223 } 224 225 // TODO: try to generate address preincrement 226 if (Offset.getImm() != 0) { 227 LLVM_DEBUG(dbgs() << "[ABAW] Non-zero offset\n"); 228 return nullptr; 229 } 230 231 for (auto &Add : MRI->use_nodbg_instructions(B)) { 232 int64_t Incr; 233 if (!isAddConstantOp(Add, Incr)) 234 continue; 235 if (!isValidLoadStoreOffset(Incr)) 236 continue; 237 238 SmallVector<MachineInstr *, 8> Uses; 239 MachineInstr *MoveTo = canJoinInstructions(&Ldst, &Add, &Uses); 240 241 if (!MoveTo) 242 continue; 243 244 if (!canFixPastUses(Uses, Add.getOperand(2), B)) 245 continue; 246 247 LLVM_DEBUG(MachineInstr *First = &Ldst; MachineInstr *Last = &Add; 248 if (MDT->dominates(Last, First)) std::swap(First, Last); 249 dbgs() << "[ABAW] Instructions " << *First << " and " << *Last 250 << " combined\n"; 251 252 ); 253 254 MachineInstr *Result = Ldst.getNextNode(); 255 if (MoveTo == &Add) { 256 Ldst.removeFromParent(); 257 Add.getParent()->insertAfter(Add.getIterator(), &Ldst); 258 } 259 if (Result == &Add) 260 Result = Result->getNextNode(); 261 262 fixPastUses(Uses, B, Incr); 263 264 int NewOpcode = ARC::getPostIncOpcode(Ldst.getOpcode()); 265 assert(NewOpcode > 0 && "No postincrement form found"); 266 unsigned NewBaseReg = Add.getOperand(0).getReg(); 267 changeToAddrMode(Ldst, NewOpcode, NewBaseReg, Add.getOperand(2)); 268 Add.eraseFromParent(); 269 270 return Result; 271 } 272 return nullptr; 273 } 274 275 MachineInstr * 276 ARCOptAddrMode::canJoinInstructions(MachineInstr *Ldst, MachineInstr *Add, 277 SmallVectorImpl<MachineInstr *> *Uses) { 278 assert(Ldst && Add && "NULL instruction passed"); 279 280 MachineInstr *First = Add; 281 MachineInstr *Last = Ldst; 282 if (MDT->dominates(Ldst, Add)) 283 std::swap(First, Last); 284 else if (!MDT->dominates(Add, Ldst)) 285 return nullptr; 286 287 LLVM_DEBUG(dbgs() << "canJoinInstructions: " << *First << *Last); 288 289 unsigned BasePos, OffPos; 290 291 if (!AII->getBaseAndOffsetPosition(*Ldst, BasePos, OffPos)) { 292 LLVM_DEBUG( 293 dbgs() 294 << "[canJoinInstructions] Cannot determine base/offset position\n"); 295 return nullptr; 296 } 297 298 Register BaseReg = Ldst->getOperand(BasePos).getReg(); 299 300 // prohibit this: 301 // v1 = add v0, c 302 // st v1, [v0, 0] 303 // and this 304 // st v0, [v0, 0] 305 // v1 = add v0, c 306 if (Ldst->mayStore() && Ldst->getOperand(0).isReg()) { 307 Register StReg = Ldst->getOperand(0).getReg(); 308 if (Add->getOperand(0).getReg() == StReg || BaseReg == StReg) { 309 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Store uses result of Add\n"); 310 return nullptr; 311 } 312 } 313 314 SmallVector<MachineInstr *, 4> UsesAfterLdst; 315 SmallVector<MachineInstr *, 4> UsesAfterAdd; 316 for (MachineInstr &MI : MRI->use_nodbg_instructions(BaseReg)) { 317 if (&MI == Ldst || &MI == Add) 318 continue; 319 if (&MI != Add && MDT->dominates(Ldst, &MI)) 320 UsesAfterLdst.push_back(&MI); 321 else if (!MDT->dominates(&MI, Ldst)) 322 return nullptr; 323 if (MDT->dominates(Add, &MI)) 324 UsesAfterAdd.push_back(&MI); 325 } 326 327 MachineInstr *Result = nullptr; 328 329 if (First == Add) { 330 // n = add b, i 331 // ... 332 // x = ld [b, o] or x = ld [n, o] 333 334 if (noUseOfAddBeforeLoadOrStore(First, Last)) { 335 Result = Last; 336 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can sink Add down to Ldst\n"); 337 } else if (canHoistLoadStoreTo(Ldst, Add)) { 338 Result = First; 339 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Ldst to Add\n"); 340 } 341 } else { 342 // x = ld [b, o] 343 // ... 344 // n = add b, i 345 Result = First; 346 LLVM_DEBUG(dbgs() << "[canJoinInstructions] Can hoist Add to Ldst\n"); 347 } 348 if (Result && Uses) 349 *Uses = (Result == Ldst) ? UsesAfterLdst : UsesAfterAdd; 350 return Result; 351 } 352 353 bool ARCOptAddrMode::canFixPastUses(const ArrayRef<MachineInstr *> &Uses, 354 MachineOperand &Incr, unsigned BaseReg) { 355 356 assert(Incr.isImm() && "Expected immediate increment"); 357 int64_t NewOffset = Incr.getImm(); 358 for (MachineInstr *MI : Uses) { 359 int64_t Dummy; 360 if (isAddConstantOp(*MI, Dummy)) { 361 if (isValidIncrementOffset(Dummy + NewOffset)) 362 continue; 363 return false; 364 } 365 if (isLoadStoreThatCanHandleDisplacement(AII, *MI, -NewOffset)) 366 continue; 367 LLVM_DEBUG(dbgs() << "Instruction cannot handle displacement " << -NewOffset 368 << ": " << *MI); 369 return false; 370 } 371 return true; 372 } 373 374 void ARCOptAddrMode::fixPastUses(ArrayRef<MachineInstr *> Uses, 375 unsigned NewBase, int64_t NewOffset) { 376 377 for (MachineInstr *MI : Uses) { 378 int64_t Amount; 379 unsigned BasePos, OffPos; 380 if (isAddConstantOp(*MI, Amount)) { 381 NewOffset += Amount; 382 assert(isValidIncrementOffset(NewOffset) && 383 "New offset won't fit into ADD instr"); 384 BasePos = 1; 385 OffPos = 2; 386 } else if (AII->getBaseAndOffsetPosition(*MI, BasePos, OffPos)) { 387 MachineOperand &MO = MI->getOperand(OffPos); 388 assert(MO.isImm() && "expected immediate operand"); 389 NewOffset += MO.getImm(); 390 assert(isValidLoadStoreOffset(NewOffset) && 391 "New offset won't fit into LD/ST"); 392 } else 393 llvm_unreachable("unexpected instruction"); 394 395 MI->getOperand(BasePos).setReg(NewBase); 396 MI->getOperand(OffPos).setImm(NewOffset); 397 } 398 } 399 400 bool ARCOptAddrMode::canHoistLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { 401 if (Ldst->getParent() != To->getParent()) 402 return false; 403 MachineBasicBlock::const_iterator MI(To), ME(Ldst), 404 End(Ldst->getParent()->end()); 405 406 bool IsStore = Ldst->mayStore(); 407 for (; MI != ME && MI != End; ++MI) { 408 if (MI->isDebugValue()) 409 continue; 410 if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || 411 MI->hasUnmodeledSideEffects()) 412 return false; 413 if (IsStore && MI->mayLoad()) 414 return false; 415 } 416 417 for (auto &O : Ldst->explicit_operands()) { 418 if (!O.isReg() || !O.isUse()) 419 continue; 420 MachineInstr *OpDef = MRI->getVRegDef(O.getReg()); 421 if (!OpDef || !MDT->dominates(OpDef, To)) 422 return false; 423 } 424 return true; 425 } 426 427 // bool ARCOptAddrMode::canSinkLoadStoreTo(MachineInstr *Ldst, MachineInstr *To) { 428 // // Can only sink load/store within same BB 429 // if (Ldst->getParent() != To->getParent()) 430 // return false; 431 // MachineBasicBlock::const_iterator MI(Ldst), ME(To), 432 // End(Ldst->getParent()->end()); 433 434 // bool IsStore = Ldst->mayStore(); 435 // bool IsLoad = Ldst->mayLoad(); 436 437 // Register ValReg = IsLoad ? Ldst->getOperand(0).getReg() : Register(); 438 // for (; MI != ME && MI != End; ++MI) { 439 // if (MI->isDebugValue()) 440 // continue; 441 // if (MI->mayStore() || MI->isCall() || MI->isInlineAsm() || 442 // MI->hasUnmodeledSideEffects()) 443 // return false; 444 // if (IsStore && MI->mayLoad()) 445 // return false; 446 // if (ValReg && MI->readsVirtualRegister(ValReg)) 447 // return false; 448 // } 449 // return true; 450 // } 451 452 void ARCOptAddrMode::changeToAddrMode(MachineInstr &Ldst, unsigned NewOpcode, 453 unsigned NewBase, 454 MachineOperand &NewOffset) { 455 bool IsStore = Ldst.mayStore(); 456 unsigned BasePos, OffPos; 457 MachineOperand Src = MachineOperand::CreateImm(0xDEADBEEF); 458 AII->getBaseAndOffsetPosition(Ldst, BasePos, OffPos); 459 460 Register BaseReg = Ldst.getOperand(BasePos).getReg(); 461 462 Ldst.removeOperand(OffPos); 463 Ldst.removeOperand(BasePos); 464 465 if (IsStore) { 466 Src = Ldst.getOperand(BasePos - 1); 467 Ldst.removeOperand(BasePos - 1); 468 } 469 470 Ldst.setDesc(AST->getInstrInfo()->get(NewOpcode)); 471 Ldst.addOperand(MachineOperand::CreateReg(NewBase, true)); 472 if (IsStore) 473 Ldst.addOperand(Src); 474 Ldst.addOperand(MachineOperand::CreateReg(BaseReg, false)); 475 Ldst.addOperand(NewOffset); 476 LLVM_DEBUG(dbgs() << "[ABAW] New Ldst: " << Ldst); 477 } 478 479 bool ARCOptAddrMode::processBasicBlock(MachineBasicBlock &MBB) { 480 bool Changed = false; 481 for (auto MI = MBB.begin(), ME = MBB.end(); MI != ME; ++MI) { 482 if (MI->isDebugValue()) 483 continue; 484 if (!MI->mayLoad() && !MI->mayStore()) 485 continue; 486 if (ARC::getPostIncOpcode(MI->getOpcode()) < 0) 487 continue; 488 MachineInstr *Res = tryToCombine(*MI); 489 if (Res) { 490 Changed = true; 491 // Res points to the next instruction. Rewind to process it 492 MI = std::prev(Res->getIterator()); 493 } 494 } 495 return Changed; 496 } 497 498 bool ARCOptAddrMode::runOnMachineFunction(MachineFunction &MF) { 499 if (skipFunction(MF.getFunction()) || KILL_PASS()) 500 return false; 501 502 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 503 if (DUMP_BEFORE()) 504 MF.dump(); 505 #endif 506 if (VIEW_BEFORE()) 507 MF.viewCFG(); 508 509 AST = &MF.getSubtarget<ARCSubtarget>(); 510 AII = AST->getInstrInfo(); 511 MRI = &MF.getRegInfo(); 512 MDT = &getAnalysis<MachineDominatorTree>(); 513 514 bool Changed = false; 515 for (auto &MBB : MF) 516 Changed |= processBasicBlock(MBB); 517 518 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 519 if (DUMP_AFTER()) 520 MF.dump(); 521 #endif 522 if (VIEW_AFTER()) 523 MF.viewCFG(); 524 return Changed; 525 } 526 527 //===----------------------------------------------------------------------===// 528 // Public Constructor Functions 529 //===----------------------------------------------------------------------===// 530 531 FunctionPass *llvm::createARCOptAddrMode() { return new ARCOptAddrMode(); } 532