blob: e014f5d1eb042a5361044d9e49d2c5f93cddb021 [file] [log] [blame]
//===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This file implements dead code elimination and basic block merging, along
// with a collection of other peephole control flow optimizations. For example:
// * Removes basic blocks with no predecessors.
// * Merges a basic block into its predecessor if there is only one and the
// predecessor only has one successor.
// * Eliminates PHI nodes for basic blocks with a single predecessor.
// * Eliminates a basic block that only contains an unconditional branch.
// * Changes invoke instructions to nounwind functions to be calls.
// * Change things like "if (x) if (y)" into "if (x&y)".
// * etc..
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/SimplifyCFG.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
#include <utility>
using namespace llvm;
#define DEBUG_TYPE "simplifycfg"
static cl::opt<unsigned> UserBonusInstThreshold(
"bonus-inst-threshold", cl::Hidden, cl::init(1),
cl::desc("Control the number of bonus instructions (default = 1)"));
static cl::opt<bool> UserKeepLoops(
"keep-loops", cl::Hidden, cl::init(true),
cl::desc("Preserve canonical loop structure (default = true)"));
static cl::opt<bool> UserSwitchRangeToICmp(
"switch-range-to-icmp", cl::Hidden, cl::init(false),
"Convert switches into an integer range comparison (default = false)"));
static cl::opt<bool> UserSwitchToLookup(
"switch-to-lookup", cl::Hidden, cl::init(false),
cl::desc("Convert switches to lookup tables (default = false)"));
static cl::opt<bool> UserForwardSwitchCond(
"forward-switch-cond", cl::Hidden, cl::init(false),
cl::desc("Forward switch condition to phi ops (default = false)"));
static cl::opt<bool> UserHoistCommonInsts(
"hoist-common-insts", cl::Hidden, cl::init(false),
cl::desc("hoist common instructions (default = false)"));
static cl::opt<bool> UserSinkCommonInsts(
"sink-common-insts", cl::Hidden, cl::init(false),
cl::desc("Sink common instructions (default = false)"));
STATISTIC(NumSimpl, "Number of blocks simplified");
static bool
performBlockTailMerging(Function &F, ArrayRef<BasicBlock *> BBs,
std::vector<DominatorTree::UpdateType> *Updates) {
SmallVector<PHINode *, 1> NewOps;
// We don't want to change IR just because we can.
// Only do that if there are at least two blocks we'll tail-merge.
if (BBs.size() < 2)
return false;
if (Updates)
Updates->reserve(Updates->size() + BBs.size());
BasicBlock *CanonicalBB;
Instruction *CanonicalTerm;
auto *Term = BBs[0]->getTerminator();
// Create a canonical block for this function terminator type now,
// placing it *before* the first block that will branch to it.
CanonicalBB = BasicBlock::Create(
F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
// We'll also need a PHI node per each operand of the terminator.
for (auto I : zip(Term->operands(), NewOps)) {
std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
CanonicalBB->getName() + ".op");
std::get<1>(I)->insertInto(CanonicalBB, CanonicalBB->end());
// Make it so that this canonical block actually has the right
// terminator.
CanonicalTerm = Term->clone();
CanonicalTerm->insertInto(CanonicalBB, CanonicalBB->end());
// If the canonical terminator has operands, rewrite it to take PHI's.
for (auto I : zip(NewOps, CanonicalTerm->operands()))
std::get<1>(I) = std::get<0>(I);
// Now, go through each block (with the current terminator type)
// we've recorded, and rewrite it to branch to the new common block.
const DILocation *CommonDebugLoc = nullptr;
for (BasicBlock *BB : BBs) {
auto *Term = BB->getTerminator();
assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&
"All blocks to be tail-merged must be the same "
"(function-terminating) terminator type.");
// Aha, found a new non-canonical function terminator. If it has operands,
// forward them to the PHI nodes in the canonical block.
for (auto I : zip(Term->operands(), NewOps))
std::get<1>(I)->addIncoming(std::get<0>(I), BB);
// Compute the debug location common to all the original terminators.
if (!CommonDebugLoc)
CommonDebugLoc = Term->getDebugLoc();
CommonDebugLoc =
DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
// And turn BB into a block that just unconditionally branches
// to the canonical block.
BranchInst::Create(CanonicalBB, BB);
if (Updates)
Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});
return true;
static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F,
DomTreeUpdater *DTU) {
SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
// Scan all the blocks in the function, record the interesting-ones.
for (BasicBlock &BB : F) {
if (DTU && DTU->isBBPendingDeletion(&BB))
// We are only interested in function-terminating blocks.
if (!succ_empty(&BB))
auto *Term = BB.getTerminator();
// Fow now only support `ret`/`resume` function terminators.
// FIXME: lift this restriction.
switch (Term->getOpcode()) {
case Instruction::Ret:
case Instruction::Resume:
// We can't tail-merge block that contains a musttail call.
if (BB.getTerminatingMustTailCall())
// Calls to experimental_deoptimize must be followed by a return
// of the value computed by experimental_deoptimize.
// I.e., we can not change `ret` to `br` for this block.
if (auto *CI =
dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
if (Function *F = CI->getCalledFunction())
if (Intrinsic::ID ID = F->getIntrinsicID())
if (ID == Intrinsic::experimental_deoptimize)
// PHI nodes cannot have token type, so if the terminator has an operand
// with token type, we can not tail-merge this kind of function terminators.
if (any_of(Term->operands(),
[](Value *Op) { return Op->getType()->isTokenTy(); }))
// Canonical blocks are uniqued based on the terminator type (opcode).
bool Changed = false;
std::vector<DominatorTree::UpdateType> Updates;
for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure))
Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr);
if (DTU)
return Changed;
/// Call SimplifyCFG on all the blocks in the function,
/// iterating until no more changes are made.
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
DomTreeUpdater *DTU,
const SimplifyCFGOptions &Options) {
bool Changed = false;
bool LocalChange = true;
SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
FindFunctionBackedges(F, Edges);
SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;
for (unsigned i = 0, e = Edges.size(); i != e; ++i)
UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),
unsigned IterCnt = 0;
while (LocalChange) {
assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");
LocalChange = false;
// Loop over all of the basic blocks and remove them if they are unneeded.
for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
BasicBlock &BB = *BBIt++;
if (DTU) {
!DTU->isBBPendingDeletion(&BB) &&
"Should not end up trying to simplify blocks marked for removal.");
// Make sure that the advanced iterator does not point at the blocks
// that are marked for removal, skip over all such blocks.
while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))
if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {
LocalChange = true;
Changed |= LocalChange;
return Changed;
static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
DominatorTree *DT,
const SimplifyCFGOptions &Options) {
DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
EverChanged |=
tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
// If neither pass changed anything, we're done.
if (!EverChanged) return false;
// iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,
// removeUnreachableBlocks is needed to nuke them, which means we should
// iterate between the two optimizations. We structure the code like this to
// avoid rerunning iterativelySimplifyCFG if the second pass of
// removeUnreachableBlocks doesn't do anything.
if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))
return true;
do {
EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);
} while (EverChanged);
return true;
static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
DominatorTree *DT,
const SimplifyCFGOptions &Options) {
assert((!RequireAndPreserveDomTree ||
(DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
"Original domtree is invalid?");
bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
assert((!RequireAndPreserveDomTree ||
(DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
"Failed to maintain validity of domtree!");
return Changed;
// Command-line settings override compile-time settings.
static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {
if (UserBonusInstThreshold.getNumOccurrences())
Options.BonusInstThreshold = UserBonusInstThreshold;
if (UserForwardSwitchCond.getNumOccurrences())
Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
if (UserSwitchRangeToICmp.getNumOccurrences())
Options.ConvertSwitchRangeToICmp = UserSwitchRangeToICmp;
if (UserSwitchToLookup.getNumOccurrences())
Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
if (UserKeepLoops.getNumOccurrences())
Options.NeedCanonicalLoop = UserKeepLoops;
if (UserHoistCommonInsts.getNumOccurrences())
Options.HoistCommonInsts = UserHoistCommonInsts;
if (UserSinkCommonInsts.getNumOccurrences())
Options.SinkCommonInsts = UserSinkCommonInsts;
SimplifyCFGPass::SimplifyCFGPass() {
SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
: Options(Opts) {
void SimplifyCFGPass::printPipeline(
raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(
OS, MapClassName2PassName);
OS << "<";
OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ";";
OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";
OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-")
<< "switch-range-to-icmp;";
OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")
<< "switch-to-lookup;";
OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";
OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";
OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts";
OS << ">";
PreservedAnalyses SimplifyCFGPass::run(Function &F,
FunctionAnalysisManager &AM) {
auto &TTI = AM.getResult<TargetIRAnalysis>(F);
Options.AC = &AM.getResult<AssumptionAnalysis>(F);
DominatorTree *DT = nullptr;
if (RequireAndPreserveDomTree)
DT = &AM.getResult<DominatorTreeAnalysis>(F);
if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
} else {
if (!simplifyFunctionCFG(F, TTI, DT, Options))
return PreservedAnalyses::all();
PreservedAnalyses PA;
if (RequireAndPreserveDomTree)
return PA;
namespace {
struct CFGSimplifyPass : public FunctionPass {
static char ID;
SimplifyCFGOptions Options;
std::function<bool(const Function &)> PredicateFtor;
CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
std::function<bool(const Function &)> Ftor = nullptr)
: FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
// Check for command-line overrides of options for debug/customization.
bool runOnFunction(Function &F) override {
if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
return false;
Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
DominatorTree *DT = nullptr;
if (RequireAndPreserveDomTree)
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
} else {
auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
return simplifyFunctionCFG(F, TTI, DT, Options);
void getAnalysisUsage(AnalysisUsage &AU) const override {
if (RequireAndPreserveDomTree)
if (RequireAndPreserveDomTree)
char CFGSimplifyPass::ID = 0;
INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
// Public interface to the CFGSimplification pass
FunctionPass *
llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
std::function<bool(const Function &)> Ftor) {
return new CFGSimplifyPass(Options, std::move(Ftor));