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