LLVM  6.0.0svn
UnreachableBlockElim.cpp
Go to the documentation of this file.
1 //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass is an extremely simple version of the SimplifyCFG pass. Its sole
11 // job is to delete LLVM basic blocks that are not reachable from the entry
12 // node. To do this, it performs a simple depth first traversal of the CFG,
13 // then deletes any unvisited nodes.
14 //
15 // Note that this pass is really a hack. In particular, the instruction
16 // selectors for various targets should just not generate code for unreachable
17 // blocks. Until LLVM has a more systematic way of defining instruction
18 // selectors, however, we cannot really expect them to handle additional
19 // complexity.
20 //
21 //===----------------------------------------------------------------------===//
22 
25 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/CodeGen/Passes.h"
34 #include "llvm/IR/CFG.h"
35 #include "llvm/IR/Constant.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/Type.h"
40 #include "llvm/Pass.h"
41 using namespace llvm;
42 
45 
46  // Mark all reachable blocks.
47  for (BasicBlock *BB : depth_first_ext(&F, Reachable))
48  (void)BB/* Mark all reachable blocks */;
49 
50  // Loop over all dead blocks, remembering them and deleting all instructions
51  // in them.
52  std::vector<BasicBlock*> DeadBlocks;
53  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
54  if (!Reachable.count(&*I)) {
55  BasicBlock *BB = &*I;
56  DeadBlocks.push_back(BB);
57  while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
58  PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
59  BB->getInstList().pop_front();
60  }
61  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
62  (*SI)->removePredecessor(BB);
63  BB->dropAllReferences();
64  }
65 
66  // Actually remove the blocks now.
67  for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
68  DeadBlocks[i]->eraseFromParent();
69  }
70 
71  return !DeadBlocks.empty();
72 }
73 
74 namespace {
75 class UnreachableBlockElimLegacyPass : public FunctionPass {
76  bool runOnFunction(Function &F) override {
77  return eliminateUnreachableBlock(F);
78  }
79 
80 public:
81  static char ID; // Pass identification, replacement for typeid
82  UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
85  }
86 
87  void getAnalysisUsage(AnalysisUsage &AU) const override {
89  }
90 };
91 }
93 INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
94  "Remove unreachable blocks from the CFG", false, false)
95 
97  return new UnreachableBlockElimLegacyPass();
98 }
99 
102  bool Changed = eliminateUnreachableBlock(F);
103  if (!Changed)
104  return PreservedAnalyses::all();
107  return PA;
108 }
109 
110 namespace {
111  class UnreachableMachineBlockElim : public MachineFunctionPass {
112  bool runOnMachineFunction(MachineFunction &F) override;
113  void getAnalysisUsage(AnalysisUsage &AU) const override;
114  MachineModuleInfo *MMI;
115  public:
116  static char ID; // Pass identification, replacement for typeid
117  UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
118  };
119 }
121 
122 INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
123  "Remove unreachable machine basic blocks", false, false)
124 
126 
127 void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
131 }
132 
133 bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
135  bool ModifiedPHI = false;
136 
137  MMI = getAnalysisIfAvailable<MachineModuleInfo>();
138  MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
139  MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
140 
141  // Mark all reachable blocks.
142  for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
143  (void)BB/* Mark all reachable blocks */;
144 
145  // Loop over all dead blocks, remembering them and deleting all instructions
146  // in them.
147  std::vector<MachineBasicBlock*> DeadBlocks;
148  for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
149  MachineBasicBlock *BB = &*I;
150 
151  // Test for deadness.
152  if (!Reachable.count(BB)) {
153  DeadBlocks.push_back(BB);
154 
155  // Update dominator and loop info.
156  if (MLI) MLI->removeBlock(BB);
157  if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB);
158 
159  while (BB->succ_begin() != BB->succ_end()) {
160  MachineBasicBlock* succ = *BB->succ_begin();
161 
162  MachineBasicBlock::iterator start = succ->begin();
163  while (start != succ->end() && start->isPHI()) {
164  for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
165  if (start->getOperand(i).isMBB() &&
166  start->getOperand(i).getMBB() == BB) {
167  start->RemoveOperand(i);
168  start->RemoveOperand(i-1);
169  }
170 
171  start++;
172  }
173 
174  BB->removeSuccessor(BB->succ_begin());
175  }
176  }
177  }
178 
179  // Actually remove the blocks now.
180  for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
181  DeadBlocks[i]->eraseFromParent();
182 
183  // Cleanup PHI nodes.
184  for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
185  MachineBasicBlock *BB = &*I;
186  // Prune unneeded PHI entries.
188  BB->pred_end());
190  while (phi != BB->end() && phi->isPHI()) {
191  for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
192  if (!preds.count(phi->getOperand(i).getMBB())) {
193  phi->RemoveOperand(i);
194  phi->RemoveOperand(i-1);
195  ModifiedPHI = true;
196  }
197 
198  if (phi->getNumOperands() == 3) {
199  const MachineOperand &Input = phi->getOperand(1);
200  const MachineOperand &Output = phi->getOperand(0);
201  unsigned InputReg = Input.getReg();
202  unsigned OutputReg = Output.getReg();
203  assert(Output.getSubReg() == 0 && "Cannot have output subregister");
204  ModifiedPHI = true;
205 
206  if (InputReg != OutputReg) {
208  unsigned InputSub = Input.getSubReg();
209  if (InputSub == 0 &&
210  MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
211  !Input.isUndef()) {
212  MRI.replaceRegWith(OutputReg, InputReg);
213  } else {
214  // The input register to the PHI has a subregister or it can't be
215  // constrained to the proper register class or it is undef:
216  // insert a COPY instead of simply replacing the output
217  // with the input.
219  BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
220  TII->get(TargetOpcode::COPY), OutputReg)
221  .addReg(InputReg, getRegState(Input), InputSub);
222  }
223  phi++->eraseFromParent();
224  }
225  continue;
226  }
227 
228  ++phi;
229  }
230  }
231 
232  F.RenumberBlocks();
233 
234  return (!DeadBlocks.empty() || ModifiedPHI);
235 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them...
iterator end()
Definition: Function.h:590
unsigned getReg() const
getReg - Returns the register number.
unsigned getSubReg() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:238
F(f)
void initializeUnreachableBlockElimLegacyPassPass(PassRegistry &)
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
static bool eliminateUnreachableBlock(Function &F)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
FunctionPass * createUnreachableBlockEliminationPass()
createUnreachableBlockEliminationPass - The LLVM code generator does not work well with unreachable b...
virtual const TargetInstrInfo * getInstrInfo() const
iterator begin()
Definition: Function.h:588
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...
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static bool runOnFunction(Function &F, bool PostInlining)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Represent the analysis usage information of a pass.
void pop_front()
Definition: ilist.h:327
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
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:418
MachineOperand class - Representation of each machine instruction operand.
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.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
#define I(x, y, z)
Definition: MD5.cpp:58
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void dropAllReferences()
Cause all subinstructions to "let go" of all the references that said subinstructions are maintaining...
Definition: BasicBlock.cpp:210
INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim", "Remove unreachable blocks from the CFG", false, false) FunctionPass *llvm
This class contains meta information specific to a module.