LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SimplifyCFGPass.cpp
Go to the documentation of this file.
1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
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 file implements dead code elimination and basic block merging, along
11 // with a collection of other peephole control flow optimizations. For example:
12 //
13 // * Removes basic blocks with no predecessors.
14 // * Merges a basic block into its predecessor if there is only one and the
15 // predecessor only has one successor.
16 // * Eliminates PHI nodes for basic blocks with a single predecessor.
17 // * Eliminates a basic block that only contains an unconditional branch.
18 // * Changes invoke instructions to nounwind functions to be calls.
19 // * Change things like "if (x) if (y)" into "if (x&y)".
20 // * etc..
21 //
22 //===----------------------------------------------------------------------===//
23 
24 #define DEBUG_TYPE "simplifycfg"
25 #include "llvm/Transforms/Scalar.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/Attributes.h"
31 #include "llvm/IR/Constants.h"
32 #include "llvm/IR/DataLayout.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Module.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/CFG.h"
39 using namespace llvm;
40 
41 STATISTIC(NumSimpl, "Number of blocks simplified");
42 
43 namespace {
44 struct CFGSimplifyPass : public FunctionPass {
45  static char ID; // Pass identification, replacement for typeid
46  CFGSimplifyPass() : FunctionPass(ID) {
48  }
49  virtual bool runOnFunction(Function &F);
50 
51  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
53  }
54 };
55 }
56 
57 char CFGSimplifyPass::ID = 0;
58 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
59  false)
61 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
62  false)
63 
64 // Public interface to the CFGSimplification pass
66  return new CFGSimplifyPass();
67 }
68 
69 /// mergeEmptyReturnBlocks - If we have more than one empty (other than phi
70 /// node) return blocks, merge them together to promote recursive block merging.
72  bool Changed = false;
73 
74  BasicBlock *RetBlock = 0;
75 
76  // Scan all the blocks in the function, looking for empty return blocks.
77  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
78  BasicBlock &BB = *BBI++;
79 
80  // Only look at return blocks.
82  if (Ret == 0) continue;
83 
84  // Only look at the block if it is empty or the only other thing in it is a
85  // single PHI node that is the operand to the return.
86  if (Ret != &BB.front()) {
87  // Check for something else in the block.
89  --I;
90  // Skip over debug info.
91  while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
92  --I;
93  if (!isa<DbgInfoIntrinsic>(I) &&
94  (!isa<PHINode>(I) || I != BB.begin() ||
95  Ret->getNumOperands() == 0 ||
96  Ret->getOperand(0) != I))
97  continue;
98  }
99 
100  // If this is the first returning block, remember it and keep going.
101  if (RetBlock == 0) {
102  RetBlock = &BB;
103  continue;
104  }
105 
106  // Otherwise, we found a duplicate return block. Merge the two.
107  Changed = true;
108 
109  // Case when there is no input to the return or when the returned values
110  // agree is trivial. Note that they can't agree if there are phis in the
111  // blocks.
112  if (Ret->getNumOperands() == 0 ||
113  Ret->getOperand(0) ==
114  cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
115  BB.replaceAllUsesWith(RetBlock);
116  BB.eraseFromParent();
117  continue;
118  }
119 
120  // If the canonical return block has no PHI node, create one now.
121  PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
122  if (RetBlockPHI == 0) {
123  Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
124  pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
125  RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
126  std::distance(PB, PE), "merge",
127  &RetBlock->front());
128 
129  for (pred_iterator PI = PB; PI != PE; ++PI)
130  RetBlockPHI->addIncoming(InVal, *PI);
131  RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
132  }
133 
134  // Turn BB into a block that just unconditionally branches to the return
135  // block. This handles the case when the two return blocks have a common
136  // predecessor but that return different things.
137  RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
139  BranchInst::Create(RetBlock, &BB);
140  }
141 
142  return Changed;
143 }
144 
145 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
146 /// iterating until no more changes are made.
148  const DataLayout *TD) {
149  bool Changed = false;
150  bool LocalChange = true;
151  while (LocalChange) {
152  LocalChange = false;
153 
154  // Loop over all of the basic blocks and remove them if they are unneeded...
155  //
156  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
157  if (SimplifyCFG(BBIt++, TTI, TD)) {
158  LocalChange = true;
159  ++NumSimpl;
160  }
161  }
162  Changed |= LocalChange;
163  }
164  return Changed;
165 }
166 
167 // It is possible that we may require multiple passes over the code to fully
168 // simplify the CFG.
169 //
170 bool CFGSimplifyPass::runOnFunction(Function &F) {
171  const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
172  const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
173  bool EverChanged = removeUnreachableBlocks(F);
174  EverChanged |= mergeEmptyReturnBlocks(F);
175  EverChanged |= iterativelySimplifyCFG(F, TTI, TD);
176 
177  // If neither pass changed anything, we're done.
178  if (!EverChanged) return false;
179 
180  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
181  // removeUnreachableBlocks is needed to nuke them, which means we should
182  // iterate between the two optimizations. We structure the code like this to
183  // avoid reruning iterativelySimplifyCFG if the second pass of
184  // removeUnreachableBlocks doesn't do anything.
185  if (!removeUnreachableBlocks(F))
186  return true;
187 
188  do {
189  EverChanged = iterativelySimplifyCFG(F, TTI, TD);
190  EverChanged |= removeUnreachableBlocks(F);
191  } while (EverChanged);
192 
193  return true;
194 }
void addIncoming(Value *V, BasicBlock *BB)
static PassRegistry * getPassRegistry()
iterator end()
Definition: Function.h:397
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:266
unsigned getNumOperands() const
Definition: User.h:108
const Instruction & front() const
Definition: BasicBlock.h:205
F(f)
Simplify the CFG
iterator begin()
Definition: BasicBlock.h:193
AnalysisUsage & addRequired()
Simplify the false
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:172
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=0)
This file contains the simple types necessary to represent the attributes associated with functions a...
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
STATISTIC(NumSimpl,"Number of blocks simplified")
void replaceAllUsesWith(Value *V)
Definition: Value.cpp:303
iterator begin()
Definition: Function.h:395
bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, const DataLayout *TD=0)
simplifycfg
LLVM Basic Block Representation.
Definition: BasicBlock.h:72
Interval::pred_iterator pred_begin(Interval *I)
Definition: Interval.h:117
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=0)
Value * getOperand(unsigned i) const
Definition: User.h:88
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:120
#define INITIALIZE_AG_DEPENDENCY(depName)
Definition: PassSupport.h:169
Type * getType() const
Definition: Value.h:111
void eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:100
void setOperand(unsigned i, Value *Val)
Definition: User.h:92
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, const DataLayout *TD)
FunctionPass * createCFGSimplificationPass()
#define I(x, y, z)
Definition: MD5.cpp:54
TerminatorInst * getTerminator()
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
INITIALIZE_PASS_BEGIN(CFGSimplifyPass,"simplifycfg","Simplify the CFG", false, false) INITIALIZE_PASS_END(CFGSimplifyPass
static bool mergeEmptyReturnBlocks(Function &F)
void initializeCFGSimplifyPassPass(PassRegistry &)
LLVM Value Representation.
Definition: Value.h:66
bool removeUnreachableBlocks(Function &F)
Remove all blocks that can not be reached from the function's entry.
Definition: Local.cpp:1243
INITIALIZE_PASS(GlobalMerge,"global-merge","Global Merge", false, false) bool GlobalMerge const DataLayout * TD