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