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