LLVM  15.0.0git
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/MapVector.h"
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"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/ValueHandle.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
42 #include "llvm/Transforms/Scalar.h"
46 #include <utility>
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "simplifycfg"
50 
52  "bonus-inst-threshold", cl::Hidden, cl::init(1),
53  cl::desc("Control the number of bonus instructions (default = 1)"));
54 
56  "keep-loops", cl::Hidden, cl::init(true),
57  cl::desc("Preserve canonical loop structure (default = true)"));
58 
60  "switch-range-to-icmp", cl::Hidden, cl::init(false),
61  cl::desc(
62  "Convert switches into an integer range comparison (default = false)"));
63 
65  "switch-to-lookup", cl::Hidden, cl::init(false),
66  cl::desc("Convert switches to lookup tables (default = false)"));
67 
69  "forward-switch-cond", cl::Hidden, cl::init(false),
70  cl::desc("Forward switch condition to phi ops (default = false)"));
71 
73  "hoist-common-insts", cl::Hidden, cl::init(false),
74  cl::desc("hoist common instructions (default = false)"));
75 
77  "sink-common-insts", cl::Hidden, cl::init(false),
78  cl::desc("Sink common instructions (default = false)"));
79 
80 
81 STATISTIC(NumSimpl, "Number of blocks simplified");
82 
83 static bool
85  std::vector<DominatorTree::UpdateType> *Updates) {
87 
88  // We don't want to change IR just because we can.
89  // Only do that if there are at least two blocks we'll tail-merge.
90  if (BBs.size() < 2)
91  return false;
92 
93  if (Updates)
94  Updates->reserve(Updates->size() + BBs.size());
95 
96  BasicBlock *CanonicalBB;
97  Instruction *CanonicalTerm;
98  {
99  auto *Term = BBs[0]->getTerminator();
100 
101  // Create a canonical block for this function terminator type now,
102  // placing it *before* the first block that will branch to it.
103  CanonicalBB = BasicBlock::Create(
104  F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
105  // We'll also need a PHI node per each operand of the terminator.
106  NewOps.resize(Term->getNumOperands());
107  for (auto I : zip(Term->operands(), NewOps)) {
108  std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
109  /*NumReservedValues=*/BBs.size(),
110  CanonicalBB->getName() + ".op");
111  CanonicalBB->getInstList().push_back(std::get<1>(I));
112  }
113  // Make it so that this canonical block actually has the right
114  // terminator.
115  CanonicalTerm = Term->clone();
116  CanonicalBB->getInstList().push_back(CanonicalTerm);
117  // If the canonical terminator has operands, rewrite it to take PHI's.
118  for (auto I : zip(NewOps, CanonicalTerm->operands()))
119  std::get<1>(I) = std::get<0>(I);
120  }
121 
122  // Now, go through each block (with the current terminator type)
123  // we've recorded, and rewrite it to branch to the new common block.
124  const DILocation *CommonDebugLoc = nullptr;
125  for (BasicBlock *BB : BBs) {
126  auto *Term = BB->getTerminator();
127  assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&
128  "All blocks to be tail-merged must be the same "
129  "(function-terminating) terminator type.");
130 
131  // Aha, found a new non-canonical function terminator. If it has operands,
132  // forward them to the PHI nodes in the canonical block.
133  for (auto I : zip(Term->operands(), NewOps))
134  std::get<1>(I)->addIncoming(std::get<0>(I), BB);
135 
136  // Compute the debug location common to all the original terminators.
137  if (!CommonDebugLoc)
138  CommonDebugLoc = Term->getDebugLoc();
139  else
140  CommonDebugLoc =
141  DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
142 
143  // And turn BB into a block that just unconditionally branches
144  // to the canonical block.
145  Term->eraseFromParent();
146  BranchInst::Create(CanonicalBB, BB);
147  if (Updates)
148  Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});
149  }
150 
151  CanonicalTerm->setDebugLoc(CommonDebugLoc);
152 
153  return true;
154 }
155 
157  DomTreeUpdater *DTU) {
158  SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
159  Structure;
160 
161  // Scan all the blocks in the function, record the interesting-ones.
162  for (BasicBlock &BB : F) {
163  if (DTU && DTU->isBBPendingDeletion(&BB))
164  continue;
165 
166  // We are only interested in function-terminating blocks.
167  if (!succ_empty(&BB))
168  continue;
169 
170  auto *Term = BB.getTerminator();
171 
172  // Fow now only support `ret`/`resume` function terminators.
173  // FIXME: lift this restriction.
174  switch (Term->getOpcode()) {
175  case Instruction::Ret:
176  case Instruction::Resume:
177  break;
178  default:
179  continue;
180  }
181 
182  // We can't tail-merge block that contains a musttail call.
183  if (BB.getTerminatingMustTailCall())
184  continue;
185 
186  // Calls to experimental_deoptimize must be followed by a return
187  // of the value computed by experimental_deoptimize.
188  // I.e., we can not change `ret` to `br` for this block.
189  if (auto *CI =
190  dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
191  if (Function *F = CI->getCalledFunction())
192  if (Intrinsic::ID ID = F->getIntrinsicID())
193  if (ID == Intrinsic::experimental_deoptimize)
194  continue;
195  }
196 
197  // PHI nodes cannot have token type, so if the terminator has an operand
198  // with token type, we can not tail-merge this kind of function terminators.
199  if (any_of(Term->operands(),
200  [](Value *Op) { return Op->getType()->isTokenTy(); }))
201  continue;
202 
203  // Canonical blocks are uniqued based on the terminator type (opcode).
204  Structure[Term->getOpcode()].emplace_back(&BB);
205  }
206 
207  bool Changed = false;
208 
209  std::vector<DominatorTree::UpdateType> Updates;
210 
211  for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure))
212  Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr);
213 
214  if (DTU)
215  DTU->applyUpdates(Updates);
216 
217  return Changed;
218 }
219 
220 /// Call SimplifyCFG on all the blocks in the function,
221 /// iterating until no more changes are made.
223  DomTreeUpdater *DTU,
224  const SimplifyCFGOptions &Options) {
225  bool Changed = false;
226  bool LocalChange = true;
227 
229  FindFunctionBackedges(F, Edges);
230  SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
231  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
232  UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
233 
234  SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
235  UniqueLoopHeaders.end());
236 
237  unsigned IterCnt = 0;
238  (void)IterCnt;
239  while (LocalChange) {
240  assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");
241  LocalChange = false;
242 
243  // Loop over all of the basic blocks and remove them if they are unneeded.
244  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
245  BasicBlock &BB = *BBIt++;
246  if (DTU) {
247  assert(
248  !DTU->isBBPendingDeletion(&BB) &&
249  "Should not end up trying to simplify blocks marked for removal.");
250  // Make sure that the advanced iterator does not point at the blocks
251  // that are marked for removal, skip over all such blocks.
252  while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
253  ++BBIt;
254  }
255  if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
256  LocalChange = true;
257  ++NumSimpl;
258  }
259  }
260  Changed |= LocalChange;
261  }
262  return Changed;
263 }
264 
266  DominatorTree *DT,
267  const SimplifyCFGOptions &Options) {
269 
270  bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
271  EverChanged |=
272  tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
273  EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
274 
275  // If neither pass changed anything, we're done.
276  if (!EverChanged) return false;
277 
278  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
279  // removeUnreachableBlocks is needed to nuke them, which means we should
280  // iterate between the two optimizations. We structure the code like this to
281  // avoid rerunning iterativelySimplifyCFG if the second pass of
282  // removeUnreachableBlocks doesn't do anything.
283  if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
284  return true;
285 
286  do {
287  EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
288  EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
289  } while (EverChanged);
290 
291  return true;
292 }
293 
295  DominatorTree *DT,
296  const SimplifyCFGOptions &Options) {
299  "Original domtree is invalid?");
300 
301  bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
302 
305  "Failed to maintain validity of domtree!");
306 
307  return Changed;
308 }
309 
310 // Command-line settings override compile-time settings.
312  if (UserBonusInstThreshold.getNumOccurrences())
313  Options.BonusInstThreshold = UserBonusInstThreshold;
315  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
317  Options.ConvertSwitchRangeToICmp = UserSwitchRangeToICmp;
319  Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
321  Options.NeedCanonicalLoop = UserKeepLoops;
323  Options.HoistCommonInsts = UserHoistCommonInsts;
325  Options.SinkCommonInsts = UserSinkCommonInsts;
326 }
327 
330 }
331 
333  : Options(Opts) {
335 }
336 
338  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
339  static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(
340  OS, MapClassName2PassName);
341  OS << "<";
342  OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ";";
343  OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";
344  OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-")
345  << "switch-range-to-icmp;";
346  OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")
347  << "switch-to-lookup;";
348  OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";
349  OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";
350  OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts";
351  OS << ">";
352 }
353 
356  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
357  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
358  DominatorTree *DT = nullptr;
360  DT = &AM.getResult<DominatorTreeAnalysis>(F);
361  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
362  Options.setSimplifyCondBranch(false).setFoldTwoEntryPHINode(false);
363  } else {
364  Options.setSimplifyCondBranch(true).setFoldTwoEntryPHINode(true);
365  }
366  if (!simplifyFunctionCFG(F, TTI, DT, Options))
367  return PreservedAnalyses::all();
371  return PA;
372 }
373 
374 namespace {
375 struct CFGSimplifyPass : public FunctionPass {
376  static char ID;
378  std::function<bool(const Function &)> PredicateFtor;
379 
380  CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
381  std::function<bool(const Function &)> Ftor = nullptr)
382  : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
383 
385 
386  // Check for command-line overrides of options for debug/customization.
388  }
389 
390  bool runOnFunction(Function &F) override {
391  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
392  return false;
393 
394  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
395  DominatorTree *DT = nullptr;
397  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
398  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
399  Options.setSimplifyCondBranch(false)
400  .setFoldTwoEntryPHINode(false);
401  } else {
402  Options.setSimplifyCondBranch(true)
403  .setFoldTwoEntryPHINode(true);
404  }
405 
406  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
407  return simplifyFunctionCFG(F, TTI, DT, Options);
408  }
409  void getAnalysisUsage(AnalysisUsage &AU) const override {
417  }
418 };
419 }
420 
421 char CFGSimplifyPass::ID = 0;
422 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
423  false)
427 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
428  false)
429 
430 // Public interface to the CFGSimplification pass
431 FunctionPass *
433  std::function<bool(const Function &)> Ftor) {
434  return new CFGSimplifyPass(Options, std::move(Ftor));
435 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
UserHoistCommonInsts
static cl::opt< bool > UserHoistCommonInsts("hoist-common-insts", cl::Hidden, cl::init(false), cl::desc("hoist common instructions (default = false)"))
AssumptionCache.h
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2479
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
iterativelySimplifyCFG
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const SimplifyCFGOptions &Options)
Call SimplifyCFG on all the blocks in the function, iterating until no more changes are made.
Definition: SimplifyCFGPass.cpp:222
llvm::SimplifyCFGPass::SimplifyCFGPass
SimplifyCFGPass()
The default constructor sets the pass options to create canonical IR, rather than optimal IR.
Definition: SimplifyCFGPass.cpp:328
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::FindFunctionBackedges
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:34
IntrinsicInst.h
llvm::DILocation::getMergedLocation
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Definition: DebugInfoMetadata.cpp:101
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
DebugInfoMetadata.h
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::PassInfoMixin< SimplifyCFGPass >
llvm::SimplifyCFGOptions::setFoldTwoEntryPHINode
SimplifyCFGOptions & setFoldTwoEntryPHINode(bool B)
Definition: SimplifyCFGOptions.h:74
llvm::Function
Definition: Function.h:60
Pass.h
CFG
Simplify the CFG
Definition: SimplifyCFGPass.cpp:427
llvm::createCFGSimplificationPass
FunctionPass * createCFGSimplificationPass(SimplifyCFGOptions Options=SimplifyCFGOptions(), std::function< bool(const Function &)> Ftor=nullptr)
Definition: SimplifyCFGPass.cpp:432
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::SimplifyCFGOptions::BonusInstThreshold
int BonusInstThreshold
Definition: SimplifyCFGOptions.h:24
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
MapVector.h
DomTreeUpdater.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::removeUnreachableBlocks
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
Definition: Local.cpp:2485
llvm::SimplifyCFGOptions::ConvertSwitchToLookupTable
bool ConvertSwitchToLookupTable
Definition: SimplifyCFGOptions.h:27
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
llvm::SimplifyCFGOptions::HoistCommonInsts
bool HoistCommonInsts
Definition: SimplifyCFGOptions.h:29
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
CommandLine.h
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1374
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::make_second_range
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
Definition: STLExtras.h:1337
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:167
llvm::SimplifyCFGOptions::setSimplifyCondBranch
SimplifyCFGOptions & setSimplifyCondBranch(bool B)
Definition: SimplifyCFGOptions.h:69
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
UserForwardSwitchCond
static cl::opt< bool > UserForwardSwitchCond("forward-switch-cond", cl::Hidden, cl::init(false), cl::desc("Forward switch condition to phi ops (default = false)"))
llvm::SimplifyCFGOptions::AC
AssumptionCache * AC
Definition: SimplifyCFGOptions.h:34
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
simplifyFunctionCFGImpl
static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)
Definition: SimplifyCFGPass.cpp:265
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
tailMergeBlocksWithSimilarFunctionTerminators
static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, DomTreeUpdater *DTU)
Definition: SimplifyCFGPass.cpp:156
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:619
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:395
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, false) INITIALIZE_PASS_END(CFGSimplifyPass
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
llvm::cl::opt
Definition: CommandLine.h:1392
UserSwitchRangeToICmp
static cl::opt< bool > UserSwitchRangeToICmp("switch-range-to-icmp", cl::Hidden, cl::init(false), cl::desc("Convert switches into an integer range comparison (default = false)"))
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2535
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3142
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:364
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SimplifyCFGOptions::NeedCanonicalLoop
bool NeedCanonicalLoop
Definition: SimplifyCFGOptions.h:28
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1675
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:776
UserBonusInstThreshold
static cl::opt< unsigned > UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), cl::desc("Control the number of bonus instructions (default = 1)"))
llvm::initializeCFGSimplifyPassPass
void initializeCFGSimplifyPassPass(PassRegistry &)
llvm::simplifyCFG
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
Definition: SimplifyCFG.cpp:7206
CFG.h
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
performBlockTailMerging
static bool performBlockTailMerging(Function &F, ArrayRef< BasicBlock * > BBs, std::vector< DominatorTree::UpdateType > *Updates)
Definition: SimplifyCFGPass.cpp:84
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1624
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
Simplify
assume Assume Simplify
Definition: AssumeBundleBuilder.cpp:604
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::SimplifyCFGPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: SimplifyCFGPass.cpp:337
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::SimplifyCFGOptions::ForwardSwitchCondToPhi
bool ForwardSwitchCondToPhi
Definition: SimplifyCFGOptions.h:25
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::RequireAndPreserveDomTree
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
ValueHandle.h
applyCommandLineOverridesToOptions
static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options)
Definition: SimplifyCFGPass.cpp:311
UserKeepLoops
static cl::opt< bool > UserKeepLoops("keep-loops", cl::Hidden, cl::init(true), cl::desc("Preserve canonical loop structure (default = true)"))
UserSwitchToLookup
static cl::opt< bool > UserSwitchToLookup("switch-to-lookup", cl::Hidden, cl::init(false), cl::desc("Convert switches to lookup tables (default = false)"))
Attributes.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
std
Definition: BitVector.h:851
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::PHINode::Create
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...
Definition: Instructions.h:2693
llvm::SimplifyCFGOptions::ConvertSwitchRangeToICmp
bool ConvertSwitchRangeToICmp
Definition: SimplifyCFGOptions.h:26
SimplifyCFGOptions.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:364
llvm::SimplifyCFGOptions
Definition: SimplifyCFGOptions.h:23
Instructions.h
SmallVector.h
Dominators.h
simplifyFunctionCFG
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)
Definition: SimplifyCFGPass.cpp:294
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
TargetTransformInfo.h
llvm::SimplifyCFGOptions::SinkCommonInsts
bool SinkCommonInsts
Definition: SimplifyCFGOptions.h:30
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::SimplifyCFGPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SimplifyCFGPass.cpp:354
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::cl::desc
Definition: CommandLine.h:405
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
SimplifyCFG.h
UserSinkCommonInsts
static cl::opt< bool > UserSinkCommonInsts("sink-common-insts", cl::Hidden, cl::init(false), cl::desc("Sink common instructions (default = false)"))
simplifycfg
simplifycfg
Definition: SimplifyCFGPass.cpp:427
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66
llvm::SmallPtrSetImpl::insert
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:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38