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 
81 static bool
83  std::vector<DominatorTree::UpdateType> *Updates) {
85 
86  // We don't want to change IR just because we can.
87  // Only do that if there are at least two blocks we'll tail-merge.
88  if (BBs.size() < 2)
89  return false;
90 
91  if (Updates)
92  Updates->reserve(Updates->size() + BBs.size());
93 
94  BasicBlock *CanonicalBB;
95  Instruction *CanonicalTerm;
96  {
97  auto *Term = BBs[0]->getTerminator();
98 
99  // Create a canonical block for this function terminator type now,
100  // placing it *before* the first block that will branch to it.
101  CanonicalBB = BasicBlock::Create(
102  F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
103  // We'll also need a PHI node per each operand of the terminator.
104  NewOps.resize(Term->getNumOperands());
105  for (auto I : zip(Term->operands(), NewOps)) {
106  std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
107  /*NumReservedValues=*/BBs.size(),
108  CanonicalBB->getName() + ".op");
109  CanonicalBB->getInstList().push_back(std::get<1>(I));
110  }
111  // Make it so that this canonical block actually has the right
112  // terminator.
113  CanonicalTerm = Term->clone();
114  CanonicalBB->getInstList().push_back(CanonicalTerm);
115  // If the canonical terminator has operands, rewrite it to take PHI's.
116  for (auto I : zip(NewOps, CanonicalTerm->operands()))
117  std::get<1>(I) = std::get<0>(I);
118  }
119 
120  // Now, go through each block (with the current terminator type)
121  // we've recorded, and rewrite it to branch to the new common block.
122  const DILocation *CommonDebugLoc = nullptr;
123  for (BasicBlock *BB : BBs) {
124  auto *Term = BB->getTerminator();
125  assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&
126  "All blocks to be tail-merged must be the same "
127  "(function-terminating) terminator type.");
128 
129  // Aha, found a new non-canonical function terminator. If it has operands,
130  // forward them to the PHI nodes in the canonical block.
131  for (auto I : zip(Term->operands(), NewOps))
132  std::get<1>(I)->addIncoming(std::get<0>(I), BB);
133 
134  // Compute the debug location common to all the original terminators.
135  if (!CommonDebugLoc)
136  CommonDebugLoc = Term->getDebugLoc();
137  else
138  CommonDebugLoc =
139  DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
140 
141  // And turn BB into a block that just unconditionally branches
142  // to the canonical block.
143  Term->eraseFromParent();
144  BranchInst::Create(CanonicalBB, BB);
145  if (Updates)
146  Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});
147  }
148 
149  CanonicalTerm->setDebugLoc(CommonDebugLoc);
150 
151  return true;
152 }
153 
155  DomTreeUpdater *DTU) {
156  SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
157  Structure;
158 
159  // Scan all the blocks in the function, record the interesting-ones.
160  for (BasicBlock &BB : F) {
161  if (DTU && DTU->isBBPendingDeletion(&BB))
162  continue;
163 
164  // We are only interested in function-terminating blocks.
165  if (!succ_empty(&BB))
166  continue;
167 
168  auto *Term = BB.getTerminator();
169 
170  // Fow now only support `ret`/`resume` function terminators.
171  // FIXME: lift this restriction.
172  switch (Term->getOpcode()) {
173  case Instruction::Ret:
174  case Instruction::Resume:
175  break;
176  default:
177  continue;
178  }
179 
180  // We can't tail-merge block that contains a musttail call.
181  if (BB.getTerminatingMustTailCall())
182  continue;
183 
184  // Calls to experimental_deoptimize must be followed by a return
185  // of the value computed by experimental_deoptimize.
186  // I.e., we can not change `ret` to `br` for this block.
187  if (auto *CI =
188  dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
189  if (Function *F = CI->getCalledFunction())
190  if (Intrinsic::ID ID = F->getIntrinsicID())
191  if (ID == Intrinsic::experimental_deoptimize)
192  continue;
193  }
194 
195  // PHI nodes cannot have token type, so if the terminator has an operand
196  // with token type, we can not tail-merge this kind of function terminators.
197  if (any_of(Term->operands(),
198  [](Value *Op) { return Op->getType()->isTokenTy(); }))
199  continue;
200 
201  // Canonical blocks are uniqued based on the terminator type (opcode).
202  Structure[Term->getOpcode()].emplace_back(&BB);
203  }
204 
205  bool Changed = false;
206 
207  std::vector<DominatorTree::UpdateType> Updates;
208 
209  for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure))
210  Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr);
211 
212  if (DTU)
213  DTU->applyUpdates(Updates);
214 
215  return Changed;
216 }
217 
218 /// Call SimplifyCFG on all the blocks in the function,
219 /// iterating until no more changes are made.
221  DomTreeUpdater *DTU,
222  const SimplifyCFGOptions &Options) {
223  bool Changed = false;
224  bool LocalChange = true;
225 
227  FindFunctionBackedges(F, Edges);
228  SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
229  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
230  UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
231 
232  SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
233  UniqueLoopHeaders.end());
234 
235  unsigned IterCnt = 0;
236  (void)IterCnt;
237  while (LocalChange) {
238  assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");
239  LocalChange = false;
240 
241  // Loop over all of the basic blocks and remove them if they are unneeded.
242  for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
243  BasicBlock &BB = *BBIt++;
244  if (DTU) {
245  assert(
246  !DTU->isBBPendingDeletion(&BB) &&
247  "Should not end up trying to simplify blocks marked for removal.");
248  // Make sure that the advanced iterator does not point at the blocks
249  // that are marked for removal, skip over all such blocks.
250  while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
251  ++BBIt;
252  }
253  if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
254  LocalChange = true;
255  ++NumSimpl;
256  }
257  }
258  Changed |= LocalChange;
259  }
260  return Changed;
261 }
262 
264  DominatorTree *DT,
265  const SimplifyCFGOptions &Options) {
267 
268  bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
269  EverChanged |=
270  tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
271  EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
272 
273  // If neither pass changed anything, we're done.
274  if (!EverChanged) return false;
275 
276  // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
277  // removeUnreachableBlocks is needed to nuke them, which means we should
278  // iterate between the two optimizations. We structure the code like this to
279  // avoid rerunning iterativelySimplifyCFG if the second pass of
280  // removeUnreachableBlocks doesn't do anything.
281  if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
282  return true;
283 
284  do {
285  EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
286  EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
287  } while (EverChanged);
288 
289  return true;
290 }
291 
293  DominatorTree *DT,
294  const SimplifyCFGOptions &Options) {
297  "Original domtree is invalid?");
298 
299  bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
300 
303  "Failed to maintain validity of domtree!");
304 
305  return Changed;
306 }
307 
308 // Command-line settings override compile-time settings.
310  if (UserBonusInstThreshold.getNumOccurrences())
311  Options.BonusInstThreshold = UserBonusInstThreshold;
313  Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
315  Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
317  Options.NeedCanonicalLoop = UserKeepLoops;
319  Options.HoistCommonInsts = UserHoistCommonInsts;
321  Options.SinkCommonInsts = UserSinkCommonInsts;
322 }
323 
326 }
327 
329  : Options(Opts) {
331 }
332 
334  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
335  static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(
336  OS, MapClassName2PassName);
337  OS << "<";
338  OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ";";
339  OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";
340  OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")
341  << "switch-to-lookup;";
342  OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";
343  OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";
344  OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts";
345  OS << ">";
346 }
347 
350  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
351  Options.AC = &AM.getResult<AssumptionAnalysis>(F);
352  DominatorTree *DT = nullptr;
354  DT = &AM.getResult<DominatorTreeAnalysis>(F);
355  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
356  Options.setSimplifyCondBranch(false).setFoldTwoEntryPHINode(false);
357  } else {
358  Options.setSimplifyCondBranch(true).setFoldTwoEntryPHINode(true);
359  }
360  if (!simplifyFunctionCFG(F, TTI, DT, Options))
361  return PreservedAnalyses::all();
365  return PA;
366 }
367 
368 namespace {
369 struct CFGSimplifyPass : public FunctionPass {
370  static char ID;
372  std::function<bool(const Function &)> PredicateFtor;
373 
374  CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
375  std::function<bool(const Function &)> Ftor = nullptr)
376  : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
377 
379 
380  // Check for command-line overrides of options for debug/customization.
382  }
383 
384  bool runOnFunction(Function &F) override {
385  if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
386  return false;
387 
388  Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
389  DominatorTree *DT = nullptr;
391  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
392  if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
393  Options.setSimplifyCondBranch(false)
394  .setFoldTwoEntryPHINode(false);
395  } else {
396  Options.setSimplifyCondBranch(true)
397  .setFoldTwoEntryPHINode(true);
398  }
399 
400  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
401  return simplifyFunctionCFG(F, TTI, DT, Options);
402  }
403  void getAnalysisUsage(AnalysisUsage &AU) const override {
411  }
412 };
413 }
414 
415 char CFGSimplifyPass::ID = 0;
416 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
417  false)
421 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
422  false)
423 
424 // Public interface to the CFGSimplification pass
425 FunctionPass *
427  std::function<bool(const Function &)> Ftor) {
428  return new CFGSimplifyPass(Options, std::move(Ftor));
429 }
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:2420
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
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:220
llvm::SimplifyCFGPass::SimplifyCFGPass
SimplifyCFGPass()
The default constructor sets the pass options to create canonical IR, rather than optimal IR.
Definition: SimplifyCFGPass.cpp:324
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:783
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:62
Pass.h
CFG
Simplify the CFG
Definition: SimplifyCFGPass.cpp:421
llvm::createCFGSimplificationPass
FunctionPass * createCFGSimplificationPass(SimplifyCFGOptions Options=SimplifyCFGOptions(), std::function< bool(const Function &)> Ftor=nullptr)
Definition: SimplifyCFGPass.cpp:426
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1176
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:1592
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:2467
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:55
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:1356
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
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:1302
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:263
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
tailMergeBlocksWithSimilarFunctionTerminators
static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, DomTreeUpdater *DTU)
Definition: SimplifyCFGPass.cpp:154
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:608
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:402
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
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:232
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2476
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:173
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:3148
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
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:1650
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:743
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:6789
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:82
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:1599
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:603
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:333
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:309
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:850
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
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:2699
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:292
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
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:348
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:412
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:633
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)"))
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
simplifycfg
simplifycfg
Definition: SimplifyCFGPass.cpp:421
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:68
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:38