LLVM  9.0.0svn
SimplifyCFGPass.cpp
Go to the documentation of this file.
1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
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 file implements dead code elimination and basic block merging, along
10 // with a collection of other peephole control flow optimizations. For example:
11 //
12 // * Removes basic blocks with no predecessors.
13 // * Merges a basic block into its predecessor if there is only one and the
14 // predecessor only has one successor.
15 // * Eliminates PHI nodes for basic blocks with a single predecessor.
16 // * Eliminates a basic block that only contains an unconditional branch.
17 // * Changes invoke instructions to nounwind functions to be calls.
18 // * Change things like "if (x) if (y)" into "if (x&y)".
19 // * etc..
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Statistic.h"
27 #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"
42 #include <utility>
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "simplifycfg"
46 
48  "bonus-inst-threshold", cl::Hidden, cl::init(1),
49  cl::desc("Control the number of bonus instructions (default = 1)"));
50 
52  "keep-loops", cl::Hidden, cl::init(true),
53  cl::desc("Preserve canonical loop structure (default = true)"));
54 
56  "switch-to-lookup", cl::Hidden, cl::init(false),
57  cl::desc("Convert switches to lookup tables (default = false)"));
58 
60  "forward-switch-cond", cl::Hidden, cl::init(false),
61  cl::desc("Forward switch condition to phi ops (default = false)"));
62 
64  "sink-common-insts", cl::Hidden, cl::init(false),
65  cl::desc("Sink common instructions (default = false)"));
66 
67 
68 STATISTIC(NumSimpl, "Number of blocks simplified");
69 
70 /// If we have more than one empty (other than phi node) return blocks,
71 /// merge them together to promote recursive block merging.
73  bool Changed = false;
74 
75  BasicBlock *RetBlock = nullptr;
76 
77  // Scan all the blocks in the function, looking for empty return blocks.
78  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
79  BasicBlock &BB = *BBI++;
80 
81  // Only look at return blocks.
83  if (!Ret) continue;
84 
85  // Only look at the block if it is empty or the only other thing in it is a
86  // single PHI node that is the operand to the return.
87  if (Ret != &BB.front()) {
88  // Check for something else in the block.
90  --I;
91  // Skip over debug info.
92  while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
93  --I;
94  if (!isa<DbgInfoIntrinsic>(I) &&
95  (!isa<PHINode>(I) || I != BB.begin() || 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) {
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) {
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 /// Call SimplifyCFG on all the blocks in the function,
146 /// iterating until no more changes are made.
148  const SimplifyCFGOptions &Options) {
149  bool Changed = false;
150  bool LocalChange = true;
151 
153  FindFunctionBackedges(F, Edges);
154  SmallPtrSet<BasicBlock *, 16> LoopHeaders;
155  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
156  LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
157 
158  while (LocalChange) {
159  LocalChange = false;
160 
161  // Loop over all of the basic blocks and remove them if they are unneeded.
162  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
163  if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
164  LocalChange = true;
165  ++NumSimpl;
166  }
167  }
168  Changed |= LocalChange;
169  }
170  return Changed;
171 }
172 
174  const SimplifyCFGOptions &Options) {
175  bool EverChanged = removeUnreachableBlocks(F);
176  EverChanged |= mergeEmptyReturnBlocks(F);
177  EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
178 
179  // If neither pass changed anything, we're done.
180  if (!EverChanged) return false;
181 
182  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
183  // removeUnreachableBlocks is needed to nuke them, which means we should
184  // iterate between the two optimizations. We structure the code like this to
185  // avoid rerunning iterativelySimplifyCFG if the second pass of
186  // removeUnreachableBlocks doesn't do anything.
187  if (!removeUnreachableBlocks(F))
188  return true;
189 
190  do {
191  EverChanged = iterativelySimplifyCFG(F, TTI, Options);
192  EverChanged |= removeUnreachableBlocks(F);
193  } while (EverChanged);
194 
195  return true;
196 }
197 
198 // Command-line settings override compile-time settings.
200  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
202  : Opts.BonusInstThreshold;
203  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
205  : Opts.ForwardSwitchCondToPhi;
206  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
209  Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
210  ? UserKeepLoops
211  : Opts.NeedCanonicalLoop;
212  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
214  : Opts.SinkCommonInsts;
215 }
216 
219  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
220  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
221  if (!simplifyFunctionCFG(F, TTI, Options))
222  return PreservedAnalyses::all();
224  PA.preserve<GlobalsAA>();
225  return PA;
226 }
227 
228 namespace {
229 struct CFGSimplifyPass : public FunctionPass {
230  static char ID;
231  SimplifyCFGOptions Options;
232  std::function<bool(const Function &)> PredicateFtor;
233 
234  CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
235  bool ConvertSwitch = false, bool KeepLoops = true,
236  bool SinkCommon = false,
237  std::function<bool(const Function &)> Ftor = nullptr)
238  : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
239 
241 
242  // Check for command-line overrides of options for debug/customization.
243  Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
245  : Threshold;
246 
247  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
249  : ForwardSwitchCond;
250 
251  Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
253  : ConvertSwitch;
254 
255  Options.NeedCanonicalLoop =
256  UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
257 
258  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
260  : SinkCommon;
261  }
262 
263  bool runOnFunction(Function &F) override {
264  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
265  return false;
266 
267  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
268  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
269  return simplifyFunctionCFG(F, TTI, Options);
270  }
271  void getAnalysisUsage(AnalysisUsage &AU) const override {
275  }
276 };
277 }
278 
279 char CFGSimplifyPass::ID = 0;
280 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
281  false)
284 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
285  false)
286 
287 // Public interface to the CFGSimplification pass
288 FunctionPass *
289 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
290  bool ConvertSwitch, bool KeepLoops,
291  bool SinkCommon,
292  std::function<bool(const Function &)> Ftor) {
293  return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
294  KeepLoops, SinkCommon, std::move(Ftor));
295 }
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:67
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:37
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
iterator end()
Definition: Function.h:674
AssumptionCache * AC
Definition: Local.h:69
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:2228
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:137
Simplify the CFG
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
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:50
Definition: BitVector.h:937
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:244
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:65
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
iterator begin()
Definition: Function.h:672
Value * getOperand(unsigned i) const
Definition: User.h:169
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:432
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:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:280
bool ConvertSwitchToLookupTable
Definition: Local.h:66
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:370
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:112
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:284
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
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:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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:837
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:174
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:114
#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:332
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...
void initializeCFGSimplifyPassPass(PassRegistry &)
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:72
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:63
This pass exposes codegen information to IR-level passes.