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