chains.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "graph.h"
#include "dg.h"
#include "misc.h"
#include "properties.h"
#include "ri-util.h"
#include "effects-util.h"
#include "ricedg.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "chains.h"
#include "pipsdbm.h"
#include "pips-libs.h"

Include dependency graph for chains.c:

Go to the source code of this file.

Macros
#define	MAKE_STATEMENT_SET()   (set_make( set_pointer ))
	Macro to create set. More...
#define	INIT_STATEMENT_SIZE   20
	Default sizes for corresponding sets. More...
#define	INIT_ENTITY_SIZE   10
#define	GEN(st)   ((set)hash_get( Gen, (char *)st ))
#define	REF(st)   ((set)hash_get( Ref, (char *)st ))
#define	DEF_IN(st)   ((set)hash_get(Def_in, (char *)st))
#define	DEF_OUT(st)   ((set)hash_get(Def_out, (char *)st))
#define	REF_IN(st)   ((set)hash_get(Ref_in, (char *)st))
#define	REF_OUT(st)   ((set)hash_get(Ref_out, (char *)st))
#define	TABLE_FREE(t)    {HASH_MAP( k, v, {set_free( (set)v ) ;}, t ) ; hash_table_free(t);}

Typedefs
typedef void *	arc_label
	– usedef.c More...
typedef void *	vertex_label

Functions
static void	reset_effects ()
	Some forward declarations. More...
static list	load_statement_effects (statement s)
static void	inout_control ()
static void	inout_statement ()
static void	genref_statement ()
static bool	dd_du (effect fin, effect fout)
	DD_DU detects Def/Def, Def/Use conflicts between effects FIN and FOUT. More...
static bool	ud (effect fin, effect fout)
	UD detects Use/Def conflicts between effects FIN and FOUT. More...
static void	add_conflicts (effect fin, statement stout, vertex vout, cons *effect_outs, bool(*which)())
	adds conflict arcs to the dependence graph dg between the in-coming statement STIN and the out-going STOUT. More...
static void	local_print_statement_set (string msg, set s)
	Access functions for debug only. More...
static vertex	vertex_statement (statement st)
static bool	init_one_statement (statement st)
	Initializes the global data structures needed for usedef computation of one statement. More...
