ricedg.c

Go to the documentation of this file.

/*
 
 $Id: ricedg.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
/* Dependence Graph computation for Allen & Kennedy algorithm
 *
 * Remi Triolet, Yi-qing Yang
 *
 * Modifications:
 *  - new option to use semantics analysis results (Francois Irigoin,
 *    12 April 1991)
 *
 *  - compute the dependence cone, the statistics.
 *    (Yi-Qing, August 1991)
 *
 *  - updated using DEFINE_CURRENT_MAPPING, BA, September 3, 1993
 *
 *  - dg_type introduced to replace dg_fast and dg_semantics; it is more
 *    general. (BC, August 1995).
 *
 *  - TestDependence split into different procedures for more readability.
 *    (BC, August 1995).
 *
 *  - creation of quick_privatize.c and prettyprint.c to reduce
 *    the size of ricedg.c (FI, Oct. 1995)
 *
 * Notes:
 *  - Many values seem to be assigned to StatementToContext and never be
 *    freed;
 *
 */
 
#include "genC.h"
#include "local.h"
#include "workspace-util.h"
#include "prettyprint.h"
 
/* local variables */
/*the variables for the statistics of test of dependence and parallelization */
/* they should not be global ? FC.
 */
int NbrArrayDepInit = 0;
int NbrIndepFind = 0;
int NbrAllEquals = 0;
int NbrDepCnst = 0;
int NbrTestExact = 0;
int NbrDepInexactEq = 0;
int NbrDepInexactFM = 0;
int NbrDepInexactEFM = 0;
int NbrScalDep = 0;
int NbrIndexDep = 0;
int deptype[5][3], constdep[5][3];
int NbrTestCnst = 0;
int NbrTestGcd = 0;
int NbrTestSimple = 0; /* by sc_normalize() */
int NbrTestDiCnst = 0;
int NbrTestProjEqDi = 0;
int NbrTestProjFMDi = 0;
int NbrTestProjEq = 0;
int NbrTestProjFM = 0;
int NbrTestDiVar = 0;
int NbrProjFMTotal = 0;
int NbrFMSystNonAug = 0;
int FMComp[18]; /*for counting the number of F-M complexity less than 16.
 The complexity of one projection by F-M is multiply
 of the nbr. of inequations positive and the nbr. of
 inequations negatives who containe the variable
 eliminated.The last elem of the array (ie FMComp[17])
 is used to count cases with complexity over 16*/
bool is_test_exact = true;
bool is_test_inexact_eq = false;
bool is_test_inexact_fm = false;
bool is_dep_cnst = false;
bool is_test_Di;
bool Finds2s1;
 
/* to map statements to execution contexts */
/* Psysteme_undefined is not defined in sc.h; as Psysteme is external,
 * I define it here. BA, September 1993
 */
#define Psysteme_undefined SC_UNDEFINED
DEFINE_CURRENT_MAPPING(context, Psysteme)
 
/* to map statements to enclosing loops */
/* DEFINE_CURRENT_MAPPING(loops, list) now defined in ri-util, BA, September 1993 */
 
/* the dependence graph being updated */
static graph dg;
 
static bool PRINT_RSDG = false;
 
/* Different types of dependence tests:
 *
 * switch dg_type:
 *
 *      DG_FAST: no context constraints are added
 *      DG_FULL: use loop bounds as context
 *      DG_SEMANTICS : use preconditions as context
 *
 * The use of the variable dg_type allows to add more cases in the future.
 */
#define DG_FAST 1
#define DG_FULL 2
#define DG_SEMANTICS 3
 
static int dg_type = DG_FAST;
 
// stupid counter used by one debug message in ricedg
extern int Nbrdo;
 
/*********************************************************************************/
/* INTERFACE FUNCTIONS                                                           */
/*********************************************************************************/
 
static bool rice_dependence_graph(char */*mod_name*/);
 
bool rice_fast_dependence_graph(char *mod_name) {
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}
 
bool rice_full_dependence_graph(char *mod_name) {
  dg_type = DG_FULL;
  return rice_dependence_graph(mod_name);
}
 
bool rice_semantics_dependence_graph(char *mod_name) {
  dg_type = DG_SEMANTICS;
  return rice_dependence_graph(mod_name);
}
 
bool rice_regions_dependence_graph(char *mod_name) {
  if(!same_string_p(rule_phase(find_rule_by_resource("CHAINS")),
      "REGION_CHAINS"))
    pips_user_warning("Region chains not selected - using effects instead\n");
 
  dg_type = DG_FAST;
  return rice_dependence_graph(mod_name);
}
 
 
 
/*********************************************************************************/
/* STATIC FUNCTION DECLARATIONS                                                  */
/*********************************************************************************/
 
static void rdg_unstructured(unstructured /*u*/);
static void rdg_statement(statement /*stat*/);
static void rdg_loop(statement /*stat*/);
static void rice_update_dependence_graph(statement /*stat*/, set /*region*/);
static list TestCoupleOfEffects(statement /*s1*/,
                                effect /*e1*/,
                                statement /*s2*/,
                                effect /*e2*/,
                                list /*llv*/,
                                Ptsg */*gs*/,
                                list */*levelsop*/,
                                Ptsg */*gsop*/);
static list TestDependence(list /*n1*/,
                           Psysteme /*sc1*/,
                           statement /*s1*/,
                           effect /*ef1*/,
                           reference /*r1*/,
                           list /*n2*/,
                           Psysteme /*sc2*/,
                           statement /*s2*/,
                           effect /*ef2*/,
                           reference /*r2*/,
                           list /*llv*/,
                           Ptsg */*gs*/,
                           list */*levelsop*/,
                           Ptsg */*gsop*/);
static bool build_and_test_dependence_context(reference /*r1*/,
                                              reference /*r2*/,
                                              Psysteme /*sc1*/,
                                              Psysteme /*sc2*/,
                                              Psysteme */*psc_dep*/,
                                              list /*llv*/,
                                              list /*s2_enc_loops*/);
static bool gcd_and_constant_dependence_test(reference /*r1*/,
                                             reference /*r2*/,
                                             list /*llv*/,
                                             list /*s2_enc_loops*/,
                                             Psysteme */*psc_dep*/);
static void dependence_system_add_lci_and_di(Psysteme */*psc_dep*/,
                                             list /*s1_enc_loops*/,
                                             Pvecteur */*p_DiIncNonCons*/);
static list TestDiVariables(Psysteme /*ps*/,
                            int /*cl*/,
                            statement /*s1*/,
                            effect /*ef1*/,
                            statement /*s2*/,
                            effect /*ef2*/);
static Ptsg dependence_cone_positive(Psysteme /*dep_sc*/);
static list loop_variant_list(statement /*stat*/);
static bool TestDiCnst(Psysteme /*ps*/,
                       int /*cl*/,
                       statement /*s1*/,
                       effect /*ef1*/,
                       statement /*s2*/,
                       effect /*ef2*/);
 
 
/**************************************** WALK THROUGH THE DEPENDENCE GRAPH */
 
/* The supplementary call to init_ordering_to_statement should be
 avoided if ordering.c were more clever. */
