PeepholeOptimizer.cpp revision 418a3638acfa95e4212a38100adfc2f8cdd45919 
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//     Another instance, in this code:
35//
36//       sub r1, r3 | sub r1, imm
37//       cmp r3, r1 or cmp r1, r3 | cmp r1, imm
38//       bge L1
39//
40//     If the branch instruction can use flag from "sub", then we can replace
41//     "sub" with "subs" and eliminate the "cmp" instruction.
42//
43// - Optimize Bitcast pairs:
44//
45//     v1 = bitcast v0
46//     v2 = bitcast v1
47//        = v2
48//   =>
49//     v1 = bitcast v0
50//        = v0
51//
52//===----------------------------------------------------------------------===//
53
54#define DEBUG_TYPE "peephole-opt"
55#include "llvm/CodeGen/Passes.h"
56#include "llvm/CodeGen/MachineDominators.h"
57#include "llvm/CodeGen/MachineInstrBuilder.h"
58#include "llvm/CodeGen/MachineRegisterInfo.h"
59#include "llvm/Target/TargetInstrInfo.h"
60#include "llvm/Target/TargetRegisterInfo.h"
61#include "llvm/Support/CommandLine.h"
62#include "llvm/ADT/DenseMap.h"
63#include "llvm/ADT/SmallPtrSet.h"
64#include "llvm/ADT/SmallSet.h"
65#include "llvm/ADT/Statistic.h"
66using namespace llvm;
67
68// Optimize Extensions
69static cl::opt<bool>
70Aggressive("aggressive-ext-opt", cl::Hidden,
71           cl::desc("Aggressive extension optimization"));
72
73static cl::opt<bool>
74DisablePeephole("disable-peephole", cl::Hidden, cl::init(false),
75                cl::desc("Disable the peephole optimizer"));
76
77STATISTIC(NumReuse,      "Number of extension results reused");
78STATISTIC(NumBitcasts,   "Number of bitcasts eliminated");
79STATISTIC(NumCmps,       "Number of compares eliminated");
80STATISTIC(NumImmFold,    "Number of move immediate folded");
81
82namespace {
83  class PeepholeOptimizer : public MachineFunctionPass {
84    const TargetMachine   *TM;
85    const TargetInstrInfo *TII;
86    MachineRegisterInfo   *MRI;
87    MachineDominatorTree  *DT;  // Machine dominator tree
88
89  public:
90    static char ID; // Pass identification
91    PeepholeOptimizer() : MachineFunctionPass(ID) {
92      initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
93    }
94
95    virtual bool runOnMachineFunction(MachineFunction &MF);
96
97    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
98      AU.setPreservesCFG();
99      MachineFunctionPass::getAnalysisUsage(AU);
100      if (Aggressive) {
101        AU.addRequired<MachineDominatorTree>();
102        AU.addPreserved<MachineDominatorTree>();
103      }
104    }
105
106  private:
107    bool optimizeBitcastInstr(MachineInstr *MI, MachineBasicBlock *MBB);
108    bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB);
109    bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
110                          SmallPtrSet<MachineInstr*, 8> &LocalMIs);
111    bool isMoveImmediate(MachineInstr *MI,
112                         SmallSet<unsigned, 4> &ImmDefRegs,
113                         DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
114    bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
115                       SmallSet<unsigned, 4> &ImmDefRegs,
116                       DenseMap<unsigned, MachineInstr*> &ImmDefMIs);
117  };
118}
119
120char PeepholeOptimizer::ID = 0;
121char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID;
122INITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts",
123                "Peephole Optimizations", false, false)
124INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
125INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts",
126                "Peephole Optimizations", false, false)
127
128/// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads
129/// a single register and writes a single register and it does not modify the
130/// source, and if the source value is preserved as a sub-register of the
131/// result, then replace all reachable uses of the source with the subreg of the
132/// result.
133///
134/// Do not generate an EXTRACT that is used only in a debug use, as this changes
135/// the code. Since this code does not currently share EXTRACTs, just ignore all
136/// debug uses.
137bool PeepholeOptimizer::
138optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB,
139                 SmallPtrSet<MachineInstr*, 8> &LocalMIs) {
140  unsigned SrcReg, DstReg, SubIdx;
141  if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx))
142    return false;
143
144  if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
145      TargetRegisterInfo::isPhysicalRegister(SrcReg))
146    return false;
147
148  MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(SrcReg);
149  if (++UI == MRI->use_nodbg_end())
150    // No other uses.
151    return false;
152
153  // Ensure DstReg can get a register class that actually supports
154  // sub-registers. Don't change the class until we commit.
155  const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
156  DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx);
157  if (!DstRC)
158    return false;
159
160  // The source has other uses. See if we can replace the other uses with use of
161  // the result of the extension.
162  SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
163  UI = MRI->use_nodbg_begin(DstReg);
164  for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
165       UI != UE; ++UI)
166    ReachedBBs.insert(UI->getParent());
167
168  // Uses that are in the same BB of uses of the result of the instruction.
169  SmallVector<MachineOperand*, 8> Uses;
170
171  // Uses that the result of the instruction can reach.
172  SmallVector<MachineOperand*, 8> ExtendedUses;
173
174  bool ExtendLife = true;
175  UI = MRI->use_nodbg_begin(SrcReg);
176  for (MachineRegisterInfo::use_nodbg_iterator UE = MRI->use_nodbg_end();
177       UI != UE; ++UI) {
178    MachineOperand &UseMO = UI.getOperand();
179    MachineInstr *UseMI = &*UI;
180    if (UseMI == MI)
181      continue;
182
183    if (UseMI->isPHI()) {
184      ExtendLife = false;
185      continue;
186    }
187
188    // It's an error to translate this:
189    //
190    //    %reg1025 = <sext> %reg1024
191    //     ...
192    //    %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
193    //
194    // into this:
195    //
196    //    %reg1025 = <sext> %reg1024
197    //     ...
198    //    %reg1027 = COPY %reg1025:4
199    //    %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
200    //
201    // The problem here is that SUBREG_TO_REG is there to assert that an
202    // implicit zext occurs. It doesn't insert a zext instruction. If we allow
203    // the COPY here, it will give us the value after the <sext>, not the
204    // original value of %reg1024 before <sext>.
205    if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
206      continue;
207
208    MachineBasicBlock *UseMBB = UseMI->getParent();
209    if (UseMBB == MBB) {
210      // Local uses that come after the extension.
211      if (!LocalMIs.count(UseMI))
212        Uses.push_back(&UseMO);
213    } else if (ReachedBBs.count(UseMBB)) {
214      // Non-local uses where the result of the extension is used. Always
215      // replace these unless it's a PHI.
216      Uses.push_back(&UseMO);
217    } else if (Aggressive && DT->dominates(MBB, UseMBB)) {
218      // We may want to extend the live range of the extension result in order
219      // to replace these uses.
220      ExtendedUses.push_back(&UseMO);
221    } else {
222      // Both will be live out of the def MBB anyway. Don't extend live range of
223      // the extension result.
224      ExtendLife = false;
225      break;
226    }
227  }
228
229  if (ExtendLife && !ExtendedUses.empty())
230    // Extend the liveness of the extension result.
231    std::copy(ExtendedUses.begin(), ExtendedUses.end(),
232              std::back_inserter(Uses));
233
234  // Now replace all uses.
235  bool Changed = false;
236  if (!Uses.empty()) {
237    SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
238
239    // Look for PHI uses of the extended result, we don't want to extend the
240    // liveness of a PHI input. It breaks all kinds of assumptions down
241    // stream. A PHI use is expected to be the kill of its source values.
242    UI = MRI->use_nodbg_begin(DstReg);
243    for (MachineRegisterInfo::use_nodbg_iterator
244           UE = MRI->use_nodbg_end(); UI != UE; ++UI)
245      if (UI->isPHI())
246        PHIBBs.insert(UI->getParent());
247
248    const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
249    for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
250      MachineOperand *UseMO = Uses[i];
251      MachineInstr *UseMI = UseMO->getParent();
252      MachineBasicBlock *UseMBB = UseMI->getParent();
253      if (PHIBBs.count(UseMBB))
254        continue;
255
256      // About to add uses of DstReg, clear DstReg's kill flags.
257      if (!Changed) {
258        MRI->clearKillFlags(DstReg);
259        MRI->constrainRegClass(DstReg, DstRC);
260      }
261
262      unsigned NewVR = MRI->createVirtualRegister(RC);
263      BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
264              TII->get(TargetOpcode::COPY), NewVR)
265        .addReg(DstReg, 0, SubIdx);
266
267      UseMO->setReg(NewVR);
268      ++NumReuse;
269      Changed = true;
270    }
271  }
272
273  return Changed;
274}
275
276/// optimizeBitcastInstr - If the instruction is a bitcast instruction A that
277/// cannot be optimized away during isel (e.g. ARM::VMOVSR, which bitcast
278/// a value cross register classes), and the source is defined by another
279/// bitcast instruction B. And if the register class of source of B matches
280/// the register class of instruction A, then it is legal to replace all uses
281/// of the def of A with source of B. e.g.
282///   %vreg0<def> = VMOVSR %vreg1
283///   %vreg3<def> = VMOVRS %vreg0
284///   Replace all uses of vreg3 with vreg1.
285
286bool PeepholeOptimizer::optimizeBitcastInstr(MachineInstr *MI,
287                                             MachineBasicBlock *MBB) {
288  unsigned NumDefs = MI->getDesc().getNumDefs();
289  unsigned NumSrcs = MI->getDesc().getNumOperands() - NumDefs;
290  if (NumDefs != 1)
291    return false;
292
293  unsigned Def = 0;
294  unsigned Src = 0;
295  for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
296    const MachineOperand &MO = MI->getOperand(i);
297    if (!MO.isReg())
298      continue;
299    unsigned Reg = MO.getReg();
300    if (!Reg)
301      continue;
302    if (MO.isDef())
303      Def = Reg;
304    else if (Src)
305      // Multiple sources?
306      return false;
307    else
308      Src = Reg;
309  }
310
311  assert(Def && Src && "Malformed bitcast instruction!");
312
313  MachineInstr *DefMI = MRI->getVRegDef(Src);
314  if (!DefMI || !DefMI->isBitcast())
315    return false;
316
317  unsigned SrcSrc = 0;
318  NumDefs = DefMI->getDesc().getNumDefs();
319  NumSrcs = DefMI->getDesc().getNumOperands() - NumDefs;
320  if (NumDefs != 1)
321    return false;
322  for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
323    const MachineOperand &MO = DefMI->getOperand(i);
324    if (!MO.isReg() || MO.isDef())
325      continue;
326    unsigned Reg = MO.getReg();
327    if (!Reg)
328      continue;
329    if (!MO.isDef()) {
330      if (SrcSrc)
331        // Multiple sources?
332        return false;
333      else
334        SrcSrc = Reg;
335    }
336  }
337
338  if (MRI->getRegClass(SrcSrc) != MRI->getRegClass(Def))
339    return false;
340
341  MRI->replaceRegWith(Def, SrcSrc);
342  MRI->clearKillFlags(SrcSrc);
343  MI->eraseFromParent();
344  ++NumBitcasts;
345  return true;
346}
347
348/// optimizeCmpInstr - If the instruction is a compare and the previous
349/// instruction it's comparing against all ready sets (or could be modified to
350/// set) the same flag as the compare, then we can remove the comparison and use
351/// the flag from the previous instruction.
352bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI,
353                                         MachineBasicBlock *MBB) {
354  // If this instruction is a comparison against zero and isn't comparing a
355  // physical register, we can try to optimize it.
356  unsigned SrcReg;
357  int CmpMask, CmpValue;
358  if (!TII->AnalyzeCompare(MI, SrcReg, CmpMask, CmpValue) ||
359      TargetRegisterInfo::isPhysicalRegister(SrcReg))
360    return false;
361
362  // Attempt to optimize the comparison instruction.
363  if (TII->OptimizeCompareInstr(MI, SrcReg, CmpMask, CmpValue, MRI)) {
364    ++NumCmps;
365    return true;
366  }
367
368  return false;
369}
370
371bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI,
372                                        SmallSet<unsigned, 4> &ImmDefRegs,
373                                 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
374  const MCInstrDesc &MCID = MI->getDesc();
375  if (!MI->isMoveImmediate())
376    return false;
377  if (MCID.getNumDefs() != 1)
378    return false;
379  unsigned Reg = MI->getOperand(0).getReg();
380  if (TargetRegisterInfo::isVirtualRegister(Reg)) {
381    ImmDefMIs.insert(std::make_pair(Reg, MI));
382    ImmDefRegs.insert(Reg);
383    return true;
384  }
385
386  return false;
387}
388
389/// foldImmediate - Try folding register operands that are defined by move
390/// immediate instructions, i.e. a trivial constant folding optimization, if
391/// and only if the def and use are in the same BB.
392bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
393                                      SmallSet<unsigned, 4> &ImmDefRegs,
394                                 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
395  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
396    MachineOperand &MO = MI->getOperand(i);
397    if (!MO.isReg() || MO.isDef())
398      continue;
399    unsigned Reg = MO.getReg();
400    if (!TargetRegisterInfo::isVirtualRegister(Reg))
401      continue;
402    if (ImmDefRegs.count(Reg) == 0)
403      continue;
404    DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg);
405    assert(II != ImmDefMIs.end());
406    if (TII->FoldImmediate(MI, II->second, Reg, MRI)) {
407      ++NumImmFold;
408      return true;
409    }
410  }
411  return false;
412}
413
414bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
415  if (DisablePeephole)
416    return false;
417
418  TM  = &MF.getTarget();
419  TII = TM->getInstrInfo();
420  MRI = &MF.getRegInfo();
421  DT  = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0;
422
423  bool Changed = false;
424
425  SmallPtrSet<MachineInstr*, 8> LocalMIs;
426  SmallSet<unsigned, 4> ImmDefRegs;
427  DenseMap<unsigned, MachineInstr*> ImmDefMIs;
428  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
429    MachineBasicBlock *MBB = &*I;
430
431    bool SeenMoveImm = false;
432    LocalMIs.clear();
433    ImmDefRegs.clear();
434    ImmDefMIs.clear();
435
436    bool First = true;
437    MachineBasicBlock::iterator PMII;
438    for (MachineBasicBlock::iterator
439           MII = I->begin(), MIE = I->end(); MII != MIE; ) {
440      MachineInstr *MI = &*MII;
441      LocalMIs.insert(MI);
442
443      if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
444          MI->isKill() || MI->isInlineAsm() || MI->isDebugValue() ||
445          MI->hasUnmodeledSideEffects()) {
446        ++MII;
447        continue;
448      }
449
450      if (MI->isBitcast()) {
451        if (optimizeBitcastInstr(MI, MBB)) {
452          // MI is deleted.
453          LocalMIs.erase(MI);
454          Changed = true;
455          MII = First ? I->begin() : llvm::next(PMII);
456          continue;
457        }
458      } else if (MI->isCompare()) {
459        if (optimizeCmpInstr(MI, MBB)) {
460          // MI is deleted.
461          LocalMIs.erase(MI);
462          Changed = true;
463          MII = First ? I->begin() : llvm::next(PMII);
464          continue;
465        }
466      }
467
468      if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
469        SeenMoveImm = true;
470      } else {
471        Changed |= optimizeExtInstr(MI, MBB, LocalMIs);
472        if (SeenMoveImm)
473          Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs);
474      }
475
476      First = false;
477      PMII = MII;
478      ++MII;
479    }
480  }
481
482  return Changed;
483}
484