icm.c File Reference

#include "local.h"
#include "prettyprint.h"
#include "effects-generic.h"
#include "effects-simple.h"

Include dependency graph for icm.c:

Go to the source code of this file.

Macros
#define	NB_SIMPLIFY_PASSES   1
	Set to 2 if we want to simplify in two passes. More...
#define	FLOW_DEPENDANCE   1
#define	ANTI_DEPENDANCE   2
#define	OUTPUT_DEPENDANCE   4
#define	INPUT_DEPENDANCE   8
#define	ALL_DEPENDANCES   (FLOW_DEPENDANCE|ANTI_DEPENDANCE|OUTPUT_DEPENDANCE)

Functions
statement	vertex_to_statement (vertex v)
	Vertex_to_statement looks for the statement that is pointed to by vertex v. More...
void	dump_sef (statement_effects se)
	icm.c More...
static void	prettyprint_conflict (FILE *fd, conflict c)
static void	prettyprint_successor (FILE *fd, successor su)
static void	prettyprint_vertex (FILE *fd, vertex v)
void	print_list_entities (list l)
static set	vertices_to_statements (list vl, set ss)
	of statement More...
static set	invariant_vertex_to_invariant_entities (vertex v, set rs)
	of entity More...
static bool	statement_mark (statement s)
static bool	loop_level_in (loop l)
static void	loop_level_out (__attribute__((unused)) loop l)
static bool	action_dependance_p (conflict c, int dependance_type)
static bool	dependance_vertices_p (vertex v1, vertex v2, int dependance_type, int level)
	Test the existence of a given dependence between two vertices v1, v2. More...
static bool	exist_non_self_dependance_from_vertex_p (vertex v, int dependance_type, int level)
static list	remove_dependance_from_levels (list levels, int level_min, int level_max)
	of level More...
static list	remove_dependance_from_conflicts (list conflicts, int dependance_type, int level_min, int level_max)
	of conflict More...
static list	remove_dependances_from_successors (list successors, vertex v2, int dependance_type, int level_min, int level_max)
	of successor More...
static void	remove_dependance (vertex v1, vertex v2, int dependance_type, int level_min, int level_max)
static bool	common_ignore_this_vertex (set region, vertex v)
static bool	icm_ignore_this_successor (vertex v, set region, successor su, int level)
static bool	invariant_ignore_this_successor (vertex v, set region, successor su, int level)
static bool	statement_depend_of_indices_p (statement st, list indices, int level)
static bool	inv_entity_filter (entity e)
static bool	ref_flt (reference r)
static bool	expressions_invariant_p (list le)
static bool	vertex_partially_invariant_p (vertex v, __attribute__((unused)) graph g, __attribute__((unused)) int level, __attribute__((unused)) set invariant)
static bool	vertex_invariant_p (vertex v, graph g, int level, set region, set invariant)
static void	SimplifyInvariantVertex (vertex v, set region, int level)
static graph	DoInvariantsStatements (list lsccs, graph g, set region, int level, set partially_invariant)
static bool	vertex_redundant_p (vertex v, __attribute__((unused)) graph g, int level, set region, set partially_invariant, set redundant)
static void	SimplifyRedundantVertex (vertex v, set region, int level)
static graph	DoRedundantsStatements (list lsccs, graph g, set region, int level, set partially_invariant)
static graph	SimplifyGraph (graph g, set region, int level, unsigned int count)
static graph	SupressDependances (graph g, set region, int level, unsigned int count)
static bool	does_it_depend (statement s)
	Set whether s depends from enclosing indices. More...
static bool	push_depending_index (loop l)
static void	pop_depending_index (loop l)
static bool	drop_it (loop l)
static expression	compute_final_index_value (expression m1, expression m2, expression m3)
static bool	icm_loop_rwt (loop l)
static void	drop_dummy_loops (statement s)
static statement	icm_codegen (statement stat, graph g, set region, int level, bool task_parallelize_p)
bool	invariant_code_motion (const char *module_name)
	Phase that hoists loop invariant code out of loops. More...

Variables
static int	reference_level =0
static bool	expression_invariant = false
static set	invariant_entities = set_undefined
	of entity More...
static list	indices = NIL
static int	depth = 0
static list	depending_indices
	of entity More...
static bool	it_depends

Macro Definition Documentation

ALL_DEPENDANCES

#define ALL_DEPENDANCES   (FLOW_DEPENDANCE|ANTI_DEPENDANCE|OUTPUT_DEPENDANCE)

Definition at line 56 of file icm.c.

ANTI_DEPENDANCE

#define ANTI_DEPENDANCE   2

Definition at line 53 of file icm.c.

FLOW_DEPENDANCE

#define FLOW_DEPENDANCE   1

Definition at line 52 of file icm.c.

INPUT_DEPENDANCE

#define INPUT_DEPENDANCE   8

Definition at line 55 of file icm.c.

NB_SIMPLIFY_PASSES

#define NB_SIMPLIFY_PASSES   1

Set to 2 if we want to simplify in two passes.

Definition at line 49 of file icm.c.

OUTPUT_DEPENDANCE

#define OUTPUT_DEPENDANCE   4

Definition at line 54 of file icm.c.

Function Documentation

action_dependance_p()

static bool action_dependance_p ( conflict  c, int  dependance_type  )

static

Definition at line 258 of file icm.c.

{
    action s = effect_action(conflict_source(c)) ;
    action k = effect_action(conflict_sink(c)) ;
 
    return (((dependance_type & FLOW_DEPENDANCE) &&
            ((action_write_p(s) && action_read_p(k)))) ||
            ((dependance_type & ANTI_DEPENDANCE) &&
            ((action_read_p(s) && action_write_p(k)))) ||
            ((dependance_type & OUTPUT_DEPENDANCE) &&
            ((action_write_p(s) && action_write_p(k)))) ||
            ((dependance_type & INPUT_DEPENDANCE) &&
            ((action_read_p(s) && action_read_p(k)))));
}

References action_read_p, action_write_p, ANTI_DEPENDANCE, conflict_sink, conflict_source, effect_action, FLOW_DEPENDANCE, INPUT_DEPENDANCE, and OUTPUT_DEPENDANCE.

Referenced by dependance_vertices_p(), and remove_dependance_from_conflicts().

Here is the caller graph for this function:

common_ignore_this_vertex()

static bool common_ignore_this_vertex ( set  region, vertex  v  )

static

Parameters

region

of statement

Definition at line 536 of file icm.c.

{
    return(!set_belong_p(region, (char *) vertex_to_statement(v)));
}

References region, set_belong_p(), and vertex_to_statement().

Referenced by icm_ignore_this_successor(), invariant_ignore_this_successor(), SimplifyGraph(), SimplifyInvariantVertex(), SimplifyRedundantVertex(), and SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_final_index_value()

static expression compute_final_index_value ( expression  m1, expression  m2, expression  m3  )

static

max of (val_e2, 0)

memory leak

Definition at line 1254 of file icm.c.

{
    expression result;
    expression E0 = make_op_exp("-", m2, copy_expression(m1));
    expression E1 = make_op_exp("+", E0, copy_expression(m3));
    expression E2 = make_op_exp("/", E1, copy_expression(m3));
 
    if (expression_constant_p(E2)) {
        int val_E2 = expression_to_int(E2);
 
        /* max of (val_e2, 0) */
        if (val_E2 > 0) {
            expression E3 = make_op_exp("*", E2, m3);
            result = make_op_exp("+", E3, m1);
        }
        else {
            result = m1;
        free_expression(m3);
        }
    }
    else {
        expression zero = int_to_expression(0);
        expression p_int, E3, E4;
 
        p_int = MakeUnaryCall(entity_intrinsic(INT_GENERIC_CONVERSION_NAME), 
                              E2);
 
        E3 = MakeBinaryCall(entity_intrinsic(MAX_OPERATOR_NAME),
                            p_int, 
                            zero);
        E4 = make_op_exp("*", E3, m3);
        result = make_op_exp("+", m1, E4);
    }
 
    /* memory leak */
 
    return result;
}