static bool rice_dependence_graph(char *mod_name) {
  FILE *fp;
 
  statement mod_stat;
  int i, j;
  graph chains;
  string dg_name;
  entity module = local_name_to_top_level_entity(mod_name);
 
  set_current_module_entity(module);
 
  set_current_module_statement((statement)db_get_memory_resource(DBR_CODE,
                                                                 mod_name,
                                                                 true));
  mod_stat = get_current_module_statement();
 
  chains = (graph)db_get_memory_resource(DBR_CHAINS, mod_name, true);
 
  ResetLoopCounter();
 
  debug_on("RICEDG_DEBUG_LEVEL");
  pips_debug(1, "Computing Rice dependence graph for %s\n", mod_name);
 
  ifdebug(2) {
    hash_warn_on_redefinition();
    graph_consistent_p(chains);
  }
 
  ifdebug(1) {
    fprintf(stderr,
            "Space for chains: %d bytes\n",
            gen_allocated_memory((gen_chunk *)chains));
    fprintf(stderr,
            "Space for obj_table: %d bytes\n",
            current_shared_obj_table_size());
  }
 
  hash_warn_on_redefinition();
  dg = copy_graph(chains);
 
  ifdebug(1) {
    fprintf(stderr,
            "Space for chains's copy: %d bytes\n",
            gen_allocated_memory((gen_chunk *)dg));
    fprintf(stderr,
            "Space for obj_table: %d bytes\n",
            current_shared_obj_table_size());
  }
 
  pips_debug(8,"original graph\n");
  ifdebug(8) {
    set_ordering_to_statement(mod_stat);
    prettyprint_dependence_graph(stderr, mod_stat, dg);
    reset_ordering_to_statement();
  }
 
  debug_off();
 
  if(dg_type == DG_SEMANTICS)
    set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS,
                                                                   mod_name,
                                                                   true));
 
  set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS,
                                                                     mod_name,
                                                                     true));
 
  debug_on("RICEDG_DEBUG_LEVEL");
  pips_debug(1, "finding enclosing loops ...\n");
 
  set_enclosing_loops_map(loops_mapping_of_statement(mod_stat));
  ifdebug(3) {
    fprintf(stderr, "\nThe number of DOs :\n");
    fprintf(stderr, " Nbrdo=%d", Nbrdo);
  }
  debug_on("QUICK_PRIVATIZER_DEBUG_LEVEL");
 
  /* we need to access the statements from their ordering for the
   dependance-graph: */
  /* Do this as late as possible as it is also used by pipsdbm... */
  set_ordering_to_statement(mod_stat);
 
  quick_privatize_graph(dg);
  debug_off();
 
  for (i = 0; i <= 4; i++) {
    for (j = 0; j <= 2; j++) {
      deptype[i][j] = 0;
      constdep[i][j] = 0;
    }
  }
 
  /* walk thru mod_stat to find well structured loops.
   update dependence graph for these loops. */
 
  rdg_statement(mod_stat);
 
  ifdebug(3) {
    fprintf(stderr, "\nThe results of statistique of test of dependence are:\n");
    fprintf(stderr, "NbrArrayDepInit = %d\n", NbrArrayDepInit);
    fprintf(stderr, "NbrIndepFind = %d\n", NbrIndepFind);
    fprintf(stderr, "NbrAllEquals = %d\n", NbrAllEquals);
    fprintf(stderr, "NbrDepCnst = %d\n", NbrDepCnst);
    fprintf(stderr, "NbrTestExact= %d\n", NbrTestExact);
    fprintf(stderr, "NbrDepInexactEq= %d\n", NbrDepInexactEq);
    fprintf(stderr, "NbrDepInexactFM= %d\n", NbrDepInexactFM);
    fprintf(stderr, "NbrDepInexactEFM= %d\n", NbrDepInexactEFM);
    fprintf(stderr, "NbrScalDep = %d\n", NbrScalDep);
    fprintf(stderr, "NbrIndexDep = %d\n", NbrIndexDep);
    fprintf(stderr, "deptype[][]");
    for (i = 0; i <= 4; i++)
      for (j = 0; j <= 2; j++)
        fprintf(stderr, "%d  ", deptype[i][j]);
    fprintf(stderr, "\nconstdep[][]");
    for (i = 0; i <= 4; i++)
      for (j = 0; j <= 2; j++)
        fprintf(stderr, "%d  ", constdep[i][j]);
    fprintf(stderr, "\nNbrTestCnst = %d\n", NbrTestCnst);
    fprintf(stderr, "NbrTestGcd = %d\n", NbrTestGcd);
    fprintf(stderr, "NbrTestSimple = %d\n", NbrTestSimple);
    fprintf(stderr, "NbrTestDiCnst = %d\n", NbrTestDiCnst);
    fprintf(stderr, "NbrTestProjEqDi = %d\n", NbrTestProjEqDi);
    fprintf(stderr, "NbrTestProjFMDi = %d\n", NbrTestProjFMDi);
    fprintf(stderr, "NbrTestProjEq = %d\n", NbrTestProjEq);
    fprintf(stderr, "NbrTestProjFM = %d\n", NbrTestProjFM);
    fprintf(stderr, "NbrTestDiVar = %d\n", NbrTestDiVar);
    fprintf(stderr, "NbrProjFMTotal = %d\n", NbrProjFMTotal);
    fprintf(stderr, "NbrFMSystNonAug = %d\n", NbrFMSystNonAug);
    fprintf(stderr, "FMComp[]");
    for (i = 0; i < 18; i++)
      fprintf(stderr, "%d ", FMComp[i]);
  }
  /* write the result to the file correspondant in the order of :
   module,NbrArrayDeptInit,NbrIndeptFind,NbrArrayDepInit,NbrScalDep,
   NbrIndexDep,deptype[5][3]*/
  if(get_bool_property(RICEDG_PROVIDE_STATISTICS))
    writeresult(mod_name);
 
  ifdebug(2) {
    fprintf(stderr, "updated graph\n");
    prettyprint_dependence_graph(stderr, mod_stat, dg);
  }
 
  /* FI: this is not a proper way to do it */
  if(get_bool_property("PRINT_DEPENDENCE_GRAPH") || PRINT_RSDG) {
    dg_name = strdup(concatenate(db_get_current_workspace_directory(),
                                 "/",
                                 mod_name,
                                 ".dg",
                                 NULL));
    fp = safe_fopen(dg_name, "w");
    prettyprint_dependence_graph(fp, mod_stat, dg);
    safe_fclose(fp, dg_name);
  }
 
  debug_off();
 
  DB_PUT_MEMORY_RESOURCE(DBR_DG, mod_name, (char*) dg);
 
  reset_ordering_to_statement();
  reset_current_module_entity();
  reset_current_module_statement();
  reset_precondition_map();
  reset_cumulated_rw_effects();
  clean_enclosing_loops();
 
  return true;
}
 
static void rdg_unstructured(unstructured u) {
  list blocs = NIL;
 
  CONTROL_MAP(c, {
        rdg_statement(control_statement(c));
      }, unstructured_control(u), blocs);
 
  gen_free_list(blocs);
}
 
static void rdg_statement(statement stat) {
  forloop fl = forloop_undefined;
  whileloop wl = whileloop_undefined;
  statement body = statement_undefined;
  instruction istat = statement_instruction(stat);
 
  switch(instruction_tag(istat)) {
    case is_instruction_block: {
      FOREACH (STATEMENT, s, instruction_block(istat))
        rdg_statement(s);
      break;
    }
    case is_instruction_test:
      rdg_statement(test_true(instruction_test(istat)));
      rdg_statement(test_false(instruction_test(istat)));
      break;
    case is_instruction_loop:
      rdg_loop(stat);
      break;
    case is_instruction_whileloop:
      wl = instruction_whileloop (istat);
      body = whileloop_body (wl);
      rdg_statement(body);
      break;
    case is_instruction_forloop:
      fl = instruction_forloop (istat);
      body = forloop_body (fl);
      rdg_statement(body);
      break;
    case is_instruction_goto:
    case is_instruction_call:
    case is_instruction_expression:
      break;
    case is_instruction_unstructured:
      rdg_unstructured(instruction_unstructured(istat));
      break;
    default:
      pips_internal_error("case default reached with tag %d",
          instruction_tag(istat));
      break;
  }
}
 
static void rdg_loop(statement stat) {
  set region;
 
  if(get_bool_property("COMPUTE_ALL_DEPENDENCES")) {
    region = region_of_loop(stat);
    ifdebug(7) {
      fprintf(stderr, "[rdg_loop] applied on region:\n");
      print_statement_set(stderr, region);
    }
    rice_update_dependence_graph(stat, region);
  } else {
    if((region = distributable_loop(stat)) == set_undefined) {
      ifdebug(1) {
        fprintf(stderr,
                "[rdg_loop] skipping loop %td (but recursing)\n",
                statement_number(stat));
      }
      rdg_statement(loop_body(statement_loop(stat)));
    } else {
      rice_update_dependence_graph(stat, region);
      set_free(region);
    }
  }
}
 
 
 
/* Update of dependence graph
 *
 * The update of conflict information is performed for all statements in
 * a loop. This set of statements seems to be defined by "region", while
 * the loop is defined by "stat".
 *
 * Let v denote a vertex, a an arc, s a statement attached to a vertex
 * and c a conflict, i.e. a pair of effects (e1,e2). Each arc is
 * labelled by a list of statements. Each vertex points to a list of
 * arcs. Each arc points to a list of conflicts. See dg.f.tex and
 * graph.f.tex in Documentation/Newgen for more details.
 *
 * The procedure is quite complex because:
 *
 * - each dependence arc carries a list of conflicts; when a conflict is
 * found non-existent, it has to be removed from the conflict list and
 * the arc may also have to be removed from the arc list associated to
 * the current vertex if its associated conflict list becomes empty;
 * removing an element from a list is a pain because you need to know
 * the previous element and to handle the special case of the list first
 * element removal;
 *
 * - the same conflict may appear twice, once as a def-use conflict and
 * once as a use-def conflicts; since dependence testing may be long,
 * the conflict and its symmetric conflict are processed simultaneously;
 * of course, conflict list and dependence arc updates become tricky,
 *
 * - especially if the two vertices of the dependence arc are only one:
 * you can have a s1->s1 dependence; thus you might be scanning and
 * updating the very same list of arcs and conflicts twice... but there
 * is a test on pchead and pchead1 to avoid it (pchead and pchead1
 * points to the heads of the current conflict list and of the conflict
 * list containing the symmetrical conflict); remember, you have no
 * guarantee that s1!=s2 and/or v1=!v2 and/or a1!=a2
 *
 * - note that there also is a test about symmetry: def-def and use-use
 * conflicts cannot have symmetric conflicts;
 *
 * - because of the use-def/def-use symmetry, a conflict may already
 * have been processed when it is accessed;
 *
 * - due to a strange feature in the NewGen declarations, the arcs
 * are called "successors"; variables in the procedure are named with
 * the same convention except... except when they are not; so a so-called
 * "successor" may be either an arc or a vertex (or a statement since
 * each vertex points to a statement)
 *
 * - you don't know if dg is a graph or a multigraph; apparently it's
 * a multigraph but there is no clear semantics attaches to the different
 * arcs joining a pair of vertices (Pierre Jouvelot, help!)
 *
 * - conflicts are assumed uniquely identifiable by the addresses of their
 * two effects (and by labelling the same pair of vertices - but not the
 * same arc); that calls for tricky bugs if some sharing between effects
 * exists.
 *
 * The procedure is made of many too many nested loops and tests:
 *
 * for all vertex v1 in graph dg
 *   if statement s1 associated to v1 in region
 *     for all arcs a1 outgoing from v1
 *       let v2 be the sink of a1 and s2 the statement associated to v2
 *         if s2 in region
 *           for all conflicts c12 carried by a1
 *             if c12 has not yet been refined
 *               if c12 may have a symmetric conflict
 *                 for all arcs a2 outgoing from the sink v2 of a1
 *                   if sink(a2) equals v1
 *                     for all conflicts c21
 *                       if c21 equal c12
 *                         halleluia!
 *                         compute refined dependence information for c12
 *                         and possibly c21
 *                         possibly update c21 and possibly remove a2
 *                         update c12 and possibly remove a1
 *
 * Good luck for the restructuring! I'm not sure the current procedure
 * might not end up removing as a2 the very same arc a1 it uses to
 * iterate...
 */
 
