00001 /* 00002 * Copyright 2003, 2004, 2005, 2006 PathScale, Inc. All Rights Reserved. 00003 */ 00004 00005 /* 00006 00007 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00008 00009 This program is free software; you can redistribute it and/or modify it 00010 under the terms of version 2 of the GNU General Public License as 00011 published by the Free Software Foundation. 00012 00013 This program is distributed in the hope that it would be useful, but 00014 WITHOUT ANY WARRANTY; without even the implied warranty of 00015 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 00017 Further, this software is distributed without any warranty that it is 00018 free of the rightful claim of any third person regarding infringement 00019 or the like. Any license provided herein, whether implied or 00020 otherwise, applies only to this software file. Patent licenses, if 00021 any, provided herein do not apply to combinations of this program with 00022 other software, or any other product whatsoever. 00023 00024 You should have received a copy of the GNU General Public License along 00025 with this program; if not, write the Free Software Foundation, Inc., 59 00026 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00027 00028 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00029 Mountain View, CA 94043, or: 00030 00031 http://www.sgi.com 00032 00033 For further information regarding this notice, see: 00034 00035 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00036 00037 */ 00038 00039 00040 #define __STDC_LIMIT_MACROS 00041 #include <stdint.h> 00042 #if defined(BUILD_OS_DARWIN) 00043 #include <darwin_elf.h> 00044 #else /* defined(BUILD_OS_DARWIN) */ 00045 #include <elf.h> 00046 #endif /* defined(BUILD_OS_DARWIN) */ 00047 #include "assert.h" 00048 #include "defs.h" 00049 #include "mempool.h" 00050 #include "errors.h" 00051 #include "ip_graph.h" 00052 #include "ipa_cg.h" 00053 #include "ipa_df.h" 00054 00055 /*---------------------------------------------------------------------*/ 00056 /* reverse the graph for backward data flow problems */ 00057 /*---------------------------------------------------------------------*/ 00058 static void reverse_graph(GRAPH *g) 00059 { 00060 NODE_INDEX v; 00061 EDGE_INDEX e, e2; 00062 00063 00064 /* switch from vertex to to vertex */ 00065 /* switch to vertex to from vertex */ 00066 00067 for (v=0; v<GRAPH_vmax(g); v++) 00068 if (NODE_fcnt(&GRAPH_v_i(g,v)) != -1) 00069 { 00070 e = NODE_from(&GRAPH_v_i(g,v)); 00071 NODE_from(&GRAPH_v_i(g,v)) = NODE_to(&GRAPH_v_i(g,v)); 00072 NODE_to(&GRAPH_v_i(g,v)) = e; 00073 } 00074 00075 00076 for(e=0;e<GRAPH_emax(g);e++) 00077 { 00078 if (EDGE_from(&GRAPH_e_i(g,e)) != -1) 00079 { 00080 v = EDGE_from(&GRAPH_e_i(g,e)); 00081 EDGE_from(&GRAPH_e_i(g,e)) = EDGE_to(&GRAPH_e_i(g,e)); 00082 EDGE_to(&GRAPH_e_i(g,e)) = v; 00083 e2 = EDGE_nfrom(&GRAPH_e_i(g,e)); 00084 EDGE_nfrom(&GRAPH_e_i(g,e)) = EDGE_nto(&GRAPH_e_i(g,e)); 00085 EDGE_nto(&GRAPH_e_i(g,e)) = e2; 00086 } 00087 } 00088 } 00089 00090 /*---------------------------------------------------------------------*/ 00091 /* add entry and exit nodes, connect the entire graph */ 00092 /*---------------------------------------------------------------------*/ 00093 static void 00094 pre_process_graph ( GRAPH *g, DFS *df, MEM_POOL * ) 00095 { 00096 NODE_INDEX exit, v; 00097 00098 exit = g->Add_Node(0); 00099 00100 /* iterate over all the vertices */ 00101 00102 for (v=0; v < GRAPH_vmax(g); v++) { 00103 if (NODE_fcnt(&GRAPH_v_i(g,v)) != -1) { 00104 00105 /* if the vertex has no successors, create an edge from vertex 00106 to exit */ 00107 if (g->Num_Succs(v) == 0) { 00108 if (v != exit) 00109 g->Add_Edge(v, exit, 0); 00110 } 00111 } 00112 } 00113 /* set the root of the graph to be the entry vertex */ 00114 // GRAPH_root(g) = entry; 00115 00116 DFS_exit(df) = exit; 00117 } 00118 00119 /*---------------------------------------------------------------------*/ 00120 /* remove the entry and exit nodes, restore graph to original form */ 00121 /*---------------------------------------------------------------------*/ 00122 static void post_process_graph(GRAPH *g, DFS *df) 00123 { 00124 /* delete those unneccesary vertices, all edges originating to and from */ 00125 /* the vertices will be eliminated by default */ 00126 00127 g->Delete_Node(DFS_exit(df)); 00128 00129 } 00130 //----------------------------------------------------------------- 00131 // initialize the node annotation 00132 //------------------------------------------------------------------ 00133 void 00134 IPA_DATA_FLOW::Init() 00135 { 00136 INT i; 00137 DFN *d; 00138 00139 /* note at this point the exit vertex has not yet been set */ 00140 /* get the depth first ordering of the vertices */ 00141 d = DFS_d(df); 00142 00143 for ( i=DFN_first(d); i< DFN_end(d); ++i ) { 00144 INT vindex = DFN_v_list_i(d,i); 00145 00146 if (vindex == DFS_entry(df)) 00147 continue; 00148 InitializeNode ( NODE_user(&GRAPH_v_i(IPA_Call_Graph->Graph(),vindex)) ); 00149 } 00150 } 00151 00152 /*----------------------------------------------------------------------*/ 00153 /* perform meet operation on incoming edges, transfer the result to out.*/ 00154 /* the parameters passed to meet are the sets being meeted into (in), */ 00155 /* the predecessor's current data flow set (pred_set), the annotation */ 00156 /* obtained from the local phase for the current vertex, and the */ 00157 /* edge annotation obtained from the local phase. This is for the */ 00158 /* first iteration. For the next iterations, it reflects the result of */ 00159 /* the trans operation. */ 00160 /* For a call graph, local node annotation corresponds to summary */ 00161 /* information collected for a function or procedure and edge */ 00162 /* annotation refers to summary information collected for a call site */ 00163 /* the parameters passed to trans is the result of the meet operation */ 00164 /* and the previous out annotation and the variable change which */ 00165 /* is used to determine if the data flow problem has settled. */ 00166 /*----------------------------------------------------------------------*/ 00167 void IPA_DATA_FLOW::iterative_solver(DFS *df) 00168 { 00169 DFN *d; 00170 NODE_INDEX i; 00171 00172 /* get the depth first ordering of the vertices */ 00173 d = DFS_d(df); 00174 00175 // Make sure that d is not empty: 00176 assert ( d != NULL ); 00177 00178 // for a forward problem 00179 if (DFS_di(df) == FORWARD) 00180 { 00181 /* For all vertices in depth first ordering, perform meet and trans */ 00182 for ( i=DFN_first(d); i< DFN_end(d); ++i) { 00183 INT vindex = DFN_v_list_i(d,i); 00184 00185 if (vindex == DFS_entry(df) || vindex == DFS_exit(df)) 00186 /* avoid those entry nodes, since they are there */ 00187 /* to connect the entire graph */ 00188 continue; 00189 00190 /* compute the meet of incoming edge and existing in. for 00191 the meet operation, pass the in set, the predecessors 00192 out annotation, the current node annotation and current 00193 edge annotation note, for a call graph and the forward 00194 dataflow problem, the current node annotation refers to 00195 the callee and the edge annotation refers to the 00196 callsite note, the meet operation will delete the old 00197 in and return the new in. 00198 */ 00199 00200 Meet (0, 00201 NODE_user (&GRAPH_v_i (IPA_Call_Graph->Graph(), 00202 vindex)), 00203 &DFS_change(df)); 00204 00205 /* for the trans operation, pass the in set, the out set, */ 00206 /* and the current node annotation (for a call graph, it is the */ 00207 /* procedure node) and change to determine if the dataflow */ 00208 /* problem has settled. */ 00209 /* note, the trans operation will delete the old out and return */ 00210 /* the new out */ 00211 00212 Trans (0, 00213 0, 00214 NODE_user (&GRAPH_v_i (IPA_Call_Graph->Graph(), 00215 vindex)), 00216 &DFS_change(df)); 00217 00218 } 00219 } 00220 else 00221 // for a backward problem go from last to first 00222 { 00223 for (i = DFN_end(d)-1; i >= DFN_first(d); --i) 00224 { 00225 INT vindex = DFN_v_list_i(d,i); 00226 00227 if (vindex == DFS_entry(df) || vindex == DFS_exit(df)) 00228 /* avoid those entry nodes, since they are there */ 00229 /* to connect the entire graph */ 00230 continue; 00231 Meet (0, 00232 NODE_user (&GRAPH_v_i (IPA_Call_Graph->Graph(), 00233 vindex)), 00234 &DFS_change(df)); 00235 00236 Trans (DFS_in_i(df,vindex), 00237 DFS_out_i(df,vindex), 00238 NODE_user (&GRAPH_v_i (IPA_Call_Graph->Graph(), 00239 vindex)), 00240 &DFS_change(df)); 00241 } 00242 } 00243 } 00244 00245 00246 // When clone nodes are added to the graph during constant propagation 00247 // Depth-First Numbering of nodes needs to be rebuilt. 00248 BOOL IPA_Should_Rebuild_DFN; 00249 00250 /*---------------------------------------------------------------------*/ 00251 /* solve the data flow problem */ 00252 /*---------------------------------------------------------------------*/ 00253 void IPA_DATA_FLOW::dataflow(DFS *df) 00254 { 00255 NODE_INDEX tmp, root_node; 00256 INT i; 00257 00258 root_node = IPA_Call_Graph->Root(); 00259 pre_process_graph(IPA_Call_Graph->Graph(), df, m); 00260 00261 IPA_Call_Graph->Set_Root(DFS_entry(df)); 00262 00263 if (DFS_di(df) == BACKWARD) 00264 { 00265 if ( DFS_d(df) == NULL ) { 00266 DFS_d(df) = Depth_First_Ordering ( IPA_Call_Graph->Graph(), m ); 00267 } 00268 } 00269 00270 /* create the in, out annotations for all vertices */ 00271 DFS_in(df) = (void **) 00272 MEM_POOL_Alloc ( m, sizeof(void*) * GRAPH_vmax(IPA_Call_Graph->Graph()) ); 00273 00274 assert(DFS_in(df) != 0); 00275 bzero(DFS_in(df), sizeof(void*)*GRAPH_vmax(IPA_Call_Graph->Graph())); 00276 00277 DFS_out(df) = (void**) 00278 MEM_POOL_Alloc(m, sizeof(void*)*GRAPH_vmax(IPA_Call_Graph->Graph())); 00279 bzero(DFS_out(df), sizeof(void*)*GRAPH_vmax(IPA_Call_Graph->Graph())); 00280 assert(DFS_out(df) != 0); 00281 00282 DFS_change(df) = 1; 00283 00284 /* while the data flow problem has not settled do */ 00285 while(DFS_change(df)) { 00286 00287 /* reset change to 0, during the trans operation, if the new out */ 00288 /* is different from the old out then the problem has not settled */ 00289 /* and change must be set to 1 */ 00290 DFS_change(df) = 0; 00291 IPA_Should_Rebuild_DFN = FALSE; 00292 00293 /* call the iterative dataflow solver */ 00294 iterative_solver(df); 00295 00296 if (IPA_Should_Rebuild_DFN) { 00297 DFS_d(df) = Depth_First_Ordering(IPA_Call_Graph->Graph(), m); 00298 } 00299 } 00300 00301 00302 /* this pass is used if any post processing is needed. */ 00303 /* in the case of constant propagation, the tcons need to be reset */ 00304 00305 DFN* dd = DFS_d(df); 00306 for ( i=DFN_first(dd); i< DFN_end(dd); ++i ) { 00307 INT vindex = DFN_v_list_i(dd,i); 00308 if (vindex == DFS_entry(df) || vindex == DFS_exit(df)) 00309 continue; 00310 PostProcessIO(NODE_user(&GRAPH_v_i(IPA_Call_Graph->Graph(),vindex))); 00311 } 00312 00313 /* post process the graph, remove the exit and entry and additional edges */ 00314 post_process_graph(IPA_Call_Graph->Graph(),df); 00315 IPA_Call_Graph->Set_Root(root_node); 00316 } 00317 00318 /*---------------------------------------------------------------------*/ 00319 /* This routine must be invoked to start a data flow problem */ 00320 /* It sets up all the fields in the DFS data structure and */ 00321 /* solves the dataflow problem using an iterative solution */ 00322 /*---------------------------------------------------------------------*/ 00323 void IPA_DATA_FLOW::Solve() 00324 { 00325 dataflow(df); 00326 } 00327 00328 /*----------------------------------------------------------------------*/ 00329 /* clone a particular node */ 00330 /*----------------------------------------------------------------------*/ 00331 IPA_NODE* IPA_DATA_FLOW::Clone(IPA_NODE* n) 00332 { 00333 return IPA_Call_Graph->Create_Clone(n); 00334 } 00335 00336 /*----------------------------------------------------------------------*/ 00337 /* the in annotation is the current in for the vertex, */ 00338 /* edge_in is the in annotation for the incoming edge. vertex is the */ 00339 /* caller, edge is the callsite */ 00340 /* return the result of the meet operation, which is the out set */ 00341 /*----------------------------------------------------------------------*/ 00342 00343 void * 00344 IPA_DATA_FLOW::Meet ( void* , void* vertex, INT * ) 00345 { 00346 IPA_NODE *n = (IPA_NODE *)vertex; 00347 fprintf ( TFile, "Entered the MEET function \n" ); 00348 return 0; 00349 } 00350 00351 /*----------------------------------------------------------------------*/ 00352 /* return the new out set. */ 00353 /*----------------------------------------------------------------------*/ 00354 00355 void * 00356 IPA_DATA_FLOW::Trans ( void *, void *, void *vertex, INT *) 00357 { 00358 /* IPA_NODE *nclone; */ 00359 IPA_NODE *n = (IPA_NODE *)vertex; 00360 fprintf ( TFile, "Entered the trans function \n" ); 00361 /* nclone = Clone(n); */ 00362 return 0; 00363 } 00364 00365 /*----------------------------------------------------------------------*/ 00366 /* get the caller, given the edge */ 00367 /*----------------------------------------------------------------------*/ 00368 IPA_NODE* 00369 IPA_DATA_FLOW::Get_caller(IPA_EDGE *edge) 00370 { 00371 return IPA_Call_Graph->Caller (edge); 00372 } 00373 00374 /*----------------------------------------------------------------------*/ 00375 /* get the callee, given the edge */ 00376 /*----------------------------------------------------------------------*/ 00377 IPA_NODE* IPA_DATA_FLOW::Get_callee(IPA_EDGE *edge) 00378 { 00379 return IPA_Call_Graph->Callee (edge); 00380 } 00381 00382 /*----------------------------------------------------------------------*/ 00383 /* constructor */ 00384 /*----------------------------------------------------------------------*/ 00385 IPA_DATA_FLOW::IPA_DATA_FLOW (DF_DIRECTION ddf, MEM_POOL *mm) 00386 { 00387 m = mm; 00388 d = ddf; 00389 00390 df = (DFS*) MEM_POOL_Alloc(m,sizeof(DFS)); 00391 00392 DFS_di(df) = d; 00393 00394 // note, build the depth first ordering only for a forward problem 00395 // for a backward problem, build it after the graph has been 00396 // reversed 00397 00398 // build a depth first ordering of the graph 00399 DFS_d(df) = Depth_First_Ordering ( IPA_Call_Graph->Graph(), m ); 00400 DFS_entry(df) = IPA_Call_Graph->Root(); 00401 00402 } 00403 00404 //---------------------------------------------------------------------- 00405 // print the output after solving the dataflow problem 00406 //---------------------------------------------------------------------- 00407 void 00408 IPA_DATA_FLOW::Print(FILE* fp) 00409 { 00410 INT i; 00411 00412 if (df == NULL) 00413 Fail_FmtAssertion("You cannot print before solving the problem!! \n"); 00414 00415 DFN* dd = DFS_d(df); 00416 for ( i=DFN_first(dd); i< DFN_end(dd); ++i ) { 00417 INT vindex = DFN_v_list_i(dd,i); 00418 if (vindex == DFS_entry(df) || vindex == DFS_exit(df)) 00419 continue; 00420 if (NODE_user(&GRAPH_v_i(IPA_Call_Graph->Graph(),vindex)) != NULL) 00421 Print_entry(fp, DFS_out_i(df,vindex), 00422 NODE_user(&GRAPH_v_i(IPA_Call_Graph->Graph(),vindex))); 00423 } 00424 } 00425 00426 //---------------------------------------------------------------------- 00427 // print the output for each entry 00428 //---------------------------------------------------------------------- 00429 void 00430 IPA_DATA_FLOW::Print_entry ( FILE *fp, void *, void *) 00431 { 00432 fprintf ( fp, "Entered the print_entry function \n" ); 00433 }
1.5.6