LLVM  8.0.0svn
OptimizePHIs.cpp
Go to the documentation of this file.
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/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Pass.h"
26 #include <cassert>
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "opt-phis"
31 
32 STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
33 STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
34 
35 namespace {
36 
37  class OptimizePHIs : public MachineFunctionPass {
39  const TargetInstrInfo *TII;
40 
41  public:
42  static char ID; // Pass identification
43 
44  OptimizePHIs() : MachineFunctionPass(ID) {
46  }
47 
48  bool runOnMachineFunction(MachineFunction &Fn) override;
49 
50  void getAnalysisUsage(AnalysisUsage &AU) const override {
51  AU.setPreservesCFG();
53  }
54 
55  private:
56  using InstrSet = SmallPtrSet<MachineInstr *, 16>;
57  using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
58 
59  bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
60  InstrSet &PHIsInCycle);
61  bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
62  bool OptimizeBB(MachineBasicBlock &MBB);
63  };
64 
65 } // end anonymous namespace
66 
67 char OptimizePHIs::ID = 0;
68 
70 
72  "Optimize machine instruction PHIs", false, false)
73 
74 bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
75  if (skipFunction(Fn.getFunction()))
76  return false;
77 
78  MRI = &Fn.getRegInfo();
79  TII = Fn.getSubtarget().getInstrInfo();
80 
81  // Find dead PHI cycles and PHI cycles that can be replaced by a single
82  // value. InstCombine does these optimizations, but DAG legalization may
83  // introduce new opportunities, e.g., when i64 values are split up for
84  // 32-bit targets.
85  bool Changed = false;
86  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
87  Changed |= OptimizeBB(*I);
88 
89  return Changed;
90 }
91 
92 /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
93 /// are copies of SingleValReg, possibly via copies through other PHIs. If
94 /// SingleValReg is zero on entry, it is set to the register with the single
95 /// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
96 /// have been scanned.
97 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
98  unsigned &SingleValReg,
99  InstrSet &PHIsInCycle) {
100  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
101  unsigned DstReg = MI->getOperand(0).getReg();
102 
103  // See if we already saw this register.
104  if (!PHIsInCycle.insert(MI).second)
105  return true;
106 
107  // Don't scan crazily complex things.
108  if (PHIsInCycle.size() == 16)
109  return false;
110 
111  // Scan the PHI operands.
112  for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
113  unsigned SrcReg = MI->getOperand(i).getReg();
114  if (SrcReg == DstReg)
115  continue;
116  MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
117 
118  // Skip over register-to-register moves.
119  if (SrcMI && SrcMI->isCopy() &&
120  !SrcMI->getOperand(0).getSubReg() &&
121  !SrcMI->getOperand(1).getSubReg() &&
123  SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
124  if (!SrcMI)
125  return false;
126 
127  if (SrcMI->isPHI()) {
128  if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
129  return false;
130  } else {
131  // Fail if there is more than one non-phi/non-move register.
132  if (SingleValReg != 0)
133  return false;
134  SingleValReg = SrcReg;
135  }
136  }
137  return true;
138 }
139 
140 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
141 /// other PHIs in a cycle.
142 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
143  assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
144  unsigned DstReg = MI->getOperand(0).getReg();
146  "PHI destination is not a virtual register");
147 
148  // See if we already saw this register.
149  if (!PHIsInCycle.insert(MI).second)
150  return true;
151 
152  // Don't scan crazily complex things.
153  if (PHIsInCycle.size() == 16)
154  return false;
155 
156  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) {
157  if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
158  return false;
159  }
160 
161  return true;
162 }
163 
164 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
165 /// a single value.
166 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
167  bool Changed = false;
169  MII = MBB.begin(), E = MBB.end(); MII != E; ) {
170  MachineInstr *MI = &*MII++;
171  if (!MI->isPHI())
172  break;
173 
174  // Check for single-value PHI cycles.
175  unsigned SingleValReg = 0;
176  InstrSet PHIsInCycle;
177  if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
178  SingleValReg != 0) {
179  unsigned OldReg = MI->getOperand(0).getReg();
180  if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
181  continue;
182 
183  MRI->replaceRegWith(OldReg, SingleValReg);
184  MI->eraseFromParent();
185  ++NumPHICycles;
186  Changed = true;
187  continue;
188  }
189 
190  // Check for dead PHI cycles.
191  PHIsInCycle.clear();
192  if (IsDeadPHICycle(MI, PHIsInCycle)) {
193  for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
194  PI != PE; ++PI) {
195  MachineInstr *PhiMI = *PI;
196  if (MII == PhiMI)
197  ++MII;
198  PhiMI->eraseFromParent();
199  }
200  ++NumDeadPHICycles;
201  Changed = true;
202  }
203  }
204  return Changed;
205 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned getSubReg() const
STATISTIC(NumFunctions, "Total number of functions")
void initializeOptimizePHIsPass(PassRegistry &)
bool isPHI() const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:412
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
TargetInstrInfo - Interface to description of machine instruction set.
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Represent the analysis usage information of a pass.
bool isCopy() const
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:267
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE, "Optimize machine instruction PHIs", false, false) bool OptimizePHIs
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
char & OptimizePHIsID
OptimizePHIs - This pass optimizes machine instruction PHIs to take advantage of opportunities create...
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define DEBUG_TYPE
IRTranslator LLVM IR MI
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const