PeepholeOptimizer.cpp revision 0eb3edea9cb6819334173a7d288da85943201fe5
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 Bitcast pairs: 44// 45// v1 = bitcast v0 46// v2 = bitcast v1 47// = v2 48// => 49// v1 = bitcast v0 50// = v0 51// 52//===----------------------------------------------------------------------===// 53 54#define DEBUG_TYPE "peephole-opt" 55#include "llvm/CodeGen/Passes.h" 56#include "llvm/CodeGen/MachineDominators.h" 57#include "llvm/CodeGen/MachineInstrBuilder.h" 58#include "llvm/CodeGen/MachineRegisterInfo.h" 59#include "llvm/Target/TargetInstrInfo.h" 60#include "llvm/Target/TargetRegisterInfo.h" 61#include "llvm/Support/CommandLine.h" 62#include "llvm/ADT/DenseMap.h" 63#include "llvm/ADT/SmallPtrSet.h" 64#include "llvm/ADT/SmallSet.h" 65#include "llvm/ADT/Statistic.h" 66using namespace llvm; 67 68// Optimize Extensions 69static cl::opt<bool> 70Aggressive("aggressive-ext-opt", cl::Hidden, 71 cl::desc("Aggressive extension optimization")); 72 73static cl::opt<bool> 74DisablePeephole("disable-peephole", cl::Hidden, cl::init(false), 75 cl::desc("Disable the peephole optimizer")); 76 77STATISTIC(NumReuse, "Number of extension results reused"); 78STATISTIC(NumBitcasts, "Number of bitcasts eliminated"); 79STATISTIC(NumCmps, "Number of compares eliminated"); 80STATISTIC(NumImmFold, "Number of move immediate folded"); 81STATISTIC(NumLoadFold, "Number of loads folded"); 82 83namespace { 84 class PeepholeOptimizer : public MachineFunctionPass { 85 const TargetMachine *TM; 86 const TargetInstrInfo *TII; 87 MachineRegisterInfo *MRI; 88 MachineDominatorTree *DT; // Machine dominator tree 89 90 public: 91 static char ID; // Pass identification 92 PeepholeOptimizer() : MachineFunctionPass(ID) { 93 initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); 94 } 95 96 virtual bool runOnMachineFunction(MachineFunction &MF); 97 98 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 99 AU.setPreservesCFG(); 100 MachineFunctionPass::getAnalysisUsage(AU); 101 if (Aggressive) { 102 AU.addRequired<MachineDominatorTree>(); 103 AU.addPreserved<MachineDominatorTree>(); 104 } 105 } 106 107 private: 108 bool optimizeBitcastInstr(MachineInstr *MI, MachineBasicBlock *MBB); 109 bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); 110 bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 111 SmallPtrSet<MachineInstr*, 8> &LocalMIs); 112 bool isMoveImmediate(MachineInstr *MI, 113 SmallSet<unsigned, 4> &ImmDefRegs, 114 DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 115 bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 116 SmallSet<unsigned, 4> &ImmDefRegs, 117 DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 118 }; 119} 120 121char PeepholeOptimizer::ID = 0; 122char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; 123INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts", 124 "Peephole Optimizations", false, false) 125INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 126INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts", 127 "Peephole Optimizations", false, false) 128 129/// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads 130/// a single register and writes a single register and it does not modify the 131/// source, and if the source value is preserved as a sub-register of the 132/// result, then replace all reachable uses of the source with the subreg of the 133/// result. 134/// 135/// Do not generate an EXTRACT that is used only in a debug use, as this changes 136/// the code. Since this code does not currently share EXTRACTs, just ignore all 137/// debug uses. 138bool PeepholeOptimizer:: 139optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 140 SmallPtrSet<MachineInstr*, 8> &LocalMIs) { 141 unsigned SrcReg, DstReg, SubIdx; 142 if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx)) 143 return false; 144 145 if (TargetRegisterInfo::isPhysicalRegister(DstReg) || 146 TargetRegisterInfo::isPhysicalRegister(SrcReg)) 147 return false; 148 149 if (MRI->hasOneNonDBGUse(SrcReg)) 150 // No other uses. 151 return false; 152 153 // Ensure DstReg can get a register class that actually supports 154 // sub-registers. Don't change the class until we commit. 155 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 156 DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx); 157 if (!DstRC) 158 return false; 159 160 // The ext instr may be operating on a sub-register of SrcReg as well. 161 // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit 162 // register. 163 // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of 164 // SrcReg:SubIdx should be replaced. 165 bool UseSrcSubIdx = TM->getRegisterInfo()-> 166 getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != 0; 167 168 // The source has other uses. See if we can replace the other uses with use of 169 // the result of the extension. 170 SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; 171 for (MachineRegisterInfo::use_nodbg_iterator 172 UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end(); 173 UI != UE; ++UI) 174 ReachedBBs.insert(UI->getParent()); 175 176 // Uses that are in the same BB of uses of the result of the instruction. 177 SmallVector<MachineOperand*, 8> Uses; 178 179 // Uses that the result of the instruction can reach. 180 SmallVector<MachineOperand*, 8> ExtendedUses; 181 182 bool ExtendLife = true; 183 for (MachineRegisterInfo::use_nodbg_iterator 184 UI = MRI->use_nodbg_begin(SrcReg), UE = MRI->use_nodbg_end(); 185 UI != UE; ++UI) { 186 MachineOperand &UseMO = UI.getOperand(); 187 MachineInstr *UseMI = &*UI; 188 if (UseMI == MI) 189 continue; 190 191 if (UseMI->isPHI()) { 192 ExtendLife = false; 193 continue; 194 } 195 196 // Only accept uses of SrcReg:SubIdx. 197 if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx) 198 continue; 199 200 // It's an error to translate this: 201 // 202 // %reg1025 = <sext> %reg1024 203 // ... 204 // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 205 // 206 // into this: 207 // 208 // %reg1025 = <sext> %reg1024 209 // ... 210 // %reg1027 = COPY %reg1025:4 211 // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 212 // 213 // The problem here is that SUBREG_TO_REG is there to assert that an 214 // implicit zext occurs. It doesn't insert a zext instruction. If we allow 215 // the COPY here, it will give us the value after the <sext>, not the 216 // original value of %reg1024 before <sext>. 217 if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) 218 continue; 219 220 MachineBasicBlock *UseMBB = UseMI->getParent(); 221 if (UseMBB == MBB) { 222 // Local uses that come after the extension. 223 if (!LocalMIs.count(UseMI)) 224 Uses.push_back(&UseMO); 225 } else if (ReachedBBs.count(UseMBB)) { 226 // Non-local uses where the result of the extension is used. Always 227 // replace these unless it's a PHI. 228 Uses.push_back(&UseMO); 229 } else if (Aggressive && DT->dominates(MBB, UseMBB)) { 230 // We may want to extend the live range of the extension result in order 231 // to replace these uses. 232 ExtendedUses.push_back(&UseMO); 233 } else { 234 // Both will be live out of the def MBB anyway. Don't extend live range of 235 // the extension result. 236 ExtendLife = false; 237 break; 238 } 239 } 240 241 if (ExtendLife && !ExtendedUses.empty()) 242 // Extend the liveness of the extension result. 243 std::copy(ExtendedUses.begin(), ExtendedUses.end(), 244 std::back_inserter(Uses)); 245 246 // Now replace all uses. 247 bool Changed = false; 248 if (!Uses.empty()) { 249 SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; 250 251 // Look for PHI uses of the extended result, we don't want to extend the 252 // liveness of a PHI input. It breaks all kinds of assumptions down 253 // stream. A PHI use is expected to be the kill of its source values. 254 for (MachineRegisterInfo::use_nodbg_iterator 255 UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end(); 256 UI != UE; ++UI) 257 if (UI->isPHI()) 258 PHIBBs.insert(UI->getParent()); 259 260 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 261 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 262 MachineOperand *UseMO = Uses[i]; 263 MachineInstr *UseMI = UseMO->getParent(); 264 MachineBasicBlock *UseMBB = UseMI->getParent(); 265 if (PHIBBs.count(UseMBB)) 266 continue; 267 268 // About to add uses of DstReg, clear DstReg's kill flags. 269 if (!Changed) { 270 MRI->clearKillFlags(DstReg); 271 MRI->constrainRegClass(DstReg, DstRC); 272 } 273 274 unsigned NewVR = MRI->createVirtualRegister(RC); 275 MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), 276 TII->get(TargetOpcode::COPY), NewVR) 277 .addReg(DstReg, 0, SubIdx); 278 // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set. 279 if (UseSrcSubIdx) { 280 Copy->getOperand(0).setSubReg(SubIdx); 281 Copy->getOperand(0).setIsUndef(); 282 } 283 UseMO->setReg(NewVR); 284 ++NumReuse; 285 Changed = true; 286 } 287 } 288 289 return Changed; 290} 291 292/// optimizeBitcastInstr - If the instruction is a bitcast instruction A that 293/// cannot be optimized away during isel (e.g. ARM::VMOVSR, which bitcast 294/// a value cross register classes), and the source is defined by another 295/// bitcast instruction B. And if the register class of source of B matches 296/// the register class of instruction A, then it is legal to replace all uses 297/// of the def of A with source of B. e.g. 298/// %vreg0<def> = VMOVSR %vreg1 299/// %vreg3<def> = VMOVRS %vreg0 300/// Replace all uses of vreg3 with vreg1. 301 302bool PeepholeOptimizer::optimizeBitcastInstr(MachineInstr *MI, 303 MachineBasicBlock *MBB) { 304 unsigned NumDefs = MI->getDesc().getNumDefs(); 305 unsigned NumSrcs = MI->getDesc().getNumOperands() - NumDefs; 306 if (NumDefs != 1) 307 return false; 308 309 unsigned Def = 0; 310 unsigned Src = 0; 311 for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) { 312 const MachineOperand &MO = MI->getOperand(i); 313 if (!MO.isReg()) 314 continue; 315 unsigned Reg = MO.getReg(); 316 if (!Reg) 317 continue; 318 if (MO.isDef()) 319 Def = Reg; 320 else if (Src) 321 // Multiple sources? 322 return false; 323 else 324 Src = Reg; 325 } 326 327 assert(Def && Src && "Malformed bitcast instruction!"); 328 329 MachineInstr *DefMI = MRI->getVRegDef(Src); 330 if (!DefMI || !DefMI->isBitcast()) 331 return false; 332 333 unsigned SrcSrc = 0; 334 NumDefs = DefMI->getDesc().getNumDefs(); 335 NumSrcs = DefMI->getDesc().getNumOperands() - NumDefs; 336 if (NumDefs != 1) 337 return false; 338 for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) { 339 const MachineOperand &MO = DefMI->getOperand(i); 340 if (!MO.isReg() || MO.isDef()) 341 continue; 342 unsigned Reg = MO.getReg(); 343 if (!Reg) 344 continue; 345 if (!MO.isDef()) { 346 if (SrcSrc) 347 // Multiple sources? 348 return false; 349 else 350 SrcSrc = Reg; 351 } 352 } 353 354 if (MRI->getRegClass(SrcSrc) != MRI->getRegClass(Def)) 355 return false; 356 357 MRI->replaceRegWith(Def, SrcSrc); 358 MRI->clearKillFlags(SrcSrc); 359 MI->eraseFromParent(); 360 ++NumBitcasts; 361 return true; 362} 363 364/// optimizeCmpInstr - If the instruction is a compare and the previous 365/// instruction it's comparing against all ready sets (or could be modified to 366/// set) the same flag as the compare, then we can remove the comparison and use 367/// the flag from the previous instruction. 368bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI, 369 MachineBasicBlock *MBB) { 370 // If this instruction is a comparison against zero and isn't comparing a 371 // physical register, we can try to optimize it. 372 unsigned SrcReg, SrcReg2; 373 int CmpMask, CmpValue; 374 if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || 375 TargetRegisterInfo::isPhysicalRegister(SrcReg) || 376 (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2))) 377 return false; 378 379 // Attempt to optimize the comparison instruction. 380 if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { 381 ++NumCmps; 382 return true; 383 } 384 385 return false; 386} 387 388bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI, 389 SmallSet<unsigned, 4> &ImmDefRegs, 390 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 391 const MCInstrDesc &MCID = MI->getDesc(); 392 if (!MI->isMoveImmediate()) 393 return false; 394 if (MCID.getNumDefs() != 1) 395 return false; 396 unsigned Reg = MI->getOperand(0).getReg(); 397 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 398 ImmDefMIs.insert(std::make_pair(Reg, MI)); 399 ImmDefRegs.insert(Reg); 400 return true; 401 } 402 403 return false; 404} 405 406/// foldImmediate - Try folding register operands that are defined by move 407/// immediate instructions, i.e. a trivial constant folding optimization, if 408/// and only if the def and use are in the same BB. 409bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 410 SmallSet<unsigned, 4> &ImmDefRegs, 411 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 412 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 413 MachineOperand &MO = MI->getOperand(i); 414 if (!MO.isReg() || MO.isDef()) 415 continue; 416 unsigned Reg = MO.getReg(); 417 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 418 continue; 419 if (ImmDefRegs.count(Reg) == 0) 420 continue; 421 DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg); 422 assert(II != ImmDefMIs.end()); 423 if (TII->FoldImmediate(MI, II->second, Reg, MRI)) { 424 ++NumImmFold; 425 return true; 426 } 427 } 428 return false; 429} 430 431bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { 432 if (DisablePeephole) 433 return false; 434 435 TM = &MF.getTarget(); 436 TII = TM->getInstrInfo(); 437 MRI = &MF.getRegInfo(); 438 DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0; 439 440 bool Changed = false; 441 442 SmallPtrSet<MachineInstr*, 8> LocalMIs; 443 SmallSet<unsigned, 4> ImmDefRegs; 444 DenseMap<unsigned, MachineInstr*> ImmDefMIs; 445 SmallSet<unsigned, 4> FoldAsLoadDefRegs; 446 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 447 MachineBasicBlock *MBB = &*I; 448 449 bool SeenMoveImm = false; 450 LocalMIs.clear(); 451 ImmDefRegs.clear(); 452 ImmDefMIs.clear(); 453 FoldAsLoadDefRegs.clear(); 454 455 bool First = true; 456 MachineBasicBlock::iterator PMII; 457 for (MachineBasicBlock::iterator 458 MII = I->begin(), MIE = I->end(); MII != MIE; ) { 459 MachineInstr *MI = &*MII; 460 LocalMIs.insert(MI); 461 462 if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 463 MI->isKill() || MI->isInlineAsm() || MI->isDebugValue() || 464 MI->hasUnmodeledSideEffects()) { 465 ++MII; 466 continue; 467 } 468 469 if (MI->isBitcast()) { 470 if (optimizeBitcastInstr(MI, MBB)) { 471 // MI is deleted. 472 LocalMIs.erase(MI); 473 Changed = true; 474 MII = First ? I->begin() : llvm::next(PMII); 475 continue; 476 } 477 } else if (MI->isCompare()) { 478 if (optimizeCmpInstr(MI, MBB)) { 479 // MI is deleted. 480 LocalMIs.erase(MI); 481 Changed = true; 482 MII = First ? I->begin() : llvm::next(PMII); 483 continue; 484 } 485 } 486 487 if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) { 488 SeenMoveImm = true; 489 } else { 490 Changed |= optimizeExtInstr(MI, MBB, LocalMIs); 491 if (SeenMoveImm) 492 Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs); 493 } 494 495 MachineInstr *DefMI = 0; 496 MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI, FoldAsLoadDefRegs, 497 DefMI); 498 if (FoldMI) { 499 // Update LocalMIs since we replaced MI with FoldMI and deleted DefMI. 500 LocalMIs.erase(MI); 501 LocalMIs.erase(DefMI); 502 LocalMIs.insert(FoldMI); 503 MI->eraseFromParent(); 504 DefMI->eraseFromParent(); 505 ++NumLoadFold; 506 507 // MI is replaced with FoldMI. 508 Changed = true; 509 PMII = FoldMI; 510 MII = llvm::next(PMII); 511 continue; 512 } 513 514 First = false; 515 PMII = MII; 516 ++MII; 517 } 518 } 519 520 return Changed; 521} 522