ricedg.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	INFAISABLE   0
	Warning! Do not modify this file that is automatically generated! More...
#define	FAISABLE   1
#define	MAXDEPTH   9
	maximun number of nested loops More...
#define	MAXSV   1024
	maximum number of scalar variables More...
#define	FLOW_DEPENDANCE   1
	Definition for the dependance_verticies_p function. More...
#define	ANTI_DEPENDANCE   2
#define	OUTPUT_DEPENDANCE   4
#define	INPUT_DEPENDANCE   8

Functions
statement	vertex_to_statement (vertex)
	cproto-generated files More...
int	vertex_ordering (vertex)
int	compare_vertex (const void *, const void *)
	compare two vertices based on their ordering More...
hash_table	compute_ordering_to_dg_mapping (graph)
	Define a mapping from the statement ordering to the dependence graph vertices: More...
int	vertex_sort_callback (const vertex *, const vertex *)
	This is a callback for qsort function, it compares two vertex. More...
int	successor_sort_callback (const successor *, const successor *)
	This is a callback for qsort function, it compares two successor. More...
int	conflicts_sort_callback (conflict *, conflict *)
	This is a callback for qsort function, it compares two conflicts. More...
void	prettyprint_dependence_graph (FILE *, statement, graph)
	Print all edges and arcs. More...
void	prettyprint_dot_dependence_graph (FILE *, statement, graph)
	Output dependence graph in a file in graphviz dot format. More...
void	prettyprint_dependence_graph_view (FILE *, statement, graph)
	Do not print vertices and arcs ignored by the parallelization algorithms. More...
void	print_vect_in_vertice_val (FILE *, Pvecteur, Pbase)
void	print_dependence_cone (FILE *, Ptsg, Pbase)
hash_table	statements_to_successors (list, graph)
	creates a hash_table containing statements from statements as keys and their respective succesors according to dg as values More...
statement_mapping	contexts_mapping_of_nest (statement)
	contexts.c More...
entity	MakeDiVar (int)
	This function creates di variables. More...
entity	GetDiVar (int)
	This functions looks up a di variable of nesting level l in table DiVars. More...
entity	MakeLiVar (int)
	This function creates li variables(thee ith loop index variable). More...
entity	GetLiVar (int)
entity	MakeDsiVar (int)
	This function creates dsi variables. More...
entity	GetDsiVar (int)
int	DiVarLevel (entity)
	this function returns the nesting level of a given di variable e. More...
void	sc_add_di (int, entity, Psysteme, int)
void	sc_add_dsi (int, entity, Psysteme)
int	sc_proj_on_di (int, Psysteme)
Pbase	MakeDibaseinorder (int)
	Pbase MakeDibaseinorder(int n) make a base of D#1 ... More...
int	FindMaximumCommonLevel (cons *, cons *)
void	ResetLoopCounter (void)
entity	MakeLoopCounter (void)
	Create a new loop counter variable. More...
int	dep_type (action, action)
	int dep_type(action ac1,action ac2) This function test the type of the dependence. More...
int	sc_proj_optim_on_di_ofl (int, Psysteme *)
	int sc_proj_optim_on_di_ofl(cl, sc) More...
bool	sc_faisabilite_optim (Psysteme)
	bool sc_faisabilite_optim (Psysteme sc) : More...
Psysteme	sc_projection_optim_along_vecteur_ofl (Psysteme, Pvecteur)
	Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv) More...
bool	sc_minmax_of_variable_optim (Psysteme volatile, Variable, Value *, Value *)
	void sc_minmax_of_variable_optim(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin. More...
Psysteme	sc_invers (Psysteme)
	Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial. More...
void	vect_chg_var_sign (Pvecteur *, Variable)
	void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv More...
bool	context_map_undefined_p (void)
void	set_context_map (statement_mapping)
statement_mapping	get_context_map (void)
void	reset_context_map (void)
void	free_context_map (void)
void	make_context_map (void)
Psysteme	load_statement_context (statement)
void	delete_statement_context (statement)
bool	statement_context_undefined_p (statement)
void	store_statement_context (statement, Psysteme)
void	update_statement_context (statement, Psysteme)
bool	rice_fast_dependence_graph (char *)
bool	rice_full_dependence_graph (char *)
bool	rice_semantics_dependence_graph (char *)
bool	rice_regions_dependence_graph (char *)
list	TestCoupleOfReferences (list, Psysteme, statement, effect, reference, list, Psysteme, statement, effect, reference, list, Ptsg *, list *, Ptsg *)
void	writeresult (char *)
graph	compute_dg_on_statement_from_chains_in_place (statement, graph)
graph	compute_dg_on_statement_from_chains (statement, graph)
bool	print_whole_dependence_graph (const string)
	prettyprint.c More...
bool	print_filtered_dependence_graph (const string)
bool	print_filtered_dependence_daVinci_graph (const string)
bool	print_effective_dependence_graph (const string)
bool	print_loop_carried_dependence_graph (const string)
bool	print_dependence_graph (string)
bool	print_chains_graph (string)
bool	print_dot_chains_graph (string)
	This pipmake pass output the chains in a file usable by the graphviz tool dot. More...
bool	print_dot_dependence_graph (string)
	This pipmake pass output the DG in a file usable by graphviz tool dot. More...
void	quick_privatize_graph (graph)
	quick_privatize.c More...
vertex	get_vertex_in_list (list, string)
	trace.c More...
void	prettyprint_graph_text (FILE *, list)
	print a graph to text format More...
void	prettyprint_graph_daVinci (FILE *, list)
	print a graph to daVinci format, each label of successor is represented by a circular node, each vertex is represented by a square node More...
list	make_filtered_dg_or_dvdg (statement, graph)
bool	print_filtered_dg_or_dvdg (string, bool)
bool	print_loopnest_dependence_cone (const char *)
bool	find_covering_reference_path (set, statement, action, entity, statement, action, entity)
	impact_check.c More...
bool	check_way_between_two_statements (statement, statement, graph)
	Check to see if there is a directed way between 2 statements in the graph specified. More...
list	union_list (list, list)
	Union is not typed... More...
bool	impact_check (char *)

Variables
int	NbrArrayDepInit
	he variables for the statistics of test of dependence and parallelization More...
int	NbrIndepFind
int	NbrAllEquals
int	NbrDepCnst
int	NbrDepExact
int	NbrDepInexactEq
int	NbrDepInexactFM
int	NbrDepInexactEFM
int	NbrScalDep
int	NbrIndexDep
int	deptype [5][3]
int	constdep [5][3]
int	NbrTestCnst
int	NbrTestGcd
int	NbrTestSimple
int	NbrTestDiCnst
	by sc_normalize() More...
int	NbrTestProjEqDi
int	NbrTestProjFMDi
int	NbrTestProjEq
int	NbrTestProjFM
int	NbrTestDiVar
int	NbrProjFMTotal
int	NbrFMSystNonAug
int	FMComp [18]
bool	is_test_exact
	or counting the number of F-M complexity less than 16. More...
bool	is_test_inexact_eq
bool	is_test_inexact_fm
bool	is_dep_cnst
bool	is_test_Di
bool	Finds2s1
int	Nbrdo
	loop.c More...
entity	DiVars [9]
	testdep_util.c More...
entity	LiVars [9]
entity	DsiVars [1024]
int	NbrTestExact

Macro Definition Documentation

ANTI_DEPENDANCE

#define ANTI_DEPENDANCE   2

Definition at line 79 of file ricedg.h.

FAISABLE

#define FAISABLE   1

Definition at line 33 of file ricedg.h.

FLOW_DEPENDANCE

#define FLOW_DEPENDANCE   1

Definition for the dependance_verticies_p function.

Definition at line 78 of file ricedg.h.

INFAISABLE

#define INFAISABLE   0

Warning! Do not modify this file that is automatically generated!

Modify src/Libs/ricedg/ricedg-local.h instead, to add your own modifications. header file built by cproto ricedg-local.h

Definition at line 32 of file ricedg.h.

INPUT_DEPENDANCE

#define INPUT_DEPENDANCE   8

Definition at line 81 of file ricedg.h.

MAXDEPTH

#define MAXDEPTH   9

maximun number of nested loops

Definition at line 36 of file ricedg.h.

MAXSV

#define MAXSV   1024

maximum number of scalar variables

Definition at line 38 of file ricedg.h.

OUTPUT_DEPENDANCE

#define OUTPUT_DEPENDANCE   4

Definition at line 80 of file ricedg.h.

Function Documentation

check_way_between_two_statements()

bool check_way_between_two_statements	(	statement	s1,
		statement	s2,
		graph	g
	)

Check to see if there is a directed way between 2 statements in the graph specified.

Parameters

s1	1
s2	2

Definition at line 290 of file impact_check.c.

{
    vertex v1 = statement_to_vertex(s1, g);
    list vertex_processed_list = NIL;
    list vertex_rest_list = NIL;
    ADD_ELEMENT_TO_LIST(vertex_rest_list, VERTEX, v1);
 
    while(!ENDP(vertex_rest_list)) {
        vertex v = VERTEX(CAR(vertex_rest_list));
        POP(vertex_rest_list);
        if (!gen_in_list_p(v, vertex_processed_list)) {
            statement sv = vertex_to_statement(v);
            if (statement_equal_p(sv, s2))
                return true;
            else {
                ADD_ELEMENT_TO_LIST(vertex_processed_list, VERTEX, v);
                MAP(SUCCESSOR, su, {
                    vertex v2 = successor_vertex(su);
                    if (!gen_in_list_p(v2, vertex_processed_list) && !gen_in_list_p(v2, vertex_rest_list))
                        ADD_ELEMENT_TO_LIST(vertex_rest_list, VERTEX, v2);
                }, vertex_successors(v));
            }
        }
    }
    return false;
}

References ADD_ELEMENT_TO_LIST, CAR, ENDP, gen_in_list_p(), MAP, NIL, POP, s1, statement_equal_p(), statement_to_vertex(), SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Here is the call graph for this function:

compare_vertex()

int compare_vertex	(	const void *	v0,
		const void *	v1
	)

compare two vertices based on their ordering

Parameters

v0	0
v1	1

Definition at line 58 of file util.c.

{
    const vertex V0 = *(const vertex *)v0,
                 V1 = *(const vertex *)v1;
    if (V0==V1) return 0;
    return vertex_ordering(V0) > vertex_ordering(V1);
}

References vertex_ordering().

Referenced by do_scalar_renaming_in_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_dg_on_statement_from_chains()

graph compute_dg_on_statement_from_chains	(	statement	s,
		graph	chains
	)

Parameters

chains

hains

Definition at line 2363 of file ricedg.c.

                                                                     {
  dg = copy_graph(chains);
  return compute_dg_on_statement_from_chains_in_place(s, dg);
}

References chains(), compute_dg_on_statement_from_chains_in_place(), copy_graph(), and dg.

Here is the call graph for this function:

compute_dg_on_statement_from_chains_in_place()

graph compute_dg_on_statement_from_chains_in_place	(	statement	s,
		graph	chains
	)

Parameters

chains

hains

Definition at line 2342 of file ricedg.c.

                                                                              {
  dg = chains;
  dg_type = DG_FAST; //FIXME
 
  debug_on("QUICK_PRIVATIZER_DEBUG_LEVEL");
  quick_privatize_graph(dg);
  debug_off();
 
  memset(deptype,0,sizeof(deptype));
  memset(constdep,0,sizeof(deptype));
 
  rdg_statement(s);
 
  return dg;
}

References chains(), constdep, debug_off, debug_on, deptype, dg, DG_FAST, dg_type, memset(), quick_privatize_graph(), and rdg_statement().

Referenced by compute_dg_on_statement_from_chains().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_ordering_to_dg_mapping()

hash_table compute_ordering_to_dg_mapping

(

graph

dependance_graph

)

Define a mapping from the statement ordering to the dependence graph vertices:

Parameters

dependance_graph

ependance_graph

Definition at line 70 of file util.c.

{
  hash_table ordering_to_dg_mapping = hash_table_make(hash_int, 0);
 
  FOREACH(VERTEX, a_vertex, graph_vertices(dependance_graph))
  {
    pips_debug(7, "\tSuccessor list: %p for statement ordering %lld\n",
               vertex_successors(a_vertex),
               (long long int) dg_vertex_label_statement(vertex_vertex_label(a_vertex)));
 
    hash_put(ordering_to_dg_mapping,
             (char *) dg_vertex_label_statement(vertex_vertex_label(a_vertex)),
             (char *) a_vertex);
  }
 
  return ordering_to_dg_mapping;
}

References dg_vertex_label_statement, FOREACH, graph_vertices, hash_int, hash_put(), hash_table_make(), pips_debug, VERTEX, vertex_successors, and vertex_vertex_label.

Here is the call graph for this function:

conflicts_sort_callback()

int conflicts_sort_callback	(	conflict *	c1,
		conflict *	c2
	)

This is a callback for qsort function, it compares two conflicts.

Returns

0 if conflicts are equals, -1 if first is lower, 1 if second is lower

Parameters

c1	1
c2	2

Definition at line 126 of file util.c.

                                                          {
  int r_value = 0;
  effect e1_sink = conflict_sink((*c1));
  effect e2_sink = conflict_sink((*c2));
  action a1_sink = effect_action(e1_sink);
  action a2_sink = effect_action(e2_sink);
  effect e1_source = conflict_source((*c1));
  effect e2_source = conflict_source((*c2));
  action a1_source = effect_action(e1_source);
  action a2_source = effect_action(e2_source);
 
 
 
  string s1 = strdup(concatenate(full_action_to_short_string(a1_source),
                                 full_action_to_short_string(a1_sink),
                                 NULL));
  string s2 = strdup(concatenate(full_action_to_short_string(a2_source),
                                 full_action_to_short_string(a2_sink),
                                 NULL));
 
  // Compare Action in lexical order
  r_value = strcmp( s1, s2 );
  free( s1 );
  free( s2 );
 
  if ( r_value == 0 ) {
    // Compare string representing source reference
    reference r1_source = effect_any_reference(e1_source);
    string s1 = words_to_string( effect_words_reference( r1_source ) );
    reference r2_source = effect_any_reference(e2_source);
    string s2 = words_to_string( effect_words_reference( r2_source ) );
    r_value = strcmp( s1, s2 );
    free( s1 );
    free( s2 );
  }
  if ( r_value == 0 ) {
    // Compare string representing sink reference
    reference r1_sink = effect_any_reference(e1_sink);
    string s1 = words_to_string( effect_words_reference( r1_sink ) );
    reference r2_sink = effect_any_reference(e2_sink);
    string s2 = words_to_string( effect_words_reference( r2_sink ) );
    r_value = strcmp( s1, s2 );
    free( s1 );
    free( s2 );
  }
 
  return r_value;
}

References concatenate(), conflict_sink, conflict_source, effect_action, effect_any_reference, effect_words_reference(), free(), full_action_to_short_string(), s1, strdup(), and words_to_string().

Referenced by prettyprint_dependence_graph(), prettyprint_dependence_graph_view(), and xml_Chain_Graph().

Here is the call graph for this function:

Here is the caller graph for this function:

context_map_undefined_p()

bool context_map_undefined_p

(

void

)

contexts_mapping_of_nest()

statement_mapping contexts_mapping_of_nest

(

statement

stat

)

contexts.c

Parameters

stat

tat

Definition at line 162 of file contexts.c.

{
    statement_mapping contexts_map;
 
    pips_assert("contexts_mapping_of_nest", statement_loop_p(stat));
 
    contexts_map = MAKE_STATEMENT_MAPPING();
 
    contexts_mapping_of_statement(contexts_map, NULL, stat);
 
    ifdebug(8) {
        STATEMENT_MAPPING_MAP(st, context, {
            statement stp = (statement) st;
 
            if (statement_call_p(stp)) {
                fprintf(stderr, "Execution context of statement %td :\n", 
                        statement_number(stp));
                sc_fprint(stderr, (Psysteme) context, (get_variable_name_t) entity_local_name);
            }
        }, contexts_map);
    }
 
    return(contexts_map);
}

References contexts_mapping_of_statement(), entity_local_name(), fprintf(), ifdebug, MAKE_STATEMENT_MAPPING, pips_assert, sc_fprint(), statement_call_p(), statement_loop_p(), STATEMENT_MAPPING_MAP, and statement_number.

Referenced by rice_update_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

delete_statement_context()

void delete_statement_context

(

statement

)

dep_type()

int dep_type	(	action	ac1,
		action	ac2
	)

int dep_type(action ac1,action ac2) This function test the type of the dependence.

ac1, ac2 are the action of two references.The representations of the result are as follows. 0 -— def-use dependence 1 -— use-def dependence 2 -— def-def dependence 3 -— use-use dependence (added in 20/01/92) FI->YY: we also have use-use dependence (also called input dependence); there is no reason to abort here; input dependences should just be ignored for parallelization, but not for tiling or cache optimization

to please gcc

Parameters

ac1	c1
ac2	c2

Definition at line 378 of file testdep_util.c.

                   {
  if(action_write_p(ac1) && action_read_p(ac2))
    return (0);
  else if(action_read_p(ac1) && action_write_p(ac2))
    return (1);
  else if(action_write_p(ac1) && action_write_p(ac2))
    return (2);
  else if(action_read_p(ac1) && action_read_p(ac2))
    return (3);
  else
    pips_internal_error("A undefined chain ---chains fault");
 
  /* to please gcc */
  return -1;
}

References action_read_p, action_write_p, and pips_internal_error.

Referenced by insert_impact_description_as_comment(), and TestCoupleOfReferences().

Here is the caller graph for this function:

DiVarLevel()

int DiVarLevel

(

entity

e

)

this function returns the nesting level of a given di variable e.

Definition at line 185 of file testdep_util.c.

            {
  int i;
 
  for (i = 0; i < MAXDEPTH; i++)
    if(e == DiVars[i])
      return (i + 1);
 
  return (0);
}

References DiVars, and MAXDEPTH.

Referenced by sc_proj_on_di(), sc_proj_optim_on_di_ofl(), and TestDependence().

Here is the caller graph for this function:

find_covering_reference_path()

bool find_covering_reference_path	(	set	arcs_processed_set,
		statement	s_src,
		action	act_src,
		entity	ent_src,
		statement	s_dest,
		action	act_dest,
		entity	ent_dest
	)

impact_check.c

impact_check.c

Parameters

arcs_processed_set	rcs_processed_set
s_src	_src
act_src	ct_src
ent_src	nt_src
s_dest	_dest
act_dest	ct_dest
ent_dest	nt_dest

Definition at line 238 of file impact_check.c.

{
  if (statement_equal_p(s_src, s_dest))
    {
      if (entities_may_conflict_p(ent_src, ent_dest))
        return (action_write_p(act_dest) || action_read_p(act_src));
      else
        return (action_write_p(act_dest) && action_read_p(act_src));
    }
  else
    {
      vertex ver_src = statement_to_vertex(s_src, dg);
      MAP(SUCCESSOR, su, {
        statement s_tmp = vertex_to_statement(successor_vertex(su));
        dg_arc_label dal = (dg_arc_label) successor_arc_label(su);
        MAP(CONFLICT, c, {
          effect e_tmp_src = conflict_source(c);
          effect e_tmp_dest = conflict_sink(c);
          entity ent_tmp_src = reference_variable(effect_any_reference(e_tmp_src));
          entity ent_tmp_dest = reference_variable(effect_any_reference(e_tmp_dest));
          action act_tmp_src = effect_action(e_tmp_src);
          action act_tmp_dest = effect_action(e_tmp_dest);
          set arcs_processed_tmp_set = set_make(set_pointer);
          if (set_belong_p(arcs_processed_set, (char *)c)) continue;
          arcs_processed_tmp_set = set_add_element(arcs_processed_tmp_set, arcs_processed_set, (char *)c);
          if (entities_may_conflict_p(ent_src, ent_tmp_src))
            {
              if (action_write_p(act_tmp_src) || action_read_p(act_src))
                if (find_covering_reference_path(arcs_processed_tmp_set,
                                                s_tmp, act_tmp_dest, ent_tmp_dest,
                                                s_dest, act_dest, ent_dest)) return true;
            }
          else
            {
              if (action_write_p(act_tmp_src) && action_read_p(act_src))
                if (find_covering_reference_path(arcs_processed_tmp_set,
                                                s_tmp, act_tmp_dest, ent_tmp_dest,
                                                s_dest, act_dest, ent_dest)) return true;
            }
        }, dg_arc_label_conflicts(dal));
      }, vertex_successors(ver_src));
    }
  return false;
}

References action_read_p, action_write_p, CONFLICT, conflict_sink, conflict_source, dg, dg_arc_label_conflicts, effect_action, effect_any_reference, entities_may_conflict_p(), MAP, reference_variable, set_add_element(), set_belong_p(), set_make(), set_pointer, statement_equal_p(), statement_to_vertex(), SUCCESSOR, successor_arc_label, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by check_for_effected_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

FindMaximumCommonLevel()

int FindMaximumCommonLevel	(	cons *	n1,
		cons *	n2
	)

Parameters

n1	1
n2	2

Definition at line 307 of file testdep_util.c.

                 {
  int cl = 0;
 
  while(n1 != NIL && n2 != NIL) {
    if(LOOP(CAR(n1)) != LOOP(CAR(n2)))
      break;
    n1 = CDR(n1);
    n2 = CDR(n2);
    cl += 1;
  }
 
  return (cl);
}

References CAR, CDR, LOOP, and NIL.

Referenced by prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), search_parallel_loops(), TestCoupleOfReferences(), and TestDependence().