References copy_expression(), entity_intrinsic(), expression_constant_p(), expression_to_int(), free_expression(), INT_GENERIC_CONVERSION_NAME, int_to_expression(), make_op_exp(), MakeBinaryCall(), MakeUnaryCall(), and MAX_OPERATOR_NAME.

Referenced by icm_loop_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

dependance_vertices_p()

static bool dependance_vertices_p ( vertex  v1, vertex  v2, int  dependance_type, int  level  )

static

Test the existence of a given dependence between two vertices v1, v2.

Note:

• dependance_type is a bitfield which contains the kind of dependence,
• level is the minimum level wanted.

Definition at line 282 of file icm.c.

{
  ifdebug(9) {
    debug(9, "dependance_vertices_p", "");
 
    if (dependance_type & FLOW_DEPENDANCE) fprintf(stderr, "F ");
    if (dependance_type & ANTI_DEPENDANCE) fprintf(stderr, "A ");
    if (dependance_type & OUTPUT_DEPENDANCE) fprintf(stderr, "O ");
    if (dependance_type & INPUT_DEPENDANCE) fprintf(stderr, "I ");
    fprintf(stderr, "dep. at level >= %d ", level);
    fprintf(stderr,
        "between %02td and %02td ? ",
        statement_number(vertex_to_statement(v1)),
        statement_number(vertex_to_statement(v2)));
  }
 
  MAP(SUCCESSOR, su, {
      vertex s = successor_vertex(su);
      if (s == v2) {
        MAP(CONFLICT, c, {
            if (conflict_cone(c) != cone_undefined) {
              MAP(INT, l, {
                  if (l >= level) {
                    if (action_dependance_p(c, dependance_type))
                    {
                      ifdebug(9) { fprintf(stderr, "yes\n"); }
                      return true;
                    }
                  }
              }, cone_levels(conflict_cone(c)));
            }
        }, dg_arc_label_conflicts(successor_arc_label(su)));
      }
  }, vertex_successors(v1));
 
  ifdebug(9) { fprintf(stderr, "no\n"); }
  return false;
}

References action_dependance_p(), ANTI_DEPENDANCE, cone_levels, cone_undefined, CONFLICT, conflict_cone, debug(), dg_arc_label_conflicts, FLOW_DEPENDANCE, fprintf(), ifdebug, INPUT_DEPENDANCE, INT, level, MAP, OUTPUT_DEPENDANCE, statement_number, SUCCESSOR, successor_arc_label, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by exist_non_self_dependance_from_vertex_p(), icm_ignore_this_successor(), invariant_ignore_this_successor(), SimplifyInvariantVertex(), SimplifyRedundantVertex(), vertex_invariant_p(), and vertex_redundant_p().

Here is the call graph for this function:

Here is the caller graph for this function:

does_it_depend()

static bool does_it_depend ( statement  s )

static

Set whether s depends from enclosing indices.

Definition at line 1202 of file icm.c.

{
    it_depends |= statement_depend_of_indices_p(s, depending_indices, 0);
    if (it_depends) gen_recurse_stop(NULL);
    return true;
}

References depending_indices, gen_recurse_stop(), it_depends, and statement_depend_of_indices_p().

Referenced by drop_it().

Here is the call graph for this function:

Here is the caller graph for this function:

DoInvariantsStatements()

static graph DoInvariantsStatements ( list  lsccs, graph  g, set  region, int  level, set  partially_invariant  )

static

of statement

of vertex

Group of vertices : all are variants

One statement...

which is invariant

Added to the list

Invariant is partially invariant...

NL: I can't explain why we have to add the declaration statement as an invariant statement, but it's seem that it work, and permit some optimizations...

Added to the list

Invariant is partially invariant...

NL: I'm not totally sure of the explanation I propose below The variable declared inside the loop can be consider as invariant variable because there values only be important inside the loop and not outside. so from the outside of the loop these variables doesn't exist and so can be consider as invariant?

Parameters

lsccs	of scc
region	of statement
partially_invariant	of statement

Definition at line 848 of file icm.c.

{
  set /* of statement */ invariant = set_make(set_pointer);
 
  FOREACH(SCC, s, lsccs) {
    list /* of vertex */ lv = scc_vertices(s);
 
    if (gen_length(lv) > 1) {
      /* Group of vertices : all are variants */
    }
    else {
      /* One statement... */
      vertex v = VERTEX(CAR(lv));
      statement st = vertex_to_statement(v);
 
      if (!declaration_statement_p(st)) {
        if (vertex_invariant_p(v, g, level, region, invariant)) {
          /* which is invariant */
          SimplifyInvariantVertex(v, region, level);
 
          /* Added to the list */
          invariant = set_add_element(invariant,
              invariant,
              (char *) st);
 
          /* Invariant is partially invariant... */
          partially_invariant = set_add_element(partially_invariant,
              partially_invariant,
              (char *) st);
 
          invariant_entities =
              invariant_vertex_to_invariant_entities(v,
                  invariant_entities);
 
        }
        else if (vertex_partially_invariant_p(v, g, level, invariant)) {
          partially_invariant =
              set_add_element(partially_invariant,
                  partially_invariant,
                  (char *) st);
        }
      }
      else {
        //If it's an declaration, so we work on environment domain
        // NL: It's a workaround, and not totally sure that it always work, not enough test case
 
        /* NL: I can't explain why we have to add the declaration statement
         *     as an invariant statement, but it's seem that it work,
         *     and permit some optimizations...
         */
        /* Added to the list */
        invariant = set_add_element(invariant,
            invariant,
            (char *) st);
 
        /* Invariant is partially invariant... */
        partially_invariant = set_add_element(partially_invariant,
            partially_invariant,
            (char *) st);
 
        /* NL: I'm not totally sure of the explanation I propose below
         *     The variable declared inside the loop can be consider as invariant variable
         *     because there values only be important inside the loop and not outside.
         *     so from the outside of the loop these variables doesn't exist and
         *     so can be consider as invariant?
         */
        invariant_entities =
            invariant_vertex_to_invariant_entities(v,
                invariant_entities);
      }
    }
  }
 
  set_free(invariant);
 
  return g;
}

References CAR, declaration_statement_p(), FOREACH, gen_length(), invariant_entities, invariant_vertex_to_invariant_entities(), level, region, SCC, scc_vertices, set_add_element(), set_free(), set_make(), set_pointer, SimplifyInvariantVertex(), VERTEX, vertex_invariant_p(), vertex_partially_invariant_p(), and vertex_to_statement().

Referenced by SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

DoRedundantsStatements()

static graph DoRedundantsStatements ( list  lsccs, graph  g, set  region, int  level, set  partially_invariant  )

static

of statement

of vertex

Group of vertices : all are no redundant

One statement...

which is redundant

Parameters

lsccs	of scc
region	of statement
partially_invariant	of statement

Definition at line 1045 of file icm.c.

{
  set /* of statement */ redundant = set_make(set_pointer);
 
  MAP(SCC, s, {
      list /* of vertex */ lv = scc_vertices(s);
 
      if (gen_length(lv) > 1) {
        /* Group of vertices : all are no redundant */
      }
      else {
        /* One statement... */
        vertex v = VERTEX(CAR(lv));
        statement st = vertex_to_statement(v);
 
        if (set_belong_p(partially_invariant, (char *) st)) {
          if (vertex_redundant_p(v, g, level,
              region,
              partially_invariant,
              redundant)) {
            /* which is redundant */
            SimplifyRedundantVertex(v, region, level);
 
            redundant = set_add_element(redundant,
                redundant,
                (char *) st);
          }
        }
      }
  }, lsccs);
 
  set_free(redundant);
 
  return g;
}

