LLVM  8.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"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/CFG.h"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/IR/DataLayout.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/Module.h"
39 #include "llvm/Pass.h"
41 #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 
65  "sink-common-insts", cl::Hidden, cl::init(false),
66  cl::desc("Sink common instructions (default = false)"));
67 
68 
69 STATISTIC(NumSimpl, "Number of blocks simplified");
70 
71 /// If we have more than one empty (other than phi node) return blocks,
72 /// merge them together to promote recursive block merging.
74  bool Changed = false;
75 
76  BasicBlock *RetBlock = nullptr;
77 
78  // Scan all the blocks in the function, looking for empty return blocks.
79  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
80  BasicBlock &BB = *BBI++;
81 
82  // Only look at return blocks.
84  if (!Ret) continue;
85 
86  // Only look at the block if it is empty or the only other thing in it is a
87  // single PHI node that is the operand to the return.
88  if (Ret != &BB.front()) {
89  // Check for something else in the block.
91  --I;
92  // Skip over debug info.
93  while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
94  --I;
95  if (!isa<DbgInfoIntrinsic>(I) &&
96  (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
97  Ret->getOperand(0) != &*I))
98  continue;
99  }
100 
101  // If this is the first returning block, remember it and keep going.
102  if (!RetBlock) {
103  RetBlock = &BB;
104  continue;
105  }
106 
107  // Otherwise, we found a duplicate return block. Merge the two.
108  Changed = true;
109 
110  // Case when there is no input to the return or when the returned values
111  // agree is trivial. Note that they can't agree if there are phis in the
112  // blocks.
113  if (Ret->getNumOperands() == 0 ||
114  Ret->getOperand(0) ==
115  cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
116  BB.replaceAllUsesWith(RetBlock);
117  BB.eraseFromParent();
118  continue;
119  }
120 
121  // If the canonical return block has no PHI node, create one now.
122  PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
123  if (!RetBlockPHI) {
124  Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
125  pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
126  RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
127  std::distance(PB, PE), "merge",
128  &RetBlock->front());
129 
130  for (pred_iterator PI = PB; PI != PE; ++PI)
131  RetBlockPHI->addIncoming(InVal, *PI);
132  RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
133  }
134 
135  // Turn BB into a block that just unconditionally branches to the return
136  // block. This handles the case when the two return blocks have a common
137  // predecessor but that return different things.
138  RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
140  BranchInst::Create(RetBlock, &BB);
141  }
142 
143  return Changed;
144 }
145 
146 /// Call SimplifyCFG on all the blocks in the function,
147 /// iterating until no more changes are made.
149  const SimplifyCFGOptions &Options) {
150  bool Changed = false;
151  bool LocalChange = true;
152 
154  FindFunctionBackedges(F, Edges);
155  SmallPtrSet<BasicBlock *, 16> LoopHeaders;
156  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
157  LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
158 
159  while (LocalChange) {
160  LocalChange = false;
161 
162  // Loop over all of the basic blocks and remove them if they are unneeded.
163  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
164  if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
165  LocalChange = true;
166  ++NumSimpl;
167  }
168  }
169  Changed |= LocalChange;
170  }
171  return Changed;
172 }
173 
175  const SimplifyCFGOptions &Options) {
176  bool EverChanged = removeUnreachableBlocks(F);
177  EverChanged |= mergeEmptyReturnBlocks(F);
178  EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
179 
180  // If neither pass changed anything, we're done.
181  if (!EverChanged) return false;
182 
183  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
184  // removeUnreachableBlocks is needed to nuke them, which means we should
185  // iterate between the two optimizations. We structure the code like this to
186  // avoid rerunning iterativelySimplifyCFG if the second pass of
187  // removeUnreachableBlocks doesn't do anything.
188  if (!removeUnreachableBlocks(F))
189  return true;
190 
191  do {
192  EverChanged = iterativelySimplifyCFG(F, TTI, Options);
193  EverChanged |= removeUnreachableBlocks(F);
194  } while (EverChanged);
195 
196  return true;
197 }
198 
199 // Command-line settings override compile-time settings.
201  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
203  : Opts.BonusInstThreshold;
204  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
206  : Opts.ForwardSwitchCondToPhi;
207  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
210  Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
211  ? UserKeepLoops
212  : Opts.NeedCanonicalLoop;
213  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
215  : Opts.SinkCommonInsts;
216 }
217 
220  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
221  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
222  if (!simplifyFunctionCFG(F, TTI, Options))
223  return PreservedAnalyses::all();
225  PA.preserve<GlobalsAA>();
226  return PA;
227 }
228 
229 namespace {
230 struct CFGSimplifyPass : public FunctionPass {
231  static char ID;
232  SimplifyCFGOptions Options;
233  std::function<bool(const Function &)> PredicateFtor;
234 
235  CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
236  bool ConvertSwitch = false, bool KeepLoops = true,
237  bool SinkCommon = false,
238  std::function<bool(const Function &)> Ftor = nullptr)
239  : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
240 
242 
243  // Check for command-line overrides of options for debug/customization.
244  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
246  : Threshold;
247 
248  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
250  : ForwardSwitchCond;
251 
252  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
254  : ConvertSwitch;
255 
256  Options.NeedCanonicalLoop =
257  UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
258 
259  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
261  : SinkCommon;
262  }
263 
264  bool runOnFunction(Function &F) override {
265  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
266  return false;
267 
268  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
269  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
270  return simplifyFunctionCFG(F, TTI, Options);
271  }
272  void getAnalysisUsage(AnalysisUsage &AU) const override {
276  }
277 };
278 }
279 
280 char CFGSimplifyPass::ID = 0;
281 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
282  false)
285 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
286  false)
287 
288 // Public interface to the CFGSimplification pass
289 FunctionPass *
290 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
291  bool ConvertSwitch, bool KeepLoops,
292  bool SinkCommon,
293  std::function<bool(const Function &)> Ftor) {
294  return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
295  KeepLoops, SinkCommon, std::move(Ftor));
296 }
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:68
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:770
This class represents lattice values for constants.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
iterator end()
Definition: Function.h:658
AssumptionCache * AC
Definition: Local.h:71
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:2227
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)
const Instruction * 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:138
Simplify the CFG
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
FunctionPass * createCFGSimplificationPass(unsigned Threshold=1, bool ForwardSwitchCond=false, bool ConvertSwitch=false, bool KeepLoops=true, bool SinkCommon=false, std::function< bool(const Function &)> Ftor=nullptr)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Definition: BitVector.h:938
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
static cl::opt< bool > SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
bool ForwardSwitchCondToPhi
Definition: Local.h:67
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
iterator begin()
Definition: Function.h:656
Value * getOperand(unsigned i) const
Definition: User.h:170
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:419
static cl::opt< bool > UserSinkCommonInsts("sink-common-insts", cl::Hidden, cl::init(false), cl::desc("Sink common instructions (default = false)"))
simplifycfg
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:281
bool ConvertSwitchToLookupTable
Definition: Local.h:68
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:160
size_t size() const
Definition: SmallVector.h:53
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:192
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.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:175
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, const SimplifyCFGOptions &Options)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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:115
#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:175
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...
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:65
This pass exposes codegen information to IR-level passes.