lib/Transforms/Instrumentation/ProfilePaths/CombineBranch.cpp

   1 //===-- CombineBranch.cpp -------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Combine multiple back-edges going to the same sink into a single
  11 // back-edge. This introduces a new basic block and back-edge branch for each
  12 // such sink.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Support/CFG.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Pass.h"
  20
  21 namespace llvm {
  22
  23 namespace {
  24   struct CombineBranches : public FunctionPass {
  25   private:
  26     /// Possible colors that a vertex can have during depth-first search for
  27     /// back-edges.
  28     ///
  29     enum Color { WHITE, GREY, BLACK };
  30
  31     void getBackEdgesVisit(BasicBlock *u,
  32                            std::map<BasicBlock *, Color > &color,
  33                            std::map<BasicBlock *, int > &d,
  34                            int &time,
  35                            std::map<BasicBlock *, BasicBlock *> &be);
  36     void removeRedundant(std::map<BasicBlock *, BasicBlock *> &be);
  37   public:
  38     bool runOnFunction(Function &F);
  39   };
  40
  41   RegisterOpt<CombineBranches>
  42   X("branch-combine", "Multiple backedges going to same target are merged");
  43 }
  44
  45 /// getBackEdgesVisit - Get the back-edges of the control-flow graph for this
  46 /// function.  We proceed recursively using depth-first search.  We get
  47 /// back-edges by associating a time and a color with each vertex.  The time of a
  48 /// vertex is the time when it was first visited.  The color of a vertex is
  49 /// initially WHITE, changes to GREY when it is first visited, and changes to
  50 /// BLACK when ALL its neighbors have been visited.  So we have a back edge when
  51 /// we meet a successor of a node with smaller time, and GREY color.
  52 ///
  53 void CombineBranches::getBackEdgesVisit(BasicBlock *u,
  54                        std::map<BasicBlock *, Color > &color,
  55                        std::map<BasicBlock *, int > &d,
  56                        int &time,
  57                        std::map<BasicBlock *, BasicBlock *> &be) {
  58
  59   color[u]=GREY;
  60   time++;
  61   d[u]=time;
  62
  63   for (succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){
  64     BasicBlock *BB = *vl;
  65
  66     if(color[BB]!=GREY && color[BB]!=BLACK)
  67       getBackEdgesVisit(BB, color, d, time, be);
  68
  69     //now checking for d and f vals
  70     else if(color[BB]==GREY){
  71       //so v is ancestor of u if time of u > time of v
  72       if(d[u] >= d[BB]) // u->BB is a backedge
  73         be[u] = BB;
  74     }
  75   }
  76   color[u]=BLACK;//done with visiting the node and its neighbors
  77 }
  78
  79 /// removeRedundant - Remove all back-edges that are dominated by other
  80 /// back-edges in the set.
  81 ///
  82 void CombineBranches::removeRedundant(std::map<BasicBlock *, BasicBlock *> &be){
  83   std::vector<BasicBlock *> toDelete;
  84   std::map<BasicBlock *, int> seenBB;
  85
  86   for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(),
  87         ME = be.end(); MI != ME; ++MI){
  88
  89     if(seenBB[MI->second])
  90       continue;
  91
  92     seenBB[MI->second] = 1;
  93
  94     std::vector<BasicBlock *> sameTarget;
  95     sameTarget.clear();
  96
  97     for(std::map<BasicBlock *, BasicBlock *>::iterator MMI = be.begin(),
  98           MME = be.end(); MMI != MME; ++MMI){
  99
 100       if(MMI->first == MI->first)
 101         continue;
 102
 103       if(MMI->second == MI->second)
 104         sameTarget.push_back(MMI->first);
 105
 106     }
 107
 108     //so more than one branch to same target
 109     if(sameTarget.size()){
 110
 111       sameTarget.push_back(MI->first);
 112
 113       BasicBlock *newBB = new BasicBlock("newCommon", MI->first->getParent());
 114       BranchInst *newBranch = new BranchInst(MI->second, newBB);
 115
 116       std::map<PHINode *, std::vector<unsigned int> > phiMap;
 117
 118       for(std::vector<BasicBlock *>::iterator VBI = sameTarget.begin(),
 119             VBE = sameTarget.end(); VBI != VBE; ++VBI){
 120
 121         BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator());
 122         unsigned char index = 1;
 123         if(ti->getSuccessor(0) == MI->second)
 124           index = 0;
 125
 126         ti->setSuccessor(index, newBB);
 127
 128         for(BasicBlock::iterator BB2Inst = MI->second->begin(),
 129               BBend = MI->second->end(); BB2Inst != BBend; ++BB2Inst){
 130
 131           if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)){
 132             int bbIndex;
 133             bbIndex = phiInst->getBasicBlockIndex(*VBI);
 134             if(bbIndex>=0)
 135               phiMap[phiInst].push_back(bbIndex);
 136           }
 137         }
 138       }
 139
 140       for(std::map<PHINode *, std::vector<unsigned int> >::iterator
 141             PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){
 142
 143         PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch);
 144         for(std::vector<unsigned int>::iterator II = PI->second.begin(),
 145               IE = PI->second.end(); II != IE; ++II){
 146           phiNode->addIncoming(PI->first->getIncomingValue(*II),
 147                                PI->first->getIncomingBlock(*II));
 148         }
 149
 150         std::vector<BasicBlock *> tempBB;
 151         for(std::vector<unsigned int>::iterator II = PI->second.begin(),
 152               IE = PI->second.end(); II != IE; ++II){
 153           tempBB.push_back(PI->first->getIncomingBlock(*II));
 154         }
 155
 156         for(std::vector<BasicBlock *>::iterator II = tempBB.begin(),
 157               IE = tempBB.end(); II != IE; ++II){
 158           PI->first->removeIncomingValue(*II);
 159         }
 160
 161         PI->first->addIncoming(phiNode, newBB);
 162       }
 163     }
 164   }
 165 }
 166
 167 /// runOnFunction - Per function pass for combining branches.
 168 ///
 169 bool CombineBranches::runOnFunction(Function &F){
 170   if (F.isExternal ())
 171     return false;
 172
 173   // Find and remove "redundant" back-edges.
 174   std::map<BasicBlock *, Color> color;
 175   std::map<BasicBlock *, int> d;
 176   std::map<BasicBlock *, BasicBlock *> be;
 177   int time = 0;
 178   getBackEdgesVisit (F.begin (), color, d, time, be);
 179   removeRedundant (be);
 180
 181   return true; // FIXME: assumes a modification was always made.
 182 }
 183
 184 FunctionPass *createCombineBranchesPass () {
 185   return new CombineBranches();
 186 }
 187
 188 } // End llvm namespace