#include "local.h"

Include dependency graph for scc.c:

Macros
#define	NEW_MARK 1
	a set of macros to mark a vertex as 'not visited' or 'visited' and to check if a node has already been visited More...

#define	OLD_MARK 2

#define	MARK_OLD(v)

#define	MARK_NEW(v)

#define	MARKED_NEW_P(v)

Functions
void	set_sccs_drivers (bool ignore_this_vertex_fun, bool ignore_this_successor_fun)

void	reset_sccs_drivers ()

void	LowlinkCompute (graph g, set region, vertex v, int level, sccs Components)

int	IsInStack (vertex v)
	this function checks if vertex v is in the stack More...

sccs	FindSccs (graph g, set region, int level)
	FindSccs is the interface function to compute the SCCs of a graph. More...

void	ComputeInDegree (graph g, set region, int l)

list	TopSortSccs (graph __attribute__((unused)) g, set region, int l, sccs Components)

list	FindAndTopSortSccs (graph g, set region, int l)

void	PrintScc (scc s)

void	PrintSccs (sccs ss)

Variables
static int	Count
	a set of variables shared by the functions of this package. More...

static int	StackPointer

static vertex *	Stack

static bool(*	ignore_this_vertex_drv )(set, vertex)=0

static bool(*	ignore_this_successor_drv )(vertex, set, successor, int)=0

Macro Definition Documentation

◆ MARK_NEW

#define MARK_NEW ( v )

Value:

(sccflags_mark(dg_vertex_label_sccflags((dg_vertex_label) \

vertex_vertex_label(v))) = NEW_MARK)

sccflags_mark

#define sccflags_mark(x)

Definition: dg.h:275

dg_vertex_label_sccflags

#define dg_vertex_label_sccflags(x)

Definition: dg.h:237

vertex_vertex_label

#define vertex_vertex_label(x)

Definition: graph.h:152

NEW_MARK

#define NEW_MARK

a set of macros to mark a vertex as 'not visited' or 'visited' and to check if a node has already bee...

Definition: scc.c:57

_newgen_struct_dg_vertex_label_

Definition: dg.h:227

Definition at line 62 of file scc.c.

◆ MARK_OLD

#define MARK_OLD ( v )

Value:

(sccflags_mark(dg_vertex_label_sccflags((dg_vertex_label) \

vertex_vertex_label(v))) = OLD_MARK)

OLD_MARK

#define OLD_MARK

Definition: scc.c:58

Definition at line 59 of file scc.c.

◆ MARKED_NEW_P

#define MARKED_NEW_P ( v )

Value:

(sccflags_mark(dg_vertex_label_sccflags((dg_vertex_label) \

vertex_vertex_label(v))) == NEW_MARK)

Definition at line 65 of file scc.c.

◆ NEW_MARK

#define NEW_MARK 1

a set of macros to mark a vertex as 'not visited' or 'visited' and to check if a node has already been visited

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

Definition at line 57 of file scc.c.

◆ OLD_MARK

#define OLD_MARK 2

Definition at line 58 of file scc.c.

Function Documentation

◆ ComputeInDegree()

void ComputeInDegree	(	graph	g,
		set	region,
		int	l
	)

Parameters

region egion

Definition at line 244 of file scc.c.

                                                  {
   FOREACH(VERTEX, v, graph_vertices(g))
   {
     if(!ignore_this_vertex_drv(region, v)) {
       scc sv = VERTEX_ENCLOSING_SCC(v);
       FOREACH(SUCCESSOR, su, vertex_successors(v))
       {
         if(!ignore_this_successor_drv(v, region, su, l)) {
           vertex s = successor_vertex(su);
           scc ss = VERTEX_ENCLOSING_SCC(s);
           if(sv != ss)
             scc_indegree(ss) += 1;
         }
       }
     }
   }
 }

References FOREACH, graph_vertices, ignore_this_successor_drv, ignore_this_vertex_drv, region, scc_indegree, SUCCESSOR, successor_vertex, VERTEX, VERTEX_ENCLOSING_SCC, and vertex_successors.

Referenced by FindAndTopSortSccs().

Here is the caller graph for this function:

◆ FindAndTopSortSccs()

list FindAndTopSortSccs	(	graph	g,
		set	region,
		int	l
	)

Parameters

region egion

Definition at line 317 of file scc.c.

                                                     {
   list lsccs;
   sccs Components;
  
   ifdebug(8) {
     pips_debug(8, "Dependence graph:\n");
     prettyprint_dependence_graph(stderr, statement_undefined, g);
   }
  
   pips_debug(3, "computing sccs ...\n");
  
   Components = FindSccs(g, region, l);
  
   pips_debug(3, "computing in degrees ...\n");
  
   ComputeInDegree(g, region, l);
  
   pips_debug(3, "topological sort ...\n");
  
   lsccs = TopSortSccs(g, region, l,Components);
  
 //  free_sccs(Components);
   gen_free_list(sccs_sccs(Components));
   free(Components);
  
  
   return (lsccs);
 }