References CAR, gen_length(), level, MAP, redundant(), region, SCC, scc_vertices, set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, SimplifyRedundantVertex(), VERTEX, vertex_redundant_p(), and vertex_to_statement().

Referenced by SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

drop_dummy_loops()

static void drop_dummy_loops ( statement  s )

static

WARNING : We must recompute proper_effects for the program !!! So we directly call the pass !!!!!

Definition at line 1350 of file icm.c.

{
  /* WARNING :
   * We must recompute proper_effects for the program !!!
   * So we directly call the pass !!!!!
   */
  set_methods_for_proper_simple_effects();
  init_proper_rw_effects();
  proper_effects_of_module_statement(s);
 
 
  make_stmt_stack();
 
  gen_multi_recurse(s,
      statement_domain, stmt_filter, stmt_rewrite,
      loop_domain, icm_loop_rwt, gen_null,
      NULL);
 
  free_stmt_stack();
  reset_proper_rw_effects();
  generic_effects_reset_all_methods();
}

References gen_multi_recurse(), gen_null(), generic_effects_reset_all_methods(), icm_loop_rwt(), init_proper_rw_effects(), loop_domain, proper_effects_of_module_statement(), reset_proper_rw_effects(), set_methods_for_proper_simple_effects(), statement_domain, stmt_filter(), and stmt_rewrite().

Referenced by icm_codegen().

Here is the call graph for this function:

Here is the caller graph for this function:

drop_it()

static bool drop_it ( loop  l )

static

assert?

Definition at line 1228 of file icm.c.

{
  if (execution_parallel_p(loop_execution(l)))
  {
    depending_indices = NIL;
    it_depends = false;
    gen_multi_recurse(l,
        statement_domain, does_it_depend, gen_null,
        loop_domain, push_depending_index, pop_depending_index,
        NULL);
    depending_indices = NIL; /* assert? */
    return !it_depends;
  }
 
  return false;
}

References depending_indices, does_it_depend(), execution_parallel_p, gen_multi_recurse(), gen_null(), it_depends, loop_domain, loop_execution, NIL, pop_depending_index(), push_depending_index(), and statement_domain.

Referenced by icm_loop_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

dump_sef()

void dump_sef

(

statement_effects

se

)

icm.c

Parameters

se

e

Definition at line 75 of file icm.c.

{
    fprintf(stderr, "\n");
    STATEMENT_EFFECTS_MAP(s, e, {
        fprintf(stderr, 
                "%02td (%p) -> (%td) : ", 
                statement_number(s), 
                s,
                gen_length(effects_effects(e)));
 
        MAP(EFFECT, e, { 
            print_words(stderr, words_effect(e));
            fprintf(stderr, "(%p), ", e);
        }, effects_effects(e));
        
        fprintf(stderr, "\n");
    }, se);
}

References EFFECT, effects_effects, fprintf(), gen_length(), MAP, print_words(), STATEMENT_EFFECTS_MAP, statement_number, and words_effect().

Here is the call graph for this function:

exist_non_self_dependance_from_vertex_p()

static bool exist_non_self_dependance_from_vertex_p ( vertex  v, int  dependance_type, int  level  )

static

Definition at line 327 of file icm.c.

{
    MAP(SUCCESSOR, su, {
        vertex y = successor_vertex(su);
        if (v != y) {
            if (dependance_vertices_p(v, y, dependance_type, level))
                return true;
        }
    }, vertex_successors(v));
 
    return false;
}

References dependance_vertices_p(), level, MAP, SUCCESSOR, successor_vertex, and vertex_successors.

Referenced by SimplifyInvariantVertex(), and SimplifyRedundantVertex().

Here is the call graph for this function:

Here is the caller graph for this function:

expressions_invariant_p()

static bool expressions_invariant_p ( list  le )

static

Parameters

le	of expression

Definition at line 648 of file icm.c.

{
    MAP(EXPRESSION, exp, {
        expression_invariant = true;
 
        gen_recurse(exp, reference_domain, ref_flt, gen_null);
 
        if (!expression_invariant) {
            return false;
        }
    }, le);
 
    return true;
}

References exp, EXPRESSION, expression_invariant, gen_null(), gen_recurse, MAP, ref_flt(), and reference_domain.

Referenced by vertex_partially_invariant_p().

Here is the call graph for this function:

Here is the caller graph for this function:

icm_codegen()

static statement icm_codegen ( statement  stat, graph  g, set  region, int  level, bool  task_parallelize_p  )

static

Compute has_level hash and has_indices tables

LOOP

STATEMENT

Simplify the dependance graph

Definir le mapping entre les vertex originaux et les vertex copies

CodeGenerate reload the proper_rw_effects table, so we must reset before...

Generate the code (CodeGenerate don't use the first parameter...)

big hack

Remove dummy loops.

Parameters

region

of statement

Definition at line 1382 of file icm.c.

{
  statement result = statement_undefined;
  graph simplified_graph = graph_undefined;
 
  reference_level = level;
 
  debug_on("ICM_DEBUG_LEVEL");
  ifdebug(4) {
    pips_debug(9, "ICM_DEBUG_LEVEL start\n");
    pips_debug(4, "on statement:\n");
    print_statement(stat);
  }
 
  set_proper_rw_effects((statement_effects)
      db_get_memory_resource(DBR_PROPER_EFFECTS,
          get_current_module_name(),
          true));
 
  /* Compute has_level hash and has_indices tables */
 
  init_has_level();
  make_has_indices_map();
 
  indices = NIL;
 
  gen_multi_recurse(stat,
      loop_domain, loop_level_in, loop_level_out, /* LOOP */
      statement_domain, statement_mark, gen_null, /* STATEMENT */
      NULL);
 
  gen_free_list(indices);
 
  /* Simplify the dependance graph */
 
  simplified_graph = copy_graph(g);
 
  /* Definir le mapping entre les vertex originaux et les vertex copies */
 
  ifdebug(4) {
    pips_debug(4, "Original graph:\n");
    prettyprint_dependence_graph(stderr,
        statement_undefined,
        simplified_graph);
  }
 
  invariant_entities = set_make(set_pointer);
 
  simplified_graph = SimplifyGraph(simplified_graph,
      region,
      level,
      NB_SIMPLIFY_PASSES);
 
  set_free(invariant_entities);
 
  ifdebug(4) {
    pips_debug(4, "Simplified graph:\n");
    prettyprint_dependence_graph(stderr,
        statement_undefined,
        simplified_graph);
  }
 
  close_has_level();
  free_has_indices_map();
  reset_proper_rw_effects();
  /* CodeGenerate reload the
   * proper_rw_effects table, so we must
   * reset before... */
 
  pips_debug(9, "ICM_DEBUG_LEVEL stop\n");
  debug_off();
 
  /* Generate the code (CodeGenerate don't use the first
   * parameter...) */
  result =  CodeGenerate(/* big hack */ statement_undefined,
      simplified_graph,
      region,
      level,
      task_parallelize_p);
  free_graph(simplified_graph);
 
  ifdebug(4) {
    pips_debug(4, "Intermediate code:\n");
    print_statement(result);
  }
 
  /* Remove dummy loops. */
  drop_dummy_loops(result);
 
  ifdebug(4) {
    pips_debug(4, "Final code:\n");
    print_statement(result);
  }
 
  return result;
}

References CodeGenerate(), copy_graph(), db_get_memory_resource(), debug_off, debug_on, drop_dummy_loops(), free_graph(), gen_free_list(), gen_multi_recurse(), gen_null(), get_current_module_name(), graph_undefined, ifdebug, indices, invariant_entities, level, loop_domain, loop_level_in(), loop_level_out(), NB_SIMPLIFY_PASSES, NIL, pips_debug, prettyprint_dependence_graph(), print_statement(), reference_level, region, reset_proper_rw_effects(), set_free(), set_make(), set_pointer, set_proper_rw_effects(), SimplifyGraph(), statement_domain, statement_mark(), and statement_undefined.

Referenced by invariant_code_motion().

Here is the call graph for this function:

Here is the caller graph for this function:

icm_ignore_this_successor()

static bool icm_ignore_this_successor ( vertex  v, set  region, successor  su, int  level  )

static

Parameters

region

of statement

Definition at line 547 of file icm.c.

{
    if (common_ignore_this_vertex(region, successor_vertex(su)))
        return(true);
 
    if (!dependance_vertices_p(v, 
                               successor_vertex(su), 
                               ALL_DEPENDANCES, 
                               level))
        return (true);
 
    return false;
}

References ALL_DEPENDANCES, common_ignore_this_vertex(), dependance_vertices_p(), level, region, and successor_vertex.

Referenced by SimplifyGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

icm_loop_rwt()

static bool icm_loop_rwt ( loop  l )

static

Assume here that index is a scalar variable... :-)

