LLVM  14.0.0git
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/InitializePasses.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 (MachineBasicBlock &MBB : Fn)
87  Changed |= OptimizeBB(MBB);
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. PHIs may be grouped by cycle, several cycles or chains.
97 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
98  unsigned &SingleValReg,
99  InstrSet &PHIsInCycle) {
100  assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
101  Register 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  Register 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() && !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  Register 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  Register 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 (MachineInstr *PhiMI : PHIsInCycle) {
199  if (MII == PhiMI)
200  ++MII;
201  PhiMI->eraseFromParent();
202  }
203  ++NumDeadPHICycles;
204  Changed = true;
205  }
206  }
207  return Changed;
208 }
i
i
Definition: README.txt:29
llvm::OptimizePHIsID
char & OptimizePHIsID
OptimizePHIs - This pass optimizes machine instruction PHIs to take advantage of opportunities create...
Definition: OptimizePHIs.cpp:69
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:102
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
Pass.h
Statistic.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
llvm::SmallPtrSetIterator
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:266
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1291
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
MachineRegisterInfo.h
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::initializeOptimizePHIsPass
void initializeOptimizePHIsPass(PassRegistry &)
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:499
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
DEBUG_TYPE
#define DEBUG_TYPE
Definition: OptimizePHIs.cpp:30
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
SmallPtrSet.h
INITIALIZE_PASS
INITIALIZE_PASS(OptimizePHIs, DEBUG_TYPE, "Optimize machine instruction PHIs", false, false) bool OptimizePHIs
Definition: OptimizePHIs.cpp:71
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:398
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::MachineRegisterInfo::clearKillFlags
void clearKillFlags(Register Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
Definition: MachineRegisterInfo.cpp:429
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineFunctionPass.h
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1255
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineFunction
Definition: MachineFunction.h:234
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
TargetSubtargetInfo.h
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:365
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:380
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MachineRegisterInfo::constrainRegClass
const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
Definition: MachineRegisterInfo.cpp:85
MachineOperand.h
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
TargetRegisterInfo.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38