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