memory leak...

Definition at line 1294 of file icm.c.

{
  statement head = stmt_head();
 
  ifdebug(5) {
    fprintf(stderr, "TEST : loop on %s (statement %td):\n",
        entity_name(loop_index(l)),
        statement_number(head));
  }
 
  if (drop_it(l))
  {
    statement index_statement;
    statement body = loop_body(l);
 
    expression index, m1, m2, m3;
 
    m1 = copy_expression(range_lower(loop_range(l)));
    m2 = copy_expression(range_upper(loop_range(l)));
    m3 = copy_expression(range_increment(loop_range(l)));
 
    /* Assume here that index is a scalar variable... :-) */
    pips_assert("icm_loop_rwt", entity_scalar_p(loop_index(l)));
 
    index = make_factor_expression(1, loop_index(l));
 
    index_statement =
        make_assign_statement(index,
            compute_final_index_value(m1, m2, m3));
 
    statement_instruction(head)=instruction_undefined;
    update_statement_instruction(head,make_instruction_block(make_statement_list(body, index_statement)));
 
    pips_debug(5, "-> loop on %s removed (statement %td)\n",
        entity_name(loop_index(l)),
        statement_number(head));
 
    /* memory leak... */
  }
  else {
    pips_debug(5, "-> loop on %s NOT removed (statement %td)\n",
        entity_name(loop_index(l)),
        statement_number(head));
  }
 
  return true;
}

References compute_final_index_value(), copy_expression(), drop_it(), entity_name, entity_scalar_p(), fprintf(), ifdebug, instruction_undefined, loop_body, loop_index, loop_range, make_assign_statement(), make_factor_expression(), make_instruction_block(), make_statement_list, pips_assert, pips_debug, range_increment, range_lower, range_upper, statement_instruction, statement_number, and update_statement_instruction().

Referenced by drop_dummy_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

inv_entity_filter()

static bool inv_entity_filter ( entity  e )

static

Definition at line 635 of file icm.c.

{
    expression_invariant &= set_belong_p(invariant_entities, (char *) e);
    if (!expression_invariant) gen_recurse_stop(NULL);
    return true;
}

References expression_invariant, gen_recurse_stop(), invariant_entities, and set_belong_p().

Referenced by ref_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

invariant_code_motion()

bool invariant_code_motion

(

const char *

module_name

)

Phase that hoists loop invariant code out of loops.

Parameters

[in]

module_name

Returns

true because everything should go fine

Prepare some stuffs and call icm_codegen...

Parameters

module_name

odule_name

Definition at line 1495 of file icm.c.

{
  entity module = local_name_to_top_level_entity(module_name);
  statement mod_stat = statement_undefined;
  set_current_module_entity(module);
 
  set_bool_property( "GENERATE_NESTED_PARALLEL_LOOPS", true );
  set_bool_property( "RICE_DATAFLOW_DEPENDENCE_ONLY", false );
 
  set_current_module_statement((statement)
      db_get_memory_resource(DBR_CODE,
          module_name,
          true));
 
  mod_stat = get_current_module_statement();
 
  set_ordering_to_statement(mod_stat);
 
  debug_on("ICM_DEBUG_LEVEL");
 
  ifdebug(7)
  {
    fprintf(stderr,
        "\nTesting NewGen consistency for initial code %s:\n",
        module_name);
    if (statement_consistent_p((statement)mod_stat))
      fprintf(stderr," NewGen consistent statement\n");
  }
 
  ifdebug(1) {
    pips_debug(1, "original sequential code:\n\n");
    print_statement(mod_stat);
  }
 
  if (graph_undefined_p(dg)) {
    dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
  }
  else {
    pips_internal_error("dg should be undefined");
  }
 
  enclosing = 0;
  rice_statement(mod_stat, 1, &icm_codegen);
 
  ifdebug(7) {
    fprintf(stderr, "\ntransformed code %s:",module_name);
    if (statement_consistent_p((statement)mod_stat))
      fprintf(stderr," gen consistent ");
  }
 
  // Uselessly reinitialize ordering_to_statement, even if it not set...
  clean_up_sequences(mod_stat);
  module_reorder(mod_stat);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, mod_stat);
 
  dg = graph_undefined;
  reset_current_module_statement();
  reset_current_module_entity();
  reset_ordering_to_statement();
 
  debug_off();
  return true;
}

