lib/Transforms/Utils/UnifyFunctionExitNodes.cpp

   1 //===- SimplifyCFG.cpp - CFG Simplification Routines -------------*- C++ -*--=//
   2 //
   3 // This file provides several routines that are useful for simplifying CFGs in
   4 // various ways...
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/Transforms/UnifyMethodExitNodes.h"
   9 #include "llvm/BasicBlock.h"
  10 #include "llvm/Method.h"
  11 #include "llvm/iTerminators.h"
  12 #include "llvm/iPHINode.h"
  13 #include "llvm/Type.h"
  14 using std::vector;
  15
  16 AnalysisID UnifyMethodExitNodes::ID(AnalysisID::create<UnifyMethodExitNodes>());
  17
  18
  19 // UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new
  20 // BasicBlock, and converting all returns to unconditional branches to this
  21 // new basic block.  The singular exit node is returned.
  22 //
  23 // If there are no return stmts in the Method, a null pointer is returned.
  24 //
  25 bool UnifyMethodExitNodes::doit(Method *M, BasicBlock *&ExitNode) {
  26   // Loop over all of the blocks in a method, tracking all of the blocks that
  27   // return.
  28   //
  29   vector<BasicBlock*> ReturningBlocks;
  30   for(Method::iterator I = M->begin(), E = M->end(); I != E; ++I)
  31     if (isa<ReturnInst>((*I)->getTerminator()))
  32       ReturningBlocks.push_back(*I);
  33
  34   if (ReturningBlocks.empty()) {
  35     ExitNode = 0;
  36     return false;                      // No blocks return
  37   } else if (ReturningBlocks.size() == 1) {
  38     ExitNode = ReturningBlocks.front();    // Already has a single return block
  39     return false;
  40   }
  41
  42   // Otherwise, we need to insert a new basic block into the method, add a PHI
  43   // node (if the function returns a value), and convert all of the return
  44   // instructions into unconditional branches.
  45   //
  46   BasicBlock *NewRetBlock = new BasicBlock("UnifiedExitNode", M);
  47
  48   if (M->getReturnType() != Type::VoidTy) {
  49     // If the method doesn't return void... add a PHI node to the block...
  50     PHINode *PN = new PHINode(M->getReturnType());
  51     NewRetBlock->getInstList().push_back(PN);
  52
  53     // Add an incoming element to the PHI node for every return instruction that
  54     // is merging into this new block...
  55     for (vector<BasicBlock*>::iterator I = ReturningBlocks.begin(),
  56                                        E = ReturningBlocks.end(); I != E; ++I)
  57       PN->addIncoming((*I)->getTerminator()->getOperand(0), *I);
  58
  59     // Add a return instruction to return the result of the PHI node...
  60     NewRetBlock->getInstList().push_back(new ReturnInst(PN));
  61   } else {
  62     // If it returns void, just add a return void instruction to the block
  63     NewRetBlock->getInstList().push_back(new ReturnInst());
  64   }
  65
  66   // Loop over all of the blocks, replacing the return instruction with an
  67   // unconditional branch.
  68   //
  69   for (vector<BasicBlock*>::iterator I = ReturningBlocks.begin(),
  70                                      E = ReturningBlocks.end(); I != E; ++I) {
  71     delete (*I)->getInstList().pop_back();  // Remove the return insn
  72     (*I)->getInstList().push_back(new BranchInst(NewRetBlock));
  73   }
  74   ExitNode = NewRetBlock;
  75   return true;
  76 }