sccdfg.c File Reference

#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 "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"

Include dependency graph for sccdfg.c:

Go to the source code of this file.

Macros
#define	MY_MIN(a, b)   ((a)>(b)?(b):(a))
	=================================================================== More...
#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 More...
typedef dfg_vertex_label	vertex_label

Functions
int	dfg_is_in_stack (vertex v)
	================================================================= More...
void	dfg_low_link_compute (graph g, vertex v)
	================================================================= More...
sccs	dfg_find_sccs (graph g)
	================================================================= More...
void	fprint_sccs (FILE *fp, sccs obj)
	=========================================================================== More...
vertex	dfg_in_vertex_list (list l, vertex v)
	================================================================= More...
graph	dfg_reverse_graph (graph g)
	====================================================================== More...

Variables
char	vcid_scheduling_sccdfg [] = "$Id: sccdfg.c 23065 2016-03-02 09:05:50Z coelho $"
static int	Count
	A set of variables shared by the functions of this package. More...
static int	StackPointer
static vertex *	Stack
static sccs	Components

Macro Definition Documentation

DFG_MARK_NEW

#define DFG_MARK_NEW

(

v

)

Value:

  (sccflags_mark(dfg_vertex_label_sccflags((dfg_vertex_label) \
                                          vertex_vertex_label(v))) = NEW_MARK)

Definition at line 108 of file sccdfg.c.

DFG_MARK_OLD

#define DFG_MARK_OLD

(

v

)

Value:

  (sccflags_mark(dfg_vertex_label_sccflags((dfg_vertex_label) \
                                          vertex_vertex_label(v))) = OLD_MARK)

Definition at line 105 of file sccdfg.c.

DFG_MARKED_NEW_P

#define DFG_MARKED_NEW_P

(

v

)

Value:

  (sccflags_mark(dfg_vertex_label_sccflags((dfg_vertex_label) \
                                          vertex_vertex_label(v))) == NEW_MARK)

Definition at line 111 of file sccdfg.c.

DFG_VERTEX_ENCLOSING_SCC

#define DFG_VERTEX_ENCLOSING_SCC

(

v

)

Value:

   (sccflags_enclosing_scc(dfg_vertex_label_sccflags((dfg_vertex_label)\
                                          vertex_vertex_label(v))))

Definition at line 115 of file sccdfg.c.

MY_MIN

#define MY_MIN	(		a,
			b
	)		((a)>(b)?(b):(a))

===================================================================

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' and to check if a node has already been visited.

Definition at line 101 of file sccdfg.c.

NEW_MARK

#define NEW_MARK   1

Definition at line 103 of file sccdfg.c.

OLD_MARK

#define OLD_MARK   2

Definition at line 104 of file sccdfg.c.

Typedef Documentation

arc_label

typedef dfg_arc_label arc_label

lint

instantiation of the dependence graph

Definition at line 82 of file sccdfg.c.

vertex_label

typedef dfg_vertex_label vertex_label

Definition at line 83 of file sccdfg.c.

Function Documentation

dfg_find_sccs()

sccs dfg_find_sccs

(

graph

g

)

=================================================================

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 223 of file sccdfg.c.

{
 cons   *vertices = graph_vertices(g), *pv;
 
 Count = 1;
 StackPointer = 0;
 Stack = (vertex *)malloc(sizeof(vertex) * gen_length(vertices));
 Components = make_sccs(NIL);
 
 for (pv = vertices; pv != NIL; pv = CDR(pv)) 
    {
     vertex v = VERTEX(CAR(pv));
     dfg_vertex_label lv = (dfg_vertex_label) vertex_vertex_label(v);
     dfg_vertex_label_sccflags(lv) = make_sccflags(scc_undefined,1,0,0);
    }
 
 MAPL(pv, {
           vertex v = VERTEX(CAR(pv));
           if (DFG_MARKED_NEW_P(v))  dfg_low_link_compute(g, v);
          }, vertices);
 
 free(Stack);
 
 return(Components);
}

