PeepholeOptimizer.cpp revision eb96a2f6c03c0ec97c56a3493ac38024afacc774
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//===----------------------------------------------------------------------===// 35 36#define DEBUG_TYPE "peephole-opt" 37#include "llvm/CodeGen/Passes.h" 38#include "llvm/CodeGen/MachineDominators.h" 39#include "llvm/CodeGen/MachineInstrBuilder.h" 40#include "llvm/CodeGen/MachineRegisterInfo.h" 41#include "llvm/Target/TargetInstrInfo.h" 42#include "llvm/Target/TargetRegisterInfo.h" 43#include "llvm/Support/CommandLine.h" 44#include "llvm/ADT/SmallPtrSet.h" 45#include "llvm/ADT/Statistic.h" 46using namespace llvm; 47 48// Optimize Extensions 49static cl::opt<bool> 50Aggressive("aggressive-ext-opt", cl::Hidden, 51 cl::desc("Aggressive extension optimization")); 52 53static cl::opt<bool> 54DisablePeephole("disable-peephole", cl::Hidden, cl::init(false), 55 cl::desc("Disable the peephole optimizer")); 56 57STATISTIC(NumReuse, "Number of extension results reused"); 58STATISTIC(NumEliminated, "Number of compares eliminated"); 59 60namespace { 61 class PeepholeOptimizer : public MachineFunctionPass { 62 const TargetMachine *TM; 63 const TargetInstrInfo *TII; 64 MachineRegisterInfo *MRI; 65 MachineDominatorTree *DT; // Machine dominator tree 66 67 public: 68 static char ID; // Pass identification 69 PeepholeOptimizer() : MachineFunctionPass(ID) { 70 initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); 71 } 72 73 virtual bool runOnMachineFunction(MachineFunction &MF); 74 75 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 76 AU.setPreservesCFG(); 77 MachineFunctionPass::getAnalysisUsage(AU); 78 if (Aggressive) { 79 AU.addRequired<MachineDominatorTree>(); 80 AU.addPreserved<MachineDominatorTree>(); 81 } 82 } 83 84 private: 85 bool OptimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); 86 bool OptimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 87 SmallPtrSet<MachineInstr*, 8> &LocalMIs); 88 }; 89} 90 91char PeepholeOptimizer::ID = 0; 92INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts", 93 "Peephole Optimizations", false, false) 94INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 95INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts", 96 "Peephole Optimizations", false, false) 97 98FunctionPass *llvm::createPeepholeOptimizerPass() { 99 return new PeepholeOptimizer(); 100} 101 102/// OptimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads 103/// a single register and writes a single register and it does not modify the 104/// source, and if the source value is preserved as a sub-register of the 105/// result, then replace all reachable uses of the source with the subreg of the 106/// result. 107/// 108/// Do not generate an EXTRACT that is used only in a debug use, as this changes 109/// the code. Since this code does not currently share EXTRACTs, just ignore all 110/// debug uses. 111bool PeepholeOptimizer:: 112OptimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 113 SmallPtrSet<MachineInstr*, 8> &LocalMIs) { 114 unsigned SrcReg, DstReg, SubIdx; 115 if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx)) 116 return false; 117 118 if (TargetRegisterInfo::isPhysicalRegister(DstReg) || 119 TargetRegisterInfo::isPhysicalRegister(SrcReg)) 120 return false; 121 122 MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(SrcReg); 123 if (++UI == MRI->use_nodbg_end()) 124 // No other uses. 125 return false; 126 127 // The source has other uses. See if we can replace the other uses with use of 128 // the result of the extension. 129 SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; 130 UI = MRI->use_nodbg_begin(DstReg); 131 for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end(); 132 UI != UE; ++UI) 133 ReachedBBs.insert(UI->getParent()); 134 135 // Uses that are in the same BB of uses of the result of the instruction. 136 SmallVector<MachineOperand*, 8> Uses; 137 138 // Uses that the result of the instruction can reach. 139 SmallVector<MachineOperand*, 8> ExtendedUses; 140 141 bool ExtendLife = true; 142 UI = MRI->use_nodbg_begin(SrcReg); 143 for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end(); 144 UI != UE; ++UI) { 145 MachineOperand &UseMO = UI.getOperand(); 146 MachineInstr *UseMI = &*UI; 147 if (UseMI == MI) 148 continue; 149 150 if (UseMI->isPHI()) { 151 ExtendLife = false; 152 continue; 153 } 154 155 // It's an error to translate this: 156 // 157 // %reg1025 = <sext> %reg1024 158 // ... 159 // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 160 // 161 // into this: 162 // 163 // %reg1025 = <sext> %reg1024 164 // ... 165 // %reg1027 = COPY %reg1025:4 166 // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 167 // 168 // The problem here is that SUBREG_TO_REG is there to assert that an 169 // implicit zext occurs. It doesn't insert a zext instruction. If we allow 170 // the COPY here, it will give us the value after the <sext>, not the 171 // original value of %reg1024 before <sext>. 172 if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) 173 continue; 174 175 MachineBasicBlock *UseMBB = UseMI->getParent(); 176 if (UseMBB == MBB) { 177 // Local uses that come after the extension. 178 if (!LocalMIs.count(UseMI)) 179 Uses.push_back(&UseMO); 180 } else if (ReachedBBs.count(UseMBB)) { 181 // Non-local uses where the result of the extension is used. Always 182 // replace these unless it's a PHI. 183 Uses.push_back(&UseMO); 184 } else if (Aggressive && DT->dominates(MBB, UseMBB)) { 185 // We may want to extend the live range of the extension result in order 186 // to replace these uses. 187 ExtendedUses.push_back(&UseMO); 188 } else { 189 // Both will be live out of the def MBB anyway. Don't extend live range of 190 // the extension result. 191 ExtendLife = false; 192 break; 193 } 194 } 195 196 if (ExtendLife && !ExtendedUses.empty()) 197 // Extend the liveness of the extension result. 198 std::copy(ExtendedUses.begin(), ExtendedUses.end(), 199 std::back_inserter(Uses)); 200 201 // Now replace all uses. 202 bool Changed = false; 203 if (!Uses.empty()) { 204 SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; 205 206 // Look for PHI uses of the extended result, we don't want to extend the 207 // liveness of a PHI input. It breaks all kinds of assumptions down 208 // stream. A PHI use is expected to be the kill of its source values. 209 UI = MRI->use_nodbg_begin(DstReg); 210 for (MachineRegisterInfo::use_nodbg_iterator 211 UE = MRI->use_nodbg_end(); UI != UE; ++UI) 212 if (UI->isPHI()) 213 PHIBBs.insert(UI->getParent()); 214 215 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 216 for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 217 MachineOperand *UseMO = Uses[i]; 218 MachineInstr *UseMI = UseMO->getParent(); 219 MachineBasicBlock *UseMBB = UseMI->getParent(); 220 if (PHIBBs.count(UseMBB)) 221 continue; 222 223 unsigned NewVR = MRI->createVirtualRegister(RC); 224 BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), 225 TII->get(TargetOpcode::COPY), NewVR) 226 .addReg(DstReg, 0, SubIdx); 227 228 UseMO->setReg(NewVR); 229 ++NumReuse; 230 Changed = true; 231 } 232 } 233 234 return Changed; 235} 236 237/// OptimizeCmpInstr - If the instruction is a compare and the previous 238/// instruction it's comparing against all ready sets (or could be modified to 239/// set) the same flag as the compare, then we can remove the comparison and use 240/// the flag from the previous instruction. 241bool PeepholeOptimizer::OptimizeCmpInstr(MachineInstr *MI, 242 MachineBasicBlock *MBB){ 243 // If this instruction is a comparison against zero and isn't comparing a 244 // physical register, we can try to optimize it. 245 unsigned SrcReg; 246 int CmpMask, CmpValue; 247 if (!TII->AnalyzeCompare(MI, SrcReg, CmpMask, CmpValue) || 248 TargetRegisterInfo::isPhysicalRegister(SrcReg)) 249 return false; 250 251 // Attempt to optimize the comparison instruction. 252 if (TII->OptimizeCompareInstr(MI, SrcReg, CmpMask, CmpValue, MRI)) { 253 ++NumEliminated; 254 return true; 255 } 256 257 return false; 258} 259 260bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { 261 if (DisablePeephole) 262 return false; 263 264 TM = &MF.getTarget(); 265 TII = TM->getInstrInfo(); 266 MRI = &MF.getRegInfo(); 267 DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0; 268 269 bool Changed = false; 270 271 SmallPtrSet<MachineInstr*, 8> LocalMIs; 272 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 273 MachineBasicBlock *MBB = &*I; 274 LocalMIs.clear(); 275 276 for (MachineBasicBlock::iterator 277 MII = I->begin(), MIE = I->end(); MII != MIE; ) { 278 MachineInstr *MI = &*MII++; 279 LocalMIs.insert(MI); 280 281 if (MI->getDesc().hasUnmodeledSideEffects()) 282 continue; 283 284 if (MI->getDesc().isCompare()) { 285 Changed |= OptimizeCmpInstr(MI, MBB); 286 } else { 287 Changed |= OptimizeExtInstr(MI, MBB, LocalMIs); 288 } 289 } 290 } 291 292 return Changed; 293} 294