PeepholeOptimizer.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
1//===-- PeepholeOptimizer.cpp - Peephole Optimizations --------------------===// 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// Perform peephole optimizations on the machine code: 11// 12// - Optimize Extensions 13// 14// Optimization of sign / zero extension instructions. It may be extended to 15// handle other instructions with similar properties. 16// 17// On some targets, some instructions, e.g. X86 sign / zero extension, may 18// leave the source value in the lower part of the result. This optimization 19// will replace some uses of the pre-extension value with uses of the 20// sub-register of the results. 21// 22// - Optimize Comparisons 23// 24// Optimization of comparison instructions. For instance, in this code: 25// 26// sub r1, 1 27// cmp r1, 0 28// bz L1 29// 30// If the "sub" instruction all ready sets (or could be modified to set) the 31// same flag that the "cmp" instruction sets and that "bz" uses, then we can 32// eliminate the "cmp" instruction. 33// 34// Another instance, in this code: 35// 36// sub r1, r3 | sub r1, imm 37// cmp r3, r1 or cmp r1, r3 | cmp r1, imm 38// bge L1 39// 40// If the branch instruction can use flag from "sub", then we can replace 41// "sub" with "subs" and eliminate the "cmp" instruction. 42// 43// - Optimize Loads: 44// 45// Loads that can be folded into a later instruction. A load is foldable 46// if it loads to virtual registers and the virtual register defined has 47// a single use. 48// 49// - Optimize Copies and Bitcast: 50// 51// Rewrite copies and bitcasts to avoid cross register bank copies 52// when possible. 53// E.g., Consider the following example, where capital and lower 54// letters denote different register file: 55// b = copy A <-- cross-bank copy 56// C = copy b <-- cross-bank copy 57// => 58// b = copy A <-- cross-bank copy 59// C = copy A <-- same-bank copy 60// 61// E.g., for bitcast: 62// b = bitcast A <-- cross-bank copy 63// C = bitcast b <-- cross-bank copy 64// => 65// b = bitcast A <-- cross-bank copy 66// C = copy A <-- same-bank copy 67//===----------------------------------------------------------------------===// 68 69#include "llvm/CodeGen/Passes.h" 70#include "llvm/ADT/DenseMap.h" 71#include "llvm/ADT/SmallPtrSet.h" 72#include "llvm/ADT/SmallSet.h" 73#include "llvm/ADT/Statistic.h" 74#include "llvm/CodeGen/MachineDominators.h" 75#include "llvm/CodeGen/MachineInstrBuilder.h" 76#include "llvm/CodeGen/MachineRegisterInfo.h" 77#include "llvm/Support/CommandLine.h" 78#include "llvm/Support/Debug.h" 79#include "llvm/Target/TargetInstrInfo.h" 80#include "llvm/Target/TargetRegisterInfo.h" 81using namespace llvm; 82 83#define DEBUG_TYPE "peephole-opt" 84 85// Optimize Extensions 86static cl::opt<bool> 87Aggressive("aggressive-ext-opt", cl::Hidden, 88 cl::desc("Aggressive extension optimization")); 89 90static cl::opt<bool> 91DisablePeephole("disable-peephole", cl::Hidden, cl::init(false), 92 cl::desc("Disable the peephole optimizer")); 93 94STATISTIC(NumReuse, "Number of extension results reused"); 95STATISTIC(NumCmps, "Number of compares eliminated"); 96STATISTIC(NumImmFold, "Number of move immediate folded"); 97STATISTIC(NumLoadFold, "Number of loads folded"); 98STATISTIC(NumSelects, "Number of selects optimized"); 99STATISTIC(NumCopiesBitcasts, "Number of copies/bitcasts optimized"); 100 101namespace { 102 class PeepholeOptimizer : public MachineFunctionPass { 103 const TargetMachine *TM; 104 const TargetInstrInfo *TII; 105 MachineRegisterInfo *MRI; 106 MachineDominatorTree *DT; // Machine dominator tree 107 108 public: 109 static char ID; // Pass identification 110 PeepholeOptimizer() : MachineFunctionPass(ID) { 111 initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); 112 } 113 114 bool runOnMachineFunction(MachineFunction &MF) override; 115 116 void getAnalysisUsage(AnalysisUsage &AU) const override { 117 AU.setPreservesCFG(); 118 MachineFunctionPass::getAnalysisUsage(AU); 119 if (Aggressive) { 120 AU.addRequired<MachineDominatorTree>(); 121 AU.addPreserved<MachineDominatorTree>(); 122 } 123 } 124 125 private: 126 bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); 127 bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 128 SmallPtrSet<MachineInstr*, 8> &LocalMIs); 129 bool optimizeSelect(MachineInstr *MI); 130 bool optimizeCopyOrBitcast(MachineInstr *MI); 131 bool isMoveImmediate(MachineInstr *MI, 132 SmallSet<unsigned, 4> &ImmDefRegs, 133 DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 134 bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 135 SmallSet<unsigned, 4> &ImmDefRegs, 136 DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 137 bool isLoadFoldable(MachineInstr *MI, 138 SmallSet<unsigned, 16> &FoldAsLoadDefCandidates); 139 }; 140} 141 142char PeepholeOptimizer::ID = 0; 143char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; 144INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts", 145 "Peephole Optimizations", false, false) 146INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 147INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts", 148 "Peephole Optimizations", false, false) 149 150/// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads 151/// a single register and writes a single register and it does not modify the 152/// source, and if the source value is preserved as a sub-register of the 153/// result, then replace all reachable uses of the source with the subreg of the 154/// result. 155/// 156/// Do not generate an EXTRACT that is used only in a debug use, as this changes 157/// the code. Since this code does not currently share EXTRACTs, just ignore all 158/// debug uses. 159bool PeepholeOptimizer:: 160optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 161 SmallPtrSet<MachineInstr*, 8> &LocalMIs) { 162 unsigned SrcReg, DstReg, SubIdx; 163 if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx)) 164 return false; 165 166 if (TargetRegisterInfo::isPhysicalRegister(DstReg) || 167 TargetRegisterInfo::isPhysicalRegister(SrcReg)) 168 return false; 169 170 if (MRI->hasOneNonDBGUse(SrcReg)) 171 // No other uses. 172 return false; 173 174 // Ensure DstReg can get a register class that actually supports 175 // sub-registers. Don't change the class until we commit. 176 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 177 DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx); 178 if (!DstRC) 179 return false; 180 181 // The ext instr may be operating on a sub-register of SrcReg as well. 182 // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit 183 // register. 184 // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of 185 // SrcReg:SubIdx should be replaced. 186 bool UseSrcSubIdx = TM->getRegisterInfo()-> 187 getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr; 188 189 // The source has other uses. See if we can replace the other uses with use of 190 // the result of the extension. 191 SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; 192 for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) 193 ReachedBBs.insert(UI.getParent()); 194 195 // Uses that are in the same BB of uses of the result of the instruction. 196 SmallVector<MachineOperand*, 8> Uses; 197 198 // Uses that the result of the instruction can reach. 199 SmallVector<MachineOperand*, 8> ExtendedUses; 200 201 bool ExtendLife = true; 202 for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) { 203 MachineInstr *UseMI = UseMO.getParent(); 204 if (UseMI == MI) 205 continue; 206 207 if (UseMI->isPHI()) { 208 ExtendLife = false; 209 continue; 210 } 211 212 // Only accept uses of SrcReg:SubIdx. 213 if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx) 214 continue; 215 216 // It's an error to translate this: 217 // 218 // %reg1025 = <sext> %reg1024 219 // ... 220 // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 221 // 222 // into this: 223 // 224 // %reg1025 = <sext> %reg1024 225 // ... 226 // %reg1027 = COPY %reg1025:4 227 // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 228 // 229 // The problem here is that SUBREG_TO_REG is there to assert that an 230 // implicit zext occurs. It doesn't insert a zext instruction. If we allow 231 // the COPY here, it will give us the value after the <sext>, not the 232 // original value of %reg1024 before <sext>. 233 if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) 234 continue; 235 236 MachineBasicBlock *UseMBB = UseMI->getParent(); 237 if (UseMBB == MBB) { 238 // Local uses that come after the extension. 239 if (!LocalMIs.count(UseMI)) 240 Uses.push_back(&UseMO); 241 } else if (ReachedBBs.count(UseMBB)) { 242 // Non-local uses where the result of the extension is used. Always 243 // replace these unless it's a PHI. 244 Uses.push_back(&UseMO); 245 } else if (Aggressive && DT->dominates(MBB, UseMBB)) { 246 // We may want to extend the live range of the extension result in order 247 // to replace these uses. 248 ExtendedUses.push_back(&UseMO); 249 } else { 250 // Both will be live out of the def MBB anyway. Don't extend live range of 251 // the extension result. 252 ExtendLife = false; 253 break; 254 } 255 } 256 257 if (ExtendLife && !ExtendedUses.empty()) 258 // Extend the liveness of the extension result. 259 std::copy(ExtendedUses.begin(), ExtendedUses.end(), 260 std::back_inserter(Uses)); 261 262 // Now replace all uses. 263 bool Changed = false; 264 if (!Uses.empty()) { 265 SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; 266 267 // Look for PHI uses of the extended result, we don't want to extend the 268 // liveness of a PHI input. It breaks all kinds of assumptions down 269 // stream. A PHI use is expected to be the kill of its source values. 270 for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) 271 if (UI.isPHI()) 272 PHIBBs.insert(UI.getParent()); 273 274 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 275 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 276 MachineOperand *UseMO = Uses[i]; 277 MachineInstr *UseMI = UseMO->getParent(); 278 MachineBasicBlock *UseMBB = UseMI->getParent(); 279 if (PHIBBs.count(UseMBB)) 280 continue; 281 282 // About to add uses of DstReg, clear DstReg's kill flags. 283 if (!Changed) { 284 MRI->clearKillFlags(DstReg); 285 MRI->constrainRegClass(DstReg, DstRC); 286 } 287 288 unsigned NewVR = MRI->createVirtualRegister(RC); 289 MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), 290 TII->get(TargetOpcode::COPY), NewVR) 291 .addReg(DstReg, 0, SubIdx); 292 // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set. 293 if (UseSrcSubIdx) { 294 Copy->getOperand(0).setSubReg(SubIdx); 295 Copy->getOperand(0).setIsUndef(); 296 } 297 UseMO->setReg(NewVR); 298 ++NumReuse; 299 Changed = true; 300 } 301 } 302 303 return Changed; 304} 305 306/// optimizeCmpInstr - If the instruction is a compare and the previous 307/// instruction it's comparing against all ready sets (or could be modified to 308/// set) the same flag as the compare, then we can remove the comparison and use 309/// the flag from the previous instruction. 310bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI, 311 MachineBasicBlock *MBB) { 312 // If this instruction is a comparison against zero and isn't comparing a 313 // physical register, we can try to optimize it. 314 unsigned SrcReg, SrcReg2; 315 int CmpMask, CmpValue; 316 if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || 317 TargetRegisterInfo::isPhysicalRegister(SrcReg) || 318 (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2))) 319 return false; 320 321 // Attempt to optimize the comparison instruction. 322 if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { 323 ++NumCmps; 324 return true; 325 } 326 327 return false; 328} 329 330/// Optimize a select instruction. 331bool PeepholeOptimizer::optimizeSelect(MachineInstr *MI) { 332 unsigned TrueOp = 0; 333 unsigned FalseOp = 0; 334 bool Optimizable = false; 335 SmallVector<MachineOperand, 4> Cond; 336 if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable)) 337 return false; 338 if (!Optimizable) 339 return false; 340 if (!TII->optimizeSelect(MI)) 341 return false; 342 MI->eraseFromParent(); 343 ++NumSelects; 344 return true; 345} 346 347/// \brief Check if the registers defined by the pair (RegisterClass, SubReg) 348/// share the same register file. 349static bool shareSameRegisterFile(const TargetRegisterInfo &TRI, 350 const TargetRegisterClass *DefRC, 351 unsigned DefSubReg, 352 const TargetRegisterClass *SrcRC, 353 unsigned SrcSubReg) { 354 // Same register class. 355 if (DefRC == SrcRC) 356 return true; 357 358 // Both operands are sub registers. Check if they share a register class. 359 unsigned SrcIdx, DefIdx; 360 if (SrcSubReg && DefSubReg) 361 return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg, 362 SrcIdx, DefIdx) != nullptr; 363 // At most one of the register is a sub register, make it Src to avoid 364 // duplicating the test. 365 if (!SrcSubReg) { 366 std::swap(DefSubReg, SrcSubReg); 367 std::swap(DefRC, SrcRC); 368 } 369 370 // One of the register is a sub register, check if we can get a superclass. 371 if (SrcSubReg) 372 return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr; 373 // Plain copy. 374 return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr; 375} 376 377/// \brief Get the index of the definition and source for \p Copy 378/// instruction. 379/// \pre Copy.isCopy() or Copy.isBitcast(). 380/// \return True if the Copy instruction has only one register source 381/// and one register definition. Otherwise, \p DefIdx and \p SrcIdx 382/// are invalid. 383static bool getCopyOrBitcastDefUseIdx(const MachineInstr &Copy, 384 unsigned &DefIdx, unsigned &SrcIdx) { 385 assert((Copy.isCopy() || Copy.isBitcast()) && "Wrong operation type."); 386 if (Copy.isCopy()) { 387 // Copy instruction are supposed to be: Def = Src. 388 if (Copy.getDesc().getNumOperands() != 2) 389 return false; 390 DefIdx = 0; 391 SrcIdx = 1; 392 assert(Copy.getOperand(DefIdx).isDef() && "Use comes before def!"); 393 return true; 394 } 395 // Bitcast case. 396 // Bitcasts with more than one def are not supported. 397 if (Copy.getDesc().getNumDefs() != 1) 398 return false; 399 // Initialize SrcIdx to an undefined operand. 400 SrcIdx = Copy.getDesc().getNumOperands(); 401 for (unsigned OpIdx = 0, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; ++OpIdx) { 402 const MachineOperand &MO = Copy.getOperand(OpIdx); 403 if (!MO.isReg() || !MO.getReg()) 404 continue; 405 if (MO.isDef()) 406 DefIdx = OpIdx; 407 else if (SrcIdx != EndOpIdx) 408 // Multiple sources? 409 return false; 410 SrcIdx = OpIdx; 411 } 412 return true; 413} 414 415/// \brief Optimize a copy or bitcast instruction to avoid cross 416/// register bank copy. The optimization looks through a chain of 417/// copies and try to find a source that has a compatible register 418/// class. 419/// Two register classes are considered to be compatible if they share 420/// the same register bank. 421/// New copies issued by this optimization are register allocator 422/// friendly. This optimization does not remove any copy as it may 423/// overconstraint the register allocator, but replaces some when 424/// possible. 425/// \pre \p MI is a Copy (MI->isCopy() is true) 426/// \return True, when \p MI has been optimized. In that case, \p MI has 427/// been removed from its parent. 428bool PeepholeOptimizer::optimizeCopyOrBitcast(MachineInstr *MI) { 429 unsigned DefIdx, SrcIdx; 430 if (!MI || !getCopyOrBitcastDefUseIdx(*MI, DefIdx, SrcIdx)) 431 return false; 432 433 const MachineOperand &MODef = MI->getOperand(DefIdx); 434 assert(MODef.isReg() && "Copies must be between registers."); 435 unsigned Def = MODef.getReg(); 436 437 if (TargetRegisterInfo::isPhysicalRegister(Def)) 438 return false; 439 440 const TargetRegisterClass *DefRC = MRI->getRegClass(Def); 441 unsigned DefSubReg = MODef.getSubReg(); 442 443 unsigned Src; 444 unsigned SrcSubReg; 445 bool ShouldRewrite = false; 446 MachineInstr *Copy = MI; 447 const TargetRegisterInfo &TRI = *TM->getRegisterInfo(); 448 449 // Follow the chain of copies until we reach the top or find a 450 // more suitable source. 451 do { 452 unsigned CopyDefIdx, CopySrcIdx; 453 if (!getCopyOrBitcastDefUseIdx(*Copy, CopyDefIdx, CopySrcIdx)) 454 break; 455 const MachineOperand &MO = Copy->getOperand(CopySrcIdx); 456 assert(MO.isReg() && "Copies must be between registers."); 457 Src = MO.getReg(); 458 459 if (TargetRegisterInfo::isPhysicalRegister(Src)) 460 break; 461 462 const TargetRegisterClass *SrcRC = MRI->getRegClass(Src); 463 SrcSubReg = MO.getSubReg(); 464 465 // If this source does not incur a cross register bank copy, use it. 466 ShouldRewrite = shareSameRegisterFile(TRI, DefRC, DefSubReg, SrcRC, 467 SrcSubReg); 468 // Follow the chain of copies: get the definition of Src. 469 Copy = MRI->getVRegDef(Src); 470 } while (!ShouldRewrite && Copy && (Copy->isCopy() || Copy->isBitcast())); 471 472 // If we did not find a more suitable source, there is nothing to optimize. 473 if (!ShouldRewrite || Src == MI->getOperand(SrcIdx).getReg()) 474 return false; 475 476 // Rewrite the copy to avoid a cross register bank penalty. 477 unsigned NewVR = TargetRegisterInfo::isPhysicalRegister(Def) ? Def : 478 MRI->createVirtualRegister(DefRC); 479 MachineInstr *NewCopy = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 480 TII->get(TargetOpcode::COPY), NewVR) 481 .addReg(Src, 0, SrcSubReg); 482 NewCopy->getOperand(0).setSubReg(DefSubReg); 483 484 MRI->replaceRegWith(Def, NewVR); 485 MRI->clearKillFlags(NewVR); 486 MI->eraseFromParent(); 487 ++NumCopiesBitcasts; 488 return true; 489} 490 491/// isLoadFoldable - Check whether MI is a candidate for folding into a later 492/// instruction. We only fold loads to virtual registers and the virtual 493/// register defined has a single use. 494bool PeepholeOptimizer::isLoadFoldable( 495 MachineInstr *MI, 496 SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) { 497 if (!MI->canFoldAsLoad() || !MI->mayLoad()) 498 return false; 499 const MCInstrDesc &MCID = MI->getDesc(); 500 if (MCID.getNumDefs() != 1) 501 return false; 502 503 unsigned Reg = MI->getOperand(0).getReg(); 504 // To reduce compilation time, we check MRI->hasOneNonDBGUse when inserting 505 // loads. It should be checked when processing uses of the load, since 506 // uses can be removed during peephole. 507 if (!MI->getOperand(0).getSubReg() && 508 TargetRegisterInfo::isVirtualRegister(Reg) && 509 MRI->hasOneNonDBGUse(Reg)) { 510 FoldAsLoadDefCandidates.insert(Reg); 511 return true; 512 } 513 return false; 514} 515 516bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI, 517 SmallSet<unsigned, 4> &ImmDefRegs, 518 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 519 const MCInstrDesc &MCID = MI->getDesc(); 520 if (!MI->isMoveImmediate()) 521 return false; 522 if (MCID.getNumDefs() != 1) 523 return false; 524 unsigned Reg = MI->getOperand(0).getReg(); 525 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 526 ImmDefMIs.insert(std::make_pair(Reg, MI)); 527 ImmDefRegs.insert(Reg); 528 return true; 529 } 530 531 return false; 532} 533 534/// foldImmediate - Try folding register operands that are defined by move 535/// immediate instructions, i.e. a trivial constant folding optimization, if 536/// and only if the def and use are in the same BB. 537bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 538 SmallSet<unsigned, 4> &ImmDefRegs, 539 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 540 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 541 MachineOperand &MO = MI->getOperand(i); 542 if (!MO.isReg() || MO.isDef()) 543 continue; 544 unsigned Reg = MO.getReg(); 545 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 546 continue; 547 if (ImmDefRegs.count(Reg) == 0) 548 continue; 549 DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg); 550 assert(II != ImmDefMIs.end()); 551 if (TII->FoldImmediate(MI, II->second, Reg, MRI)) { 552 ++NumImmFold; 553 return true; 554 } 555 } 556 return false; 557} 558 559bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { 560 if (skipOptnoneFunction(*MF.getFunction())) 561 return false; 562 563 DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n"); 564 DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n'); 565 566 if (DisablePeephole) 567 return false; 568 569 TM = &MF.getTarget(); 570 TII = TM->getInstrInfo(); 571 MRI = &MF.getRegInfo(); 572 DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : nullptr; 573 574 bool Changed = false; 575 576 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 577 MachineBasicBlock *MBB = &*I; 578 579 bool SeenMoveImm = false; 580 SmallPtrSet<MachineInstr*, 8> LocalMIs; 581 SmallSet<unsigned, 4> ImmDefRegs; 582 DenseMap<unsigned, MachineInstr*> ImmDefMIs; 583 SmallSet<unsigned, 16> FoldAsLoadDefCandidates; 584 585 for (MachineBasicBlock::iterator 586 MII = I->begin(), MIE = I->end(); MII != MIE; ) { 587 MachineInstr *MI = &*MII; 588 // We may be erasing MI below, increment MII now. 589 ++MII; 590 LocalMIs.insert(MI); 591 592 // Skip debug values. They should not affect this peephole optimization. 593 if (MI->isDebugValue()) 594 continue; 595 596 // If there exists an instruction which belongs to the following 597 // categories, we will discard the load candidates. 598 if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || 599 MI->isKill() || MI->isInlineAsm() || 600 MI->hasUnmodeledSideEffects()) { 601 FoldAsLoadDefCandidates.clear(); 602 continue; 603 } 604 if (MI->mayStore() || MI->isCall()) 605 FoldAsLoadDefCandidates.clear(); 606 607 if (((MI->isBitcast() || MI->isCopy()) && optimizeCopyOrBitcast(MI)) || 608 (MI->isCompare() && optimizeCmpInstr(MI, MBB)) || 609 (MI->isSelect() && optimizeSelect(MI))) { 610 // MI is deleted. 611 LocalMIs.erase(MI); 612 Changed = true; 613 continue; 614 } 615 616 if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) { 617 SeenMoveImm = true; 618 } else { 619 Changed |= optimizeExtInstr(MI, MBB, LocalMIs); 620 // optimizeExtInstr might have created new instructions after MI 621 // and before the already incremented MII. Adjust MII so that the 622 // next iteration sees the new instructions. 623 MII = MI; 624 ++MII; 625 if (SeenMoveImm) 626 Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs); 627 } 628 629 // Check whether MI is a load candidate for folding into a later 630 // instruction. If MI is not a candidate, check whether we can fold an 631 // earlier load into MI. 632 if (!isLoadFoldable(MI, FoldAsLoadDefCandidates) && 633 !FoldAsLoadDefCandidates.empty()) { 634 const MCInstrDesc &MIDesc = MI->getDesc(); 635 for (unsigned i = MIDesc.getNumDefs(); i != MIDesc.getNumOperands(); 636 ++i) { 637 const MachineOperand &MOp = MI->getOperand(i); 638 if (!MOp.isReg()) 639 continue; 640 unsigned FoldAsLoadDefReg = MOp.getReg(); 641 if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) { 642 // We need to fold load after optimizeCmpInstr, since 643 // optimizeCmpInstr can enable folding by converting SUB to CMP. 644 // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and 645 // we need it for markUsesInDebugValueAsUndef(). 646 unsigned FoldedReg = FoldAsLoadDefReg; 647 MachineInstr *DefMI = nullptr; 648 MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI, 649 FoldAsLoadDefReg, 650 DefMI); 651 if (FoldMI) { 652 // Update LocalMIs since we replaced MI with FoldMI and deleted 653 // DefMI. 654 DEBUG(dbgs() << "Replacing: " << *MI); 655 DEBUG(dbgs() << " With: " << *FoldMI); 656 LocalMIs.erase(MI); 657 LocalMIs.erase(DefMI); 658 LocalMIs.insert(FoldMI); 659 MI->eraseFromParent(); 660 DefMI->eraseFromParent(); 661 MRI->markUsesInDebugValueAsUndef(FoldedReg); 662 FoldAsLoadDefCandidates.erase(FoldedReg); 663 ++NumLoadFold; 664 // MI is replaced with FoldMI. 665 Changed = true; 666 break; 667 } 668 } 669 } 670 } 671 } 672 } 673 674 return Changed; 675} 676