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     const char *getPassName() const { return "Simplify CFG"; }
  28
  29     virtual bool runOnFunction(Function &F);
  30   };
  31 }
  32
  33 Pass *createCFGSimplificationPass() {
  34   return new CFGSimplifyPass();
  35 }
  36
  37 static bool MarkAliveBlocks(BasicBlock *BB, std::set<BasicBlock*> &Reachable) {
  38   if (Reachable.count(BB)) return false;
  39   Reachable.insert(BB);
  40
  41   bool Changed = ConstantFoldTerminator(BB);
  42   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
  43     MarkAliveBlocks(*SI, Reachable);
  44
  45   return Changed;
  46 }
  47
  48
  49 // It is possible that we may require multiple passes over the code to fully
  50 // simplify the CFG.
  51 //
  52 bool CFGSimplifyPass::runOnFunction(Function &F) {
  53   std::set<BasicBlock*> Reachable;
  54   bool Changed = MarkAliveBlocks(F.begin(), Reachable);
  55
  56   // If there are unreachable blocks in the CFG...
  57   if (Reachable.size() != F.size()) {
  58     assert(Reachable.size() < F.size());
  59     NumSimpl += F.size()-Reachable.size();
  60
  61     // Loop over all of the basic blocks that are not reachable, dropping all of
  62     // their internal references...
  63     for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB)
  64       if (!Reachable.count(BB)) {
  65         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
  66           if (Reachable.count(*SI))
  67             (*SI)->removePredecessor(BB);
  68         BB->dropAllReferences();
  69       }
  70
  71     for (Function::iterator I = ++F.begin(); I != F.end();)
  72       if (!Reachable.count(I))
  73         I = F.getBasicBlockList().erase(I);
  74       else
  75         ++I;
  76
  77     Changed = true;
  78   }
  79
  80   bool LocalChange = true;
  81   while (LocalChange) {
  82     LocalChange = false;
  83
  84     // Loop over all of the basic blocks (except the first one) and remove them
  85     // if they are unneeded...
  86     //
  87     for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
  88       if (SimplifyCFG(BBIt++)) {
  89         LocalChange = true;
  90         ++NumSimpl;
  91       }
  92     }
  93     Changed |= LocalChange;
  94   }
  95
  96   return Changed;
  97 }