LLVM  14.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"
31 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/IR/CFG.h"
34 #include "llvm/IR/Constant.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
42 using namespace llvm;
43 
44 namespace {
45 class UnreachableBlockElimLegacyPass : public FunctionPass {
46  bool runOnFunction(Function &F) override {
48  }
49 
50 public:
51  static char ID; // Pass identification, replacement for typeid
52  UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
55  }
56 
57  void getAnalysisUsage(AnalysisUsage &AU) const override {
59  }
60 };
61 }
63 INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
64  "Remove unreachable blocks from the CFG", false, false)
65 
67  return new UnreachableBlockElimLegacyPass();
68 }
69 
72  bool Changed = llvm::EliminateUnreachableBlocks(F);
73  if (!Changed)
74  return PreservedAnalyses::all();
77  return PA;
78 }
79 
80 namespace {
81  class UnreachableMachineBlockElim : public MachineFunctionPass {
82  bool runOnMachineFunction(MachineFunction &F) override;
83  void getAnalysisUsage(AnalysisUsage &AU) const override;
84 
85  public:
86  static char ID; // Pass identification, replacement for typeid
87  UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
88  };
89 }
91 
92 INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
93  "Remove unreachable machine basic blocks", false, false)
94 
95 char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
96 
97 void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
98  AU.addPreserved<MachineLoopInfo>();
99  AU.addPreserved<MachineDominatorTree>();
101 }
102 
103 bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
105  bool ModifiedPHI = false;
106 
107  MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
108  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
109 
110  // Mark all reachable blocks.
111  for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
112  (void)BB/* Mark all reachable blocks */;
113 
114  // Loop over all dead blocks, remembering them and deleting all instructions
115  // in them.
116  std::vector<MachineBasicBlock*> DeadBlocks;
117  for (MachineBasicBlock &BB : F) {
118  // Test for deadness.
119  if (!Reachable.count(&BB)) {
120  DeadBlocks.push_back(&BB);
121 
122  // Update dominator and loop info.
123  if (MLI) MLI->removeBlock(&BB);
124  if (MDT && MDT->getNode(&BB)) MDT->eraseNode(&BB);
125 
126  while (BB.succ_begin() != BB.succ_end()) {
127  MachineBasicBlock* succ = *BB.succ_begin();
128 
129  MachineBasicBlock::iterator start = succ->begin();
130  while (start != succ->end() && start->isPHI()) {
131  for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
132  if (start->getOperand(i).isMBB() &&
133  start->getOperand(i).getMBB() == &BB) {
134  start->RemoveOperand(i);
135  start->RemoveOperand(i-1);
136  }
137 
138  start++;
139  }
140 
141  BB.removeSuccessor(BB.succ_begin());
142  }
143  }
144  }
145 
146  // Actually remove the blocks now.
147  for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
148  // Remove any call site information for calls in the block.
149  for (auto &I : DeadBlocks[i]->instrs())
150  if (I.shouldUpdateCallSiteInfo())
151  DeadBlocks[i]->getParent()->eraseCallSiteInfo(&I);
152 
153  DeadBlocks[i]->eraseFromParent();
154  }
155 
156  // Cleanup PHI nodes.
157  for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
158  MachineBasicBlock *BB = &*I;
159  // Prune unneeded PHI entries.
161  BB->pred_end());
163  while (phi != BB->end() && phi->isPHI()) {
164  for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
165  if (!preds.count(phi->getOperand(i).getMBB())) {
166  phi->RemoveOperand(i);
167  phi->RemoveOperand(i-1);
168  ModifiedPHI = true;
169  }
170 
171  if (phi->getNumOperands() == 3) {
172  const MachineOperand &Input = phi->getOperand(1);
173  const MachineOperand &Output = phi->getOperand(0);
174  Register InputReg = Input.getReg();
175  Register OutputReg = Output.getReg();
176  assert(Output.getSubReg() == 0 && "Cannot have output subregister");
177  ModifiedPHI = true;
178 
179  if (InputReg != OutputReg) {
180  MachineRegisterInfo &MRI = F.getRegInfo();
181  unsigned InputSub = Input.getSubReg();
182  if (InputSub == 0 &&
183  MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
184  !Input.isUndef()) {
185  MRI.replaceRegWith(OutputReg, InputReg);
186  } else {
187  // The input register to the PHI has a subregister or it can't be
188  // constrained to the proper register class or it is undef:
189  // insert a COPY instead of simply replacing the output
190  // with the input.
191  const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
192  BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
193  TII->get(TargetOpcode::COPY), OutputReg)
194  .addReg(InputReg, getRegState(Input), InputSub);
195  }
196  phi++->eraseFromParent();
197  }
198  continue;
199  }
200 
201  ++phi;
202  }
203  }
204 
205  F.RenumberBlocks();
206 
207  return (!DeadBlocks.empty() || ModifiedPHI);
208 }
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:155
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Function
Definition: Function.h:62
Pass.h
llvm::Function::eraseFromParent
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Function.cpp:365
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:449
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:102
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
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
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:251
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
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:125
Type.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
CFG.h
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
Passes.h
llvm::UnreachableBlockElimPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: UnreachableBlockElim.cpp:70
llvm::getRegState
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
Definition: MachineInstrBuilder.h:528
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:395
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:169
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:59
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineModuleInfo.h
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::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
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:382
llvm::MachineFunction
Definition: MachineFunction.h:234
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::MachineDominatorTree::eraseNode
void eraseNode(MachineBasicBlock *BB)
eraseNode - Removes a node from the dominator tree.
Definition: MachineDominators.h:201
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
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:870
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
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
Function.h
UnreachableBlockElim.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
Instructions.h
llvm::numbers::phi
constexpr double phi
Definition: MathExtras.h:71
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
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:179
INITIALIZE_PASS
INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim", "Remove unreachable blocks from the CFG", false, false) FunctionPass *llvm
Definition: UnreachableBlockElim.cpp:63
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
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:46
BasicBlockUtils.h
llvm::initializeUnreachableBlockElimLegacyPassPass
void initializeUnreachableBlockElimLegacyPassPass(PassRegistry &)
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38