array_dfg.c File Reference

#include "local.h"

Include dependency graph for array_dfg.c:

Go to the source code of this file.

Macros
#define	GRAPH_IS_DFG
	Name : array_dfg.c Package : array_dfg Author : Arnauld LESERVOT Date : 93/06/27 Modified : Documents: Platonoff's thesis and Leservot's thesis "Dataflow Analysis of Array and Scalar References" P. More...
#define	NEXT(cp)   (((cp) == NIL) ? NIL : (cp)->cdr)
	Local defines. More...

Functions
bool	my_sc_faisabilite (Psysteme in_ps)
graph	adg_dataflowgraph (statement mod_stat, statement_mapping stco_map, graph dup_dg)
	====================================================================== More...
boolean	array_dfg (char *mod_name)
	====================================================================== More...

Variables
hash_table	Gvertex_number_to_statement
	Global variables. More...
int	Gcount_re
	External variables. More...
int	Gcount_ie
statement_mapping	Gstco_map
list	Gstructural_parameters
int	my_pip_count
int	my_fai_count
static hash_table	Gforward_substitute_table

Macro Definition Documentation

GRAPH_IS_DFG

#define GRAPH_IS_DFG

Name : array_dfg.c Package : array_dfg Author : Arnauld LESERVOT Date : 93/06/27 Modified : Documents: Platonoff's thesis and Leservot's thesis "Dataflow Analysis of Array and Scalar References" P.

FEAUTRIER Comments :

Definition at line 37 of file array_dfg.c.

NEXT

#define NEXT

(

cp

)

(((cp) == NIL) ? NIL : (cp)->cdr)

Local defines.

Definition at line 41 of file array_dfg.c.

Function Documentation

adg_dataflowgraph()

graph adg_dataflowgraph	(	statement	mod_stat,
		statement_mapping	stco_map,
		graph	dup_dg
	)

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

graph adg_dataflowgraph( (statement) module_statement, (statement_mapping) static_control_map, (graph) reversed_dg ) AL 93/07/01 To compute the Array Data Flow Graph, we need : code, static_control, dependance_graph.

Return dfg graph

Return list of vertices

Initialization to have an entry node

We first put entry node in the return list

We run over each vertex of the input graph

Get destination vertex and information linked to it

We search for all the read effects of vertex dest_ver and try to find the source for each read effect in dest_ver.

For debug purpose

Get the current read_effect of destination

For debug purpose

Search for successors (in fact predecessors : input graph is reversed compared to dg graph !) that write the dest_read_eff and put their vertices in sou_l. Then, order them by decreasing order of stat. number.

No sources : Comes from Entry point

Debugging

Build the source leaf label list sou_lll. This list of leaf labels links a vertex number and a depth.

Explode candidates for each depth and then, build the candidate list cand_l by decreasing order.

we will reuse it after

We run over all possible candidates and compute to see how it could contribute to the source

Get possible source vertex and informations linked to it

If this candidate is not possible, see the next. Two cases : candidate and destination are in the same deepest loop and dest is before candidate ; or candidate is not valid with the present source.

Not a possible source => get the next candidate

will be reuse ?

For debug purpose

Get the f(u) = g(b) psystem We first duplicate arguments expressions, then we rename entities that are at a deeper depth than sou_d and forward subsitute those new entities in the expressions

Rename entities at rank > sou_d and update Gforward_substitute_table

Make corresponding indices equal in source and dest F(u) = g(b) and put it in sou_ps.

Build the sequencing predicate

compute indice1 + indice2 + 1

append at the end p.s. of source to those of dest. Concatenate the three lists to build Psys. according to the order : source-variables,sink-variables,struc.params

Build source Psysteme (IF and DO contraints). Build the context and rename variables .

Get predicate that comes from an IF statement

Get predicate that comes from enclosing DO

Rename entities in the source context system

Append sous_ps (F(u) = g(b) and seq. predicate) with prov_ps (IF and DO constraints).

Compute the new candidate source. We try to call PIP only if necesary.

If there is no condition on source...

Order the psysteme according to ent_l

Find the new source and simplify it

