444 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements dead code elimination and basic block merging, along10// 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 the14// 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"27#include "llvm/Analysis/AssumptionCache.h"28#include "llvm/Analysis/CFG.h"29#include "llvm/Analysis/DomTreeUpdater.h"30#include "llvm/Analysis/GlobalsModRef.h"31#include "llvm/Analysis/TargetTransformInfo.h"32#include "llvm/IR/Attributes.h"33#include "llvm/IR/CFG.h"34#include "llvm/IR/Dominators.h"35#include "llvm/IR/Instructions.h"36#include "llvm/IR/ValueHandle.h"37#include "llvm/InitializePasses.h"38#include "llvm/Pass.h"39#include "llvm/Support/CommandLine.h"40#include "llvm/Transforms/Scalar.h"41#include "llvm/Transforms/Scalar/SimplifyCFG.h"42#include "llvm/Transforms/Utils/Local.h"43#include "llvm/Transforms/Utils/SimplifyCFGOptions.h"44#include <utility>45using namespace llvm;46 47#define DEBUG_TYPE "simplifycfg"48 49static cl::opt<unsigned> UserBonusInstThreshold(50 "bonus-inst-threshold", cl::Hidden, cl::init(1),51 cl::desc("Control the number of bonus instructions (default = 1)"));52 53static cl::opt<bool> UserKeepLoops(54 "keep-loops", cl::Hidden, cl::init(true),55 cl::desc("Preserve canonical loop structure (default = true)"));56 57static cl::opt<bool> UserSwitchRangeToICmp(58 "switch-range-to-icmp", cl::Hidden, cl::init(false),59 cl::desc(60 "Convert switches into an integer range comparison (default = false)"));61 62static cl::opt<bool> UserSwitchToLookup(63 "switch-to-lookup", cl::Hidden, cl::init(false),64 cl::desc("Convert switches to lookup tables (default = false)"));65 66static cl::opt<bool> UserForwardSwitchCond(67 "forward-switch-cond", cl::Hidden, cl::init(false),68 cl::desc("Forward switch condition to phi ops (default = false)"));69 70static cl::opt<bool> UserHoistCommonInsts(71 "hoist-common-insts", cl::Hidden, cl::init(false),72 cl::desc("hoist common instructions (default = false)"));73 74static cl::opt<bool> UserHoistLoadsStoresWithCondFaulting(75 "hoist-loads-stores-with-cond-faulting", cl::Hidden, cl::init(false),76 cl::desc("Hoist loads/stores if the target supports conditional faulting "77 "(default = false)"));78 79static cl::opt<bool> UserSinkCommonInsts(80 "sink-common-insts", cl::Hidden, cl::init(false),81 cl::desc("Sink common instructions (default = false)"));82 83static cl::opt<bool> UserSpeculateUnpredictables(84 "speculate-unpredictables", cl::Hidden, cl::init(false),85 cl::desc("Speculate unpredictable branches (default = false)"));86 87STATISTIC(NumSimpl, "Number of blocks simplified");88 89static bool90performBlockTailMerging(Function &F, ArrayRef<BasicBlock *> BBs,91 std::vector<DominatorTree::UpdateType> *Updates) {92 SmallVector<PHINode *, 1> NewOps;93 94 // We don't want to change IR just because we can.95 // Only do that if there are at least two blocks we'll tail-merge.96 if (BBs.size() < 2)97 return false;98 99 if (Updates)100 Updates->reserve(Updates->size() + BBs.size());101 102 BasicBlock *CanonicalBB;103 Instruction *CanonicalTerm;104 {105 auto *Term = BBs[0]->getTerminator();106 107 // Create a canonical block for this function terminator type now,108 // placing it *before* the first block that will branch to it.109 CanonicalBB = BasicBlock::Create(110 F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);111 // We'll also need a PHI node per each operand of the terminator.112 NewOps.resize(Term->getNumOperands());113 for (auto I : zip(Term->operands(), NewOps)) {114 std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),115 /*NumReservedValues=*/BBs.size(),116 CanonicalBB->getName() + ".op");117 std::get<1>(I)->insertInto(CanonicalBB, CanonicalBB->end());118 }119 // Make it so that this canonical block actually has the right120 // terminator.121 CanonicalTerm = Term->clone();122 CanonicalTerm->insertInto(CanonicalBB, CanonicalBB->end());123 // If the canonical terminator has operands, rewrite it to take PHI's.124 for (auto I : zip(NewOps, CanonicalTerm->operands()))125 std::get<1>(I) = std::get<0>(I);126 }127 128 // Now, go through each block (with the current terminator type)129 // we've recorded, and rewrite it to branch to the new common block.130 DebugLoc CommonDebugLoc;131 for (BasicBlock *BB : BBs) {132 auto *Term = BB->getTerminator();133 assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&134 "All blocks to be tail-merged must be the same "135 "(function-terminating) terminator type.");136 137 // Aha, found a new non-canonical function terminator. If it has operands,138 // forward them to the PHI nodes in the canonical block.139 for (auto I : zip(Term->operands(), NewOps))140 std::get<1>(I)->addIncoming(std::get<0>(I), BB);141 142 // Compute the debug location common to all the original terminators.143 if (!CommonDebugLoc)144 CommonDebugLoc = Term->getDebugLoc();145 else146 CommonDebugLoc =147 DebugLoc::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());148 149 // And turn BB into a block that just unconditionally branches150 // to the canonical block.151 Instruction *BI = BranchInst::Create(CanonicalBB, BB);152 BI->setDebugLoc(Term->getDebugLoc());153 Term->eraseFromParent();154 155 if (Updates)156 Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});157 }158 159 CanonicalTerm->setDebugLoc(CommonDebugLoc);160 161 return true;162}163 164static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F,165 DomTreeUpdater *DTU) {166 SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>167 Structure;168 169 // Scan all the blocks in the function, record the interesting-ones.170 for (BasicBlock &BB : F) {171 if (DTU && DTU->isBBPendingDeletion(&BB))172 continue;173 174 // We are only interested in function-terminating blocks.175 if (!succ_empty(&BB))176 continue;177 178 auto *Term = BB.getTerminator();179 180 // Fow now only support `ret`/`resume` function terminators.181 // FIXME: lift this restriction.182 switch (Term->getOpcode()) {183 case Instruction::Ret:184 case Instruction::Resume:185 break;186 default:187 continue;188 }189 190 // We can't tail-merge block that contains a musttail call.191 if (BB.getTerminatingMustTailCall())192 continue;193 194 // Calls to experimental_deoptimize must be followed by a return195 // of the value computed by experimental_deoptimize.196 // I.e., we can not change `ret` to `br` for this block.197 if (auto *CI = dyn_cast_or_null<CallInst>(Term->getPrevNode())) {198 if (Function *F = CI->getCalledFunction())199 if (Intrinsic::ID ID = F->getIntrinsicID())200 if (ID == Intrinsic::experimental_deoptimize)201 continue;202 }203 204 // PHI nodes cannot have token type, so if the terminator has an operand205 // with token type, we can not tail-merge this kind of function terminators.206 if (any_of(Term->operands(),207 [](Value *Op) { return Op->getType()->isTokenTy(); }))208 continue;209 210 // Canonical blocks are uniqued based on the terminator type (opcode).211 Structure[Term->getOpcode()].emplace_back(&BB);212 }213 214 bool Changed = false;215 216 std::vector<DominatorTree::UpdateType> Updates;217 218 for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure))219 Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr);220 221 if (DTU)222 DTU->applyUpdates(Updates);223 224 return Changed;225}226 227/// Call SimplifyCFG on all the blocks in the function,228/// iterating until no more changes are made.229static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,230 DomTreeUpdater *DTU,231 const SimplifyCFGOptions &Options) {232 bool Changed = false;233 bool LocalChange = true;234 235 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;236 FindFunctionBackedges(F, Edges);237 SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders;238 for (const auto &Edge : Edges)239 UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edge.second));240 241 SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(),242 UniqueLoopHeaders.end());243 244 unsigned IterCnt = 0;245 (void)IterCnt;246 while (LocalChange) {247 assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");248 LocalChange = false;249 250 // Loop over all of the basic blocks and remove them if they are unneeded.251 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {252 BasicBlock &BB = *BBIt++;253 if (DTU) {254 assert(255 !DTU->isBBPendingDeletion(&BB) &&256 "Should not end up trying to simplify blocks marked for removal.");257 // Make sure that the advanced iterator does not point at the blocks258 // that are marked for removal, skip over all such blocks.259 while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt))260 ++BBIt;261 }262 if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) {263 LocalChange = true;264 ++NumSimpl;265 }266 }267 Changed |= LocalChange;268 }269 return Changed;270}271 272static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,273 DominatorTree *DT,274 const SimplifyCFGOptions &Options) {275 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);276 277 bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);278 EverChanged |=279 tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);280 EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);281 282 // If neither pass changed anything, we're done.283 if (!EverChanged) return false;284 285 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens,286 // removeUnreachableBlocks is needed to nuke them, which means we should287 // iterate between the two optimizations. We structure the code like this to288 // avoid rerunning iterativelySimplifyCFG if the second pass of289 // removeUnreachableBlocks doesn't do anything.290 if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr))291 return true;292 293 do {294 EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);295 EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr);296 } while (EverChanged);297 298 return true;299}300 301static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,302 DominatorTree *DT,303 const SimplifyCFGOptions &Options) {304 assert((!RequireAndPreserveDomTree ||305 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&306 "Original domtree is invalid?");307 308 bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);309 310 assert((!RequireAndPreserveDomTree ||311 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&312 "Failed to maintain validity of domtree!");313 314 return Changed;315}316 317// Command-line settings override compile-time settings.318static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {319 if (UserBonusInstThreshold.getNumOccurrences())320 Options.BonusInstThreshold = UserBonusInstThreshold;321 if (UserForwardSwitchCond.getNumOccurrences())322 Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;323 if (UserSwitchRangeToICmp.getNumOccurrences())324 Options.ConvertSwitchRangeToICmp = UserSwitchRangeToICmp;325 if (UserSwitchToLookup.getNumOccurrences())326 Options.ConvertSwitchToLookupTable = UserSwitchToLookup;327 if (UserKeepLoops.getNumOccurrences())328 Options.NeedCanonicalLoop = UserKeepLoops;329 if (UserHoistCommonInsts.getNumOccurrences())330 Options.HoistCommonInsts = UserHoistCommonInsts;331 if (UserHoistLoadsStoresWithCondFaulting.getNumOccurrences())332 Options.HoistLoadsStoresWithCondFaulting =333 UserHoistLoadsStoresWithCondFaulting;334 if (UserSinkCommonInsts.getNumOccurrences())335 Options.SinkCommonInsts = UserSinkCommonInsts;336 if (UserSpeculateUnpredictables.getNumOccurrences())337 Options.SpeculateUnpredictables = UserSpeculateUnpredictables;338}339 340SimplifyCFGPass::SimplifyCFGPass() {341 applyCommandLineOverridesToOptions(Options);342}343 344SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)345 : Options(Opts) {346 applyCommandLineOverridesToOptions(Options);347}348 349void SimplifyCFGPass::printPipeline(350 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {351 static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline(352 OS, MapClassName2PassName);353 OS << '<';354 OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ';';355 OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";356 OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-")357 << "switch-range-to-icmp;";358 OS << (Options.ConvertSwitchToArithmetic ? "" : "no-")359 << "switch-to-arithmetic;";360 OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")361 << "switch-to-lookup;";362 OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";363 OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";364 OS << (Options.HoistLoadsStoresWithCondFaulting ? "" : "no-")365 << "hoist-loads-stores-with-cond-faulting;";366 OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts;";367 OS << (Options.SpeculateBlocks ? "" : "no-") << "speculate-blocks;";368 OS << (Options.SimplifyCondBranch ? "" : "no-") << "simplify-cond-branch;";369 OS << (Options.SpeculateUnpredictables ? "" : "no-")370 << "speculate-unpredictables";371 OS << '>';372}373 374PreservedAnalyses SimplifyCFGPass::run(Function &F,375 FunctionAnalysisManager &AM) {376 auto &TTI = AM.getResult<TargetIRAnalysis>(F);377 Options.AC = &AM.getResult<AssumptionAnalysis>(F);378 DominatorTree *DT = nullptr;379 if (RequireAndPreserveDomTree)380 DT = &AM.getResult<DominatorTreeAnalysis>(F);381 if (!simplifyFunctionCFG(F, TTI, DT, Options))382 return PreservedAnalyses::all();383 PreservedAnalyses PA;384 if (RequireAndPreserveDomTree)385 PA.preserve<DominatorTreeAnalysis>();386 return PA;387}388 389namespace {390struct CFGSimplifyPass : public FunctionPass {391 static char ID;392 SimplifyCFGOptions Options;393 std::function<bool(const Function &)> PredicateFtor;394 395 CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),396 std::function<bool(const Function &)> Ftor = nullptr)397 : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {398 399 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());400 401 // Check for command-line overrides of options for debug/customization.402 applyCommandLineOverridesToOptions(Options);403 }404 405 bool runOnFunction(Function &F) override {406 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))407 return false;408 409 Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);410 DominatorTree *DT = nullptr;411 if (RequireAndPreserveDomTree)412 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();413 414 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);415 return simplifyFunctionCFG(F, TTI, DT, Options);416 }417 void getAnalysisUsage(AnalysisUsage &AU) const override {418 AU.addRequired<AssumptionCacheTracker>();419 if (RequireAndPreserveDomTree)420 AU.addRequired<DominatorTreeWrapperPass>();421 AU.addRequired<TargetTransformInfoWrapperPass>();422 if (RequireAndPreserveDomTree)423 AU.addPreserved<DominatorTreeWrapperPass>();424 AU.addPreserved<GlobalsAAWrapperPass>();425 }426};427}428 429char CFGSimplifyPass::ID = 0;430INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,431 false)432INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)433INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)434INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)435INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,436 false)437 438// Public interface to the CFGSimplification pass439FunctionPass *440llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,441 std::function<bool(const Function &)> Ftor) {442 return new CFGSimplifyPass(Options, std::move(Ftor));443}444