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