Fill "quast_undefined" part of the source with ENTRY node.

Build the new Data Flow Graph with the new source

Definition at line 70 of file array_dfg.c.

{
  graph   ret_graph = graph_undefined; /* Return dfg graph */
  list    ret_verl = NIL;               /* Return list of vertices */
  list    dest_ver_l = NIL;
  vertex  entry_v = NULL;
  quast   entry_q = NULL;
 
  debug(1, "adg_dataflowgraph", "begin \n");
 
  /* Initialization to have an entry node */
  /* We first put entry node in the return list */
  entry_v = make_vertex(make_dfg_vertex_label(ENTRY_ORDER, 
                                             predicate_undefined,
                                             sccflags_undefined), NIL);
  ADD_ELEMENT_TO_LIST( ret_verl, VERTEX, entry_v );
  entry_q = make_quast( make_quast_value(is_quast_value_quast_leaf,
                                         make_quast_leaf( NIL, make_leaf_label(ENTRY_ORDER, 0) )),
                       NIL );
 
  hash_put( Gvertex_number_to_statement, (char *) ENTRY_ORDER, (char *)
           ENTRY_ORDER );
 
 
  /* We run over each vertex of the input graph */
  for(dest_ver_l = graph_vertices( dup_dg );!ENDP(dest_ver_l);POP(dest_ver_l)) {
    vertex           ret_dest_ver = NULL, dest_ver = NULL;
    list             dest_succ = NIL, dest_loops = NIL; 
    list             dest_readl = NIL, dest_psl = NIL, dest_lcl = NIL;
    list             dest_args = NIL, prov_l = NIL;
    predicate        dest_pred = NULL;
    Psysteme         dest_test_context = NULL, dest_loop_context = NULL;
    Psysteme         dest_context = NULL;
    static_control   dest_stco;
    int              dest_nb, dest_order;
    dfg_vertex_label ret_dest_dvl = NULL;
    statement        dest_st = NULL;
    predicate        prov_pr = NULL;
 
 
    /* Get destination vertex and information linked to it */
    dest_ver   = VERTEX(CAR( dest_ver_l ));
    dest_st    = adg_vertex_to_statement(dest_ver);
    dest_succ  = vertex_successors( dest_ver );
    dest_nb    = dfg_vertex_label_statement
        ((dfg_vertex_label) vertex_vertex_label( dest_ver ));
    dest_order = adg_number_to_ordering( dest_nb );
    dest_stco  = (static_control) GET_STATEMENT_MAPPING(stco_map, dest_st);
    dest_loops = static_control_loops(  dest_stco );
    dest_psl   = static_control_params( dest_stco );
    dest_lcl   = adg_get_loop_indices(  dest_loops );
 
    dest_pred = dfg_vertex_label_exec_domain(vertex_vertex_label(dest_ver));
    if (!predicate_undefined_p(dest_pred)) 
        dest_test_context = predicate_system( dest_pred );
    else dest_test_context = SC_RN;
 
    prov_pr = adg_get_predicate_of_loops(dest_loops);
    if (prov_pr != predicate_undefined) 
        dest_loop_context = predicate_system( prov_pr );
    else dest_loop_context = SC_RN;
    dest_context = sc_append(sc_dup( dest_test_context ),dest_loop_context);
    if (dest_context != SC_UNDEFINED) adg_sc_update_base(&dest_context);
    if ((dest_context != NULL)&&(!my_sc_faisabilite(dest_context))) continue;
 
    ret_dest_ver = adg_same_dfg_vertex_number( ret_verl, dest_nb );
    ret_dest_dvl = make_dfg_vertex_label( dest_nb, 
                                         make_predicate( sc_dup(dest_context) ),
                                         sccflags_undefined );
    if (ret_dest_ver == vertex_undefined) {
      ret_dest_ver = make_vertex( ret_dest_dvl, NIL );
      ADD_ELEMENT_TO_LIST( ret_verl, VERTEX, ret_dest_ver );
    }
    else 
        vertex_vertex_label(ret_dest_ver) = ret_dest_dvl;
 
 
 
    /* We search for all the read effects of vertex dest_ver 
     * and try to find the source for each read effect in dest_ver.
     */
    dest_readl = read_reference_list( dest_ver, dest_lcl, dest_psl );
    if (get_debug_level() > 3) { /* For debug purpose */
      fprintf(stderr, "\n========================================\n");
      fprintf(stderr, "Destination Statement (ordering %d) :\n",dest_order);
      print_statement( adg_number_to_statement( dest_nb ) );
      fprintf(stderr, "Read Effects :\n");
      print_effects( dest_readl );
    }
    for(; !ENDP( dest_readl ); POP( dest_readl )) {
      effect    dest_read_eff = NULL;
      list      sou_l = NULL, sou_lll = NIL;
      list      cand_l = NIL;
      int       max_depth = 0;
      int       prov_i;
      quast     source = quast_undefined;
 
      /* Get the current read_effect of destination */
      dest_read_eff = EFFECT(CAR( dest_readl ));
      dest_args     = reference_indices(effect_any_reference(dest_read_eff));
      if (get_debug_level() > 3) { /* For debug purpose */
        fprintf(stderr, "\n\n-->  Source of Effect ?  ");
        print_effects( CONS(EFFECT, dest_read_eff, NIL) );
      }
 
 
      /* Search for successors (in fact predecessors : input 
       * graph is reversed compared to dg graph !) that write 
       * the dest_read_eff and put their vertices in sou_l.
       * Then, order them by decreasing order of stat. number.
       */
      sou_l = adg_write_reference_list( dest_ver, dest_read_eff );
      if (sou_l == NIL) {
        /* No sources : Comes from Entry point */
        adg_fill_with_quast( &source, entry_q );
 
        /* Debugging */
        debug(9,"adg_dataflowgraph","No candidates => Entry Flow\n");
        if (get_debug_level() > 2) {
          fprintf(stderr,  "\n ------  Final Source  ------\n");
          imprime_special_quast( stderr, source );
        }
 
        adg_update_dfg( source,
                       effect_any_reference( dest_read_eff ),
                       ret_dest_ver,
                       pa_full(),
                       NULL,
                       NULL,
                       dup_dg,
                       &ret_verl );
 
        continue;
      }
      sou_l = adg_decreasing_stat_order_sort( sou_l );
 
 
      /* Build the source leaf label list sou_lll.
       * This list of leaf labels links a vertex number and a depth.
       */
      for(; !ENDP(sou_l); POP(sou_l)) {
        vertex      v   = VERTEX(CAR( sou_l ));
        int         dep = stco_common_loops_of_statements(stco_map,
                                              adg_vertex_to_statement( v ), dest_st);
        leaf_label  lel = make_leaf_label( dfg_vertex_label_statement(
                                    (dfg_vertex_label) vertex_vertex_label(v)), dep );
        ADD_ELEMENT_TO_LIST(sou_lll, LEAF_LABEL, lel);
        debug(9,"adg_dataflowgraph", "\nPossible source : stat %d at depth %d\n", 
              statement_number( adg_vertex_to_statement(v) ), dep);
      }
 
 
      /* Explode candidates for each depth and then,
       * build the candidate list cand_l by decreasing order.
       */ 
      max_depth = 0;
      for(prov_l = sou_lll; !ENDP(prov_l); POP(prov_l)) {
        int dep2 = leaf_label_depth(LEAF_LABEL(CAR( prov_l )));
        if( dep2 > max_depth ) max_depth = dep2;
      }
      for(prov_i = max_depth; prov_i >= 0; prov_i-- ) {
        prov_l = sou_lll;
        for(; !ENDP(prov_l); POP(prov_l) ) {
          leaf_label prov_lel = LEAF_LABEL(CAR(prov_l));
          int dd = leaf_label_depth( prov_lel );
          int nb = leaf_label_statement( prov_lel );
          if( prov_i <= dd ) 
            ADD_ELEMENT_TO_LIST(cand_l, LEAF_LABEL,make_leaf_label( nb, prov_i ));
        }
      }    
      max_depth = 0;            /* we will reuse it after */
 
 
      /* We run over all possible candidates 
       * and compute to see how it could contribute to the source
       */
      for(; !ENDP( cand_l ); POP(cand_l) ) {
        vertex          sou_v;
        int             sou_order, sou_d;
        leaf_label      sou_lel; 
        predicate       sou_pred = NULL;
        list            sou_lcl = NULL, sou_args = NIL;
        Psysteme        sou_ps = SC_RN;
        statement       sou_s;
        static_control  sou_stco;
        list            sou_psl;
        list            sou_loops;
        list            ent_l = NULL, renamed_l = NULL, merged_l = NULL;
        list            prov_l1 = NIL, prov_l2 = NIL;
        Psysteme        prov_ps = SC_RN;
        Psysteme        loc_context = SC_RN;
        Pvecteur        prov_pv = NULL;
        quast           prov_q = NULL, sou_q = NULL;
        Pposs_source    poss = NULL; 
        quast           *local_source = NULL;
        Ppath           local_path;
 
 
        /* Get possible source vertex and informations linked to it */
        sou_lel   = LEAF_LABEL(CAR( cand_l ));
        sou_v     = adg_number_to_vertex( dup_dg, leaf_label_statement(sou_lel) );
        sou_s     = adg_vertex_to_statement( sou_v );
        sou_d     = leaf_label_depth( sou_lel );
        sou_order = statement_ordering( sou_s );
        sou_stco  = (static_control) GET_STATEMENT_MAPPING( stco_map, sou_s );
        sou_psl   = static_control_params( sou_stco );
        sou_loops = static_control_loops(sou_stco);
        max_depth = adg_number_of_same_loops(sou_loops, dest_loops );
        sou_lcl   = adg_get_loop_indices( sou_loops );
 
 
        /* If this candidate is not possible, see the next.
         * Two cases : candidate and destination are in the
         * same deepest loop and dest is before candidate ;
         * or candidate is not valid with the present source.
         */
        if ((sou_d == max_depth) && adg_is_textualy_after_p(sou_s, dest_st)) continue;
        poss       = adg_path_possible_source(&source, sou_v, sou_d, pa_full(), TAKE_LAST);
        local_path = (Ppath) poss->pat;
        /* Not a possible source => get the next candidate */
        if (pa_empty_p( local_path )) continue;
 
        if PA_UNDEFINED_P(local_path) prov_ps = SC_UNDEFINED;
        else prov_ps = local_path->psys;
        local_source = (quast*) (poss->qua);
        loc_context  = sc_append(sc_dup(prov_ps), dest_context);
        prov_ps      = SC_UNDEFINED; /* will be reuse ? */
 
        /* For debug purpose */
        if (get_debug_level() > 3) { 
          fprintf(stderr, "\nPossible Source Statement (ordering %d) ",sou_order);
          fprintf(stderr, "at depth %d :\n", sou_d);
          print_statement( sou_s );
        }
 
                                
        /* Get the f(u) = g(b) psystem 
         * We first duplicate arguments expressions,
         * then we rename entities that are at 
         * a deeper depth than sou_d and forward
         * subsitute those new entities in the 
         * expressions 
         */
        sou_args = reference_indices(syntax_reference(expression_syntax(
                                      EXPRESSION(CAR(call_arguments(instruction_call(
                                            statement_instruction(sou_s) ))))  )));
        if(gen_length(sou_args) != gen_length(dest_args)) {
          pips_internal_error("No coherence between the source array and destination array !");
        }
 
                        
        /* Rename entities at rank > sou_d
         * and update Gforward_substitute_table 
         */
        for(prov_i=0; prov_i < sou_d; prov_i++) POP(sou_lcl);
        Gforward_substitute_table = hash_table_make(hash_pointer, 2+gen_length(sou_lcl));
        renamed_l = adg_rename_entities(sou_lcl, Gforward_substitute_table);
 
                
        /* Make corresponding indices equal in source and dest
         * F(u) = g(b) and put it in sou_ps.
         */
        prov_l1 = dest_args;
        for(prov_l2=sou_args;!ENDP(prov_l2);POP(prov_l2)){
          expression sou_e = NULL, dest_e = NULL;
          Pvecteur   pvec  = NULL;
          Psysteme   pss   = NULL;
 
          dest_e = EXPRESSION(CAR(prov_l1));
          POP( prov_l1 );
          sou_e = copy_expression( EXPRESSION(CAR(prov_l2)));
          forward_substitute_in_exp(&sou_e, Gforward_substitute_table);
 
          pvec = vect_substract(EXPRESSION_PVECTEUR(sou_e),
                                EXPRESSION_PVECTEUR(dest_e));
          if (pvec != NULL) {
            pss    = sc_make( contrainte_make(pvec), CONTRAINTE_UNDEFINED );
            sou_ps = sc_append(sou_ps, sc_dup(pss));
          }
        }
 
 
        /* Build the sequencing predicate */
        if ( (sou_d >= 0) && (sou_d < max_depth) ) {
          entity  indice1 = ENTITY( gen_nth(sou_d,dest_lcl) );
          entity  indice2 = ENTITY( gen_nth(sou_d,dest_lcl) );
          
          if (renamed_l != NIL) indice1 = ENTITY(CAR(renamed_l));
          /* compute indice1 + indice2 + 1 */
          prov_pv = vect_add( vect_new(TCST, VALUE_ONE),
                  vect_substract(vect_new((Variable) indice1, VALUE_ONE),
                                 vect_new((Variable) indice2, VALUE_ONE)) );
          sou_ps = sc_append(sou_ps,
                             sc_make(CONTRAINTE_UNDEFINED, contrainte_make( prov_pv )));
        }
                        
        /* append at the end p.s. of source to those of dest.
         * Concatenate the three lists to build Psys.
         * according to the order :
         * source-variables,sink-variables,struc.params
         */
        merged_l = adg_merge_entities_lists(dest_psl,sou_psl);
        ent_l    = gen_append( renamed_l, gen_append( dest_lcl, merged_l ) );
                        
 
 
        /* Build source Psysteme (IF and DO contraints).
         * Build the context and rename variables .
         */
        /* Get predicate that comes from an IF statement */
        sou_pred = dfg_vertex_label_exec_domain(
                                                vertex_vertex_label( sou_v ));
        if (sou_pred != predicate_undefined) prov_ps = adg_sc_dup(predicate_system(sou_pred));
        /* Get predicate that comes from enclosing DO */
        prov_pr = adg_get_predicate_of_loops( sou_loops );
        if (prov_pr != predicate_undefined) {
          prov_ps = sc_append( prov_ps, predicate_system( prov_pr ) );
        }
        /* Rename entities in the source context system */
        HASH_MAP( k, v, {
          char* vval = (char *) reference_variable(
                              syntax_reference(expression_syntax((expression) v) ));
          sc_variable_rename(prov_ps, (Variable) k, (Variable) vval);
        }, Gforward_substitute_table );
        hash_table_free(Gforward_substitute_table);
 
 
        /* Append sous_ps (F(u) = g(b) and seq. predicate)
         * with prov_ps (IF and DO constraints).
         */
        sou_ps = adg_suppress_2nd_in_1st_ps( sc_append(sou_ps, prov_ps), loc_context);
        if ((sou_ps != NULL) && !my_sc_faisabilite( sou_ps )) continue;
 
        /* Compute the new candidate source.
         * We try to call PIP only if necesary.
         */
        if (get_debug_level() > 4) {
          fprintf(stderr, "\nSource Psysteme :\n");
          fprint_psysteme(stderr, sou_ps);
          if (sou_ps != SC_UNDEFINED) pu_vect_fprint(stderr, sou_ps->base);
 
          fprintf(stderr, "\nContext Psysteme :\n");
          fprint_psysteme(stderr, loc_context);
          if (loc_context != SC_RN)  pu_vect_fprint(stderr,loc_context->base);
        }
        /* If there is no condition on source...*/
        if (sou_ps == SC_UNDEFINED) {
          sou_q = make_quast( make_quast_value( is_quast_value_quast_leaf,
                                              quast_leaf_undefined), NIL );
        }
        else if (gen_length(renamed_l) == 0) {
          prov_ps = sc_append( sc_dup(sou_ps), loc_context );
          if( (prov_ps == NULL) || my_sc_faisabilite(prov_ps)) {
            prov_q = make_quast( make_quast_value( is_quast_value_quast_leaf,
                                                  quast_leaf_undefined ), NIL );
            sou_q  = make_quast( make_quast_value(is_quast_value_conditional,
                                                 make_conditional( make_predicate(sou_ps),
                                                                  prov_q, quast_undefined)
                                                 ), NIL );
          }
          else sou_q = quast_undefined;
        }
        else  {
          Pvecteur pv_unknowns;
 
          /* Order the psysteme according to ent_l */
          sort_psysteme( sou_ps, adg_list_to_vect(ent_l, true) );
          pv_unknowns = list_to_base(renamed_l);
          sou_q = pip_integer_max(sou_ps, loc_context, pv_unknowns);
          my_pip_count++;
          if (get_debug_level() > 4) imprime_special_quast( stderr, sou_q );
          sou_q = adg_compact_quast( sou_q );
        }
        adg_enrichir( sou_q, sou_lel );
        if (get_debug_level() > 4) {
          fprintf(stderr, "\nPresent source quast :\n");
          imprime_special_quast( stderr, sou_q );
        }
                        
 
        /* Find the new source and simplify it */
        adg_path_max_source(local_source, &sou_q, local_path, dest_psl, TAKE_LAST );
 
        if (get_debug_level() > 4) {
          fprintf(stderr, "\n Updated Source :\n");
          imprime_special_quast( stderr, source );
        }
      }
 
 
      /* Fill "quast_undefined" part of the source 
       * with ENTRY node.
       */
      adg_fill_with_quast( &source, entry_q );
 
 
      /* Build the new Data Flow Graph with the new source*/
      if (get_debug_level() > 2) {
        fprintf(stderr, "\n ------  Final Source  ------\n");
        imprime_special_quast( stderr, source );
      }
 
      adg_update_dfg( source, 
                     effect_any_reference( dest_read_eff ),
                     ret_dest_ver,
                     pa_full(),
                     dest_context,
                     dest_test_context,
                     dup_dg,
                     &ret_verl );
    }
  }
 
  ret_graph = make_graph( ret_verl );
  debug(1, "adg_dataflowgraph", "end \n");
  return( ret_graph );
 
}