static void rice_update_dependence_graph(statement stat, set region) {
  list pv1, ps, pss;
  list llv, llv1;
 
  pips_assert("statement is a loop", statement_loop_p(stat));
 
  pips_debug(1, "Begin\n");
 
  if(dg_type == DG_FULL) {
    pips_debug(1, "computing execution contexts\n");
    set_context_map(contexts_mapping_of_nest(stat));
  }
 
  llv = loop_variant_list(stat);
 
  ifdebug(6) {
    fprintf(stderr, "The list of loop variants is :\n");
    MAP(ENTITY, e, fprintf(stderr," %s", entity_local_name(e)), llv);
    fprintf(stderr, "\n");
  }
 
  for (pv1 = graph_vertices(dg); pv1 != NIL; pv1 = CDR(pv1)) {
    vertex v1 = VERTEX(CAR(pv1));
    dg_vertex_label dvl1 = (dg_vertex_label)vertex_vertex_label(v1);
    statement s1 = vertex_to_statement(v1);
 
    if(!set_belong_p(region, (char *)s1))
      continue;
 
    dg_vertex_label_sccflags(dvl1) = make_sccflags(scc_undefined, 0, 0, 0);
 
    ps = vertex_successors(v1);
    pss = NIL;
    while(ps != NIL) {
      successor su = SUCCESSOR(CAR(ps));
      vertex v2 = successor_vertex(su);
      statement s2 = vertex_to_statement(v2);
      dg_arc_label dal = (dg_arc_label)successor_arc_label(su);
      list true_conflicts = NIL;
      list pc, pchead;
 
      if(!set_belong_p(region, (char *)s2)) {
        pss = ps;
        ps = CDR(ps);
        continue;
      }
 
      pc = dg_arc_label_conflicts(dal);
      pchead = pc;
      while(pc != NIL) {
        conflict c = CONFLICT(CAR(pc));
        effect e1 = conflict_source(c);
        effect e2 = conflict_sink(c);
 
        ifdebug(4) {
          fprintf(stderr, "dep %02td (", statement_number(s1));
          print_words(stderr, words_effect(e1));
          fprintf(stderr, ") --> %02td (", statement_number(s2));
          print_words(stderr, words_effect(e2));
          fprintf(stderr, ") \n");
        }
 
        if(conflict_cone(c) != cone_undefined) {
          /* This conflict cone has been updated. */
          ifdebug(4) {
            fprintf(stderr, " \nThis dependence has been computed.\n");
          }
          true_conflicts = gen_nconc(true_conflicts, CONS(CONFLICT, c, NIL));
        } else { /*Compute this conflit and the opposite one */
          list ps2su = NIL, ps2sus = NIL, pcs2s1 = NIL, pchead1 = NIL;
          successor s2su = successor_undefined;
          vertex v1bis;
          statement s1bis;
          dg_arc_label dals2s1 = dg_arc_label_undefined;
          conflict cs2s1 = conflict_undefined;
          effect e1bis = effect_undefined, e2bis = effect_undefined;
          list levels = list_undefined;
          list levelsop = list_undefined;
          Ptsg gs = SG_UNDEFINED;
          Ptsg gsop = SG_UNDEFINED;
 
          Finds2s1 = false;
 
          /*looking for the opposite dependence from (s2,e2) to
           (s1,e1) */
 
          /* Make sure that you do not try to find the very same
           * conflict: eliminate symmetric conflicts like dd's,
           * and, if the KEEP-READ-READ-DEPENDENCE option is on,
           * the unusual uu's.
           */
          if(!((s1 == s2) && (action_write_p(effect_action(e1)))
              && (action_write_p(effect_action(e2)))) && !((s1 == s2)
              && (action_read_p(effect_action(e1)))
              && (action_read_p(effect_action(e2)))))
          /* && (reference_indices(effect_any_reference(e1))) != NIL) */
          {
            pips_debug (4, "looking for the opposite dependence");
 
            ps2su = vertex_successors(v2);
            ps2sus = NIL;
            while(ps2su != NIL && !Finds2s1) {
              s2su = SUCCESSOR(CAR(ps2su));
              v1bis = successor_vertex(s2su);
              s1bis = vertex_to_statement(v1bis);
              if(s1bis != s1) {
                ps2sus = ps2su;
                ps2su = CDR(ps2su);
                continue;
              } else {
                dals2s1 = (dg_arc_label)successor_arc_label(s2su);
                pcs2s1 = dg_arc_label_conflicts(dals2s1);
                pchead1 = pcs2s1;
                while((pcs2s1 != NIL) && !Finds2s1) {
                  cs2s1 = CONFLICT(CAR(pcs2s1));
                  e1bis = conflict_source(cs2s1);
                  e2bis = conflict_sink(cs2s1);
                  if(e1bis == e2 && e2bis == e1) {
                    Finds2s1 = true;
                    continue;
                  } else {
                    pcs2s1 = CDR(pcs2s1);
                    continue;
                  }
                }
                if(!Finds2s1) {
                  ps2sus = ps2su;
                  ps2su = CDR(ps2su);
                }
                continue;
              }
            }
 
            /* if (!Finds2s1)
             pips_internal_error("Expected opposite dependence are not found"); */
 
            if(Finds2s1) {
              ifdebug(4) {
                fprintf(stderr, "\n dep %02td (", statement_number(s2));
                print_words(stderr, words_effect(e1bis));
                fprintf(stderr, ") --> %02td (", statement_number(s1));
                print_words(stderr, words_effect(e2bis));
                fprintf(stderr, ") \n");
              }
            }
 
          }
 
          llv1 = gen_copy_seq(llv);
          /* freed in of leaked. */
          levels = TestCoupleOfEffects(s1,
                                       e1,
                                       s2,
                                       e2,
                                       llv1,
                                       &gs,
                                       &levelsop,
                                       &gsop);
 
          /* updating DG for the dependence (s1,e1)-->(s2,e2)*/
          if(levels == NIL) {
            debug(4, "", "\nThe dependence (s1,e1)-->(s2,e2)"
              " must be removed. \n");
 
            conflict_source(c) = effect_undefined;
            conflict_sink(c) = effect_undefined;
            free_conflict(c);
          } else {
            debug(4, "", "\nUpdating the dependence (s1,e1)-->(s2,e2)\n");
 
            if(!SG_UNDEFINED_P(gs))
              conflict_cone(c) = make_cone(levels, gs);
            else
              conflict_cone(c) = make_cone(levels, SG_UNDEFINED);
            true_conflicts = gen_nconc(true_conflicts, CONS(CONFLICT, c, NIL));
          }
 
          if(Finds2s1) {
            /* updating DG for the dependence (s2,e2)-->(s1,e1)*/
            if(levelsop == NIL) {
              debug(4, "", "\nThe dependence (s2,e2)-->(s1,e1)"
                " must be removed.\n");
 
              conflict_source(cs2s1) = effect_undefined;
              conflict_sink(cs2s1) = effect_undefined;
              /*gen_free(cs2s1);*/
 
              if(pchead == pchead1)
                /* They are in the same conflicts list */
                gen_remove(&pchead, cs2s1);
              else {
                gen_remove(&pchead1, cs2s1);
                if(pchead1 != NIL) {
                  dg_arc_label_conflicts(dals2s1) = pchead1;
                  successor_arc_label_(s2su) = newgen_arc_label(dals2s1);
                } else {
                  /* This successor has only one
                   conflict that has been killed.*/successor_vertex(s2su)
                      = vertex_undefined;
                  successor_arc_label_(s2su)
                      = (arc_label)dg_arc_label_undefined;
                  free_successor(s2su);
                  ps2su = CDR(ps2su);
                  if(ps2sus == NIL) {
                    vertex_successors(v2) = ps2su;
                  } else {
                    CDR(ps2sus) = ps2su;
                  }
                }
              }
            }
 
            else {
              debug(4, "", "\nUpdating the dependence (s2,e2)-->(s1,e1)\n");
 
              if(!SG_UNDEFINED_P(gsop))
                conflict_cone(cs2s1) = make_cone(levelsop, gsop);
              else
                conflict_cone(cs2s1) = make_cone(levelsop, SG_UNDEFINED);
            }
          }
        }
        pc = CDR(pc);
      }
 
      /* gen_free_list(dg_arc_label_conflicts(dal));*/
      if(true_conflicts != NIL) {
        dg_arc_label_conflicts(dal) = true_conflicts;
        pss = ps;
        ps = CDR(ps);
      } else {
        successor_vertex(su) = vertex_undefined;
        successor_arc_label_(su) = (arc_label)dg_arc_label_undefined;
        free_successor(su);
        ps = CDR(ps);
        if(pss == NIL)
          vertex_successors(v1) = ps;
        else
          CDR(pss) = ps;
      }
      /*ifdebug(4){ prettyprint_dependence_graph(stderr, mod_stat, dg); }*/
    }
  }
 
  ifdebug(8) {
    pips_debug(8,"updated graph\n");
    print_statement_set(stderr, region);
    prettyprint_dependence_graph(stderr, get_current_module_statement(), dg);
  }
 
  reset_context_map();
 
  // No leak
  gen_free_list(llv);
}
 
 
/*********************************************************************************/
/* DEPENDENCE TEST                                                               */
/*********************************************************************************/
 
static list TestCoupleOfEffects(statement s1,
                                effect e1,
                                statement s2,
                                effect e2,
                                list llv, /* must be freed */
                                Ptsg * gs,
                                list * levelsop,
                                Ptsg * gsop) {
  list n1 = load_statement_enclosing_loops(s1);
  Psysteme sc1 = SC_UNDEFINED;
  reference r1 = effect_any_reference( e1 );
 
  list n2 = load_statement_enclosing_loops(s2);
  Psysteme sc2 = SC_UNDEFINED;
  reference r2 = effect_any_reference(e2);
 
  switch(dg_type) {
    case DG_FAST: {
      /* use region information if some is available */
      sc1 = effect_system(e1);
      sc2 = effect_system(e2);
      break;
    }
 
    case DG_FULL: {
      sc1 = load_statement_context(s1);
      sc2 = load_statement_context(s2);
      break;
    }
 
    case DG_SEMANTICS: {
      /* This is not correct because loop bounds should be frozen on
       loop entry; we assume variables used in loop bounds are not
       too often modified by the loop body */
      transformer t1 = load_statement_precondition(s1);
      transformer t2 = load_statement_precondition(s2);
 
      sc1 = (Psysteme)predicate_system(transformer_relation(t1));
      sc2 = (Psysteme)predicate_system(transformer_relation(t2));
      break;
    }
 
    default:
      pips_internal_error("Unknown dependence test %d\n", dg_type);
      break;
  }
 
  return TestCoupleOfReferences(n1,
                                sc1,
                                s1,
                                e1,
                                r1,
                                n2,
                                sc2,
                                s2,
                                e2,
                                r2,
                                llv,
                                gs,
                                levelsop,
                                gsop);
}
 