Here is the caller graph for this function:

free_context_map()

void free_context_map

(

void

)

get_context_map()

statement_mapping get_context_map

(

void

)

get_vertex_in_list()

vertex get_vertex_in_list	(	list	in_l,
		string	in_s
	)

trace.c

trace.c

Parameters

in_l	n_l
in_s	n_s

Definition at line 35 of file trace.c.

{
    MAP(VERTEX, ver, {
        string s = (string)vertex_vertex_label(ver);
        if (same_string_p(in_s, s)) return ver;
    }, in_l);
    return vertex_undefined;
}

References MAP, same_string_p, VERTEX, vertex_undefined, and vertex_vertex_label.

Referenced by make_filtered_dg_or_dvdg().

Here is the caller graph for this function:

GetDiVar()

entity GetDiVar

(

int

l

)

This functions looks up a di variable of nesting level l in table DiVars.

di variables are created if they do not exist.

Definition at line 79 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXDEPTH)
    user_error("parallelize", "too many nested loops\n");
 
  if((e = DiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXDEPTH; i++)
      DiVars[i] = MakeDiVar(i + 1);
 
    e = DiVars[l - 1];
  }
 
  return (e);
}

References DiVars, MakeDiVar(), MAXDEPTH, and user_error.

Referenced by dependence_system_add_lci_and_di(), gcd_and_constant_dependence_test(), MakeDibaseinorder(), sc_add_di(), TestDiCnst(), and TestDiVariables().

Here is the call graph for this function:

Here is the caller graph for this function:

GetDsiVar()

entity GetDsiVar

(

int

l

)

Definition at line 164 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXSV)
    user_error("parallelize", "too many scalar variables\n");
 
  if((e = DsiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXSV; i++)
      DsiVars[i] = MakeDsiVar(i + 1);
 
    e = DsiVars[l - 1];
  }
 
  return (e);
}

References DsiVars, MakeDsiVar(), MAXSV, and user_error.

Referenced by gcd_and_constant_dependence_test(), and sc_add_dsi().

Here is the call graph for this function:

Here is the caller graph for this function:

GetLiVar()

entity GetLiVar

(

int

l

)

Definition at line 121 of file testdep_util.c.

         {
  entity e;
 
  if(l < 1 || l > MAXDEPTH)
    user_error("parallelize", "too many nested loops\n");
 
  if((e = LiVars[l - 1]) == (entity)0) {
    int i;
    for (i = 0; i < MAXDEPTH; i++)
      LiVars[i] = MakeLiVar(i + 1);
 
    e = LiVars[l - 1];
  }
 
  return (e);
}

References LiVars, MakeLiVar(), MAXDEPTH, and user_error.

Referenced by build_and_test_dependence_context(), dependence_system_add_lci_and_di(), and gcd_and_constant_dependence_test().

Here is the call graph for this function:

Here is the caller graph for this function:

impact_check()

bool impact_check

(

char *

module_name

)

ash_table control_to_set_of_dominators = hash_table_make(hash_pointer, 0);

ull_control_graph(module_name);

omputing_dominators(control_to_set_of_dominators, load_ctrl_graph(mod_stat));

set_precondition_map((statement_mapping) db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));

Looking for another formal variable in the list of alias associations that has same section and included call path. If this variable is checked dynamically with e1 => no need to continue

Looking for common variables in module or callee of modules to check for alias impact ...

formal parameter has a same section with other common variable

If u1 is defined (different to -1) and u1<l2, there is no alias impact The same for: l1 is defined (different to -1) and u2<l1

The common variable always have a good offset off2

ash_table_free(control_to_set_of_dominators);

lean_ctrl_graph();

eset_precondition_map();

Parameters

module_name

odule_name

Definition at line 1242 of file impact_check.c.

{
    list l_module_aliases = NIL;
    /*hash_table control_to_set_of_dominators = hash_table_make(hash_pointer, 0);*/
 
    number_of_processed_modules++;
    current_mod = local_name_to_top_level_entity(module_name);
 
    debug_on("RICEDG_DEBUG_LEVEL");
 
 
    l_module_aliases = alias_associations_list((alias_associations)
                                               db_get_memory_resource(DBR_ALIAS_ASSOCIATIONS,
                                                                      module_name, true));
 
    if (l_module_aliases != NIL) {
        dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
        /*full_control_graph(module_name);*/
        mod_stat = (statement)db_get_memory_resource(DBR_CODE, module_name, true);
        set_current_module_entity(current_mod);
 
        set_ordering_to_statement(mod_stat);
        init_dynamic_check_list(current_mod);
 
        /*computing_dominators(control_to_set_of_dominators, load_ctrl_graph(mod_stat));
 
        set_precondition_map((statement_mapping)
                             db_get_memory_resource(DBR_PRECONDITIONS,
                                                    module_name,
                                                    true));*/
        while (!ENDP(l_module_aliases)) {
            alias_association aa1 = ALIAS_ASSOCIATION(CAR(l_module_aliases));
            entity e1 = alias_association_variable(aa1);
            entity sec1 = alias_association_section(aa1);
            list path1 = alias_association_call_chain(aa1);
            expression off1 = alias_association_offset(aa1);
            int l1 = alias_association_lower_offset(aa1);
            int u1 = alias_association_upper_offset(aa1);
            l_module_aliases = CDR(l_module_aliases);
 
            /* Looking for another formal variable in the list of alias
               associations that has same section and included call path.
               If this variable is checked dynamically with e1 => no need
               to continue */
            MAP(ALIAS_ASSOCIATION, aa2, {
                entity e2 = alias_association_variable(aa2);
                entity sec2 = alias_association_section(aa2);
                list path2 = alias_association_call_chain(aa2);
                if (!same_entity_p(e1,e2) && same_entity_p(sec1,sec2) &&
                    !dynamic_checked_p(e1, e2) && included_call_chain_p(path1,path2)) {
 
                    int l2 = alias_association_lower_offset(aa2);
                    int u2 = alias_association_upper_offset(aa2);
 
                    if (((u1==-1)||(u1>=l2))&&((u2==-1)||(u2>=l1))) {
                        expression off2 = alias_association_offset(aa2);
                        if (gen_length(path1) < gen_length(path2))
                            impact_check_two_variables(e1, e2, off1, off2, path2);
                        else
                            impact_check_two_variables(e1, e2, off1, off2, path1);
                    }
                }
            }, l_module_aliases);
 
            /* Looking for common variables in module or callee of modules
               to check for alias impact ... */
            MAP(ENTITY, e2, {
                if (variable_in_common_p(e2)) {
                    ram ra = storage_ram(entity_storage(e2));
                    entity sec2 = ram_section(ra);
                    if (!dynamic_checked_p(e1, e2) && same_entity_p(sec1,sec2)) {
                        /* formal parameter has a same section with other common variable */
                        int l2 = ram_offset(ra);
                        int u2 = l2;
                        if (array_entity_p(e2))
                          {
                            int tmp;
                            if (SizeOfArray(e2, &tmp))
                              u2 = tmp - SizeOfElements(variable_basic(type_variable(entity_type(e2)))) + l2;
                            else
                              user_log("Varying size of common variable");
                          }
                        /* If u1 is defined (different to -1) and u1<l2, there is no alias impact
                           The same for: l1 is defined (different to -1) and u2<l1 */
                        if (((u1==-1)||(u1>=l2)) && (u2>=l1)) {
                            expression off2 = int_to_expression(l2);
                            /* The common variable always have a good offset off2 */
                            impact_check_two_variables(e1, e2, off1, off2, path1);
                        }
                    }
                }
            }, code_declarations(entity_code(current_mod)));
        }
        l_dynamic_check = NIL;
 
        DB_PUT_MEMORY_RESOURCE(DBR_CODE,module_name,mod_stat);
 
        /*hash_table_free(control_to_set_of_dominators);*/
        /*clean_ctrl_graph();*/
        reset_current_module_entity();
        reset_ordering_to_statement();
        /*reset_precondition_map();*/
        mod_stat = statement_undefined;
    }
    display_impact_alias_statistics();
    l_module_aliases = NIL;
    current_mod = entity_undefined;
 
    debug_off();
    return true;
}

References ALIAS_ASSOCIATION, alias_association_call_chain, alias_association_lower_offset, alias_association_offset, alias_association_section, alias_association_upper_offset, alias_association_variable, alias_associations_list, array_entity_p(), CAR, CDR, code_declarations, current_mod, db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, display_impact_alias_statistics(), dynamic_checked_p(), ENDP, ENTITY, entity_code(), entity_storage, entity_type, entity_undefined, gen_length(), impact_check_two_variables(), included_call_chain_p(), init_dynamic_check_list(), int_to_expression(), l_dynamic_check, l_module_aliases, local_name_to_top_level_entity(), MAP, mod_stat, module_name(), NIL, number_of_processed_modules, ram_offset, ram_section, reset_current_module_entity(), reset_ordering_to_statement(), same_entity_p(), set_current_module_entity(), set_ordering_to_statement(), SizeOfArray(), SizeOfElements(), statement_undefined, storage_ram, type_variable, user_log(), variable_basic, and variable_in_common_p().

Here is the call graph for this function:

load_statement_context()

Psysteme load_statement_context

(

statement

)

Referenced by TestCoupleOfEffects().

Here is the caller graph for this function:

make_context_map()

void make_context_map

(

void

)

make_filtered_dg_or_dvdg()

list make_filtered_dg_or_dvdg	(	statement	mod_stat,
		graph	mod_graph
	)

for computing the line numbers of statements

Additional information for EDF prettyprint. Instruction calls are given with statement numbers

Parameters

mod_stat	od_stat
mod_graph	od_graph

Definition at line 101 of file trace.c.