References Components, ComputeInDegree(), FindSccs(), free(), gen_free_list(), ifdebug, pips_debug, prettyprint_dependence_graph(), region, sccs_sccs, statement_undefined, and TopSortSccs().

Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FindSccs()

sccs FindSccs	(	graph	g,
		set	region,
		int	level
	)

FindSccs is the interface function to compute the SCCs of a graph.

It marks all nodes as 'not visited' and then apply the main function LowlinkCompute on all vertices.

A vertex is processed only if it belongs to region. Later, successors will be processed if they can be reached through arcs whose level is greater or equal to level.

g is a graph

region and level define a sub-graph of g

Bug FOREACH

Parameters

region	egion
level	evel

Definition at line 206 of file scc.c.

                                               {
   list vertices = graph_vertices(g);
   sccs Components;
  
   Count = 1;
   StackPointer = 0;
   Stack = (vertex *)malloc(sizeof(vertex) * gen_length(vertices));
   Components = make_sccs(NIL);
   FOREACH(VERTEX, v, vertices) {
     if(!ignore_this_vertex_drv(region, v)) {
       dg_vertex_label lv = (dg_vertex_label)vertex_vertex_label(v);
       sccflags fv = dg_vertex_label_sccflags(lv);
       if(fv == sccflags_undefined) {
         pips_debug (7, "fv has not been set so far");
         fv = make_sccflags(scc_undefined, 0, 0, 0);
         dg_vertex_label_sccflags(lv) = fv;
       }
       sccflags_mark(fv) = NEW_MARK;
     }
   }
   /* Bug FOREACH */FOREACH(VERTEX, v1, vertices) {
     if(!ignore_this_vertex_drv(region, v1))
       if(MARKED_NEW_P(v1)) {
         LowlinkCompute(g, region, v1, level, Components);
       }
   }
  
   free(Stack);
  
   ifdebug(3) {
     pips_debug(3, "Strongly connected components:\n");
     PrintSccs(Components);
     pips_debug(3, "End\n");
   }
  
   return (Components);
 }

References Components, Count, dg_vertex_label_sccflags, FOREACH, free(), gen_length(), graph_vertices, ifdebug, ignore_this_vertex_drv, level, LowlinkCompute(), make_sccflags(), make_sccs(), malloc(), MARKED_NEW_P, NEW_MARK, NIL, pips_debug, PrintSccs(), region, scc_undefined, sccflags_mark, sccflags_undefined, Stack, StackPointer, VERTEX, and vertex_vertex_label.

Referenced by FindAndTopSortSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IsInStack()

int IsInStack ( vertex v )

this function checks if vertex v is in the stack

Definition at line 183 of file scc.c.

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

References Stack, and StackPointer.

Referenced by LowlinkCompute().

Here is the caller graph for this function:

◆ LowlinkCompute()

void LowlinkCompute	(	graph	g,
		set	region,
		vertex	v,
		int	level,
		sccs	Components
	)

Parameters

region	egion
level	evel
Components	omponents

