icm.c

Go to the documentation of this file.

/*
 
  $Id: icm.c 23065 2016-03-02 09:05:50Z coelho $
 
  Copyright 1989-2016 MINES ParisTech
 
  This file is part of PIPS.
 
  PIPS is free software: you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  any later version.
 
  PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY; without even the implied warranty of MERCHANTABILITY or
  FITNESS FOR A PARTICULAR PURPOSE.
 
  See the GNU General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with PIPS.  If not, see <http://www.gnu.org/licenses/>.
 
*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
/*
 * Invariant Code Motion 
 *
 * Olivier Albiez
 */
 
 
/*
 * Il faut tester la presence de dependance sur le graphe original et
 * modifier une copie.
 */
 
 
#include "local.h"
#include "prettyprint.h" // for debugging
#include "effects-generic.h"
#include "effects-simple.h"
 
statement vertex_to_statement(vertex v);
 
 
/* Set to 2 if we want to simplify in two passes */
#define NB_SIMPLIFY_PASSES 1
 
 
#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)
 
/*
 * Definition of local variables
 */
static int reference_level=0;
 
static bool expression_invariant = false; 
static set /* of entity */ invariant_entities = set_undefined;
//static set /* of statement */ statements_partialy_invariant = set_undefined;
 
 
/*********************************************************** PRINT FUNCTIONS */
 
 
/*
 * Print a statement_to_effect table.
 */
void 
dump_sef(statement_effects se)
{
    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);
}
 
 
/*
 * Print a conflict.
 */
static void 
prettyprint_conflict(FILE *fd, conflict 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");
}
 
 
/*
 * Print a successor.
 */
static void 
prettyprint_successor(FILE *fd, successor su)
{
    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)));
}
 
 
/*
 * Print a vertex.
 */
static void 
prettyprint_vertex(FILE *fd, vertex v)
{
    fprintf(fd, 
            "vertex %02td :\n", 
            statement_number(vertex_to_statement(v)));
    MAP(SUCCESSOR, s, { 
        prettyprint_successor(fd, s); 
    }, vertex_successors(v));
}
 
 
/*
 * Print a entities list.
 */
void
print_list_entities(list /* of entity */ l)
{
    MAP(ENTITY, e, { 
        fprintf(stderr, "%s ", entity_name(e));
    }, l);
}
 
 
/*********************************************************** MISC FUNCTIONS */
 
 
/*
 * Add statements from the vertex list to the statements set.
 */
static set /* of statement */
vertices_to_statements(list /* of vertex */ vl, 
                       set /* of statement */ss)
{
    MAP(VERTEX, v, {
        ss = set_add_element(ss, ss, (char *) vertex_to_statement(v));
    }, vl);
 
    return ss;
}
 
 
static set /* of entity */
invariant_vertex_to_invariant_entities(vertex v,
    set /* of entity */ rs)
{
  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;
}
 
 
/************************************************************ MAPPING TOOLS */
 
 
GENERIC_LOCAL_FUNCTION(has_level, persistant_statement_to_int)
GENERIC_LOCAL_MAPPING(has_indices, list, statement)
 
static list indices = NIL;    
static int depth = 0;
 
 
/*
 * Gen_multi_recurse hook.
 * Set the depth and the indices list of the statement.
 */
static bool
statement_mark(statement s)
{
     store_has_level(s, depth);
     store_statement_has_indices(s, gen_nreverse(gen_copy_seq(indices)));
     
     return true;
}
 
 
/*
 * Gen_multi_recurse hook.
 * Update the depth and the indices list when enter a loop.
 */
static bool
loop_level_in (loop l) 
{
    entity index = loop_index(l);
    indices = CONS(ENTITY, index, indices);
    ++depth;
 
    return true;
}
 
 
/*
 * Gen_multi_recurse hook.
 * Update the depth and the indices list when exit a loop.
 */
static void
loop_level_out (__attribute__((unused))loop l) 
{
    list new_indices = CDR(indices);
    free(indices);
    indices = new_indices;
    --depth;
}
 
 
/***************************************************** DEPENDANCES FUNCTIONS */
 
 
/*
 * Test if the conflict correspond to the given dependance type.
 */
