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