LLVM  10.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  Register 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  Register 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() && !SrcMI->getOperand(0).getSubReg() &&
119  !SrcMI->getOperand(1).getSubReg() &&
121  SrcReg = SrcMI->getOperand(1).getReg();
122  SrcMI = MRI->getVRegDef(SrcReg);
123  }
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 && SingleValReg != SrcReg)
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  Register 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  Register 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 
186  // The kill flags on OldReg and SingleValReg may no longer be correct.
187  MRI->clearKillFlags(SingleValReg);
188 
189  ++NumPHICycles;
190  Changed = true;
191  continue;
192  }
193 
194  // Check for dead PHI cycles.
195  PHIsInCycle.clear();
196  if (IsDeadPHICycle(MI, PHIsInCycle)) {
197  for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
198  PI != PE; ++PI) {
199  MachineInstr *PhiMI = *PI;
200  if (MII == PhiMI)
201  ++MII;
202  PhiMI->eraseFromParent();
203  }
204  ++NumDeadPHICycles;
205  Changed = true;
206  }
207  }
208  return Changed;
209 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getSubReg() const
STATISTIC(NumFunctions, "Total number of functions")
void initializeOptimizePHIsPass(PassRegistry &)
bool isPHI() const
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
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:413
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:301
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
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19