static bool
action_dependance_p(conflict c, int dependance_type) 
{
    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)))));
}
 
 
/* 
 * 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.
 */
static bool
dependance_vertices_p(vertex v1, vertex v2, int dependance_type, int level)
{
  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;
}
 
 
/*
 * Test the existance of a given dependance from the vertex v with any other 
 * vertices than v. 
 */
static bool
exist_non_self_dependance_from_vertex_p(vertex v, 
                                        int dependance_type, 
                                        int level)
{
    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;
}
 
/*
 * Remove all levels between level_min and level_max from the list of levels.
 */
static list /* of level */
remove_dependance_from_levels(list /* of level */ levels, 
                              int level_min, 
                              int level_max)
{
    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;
}
 
 
/*
 * Remove all conflicts matching the dependance_type for a level 
 * between level_min and level_max.
 */
static list /* of conflict */
remove_dependance_from_conflicts(list /* of conflict */ conflicts, 
                                 int dependance_type, 
                                 int level_min, 
                                 int level_max)
{
    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;
}
 
 
/*
 * Remove all successors matching the given parameters.
 */
static list /* of successor */
remove_dependances_from_successors(list successors, 
                                   vertex v2, 
                                   int dependance_type, 
                                   int level_min, 
                                   int level_max)
{
    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;
}
 
 
/*
 * Remove all dependances between v1 and v2 matching the given parameters.
 */
static void
remove_dependance(vertex v1, /* Successors of this vertex are updated */
                  vertex v2, 
                  int dependance_type, 
                  int level_min, 
                  int level_max)
{
    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);
    }
}
 
 
/************************************************************ SCCS FUNCTIONS */
 
 
/*
 * FindAndTopSortSccs hook.
 * Test if the vertex belong to the region.
 */
static bool 
common_ignore_this_vertex(set /* of statement */ region, vertex v)
{
    return(!set_belong_p(region, (char *) vertex_to_statement(v)));
}
 
 
/*
 * FindAndTopSortSccs hook.
 * Test if exist any dependance with a level >= 'level'. 
 */
static bool 
icm_ignore_this_successor(vertex v, 
                          set /* of statement */ region, 
                          successor su, 
                          int level)
{
    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;
}
 
 
/*
 * FindAndTopSortSccs hook.
 * Test if exist a flow dependance with a level >= 'level'. 
 */
static bool 
invariant_ignore_this_successor(vertex v, 
                                set /* of statement */ region, 
                                successor su, 
                                int level)
{
    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);
}
 
 
/********************************************************* DG SIMPLIFICATION */
 
 
/*
 * Test if a statement depend of any indicies.
 * The 'level' first indicies are not used.
 */
static bool
statement_depend_of_indices_p(statement st, 
    list /* of entity */ indices,
    int level)
{
  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;
}
 
 
static bool
inv_entity_filter(entity e)
{
    expression_invariant &= set_belong_p(invariant_entities, (char *) e);
    if (!expression_invariant) gen_recurse_stop(NULL);
    return true;
}
 
static bool ref_flt(reference r)
{
  return inv_entity_filter(reference_variable(r));
}
 
static bool
expressions_invariant_p(list /* of expression */ le)
{
    MAP(EXPRESSION, exp, {
        expression_invariant = true;
 
        gen_recurse(exp, reference_domain, ref_flt, gen_null);
 
        if (!expression_invariant) {
            return false;
        }
    }, le);
 
    return true;
}
 
 
/*
 * Test if the vertex is partially invariant.
 */
static bool
vertex_partially_invariant_p(vertex v, 
    __attribute__((unused)) graph g,
    __attribute__((unused)) int level,
    __attribute__((unused)) set /* of statement */ invariant)
{
  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;
}
 
 
/*
 * Test if the vertex is invariant.
 */
static bool
vertex_invariant_p(vertex v, 
    graph g,
    int level,
    set /* of statement */ region,
    set /* of statement */ invariant)
{
  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;
}
 
 
/*
 * Simplify a invariant vertex 'v' using the following rule:
 *
 * if 
 *   exist output(v, v, <= level)
 *   not exist output(v, z, <= level) v != z
 * then 
 *   remove output(v, v, <= level)
 *   foreach y satisfying
 *     exist flow(v -> y, infiny)
 *     exist anti(y -> v, <= level)
 *   do remove anti(y -> v, <= level)
 */
