llvm/lib/Transforms/Scalar/SimplifyCFGPass.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-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"
  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/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"
  43 #include "llvm/Support/CommandLine.h"
  44 #include "llvm/Transforms/Scalar.h"
  45 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
  46 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  47 #include "llvm/Transforms/Utils/Local.h"
  48 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
  49 #include <utility>
  50 using namespace llvm;
  51
  52 #define DEBUG_TYPE "simplifycfg"
  53
  54 static cl::opt<unsigned> UserBonusInstThreshold(
  55     "bonus-inst-threshold", cl::Hidden, cl::init(1),
  56     cl::desc("Control the number of bonus instructions (default = 1)"));
  57
  58 static cl::opt<bool> UserKeepLoops(
  59     "keep-loops", cl::Hidden, cl::init(true),
  60     cl::desc("Preserve canonical loop structure (default = true)"));
  61
  62 static cl::opt<bool> UserSwitchToLookup(
  63     "switch-to-lookup", cl::Hidden, cl::init(false),
  64     cl::desc("Convert switches to lookup tables (default = false)"));
  65
  66 static 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
  70 static cl::opt<bool> UserHoistCommonInsts(
  71     "hoist-common-insts", cl::Hidden, cl::init(false),
  72     cl::desc("hoist common instructions (default = false)"));
  73
  74 static cl::opt<bool> UserSinkCommonInsts(
  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 tailMergeBlocksWithSimilarFunctionTerminators(Function &F,
  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)) {
 137     SmallVector<PHINode *, 1> NewOps;
 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.
 212 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
 213                                    DomTreeUpdater *DTU,
 214                                    const SimplifyCFGOptions &Options) {
 215   bool Changed = false;
 216   bool LocalChange = true;
 217
 218   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
 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
 252 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
 253                                     DominatorTree *DT,
 254                                     const SimplifyCFGOptions &Options) {
 255   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 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
 281 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
 282                                 DominatorTree *DT,
 283                                 const SimplifyCFGOptions &Options) {
 284   assert((!RequireAndPreserveDomTree ||
 285           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
 286          "Original domtree is invalid?");
 287
 288   bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
 289
 290   assert((!RequireAndPreserveDomTree ||
 291           (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
 292          "Failed to maintain validity of domtree!");
 293
 294   return Changed;
 295 }
 296
 297 // Command-line settings override compile-time settings.
 298 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {
 299   if (UserBonusInstThreshold.getNumOccurrences())
 300     Options.BonusInstThreshold = UserBonusInstThreshold;
 301   if (UserForwardSwitchCond.getNumOccurrences())
 302     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond;
 303   if (UserSwitchToLookup.getNumOccurrences())
 304     Options.ConvertSwitchToLookupTable = UserSwitchToLookup;
 305   if (UserKeepLoops.getNumOccurrences())
 306     Options.NeedCanonicalLoop = UserKeepLoops;
 307   if (UserHoistCommonInsts.getNumOccurrences())
 308     Options.HoistCommonInsts = UserHoistCommonInsts;
 309   if (UserSinkCommonInsts.getNumOccurrences())
 310     Options.SinkCommonInsts = UserSinkCommonInsts;
 311 }
 312
 313 SimplifyCFGPass::SimplifyCFGPass() : Options() {
 314   applyCommandLineOverridesToOptions(Options);
 315 }
 316
 317 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts)
 318     : Options(Opts) {
 319   applyCommandLineOverridesToOptions(Options);
 320 }
 321
 322 PreservedAnalyses SimplifyCFGPass::run(Function &F,
 323                                        FunctionAnalysisManager &AM) {
 324   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 325   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
 326   DominatorTree *DT = nullptr;
 327   if (RequireAndPreserveDomTree)
 328     DT = &AM.getResult<DominatorTreeAnalysis>(F);
 329   if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
 330     Options.setSimplifyCondBranch(false).setFoldTwoEntryPHINode(false);
 331   } else {
 332     Options.setSimplifyCondBranch(true).setFoldTwoEntryPHINode(true);
 333   }
 334   if (!simplifyFunctionCFG(F, TTI, DT, Options))
 335     return PreservedAnalyses::all();
 336   PreservedAnalyses PA;
 337   if (RequireAndPreserveDomTree)
 338     PA.preserve<DominatorTreeAnalysis>();
 339   return PA;
 340 }
 341
 342 namespace {
 343 struct CFGSimplifyPass : public FunctionPass {
 344   static char ID;
 345   SimplifyCFGOptions Options;
 346   std::function<bool(const Function &)> PredicateFtor;
 347
 348   CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(),
 349                   std::function<bool(const Function &)> Ftor = nullptr)
 350       : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) {
 351
 352     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
 353
 354     // Check for command-line overrides of options for debug/customization.
 355     applyCommandLineOverridesToOptions(Options);
 356   }
 357
 358   bool runOnFunction(Function &F) override {
 359     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
 360       return false;
 361
 362     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 363     DominatorTree *DT = nullptr;
 364     if (RequireAndPreserveDomTree)
 365       DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 366     if (F.hasFnAttribute(Attribute::OptForFuzzing)) {
 367       Options.setSimplifyCondBranch(false)
 368              .setFoldTwoEntryPHINode(false);
 369     } else {
 370       Options.setSimplifyCondBranch(true)
 371              .setFoldTwoEntryPHINode(true);
 372     }
 373
 374     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 375     return simplifyFunctionCFG(F, TTI, DT, Options);
 376   }
 377   void getAnalysisUsage(AnalysisUsage &AU) const override {
 378     AU.addRequired<AssumptionCacheTracker>();
 379     if (RequireAndPreserveDomTree)
 380       AU.addRequired<DominatorTreeWrapperPass>();
 381     AU.addRequired<TargetTransformInfoWrapperPass>();
 382     if (RequireAndPreserveDomTree)
 383       AU.addPreserved<DominatorTreeWrapperPass>();
 384     AU.addPreserved<GlobalsAAWrapperPass>();
 385   }
 386 };
 387 }
 388
 389 char CFGSimplifyPass::ID = 0;
 390 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
 391                       false)
 392 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 393 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 394 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 395 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
 396                     false)
 397
 398 // Public interface to the CFGSimplification pass
 399 FunctionPass *
 400 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options,
 401                                   std::function<bool(const Function &)> Ftor) {
 402   return new CFGSimplifyPass(Options, std::move(Ftor));
 403 }