References clean_up_sequences(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, enclosing, fprintf(), get_current_module_statement(), graph_undefined, graph_undefined_p, icm_codegen(), ifdebug, local_name_to_top_level_entity(), mod_stat, module, module_name(), module_reorder(), pips_debug, pips_internal_error, print_statement(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), rice_statement(), set_bool_property(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), statement_consistent_p(), and statement_undefined.

Here is the call graph for this function:

invariant_ignore_this_successor()

static bool invariant_ignore_this_successor ( vertex  v, set  region, successor  su, int  level  )

static

Parameters

region

of statement

Definition at line 570 of file icm.c.

{
    if (common_ignore_this_vertex(region, successor_vertex(su)))
        return(true);
 
    if (!dependance_vertices_p(v, 
                                successor_vertex(su), 
                                FLOW_DEPENDANCE, 
                                level))
        return (true);
 
    return (false);
}

References common_ignore_this_vertex(), dependance_vertices_p(), FLOW_DEPENDANCE, level, region, and successor_vertex.

Referenced by SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

invariant_vertex_to_invariant_entities()

static set invariant_vertex_to_invariant_entities ( vertex  v, set  rs  )

static

of entity

of effect

Parameters

rs

of entity

Definition at line 178 of file icm.c.

{
  statement st = vertex_to_statement(v);
  list /* of effect */ le = load_proper_rw_effects_list(st);
 
  MAP(EFFECT, ef, {
      if (effect_write_p(ef)) {
        entity e = reference_variable(effect_any_reference(ef));
 
        if (!set_belong_p(rs, (char *) v)) {
          rs = set_add_element(rs, rs, (char *) e);
        }
      }
  }, le);
 
  return rs;
}

References EFFECT, effect_any_reference, effect_write_p, load_proper_rw_effects_list(), MAP, reference_variable, set_add_element(), set_belong_p(), and vertex_to_statement().

Referenced by DoInvariantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_level_in()

static bool loop_level_in ( loop  l )

static

Definition at line 227 of file icm.c.

{
    entity index = loop_index(l);
    indices = CONS(ENTITY, index, indices);
    ++depth;
 
    return true;
}

References CONS, depth, ENTITY, indices, and loop_index.

Referenced by icm_codegen().

Here is the caller graph for this function:

loop_level_out()

static void loop_level_out ( __attribute__((unused)) loop  l )

static

Definition at line 242 of file icm.c.

{
    list new_indices = CDR(indices);
    free(indices);
    indices = new_indices;
    --depth;
}

References CDR, depth, free(), and indices.

Referenced by icm_codegen().

Here is the call graph for this function:

Here is the caller graph for this function:

pop_depending_index()

static void pop_depending_index ( loop  l )

static

Definition at line 1217 of file icm.c.

{
    list tmp = depending_indices;
    pips_assert("current loop index is poped", 
                loop_index(l)==ENTITY(CAR(depending_indices)));
    depending_indices = CDR(depending_indices);
    CDR(tmp) = NIL;
    free(tmp);
}

References CAR, CDR, depending_indices, ENTITY, free(), loop_index, NIL, and pips_assert.

Referenced by drop_it().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_conflict()

static void prettyprint_conflict ( FILE *  fd, conflict  c  )

static

Definition at line 99 of file icm.c.

{
    fprintf(fd, "\t\tfrom ");
    print_words(fd, words_effect(conflict_source(c)));
 
    fprintf(fd, " to ");
    print_words(fd, words_effect(conflict_sink(c)));
 
    fprintf(fd, " at levels ");
    MAP(INT, level, {
        fprintf(fd, " %d", level);
    }, cone_levels(conflict_cone(c)));
    fprintf(fd, "\n");
}

References cone_levels, conflict_cone, conflict_sink, conflict_source, fprintf(), INT, level, MAP, print_words(), and words_effect().

Referenced by prettyprint_successor(), and remove_dependance_from_conflicts().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_successor()

static void prettyprint_successor ( FILE *  fd, successor  su  )

static

Definition at line 119 of file icm.c.

{
    vertex v = successor_vertex(su);
    fprintf(fd, 
            "link with %02td :\n", 
            statement_number(vertex_to_statement(v)));
 
    MAP(CONFLICT, c, { 
        prettyprint_conflict(fd, c); 
    }, dg_arc_label_conflicts((dg_arc_label) successor_arc_label(su)));
}

References CONFLICT, dg_arc_label_conflicts, fprintf(), MAP, prettyprint_conflict(), statement_number, successor_arc_label, successor_vertex, and vertex_to_statement().

Referenced by prettyprint_vertex(), and remove_dependances_from_successors().

Here is the call graph for this function:

Here is the caller graph for this function:

prettyprint_vertex()

static void prettyprint_vertex ( FILE *  fd, vertex  v  )

static

Definition at line 136 of file icm.c.

{
    fprintf(fd, 
            "vertex %02td :\n", 
            statement_number(vertex_to_statement(v)));
    MAP(SUCCESSOR, s, { 
        prettyprint_successor(fd, s); 
    }, vertex_successors(v));
}

References fprintf(), MAP, prettyprint_successor(), statement_number, SUCCESSOR, vertex_successors, and vertex_to_statement().

Referenced by remove_dependance().

Here is the call graph for this function:

Here is the caller graph for this function:

print_list_entities()

void print_list_entities

(

list

l

)

Parameters

l

of entity

Definition at line 151 of file icm.c.

{
    MAP(ENTITY, e, { 
        fprintf(stderr, "%s ", entity_name(e));
    }, l);
}

References ENTITY, entity_name, fprintf(), and MAP.

Referenced by statement_depend_of_indices_p().

Here is the call graph for this function:

Here is the caller graph for this function:

push_depending_index()

static bool push_depending_index ( loop  l )

static

Definition at line 1210 of file icm.c.

{
    depending_indices = CONS(ENTITY, loop_index(l), depending_indices);
    return true;
}

References CONS, depending_indices, ENTITY, and loop_index.

Referenced by drop_it().

Here is the caller graph for this function:

ref_flt()

static bool ref_flt ( reference  r )

static

Definition at line 642 of file icm.c.

{
  return inv_entity_filter(reference_variable(r));
}

References inv_entity_filter(), and reference_variable.

Referenced by expressions_invariant_p().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_dependance()

static void remove_dependance ( vertex  v1, vertex  v2, int  dependance_type, int  level_min, int  level_max  )

static

of successor

Parameters

v2	Successors of this vertex are updated

Definition at line 488 of file icm.c.

{
    list /* of successor */ v1_successors = vertex_successors(v1);
 
    ifdebug(3) {
        pips_debug(3, "Remove ");
        
        if (dependance_type & FLOW_DEPENDANCE) fprintf(stderr, "F ");
        if (dependance_type & ANTI_DEPENDANCE) fprintf(stderr, "A ");
        if (dependance_type & OUTPUT_DEPENDANCE) fprintf(stderr, "O ");
        if (dependance_type & INPUT_DEPENDANCE) fprintf(stderr, "I ");
 
        fprintf(stderr, 
                "dep. at level >= %d and level <= %d ", 
                level_min, 
                level_max);
 
        fprintf(stderr, 
                "between %02td and %02td.\n", 
                statement_number(vertex_to_statement(v1)), 
                statement_number(vertex_to_statement(v2))); 
    } 
 
    vertex_successors(v1) = 
        remove_dependances_from_successors(v1_successors, 
                                           v2, 
                                           dependance_type, 
                                           level_min, 
                                           level_max);
 
    ifdebug(7) {
        prettyprint_vertex(stderr, v1);
    }
}

References ANTI_DEPENDANCE, FLOW_DEPENDANCE, fprintf(), ifdebug, INPUT_DEPENDANCE, OUTPUT_DEPENDANCE, pips_debug, prettyprint_vertex(), remove_dependances_from_successors(), statement_number, vertex_successors, and vertex_to_statement().

Referenced by SimplifyInvariantVertex(), and SimplifyRedundantVertex().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_dependance_from_conflicts()

static list remove_dependance_from_conflicts ( list  conflicts, int  dependance_type, int  level_min, int  level_max  )

static

of conflict

of conflict

of level

of level

memory leak : levels

memory leak : conflicts

Parameters

conflicts

of conflict

Definition at line 369 of file icm.c.

{
    list /* of conflict */ new_conflicts = NIL;
 
    ifdebug(7) {
        fprintf(stderr, "Old conflicts :\n");
        MAP(CONFLICT, c, { 
            prettyprint_conflict(stderr, c); 
        }, conflicts);
    }
 
    FOREACH(CONFLICT, c, conflicts) {
        if(conflict_cone(c) != cone_undefined) {
            if (action_dependance_p(c, dependance_type))
            {
                list /* of level */ levels = cone_levels(conflict_cone(c));
 
                list /* of level */ new_levels = 
                    remove_dependance_from_levels(levels, 
                                                  level_min, 
                                                  level_max);
 
                if (new_levels != NIL) {
                    cone_levels(conflict_cone(c)) = new_levels;
                    new_conflicts = CONS(CONFLICT, c, new_conflicts);
                }
 
                /* memory leak : levels */
            }
            else {
                new_conflicts = CONS(CONFLICT, c, new_conflicts);
            }
        }
        else {
            new_conflicts = CONS(CONFLICT, c, new_conflicts);
        }
    }
 
    /* memory leak : conflicts */
 
    ifdebug(7) 
    {
        fprintf(stderr, "New conflicts :\n");
        MAP(CONFLICT, c, { 
            prettyprint_conflict(stderr, c); 
        }, new_conflicts);
    }
 
    return new_conflicts;
}

References action_dependance_p(), cone_levels, cone_undefined, CONFLICT, conflict_cone, CONS, FOREACH, fprintf(), ifdebug, MAP, NIL, prettyprint_conflict(), and remove_dependance_from_levels().

Referenced by remove_dependances_from_successors().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_dependance_from_levels()

static list remove_dependance_from_levels ( list  levels, int  level_min, int  level_max  )

static

of level

of level

memory leak : levels

Parameters

levels

of level

Definition at line 346 of file icm.c.

{
    list /* of level */ new_levels = NIL;
 
    MAP(INT, level, {
        if ((level < level_min) || (level > level_max)) {
            new_levels = gen_nconc(new_levels, CONS(INT, level, NIL));
        }
    }, levels);
 
    /* memory leak : levels */
 
    return new_levels;
}

References CONS, gen_nconc(), INT, level, MAP, and NIL.

Referenced by remove_dependance_from_conflicts().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_dependances_from_successors()

static list remove_dependances_from_successors ( list  successors, vertex  v2, int  dependance_type, int  level_min, int  level_max  )

static

of successor

of successor

of conflict

of conflict

memory leak : lc

memory leak : successors

Definition at line 428 of file icm.c.

{
    list /* of successor */ new_successors = NIL;
 
    ifdebug(7) 
    {
        fprintf(stderr, "Old successors :\n");
        MAP(SUCCESSOR, s, { 
            prettyprint_successor(stderr, s); 
        }, successors);
    }
 
    MAP(SUCCESSOR, su, {
        vertex v = successor_vertex(su);
        
        if (v == v2) {
            list /* of conflict */ lc = 
                dg_arc_label_conflicts(successor_arc_label(su));
 
            list /* of conflict */ new_lc = 
                remove_dependance_from_conflicts(lc,
                                                 dependance_type, 
                                                 level_min, 
                                                 level_max);
 
            if (new_lc != NIL) {
                dg_arc_label_conflicts(successor_arc_label(su)) = new_lc;
                new_successors = CONS(SUCCESSOR, su, new_successors);
            }
 
            /* memory leak : lc */
        }
        else {
            new_successors = CONS(SUCCESSOR, su, new_successors);
        }
 
    }, successors);
 
    /* memory leak : successors */
 
    ifdebug(7) 
    {
        fprintf(stderr, "New successors :\n");
        MAP(SUCCESSOR, s, { 
            prettyprint_successor(stderr, s); 
        }, successors);
    }
 
    return new_successors;
}

References CONS, dg_arc_label_conflicts, fprintf(), ifdebug, MAP, NIL, prettyprint_successor(), remove_dependance_from_conflicts(), SUCCESSOR, successor_arc_label, successor_vertex, and successors().

Referenced by remove_dependance().

Here is the call graph for this function:

Here is the caller graph for this function:

SimplifyGraph()

static graph SimplifyGraph ( graph  g, set  region, int  level, unsigned int  count  )

static

of scc

Find sccs

Check if the component is strongly connected

Parameters

region

of statement

Definition at line 1092 of file icm.c.

{
  ifdebug(5) {
    pips_debug(5, "start\n");
    pips_debug(5, "level=%d, count=%d\n", level, count);
 
    pips_debug(5, "set of statement number studied: ");
    SET_MAP(elt, fprintf(stderr, "%d, ", (int) statement_number((statement) elt)), region);
    fprintf(stderr, "\n");
    ifdebug(8) {
      pips_debug(8, "set of statement studied:\n");
      SET_MAP(elt, print_statement((statement) elt), region);
    }
  }
  list /* of scc */ lsccs;
 
  /* Find sccs */
  set_sccs_drivers(&common_ignore_this_vertex,
      &icm_ignore_this_successor);
  lsccs = FindAndTopSortSccs(g, region, level);
  reset_sccs_drivers();
 
  FOREACH(SCC, elmt, lsccs) {
    /* Check if the component is strongly connected */
    if (strongly_connected_p(elmt, level)) {
      set new_region = set_make(set_pointer);
      new_region = vertices_to_statements(scc_vertices(elmt),
          new_region);
 
      g = SupressDependances(g, new_region, level, count);
 
      set_free(new_region);
    }
  }
 
  // No leak
  gen_free_list(lsccs);
 
  ifdebug(5) {
    pips_debug(5, "end\n");
  }
  return g;
}

References common_ignore_this_vertex(), count, FindAndTopSortSccs(), FOREACH, fprintf(), gen_free_list(), icm_ignore_this_successor(), ifdebug, level, pips_debug, print_statement(), region, reset_sccs_drivers(), SCC, scc_vertices, set_free(), set_make(), SET_MAP, set_pointer, set_sccs_drivers(), statement_number, strongly_connected_p(), SupressDependances(), and vertices_to_statements().

Referenced by icm_codegen(), and SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

SimplifyInvariantVertex()

static void SimplifyInvariantVertex ( vertex  v, set  region, int  level  )

static

of vertex

Parameters

region

Successors of this vertex are updated of statement

Definition at line 806 of file icm.c.

{
  set /* of vertex */ matching_vertices = set_make(set_pointer);
  statement st = vertex_to_statement(v);
 
  if (dependance_vertices_p(v, v, OUTPUT_DEPENDANCE, level) &&
      !exist_non_self_dependance_from_vertex_p(v,
          OUTPUT_DEPENDANCE, level)) {
    FOREACH(SUCCESSOR, su, vertex_successors(v)) {
      vertex y = successor_vertex(su);
      if (!common_ignore_this_vertex(region, y) &&
          dependance_vertices_p(v, y, FLOW_DEPENDANCE, level) &&
          dependance_vertices_p(y, v, ANTI_DEPENDANCE, level)) {
 
        matching_vertices = set_add_element(matching_vertices,
            matching_vertices,
            (char *) y);
      }
    }
 
    //remove_dependance(v, v, OUTPUT_DEPENDANCE, 0, load_has_level(st));
    remove_dependance(v, v, OUTPUT_DEPENDANCE, level, load_has_level(st));
 
    if (!set_empty_p(matching_vertices)) {
      SET_MAP(y, {
          remove_dependance((vertex) y, v, ANTI_DEPENDANCE,
              //0, load_has_level(st));
              level, load_has_level(st));
      }, matching_vertices);
    }
  }
 
  set_free(matching_vertices);
}

References ANTI_DEPENDANCE, common_ignore_this_vertex(), dependance_vertices_p(), exist_non_self_dependance_from_vertex_p(), FLOW_DEPENDANCE, FOREACH, level, OUTPUT_DEPENDANCE, region, remove_dependance(), set_add_element(), set_empty_p(), set_free(), set_make(), SET_MAP, set_pointer, SUCCESSOR, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by DoInvariantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

SimplifyRedundantVertex()

static void SimplifyRedundantVertex ( vertex  v, set  region, int  level  )

static

of vertices

Parameters

region

Successors of this vertex are updated of statement

Definition at line 1005 of file icm.c.

{
  set /* of vertices */ matching_vertices = set_make(set_pointer);
  statement st = vertex_to_statement(v);
 
  if (dependance_vertices_p(v, v, OUTPUT_DEPENDANCE, level) &&
      !exist_non_self_dependance_from_vertex_p(v,
          OUTPUT_DEPENDANCE, level)) {
    FOREACH(SUCCESSOR, su, vertex_successors(v)) {
      vertex y = successor_vertex(su);
      if (!common_ignore_this_vertex(region, y) &&
          dependance_vertices_p(y, v, FLOW_DEPENDANCE, level) &&
          dependance_vertices_p(v, y, ANTI_DEPENDANCE, level)) {
 
        matching_vertices = set_add_element(matching_vertices,
            matching_vertices,
            (char *) y);
      }
    }
 
    remove_dependance(v, v, OUTPUT_DEPENDANCE, 0, load_has_level(st));
 
    if (!set_empty_p(matching_vertices)) {
      SET_MAP(y, {
          remove_dependance(v, (vertex)y, ANTI_DEPENDANCE,
              0, load_has_level(st));
      }, matching_vertices);
    }
  }
 
  set_free(matching_vertices);
}

References ANTI_DEPENDANCE, common_ignore_this_vertex(), dependance_vertices_p(), exist_non_self_dependance_from_vertex_p(), FLOW_DEPENDANCE, FOREACH, level, OUTPUT_DEPENDANCE, region, remove_dependance(), set_add_element(), set_empty_p(), set_free(), set_make(), SET_MAP, set_pointer, SUCCESSOR, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by DoRedundantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_depend_of_indices_p()

static bool statement_depend_of_indices_p ( statement  st, list  indices, int  level  )

static

of effect

Ignore the first indicies...

Parameters

indices

of entity

Definition at line 596 of file icm.c.

{
  list /* of effect */ le = load_proper_rw_effects_list(st);
 
  ifdebug(6) {
    pips_debug(6, "Statement %02td depend of ", statement_number(st));
    print_list_entities(indices);
  }
 
  /* Ignore the first indicies... */
  for(; level > reference_level; --level) {
    indices = CDR(indices);
  }
 
  MAP(ENTITY, index, {
      MAP(EFFECT, ef, {
          entity e = reference_variable(effect_any_reference(ef));
          if (e == index) {
 
            ifdebug(6) {
              fprintf(stderr,": yes\n");
            }
 
            return true;
          }
      }, le);
  }, indices);
 
  ifdebug(6) {
    fprintf(stderr,": no\n");
  }
 
  return false;
}

References CDR, EFFECT, effect_any_reference, ENTITY, fprintf(), ifdebug, indices, level, load_proper_rw_effects_list(), MAP, pips_debug, print_list_entities(), reference_level, reference_variable, and statement_number.

Referenced by does_it_depend(), and vertex_invariant_p().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_mark()

static bool statement_mark ( statement  s )

static

Definition at line 213 of file icm.c.

{
     store_has_level(s, depth);
     store_statement_has_indices(s, gen_nreverse(gen_copy_seq(indices)));
     
     return true;
}

References depth, gen_copy_seq(), gen_nreverse(), and indices.

Referenced by icm_codegen().

Here is the call graph for this function:

Here is the caller graph for this function:

SupressDependances()

static graph SupressDependances ( graph  g, set  region, int  level, unsigned int  count  )

static

of scc

of statement

Find sccs considering only flow dependances

Forward simplification

Backward simplification

Parameters

region

of statement

Definition at line 1144 of file icm.c.

{
  ifdebug(5) {
    pips_debug(5, "start\n");
    pips_debug(5, "level=%d, count=%d\n", level, count);
 
    pips_debug(5, "set of statement number studied: ");
    SET_MAP(elt, fprintf(stderr, "%d, ", (int) statement_number((statement) elt)), region);
    fprintf(stderr, "\n");
    ifdebug(8) {
      pips_debug(8, "set of statement studied:\n");
      SET_MAP(elt, print_statement((statement) elt), region);
    }
  }
  list /* of scc */ lsccs;
  set /* of statement */ partially_invariant = set_make(set_pointer);
 
  /* Find sccs considering only flow dependances */
  set_sccs_drivers(&common_ignore_this_vertex,
      &invariant_ignore_this_successor);
  lsccs = FindAndTopSortSccs(g, region, level);
  reset_sccs_drivers();
 
  /* Forward simplification */
  g = DoInvariantsStatements(lsccs, g, region, level, partially_invariant);
 
  /* Backward simplification */
  lsccs = gen_nreverse(lsccs);
  g = DoRedundantsStatements(lsccs, g, region, level, partially_invariant);
 
  // No leak
  gen_free_list(lsccs);
  set_free(partially_invariant);
 
  if (count > 1) {
    return SimplifyGraph(g, region, level, count-1);
  }
  else{
    return SimplifyGraph(g, region, level+1, NB_SIMPLIFY_PASSES);
  }
}

References common_ignore_this_vertex(), count, DoInvariantsStatements(), DoRedundantsStatements(), FindAndTopSortSccs(), fprintf(), gen_free_list(), gen_nreverse(), ifdebug, invariant_ignore_this_successor(), level, NB_SIMPLIFY_PASSES, pips_debug, print_statement(), region, reset_sccs_drivers(), set_free(), set_make(), SET_MAP, set_pointer, set_sccs_drivers(), SimplifyGraph(), and statement_number.

Referenced by SimplifyGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

vertex_invariant_p()

static bool vertex_invariant_p ( vertex  v, graph  g, int  level, set  region, set  invariant  )

static

Test if the statement is dependent of ALL loop indexes >= level

If there is a flow dependence from v to v, then v is not variant

If there is a flow dependence from y to v and if y is not invariant, then v is not invariant

Parameters

region	of statement
invariant	of statement

Definition at line 736 of file icm.c.

{
  statement st = vertex_to_statement(v);
 
  /* Test if the statement is dependent of ALL loop indexes >= level */
  if (statement_depend_of_indices_p(st,
      load_statement_has_indices(st),
      level)) {
    pips_debug(6,
        "statement %02td is not invariant (depend of indices).\n",
        statement_number(st));
 
    return false;
  }
 
  /* If there is a flow dependence from v to v, then v is not variant */
  if (dependance_vertices_p(v, v, FLOW_DEPENDANCE, level)) {
    pips_debug(6,
        "statement %02td is not invariant (self flow dep).\n",
        statement_number(st));
 
    return false;
  }
 
  /* If there is a flow dependence from y to v and if y is not invariant,
   * then v is not invariant */
  MAP(VERTEX, y, {
      if (dependance_vertices_p(y, v, FLOW_DEPENDANCE, level)) {
        statement y_st = vertex_to_statement(y);
 
        if (!set_belong_p(invariant, (char *) y_st) &&
            set_belong_p(region, (char *) y_st)) {
 
          pips_debug(6,
              "statement %02td is not invariant "
              "(dep. of %02td).\n",
              statement_number(st),
              statement_number(y_st));
 
          return false;
        }
      }
  }, graph_vertices(g));
 
  pips_debug(6,
      "statement %02td is invariant.\n",
      statement_number(st));
 
  return true;
}

References dependance_vertices_p(), FLOW_DEPENDANCE, graph_vertices, level, MAP, pips_debug, region, set_belong_p(), statement_depend_of_indices_p(), statement_number, VERTEX, and vertex_to_statement().

Referenced by DoInvariantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

vertex_partially_invariant_p()

static bool vertex_partially_invariant_p ( vertex  v, __attribute__((unused)) graph  g, __attribute__((unused)) int  level, __attribute__((unused)) set  invariant  )

static

Looking for write effects only

Which kind of reference we have ?

An array access with well known indices

An array access with unknow indices

A scalar variable

Parameters

invariant

of statement

Definition at line 668 of file icm.c.

{
  statement st = vertex_to_statement(v);
 
  MAP(EFFECT, ef, {
      reference ref = effect_any_reference(ef);
 
      /* Looking for write effects only */
      if (effect_write_p(ef)) {
 
        /* Which kind of reference we have ? */
        if (reference_indices(ref) != NIL) {
          /* An array access with well known indices */
          if (expressions_invariant_p(reference_indices(ref))) {
            pips_debug(6,
                "statement %02td is partially invariant "
                "(known array access).\n",
                statement_number(st));
 
            return true;
          }
          else {
            pips_debug(6,
                "statement %02td is not partially invariant "
                "(known array access).\n",
                statement_number(st));
 
            return false;
          }
        }
        else {
          if(variable_entity_dimension(reference_variable(ref)) != 0) {
            /* An array access with unknow indices */
            pips_debug(6,
                "statement %02td is not partially invariant "
                "(UNKNOWN array access).\n",
                statement_number(st));
 
            return false;
          }
          else {
            /* A scalar variable */
            pips_debug(6,
                "statement %02td is partially invariant "
                "(scalar access).\n",
                statement_number(st));
 
            return true;
          }
        }
      }
  }, load_proper_rw_effects_list(st));
 
  pips_debug(6,
      "statement %02td is not partially invariant.\n",
      statement_number(st));
 
  return false;
}

References EFFECT, effect_any_reference, effect_write_p, expressions_invariant_p(), load_proper_rw_effects_list(), MAP, NIL, pips_debug, ref, reference_indices, reference_variable, statement_number, variable_entity_dimension(), and vertex_to_statement().

Referenced by DoInvariantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

vertex_redundant_p()

static bool vertex_redundant_p ( vertex  v, __attribute__((unused)) graph  g, int  level, set  region, set  partially_invariant, set  redundant  )

static

Test if the statement is depandant of ALL loop indexes >= level

This condition is not required, but putting a statement depending of indicies after the loop is tiedous (setting the value to the bound+1...)

Test if we are not always writing at the same adress ie. is not partially_invariant.

If there is a flow dependance from v to y and if y is not redundant, then v is not redundant

Parameters

region	of statement
partially_invariant	of statement
redundant	of statement

Definition at line 935 of file icm.c.

{
  statement st = vertex_to_statement(v);
 
  /* Test if the statement is depandant of ALL loop indexes >= level */
  /* This condition is not required, but putting a statement depending
       of indicies after the loop is tiedous (setting the value to 
       the bound+1...) */
/*
  if (statement_depend_of_indices_p(st, 
  load_statement_has_indices(st),
  level)) {
  ifdebug(6) { 
  debug(6, "vertex_redundant_p", "");
  fprintf(stderr, 
  "statement %02d is not redundant (depend of indices).\n",
  statement_number(st));
  }
 
  return false;
  }
*/
 
  /* Test if we are not always writing at the same adress
       ie. is not partially_invariant. */
  if (!set_belong_p(partially_invariant, (char *) st)) {
    pips_debug(6,
          "statement %02td is not redundant (variable address).\n",
          statement_number(st));
 
    return false;
  }
 
  /* If there is a flow dependance from v to y and if y is not redundant,
       then v is not redundant */
  FOREACH(SUCCESSOR, su, vertex_successors(v)) {
    vertex y = successor_vertex(su);
    if (dependance_vertices_p(v, y, FLOW_DEPENDANCE, level)) {
      statement y_st = vertex_to_statement(y);
 
      if (!set_belong_p(redundant, (char *) y_st) &&
          set_belong_p(region, (char *) y_st)) {
 
        pips_debug(6,
              "statement %td is not redundant "
              "(dep. of %td).\n",
              statement_number(st),
              statement_number(y_st));
 
        return false;
      }
    }
  }
 
  pips_debug(6,
        "statement %td is redundant.\n",
        statement_number(st));
  return true;
}

References dependance_vertices_p(), FLOW_DEPENDANCE, FOREACH, level, pips_debug, redundant(), region, set_belong_p(), statement_number, SUCCESSOR, successor_vertex, vertex_successors, and vertex_to_statement().

Referenced by DoRedundantsStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

vertex_to_statement()

statement vertex_to_statement

(

vertex

v

)

Vertex_to_statement looks for the statement that is pointed to by vertex v.

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

Definition at line 45 of file util.c.

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

References dg_vertex_label_statement, ordering_to_statement(), and vertex_vertex_label.

Referenced by adg_dup_disjunctive_nodes(), adg_list_same_order_in_dg(), adg_same_order_in_dg(), allocate_task_to_cluster(), bdsc_code_instrumentation(), bottom_level(), check_tiling_legality(), check_way_between_two_statements(), clean_sdg(), common_ignore_this_vertex(), communications_construction(), contains_level_l_dependence(), dependance_vertices_p(), dg_vertex_dup(), dma_statements_conflict_p(), do_reduction_detection(), do_reduction_propagation(), do_redundant_load_store_elimination(), do_scalar_renaming_in_graph(), do_scalar_renaming_in_successors(), do_scalar_renaming_in_vertex(), DoInvariantsStatements(), DoRedundantsStatements(), end_idle_clusters(), find_covering_reference_path(), find_level_l_loop_statement(), flint_initialize_statement_def_use_variables(), graph_to_live_writes(), ignore_this_conflict(), init_statement_equivalence_table(), initialization(), invariant_vertex_to_invariant_entities(), IsolatedStatement(), make_filtered_dg_or_dvdg(), parse_instrumented_file(), predecessors(), prettyprint_successor(), prettyprint_vertex(), print_loopnest_dependence_cone(), print_SDGs(), PrintScc(), quick_privatize_graph(), quick_privatize_loop(), ready_node(), remove_dependance(), rice_update_dependence_graph(), scc_region(), schedule_failsafe(), search_parallel_loops(), sequence_dg(), SimplifyInvariantVertex(), SimplifyRedundantVertex(), some_conflicts_between(), statement_conflicts_p(), statement_to_vertex(), statements_conflict_p(), statements_conflict_relaxed_p(), stats_has_rw_conf_p(), step_analyse_CHAINS_DG(), successor_only_has_rr_conflict_p(), successors(), t_level(), tlevel_decrease(), topological_sort(), TopSortSccs(), update_priority_values(), vertex_invariant_p(), vertex_partially_invariant_p(), vertex_redundant_p(), vertex_to_chains(), vertices_to_statements(), xml_Chain_Graph(), and zeroing_multiple_edges().

Here is the call graph for this function:

vertices_to_statements()

static set vertices_to_statements ( list  vl, set  ss  )

static

of statement

Parameters

vl	of vertex
ss	of statement

Definition at line 166 of file icm.c.

{
    MAP(VERTEX, v, {
        ss = set_add_element(ss, ss, (char *) vertex_to_statement(v));
    }, vl);
 
    return ss;
}

References MAP, set_add_element(), VERTEX, and vertex_to_statement().

Referenced by SimplifyGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

depending_indices

list depending_indices

static

of entity

Definition at line 1195 of file icm.c.

Referenced by does_it_depend(), drop_it(), pop_depending_index(), and push_depending_index().

depth

int depth = 0

static

Definition at line 205 of file icm.c.

Referenced by loop_level_in(), loop_level_out(), and statement_mark().

expression_invariant

bool expression_invariant = false

static

Definition at line 63 of file icm.c.

Referenced by expressions_invariant_p(), and inv_entity_filter().

indices

list indices = NIL

static

Definition at line 204 of file icm.c.

Referenced by basic_and_indices_to_basic(), copy_n_reference(), copy_write_statement_with_cumulated_regions(), do_array_to_pointer_walk_expression(), do_check_isolate_statement_preconditions_on_call(), do_group_constants_terapix(), do_isolate_statement_preconditions_satisified_p(), do_linearize_array_reference(), do_outliner_smart_replacment(), filter_regions(), gather_local_indices(), gfc2pips_array_ref2indices(), icm_codegen(), indice_p(), io_comp_regions(), isolate_patch_reference(), loop_level_in(), loop_level_out(), loop_nest_to_local_variables(), make_base_phi_variables(), make_send_receive_conversion(), make_start_ru_module(), MakeAtom(), reference_offset(), replace_entity_by_expression_expression_walker(), simdizer_auto_tile(), statement_depend_of_indices_p(), statement_mark(), xml_array_in_task(), xml_Chain_Graph(), xml_data(), xml_references(), and xml_tiling().

invariant_entities

set invariant_entities = set_undefined

static

of entity

Definition at line 64 of file icm.c.

Referenced by DoInvariantsStatements(), icm_codegen(), and inv_entity_filter().

it_depends

bool it_depends

static

Definition at line 1196 of file icm.c.

Referenced by does_it_depend(), and drop_it().

reference_level

int reference_level =0

static

Definition at line 61 of file icm.c.

Referenced by icm_codegen(), and statement_depend_of_indices_p().