{
    list verlist = NIL;
    list vars_ent_list = get_list_of_variable_to_filter();
 
    persistant_statement_to_int s_to_l = persistant_statement_to_int_undefined;
    int dl = -1;
 
    if (!statement_undefined_p(mod_stat)) {
        /* for computing the line numbers of statements */
        s_to_l = statement_to_line_number(mod_stat);
        dl = module_to_declaration_length(get_current_module_entity());
    }
 
    MAP(VERTEX, v1, {
        statement s1 = vertex_to_statement(v1);
 
        MAP(SUCCESSOR, su, {
            vertex v2 = successor_vertex(su);
            statement s2 = vertex_to_statement(v2);
            dg_arc_label dal = (dg_arc_label) successor_arc_label(su);
 
            MAP(CONFLICT, c, {
                if (!statement_undefined_p(mod_stat)) {
                    entity conflict_var = reference_variable(effect_any_reference(conflict_source(c)));
                    if (gen_in_list_p(conflict_var, vars_ent_list) || vars_ent_list == NIL) {
                        string succ_label = (string)malloc(sizeof(string)*30);
                        int l1 = dl + apply_persistant_statement_to_int(s_to_l, s1);
                        int l2 = dl + apply_persistant_statement_to_int(s_to_l, s2);
 
                        vertex vertex_parent = NULL;
                        vertex vertex_child = NULL;
                        char statement_action_parent = action_read_p(effect_action(conflict_source(c))) ? 'R' : 'W';
                        char statement_action_child = action_read_p(effect_action(conflict_sink(c))) ? 'R' : 'W';
                        string variable_name_parent = words_to_string(effect_words_reference(effect_any_reference(conflict_source(c))));
                        string variable_name_child = words_to_string(effect_words_reference(effect_any_reference(conflict_sink(c))));
                        string node_name_parent = (string)malloc(sizeof(string)*strlen(variable_name_parent) + 30);
                        string node_name_child = (string)malloc(sizeof(string)*strlen(variable_name_child) + 30);
 
                        successor succ = NULL;
                        memset(node_name_parent, 0, sizeof(string)*strlen(variable_name_parent) + 30);
                        memset(node_name_child, 0, sizeof(string)*strlen(variable_name_child) + 30);
                        sprintf(node_name_parent, "%d-<%s>-%c", l1, variable_name_parent, statement_action_parent);
                        sprintf(node_name_child, "%d-<%s>-%c", l2, variable_name_child, statement_action_child);
 
                        /* Additional information for EDF prettyprint.
                           Instruction calls are given with  statement numbers
                        */
                        if (get_bool_property("PRETTYPRINT_WITH_COMMON_NAMES")) {
                            if (instruction_call_p(statement_instruction(s1)))
                                sprintf(node_name_parent + strlen(node_name_parent), " %td-%s", statement_number(s1),
                                        entity_local_name(call_function(instruction_call(statement_instruction(s1)))));
                            else sprintf(node_name_parent + strlen(node_name_parent), " %td", statement_number(s1));
                            if (instruction_call_p(statement_instruction(s2)))
                                sprintf(node_name_child + strlen(node_name_child), " %td-%s", statement_number(s2),
                                        entity_local_name(call_function(instruction_call(statement_instruction(s2)))));
                            else sprintf(node_name_child + strlen(node_name_child), " %td", statement_number(s2));
                        }
 
                        memset(succ_label, 0, strlen(succ_label));
                        if (conflict_cone(c) != cone_undefined) {
                            if (!statement_undefined_p(mod_stat)) {
                                strcat(succ_label, "levels(");
                                MAPL(pl, {
                                    sprintf(succ_label + strlen(succ_label),
                                            pl == cone_levels(conflict_cone(c)) ? "%td" : ",%td", INT(CAR(pl)));
                                }, cone_levels(conflict_cone(c)));
                                strcat(succ_label, ")");
                            }
                        }
 
                        vertex_parent = get_vertex_in_list(verlist, node_name_parent);
                        if (vertex_undefined_p(vertex_parent)) {
                            vertex_parent = make_vertex((vertex_label)node_name_parent, NIL);
                            ADD_ELEMENT_TO_LIST(verlist, VERTEX, vertex_parent);
                        }
 
                        vertex_child = get_vertex_in_list(verlist, node_name_child);
                        if (vertex_undefined_p(vertex_child)) {
                            vertex_child = make_vertex((vertex_label)node_name_child, NIL);
                            ADD_ELEMENT_TO_LIST(verlist, VERTEX, vertex_child);
                        }
 
                        succ = make_successor((dg_arc_label)succ_label, vertex_child);
                        ADD_ELEMENT_TO_LIST(vertex_successors(vertex_parent), SUCCESSOR, succ);
                    }
                }
            }, dg_arc_label_conflicts(dal));
 
        }, vertex_successors(v1));
 
    }, graph_vertices(mod_graph));
 
    gen_free_list(vars_ent_list);
 
    if (!statement_undefined_p(mod_stat))
        free_persistant_statement_to_int(s_to_l);
 
    return verlist;
}

References action_read_p, ADD_ELEMENT_TO_LIST, apply_persistant_statement_to_int(), call_function, CAR, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), entity_local_name(), free_persistant_statement_to_int(), gen_free_list(), gen_in_list_p(), get_bool_property(), get_current_module_entity(), get_list_of_variable_to_filter(), get_vertex_in_list(), graph_vertices, instruction_call, instruction_call_p, INT, make_successor(), make_vertex(), malloc(), MAP, MAPL, memset(), mod_stat, module_to_declaration_length(), NIL, persistant_statement_to_int_undefined, pl, reference_variable, s1, statement_instruction, statement_number, statement_to_line_number(), statement_undefined_p, SUCCESSOR, successor_arc_label, successor_vertex, verlist, VERTEX, vertex_successors, vertex_to_statement(), vertex_undefined_p, and words_to_string().

Referenced by print_filtered_dg_or_dvdg().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDibaseinorder()

Pbase MakeDibaseinorder

(

int

n

)

Pbase MakeDibaseinorder(int n) make a base of D#1 ...

D::n in order of D#1-> D#2, ...-> D::n.

Definition at line 296 of file testdep_util.c.

         {
  Pbase Dibase = BASE_NULLE;
  int i;
 
  for (i = 1; i <= n; i++) {
    Dibase = vect_add_variable(Dibase, (Variable)GetDiVar(n - i + 1));
  }
  return (Dibase);
}

References BASE_NULLE, GetDiVar(), and vect_add_variable().

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDiVar()

entity MakeDiVar

(

int

l

)

This function creates di variables.

There are MAXDEPTH di variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.

Parameters

l	is the nesting level of the variable to create

Create a variable of this format: "d#X"

