blob: 1a7b77387d36a8cee65871980d828c69d0d149df [file] [log] [blame]
Chris Lattner44d2c352003-10-13 03:32:08 +00001//===-- CombineBranch.cpp -------------------------------------------------===//
John Criswell482202a2003-10-20 19:43:21 +00002//
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 Lattner44d2c352003-10-13 03:32:08 +00009//
Brian Gaekea9c57792004-06-03 05:03:02 +000010// 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 Lattner44d2c352003-10-13 03:32:08 +000013//
Anand Shukla89233e12003-07-18 16:08:32 +000014//===----------------------------------------------------------------------===//
15
Anand Shukla89233e12003-07-18 16:08:32 +000016#include "llvm/Support/CFG.h"
Misha Brukman63b38bd2004-07-29 17:30:56 +000017#include "llvm/Instructions.h"
Anand Shukla89233e12003-07-18 16:08:32 +000018#include "llvm/Function.h"
19#include "llvm/Pass.h"
Brian Gaekef9639d22004-12-13 21:28:39 +000020#include "llvm/Type.h"
Anand Shukla89233e12003-07-18 16:08:32 +000021
Brian Gaeke960707c2003-11-11 22:41:34 +000022namespace llvm {
23
Brian Gaeke960707c2003-11-11 22:41:34 +000024namespace {
Anand Shukla89233e12003-07-18 16:08:32 +000025 struct CombineBranches : public FunctionPass {
26 private:
Brian Gaekeef327be2004-03-30 19:53:46 +000027 /// Possible colors that a vertex can have during depth-first search for
28 /// back-edges.
29 ///
30 enum Color { WHITE, GREY, BLACK };
31
Anand Shukla89233e12003-07-18 16:08:32 +000032 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 Shukla89233e12003-07-18 16:08:32 +000038 public:
39 bool runOnFunction(Function &F);
40 };
41
Brian Gaekeef327be2004-03-30 19:53:46 +000042 RegisterOpt<CombineBranches>
43 X("branch-combine", "Multiple backedges going to same target are merged");
Anand Shukla89233e12003-07-18 16:08:32 +000044}
45
Brian Gaekeef327be2004-03-30 19:53:46 +000046/// 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 Shukla89233e12003-07-18 16:08:32 +000054void 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 Lattnera9400952003-09-24 22:06:25 +000064 for (succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){
Anand Shukla89233e12003-07-18 16:08:32 +000065 BasicBlock *BB = *vl;
66
Brian Gaekeef327be2004-03-30 19:53:46 +000067 if(color[BB]!=GREY && color[BB]!=BLACK)
Anand Shukla89233e12003-07-18 16:08:32 +000068 getBackEdgesVisit(BB, color, d, time, be);
Anand Shukla89233e12003-07-18 16:08:32 +000069
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 Gaekeef327be2004-03-30 19:53:46 +000073 if(d[u] >= d[BB]) // u->BB is a backedge
Anand Shukla89233e12003-07-18 16:08:32 +000074 be[u] = BB;
Anand Shukla89233e12003-07-18 16:08:32 +000075 }
76 }
77 color[u]=BLACK;//done with visiting the node and its neighbors
78}
79
Brian Gaekeef327be2004-03-30 19:53:46 +000080/// removeRedundant - Remove all back-edges that are dominated by other
81/// back-edges in the set.
82///
Anand Shukla89233e12003-07-18 16:08:32 +000083void 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 Gaekec0b9b832004-06-01 20:06:10 +0000115 BranchInst *newBranch = new BranchInst(MI->second, newBB);
Anand Shukla89233e12003-07-18 16:08:32 +0000116
117 std::map<PHINode *, std::vector<unsigned int> > phiMap;
118
Anand Shukla89233e12003-07-18 16:08:32 +0000119 for(std::vector<BasicBlock *>::iterator VBI = sameTarget.begin(),
120 VBE = sameTarget.end(); VBI != VBE; ++VBI){
121
Anand Shukla89233e12003-07-18 16:08:32 +0000122 BranchInst *ti = cast<BranchInst>((*VBI)->getTerminator());
123 unsigned char index = 1;
Brian Gaekeef327be2004-03-30 19:53:46 +0000124 if(ti->getSuccessor(0) == MI->second)
Anand Shukla89233e12003-07-18 16:08:32 +0000125 index = 0;
Anand Shukla89233e12003-07-18 16:08:32 +0000126
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 Gaekeef327be2004-03-30 19:53:46 +0000135 if(bbIndex>=0)
Anand Shukla89233e12003-07-18 16:08:32 +0000136 phiMap[phiInst].push_back(bbIndex);
Anand Shukla89233e12003-07-18 16:08:32 +0000137 }
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 Shukla89233e12003-07-18 16:08:32 +0000164 }
165 }
166}
167
Brian Gaekeef327be2004-03-30 19:53:46 +0000168/// runOnFunction - Per function pass for combining branches.
169///
170bool 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 Shukla89233e12003-07-18 16:08:32 +0000176 std::map<BasicBlock *, int> d;
177 std::map<BasicBlock *, BasicBlock *> be;
Brian Gaekeef327be2004-03-30 19:53:46 +0000178 int time = 0;
179 getBackEdgesVisit (F.begin (), color, d, time, be);
180 removeRedundant (be);
Anand Shukla89233e12003-07-18 16:08:32 +0000181
Brian Gaekeef327be2004-03-30 19:53:46 +0000182 return true; // FIXME: assumes a modification was always made.
Anand Shukla89233e12003-07-18 16:08:32 +0000183}
Brian Gaeke960707c2003-11-11 22:41:34 +0000184
Brian Gaeke33e834e2004-09-30 20:14:29 +0000185FunctionPass *createCombineBranchesPass () {
186 return new CombineBranches();
187}
188
Brian Gaeke960707c2003-11-11 22:41:34 +0000189} // End llvm namespace