Definition at line 115 of file scc.c.

                                                                                {
   dg_vertex_label dvl = (dg_vertex_label)vertex_vertex_label(v);
   sccflags fv = dg_vertex_label_sccflags(dvl);
   statement sv = ordering_to_statement(dg_vertex_label_statement(dvl));
  
   pips_debug(7, "vertex is %zd (%zd %zd %zd)\n", statement_number(sv),
       sccflags_mark(fv), sccflags_lowlink(fv), sccflags_dfnumber(fv));
  
   MARK_OLD(v);
  
   sccflags_lowlink(fv) = Count;
   sccflags_dfnumber(fv) = Count;
  
   Count++;
  
   Stack[StackPointer++] = v;
   FOREACH(SUCCESSOR, su, vertex_successors(v)) {
  
     if(!ignore_this_successor_drv(v, region, su, level)) {
       vertex s = successor_vertex(su);
  
       if(!ignore_this_vertex_drv(region, s)) {
         dg_vertex_label dsl = (dg_vertex_label)vertex_vertex_label(s);
         sccflags fs = dg_vertex_label_sccflags(dsl);
         statement ss = ordering_to_statement(dg_vertex_label_statement(dsl));
  
         pips_debug(7, "successor before is %zd (%zd %zd %zd)\n",
             statement_number(ss), sccflags_mark(fs),
             sccflags_lowlink(fs), sccflags_dfnumber(fs));
  
         if(MARKED_NEW_P(s)) {
           LowlinkCompute(g, region, s, level, Components);
           pips_debug(7, "successor after is %zd (%zd %zd %zd)\n",
               statement_number(ss), sccflags_mark(fs),
               sccflags_lowlink(fs), sccflags_dfnumber(fs));
           sccflags_lowlink(fv) = MIN(sccflags_lowlink(fv),
               sccflags_lowlink(fs));
         } else {
           if((sccflags_dfnumber(fs) < sccflags_dfnumber(fv)) && IsInStack(s)) {
             sccflags_lowlink(fv) = MIN(sccflags_dfnumber(fs),
                 sccflags_lowlink(fv));
           }
         }
       }
     }
   }
  
   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 = dg_vertex_label_sccflags((dg_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 Components, CONS, Count, dg_vertex_label_sccflags, dg_vertex_label_statement, FOREACH, gen_nconc(), ignore_this_successor_drv, ignore_this_vertex_drv, IsInStack(), level, LowlinkCompute(), make_scc(), MARK_OLD, MARKED_NEW_P, MIN, NIL, ordering_to_statement(), pips_debug, region, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccflags_mark, sccs_sccs, Stack, StackPointer, statement_number, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.

Referenced by FindSccs(), and LowlinkCompute().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PrintScc()

void PrintScc ( scc s )

Definition at line 346 of file scc.c.

                      {
   fprintf(stderr, "Scc's statements : ");
   FOREACH(VERTEX, v, scc_vertices(s)) {
     statement st = vertex_to_statement(v);
  
     fprintf(stderr, "%02td ", statement_number(st));
   }
   fprintf(stderr, " -  in degree : %td\n", scc_indegree(s));
 }

References FOREACH, fprintf(), scc_indegree, scc_vertices, statement_number, VERTEX, and vertex_to_statement().

Referenced by ConnectedStatements(), and PrintSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PrintSccs()

void PrintSccs ( sccs ss )

Parameters

ss s

Definition at line 356 of file scc.c.

                         {
   fprintf(stderr, "Strongly connected components:\n");
   if(!ENDP(sccs_sccs(ss))) {
     MAPL(ps, {PrintScc(SCC(CAR(ps)));}, sccs_sccs(ss));
   } else {
     fprintf(stderr, "Empty list of scc\n");
   }
 }

References CAR, ENDP, fprintf(), MAPL, PrintScc(), SCC, and sccs_sccs.

Referenced by FindSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reset_sccs_drivers()

void reset_sccs_drivers ( void )

Definition at line 98 of file scc.c.

                           {
   pips_assert( "ignore_this_vertex_drv is not set", ignore_this_vertex_drv != 0 );
   pips_assert( "ignore_this_successor_drv is not set", ignore_this_successor_drv != 0 );
   ignore_this_vertex_drv = 0;
   ignore_this_successor_drv = 0;
 }

References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.

Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().

Here is the caller graph for this function:

◆ set_sccs_drivers()

void set_sccs_drivers	(	bool *	ignore_this_vertex_fun,
		bool *	ignore_this_successor_fun
	)

Definition at line 88 of file scc.c.

 {
   pips_assert( "ignore_this_vertex_drv is set", ignore_this_vertex_drv == 0 );
   pips_assert( "ignore_this_successor_drv is set", ignore_this_successor_drv == 0 );
  
   ignore_this_vertex_drv = ignore_this_vertex_fun;
   ignore_this_successor_drv = ignore_this_successor_fun;
 }

References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.

◆ TopSortSccs()

list TopSortSccs	(	graph __attribute__((unused))	g,
		set	region,
		int	l,
		sccs	Components
	)

Definition at line 262 of file scc.c.

                                                                                       {
   list lsccs = NIL, elsccs = NIL, no_ins = NIL;
   FOREACH(SCC, s, sccs_sccs(Components)) {
     if(scc_indegree(s) == 0)
       no_ins = CONS(SCC, s, no_ins);
   }
  
   while(no_ins != NIL) {
     list pcs;
     scc cs;
  
     pcs = no_ins;
     no_ins = CDR(no_ins);
     INSERT_AT_END(lsccs, elsccs, pcs);
  
     pips_debug(3, "updating in degrees ...\n");
     cs = SCC(CAR(pcs));
     FOREACH(VERTEX, v, scc_vertices(cs))
     {
       scc sv = VERTEX_ENCLOSING_SCC(v);
       FOREACH(SUCCESSOR, su, vertex_successors(v))
       {
         if(!ignore_this_successor_drv(v, region, su, l)) {
           vertex s = successor_vertex(su);
           scc ss = VERTEX_ENCLOSING_SCC(s);
           if(sv != ss && (scc_indegree(ss) -= 1) == 0
               && !ignore_this_vertex_drv(region, s)) {
             no_ins = CONS(SCC, ss, no_ins);
           }
         }
       }
     }
   }
  
   ifdebug(3) {
     fprintf(stderr, "[TopSortSccs] topological order:\n");
     FOREACH(SCC, s, lsccs) {
       fprintf(stderr, "( ");
       FOREACH(VERTEX, v, scc_vertices(s)) {
         statement st = vertex_to_statement(v);
  
         fprintf(stderr, "%td ", statement_number(st));
       }
       fprintf(stderr, ")   -->   ");
     }
     fprintf(stderr, "\n");
   }
  
   return (lsccs);
 }