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