#include <stdlib.h>#include <stdio.h>#include <string.h>#include <limits.h>#include "genC.h"#include "boolean.h"#include "vecteur.h"#include "contrainte.h"#include "sc.h"#include "ray_dte.h"#include "sommet.h"#include "sg.h"#include "polyedre.h"#include "union.h"#include "matrix.h"#include "ri.h"#include "graph.h"#include "dg.h"#include "misc.h"#include "ri-util.h"#include "properties.h"#include "constants.h"#include "rice.h"#include "ricedg.h"#include "complexity_ri.h"#include "database.h"#include "makefile.h"#include "parser_private.h"#include "property.h"#include "reduction.h"#include "tiling.h"#include "text.h"#include "text-util.h"#include "pipsdbm.h"#include "paf_ri.h"#include "paf-util.h"#include "resources.h"#include "scheduling.h"Go to the source code of this file.
Defines | |
| #define | MY_MIN(a, b) ((a)>(b)?(b):(a)) |
| =================================================================== | |
| #define | NEW_MARK 1 |
| #define | OLD_MARK 2 |
| #define | DFG_MARK_OLD(v) |
| #define | DFG_MARK_NEW(v) |
| #define | DFG_MARKED_NEW_P(v) |
| #define | DFG_VERTEX_ENCLOSING_SCC(v) |
Typedefs | |
| typedef dfg_arc_label | arc_label |
| lint | |
| typedef dfg_vertex_label | vertex_label |
Functions | |
| int | dfg_is_in_stack (vertex v) |
| ================================================================= | |
| void | dfg_low_link_compute (graph g, vertex v) |
| ================================================================= | |
| sccs | dfg_find_sccs (graph g) |
| ================================================================= | |
| void | fprint_sccs (FILE *fp, sccs obj) |
| =========================================================================== | |
| vertex | dfg_in_vertex_list (list l, vertex v) |
| ================================================================= | |
| graph | dfg_reverse_graph (graph g) |
| ====================================================================== | |
Variables | |
| char | vcid_scheduling_sccdfg [] = "$Id: sccdfg.c 16236 2010-03-04 14:39:43Z guelton $" |
| static int | Count |
| A set of variables shared by the functions of this package. | |
| static int | StackPointer |
| static vertex * | Stack |
| static sccs | Components |
| #define DFG_MARK_NEW | ( | v | ) |
| #define DFG_MARK_OLD | ( | v | ) |
Definition at line 106 of file sccdfg.c.
Referenced by dfg_low_link_compute().
| #define DFG_MARKED_NEW_P | ( | v | ) |
Definition at line 112 of file sccdfg.c.
Referenced by dfg_find_sccs(), and dfg_low_link_compute().
| #define DFG_VERTEX_ENCLOSING_SCC | ( | v | ) |
===================================================================
This collection of functions implements Tarjan's algorithm to find the strongly connected components of a directed graph.
this algorithm is presented in: Types de Donnees et Algorithmes Recherche, Tri, Algorithmes sur les Graphes Marie-Claude Gaudel, Michele Soria, Christine Froidevaux Collection Didactique INRIA ==================================================================== A set of macros to mark a vertex as 'not visited' or 'visited' andto check if a node has already been visited.
| typedef dfg_arc_label arc_label |
| typedef dfg_vertex_label vertex_label |
=================================================================
dfg_find_sccs is the interface function to compute the SCCs of a graph. It marks all nodes as 'not visited' and then apply the main function dfg_low_link_compute() on all vertices.
AC 93/10/19
Definition at line 224 of file sccdfg.c.
References CAR, CDR, Count, dfg_low_link_compute(), DFG_MARKED_NEW_P, dfg_vertex_label_sccflags, free(), gen_length(), graph_vertices, make_sccflags(), make_sccs(), malloc(), MAPL, NIL, scc_undefined, StackPointer, v, VERTEX, and vertex_vertex_label.
Referenced by scheduling().
00227 { 00228 cons *vertices = graph_vertices(g), *pv; 00229 00230 Count = 1; 00231 StackPointer = 0; 00232 Stack = (vertex *)malloc(sizeof(vertex) * gen_length(vertices)); 00233 Components = make_sccs(NIL); 00234 00235 for (pv = vertices; pv != NIL; pv = CDR(pv)) 00236 { 00237 vertex v = VERTEX(CAR(pv)); 00238 dfg_vertex_label lv = (dfg_vertex_label) vertex_vertex_label(v); 00239 dfg_vertex_label_sccflags(lv) = make_sccflags(scc_undefined,1,0,0); 00240 } 00241 00242 MAPL(pv, { 00243 vertex v = VERTEX(CAR(pv)); 00244 if (DFG_MARKED_NEW_P(v)) dfg_low_link_compute(g, v); 00245 }, vertices); 00246 00247 free(Stack); 00248 00249 return(Components); 00250 }
=================================================================
The following functions are used to build the reverse graph of a dataflow graph ===================================================================================================================================vertex dfg_in_vertex_list((list) l, (vertex) v): Input : A list l of vertices. A vertex v of a dataflow graph. Returns vertex_undefined if v is not in list l. Returns v' that has the same statement_ordering than v.
AC 93/10/19
Definition at line 309 of file sccdfg.c.
References CAR, dfg_vertex_label_statement, ENDP, i, POP, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by dfg_reverse_graph().
00313 { 00314 vertex ver; 00315 int p, i; 00316 00317 i = dfg_vertex_label_statement((dfg_vertex_label)\ 00318 vertex_vertex_label(v)); 00319 for ( ; !ENDP(l); POP(l)) 00320 { 00321 ver = VERTEX(CAR(l)); 00322 p = dfg_vertex_label_statement((dfg_vertex_label)\ 00323 vertex_vertex_label(ver)); 00324 if (p == i) return(ver); 00325 } 00326 00327 return (vertex_undefined); 00328 }
| int dfg_is_in_stack | ( | vertex | v | ) |
=================================================================
int dfg_is_in_stack(v) : this function checks if vertex v is in the stack.
AC 93/10/18
Definition at line 136 of file sccdfg.c.
References FALSE, i, StackPointer, and TRUE.
Referenced by dfg_low_link_compute().
00139 { 00140 int i; 00141 00142 for (i = 0; i < StackPointer; i++) 00143 if (Stack[i] == v) return(TRUE); 00144 00145 return(FALSE); 00146 }
=================================================================
dfg_low_link_compute() is the main function. Its behavior is explained in the book mentionned ealier.
AC 93/10/18
Definition at line 155 of file sccdfg.c.
References CAR, CONS, Count, dfg_is_in_stack(), DFG_MARK_OLD, DFG_MARKED_NEW_P, dfg_vertex_label_sccflags, gen_nconc(), make_scc(), MAPL, MY_MIN, NIL, s, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccs_sccs, StackPointer, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by dfg_find_sccs().
00159 { 00160 dfg_vertex_label dvl = (dfg_vertex_label)vertex_vertex_label(v); 00161 sccflags fv = dfg_vertex_label_sccflags(dvl); 00162 00163 DFG_MARK_OLD(v); 00164 00165 sccflags_lowlink(fv) = Count; 00166 sccflags_dfnumber(fv) = Count; 00167 00168 Count ++; 00169 00170 Stack[StackPointer++] = v; 00171 00172 MAPL(ps, { 00173 vertex s = successor_vertex(SUCCESSOR(CAR(ps))); 00174 if (s != (vertex)NIL) 00175 { 00176 sccflags fs = dfg_vertex_label_sccflags((dfg_vertex_label)\ 00177 vertex_vertex_label(s)); 00178 if (DFG_MARKED_NEW_P(s)) 00179 { 00180 dfg_low_link_compute(g, s); 00181 sccflags_lowlink(fv) = MY_MIN(sccflags_lowlink(fv),\ 00182 sccflags_lowlink(fs)); 00183 } 00184 else 00185 { 00186 if ((sccflags_dfnumber(fs) < sccflags_dfnumber(fv)) &&\ 00187 dfg_is_in_stack(s)) 00188 sccflags_lowlink(fv) = MY_MIN(sccflags_dfnumber(fs),\ 00189 sccflags_lowlink(fv)); 00190 } 00191 } 00192 }, vertex_successors(v)); 00193 00194 if (sccflags_lowlink(fv) == sccflags_dfnumber(fv)) 00195 { 00196 scc ns = make_scc(NIL, 0); 00197 vertex p; 00198 sccflags fp; 00199 cons *pv = NIL; 00200 00201 do 00202 { 00203 p = Stack[--StackPointer]; 00204 fp = dfg_vertex_label_sccflags((dfg_vertex_label)\ 00205 vertex_vertex_label(p)); 00206 sccflags_enclosing_scc(fp) = ns; 00207 pv = gen_nconc(pv, CONS(VERTEX, p, NIL)); 00208 } while (v != p); 00209 00210 scc_vertices(ns) = pv; 00211 sccs_sccs(Components) = gen_nconc(sccs_sccs(Components),\ 00212 CONS(SCC, ns, NIL)); 00213 } 00214 }
======================================================================
graph dfg_reverse_graph((graph) g): This function is used to reverse Pips's graph in order to have all possible sources directly (Feautrier's dependance graph).
AC 93/10/19
Definition at line 340 of file sccdfg.c.
References ADD_ELEMENT_TO_LIST, CAR, copy_dfg_vertex_label(), dfg_in_vertex_list(), graph_undefined, graph_vertices, make_graph(), make_successor(), make_vertex(), MAPL, NIL, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by scheduling().
00343 { 00344 graph rev_graph = graph_undefined; 00345 list vlist = NIL, li = NIL; 00346 successor succ, succ2; 00347 vertex v1, v2, v3, v4, v5; 00348 00349 MAPL(ver_ptr,{ 00350 v1 = VERTEX(CAR(ver_ptr)); 00351 v5 = dfg_in_vertex_list(vlist, v1); 00352 if (v5 == vertex_undefined) 00353 { 00354 v2 = make_vertex(copy_dfg_vertex_label((dfg_vertex_label)\ 00355 vertex_vertex_label(v1)), NIL); 00356 ADD_ELEMENT_TO_LIST(vlist, VERTEX, v2); 00357 } 00358 else v2 = v5; 00359 00360 MAPL(succ_ptr, { 00361 li = NIL; 00362 succ = SUCCESSOR(CAR(succ_ptr)); 00363 v3 = successor_vertex(succ); 00364 v5 = dfg_in_vertex_list(vlist, v3); 00365 succ2 = make_successor((dfg_arc_label)\ 00366 successor_arc_label(succ), v2); 00367 if (v5 == vertex_undefined) 00368 { 00369 ADD_ELEMENT_TO_LIST(li, SUCCESSOR, succ2); 00370 v4 = make_vertex(copy_dfg_vertex_label((dfg_vertex_label)\ 00371 vertex_vertex_label(v3)), li); 00372 ADD_ELEMENT_TO_LIST(vlist, VERTEX, v4); 00373 } 00374 else 00375 ADD_ELEMENT_TO_LIST(vertex_successors(v5),\ 00376 SUCCESSOR, succ2); 00377 }, vertex_successors(v1)); 00378 }, graph_vertices(g)); 00379 rev_graph = make_graph(vlist); 00380 00381 return(rev_graph); 00382 }
| void fprint_sccs | ( | FILE * | fp, | |
| sccs | obj | |||
| ) |
===========================================================================
void fprint_sccs(FILE *fp, sccs obj): prints in the file "fp" the list of strongly connected components "obj".
AC 93/10/20
Definition at line 259 of file sccdfg.c.
References CAR, CDR, DATAFLOW, dfg_arc_label_dataflows, fprint_dataflow(), fprintf(), NIL, SCC, scc_vertices, sccs_sccs, sink_stmt, source_stmt, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_int_stmt(), and vertex_successors.
Referenced by scheduling().
00263 { 00264 list nodes_l, su_l, df_l, scc_l; 00265 int source_stmt, sink_stmt; 00266 int iter = 0; 00267 00268 fprintf(fp,"\n Graphe des Composantes Connexes :\n"); 00269 fprintf(fp,"==================================\n"); 00270 00271 for(scc_l = sccs_sccs(obj); scc_l != NIL; scc_l = CDR(scc_l)) 00272 { 00273 scc scc_an = SCC(CAR(scc_l)); 00274 iter++; 00275 fprintf(fp,"\ncomposante %d :\n",iter); 00276 for(nodes_l=scc_vertices(scc_an);nodes_l !=NIL;nodes_l=CDR(nodes_l)) 00277 { 00278 vertex crt_v = VERTEX(CAR(nodes_l)); 00279 source_stmt = vertex_int_stmt(crt_v); 00280 fprintf(fp,"\tins_%d:\n", source_stmt); 00281 su_l = vertex_successors(crt_v); 00282 for( ; su_l != NIL; su_l = CDR(su_l)) 00283 { 00284 successor su = SUCCESSOR(CAR(su_l)); 00285 sink_stmt = vertex_int_stmt(successor_vertex(su)); 00286 df_l= dfg_arc_label_dataflows((dfg_arc_label)successor_arc_label(su)); 00287 for ( ; df_l != NIL; df_l = CDR(df_l)) 00288 fprint_dataflow(fp, sink_stmt, DATAFLOW(CAR(df_l))); 00289 } 00290 } 00291 } 00292 }
sccs Components [static] |
int Count [static] |
A set of variables shared by the functions of this package.
The stack contains the current SCC, i.e. the SCC currently being built. Components is the result, i.e. a set of scc.
Definition at line 125 of file sccdfg.c.
Referenced by dfg_find_sccs(), and dfg_low_link_compute().
int StackPointer [static] |
Definition at line 125 of file sccdfg.c.
Referenced by dfg_find_sccs(), dfg_is_in_stack(), and dfg_low_link_compute().
| char vcid_scheduling_sccdfg[] = "$Id: sccdfg.c 16236 2010-03-04 14:39:43Z guelton $" |
1.6.2-20100208