PeepholeOptimizer.cpp revision 04ac81d5db058a3a9492e1aff1f398a8643bfda9 
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