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