References ADD_ELEMENT_TO_LIST, adg_compact_quast(), adg_decreasing_stat_order_sort(), adg_enrichir(), adg_fill_with_quast(), adg_get_loop_indices(), adg_get_predicate_of_loops(), adg_is_textualy_after_p(), adg_list_to_vect(), adg_merge_entities_lists(), adg_number_of_same_loops(), adg_number_to_ordering(), adg_number_to_statement(), adg_number_to_vertex(), adg_path_max_source(), adg_path_possible_source(), adg_rename_entities(), adg_same_dfg_vertex_number(), adg_sc_dup(), adg_sc_update_base(), adg_suppress_2nd_in_1st_ps(), adg_update_dfg(), adg_vertex_to_statement(), adg_write_reference_list(), Ssysteme::base, call_arguments, CAR, CONS, contrainte_make(), CONTRAINTE_UNDEFINED, copy_expression(), debug(), dfg_vertex_label_exec_domain, dfg_vertex_label_statement, EFFECT, effect_any_reference, ENDP, ENTITY, ENTRY_ORDER, EXPRESSION, EXPRESSION_PVECTEUR, expression_syntax, forward_substitute_in_exp(), fprint_psysteme(), fprintf(), gen_append(), gen_length(), gen_nth(), get_debug_level(), GET_STATEMENT_MAPPING, Gforward_substitute_table, graph_undefined, graph_vertices, Gvertex_number_to_statement, HASH_MAP, hash_pointer, hash_put(), hash_table_free(), hash_table_make(), if(), imprime_special_quast(), instruction_call, is_quast_value_conditional, is_quast_value_quast_leaf, LEAF_LABEL, leaf_label_depth, leaf_label_statement, list_to_base(), make_conditional(), make_dfg_vertex_label(), make_graph(), make_leaf_label(), make_predicate(), make_quast(), make_quast_leaf(), make_quast_value(), make_vertex(), my_pip_count, my_sc_faisabilite(), NIL, pa_empty_p(), pa_full(), PA_UNDEFINED_P, Sposs_source::pat, pip_integer_max(), pips_internal_error, POP, predicate_system, predicate_undefined, predicate_undefined_p, print_effects, print_statement(), Spath::psys, pu_vect_fprint(), Sposs_source::qua, quast_leaf_undefined, quast_undefined, read_reference_list(), reference_indices, reference_variable, sc_append(), sc_dup(), sc_make(), sc_variable_rename(), sccflags_undefined, sort_psysteme(), statement_instruction, statement_number, statement_ordering, static_control_loops, static_control_params, stco_common_loops_of_statements(), syntax_reference, TAKE_LAST, TCST, VALUE_ONE, vect_add(), vect_new(), vect_substract(), VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.