References CAR, CDR, Components, 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, Stack, StackPointer, VERTEX, and vertex_vertex_label.

Referenced by scheduling().

Here is the call graph for this function:

Here is the caller graph for this function:

dfg_in_vertex_list()

vertex dfg_in_vertex_list	(	list	l,
		vertex	v
	)

=================================================================

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 308 of file sccdfg.c.

{
 vertex     ver;
 int        p, i;
 
 i = dfg_vertex_label_statement((dfg_vertex_label)\
                                        vertex_vertex_label(v));
 for ( ; !ENDP(l); POP(l)) 
    {
     ver = VERTEX(CAR(l));
     p = dfg_vertex_label_statement((dfg_vertex_label)\
                                          vertex_vertex_label(ver));
     if (p == i) return(ver);
    }
 
 return (vertex_undefined);
}

References CAR, dfg_vertex_label_statement, ENDP, POP, VERTEX, vertex_undefined, and vertex_vertex_label.

Referenced by dfg_reverse_graph().

Here is the caller graph for this function:

dfg_is_in_stack()

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 135 of file sccdfg.c.

{
 int     i;
 
 for (i = 0; i < StackPointer; i++)
     if (Stack[i] == v)  return(true);
 
 return(false);
}

References Stack, and StackPointer.

Referenced by dfg_low_link_compute().

Here is the caller graph for this function:

dfg_low_link_compute()

void dfg_low_link_compute	(	graph	g,
		vertex	v
	)

=================================================================

dfg_low_link_compute() is the main function. Its behavior is explained in the book mentionned ealier.

AC 93/10/18

Definition at line 154 of file sccdfg.c.

{
 dfg_vertex_label dvl = (dfg_vertex_label)vertex_vertex_label(v);
 sccflags fv = dfg_vertex_label_sccflags(dvl);
 
 DFG_MARK_OLD(v);
 
 sccflags_lowlink(fv) = Count;
 sccflags_dfnumber(fv) = Count;
 
 Count ++;
 
 Stack[StackPointer++] = v;
 
 MAPL(ps, {
      vertex s = successor_vertex(SUCCESSOR(CAR(ps)));
      if (s != (vertex)NIL)
         {
          sccflags fs = dfg_vertex_label_sccflags((dfg_vertex_label)\
                                                vertex_vertex_label(s));
          if (DFG_MARKED_NEW_P(s))
             {
              dfg_low_link_compute(g, s);
              sccflags_lowlink(fv) = MY_MIN(sccflags_lowlink(fv),\
                                         sccflags_lowlink(fs));
             } 
          else
             {
              if ((sccflags_dfnumber(fs) < sccflags_dfnumber(fv)) &&\
                        dfg_is_in_stack(s)) 
                 sccflags_lowlink(fv) = MY_MIN(sccflags_dfnumber(fs),\
                                            sccflags_lowlink(fv));
             }
         }
    }, vertex_successors(v));
 
 if (sccflags_lowlink(fv) == sccflags_dfnumber(fv)) 
    {
     scc      ns = make_scc(NIL, 0);
     vertex   p;
     sccflags fp;
     cons     *pv = NIL;
 
     do
        {
         p = Stack[--StackPointer];
         fp = dfg_vertex_label_sccflags((dfg_vertex_label)\
                                          vertex_vertex_label(p));
         sccflags_enclosing_scc(fp) = ns;
         pv = gen_nconc(pv, CONS(VERTEX, p, NIL));
        } while (v != p);
 
     scc_vertices(ns) = pv;
     sccs_sccs(Components) = gen_nconc(sccs_sccs(Components),\
                                               CONS(SCC, ns, NIL));
    }
}

References CAR, Components, 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, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccs_sccs, Stack, StackPointer, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.

Referenced by dfg_find_sccs().

Here is the call graph for this function:

Here is the caller graph for this function:

dfg_reverse_graph()

graph dfg_reverse_graph

(

graph

g

)

======================================================================

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 339 of file sccdfg.c.

