LLVM  9.0.0svn
OptimizePHIs.cpp
Go to the documentation of this file.
1 //===- OptimizePHIs.cpp - Optimize machine instruction PHIs ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass optimizes machine instruction PHIs to take advantage of
10 // opportunities created during DAG legalization.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Pass.h"
25 #include <cassert>
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "opt-phis"
30 
31 STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
32 STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
33 
34 namespace {
35 
36  class OptimizePHIs : public MachineFunctionPass {
38  const TargetInstrInfo *TII;
39 
40  public:
41  static char ID; // Pass identification
42 
43  OptimizePHIs() : MachineFunctionPass(ID) {
45  }
46 
47  bool runOnMachineFunction(MachineFunction &Fn) override;
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
50  AU.setPreservesCFG();
52  }
53 
54  private:
55  using InstrSet = SmallPtrSet<MachineInstr *, 16>;
56  using InstrSetIterator = SmallPtrSetIterator<MachineInstr *>;
57 
58  bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
59  InstrSet &PHIsInCycle);
60  bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
61  bool OptimizeBB(MachineBasicBlock &MBB);
62  };
63 
64 } // end anonymous namespace
65 
66 char OptimizePHIs::ID = 0;
67 
69 
71  "Optimize machine instruction PHIs", false, false)
72 
73 bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
74  if (skipFunction(Fn.getFunction()))
75  return false;
76 
77  MRI = &Fn.getRegInfo();
78  TII = Fn.getSubtarget().getInstrInfo();
79 
80  // Find dead PHI cycles and PHI cycles that can be replaced by a single
81  // value. InstCombine does these optimizations, but DAG legalization may
82  // introduce new opportunities, e.g., when i64 values are split up for
83  // 32-bit targets.
84  bool Changed = false;
85  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
86  Changed |= OptimizeBB(*I);
87 
88  return Changed;
89 }
90 
91 /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
92 /// are copies of SingleValReg, possibly via copies through other PHIs. If
93 /// SingleValReg is zero on entry, it is set to the register with the single
94 /// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
95 /// have been scanned. PHIs may be grouped by cycle, several cycles or chains.
96 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
97  unsigned &SingleValReg,
98  InstrSet &PHIsInCycle) {
99  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
100  unsigned DstReg = MI->getOperand(0).getReg();
101 
102  // See if we already saw this register.
103  if (!PHIsInCycle.insert(MI).second)
104  return true;
105 
106  // Don't scan crazily complex things.
107  if (PHIsInCycle.size() == 16)
108  return false;
109 
110  // Scan the PHI operands.
111  for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
112  unsigned SrcReg = MI->getOperand(i).getReg();
113  if (SrcReg == DstReg)
114  continue;
115  MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
116 
117  // Skip over register-to-register moves.
118  if (SrcMI && SrcMI->isCopy() &&
119  !SrcMI->getOperand(0).getSubReg() &&
120  !SrcMI->getOperand(1).getSubReg() &&
122  SrcReg = SrcMI->getOperand(1).getReg();
123  SrcMI = MRI->getVRegDef(SrcReg);
124  }
125  if (!SrcMI)
126  return false;
127 
128  if (SrcMI->isPHI()) {
129  if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
130  return false;
131  } else {
132  // Fail if there is more than one non-phi/non-move register.
133  if (SingleValReg != 0 && SingleValReg != SrcReg)
134  return false;
135  SingleValReg = SrcReg;
136  }
137  }
138  return true;
139 }
140 
141 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
142 /// other PHIs in a cycle.
143 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
144  assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
145  unsigned DstReg = MI->getOperand(0).getReg();
147  "PHI destination is not a virtual register");
148 
149  // See if we already saw this register.
150  if (!PHIsInCycle.insert(MI).second)
151  return true;
152 
153  // Don't scan crazily complex things.
154  if (PHIsInCycle.size() == 16)
155  return false;
156 
157  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(DstReg)) {
158  if (!UseMI.isPHI() || !IsDeadPHICycle(&UseMI, PHIsInCycle))
159  return false;
160  }
161 
162  return true;
163 }
164 
165 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
166 /// a single value.
167 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
168  bool Changed = false;
170  MII = MBB.begin(), E = MBB.end(); MII != E; ) {
171  MachineInstr *MI = &*MII++;
172  if (!MI->isPHI())
173  break;
174 
175  // Check for single-value PHI cycles.
176  unsigned SingleValReg = 0;
177  InstrSet PHIsInCycle;
178  if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
179  SingleValReg != 0) {
180  unsigned OldReg = MI->getOperand(0).getReg();
181  if (!MRI->constrainRegClass(SingleValReg, MRI->getRegClass(OldReg)))
182  continue;
183 
184  MRI->replaceRegWith(OldReg, SingleValReg);
185  MI->eraseFromParent();
186 
187  // The kill flags on OldReg and SingleValReg may no longer be correct.
188  MRI->clearKillFlags(SingleValReg);
189 
190  ++NumPHICycles;
191  Changed = true;
192  continue;
193  }
194 
195  // Check for dead PHI cycles.
196  PHIsInCycle.clear();
197  if (IsDeadPHICycle(MI, PHIsInCycle)) {
198  for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
199  PI != PE; ++PI) {
200  MachineInstr *PhiMI = *PI;
201  if (MII == PhiMI)
202  ++MII;
203  PhiMI->eraseFromParent();
204  }
205  ++NumDeadPHICycles;
206  Changed = true;
207  }
208  }
209  return Changed;
210 }
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.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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
Retuns the total number of operands.
Definition: MachineInstr.h:411
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 ...
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
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:266
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:417
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:285
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:63
#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:413
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const