static void	kill_effects (set gen, set killers)
	The genref_xxx functions implement the computation of GEN and REF sets from Aho, Sethi and Ullman "Compilers" (p. More...
static void	genref_one_statement (statement st)
	Compute Gen and Ref set for a single statement. More...
static void	genref_test (test t, statement s)
	Compute Gen and Ref set for a test. More...
static void	mask_effects (set s, list l)
	MASK_EFFECTS masks the effects in S according to the locals L. More...
static void	genref_any_loop (statement body, statement st, list locals, _UNUSED_ bool one_trip_do_p)
	Compute Gen and Ref set for any loop (do, for, while,...) @description It has to deal specially with the loop variable which is not managed in the Dragon book. More...
static void	genref_loop (loop l, statement st)
	Compute Gen and Ref set for a "do" loop @description see genref_any_loop() More...
static void	genref_forloop (forloop l, statement st)
	Compute Gen and Ref set for a "for" loop @description see genref_any_loop() More...
static void	genref_whileloop (whileloop l, statement st)
	Compute Gen and Ref set for a "while" loop @description see genref_any_loop() More...
static void	genref_block (cons *sts, statement st)
	Compute Gen and Ref set for a block @description The Dragon book only deals with a sequence of two statements. More...
static void	genref_unstructured (unstructured u, statement st)
	Compute Gen and Ref set for an unstructured @description computes the gens, refs, and kills set of the unstructured by recursing on INOUT_CONTROL. More...
static void	genref_instruction (instruction i, statement st)
	Does the dispatch and recursion loop @description. More...
static void	genref_statement (statement s)
	Compute recursively Gen and Ref set for a statement. More...
static void	inout_block (_UNUSED_ statement st, cons *sts)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_test (_UNUSED_ statement s, test t)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_any_loop (statement st, statement body, bool one_trip_do_p, bool __attribute__((unused)) never_executed_p)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_loop (statement st, loop lo)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_whileloop (statement st, whileloop wl)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_forloop (statement st, forloop fl)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_call (statement st, call __attribute__((unused)) c)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_unstructured (statement st, unstructured u)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_statement (statement st)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static void	inout_control (control ct)
	Propagates in sets of ST (which is inherited) to compute the out sets. More...
static cons *	pushnew_conflict (effect fin, effect fout, cons *cfs)
	adds the conflict FIN->FOUT in the list CFS @description adds the conflict FIN->FOUT in the list CFS (if it's not already there, and apparently even if it's already there for performance reason...). More...
graph	statement_dependence_graph (statement s)
	Compute from a given statement, the dependency graph. More...
static void	set_effects (char *module_name, enum chain_type use)
	Select the type of effects used to compute dependence chains. More...
static bool	chains (char *module_name, enum chain_type use)
	Compute chain dependence for a module according different kinds of store-like effects. More...
bool	atomic_chains (const string module_name)
	Phase to compute atomic chains based on proper effects (simple memory accesses) More...
bool	region_chains (const string module_name)
	Phase to compute atomic chains based on array regions. More...
bool	in_out_regions_chains (const string module_name)
	Phase to compute atomic chains based on in-out array regions. More...

Variables
static hash_table	effects2statement
	Mapping from effects to the associated statement. More...
static hash_table	Gen
	Gen maps each statement to the effects it generates. More...
static hash_table	Ref
	Refs maps each statement to the effects it references. More...
static set	current_defs
	current_defs is the set of DEF at the current point of the computation More...
static set	current_refs
static hash_table	Def_in
	Def_in maps each statement to the statements that are in-coming the statement It's only used for unstructured, current_defs is used for structured parts. More...
static hash_table	Def_out
	Def_out maps each statement to the statements that are out-coming the statement It's only used for unstructured, current_defs is used for structured parts. More...
static hash_table	Ref_in
	Ref_in maps each statement to the effects that are in-coming the statement It's only used for unstructured, current_refs is used for structured parts. More...
static hash_table	Ref_out
	Ref_out maps each statement to the effects that are out-coming the statement It's only used for unstructured, current_refs is used for structured parts. More...
static graph	dg
	dg is the dependency graph ; FIXME : should not be static global ? More...
static hash_table	Vertex_statement
	Vertex_statement maps each statement to its vertex in the dependency graph. More...
static bool	one_trip_do_p
	Some properties. More...
static bool	keep_read_read_dependences_p
static bool	mask_effects_p
static bool	dataflow_dependence_only_p
static bool	rgch = false
	functions for effects maps More...
static bool	iorgch = false

Macro Definition Documentation

DEF_IN

#define DEF_IN

(

st

)

((set)hash_get(Def_in, (char *)st))

Definition at line 106 of file chains.c.

DEF_OUT

#define DEF_OUT

(

st

)

((set)hash_get(Def_out, (char *)st))

Definition at line 111 of file chains.c.

GEN

#define GEN

(

st

)

((set)hash_get( Gen, (char *)st ))

Definition at line 93 of file chains.c.

INIT_ENTITY_SIZE

#define INIT_ENTITY_SIZE   10

Definition at line 86 of file chains.c.

INIT_STATEMENT_SIZE

#define INIT_STATEMENT_SIZE   20

Default sizes for corresponding sets.

This is automatically adjusted according to needs by the hash table package.

Definition at line 85 of file chains.c.

MAKE_STATEMENT_SET

#define MAKE_STATEMENT_SET

(

)

(set_make( set_pointer ))

Macro to create set.

Definition at line 81 of file chains.c.

REF

#define REF

(

st

)

((set)hash_get( Ref, (char *)st ))

Definition at line 97 of file chains.c.

REF_IN

#define REF_IN

(

st

)

((set)hash_get(Ref_in, (char *)st))

Definition at line 116 of file chains.c.

REF_OUT

#define REF_OUT

(

st

)

((set)hash_get(Ref_out, (char *)st))

Definition at line 121 of file chains.c.

TABLE_FREE

#define TABLE_FREE

(

t

)

{HASH_MAP( k, v, {set_free( (set)v ) ;}, t ) ; hash_table_free(t);}

Typedef Documentation

arc_label

typedef void* arc_label

– usedef.c

Computes (approximate) use/def chains of a structured control graph.

Definition at line 43 of file chains.c.

vertex_label

typedef void* vertex_label

Definition at line 44 of file chains.c.

Function Documentation

add_conflicts()

static void add_conflicts ( effect  fin, statement  stout, vertex  vout, cons *  effect_outs, bool(*)()  which  )

static

adds conflict arcs to the dependence graph dg between the in-coming statement STIN and the out-going STOUT.

@description Note that output dependencies are not minimal (e.g., i = s ; s = ... ; s = ...) creates an oo-dep between the i assignment and the last s assignment.

To speed up pushnew_conflict() without damaging the integrity of the use-def chains

I think that most of this is hazardous when mixes of pointers, arrays and structs are involved. However, there should be no pointer anymore with CONSTANT_PATH_EFFECTS set to TRUE! We need to think more about all of this. BC.

Second version due to accuracy improvements in effect computation

This is the standard case

I'm not sure this can be the case because of effects_might_conflict_even_read_only_p(fin, fout)

a write on the shorter memory access path conflicts with the longer one. If a[i] is written, then a[i][j] depends on it. If a[i] is read, no conflict

dout > din

same explanation as above

Why should we limit this test to pointers? Structures, structures of arrays and arrays of structures with pointers embedded somewhere must behave in the very same way. Why not unify the two cases? Because we have not spent enough time thinking about memory access paths.

a write on the shorter memory access path conflicts with the longer one. If a[i] is written, then a[i][j] depends on it. If a[i] is read, no conflict

same explanation as above

Here we filter effect on loop indices except for abstract locations

Add conflicts

The sink vertex in the graph

Try first to find an existing vertex for this statement

There is no sink vertex for this statement, create one

Use existing vertex for this statement

Definition at line 1050 of file chains.c.

                                          {
  vertex vin;
  cons *cs = NIL;
 
  ifdebug(2) {
    statement stin = hash_get( effects2statement, fin );
    _int stin_o = statement_ordering(stin);
    _int stout_o = statement_ordering(stout);
    fprintf( stderr,
             "Conflicts %td (%td,%td) (%p) -> %td (%td,%td) (%p) %s"
             " for \"%s\"\n",
             statement_number(stin),
             ORDERING_NUMBER(stin_o),
             ORDERING_STATEMENT(stin_o),
             stin,
             statement_number(stout),
             ORDERING_NUMBER(stout_o),
             ORDERING_STATEMENT(stout_o),
             stout,
             ( which == ud ) ? "ud" : "dd_du",
             entity_local_name(effect_to_entity(fin)));
  }
 
  /* To speed up pushnew_conflict() without damaging the integrity of
   the use-def chains */
  ifdebug(1) {
    statement stin = hash_get( effects2statement, fin );
    cons *effect_ins = load_statement_effects( stin );
    if ( !gen_once_p( effect_ins ) ) {
      pips_internal_error("effect_ins are redundant");
    }
    if ( !gen_once_p( effect_outs ) ) {
      pips_internal_error("effect_outs are redundant");
    }
  }
  FOREACH(EFFECT, fout, effect_outs) {
    ifdebug(2) {
      print_effect(fin);
      fprintf(stderr," -> ");
      print_effect(fout);
      fprintf(stderr,"\n");
    }
 
    // We want to check the conflict even with read/read, because we already
    // asserted what we want before (ud/du/dd)
    if((*which)(fin, fout) && effects_might_conflict_even_read_only_p(fin, fout)) {
      entity ein = effect_entity(fin);
      bool ein_abstract_location_p = entity_abstract_location_p(ein);
      entity eout = effect_entity(fout);
      bool add_conflict_p = true;
 
      /* I think that most of this is hazardous when mixes of
         pointers, arrays and structs are involved. However, there
         should be no pointer anymore with CONSTANT_PATH_EFFECTS set
         to TRUE!  We need to think more about all of this. BC.
      */
      if(ein_abstract_location_p) {
#if 0 //SG: as is, this code is equivalent to doing nothing
            pips_debug(2, "abstract location case \n");
        entity alout = variable_to_abstract_location(eout);
        /* this test is not correct, rout should be converted to an abstract location, not eout. BC. */
        if(abstract_locations_may_conflict_p(ein, alout))
          add_conflict_p = true;
#endif
      } else {
        reference rin = effect_any_reference(fin);
        int din = gen_length(reference_indices(rin));
        reference rout = effect_any_reference(fout);
        int dout = gen_length(reference_indices(rout));
        type tin = ultimate_type(entity_type(ein));
        type tout = ultimate_type(entity_type(eout));
        if(pointer_type_p(tin) && pointer_type_p(tout)) {
          pips_debug(2, "pointer type case \n");
          /* Second version due to accuracy improvements in effect
         computation */
          if(din == dout) {
            /* This is the standard case */
            add_conflict_p = true;
          } else if(din < dout) {
            /* I'm not sure this can be the case because of
             * effects_might_conflict_even_read_only_p(fin, fout) */
            /* a write on the shorter memory access path conflicts
             * with the longer one. If a[i] is written, then a[i][j]
             * depends on it. If a[i] is read, no conflict */
            add_conflict_p = action_write_p(effect_action(fin));
          } else /* dout > din */{
            /* same explanation as above */
            add_conflict_p = action_write_p(effect_action(fout));
          }
        } else {
          /* Why should we limit this test to pointers? Structures,
           * structures of arrays and arrays of structures with
           * pointers embedded somewhere must behave in the very same
           * way. Why not unify the two cases? Because we have not
           * spent enough time thinking about memory access paths. */
          if(din < dout) {
            /* a write on the shorter memory access path conflicts
             * with the longer one. If a[i] is written, then a[i][j]
             * depends on it. If a[i] is read, no conflict */
            add_conflict_p = action_write_p(effect_action(fin));
          } else if(dout < din) {
            /* same explanation as above */
            add_conflict_p = action_write_p(effect_action(fout));
          }
        }
      }
 
      if(add_conflict_p) {
        pips_debug(2, "add_conflicts_p is true; checking conflicts with loop indices\n");
        bool remove_this_conflict_p = false;
        if(!ein_abstract_location_p && store_effect_p(fin)) {
          /* Here we filter effect on loop indices except for abstract
           locations */
          list loops = load_statement_enclosing_loops(stout);
          FOREACH( statement, el, loops ) {
            entity il = loop_index(statement_loop(el));
            pips_debug(2, "checking conflict with %s\n", entity_name(il));
            remove_this_conflict_p |= entities_may_conflict_p(ein, il);
            pips_debug(2, "remove_this_conflict_ p = %s\n", bool_to_string(remove_this_conflict_p));
          }
        }
        if(!remove_this_conflict_p) {
          cs = pushnew_conflict(fin, fout, cs);
        }
      }
    }
  }
 
  /* Add conflicts */
  if(!ENDP( cs )) {
    statement stin = hash_get( effects2statement, fin );
    vin = vertex_statement( stin );
 
    /* The sink vertex in the graph */
    successor sout = successor_undefined;
    /* Try first to find an existing vertex for this statement */
    FOREACH( successor, s, vertex_successors( vin ) ) {
      if(successor_vertex(s) == vout) {
        sout = s;
        break;
      }
    }
    if(successor_undefined_p(sout)) {
      /* There is no sink vertex for this statement, create one */
      sout = make_successor(make_dg_arc_label(cs), vout);
      vertex_successors( vin )
          = CONS( SUCCESSOR, sout, vertex_successors( vin ));
    } else {
      /* Use existing vertex for this statement */
      gen_nconc(successor_arc_label(sout), cs);
 
    }
  }
 
}

References abstract_locations_may_conflict_p(), action_write_p, bool_to_string(), CONS, EFFECT, effect_action, effect_any_reference, effect_entity(), effect_to_entity(), effects2statement, effects_might_conflict_even_read_only_p(), ENDP, entities_may_conflict_p(), entity_abstract_location_p(), entity_local_name(), entity_name, entity_type, FOREACH, fprintf(), gen_length(), gen_nconc(), gen_once_p(), hash_get(), ifdebug, load_statement_effects(), load_statement_enclosing_loops(), loop_index, loops, make_dg_arc_label(), make_successor(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_debug, pips_internal_error, pointer_type_p(), print_effect, pushnew_conflict(), reference_indices, statement_loop(), statement_number, statement_ordering, store_effect_p(), SUCCESSOR, successor_arc_label, successor_undefined, successor_undefined_p, successor_vertex, ud(), ultimate_type(), variable_to_abstract_location(), vertex_statement(), and vertex_successors.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

atomic_chains()

bool atomic_chains

(

const string

module_name

)

Phase to compute atomic chains based on proper effects (simple memory accesses)

Parameters

module_name

odule_name

Definition at line 1442 of file chains.c.

                                             {
  return chains( module_name, USE_PROPER_EFFECTS );
}

References chains(), module_name(), and USE_PROPER_EFFECTS.

Here is the call graph for this function:

chains()

static bool chains ( char *  module_name, enum chain_type  use  )

static

Compute chain dependence for a module according different kinds of store-like effects.

Parameters

module_name	is the name of the module we want to compute the chains
use	the type of effects we want to use to compute the dependence chains

Returns

true because we are very confident it works :-)

set_entity_to_size(); should be performed at the workspace level

Definition at line 1397 of file chains.c.

                                                              {
  statement module_stat;
  graph module_graph;
  void print_graph();
 
  set_current_module_statement( (statement) db_get_memory_resource( DBR_CODE,
                                                                    module_name,
                                                                    true ) );
  module_stat = get_current_module_statement( );
  set_current_module_entity( local_name_to_top_level_entity( module_name ) );
  /* set_entity_to_size(); should be performed at the workspace level */
 
  debug_on("CHAINS_DEBUG_LEVEL");
 
  pips_debug(1, "finding enclosing loops ...\n");
  set_enclosing_loops_map( loops_mapping_of_statement( module_stat ) );
 
 
  set_effects( module_name, use );
  set_conflict_testing_properties();
 
  module_graph = statement_dependence_graph( module_stat );
 
  ifdebug(2) {
    set_ordering_to_statement( module_stat );
    prettyprint_dependence_graph( stderr, module_stat, module_graph );
    reset_ordering_to_statement( );
  }
 
  debug_off();
 
  DB_PUT_MEMORY_RESOURCE(DBR_CHAINS, module_name, (char*) module_graph);
 
  reset_effects( );
  clean_enclosing_loops( );
  reset_current_module_statement( );
  reset_current_module_entity( );
 
  return true;
}

References clean_enclosing_loops(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, get_current_module_statement(), ifdebug, local_name_to_top_level_entity(), loops_mapping_of_statement(), module_name(), pips_debug, prettyprint_dependence_graph(), reset_current_module_entity(), reset_current_module_statement(), reset_effects(), reset_ordering_to_statement(), set_conflict_testing_properties(), set_current_module_entity(), set_current_module_statement(), set_effects(), set_enclosing_loops_map(), set_ordering_to_statement(), and statement_dependence_graph().

Referenced by atomic_chains(), compute_dg_on_statement_from_chains(), compute_dg_on_statement_from_chains_in_place(), do_simplify_dg(), in_out_regions_chains(), region_chains(), and rice_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

dd_du()

static bool dd_du ( effect  fin, effect  fout  )

static

DD_DU detects Def/Def, Def/Use conflicts between effects FIN and FOUT.

Definition at line 1025 of file chains.c.

                                             {
  bool conflict_p = action_write_p( effect_action( fin ));
 
  if ( dataflow_dependence_only_p ) {
    conflict_p = conflict_p && action_read_p( effect_action( fout ) );
  }
 
  return conflict_p;
}

References action_read_p, action_write_p, dataflow_dependence_only_p, and effect_action.

Referenced by inout_statement().

Here is the caller graph for this function:

genref_any_loop()

static void genref_any_loop ( statement  body, statement  st, list  locals, _UNUSED_ bool  one_trip_do_p  )

static

Compute Gen and Ref set for any loop (do, for, while,...) @description It has to deal specially with the loop variable which is not managed in the Dragon book.

Effect masking is performed on locals (i.e., gen&ref sets are pruned from local definitions).

For DO loop, if loops are at least one trip (set by property "ONE_TRIP_DO"), then statements are always killed by execution of loop body.

Parameters

l	the loop to compute
st	the statement that hold the loop

Compute genref on the loop body

Summarize the body to the statement that hold the loop

Filter effects on local variables

Definition at line 372 of file chains.c.

{
  set gen = GEN( st );
  set ref = REF( st );
 
  /* Compute genref on the loop body */
  genref_statement( body );
 
  /* Summarize the body to the statement that hold the loop */
  set_union( gen, gen, GEN( body ) );
  set_union( ref, ref, REF( body ) );
 
  /* Filter effects on local variables */
  if ( mask_effects_p ) {
    mask_effects( gen, locals );
    mask_effects( ref, locals );
  }
 
}

References gen(), GEN, genref_statement(), mask_effects(), mask_effects_p, REF, ref, and set_union().

Referenced by genref_forloop(), genref_loop(), and genref_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_block()

static void genref_block ( cons *  sts, statement  st  )

static

Compute Gen and Ref set for a block @description The Dragon book only deals with a sequence of two statements.

here we generalize to lists, via recursion. Statement are processed in reversed order (i.e. on the descending phase of recursion)

Parameters

sts	the list of statements inside the block
st	the statement that hold the block

Summarize for the block

loop over statements inside the block

Definition at line 460 of file chains.c.

                                                    {
  /* Summarize for the block */
  set gen_st = GEN( st );
  set ref_st = REF( st );
 
  /* loop over statements inside the block */
  FOREACH( statement, one, sts ) {
 
    genref_statement( one );
 
    // We no longer use a "kill set" FIXME : one_trip_do, test, ....
    kill_effects(gen_st,GEN(one));
    set_union(gen_st,GEN(one),gen_st);
 
    set_union( ref_st, REF( one ), ref_st );
 
  }
  // Gen for the block doesn't include locally declared variable
  if ( mask_effects_p) {
    mask_effects( gen_st, statement_declarations(st) );
    mask_effects( ref_st, statement_declarations(st) );
  }
}

References FOREACH, GEN, genref_statement(), kill_effects(), mask_effects(), mask_effects_p, REF, set_union(), and statement_declarations.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_forloop()

static void genref_forloop ( forloop  l, statement  st  )

static

Compute Gen and Ref set for a "for" loop @description see genref_any_loop()

Parameters

l	the loop to compute
st	the statement that hold the loop

Call the generic function handling all kind of loop

Definition at line 426 of file chains.c.

                                                      {
  statement body = forloop_body( l );
  list locals = statement_declarations(st);
 
  /* Call the generic function handling all kind of loop */
  genref_any_loop( body, st, locals, one_trip_do_p );
 
}

References forloop_body, genref_any_loop(), one_trip_do_p, and statement_declarations.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_instruction()

static void genref_instruction ( instruction  i, statement  st  )

static

Does the dispatch and recursion loop @description.

Parameters

i	is the instruction
st	is the statement that hold the instruction

no recursion for these kind of instruction

Definition at line 530 of file chains.c.

                                                              {
  cons *pc;
  test t;
  loop l;
 
  switch ( instruction_tag(i) ) {
    case is_instruction_block:
      genref_block( pc = instruction_block(i), st );
      break;
    case is_instruction_test:
      t = instruction_test(i);
      genref_test( t, st );
      break;
    case is_instruction_loop:
      l = instruction_loop(i);
      genref_loop( l, st );
      break;
    case is_instruction_whileloop: {
      whileloop l = instruction_whileloop(i);
      genref_whileloop( l, st );
      break;
    }
    case is_instruction_forloop: {
      forloop l = instruction_forloop(i);
      genref_forloop( l, st );
      break;
    }
    case is_instruction_unstructured:
      genref_unstructured( instruction_unstructured( i ), st );
      break;
    case is_instruction_call:
    case is_instruction_expression:
    case is_instruction_goto:
      /* no recursion for these kind of instruction */
      break;
    default:
      pips_internal_error("unexpected tag %d", instruction_tag(i));
  }
}

References genref_block(), genref_forloop(), genref_loop(), genref_test(), genref_unstructured(), genref_whileloop(), instruction_block, instruction_forloop, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, and pips_internal_error.

Referenced by genref_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_loop()

static void genref_loop ( loop  l, statement  st  )

static

Compute Gen and Ref set for a "do" loop @description see genref_any_loop()

Parameters

l	the loop to compute
st	the statement that hold the loop

Building locals list

Call the generic function handling all kind of loop

We free because we are good programmers and we don't leak ;-)

Definition at line 403 of file chains.c.

                                                {
  statement body = loop_body( l );
 
  /* Building locals list */
  list llocals = loop_locals( l );
  list slocals = statement_declarations(st);
  list locals = gen_nconc( gen_copy_seq( llocals ), gen_copy_seq( slocals ) );
 
  /* Call the generic function handling all kind of loop */
  genref_any_loop( body, st, locals, one_trip_do_p );
 
  /* We free because we are good programmers and we don't leak ;-) */
  gen_free_list( locals );
}

References gen_copy_seq(), gen_free_list(), gen_nconc(), genref_any_loop(), loop_body, loop_locals, one_trip_do_p, and statement_declarations.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_one_statement()

static void genref_one_statement ( statement  st )

static

Compute Gen and Ref set for a single statement.

Parameters

st	the statement to compute

Loop over effects to find which one will generates or references some variables

A write effect will always generate a definition

A read effect will always generate a reference

Secure programming

Definition at line 276 of file chains.c.

                                                 {
  set gen = GEN( st );
  set ref = REF( st );
  set_clear( gen );
  set_clear( ref );
  /* Loop over effects to find which one will generates
   * or references some variables
   */
  FOREACH( effect, e, load_statement_effects(st) )
  {
    action a = effect_action( e );
 
    if ( action_write_p( a ) ) {
      pips_assert("Effect isn't map to this statement !",
          st == hash_get(effects2statement, e));
 
      /* A write effect will always generate a definition */
      set_add_element( gen, gen, (char *) e );
    } else if ( action_read_p( a ) ) {
      /* A read effect will always generate a reference */
      set_add_element( ref, ref, (char *) e );
    } else {
      /* Secure programming */
      pips_internal_error("Unknow action for effect : "
          "neither a read nor a write !");
    }
  }
}

References action_read_p, action_write_p, effect_action, effects2statement, FOREACH, gen(), GEN, hash_get(), load_statement_effects(), pips_assert, pips_internal_error, REF, ref, set_add_element(), and set_clear().

Referenced by genref_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_statement() [1/2]

static void genref_statement ( )

static

Referenced by genref_any_loop(), genref_block(), genref_test(), genref_unstructured(), and statement_dependence_graph().

Here is the caller graph for this function:

genref_statement() [2/2]

static void genref_statement ( statement  s )

static

Compute recursively Gen and Ref set for a statement.

This is the main entry to this task. @description computes the gens and refs set of the statement by recursing

Parameters

s	is the statement to compute

Compute genref using effects associated to the statement itself

Recurse inside the statement (relevant for blocks, loop, ...)

Definition at line 578 of file chains.c.

                                            {
 
  /* Compute genref using effects associated to the statement itself */
  genref_one_statement( s );
 
  ifdebug(2) {
    debug( 2,
           "genref_statement",
           "Result genref_one_statement for Statement %p [%s]:\n",
           s,
           statement_identification( s ) );
    local_print_statement_set( "GEN", GEN( s ) );
    local_print_statement_set( "REF", REF( s ) );
  }
 
  /* Recurse inside the statement (relevant for blocks, loop, ...) */
  genref_instruction( statement_instruction(s), s );
 
  ifdebug(2) {
    debug( 2,
           "genref_statement",
           "Result for Statement %p [%s]:\n",
           s,
           statement_identification( s ) );
    ;
    local_print_statement_set( "GEN", GEN( s ) );
    local_print_statement_set( "REF", REF( s ) );
  }
}

References debug(), GEN, genref_instruction(), genref_one_statement(), ifdebug, local_print_statement_set(), REF, statement_identification(), and statement_instruction.

Here is the call graph for this function:

genref_test()

static void genref_test ( test  t, statement  s  )

static

Compute Gen and Ref set for a test.

Parameters

t	the test
s	the statement to compute

compute true path

compute false path

Combine the two path to summarize the test

Definition at line 310 of file chains.c.

                                               {
  statement st = test_true(t);
  statement sf = test_false(t);
  set ref = REF( s );
 
  /* compute true path */
  genref_statement( st );
  /* compute false path */
  genref_statement( sf );
 
  /* Combine the two path to summarize the test */
  set_union( GEN( s ), GEN( st ), GEN( sf ) );
  set_union( ref, ref, REF( sf ) );
  set_union( ref, ref, REF( st ) );
}

References GEN, genref_statement(), REF, ref, set_union(), test_false, and test_true.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_unstructured()

static void genref_unstructured ( unstructured  u, statement  st  )

static

Compute Gen and Ref set for an unstructured @description computes the gens, refs, and kills set of the unstructured by recursing on INOUT_CONTROL.

The gens&refs can then be inferred. The situation for the kills is more fishy; for the moment, we just keep the kills that are common to all statements of the control graph.

Parameters

u	is the unstructured
st	is the statement that hold the unstructured

recursing

Definition at line 494 of file chains.c.

                                                                {
  control c = unstructured_control( u );
  statement exit = control_statement( unstructured_exit( u ));
  cons *blocs = NIL;
 
  set_clear( DEF_IN( st ) );
  /* recursing */
  CONTROL_MAP( c, {statement st = control_statement( c );
        genref_statement( st );
        },
      c, blocs );
 
  if ( set_undefined_p( DEF_OUT( exit )) ) {
    set ref = MAKE_STATEMENT_SET();
    set empty = MAKE_STATEMENT_SET();
    CONTROL_MAP( cc, {
          set_union( ref, ref, REF( control_statement( cc )));
        }, c, blocs );
    set_assign( REF( st ), ref );
    set_free( ref );
    set_assign( GEN( st ), empty );
    set_free( empty );
  } else {
    set_assign( GEN( st ), DEF_OUT( exit ) );
    set_difference( REF( st ), REF_OUT( exit ), REF_IN( st ) );
  }
  gen_free_list( blocs );
}

References CONTROL_MAP, control_statement, DEF_IN, DEF_OUT, empty, exit, GEN, gen_free_list(), genref_statement(), MAKE_STATEMENT_SET, NIL, REF, ref, REF_IN, REF_OUT, set_assign(), set_clear(), set_difference(), set_free(), set_undefined_p, set_union(), unstructured_control, and unstructured_exit.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

genref_whileloop()

static void genref_whileloop ( whileloop  l, statement  st  )

static

Compute Gen and Ref set for a "while" loop @description see genref_any_loop()

Parameters

l	the loop to compute
st	the statement that hold the loop

Call the generic function handling all kind of loop

Definition at line 442 of file chains.c.

                                                          {
  statement body = whileloop_body( l );
  list locals = statement_declarations(st);
 
  /* Call the generic function handling all kind of loop */
  genref_any_loop( body, st, locals, one_trip_do_p );
}

References genref_any_loop(), one_trip_do_p, statement_declarations, and whileloop_body.

Referenced by genref_instruction().

Here is the call graph for this function:

Here is the caller graph for this function:

in_out_regions_chains()

bool in_out_regions_chains

(

const string

module_name

)

Phase to compute atomic chains based on in-out array regions.

Parameters

module_name

odule_name

Definition at line 1456 of file chains.c.

                                                     {
  return chains( module_name, USE_IN_OUT_REGIONS );
}

References chains(), module_name(), and USE_IN_OUT_REGIONS.

Here is the call graph for this function:

init_one_statement()

static bool init_one_statement ( statement  st )

static

Initializes the global data structures needed for usedef computation of one statement.

Parameters

st	the statement to initialize

Returns

always true (gen_recurse continuation)

First initialization (normal use)

Create a new vertex in the DG for the statement:

If the statement has never been seen, allocate new sets: This could be optimized : {DEF,REF}_{IN,OUT} are needed only for unstructured

FI: regions are not really proper effects... I should use proper effects for non-call instruction I need a global variable let's kludge this for the time being, 5 August 1992

If the statement has already been seen, reset the sets associated to it:

Go on recursing down:

Definition at line 172 of file chains.c.

                                               {
 
  if ( GEN( st ) == (set) HASH_UNDEFINED_VALUE ) {
    /* First initialization (normal use) */
 
    ifdebug(2) {
      fprintf( stderr,
               "Init statement %td with effects %p, ordering %tx\n",
               statement_number( st ),
               load_statement_effects( st ),
               statement_ordering(st) );
      print_effects( load_statement_effects( st ) );
    }
 
    /* Create a new vertex in the DG for the statement: */
    dg_vertex_label l;
    vertex v;
    l = make_dg_vertex_label( statement_ordering(st), sccflags_undefined );
    v = make_vertex( l, NIL );
    hash_put( Vertex_statement, (char *) st, (char *) v );
    graph_vertices( dg ) = CONS( VERTEX, v, graph_vertices( dg ));
 
    /* If the statement has never been seen, allocate new sets:
     * This could be optimized : {DEF,REF}_{IN,OUT} are
     * needed only for unstructured */
    hash_put( Gen, (char *) st, (char *) MAKE_STATEMENT_SET() );
    hash_put( Ref, (char *) st, (char *) MAKE_STATEMENT_SET() );
    hash_put( Def_in, (char *) st, (char *) MAKE_STATEMENT_SET() );
    hash_put( Def_out, (char *) st, (char *) MAKE_STATEMENT_SET() );
    hash_put( Ref_in, (char *) st, (char *) MAKE_STATEMENT_SET() );
    hash_put( Ref_out, (char *) st, (char *) MAKE_STATEMENT_SET() );
 
    /* FI: regions are not really proper effects...
     I should use proper effects for non-call instruction
     I need a global variable
     let's kludge this for the time being, 5 August 1992
     */
    if ( !instruction_block_p(statement_instruction(st)) ) {
      FOREACH(EFFECT, e, load_statement_effects(st) )
      {
        hash_put( effects2statement, (char *) e, (char *) st );
      }
    }
  } else {
    /* If the statement has already been seen, reset the sets associated
     to it: */
    set_clear( GEN( st ) );
    set_clear( REF( st ) );
    set_clear( DEF_OUT( st ) );
    set_clear( DEF_IN( st ) );
    set_clear( REF_OUT( st ) );
    set_clear( REF_IN( st ) );
  }
  /* Go on recursing down: */
  return true;
}

References CONS, Def_in, DEF_IN, Def_out, DEF_OUT, dg, EFFECT, effects2statement, FOREACH, fprintf(), Gen, GEN, graph_vertices, hash_put(), HASH_UNDEFINED_VALUE, ifdebug, instruction_block_p, load_statement_effects(), make_dg_vertex_label(), MAKE_STATEMENT_SET, make_vertex(), NIL, print_effects, Ref, REF, Ref_in, REF_IN, Ref_out, REF_OUT, sccflags_undefined, set_clear(), statement_instruction, statement_number, statement_ordering, VERTEX, and Vertex_statement.

Referenced by statement_dependence_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_any_loop()

static void inout_any_loop ( statement  st, statement  body, bool  one_trip_do_p, bool __attribute__((unused))  never_executed_p  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the loop
lo	is the loop
one_trip_do_p	tell if there is always at least one trip (do loop only)
never_executed_p	tell if loop never executed (when it's possible, do loop only) (unused)

Compute "in" sets for the loop body

Compute loop body

Compute "out" sets for the loop

Body is not always done, approximation by union

Definition at line 673 of file chains.c.

                                                                                                                               {
  // NL: I don't know how it work to make the optimization with never_executed_p
  // Maybe decorate the code by
  // if(!never_executed_p) {
  set def_in;
  set ref_in;
 
  if ( ! one_trip_do_p ) {
    // Save DEF and REF
    def_in = set_dup(current_defs);
    ref_in = set_dup(current_refs);
  }
 
  /* Compute "in" sets for the loop body */
  set_union( current_defs, current_defs, GEN( st ) );
  set_union( current_refs, current_refs, REF( st ) );
 
  /* Compute loop body */
  inout_statement( body );
 
  /* Compute "out" sets for the loop */
  if ( ! one_trip_do_p ) {
    /* Body is not always done, approximation by union */
    set_union( current_defs, current_defs, def_in );
    set_union( current_refs, current_refs, ref_in );
    // Free temporary set
    set_free(def_in);
    set_free(ref_in);
  }
}

References current_defs, current_refs, GEN, inout_statement(), one_trip_do_p, REF, set_dup(), set_free(), and set_union().

Referenced by inout_forloop(), inout_loop(), and inout_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_block()

static void inout_block ( _UNUSED_ statement  st, cons *  sts  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the block
sts	is the list of statement inside the block

loop over statements inside the block

Compute the outs from the ins for this statement

Definition at line 614 of file chains.c.

                                                            {
 
  /* loop over statements inside the block */
  FOREACH( statement, one, sts ) {
    /* Compute the outs from the ins for this statement */
    inout_statement( one );
  }
}

References FOREACH, and inout_statement().

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_call()

static void inout_call ( statement  st, call __attribute__((unused))  c  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the call
c	is the call (unused)

Compute "out" sets

Definition at line 746 of file chains.c.

                                                                        {
  /* Compute "out" sets  */
 
  kill_effects(current_defs,GEN(st));
  set_union( current_defs, GEN( st ), current_defs);
 
  kill_effects(current_refs,GEN(st));
  set_union( current_refs, REF( st ), current_refs);
}

References current_defs, current_refs, GEN, kill_effects(), REF, and set_union().

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_control() [1/2]

static void inout_control ( )

static

Referenced by inout_unstructured().

Here is the caller graph for this function:

inout_control() [2/2]

static void inout_control ( control  ct )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

@description It computes the in and out sets of the structured control graph. This is done by fixed point iteration (see Dragon book, p. 625), except that the in set of CT is not empty (this explains the set_union instead of set_assign in the fixed point computation loop on IN( st )). Once again, the correctness of this modification is not proven.

Parameters

ct	is the control to compute

Prepare "in" sets

Restore out sets

Definition at line 909 of file chains.c.

                                        {
  bool change;
  set d_oldout = MAKE_STATEMENT_SET();
  set d_out = MAKE_STATEMENT_SET();
  set r_oldout = MAKE_STATEMENT_SET();
  set r_out = MAKE_STATEMENT_SET();
  cons *blocs = NIL;
 
 
  ifdebug(2) {
    fprintf( stderr, "Computing DEF_IN and OUT of control %p entering", ct );
    local_print_statement_set( "", DEF_IN( control_statement( ct )) );
  }
 
  CONTROL_MAP( c, {statement st = control_statement( c );
        set_assign( DEF_OUT( st ), GEN( st ));
        set_assign( REF_OUT( st ), REF( st ));
 
        if( c != ct ) {
          set_clear( DEF_IN( st ));
          set_clear( REF_OUT( st ));
        }},
      ct, blocs );
 
  for ( change = true; change; ) {
    ifdebug(3) {
      fprintf( stderr, "Iterating on %p ...\n", ct );
    }
    change = false;
 
    CONTROL_MAP( b,
        { statement st = control_statement( b );
 
          set_clear( d_out );
          set_clear( r_out );
          MAPL( preds, {control pred = CONTROL( CAR( preds ));
                statement pst = control_statement( pred );
 
                set_union( d_out, d_out, DEF_OUT( pst ));
                set_union( r_out, r_out, REF_OUT( pst ));},
              control_predecessors( b ));
          set_union( DEF_IN( st ), DEF_IN( st ), d_out );
          set_union( REF_IN( st ), REF_IN( st ), r_out );
          set_assign( d_oldout, DEF_OUT( st ));
          set_union( DEF_OUT( st ), GEN( st ),DEF_IN( st ));
                     // FIXME set_difference( diff, DEF_IN( st ), KILL( st )));
          set_assign( r_oldout, REF_OUT( st ));
          set_union( REF_OUT( st ), REF( st ), REF_IN( st ));
          change |= (!set_equal_p( d_oldout, DEF_OUT( st )) ||
              !set_equal_p( r_oldout, REF_OUT( st )));
        }, ct, blocs );
  }
 
  CONTROL_MAP( c, {
                   statement st = control_statement( c );
                   /* Prepare "in" sets */
                   set_assign( current_defs, DEF_IN( st ) );
                   set_assign( current_refs, REF_IN( st ) );
 
                   inout_statement( st);
 
                   /* Restore out sets */
                   set_assign( DEF_OUT( st ), current_defs );
                   set_assign( REF_OUT( st ), current_refs );
                  },
      ct, blocs );
  set_free( d_oldout );
  set_free( d_out );
  set_free( r_oldout );
  set_free( r_out );
  gen_free_list( blocs );
 
}

References CAR, CONTROL, CONTROL_MAP, control_predecessors, control_statement, current_defs, current_refs, DEF_IN, DEF_OUT, fprintf(), GEN, gen_free_list(), ifdebug, inout_statement(), local_print_statement_set(), MAKE_STATEMENT_SET, MAPL, NIL, REF, REF_IN, REF_OUT, set_assign(), set_clear(), set_equal_p(), set_free(), and set_union().

Here is the call graph for this function:

inout_forloop()

static void inout_forloop ( statement  st, forloop  fl  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the loop
t	is the loop

Definition at line 735 of file chains.c.

                                                      {
  statement body = forloop_body( fl );
  inout_any_loop( st, body, one_trip_do_p, false );
}

References forloop_body, inout_any_loop(), and one_trip_do_p.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_loop()

static void inout_loop ( statement  st, loop  lo  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the loop
lo	is the loop

Definition at line 710 of file chains.c.

                                                {
  // Try to detect loop executed at least once trivial case
  bool executed_once_p = one_trip_do_p;
  if(!executed_once_p) executed_once_p = loop_executed_at_least_once_p(lo);
 
  inout_any_loop( st, loop_body( lo ), executed_once_p, loop_executed_never_p(lo) );
}

References inout_any_loop(), loop_body, loop_executed_at_least_once_p(), loop_executed_never_p(), and one_trip_do_p.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_statement() [1/2]

static void inout_statement ( )

static

Referenced by inout_any_loop(), inout_block(), inout_control(), inout_test(), and statement_dependence_graph().

Here is the caller graph for this function:

inout_statement() [2/2]

static void inout_statement ( statement  st )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement to compute

Compute Def-Def and Def-Use conflicts from Def_in set

Compute Use-Def conflicts from Ref_in set

Compute "out" sets for the instruction : recursion

The second argument is not used

Definition at line 805 of file chains.c.

                                            {
  instruction i;
  static int indent = 0;
 
  ifdebug(2) {
    pips_debug( 2,
             "%*s> Computing DEF and REF for statement %p (%td %td):\n"
             "current_defs %p, current_refs %p\n",
             indent++,
             "",
             st,
             statement_number( st ),
             statement_ordering( st ),
             current_defs,
             current_refs );
    local_print_statement_set( "DEF_IN", current_defs );
    local_print_statement_set( "REF_IN", current_refs );
  }
  /* Compute Def-Def and Def-Use conflicts from Def_in set */
  vertex statement_vertex = vertex_statement( st );
  cons *effects = load_statement_effects( st );
  SET_FOREACH( effect, defIn, current_defs) {
    add_conflicts( defIn, st, statement_vertex, effects, dd_du );
  }
  /* Compute Use-Def conflicts from Ref_in set */
  SET_FOREACH( effect, refIn, current_refs) {
    add_conflicts( refIn, st, statement_vertex, effects, ud );
  }
 
  ifdebug(3) {
    pips_debug( 3,
             "%*s> After add conflicts for statement %p (%td %td):\n"
             "current_defs %p, current_refs %p\n",
             indent,
             "",
             st,
             statement_number( st ),
             statement_ordering( st ),
             current_defs,
             current_refs );
    local_print_statement_set( "DEF_IN", current_defs );
    local_print_statement_set( "REF_IN", current_refs );
  }
 
  /* Compute "out" sets for the instruction : recursion */
  switch ( instruction_tag( i = statement_instruction( st )) ) {
    case is_instruction_block:
      inout_block( st, instruction_block( i ) );
      break;
    case is_instruction_test:
      inout_test( st, instruction_test( i ) );
      break;
    case is_instruction_loop:
      inout_loop( st, instruction_loop( i ) );
      break;
    case is_instruction_whileloop:
      inout_whileloop( st, instruction_whileloop( i ) );
      break;
    case is_instruction_forloop:
      inout_forloop( st, instruction_forloop( i ) );
      break;
    case is_instruction_call:
      inout_call( st, instruction_call( i ) );
      break;
    case is_instruction_expression:
      /* The second argument is not used */
      inout_call( st, (call) instruction_expression( i ) );
      break;
    case is_instruction_goto:
      pips_internal_error("Unexpected tag %d", i );
      break;
    case is_instruction_unstructured:
      inout_unstructured( st, instruction_unstructured( i ) );
      break;
    default:
      pips_internal_error("Unknown tag %d", instruction_tag(i) );
  }
  ifdebug(2) {
    pips_debug( 2,
             "%*s> Statement %p (%td %td):\n"
             "current_defs %p, current_refs %p\n",
             indent--,
             "",
             st,
             statement_number( st ),
             statement_ordering( st ),
             current_defs,
             current_refs );
    local_print_statement_set( "DEF_OUT", DEF_OUT( st ) );
    local_print_statement_set( "REF_OUT", REF_OUT( st ) );
  }
 
}

References add_conflicts(), current_defs, current_refs, dd_du(), DEF_OUT, ifdebug, inout_block(), inout_call(), inout_forloop(), inout_loop(), inout_test(), inout_unstructured(), inout_whileloop(), instruction_block, instruction_call, instruction_expression, instruction_forloop, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, load_statement_effects(), local_print_statement_set(), pips_debug, pips_internal_error, REF_OUT, SET_FOREACH, statement_instruction, statement_number, statement_ordering, ud(), and vertex_statement().

Here is the call graph for this function:

inout_test()

static void inout_test ( _UNUSED_ statement  s, test  t  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the test
t	is the test

Compute the out for the test

Definition at line 629 of file chains.c.

                                                       {
  statement st = test_true( t );
  statement sf = test_false( t );
 
  // Save DEF and REF
  set def_in = set_dup(current_defs);
  set ref_in = set_dup(current_refs);
 
  /*
   * Compute true path
   */
  inout_statement( st );
 
  // Save DEF and REF
  set def_out = current_defs;
  set ref_out = current_refs;
 
  // Restore DEF and REF
  current_defs = def_in;
  current_refs = ref_in;
 
  /*
   * Compute false path
   */
  inout_statement( sf );
 
  /* Compute the out for the test */
  set_union( current_defs, current_defs, def_out );
  set_union( current_refs, current_refs, ref_out );
 
  // Free temporary set
  set_free(def_out);
  set_free(ref_out);
 
}

References current_defs, current_refs, inout_statement(), set_dup(), set_free(), set_union(), test_false, and test_true.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_unstructured()

static void inout_unstructured ( statement  st, unstructured  u  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the unstructured
u	is the unstructured

Compute "in" sets

Compute the unstructured

Compute "out" sets

Definition at line 762 of file chains.c.

                                                               {
  control c = unstructured_control( u );
  control exit = unstructured_exit( u );
  statement s_exit = control_statement( exit );
 
  /* Compute "in" sets */
  set_assign( DEF_IN( control_statement( c )), current_defs );
  set_assign( REF_IN( control_statement( c )), current_refs );
 
  /* Compute the unstructured */
  inout_control( c );
 
  /* Compute "out" sets */
  if ( set_undefined_p( DEF_OUT( s_exit )) ) {
    list blocs = NIL;
    set ref = MAKE_STATEMENT_SET();
    set empty = MAKE_STATEMENT_SET();
 
    CONTROL_MAP( cc, {
          set_union( ref, ref, REF( control_statement( cc )));
        }, c, blocs );
    set_assign( REF_OUT( st ), ref );
    set_assign( DEF_OUT( st ), empty );
 
    set_free( ref );
    set_free( empty );
    gen_free_list( blocs );
  } else {
    set_assign( DEF_OUT( st ), DEF_OUT( s_exit ) );
    set_assign( REF_OUT( st ), REF_OUT( s_exit ) );
  }
 
  // Exit from unstructured, restore global DEF
  set_assign( current_defs, DEF_OUT( st ) );
  set_assign( current_refs, REF_OUT( st ) );
 
}

References CONTROL_MAP, control_statement, current_defs, current_refs, DEF_IN, DEF_OUT, empty, exit, gen_free_list(), inout_control(), MAKE_STATEMENT_SET, NIL, REF, ref, REF_IN, REF_OUT, set_assign(), set_free(), set_undefined_p, set_union(), unstructured_control, and unstructured_exit.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

inout_whileloop()

static void inout_whileloop ( statement  st, whileloop  wl  )

static

Propagates in sets of ST (which is inherited) to compute the out sets.

Parameters

st	is the statement that hold the loop
t	is the loop

Definition at line 724 of file chains.c.

                                                          {
  statement body = whileloop_body( wl );
  inout_any_loop( st, body, false, false );
}

References inout_any_loop(), and whileloop_body.

Referenced by inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

kill_effects()

static void kill_effects ( set  gen, set  killers  )

static

The genref_xxx functions implement the computation of GEN and REF sets from Aho, Sethi and Ullman "Compilers" (p.

612). This is slightly more complex since we use a structured control graph, thus fixed point computations can be recursively required (the correctness of this is probable, although not proven, as far as I can tell). KILL_STATEMENT updates the KILL set of statement ST on entity LHS. Only effects that modify one reference (i.e., assignments) are killed (see above). Write effects on arrays (see IDXS) don't kill the definitions of the array. Equivalence with non-array entities is managed properly.

Kill the GEN set with a set of KILL effects

Parameters

gen	the set to filter, modified by side effects
killers	the "killer" effects

A killer effect is exact and is a write (environment effects kills !!)

We only kill store effect

We avoid a self killing

Definition at line 244 of file chains.c.

                                               {
    set killed = MAKE_STATEMENT_SET();
    SET_FOREACH(effect,killer,killers) {
        /* A killer effect is exact and is a write (environment effects kills !!) */
        if ( action_write_p(effect_action(killer))
             // these tests are optimizations to avoid redundant tests inside the
             // SET_FOREACH loop;
             // they allow to call first_exact_scalar_effect_certainly_includes_second_effect_p
             // instead of first_effect_certainly_includes_second_effect_p
             // if the latter is enhanced, these tests should be updated accordingly.
             && effect_exact_p(killer) && effect_scalar_p(killer) ) {
            SET_FOREACH(effect,e,gen) {
                /* We only kill store effect */
                if(store_effect_p(e)) {
                    /* We avoid a self killing */
                    if( e != killer
                        && first_exact_scalar_effect_certainly_includes_second_effect_p(killer, e) ) {
                        set_add_element( killed, killed, e );
                    }
                }
            }
            set_difference(gen,gen,killed);
            set_clear(killed);
        }
    }
    set_free(killed);
}

References action_write_p, effect_action, effect_exact_p, effect_scalar_p(), first_exact_scalar_effect_certainly_includes_second_effect_p(), gen(), MAKE_STATEMENT_SET, set_add_element(), set_clear(), set_difference(), SET_FOREACH, set_free(), and store_effect_p().

Referenced by genref_block(), and inout_call().

Here is the call graph for this function:

Here is the caller graph for this function:

load_statement_effects()

static list load_statement_effects ( statement  s )

static

else, flow thru!

FI: I wonder about iorgch; I would expect the same kind of stuff for the case expression, which may also hide a call to a user defined function, for instance via a for loop construct.

Definition at line 1276 of file chains.c.

                                                  {
  instruction inst = statement_instruction( s );
  tag t = instruction_tag( inst );
  tag call_t;
  list le = NIL;
 
  switch ( t ) {
    case is_instruction_call:
      call_t
          = value_tag(entity_initial(call_function( instruction_call( inst ))));
      if ( iorgch && ( call_t == is_value_code ) ) {
        list l_in = load_statement_in_regions( s );
        list l_out = load_statement_out_regions( s );
        le = gen_append( l_in, l_out );
        break;
      }
      /* else, flow thru! */
      _FALLTHROUGH_;
    case is_instruction_expression:
      /* FI: I wonder about iorgch; I would expect the same kind of
       stuff for the case expression, which may also hide a call to
       a user defined function, for instance via a for loop
       construct. */
    case is_instruction_block:
    case is_instruction_test:
    case is_instruction_loop:
    case is_instruction_whileloop:
    case is_instruction_forloop:
    case is_instruction_unstructured:
      le = load_proper_rw_effects_list( s );
      break;
    case is_instruction_goto:
      pips_internal_error("Go to statement in CODE data structure %d", t );
      break;
    default:
      pips_internal_error("Unknown tag %d", t );
  }
 
  return le;
}

References _FALLTHROUGH_, call_function, entity_initial, gen_append(), instruction_call, instruction_tag, iorgch, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, is_value_code, load_proper_rw_effects_list(), load_statement_in_regions(), load_statement_out_regions(), NIL, pips_internal_error, statement_instruction, and value_tag.

Referenced by add_conflicts(), genref_one_statement(), init_one_statement(), and inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

local_print_statement_set()

static void local_print_statement_set ( string  msg, set  s  )

static

Access functions for debug only.

displays on stderr, the MSG followed by the set of statement numbers associated to effects present in the set S.

Parameters

msg	a string to be display at the beginning
s	the set of effects to display

Definition at line 144 of file chains.c.

                                                           {
  fprintf( stderr, "\t%s ", msg );
  SET_FOREACH( effect, eff, s) {
    fprintf( stderr,
             ",%p (%td) ",
             eff,
             statement_number( (statement)hash_get(effects2statement,eff) ) );
    print_effect( (effect) eff );
  }
  fprintf( stderr, "\n" );
}

References effects2statement, fprintf(), hash_get(), print_effect, SET_FOREACH, and statement_number.

Referenced by genref_statement(), inout_control(), and inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

mask_effects()

static void mask_effects ( set  s, list  l  )

static

MASK_EFFECTS masks the effects in S according to the locals L.

Parameters

s	the set of effects
l	the locals to mask

Register which one we have to mask

Do the masking

We free because we are good programmers and we don't leak ;-)

Definition at line 331 of file chains.c.

                                          {
  cons *to_mask = NIL;
  /*
   * Loop over effect and check if they affect a local variable
   * We mask only read effects (FIXME : why ?)
   */
  SET_FOREACH(effect, f, s) {
    action a = effect_action( f );
 
    if ( action_read_p( a ) ) {
      FOREACH( entity, e, l )
      {
        if ( effect_may_read_or_write_memory_paths_from_entity_p( f, e ) ) {
          /* Register which one we have to mask */
          to_mask = CONS( effect, f, to_mask );
        }
      }
    }
  }
  /* Do the masking */
  FOREACH( effect, f, to_mask ) {
    set_del_element( s, s, (char *) f );
  }
 
  /* We free because we are good programmers and we don't leak ;-) */
  gen_free_list( to_mask );
}

References action_read_p, CONS, effect_action, effect_may_read_or_write_memory_paths_from_entity_p(), f(), FOREACH, gen_free_list(), NIL, set_del_element(), and SET_FOREACH.

Referenced by genref_any_loop(), and genref_block().

Here is the call graph for this function:

Here is the caller graph for this function:

pushnew_conflict()

static cons* pushnew_conflict ( effect  fin, effect  fout, cons *  cfs  )

static

adds the conflict FIN->FOUT in the list CFS @description adds the conflict FIN->FOUT in the list CFS (if it's not already there, and apparently even if it's already there for performance reason...).

Parameters

fin	is the incoming effect
fout	is the sink effect
cfs	is the list of conflict to update

FI: This is a bottleneck for large modules with lots of callees and long effect lists. Let's assume that the pairs (fin, fout) are always unique because the effects are sets.

create the conflict

Add the conflict to the list

Definition at line 993 of file chains.c.

                                                                    {
  conflict c;
 
  /* FI: This is a bottleneck for large modules with lots of callees and
   long effect lists. Let's assume that the pairs (fin, fout) are
   always unique because the effects are sets. */
 
  /*
   MAPL( cs, {
   conflict c = CONFLICT( CAR( cs )) ;
 
   if( conflict_source( c )==fin && conflict_sink( c )==fout ) {
   return( cfs ) ;
   }
   }, cfs ) ;
   */
 
  /* create the conflict */
  c = make_conflict( fin, fout, cone_undefined );
  ifdebug(2) {
    fprintf( stderr,
             "Adding %s->%s\n",
             entity_name( effect_entity( fin )),
             entity_name( effect_entity( fout )) );
  }
  /* Add the conflict to the list */
  return ( CONS( CONFLICT, c, cfs ) );
}

References cone_undefined, CONFLICT, CONS, effect_entity(), entity_name, fprintf(), ifdebug, and make_conflict().

Referenced by add_conflicts().

Here is the call graph for this function:

Here is the caller graph for this function:

region_chains()

bool region_chains

(

const string

module_name

)

Phase to compute atomic chains based on array regions.

Parameters

module_name

odule_name

Definition at line 1449 of file chains.c.

                                             {
  return chains( module_name, USE_REGIONS );
}

References chains(), module_name(), and USE_REGIONS.

Here is the call graph for this function:

reset_effects()

static void reset_effects ( )

static

Some forward declarations.

Definition at line 1379 of file chains.c.

                            {
  reset_proper_rw_effects( );
  if ( iorgch ) {
    reset_in_effects( );
    reset_out_effects( );
  }
}

References iorgch, reset_in_effects(), reset_out_effects(), and reset_proper_rw_effects().

Referenced by chains().

Here is the call graph for this function:

Here is the caller graph for this function:

set_effects()

static void set_effects ( char *  module_name, enum chain_type  use  )

static

Select the type of effects used to compute dependence chains.

Definition at line 1318 of file chains.c.

                                                                  {
  switch ( use ) {
 
#ifdef HAVE_PIPS_effects_simple_LIBRARY
 
    case USE_PROPER_EFFECTS:
      rgch = false;
      iorgch = false;
      string pe =
          db_get_memory_resource( DBR_PROPER_EFFECTS, module_name, true );
      set_proper_rw_effects( (statement_effects) pe );
      break;
 
#endif // HAVE_PIPS_effects_simple_LIBRARY
 
#ifdef HAVE_PIPS_effects_convex_LIBRARY
 
      /* In fact, we use proper regions only; proper regions of
       * calls are similar to regions, except for expressions given
       * as arguments, whose regions are simply appended to the list
       * (non convex hull).  For simple statements (assignments),
       * proper regions contain the list elementary regions (there
       * is no summarization, i.e no convex hull).  For loops and
       * tests, proper regions contain the elements accessed in the
       * tests and loop range. BC.
       */
    case USE_REGIONS:
      rgch = true;
      iorgch = false;
      string pr =
          db_get_memory_resource( DBR_PROPER_REGIONS, module_name, true );
      set_proper_rw_effects( (statement_effects) pr );
      break;
 
      /* For experimental purpose only */
    case USE_IN_OUT_REGIONS:
      rgch = false;
      iorgch = true;
      /* Proper regions */
      string iopr = db_get_memory_resource( DBR_PROPER_REGIONS,
                                            module_name,
                                            true );
      set_proper_rw_effects( (statement_effects) iopr );
 
      /* in regions */
      string ir = db_get_memory_resource( DBR_IN_REGIONS, module_name, true );
      set_in_effects( (statement_effects) ir );
 
      /* out regions */
      string or = db_get_memory_resource( DBR_OUT_REGIONS, module_name, true );
      set_out_effects( (statement_effects) or );
      break;
 
#endif // HAVE_PIPS_effects_convex_LIBRARY
 
    default:
      pips_internal_error("ill. parameter use = %d", use );
  }
 
}

References db_get_memory_resource(), iorgch, module_name(), pips_internal_error, rgch, set_in_effects(), set_out_effects(), set_proper_rw_effects(), USE_IN_OUT_REGIONS, USE_PROPER_EFFECTS, and USE_REGIONS.

Referenced by chains().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_dependence_graph()

graph statement_dependence_graph

(

statement

s

)

Compute from a given statement, the dependency graph.

cproto-generated files

@description Statement s is assumed "controlized", i.e. GOTO have been replaced by unstructured.

FIXME FI: this function is bugged. As Pierre said, you have to start with an unstructured for the use-def chain computation to be correct.

Initialize some properties

Initialize global hashtables

Initialize the dg

Initialize data structures for all the statements

It recursively initializes the sets of gens, ins and outs for the statements that appear in st. Note that not only call statements are there, but also enclosing statements (e.g, blocks and loops).

Compute genref phase

Compute inout phase and create conflicts

Definition at line 1218 of file chains.c.

                                                {
  /* Initialize some properties */
  one_trip_do_p = get_bool_property( "ONE_TRIP_DO" );
  keep_read_read_dependences_p = get_bool_property( "KEEP_READ_READ_DEPENDENCE" );
  mask_effects_p = get_bool_property("CHAINS_MASK_EFFECTS");
  dataflow_dependence_only_p = get_bool_property("CHAINS_DATAFLOW_DEPENDENCE_ONLY");
 
  /* Initialize global hashtables */
  effects2statement = hash_table_make( hash_pointer, 0 );
  Gen = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Ref = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Def_in = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Def_out = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Ref_in = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Ref_out = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  Vertex_statement = hash_table_make( hash_pointer, INIT_STATEMENT_SIZE );
  current_defs = set_make(set_pointer);
  current_refs = set_make(set_pointer);
 
  /* Initialize the dg */
  dg = make_graph( NIL );
 
  /* Initialize data structures for all the statements
 
   It recursively initializes the sets of gens, ins and outs for
   the statements that appear in st. Note that not only call statements are
   there, but also enclosing statements (e.g, blocks and loops). */
  gen_recurse(s, statement_domain, init_one_statement, gen_null);
 
  /* Compute genref phase */
  genref_statement( s );
 
  /* Compute inout phase and create conflicts*/
  inout_statement( s );
 
#define TABLE_FREE(t)                                                   \
  {HASH_MAP( k, v, {set_free( (set)v ) ;}, t ) ; hash_table_free(t);}
 
  TABLE_FREE(Gen);
  TABLE_FREE(Ref);
  TABLE_FREE(Def_in);
  TABLE_FREE(Def_out);
  TABLE_FREE(Ref_in);
  TABLE_FREE(Ref_out);
 
  hash_table_free( Vertex_statement );
  hash_table_free( effects2statement );
 
  set_free(current_defs);
  set_free(current_refs);
 
  return ( dg );
}

References current_defs, current_refs, dataflow_dependence_only_p, Def_in, Def_out, dg, effects2statement, Gen, gen_null(), gen_recurse, genref_statement(), get_bool_property(), hash_pointer, hash_table_free(), hash_table_make(), init_one_statement(), INIT_STATEMENT_SIZE, inout_statement(), keep_read_read_dependences_p, make_graph(), mask_effects_p, NIL, one_trip_do_p, Ref, Ref_in, Ref_out, set_free(), set_make(), set_pointer, statement_domain, TABLE_FREE, and Vertex_statement.

Referenced by chains().

Here is the call graph for this function:

Here is the caller graph for this function:

ud()

static bool ud ( effect  fin, effect  fout  )

static

UD detects Use/Def conflicts between effects FIN and FOUT.

Definition at line 1038 of file chains.c.

                                          {
  return ( action_read_p( effect_action( fin ))
      && ( action_write_p( effect_action( fout )) || keep_read_read_dependences_p ) );
}

References action_read_p, action_write_p, effect_action, and keep_read_read_dependences_p.

Referenced by add_conflicts(), create_parameters_h(), and inout_statement().

Here is the caller graph for this function:

vertex_statement()

static vertex vertex_statement ( statement  st )

static

Returns

the vertex associated to the statement ST in the dependence graph DG.

Definition at line 159 of file chains.c.

                                               {
  vertex v = (vertex) hash_get( Vertex_statement, (char *) st );
  pips_assert( "vertex_statement", v != (vertex)HASH_UNDEFINED_VALUE );
  return ( v );
}

References hash_get(), HASH_UNDEFINED_VALUE, pips_assert, and Vertex_statement.

Referenced by add_conflicts(), and inout_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

current_defs

set current_defs

static

current_defs is the set of DEF at the current point of the computation

Definition at line 100 of file chains.c.

Referenced by inout_any_loop(), inout_call(), inout_control(), inout_statement(), inout_test(), inout_unstructured(), and statement_dependence_graph().

current_refs

set current_refs

static

Definition at line 101 of file chains.c.

Referenced by inout_any_loop(), inout_call(), inout_control(), inout_statement(), inout_test(), inout_unstructured(), and statement_dependence_graph().

dataflow_dependence_only_p

bool dataflow_dependence_only_p

static

Definition at line 133 of file chains.c.

Referenced by dd_du(), and statement_dependence_graph().

Def_in

hash_table Def_in

static

Def_in maps each statement to the statements that are in-coming the statement It's only used for unstructured, current_defs is used for structured parts.

Definition at line 105 of file chains.c.

Referenced by init_one_statement(), and statement_dependence_graph().

Def_out

hash_table Def_out

static

Def_out maps each statement to the statements that are out-coming the statement It's only used for unstructured, current_defs is used for structured parts.

Definition at line 110 of file chains.c.

Referenced by init_one_statement(), and statement_dependence_graph().

dg

graph dg

static

dg is the dependency graph ; FIXME : should not be static global ?

Definition at line 124 of file chains.c.

Referenced by array_dfg(), bottom_level(), check_tiling_legality(), comEngine_distribute(), comEngine_distribute_code(), comEngine_feasability(), defs_elim_of_assign_call(), defs_elim_of_statement(), defs_elim_of_unstructured(), do_reduction_detection(), do_reduction_propagation(), do_redundant_load_store_elimination(), do_scalar_renaming(), forward_substitute(), freia_mppa_compile_calls(), fs_filter(), full_parallel_loop_nest_p(), get_vertex_of_statement(), if_conversion_compact(), if_conversion_compact_stats(), init_one_statement(), initialization(), instruction_to_wp65_code(), invariant_code_motion(), loop_nest_to_local_variables(), loop_nest_to_wp65_code(), module_to_wp65_modules(), mppa_call_helper(), mppa_dag_maybe_split_instrs_cmd(), mppa_dag_split(), parse_instrumented_file(), phrase_remove_dependences(), print_dependence_or_chains_graph(), print_dot_dependence_or_chains_graph(), print_filtered_dg_or_dvdg(), print_loopnest_dependence_cone(), reference_conflicting_p(), reference_conflicting_test_and_update(), sc_delimiter(), sc_get_port_id(), sc_kernel_specific_agent(), scalar_renaming(), search_parallel_loops(), sigmac_name_instances(), sigmac_params_decl(), simplify_dg(), statement_dependence_graph(), statements_to_successors(), t_level(), top_level(), wp65(), and xml_Chains().

effects2statement

hash_table effects2statement

static

Mapping from effects to the associated statement.

Definition at line 89 of file chains.c.

Referenced by add_conflicts(), genref_one_statement(), init_one_statement(), local_print_statement_set(), and statement_dependence_graph().

Gen

hash_table Gen

static

Gen maps each statement to the effects it generates.

Definition at line 92 of file chains.c.

Referenced by init_one_statement(), and statement_dependence_graph().

iorgch

bool iorgch = false

static

Definition at line 1274 of file chains.c.

Referenced by load_statement_effects(), reset_effects(), and set_effects().

keep_read_read_dependences_p

bool keep_read_read_dependences_p

static

Definition at line 131 of file chains.c.

Referenced by statement_dependence_graph(), and ud().

mask_effects_p

bool mask_effects_p

static

Definition at line 132 of file chains.c.

Referenced by genref_any_loop(), genref_block(), and statement_dependence_graph().

one_trip_do_p

bool one_trip_do_p

static

Some properties.

Definition at line 130 of file chains.c.

Referenced by genref_forloop(), genref_loop(), genref_whileloop(), inout_any_loop(), inout_forloop(), inout_loop(), and statement_dependence_graph().

Ref

hash_table Ref

static

Refs maps each statement to the effects it references.

Definition at line 96 of file chains.c.

Referenced by AllocateDadStruct(), GetRefTemp(), init_one_statement(), statement_dependence_graph(), TransRefTemp(), and update_indices_for_local_computation().

Ref_in

hash_table Ref_in

static

Ref_in maps each statement to the effects that are in-coming the statement It's only used for unstructured, current_refs is used for structured parts.

Definition at line 115 of file chains.c.

Referenced by init_one_statement(), and statement_dependence_graph().

Ref_out

hash_table Ref_out

static

Ref_out maps each statement to the effects that are out-coming the statement It's only used for unstructured, current_refs is used for structured parts.

Definition at line 120 of file chains.c.

Referenced by init_one_statement(), and statement_dependence_graph().

rgch

bool rgch = false

static

functions for effects maps

Definition at line 1273 of file chains.c.

Referenced by set_effects().

Vertex_statement

hash_table Vertex_statement

static

Vertex_statement maps each statement to its vertex in the dependency graph.

Definition at line 127 of file chains.c.

Referenced by init_one_statement(), statement_dependence_graph(), and vertex_statement().