LLVM  6.0.0svn
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 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Analysis/CFG.h"
31 #include "llvm/IR/Attributes.h"
32 #include "llvm/IR/CFG.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DataLayout.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/Pass.h"
40 #include "llvm/Transforms/Scalar.h"
43 #include <utility>
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "simplifycfg"
47 
49  "bonus-inst-threshold", cl::Hidden, cl::init(1),
50  cl::desc("Control the number of bonus instructions (default = 1)"));
51 
53  "keep-loops", cl::Hidden, cl::init(true),
54  cl::desc("Preserve canonical loop structure (default = true)"));
55 
57  "switch-to-lookup", cl::Hidden, cl::init(false),
58  cl::desc("Convert switches to lookup tables (default = false)"));
59 
61  "forward-switch-cond", cl::Hidden, cl::init(false),
62  cl::desc("Forward switch condition to phi ops (default = false)"));
63 
64 STATISTIC(NumSimpl, "Number of blocks simplified");
65 
66 /// If we have more than one empty (other than phi node) return blocks,
67 /// merge them together to promote recursive block merging.
69  bool Changed = false;
70 
71  BasicBlock *RetBlock = nullptr;
72 
73  // Scan all the blocks in the function, looking for empty return blocks.
74  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
75  BasicBlock &BB = *BBI++;
76 
77  // Only look at return blocks.
79  if (!Ret) continue;
80 
81  // Only look at the block if it is empty or the only other thing in it is a
82  // single PHI node that is the operand to the return.
83  if (Ret != &BB.front()) {
84  // Check for something else in the block.
86  --I;
87  // Skip over debug info.
88  while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
89  --I;
90  if (!isa<DbgInfoIntrinsic>(I) &&
91  (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
92  Ret->getOperand(0) != &*I))
93  continue;
94  }
95 
96  // If this is the first returning block, remember it and keep going.
97  if (!RetBlock) {
98  RetBlock = &BB;
99  continue;
100  }
101 
102  // Otherwise, we found a duplicate return block. Merge the two.
103  Changed = true;
104 
105  // Case when there is no input to the return or when the returned values
106  // agree is trivial. Note that they can't agree if there are phis in the
107  // blocks.
108  if (Ret->getNumOperands() == 0 ||
109  Ret->getOperand(0) ==
110  cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
111  BB.replaceAllUsesWith(RetBlock);
112  BB.eraseFromParent();
113  continue;
114  }
115 
116  // If the canonical return block has no PHI node, create one now.
117  PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
118  if (!RetBlockPHI) {
119  Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
120  pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
121  RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
122  std::distance(PB, PE), "merge",
123  &RetBlock->front());
124 
125  for (pred_iterator PI = PB; PI != PE; ++PI)
126  RetBlockPHI->addIncoming(InVal, *PI);
127  RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
128  }
129 
130  // Turn BB into a block that just unconditionally branches to the return
131  // block. This handles the case when the two return blocks have a common
132  // predecessor but that return different things.
133  RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
135  BranchInst::Create(RetBlock, &BB);
136  }
137 
138  return Changed;
139 }
140 
141 /// Call SimplifyCFG on all the blocks in the function,
142 /// iterating until no more changes are made.
144  const SimplifyCFGOptions &Options) {
145  bool Changed = false;
146  bool LocalChange = true;
147 
149  FindFunctionBackedges(F, Edges);
150  SmallPtrSet<BasicBlock *, 16> LoopHeaders;
151  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
152  LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
153 
154  while (LocalChange) {
155  LocalChange = false;
156 
157  // Loop over all of the basic blocks and remove them if they are unneeded.
158  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
159  if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
160  LocalChange = true;
161  ++NumSimpl;
162  }
163  }
164  Changed |= LocalChange;
165  }
166  return Changed;
167 }
168 
170  const SimplifyCFGOptions &Options) {
171  bool EverChanged = removeUnreachableBlocks(F);
172  EverChanged |= mergeEmptyReturnBlocks(F);
173  EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
174 
175  // If neither pass changed anything, we're done.
176  if (!EverChanged) return false;
177 
178  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
179  // removeUnreachableBlocks is needed to nuke them, which means we should
180  // iterate between the two optimizations. We structure the code like this to
181  // avoid rerunning iterativelySimplifyCFG if the second pass of
182  // removeUnreachableBlocks doesn't do anything.
183  if (!removeUnreachableBlocks(F))
184  return true;
185 
186  do {
187  EverChanged = iterativelySimplifyCFG(F, TTI, Options);
188  EverChanged |= removeUnreachableBlocks(F);
189  } while (EverChanged);
190 
191  return true;
192 }
193 
194 // Command-line settings override compile-time settings.
196  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
198  : Opts.BonusInstThreshold;
199  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
201  : Opts.ForwardSwitchCondToPhi;
202  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
205  Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
206  ? UserKeepLoops
207  : Opts.NeedCanonicalLoop;
208 }
209 
212  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
213  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
214  if (!simplifyFunctionCFG(F, TTI, Options))
215  return PreservedAnalyses::all();
217  PA.preserve<GlobalsAA>();
218  return PA;
219 }
220 
221 namespace {
222 struct CFGSimplifyPass : public FunctionPass {
223  static char ID;
224  SimplifyCFGOptions Options;
225  std::function<bool(const Function &)> PredicateFtor;
226 
227  CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
228  bool ConvertSwitch = false, bool KeepLoops = true,
229  std::function<bool(const Function &)> Ftor = nullptr)
230  : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
231 
233 
234  // Check for command-line overrides of options for debug/customization.
235  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
237  : Threshold;
238 
239  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
241  : ForwardSwitchCond;
242 
243  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
245  : ConvertSwitch;
246 
247  Options.NeedCanonicalLoop =
248  UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
249  }
250 
251  bool runOnFunction(Function &F) override {
252  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
253  return false;
254 
255  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
256  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
257  return simplifyFunctionCFG(F, TTI, Options);
258  }
259  void getAnalysisUsage(AnalysisUsage &AU) const override {
263  }
264 };
265 }
266 
267 char CFGSimplifyPass::ID = 0;
268 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
269  false)
272 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
273  false)
274 
275 // Public interface to the CFGSimplification pass
276 FunctionPass *
277 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
278  bool ConvertSwitch, bool KeepLoops,
279  std::function<bool(const Function &)> Ftor) {
280  return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
281  KeepLoops, std::move(Ftor));
282 }
Legacy wrapper pass to provide the GlobalsAAResult object.
This file provides the interface for the pass responsible for both simplifying and canonicalizing the...
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static cl::opt< bool > UserSwitchToLookup("switch-to-lookup", cl::Hidden, cl::init(false), cl::desc("Convert switches to lookup tables (default = false)"))
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
SimplifyCFGPass()
The default constructor sets the pass options to create canonical IR, rather than optimal IR...
Definition: SimplifyCFG.h:38
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
iterator end()
Definition: Function.h:590
FunctionPass * createCFGSimplificationPass(unsigned Threshold=1, bool ForwardSwitchCond=false, bool ConvertSwitch=false, bool KeepLoops=true, std::function< bool(const Function &)> Ftor=nullptr)
AssumptionCache * AC
Definition: Local.h:66
An immutable pass that tracks lazily created AssumptionCache objects.
static cl::opt< unsigned > UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), cl::desc("Control the number of bonus instructions (default = 1)"))
Analysis pass providing the TargetTransformInfo.
STATISTIC(NumFunctions, "Total number of functions")
F(f)
Simplify the CFG
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Definition: BitVector.h:920
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options)
Call SimplifyCFG on all the blocks in the function, iterating until no more changes are made...
This file contains the simple types necessary to represent the attributes associated with functions a...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool ForwardSwitchCondToPhi
Definition: Local.h:63
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
iterator begin()
Definition: Function.h:588
Value * getOperand(unsigned i) const
Definition: User.h:154
static cl::opt< bool > UserForwardSwitchCond("forward-switch-cond", cl::Hidden, cl::init(false), cl::desc("Forward switch condition to phi ops (default = false)"))
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
simplifycfg
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:264
bool ConvertSwitchToLookupTable
Definition: Local.h:64
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
A function analysis which provides an AssumptionCache.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:176
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:1730
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options)
INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, false) INITIALIZE_PASS_END(CFGSimplifyPass
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static cl::opt< bool > UserKeepLoops("keep-loops", cl::Hidden, cl::init(true), cl::desc("Preserve canonical loop structure (default = true)"))
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock *> > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them...
Definition: CFG.cpp:27
static bool mergeEmptyReturnBlocks(Function &F)
If we have more than one empty (other than phi node) return blocks, merge them together to promote re...
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
void initializeCFGSimplifyPassPass(PassRegistry &)
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:73
print Print MemDeps of function
A container for analyses that lazily runs them and caches their results.
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options={}, SmallPtrSetImpl< BasicBlock *> *LoopHeaders=nullptr)
This function is used to do simplification of a CFG.
A set of parameters used to control the transforms in the SimplifyCFG pass.
Definition: Local.h:61
This pass exposes codegen information to IR-level passes.
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120