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->front(), 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 I = F->begin()+1, E = F->end(); I != E; ++I)
  64       if (!Reachable.count(*I)) {
  65         BasicBlock *BB = *I;
  66         for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
  67           if (Reachable.count(*SI))
  68             (*SI)->removePredecessor(BB);
  69         BB->dropAllReferences();
  70       }
  71
  72     for (Function::iterator I = F->begin()+1; I != F->end();)
  73       if (!Reachable.count(*I))
  74         delete F->getBasicBlocks().remove(I);
  75       else
  76         ++I;
  77
  78     Changed = true;
  79   }
  80
  81   bool LocalChange = true;
  82   while (LocalChange) {
  83     LocalChange = false;
  84
  85     // Loop over all of the basic blocks (except the first one) and remove them
  86     // if they are unneeded...
  87     //
  88     for (Function::iterator BBIt = F->begin()+1; BBIt != F->end(); ) {
  89       if (SimplifyCFG(BBIt)) {
  90         LocalChange = true;
  91         ++NumSimpl;
  92       } else {
  93         ++BBIt;
  94       }
  95     }
  96     Changed |= LocalChange;
  97   }
  98
  99   return Changed;
 100 }