LLVM  15.0.0git
UnreachableBlockElim.cpp
Go to the documentation of this file.
1 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
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 is an extremely simple version of the SimplifyCFG pass. Its sole
10 // job is to delete LLVM basic blocks that are not reachable from the entry
11 // node. To do this, it performs a simple depth first traversal of the CFG,
12 // then deletes any unvisited nodes.
13 //
14 // Note that this pass is really a hack. In particular, the instruction
15 // selectors for various targets should just not generate code for unreachable
16 // blocks. Until LLVM has a more systematic way of defining instruction
17 // selectors, however, we cannot really expect them to handle additional
18 // complexity.
19 //
20 //===----------------------------------------------------------------------===//
21 
24 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/InitializePasses.h"
34 #include "llvm/Pass.h"
36 using namespace llvm;
37 
38 namespace {
39 class UnreachableBlockElimLegacyPass : public FunctionPass {
40  bool runOnFunction(Function &F) override {
42  }
43 
44 public:
45  static char ID; // Pass identification, replacement for typeid
46  UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
49  }
50 
51  void getAnalysisUsage(AnalysisUsage &AU) const override {
53  }
54 };
55 }
57 INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
58  "Remove unreachable blocks from the CFG", false, false)
59 
61  return new UnreachableBlockElimLegacyPass();
62 }
63 
66  bool Changed = llvm::EliminateUnreachableBlocks(F);
67  if (!Changed)
68  return PreservedAnalyses::all();
71  return PA;
72 }
73 
74 namespace {
75  class UnreachableMachineBlockElim : public MachineFunctionPass {
76  bool runOnMachineFunction(MachineFunction &F) override;
77  void getAnalysisUsage(AnalysisUsage &AU) const override;
78 
79  public:
80  static char ID; // Pass identification, replacement for typeid
81  UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
82  };
83 }
85 
86 INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
87  "Remove unreachable machine basic blocks", false, false)
88 
89 char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
90 
91 void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
92  AU.addPreserved<MachineLoopInfo>();
93  AU.addPreserved<MachineDominatorTree>();
95 }
96 
97 bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
99  bool ModifiedPHI = false;
100 
101  MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
102  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
103 
104  // Mark all reachable blocks.
105  for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
106  (void)BB/* Mark all reachable blocks */;
107 
108  // Loop over all dead blocks, remembering them and deleting all instructions
109  // in them.
110  std::vector<MachineBasicBlock*> DeadBlocks;
111  for (MachineBasicBlock &BB : F) {
112  // Test for deadness.
113  if (!Reachable.count(&BB)) {
114  DeadBlocks.push_back(&BB);
115 
116  // Update dominator and loop info.
117  if (MLI) MLI->removeBlock(&BB);
118  if (MDT && MDT->getNode(&BB)) MDT->eraseNode(&BB);
119 
120  while (BB.succ_begin() != BB.succ_end()) {
121  MachineBasicBlock* succ = *BB.succ_begin();
122 
123  MachineBasicBlock::iterator start = succ->begin();
124  while (start != succ->end() && start->isPHI()) {
125  for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
126  if (start->getOperand(i).isMBB() &&
127  start->getOperand(i).getMBB() == &BB) {
128  start->removeOperand(i);
129  start->removeOperand(i-1);
130  }
131 
132  start++;
133  }
134 
135  BB.removeSuccessor(BB.succ_begin());
136  }
137  }
138  }
139 
140  // Actually remove the blocks now.
141  for (MachineBasicBlock *BB : DeadBlocks) {
142  // Remove any call site information for calls in the block.
143  for (auto &I : BB->instrs())
144  if (I.shouldUpdateCallSiteInfo())
145  BB->getParent()->eraseCallSiteInfo(&I);
146 
147  BB->eraseFromParent();
148  }
149 
150  // Cleanup PHI nodes.
151  for (MachineBasicBlock &BB : F) {
152  // Prune unneeded PHI entries.
154  BB.pred_end());
156  while (phi != BB.end() && phi->isPHI()) {
157  for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
158  if (!preds.count(phi->getOperand(i).getMBB())) {
159  phi->removeOperand(i);
160  phi->removeOperand(i-1);
161  ModifiedPHI = true;
162  }
163 
164  if (phi->getNumOperands() == 3) {
165  const MachineOperand &Input = phi->getOperand(1);
166  const MachineOperand &Output = phi->getOperand(0);
167  Register InputReg = Input.getReg();
168  Register OutputReg = Output.getReg();
169  assert(Output.getSubReg() == 0 && "Cannot have output subregister");
170  ModifiedPHI = true;
171 
172  if (InputReg != OutputReg) {
173  MachineRegisterInfo &MRI = F.getRegInfo();
174  unsigned InputSub = Input.getSubReg();
175  if (InputSub == 0 &&
176  MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
177  !Input.isUndef()) {
178  MRI.replaceRegWith(OutputReg, InputReg);
179  } else {
180  // The input register to the PHI has a subregister or it can't be
181  // constrained to the proper register class or it is undef:
182  // insert a COPY instead of simply replacing the output
183  // with the input.
184  const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
185  BuildMI(BB, BB.getFirstNonPHI(), phi->getDebugLoc(),
186  TII->get(TargetOpcode::COPY), OutputReg)
187  .addReg(InputReg, getRegState(Input), InputSub);
188  }
189  phi++->eraseFromParent();
190  }
191  continue;
192  }
193 
194  ++phi;
195  }
196  }
197 
198  F.RenumberBlocks();
199 
200  return (!DeadBlocks.empty() || ModifiedPHI);
201 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::SPIRV::StorageClass::Input
@ Input
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::Function
Definition: Function.h:60
Pass.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
TargetInstrInfo.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
preds
preds
Definition: README.txt:340
llvm::createUnreachableBlockEliminationPass
FunctionPass * createUnreachableBlockEliminationPass()
createUnreachableBlockEliminationPass - The LLVM code generator does not work well with unreachable b...
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
MachineLoopInfo.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::SPIRV::StorageClass::Output
@ Output
SmallPtrSet.h
llvm::EliminateUnreachableBlocks
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
Definition: BasicBlockUtils.cpp:123
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:642
Passes.h
llvm::UnreachableBlockElimPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnreachableBlockElim.cpp:64
llvm::getRegState
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
Definition: MachineInstrBuilder.h:528
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:174
I
#define I(x, y, z)
Definition: MD5.cpp:58
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::SmallPtrSetImpl< NodeRef >::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::MachineDominatorTree::eraseNode
void eraseNode(MachineBasicBlock *BB)
eraseNode - Removes a node from the dominator tree.
Definition: MachineDominators.h:206
llvm::UnreachableMachineBlockElimID
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:378
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
UnreachableBlockElim.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::numbers::phi
constexpr double phi
Definition: MathExtras.h:71
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
MachineInstrBuilder.h
Dominators.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:328
llvm::MachineLoopInfo::removeBlock
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: MachineLoopInfo.h:178
INITIALIZE_PASS
INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim", "Remove unreachable blocks from the CFG", false, false) FunctionPass *llvm
Definition: UnreachableBlockElim.cpp:57
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:83
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
BasicBlockUtils.h
llvm::initializeUnreachableBlockElimLegacyPassPass
void initializeUnreachableBlockElimLegacyPassPass(PassRegistry &)
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:280
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38