1.3.10. EquivBUDataStructures遍
EquivBUDataStructures是CompleteBUDataStructures的更進一步，它會為每個函數同類集産生一個簡并的函數圖，并以這個簡并圖作為同類集中每個函數的圖。然後在此基礎上，在前面CompleteDataStructure遍産生的調用鍊SCC上進行函數圖内聯。由此，函數圖的個數，進而DSNode節點的個數将進一步減少。注意，這裡的同類集不是調用鍊同類集，而是記憶體對象同類集（即由同一個DSNode代表）。
42 bool EquivBUDataStructures::runOnModule(Module&M) {
43 init(&getAnalysis<CompleteBUDataStructures>(),true, true, false, true);
44
45 //make a list ofall the DSGraphs
46 std::set<DSGraph *>graphList;
47 for(Module::iteratorF = M.begin(); F != M.end(); ++F)
48 {
49 if(!(F->isDeclaration()))
50 graphList.insert(getOrCreateGraph(F));
51 }
52
53 //update the EQclass from indirect calls
54 buildIndirectFunctionSets();
55 formGlobalECs();
56 mergeGraphsByGlobalECs();
EquivBUDataStructures前面的幾步與CompleteBUDataStructures的前幾步是一樣的。不過這些操作是在CompleteBUDataStructures處理的結果上進行的。上面55行對最新的處理結果更新了同類集關系，56行的mergeGraphsByGlobalECs将函數同類集的圖進行簡并。
GlobalECs是一個同類集的容器，下面140及141行分别傳回這個集合的首尾疊代器。142行的循環周遊這個集合，146行篩選掉不是Leader的成員。154行的member_iterator用于周遊某一個Leader所在的同類集（Leader總是這個同類集的首元素），155行就是周遊這個集合。這裡的同類集由同一塊記憶體所代表的對象組成，156行篩選出Function（函數）類型的對象。這裡隻處理函數的同類集。
對于某個同類集，176行的BaseGraph在一開始為0（147行處指派），177、178行擷取對應的DSGraph及指向傳回值、可變參數、指針參數的DSNodeHandle節點。如果函數已經處理過，滿足179行條件，我們需要簡并這兩次（甚至可能更多次）給出的參數，因為這兩（幾）次給出的參數的數目不一定相同，需要形如202~207行的處理。如果BaseGraph不是空，而指定函數尚未處理（214行條件），BaseGraph中的是同類集中的其他函數，那麼218行通過cloneInto把函數圖拷貝、簡并入BaseGraph，接着簡并參數。
131 void
132 EquivBUDataStructures::mergeGraphsByGlobalECs() {
133 //
134 // Merge thegraphs for each equivalence class. Wefirst scan all elements
135 // in theequivalence classes and look for those elements which are leaders.
136 // For eachleader, we scan through all of its members and merge the DSGraphs
137 // for memberswhich are functions.
138 //
139
140 EquivalenceClasses<const GlobalValue*>::iterator EQSI = GlobalECs.begin();
141 EquivalenceClasses<const GlobalValue*>::iterator EQSE = GlobalECs.end();
142 for (;EQSI !=EQSE; ++EQSI) {
143 //
144 // If thiselement is not a leader, then skip it.
145 //
146 if (!EQSI->isLeader()) continue;
147 DSGraph* BaseGraph = 0;
148 std::vector<DSNodeHandle> Args;
149
150 //
151 // Iteratethrough all members of this equivalence class, looking for
152 // functions.
153 //
154 EquivalenceClasses<const GlobalValue*>::member_iterator MI;
155 for (MI =GlobalECs.member_begin(EQSI); MI != GlobalECs.member_end(); ++MI){
156 if (constFunction* F = dyn_cast<Function>(*MI)) {
157 //
158 // If thefunction has no body, then it has no DSGraph.
159 //
160 // FIXME: Idon't believe this is correct; the stdlib pass can assign
161 // DSGraphs to C standard libraryfunctions.
162 //
163 if (F->isDeclaration())
164 continue;
165
166 //
167 // We haveone of three possibilities:
168 // 1) This is the first function we'veseen. If so, grab its DSGraph
169 // and the DSNodes for its arguments.
170 //
171 // 2) We have already seen this functionbefore. Do nothing.
172 //
173 // 3) We haven't seen this function before, andit's not the first one
174 // we've seen. Merge its DSGraph into the DSGraph we'recreating.
175 //
176 if (!BaseGraph) {
177 BaseGraph = getOrCreateGraph(F);
178 BaseGraph->getFunctionArgumentsForCall(F,Args);
179 } else if(BaseGraph->containsFunction(F)) {
180 //
181 // TheDSGraph for this function has already been merged into the
182 // graphthat we are creating. However, that doesnot mean that
183 //function arguments of this function have been merged with the
184 // functionarguments of the other functions in the equivalence graph
185 // (oreven with functions belonging to the same SCC in the call
186 //graph). Furthermore, it doesn'tnecessarily imply that the
187 //contained function's DSGraph is the same as the one we're
188 //building; it is possible (I think) for only the function's DSNodes
189 // andother information to have been merged in.
190 //
191 // Forthese reasons, we will merge the function argument DSNodes and
192 // setthis function's DSGraph to be the same graph used for all
193 // otherfunction's in this equivalence class.
194 //
195
196 //
197 // Mergethe arguments together.
198 //
199 std::vector<DSNodeHandle>NextArgs;
200 BaseGraph->getFunctionArgumentsForCall(F,NextArgs);
201 unsigned i = 0, e = Args.size();
202 for(; i != e; ++i) {
203 if (i == NextArgs.size()) break;
204 Args[i].mergeWith(NextArgs[i]);
205 }
206 for(e = NextArgs.size(); i != e; ++i)
207 Args.push_back(NextArgs[i]);
208
209 //
210 // Makethis function use the DSGraph that we're creating for all of
211 // thefunctions in this equivalence class.
212 //
213 setDSGraph(*F, BaseGraph);
214 } else {
215 //
216 // Mergein the DSGraph.
217 //
218 BaseGraph->cloneInto(getOrCreateGraph(F));
219
220 //
221 // Merge thearguments together.
222 //
223 std::vector<DSNodeHandle>NextArgs;
224 BaseGraph->getFunctionArgumentsForCall(F,NextArgs);
225 unsigned i = 0, e = Args.size();
226 for(; i != e; ++i) {
227 if (i == NextArgs.size()) break;
228 Args[i].mergeWith(NextArgs[i]);
229 }
230 for(e = NextArgs.size(); i != e; ++i)
231 Args.push_back(NextArgs[i]);
232
233 //
234 // Makethis function use the DSGraph that we're creating for all of
235 // thefunctions in this equivalence class.
236 //
237 setDSGraph(*F, BaseGraph);
238 }
239 }
240 }
241
242 //
243 // Update theglobals graph with any information that has changed due to
244 // graphmerging.
245 //
246 if (BaseGraph)
247 cloneIntoGlobals(BaseGraph,DSGraph::DontCloneCallNodes |
248 DSGraph::DontCloneAuxCallNodes |
249 DSGraph::StripAllocaBit);
250 }
251 }
對于簡并同類集最後得到的BaseGraph，在247行把其中的資訊拷貝回全局圖。因為在上面213及237行處把同類集中所有的函數的圖都設定為BaseGraph，接下來59~63行把BaseGraph從graphList先行除去（因為BaseGraph可以與graphList中的圖相同，參考177行，這對應同類集隻包含一個函數的情況。否則BaseGraph是建立的，graphList中沒有記錄），然後在65~76行，把其餘圖删除。
EquivBUDataStructures::runOnModule（續）
58 //remove all theDSGraph, that still have references
59 for(Module::iteratorF = M.begin(); F != M.end(); ++F)
60 {
61 if(!(F->isDeclaration()))
62 graphList.erase(getOrCreateGraph(F));
63 }
64 // free memoryfor the DSGraphs, no longer in use.
65 for(std::set<DSGraph*>::iteratori = graphList.begin(),e = graphList.end();
66 i!=e;i++) {
67 delete(*i);
68 }
69 DEBUG(verifyMerging());
70
71 formGlobalECs();
72
73 for(Module::iterator F = M.begin(); F != M.end(); ++F) {
74 if (!(F->isDeclaration())) {
75 if (DSGraph * Graph =getOrCreateGraph(F)) {
76 cloneGlobalsInto(Graph, DSGraph::DontCloneCallNodes|
77 DSGraph::DontCloneAuxCallNodes);
78 }
79 }
80 }
81
82 bool result = runOnModuleInternal(M);
83
84 // CBU containsthe correct call graph.
85 // Restore it, sothat subsequent passes and clients can get it.
86 restoreCorrectCallGraph();
87 returnresult;
88 }
71~82行的處理與BUDataStructure相同，但它是在CompleteDataStructure結果的基礎上進行的。在86行，通過下面的函數把callgraph恢複為CompleteDataStructure給出的樣子。這是因為callgraph反映的是實際函數的調用情況，盡管調用鍊SCC裡的函數調用由其Leader來代表，EquivBUDataStructures實際上不應該改變callgraph，它隻是簡并同類集函數的圖，減少節點數。但以目前的實作，EquivBUDataStructures有可能改變callgraph。
1512 void DataStructures::restoreCorrectCallGraph(){
1513 callgraph = GraphSource->callgraph;
1514 }
其中的GraphSource是在init時設定的，指向CompleteDataStructure的執行個體。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)