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