{
 graph       rev_graph = graph_undefined;
 list        vlist = NIL, li = NIL;
 successor   succ, succ2;
 vertex      v1, v2, v3, v4, v5;
 
 MAPL(ver_ptr,{
      v1 = VERTEX(CAR(ver_ptr));
      v5 = dfg_in_vertex_list(vlist, v1);
      if (v5 == vertex_undefined) 
         {
          v2 = make_vertex(copy_dfg_vertex_label((dfg_vertex_label)\
                             vertex_vertex_label(v1)), NIL);
          ADD_ELEMENT_TO_LIST(vlist, VERTEX, v2);
         }
      else v2 = v5;
 
      MAPL(succ_ptr, {
           li = NIL;
           succ = SUCCESSOR(CAR(succ_ptr));
           v3  = successor_vertex(succ);
           v5  = dfg_in_vertex_list(vlist, v3);
           succ2 = make_successor((dfg_arc_label)\
                                     successor_arc_label(succ), v2);
           if (v5 == vertex_undefined) 
              {
               ADD_ELEMENT_TO_LIST(li, SUCCESSOR, succ2);
               v4 = make_vertex(copy_dfg_vertex_label((dfg_vertex_label)\
                                  vertex_vertex_label(v3)), li);
               ADD_ELEMENT_TO_LIST(vlist, VERTEX, v4);
              }
           else
               ADD_ELEMENT_TO_LIST(vertex_successors(v5),\
                                                SUCCESSOR, succ2);
          }, vertex_successors(v1));
     }, graph_vertices(g));
 rev_graph = make_graph(vlist);
 
 return(rev_graph);
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

fprint_sccs()

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 258 of file sccdfg.c.

{
 list  nodes_l, su_l, df_l, scc_l;
 int   source_stmt, sink_stmt;
 int   iter = 0;
 
 fprintf(fp,"\n Graphe des Composantes Connexes :\n");
 fprintf(fp,"==================================\n");
 
 for(scc_l = sccs_sccs(obj); scc_l != NIL; scc_l = CDR(scc_l))
   {
    scc scc_an = SCC(CAR(scc_l));
    iter++;
    fprintf(fp,"\ncomposante %d :\n",iter);
    for(nodes_l=scc_vertices(scc_an);nodes_l !=NIL;nodes_l=CDR(nodes_l))
      {
       vertex crt_v = VERTEX(CAR(nodes_l));
       source_stmt = vertex_int_stmt(crt_v);
       fprintf(fp,"\tins_%d:\n", source_stmt);
       su_l = vertex_successors(crt_v);
       for( ; su_l != NIL; su_l = CDR(su_l))
         {
          successor su = SUCCESSOR(CAR(su_l));
          sink_stmt = vertex_int_stmt(successor_vertex(su));
          df_l= dfg_arc_label_dataflows((dfg_arc_label)successor_arc_label(su));
          for ( ; df_l != NIL; df_l = CDR(df_l))
             fprint_dataflow(fp, sink_stmt, DATAFLOW(CAR(df_l)));
         }
      }
   }
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

Components

sccs Components

static

Definition at line 126 of file sccdfg.c.

Referenced by dfg_find_sccs(), dfg_low_link_compute(), FindAndTopSortSccs(), FindSccs(), LowlinkCompute(), and TopSortSccs().

Count

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 124 of file sccdfg.c.

Referenced by dfg_find_sccs(), and dfg_low_link_compute().

Stack

vertex* Stack

static

Definition at line 125 of file sccdfg.c.

Referenced by dfg_find_sccs(), dfg_is_in_stack(), and dfg_low_link_compute().

StackPointer

int StackPointer

static

Definition at line 124 of file sccdfg.c.

Referenced by dfg_find_sccs(), dfg_is_in_stack(), and dfg_low_link_compute().

vcid_scheduling_sccdfg

char vcid_scheduling_sccdfg[] = "$Id: sccdfg.c 23065 2016-03-02 09:05:50Z coelho $"

Definition at line 29 of file sccdfg.c.