PeepholeOptimizer.cpp revision d8d0279c007e70c325b4ac9d9893b31ee5f21085 
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  if (MRI->hasOneNonDBGUse(SrcReg))
149    // No other uses.
150    return false;
151
152  // Ensure DstReg can get a register class that actually supports
153  // sub-registers. Don't change the class until we commit.
154  const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
155  DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx);
156  if (!DstRC)
157    return false;
158
159  // The source has other uses. See if we can replace the other uses with use of
160  // the result of the extension.
161  SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs;
162  for (MachineRegisterInfo::use_nodbg_iterator
163       UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end();
164       UI != UE; ++UI)
165    ReachedBBs.insert(UI->getParent());
166
167  // Uses that are in the same BB of uses of the result of the instruction.
168  SmallVector<MachineOperand*, 8> Uses;
169
170  // Uses that the result of the instruction can reach.
171  SmallVector<MachineOperand*, 8> ExtendedUses;
172
173  bool ExtendLife = true;
174  for (MachineRegisterInfo::use_nodbg_iterator
175       UI = MRI->use_nodbg_begin(SrcReg), UE = MRI->use_nodbg_end();
176       UI != UE; ++UI) {
177    MachineOperand &UseMO = UI.getOperand();
178    MachineInstr *UseMI = &*UI;
179    if (UseMI == MI)
180      continue;
181
182    if (UseMI->isPHI()) {
183      ExtendLife = false;
184      continue;
185    }
186
187    // It's an error to translate this:
188    //
189    //    %reg1025 = <sext> %reg1024
190    //     ...
191    //    %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
192    //
193    // into this:
194    //
195    //    %reg1025 = <sext> %reg1024
196    //     ...
197    //    %reg1027 = COPY %reg1025:4
198    //    %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
199    //
200    // The problem here is that SUBREG_TO_REG is there to assert that an
201    // implicit zext occurs. It doesn't insert a zext instruction. If we allow
202    // the COPY here, it will give us the value after the <sext>, not the
203    // original value of %reg1024 before <sext>.
204    if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG)
205      continue;
206
207    MachineBasicBlock *UseMBB = UseMI->getParent();
208    if (UseMBB == MBB) {
209      // Local uses that come after the extension.
210      if (!LocalMIs.count(UseMI))
211        Uses.push_back(&UseMO);
212    } else if (ReachedBBs.count(UseMBB)) {
213      // Non-local uses where the result of the extension is used. Always
214      // replace these unless it's a PHI.
215      Uses.push_back(&UseMO);
216    } else if (Aggressive && DT->dominates(MBB, UseMBB)) {
217      // We may want to extend the live range of the extension result in order
218      // to replace these uses.
219      ExtendedUses.push_back(&UseMO);
220    } else {
221      // Both will be live out of the def MBB anyway. Don't extend live range of
222      // the extension result.
223      ExtendLife = false;
224      break;
225    }
226  }
227
228  if (ExtendLife && !ExtendedUses.empty())
229    // Extend the liveness of the extension result.
230    std::copy(ExtendedUses.begin(), ExtendedUses.end(),
231              std::back_inserter(Uses));
232
233  // Now replace all uses.
234  bool Changed = false;
235  if (!Uses.empty()) {
236    SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
237
238    // Look for PHI uses of the extended result, we don't want to extend the
239    // liveness of a PHI input. It breaks all kinds of assumptions down
240    // stream. A PHI use is expected to be the kill of its source values.
241    for (MachineRegisterInfo::use_nodbg_iterator
242         UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end();
243         UI != UE; ++UI)
244      if (UI->isPHI())
245        PHIBBs.insert(UI->getParent());
246
247    const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
248    for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
249      MachineOperand *UseMO = Uses[i];
250      MachineInstr *UseMI = UseMO->getParent();
251      MachineBasicBlock *UseMBB = UseMI->getParent();
252      if (PHIBBs.count(UseMBB))
253        continue;
254
255      // About to add uses of DstReg, clear DstReg's kill flags.
256      if (!Changed) {
257        MRI->clearKillFlags(DstReg);
258        MRI->constrainRegClass(DstReg, DstRC);
259      }
260
261      unsigned NewVR = MRI->createVirtualRegister(RC);
262      BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(),
263              TII->get(TargetOpcode::COPY), NewVR)
264        .addReg(DstReg, 0, SubIdx);
265
266      UseMO->setReg(NewVR);
267      ++NumReuse;
268      Changed = true;
269    }
270  }
271
272  return Changed;
273}
274
275/// optimizeBitcastInstr - If the instruction is a bitcast instruction A that
276/// cannot be optimized away during isel (e.g. ARM::VMOVSR, which bitcast
277/// a value cross register classes), and the source is defined by another
278/// bitcast instruction B. And if the register class of source of B matches
279/// the register class of instruction A, then it is legal to replace all uses
280/// of the def of A with source of B. e.g.
281///   %vreg0<def> = VMOVSR %vreg1
282///   %vreg3<def> = VMOVRS %vreg0
283///   Replace all uses of vreg3 with vreg1.
284
285bool PeepholeOptimizer::optimizeBitcastInstr(MachineInstr *MI,
286                                             MachineBasicBlock *MBB) {
287  unsigned NumDefs = MI->getDesc().getNumDefs();
288  unsigned NumSrcs = MI->getDesc().getNumOperands() - NumDefs;
289  if (NumDefs != 1)
290    return false;
291
292  unsigned Def = 0;
293  unsigned Src = 0;
294  for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
295    const MachineOperand &MO = MI->getOperand(i);
296    if (!MO.isReg())
297      continue;
298    unsigned Reg = MO.getReg();
299    if (!Reg)
300      continue;
301    if (MO.isDef())
302      Def = Reg;
303    else if (Src)
304      // Multiple sources?
305      return false;
306    else
307      Src = Reg;
308  }
309
310  assert(Def && Src && "Malformed bitcast instruction!");
311
312  MachineInstr *DefMI = MRI->getVRegDef(Src);
313  if (!DefMI || !DefMI->isBitcast())
314    return false;
315
316  unsigned SrcSrc = 0;
317  NumDefs = DefMI->getDesc().getNumDefs();
318  NumSrcs = DefMI->getDesc().getNumOperands() - NumDefs;
319  if (NumDefs != 1)
320    return false;
321  for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) {
322    const MachineOperand &MO = DefMI->getOperand(i);
323    if (!MO.isReg() || MO.isDef())
324      continue;
325    unsigned Reg = MO.getReg();
326    if (!Reg)
327      continue;
328    if (!MO.isDef()) {
329      if (SrcSrc)
330        // Multiple sources?
331        return false;
332      else
333        SrcSrc = Reg;
334    }
335  }
336
337  if (MRI->getRegClass(SrcSrc) != MRI->getRegClass(Def))
338    return false;
339
340  MRI->replaceRegWith(Def, SrcSrc);
341  MRI->clearKillFlags(SrcSrc);
342  MI->eraseFromParent();
343  ++NumBitcasts;
344  return true;
345}
346
347/// optimizeCmpInstr - If the instruction is a compare and the previous
348/// instruction it's comparing against all ready sets (or could be modified to
349/// set) the same flag as the compare, then we can remove the comparison and use
350/// the flag from the previous instruction.
351bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI,
352                                         MachineBasicBlock *MBB) {
353  // If this instruction is a comparison against zero and isn't comparing a
354  // physical register, we can try to optimize it.
355  unsigned SrcReg;
356  int CmpMask, CmpValue;
357  if (!TII->AnalyzeCompare(MI, SrcReg, CmpMask, CmpValue) ||
358      TargetRegisterInfo::isPhysicalRegister(SrcReg))
359    return false;
360
361  // Attempt to optimize the comparison instruction.
362  if (TII->OptimizeCompareInstr(MI, SrcReg, CmpMask, CmpValue, MRI)) {
363    ++NumCmps;
364    return true;
365  }
366
367  return false;
368}
369
370bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI,
371                                        SmallSet<unsigned, 4> &ImmDefRegs,
372                                 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
373  const MCInstrDesc &MCID = MI->getDesc();
374  if (!MI->isMoveImmediate())
375    return false;
376  if (MCID.getNumDefs() != 1)
377    return false;
378  unsigned Reg = MI->getOperand(0).getReg();
379  if (TargetRegisterInfo::isVirtualRegister(Reg)) {
380    ImmDefMIs.insert(std::make_pair(Reg, MI));
381    ImmDefRegs.insert(Reg);
382    return true;
383  }
384
385  return false;
386}
387
388/// foldImmediate - Try folding register operands that are defined by move
389/// immediate instructions, i.e. a trivial constant folding optimization, if
390/// and only if the def and use are in the same BB.
391bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB,
392                                      SmallSet<unsigned, 4> &ImmDefRegs,
393                                 DenseMap<unsigned, MachineInstr*> &ImmDefMIs) {
394  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
395    MachineOperand &MO = MI->getOperand(i);
396    if (!MO.isReg() || MO.isDef())
397      continue;
398    unsigned Reg = MO.getReg();
399    if (!TargetRegisterInfo::isVirtualRegister(Reg))
400      continue;
401    if (ImmDefRegs.count(Reg) == 0)
402      continue;
403    DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg);
404    assert(II != ImmDefMIs.end());
405    if (TII->FoldImmediate(MI, II->second, Reg, MRI)) {
406      ++NumImmFold;
407      return true;
408    }
409  }
410  return false;
411}
412
413bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) {
414  if (DisablePeephole)
415    return false;
416
417  TM  = &MF.getTarget();
418  TII = TM->getInstrInfo();
419  MRI = &MF.getRegInfo();
420  DT  = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0;
421
422  bool Changed = false;
423
424  SmallPtrSet<MachineInstr*, 8> LocalMIs;
425  SmallSet<unsigned, 4> ImmDefRegs;
426  DenseMap<unsigned, MachineInstr*> ImmDefMIs;
427  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
428    MachineBasicBlock *MBB = &*I;
429
430    bool SeenMoveImm = false;
431    LocalMIs.clear();
432    ImmDefRegs.clear();
433    ImmDefMIs.clear();
434
435    bool First = true;
436    MachineBasicBlock::iterator PMII;
437    for (MachineBasicBlock::iterator
438           MII = I->begin(), MIE = I->end(); MII != MIE; ) {
439      MachineInstr *MI = &*MII;
440      LocalMIs.insert(MI);
441
442      if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
443          MI->isKill() || MI->isInlineAsm() || MI->isDebugValue() ||
444          MI->hasUnmodeledSideEffects()) {
445        ++MII;
446        continue;
447      }
448
449      if (MI->isBitcast()) {
450        if (optimizeBitcastInstr(MI, MBB)) {
451          // MI is deleted.
452          LocalMIs.erase(MI);
453          Changed = true;
454          MII = First ? I->begin() : llvm::next(PMII);
455          continue;
456        }
457      } else if (MI->isCompare()) {
458        if (optimizeCmpInstr(MI, MBB)) {
459          // MI is deleted.
460          LocalMIs.erase(MI);
461          Changed = true;
462          MII = First ? I->begin() : llvm::next(PMII);
463          continue;
464        }
465      }
466
467      if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
468        SeenMoveImm = true;
469      } else {
470        Changed |= optimizeExtInstr(MI, MBB, LocalMIs);
471        if (SeenMoveImm)
472          Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs);
473      }
474
475      First = false;
476      PMII = MII;
477      ++MII;
478    }
479  }
480
481  return Changed;
482}
483