static void
SimplifyInvariantVertex(vertex v, /* Successors of this vertex are updated */
    set /* of statement */ region,
    int level)
{
  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);
}
 
 
/*
 * Find and simplify invariants statements.
 */
static graph
DoInvariantsStatements(list /* of scc */ lsccs, 
    graph g,
    set /* of statement */ region,
    int level,
    set /* of statement */ partially_invariant)
{
  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;
}
 
 
/*
 * Test if the vertex is redundant.
 */
static bool
vertex_redundant_p(vertex v, 
    __attribute__((unused)) graph g,
    int level,
    set /* of statement */ region,
    set /* of statement */ partially_invariant,
    set /* of statement */ redundant)
{
  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;
}
 
 
/*
 * Simplify a redundant vertex 'v' using the following rule:
 */
static void
SimplifyRedundantVertex(vertex v, /* Successors of this vertex are updated */
    set /* of statement */ region,
    int level)
{
  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);
}
 
 
/*
 * Find and simplify redundant statements.
 */
static graph
DoRedundantsStatements(list /* of scc */ lsccs, 
    graph g,
    set /* of statement */ region,
    int level,
    set /* of statement */ partially_invariant)
{
  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;
}
 
static graph SimplifyGraph(graph g, set region, int level, unsigned int count);
static graph SupressDependances(graph g, set region, int level, unsigned int count);
 
/*
 * Simplify the dependence graph.
 */
static graph
SimplifyGraph(graph g,
    set /* of statement */ region,
    int level,
    unsigned int count)
{
  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;
}
 
 
/*
 * Supress unneeded dependances.
 */
static graph
SupressDependances(graph g,
    set /* of statement */ region,
    int level,
    unsigned int count)
{
  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);
  }
}
 
 
/******************************************************** REMOVE DUMMY LOOPS */
 
 
DEFINE_LOCAL_STACK(stmt, statement)
 
static list /* of entity */ depending_indices;
static bool it_depends;
 
 
/* 
 * Set whether s depends from enclosing indices
 */
static bool does_it_depend(statement s)
{
    it_depends |= statement_depend_of_indices_p(s, depending_indices, 0);
    if (it_depends) gen_recurse_stop(NULL);
    return true;
}
 
 
static bool push_depending_index(loop l)
{
    depending_indices = CONS(ENTITY, loop_index(l), depending_indices);
    return true;
}
 
 
static void pop_depending_index(loop l)
{
    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);
}
 
 
static bool drop_it(loop l)
{
  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;
}
 
 
/*
 * Compute the final expression of the loop index.
 * Follow the ANSI Fortran 77 normalization.
 
 *  = m1 + MAX(INT((m2 - m1 + m3) / m3), 0) * m3
 
 */
static expression
compute_final_index_value(expression m1, expression m2, expression m3)
{
    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;
}
 
 
static bool icm_loop_rwt(loop l)
{
  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;
}
 
 
/*
 * Drop all loops l  matching the pattern:
 *   l is parallel
 *   the body of l doesn't use indicies of the loop l.
 *
 * WARNING : the pattern is correct ????????
 */
static void drop_dummy_loops(statement s)
{
  /* 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();
}
 
 
/*********************************************************** REGENERATE CODE */
 
 
/*
 * Simplify the dependance graph and regenerate the code.
 *
 * Using the algorithm described in Chapter xxx of Julien Zory's PhD?
 */
static statement icm_codegen(statement stat,
    graph g,
    set /* of statement */ region,
    int level,
    bool task_parallelize_p)
{
  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;
}
 
 
/*************************************************************** ENTRY POINT */
 
 
/* Phase that hoists loop invariant code out of loops.
 
   @param[in] module_name
 
   @return true because everything should go fine
 
   Prepare some stuffs and call icm_codegen...
*/
bool invariant_code_motion(const char* module_name)
{
  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;
}