LLVM  14.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"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/IR/DataLayout.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/IntrinsicInst.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/ValueHandle.h"
41 #include "llvm/InitializePasses.h"
42 #include "llvm/Pass.h"
44 #include "llvm/Transforms/Scalar.h"
49 #include <utility>
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "simplifycfg"
53 
55  "bonus-inst-threshold", cl::Hidden, cl::init(1),
56  cl::desc("Control the number of bonus instructions (default = 1)"));
57 
59  "keep-loops", cl::Hidden, cl::init(true),
60  cl::desc("Preserve canonical loop structure (default = true)"));
61 
63  "switch-to-lookup", cl::Hidden, cl::init(false),
64  cl::desc("Convert switches to lookup tables (default = false)"));
65 
67  "forward-switch-cond", cl::Hidden, cl::init(false),
68  cl::desc("Forward switch condition to phi ops (default = false)"));
69 
71  "hoist-common-insts", cl::Hidden, cl::init(false),
72  cl::desc("hoist common instructions (default = false)"));
73 
75  "sink-common-insts", cl::Hidden, cl::init(false),
76  cl::desc("Sink common instructions (default = false)"));
77 
78 
79 STATISTIC(NumSimpl, "Number of blocks simplified");
80 
82  DomTreeUpdater *DTU) {
83  SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
84  Structure;
85 
86  // Scan all the blocks in the function, record the interesting-ones.
87  for (BasicBlock &BB : F) {
88  if (DTU && DTU->isBBPendingDeletion(&BB))
89  continue;
90 
91  // We are only interested in function-terminating blocks.
92  if (!succ_empty(&BB))
93  continue;
94 
95  auto *Term = BB.getTerminator();
96 
97  // Fow now only support `ret`/`resume` function terminators.
98  // FIXME: lift this restriction.
99  switch (Term->getOpcode()) {
100  case Instruction::Ret:
101  case Instruction::Resume:
102  break;
103  default:
104  continue;
105  }
106 
107  // We can't tail-merge block that contains a musttail call.
108  if (BB.getTerminatingMustTailCall())
109  continue;
110 
111  // Calls to experimental_deoptimize must be followed by a return
112  // of the value computed by experimental_deoptimize.
113  // I.e., we can not change `ret` to `br` for this block.
114  if (auto *CI =
115  dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
116  if (Function *F = CI->getCalledFunction())
117  if (Intrinsic::ID ID = F->getIntrinsicID())
118  if (ID == Intrinsic::experimental_deoptimize)
119  continue;
120  }
121 
122  // PHI nodes cannot have token type, so if the terminator has an operand
123  // with token type, we can not tail-merge this kind of function terminators.
124  if (any_of(Term->operands(),
125  [](Value *Op) { return Op->getType()->isTokenTy(); }))
126  continue;
127 
128  // Canonical blocks are uniqued based on the terminator type (opcode).
129  Structure[Term->getOpcode()].emplace_back(&BB);
130  }
131 
132  bool Changed = false;
133 
134  std::vector<DominatorTree::UpdateType> Updates;
135 
136  for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure)) {
138 
139  // We don't want to change IR just because we can.
140  // Only do that if there are at least two blocks we'll tail-merge.
141  if (BBs.size() < 2)
142  continue;
143 
144  Changed = true;
145 
146  if (DTU)
147  Updates.reserve(Updates.size() + BBs.size());
148 
149  BasicBlock *CanonicalBB;
150  Instruction *CanonicalTerm;
151  {
152  auto *Term = BBs[0]->getTerminator();
153 
154  // Create a canonical block for this function terminator type now,
155  // placing it *before* the first block that will branch to it.
156  CanonicalBB = BasicBlock::Create(
157  F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
158  // We'll also need a PHI node per each operand of the terminator.
159  NewOps.resize(Term->getNumOperands());
160  for (auto I : zip(Term->operands(), NewOps)) {
161  std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
162  /*NumReservedValues=*/BBs.size(),
163  CanonicalBB->getName() + ".op");
164  CanonicalBB->getInstList().push_back(std::get<1>(I));
165  }
166  // Make it so that this canonical block actually has the right
167  // terminator.
168  CanonicalTerm = Term->clone();
169  CanonicalBB->getInstList().push_back(CanonicalTerm);
170  // If the canonical terminator has operands, rewrite it to take PHI's.
171  for (auto I : zip(NewOps, CanonicalTerm->operands()))
172  std::get<1>(I) = std::get<0>(I);
173  }
174 
175  // Now, go through each block (with the current terminator type)
176  // we've recorded, and rewrite it to branch to the new common block.
177  const DILocation *CommonDebugLoc = nullptr;
178  for (BasicBlock *BB : BBs) {
179  auto *Term = BB->getTerminator();
180 
181  // Aha, found a new non-canonical function terminator. If it has operands,
182  // forward them to the PHI nodes in the canonical block.
183  for (auto I : zip(Term->operands(), NewOps))
184  std::get<1>(I)->addIncoming(std::get<0>(I), BB);
185 
186  // Compute the debug location common to all the original terminators.
187  if (!CommonDebugLoc)
188  CommonDebugLoc = Term->getDebugLoc();
189  else
190  CommonDebugLoc =
191  DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
192 
193  // And turn BB into a block that just unconditionally branches
194  // to the canonical block.
195  Term->eraseFromParent();
196  BranchInst::Create(CanonicalBB, BB);
197  if (DTU)
198  Updates.push_back({DominatorTree::Insert, BB, CanonicalBB});
199  }
200 
201  CanonicalTerm->setDebugLoc(CommonDebugLoc);
202  }
203 
204  if (DTU)
205  DTU->applyUpdates(Updates);
206 
207  return Changed;
208 }
209 
210 /// Call SimplifyCFG on all the blocks in the function,
211 /// iterating until no more changes are made.
213  DomTreeUpdater *DTU,
214  const SimplifyCFGOptions &Options) {
215  bool Changed = false;
216  bool LocalChange = true;
217 
219  FindFunctionBackedges(F, Edges);
220  SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
221  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
222  UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
223 
224  SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
225  UniqueLoopHeaders.end());
226 
227  while (LocalChange) {
228  LocalChange = false;
229 
230  // Loop over all of the basic blocks and remove them if they are unneeded.
231  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
232  BasicBlock &BB = *BBIt++;
233  if (DTU) {
234  assert(
235  !DTU->isBBPendingDeletion(&BB) &&
236  "Should not end up trying to simplify blocks marked for removal.");
237  // Make sure that the advanced iterator does not point at the blocks
238  // that are marked for removal, skip over all such blocks.
239  while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
240  ++BBIt;
241  }
242  if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
243  LocalChange = true;
244  ++NumSimpl;
245  }
246  }
247  Changed |= LocalChange;
248  }
249  return Changed;
250 }
251 
253  DominatorTree *DT,
254  const SimplifyCFGOptions &Options) {
256 
257  bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
258  EverChanged |=
259  tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
260  EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
261 
262  // If neither pass changed anything, we're done.
263  if (!EverChanged) return false;
264 
265  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
266  // removeUnreachableBlocks is needed to nuke them, which means we should
267  // iterate between the two optimizations. We structure the code like this to
268  // avoid rerunning iterativelySimplifyCFG if the second pass of
269  // removeUnreachableBlocks doesn't do anything.
270  if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
271  return true;
272 
273  do {
274  EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
275  EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
276  } while (EverChanged);
277 
278  return true;
279 }
280 
282  DominatorTree *DT,
283  const SimplifyCFGOptions &Options) {
286  "Original domtree is invalid?");
287 
288  bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
289 
292  "Failed to maintain validity of domtree!");
293 
294  return Changed;
295 }
296 
297 // Command-line settings override compile-time settings.
299  if (UserBonusInstThreshold.getNumOccurrences())
300  Options.BonusInstThreshold = UserBonusInstThreshold;
302  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
304  Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
306  Options.NeedCanonicalLoop = UserKeepLoops;
308  Options.HoistCommonInsts = UserHoistCommonInsts;
310  Options.SinkCommonInsts = UserSinkCommonInsts;
311 }
312 
315 }
316 
318  : Options(Opts) {
320 }
321 
323  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
324  static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(
325  OS, MapClassName2PassName);
326  OS << "<";
327  OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ";";
328  OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";
329  OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")
330  << "switch-to-lookup;";
331  OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";
332  OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";
333  OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts";
334  OS << ">";
335 }
336 
339  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
340  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
341  DominatorTree *DT = nullptr;
343  DT = &AM.getResult<DominatorTreeAnalysis>(F);
344  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
345  Options.setSimplifyCondBranch(false).setFoldTwoEntryPHINode(false);
346  } else {
347  Options.setSimplifyCondBranch(true).setFoldTwoEntryPHINode(true);
348  }
349  if (!simplifyFunctionCFG(F, TTI, DT, Options))
350  return PreservedAnalyses::all();
354  return PA;
355 }
356 
357 namespace {
358 struct CFGSimplifyPass : public FunctionPass {
359  static char ID;
361  std::function<bool(const Function &)> PredicateFtor;
362 
363  CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
364  std::function<bool(const Function &)> Ftor = nullptr)
365  : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
366 
368 
369  // Check for command-line overrides of options for debug/customization.
371  }
372 
373  bool runOnFunction(Function &F) override {
374  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
375  return false;
376 
377  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
378  DominatorTree *DT = nullptr;
380  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
381  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
382  Options.setSimplifyCondBranch(false)
383  .setFoldTwoEntryPHINode(false);
384  } else {
385  Options.setSimplifyCondBranch(true)
386  .setFoldTwoEntryPHINode(true);
387  }
388 
389  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
390  return simplifyFunctionCFG(F, TTI, DT, Options);
391  }
392  void getAnalysisUsage(AnalysisUsage &AU) const override {
400  }
401 };
402 }
403 
404 char CFGSimplifyPass::ID = 0;
405 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
406  false)
410 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
411  false)
412 
413 // Public interface to the CFGSimplification pass
414 FunctionPass *
416  std::function<bool(const Function &)> Ftor) {
417  return new CFGSimplifyPass(Options, std::move(Ftor));
418 }
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:155
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:2331
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:212
llvm::SimplifyCFGPass::SimplifyCFGPass
SimplifyCFGPass()
The default constructor sets the pass options to create canonical IR, rather than optimal IR.
Definition: SimplifyCFGPass.cpp:313
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:100
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:779
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:230
llvm::PassInfoMixin< SimplifyCFGPass >
llvm::SimplifyCFGOptions::setFoldTwoEntryPHINode
SimplifyCFGOptions & setFoldTwoEntryPHINode(bool B)
Definition: SimplifyCFGOptions.h:69
llvm::Function
Definition: Function.h:61
Pass.h
CFG
Simplify the CFG
Definition: SimplifyCFGPass.cpp:410
llvm::createCFGSimplificationPass
FunctionPass * createCFGSimplificationPass(SimplifyCFGOptions Options=SimplifyCFGOptions(), std::function< bool(const Function &)> Ftor=nullptr)
Definition: SimplifyCFGPass.cpp:415
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:151
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
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:2459
Module.h
llvm::SimplifyCFGOptions::ConvertSwitchToLookupTable
bool ConvertSwitchToLookupTable
Definition: SimplifyCFGOptions.h:26
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:449
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:256
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
llvm::SimplifyCFGOptions::HoistCommonInsts
bool HoistCommonInsts
Definition: SimplifyCFGOptions.h:28
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:1335
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:1264
Constants.h
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:166
llvm::SimplifyCFGOptions::setSimplifyCondBranch
SimplifyCFGOptions & setSimplifyCondBranch(bool B)
Definition: SimplifyCFGOptions.h:64
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:33
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
simplifyFunctionCFGImpl
static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)
Definition: SimplifyCFGPass.cpp:252
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
tailMergeBlocksWithSimilarFunctionTerminators
static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, DomTreeUpdater *DTU)
Definition: SimplifyCFGPass.cpp:81
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:53
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:404
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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: STLExtras.h:168
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:232
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2387
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
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:3124
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SimplifyCFGOptions::NeedCanonicalLoop
bool NeedCanonicalLoop
Definition: SimplifyCFGOptions.h:27
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:1609
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
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:736
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:6765
CFG.h
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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:1558
DataLayout.h
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:322
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
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:309
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:298
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:838
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:2675
SimplifyCFGOptions.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
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:281
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
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:29
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::SimplifyCFGPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SimplifyCFGPass.cpp:337
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:414
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
BasicBlockUtils.h
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:410
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:67
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37