Go to the documentation of this file.
49 #define DEBUG_TYPE "simplifycfg"
53 cl::desc(
"Control the number of bonus instructions (default = 1)"));
57 cl::desc(
"Preserve canonical loop structure (default = true)"));
62 "Convert switches into an integer range comparison (default = false)"));
66 cl::desc(
"Convert switches to lookup tables (default = false)"));
70 cl::desc(
"Forward switch condition to phi ops (default = false)"));
74 cl::desc(
"hoist common instructions (default = false)"));
78 cl::desc(
"Sink common instructions (default = false)"));
81 STATISTIC(NumSimpl,
"Number of blocks simplified");
85 std::vector<DominatorTree::UpdateType> *Updates) {
99 auto *
Term = BBs[0]->getTerminator();
104 F.getContext(),
Twine(
"common.") +
Term->getOpcodeName(), &
F, BBs[0]);
107 for (
auto I :
zip(
Term->operands(), NewOps)) {
110 CanonicalBB->
getName() +
".op");
115 CanonicalTerm =
Term->clone();
116 CanonicalBB->
getInstList().push_back(CanonicalTerm);
119 std::get<1>(
I) = std::get<0>(
I);
126 auto *
Term =
BB->getTerminator();
128 "All blocks to be tail-merged must be the same "
129 "(function-terminating) terminator type.");
133 for (
auto I :
zip(
Term->operands(), NewOps))
134 std::get<1>(
I)->addIncoming(std::get<0>(
I),
BB);
138 CommonDebugLoc =
Term->getDebugLoc();
145 Term->eraseFromParent();
170 auto *
Term =
BB.getTerminator();
174 switch (
Term->getOpcode()) {
176 case Instruction::Resume:
183 if (
BB.getTerminatingMustTailCall())
190 dyn_cast_or_null<CallInst>(
Term->getPrevNonDebugInstruction())) {
191 if (
Function *
F = CI->getCalledFunction())
193 if (
ID == Intrinsic::experimental_deoptimize)
200 [](
Value *
Op) { return Op->getType()->isTokenTy(); }))
204 Structure[
Term->getOpcode()].emplace_back(&
BB);
207 bool Changed =
false;
209 std::vector<DominatorTree::UpdateType> Updates;
225 bool Changed =
false;
226 bool LocalChange =
true;
231 for (
unsigned i = 0,
e = Edges.size();
i !=
e; ++
i)
235 UniqueLoopHeaders.
end());
237 unsigned IterCnt = 0;
239 while (LocalChange) {
240 assert(IterCnt++ < 1000 &&
"Iterative simplification didn't converge!");
249 "Should not end up trying to simplify blocks marked for removal.");
260 Changed |= LocalChange;
276 if (!EverChanged)
return false;
289 }
while (EverChanged);
299 "Original domtree is invalid?");
305 "Failed to maintain validity of domtree!");
340 OS, MapClassName2PassName);
345 <<
"switch-range-to-icmp;";
347 <<
"switch-to-lookup;";
361 if (
F.hasFnAttribute(Attribute::OptForFuzzing)) {
391 if (skipFunction(
F) || (PredicateFtor && !PredicateFtor(
F)))
394 Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
397 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
398 if (
F.hasFnAttribute(Attribute::OptForFuzzing)) {
399 Options.setSimplifyCondBranch(
false)
400 .setFoldTwoEntryPHINode(
false);
402 Options.setSimplifyCondBranch(
true)
403 .setFoldTwoEntryPHINode(
true);
406 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
A set of analyses that are preserved following a run of a transformation pass.
static cl::opt< bool > UserHoistCommonInsts("hoist-common-insts", cl::Hidden, cl::init(false), cl::desc("hoist common instructions (default = false)"))
Analysis pass providing the TargetTransformInfo.
This is an optimization pass for GlobalISel generic memory operations.
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.
SimplifyCFGPass()
The default constructor sets the pass options to create canonical IR, rather than optimal IR.
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.
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...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
SimplifyCFGOptions & setFoldTwoEntryPHINode(bool B)
FunctionPass * createCFGSimplificationPass(SimplifyCFGOptions Options=SimplifyCFGOptions(), std::function< bool(const Function &)> Ftor=nullptr)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
bool ConvertSwitchToLookupTable
static constexpr UpdateKind Insert
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
bool succ_empty(const Instruction *I)
LLVM Basic Block Representation.
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
SimplifyCFGOptions & setSimplifyCondBranch(bool B)
Represent the analysis usage information of a pass.
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 simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)
Legacy analysis pass which computes a DominatorTree.
static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, DomTreeUpdater *DTU)
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
STATISTIC(NumFunctions, "Total number of functions")
This class implements an extremely fast bulk output stream that can only output to a stream.
int getNumOccurrences() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
An efficient, type-erasing, non-owning reference to a callable.
INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, false) INITIALIZE_PASS_END(CFGSimplifyPass
A MapVector that performs no allocations if smaller than a certain size.
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)"))
A function analysis which provides an AssumptionCache.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
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
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
initializer< Ty > init(const Ty &Val)
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
print Print MemDeps of function
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
static cl::opt< unsigned > UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), cl::desc("Control the number of bonus instructions (default = 1)"))
void initializeCFGSimplifyPassPass(PassRegistry &)
bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})
An immutable pass that tracks lazily created AssumptionCache objects.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
static bool performBlockTailMerging(Function &F, ArrayRef< BasicBlock * > BBs, std::vector< DominatorTree::UpdateType > *Updates)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
StringRef - Represent a constant reference to a string, i.e.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool ForwardSwitchCondToPhi
StringRef getName() const
Return a constant reference to the value's name.
cl::opt< bool > RequireAndPreserveDomTree
This function is used to do simplification of a CFG.
static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options)
static cl::opt< bool > UserKeepLoops("keep-loops", cl::Hidden, cl::init(true), cl::desc("Preserve canonical loop structure (default = true)"))
static cl::opt< bool > UserSwitchToLookup("switch-to-lookup", cl::Hidden, cl::init(false), cl::desc("Convert switches to lookup tables (default = false)"))
static bool runOnFunction(Function &F, bool PostInlining)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
bool ConvertSwitchRangeToICmp
Analysis pass which computes a DominatorTree.
const InstListType & getInstList() const
Return the underlying instruction list container.
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)
Legacy wrapper pass to provide the GlobalsAAResult object.
size_t size() const
size - Get the array size.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
A container for analyses that lazily runs them and caches their results.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
FunctionPass class - This class is used to implement most global optimizations.
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
AnalysisUsage & addRequired()
void reserve(size_type N)
static cl::opt< bool > UserSinkCommonInsts("sink-common-insts", cl::Hidden, cl::init(false), cl::desc("Sink common instructions (default = false)"))
LLVM Value Representation.
BasicBlockListType::iterator iterator
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.