/*
 * This function checks if two references have memory locations in common.
 *
 * The problem is obvious for references to the same scalar variable.
 *
 * The problem is also obvious if the references are not to the same
 * variable, except if the two variables have memory locations in common,
 * in which case we assume there are common locations and all kind of
 * dependences (although offsets in COMMON could be taken into account).
 *
 * When both references are to the same array variable, the function
 * TestDependence() is called.
 *
 * FI: When both references are relative to the same pointer variable, the
 * variable value is *assumed* to be the same in the two statements and
 * the function TestDependence() is called. Transformers on pointers
 * should be used to check that the pointer value is constant. The
 * simplest transformer would be the written memory effects for the
 * common enclosing loop.
 */
 
list TestCoupleOfReferences(list n1,
                            Psysteme sc1 __attribute__ ((unused)),
                            statement s1,
                            effect ef1,
                            reference r1,
                            list n2,
                            Psysteme sc2 __attribute__ ((unused)),
                            statement s2,
                            effect ef2,
                            reference r2,
                            list llv,
                            Ptsg * gs __attribute__ ((unused)),
                            list * levelsop __attribute__ ((unused)),
                            Ptsg * gsop __attribute__ ((unused))) {
  _int i, cl, dims, ty;
  list levels = NIL, levels1 = NIL;
 
  entity e1 = reference_variable(r1);
  entity e2 = reference_variable(r2);
 
  list b1 = reference_indices(r1);
  list b2 = reference_indices(r2);
 
  type t1 = ultimate_type(entity_type(e1));
 
  if(e1 != e2) {
    ifdebug(1) {
      fprintf(stderr, "dep %02td (", statement_number(s1));
      print_words(stderr, words_effect(ef1));
      fprintf(stderr, ") --> %02td (", statement_number(s2));
      print_words(stderr, words_effect(ef2));
      fprintf(stderr, ") \n");
    }
    pips_user_warning("Dependence between differents variables: "
        "%s and %s\nDependence assumed\n",
        entity_user_name(e1), entity_user_name(e2));
  }
 
  /* if (e1 == e2 && !entity_scalar_p(e1) && !entity_scalar_p(e2)) */
  /* FI: Why have two tests under the condition e1==e2? */
 
  /* FI: this test must be modified to take pointer dereferencing
   * such as p[i] into account, although p as an entity generates
   * atomic references.
   *
   * If chains.c were updated, we could also check that:
   * gen_length(b1)==gen_length(b2).
   */
  if(e1 == e2 && !entity_all_locations_p(e1) && !entity_all_locations_p(e2)
      && (!entity_atomic_reference_p(e1) || (pointer_type_p(t1)
          && gen_length(b1) > 0))) {
    if(get_bool_property("RICEDG_STATISTICS_ALL_ARRAYS")) {
      NbrArrayDepInit++;
    } else {
      if(b1 != NIL && b2 != NIL)
        NbrArrayDepInit++;
    }
 
    if(b1 == NIL || b2 == NIL) {
      /* A(*) reference appears in the dependence graph */
      cl = FindMaximumCommonLevel(n1, n2);
 
      for (i = 1; i <= cl; i++)
        levels = gen_nconc(levels, CONS(INT, i, NIL));
 
      if(statement_possible_less_p(s1, s2))
        levels = gen_nconc(levels, CONS(INT, cl+1, NIL));
 
      if(Finds2s1) {
        for (i = 1; i <= cl; i++)
          levels1 = gen_nconc(levels1, CONS(INT, i, NIL));
 
        if(statement_possible_less_p(s2, s1))
          levels1 = gen_nconc(levels1, CONS(INT, cl+1, NIL));
 
        *levelsop = levels1;
      }
 
      gen_free_list(llv);
    } else {
      /* llv is freed here */
      levels = TestDependence(n1,
                              sc1,
                              s1,
                              ef1,
                              r1,
                              n2,
                              sc2,
                              s2,
                              ef2,
                              r2,
                              llv,
                              gs,
                              levelsop,
                              gsop);
    }
 
    if(get_bool_property("RICEDG_STATISTICS_ALL_ARRAYS") || (b1 != NIL && b2
        != NIL)) {
      if(levels != NIL) {
        /* test the dependence type, constant dependence?  */
        dims = gen_length(b1);
        ty = dep_type(effect_action(ef1), effect_action(ef2));
        deptype[dims][ty]++;
        if(is_dep_cnst) {
          NbrDepCnst++;
          constdep[dims][ty]++;
        }
      }
 
      if(*levelsop != NIL) {
        /* test the dependence type, constant dependence?
         exact dependence? */
        dims = gen_length(b1);
        ty = dep_type(effect_action(ef2), effect_action(ef1));
        deptype[dims][ty]++;
        if(is_dep_cnst) {
          NbrDepCnst++;
          constdep[dims][ty]++;
        }
      }
 
      if(levels != NIL || *levelsop != NIL) {
        if(is_test_exact)
          NbrTestExact++;
        else {
          if(is_test_inexact_eq) {
            if(is_test_inexact_fm)
              NbrDepInexactEFM++;
            else
              NbrDepInexactEq++;
          } else
            NbrDepInexactFM++;
        }
      }
 
      ifdebug(6) {
        if(is_test_exact)
          fprintf(stderr, "\nThis test is exact! \n");
        else if(is_test_inexact_eq)
          fprintf(stderr, "\nTest not exact : "
            "non-exact elimination of equation!");
        else
          fprintf(stderr, "\nTest not exact : "
            "non-exact elimination of F-M!");
      }
    }
 
    return (levels);
  } else {
    /* the case of scalar variables and equivalenced arrays */
 
    // llv is no longer used
    gen_free_list(llv);
 
    cl = FindMaximumCommonLevel(n1, n2);
 
    for (i = 1; i <= cl; i++)
      levels = gen_nconc(levels, CONS(INT, i, NIL));
 
    if(statement_possible_less_p(s1, s2))
      levels = gen_nconc(levels, CONS(INT, cl+1, NIL));
 
    if((instruction_loop_p(statement_instruction(s1)))
        || instruction_loop_p(statement_instruction(s2)))
      NbrIndexDep++;
    else {/*scalar variable dependence */
      NbrScalDep++;
      ty = dep_type(effect_action(ef1), effect_action(ef2));
      deptype[0][ty]++;
    }
 
    if(Finds2s1) {
      for (i = 1; i <= cl; i++)
        levels1 = gen_nconc(levels1, CONS(INT, i, NIL));
 
      if(statement_possible_less_p(s2, s1))
        levels1 = gen_nconc(levels1, CONS(INT, cl+1, NIL));
 
      *levelsop = levels1;
      if((instruction_loop_p(statement_instruction(s1)))
          || instruction_loop_p(statement_instruction(s2)))
        NbrIndexDep++;
      else {/*case of scalar variable dependence */
        NbrScalDep++;
        ty = dep_type(effect_action(ef2), effect_action(ef1));
        deptype[0][ty]++;
      }
    }
 
    return (levels);
  }
}
 
/* static list TestDependence(list n1, n2, Psysteme sc1, sc2,
 *                             statement s1, s2, effect ef1, ef2,
 *                             reference r1, r2, list llv,
 *                             list *levelsop, Ptsg *gs,*gsop)
 * input    :
 *      list n1, n2      : enclosing loops for statements s1 and s2;
 *      Psysteme sc1, sc2: current context for each statement;
 *      statement s1, s2 : currently analyzed statements;
 *      effect ef1, ef2  : effects of each statement upon the current variable;
 *                         (maybe array regions)
 *      reference r1, r2 : current variables references;
 *      list llv         : loop variant list
 *                         (variables that vary in loop nests n1 and n2?);
 *      list *levelsop   : dependence levels from s2 to s1
 *      Ptsg *gs,*gsop   : dependence cones from s1 to s2 and from s2 to s1
 * output   : dependence levels from s1 to s2
 * modifies : levelsop, gsop, gs and returns levels
 *
 * Comments :
 *
 * This procedure has been amplified twice. The initial procedure
 * only computed the dependence levels, "levels", for conflict s1->s2.
 * The dependence cone computation was added by Yi-Qing Yang. She later
 * added the computation of the dependence levels and the dependence cone
 * for symetrical conflict, s2 -> s1, because both conflicts share the
 * same dependence system and because a set of tests can be shared.
 *
 * For her PhD, Yi-Qing Yang also added intermediate tests and instrumentation.
 *
 * This much too long procedure is made of three parts:
 *  0. The initialization of the dependence system
 *  1. A set of feasibility tests applied to the dependence system
 *  2. The computation of levels and cone for s1->s2
 *  3. The very same computation for s2->s1
 *
 * Modification :
 *
 * - ajout des tests de faisabilites pour le systeme initial,
 * avant la projection. Yi-Qing (18/10/91)
 *
 * - decoupage de la procedure par Beatrice Creusillet
 *
 * - (indirect) build_and_test_dependence_context(), in fact system, no
 *   longer has side effects on sc1 and sc2 thru sc_normalize(); FI (12/12/95)
 *
 * - sc_rm() uncommented out after call to gcd_and_constant_dependence_test()
 *
 * - base_rm(tmp_base) added after call to sc_proj_optim_on_di_ofl() just
 *   before returning with levels==NIL
 *
 * - sc_rm() added for dep_syst, dep_syst1, dep_syst_op and dep_syst2
 */