Referenced by array_dfg().

Here is the caller graph for this function:

array_dfg()

boolean array_dfg

(

char*

mod_name

)

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

stubs.c

void array_dfg( (char*) module_name ) AL 93/06/29

It computes the array data flow graph using Feautrier's algorithm. This kind of graph detects the real dependances between arrays. It could be computed on a static control program. The original code is prepared by the static_controlize package. See its comments for more details.

summary or not ?

Initialize debugging functions

Initialization of the pass

set current_module_entity to ent ...

If the input program is not a static_control one, return

What will we compute ?

We need the dependance graph for a first source approximation. The graph is first reversed to have the possible source statement. Then we take only the WR dependances. At the end : duplicate nodes "a la Redon" for IF statement.

We reorder the statement number linked to each vertex in order to distinguich duplicated vertices

We compute the core of the pass

End of the program

Parameters

mod_name

odule

Definition at line 501 of file array_dfg.c.

{
  extern int            Gcount_re;
  extern int            Gcount_ie;
  graph                 dg = NULL, rev_dg = NULL, wr_dg = NULL; 
  graph                 dup_dg = NULL, ret_dfg = NULL;
  entity                ent = NULL;
  statement             mod_stat = NULL;
  static_control        stco = NULL;
  string                ss = NULL; /* summary or not ? */
  bool                  SUMMARY = false;
  
  /* Initialize debugging functions */
  debug_on("ARRAY_DFG_DEBUG_LEVEL");
  if (get_debug_level() > 0) 
    user_log("\n\n *** COMPUTE ARRAY DATA FLOW GRAPH for %s\n",mod_name);
 
 
  my_pip_count = 0;
  my_fai_count = 0;
 
  /* Initialization of the pass */
  Gcount_re = 0;
  Gcount_ie = 0;
  ent       = local_name_to_top_level_entity( mod_name );
  set_current_module_entity(ent); /* set current_module_entity to ent ... */
  
  mod_stat  = (statement) db_get_memory_resource(DBR_CODE, mod_name, true);
  Gstco_map = (statement_mapping) db_get_memory_resource(DBR_STATIC_CONTROL,
                                                         mod_name, true);
  
  /* If the input program is not a static_control one, return */
  stco   = (static_control) GET_STATEMENT_MAPPING(Gstco_map, mod_stat);
  if ( !static_control_yes( stco )) {
    pips_user_error("\n"
                    " CAN'T APPLY FEAUTRIER'S ALGORITHM:\n"
                    " This is not a static control program !");
  }
  Gstructural_parameters = static_control_params( stco );
  set_proper_rw_effects((statement_effects) 
                       db_get_memory_resource(DBR_PROPER_EFFECTS, mod_name, true));
 
  /* What will we compute ? */
  SUMMARY = ((ss = getenv("SUMMARY")) != NULL)? atoi(ss) : false;
  
  
  /* We need the dependance graph for a first source approximation.
   * The graph is first reversed to have the possible source statement.
   * Then we take only the WR dependances.
   * At the end : duplicate nodes "a la Redon" for IF statement.
   */
  dg      = (graph) db_get_memory_resource( DBR_DG, mod_name, true );
  rev_dg  = adg_reverse_graph( dg );
  wr_dg   = adg_only_call_WR_dependence( rev_dg );
  dup_dg  = adg_dup_disjunctive_nodes( wr_dg, Gstco_map );
  
  /* We reorder the statement number linked to each vertex
   * in order to distinguich duplicated vertices 
   */
  adg_reorder_statement_number( dup_dg );
  
  /* We compute the core of the pass */
  if (!SUMMARY) 
  { ret_dfg = adg_dataflowgraph( mod_stat, Gstco_map, dup_dg );}
  else ret_dfg = adg_dataflowgraph_with_extremities(mod_stat, Gstco_map, dup_dg);
  
  
  /* End of the program */
  if (get_debug_level() > 0) fprint_dfg(stderr, ret_dfg);
  if (get_debug_level() > 8) fprint_dfg(stderr, adg_pure_dfg(ret_dfg));
  
  DB_PUT_MEMORY_RESOURCE( DBR_ADFG, strdup(mod_name), ret_dfg);
  
  if (get_debug_level() > 0)  {
    printf("\n PIP CALLS : %d\n", my_pip_count);
    printf("\n FAI CALLS : %d\n", my_fai_count);
  }
 
  if (get_debug_level() > 0) user_log("\n\n *** ARRAY_DFG done\n");
  debug_off();
 
  reset_proper_rw_effects();
  reset_current_module_entity();
  reset_current_module_statement();
 
  return(true);
}

References adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_dup_disjunctive_nodes(), adg_only_call_WR_dependence(), adg_pure_dfg(), adg_reorder_statement_number(), adg_reverse_graph(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, fprint_dfg(), Gcount_ie, Gcount_re, get_debug_level(), GET_STATEMENT_MAPPING, Gstco_map, Gstructural_parameters, local_name_to_top_level_entity(), mod_stat, my_fai_count, my_pip_count, pips_user_error, printf(), reset_current_module_entity(), reset_current_module_statement(), reset_proper_rw_effects(), set_current_module_entity(), set_proper_rw_effects(), static_control_params, static_control_yes, strdup(), SUMMARY, and user_log().

Here is the call graph for this function:

my_sc_faisabilite()

bool my_sc_faisabilite

(

Psysteme

in_ps

)

Definition at line 55 of file array_dfg.c.

{
  my_fai_count++;
  return(sc_rational_feasibility_ofl_ctrl(in_ps, NO_OFL_CTRL,true));
}

References my_fai_count, NO_OFL_CTRL, and sc_rational_feasibility_ofl_ctrl().

Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

Gcount_ie

int Gcount_ie

Definition at line 46 of file array_dfg.c.

Referenced by adg_get_integer_entity(), and array_dfg().

Gcount_re

int Gcount_re

External variables.

Global variables.

Definition at line 45 of file array_dfg.c.

Referenced by adg_rename_entities(), and array_dfg().

Gforward_substitute_table

hash_table Gforward_substitute_table

static

Definition at line 53 of file array_dfg.c.

Referenced by adg_dataflowgraph().

Gstco_map

statement_mapping Gstco_map

Definition at line 47 of file array_dfg.c.

Referenced by adg_enrichir(), adg_max_of_leaves(), adg_path_max_source(), adg_path_possible_source(), and array_dfg().

Gstructural_parameters

list Gstructural_parameters

Definition at line 48 of file array_dfg.c.

Referenced by adg_dataflowgraph_with_extremities(), and array_dfg().

Gvertex_number_to_statement

hash_table Gvertex_number_to_statement

extern

Global variables.

Definition at line 42 of file adg_graph.c.

Referenced by adg_dataflowgraph(), adg_number_to_ordering(), adg_reorder_statement_number(), and adg_vertex_to_ordering().

my_fai_count

int my_fai_count

Definition at line 51 of file array_dfg.c.

Referenced by array_dfg(), and my_sc_faisabilite().

my_pip_count

int my_pip_count

Definition at line 50 of file array_dfg.c.

Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), and array_dfg().