lib/Transforms/Scalar/SimplifyCFG.cpp

   1 //===- SimplifyCFG.cpp - CFG Simplification Pass --------------------------===//
   2 //
   3 // This file implements dead code elimination and basic block merging.
   4 //
   5 // Specifically, this:
   6 //   * removes basic blocks with no predecessors
   7 //   * merges a basic block into its predecessor if there is only one and the
   8 //     predecessor only has one successor.
   9 //   * Eliminates PHI nodes for basic blocks with a single predecessor
  10 //   * Eliminates a basic block that only contains an unconditional branch
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/Scalar.h"
  15 #include "llvm/Transforms/Utils/Local.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/GlobalVariable.h"
  18 #include "llvm/Support/CFG.h"
  19 #include "llvm/Pass.h"
  20 #include "Support/StatisticReporter.h"
  21 #include <set>
  22
  23 static Statistic<> NumSimpl("cfgsimplify\t- Number of blocks simplified");
  24
  25 namespace {
  26   struct CFGSimplifyPass : public FunctionPass {
  27     virtual bool runOnFunction(Function &F);
  28   };
  29   RegisterOpt<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
  30 }
  31
  32 Pass *createCFGSimplificationPass() {
  33   return new CFGSimplifyPass();
  34 }
  35
  36 static bool MarkAliveBlocks(BasicBlock *BB, std::set<BasicBlock*> &Reachable) {
  37   if (Reachable.count(BB)) return false;
  38   Reachable.insert(BB);
  39
  40   bool Changed = ConstantFoldTerminator(BB);
  41   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
  42     MarkAliveBlocks(*SI, Reachable);
  43
  44   return Changed;
  45 }
  46
  47
  48 // It is possible that we may require multiple passes over the code to fully
  49 // simplify the CFG.
  50 //
  51 bool CFGSimplifyPass::runOnFunction(Function &F) {
  52   std::set<BasicBlock*> Reachable;
  53   bool Changed = MarkAliveBlocks(F.begin(), Reachable);
  54
  55   // If there are unreachable blocks in the CFG...
  56   if (Reachable.size() != F.size()) {
  57     assert(Reachable.size() < F.size());
  58     NumSimpl += F.size()-Reachable.size();
  59
  60     // Loop over all of the basic blocks that are not reachable, dropping all of
  61     // their internal references...
  62     for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB)
  63       if (!Reachable.count(BB)) {
  64         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
  65           if (Reachable.count(*SI))
  66             (*SI)->removePredecessor(BB);
  67         BB->dropAllReferences();
  68       }
  69
  70     for (Function::iterator I = ++F.begin(); I != F.end();)
  71       if (!Reachable.count(I))
  72         I = F.getBasicBlockList().erase(I);
  73       else
  74         ++I;
  75
  76     Changed = true;
  77   }
  78
  79   bool LocalChange = true;
  80   while (LocalChange) {
  81     LocalChange = false;
  82
  83     // Loop over all of the basic blocks (except the first one) and remove them
  84     // if they are unneeded...
  85     //
  86     for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
  87       if (SimplifyCFG(BBIt++)) {
  88         LocalChange = true;
  89         ++NumSimpl;
  90       }
  91     }
  92     Changed |= LocalChange;
  93   }
  94
  95   return Changed;
  96 }