LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

CombineBranch.cpp

Go to the documentation of this file.
00001 //===-- CombineBranch.cpp -------------------------------------------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Combine multiple back-edges going to the same sink into a single
00011 // back-edge. This introduces a new basic block and back-edge branch for each
00012 // such sink.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Support/CFG.h"
00017 #include "llvm/Instructions.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/Pass.h"
00020 
00021 namespace llvm {
00022 
00023 namespace {
00024   struct CombineBranches : public FunctionPass {
00025   private:
00026     /// Possible colors that a vertex can have during depth-first search for
00027     /// back-edges.
00028     ///
00029     enum Color { WHITE, GREY, BLACK };
00030 
00031     void getBackEdgesVisit(BasicBlock *u,
00032          std::map<BasicBlock *, Color > &color,
00033          std::map<BasicBlock *, int > &d, 
00034          int &time,
00035          std::map<BasicBlock *, BasicBlock *> &be);
00036     void removeRedundant(std::map<BasicBlock *, BasicBlock *> &be);
00037   public:
00038     bool runOnFunction(Function &F);
00039   };
00040   
00041   RegisterOpt<CombineBranches>
00042   X("branch-combine", "Multiple backedges going to same target are merged");
00043 }
00044 
00045 /// getBackEdgesVisit - Get the back-edges of the control-flow graph for this
00046 /// function.  We proceed recursively using depth-first search.  We get
00047 /// back-edges by associating a time and a color with each vertex.  The time of a
00048 /// vertex is the time when it was first visited.  The color of a vertex is
00049 /// initially WHITE, changes to GREY when it is first visited, and changes to
00050 /// BLACK when ALL its neighbors have been visited.  So we have a back edge when
00051 /// we meet a successor of a node with smaller time, and GREY color.
00052 ///
00053 void CombineBranches::getBackEdgesVisit(BasicBlock *u,
00054                        std::map<BasicBlock *, Color > &color,
00055                        std::map<BasicBlock *, int > &d, 
00056                        int &time,
00057            std::map<BasicBlock *, BasicBlock *> &be) {
00058   
00059   color[u]=GREY;
00060   time++;
00061   d[u]=time;
00062 
00063   for (succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){
00064     BasicBlock *BB = *vl;
00065 
00066     if(color[BB]!=GREY && color[BB]!=BLACK)
00067       getBackEdgesVisit(BB, color, d, time, be);
00068     
00069     //now checking for d and f vals
00070     else if(color[BB]==GREY){
00071       //so v is ancestor of u if time of u > time of v
00072       if(d[u] >= d[BB]) // u->BB is a backedge
00073   be[u] = BB;
00074     }
00075   }
00076   color[u]=BLACK;//done with visiting the node and its neighbors
00077 }
00078 
00079 /// removeRedundant - Remove all back-edges that are dominated by other
00080 /// back-edges in the set.
00081 ///
00082 void CombineBranches::removeRedundant(std::map<BasicBlock *, BasicBlock *> &be){
00083   std::vector<BasicBlock *> toDelete;
00084   std::map<BasicBlock *, int> seenBB;
00085   
00086   for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), 
00087   ME = be.end(); MI != ME; ++MI){
00088     
00089     if(seenBB[MI->second])
00090       continue;
00091     
00092     seenBB[MI->second] = 1;
00093 
00094     std::vector<BasicBlock *> sameTarget;
00095     sameTarget.clear();
00096     
00097     for(std::map<BasicBlock *, BasicBlock *>::iterator MMI = be.begin(), 
00098     MME = be.end(); MMI != MME; ++MMI){
00099       
00100       if(MMI->first == MI->first)
00101   continue;
00102       
00103       if(MMI->second == MI->second)
00104   sameTarget.push_back(MMI->first);
00105       
00106     }
00107     
00108     //so more than one branch to same target
00109     if(sameTarget.size()){
00110 
00111       sameTarget.push_back(MI->first);
00112 
00113       BasicBlock *newBB = new BasicBlock("newCommon", MI->first->getParent());
00114       BranchInst *newBranch = new BranchInst(MI->second, newBB);
00115 
00116       std::map<PHINode *, std::vector<unsigned int> > phiMap;
00117 
00118       for(std::vector<BasicBlock *>::iterator VBI = sameTarget.begin(),
00119       VBE = sameTarget.end(); VBI != VBE; ++VBI){
00120 
00121   BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator());
00122   unsigned char index = 1;
00123   if(ti->getSuccessor(0) == MI->second)
00124     index = 0;
00125 
00126   ti->setSuccessor(index, newBB);
00127 
00128   for(BasicBlock::iterator BB2Inst = MI->second->begin(), 
00129         BBend = MI->second->end(); BB2Inst != BBend; ++BB2Inst){
00130     
00131     if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)){
00132       int bbIndex;
00133       bbIndex = phiInst->getBasicBlockIndex(*VBI);
00134       if(bbIndex>=0)
00135         phiMap[phiInst].push_back(bbIndex);
00136     }
00137   }
00138       }
00139 
00140       for(std::map<PHINode *, std::vector<unsigned int> >::iterator
00141       PI = phiMap.begin(), PE = phiMap.end(); PI != PE; ++PI){
00142   
00143   PHINode *phiNode = new PHINode(PI->first->getType(), "phi", newBranch);
00144   for(std::vector<unsigned int>::iterator II = PI->second.begin(),
00145         IE = PI->second.end(); II != IE; ++II){
00146     phiNode->addIncoming(PI->first->getIncomingValue(*II),
00147              PI->first->getIncomingBlock(*II));
00148   }
00149 
00150   std::vector<BasicBlock *> tempBB;
00151   for(std::vector<unsigned int>::iterator II = PI->second.begin(),
00152         IE = PI->second.end(); II != IE; ++II){
00153     tempBB.push_back(PI->first->getIncomingBlock(*II));
00154   }
00155 
00156   for(std::vector<BasicBlock *>::iterator II = tempBB.begin(),
00157         IE = tempBB.end(); II != IE; ++II){
00158     PI->first->removeIncomingValue(*II);
00159   }
00160 
00161   PI->first->addIncoming(phiNode, newBB);
00162       }
00163     }
00164   }
00165 }
00166 
00167 /// runOnFunction - Per function pass for combining branches.
00168 ///
00169 bool CombineBranches::runOnFunction(Function &F){
00170   if (F.isExternal ())
00171     return false;
00172 
00173   // Find and remove "redundant" back-edges.
00174   std::map<BasicBlock *, Color> color;
00175   std::map<BasicBlock *, int> d;
00176   std::map<BasicBlock *, BasicBlock *> be;
00177   int time = 0;
00178   getBackEdgesVisit (F.begin (), color, d, time, be);
00179   removeRedundant (be);
00180   
00181   return true; // FIXME: assumes a modification was always made.
00182 }
00183 
00184 FunctionPass *createCombineBranchesPass () {
00185   return new CombineBranches();
00186 }
00187 
00188 } // End llvm namespace