OptimizePHIs.cpp revision 1f74590e9d1b9cf0f1f81a156efea73f76546e05 
1//===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===//
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// This pass optimizes machine instruction PHIs to take advantage of
11// opportunities created during DAG legalization.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "phi-opt"
16#include "llvm/CodeGen/Passes.h"
17#include "llvm/CodeGen/MachineFunctionPass.h"
18#include "llvm/CodeGen/MachineInstr.h"
19#include "llvm/CodeGen/MachineRegisterInfo.h"
20#include "llvm/Target/TargetInstrInfo.h"
21#include "llvm/Function.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/Statistic.h"
24using namespace llvm;
25
26STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
27STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
28
29namespace {
30  class OptimizePHIs : public MachineFunctionPass {
31    MachineRegisterInfo *MRI;
32    const TargetInstrInfo *TII;
33
34  public:
35    static char ID; // Pass identification
36    OptimizePHIs() : MachineFunctionPass(&ID) {}
37
38    virtual bool runOnMachineFunction(MachineFunction &MF);
39
40    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
41      AU.setPreservesCFG();
42      MachineFunctionPass::getAnalysisUsage(AU);
43    }
44
45  private:
46    typedef SmallPtrSet<MachineInstr*, 16> InstrSet;
47    typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator;
48
49    bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
50                               InstrSet &PHIsInCycle);
51    bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
52    bool OptimizeBB(MachineBasicBlock &MBB);
53  };
54}
55
56char OptimizePHIs::ID = 0;
57INITIALIZE_PASS(OptimizePHIs, "opt-phis",
58                "Optimize machine instruction PHIs", false, false);
59
60FunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); }
61
62bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
63  MRI = &Fn.getRegInfo();
64  TII = Fn.getTarget().getInstrInfo();
65
66  // Find dead PHI cycles and PHI cycles that can be replaced by a single
67  // value.  InstCombine does these optimizations, but DAG legalization may
68  // introduce new opportunities, e.g., when i64 values are split up for
69  // 32-bit targets.
70  bool Changed = false;
71  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
72    Changed |= OptimizeBB(*I);
73
74  return Changed;
75}
76
77/// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
78/// are copies of SingleValReg, possibly via copies through other PHIs.  If
79/// SingleValReg is zero on entry, it is set to the register with the single
80/// non-copy value.  PHIsInCycle is a set used to keep track of the PHIs that
81/// have been scanned.
82bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
83                                         unsigned &SingleValReg,
84                                         InstrSet &PHIsInCycle) {
85  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
86  unsigned DstReg = MI->getOperand(0).getReg();
87
88  // See if we already saw this register.
89  if (!PHIsInCycle.insert(MI))
90    return true;
91
92  // Don't scan crazily complex things.
93  if (PHIsInCycle.size() == 16)
94    return false;
95
96  // Scan the PHI operands.
97  for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
98    unsigned SrcReg = MI->getOperand(i).getReg();
99    if (SrcReg == DstReg)
100      continue;
101    MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
102
103    // Skip over register-to-register moves.
104    if (SrcMI && SrcMI->isCopy() &&
105        !SrcMI->getOperand(0).getSubReg() &&
106        !SrcMI->getOperand(1).getSubReg() &&
107        TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
108      SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
109    if (!SrcMI)
110      return false;
111
112    if (SrcMI->isPHI()) {
113      if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
114        return false;
115    } else {
116      // Fail if there is more than one non-phi/non-move register.
117      if (SingleValReg != 0)
118        return false;
119      SingleValReg = SrcReg;
120    }
121  }
122  return true;
123}
124
125/// IsDeadPHICycle - Check if the register defined by a PHI is only used by
126/// other PHIs in a cycle.
127bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
128  assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
129  unsigned DstReg = MI->getOperand(0).getReg();
130  assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
131         "PHI destination is not a virtual register");
132
133  // See if we already saw this register.
134  if (!PHIsInCycle.insert(MI))
135    return true;
136
137  // Don't scan crazily complex things.
138  if (PHIsInCycle.size() == 16)
139    return false;
140
141  for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg),
142         E = MRI->use_end(); I != E; ++I) {
143    MachineInstr *UseMI = &*I;
144    if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle))
145      return false;
146  }
147
148  return true;
149}
150
151/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
152/// a single value.
153bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
154  bool Changed = false;
155  for (MachineBasicBlock::iterator
156         MII = MBB.begin(), E = MBB.end(); MII != E; ) {
157    MachineInstr *MI = &*MII++;
158    if (!MI->isPHI())
159      break;
160
161    // Check for single-value PHI cycles.
162    unsigned SingleValReg = 0;
163    InstrSet PHIsInCycle;
164    if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
165        SingleValReg != 0) {
166      MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg);
167      MI->eraseFromParent();
168      ++NumPHICycles;
169      Changed = true;
170      continue;
171    }
172
173    // Check for dead PHI cycles.
174    PHIsInCycle.clear();
175    if (IsDeadPHICycle(MI, PHIsInCycle)) {
176      for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
177           PI != PE; ++PI) {
178        MachineInstr *PhiMI = *PI;
179        if (&*MII == PhiMI)
180          ++MII;
181        PhiMI->eraseFromParent();
182      }
183      ++NumDeadPHICycles;
184      Changed = true;
185    }
186  }
187  return Changed;
188}
189