Definition at line 63 of file testdep_util.c.

                        {
  entity e;
  string s;
  /* Create a variable of this format: "d#X" */
  asprintf(&s, "%s%sd#%d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetDiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeDsiVar()

entity MakeDsiVar

(

int

l

)

This function creates dsi variables.

There are MAXSV dsi variables which means that programs with more than MAXSV scalar variables cannot be parallelized by PIPS.

Parameters

l	means to create Dsi[l] variable

Create a variable of this format: "ds#XXXX"

Definition at line 146 of file testdep_util.c.

                         {
  entity e;
  string s;
  /* Create a variable of this format: "ds#XXXX" */
  asprintf(&s, "%s%sds#%.4d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetDsiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeLiVar()

entity MakeLiVar

(

int

l

)

This function creates li variables(thee ith loop index variable).

There are MAXDEPTH li variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.

Parameters

l	is the nesting level of the variable to create

Create a variable of this format: "l#X"

Definition at line 103 of file testdep_util.c.

                        {
  entity e;
  string s;
  /* Create a variable of this format: "l#X" */
  asprintf(&s, "%s%sl#%d", DI_VAR_MODULE_NAME, MODULE_SEP_STRING, l);
 
  if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined)
    e = make_entity(s, type_undefined, storage_undefined, value_undefined);
  else
    free(s);
 
  return (e);
}

References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.

Referenced by GetLiVar().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeLoopCounter()

entity MakeLoopCounter

(

void

)

Create a new loop counter variable.

Create a variable of this format: "lc#XXXXXX"

Try a new free one:

Definition at line 334 of file testdep_util.c.

                         {
  entity e;
  string s;
  //static char lcn[] = "lc#XXXXXX";
 
  while(1) {
    /* Create a variable of this format: "lc#XXXXXX" */
    asprintf(&s,
             "%s%slc#%06d",
             LOOP_COUNTER_MODULE_NAME,
             MODULE_SEP_STRING,
             ilc);
 
    if((e = gen_find_tabulated(s, entity_domain)) == entity_undefined) {
      pips_debug(8, "loop counter is %s\n", s);
      return make_entity(strdup(s),
                         type_undefined,
                         storage_undefined,
                         value_undefined);
    } else
      free(s);
 
    /* Try a new free one: */
    if((ilc += 1) == ILCMAX)
      break;
  }
 
  pips_internal_error("too many loop counters");
  return (entity_undefined);
}

References asprintf, entity_domain, entity_undefined, free(), gen_find_tabulated(), ilc, ILCMAX, LOOP_COUNTER_MODULE_NAME, make_entity, MODULE_SEP_STRING, pips_debug, pips_internal_error, storage_undefined, strdup(), type_undefined, and value_undefined.

Referenced by dependence_system_add_lci_and_di().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_dependence_graph()

void prettyprint_dependence_graph	(	FILE *	fd,
		statement	mod_stat,
		graph	mod_graph
	)

Print all edges and arcs.

There is no guarantee that the ordering_to_statement() hash table is the proper one

compute line numbers for statements

If we have zero printable conflicts, move on.

If we have more than one conflict, let's sort them !

FI: the number of conflicts should take into account the filtering due to PRETTYPRINT_MEMORY_EFFECTS_ONLY

Modification at revision 12484 because statement numbers were not initialized by C parser, with no validation of ricedg available at that time

factorize line numbers

FI: I should use another property, specific to the use-def chains, but this is quite close

if (!entity_scalar_p(reference_variable (effect_any_reference(conflict_source(c))))) {

Additional information for EDF prettyprint. Instruction calls are given with statement numbers

uniform dependence

sg_fprint(fd,gs,entity_local_name);

FI: almost print_dependence_cone:-(

Parameters

fd	d
mod_stat	od_stat
mod_graph	od_graph

Definition at line 177 of file util.c.

{
  cons *pv1, *ps, *pc;
  Ptsg gs;
  int banner_number = 0;
  bool sru_format_p =
      get_bool_property( "PRINT_DEPENDENCE_GRAPH_USING_SRU_FORMAT" );
  persistant_statement_to_int s_to_l = persistant_statement_to_int_undefined;
  int dl = -1;
  debug_on("RICEDG_DEBUG_LEVEL");
 
  ifdebug(8) {
    /* There is no guarantee that the ordering_to_statement()
     * hash table is the proper one */
    print_ordering_to_statement( );
  }
 
  if ( sru_format_p && !statement_undefined_p(mod_stat) ) {
    /* compute line numbers for statements */
    s_to_l = statement_to_line_number( mod_stat );
    dl = module_to_declaration_length( get_current_module_entity( ) );
  } else {
    banner_number
        = get_bool_property( "PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS" )
          + 2 * get_bool_property( "PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS" )
          + 4 * get_bool_property( "PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES" );
    fprintf( fd, "%s\n", dependence_graph_banner[banner_number] );
  }
 
  gen_sort_list(graph_vertices(mod_graph), (gen_cmp_func_t)vertex_sort_callback);
  for ( pv1 = graph_vertices(mod_graph); !ENDP(pv1); pv1 = CDR(pv1) ) {
    vertex v1 = VERTEX(CAR(pv1));
    statement s1 = vertex_to_statement( v1 );
    gen_sort_list(vertex_successors(v1), (gen_cmp_func_t)successor_sort_callback);
    for ( ps = vertex_successors(v1); !ENDP(ps); ps = CDR(ps) ) {
      successor su = SUCCESSOR(CAR(ps));
      vertex v2 = successor_vertex(su);
      statement s2 = vertex_to_statement( v2 );
      dg_arc_label dal = (dg_arc_label) successor_arc_label(su);
 
      /* If we have zero printable conflicts, move on.
       *
       * If we have more than one conflict, let's sort them !
       *
       * FI: the number of conflicts should take into account the
       * filtering due to PRETTYPRINT_MEMORY_EFFECTS_ONLY
       */
      list cl = dg_arc_label_conflicts(dal);
      int nb_conflicts = gen_length(cl);
      if(get_bool_property("PRETTYPRINT_MEMORY_EFFECTS_ONLY")) {
        FOREACH(CONFLICT, c, cl) {
          effect efsrc = conflict_source(c);
          if(!store_effect_p(efsrc))
            nb_conflicts--;
        }
      }
 
      if(nb_conflicts==0)
        continue;
 
      if ( !sru_format_p || statement_undefined_p(mod_stat) ) {
        /* Modification at revision 12484 because statement
         numbers were not initialized by C parser, with no
         validation of ricedg available at that time*/
        /* factorize line numbers */
        //fprintf(fd, "\t%s -->",
        // external_statement_identification(s1)
        // Revision 10893: %02d and statement_number (Pham Dat)
        fprintf( fd, "\t%02td -->", statement_number(s1) );
        //fprintf(fd, " %s with conflicts\n",
        // external_statement_identification(s2)
        fprintf( fd, " %02td with conflicts\n", statement_number(s2) );
      }
 
      if ( nb_conflicts > 1 ) {
        /*
         * Convert the list to an array for sorting
         * 20 is the initial size, should be enough for most cases
         *
         * FI: should generate a bug anytime when calls are
         * involved. At least use dependent types... or pass gen_length()
         */
        gen_array_t conflicts_array = gen_array_make( 20 );
        list_to_array( dg_arc_label_conflicts(dal), conflicts_array );
        qsort( gen_array_pointer( conflicts_array ),
               gen_array_nitems( conflicts_array ),
               sizeof(void *),
               (gen_cmp_func_t) conflicts_sort_callback);
        list conflicts_list = NIL;
        GEN_ARRAY_FOREACH(conflict, s, conflicts_array)
          conflicts_list = CONS(conflict, s, conflicts_list);
        gen_array_free(conflicts_array);
        dg_arc_label_conflicts(dal)=conflicts_list;
      }
 
      /*
       * Loop over conflict and print them
       */
      for ( pc = dg_arc_label_conflicts(dal); !ENDP(pc); pc = CDR(pc) ) {
        conflict c = CONFLICT(CAR(pc));
        effect efsrc = conflict_source(c);
 
        /* FI: I should use another property, specific to the use-def
           chains, but this is quite close */
        if(store_effect_p(efsrc)
           || !get_bool_property("PRETTYPRINT_MEMORY_EFFECTS_ONLY")) {
 
        /* if (!entity_scalar_p(reference_variable
         (effect_any_reference(conflict_source(c))))) {
         */
        if ( sru_format_p && !statement_undefined_p(mod_stat) ) {
          int l1 = dl + apply_persistant_statement_to_int( s_to_l, s1 );
          int l2 = dl + apply_persistant_statement_to_int( s_to_l, s2 );
 
          fprintf( fd, "%d %d ", l1, l2 );
          /*
           fprintf(fd, "%d %d ",
           statement_number(s1), statement_number(s2));
           */
          fprintf( fd,
                   "%s %s ",
                   full_action_to_short_string(effect_action(conflict_source(c))),
                   full_action_to_short_string(effect_action(conflict_sink(c))));
          fprintf( fd, "<" );
          print_words( fd,
                       effect_words_reference(
                           effect_any_reference(conflict_source(c)) ) );
          fprintf( fd, "> - <" );
          print_words( fd,
                       effect_words_reference(
                           effect_any_reference(conflict_sink(c)) ) );
          fprintf( fd, ">" );
 
          /* Additional information for EDF prettyprint.
           Instruction calls are given with  statement numbers
           */
          if ( get_bool_property( "PRETTYPRINT_WITH_COMMON_NAMES" ) ) {
            if ( instruction_call_p(statement_instruction(s1)) )
              fprintf( fd,
                       " %td-%s",
                       statement_number(s1),
                       entity_local_name(
                           call_function(
                               instruction_call(statement_instruction(s1))) ) );
            else
              fprintf( fd, " %td", statement_number(s1) );
            if ( instruction_call_p(statement_instruction(s2)) )
              fprintf( fd,
                       " %td-%s",
                       statement_number(s2),
                       entity_local_name(
                           call_function(
                               instruction_call(statement_instruction(s2))) ) );
            else
              fprintf( fd, " %td", statement_number(s2) );
          }
 
        } else {
          fprintf( fd, "\t\tfrom " );
          print_words( fd, words_effect( conflict_source(c) ) );
 
          fprintf( fd, " to " );
          print_words( fd, words_effect( conflict_sink(c) ) );
        }
 
        if ( conflict_cone(c) != cone_undefined ) {
          if ( sru_format_p && !statement_undefined_p(mod_stat) ) {
            fprintf( fd, " levels(" );
            MAPL(pl, {
                  fprintf(fd, pl==cone_levels(conflict_cone(c))? "%td" : ",%td",
                      INT(CAR(pl)));
                }, cone_levels(conflict_cone(c)));
            fprintf( fd, ") " );
          } else {
            fprintf( fd, " at levels " );
            MAPL(pl, {
                  fprintf(fd, " %td", INT(CAR(pl)));
                }, cone_levels(conflict_cone(c)));
            fprintf( fd, "\n" );
          }
 
          if( get_bool_property( "PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES" ) ) {
            gs = (Ptsg) cone_generating_system(conflict_cone(c));
            if( !SG_UNDEFINED_P( gs ) ) {
              if( sru_format_p && !statement_undefined_p(mod_stat) ) {
                if( sg_nbre_sommets( gs ) == 1 && sg_nbre_rayons( gs ) == 0
                    && sg_nbre_droites( gs ) == 0 ) {
                  /* uniform dependence */
                  fprintf( fd, "uniform" );
                  fprint_lsom_as_dense( fd, sg_sommets( gs ), gs->base );
                } else {
                  sg_fprint_as_ddv( fd, gs );
                }
              } else {
                /* sg_fprint(fd,gs,entity_local_name); */
                /* FI: almost print_dependence_cone:-( */
                sg_fprint_as_dense( fd, gs, gs->base );
                ifdebug(2) {
                  Psysteme sc1 = sc_new( );
                  sc1 = sg_to_sc_chernikova( gs );
                  (void) fprintf( fd,
                                  "syst. lin. correspondant au syst. gen.:\n" );
                  sc_fprint( fd, sc1, (get_variable_name_t) entity_local_name );
                }
              }
            }
          }
        } else {
          if ( sru_format_p && !statement_undefined_p(mod_stat) )
            fprintf( fd, " levels()" );
        }
        fprintf( fd, "\n" );
        }
      }
    }
  }
 
  if ( sru_format_p && !statement_undefined_p(mod_stat) ) {
    free_persistant_statement_to_int( s_to_l );
  } else {
    fprintf( fd,
             "\n****************** End of Dependence Graph ******************\n" );
  }
 
  debug_off();
}

References apply_persistant_statement_to_int(), type_sg::base, call_function, CAR, CDR, cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflicts_sort_callback(), CONS, debug_off, debug_on, dependence_graph_banner, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), ENDP, entity_local_name(), FOREACH, fprint_lsom_as_dense(), fprintf(), free_persistant_statement_to_int(), full_action_to_short_string(), GEN_ARRAY_FOREACH, gen_array_free(), gen_array_make(), gen_array_nitems(), gen_array_pointer(), gen_length(), gen_sort_list(), get_bool_property(), get_current_module_entity(), graph_vertices, ifdebug, instruction_call, instruction_call_p, INT, list_to_array(), MAPL, mod_stat, module_to_declaration_length(), NIL, persistant_statement_to_int_undefined, pl, print_ordering_to_statement(), print_words(), s1, sc_fprint(), sc_new(), sg_fprint_as_ddv(), sg_fprint_as_dense(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_sommets, sg_to_sc_chernikova(), SG_UNDEFINED_P, statement_instruction, statement_number, statement_to_line_number(), statement_undefined_p, store_effect_p(), SUCCESSOR, successor_arc_label, successor_sort_callback(), successor_vertex, VERTEX, vertex_sort_callback(), vertex_successors, vertex_to_statement(), and words_effect().

Referenced by chains(), FindAndTopSortSccs(), icm_codegen(), print_dependence_or_chains_graph(), rice_dependence_graph(), and rice_update_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_dependence_graph_view()

void prettyprint_dependence_graph_view	(	FILE *	fd,
		statement	mod_stat,
		graph	mod_graph
	)

Do not print vertices and arcs ignored by the parallelization algorithms.

At least, hopefully...

f (! entity_scalar_p(reference_variable (effect_any_reference(conflict_source(c))))) {

sg_fprint(fd,gs,entity_local_name);

Parameters

fd	d
mod_stat	od_stat
mod_graph	od_graph

Definition at line 833 of file util.c.

{
  cons *pv1, *ps, *pc;
  Ptsg gs;
  int banner_number = 0;
 
  banner_number =
      get_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS") +
      2*get_bool_property
      ("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS") +
      4*get_bool_property
      ("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES");
 
  fprintf(fd, "%s\n", dependence_graph_banner[banner_number]);
 
  set_enclosing_loops_map( loops_mapping_of_statement(mod_stat) );
 
  debug_on("RICEDG_DEBUG_LEVEL");
 
  for (pv1 = graph_vertices(mod_graph); !ENDP(pv1); pv1 = CDR(pv1)) {
    vertex v1 = VERTEX(CAR(pv1));
    statement s1 = vertex_to_statement(v1);
    list loops1 = load_statement_enclosing_loops(s1);
 
    for (ps = vertex_successors(v1); !ENDP(ps); ps = CDR(ps)) {
      successor su = SUCCESSOR(CAR(ps));
      vertex v2 = successor_vertex(su);
      statement s2 = vertex_to_statement(v2);
      list loops2 = load_statement_enclosing_loops(s2);
      dg_arc_label dal = (dg_arc_label) successor_arc_label(su);
 
      /*
       * If we have more than one conflict, let's sort them !
       */
      int nb_conflicts = gen_length(dg_arc_label_conflicts(dal));
      if ( nb_conflicts > 1 ) {
        /*
         * Convert the list to an array for sorting
         * 20 is the initial size, should be enough for most of the case
         */
        gen_array_t conflicts_array = gen_array_make( 20 );
        list_to_array( dg_arc_label_conflicts(dal), conflicts_array );
        qsort( gen_array_pointer( conflicts_array ),
            gen_array_nitems( conflicts_array ),
            sizeof(void *),
            (gen_cmp_func_t) conflicts_sort_callback);
        list conflicts_list = NIL;
        GEN_ARRAY_FOREACH(conflict, s, conflicts_array)
        conflicts_list = CONS(conflict, s, conflicts_list);
        gen_array_free(conflicts_array);
        dg_arc_label_conflicts(dal)=conflicts_list;
      }
      int nbrcomloops = FindMaximumCommonLevel(loops1, loops2);
      for (pc = dg_arc_label_conflicts(dal); !ENDP(pc); pc = CDR(pc)) {
        conflict c = CONFLICT(CAR(pc));
 
        if(conflict_cone(c) == cone_undefined) continue;
        else {
          cons * lls = cone_levels(conflict_cone(c));
          cons *llsred =NIL;
          if (get_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS")){
            MAPL(pl,{
                _int level = INT(CAR(pl));
                if (level <= nbrcomloops) {
                  if (! ignore_this_conflict(v1,v2,c,level)) {
                    llsred = gen_nconc(llsred, CONS(INT, level, NIL));
                  }
                }
                else {
                  if (get_bool_property
                      ("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS")) {
                    continue;
                  }
                  else llsred = gen_nconc(llsred, CONS(INT, level, NIL));
                }
            }, lls);
          }
          if (llsred == NIL) continue;
          else {
            /*if (!     entity_scalar_p(reference_variable
                          (effect_any_reference(conflict_source(c))))) { */
 
            fprintf(fd, "\t%02td --> %02td with conflicts\n",
                statement_number(s1), statement_number(s2));
 
            fprintf(fd, "\t\tfrom ");
            print_words(fd, words_effect(conflict_source(c)));
 
            fprintf(fd, " to ");
            print_words(fd, words_effect(conflict_sink(c)));
 
            fprintf(fd, " at levels ");
            MAPL(pl, {
                fprintf(fd, " %td", INT(CAR(pl)));
            }, llsred);
 
            fprintf(fd, "\n");
            if(get_bool_property
                ("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES")) {
              gs = (Ptsg)cone_generating_system(conflict_cone(c));
              if (!SG_UNDEFINED_P(gs)) {
                /* sg_fprint(fd,gs,entity_local_name); */
                sg_fprint_as_dense(fd, gs, gs->base);
                ifdebug(2) {
                  Psysteme sc1 = sc_new();
                  sc1 = sg_to_sc_chernikova(gs);
                  (void) fprintf(fd,"syst. lin. correspondant au  syst. gen.:\n");
                  sc_fprint(fd, sc1, (get_variable_name_t) entity_local_name);
                }
              }
              fprintf(fd, "\n");
            }
          }
        }
      }
    }
  }
  clean_enclosing_loops();
  debug_off();
  fprintf(fd, "\n****************** End of Dependence Graph "
      "******************\n");
}

References type_sg::base, CAR, CDR, clean_enclosing_loops(), cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflicts_sort_callback(), CONS, debug_off, debug_on, dependence_graph_banner, dg_arc_label_conflicts, ENDP, entity_local_name(), prettyprint_dot_context::fd, FindMaximumCommonLevel(), fprintf(), GEN_ARRAY_FOREACH, gen_array_free(), gen_array_make(), gen_array_nitems(), gen_array_pointer(), gen_length(), gen_nconc(), get_bool_property(), graph_vertices, ifdebug, ignore_this_conflict(), INT, level, list_to_array(), load_statement_enclosing_loops(), loops_mapping_of_statement(), MAPL, mod_stat, NIL, pl, print_words(), s1, sc_fprint(), sc_new(), set_enclosing_loops_map(), sg_fprint_as_dense(), sg_to_sc_chernikova(), SG_UNDEFINED_P, statement_number, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_to_statement(), and words_effect().

Referenced by print_dependence_or_chains_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_dot_dependence_graph()

void prettyprint_dot_dependence_graph	(	FILE *	fd,
		statement	mod_stat,
		graph	mod_graph
	)

Output dependence graph in a file in graphviz dot format.

Parameters

fd	is the file descriptor where to output
mod_stat	is the module statement (not necessary module, it can be a block statement for instance
graph	is the dependence graph to print

There is no guarantee that the ordering_to_statement() hash table is the proper one

graph style

Nodes style

uniform dependence

Parameters

fd	d
mod_stat	od_stat
mod_graph	od_graph

Definition at line 583 of file util.c.

                                                         {
  debug_on( "RICEDG_DEBUG_LEVEL" );
 
  ifdebug(8) {
    /* There is no guarantee that the ordering_to_statement()
     * hash table is the proper one */
    print_ordering_to_statement( );
  }
  // Begin graph
  fprintf( fd, "digraph {\n" );
 
 
  bool centered = get_bool_property( "PRINT_DOTDG_CENTERED" );
  const char* title = get_string_property( "PRINT_DOTDG_TITLE" );
  const char* title_position = get_string_property( "PRINT_DOTDG_TITLE_POSITION" );
  const char* background = get_string_property( "PRINT_DOTDG_BACKGROUND" );
  const char* nodeshape= get_string_property( "PRINT_DOTDG_NODE_SHAPE" );
  const char* nodeshapecolor = get_string_property( "PRINT_DOTDG_NODE_SHAPE_COLOR" );
  const char* nodefillcolor = get_string_property( "PRINT_DOTDG_NODE_FILL_COLOR" );
  const char* nodefontcolor = get_string_property( "PRINT_DOTDG_NODE_FONT_COLOR" );
  const char* nodefontsize = get_string_property( "PRINT_DOTDG_NODE_FONT_SIZE" );
  const char* nodefontface = get_string_property( "PRINT_DOTDG_NODE_FONT_FACE" );
 
 
  /* graph style */
  fprintf( fd,
           "\n"
           "  /* graph style */\n");
  // Print title if not empty
  if( !same_string_p( title, "" ) ) {
    fprintf( fd, "  label=\"%s\";\n", title);
  }
  // Print title location if not empty
  if( !same_string_p( title_position, "" ) ) {
    fprintf( fd, "  labelloc=\"%s\";\n", title_position);
  }
  // Print background color if not empty
  if( !same_string_p( background, "" ) ) {
    fprintf( fd, "  bgcolor=\"%s\";\n", background);
  }
  if( centered ) {
    fprintf( fd, "  center=\"true\";\n");
  }
  fprintf( fd, "\n\n");
 
 
 
  /* Nodes style */
  fprintf( fd,
           "\n"
             "  /* Nodes style */\n"
             "  node [shape=\"%s\",color=\"%s\",fillcolor=\"%s\","
             "fontcolor=\"%s\",fontsize=\"%s\",fontname=\"%s\"];\n\n",
           nodeshape,
           nodeshapecolor,
           nodefillcolor,
           nodefontcolor,
           nodefontsize,
           nodefontface );
 
 
 
 
  // Should we print the statement or only its ordering ?
  bool print_statement = get_bool_property( "PRINT_DOTDG_STATEMENT" );
  // Should node be ordered top down according to the statement ordering ?
  bool ordered = get_bool_property( "PRINT_DOTDG_TOP_DOWN_ORDERED" );
 
  if( ordered || print_statement ) {
  fprintf( fd,
               "\n  {\n    /* Print nodes for statements %s order them */\n\n",
             ordered ? "and" : "but don't" );
 
    if ( ordered ) {
      fprintf( fd,
               "    /* ordering edges must be invisible, so set background color */\n"
               "    edge  [weight=100,color=%s];\n\n",
               background );
    }
 
    // Generate nodes
    struct prettyprint_dot_context ctx;
    ctx.fd = fd;
    ctx.current = NULL;
    ctx.ordered = ordered;
    ctx.print_statement = print_statement;
    ctx.previous_ordering = 0;
 
    gen_context_recurse( mod_stat, &ctx,
        statement_domain, prettyprint_dot_nodes, gen_null2 );
    fprintf( fd, "  }\n\n" );
  }
 
 
  fprintf( fd, "  /* Print arcs between statements */\n\n" );
  fprintf( fd, "  /* Dependence arcs won't constrain node positions */\nedge [constraint=false];\n\n" );
 
 
 
  const char* flowdep_color = get_string_property( "PRINT_DOTDG_FLOW_DEP_COLOR" );
  const char* flowdep_style = get_string_property( "PRINT_DOTDG_FLOW_DEP_STYLE" );
  const char* antidep_color = get_string_property( "PRINT_DOTDG_ANTI_DEP_COLOR" );
  const char* antidep_style = get_string_property( "PRINT_DOTDG_ANTI_DEP_STYLE" );
  const char* outputdep_color = get_string_property( "PRINT_DOTDG_OUTPUT_DEP_COLOR" );
  const char* outputdep_style = get_string_property( "PRINT_DOTDG_OUTPUT_DEP_STYLE" );
  const char* inputdep_color = get_string_property( "PRINT_DOTDG_INPUT_DEP_COLOR" );
  const char* inputdep_style = get_string_property( "PRINT_DOTDG_INPUT_DEP_STYLE" );
 
  bool mask_loop_carried = get_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS");
  bool mask_loop_privatized = get_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS");
  set_enclosing_loops_map( loops_mapping_of_statement(mod_stat) );
 
  // Loop over the graph and print all dependences
  FOREACH( vertex, v1 , graph_vertices( mod_graph ) ) {
    statement s1 = vertex_to_statement( v1 );
    list loops1 = load_statement_enclosing_loops(s1);
    FOREACH( successor, su, vertex_successors(v1) )
    {
      vertex v2 = successor_vertex( su );
      statement s2 = vertex_to_statement( v2 );
      list loops2 = load_statement_enclosing_loops(s2);
      dg_arc_label dal = (dg_arc_label) successor_arc_label( su );
      int nbrcomloops = FindMaximumCommonLevel(loops1, loops2);
      FOREACH( conflict, c, dg_arc_label_conflicts( dal ) )
      {
        action source_act = effect_action( conflict_source( c ) );
        action sink_act = effect_action( conflict_sink( c ) );
        reference sink_ref = effect_any_reference( conflict_sink( c ) );
        reference source_ref = effect_any_reference( conflict_source( c ) );
        const char* color = inputdep_color;
        const char* style = inputdep_style;
 
        /*
         * Here we check if this arc is only loop carried or not and we might
         * skip it if required by property
         */
        bool keep_this_conflict = true;
        if(mask_loop_carried && conflict_cone(c) != cone_undefined) {
          list lls = cone_levels(conflict_cone(c));
          keep_this_conflict = false;
          FOREACH(int, level, lls) {
            if(level > nbrcomloops ) {
              keep_this_conflict = true;
              break;
            }
          }
        }
        bool keep_this_conflict_privatized = true;
        if(mask_loop_privatized && conflict_cone(c) != cone_undefined) {
          list lls = cone_levels(conflict_cone(c));
          keep_this_conflict_privatized = true;
          FOREACH(int, level, lls) {
            if(level > nbrcomloops || ignore_this_conflict(v1,v2,c,level)) {
              keep_this_conflict_privatized=false;
              //break;
            }
          }
        }
 
        keep_this_conflict =  keep_this_conflict &&  keep_this_conflict_privatized;
        //verify also for level = 0
        if(mask_loop_privatized && ignore_this_conflict(v1,v2,c,0))
          keep_this_conflict=false;
 
        if(!keep_this_conflict) {
          continue;
        }
 
 
        // Ok let's display it now.
 
        if( action_read_p( source_act ) && action_write_p( sink_act ) ) {
          color = antidep_color;
          style = antidep_style;
        } else if( action_write_p( source_act ) && action_write_p( sink_act ) ) {
          color = outputdep_color;
          style = outputdep_style;
        } else if( action_write_p( source_act ) && action_read_p( sink_act ) ) {
          color = flowdep_color;
          style = flowdep_style;
        }
        fprintf( fd,
            "%d -> %d [color=%s,style=%s,label=\"",
            (int) statement_ordering(s1),
            (int) statement_ordering(s2),
            color,
            style );
        fprintf( fd,
            "%s <",
            full_action_to_short_string( source_act ));
        print_words( fd,
            effect_words_reference( source_ref ) );
        fprintf( fd, ">\\n" );
        fprintf( fd,
            "%s <",
            full_action_to_short_string( sink_act ));
        print_words( fd,
            effect_words_reference( sink_ref ) );
        fprintf( fd, ">\\n" );
 
 
        // Print the levels and the cone
        if ( conflict_cone( c ) != cone_undefined ) {
          fprintf( fd, " levels(" );
          MAPL(pl, {
              fprintf(fd, pl==cone_levels(conflict_cone(c))? "%td" : ",%td",
                  INT(CAR(pl)));
          }, cone_levels(conflict_cone(c)));
          fprintf( fd, ") " );
 
          if ( get_bool_property( "PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES" ) ) {
            Ptsg gs = (Ptsg) cone_generating_system( conflict_cone( c ) );
            if ( !SG_UNDEFINED_P( gs ) ) {
              if ( sg_nbre_sommets( gs ) == 1 && sg_nbre_rayons( gs ) == 0
                  && sg_nbre_droites( gs ) == 0 ) {
                /* uniform dependence */
                fprintf( fd, "uniform" );
                fprint_lsom_as_dense( fd, sg_sommets( gs ), gs->base );
              } else {
                sg_fprint_as_ddv( fd, gs );
              }
            }
          }
        } else {
          fprintf( fd, " levels()" );
        }
        fprintf( fd, "\"];\n" );
      }
    }
  }
 
  fprintf( fd, "\n}\n" );
 
  reset_enclosing_loops_map();
 
  debug_off( );
}

References action_read_p, action_write_p, type_sg::base, CAR, cone_generating_system, cone_levels, cone_undefined, conflict_cone, conflict_sink, conflict_source, prettyprint_dot_context::current, debug_off, debug_on, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), prettyprint_dot_context::fd, FindMaximumCommonLevel(), FOREACH, fprint_lsom_as_dense(), fprintf(), full_action_to_short_string(), gen_context_recurse, gen_null2(), get_bool_property(), get_string_property(), graph_vertices, ifdebug, ignore_this_conflict(), INT, level, load_statement_enclosing_loops(), loops_mapping_of_statement(), MAPL, mod_stat, prettyprint_dot_context::ordered, pl, prettyprint_dot_nodes(), prettyprint_dot_context::previous_ordering, print_ordering_to_statement(), print_statement(), prettyprint_dot_context::print_statement, print_words(), reset_enclosing_loops_map(), s1, same_string_p, set_enclosing_loops_map(), sg_fprint_as_ddv(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_sommets, SG_UNDEFINED_P, statement_domain, statement_ordering, successor_arc_label, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by do_simplify_dg(), and print_dot_dependence_or_chains_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_graph_daVinci()

void prettyprint_graph_daVinci	(	FILE *	out_f,
		list	l_of_vers
	)

print a graph to daVinci format, each label of successor is represented by a circular node, each vertex is represented by a square node

To match the call to the free() at the end:

Parameters

out_f	ut_f
l_of_vers	_of_vers

Definition at line 63 of file trace.c.

                                                             {
    /* To match the call to the free() at the end: */
    string gr_buffer = strdup(""); 
    bool first_node_parent = true;
    fprintf(out_f, "[\n");
 
    MAP(VERTEX, ver, {
        string node_name_parent = (string)vertex_vertex_label(ver);
        bool first_node_child = true;
        if (first_node_parent)
            first_node_parent = false;
        else
            fprintf(out_f, ",\n");
        fprintf(out_f,"l(\"%s\",n(\"\",[a(\"OBJECT\",\"%s\")],[\n", node_name_parent, node_name_parent); 
 
        MAP(SUCCESSOR, succ, {
            string node_name_child = (string)vertex_vertex_label(successor_vertex(succ));
            if (first_node_child)
                first_node_child = false;
            else
                fprintf(out_f, ",\n");
            if (strlen((string)successor_arc_label(succ)) == 0) {
                fprintf(out_f, "  l(\"\",e(\"\",[],r(\"%s\")))", node_name_child);
            } else {
                string temp_buffer = strdup(concatenate(gr_buffer, ",\nl(\"", node_name_parent, "-", node_name_child, "\",n(\"\",[a(\"OBJECT\",\"", (string)successor_arc_label(succ), "\"),a(\"_GO\",\"ellipse\")],[\n  l(\"\",e(\"\",[],r(\"", node_name_child, "\")))]))", NULL));
                free(gr_buffer);
                gr_buffer = temp_buffer;
                fprintf(out_f, "  l(\"\",e(\"\",[],r(\"%s-%s\")))", node_name_parent, node_name_child);
            } 
        }, vertex_successors(ver));
        fprintf(out_f, "]))");
    }, l_of_vers);
 
    fprintf(out_f, "%s", gr_buffer);
    fprintf(out_f, "\n]");
    free(gr_buffer);
}

References concatenate(), fprintf(), free(), MAP, strdup(), SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.

Referenced by print_filtered_dg_or_dvdg().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_graph_text()

void prettyprint_graph_text	(	FILE *	out_f,
		list	l_of_vers
	)

print a graph to text format

Parameters

out_f	ut_f
l_of_vers	_of_vers

Definition at line 46 of file trace.c.

{
  FOREACH (VERTEX, ver, l_of_vers) {
    FOREACH (SUCCESSOR, succ,  vertex_successors(ver)) {
      fputs((string) vertex_vertex_label (ver), out_f);
      fprintf(out_f, " ");
      fputs((string) vertex_vertex_label (successor_vertex(succ)), out_f);
      fprintf(out_f, " ");
      fputs((string) successor_arc_label (succ), out_f);
      fprintf(out_f, "\n");
    }
  }
}

References FOREACH, fprintf(), SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.

Referenced by print_filtered_dg_or_dvdg().

Here is the call graph for this function:

Here is the caller graph for this function:

print_chains_graph()

bool print_chains_graph

(

string

name

)

Parameters

name

ame

Definition at line 131 of file prettyprint.c.

{
    return print_dependence_or_chains_graph(name, false);
}

References print_dependence_or_chains_graph().

Here is the call graph for this function:

print_dependence_cone()

void print_dependence_cone	(	FILE *	fd,
		Ptsg	dc,
		Pbase	basis
	)

Parameters

fd	d
dc	c
basis	asis

Definition at line 974 of file util.c.

{
    Psommet v;
    Pray_dte r;
    fprintf(fd,"\nDependence cone :\n");
    if (SG_UNDEFINED_P(dc)) fprintf(fd, "NULL \n");
    else {
        fprintf(fd,"basis :");
        base_fprint(fd, basis, (get_variable_name_t) safe_entity_name);
        fprintf(fd,"%d vertice(s) :",sg_nbre_sommets(dc));
        v = sg_sommets(dc);
        for(; v!=NULL; v= v->succ) {
            fprint_string_Value(fd, " \n\t denominator = ", v->denominateur);
            fprintf(fd, "\t");
            print_vect_in_vertice_val(fd,v->vecteur,basis);     
        }
 
        fprintf(fd,"\n%d ray(s) : ",sg_nbre_rayons(dc));
   
        for(r = sg_rayons(dc); r!=NULL; r=r->succ) 
            print_vect_in_vertice_val(fd,r->vecteur,basis);
    
        fprintf(fd,"\n%d line(s) : ",sg_nbre_droites(dc));
   
        for(r = sg_droites(dc); r!=NULL; r=r->succ) 
            print_vect_in_vertice_val(fd,r->vecteur,basis);
        fprintf(fd,"\n");
    }
}

References base_fprint(), typ_som::denominateur, prettyprint_dot_context::fd, fprint_string_Value(), fprintf(), print_vect_in_vertice_val(), safe_entity_name(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, sg_sommets, SG_UNDEFINED_P, rdte::succ, typ_som::succ, rdte::vecteur, and typ_som::vecteur.

Referenced by dependence_cone_positive(), and TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

print_dependence_graph()

bool print_dependence_graph

(

string

name

)

Parameters

name

ame

Definition at line 126 of file prettyprint.c.

{
    return print_dependence_or_chains_graph(name, true);
}

References print_dependence_or_chains_graph().

Referenced by print_effective_dependence_graph(), print_loop_carried_dependence_graph(), and print_whole_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

print_dot_chains_graph()

bool print_dot_chains_graph

(

string

name

)

This pipmake pass output the chains in a file usable by the graphviz tool dot.

Parameters

name	is the name of the module, given by pipsmake

Returns

always true ? see print_dot_dependence_graph

Parameters

name

ame

Definition at line 200 of file prettyprint.c.

                                           {
  return print_dot_dependence_or_chains_graph( name, false );
}

References print_dot_dependence_or_chains_graph().

Here is the call graph for this function:

print_dot_dependence_graph()

bool print_dot_dependence_graph

(

string

name

)

This pipmake pass output the DG in a file usable by graphviz tool dot.

Parameters

name	is the name of the module, given by pipsmake

Returns

always true ? see print_dot_dependence_graph

Parameters

name

ame

Definition at line 210 of file prettyprint.c.

                                               {
  return print_dot_dependence_or_chains_graph( name, true );
}

References print_dot_dependence_or_chains_graph().

Here is the call graph for this function:

print_effective_dependence_graph()

bool print_effective_dependence_graph

(

const

string

)

Parameters

string

od_name

Definition at line 59 of file prettyprint.c.

{
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS",
                      true);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS",
                      false);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES",
                      false);
    return print_dependence_graph(mod_name);
}

References print_dependence_graph(), and set_bool_property().

Here is the call graph for this function:

print_filtered_dependence_daVinci_graph()

bool print_filtered_dependence_daVinci_graph

(

const

string

)

Parameters

string

od_name

Definition at line 52 of file prettyprint.c.

{
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES",
                      true);
    return print_filtered_dg_or_dvdg(mod_name, true);
}

References print_filtered_dg_or_dvdg(), and set_bool_property().

Here is the call graph for this function:

print_filtered_dependence_graph()

bool print_filtered_dependence_graph

(

const

string

)

Parameters

string

od_name

Definition at line 45 of file prettyprint.c.

{
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES",
                      true);
    return print_filtered_dg_or_dvdg(mod_name, false);
}

References print_filtered_dg_or_dvdg(), and set_bool_property().

Here is the call graph for this function:

print_filtered_dg_or_dvdg()

bool print_filtered_dg_or_dvdg	(	string	mod_name,
		bool	is_dv
	)

Parameters

mod_name	od_name
is_dv	s_dv

Definition at line 202 of file trace.c.

{
    string dg_name = NULL;
    string local_dg_name = NULL;
    FILE *fp;
    graph dg;
    statement mod_stat;
    list flt_graph;
 
    set_current_module_entity(local_name_to_top_level_entity(mod_name));
    set_current_module_statement( (statement)
        db_get_memory_resource(DBR_CODE, mod_name, true) );
    mod_stat = get_current_module_statement();
    set_ordering_to_statement(mod_stat);
    
    dg = (graph) db_get_memory_resource(DBR_DG, mod_name, true);
 
    flt_graph = make_filtered_dg_or_dvdg(mod_stat, dg);
 
    local_dg_name = db_build_file_resource_name(DBR_DG, mod_name, is_dv ? ".dvdg" : ".dg");
    dg_name = strdup(concatenate(db_get_current_workspace_directory(), 
                                 "/", local_dg_name, NULL));
    fp = safe_fopen(dg_name, "w");
 
    debug_on("RICEDG_DEBUG_LEVEL");
 
    if (is_dv) {
        prettyprint_graph_daVinci(fp, flt_graph);
    } else {
        prettyprint_graph_text(fp, flt_graph);
    }
 
    debug_off();
    
    safe_fclose(fp, dg_name);
    free(dg_name);
    
    DB_PUT_FILE_RESOURCE(is_dv ? DBR_DVDG_FILE : DBR_DG_FILE, strdup(mod_name), local_dg_name);
 
    gen_free_list(flt_graph);
    
    reset_current_module_statement();
    reset_current_module_entity();
    reset_ordering_to_statement();
 
    return true;
}

References concatenate(), db_build_file_resource_name(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_FILE_RESOURCE, debug_off, debug_on, dg, free(), gen_free_list(), get_current_module_statement(), local_name_to_top_level_entity(), make_filtered_dg_or_dvdg(), mod_stat, prettyprint_graph_daVinci(), prettyprint_graph_text(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), safe_fclose(), safe_fopen(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), and strdup().

Referenced by print_filtered_dependence_daVinci_graph(), and print_filtered_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

print_loop_carried_dependence_graph()

bool print_loop_carried_dependence_graph

(

const

string

)

Parameters

string

od_name

Definition at line 70 of file prettyprint.c.

{
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS",
                      true);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS",
                      true);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES",
                      true);
    return print_dependence_graph(mod_name);
}

References print_dependence_graph(), and set_bool_property().

Here is the call graph for this function:

print_loopnest_dependence_cone()

bool print_loopnest_dependence_cone

(

const char *

module_name

)

Get the loop label from the user

Parameters

module_name

odule_name

Definition at line 274 of file trace.c.

{
  statement mod_stat;
  graph dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
  FILE *fp;
  string dc_name,local_dc_name;
  statement loopnest_st;
  bool first=true;
  set_current_module_entity(local_name_to_top_level_entity(module_name));
  set_current_module_statement( (statement)
                                db_get_memory_resource(DBR_CODE, module_name, true) );
  mod_stat = get_current_module_statement();
  set_ordering_to_statement(mod_stat);
  local_dc_name = db_build_file_resource_name(DBR_DC_FILE, module_name,  ".dc");
  dc_name = strdup(concatenate(db_get_current_workspace_directory(), "/", local_dc_name, NULL));
  fp = safe_fopen(dc_name, "w");
 
  debug_on("RICEDG_DEBUG_LEVEL");
  
  /* Get the loop label from the user */
  const char* lp_label = get_string_property("LOOP_LABEL");
  if( string_undefined_p( lp_label))
    pips_user_warning("No loop label", "Please precise the loop label\n");
   
  if(lp_label)
    {
      selected_label = find_label_entity(module_name, lp_label);
      if (entity_undefined_p(selected_label)) {
        pips_user_warning("loop label does not exist\n", "Please give a valid label (%s not valid)\n",lp_label);
      }
    }
  if (!entity_undefined_p(selected_label)) {
    fprintf(fp,"Label: %s ",lp_label);
    loopnest_st=find_loop_from_label(mod_stat, selected_label);    
    FOREACH(VERTEX,v,graph_vertices(dg)) {
      statement s = vertex_to_statement(v);
      // Verify s is a statement in the loop nest
      statement_in_loopnest_p= false;
      test_statement_of_reference = s;
      gen_recurse(loopnest_st, statement_domain, gen_true,statement_in_loopnest);
        
      if(statement_in_loopnest_p) {
        FOREACH(SUCCESSOR,su,vertex_successors(v)) {
              
          vertex v2 = successor_vertex(su);
          statement s2 = vertex_to_statement( v2 );
          // Verify s2 is a statement in the loop nest      
          statement_in_loopnest_p= false;
          test_statement_of_reference = s2;
          gen_recurse(loopnest_st, statement_domain, gen_true,statement_in_loopnest);
        
          if(statement_in_loopnest_p) { // s and s2 are in the loop nest
           
            FOREACH(CONFLICT,c,dg_arc_label_conflicts(successor_arc_label(su))) {
                       
              if ( conflict_cone(c) != cone_undefined ) {
                Ptsg gs = (Ptsg) cone_generating_system(conflict_cone(c));
                if( !SG_UNDEFINED_P(gs)) {
                  if (first) {
                    fprintf(fp,"- Dependence Cone Basis :");
                    base_fprint(fp,gs->base , (get_variable_name_t) safe_entity_name);
                    first=false;
                  }
                  if( sg_nbre_rayons(gs) > 0) {
                    for (Pray_dte e = sg_rayons(gs); e != NULL; e = e->succ) {
                      print_cone_vecteur(fp,e->vecteur, gs,2);
                    }
                  }
                  if( sg_nbre_droites(gs) > 0) {
                    for (Pray_dte e = sg_droites(gs); e != NULL; e = e->succ) {
                      Pvecteur v=vect_copy(e->vecteur);
                      print_cone_vecteur(fp,e->vecteur, gs,2);
                      vect_chg_sgn(v);
                      print_cone_vecteur(fp,e->vecteur, gs,2);
                      vect_rm(v);
                    }
                  }
                  if(  sg_nbre_sommets(gs) > 0) {
                    for (Psommet e = sg_sommets(gs); e != NULL; e = e->succ) {
                      print_cone_vecteur(fp,e->vecteur, gs,1);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    if (first) fprintf(fp,"- No Dependencies");
  }
 
  debug_off();
    
  safe_fclose(fp, dc_name);
  free(dc_name);
    
  DB_PUT_FILE_RESOURCE( DBR_DC_FILE, strdup(module_name), local_dc_name);
 
  reset_current_module_statement();
  reset_current_module_entity();
  reset_ordering_to_statement();
 
  return true;
}

References type_sg::base, base_fprint(), concatenate(), cone_generating_system, cone_undefined, CONFLICT, conflict_cone, db_build_file_resource_name(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_FILE_RESOURCE, debug_off, debug_on, dg, dg_arc_label_conflicts, entity_undefined_p, find_label_entity(), find_loop_from_label(), FOREACH, fprintf(), free(), gen_recurse, gen_true(), get_current_module_statement(), get_string_property(), graph_vertices, local_name_to_top_level_entity(), mod_stat, module_name(), pips_user_warning, print_cone_vecteur(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), safe_entity_name(), safe_fclose(), safe_fopen(), selected_label, set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, sg_sommets, SG_UNDEFINED_P, statement_domain, statement_in_loopnest(), statement_in_loopnest_p, strdup(), string_undefined_p, SUCCESSOR, successor_arc_label, successor_vertex, test_statement_of_reference, vect_chg_sgn(), vect_copy(), vect_rm(), VERTEX, vertex_successors, and vertex_to_statement().

Here is the call graph for this function:

print_vect_in_vertice_val()

void print_vect_in_vertice_val	(	FILE *	fd,
		Pvecteur	v,
		Pbase	b
	)

Parameters

fd

d

Definition at line 959 of file util.c.

{
    fprintf(fd,"(");
    for(; b!=NULL; b=b->succ) {
        fprint_string_Value(fd, " ",vect_coeff(b->var,v));
        if(b->succ !=NULL)
            fprintf(fd,",");
    }
    fprintf(fd," )");
}

References prettyprint_dot_context::fd, fprint_string_Value(), fprintf(), Svecteur::succ, Svecteur::var, and vect_coeff().

Referenced by print_dependence_cone().

Here is the call graph for this function:

Here is the caller graph for this function:

print_whole_dependence_graph()

bool print_whole_dependence_graph

(

const string

mod_name

)

prettyprint.c

prettyprint.c

Parameters

mod_name

od_name

Definition at line 34 of file prettyprint.c.

{
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_PRIVATIZED_DEPS",
                      false);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITHOUT_NOLOOPCARRIED_DEPS",
                      false);
    set_bool_property("PRINT_DEPENDENCE_GRAPH_WITH_DEPENDENCE_CONES",
                      true);
    return print_dependence_graph(mod_name);
}

References print_dependence_graph(), and set_bool_property().

Here is the call graph for this function:

quick_privatize_graph()

void quick_privatize_graph

(

graph

dep_graph

)

quick_privatize.c

we analyze arcs exiting from loop statements

Parameters

dep_graph

ep_graph

Definition at line 38 of file quick_privatize.c.

                                            {
  /* we analyze arcs exiting from loop statements */
  FOREACH (VERTEX, v1, graph_vertices(dep_graph)) {
    statement s1 = vertex_to_statement(v1);
    list successors = vertex_successors(v1);
    if(statement_loop_p(s1)) {
      loop l = statement_loop(s1);
      list locals = loop_locals(l);
      entity ind = loop_index(l);
 
      if(gen_find_eq(ind, locals) == entity_undefined) {
        if(// entity_privatizable_in_loop_p(ind, l) && /* to be restored when global variables are uniformly treated everywhere. BC.*/
           quick_privatize_loop(s1, successors)) {
          pips_debug(1, "Index for loop %" PRIdPTR " privatized\n",
              statement_number(s1));
          loop_locals(l) = CONS(ENTITY, ind, locals);
        } else {
          pips_debug(1, "could not privatize loop %" PRIdPTR "\n",
              statement_number(s1));
        }
      }
    }
  }
}

References CONS, dep_graph, ENTITY, entity_undefined, FOREACH, gen_find_eq(), graph_vertices, loop_index, loop_locals, pips_debug, quick_privatize_loop(), s1, statement_loop(), statement_loop_p(), statement_number, successors(), VERTEX, vertex_successors, and vertex_to_statement().

Referenced by compute_dg_on_statement_from_chains_in_place(), and rice_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_context_map()

void reset_context_map

(

void

)

Referenced by rice_update_dependence_graph().

Here is the caller graph for this function:

ResetLoopCounter()

void ResetLoopCounter

(

void

)

Definition at line 329 of file testdep_util.c.

                        {
  ilc = 0;
}

References ilc.

Referenced by rice_dependence_graph().

Here is the caller graph for this function:

rice_fast_dependence_graph()

bool rice_fast_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 139 of file ricedg.c.

                                                {
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}

References DG_FAST, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

rice_full_dependence_graph()

bool rice_full_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 144 of file ricedg.c.

                                                {
  dg_type = DG_FULL;
  return rice_dependence_graph(mod_name);
}

References DG_FULL, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

rice_regions_dependence_graph()

bool rice_regions_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 154 of file ricedg.c.

                                                   {
  if(!same_string_p(rule_phase(find_rule_by_resource("CHAINS")),
      "REGION_CHAINS"))
    pips_user_warning("Region chains not selected - using effects instead\n");
 
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}

References DG_FAST, dg_type, find_rule_by_resource(), pips_user_warning, rice_dependence_graph(), rule_phase, and same_string_p.

Here is the call graph for this function:

rice_semantics_dependence_graph()

bool rice_semantics_dependence_graph

(

char *

mod_name

)

Parameters

mod_name

od_name

Definition at line 149 of file ricedg.c.

                                                     {
  dg_type = DG_SEMANTICS;
  return rice_dependence_graph(mod_name);
}

References DG_SEMANTICS, dg_type, and rice_dependence_graph().

Here is the call graph for this function:

sc_add_di()

void sc_add_di	(	int	l,
		entity	e,
		Psysteme	s,
		int	li
	)

Parameters

li

i

Definition at line 209 of file testdep_util.c.

                                    {
  Variable v = (Variable)GetDiVar(l);
  Value vli = int_to_value(li);
  Pcontrainte pc;
 
  for (pc = s->egalites; pc != NULL; pc = pc->succ) {
    Value ve = vect_coeff((Variable)e, pc->vecteur);
    value_product(ve, vli);
    vect_add_elem(&(pc->vecteur), v, ve);
  }
 
  for (pc = s->inegalites; pc != NULL; pc = pc->succ) {
    Value ve = vect_coeff((Variable)e, pc->vecteur);
    value_product(ve, vli);
    vect_add_elem(&(pc->vecteur), v, ve);
  }
}

References Ssysteme::egalites, GetDiVar(), Ssysteme::inegalites, int_to_value, Scontrainte::succ, value_product, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.

Referenced by build_and_test_dependence_context().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_add_dsi()

void sc_add_dsi	(	int	l,
		entity	e,
		Psysteme	s
	)

Definition at line 238 of file testdep_util.c.

                             {
  Variable v = (Variable)GetDsiVar(l);
  Pcontrainte pc;
  for (pc = s->egalites; pc != NULL; pc = pc->succ) {
    vect_add_elem(&(pc->vecteur), v, vect_coeff((Variable)e, pc->vecteur));
  }
 
  for (pc = s->inegalites; pc != NULL; pc = pc->succ) {
    vect_add_elem(&(pc->vecteur), v, vect_coeff((Variable)e, pc->vecteur));
  }
}

References Ssysteme::egalites, GetDsiVar(), Ssysteme::inegalites, Scontrainte::succ, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.

Referenced by build_and_test_dependence_context().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_faisabilite_optim()

bool sc_faisabilite_optim

(

Psysteme

sc

)

bool sc_faisabilite_optim (Psysteme sc) :

Test system sc feasibility by successive projections along all variables in its basis.

carry out the projection with function sc_projection_optim_along_vecteur().

sc_normalize() is called here before the projection, which means that sc may be deallocated

result :

boolean : true if system is faisable false else

Modification:

• call to sc_rm() added when sc_projection_optim_along_vecteur_ofl() returns sc_empty; necessary to have a consistent interface: when FALSE is returned, sc always has been freed.

Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation

Parameters

sc

c

Definition at line 484 of file testdep_util.c.

               {
  debug(6, "sc_faisabilite_optim", "begin\n");
  sc = sc_normalize(sc);
  if(!sc_empty_p(sc)) {
    /* Automatic variables read in a CATCH block need to be declared volatile as
     * specified by the documentation*/
    Psysteme volatile sc1 = sc_dup(sc);
    is_test_Di = false;
 
    CATCH(overflow_error) {
      pips_debug(7, "overflow error, returning TRUE. \n");
      sc_rm(sc1);
      debug(6, "sc_faisabilite_optim", "end\n");
      return (true);
 
    } TRY {
      Pbase base_sc1 = base_dup(sc1->base);
      sc1 = sc_projection_optim_along_vecteur_ofl(sc1, base_sc1);
      base_rm(base_sc1);
      if(sc_empty_p(sc1)) {
        debug(7, "sc_faisabilite_optim", "system not feasible\n");
        debug(6, "sc_faisabilite_optim", "end\n");
        sc_rm(sc);
        UNCATCH(overflow_error);
        return (false);
      } else {
        sc_rm(sc1);
        debug(7, "sc_faisabilite_optim", "system feasible\n");
        debug(6, "sc_faisabilite_optim", "end\n");
        UNCATCH(overflow_error);
        return (true);
      }
    }
  } else {
    debug(7, "sc_faisabilite_optim", "normalized system not feasible\n");
    debug(6, "sc_faisabilite_optim", "end\n");
    sc_rm(sc);
    return (false);
  }
}

References Ssysteme::base, base_dup(), base_rm, CATCH, debug(), is_test_Di, overflow_error, pips_debug, sc_dup(), sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), TRY, and UNCATCH.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_invers()

Psysteme sc_invers

(

Psysteme

ps

)

Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial.

pour chaque element b dans le base initial, remplace b par -b dans le systeme initial.

Parameters

ps

s

Definition at line 1060 of file testdep_util.c.

               {
  Pbase b;
  Pcontrainte eq;
  Variable v;
 
  for (b = ps->base; !VECTEUR_NUL_P(b); b = b->succ) {
    v = vecteur_var(b);
    for (eq = ps->egalites; eq != NULL; eq = eq->succ)
      vect_chg_var_sign(&eq->vecteur, v);
    
    for (eq = ps->inegalites; eq != NULL; eq = eq->succ)
      vect_chg_var_sign(&eq->vecteur, v);
  }
  return (ps);
}

References eq, Scontrainte::succ, Svecteur::succ, vect_chg_var_sign(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_minmax_of_variable_optim()

bool sc_minmax_of_variable_optim	(	Psysteme volatile	ps,
		Variable	var,
		Value *	pmin,
		Value *	pmax
	)

void sc_minmax_of_variable_optim(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin.

la procedure retourne la valeur false si le systeme est infaisable et true sinon

le systeme ps est detruit.

projection sur toutes les variables sauf var

cette contrainte nous donne une borne max

cette contrainte nous donne une borne min

Parameters

ps	s
var	ar
pmin	min
pmax	max

Definition at line 975 of file testdep_util.c.

                                                        {
  Value val;
  Pcontrainte pc;
  Pbase b;
  Pvecteur pv = NULL;
 
  *pmax = VALUE_MAX;
  *pmin = VALUE_MIN;
 
  if(sc_value_of_variable(ps, var, &val) == true) {
    *pmin = val;
    *pmax = val;
    return true;
  }
 
  /* projection sur toutes les variables sauf var */
  for (b = ps->base; !VECTEUR_NUL_P(b); b = b->succ) {
    Variable v = vecteur_var(b);
    if(v != var) {
      vect_add_elem(&pv, v, 1);
    }
  }
 
  CATCH(overflow_error) {
    debug(6,
          "sc_minmax_of_variable_optim",
          " overflow error, returning INT_MAX and INT_MIN. \n");
    *pmax = INT_MAX;
    *pmin = INT_MIN;
  } TRY {
 
    ps = sc_projection_optim_along_vecteur_ofl(ps, pv);
    if(sc_empty_p(ps)) {
      sc_rm(ps);
      UNCATCH(overflow_error);
      return false;
    }
    if(sc_empty_p(ps = sc_normalize(ps))) {
      sc_rm(ps);
      UNCATCH(overflow_error);
      return false;
    }
 
    if(sc_value_of_variable(ps, var, &val) == true) {
      *pmin = val;
      *pmax = val;
      UNCATCH(overflow_error);
      return true;
    }
 
    for (pc = ps->inegalites; pc != NULL; pc = pc->succ) {
      Value cv = vect_coeff(var, pc->vecteur);
      Value cc = value_uminus(vect_coeff(TCST, pc->vecteur));
 
      if(value_pos_p(cv)) {
        /* cette contrainte nous donne une borne max */
        Value bs = value_pdiv(cc,cv);
        if(value_lt(bs,*pmax))
          *pmax = bs;
      } else if(value_neg_p(cv)) {
        /* cette contrainte nous donne une borne min */
        Value bi = value_pdiv(cc,cv);
        if(value_gt(bi,*pmin))
          *pmin = bi;
      }
    }
 
    UNCATCH(overflow_error);
    vect_rm(pv);
  }
 
  if(value_lt(*pmax,*pmin))
    return false;
 
  sc_rm(ps);
 
  return true;
}

References CATCH, debug(), overflow_error, sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), sc_value_of_variable(), Scontrainte::succ, Svecteur::succ, TCST, TRY, UNCATCH, value_gt, value_lt, VALUE_MAX, VALUE_MIN, value_neg_p, value_pdiv, value_pos_p, value_uminus, vect_add_elem(), vect_coeff(), vect_rm(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDiVariables().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_proj_on_di()

int sc_proj_on_di	(	int	cl,
		Psysteme	s
	)

Parameters

cl

l

Definition at line 267 of file testdep_util.c.

                     {
  Pbase coord;
 
  for (coord = s->base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
    Variable v = vecteur_var(coord);
    int l = DiVarLevel((entity)v);
    
    if(l <= 0 || l > cl) {
      debug(8,
            "ProjectOnDi",
            "projection sur %s\n",
            entity_local_name((entity)v));
      if(SC_EMPTY_P(s = sc_projection_pure(s, v))) {
        debug(8, "ProjectOnDi", "infaisable\n");
        return (false);
      }
      debug(8, "ProjectOnDi", "faisable\n");
    }
  }
 
  return (true);
}

References Ssysteme::base, debug(), DiVarLevel(), entity_local_name(), Svecteur::succ, VECTEUR_NUL_P, and vecteur_var.

Here is the call graph for this function:

sc_proj_optim_on_di_ofl()

int sc_proj_optim_on_di_ofl	(	int	cl,
		Psysteme *	psc
	)

int sc_proj_optim_on_di_ofl(cl, sc)

This function projects a system onto a set of di variables. This set is defined by cl, the common nesting level of the two array references being tested: only di variables whose nesting level is less than or equal to cl are kept in the projected system (i.e. outermost loops).

The projection is performed by first eliminating variables in the equations. Variables whose coefficients are 1 or -1 are considered first. (in such case it's integer elimination). Remaining inequalities are projected by Fourier-Motzkin elimination.

cl is the common nesting level. sc is the system to project. sc is modified but psc always points to a consistent Psysteme on return (i.e. it's up to the caller to free it). *psc on return is sc_empty() if *psc on entry turns out to be non-feasible. a long jump buffer must have been initialized to handle overflows The value returned is true if the system is feasible, false otherwise.

find the set of variables to be eliminated

find one

Parameters

cl	l
psc	sc

Definition at line 415 of file testdep_util.c.

{
  Pbase coord;
  Pvecteur pv = VECTEUR_NUL;
  Variable v;
  int l;
  int res;
 
  pips_debug(6, "begin\n");
 
  /* find the set of variables to be eliminated */
  for (coord = (*psc)->base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
    v = vecteur_var(coord);
    l = DiVarLevel((entity)v);
    
    if(l <= 0 || l > cl) /* find one */
      vect_add_elem(&pv, v, 1);
  }
 
  ifdebug(6) {
    fprintf(stderr, "The list of variables to be eliminated is :\n");
    vect_debug(pv);
  }
  is_test_Di = true;
 
  pips_assert("Dependence system *psc is consistent before projection",
              sc_consistent_p(*psc));
 
  *psc = sc_projection_optim_along_vecteur_ofl(*psc, pv);
 
  pips_assert("Dependence system *psc is consistent after projection",
              sc_consistent_p(*psc));
 
  if(sc_empty_p(*psc))
    res = false;
  else
    res = true;
 
 
  vect_rm(pv);
 
 
  pips_assert("Dependence system *psc is consistent after empty test",
              sc_consistent_p(*psc));
  pips_debug(6, "end\n");
 
  return res;
}

References DiVarLevel(), fprintf(), ifdebug, is_test_Di, pips_assert, pips_debug, sc_consistent_p(), sc_empty_p(), sc_projection_optim_along_vecteur_ofl(), Svecteur::succ, vect_add_elem(), vect_debug(), vect_rm(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.

Referenced by TestDependence().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_projection_optim_along_vecteur_ofl()

Psysteme sc_projection_optim_along_vecteur_ofl	(	Psysteme	sc,
		Pvecteur	pv
	)

Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv)

This fonction returns the projected system resulting of the SUCCESSIVE projections of the system sc along the variables contained in vecteur pv. Variables are only more or less projected according to their order in pv.

The projection is done first by eliminating variables constrained by equations. The variables whose coefficients are 1 (or -1?) are considered first (in such case it is a valide integer elimination), then variables appearing in equations with non unit coefficient, and finally all left over variables in pv using Fourier-Motzkin elimination. At each step, the order in pv is used.

If the system sc is not faisable, SC_EMPTY is returned.

FI: this function could be moved to linear... but for the debugging stuff. Also, it could be broken into three parts. And the number of return statements should be reduced to one.

The elimination of variables using equations

First,carry out the integer elimination possible

coeff == 1, do this integer elimination for variable v with the others contrainte(equations and inequations

remove v from the list of variables to be projected pve

it's in head

carry out the non-exact elimination if necessary and possible using other equations

find a variable which appears in the equations, eliminate it

liminate v in the list of variables pve

it's in head

carry out the elimination using Fourier-Motzkin for the other variables

detection of non feasability of Psysteme sc

sc->inegalites = contrainte_sort(sc->inegalites, sc->base, BASE_NULLE,

true, false);

ifdebug(8) {

debug(8, "", "Sorted system :\n");

sc_syst_debug(sc);

}

Are we done? This used to be always true, but sc_normalize() may promote inequalities as equations. Since the projection steps may reveal some implicit equations, we are not sure here that all projections have been performed by the three steps (equations, equations, inequalities).

See for instance the test dependence in SAC/sgemm for such an example.

Update the base and the dimension of the constraint system sc

Clean up auxiliary data structures

Parameters

sc	c
pv	v

Definition at line 648 of file testdep_util.c.

{
  Pcontrainte eq;
  Pvecteur pv1, prv, pve;
  Variable v;
  Value coeff;
  int syst_size_init;
  Pbase base_sc = base_dup(sc->base);
  Pbase lb = BASE_NULLE;
 
  pips_assert("The input constraint system is consistent", sc_consistent_p(sc));
  ifdebug(7) {
    pips_debug(7, "All variables to project: ");
    vect_dump(pv);
  }
 
  pve = vect_dup(pv);
  Pvecteur pve_to_free = pve;
 
  do {
    /* The elimination of variables using  equations */
    if(pve != NULL && sc->nb_eq != 0) {
 
      /* First,carry out the integer elimination possible */
      pips_debug(7, "carry out the integer elimination by equation:\n");
 
      prv = NULL;
      pv1 = pve;
      while(!VECTEUR_NUL_P(pv1) && (sc->nb_eq != 0)) {
        v = pv1->var;
        eq = contrainte_var_min_coeff(sc->egalites, v, &coeff, false);
        if((eq == NULL) || value_notone_p(coeff)) {
          prv = pv1;
          pv1 = pv1->succ;
        } else {
          ifdebug(7) {
            fprintf(stderr, "eliminate %s by :", entity_local_name((entity)v));
            egalite_debug(eq);
          }
          /* coeff == 1, do this integer elimination for variable
           * v with the others contrainte(equations and inequations */
          sc = sc_variable_substitution_with_eq_ofl_ctrl(sc, eq, v, FWD_OFL_CTRL);
 
          if(sc_empty_p(sc)) {
            if(is_test_Di)
              NbrTestProjEqDi++;
            else
              NbrTestProjEq++;
            pips_debug(7, "projection infaisable\n");
            for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
              v = pv1->var;
              sc_base_remove_variable(sc, v);
            }
            base_rm(base_sc);
            vect_rm(pve_to_free);
 
            pips_debug(7, "Return 1: empty\n");
            return (sc);
          }
          sc = sc_normalize(sc);
 
          if(sc_empty_p(sc)) { // FI: another normalization step is going to occur here
            if(is_test_Di)
              NbrTestProjEqDi++;
            else
              NbrTestProjEq++;
            pips_debug(7, "normalisation infaisable\n");
 
            for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
              v = pv1->var;
              sc_base_remove_variable(sc, v);
            }
 
            vect_rm(pve_to_free);
 
            pips_debug(7, "Return 2: empty\n");
            return (sc);
 
          }
 
          // The removal is delayed till the end of the function. sc is
          // still consistent. However, too many variables might be left if an
          // intermediate return occurs
          // sc_base_remove_variable(sc, v);
        
          ifdebug(7) {
            fprintf(stderr, "projected normalised system is:\n");
            sc_syst_debug(sc);
          }
 
          /* remove v from the list of variables to be projected pve */
          if(prv == NULL) /* it's in head */
            pve = pv1 = pv1->succ;
          else {
            prv->succ = pv1->succ;
            free(pv1);
            pv1 = prv->succ;
          }
        }
      }
    }
 
    pips_assert("sc is consistent after the first use of equations",
                sc_consistent_p(sc));
    ifdebug(7) {
      pips_debug(7, "Variables left to project after the first step: ");
      vect_dump(pv);
    }
 
    /* carry out the non-exact elimination if necessary and possible
       using other equations */
    if(pve != NULL && sc->egalites != NULL) {
      pips_debug(7, "carry out the non integer elimination by equation:\n");
      pv1 = pve;
      prv = NULL;
      while((sc->egalites != 0) && (pv1 != NULL)) {
        v = pv1->var;
        eq = contrainte_var_min_coeff(sc->egalites, v, &coeff, true);
        if(eq == NULL && pv1 != NULL) {
          prv = pv1;
          pv1 = pv1->succ;
        } else {
          if(eq != NULL) {
            /* find a variable which appears in the equations, eliminate it*/
            ifdebug(7) {
              fprintf(stderr, "eliminate %s by :", entity_local_name((entity)v));
              egalite_debug(eq);
            }
            if(is_test_inexact_eq == false)
              is_test_inexact_eq = true;
            if(is_test_exact)
              is_test_exact = false;
 
            sc = sc_variable_substitution_with_eq_ofl_ctrl(sc,
                                                           eq,
                                                           v,
                                                           FWD_OFL_CTRL);
            if(sc_empty_p(sc)) {
              if(is_test_Di)
                NbrTestProjEqDi++;
              else
                NbrTestProjEq++;
              pips_debug(7, "projection-infaisable\n");
 
              for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
                v = pv1->var;
                sc_base_remove_variable(sc, v);
              }
              base_rm(base_sc);
              vect_rm(pve_to_free);
 
              pips_debug(7, "Return 3: empty\n");
              return sc;
            }
 
            sc = sc_normalize(sc);
 
            if(sc_empty_p(sc)) { // FI: should be sc_is_empty_p... or
              // the normalization is repeated...
              pips_debug(7, "normalization detects a non-feasible constraint system\n");
              if(is_test_Di)
                NbrTestProjEqDi++;
              else
                NbrTestProjEq++;
 
              for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
                v = pv1->var;
                sc_base_remove_variable(sc, v);
              }
 
              vect_rm(pve_to_free);
 
              pips_debug(7, "Return 4: empty\n");
              return sc;
            }
 
            // FI: the removal is delayed to end of this function, but
            // sc is nevertheless consistent
            // sc_base_remove_variable(sc, v);
            ifdebug(7) {
              fprintf(stderr, "projected normalised system is:\n");
              sc_syst_debug(sc);
            }
            /*eliminate v in the list of variables pve*/
            if(prv == NULL) /* it's in head */
              pve = pv1 = pv1->succ;
            else
              prv->succ = pv1 = pv1->succ;
          }
        }
      }
    }
 
    pips_assert("sc is consistent after the second use of equations",
                sc_consistent_p(sc));
    ifdebug(7) {
      pips_debug(7, "Variables left to project with Fourier-Motzkin: ");
      vect_dump(pve);
    }
 
    /* carry out the elimination using Fourier-Motzkin for the other variables */
 
    if(pve != NULL) {
      pv1 = pve;
 
      while(pv1 != NULL) {
 
        NbrProjFMTotal++;
        syst_size_init = nb_elems_list(sc->inegalites);
        v = pv1->var;
 
        ifdebug(7) {
          fprintf(stderr, "eliminate %s by F-M\n", entity_local_name((entity)v));
          pips_debug(7, "is_test_exact before: ");
          if(is_test_exact)
            fprintf(stderr, "%s\n", "exact");
          else
            fprintf(stderr, "%s\n", "not exact");
        }
 
        if(combiner_ofl_with_test(sc, v) == false) {
          /* detection of non feasability of Psysteme sc */
          if(is_test_Di)
            NbrTestProjFMDi++;
          else
            NbrTestProjFM++;
          sc_rm(sc);
          sc = sc_empty(base_sc);
          for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
            v = pv1->var;
            sc_base_remove_variable(sc, v);
          }
 
          vect_rm(pve_to_free);
 
          pips_debug(7, "Return 5: empty\n");
          return sc;
        }
 
        sc = sc_normalize(sc);
 
        if(sc_empty_p(sc)) {
          if(is_test_Di)
            NbrTestProjFMDi++;
          else
            NbrTestProjFM++;
          pips_debug(7, "normalisation-infaisable\n");
          for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
            v = pv1->var;
            sc_base_remove_variable(sc, v);
          }
 
          vect_rm(pve_to_free);
 
          pips_debug(7, "Return 6: empty\n");
          return sc;
        }
 
        /*          sc->inegalites = contrainte_sort(sc->inegalites, sc->base, BASE_NULLE, */
        /*                                           true, false); */
 
        /*          ifdebug(8) { */
        /*              debug(8, "", "Sorted system :\n"); */
        /*              sc_syst_debug(sc); */
        /*          } */
 
        build_sc_nredund_2pass_ofl_ctrl(&sc, FWD_OFL_CTRL);
 
        ifdebug(7) {
          pips_debug(7, "is_test_exact after: ");
          if(is_test_exact)
            fprintf(stderr, "%s\n", "exact");
          else
            fprintf(stderr, "%s\n", "not exact");
          fprintf(stderr, "projected normalised system is:\n");
          sc_syst_debug(sc);
        }
        if(nb_elems_list(sc->inegalites) <= syst_size_init)
          NbrFMSystNonAug++;
        pv1 = pv1->succ;
      }
    }
 
    pips_assert("sc is consistent before base update", sc);
 
    /* Are we done? This used to be always true, but sc_normalize()
       may promote inequalities as equations. Since the projection
       steps may reveal some implicit equations, we are not sure here
       that all projections have been performed by the three steps
       (equations, equations, inequalities).
 
       See for instance the test dependence in SAC/sgemm for such an example.
    */
    Pbase mb = sc_to_minimal_basis(sc);
    lb = base_intersection(mb, pv);
    vect_rm(mb);
    
  } while(!BASE_NULLE_P(lb)); // No need to free lb since it is empty
 
  /* Update the base and the dimension of the constraint system sc */
 
  sc->nb_ineq = nb_elems_list(sc->inegalites);
  for (pv1 = pv; pv1 != NULL; pv1 = pv1->succ) {
    v = pv1->var;
    sc_base_remove_variable(sc, v);
  }
 
  pips_assert("sc is consistent after base update", sc);
 
  /* Clean up auxiliary data structures */
  vect_rm(pve_to_free);
  base_rm(base_sc);
 
  pips_debug(7, "final return: faisable\n");
 
  return sc;
}

References Ssysteme::base, base_dup(), base_intersection(), BASE_NULLE, BASE_NULLE_P, base_rm, build_sc_nredund_2pass_ofl_ctrl(), combiner_ofl_with_test(), contrainte_var_min_coeff(), egalite_debug(), Ssysteme::egalites, entity_local_name(), eq, fprintf(), free(), FWD_OFL_CTRL, ifdebug, Ssysteme::inegalites, is_test_Di, is_test_exact, is_test_inexact_eq, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, NbrFMSystNonAug, NbrProjFMTotal, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, pips_assert, pips_debug, prv(), sc_base_remove_variable(), sc_consistent_p(), sc_empty(), sc_empty_p(), sc_normalize(), sc_rm(), sc_syst_debug(), sc_to_minimal_basis(), Svecteur::succ, value_notone_p, Svecteur::var, vect_dump(), vect_dup(), vect_rm(), and VECTEUR_NUL_P.

Referenced by sc_faisabilite_optim(), sc_minmax_of_variable_optim(), and sc_proj_optim_on_di_ofl().

Here is the call graph for this function:

Here is the caller graph for this function:

set_context_map()

void set_context_map

(

statement_mapping

)

Referenced by rice_update_dependence_graph().

Here is the caller graph for this function:

statement_context_undefined_p()

bool statement_context_undefined_p

(

statement

)

statements_to_successors()

hash_table statements_to_successors	(	list	statements,
		graph	dg
	)

creates a hash_table containing statements from statements as keys and their respective succesors according to dg as values

Parameters

statements	input statements
dg	dependecy graph

Returns

allocated hash_table with (statement,successors pairs)

Parameters

statements	tatements
dg	g

Definition at line 1018 of file util.c.

{
  hash_table successors = hash_table_make(hash_pointer, HASH_DEFAULT_SIZE);
  FOREACH(VERTEX,v,graph_vertices(dg))
  {
    statement s = vertex_to_statement(v);
    if( !statement_undefined_p(gen_find_eq(s,statements)))
    {
      list succ = vertex_successors(v);
      hash_put(successors,s,succ);
    }
  }
  return successors;
}

References dg, FOREACH, gen_find_eq(), graph_vertices, HASH_DEFAULT_SIZE, hash_pointer, hash_put(), hash_table_make(), statement_undefined_p, successors(), VERTEX, vertex_successors, and vertex_to_statement().

Referenced by fs_filter(), and if_conversion_compact_stats().

Here is the call graph for this function:

Here is the caller graph for this function:

store_statement_context()

void store_statement_context	(	statement	,
		Psysteme
	)

successor_sort_callback()

int successor_sort_callback	(	const successor *	succ1,
		const successor *	succ2
	)

This is a callback for qsort function, it compares two successor.

Returns

0 if these are equals, -1 if first is lower, 1 if second is lower

Parameters

succ1	ucc1
succ2	ucc2

Definition at line 116 of file util.c.

                                                                              {
  vertex v1 = successor_vertex(*succ1);
  vertex v2 = successor_vertex(*succ2);
  return vertex_sort_callback( &v1, &v2 );
}

References successor_vertex, and vertex_sort_callback().

Referenced by prettyprint_dependence_graph(), and xml_Chain_Graph().

Here is the call graph for this function:

Here is the caller graph for this function:

TestCoupleOfReferences()

list TestCoupleOfReferences	(	list	,
		Psysteme	,
		statement	,
		effect	,
		reference	,
		list	,
		Psysteme	,
		statement	,
		effect	,
		reference	,
		list	,
		Ptsg *	,
		list *	,
		Ptsg *
	)

union_list()

list union_list	(	list	l1,
		list	l2
	)

Union is not typed...

Parameters

l1	1
l2	2

Definition at line 376 of file impact_check.c.

                                  {
  list cl = list_undefined;
 
  for(cl=l2; !ENDP(cl); POP(cl)) {
    gen_chunk * gcp = CHUNK(CAR(cl));
        if(!gen_in_list_p(gcp , l1))
          l1 = gen_nconc(l1, gen_cons(gcp, NIL));
  }
 
  return l1;
}

References CAR, CHUNK, ENDP, gen_cons(), gen_in_list_p(), gen_nconc(), list_undefined, NIL, and POP.

Referenced by check_new_arc_for_structured_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

update_statement_context()

void update_statement_context	(	statement	,
		Psysteme
	)

vect_chg_var_sign()

void vect_chg_var_sign	(	Pvecteur *	ppv,
		Variable	var
	)

void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv

Parameters

ppv	pv
var	ar

Definition at line 1080 of file testdep_util.c.

                              {
  Pvecteur pvcour;
 
  for (pvcour = (*ppv); pvcour != NULL; pvcour = pvcour->succ)
    if(pvcour->var == var)
      value_oppose(pvcour->val);
 
  return;
}

References Svecteur::succ, Svecteur::val, value_oppose, and Svecteur::var.

Referenced by sc_invers().

Here is the caller graph for this function:

vertex_ordering()

int vertex_ordering

(

vertex

v

)

Definition at line 51 of file util.c.

{
  dg_vertex_label dvl = (dg_vertex_label) vertex_vertex_label(v);
  return dg_vertex_label_statement(dvl);
}

References dg_vertex_label_statement, and vertex_vertex_label.

Referenced by compare_vertex(), get_vertex_of_statement(), and init_statement_equivalence_table().

Here is the caller graph for this function:

vertex_sort_callback()

int vertex_sort_callback	(	const vertex *	v1,
		const vertex *	v2
	)

This is a callback for qsort function, it compares two vertex.

Returns

0 if these are equals, -1 if first is lower, 1 if second is lower

Parameters

v1	1
v2	2

Definition at line 105 of file util.c.

                                                               {
  statement s1 = vertex_to_statement( *v1 );
  statement s2 = vertex_to_statement( *v2 );
  return statement_number(s1) > statement_number(s2);
}

References s1, statement_number, and vertex_to_statement().

Referenced by prettyprint_dependence_graph(), successor_sort_callback(), and xml_Chain_Graph().

Here is the call graph for this function:

Here is the caller graph for this function:

vertex_to_statement()

statement vertex_to_statement

(

vertex

v

)

cproto-generated files

util.c

cproto-generated files

This information is kept in a static hash_table named OrderingToStatement. See ri-util/ordering.c for more information.

Definition at line 45 of file util.c.

{
  dg_vertex_label dvl = (dg_vertex_label) vertex_vertex_label(v);
  return(ordering_to_statement(dg_vertex_label_statement(dvl)));
}

Referenced by prettyprint_dependence_graph(), prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), statements_to_successors(), and vertex_sort_callback().

Here is the caller graph for this function:

writeresult()

void writeresult

(

char *

mod_name

)

to avoid warnings from compiler

Parameters

mod_name

od_name

Definition at line 2268 of file ricedg.c.

                                 {
  FILE *fp;
  string filename;
  int i, j;
 
  switch(dg_type) {
    case DG_FAST:
      filename = "resulttestfast";
      break;
    case DG_FULL:
      filename = "resulttestfull";
      break;
    case DG_SEMANTICS:
      filename = "resulttestseman";
      break;
    default:
      pips_internal_error("erroneous dg type.");
      return; /* to avoid warnings from compiler */
  }
 
  filename = strdup(concatenate(db_get_current_workspace_directory(),
                                "/",
                                mod_name,
                                ".",
                                filename,
                                0));
 
  fp = safe_fopen(filename, "w");
 
  fprintf(fp, "%s", mod_name);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d",
          NbrArrayDepInit,
          NbrIndepFind,
          NbrAllEquals,
          NbrDepCnst,
          NbrTestExact,
          NbrDepInexactEq,
          NbrDepInexactFM,
          NbrDepInexactEFM,
          NbrScalDep,
          NbrIndexDep);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", deptype[i][j]);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", constdep[i][j]);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d %d",
          NbrTestCnst,
          NbrTestGcd,
          NbrTestSimple,
          NbrTestDiCnst,
          NbrTestProjEqDi,
          NbrTestProjFMDi,
          NbrTestProjEq,
          NbrTestProjFM,
          NbrTestDiVar,
          NbrProjFMTotal,
          NbrFMSystNonAug);
  for (i = 0; i < 18; i++)
    fprintf(fp, " %d", FMComp[i]);
  fprintf(fp, "\n");
 
  safe_fclose(fp, filename);
  free(filename);
}

References concatenate(), constdep, db_get_current_workspace_directory(), deptype, DG_FAST, DG_FULL, DG_SEMANTICS, dg_type, FMComp, fprintf(), free(), NbrAllEquals, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, NbrFMSystNonAug, NbrIndepFind, NbrIndexDep, NbrProjFMTotal, NbrScalDep, NbrTestCnst, NbrTestDiCnst, NbrTestDiVar, NbrTestExact, NbrTestGcd, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, NbrTestSimple, pips_internal_error, safe_fclose(), safe_fopen(), and strdup().

Referenced by rice_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

constdep

int constdep[5][3]

Definition at line 52 of file ricedg.h.

deptype

int deptype[5][3]

extern

Definition at line 141 of file ricedg.h.

Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

DiVars

entity DiVars[9]

extern

testdep_util.c

testdep_util.c

di variables are pseudo variables created by PIPS and not accessible to the user that represent the distance between two dependent statement iterations. the sign of this distance is sufficient for Kennedy's way of parallelizing programs, but the exact value migth be of interest for other algorithms such as systolic algorithms.

Written by Remi, Yi-Qing; reorganized by Yi-Qing (18/09/91) To deal with overflow errors occuring during the projection of a Psysteme along a variable The tables of di variables, li variables and ds variables.

Variable DiVars[i-1] or LiVars[i-1] is associated to the loop at nesting level i. A di variable represents the difference in iteration number between the two references considered.

The variable DsiVars[i] is associated to the ith element in the list of scalar variables modified in the loops

Definition at line 53 of file testdep_util.c.

Referenced by DiVarLevel(), and GetDiVar().

DsiVars

entity DsiVars[1024]

extern

Definition at line 55 of file testdep_util.c.

Referenced by GetDsiVar().

Finds2s1

bool Finds2s1

extern

Definition at line 160 of file ricedg.h.

Referenced by rice_update_dependence_graph(), TestCoupleOfReferences(), and TestDependence().

FMComp

int FMComp[18]

extern

Definition at line 154 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

is_dep_cnst

bool is_dep_cnst

extern

Definition at line 158 of file ricedg.h.

Referenced by TestCoupleOfReferences(), and TestDependence().

is_test_Di

bool is_test_Di

extern

Definition at line 159 of file ricedg.h.

is_test_exact

bool is_test_exact

extern

or counting the number of F-M complexity less than 16.

The complexity of one projection by F-M is multiply of the nbr. of inequations positive and the nbr. of inequations negatives who containe the variable eliminated.The last elem of the array (ie FMComp[17]) is used to count cases with complexity over 16

Definition at line 155 of file ricedg.h.

Referenced by TestCoupleOfReferences(), and TestDependence().

is_test_inexact_eq

bool is_test_inexact_eq

extern

Definition at line 156 of file ricedg.h.

Referenced by TestCoupleOfReferences(), and TestDependence().

is_test_inexact_fm

bool is_test_inexact_fm

extern

Definition at line 157 of file ricedg.h.

Referenced by TestCoupleOfReferences(), and TestDependence().

LiVars

entity LiVars[9]

extern

Definition at line 54 of file testdep_util.c.

Referenced by GetLiVar().

NbrAllEquals

int NbrAllEquals

extern

Definition at line 133 of file ricedg.h.

Referenced by rice_dependence_graph(), TestDependence(), TestDiCnst(), and writeresult().

NbrArrayDepInit

int NbrArrayDepInit

extern

he variables for the statistics of test of dependence and parallelization

ricedg.c

he variables for the statistics of test of dependence and parallelization

Remi Triolet, Yi-qing Yang

Modifications:

• new option to use semantics analysis results (Francois Irigoin, 12 April 1991)
• compute the dependence cone, the statistics. (Yi-Qing, August 1991)
• updated using DEFINE_CURRENT_MAPPING, BA, September 3, 1993
• dg_type introduced to replace dg_fast and dg_semantics; it is more general. (BC, August 1995).
• TestDependence split into different procedures for more readability. (BC, August 1995).
• creation of quick_privatize.c and prettyprint.c to reduce the size of ricedg.c (FI, Oct. 1995)

Notes:

• Many values seem to be assigned to StatementToContext and never be freed; local variables he variables for the statistics of test of dependence and parallelization they should not be global ? FC.

Definition at line 131 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepCnst

int NbrDepCnst

extern

Definition at line 134 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepExact

int NbrDepExact

extern

NbrDepInexactEFM

int NbrDepInexactEFM

extern

Definition at line 138 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepInexactEq

int NbrDepInexactEq

extern

Definition at line 136 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrDepInexactFM

int NbrDepInexactFM

extern

Definition at line 137 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrFMSystNonAug

int NbrFMSystNonAug

extern

Definition at line 153 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrIndepFind

int NbrIndepFind

extern

Definition at line 132 of file ricedg.h.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrIndexDep

int NbrIndexDep

extern

Definition at line 140 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrProjFMTotal

int NbrProjFMTotal

extern

Definition at line 152 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrScalDep

int NbrScalDep

extern

Definition at line 139 of file ricedg.h.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrTestCnst

int NbrTestCnst

extern

Definition at line 143 of file ricedg.h.

Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().

NbrTestDiCnst

int NbrTestDiCnst

extern

by sc_normalize()

Definition at line 146 of file ricedg.h.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrTestDiVar

int NbrTestDiVar

extern

Definition at line 151 of file ricedg.h.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().

NbrTestExact

int NbrTestExact

extern

Definition at line 68 of file ricedg.c.

Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().

NbrTestGcd

int NbrTestGcd

extern

Definition at line 144 of file ricedg.h.

Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().

NbrTestProjEq

int NbrTestProjEq

extern

Definition at line 149 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrTestProjEqDi

int NbrTestProjEqDi

extern

Definition at line 147 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrTestProjFM

int NbrTestProjFM

extern

Definition at line 150 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrTestProjFMDi

int NbrTestProjFMDi

extern

Definition at line 148 of file ricedg.h.

Referenced by rice_dependence_graph(), and writeresult().

NbrTestSimple

int NbrTestSimple

extern

Definition at line 145 of file ricedg.h.

Referenced by rice_dependence_graph(), TestDependence(), and writeresult().