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/SmallPtrSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Analysis/AssumptionCache.h"
  27 #include "llvm/Analysis/CFG.h"
  28 #include "llvm/Analysis/GlobalsModRef.h"
  29 #include "llvm/Analysis/TargetTransformInfo.h"
  30 #include "llvm/Transforms/Utils/Local.h"
  31 #include "llvm/IR/Attributes.h"
  32 #include "llvm/IR/CFG.h"
  33 #include "llvm/IR/Constants.h"
  34 #include "llvm/IR/DataLayout.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/IntrinsicInst.h"
  37 #include "llvm/IR/Module.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 <utility>
  43 using namespace llvm;
  44
  45 #define DEBUG_TYPE "simplifycfg"
  46
  47 static cl::opt<unsigned> UserBonusInstThreshold(
  48     "bonus-inst-threshold", cl::Hidden, cl::init(1),
  49     cl::desc("Control the number of bonus instructions (default = 1)"));
  50
  51 static cl::opt<bool> UserKeepLoops(
  52     "keep-loops", cl::Hidden, cl::init(true),
  53     cl::desc("Preserve canonical loop structure (default = true)"));
  54
  55 static cl::opt<bool> UserSwitchToLookup(
  56     "switch-to-lookup", cl::Hidden, cl::init(false),
  57     cl::desc("Convert switches to lookup tables (default = false)"));
  58
  59 static cl::opt<bool> UserForwardSwitchCond(
  60     "forward-switch-cond", cl::Hidden, cl::init(false),
  61     cl::desc("Forward switch condition to phi ops (default = false)"));
  62
  63 static cl::opt<bool> UserSinkCommonInsts(
  64     "sink-common-insts", cl::Hidden, cl::init(false),
  65     cl::desc("Sink common instructions (default = false)"));
  66
  67
  68 STATISTIC(NumSimpl, "Number of blocks simplified");
  69
  70 /// If we have more than one empty (other than phi node) return blocks,
  71 /// merge them together to promote recursive block merging.
  72 static bool mergeEmptyReturnBlocks(Function &F) {
  73   bool Changed = false;
  74
  75   BasicBlock *RetBlock = nullptr;
  76
  77   // Scan all the blocks in the function, looking for empty return blocks.
  78   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
  79     BasicBlock &BB = *BBI++;
  80
  81     // Only look at return blocks.
  82     ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
  83     if (!Ret) continue;
  84
  85     // Only look at the block if it is empty or the only other thing in it is a
  86     // single PHI node that is the operand to the return.
  87     if (Ret != &BB.front()) {
  88       // Check for something else in the block.
  89       BasicBlock::iterator I(Ret);
  90       --I;
  91       // Skip over debug info.
  92       while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
  93         --I;
  94       if (!isa<DbgInfoIntrinsic>(I) &&
  95           (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
  96            Ret->getOperand(0) != &*I))
  97         continue;
  98     }
  99
 100     // If this is the first returning block, remember it and keep going.
 101     if (!RetBlock) {
 102       RetBlock = &BB;
 103       continue;
 104     }
 105
 106     // Otherwise, we found a duplicate return block.  Merge the two.
 107     Changed = true;
 108
 109     // Case when there is no input to the return or when the returned values
 110     // agree is trivial.  Note that they can't agree if there are phis in the
 111     // blocks.
 112     if (Ret->getNumOperands() == 0 ||
 113         Ret->getOperand(0) ==
 114           cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
 115       BB.replaceAllUsesWith(RetBlock);
 116       BB.eraseFromParent();
 117       continue;
 118     }
 119
 120     // If the canonical return block has no PHI node, create one now.
 121     PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
 122     if (!RetBlockPHI) {
 123       Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
 124       pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
 125       RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
 126                                     std::distance(PB, PE), "merge",
 127                                     &RetBlock->front());
 128
 129       for (pred_iterator PI = PB; PI != PE; ++PI)
 130         RetBlockPHI->addIncoming(InVal, *PI);
 131       RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
 132     }
 133
 134     // Turn BB into a block that just unconditionally branches to the return
 135     // block.  This handles the case when the two return blocks have a common
 136     // predecessor but that return different things.
 137     RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
 138     BB.getTerminator()->eraseFromParent();
 139     BranchInst::Create(RetBlock, &BB);
 140   }
 141
 142   return Changed;
 143 }
 144
 145 /// Call SimplifyCFG on all the blocks in the function,
 146 /// iterating until no more changes are made.
 147 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
 148                                    const SimplifyCFGOptions &Options) {
 149   bool Changed = false;
 150   bool LocalChange = true;
 151
 152   SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
 153   FindFunctionBackedges(F, Edges);
 154   SmallPtrSet<BasicBlock *, 16> LoopHeaders;
 155   for (unsigned i = 0, e = Edges.size(); i != e; ++i)
 156     LoopHeaders.insert(const_cast<BasicBlock *>(Edges[i].second));
 157
 158   while (LocalChange) {
 159     LocalChange = false;
 160
 161     // Loop over all of the basic blocks and remove them if they are unneeded.
 162     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
 163       if (simplifyCFG(&*BBIt++, TTI, Options, &LoopHeaders)) {
 164         LocalChange = true;
 165         ++NumSimpl;
 166       }
 167     }
 168     Changed |= LocalChange;
 169   }
 170   return Changed;
 171 }
 172
 173 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
 174                                 const SimplifyCFGOptions &Options) {
 175   bool EverChanged = removeUnreachableBlocks(F);
 176   EverChanged |= mergeEmptyReturnBlocks(F);
 177   EverChanged |= iterativelySimplifyCFG(F, TTI, Options);
 178
 179   // If neither pass changed anything, we're done.
 180   if (!EverChanged) return false;
 181
 182   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
 183   // removeUnreachableBlocks is needed to nuke them, which means we should
 184   // iterate between the two optimizations.  We structure the code like this to
 185   // avoid rerunning iterativelySimplifyCFG if the second pass of
 186   // removeUnreachableBlocks doesn't do anything.
 187   if (!removeUnreachableBlocks(F))
 188     return true;
 189
 190   do {
 191     EverChanged = iterativelySimplifyCFG(F, TTI, Options);
 192     EverChanged |= removeUnreachableBlocks(F);
 193   } while (EverChanged);
 194
 195   return true;
 196 }
 197
 198 // Command-line settings override compile-time settings.
 199 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) {
 200   Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
 201                                    ? UserBonusInstThreshold
 202                                    : Opts.BonusInstThreshold;
 203   Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
 204                                        ? UserForwardSwitchCond
 205                                        : Opts.ForwardSwitchCondToPhi;
 206   Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
 207                                            ? UserSwitchToLookup
 208                                            : Opts.ConvertSwitchToLookupTable;
 209   Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
 210                                   ? UserKeepLoops
 211                                   : Opts.NeedCanonicalLoop;
 212   Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
 213                                 ? UserSinkCommonInsts
 214                                 : Opts.SinkCommonInsts;
 215 }
 216
 217 PreservedAnalyses SimplifyCFGPass::run(Function &F,
 218                                        FunctionAnalysisManager &AM) {
 219   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 220   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
 221   if (!simplifyFunctionCFG(F, TTI, Options))
 222     return PreservedAnalyses::all();
 223   PreservedAnalyses PA;
 224   PA.preserve<GlobalsAA>();
 225   return PA;
 226 }
 227
 228 namespace {
 229 struct CFGSimplifyPass : public FunctionPass {
 230   static char ID;
 231   SimplifyCFGOptions Options;
 232   std::function<bool(const Function &)> PredicateFtor;
 233
 234   CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
 235                   bool ConvertSwitch = false, bool KeepLoops = true,
 236                   bool SinkCommon = false,
 237                   std::function<bool(const Function &)> Ftor = nullptr)
 238       : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
 239
 240     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
 241
 242     // Check for command-line overrides of options for debug/customization.
 243     Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
 244                                     ? UserBonusInstThreshold
 245                                     : Threshold;
 246
 247     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
 248                                          ? UserForwardSwitchCond
 249                                          : ForwardSwitchCond;
 250
 251     Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
 252                                              ? UserSwitchToLookup
 253                                              : ConvertSwitch;
 254
 255     Options.NeedCanonicalLoop =
 256         UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
 257
 258     Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
 259                                   ? UserSinkCommonInsts
 260                                   : SinkCommon;
 261   }
 262
 263   bool runOnFunction(Function &F) override {
 264     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
 265       return false;
 266
 267     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 268     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 269     return simplifyFunctionCFG(F, TTI, Options);
 270   }
 271   void getAnalysisUsage(AnalysisUsage &AU) const override {
 272     AU.addRequired<AssumptionCacheTracker>();
 273     AU.addRequired<TargetTransformInfoWrapperPass>();
 274     AU.addPreserved<GlobalsAAWrapperPass>();
 275   }
 276 };
 277 }
 278
 279 char CFGSimplifyPass::ID = 0;
 280 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
 281                       false)
 282 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 283 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 284 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
 285                     false)
 286
 287 // Public interface to the CFGSimplification pass
 288 FunctionPass *
 289 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
 290                                   bool ConvertSwitch, bool KeepLoops,
 291                                   bool SinkCommon,
 292                                   std::function<bool(const Function &)> Ftor) {
 293   return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
 294                              KeepLoops, SinkCommon, std::move(Ftor));
 295 }