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 (MachineBasicBlock *BB : DeadBlocks) {
148  // Remove any call site information for calls in the block.
149  for (auto &I : BB->instrs())
150  if (I.shouldUpdateCallSiteInfo())
151  BB->getParent()->eraseCallSiteInfo(&I);
152 
153  BB->eraseFromParent();
154  }
155 
156  // Cleanup PHI nodes.
157  for (MachineBasicBlock &BB : F) {
158  // Prune unneeded PHI entries.
160  BB.pred_end());
162  while (phi != BB.end() && phi->isPHI()) {
163  for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
164  if (!preds.count(phi->getOperand(i).getMBB())) {
165  phi->RemoveOperand(i);
166  phi->RemoveOperand(i-1);
167  ModifiedPHI = true;
168  }
169 
170  if (phi->getNumOperands() == 3) {
171  const MachineOperand &Input = phi->getOperand(1);
172  const MachineOperand &Output = phi->getOperand(0);
173  Register InputReg = Input.getReg();
174  Register OutputReg = Output.getReg();
175  assert(Output.getSubReg() == 0 && "Cannot have output subregister");
176  ModifiedPHI = true;
177 
178  if (InputReg != OutputReg) {
179  MachineRegisterInfo &MRI = F.getRegInfo();
180  unsigned InputSub = Input.getSubReg();
181  if (InputSub == 0 &&
182  MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
183  !Input.isUndef()) {
184  MRI.replaceRegWith(OutputReg, InputReg);
185  } else {
186  // The input register to the PHI has a subregister or it can't be
187  // constrained to the proper register class or it is undef:
188  // insert a COPY instead of simply replacing the output
189  // with the input.
190  const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
191  BuildMI(BB, BB.getFirstNonPHI(), phi->getDebugLoc(),
192  TII->get(TargetOpcode::COPY), OutputReg)
193  .addReg(InputReg, getRegState(Input), InputSub);
194  }
195  phi++->eraseFromParent();
196  }
197  continue;
198  }
199 
200  ++phi;
201  }
202  }
203 
204  F.RenumberBlocks();
205 
206  return (!DeadBlocks.empty() || ModifiedPHI);
207 }
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::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:55
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
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
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
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:241
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
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
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:272
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:274
MachineDominators.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38