static list TestDependence(list n1,
                           Psysteme sc1,
                           statement s1,
                           effect ef1,
                           reference r1,
                           list n2,
                           Psysteme sc2,
                           statement s2,
                           effect ef2,
                           reference r2,
                           list llv,
                           Ptsg * gs,
                           list * levelsop,
                           Ptsg * gsop) {
  Psysteme dep_syst = SC_UNDEFINED;
  Psysteme dep_syst1 = SC_UNDEFINED;
  Psysteme dep_syst2 = SC_UNDEFINED;
  volatile Psysteme dep_syst_op = SC_UNDEFINED;
  Pbase b, coord;
  /* Automatic variables read in a CATCH block need to be declared volatile as
   * specified by the documentation*/
  Pbase volatile tmp_base;
 
  int l, cl;
  list levels;
  Pvecteur DiIncNonCons = NULL;
 
  /* Elimination of loop indices from loop variants llv */
  /* We use n2 because we take care of variables modified in
   an iteration only for the second system. */
  FOREACH(STATEMENT, s, n2) {
    entity i = loop_index(statement_loop(s));
    gen_remove(&llv,i); /* llv is dead, must be freed... */
  }
 
  ifdebug(6) {
    pips_debug(6, "loop variants after removing loop indices :\n");
    print_arguments(llv);
  }
 
  /* Build the dependence context system from the two initial context systems
   * sc1 and sc2. BC
   */
  if(!build_and_test_dependence_context(r1, r2, sc1, sc2, &dep_syst, llv, n2)) {
    /* the context system is not feasible : no dependence. BC */
    /* No dep_syst() to deallocate either, FI */
    NbrIndepFind++;
    pips_debug(4, "context system not feasible\n");
    *levelsop = NIL;
 
    gen_free_list(llv);
    return NIL;
  }
 
  /* Further construction of the dependence system; Constant and GCD tests
   * at the same time.
   */
 
  // FI: why is dep_syst only weekly consistent here?
  assert(sc_weak_consistent_p(dep_syst));
 
  if(gcd_and_constant_dependence_test(r1, r2, llv, n2, &dep_syst)) {
    /* independence proved */
    /* FI: the next statement was commented out... */
    sc_rm(dep_syst);
    NbrIndepFind++;
    *levelsop = NIL;
 
    gen_free_list(llv);
    return NIL;
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  gen_free_list(llv);
 
  dependence_system_add_lci_and_di(&dep_syst, n1, &DiIncNonCons);
 
  ifdebug(6) {
    fprintf(stderr, "\ninitial system is:\n");
    sc_syst_debug(dep_syst);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  /* Consistency Test */
  if(sc_empty_p(dep_syst = sc_normalize(dep_syst))) {
    sc_rm(dep_syst);
    NbrTestSimple++;
    NbrIndepFind++;
    pips_debug(4, "initial normalized system not feasible\n");
    *levelsop = NIL;
 
    return (NIL);
  }
 
  cl = FindMaximumCommonLevel(n1, n2);
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  if(TestDiCnst(dep_syst, cl, s1, ef1, s2, ef2) == true) {
    /* find independences (non loop carried dependence, intra-statement).*/
    /* Such dependences are counted here as independence, but other
     * parallelizer preserve them because they are useful for
     * (assembly) instructon level scheduling
     */
    NbrTestDiCnst++;
    NbrIndepFind++;
    pips_debug(4,"\nTestDiCnst succeeded!\n");
    *levelsop = NIL;
 
    return (NIL);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  is_test_exact = true;
  is_test_inexact_eq = false;
  is_test_inexact_fm = false;
  is_dep_cnst = false;
 
  tmp_base = base_dup(dep_syst->base);
 
  CATCH(overflow_error) {
    /* Some kind of arithmetic error, e.g. an integer overflow
     * has occured. Assume dependence to be conservative.
     */
    Pbase dep_syst_base = BASE_UNDEFINED;
 
    /* FI: wouldn't it be simpler to enumerate the useful di
     * variables?!?
     */
    /* eliminate non di variables from the basis */
    for (coord = tmp_base; !VECTEUR_NUL_P(coord); coord = coord->succ) {
      Variable v = vecteur_var(coord);
      l = DiVarLevel((entity)v);
      if(l <= 0 || l > cl)
        base_add_variable(dep_syst_base, v);
    }
    dep_syst = sc_rn(dep_syst_base);
  } TRY {
    if(sc_proj_optim_on_di_ofl(cl, &dep_syst) == false) {
      pips_debug(4,
          "projected system by sc_proj_optim_on_di() is not feasible\n");
      sc_rm(dep_syst);
      NbrIndepFind++;
      *levelsop = NIL;
 
      UNCATCH(overflow_error);
      base_rm(tmp_base);
      return (NIL);
    } else
      UNCATCH(overflow_error);
  }
 
  ifdebug(6) {
    fprintf(stderr, "projected system is:\n");
    sc_syst_debug(dep_syst);
  }
 
  pips_assert("The dependence system is consistent", sc_consistent_p(dep_syst));
 
  base_rm(tmp_base); // FI: delayed to help with debugging
 
  if(!sc_faisabilite_optim(dep_syst)) {
    /* Here, the long jump overflow buffer is handled at a lower level! */pips_debug(4, "projected system not feasible\n");
    NbrIndepFind++;
    *levelsop = NIL;
 
    return (NIL);
  }
 
  ifdebug(6) {
    fprintf(stderr, "normalised projected system is:\n");
    sc_syst_debug(dep_syst);
    fprintf(stderr, "The list of DiIncNonCons is :\n");
    vect_debug(DiIncNonCons);
  }
 
  /* keep DiIncNonCons variables if their value is unknown or different
   * from zero. Otherwise eliminate them from the dep_syst
   *
   * FI: I'm lost for this step. My guess DiIncNonCons==VECTEUR_NUL
   * in 99.99 % of all cases...
   */
  if(dep_syst != NULL) {
    while(DiIncNonCons != NULL) {
      Variable di;
      Value val;
 
      di = DiIncNonCons->var;
      if(sc_value_of_variable(dep_syst, di, &val) == true)
        if(value_notzero_p(val)) {
          sc_elim_var(dep_syst, di);
        }
      DiIncNonCons = DiIncNonCons->succ;
    }
  }
 
  ifdebug(4) {
    fprintf(stderr,
            "normalised projected system after DiIncNonCons elimination is:\n");
    sc_syst_debug(dep_syst);
  }
 
  /* Compute the levels for dependence arc s1 to s2 and of the opposite
   * dependence arc s2 to s1. Also compute the dependence cones if some
   * level exists (FI: shouldn't it be a loop-carried level?).
   *
   * For both cases, two systems are allocated, one is used to find the
   * dependence levels, the other one to compute the dependence cone.
   *
   * For s1->s2, dep_syst is used to compute the levels and dep_syst1
   * the cone.
   *
   * For s2->s1, dep_syst_op (op==oppposite) is used to find the dependence
   * levels, and dep_syst2 the dependence cone.
   */
 
  /* Build the dependence system for the opposite arc s2->s1
   * before dep_syst is modified
   */
 
  *levelsop = NIL;
  if(Finds2s1)
    dep_syst_op = sc_invers(sc_dup(dep_syst));
 
  /* Start processing for arc s1->s2 */
 
  ifdebug(4) {
    debug(4, "", "\nComputes the levels and DC for dep: (s1,e1)->(s2,e2)\n");
    fprintf(stderr, "\nThe distance system for dep is:\n");
    sc_syst_debug(dep_syst);
  }
 
  /* Make a proper copy of dep_syst before it is destroyed to compute
   * dependence levels. The basis must be in a specific order to check
   * lexico-positivity.
   */
  dep_syst1 = sc_dup(dep_syst);
  b = MakeDibaseinorder(cl);
  base_rm(dep_syst1->base);
  dep_syst1->base = b;
  dep_syst1->dimension = cl;
 
  if(dep_syst1->dimension == dep_syst1->nb_eq)
    is_dep_cnst = true;
 
  /* Compute dependence levels for s1->s2 */
  levels = TestDiVariables(dep_syst, cl, s1, ef1, s2, ef2);
  /* dep_syst is unfeasible or almost empty, and now useless */
  sc_rm(dep_syst);
 
  /* if (levels == NIL) NbrTestDiVar++;  Qui l'a enleve', pourquoi ? */
 
  if(levels != NIL) {
 
    *gs = dependence_cone_positive(dep_syst1);
 
    /* If the cone is not feasible, there are no loop-carried dependences.
     * (FI: the cone is strictly positive then...)
     *
     * This might not havebeen found by the previous test when computing
     * levels.
     *
     * But the dependence cone construction does not consider non-loop
     * carried dependences; so we can only remove those levels that are
     * smaller than the number of common levels
     */
    if(sg_empty(*gs)) {
      list l_tmp = levels;
      bool ok = false;
 
      pips_debug(5, "dependence cone not feasible\n");
      MAP(INT, ll, {if (ll == cl+1) ok = true;}, l_tmp);
 
      if(ok) {
        pips_debug(5, "innermost level found and kept\n");
        levels = CONS(INT, cl+1, NIL);
      } else {
        pips_debug(5, "innermost level not found, no dependences");
        levels = NIL;
      }
      gen_free_list(l_tmp);
      sg_rm(*gs);
      *gs = SG_UNDEFINED;
    }
  }
  sc_rm(dep_syst1);
 
  /* print results for arc s1->s2 */
 
  ifdebug(4) {
    fprintf(stderr, "\nThe levels for dep (s1,s2) are:");
    MAP(INT, pl,
        {
          fprintf(stderr, " %d", pl);
        }, levels);
 
    if(!SG_UNDEFINED_P(*gs)) {
      fprintf(stderr, "\nThe lexico-positive dependence cone for"
        " dep (s1,s2) :\n");
      print_dependence_cone(stderr, *gs, b);
    } else
      fprintf(stderr, "\nLexico-positive dependence cone"
        " doesn't exist for dep (s1,s2).\n");
  }
 
  /* Start the processing for arc s2->s1 */
 
  if(Finds2s1) {
 
    pips_debug(4,"Computes the levels and DC for dep_op: (s2,e2)->(s1,e1)\n");
    ifdebug(4) {
      fprintf(stderr, "\nThe invers distance system for dep_op is:\n");
      sc_syst_debug(dep_syst_op);
    }
 
    dep_syst2 = sc_dup(dep_syst_op);
    b = MakeDibaseinorder(cl);
    base_rm(dep_syst2->base);
    dep_syst2->base = b;
    dep_syst2->dimension = cl;
 
    *levelsop = TestDiVariables(dep_syst_op, cl, s2, ef2, s1, ef1);
    sc_rm(dep_syst_op);
    if(*levelsop != NIL) {
      /* if (*levelsop == NIL) NbrTestDiVar++;  Pourquoi? */
      *gsop = dependence_cone_positive(dep_syst2);
      sc_rm(dep_syst2);
 
      /* if the cone is not feasible, there are no loop-carried dependences;
       * this was not found by the previous test when computing levels;
       * but the dependence cone construction does not consider non-loop
       * carried dependences; so we can only remove those levels that are
       * smaller than the number of common levels
       */
      if(sg_empty(*gsop)) {
        list l_tmp = *levelsop;
        bool ok = false;
 
        MAP(INT, ll, {if (ll == cl+1) ok = true;}, l_tmp);
 
        if(ok) {
          *levelsop = CONS(INT, cl+1, NIL);
        } else {
          *levelsop = NIL;
        }
        gen_free_list(l_tmp);
        sg_rm(*gsop);
        *gsop = SG_UNDEFINED;
      }
    }
 
    ifdebug(4) {
      fprintf(stderr, "\nThe levels for dep_op (s2,s1) is:");
      MAP(INT, pl,
          {
            fprintf(stderr, " %d", pl);
          }, *levelsop);
 
      if(!SG_UNDEFINED_P(*gsop)) {
        fprintf(stderr, "\nThe lexico-positive Dependence "
          "cone for dep_op (s2,s1):\n");
        print_dependence_cone(stderr, *gsop, b);
      } else
        fprintf(stderr, "\nLexico-positive dependence cone "
          "does not exist for dep_op (s2,s1).\n");
 
    }
  }
 
  if(levels == NIL && *levelsop == NIL) {
    NbrTestDiVar++;
    NbrIndepFind++;
    if(s1 == s2) {
      /* the case of "all equals" independence at the same statement*/
      NbrAllEquals++;
    }
 
    return (NIL);
  }
 
  return (levels);
}
 
 
/* static bool build_and_test_dependence_context(reference r1, r2,
 *                                                  Psystem sc1, sc2, *psc_dep,
 *                                                  list llv, s2_enc_loops)
 * input    :
 *      reference r1, r2  : current array references;
 *      Psystem sc1, sc2  : context systems for r1 and r2;
 *                          they might be modified and even be freed (!)
 *                          by normalization procedures
 *      Psystem *psc_dep  : pointer toward the dependence context systeme;
 *      list llv          : current loop nest variant list;
 *      list s2_enc_loops : statement s2 enclosing loops;
 *
 * output  :
 *      bool           : false if one of the initial systems is unfeasible
 *                          after normalization;
 *                          true otherwise;
 *      *psc_dep          : dependence system is the function value is true;
 *                          SC_EMPTY otherwise; no need to sc_rm() in the
 *                          latter case.
 *
 * side effects :
 *      psc_dep           : points toward the dependence context system built
 *                          from sc1 and sc2, r1 and r2, and llv.
 *                          Dependence distance variables (di) are introduced
 *                          in sc2, along with the dsi variables to take care
 *                          of variables in llv
 *                          modified in the loop nest;
 *                          irrelevant (?) existencial constraints are removed.
 *                          in order to make further manipulations easier.
 *      sc1               : side_effect of sc_normalize()
 *      sc2               : side_effect of sc_normalize()
 *
 * Comment  :
 *
 * Modifications:
 *  - sc1 and sc2 cannot be sc_normalized because they may be part of
 *    statement preconditions or regions; sc_normalize() is replaced by
 *    sc_empty_p(); since regions and preconditions are normalized with
 *    stronger normalization procedure, and since the feasibility of the
 *    dependence test will be tested with an even stronger test, this
 *    should have no accuracy impact (FI, 12 December 1995)
 */
static bool build_and_test_dependence_context(reference r1,
                                              reference r2,
                                              Psysteme sc1,
                                              Psysteme sc2,
                                              Psysteme * psc_dep,
                                              list llv,
                                              list s2_enc_loops) {
  Psysteme sc_dep, sc_tmp;
  list pc;
  int l, inc;
 
  /* *psc_dep must be undefined */pips_assert("build_and_test_dependence_context", SC_UNDEFINED_P(*psc_dep));
 
  /* Construction of initial systems sc_dep and sc_tmp from sc1 and sc2
   if not undefined
   */
  if(SC_UNDEFINED_P(sc1) && SC_UNDEFINED_P(sc2)) {
    sc_dep = sc_new();
  } else {
    if(SC_UNDEFINED_P(sc1))
      sc_dep = sc_new();
    else {
      /* sc_dep = sc1, but:
       * we keep only useful constraints in the predicate
       * (To avoid overflow errors, and to make projections easier)
       */
      Pbase variables = BASE_UNDEFINED;
 
      if(sc_empty_p(sc1)) {
        *psc_dep = SC_EMPTY;
        pips_debug(4,
            "first initial normalized system sc1 not feasible\n");
        return (false);
      }
 
      ifdebug(6) {
        debug(6, "", "Initial system sc1 before restrictions : \n");
        sc_syst_debug(sc1);
      }
 
      FOREACH(EXPRESSION, ex1,reference_indices(r1)) {
        normalized x1 = NORMALIZE_EXPRESSION(ex1);
 
        if(normalized_linear_p(x1)) {
          Pvecteur v1;
          Pvecteur v;
          v1 = (Pvecteur)normalized_linear(x1);
          for (v = v1; !VECTEUR_NUL_P(v); v = v->succ) {
            if(vecteur_var(v) != TCST)
              variables = base_add_variable(variables, vecteur_var(v));
          }
        }
      }
 
      sc_dep = sc_restricted_to_variables_transitive_closure(sc1, variables);
    }
 
    if(SC_UNDEFINED_P(sc2))
      sc_tmp = sc_new();
    else {
      /* sc_tmp = sc2, but:
       * we keep only useful constraints in the predicate
       * (To avoid overflow errors, and to make projections easier)
       *
       * FI: I'm not sure this is correct. I'm afraid sc2 might
       * be unfeasible and become feasible due to a careless
       * elimination... It all depends on:
       *
       *     sc_restricted_to_variables_transitive_closure()
       *
       * There might be a better function for that purpose
       */
      Pbase variables = BASE_UNDEFINED;
 
      if(sc_empty_p(sc2)) {
        *psc_dep = SC_EMPTY;
        pips_debug(4,
            "second initial normalized system not feasible\n");
        return (false);
      }
 
      ifdebug(6) {
        debug(6, "", "Initial system sc2 before restrictions : \n");
        sc_syst_debug(sc2);
      }
 
      FOREACH(EXPRESSION, ex2, reference_indices(r2)) {
        normalized x2 = NORMALIZE_EXPRESSION(ex2);
 
        if(normalized_linear_p(x2)) {
          Pvecteur v2;
          Pvecteur v;
 
          v2 = (Pvecteur)normalized_linear(x2);
          for (v = v2; !VECTEUR_NUL_P(v); v = v->succ) {
            if(vecteur_var(v) != TCST)
              variables = base_add_variable(variables, vecteur_var(v));
          }
 
        }
      }
 
 
      sc_tmp = sc_restricted_to_variables_transitive_closure(sc2, variables);
    }
 
    ifdebug(6) {
      debug(6, "", "Initial systems after restrictions : \n");
      sc_syst_debug(sc_dep);
      sc_syst_debug(sc_tmp);
    }
 
    /* introduce dependence distance variable if loop increment value
     is known or ... */
    for (pc = s2_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
      loop lo = statement_loop(STATEMENT(CAR(pc)));
      entity i2 = loop_index(lo);
      /* FI: a more powerful evaluation function for inc should be called
       * when preconditions are available. For instance, mdg could
       * be handled without having to partial_evaluate it
       *
       * It's not clear whether sc1 or sc2 should be used to
       * estimate a variable increment like N.
       *
       * It's not clear whether it's correct or not. You would like
       * N (or other variables in the increment expression) to be
       * constant within the loop nest.
       *
       * It would be better to know the precondition associated
       * to the corresponding loop statement, but the information
       * is lost in this low-level function.
       *
       * FI: this is not true, you have sc1 and sc2 at hand to call
       * sc_minmax_of_variable()
       */
      inc = loop_increment_value(lo);
      if(inc != 0)
        sc_add_di(l, i2, sc_tmp, inc);
      else
        sc_chg_var(sc_tmp, (Variable)i2, (Variable)GetLiVar(l));
    }
 
    /* take care of variables modified in the loop */
    for (pc = llv, l = 1; pc != NIL; pc = CDR(pc), l++) {
      sc_add_dsi(l, ENTITY(CAR(pc)), sc_tmp);
    }
 
    /* sc_tmp is emptied and freed by sc_fusion() */
    sc_dep = sc_fusion(sc_dep, sc_tmp);
    vect_rm(sc_dep->base);
    sc_dep->base = BASE_NULLE;
    sc_creer_base(sc_dep);
 
  }
 
  ifdebug(6) {
    pips_debug(6,
        "\ndependence context is:\n");
    sc_syst_debug(sc_dep);
  }
 
  *psc_dep = sc_dep;
  return (true);
}
 
/* static bool gcd_and_constant_dependence_test(references r1, r2,
 *                                                 list llv, s2_enc_loops,
 *                                                 Psysteme *psc_dep)
 * input    :
 *      references r1, r2 : current references;
 *      list llv          : loop nest variant list;
 *      list s2_enc_loops : enclosing loops for statement s2;
 *      Psysteme *psc_dep : pointer toward the depedence system;
 * output   : true if there is no dependence (GCD and constant test successful);
 *            false if independence could not be proved.
 * modifies : *psc_dep; at least adds dependence equations on phi variables
 * comment  :
 *  - *psc_dep must be defined on entry; it must have been initialized
 *    by build_and_test_dependence_context.
 *  - no side effects on r1, r2,...
 */
static bool gcd_and_constant_dependence_test(reference r1,
                                             reference r2,
                                             list llv,
                                             list s2_enc_loops,
                                             Psysteme * psc_dep) {
  list pc1, pc2, pc;
  int l;
 
  /* Further construction of the dependence system; Constant and GCD tests
   * at the same time.
   */
  pc1 = reference_indices(r1);
  pc2 = reference_indices(r2);
 
  while(pc1 != NIL && pc2 != NIL) {
    expression ex1, ex2;
    normalized x1, x2;
 
    ex1 = EXPRESSION(CAR(pc1));
    x1 = NORMALIZE_EXPRESSION(ex1);
 
    ex2 = EXPRESSION(CAR(pc2));
    x2 = NORMALIZE_EXPRESSION(ex2);
 
    if(normalized_linear_p(x1) && normalized_linear_p(x2)) {
      Pvecteur v1, v2, v;
 
      v1 = (Pvecteur)normalized_linear(x1);
      v2 = vect_dup((Pvecteur)normalized_linear(x2));
 
      for (pc = s2_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
        loop lo = statement_loop(STATEMENT(CAR(pc)));
        entity i = loop_index(lo);
        int li = loop_increment_value(lo);
        Value vli = int_to_value(li);
        if(value_notzero_p(vli)) {
          Value v = vect_coeff((Variable)i, v2);
          value_product(v,vli);
          vect_add_elem(&v2, (Variable)GetDiVar(l), v);
        } else
          vect_chg_var(&v2, (Variable)i, (Variable)GetLiVar(l));
      }
 
      for (pc = llv, l = 1; pc != NIL; pc = CDR(pc), l++) {
        vect_add_elem(&v2,
                      (Variable)GetDsiVar(l),
                      vect_coeff((Variable)ENTITY(CAR(pc)), v2));
      }
 
      if(!VECTEUR_UNDEFINED_P(v = vect_substract(v1, v2))) {
        Pcontrainte c = contrainte_make(v);
 
        /* case of T(3)=... et T(4)=... */
        if(contrainte_constante_p(c) && value_notzero_p(COEFF_CST(c))) {
          NbrTestCnst++;
          pips_debug(4,"TestCnst succeeded!");
          return (true);
        }
        /* test of GCD */
        if(egalite_normalize(c) == false) {
          NbrTestGcd++;
          pips_debug(4,"TestGcd succeeded!\n");
          return (true);
        }
        sc_add_eg(*psc_dep, c);
      }
      vect_rm(v2);
    }
 
    pc1 = CDR(pc1);
    pc2 = CDR(pc2);
  }
 
  if(pc1 != NIL || pc2 != NIL) {
    if(fortran_module_p(get_current_module_entity())) {
      pips_internal_error("numbers of subscript expressions differ");
    } else {
      /* C assumed */
      pips_user_warning("dependence tested between two memory access paths"
                        " of different lengths for variable \"%s\".\n",
                        entity_user_name(reference_variable(r1)));
    }
  }
 
  /* Update base of *psc_dep */
  Pbase mb = sc_to_minimal_basis(*psc_dep);
  Pbase cb = sc_base(*psc_dep);
  if(!vect_in_basis_p(mb, cb)) {
    Pbase nb = base_union(cb, mb);
    sc_base(*psc_dep) = nb;
    sc_dimension(*psc_dep) = vect_size(nb); // base_dimension(nb);
    vect_rm(cb);
  }
  vect_rm(mb);
 
  pips_assert("The dependence system is consistent", sc_consistent_p(*psc_dep));
 
  return (false);
}
 
/* static void dependence_system_add_lci_and_di(Psysteme *psc_dep,
 *                                              list s1_enc_loops,
 *                                              Pvecteur *p_DiIncNonCons)
 * input    :
 *      Psysteme *psc_dep : pointer toward the dependence system;
 *      list s1_enc_loops : statement s1 enclosing loops;
 *      Pvecteur *p_DiIncNonCons : pointer toward DiIncNonCons.
 *
 * output   : none
 *
 * modifies :
 *
 *  *psc_dep, the dependence systeme (addition of constraints with lci and di
 *            variables, if useful; lci is a loop counter, di an iteration
 *            difference variable);
 *
 *  DiIncNonCons: di variables are added to DiIncNonCons (means Di variables
 *            for loops with non constant increment, i.e. unknown increment),
 *            if any such loop exists.
 *
 * comment  : DiIncNonCons must be undefined on entry.
 */
static void dependence_system_add_lci_and_di(psc_dep,
                                             s1_enc_loops,
                                             p_DiIncNonCons)
  Psysteme *psc_dep;list s1_enc_loops;Pvecteur *p_DiIncNonCons; {
  int l;
  list pc;
 
  pips_assert("dependence_system_add_lci_and_di",
      VECTEUR_UNDEFINED_P(*p_DiIncNonCons));
 
  /* Addition of lck, the loop counters, and di, the iteration difference,
   * variables (if useful).
   */
  for (pc = s1_enc_loops, l = 1; pc != NIL; pc = CDR(pc), l++) {
    loop lo = statement_loop(STATEMENT(CAR(pc)));
    entity ind = loop_index(lo);
    int inc = loop_increment_value(lo);
 
    expression lb = range_lower(loop_range(lo));
    normalized nl = NORMALIZE_EXPRESSION(lb);
 
    /* If the loop increment is not trivial, express the current
     * index value as the sum of the lower bound and the product
     * of the loop counter by the loop increment.
     *
     * Else, this new equation would be redundant
     */
    /* make   nl + inc*lc# - ind = 0 */
    if(inc != 0 && inc != 1 && inc != -1 && normalized_linear_p(nl)) {
      Pcontrainte pc;
      entity lc;
      Pvecteur pv;
 
      lc = MakeLoopCounter();
      pv = vect_dup((Pvecteur)normalized_linear(nl));
      vect_add_elem(&pv, (Variable)lc, inc);
      vect_add_elem(&pv, (Variable)ind, -1);
      pc = contrainte_make(pv);
      sc_add_eg(*psc_dep, pc);
    }
 
    /* If the loop increment is unknown, which is expressed by inc==0,
     * well, I do not understand what li variables are, not how they work
     */
    /* make d#i - l#i + ind = 0 ,
     add d#i in list of DiIncNonCons*/
    if(inc == 0) {
      Pcontrainte pc;
      Pvecteur pv = NULL;
      entity di;
 
      di = GetDiVar(l);
      vect_add_elem(&pv, (Variable)di, 1);
      vect_add_elem(&pv, (Variable)GetLiVar(l), -1);
      vect_add_elem(&pv, (Variable)ind, 1);
      pc = contrainte_make(pv);
      sc_add_eg(*psc_dep, pc);
 
      vect_add_elem(p_DiIncNonCons, (Variable)di, 1);
    }
 
  }
 
  /* Update basis */
  if(!BASE_NULLE_P((*psc_dep)->base)) {
    vect_rm((*psc_dep)->base);
    (*psc_dep)->base = BASE_UNDEFINED;
  }
  sc_creer_base(*psc_dep);
}
 
 
 
/*
 * This function implements one of the last steps of the CRI dependence test.
 *
 * System ps has been projected on di variables. ps is examined to find
 * out the set of possible values for di variables, the iteration differences
 * for which a dependence exist.
 *
 * Loops are numbered from 1 to cl, the maximum nesting level.
 * At each step, the di variable corresponding to the current nesting level
 * is examined.
 *
 * Dependences levels added to the graph depend on the sign of the values
 * computed for di. There is a dependence from s1 to s2 if di can be
 * positive and from s2 to s1 if di can be negative.
 *
 * There are no loop-carried dependence if di is equal to zero. The
 * corresponding level is cl+1.
 *
 * Finally, di is set to 0 at the end of the loop since
 * dependences at level l are examined assuming the enclosing loops are
 * at the same iteration.
 *
 * Input:
 *
 *   ps is the projected system (the distance system for the dep: (s1->s2).
 *      a copy of ps, pss is allocated to compute di's value, but ps is
 *      modified until it is empty (all di variables have been projected),
 *      or until it is unfeasible (this is detected on pss)
 *
 *   cl is the common nesting level of statement s1 and s2.
 *
 * Temporaries:
 *
 *   pss is deallocated by sc_minmax_of_variable_optim()
 *
 * Modification :
 *
 * -  variable NotPositive added to take into acounnt the case di<=0.
 *    Yi Qing (10/91)
 */
 
static list TestDiVariables(Psysteme ps,
                            int cl,
                            statement s1,
                            effect ef1 __attribute__ ((unused)),
                            statement s2,
                            effect ef2 __attribute__ ((unused))) {
  list levels = NIL;
  _int l;
  bool all_level_founds = false;
 
  pips_debug(7, "maximum common level (cl): %d\n", cl);
 
  for (l = 1; !all_level_founds && l <= cl; l++) {
    Variable di = (Variable)GetDiVar(l);
    Value min, max;
    int IsPositif, IsNegatif, IsNull, NotPositif;
    /* FI: Keep a consistent interface in memory allocation */
    /* Psysteme pss = (l==cl) ? ps : sc_dup(ps); */
    Psysteme pss = sc_dup(ps);
 
    ifdebug(7) {
      pips_debug(7, "current level: %td, variable: %s\n",
          l, entity_local_name((entity) di));
    }
 
    if(sc_minmax_of_variable_optim(pss, di, &min, &max) == false) {
      pips_debug(7,"sc_minmax_of_variable_optim: non feasible system\n");
      all_level_founds = true;
      break;
    }
 
    IsPositif = value_pos_p(min);
    IsNegatif = value_neg_p(max);
    IsNull = value_zero_p(min) && value_zero_p(max);
    NotPositif = value_zero_p(max) && value_neg_p(min);
 
    ifdebug(7) {
      pips_debug(7, "values: ");
      fprint_string_Value(stderr, "min = ", min);
      fprint_string_Value(stderr, "  max = ", max);
      fprintf(stderr,
              "  ==> %s\n",
              IsPositif ? "positive" : (IsNegatif ? "negative"
                                                  : (IsNull ? "null"
                                                            : "undefined")));
    }
 
    if(IsNegatif) {
      all_level_founds = true;
      break;
    }
 
    if(IsPositif) {
      pips_debug(7, "adding level %td\n", l);
      levels = gen_nconc(levels, CONS(INT, l, NIL));
      all_level_founds = true;
      break;
    }
 
    if(!IsNull && !NotPositif) {
      pips_debug(7, "adding level %td\n", l);
      levels = gen_nconc(levels, CONS(INT, l, NIL));
    }
 
    if(!all_level_founds && l <= cl - 1) {
      pips_debug(7, "forcing variable %s to 0 (l < cl)\n",
          entity_local_name((entity) di));
      /* This function does not test feasibility and does not
       * deallocate ps
       */
      sc_force_variable_to_zero(ps, di);
    }
  }
 
  /* If there is no dependence at a common loop level: since the system
   * is feasible, it can be a dependence at the innermost level (inside the
   * common loop nest).
   *
   * WARNING:
   *
   * If the source and target statements are identical, we do not
   * add the innermost level because the parallelization phase
   * (rice) does not appreciate.  In order to be correct, we should
   * add this level 1) because the statement may be a call to an
   * external routine, in which case we cannot be sure that all the
   * writes are performed before the reads and 2) even in the case
   * of a single assignement, the generated code must preserve the
   * order of the write and read memory operations. BC.
   */
  if(!all_level_founds && s1 != s2 && statement_possible_less_p(s1, s2)) {
    pips_debug(7, "adding innermost level %td\n", l);
    levels = gen_nconc(levels, CONS(INT, l, NIL));
  }
 
  return (levels);
}
 
/* Ptsg  dependence_cone_positive(Psysteme dept_syst)
 */
static Ptsg dependence_cone_positive(dep_sc)
  Psysteme dep_sc; {
  Psysteme volatile sc_env = SC_UNDEFINED;
  Ptsg volatile sg_env = NULL;
  Pbase b;
  int n, j;
  int volatile i;
 
  if(SC_UNDEFINED_P(dep_sc))
    return (sg_new());
 
  sc_env = sc_empty(base_dup(dep_sc->base));
  n = dep_sc->dimension;
  b = dep_sc->base;
 
  for (i = 1; i <= n; i++) {
    volatile Psysteme sub_sc = sc_dup(dep_sc);
    Pvecteur v;
    Pcontrainte pc;
    Pbase b1;
 
    for (j = 1, b1 = b; j <= i - 1; j++, b1 = b1->succ) {
      /* add the contraints  bj = 0 (1<=j<i) */
      v = vect_new(b1->var, 1);
      pc = contrainte_make(v);
      sc_add_eg(sub_sc,pc);
    }
    /* add the contraints - bi <= -1 (1<=j<i) */
    v = vect_new(b1->var, -1);
    vect_add_elem(&v, TCST, 1);
    pc = contrainte_make(v);
    sc_add_ineg(sub_sc,pc);
 
    ifdebug(7) {
      fprintf(stderr, "\nInitial sub lexico-positive dependence system:\n");
      sc_syst_debug(sub_sc);
    }
 
    /* dans le cas d'une erreur d'overflow, on fait comme si le test
     *  avait renvoye' true. bc.
     */CATCH(overflow_error) {
      pips_debug(1, "overflow error.\n");
    } TRY
    {
      if(!sc_integer_feasibility_ofl_ctrl(sub_sc, FWD_OFL_CTRL, true)) {
        sc_rm(sub_sc);
        pips_debug(7,"sub lexico-positive dependence system not feasible\n");
 
        UNCATCH(overflow_error);
        continue;
      } else
        UNCATCH(overflow_error);
 
    }
 
    if(sc_empty_p(sub_sc = sc_normalize(sub_sc))) {
      sc_rm(sub_sc); /* to mimic previous behavior of sc_normalize */
      pips_debug(7, "normalized system not feasible\n");
 
      continue;
    }
 
    /* We get a normalized sub lexico-positive dependence system */ifdebug(7) {
      fprintf(stderr, "Normalized sub lexico-positive dependence system :\n");
      sc_syst_debug(sub_sc);
    }
 
    {
      Psysteme old_sc_env = sc_env;
      sc_env = sc_enveloppe_chernikova(sc_env, sub_sc);
      sc_rm(old_sc_env);
    }
 
    sc_rm(sub_sc);
 
    ifdebug(7) {
      fprintf(stderr, "Dependence system of the enveloppe of subs "
        "lexico-positive dependence:\n");
      sc_syst_debug(sc_env);
 
      if(!SC_UNDEFINED_P(sc_env) && !sc_rn_p(sc_env)) {
        sg_env = sc_to_sg_chernikova(sc_env);
        fprintf(stderr, "Enveloppe of the subs lexico-positive "
          "dependence cones:\n");
        if(!SG_UNDEFINED_P(sg_env) && vect_size(sg_env->base) != 0) {
          print_dependence_cone(stderr, sg_env, sg_env->base);
          sg_rm(sg_env);
          sg_env = (Ptsg)NULL;
        }
      }
    }
 
  }
 
  if(!SC_UNDEFINED_P(sc_env) && sc_dimension(sc_env) != 0) {
 
    sg_env = sc_to_sg_chernikova(sc_env);
    sc_rm(sc_env);
  } else {
    sg_env = sg_new();
  }
 
  return (sg_env);
}
 
static list loop_variant_list(stat)
  statement stat; {
  list lv = NIL;
  loop l;
  list locals;
 
  pips_assert("statement stat is a loop", statement_loop_p(stat));
  FOREACH (EFFECT, ef, load_cumulated_rw_effects_list(stat)) {
    entity en = effect_entity(ef);
    if(action_write_p( effect_action( ef )) && !entity_all_locations_p(en)
        && entity_integer_scalar_p(en))
      lv = gen_nconc(lv, CONS(ENTITY, en, NIL));
  }
  l = statement_loop(stat);
  locals = loop_locals(l);
  FOREACH (ENTITY, v, locals) {
    if(gen_find_eq(v, lv) == entity_undefined)
      lv = CONS(ENTITY, v, lv);
  }
  locals = statement_declarations(loop_body(l));
  FOREACH (ENTITY, v, locals) {
    if(gen_find_eq(v, lv) == entity_undefined)
      lv = CONS(ENTITY, v, lv);
  }
  return (lv);
}
 
/* this function detects intra-statement, non loop carried dependence
 * ( Di=(0,0,...0) and s1 = s2).
 */
static bool TestDiCnst(Psysteme ps,
                       int cl,
                       statement s1,
                       effect ef1 __attribute__ ((unused)),
                       statement s2,
                       effect ef2 __attribute__ ((unused))) {
  int l;
 
  for (l = 1; l <= cl; l++) {
    Variable di = (Variable)GetDiVar(l);
    Psysteme pss;
    Value val;
    bool success_p = true;
 
    pss = sc_dup(ps);
    success_p = sc_value_of_variable(pss, di, &val);
    sc_rm(pss);
 
    if(success_p) {
      if(value_notzero_p(val)) {
        return (false);
      }
    } else {
      return (false);
    }
  }
 
  /* case of di zero */
  if(s1 == s2) {
    NbrAllEquals++;
    return (true);
  } else
    return (false);
}
 
 
 
void writeresult(char *mod_name) {
  FILE *fp;
  string filename;
  int i, j;
 
  switch(dg_type) {
    case DG_FAST:
      filename = "resulttestfast";
      break;
    case DG_FULL:
      filename = "resulttestfull";
      break;
    case DG_SEMANTICS:
      filename = "resulttestseman";
      break;
    default:
      pips_internal_error("erroneous dg type.");
      return; /* to avoid warnings from compiler */
  }
 
  filename = strdup(concatenate(db_get_current_workspace_directory(),
                                "/",
                                mod_name,
                                ".",
                                filename,
                                0));
 
  fp = safe_fopen(filename, "w");
 
  fprintf(fp, "%s", mod_name);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d",
          NbrArrayDepInit,
          NbrIndepFind,
          NbrAllEquals,
          NbrDepCnst,
          NbrTestExact,
          NbrDepInexactEq,
          NbrDepInexactFM,
          NbrDepInexactEFM,
          NbrScalDep,
          NbrIndexDep);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", deptype[i][j]);
  for (i = 0; i <= 4; i++)
    for (j = 0; j <= 2; j++)
      fprintf(fp, " %d", constdep[i][j]);
  fprintf(fp,
          " %d %d %d %d %d %d %d %d %d %d %d",
          NbrTestCnst,
          NbrTestGcd,
          NbrTestSimple,
          NbrTestDiCnst,
          NbrTestProjEqDi,
          NbrTestProjFMDi,
          NbrTestProjEq,
          NbrTestProjFM,
          NbrTestDiVar,
          NbrProjFMTotal,
          NbrFMSystNonAug);
  for (i = 0; i < 18; i++)
    fprintf(fp, " %d", FMComp[i]);
  fprintf(fp, "\n");
 
  safe_fclose(fp, filename);
  free(filename);
}
 
 
// have to be done before call :
// * set_ordering_to_statement
// * set_enclosing_loops_map
// * loading cumulated effects
graph compute_dg_on_statement_from_chains_in_place(statement s, graph chains) {
  dg = chains;
  dg_type = DG_FAST; //FIXME
 
  debug_on("QUICK_PRIVATIZER_DEBUG_LEVEL");
  quick_privatize_graph(dg);
  debug_off();
 
  memset(deptype,0,sizeof(deptype));
  memset(constdep,0,sizeof(deptype));
 
  rdg_statement(s);
 
  return dg;
}
 
 
// have to be done before call :
// * set_ordering_to_statement
// * set_enclosing_loops_map
// * loading cumulated effects
graph compute_dg_on_statement_from_chains(statement s, graph chains) {
  dg = copy_graph(chains);
  return compute_dg_on_statement_from_chains_in_place(s, dg);
}