1 //===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains a pass that performs load / store related peephole 11 // optimizations. This pass should be run after register allocation. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "arm-ldst-opt" 16 #include "ARM.h" 17 #include "ARMAddressingModes.h" 18 #include "ARMBaseInstrInfo.h" 19 #include "ARMMachineFunctionInfo.h" 20 #include "ARMRegisterInfo.h" 21 #include "llvm/DerivedTypes.h" 22 #include "llvm/Function.h" 23 #include "llvm/CodeGen/MachineBasicBlock.h" 24 #include "llvm/CodeGen/MachineFunctionPass.h" 25 #include "llvm/CodeGen/MachineInstr.h" 26 #include "llvm/CodeGen/MachineInstrBuilder.h" 27 #include "llvm/CodeGen/MachineRegisterInfo.h" 28 #include "llvm/CodeGen/RegisterScavenging.h" 29 #include "llvm/Target/TargetData.h" 30 #include "llvm/Target/TargetInstrInfo.h" 31 #include "llvm/Target/TargetMachine.h" 32 #include "llvm/Target/TargetRegisterInfo.h" 33 #include "llvm/Support/ErrorHandling.h" 34 #include "llvm/ADT/DenseMap.h" 35 #include "llvm/ADT/STLExtras.h" 36 #include "llvm/ADT/SmallPtrSet.h" 37 #include "llvm/ADT/SmallSet.h" 38 #include "llvm/ADT/SmallVector.h" 39 #include "llvm/ADT/Statistic.h" 40 using namespace llvm; 41 42 STATISTIC(NumLDMGened , "Number of ldm instructions generated"); 43 STATISTIC(NumSTMGened , "Number of stm instructions generated"); 44 STATISTIC(NumVLDMGened, "Number of vldm instructions generated"); 45 STATISTIC(NumVSTMGened, "Number of vstm instructions generated"); 46 STATISTIC(NumLdStMoved, "Number of load / store instructions moved"); 47 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation"); 48 STATISTIC(NumSTRDFormed,"Number of strd created before allocation"); 49 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm"); 50 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm"); 51 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's"); 52 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's"); 53 54 /// ARMAllocLoadStoreOpt - Post- register allocation pass the combine 55 /// load / store instructions to form ldm / stm instructions. 56 57 namespace { 58 struct ARMLoadStoreOpt : public MachineFunctionPass { 59 static char ID; 60 ARMLoadStoreOpt() : MachineFunctionPass(ID) {} 61 62 const TargetInstrInfo *TII; 63 const TargetRegisterInfo *TRI; 64 ARMFunctionInfo *AFI; 65 RegScavenger *RS; 66 bool isThumb2; 67 68 virtual bool runOnMachineFunction(MachineFunction &Fn); 69 70 virtual const char *getPassName() const { 71 return "ARM load / store optimization pass"; 72 } 73 74 private: 75 struct MemOpQueueEntry { 76 int Offset; 77 unsigned Reg; 78 bool isKill; 79 unsigned Position; 80 MachineBasicBlock::iterator MBBI; 81 bool Merged; 82 MemOpQueueEntry(int o, unsigned r, bool k, unsigned p, 83 MachineBasicBlock::iterator i) 84 : Offset(o), Reg(r), isKill(k), Position(p), MBBI(i), Merged(false) {} 85 }; 86 typedef SmallVector<MemOpQueueEntry,8> MemOpQueue; 87 typedef MemOpQueue::iterator MemOpQueueIter; 88 89 bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, 90 int Offset, unsigned Base, bool BaseKill, int Opcode, 91 ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch, 92 DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs); 93 void MergeOpsUpdate(MachineBasicBlock &MBB, 94 MemOpQueue &MemOps, 95 unsigned memOpsBegin, 96 unsigned memOpsEnd, 97 unsigned insertAfter, 98 int Offset, 99 unsigned Base, 100 bool BaseKill, 101 int Opcode, 102 ARMCC::CondCodes Pred, 103 unsigned PredReg, 104 unsigned Scratch, 105 DebugLoc dl, 106 SmallVector<MachineBasicBlock::iterator, 4> &Merges); 107 void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base, 108 int Opcode, unsigned Size, 109 ARMCC::CondCodes Pred, unsigned PredReg, 110 unsigned Scratch, MemOpQueue &MemOps, 111 SmallVector<MachineBasicBlock::iterator, 4> &Merges); 112 113 void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps); 114 bool FixInvalidRegPairOp(MachineBasicBlock &MBB, 115 MachineBasicBlock::iterator &MBBI); 116 bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB, 117 MachineBasicBlock::iterator MBBI, 118 const TargetInstrInfo *TII, 119 bool &Advance, 120 MachineBasicBlock::iterator &I); 121 bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB, 122 MachineBasicBlock::iterator MBBI, 123 bool &Advance, 124 MachineBasicBlock::iterator &I); 125 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB); 126 bool MergeReturnIntoLDM(MachineBasicBlock &MBB); 127 }; 128 char ARMLoadStoreOpt::ID = 0; 129 } 130 131 static int getLoadStoreMultipleOpcode(int Opcode, ARM_AM::AMSubMode Mode) { 132 switch (Opcode) { 133 default: llvm_unreachable("Unhandled opcode!"); 134 case ARM::LDRi12: 135 ++NumLDMGened; 136 switch (Mode) { 137 default: llvm_unreachable("Unhandled submode!"); 138 case ARM_AM::ia: return ARM::LDMIA; 139 case ARM_AM::da: return ARM::LDMDA; 140 case ARM_AM::db: return ARM::LDMDB; 141 case ARM_AM::ib: return ARM::LDMIB; 142 } 143 break; 144 case ARM::STRi12: 145 ++NumSTMGened; 146 switch (Mode) { 147 default: llvm_unreachable("Unhandled submode!"); 148 case ARM_AM::ia: return ARM::STMIA; 149 case ARM_AM::da: return ARM::STMDA; 150 case ARM_AM::db: return ARM::STMDB; 151 case ARM_AM::ib: return ARM::STMIB; 152 } 153 break; 154 case ARM::t2LDRi8: 155 case ARM::t2LDRi12: 156 ++NumLDMGened; 157 switch (Mode) { 158 default: llvm_unreachable("Unhandled submode!"); 159 case ARM_AM::ia: return ARM::t2LDMIA; 160 case ARM_AM::db: return ARM::t2LDMDB; 161 } 162 break; 163 case ARM::t2STRi8: 164 case ARM::t2STRi12: 165 ++NumSTMGened; 166 switch (Mode) { 167 default: llvm_unreachable("Unhandled submode!"); 168 case ARM_AM::ia: return ARM::t2STMIA; 169 case ARM_AM::db: return ARM::t2STMDB; 170 } 171 break; 172 case ARM::VLDRS: 173 ++NumVLDMGened; 174 switch (Mode) { 175 default: llvm_unreachable("Unhandled submode!"); 176 case ARM_AM::ia: return ARM::VLDMSIA; 177 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists. 178 } 179 break; 180 case ARM::VSTRS: 181 ++NumVSTMGened; 182 switch (Mode) { 183 default: llvm_unreachable("Unhandled submode!"); 184 case ARM_AM::ia: return ARM::VSTMSIA; 185 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists. 186 } 187 break; 188 case ARM::VLDRD: 189 ++NumVLDMGened; 190 switch (Mode) { 191 default: llvm_unreachable("Unhandled submode!"); 192 case ARM_AM::ia: return ARM::VLDMDIA; 193 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists. 194 } 195 break; 196 case ARM::VSTRD: 197 ++NumVSTMGened; 198 switch (Mode) { 199 default: llvm_unreachable("Unhandled submode!"); 200 case ARM_AM::ia: return ARM::VSTMDIA; 201 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists. 202 } 203 break; 204 } 205 206 return 0; 207 } 208 209 namespace llvm { 210 namespace ARM_AM { 211 212 AMSubMode getLoadStoreMultipleSubMode(int Opcode) { 213 switch (Opcode) { 214 default: llvm_unreachable("Unhandled opcode!"); 215 case ARM::LDMIA_RET: 216 case ARM::LDMIA: 217 case ARM::LDMIA_UPD: 218 case ARM::STMIA: 219 case ARM::STMIA_UPD: 220 case ARM::t2LDMIA_RET: 221 case ARM::t2LDMIA: 222 case ARM::t2LDMIA_UPD: 223 case ARM::t2STMIA: 224 case ARM::t2STMIA_UPD: 225 case ARM::VLDMSIA: 226 case ARM::VLDMSIA_UPD: 227 case ARM::VSTMSIA: 228 case ARM::VSTMSIA_UPD: 229 case ARM::VLDMDIA: 230 case ARM::VLDMDIA_UPD: 231 case ARM::VSTMDIA: 232 case ARM::VSTMDIA_UPD: 233 return ARM_AM::ia; 234 235 case ARM::LDMDA: 236 case ARM::LDMDA_UPD: 237 case ARM::STMDA: 238 case ARM::STMDA_UPD: 239 return ARM_AM::da; 240 241 case ARM::LDMDB: 242 case ARM::LDMDB_UPD: 243 case ARM::STMDB: 244 case ARM::STMDB_UPD: 245 case ARM::t2LDMDB: 246 case ARM::t2LDMDB_UPD: 247 case ARM::t2STMDB: 248 case ARM::t2STMDB_UPD: 249 case ARM::VLDMSDB_UPD: 250 case ARM::VSTMSDB_UPD: 251 case ARM::VLDMDDB_UPD: 252 case ARM::VSTMDDB_UPD: 253 return ARM_AM::db; 254 255 case ARM::LDMIB: 256 case ARM::LDMIB_UPD: 257 case ARM::STMIB: 258 case ARM::STMIB_UPD: 259 return ARM_AM::ib; 260 } 261 262 return ARM_AM::bad_am_submode; 263 } 264 265 } // end namespace ARM_AM 266 } // end namespace llvm 267 268 static bool isT2i32Load(unsigned Opc) { 269 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8; 270 } 271 272 static bool isi32Load(unsigned Opc) { 273 return Opc == ARM::LDRi12 || isT2i32Load(Opc); 274 } 275 276 static bool isT2i32Store(unsigned Opc) { 277 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8; 278 } 279 280 static bool isi32Store(unsigned Opc) { 281 return Opc == ARM::STRi12 || isT2i32Store(Opc); 282 } 283 284 /// MergeOps - Create and insert a LDM or STM with Base as base register and 285 /// registers in Regs as the register operands that would be loaded / stored. 286 /// It returns true if the transformation is done. 287 bool 288 ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB, 289 MachineBasicBlock::iterator MBBI, 290 int Offset, unsigned Base, bool BaseKill, 291 int Opcode, ARMCC::CondCodes Pred, 292 unsigned PredReg, unsigned Scratch, DebugLoc dl, 293 SmallVector<std::pair<unsigned, bool>, 8> &Regs) { 294 // Only a single register to load / store. Don't bother. 295 unsigned NumRegs = Regs.size(); 296 if (NumRegs <= 1) 297 return false; 298 299 ARM_AM::AMSubMode Mode = ARM_AM::ia; 300 // VFP and Thumb2 do not support IB or DA modes. 301 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode); 302 bool haveIBAndDA = isNotVFP && !isThumb2; 303 if (Offset == 4 && haveIBAndDA) 304 Mode = ARM_AM::ib; 305 else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) 306 Mode = ARM_AM::da; 307 else if (Offset == -4 * (int)NumRegs && isNotVFP) 308 // VLDM/VSTM do not support DB mode without also updating the base reg. 309 Mode = ARM_AM::db; 310 else if (Offset != 0) { 311 // Check if this is a supported opcode before we insert instructions to 312 // calculate a new base register. 313 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return false; 314 315 // If starting offset isn't zero, insert a MI to materialize a new base. 316 // But only do so if it is cost effective, i.e. merging more than two 317 // loads / stores. 318 if (NumRegs <= 2) 319 return false; 320 321 unsigned NewBase; 322 if (isi32Load(Opcode)) 323 // If it is a load, then just use one of the destination register to 324 // use as the new base. 325 NewBase = Regs[NumRegs-1].first; 326 else { 327 // Use the scratch register to use as a new base. 328 NewBase = Scratch; 329 if (NewBase == 0) 330 return false; 331 } 332 int BaseOpc = !isThumb2 ? ARM::ADDri : ARM::t2ADDri; 333 if (Offset < 0) { 334 BaseOpc = !isThumb2 ? ARM::SUBri : ARM::t2SUBri; 335 Offset = - Offset; 336 } 337 int ImmedOffset = isThumb2 338 ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset); 339 if (ImmedOffset == -1) 340 // FIXME: Try t2ADDri12 or t2SUBri12? 341 return false; // Probably not worth it then. 342 343 BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase) 344 .addReg(Base, getKillRegState(BaseKill)).addImm(Offset) 345 .addImm(Pred).addReg(PredReg).addReg(0); 346 Base = NewBase; 347 BaseKill = true; // New base is always killed right its use. 348 } 349 350 bool isDef = (isi32Load(Opcode) || Opcode == ARM::VLDRS || 351 Opcode == ARM::VLDRD); 352 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode); 353 if (!Opcode) return false; 354 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(Opcode)) 355 .addReg(Base, getKillRegState(BaseKill)) 356 .addImm(Pred).addReg(PredReg); 357 for (unsigned i = 0; i != NumRegs; ++i) 358 MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef) 359 | getKillRegState(Regs[i].second)); 360 361 return true; 362 } 363 364 // MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on 365 // success. 366 void ARMLoadStoreOpt::MergeOpsUpdate(MachineBasicBlock &MBB, 367 MemOpQueue &memOps, 368 unsigned memOpsBegin, unsigned memOpsEnd, 369 unsigned insertAfter, int Offset, 370 unsigned Base, bool BaseKill, 371 int Opcode, 372 ARMCC::CondCodes Pred, unsigned PredReg, 373 unsigned Scratch, 374 DebugLoc dl, 375 SmallVector<MachineBasicBlock::iterator, 4> &Merges) { 376 // First calculate which of the registers should be killed by the merged 377 // instruction. 378 const unsigned insertPos = memOps[insertAfter].Position; 379 SmallSet<unsigned, 4> KilledRegs; 380 DenseMap<unsigned, unsigned> Killer; 381 for (unsigned i = 0, e = memOps.size(); i != e; ++i) { 382 if (i == memOpsBegin) { 383 i = memOpsEnd; 384 if (i == e) 385 break; 386 } 387 if (memOps[i].Position < insertPos && memOps[i].isKill) { 388 unsigned Reg = memOps[i].Reg; 389 KilledRegs.insert(Reg); 390 Killer[Reg] = i; 391 } 392 } 393 394 SmallVector<std::pair<unsigned, bool>, 8> Regs; 395 for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) { 396 unsigned Reg = memOps[i].Reg; 397 // If we are inserting the merged operation after an operation that 398 // uses the same register, make sure to transfer any kill flag. 399 bool isKill = memOps[i].isKill || KilledRegs.count(Reg); 400 Regs.push_back(std::make_pair(Reg, isKill)); 401 } 402 403 // Try to do the merge. 404 MachineBasicBlock::iterator Loc = memOps[insertAfter].MBBI; 405 ++Loc; 406 if (!MergeOps(MBB, Loc, Offset, Base, BaseKill, Opcode, 407 Pred, PredReg, Scratch, dl, Regs)) 408 return; 409 410 // Merge succeeded, update records. 411 Merges.push_back(prior(Loc)); 412 for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) { 413 // Remove kill flags from any memops that come before insertPos. 414 if (Regs[i-memOpsBegin].second) { 415 unsigned Reg = Regs[i-memOpsBegin].first; 416 if (KilledRegs.count(Reg)) { 417 unsigned j = Killer[Reg]; 418 int Idx = memOps[j].MBBI->findRegisterUseOperandIdx(Reg, true); 419 assert(Idx >= 0 && "Cannot find killing operand"); 420 memOps[j].MBBI->getOperand(Idx).setIsKill(false); 421 memOps[j].isKill = false; 422 } 423 memOps[i].isKill = true; 424 } 425 MBB.erase(memOps[i].MBBI); 426 // Update this memop to refer to the merged instruction. 427 // We may need to move kill flags again. 428 memOps[i].Merged = true; 429 memOps[i].MBBI = Merges.back(); 430 memOps[i].Position = insertPos; 431 } 432 } 433 434 /// MergeLDR_STR - Merge a number of load / store instructions into one or more 435 /// load / store multiple instructions. 436 void 437 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, 438 unsigned Base, int Opcode, unsigned Size, 439 ARMCC::CondCodes Pred, unsigned PredReg, 440 unsigned Scratch, MemOpQueue &MemOps, 441 SmallVector<MachineBasicBlock::iterator, 4> &Merges) { 442 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode); 443 int Offset = MemOps[SIndex].Offset; 444 int SOffset = Offset; 445 unsigned insertAfter = SIndex; 446 MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI; 447 DebugLoc dl = Loc->getDebugLoc(); 448 const MachineOperand &PMO = Loc->getOperand(0); 449 unsigned PReg = PMO.getReg(); 450 unsigned PRegNum = PMO.isUndef() ? UINT_MAX 451 : getARMRegisterNumbering(PReg); 452 unsigned Count = 1; 453 unsigned Limit = ~0U; 454 455 // vldm / vstm limit are 32 for S variants, 16 for D variants. 456 457 switch (Opcode) { 458 default: break; 459 case ARM::VSTRS: 460 Limit = 32; 461 break; 462 case ARM::VSTRD: 463 Limit = 16; 464 break; 465 case ARM::VLDRD: 466 Limit = 16; 467 break; 468 case ARM::VLDRS: 469 Limit = 32; 470 break; 471 } 472 473 for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) { 474 int NewOffset = MemOps[i].Offset; 475 const MachineOperand &MO = MemOps[i].MBBI->getOperand(0); 476 unsigned Reg = MO.getReg(); 477 unsigned RegNum = MO.isUndef() ? UINT_MAX 478 : getARMRegisterNumbering(Reg); 479 // Register numbers must be in ascending order. For VFP / NEON load and 480 // store multiples, the registers must also be consecutive and within the 481 // limit on the number of registers per instruction. 482 if (Reg != ARM::SP && 483 NewOffset == Offset + (int)Size && 484 ((isNotVFP && RegNum > PRegNum) || 485 ((Count < Limit) && RegNum == PRegNum+1))) { 486 Offset += Size; 487 PRegNum = RegNum; 488 ++Count; 489 } else { 490 // Can't merge this in. Try merge the earlier ones first. 491 MergeOpsUpdate(MBB, MemOps, SIndex, i, insertAfter, SOffset, 492 Base, false, Opcode, Pred, PredReg, Scratch, dl, Merges); 493 MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch, 494 MemOps, Merges); 495 return; 496 } 497 498 if (MemOps[i].Position > MemOps[insertAfter].Position) 499 insertAfter = i; 500 } 501 502 bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1; 503 MergeOpsUpdate(MBB, MemOps, SIndex, MemOps.size(), insertAfter, SOffset, 504 Base, BaseKill, Opcode, Pred, PredReg, Scratch, dl, Merges); 505 return; 506 } 507 508 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base, 509 unsigned Bytes, unsigned Limit, 510 ARMCC::CondCodes Pred, unsigned PredReg){ 511 unsigned MyPredReg = 0; 512 if (!MI) 513 return false; 514 if (MI->getOpcode() != ARM::t2SUBri && 515 MI->getOpcode() != ARM::tSUBspi && 516 MI->getOpcode() != ARM::SUBri) 517 return false; 518 519 // Make sure the offset fits in 8 bits. 520 if (Bytes == 0 || (Limit && Bytes >= Limit)) 521 return false; 522 523 unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME 524 return (MI->getOperand(0).getReg() == Base && 525 MI->getOperand(1).getReg() == Base && 526 (MI->getOperand(2).getImm()*Scale) == Bytes && 527 llvm::getInstrPredicate(MI, MyPredReg) == Pred && 528 MyPredReg == PredReg); 529 } 530 531 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base, 532 unsigned Bytes, unsigned Limit, 533 ARMCC::CondCodes Pred, unsigned PredReg){ 534 unsigned MyPredReg = 0; 535 if (!MI) 536 return false; 537 if (MI->getOpcode() != ARM::t2ADDri && 538 MI->getOpcode() != ARM::tADDspi && 539 MI->getOpcode() != ARM::ADDri) 540 return false; 541 542 if (Bytes == 0 || (Limit && Bytes >= Limit)) 543 // Make sure the offset fits in 8 bits. 544 return false; 545 546 unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME 547 return (MI->getOperand(0).getReg() == Base && 548 MI->getOperand(1).getReg() == Base && 549 (MI->getOperand(2).getImm()*Scale) == Bytes && 550 llvm::getInstrPredicate(MI, MyPredReg) == Pred && 551 MyPredReg == PredReg); 552 } 553 554 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) { 555 switch (MI->getOpcode()) { 556 default: return 0; 557 case ARM::LDRi12: 558 case ARM::STRi12: 559 case ARM::t2LDRi8: 560 case ARM::t2LDRi12: 561 case ARM::t2STRi8: 562 case ARM::t2STRi12: 563 case ARM::VLDRS: 564 case ARM::VSTRS: 565 return 4; 566 case ARM::VLDRD: 567 case ARM::VSTRD: 568 return 8; 569 case ARM::LDMIA: 570 case ARM::LDMDA: 571 case ARM::LDMDB: 572 case ARM::LDMIB: 573 case ARM::STMIA: 574 case ARM::STMDA: 575 case ARM::STMDB: 576 case ARM::STMIB: 577 case ARM::t2LDMIA: 578 case ARM::t2LDMDB: 579 case ARM::t2STMIA: 580 case ARM::t2STMDB: 581 case ARM::VLDMSIA: 582 case ARM::VSTMSIA: 583 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4; 584 case ARM::VLDMDIA: 585 case ARM::VSTMDIA: 586 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8; 587 } 588 } 589 590 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc, 591 ARM_AM::AMSubMode Mode) { 592 switch (Opc) { 593 default: llvm_unreachable("Unhandled opcode!"); 594 case ARM::LDMIA: 595 case ARM::LDMDA: 596 case ARM::LDMDB: 597 case ARM::LDMIB: 598 switch (Mode) { 599 default: llvm_unreachable("Unhandled submode!"); 600 case ARM_AM::ia: return ARM::LDMIA_UPD; 601 case ARM_AM::ib: return ARM::LDMIB_UPD; 602 case ARM_AM::da: return ARM::LDMDA_UPD; 603 case ARM_AM::db: return ARM::LDMDB_UPD; 604 } 605 break; 606 case ARM::STMIA: 607 case ARM::STMDA: 608 case ARM::STMDB: 609 case ARM::STMIB: 610 switch (Mode) { 611 default: llvm_unreachable("Unhandled submode!"); 612 case ARM_AM::ia: return ARM::STMIA_UPD; 613 case ARM_AM::ib: return ARM::STMIB_UPD; 614 case ARM_AM::da: return ARM::STMDA_UPD; 615 case ARM_AM::db: return ARM::STMDB_UPD; 616 } 617 break; 618 case ARM::t2LDMIA: 619 case ARM::t2LDMDB: 620 switch (Mode) { 621 default: llvm_unreachable("Unhandled submode!"); 622 case ARM_AM::ia: return ARM::t2LDMIA_UPD; 623 case ARM_AM::db: return ARM::t2LDMDB_UPD; 624 } 625 break; 626 case ARM::t2STMIA: 627 case ARM::t2STMDB: 628 switch (Mode) { 629 default: llvm_unreachable("Unhandled submode!"); 630 case ARM_AM::ia: return ARM::t2STMIA_UPD; 631 case ARM_AM::db: return ARM::t2STMDB_UPD; 632 } 633 break; 634 case ARM::VLDMSIA: 635 switch (Mode) { 636 default: llvm_unreachable("Unhandled submode!"); 637 case ARM_AM::ia: return ARM::VLDMSIA_UPD; 638 case ARM_AM::db: return ARM::VLDMSDB_UPD; 639 } 640 break; 641 case ARM::VLDMDIA: 642 switch (Mode) { 643 default: llvm_unreachable("Unhandled submode!"); 644 case ARM_AM::ia: return ARM::VLDMDIA_UPD; 645 case ARM_AM::db: return ARM::VLDMDDB_UPD; 646 } 647 break; 648 case ARM::VSTMSIA: 649 switch (Mode) { 650 default: llvm_unreachable("Unhandled submode!"); 651 case ARM_AM::ia: return ARM::VSTMSIA_UPD; 652 case ARM_AM::db: return ARM::VSTMSDB_UPD; 653 } 654 break; 655 case ARM::VSTMDIA: 656 switch (Mode) { 657 default: llvm_unreachable("Unhandled submode!"); 658 case ARM_AM::ia: return ARM::VSTMDIA_UPD; 659 case ARM_AM::db: return ARM::VSTMDDB_UPD; 660 } 661 break; 662 } 663 664 return 0; 665 } 666 667 /// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base 668 /// register into the LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible: 669 /// 670 /// stmia rn, <ra, rb, rc> 671 /// rn := rn + 4 * 3; 672 /// => 673 /// stmia rn!, <ra, rb, rc> 674 /// 675 /// rn := rn - 4 * 3; 676 /// ldmia rn, <ra, rb, rc> 677 /// => 678 /// ldmdb rn!, <ra, rb, rc> 679 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB, 680 MachineBasicBlock::iterator MBBI, 681 bool &Advance, 682 MachineBasicBlock::iterator &I) { 683 MachineInstr *MI = MBBI; 684 unsigned Base = MI->getOperand(0).getReg(); 685 bool BaseKill = MI->getOperand(0).isKill(); 686 unsigned Bytes = getLSMultipleTransferSize(MI); 687 unsigned PredReg = 0; 688 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 689 int Opcode = MI->getOpcode(); 690 DebugLoc dl = MI->getDebugLoc(); 691 692 // Can't use an updating ld/st if the base register is also a dest 693 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined. 694 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i) 695 if (MI->getOperand(i).getReg() == Base) 696 return false; 697 698 bool DoMerge = false; 699 ARM_AM::AMSubMode Mode = ARM_AM::getLoadStoreMultipleSubMode(Opcode); 700 701 // Try merging with the previous instruction. 702 MachineBasicBlock::iterator BeginMBBI = MBB.begin(); 703 if (MBBI != BeginMBBI) { 704 MachineBasicBlock::iterator PrevMBBI = prior(MBBI); 705 while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue()) 706 --PrevMBBI; 707 if (Mode == ARM_AM::ia && 708 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) { 709 Mode = ARM_AM::db; 710 DoMerge = true; 711 } else if (Mode == ARM_AM::ib && 712 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) { 713 Mode = ARM_AM::da; 714 DoMerge = true; 715 } 716 if (DoMerge) 717 MBB.erase(PrevMBBI); 718 } 719 720 // Try merging with the next instruction. 721 MachineBasicBlock::iterator EndMBBI = MBB.end(); 722 if (!DoMerge && MBBI != EndMBBI) { 723 MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI); 724 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue()) 725 ++NextMBBI; 726 if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) && 727 isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) { 728 DoMerge = true; 729 } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) && 730 isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) { 731 DoMerge = true; 732 } 733 if (DoMerge) { 734 if (NextMBBI == I) { 735 Advance = true; 736 ++I; 737 } 738 MBB.erase(NextMBBI); 739 } 740 } 741 742 if (!DoMerge) 743 return false; 744 745 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode); 746 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(NewOpc)) 747 .addReg(Base, getDefRegState(true)) // WB base register 748 .addReg(Base, getKillRegState(BaseKill)) 749 .addImm(Pred).addReg(PredReg); 750 751 // Transfer the rest of operands. 752 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum) 753 MIB.addOperand(MI->getOperand(OpNum)); 754 755 // Transfer memoperands. 756 MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end()); 757 758 MBB.erase(MBBI); 759 return true; 760 } 761 762 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc, 763 ARM_AM::AddrOpc Mode) { 764 switch (Opc) { 765 case ARM::LDRi12: 766 return ARM::LDR_PRE; 767 case ARM::STRi12: 768 return ARM::STR_PRE; 769 case ARM::VLDRS: 770 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD; 771 case ARM::VLDRD: 772 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD; 773 case ARM::VSTRS: 774 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD; 775 case ARM::VSTRD: 776 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD; 777 case ARM::t2LDRi8: 778 case ARM::t2LDRi12: 779 return ARM::t2LDR_PRE; 780 case ARM::t2STRi8: 781 case ARM::t2STRi12: 782 return ARM::t2STR_PRE; 783 default: llvm_unreachable("Unhandled opcode!"); 784 } 785 return 0; 786 } 787 788 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc, 789 ARM_AM::AddrOpc Mode) { 790 switch (Opc) { 791 case ARM::LDRi12: 792 return ARM::LDR_POST; 793 case ARM::STRi12: 794 return ARM::STR_POST; 795 case ARM::VLDRS: 796 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD; 797 case ARM::VLDRD: 798 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD; 799 case ARM::VSTRS: 800 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD; 801 case ARM::VSTRD: 802 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD; 803 case ARM::t2LDRi8: 804 case ARM::t2LDRi12: 805 return ARM::t2LDR_POST; 806 case ARM::t2STRi8: 807 case ARM::t2STRi12: 808 return ARM::t2STR_POST; 809 default: llvm_unreachable("Unhandled opcode!"); 810 } 811 return 0; 812 } 813 814 /// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base 815 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible: 816 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB, 817 MachineBasicBlock::iterator MBBI, 818 const TargetInstrInfo *TII, 819 bool &Advance, 820 MachineBasicBlock::iterator &I) { 821 MachineInstr *MI = MBBI; 822 unsigned Base = MI->getOperand(1).getReg(); 823 bool BaseKill = MI->getOperand(1).isKill(); 824 unsigned Bytes = getLSMultipleTransferSize(MI); 825 int Opcode = MI->getOpcode(); 826 DebugLoc dl = MI->getDebugLoc(); 827 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS || 828 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS); 829 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12); 830 if (isi32Load(Opcode) || isi32Store(Opcode)) 831 if (MI->getOperand(2).getImm() != 0) 832 return false; 833 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0) 834 return false; 835 836 bool isLd = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD; 837 // Can't do the merge if the destination register is the same as the would-be 838 // writeback register. 839 if (isLd && MI->getOperand(0).getReg() == Base) 840 return false; 841 842 unsigned PredReg = 0; 843 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 844 bool DoMerge = false; 845 ARM_AM::AddrOpc AddSub = ARM_AM::add; 846 unsigned NewOpc = 0; 847 // AM2 - 12 bits, thumb2 - 8 bits. 848 unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100); 849 850 // Try merging with the previous instruction. 851 MachineBasicBlock::iterator BeginMBBI = MBB.begin(); 852 if (MBBI != BeginMBBI) { 853 MachineBasicBlock::iterator PrevMBBI = prior(MBBI); 854 while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue()) 855 --PrevMBBI; 856 if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) { 857 DoMerge = true; 858 AddSub = ARM_AM::sub; 859 } else if (!isAM5 && 860 isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) { 861 DoMerge = true; 862 } 863 if (DoMerge) { 864 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, AddSub); 865 MBB.erase(PrevMBBI); 866 } 867 } 868 869 // Try merging with the next instruction. 870 MachineBasicBlock::iterator EndMBBI = MBB.end(); 871 if (!DoMerge && MBBI != EndMBBI) { 872 MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI); 873 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue()) 874 ++NextMBBI; 875 if (!isAM5 && 876 isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) { 877 DoMerge = true; 878 AddSub = ARM_AM::sub; 879 } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) { 880 DoMerge = true; 881 } 882 if (DoMerge) { 883 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, AddSub); 884 if (NextMBBI == I) { 885 Advance = true; 886 ++I; 887 } 888 MBB.erase(NextMBBI); 889 } 890 } 891 892 if (!DoMerge) 893 return false; 894 895 unsigned Offset = 0; 896 if (isAM2) 897 Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift); 898 else if (!isAM5) 899 Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes; 900 901 if (isAM5) { 902 // VLDM[SD}_UPD, VSTM[SD]_UPD 903 // (There are no base-updating versions of VLDR/VSTR instructions, but the 904 // updating load/store-multiple instructions can be used with only one 905 // register.) 906 MachineOperand &MO = MI->getOperand(0); 907 BuildMI(MBB, MBBI, dl, TII->get(NewOpc)) 908 .addReg(Base, getDefRegState(true)) // WB base register 909 .addReg(Base, getKillRegState(isLd ? BaseKill : false)) 910 .addImm(Pred).addReg(PredReg) 911 .addReg(MO.getReg(), (isLd ? getDefRegState(true) : 912 getKillRegState(MO.isKill()))); 913 } else if (isLd) { 914 if (isAM2) 915 // LDR_PRE, LDR_POST, 916 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg()) 917 .addReg(Base, RegState::Define) 918 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg); 919 else 920 // t2LDR_PRE, t2LDR_POST 921 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg()) 922 .addReg(Base, RegState::Define) 923 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg); 924 } else { 925 MachineOperand &MO = MI->getOperand(0); 926 if (isAM2) 927 // STR_PRE, STR_POST 928 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base) 929 .addReg(MO.getReg(), getKillRegState(MO.isKill())) 930 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg); 931 else 932 // t2STR_PRE, t2STR_POST 933 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base) 934 .addReg(MO.getReg(), getKillRegState(MO.isKill())) 935 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg); 936 } 937 MBB.erase(MBBI); 938 939 return true; 940 } 941 942 /// isMemoryOp - Returns true if instruction is a memory operation that this 943 /// pass is capable of operating on. 944 static bool isMemoryOp(const MachineInstr *MI) { 945 // When no memory operands are present, conservatively assume unaligned, 946 // volatile, unfoldable. 947 if (!MI->hasOneMemOperand()) 948 return false; 949 950 const MachineMemOperand *MMO = *MI->memoperands_begin(); 951 952 // Don't touch volatile memory accesses - we may be changing their order. 953 if (MMO->isVolatile()) 954 return false; 955 956 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is 957 // not. 958 if (MMO->getAlignment() < 4) 959 return false; 960 961 // str <undef> could probably be eliminated entirely, but for now we just want 962 // to avoid making a mess of it. 963 // FIXME: Use str <undef> as a wildcard to enable better stm folding. 964 if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() && 965 MI->getOperand(0).isUndef()) 966 return false; 967 968 // Likewise don't mess with references to undefined addresses. 969 if (MI->getNumOperands() > 1 && MI->getOperand(1).isReg() && 970 MI->getOperand(1).isUndef()) 971 return false; 972 973 int Opcode = MI->getOpcode(); 974 switch (Opcode) { 975 default: break; 976 case ARM::VLDRS: 977 case ARM::VSTRS: 978 return MI->getOperand(1).isReg(); 979 case ARM::VLDRD: 980 case ARM::VSTRD: 981 return MI->getOperand(1).isReg(); 982 case ARM::LDRi12: 983 case ARM::STRi12: 984 case ARM::t2LDRi8: 985 case ARM::t2LDRi12: 986 case ARM::t2STRi8: 987 case ARM::t2STRi12: 988 return MI->getOperand(1).isReg(); 989 } 990 return false; 991 } 992 993 /// AdvanceRS - Advance register scavenger to just before the earliest memory 994 /// op that is being merged. 995 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) { 996 MachineBasicBlock::iterator Loc = MemOps[0].MBBI; 997 unsigned Position = MemOps[0].Position; 998 for (unsigned i = 1, e = MemOps.size(); i != e; ++i) { 999 if (MemOps[i].Position < Position) { 1000 Position = MemOps[i].Position; 1001 Loc = MemOps[i].MBBI; 1002 } 1003 } 1004 1005 if (Loc != MBB.begin()) 1006 RS->forward(prior(Loc)); 1007 } 1008 1009 static int getMemoryOpOffset(const MachineInstr *MI) { 1010 int Opcode = MI->getOpcode(); 1011 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD; 1012 unsigned NumOperands = MI->getDesc().getNumOperands(); 1013 unsigned OffField = MI->getOperand(NumOperands-3).getImm(); 1014 1015 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 || 1016 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 || 1017 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 || 1018 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12) 1019 return OffField; 1020 1021 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField) 1022 : ARM_AM::getAM5Offset(OffField) * 4; 1023 if (isAM3) { 1024 if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub) 1025 Offset = -Offset; 1026 } else { 1027 if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub) 1028 Offset = -Offset; 1029 } 1030 return Offset; 1031 } 1032 1033 static void InsertLDR_STR(MachineBasicBlock &MBB, 1034 MachineBasicBlock::iterator &MBBI, 1035 int Offset, bool isDef, 1036 DebugLoc dl, unsigned NewOpc, 1037 unsigned Reg, bool RegDeadKill, bool RegUndef, 1038 unsigned BaseReg, bool BaseKill, bool BaseUndef, 1039 bool OffKill, bool OffUndef, 1040 ARMCC::CondCodes Pred, unsigned PredReg, 1041 const TargetInstrInfo *TII, bool isT2) { 1042 if (isDef) { 1043 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(), 1044 TII->get(NewOpc)) 1045 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill)) 1046 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef)); 1047 MIB.addImm(Offset).addImm(Pred).addReg(PredReg); 1048 } else { 1049 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(), 1050 TII->get(NewOpc)) 1051 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef)) 1052 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef)); 1053 MIB.addImm(Offset).addImm(Pred).addReg(PredReg); 1054 } 1055 } 1056 1057 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB, 1058 MachineBasicBlock::iterator &MBBI) { 1059 MachineInstr *MI = &*MBBI; 1060 unsigned Opcode = MI->getOpcode(); 1061 if (Opcode == ARM::LDRD || Opcode == ARM::STRD || 1062 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) { 1063 unsigned EvenReg = MI->getOperand(0).getReg(); 1064 unsigned OddReg = MI->getOperand(1).getReg(); 1065 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false); 1066 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false); 1067 if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum) 1068 return false; 1069 1070 MachineBasicBlock::iterator NewBBI = MBBI; 1071 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8; 1072 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8; 1073 bool EvenDeadKill = isLd ? 1074 MI->getOperand(0).isDead() : MI->getOperand(0).isKill(); 1075 bool EvenUndef = MI->getOperand(0).isUndef(); 1076 bool OddDeadKill = isLd ? 1077 MI->getOperand(1).isDead() : MI->getOperand(1).isKill(); 1078 bool OddUndef = MI->getOperand(1).isUndef(); 1079 const MachineOperand &BaseOp = MI->getOperand(2); 1080 unsigned BaseReg = BaseOp.getReg(); 1081 bool BaseKill = BaseOp.isKill(); 1082 bool BaseUndef = BaseOp.isUndef(); 1083 bool OffKill = isT2 ? false : MI->getOperand(3).isKill(); 1084 bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef(); 1085 int OffImm = getMemoryOpOffset(MI); 1086 unsigned PredReg = 0; 1087 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 1088 1089 if (OddRegNum > EvenRegNum && OffImm == 0) { 1090 // Ascending register numbers and no offset. It's safe to change it to a 1091 // ldm or stm. 1092 unsigned NewOpc = (isLd) 1093 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA) 1094 : (isT2 ? ARM::t2STMIA : ARM::STMIA); 1095 if (isLd) { 1096 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 1097 .addReg(BaseReg, getKillRegState(BaseKill)) 1098 .addImm(Pred).addReg(PredReg) 1099 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill)) 1100 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill)); 1101 ++NumLDRD2LDM; 1102 } else { 1103 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 1104 .addReg(BaseReg, getKillRegState(BaseKill)) 1105 .addImm(Pred).addReg(PredReg) 1106 .addReg(EvenReg, 1107 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef)) 1108 .addReg(OddReg, 1109 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef)); 1110 ++NumSTRD2STM; 1111 } 1112 NewBBI = llvm::prior(MBBI); 1113 } else { 1114 // Split into two instructions. 1115 unsigned NewOpc = (isLd) 1116 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12) 1117 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12); 1118 DebugLoc dl = MBBI->getDebugLoc(); 1119 // If this is a load and base register is killed, it may have been 1120 // re-defed by the load, make sure the first load does not clobber it. 1121 if (isLd && 1122 (BaseKill || OffKill) && 1123 (TRI->regsOverlap(EvenReg, BaseReg))) { 1124 assert(!TRI->regsOverlap(OddReg, BaseReg)); 1125 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc, 1126 OddReg, OddDeadKill, false, 1127 BaseReg, false, BaseUndef, false, OffUndef, 1128 Pred, PredReg, TII, isT2); 1129 NewBBI = llvm::prior(MBBI); 1130 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc, 1131 EvenReg, EvenDeadKill, false, 1132 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef, 1133 Pred, PredReg, TII, isT2); 1134 } else { 1135 if (OddReg == EvenReg && EvenDeadKill) { 1136 // If the two source operands are the same, the kill marker is 1137 // probably on the first one. e.g. 1138 // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0 1139 EvenDeadKill = false; 1140 OddDeadKill = true; 1141 } 1142 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc, 1143 EvenReg, EvenDeadKill, EvenUndef, 1144 BaseReg, false, BaseUndef, false, OffUndef, 1145 Pred, PredReg, TII, isT2); 1146 NewBBI = llvm::prior(MBBI); 1147 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc, 1148 OddReg, OddDeadKill, OddUndef, 1149 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef, 1150 Pred, PredReg, TII, isT2); 1151 } 1152 if (isLd) 1153 ++NumLDRD2LDR; 1154 else 1155 ++NumSTRD2STR; 1156 } 1157 1158 MBB.erase(MI); 1159 MBBI = NewBBI; 1160 return true; 1161 } 1162 return false; 1163 } 1164 1165 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR 1166 /// ops of the same base and incrementing offset into LDM / STM ops. 1167 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) { 1168 unsigned NumMerges = 0; 1169 unsigned NumMemOps = 0; 1170 MemOpQueue MemOps; 1171 unsigned CurrBase = 0; 1172 int CurrOpc = -1; 1173 unsigned CurrSize = 0; 1174 ARMCC::CondCodes CurrPred = ARMCC::AL; 1175 unsigned CurrPredReg = 0; 1176 unsigned Position = 0; 1177 SmallVector<MachineBasicBlock::iterator,4> Merges; 1178 1179 RS->enterBasicBlock(&MBB); 1180 MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); 1181 while (MBBI != E) { 1182 if (FixInvalidRegPairOp(MBB, MBBI)) 1183 continue; 1184 1185 bool Advance = false; 1186 bool TryMerge = false; 1187 bool Clobber = false; 1188 1189 bool isMemOp = isMemoryOp(MBBI); 1190 if (isMemOp) { 1191 int Opcode = MBBI->getOpcode(); 1192 unsigned Size = getLSMultipleTransferSize(MBBI); 1193 const MachineOperand &MO = MBBI->getOperand(0); 1194 unsigned Reg = MO.getReg(); 1195 bool isKill = MO.isDef() ? false : MO.isKill(); 1196 unsigned Base = MBBI->getOperand(1).getReg(); 1197 unsigned PredReg = 0; 1198 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MBBI, PredReg); 1199 int Offset = getMemoryOpOffset(MBBI); 1200 // Watch out for: 1201 // r4 := ldr [r5] 1202 // r5 := ldr [r5, #4] 1203 // r6 := ldr [r5, #8] 1204 // 1205 // The second ldr has effectively broken the chain even though it 1206 // looks like the later ldr(s) use the same base register. Try to 1207 // merge the ldr's so far, including this one. But don't try to 1208 // combine the following ldr(s). 1209 Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg()); 1210 if (CurrBase == 0 && !Clobber) { 1211 // Start of a new chain. 1212 CurrBase = Base; 1213 CurrOpc = Opcode; 1214 CurrSize = Size; 1215 CurrPred = Pred; 1216 CurrPredReg = PredReg; 1217 MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI)); 1218 ++NumMemOps; 1219 Advance = true; 1220 } else { 1221 if (Clobber) { 1222 TryMerge = true; 1223 Advance = true; 1224 } 1225 1226 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) { 1227 // No need to match PredReg. 1228 // Continue adding to the queue. 1229 if (Offset > MemOps.back().Offset) { 1230 MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, 1231 Position, MBBI)); 1232 ++NumMemOps; 1233 Advance = true; 1234 } else { 1235 for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end(); 1236 I != E; ++I) { 1237 if (Offset < I->Offset) { 1238 MemOps.insert(I, MemOpQueueEntry(Offset, Reg, isKill, 1239 Position, MBBI)); 1240 ++NumMemOps; 1241 Advance = true; 1242 break; 1243 } else if (Offset == I->Offset) { 1244 // Collision! This can't be merged! 1245 break; 1246 } 1247 } 1248 } 1249 } 1250 } 1251 } 1252 1253 if (MBBI->isDebugValue()) { 1254 ++MBBI; 1255 if (MBBI == E) 1256 // Reach the end of the block, try merging the memory instructions. 1257 TryMerge = true; 1258 } else if (Advance) { 1259 ++Position; 1260 ++MBBI; 1261 if (MBBI == E) 1262 // Reach the end of the block, try merging the memory instructions. 1263 TryMerge = true; 1264 } else 1265 TryMerge = true; 1266 1267 if (TryMerge) { 1268 if (NumMemOps > 1) { 1269 // Try to find a free register to use as a new base in case it's needed. 1270 // First advance to the instruction just before the start of the chain. 1271 AdvanceRS(MBB, MemOps); 1272 // Find a scratch register. 1273 unsigned Scratch = RS->FindUnusedReg(ARM::GPRRegisterClass); 1274 // Process the load / store instructions. 1275 RS->forward(prior(MBBI)); 1276 1277 // Merge ops. 1278 Merges.clear(); 1279 MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize, 1280 CurrPred, CurrPredReg, Scratch, MemOps, Merges); 1281 1282 // Try folding preceding/trailing base inc/dec into the generated 1283 // LDM/STM ops. 1284 for (unsigned i = 0, e = Merges.size(); i < e; ++i) 1285 if (MergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI)) 1286 ++NumMerges; 1287 NumMerges += Merges.size(); 1288 1289 // Try folding preceding/trailing base inc/dec into those load/store 1290 // that were not merged to form LDM/STM ops. 1291 for (unsigned i = 0; i != NumMemOps; ++i) 1292 if (!MemOps[i].Merged) 1293 if (MergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI)) 1294 ++NumMerges; 1295 1296 // RS may be pointing to an instruction that's deleted. 1297 RS->skipTo(prior(MBBI)); 1298 } else if (NumMemOps == 1) { 1299 // Try folding preceding/trailing base inc/dec into the single 1300 // load/store. 1301 if (MergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) { 1302 ++NumMerges; 1303 RS->forward(prior(MBBI)); 1304 } 1305 } 1306 1307 CurrBase = 0; 1308 CurrOpc = -1; 1309 CurrSize = 0; 1310 CurrPred = ARMCC::AL; 1311 CurrPredReg = 0; 1312 if (NumMemOps) { 1313 MemOps.clear(); 1314 NumMemOps = 0; 1315 } 1316 1317 // If iterator hasn't been advanced and this is not a memory op, skip it. 1318 // It can't start a new chain anyway. 1319 if (!Advance && !isMemOp && MBBI != E) { 1320 ++Position; 1321 ++MBBI; 1322 } 1323 } 1324 } 1325 return NumMerges > 0; 1326 } 1327 1328 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return ops 1329 /// ("bx lr" and "mov pc, lr") into the preceding stack restore so it 1330 /// directly restore the value of LR into pc. 1331 /// ldmfd sp!, {..., lr} 1332 /// bx lr 1333 /// or 1334 /// ldmfd sp!, {..., lr} 1335 /// mov pc, lr 1336 /// => 1337 /// ldmfd sp!, {..., pc} 1338 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) { 1339 if (MBB.empty()) return false; 1340 1341 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr(); 1342 if (MBBI != MBB.begin() && 1343 (MBBI->getOpcode() == ARM::BX_RET || 1344 MBBI->getOpcode() == ARM::tBX_RET || 1345 MBBI->getOpcode() == ARM::MOVPCLR)) { 1346 MachineInstr *PrevMI = prior(MBBI); 1347 unsigned Opcode = PrevMI->getOpcode(); 1348 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD || 1349 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD || 1350 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) { 1351 MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1); 1352 if (MO.getReg() != ARM::LR) 1353 return false; 1354 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET); 1355 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) || 1356 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!"); 1357 PrevMI->setDesc(TII->get(NewOpc)); 1358 MO.setReg(ARM::PC); 1359 PrevMI->copyImplicitOps(&*MBBI); 1360 MBB.erase(MBBI); 1361 return true; 1362 } 1363 } 1364 return false; 1365 } 1366 1367 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { 1368 const TargetMachine &TM = Fn.getTarget(); 1369 AFI = Fn.getInfo<ARMFunctionInfo>(); 1370 TII = TM.getInstrInfo(); 1371 TRI = TM.getRegisterInfo(); 1372 RS = new RegScavenger(); 1373 isThumb2 = AFI->isThumb2Function(); 1374 1375 bool Modified = false; 1376 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 1377 ++MFI) { 1378 MachineBasicBlock &MBB = *MFI; 1379 Modified |= LoadStoreMultipleOpti(MBB); 1380 if (TM.getSubtarget<ARMSubtarget>().hasV5TOps()) 1381 Modified |= MergeReturnIntoLDM(MBB); 1382 } 1383 1384 delete RS; 1385 return Modified; 1386 } 1387 1388 1389 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move 1390 /// load / stores from consecutive locations close to make it more 1391 /// likely they will be combined later. 1392 1393 namespace { 1394 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{ 1395 static char ID; 1396 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {} 1397 1398 const TargetData *TD; 1399 const TargetInstrInfo *TII; 1400 const TargetRegisterInfo *TRI; 1401 const ARMSubtarget *STI; 1402 MachineRegisterInfo *MRI; 1403 MachineFunction *MF; 1404 1405 virtual bool runOnMachineFunction(MachineFunction &Fn); 1406 1407 virtual const char *getPassName() const { 1408 return "ARM pre- register allocation load / store optimization pass"; 1409 } 1410 1411 private: 1412 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl, 1413 unsigned &NewOpc, unsigned &EvenReg, 1414 unsigned &OddReg, unsigned &BaseReg, 1415 int &Offset, 1416 unsigned &PredReg, ARMCC::CondCodes &Pred, 1417 bool &isT2); 1418 bool RescheduleOps(MachineBasicBlock *MBB, 1419 SmallVector<MachineInstr*, 4> &Ops, 1420 unsigned Base, bool isLd, 1421 DenseMap<MachineInstr*, unsigned> &MI2LocMap); 1422 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB); 1423 }; 1424 char ARMPreAllocLoadStoreOpt::ID = 0; 1425 } 1426 1427 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { 1428 TD = Fn.getTarget().getTargetData(); 1429 TII = Fn.getTarget().getInstrInfo(); 1430 TRI = Fn.getTarget().getRegisterInfo(); 1431 STI = &Fn.getTarget().getSubtarget<ARMSubtarget>(); 1432 MRI = &Fn.getRegInfo(); 1433 MF = &Fn; 1434 1435 bool Modified = false; 1436 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 1437 ++MFI) 1438 Modified |= RescheduleLoadStoreInstrs(MFI); 1439 1440 return Modified; 1441 } 1442 1443 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base, 1444 MachineBasicBlock::iterator I, 1445 MachineBasicBlock::iterator E, 1446 SmallPtrSet<MachineInstr*, 4> &MemOps, 1447 SmallSet<unsigned, 4> &MemRegs, 1448 const TargetRegisterInfo *TRI) { 1449 // Are there stores / loads / calls between them? 1450 // FIXME: This is overly conservative. We should make use of alias information 1451 // some day. 1452 SmallSet<unsigned, 4> AddedRegPressure; 1453 while (++I != E) { 1454 if (I->isDebugValue() || MemOps.count(&*I)) 1455 continue; 1456 const MCInstrDesc &MCID = I->getDesc(); 1457 if (MCID.isCall() || MCID.isTerminator() || I->hasUnmodeledSideEffects()) 1458 return false; 1459 if (isLd && MCID.mayStore()) 1460 return false; 1461 if (!isLd) { 1462 if (MCID.mayLoad()) 1463 return false; 1464 // It's not safe to move the first 'str' down. 1465 // str r1, [r0] 1466 // strh r5, [r0] 1467 // str r4, [r0, #+4] 1468 if (MCID.mayStore()) 1469 return false; 1470 } 1471 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) { 1472 MachineOperand &MO = I->getOperand(j); 1473 if (!MO.isReg()) 1474 continue; 1475 unsigned Reg = MO.getReg(); 1476 if (MO.isDef() && TRI->regsOverlap(Reg, Base)) 1477 return false; 1478 if (Reg != Base && !MemRegs.count(Reg)) 1479 AddedRegPressure.insert(Reg); 1480 } 1481 } 1482 1483 // Estimate register pressure increase due to the transformation. 1484 if (MemRegs.size() <= 4) 1485 // Ok if we are moving small number of instructions. 1486 return true; 1487 return AddedRegPressure.size() <= MemRegs.size() * 2; 1488 } 1489 1490 bool 1491 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, 1492 DebugLoc &dl, 1493 unsigned &NewOpc, unsigned &EvenReg, 1494 unsigned &OddReg, unsigned &BaseReg, 1495 int &Offset, unsigned &PredReg, 1496 ARMCC::CondCodes &Pred, 1497 bool &isT2) { 1498 // Make sure we're allowed to generate LDRD/STRD. 1499 if (!STI->hasV5TEOps()) 1500 return false; 1501 1502 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD 1503 unsigned Scale = 1; 1504 unsigned Opcode = Op0->getOpcode(); 1505 if (Opcode == ARM::LDRi12) 1506 NewOpc = ARM::LDRD; 1507 else if (Opcode == ARM::STRi12) 1508 NewOpc = ARM::STRD; 1509 else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) { 1510 NewOpc = ARM::t2LDRDi8; 1511 Scale = 4; 1512 isT2 = true; 1513 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) { 1514 NewOpc = ARM::t2STRDi8; 1515 Scale = 4; 1516 isT2 = true; 1517 } else 1518 return false; 1519 1520 // Make sure the base address satisfies i64 ld / st alignment requirement. 1521 if (!Op0->hasOneMemOperand() || 1522 !(*Op0->memoperands_begin())->getValue() || 1523 (*Op0->memoperands_begin())->isVolatile()) 1524 return false; 1525 1526 unsigned Align = (*Op0->memoperands_begin())->getAlignment(); 1527 const Function *Func = MF->getFunction(); 1528 unsigned ReqAlign = STI->hasV6Ops() 1529 ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext())) 1530 : 8; // Pre-v6 need 8-byte align 1531 if (Align < ReqAlign) 1532 return false; 1533 1534 // Then make sure the immediate offset fits. 1535 int OffImm = getMemoryOpOffset(Op0); 1536 if (isT2) { 1537 int Limit = (1 << 8) * Scale; 1538 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1))) 1539 return false; 1540 Offset = OffImm; 1541 } else { 1542 ARM_AM::AddrOpc AddSub = ARM_AM::add; 1543 if (OffImm < 0) { 1544 AddSub = ARM_AM::sub; 1545 OffImm = - OffImm; 1546 } 1547 int Limit = (1 << 8) * Scale; 1548 if (OffImm >= Limit || (OffImm & (Scale-1))) 1549 return false; 1550 Offset = ARM_AM::getAM3Opc(AddSub, OffImm); 1551 } 1552 EvenReg = Op0->getOperand(0).getReg(); 1553 OddReg = Op1->getOperand(0).getReg(); 1554 if (EvenReg == OddReg) 1555 return false; 1556 BaseReg = Op0->getOperand(1).getReg(); 1557 Pred = llvm::getInstrPredicate(Op0, PredReg); 1558 dl = Op0->getDebugLoc(); 1559 return true; 1560 } 1561 1562 namespace { 1563 struct OffsetCompare { 1564 bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const { 1565 int LOffset = getMemoryOpOffset(LHS); 1566 int ROffset = getMemoryOpOffset(RHS); 1567 assert(LHS == RHS || LOffset != ROffset); 1568 return LOffset > ROffset; 1569 } 1570 }; 1571 } 1572 1573 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB, 1574 SmallVector<MachineInstr*, 4> &Ops, 1575 unsigned Base, bool isLd, 1576 DenseMap<MachineInstr*, unsigned> &MI2LocMap) { 1577 bool RetVal = false; 1578 1579 // Sort by offset (in reverse order). 1580 std::sort(Ops.begin(), Ops.end(), OffsetCompare()); 1581 1582 // The loads / stores of the same base are in order. Scan them from first to 1583 // last and check for the following: 1584 // 1. Any def of base. 1585 // 2. Any gaps. 1586 while (Ops.size() > 1) { 1587 unsigned FirstLoc = ~0U; 1588 unsigned LastLoc = 0; 1589 MachineInstr *FirstOp = 0; 1590 MachineInstr *LastOp = 0; 1591 int LastOffset = 0; 1592 unsigned LastOpcode = 0; 1593 unsigned LastBytes = 0; 1594 unsigned NumMove = 0; 1595 for (int i = Ops.size() - 1; i >= 0; --i) { 1596 MachineInstr *Op = Ops[i]; 1597 unsigned Loc = MI2LocMap[Op]; 1598 if (Loc <= FirstLoc) { 1599 FirstLoc = Loc; 1600 FirstOp = Op; 1601 } 1602 if (Loc >= LastLoc) { 1603 LastLoc = Loc; 1604 LastOp = Op; 1605 } 1606 1607 unsigned Opcode = Op->getOpcode(); 1608 if (LastOpcode && Opcode != LastOpcode) 1609 break; 1610 1611 int Offset = getMemoryOpOffset(Op); 1612 unsigned Bytes = getLSMultipleTransferSize(Op); 1613 if (LastBytes) { 1614 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes)) 1615 break; 1616 } 1617 LastOffset = Offset; 1618 LastBytes = Bytes; 1619 LastOpcode = Opcode; 1620 if (++NumMove == 8) // FIXME: Tune this limit. 1621 break; 1622 } 1623 1624 if (NumMove <= 1) 1625 Ops.pop_back(); 1626 else { 1627 SmallPtrSet<MachineInstr*, 4> MemOps; 1628 SmallSet<unsigned, 4> MemRegs; 1629 for (int i = NumMove-1; i >= 0; --i) { 1630 MemOps.insert(Ops[i]); 1631 MemRegs.insert(Ops[i]->getOperand(0).getReg()); 1632 } 1633 1634 // Be conservative, if the instructions are too far apart, don't 1635 // move them. We want to limit the increase of register pressure. 1636 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this. 1637 if (DoMove) 1638 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp, 1639 MemOps, MemRegs, TRI); 1640 if (!DoMove) { 1641 for (unsigned i = 0; i != NumMove; ++i) 1642 Ops.pop_back(); 1643 } else { 1644 // This is the new location for the loads / stores. 1645 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp; 1646 while (InsertPos != MBB->end() 1647 && (MemOps.count(InsertPos) || InsertPos->isDebugValue())) 1648 ++InsertPos; 1649 1650 // If we are moving a pair of loads / stores, see if it makes sense 1651 // to try to allocate a pair of registers that can form register pairs. 1652 MachineInstr *Op0 = Ops.back(); 1653 MachineInstr *Op1 = Ops[Ops.size()-2]; 1654 unsigned EvenReg = 0, OddReg = 0; 1655 unsigned BaseReg = 0, PredReg = 0; 1656 ARMCC::CondCodes Pred = ARMCC::AL; 1657 bool isT2 = false; 1658 unsigned NewOpc = 0; 1659 int Offset = 0; 1660 DebugLoc dl; 1661 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc, 1662 EvenReg, OddReg, BaseReg, 1663 Offset, PredReg, Pred, isT2)) { 1664 Ops.pop_back(); 1665 Ops.pop_back(); 1666 1667 const MCInstrDesc &MCID = TII->get(NewOpc); 1668 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI); 1669 MRI->constrainRegClass(EvenReg, TRC); 1670 MRI->constrainRegClass(OddReg, TRC); 1671 1672 // Form the pair instruction. 1673 if (isLd) { 1674 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID) 1675 .addReg(EvenReg, RegState::Define) 1676 .addReg(OddReg, RegState::Define) 1677 .addReg(BaseReg); 1678 // FIXME: We're converting from LDRi12 to an insn that still 1679 // uses addrmode2, so we need an explicit offset reg. It should 1680 // always by reg0 since we're transforming LDRi12s. 1681 if (!isT2) 1682 MIB.addReg(0); 1683 MIB.addImm(Offset).addImm(Pred).addReg(PredReg); 1684 ++NumLDRDFormed; 1685 } else { 1686 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID) 1687 .addReg(EvenReg) 1688 .addReg(OddReg) 1689 .addReg(BaseReg); 1690 // FIXME: We're converting from LDRi12 to an insn that still 1691 // uses addrmode2, so we need an explicit offset reg. It should 1692 // always by reg0 since we're transforming STRi12s. 1693 if (!isT2) 1694 MIB.addReg(0); 1695 MIB.addImm(Offset).addImm(Pred).addReg(PredReg); 1696 ++NumSTRDFormed; 1697 } 1698 MBB->erase(Op0); 1699 MBB->erase(Op1); 1700 1701 // Add register allocation hints to form register pairs. 1702 MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg); 1703 MRI->setRegAllocationHint(OddReg, ARMRI::RegPairOdd, EvenReg); 1704 } else { 1705 for (unsigned i = 0; i != NumMove; ++i) { 1706 MachineInstr *Op = Ops.back(); 1707 Ops.pop_back(); 1708 MBB->splice(InsertPos, MBB, Op); 1709 } 1710 } 1711 1712 NumLdStMoved += NumMove; 1713 RetVal = true; 1714 } 1715 } 1716 } 1717 1718 return RetVal; 1719 } 1720 1721 bool 1722 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) { 1723 bool RetVal = false; 1724 1725 DenseMap<MachineInstr*, unsigned> MI2LocMap; 1726 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap; 1727 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap; 1728 SmallVector<unsigned, 4> LdBases; 1729 SmallVector<unsigned, 4> StBases; 1730 1731 unsigned Loc = 0; 1732 MachineBasicBlock::iterator MBBI = MBB->begin(); 1733 MachineBasicBlock::iterator E = MBB->end(); 1734 while (MBBI != E) { 1735 for (; MBBI != E; ++MBBI) { 1736 MachineInstr *MI = MBBI; 1737 const MCInstrDesc &MCID = MI->getDesc(); 1738 if (MCID.isCall() || MCID.isTerminator()) { 1739 // Stop at barriers. 1740 ++MBBI; 1741 break; 1742 } 1743 1744 if (!MI->isDebugValue()) 1745 MI2LocMap[MI] = ++Loc; 1746 1747 if (!isMemoryOp(MI)) 1748 continue; 1749 unsigned PredReg = 0; 1750 if (llvm::getInstrPredicate(MI, PredReg) != ARMCC::AL) 1751 continue; 1752 1753 int Opc = MI->getOpcode(); 1754 bool isLd = isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD; 1755 unsigned Base = MI->getOperand(1).getReg(); 1756 int Offset = getMemoryOpOffset(MI); 1757 1758 bool StopHere = false; 1759 if (isLd) { 1760 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI = 1761 Base2LdsMap.find(Base); 1762 if (BI != Base2LdsMap.end()) { 1763 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) { 1764 if (Offset == getMemoryOpOffset(BI->second[i])) { 1765 StopHere = true; 1766 break; 1767 } 1768 } 1769 if (!StopHere) 1770 BI->second.push_back(MI); 1771 } else { 1772 SmallVector<MachineInstr*, 4> MIs; 1773 MIs.push_back(MI); 1774 Base2LdsMap[Base] = MIs; 1775 LdBases.push_back(Base); 1776 } 1777 } else { 1778 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI = 1779 Base2StsMap.find(Base); 1780 if (BI != Base2StsMap.end()) { 1781 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) { 1782 if (Offset == getMemoryOpOffset(BI->second[i])) { 1783 StopHere = true; 1784 break; 1785 } 1786 } 1787 if (!StopHere) 1788 BI->second.push_back(MI); 1789 } else { 1790 SmallVector<MachineInstr*, 4> MIs; 1791 MIs.push_back(MI); 1792 Base2StsMap[Base] = MIs; 1793 StBases.push_back(Base); 1794 } 1795 } 1796 1797 if (StopHere) { 1798 // Found a duplicate (a base+offset combination that's seen earlier). 1799 // Backtrack. 1800 --Loc; 1801 break; 1802 } 1803 } 1804 1805 // Re-schedule loads. 1806 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) { 1807 unsigned Base = LdBases[i]; 1808 SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base]; 1809 if (Lds.size() > 1) 1810 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap); 1811 } 1812 1813 // Re-schedule stores. 1814 for (unsigned i = 0, e = StBases.size(); i != e; ++i) { 1815 unsigned Base = StBases[i]; 1816 SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base]; 1817 if (Sts.size() > 1) 1818 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap); 1819 } 1820 1821 if (MBBI != E) { 1822 Base2LdsMap.clear(); 1823 Base2StsMap.clear(); 1824 LdBases.clear(); 1825 StBases.clear(); 1826 } 1827 } 1828 1829 return RetVal; 1830 } 1831 1832 1833 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store 1834 /// optimization pass. 1835 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) { 1836 if (PreAlloc) 1837 return new ARMPreAllocLoadStoreOpt(); 1838 return new ARMLoadStoreOpt(); 1839 } 1840
