prgm_mapping.c

Go to the documentation of this file.

/*
 
  $Id: prgm_mapping.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
 
/* Name     : prgm_mapping.c
 * Package  : prgm_mapping
 * Author   : Alexis Platonoff
 * Date     : april 1993
 * Historic :
 * Documents: SOON
 * Comments : This file contains the functions for the computation of the
 * placement function. The main function is prgm_mapping().
 */
 
/* Ansi includes        */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#include <sys/times.h>          /* performance purpose */
#include <sys/time.h>           /* performance purpose */
 
/* Newgen includes      */
#include "genC.h"
 
/* C3 includes          */
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "sc.h"
#include "polyedre.h"
#include "union.h"
#include "matrice.h"
#include "matrix.h"
 
/* Pips includes        */
#include "ri.h"
#include "constants.h"
#include "ri-util.h"
#include "misc.h"
#include "complexity_ri.h"
#include "database.h"
#include "graph.h"
#include "dg.h"
#include "paf_ri.h"
#include "parser_private.h"
#include "property.h"
#include "reduction.h"
#include "text.h"
#include "text-util.h"
#include "tiling.h"
#include "text-util.h"
#include "pipsdbm.h"
#include "resources.h"
#include "static_controlize.h"
#include "paf-util.h"
#include "pip.h"
#include "array_dfg.h"
#include "prgm_mapping.h"
 
/* Macro functions      */
#define DOT "."
#define BDT_STRING "bdt"
#define STMT_HT_SIZE 100        /* hash table max size */
#define DTF_HT_SIZE 200         /* hash table max size */
#define ENT_HT_SIZE 200         /* hash table max size */
 
/* Internal variables   */
 
/* Global variables */
plc pfunc;              /* The placement function */
graph the_dfg;          /* The data flow graph */
bdt the_bdt;            /* The timing function */
int nb_nodes,           /* The number of nodes in the DFG */
    nb_dfs;             /* The number of dataflows in the DFG */
hash_table DtfToSink;   /* Mapping from a dataflow to its sink statement */
hash_table DtfToDist;   /* Mapping from a dataflow to its distance */
hash_table DtfToWgh;    /* Mapping from a dataflow to its weight */
hash_table StmtToProto; /* Mapping from a statement (int) to its prototype */
hash_table StmtToPdim;  /* Mapping from a statement to the dim of its plc func */
hash_table StmtToBdim;  /* Mapping from a statement to the dim of its bdt */
hash_table StmtToDim;   /* Mapping from a stmt to its iteration space dim */
hash_table StmtToLamb;  /* Mapping from a stmt to its lambda coeff */
hash_table StmtToMu;    /* Mapping from a stmt to its mu coeff */
hash_table UnkToFrenq;  /* Mapping from an entity to its frenq in the plc proto */
int count_mu_coeff;
list subs_l;
list prgm_parameter_l;
 
/* Local defines */
typedef dfg_vertex_label vertex_label;
typedef dfg_arc_label arc_label;
 
#define PLC_EXT ".plc_file"
 
/* ======================================================================== */
bool print_plc(module_name)
const char* module_name;
{
  char *localfilename;
  FILE        *fd;
  char        *filename;
  plc the_plc;
 
  debug_on( "PRINT_PLC_DEBUG_LEVEL" );
 
  if (get_debug_level() > 1)
      user_log("\n\n *** PRINTING PLC for %s\n", module_name);
 
  the_plc = (plc) db_get_memory_resource(DBR_PLC, module_name, true);
 
  localfilename = strdup(concatenate(module_name, PLC_EXT, NULL));
  filename = strdup(concatenate(db_get_current_workspace_directory(), 
                                "/", localfilename, NULL));
 
  fd = safe_fopen(filename, "w");
  fprint_plc(fd, the_plc);
  safe_fclose(fd, filename);
 
  DB_PUT_FILE_RESOURCE(DBR_PLC_FILE, strdup(module_name), localfilename);
  
  free(filename);
 
  if(get_debug_level() > 0)
    fprintf(stderr, "\n\n *** PRINT_PLC DONE\n");
 
  debug_off();
 
  return(true);
}
 
 
/* ======================================================================== */
/*
 * list plc_make_proto():
 *
 * computes the prototype of placement function for each statement,
 * i.e. for each node of the DGF. Returns the list of unknowns
 * coefficients that have been created.
 *
 * For each node, this consists in building a polynome which will be
 * associated via the hash table "StmtToProto" to the corresponding
 * statement.
 *
 * The placement function is an integer linear function on the indices of
 * the englobing loops and structure parameters of the statement. We have
 * to determine the coefficients associated to each index. These unknowns
 * are represented by variables, so the prototype is a polynome of degree
 * two (2). Moreover there is an unknown constant term.
 *
 * For example, with a statement englobed by three (3) loops (I1, I2, I3)
 * and having one structure parameter (N), the prototype is :
 *
 *      COEFF1*I1 + COEFF2*I2 + COEFF3*I3 + COEFF$*N + COEFF5
 *
 * Note: The list "l_lamb" that contains all the coefficients is build
 * during by appending the sublists associated to each statement. Each
 * sublist is ordered as follow: you have first the coeff for the constant
 * term, the coeffs for the loop indices (from the outermost to the
 * innermost) and the coeffs of the structure parameters (the order of the
 * static_controlize). This order is used in the function
 * broadcast_conditions().*/
list plc_make_proto()
{
  extern graph the_dfg;          /* the DFG */
  extern hash_table StmtToProto, /* Mapping from a statement to its
                                  * prototype */
                    StmtToLamb;  /* Mapping from a statement to its
                                  * lambda coeff */
 
 
  int count_coeff;
  list l, l_lamb = NIL, stmt_lamb;
  entity lamb;
  Ppolynome pp_proto, pp_ind, pp_par, pp_coeff, pp_new;
 
  /* We create the hash table that will contain the prototype */
  StmtToProto = hash_table_make(hash_int, nb_nodes+1);
  StmtToLamb = hash_table_make(hash_int, nb_nodes+1);
 
  /* We initialize the counter of coefficients in order to have all
   * unknowns represented by different entities.
   */
  count_coeff = 0;
 
  /* For each node of the data flow graph we compute a prototype. */
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    vertex v;
    int stmt;
    static_control stct;
    list ind_l, par_l, aux_par_l;
 
    v = VERTEX(CAR(l));
    stmt = dfg_vertex_label_statement((dfg_vertex_label) vertex_vertex_label(v));
 
    /* We get the "static_control" associated to the statement. */
    stct = get_stco_from_current_map(adg_number_to_statement(stmt));
 
    /* We get the list of indices of the englobing loops and structure
     * parameters.
     */
    ind_l = static_control_to_indices(stct);
    par_l = gen_append(prgm_parameter_l, NIL);
 
    stmt_lamb = NIL;
 
    /* First, we initialize the polynome in building the constant term. */
    lamb = make_coeff(CONST_COEFF, ++count_coeff);
    stmt_lamb = gen_nconc(stmt_lamb, CONS(ENTITY, lamb, NIL));
    pp_proto = make_polynome(1.0, (Variable) lamb, (Value) 1);
 
    /* Then, for each index (ind) we build the monome ind*COEFF#, and add it
     * to the polynome.
     */
    for( ; ind_l != NIL; ind_l = CDR(ind_l)) {
      entity ind = ENTITY(CAR(ind_l));
 
      lamb = make_coeff(INDEX_COEFF, ++count_coeff);
      stmt_lamb = gen_nconc(stmt_lamb, CONS(ENTITY, lamb, NIL));
 
      pp_ind = make_polynome(1.0, (Variable) ind, (Value) 1);
      pp_coeff = make_polynome(1.0, (Variable) lamb, (Value) 1);
      pp_new = polynome_mult(pp_ind, pp_coeff);
 
      polynome_add(&pp_proto, pp_new);
    }
 
    /* Then, for each parameter (par) we build the monome par*COEFF#, and add it
     * to the polynome.
     */
    for(aux_par_l = par_l ; !ENDP(aux_par_l); POP(aux_par_l)) {
      entity par = ENTITY(CAR(aux_par_l));
 
      lamb = make_coeff(PARAM_COEFF, ++count_coeff);
      stmt_lamb = gen_nconc(stmt_lamb, CONS(ENTITY, lamb, NIL));
 
      pp_par = make_polynome(1.0, (Variable) par, (Value) 1);
      pp_coeff = make_polynome(1.0, (Variable) lamb, (Value) 1);
      pp_new = polynome_mult(pp_par, pp_coeff);
 
      polynome_add(&pp_proto, pp_new);
    }
 
    /* We put the new prototype on the hash table. */
    hash_put(StmtToLamb, (char *) stmt , (char *) stmt_lamb);
    hash_put(StmtToProto, (char *) stmt , (char *) pp_proto);
 
    l_lamb = gen_append(stmt_lamb, l_lamb);
  }
  return(l_lamb);
}
 
/* ======================================================================== */
/*
 * void initialize_mu_list(int stmt, dim)
 */
void initialize_mu_list(stmt, dim)
int stmt, dim;
{
  extern int count_mu_coeff;
  extern hash_table StmtToMu;
 
  list mu_l = NIL;
  int i;
 
  for(i = 0; i < dim; i++) {
    entity mu = make_coeff(MU_COEFF, count_mu_coeff++);
    mu_l = gen_nconc(mu_l, CONS(ENTITY, mu, NIL));
  }
  hash_put(StmtToMu, (char *) stmt , (char *) mu_l);
}
 
 
/* ======================================================================== */
/*
 * int plc_make_min_dim():
 *
 * computes the minimum number of dimensions for the placement
 * function.
 *
 * It is equal to the dimension associated to the instruction
 * which is nested into the deepest sequential nest loop, i.e., which has
 * the schedule with the biggest number of dimensions. In all cases, the
 * placement has at least one dimension.
 */
int plc_make_min_dim()
{
  extern graph the_dfg;
  extern bdt the_bdt;
  extern hash_table StmtToPdim, StmtToBdim;
 
  int dmin = 1, bdmax = 1;
  list l;
 
  StmtToPdim = hash_table_make(hash_pointer, nb_nodes+1);
  StmtToBdim = hash_table_make(hash_pointer, nb_nodes+1);
  StmtToMu = hash_table_make(hash_pointer, nb_nodes+1);
 
  /* For each node of the data flow graph we compute its dimension. */
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    vertex v;
    int stmt, dim, b_dim, p_dim;
    static_control stct;
    list ind_l;
 
    v = VERTEX(CAR(l));
    stmt = vertex_int_stmt(v);
    stct = get_stco_from_current_map(adg_number_to_statement(stmt));
    ind_l = static_control_to_indices(stct);
 
    /* We compute the dimension of the current node */
    dim = gen_length(ind_l);
 
    /* We get the dimension of the timing and placement function of the
     * current node */
    b_dim = (int) hash_get(StmtToBdim, (char *) stmt);
    p_dim = (int) hash_get(StmtToPdim, (char *) stmt);
 
    if((bdmax <= b_dim) && (dmin < p_dim))
      dmin = p_dim;
  }
  return(dmin);
}
 
 
/* ======================================================================== */
/*
 * int plc_make_dim():
 *
 * computes the maximum possible dimension of the placement function
 * associated to each instruction and returns the greatest of these
 * dimensions.
 *
 * For an given instruction, the dimension of its placement function is the
 * substraction of the englobing space dimension and the timing function
 * dimension.
 */
int plc_make_dim()
{
  extern graph the_dfg;
  extern bdt the_bdt;
  extern hash_table StmtToPdim, StmtToBdim;
 
  int dmax = 0;
  list l;
 
  StmtToPdim = hash_table_make(hash_pointer, nb_nodes+1);
  StmtToBdim = hash_table_make(hash_pointer, nb_nodes+1);
  StmtToMu = hash_table_make(hash_pointer, nb_nodes+1);
 
  /* For each node of the data flow graph we compute its dimension. */
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    vertex v = VERTEX(CAR(l));
    int stmt = vertex_int_stmt(v);
    static_control stct = get_stco_from_current_map(adg_number_to_statement(stmt));
    list ind_l = static_control_to_indices(stct);
    int dim, b_dim = 0, sdim;
 
    /* We compute the dimension of the current node */
    dim = gen_length(ind_l);
 
    /* We compute the dimension of the timing function of the current node */
    if(the_bdt != bdt_undefined) {
      list bl;
      b_dim = 0;
      for(bl = bdt_schedules(the_bdt); bl != NIL; bl = CDR(bl)) {
        schedule sc = SCHEDULE(CAR(bl));
        if(schedule_statement(sc) == stmt) {
          list dl;
          sdim = 0;
          for(dl = schedule_dims(sc); dl != NIL; dl = CDR(dl)) {
            expression e = EXPRESSION(CAR(dl));
            if(! expression_constant_p(e)) {
              list l;
              bool ind_not_null;
              Pvecteur pv;
  
              NORMALIZE_EXPRESSION(e);
              pv = (Pvecteur) normalized_linear(expression_normalized(e));
 
              ind_not_null = false;
              for(l = ind_l; (!ENDP(l)) && (!ind_not_null); POP(l)) {
                entity var = ENTITY(CAR(l));
                if(vect_coeff((Variable) var, pv) != 0)
                  ind_not_null = true;
              }
              if(ind_not_null)
                sdim++;
            }
          }
          if(sdim > b_dim)
            b_dim = sdim;
        }
      }
    }
    dim = dim - b_dim;
    if(dim > dmax)
      dmax = dim;
    hash_put(StmtToPdim, (char *) stmt, (char *) dim);
    hash_put(StmtToBdim, (char *) stmt, (char *) b_dim);
 
    initialize_mu_list(stmt, dim);
  }
  return(dmax);
}
 
 
/* ======================================================================== */
/*
 * void plc_make_distance():
 *
 * computes the distance equation associated to each dataflow of the DFG.
 *
 * The distance is : PI(sink, x) - PI(source, h(x))
 * where "sink" is the sink statement of the dataflow, "source" is the source
 * statement of the dataflow, "x" is the iteration vector of sink statement,
 * "h" is the transformation function of the dataflow and "PI" is the
 * placement function (or prototype).
 *
 * So, for one given dataflow, the computation needs both prototypes of sink
 * and source statements ("pp_sink" and "pp_source"), the transformations
 * ("trans_l") and the iteration vector of the source ("source_ind_l").
 *
 * Each distance is put in a hash table "DtfToDis".
 */
void plc_make_distance()
{
  extern graph the_dfg;
  extern hash_table StmtToProto, /* Mapping from a stmt to its prototype */
                    DtfToDist;  /* Mapping from a dataflow to its distance */
 
  list l, su_l, df_l, source_ind_l, trans_l, si_l;
  int source_stmt, sink_stmt;
  static_control source_stct;
  Ppolynome pp_source, pp_sink, pp_dist;
 
  /* We create the hash table. */
  DtfToDist = hash_table_make(hash_pointer, nb_dfs+1);
 
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    vertex v = VERTEX(CAR(l));
 
    source_stmt = vertex_int_stmt(v);
    source_stct = get_stco_from_current_map(adg_number_to_statement(source_stmt));
 
    /* Prototype of the source statement. */
    pp_source = (Ppolynome) hash_get(StmtToProto, (char *) source_stmt);
 
    /* Iteration vector of the source statement. */
    source_ind_l = static_control_to_indices(source_stct);
 
    su_l = vertex_successors(v);
 
    for( ; su_l != NIL; su_l = CDR(su_l)) {
      successor su = SUCCESSOR(CAR(su_l));
      vertex sink_v = successor_vertex(su);
 
      sink_stmt = vertex_int_stmt(sink_v);
 
      /* Prototype of the sink statement. */
      pp_sink = (Ppolynome) hash_get(StmtToProto, (char *) sink_stmt);
 
      df_l = dfg_arc_label_dataflows((dfg_arc_label) successor_arc_label(su));
 
      /* For each dataflow of the data flow graph we compute a distance. */
      for( ; df_l != NIL; df_l = CDR(df_l)) {
        Ppolynome aux_pp;
        predicate exec_domain, gov_pred;
        Psysteme impl_sc, elim_sc, sc_ed = SC_UNDEFINED,
                 sc_gp = SC_UNDEFINED, df_domain;
        list elim_vvs, impl_var, elim_var;
 
        dataflow df = DATAFLOW(CAR(df_l));
 
        /* Transformations of the dataflows. */
        trans_l = dataflow_transformation(df);
 
        /* There should be as much transformation expressions as source
         * indices in the source iteration vector.
         */
        pips_assert("plc_make_distance",
             gen_length(trans_l) == gen_length(source_ind_l));
 
        if(get_debug_level() > 3) 
        {
          fprintf(stderr, "[plc_make_distance] \t for edge %d ->", source_stmt);
          fprint_dataflow(stderr, sink_stmt, df);
          fprintf(stderr, "\n");
        }
 
        /* We now compute PI(source, h(x)). This is done by making the
         * substitution, in the source prototype, of each index of the
         * iteration vector of the source statement to the corresponding
         * transformation expression.
         *
         * For this, we duplicate our polynome (source prototype) in
         * "aux_pp". Then, for each index, we get its factor in "aux_pp",
         * multiply it with the corresponding transformation, add it to
         * "pp_dist" (initialized to POLYNOME_NUL) and eliminate the index
         * in "aux_pp" (we substitute the index by POLYNOME_NUL). Then, we
         * add "aux_pp" to "pp_dist", it contains the remnants of "pp_source"
         * that are not factor of one of the indices.
         */
        pp_dist = POLYNOME_NUL;
        aux_pp = polynome_dup(pp_source);
        si_l = source_ind_l;
 if(get_debug_level() > 4) {
    fprintf(stderr, "[plc_make_distance] \t\tSource prototype:\n");
    polynome_fprint(stderr, aux_pp, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
 }
        for( ; si_l != NIL; si_l = CDR(si_l), trans_l = CDR(trans_l)) {
          entity var = ENTITY(CAR(si_l));
          expression trans = EXPRESSION(CAR(trans_l));
 
          polynome_add(&pp_dist,
            polynome_mult(expression_to_polynome(trans),
                          vecteur_to_polynome(prototype_factorize(aux_pp,
                                                                  (Variable) var))));
/*
          polynome_add(&pp_dist,
            polynome_mult(expression_to_polynome(trans),
                          polynome_factorize(aux_pp, (Variable) var, 1)));
*/
 
          aux_pp = prototype_var_subst(aux_pp, (Variable) var, POLYNOME_NUL);
/*
          di_polynome_var_subst_null(&aux_pp, var);
          aux_pp = polynome_var_subst(aux_pp, (Variable) var, POLYNOME_NUL);
*/
 
 if(get_debug_level() > 5) {
    fprintf(stderr, "[plc_make_distance] \t\t\tTransformation for index %s : %s\n",
            entity_local_name(var), expression_to_string(trans));
    fprintf(stderr, "[plc_make_distance] \t\t\tCrt PI(source, h(x)):\n");
    polynome_fprint(stderr, pp_dist, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
 }
        }
        polynome_add(&pp_dist, aux_pp);
 
 if(get_debug_level() > 5) {
    fprintf(stderr, "[plc_make_distance] \t\t\tPI(sink, x) :\n");
    polynome_fprint(stderr, pp_sink, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
    fprintf(stderr, "[plc_make_distance] \t\t\tPI(source, h(x)) :\n");
    polynome_fprint(stderr, pp_dist, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
 }
 
        /* We now compute the distance : D = PI(sink, x) - PI(source, h(x))
         * Still, it is a polynome ("pp_dist").
         */
        polynome_negate(&pp_dist);
        polynome_add(&pp_dist, pp_sink);
 
 if(get_debug_level() > 4) {
    fprintf(stderr, "[plc_make_distance] BEFORE IMPL ELIM \t\tDistance pp:\n");
    polynome_fprint(stderr, pp_dist, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
 }
 
        /* We now eliminate variables in order to have free variables. This
         * is done using the implicit equations of the execution domain
         * intersection the governing predicate.
         */
        exec_domain = VERTEX_DOMAIN(sink_v);
        gov_pred = dataflow_governing_pred(df);
        if(exec_domain == predicate_undefined) {
          if(gov_pred == predicate_undefined)
            df_domain = sc_new();
          else
            df_domain = (Psysteme) predicate_system(gov_pred);
        }
        else {
          if(gov_pred == predicate_undefined)
            df_domain = (Psysteme) predicate_system(exec_domain);
          else {
            df_domain = sc_new();
            sc_ed = (Psysteme) predicate_system(exec_domain);
            sc_gp = (Psysteme) predicate_system(gov_pred);
            df_domain = sc_intersection(df_domain, sc_ed, sc_gp);
          }
        }
 
 if(get_debug_level() > 4) {
   fprintf(stderr, "[plc_make_distance] \t\t Exec domain: ");
   fprint_psysteme(stderr, sc_ed);
   fprintf(stderr, "[plc_make_distance] \t\t Gov pred   : ");
   fprint_psysteme(stderr, sc_gp);
   fprintf(stderr, "[plc_make_distance] \t\t Inter the 2: ");
   fprint_psysteme(stderr, df_domain);
 }
 
        impl_sc = find_implicit_equation(df_domain);
 
 if(get_debug_level() > 4) {
   fprintf(stderr, "[plc_make_distance] \t\t Impl sys   : ");
   fprint_psysteme(stderr, impl_sc);
 }
 
        if(impl_sc != NULL) {
          impl_var = base_to_list(impl_sc->base);
 
          elim_sc = elim_var_with_eg(impl_sc, &impl_var, &elim_var);
          elim_vvs = make_vvs_from_sc(elim_sc, elim_var);
 
 if(get_debug_level() > 4) {
   fprintf(stderr, "[plc_make_distance] \t\t New subs  :\n");
   fprint_vvs(stderr, elim_vvs);
 }
 
          pp_dist = vvs_on_polynome(elim_vvs, pp_dist);
 
        }
 if(get_debug_level() > 4) {
    fprintf(stderr, "[plc_make_distance] \t\tDistance pp:\n");
    polynome_fprint(stderr, pp_dist, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
 }
 
        /* We put this polynome in the hash table. */
        hash_put(DtfToDist, (char *) df , (char *) pp_dist);
 
      }
    }
  }
}
 
 
/* ======================================================================== */
/*
 * Psysteme cutting_conditions(list df_l):
 *
 * returns a system of equations to be verified in order to zero out all
 * the distances associated to each dataflow of the list "df_l".
 *
 * The distance is taken from a hash table "DtfToDis".
 *
 * In fact, for each distance (i.e. dataflow), we create two systems: one that
 * nullified the factor of the loop indices (Mi) and one that nullified the
 * structure parameters and the constant term (Mp).
 *
 * For example, with I and J as indices, N as parameter, the distance
 *      I*(C1-C2) + J*(C3+C1) + N*(C2+C3) + C4-C1)
 * will leave the following systems :
 *      Mi = {C1-C2 = 0, C3+C1 = 0} 
 *      Mp = {C2+C3 = 0, C4-C1 = 0}
 * The C# are unknown coefficients created for the prototypes.
 *
 * The return system M is the union of this system so as to place first the
 * Mi systems (in decreasing weight order) and then the Mp systems (in 
 * decreasing weight order).
 */
Psysteme cutting_conditions(df_l)
list df_l;
{
  extern hash_table DtfToDist;  /* Mapping from a dataflow to its distance */
  extern list prgm_parameter_l;
 
  list l, sink_ind_l, sink_par_l;
  int sink_stmt;
  static_control sink_stct;
  Psysteme Mi, Mp, M;
  Ppolynome pp_dist;
 
  Mi = sc_new();
  Mp = sc_new();
  for(l = df_l; !ENDP(l); POP(l)) {
    dataflow df = DATAFLOW(CAR(l));
    Psysteme Mi_local, Mp_local;
 
    sink_stmt = (int) hash_get(DtfToSink, (char *) df);
    sink_stct = get_stco_from_current_map(adg_number_to_statement(sink_stmt));
 
    /* Iteration vector of the sink statement. */
    sink_ind_l = static_control_to_indices(sink_stct);
 
    /* Structure parameters. */
    /* sink_par_l = gen_append(static_control_params(sink_stct),
     * CONS(ENTITY, (entity) TCST, NIL)); */
    sink_par_l = gen_append(prgm_parameter_l,
                            CONS(ENTITY, (entity) TCST, NIL));
 
    pp_dist = polynome_dup((Ppolynome) hash_get(DtfToDist, (char *) df));
 
    /* We transforme this polynome ("pp_dist") into two systems of
     * equations, Mi and Mp (cf. above).
     */
    Mi_local = nullify_factors(&pp_dist, sink_ind_l, false);
    Mp_local = nullify_factors(&pp_dist, sink_par_l, true);
 
    polynome_rm(&pp_dist);
 
    if(get_debug_level() > 3) {
      fprintf(stderr, "[plc_make_distance] \tDistance Mi:\n");
      fprint_psysteme(stderr, Mi_local);
      fprintf(stderr, "[plc_make_distance] \tDistance Mp:\n");
      fprint_psysteme(stderr, Mp_local);
    }
    Mi = append_eg(Mi, Mi_local);
    Mp = append_eg(Mp, Mp_local);
  }
  M = append_eg(Mi, Mp);
  sc_normalize(M);
  return(M);
}
 
 
/* ======================================================================== */
/*
 * list sort_dfg_node(list l_nodes):
 *
 * returns the sorted list of the nodes of the list "l_nodes". The sorting
 * is based on the dimension of the nodes, in decreasing order.
 *
 * We need to compute for each node its dimension. This dimension is the
 * dimension of the iteration space of its associated statement, i.e. the
 * length of the list of the loop indices.
 */
list sort_dfg_node(l_nodes)
list l_nodes;
{
  extern hash_table StmtToDim;
  extern int nb_nodes;
 
  list l, new_l;
 
  StmtToDim = hash_table_make(hash_int, nb_nodes+1);
 
  /* For each node of the data flow graph we compute its dimension. */
  for(l = l_nodes; l != NIL; l = CDR(l)) {
    int stmt = vertex_int_stmt(VERTEX(CAR(l)));
    static_control stct = get_stco_from_current_map(adg_number_to_statement(stmt));
    list ind_l = static_control_to_indices(stct);
 
    hash_put(StmtToDim, (char *) stmt, (char *) gen_length(ind_l));
  }
  new_l = general_merge_sort(l_nodes, compare_nodes_dim);
 
  hash_table_free(StmtToDim);
 
  return(new_l);
}
 
 
/* ======================================================================== */
/*
 * void edge_weight():
 *
 * computes the weight of each  dataflows of DFG. If a
 * dataflow is a broadcast or a reduction, its weight is the dimension of
 * the space on which the data movement is done. Else it is the dimension
 * of its emitter set Ee = {y/ y = he(x), x in Pe}.
 * 
 * he: transformations
 * Pe: execution domain of the sink and governing predicate of the edge
 * y: indices of the sources
 * x: indices of the sink
 *
 * For the computation of the dimension of this emitter set, we eliminate x
 * by a combination of Gauss-Jordan and Fourier-Motzkin
 * algorithms. Ee is then defined by a set of inequalities for which we can
 * compute the set of implicit equations Eei. The dimension of Ee is then
 * equal to:
 *      Dim(y) - Card(Eei)
 */
void edge_weight()
{
  extern graph the_dfg;
  extern hash_table DtfToSink,
                    DtfToWgh;
 
  list l, su_l, df_l;
  Psysteme sc_trans, sc_elim;
  predicate sink_domain;
  int source_stmt, sink_stmt, n_impl, poids;
  static_control sink_stct;
 
  /* We initialize the weight and sink statement hash tables */
  DtfToWgh = hash_table_make(hash_pointer, nb_dfs+1);
  DtfToSink = hash_table_make(hash_pointer, nb_dfs+1);
 
  /* For each dataflow of the data flow graph we compute its weight. */
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    vertex v = VERTEX(CAR(l));
    source_stmt = vertex_int_stmt(v);
 
    su_l = vertex_successors(v);
 
    for( ; su_l != NIL; su_l = CDR(su_l)) {
      successor su = SUCCESSOR(CAR(su_l));
 
      sink_stmt = vertex_int_stmt(successor_vertex(su));
      sink_stct = get_stco_from_current_map(adg_number_to_statement(sink_stmt));
      sink_domain = VERTEX_DOMAIN(successor_vertex(su));
 
      df_l = SUCC_DATAFLOWS(su);
 
      for(; df_l != NIL; df_l = CDR(df_l)) {
        dataflow df = DATAFLOW(CAR(df_l));
 
        if(is_broadcast_p(df) || is_reduction_p(df)) {
          poids = communication_dim(df);
        }
        else {
          predicate gov_pred;
          list trans_l, si_l, aux_l;
 
          gov_pred = dataflow_governing_pred(df);
          trans_l = put_source_ind(dataflow_transformation(df));
 
          /* Transformation system of equations */
          sc_trans = make_expression_equalities(trans_l);
 
          /* We append the execution domain of the sink. */
          if(sink_domain != predicate_undefined)
            sc_trans = sc_append(sc_trans, (Psysteme) predicate_system(sink_domain));
 
          /* We append the governing predicate. "sc_trans" is what we called Ee
           * (the emitter set, cf. above).
           */
          if(gov_pred != predicate_undefined)
            sc_trans = sc_append(sc_trans, (Psysteme) predicate_system(gov_pred));
 
 if(get_debug_level() > 3) 
{
    fprintf(stderr, "[edge_weight] \tfor edge: %d ->", source_stmt);
    fprint_dataflow(stderr, sink_stmt, df);
    fprintf(stderr, "\n");
    fprintf(stderr, "[edge_weight] \ttrans system is:");
    fprint_psysteme(stderr, sc_trans);
 }
 
          /* Gauss-Jordan eliminations (with equalities). */
          si_l = static_control_to_indices(sink_stct);
 
          aux_l = NIL;
 
          sc_elim = elim_var_with_eg(sc_trans, &si_l, &aux_l);
 
 if(get_debug_level() > 5) {
    fprintf(stderr, "[edge_weight] \t\t\tElim equations are: ");
    fprint_psysteme(stderr, sc_elim);
    fprintf(stderr, "[edge_weight] \t\t\tAfter elim equations: ");
    fprint_psysteme(stderr, sc_trans);
 }
          /* Fourier-Motzkin eliminations (with inequalities). */
          for( ; si_l != NIL; si_l = CDR(si_l)) {
            entity var = ENTITY(CAR(si_l));
            sc_trans = sc_integer_projection_along_variable(sc_dup(sc_trans),
                                                            sc_trans,
                                                            (Variable) var);
 
            debug(7, "edge_weight", "\t\t\t\tElim ineq with %s\n",
                  entity_local_name(var));
          }
 
          /* We compute the number of implicit equations. */
          n_impl = count_implicit_equation(sc_trans);
 
 if(get_debug_level() > 4) {
    fprintf(stderr, "[edge_weight] \t\tNumber of implicit equa is %d of: ", n_impl);
    fprint_psysteme(stderr, sc_trans);
 }
          /* We compute the weight of the current dataflow. */
          poids = gen_length(trans_l) - n_impl;
 
        }
 
        debug(4, "edge_weight", "\tWeight of the edge: %d\n", poids);
 
        /* We update the hash tables keyed by the dataflow with its weight
         * and its sink statement.
         */
        hash_put(DtfToWgh, (char *) df , (char *) poids);
        hash_put(DtfToSink, (char *) df , (char *) sink_stmt);
      }
    }
  }
}
 
 
/* ======================================================================== */
/*
 * bool in_list_p(chunk *c, list l)
 *
 * returns true if "c" appears in "l".
 */
bool in_list_p(c, l)
chunk *c;
list l;
{
  list ll = l;
  bool not_found = true;
 
  for( ; !ENDP(ll) && (not_found); POP(ll) ) {
    if(c == CHUNK(CAR(ll)))
      not_found = false;
  }
  return(!not_found);
}
 
/* ======================================================================== */
/*
 * void add_to_list(chunk *c, list *l)
 *
 * Adds "c" in "l" if it does not appears in it yet.
 *
 * Note: "l" is a pointer to a list, the usage is add_to_list(c, &l);
 */
void add_to_list(c, l)
chunk *c;
list *l;
{
  list ll = *l;
  if(!in_list_p(c, ll))
    *l = CONS(CHUNK, c, ll);
}
 
/* ======================================================================== */
/*
 * int prototype_dimension(Ppolynome pp, list ind_l):
 *
 * returns the number of linearly independent vectors we can construct with
 * "pp" and "ind_l".
 *
 * Indeed, "pp" is a prototype, i.e. a 2-dimensional polynome without squared
 * variables. For instance (x.y + y.z) could be a prototype, but (x^2 + y.z)
 * could not.
 *
 * We distinguish three kinds of variables in this polynome: the indices (from
 * "ind_l"), the parameters and the coefficients. A monome of this polynome
 * can be of six kinds:
 *      _ a constant (integer value)
 *      _ a coefficient multiplied by a constant
 *      _ a parameter multiplied by a constant
 *      _ an index multiplied by a constant
 *      _ a parameter multiplied by a coefficient and a constant
 *      _ an index multiplied by a coefficient and a constant
 *
 * So "pp" may be represented as: pp = I.A.L + P.B.L + C.L + I.D + P.E + c,
 * where I and P are respectively row vectors of indices and of parameters,
 * A and B are 2-D integer matrices, L is a column vector of coefficients,
 * C, D and E are integer column vectors and c is an integer scalar.
 *
 * The goal of this function is to count how many independent vectors we can
 * have when giving values to the coefficients. These vectors represented as
 * linear combinations of the indices from "ind_l". So, only the monomes that
 * contain an index are useful for this computation: ppi = I.A.L + I.D
 *
 * So the number of independent vectors is also the number of independent
 * values of A.L, so it is rank(A).
 *
 * Note: this function take advantage of the special form of the prototype
 * polynome.
 */
int prototype_dimension(pp, ind_l)
Ppolynome pp;
list ind_l;
{
  int dim, n, m;
  Value det_q, det_p;
  matrice mat_A, mat_Z, mat_P, mat_Q, mat_H;
  list li;
  Pbase base_L;
  Psysteme ps_AL = sc_new();
 
if(get_debug_level() > 7) {
fprintf(stderr, "[prototype_dimension] Prototype : ");
polynome_fprint(stderr, pp, pu_variable_name, pu_is_inferior_var);
fprintf(stderr, "\n");
fprintf(stderr, "[prototype_dimension] Indices : ");
fprint_entity_list(stderr, ind_l);
fprintf(stderr, "\n");
}
 
 
  /* We construct A.L, in which each line correspond to the factor of one
   * index in "pp".
   */
  for(li = ind_l; !ENDP(li); POP(li)) {
    Pvecteur one_line = prototype_factorize(pp, (Variable) ENTITY(CAR(li)));
    sc_add_egalite(ps_AL, contrainte_make(one_line));
  }
  sc_creer_base(ps_AL);
 
  /* L is the list of variables contained in AL. */
  base_L = ps_AL->base;
 
if(get_debug_level() > 7) {
fprintf(stderr, "[prototype_dimension] ps_AL : ");
fprint_psysteme(stderr, ps_AL);
fprintf(stderr, "[prototype_dimension] base_L : ");
pu_vect_fprint(stderr, base_L);
fprintf(stderr, "\n");
}
 
  n = ps_AL->nb_eq;
  m = base_dimension(base_L);
 
  if( (n == 0) || (m == 0) )
    dim = 0;
  else {
    mat_A = matrice_new(n, m);
    mat_Z = matrice_new(n, 1);
    pu_contraintes_to_matrices(ps_AL->egalites, base_L, mat_A, mat_Z, n, m);
    mat_P = matrice_new(n, n);
    mat_Q = matrice_new(m, m);
    mat_H = matrice_new(n, m);
    matrice_hermite(mat_A, n, m, mat_P, mat_H, mat_Q, &det_p, &det_q);
    dim = dim_H(mat_H, n, m);
 
if(get_debug_level() > 7) {
fprintf(stderr, "[prototype_dimension] A of rank = %d : ", dim);
matrice_fprint(stderr, mat_A, n, m);
fprintf(stderr, "\n");
}
 
    matrice_free(mat_A);
    matrice_free(mat_Z);
    matrice_free(mat_P);
    matrice_free(mat_Q);
    matrice_free(mat_H);
  }
 
/* OLD VERSION */
/*
  for(ppp = pp; ppp != NULL; ppp = ppp->succ) {
    entity first = entity_undefined, second = entity_undefined;
    pv = (ppp->monome)->term;
 
    for(; (pv != NULL) && (second == entity_undefined); pv = pv->succ) {
      second = first;
      first = (entity) pv->var;
    }
    if(pv != NULL)
      pips_internal_error("Not a prototype polynome");
 
    if( (first != entity_undefined) && (second != entity_undefined) ) {
      if(in_list_p(first, ind_l)) {
        add_to_list(second, &ivf_l);
      }
      else if(in_list_p(second, ind_l)) {
        add_to_list(first, &ivf_l);
      }
    }
  }
 
  dim = gen_length(ivf_l);
 
  gen_free_list(ivf_l);
*/
 
  return(dim);
}
 
 
/* ======================================================================== */
/*
 * bool is_not_trivial_p(list vvs):
 *
 * returns true if all the prototypes are not trivial after applying "vvs".
 * Otherwise, returns FALSE.
 *
 * A prototype is not trivial if it depends on enough parameters that one may
 * construct the required number of linearly independent solutions.
 */
bool is_not_trivial_p(vvs)
list vvs;
{
  extern hash_table StmtToProto, /* Mapping from a statement to its prototype */
                    StmtToBdim;
 
  hash_table stp;
 
 list l, ind_l;
 int stmt, dim_plc, dim_bdt;
 Ppolynome pp;
 bool proto_not_triv = true;
 
  if(get_debug_level() > 5) {
    fprintf(stderr, "[is_not_trivial_p] \t\t\tSub is:\n");
    fprint_vvs(stderr, vvs);
    fprintf(stderr, "\n");
  }
 
  stp = hash_table_make(hash_int, nb_nodes+1);
 
  /* For each stmt in the dataflow graph we test if its proto is trivial */
  for(l = graph_vertices(the_dfg); (l != NIL) && proto_not_triv; l = CDR(l)) {
    vertex v = VERTEX(CAR(l));
 
    stmt = vertex_int_stmt(v);
    ind_l = static_control_to_indices(get_stco_from_current_map(adg_number_to_statement(stmt)));
    pp = polynome_dup((Ppolynome) hash_get(StmtToProto, (char *) stmt));
 
    dim_bdt = (int) hash_get(StmtToBdim, (char *) stmt);
 
    dim_plc = gen_length(ind_l) - dim_bdt;
 
  if(get_debug_level() > 6) {
    fprintf(stderr, "[is_not_trivial_p] \t\t\t\tProto is:");
    polynome_fprint(stderr, pp, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
  }
 
    pp = vvs_on_polynome(vvs, pp);
 
  if(get_debug_level() > 5) {
    fprintf(stderr, "[is_not_trivial_p] must be of dim %d, After apply sub:", dim_plc);
    polynome_fprint(stderr, pp, pu_variable_name, pu_is_inferior_var);
    fprintf(stderr, "\n");
  }
 
    /* we carry on if the prototype is not trivial */
    if(prototype_dimension(pp, ind_l) < dim_plc)
      proto_not_triv = false;
    else
      hash_put(stp, (char *) stmt, (char *) pp);
  }
 
  if(get_debug_level() > 6) {
    fprintf(stderr, "[is_not_trivial_p] \t\t\t\tTriviality:");
    if(proto_not_triv)
       fprintf(stderr, "NON\n");
    else
       fprintf(stderr, "OUI\n");
  }
 
  if(proto_not_triv) {
    hash_table_free(StmtToProto);
    StmtToProto = stp;
 
    if(get_debug_level() > 3) {
      fprintf(stderr, "[is_not_trivial_p] New protos:\n");
      plc_fprint_proto(stderr, the_dfg, StmtToProto);
    }
  }
  else
    hash_table_free(stp);
 
 return(proto_not_triv);
}
 
 
/* ======================================================================== */
/*
 * list valuer(int dim, list xunks, list pcunks)
 *
 * valuation for the dimension "dim" of the placement function.
 *
 * "xunks" is the list of the INDEX coefficients not yet valuated: valuation
 * to 1 or 0.
 * "punks" is the list of the PARAM coefficients not yet valuated: valuation
 * using farkas lemma and PIP. These "punks" can be negative, so for this
 * resolution, we do the following: "punks = (p1, p2, p3) => p1 = a1 - a0,
 * p2 = a2 - a0, p3 = a3 - a0, with (a0, a1, a2, a3) positive. These a# are
 * called AUXIL coefficients, and "a0" is what we call "offset". Our list of
 * AUXIL coefficients is called "vl".
 */
list valuer(dim, xunks, pcunks)
int dim;
list xunks, pcunks;
{
  extern graph the_dfg;
 
  list l, ll, vl, var_l, sol, farkas_mult;
  int count_xc = 0, count_auxil_coeff = 0, stmt, count_farkas_mult;
  entity offset, nc;
  list new_vvs = NIL, vl_vvs;
  Psysteme pip_ps;
  Pcontrainte pc;
  Pvecteur pv_off;
  static_control stct;
  quast q_sol;
  quast_leaf ql;
  quast_value quv;
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nPLC at dim %2d :\n===============\n", dim);
}
 
  offset = find_or_create_coeff(AUXIL_COEFF, count_auxil_coeff);
  pv_off = vect_new((Variable) offset, 1);
  vl = CONS(ENTITY, offset, NIL);
 
  for(l = xunks; l != NIL; l = CDR(l)) {
    list xus = CONSP(CAR(l));
    for(ll = xus; !ENDP(ll); POP(ll)) {
      entity e = ENTITY(CAR(ll));
      if(count_xc == dim)
        new_vvs = compose_vvs(new_vvs, make_vvs(e, 1, vect_new(TCST, 1)));
      else
        new_vvs = compose_vvs(new_vvs, make_vvs(e, 1, vect_new(TCST, 0)));
    }
    count_xc++;
  }
 
  for(l = pcunks; l != NIL; l = CDR(l)) {
    entity e = ENTITY(CAR(l));
    count_auxil_coeff++;
    nc = find_or_create_coeff(AUXIL_COEFF, count_auxil_coeff);
    vl = CONS(ENTITY, nc, vl);
    new_vvs = compose_vvs(new_vvs,
                          make_vvs(e, 1,
                                   vect_cl2_ofl_ctrl(1,
                                                     vect_new((Variable) nc,1),
                                                     -1,pv_off,
                                                     NO_OFL_CTRL)));
  }
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nNew subs:\n");
fprint_vvs(stderr, new_vvs);
fprintf(stderr, "\n");
}
 
  pip_ps = sc_new();
  farkas_mult = NIL;
  count_farkas_mult = 0;
  vl_vvs = NIL;
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    list vvs, elim_vvs, aux_vvs;
    Psysteme elim_ps, farkas_ps, sc_ed;
    Ppolynome farkas_pp, sub_pp, proto_pp;
    list init_l = NIL, elim_l = NIL, new_vl;
    vertex v = VERTEX(CAR(l));
 
    stmt = vertex_int_stmt(v);
    proto_pp = (Ppolynome) hash_get(StmtToProto, (char *) stmt);
    stct = get_stco_from_current_map(adg_number_to_statement(stmt));
 
    sub_pp = vvs_on_polynome(compose_vvs(vl_vvs, new_vvs),
                             polynome_dup(proto_pp));
    sc_ed = (Psysteme) predicate_system(VERTEX_DOMAIN(v));
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nFarkas with %d : ", stmt);
polynome_fprint(stderr, sub_pp, pu_variable_name, pu_is_inferior_var);
fprint_psysteme(stderr, sc_ed);
fprint_entity_list(stderr, init_l);
fprintf(stderr, "\n");
}
 
    farkas_pp = apply_farkas(sub_pp, sc_ed, &init_l, &count_farkas_mult);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nFarkas DONE:\n");
polynome_fprint(stderr, farkas_pp, pu_variable_name, pu_is_inferior_var);
fprintf(stderr, "\nCoeff of Farkas: ");
fprint_entity_list(stderr, init_l);
fprintf(stderr, "\n");
}
 
    var_l = gen_concatenate(static_control_to_indices(stct),
                            prgm_parameter_l);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\n List of Var to elim: ");
fprint_entity_list(stderr, var_l);
fprintf(stderr, "\n");
}
 
    farkas_ps = nullify_factors(&farkas_pp, var_l, true);
 
/*    (void) polynome_free(sub_pp);*/
    (void) polynome_free(farkas_pp);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nEquations :\n");
fprint_psysteme(stderr, farkas_ps);
fprintf(stderr, "\n");
}
 
    elim_ps = elim_var_with_eg(farkas_ps, &init_l, &elim_l);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nAfter ELIM LAMBDAS\n");
fprintf(stderr, "\nElim Coeff and System: ");
fprint_entity_list(stderr, elim_l);
fprint_psysteme(stderr, elim_ps);
fprintf(stderr, "Remaining Coeff and System :\n");
fprint_entity_list(stderr, init_l);
fprint_psysteme(stderr, farkas_ps);
fprintf(stderr, "\n");
}
 
    if(init_l != NIL)
      farkas_mult = gen_nconc(farkas_mult, init_l);
 
    aux_vvs = NIL;
    new_vl = gen_concatenate(vl, NIL);
    if(farkas_ps->nb_eq != 0) {
      list vl_elim = NIL;
      Psysteme vl_ps;
 
      vl_ps = elim_var_with_eg(farkas_ps, &new_vl, &vl_elim);
 
      aux_vvs = make_vvs_from_sc(vl_ps, vl_elim);
 
      vl_vvs = compose_vvs(vl_vvs, aux_vvs);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nAfter ELIM AUXIL\n");
fprintf(stderr, "\nElim Coeff and System: ");
fprint_entity_list(stderr, vl_elim);
fprint_psysteme(stderr, vl_ps);
fprintf(stderr, "Remaining Coeff and System :\n");
fprint_entity_list(stderr, new_vl);
fprint_psysteme(stderr, farkas_ps);
fprintf(stderr, "\n");
}
    }
 
    elim_vvs = make_vvs_from_sc(elim_ps, elim_l);
 
    for(vvs = elim_vvs ; vvs != NIL; vvs = CDR(vvs)) {
      var_val vv = VAR_VAL(CAR(vvs));
      Pvecteur pv = (Pvecteur) normalized_linear(expression_normalized(var_val_value(vv)));
      sc_add_inegalite(pip_ps, contrainte_make(vect_multiply(pv, -1)));
    }
    for(pc = farkas_ps->egalites; pc != NULL; pc = pc->succ) {
      sc_add_egalite(pip_ps, contrainte_dup(pc));
    }
    pip_ps = vvs_on_systeme(aux_vvs, pip_ps);
    sc_normalize(pip_ps);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nNEW PIP systeme :\n");
fprint_psysteme(stderr, pip_ps);
fprintf(stderr, "\nVL subs:\n");
fprint_vvs(stderr, vl_vvs);
fprintf(stderr, "\n");
}
  }
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nNEW subs (before):\n");
fprint_vvs(stderr, new_vvs);
fprintf(stderr, "\n");
}
 
  new_vvs = vvs_on_vvs(vl_vvs, new_vvs);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nNEW subs:\n");
fprint_vvs(stderr, new_vvs);
fprintf(stderr, "\n");
}
  vect_rm(pip_ps->base);
  pip_ps->base = NULL;
  sc_creer_base(pip_ps);
 
  /* We sort the unknowns in order to have the auxiliary variables first */
  var_l = general_merge_sort(base_to_list(pip_ps->base), compare_coeff);
  pip_ps->base = list_to_base(var_l);
 
  q_sol = pip_integer_min(pip_ps, SC_EMPTY, pip_ps->base);
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nSol to PIP sys :\n\tList of unks:");
fprint_entity_list(stderr, var_l);
fprintf(stderr, "\n");
imprime_quast(stderr, q_sol);
fprintf(stderr, "\n");
}
 
  if( (q_sol == quast_undefined) || (q_sol == NULL) )
    user_error("valuer", "Pip sol undefined\n");
  quv = quast_quast_value(q_sol);
  if( quv == quast_value_undefined )
    user_error("valuer", "Pip sol undefined\n");
  switch( quast_value_tag(quv)) {
    case is_quast_value_conditional:
      user_error("valuer", "Pip sol conditional\n");
    break;
 
    case is_quast_value_quast_leaf:
      ql = quast_value_quast_leaf( quv );
      sol = quast_leaf_solution(ql);
      for( ; sol != NIL; POP(sol), POP(var_l)) {
        expression exp = EXPRESSION(CAR(sol));
        entity var = ENTITY(CAR(var_l));
        Pvecteur pv;
 
        if(expression_constant_p(exp))
          pv = vect_new(TCST, expression_to_int(exp));
        else {
          NORMALIZE_EXPRESSION(exp);
          pv = (Pvecteur) expression_normalized(exp);
        }
        new_vvs = vvs_on_vvs(make_vvs(var, 1, pv), new_vvs);
      }
    break;
  }
 
if(get_debug_level() > 3) {
fprintf(stderr, "\nNEW subs (FINAL):\n");
fprint_vvs(stderr, new_vvs);
fprintf(stderr, "\n");
}
 
  return(new_vvs);
}
 
 
 
/* ======================================================================== */
/* void sort_unknowns(list *lambda, int dmax) :
 *
 * 
 */
void sort_unknowns(lambda, dmax)
list *lambda;
int dmax;
{
  extern hash_table StmtToProto;
  extern hash_table UnkToFrenq;
 
  list vl, xl = NIL, cl, newl = *lambda, pl = NIL;
  int nb_xl = 0, *frenq_tab, r;
 
  for(cl = newl; !ENDP(cl); POP(cl)) {
    entity u = ENTITY(CAR(cl));
    if(is_index_coeff_p(u)) {
      nb_xl++;
      xl = gen_nconc(xl, CONS(ENTITY, u, NIL));
    }
    else
      pl = CONS(ENTITY, u, pl);
  }
  newl = pl;
  if(nb_xl <= dmax) {
    for(; !ENDP(xl); POP(xl)) {
      entity e = ENTITY(CAR(xl));
      newl = CONS(ENTITY, e, newl);
    }
  }
  else {
    UnkToFrenq = hash_table_make(hash_pointer, ENT_HT_SIZE);
    frenq_tab = (int *) malloc(sizeof(int) * nb_xl);
    for(r = 0; r < nb_xl; r++) {frenq_tab[r] = 0;}
 
    for(vl = graph_vertices(the_dfg); vl != NIL; vl = CDR(vl)) {
      int stmt = vertex_int_stmt(VERTEX(CAR(vl)));
      Ppolynome pp = (Ppolynome) hash_get(StmtToProto, (char *) stmt);
 
      for(cl = xl, r = 0; cl != NIL; cl = CDR(cl), r++) {
        Pvecteur pv_fac = prototype_factorize(pp, (Variable) ENTITY(CAR(cl)));
        frenq_tab[r] += vect_size(pv_fac);
      }
    }
    for(cl = xl, r = 0 ; cl != NIL; cl = CDR(cl), r++) {
      entity ce = ENTITY(CAR(cl));
      hash_put(UnkToFrenq, (char *) ce, (char *) frenq_tab[r]);
 
      debug(5, "sort_unknowns", "Frenq of %s is %d\n",
            entity_local_name(ce), frenq_tab[r]);
    }
    newl = gen_nconc(general_merge_sort(xl, compare_unks_frenq), newl);
 
    free(frenq_tab);
    hash_table_free(UnkToFrenq);
  }
  *lambda = newl;
}
 
 
/* ======================================================================== */
list partition_unknowns(unks, dmax)
list *unks;
int dmax;
{
  extern hash_table StmtToProto;
 
  list l, xl = NIL, cl, xunks, pcunks, aux_xl, xul;
  int nb_xl = 0;
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] BEGIN with dmax = %d, and unks: ", dmax);
fprint_entity_list(stderr, *unks);
fprintf(stderr, "\n");
}
 
  pcunks = NIL;
  for(cl = *unks; !ENDP(cl); POP(cl)) {
    entity u = ENTITY(CAR(cl));
    if(is_index_coeff_p(u)) {
      nb_xl++;
      xl = gen_nconc(xl, CONS(ENTITY, u, NIL));
    }
    else
      pcunks = CONS(ENTITY, u, pcunks);
  }
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] pcunks: ");
fprint_entity_list(stderr, pcunks);
fprintf(stderr, "\n");
fprintf(stderr, "[partition_unknowns] %d in xl: ", nb_xl);
fprint_entity_list(stderr, xl);
fprintf(stderr, "\n");
}
 
  *unks = pcunks;
  xunks = NIL;
  if(nb_xl <= dmax) {
    for(; !ENDP(xl); POP(xl)) {
      entity e = ENTITY(CAR(xl));
      xunks = gen_nconc(xunks, CONS(CONSP, CONS(ENTITY, e, NIL), NIL));
    }
  }
  else {
    list rem_xl = gen_append(xl, NIL);
    for(l = graph_vertices(the_dfg); !ENDP(l) && !ENDP(rem_xl); POP(l)) {
      int stmt = vertex_int_stmt(VERTEX(CAR(l)));
      Ppolynome proto_pp = (Ppolynome) hash_get(StmtToProto, (char *) stmt);
      list lax, plax = NIL;
 
      aux_xl = gen_append(xl, NIL);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] stmt %d, proto: ", stmt);
polynome_fprint(stderr, proto_pp, pu_variable_name, pu_is_inferior_var);
fprintf(stderr, "\n");
}
 
      for(cl = xl; cl != NIL; cl = CDR(cl)) {
        entity e = ENTITY(CAR(cl));
        Pvecteur pv_fac = prototype_factorize(proto_pp, (Variable) e);
        if(VECTEUR_NUL_P(pv_fac)) {
          gen_remove(&aux_xl, (chunk *) e);
        }
      }
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] xl of crt proto:");
fprint_entity_list(stderr, aux_xl);
fprintf(stderr, "\n");
}
 
      for(lax = xunks; !ENDP(lax) && !ENDP(rem_xl) && !ENDP(aux_xl); POP(lax)) {
        list crt_ax = CONSP(CAR(lax));
        bool not_found = true;
        entity e = entity_undefined;
 
        for(cl = aux_xl; !ENDP(cl) && not_found; cl = CDR(cl)) {
          e = ENTITY(CAR(cl));
          if(in_list_p((chunk *) e, crt_ax))
            not_found = false;
        }
        if(not_found) {
          for(cl = aux_xl; !ENDP(cl) && not_found; cl = CDR(cl)) {
            e = ENTITY(CAR(cl));
            if(in_list_p((chunk *) e, rem_xl))
              not_found = false;
          }
          if(!not_found) {
            CONSP(CAR(lax)) = gen_nconc(crt_ax, CONS(ENTITY, e, NIL));
            gen_remove(&rem_xl, (chunk *) e);
            gen_remove(&aux_xl, (chunk *) e);
          }
        }
        else
          gen_remove(&aux_xl, (chunk *) e);
        plax = lax;
      }
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] xl of crt proto (again):");
fprint_entity_list(stderr, aux_xl);
fprintf(stderr, "\n");
fprintf(stderr, "[partition_unknowns] Remaining xl:");
fprint_entity_list(stderr, rem_xl);
fprintf(stderr, "\n");
 
fprintf(stderr, "[partition_unknowns] Crt unks (addition): ");
for(xul = xunks; !ENDP(xul); POP(xul)) {
  fprintf(stderr, "(");
  fprint_entity_list(stderr, CONSP(CAR(xul)));
  fprintf(stderr, ") ");
}
fprintf(stderr, "\n");
}
 
      if(!ENDP(rem_xl)) {
        for(cl = aux_xl; !ENDP(cl); cl = CDR(cl)) {
          entity e = ENTITY(CAR(cl));
          if(in_list_p((chunk *) e, rem_xl)) {
            if(ENDP(plax)) {
              xunks = CONS(CONSP, CONS(ENTITY, e, NIL), NIL);
              plax = xunks;
            }
            else {
              CDR(plax) = CONS(CONSP, CONS(ENTITY, e, NIL), NIL);
              plax = CDR(plax);
            }
            gen_remove(&rem_xl, (chunk *) e);
          }
        }
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partition_unknowns] Remaining xl (again):");
fprint_entity_list(stderr, rem_xl);
fprintf(stderr, "\n");
 
fprintf(stderr, "[partition_unknowns] Crt unks (appendition): ");
for(xul = xunks; !ENDP(xul); POP(xul)) {
  fprintf(stderr, "(");
  fprint_entity_list(stderr, CONSP(CAR(xul)));
  fprintf(stderr, ") ");
}
fprintf(stderr, "\n");
}
 
      }
    }
  }
  return(xunks);
}
 
 
/* ======================================================================== */
/*
 * Psysteme system_inversion_restrict(Psysteme sys, list unks_l var_l par_l,
 *                                    int nb_restrict, bool is_first):
 *
 * sys -> B.e, unks_l -> l, ps_res -> l.B^(-1), var_l -> e :
 *
 * a = B.e
 * m.a = l.e
 * =>
 * m = l.B^(-1)
 */
Psysteme system_inversion_restrict(sys, unks_l, var_l, par_l, nb_restrict, is_first)
Psysteme sys;
list unks_l, var_l, par_l;
int nb_restrict;
bool is_first;
{
  Psysteme full_ps;
  Pcontrainte new_pc;
  int n, m1, m2, r, d, i, j;
  matrice A, B, inv_A, Bz, R, Rt;
 
  full_ps = completer_base(sys, var_l, par_l);
  n = full_ps->nb_eq;
  m1 = gen_length(var_l);
  m2 = gen_length(par_l) + 1;
 
  A = matrice_new(n,n);
  B = matrice_new(n,m2);
  contraintes_with_sym_cst_to_matrices(full_ps->egalites,list_to_base(var_l),
                                       list_to_base(par_l),A,B,n,n,m2);
 
  inv_A = matrice_new(n,n);
  matrice_general_inversion(A, inv_A, n);
 
  if(is_first) {
    r = nb_restrict;
    d = 0;
  }
  else {
    r = n - nb_restrict;
    d = nb_restrict;
  }
 
  R = matrice_new(n, r);
  for(i = 1; i <= n; i++)
    for(j = 1; j <= r; j++)
      ACCESS(R, n, i, j) = ACCESS(inv_A, n, i, j+d);
  R[0] = 1;
 
  Rt = matrice_new(r, n);
  matrice_transpose(R, Rt, n, r);
 
  Bz = matrice_new(r, 1);
  matrice_nulle(Bz, r, 1);
 
  pu_matrices_to_contraintes(&new_pc, list_to_base(unks_l), Rt, Bz, r, n);
 
  matrice_free(A);
  matrice_free(B);
  matrice_free(inv_A);
  matrice_free(Bz);
  matrice_free(R);
  matrice_free(Rt);
 
  return(sc_make(new_pc, NULL));
}
 
 
/* ======================================================================== */
bool solve_system_by_succ_elim(sys, sigma)
Psysteme sys;
list *sigma;
{
  bool result = true;
  list sig = *sigma, sigma_p;
  Pcontrainte leg;
  Pvecteur new_v;
 
  /* We walk through all the equations of M_ps. */
  for(leg = sys->egalites; leg != NULL; leg = leg->succ) {
    if(get_debug_level() > 3) {
      fprintf(stderr, "[solve_system_by_succ_elim] \tCrt equation:");
      pu_egalite_fprint(stderr, leg, pu_variable_name);
      fprintf(stderr, "\n");
    }
 
    /* We apply on this expression the substitution "sigma" */
    new_v = vvs_on_vecteur(sig, leg->vecteur);
    if(get_debug_level() > 1) {
      fprintf(stderr, "[solve_system_by_succ_elim] \t\tEqu after apply crt subs:");
      pu_vect_fprint(stderr, new_v);
      fprintf(stderr, "\n");
    }
 
    /* We create the elementary substitution with a variable not yet
     * eliminated.
     */
    sigma_p = plc_make_vvs_with_vector(new_v);
    if(get_debug_level() > 4) {
      fprintf(stderr, "[solve_system_by_succ_elim] \t\tSubs of non elim var:\n");
      fprint_vvs(stderr, sigma_p);
      fprintf(stderr, "\n");
    }
 
    if(sigma_p == NIL) {
      /*result = true;*/
    }
    /* We apply it on all prototypes, if none becomes trivial ... */
    else if(is_not_trivial_p(sigma_p)) {
 
      if(get_debug_level() > 3) {
        fprintf(stderr, "[solve_system_by_succ_elim] \tCrt local subs :\n");
        fprint_vvs(stderr, sigma_p);
        fprintf(stderr, "\n");
      }
 
      sig = compose_vvs(sigma_p, sig);
      /*result = true;*/
    }
    else
      result = false;
  }
  *sigma = sig;
 
  return(result);
}
 
 
/* ========================================================================= */
/*
 * bool constant_vecteur_p(Pvecteur pv)
 */
bool constant_vecteur_p(pv)
Pvecteur pv;
{
  if(pv == NULL)
    return(true);
  else
    return( (pv->succ == NULL) && (pv->var == TCST) );
}
 
 
/* ========================================================================= */
/* Psysteme broadcast_dimensions(placement pla, list mu_list)
 *
 */
Psysteme broadcast_dimensions(pla, mu_list)
placement pla;
list mu_list;
{
  list plc_dims, mu_l;
  Psysteme ps_bp;
 
  ps_bp = SC_EMPTY;
  mu_l = mu_list;
  plc_dims =  placement_dims(pla);
  if(plc_dims != NIL) {
    ps_bp = sc_new();
 
    for(; !ENDP(plc_dims); POP(plc_dims), POP(mu_l)) {
      Ppolynome crt_pp = (Ppolynome) CHUNK(CAR(plc_dims));
      Pvecteur pv;
      Variable crt_mu;
 
      crt_mu = (Variable) ENTITY(CAR(mu_l));
      pv = prototype_factorize(crt_pp, crt_mu);
      if(!constant_vecteur_p(pv))
        sc_add_egalite(ps_bp, contrainte_make(pv));
    }
  }
  return(ps_bp);
}
 
 
/* ======================================================================== */
/*
 * Psysteme completer_n_base(Psysteme sys dims_sys, list var_l par_l, int dim)
 *
 * idem as completer_base(), except that we add dimensions from dims_sys
 * until "sys" has "dim" vectors.
 */
Psysteme completer_n_base(sys, dims_sys, var_l, par_l, dim)
Psysteme sys, dims_sys;
list var_l, par_l;
int dim;
{
  Psysteme ps = sc_dup(sys), new_ps = sc_new();
  Pcontrainte pc;
  int crt_dim = sys->nb_eq;
  Pbase var_b, par_b;
 
  var_b = list_to_base(var_l);
  par_b = list_to_base(par_l);
 
  if(dim < crt_dim)
    pips_internal_error("There should not be so much dims");
  else if(dim == crt_dim)
    return(ps);
 
  for(pc = dims_sys->egalites; crt_dim < dim; pc = pc->succ) {
    Pvecteur pv = pc->vecteur;
    Psysteme aux_ps = sc_dup(ps);
    Psysteme aux_new_ps = sc_dup(new_ps);
 
    sc_add_egalite(aux_new_ps, contrainte_make(pv));
    aux_ps = append_eg(aux_ps, aux_new_ps);
 
    if(vecteurs_libres_p(aux_ps, var_b, par_b)) {
      new_ps = aux_new_ps;
      crt_dim++;
    }
    else
      sc_rm(aux_ps);
  }
  ps = append_eg(ps, new_ps);
  ps->base = NULL;
  sc_creer_base(ps);
  return(ps);
}
 
 
/* ========================================================================= */
/*
 * void pm_matrice_scalar_mult(int scal, matrice mat_M, int m n)
 */
void pm_matrice_scalar_mult(scal, mat_M, m, n)
int scal, m, n;
matrice mat_M;
{
  int i, j;
  for(i = 1; i <= m; i++) {
    for(j = 1; j <= n; j++) {
      ACCESS(mat_M, m, i, j) = scal * ACCESS(mat_M, m, i, j);
    }
  }
}
 
 
/* ========================================================================= */
/*
 * list partial_broadcast_coefficients(list var_l, list *used_mu)
 *
 * Takes into account the partial broadcast prototypes (contain in "pfunc") to
 * replace some of the coefficients in "var_l" by the "mu" coefficients
 * (used by these broadcast prototypes). The returned value the substitution
 * resulting of this computation. "used_mu" should be empty at the beginning
 * and is equal to the list of the mu coeff actually used.
 *
 * This computation is done on each statemwent.
 *
 * For a given statemwent s, we have to get the corresponding placement
 * object sp of the list contained in "pfunc" (a global variable). The
 * broadcast prototypes are contained in the field dims.
 * If this list is empty, we do not have anything to do. Else, this list
 * contained at most sd prototypes (sd is the dimension of the distribution
 * space for s). Each prototype has been associated to a Mu coefficient.
 * First, we have to construct the dimension not filled (if any). After this,
 * we will have sd prototypes as:
 *      for i in {1,...,sd}, bp_i = mu_i.eps_i
 * When summed:
 *      bp = J.M, where J is a row vector of broadcast directions and M is a
 * column vector of Mu coefficients.
 * These broadcast directions may be expressed with respect to the indices:
 *      J = I.P, where I is a row vector of indices and P is a 2-D matrice.
 *
 * Prototype of s may be represented as:
 *      pp = I.A.L + S.B.L + C.L + I.D + S.E + c, where S is a row vector of
 * parameters,  A and B are 2-D integer matrices, L is a column vector of
 * coefficients (those of "var_l"), C, D and E are integer column vectors
 * and c is an integer scalar.
 *
 * So, we have:
 *      I.A.L + I.D = J.M = I.P.M
 * i.e.:
 *      A.L + D = P.M
 *
 * So we have to construct the following system of equation:
 *      A.L + D - P.M == 0
 * From this system, we can express some of coefficients of L with respect to
 * the others (of L and M).
 *
 * 
 */
list partial_broadcast_coefficients(var_l, used_mu)
list var_l;
list *used_mu;
{
  extern plc pfunc;
 
  list plcs, new_vvs = NIL, uml = NIL;
 
  for(plcs = plc_placements(pfunc); !ENDP(plcs); POP(plcs)){
    placement crt_pla = PLACEMENT(CAR(plcs));
    list crt_dims = placement_dims(crt_pla);
    int crt_stmt = placement_statement(crt_pla);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] for stmt %d, with dims:\n", crt_stmt);
fprint_pla_pp_dims(stderr, crt_pla);
fprintf(stderr, "\n");
}
 
    if(crt_dims != NIL) {
      list mu_list, ind_l, par_l, vl, il, init_l, elim_l, vvs_L;
      Psysteme ps_bp, ps_pp_dims, new_ps, elim_ps;
      static_control stct;
      int i,j, sd, n, m, l;
      Pcontrainte new_pc;
      Ppolynome pp;
      matrice mat_Q, mat_Qc, mat_P, mat_Pc, mat_A;
 
      mu_list = (list) hash_get(StmtToMu, (char *) crt_stmt);
      uml = gen_append(mu_list, uml);
      stct = get_stco_from_current_map(adg_number_to_statement(crt_stmt));
      ind_l = static_control_to_indices(stct);
      par_l = gen_append(prgm_parameter_l, NIL);
      sd = (int) hash_get(StmtToPdim, (char *) crt_stmt);
      pp = (Ppolynome) hash_get(StmtToProto, (char *) crt_stmt);
 
      /* Construction of the directions that might be generated by the
       * prototype.
       */
      ps_pp_dims = sc_new();
      for(vl = var_l; !ENDP(vl); POP(vl)) {
        entity crt_var = ENTITY(CAR(vl));
        Pvecteur pv = prototype_factorize(pp, (Variable) crt_var);
        if(!VECTEUR_NUL_P(pv)) {
          Psysteme aux_ps = sc_new();
          sc_add_egalite(aux_ps, contrainte_make(pv));
          sc_creer_base(aux_ps);
          ps_pp_dims = append_eg(ps_pp_dims, aux_ps);
        }
      }
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Prototype dir:\n");
fprint_psysteme(stderr, ps_pp_dims);
fprintf(stderr, "\n");
}
 
      /* Construction of -P.M */
      ps_bp = broadcast_dimensions(crt_pla, mu_list);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Broadcast dir:\n");
fprint_psysteme(stderr, ps_bp);
fprintf(stderr, "\n");
}
 
      ps_bp = completer_n_base(ps_bp, ps_pp_dims, ind_l, par_l, sd);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] FULL Broadcast dir:\n");
fprint_psysteme(stderr, ps_bp);
fprintf(stderr, "\n");
}
 
      n = sd;
      m = gen_length(ind_l);
      mat_Q = matrice_new(n, m);
      mat_Qc = matrice_new(n, 1);
      pu_contraintes_to_matrices(ps_bp->egalites, list_to_base(ind_l),
                                 mat_Q, mat_Qc, n, m);
      mat_P = matrice_new(m, n);
      mat_Pc = matrice_new(m, 1);
      matrice_nulle(mat_Pc, m, 1);
      matrice_transpose(mat_Q, mat_P, n, m);
      pm_matrice_scalar_mult(-1, mat_P, m, n);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Matrix -P:\n");
matrice_fprint(stderr, mat_P, m, n);
fprintf(stderr, "\n");
}
 
      /* Construction of A.L + D */
      l = gen_length(var_l)+1;
      mat_A = matrice_new(m, l);
      for(il = ind_l, i=1; !ENDP(il); POP(il), i++) {
        entity crt_ind = ENTITY(CAR(il));
        Pvecteur pv = prototype_factorize(pp, (Variable) crt_ind);
 
        for(vl = var_l, j=1; !ENDP(vl); POP(vl), j++) {
          entity crt_v = ENTITY(CAR(vl));
          ACCESS(mat_A,m,i,j) = vect_coeff((Variable) crt_v, pv);
        }
        ACCESS(mat_A,m,i,l) = vect_coeff(TCST, pv);
      }
      DENOMINATOR(mat_A) = 1;
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Matrix A|D:\n");
matrice_fprint(stderr, mat_A, m, l);
fprintf(stderr, "\n");
}
 
      /* A.L + D - P.M */
      matrices_to_contraintes_with_sym_cst(&new_pc, list_to_base(mu_list),
                                           list_to_base(var_l), mat_P, mat_A,
                                           m, n, l);
 
      matrice_free(mat_Q);
      matrice_free(mat_Qc);
      matrice_free(mat_P);
      matrice_free(mat_Pc);
      matrice_free(mat_A);
 
      new_ps = sc_make(new_pc, NULL);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] A.L + D - P.M:\n");
fprint_psysteme(stderr, new_ps);
fprintf(stderr, "\t Var to eliminate : ");
fprint_entity_list(stderr, var_l);
fprintf(stderr, "\n");
}
 
      init_l = gen_append(var_l, NIL);
      elim_l= NIL;
      elim_ps = elim_var_with_eg(new_ps, &init_l, &elim_l);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] After ELIM LAMBDAs\n");
fprintf(stderr, "\tElim Coeff and System: ");
fprint_entity_list(stderr, elim_l);
fprint_psysteme(stderr, elim_ps);
fprintf(stderr, "\tRemaining Coeff and System : ");
fprint_entity_list(stderr, init_l);
fprint_psysteme(stderr, new_ps);
fprintf(stderr, "\n");
}
 
      vvs_L = make_vvs_from_sc(elim_ps, elim_l);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Sub for elim lambdas:\n");
fprint_vvs(stderr, vvs_L);
fprintf(stderr, "\n");
}
 
      if(new_ps->nb_eq != 0) {
        Psysteme elim_ps2;
        list elim_l2, init_l2;
        list vvs_M;
 
        init_l2 = gen_append(mu_list, NIL);
        elim_l2 = NIL;
        elim_ps2 = elim_var_with_eg(new_ps, &init_l2, &elim_l2);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] After ELIM MUs\n");
fprintf(stderr, "\tElim Coeff and System: ");
fprint_entity_list(stderr, elim_l2);
fprint_psysteme(stderr, elim_ps2);
fprintf(stderr, "\tRemaining Coeff and System : ");
fprint_entity_list(stderr, init_l2);
fprint_psysteme(stderr, new_ps);
fprintf(stderr, "\n");
}
 
        vvs_M = make_vvs_from_sc(elim_ps2, elim_l2);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Sub for elim mus:\n");
fprint_vvs(stderr, vvs_M);
fprintf(stderr, "\n");
}
 
        vvs_L = compose_vvs(vvs_L, vvs_M);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Sub for MUs and LAMBDAs:\n");
fprint_vvs(stderr, vvs_L);
fprintf(stderr, "\n");
}
      }
      new_vvs = compose_vvs(new_vvs, vvs_L);
 
if(get_debug_level() > 4) {
fprintf(stderr, "[partial_broadcast_coefficients] Crt sub:\n");
fprint_vvs(stderr, new_vvs);
fprintf(stderr, "\n");
}
    }
  }
  *used_mu = uml;
  return(new_vvs);
}
 
 
/* ======================================================================== */
bool is_mu_coeff_p(e)
entity e;
{
  return(strncmp(entity_local_name(e), MU_COEFF, 4) == 0);
}
 
 
/* ========================================================================= */
/*
 * list get_mu_coeff(list sigma)
 */
list get_mu_coeff(sigma)
list sigma;
{
  list mu_list = NIL, vl;
 
  for(vl = sigma; !ENDP(vl); POP(vl)) {
    var_val vv = VAR_VAL(CAR(vl));
    entity c = var_val_variable(vv);
 
    if(is_mu_coeff_p(c))
      mu_list = CONS(ENTITY, c, mu_list);
  }
  return(mu_list);
}
 
 
/* ========================================================================= */
/*
 * void vvs_on_prototypes(list sigma)
 */
void vvs_on_prototypes(sigma)
list sigma;
{
  extern hash_table StmtToProto;
  extern graph the_dfg;
 
  list vl;
 
  for(vl = graph_vertices(the_dfg); vl != NIL; vl = CDR(vl)) {
    vertex v = VERTEX(CAR(vl));
    int stmt = vertex_int_stmt(v);
    Ppolynome pp = (Ppolynome) hash_get(StmtToProto, (char *) stmt);
 
    (void) hash_del(StmtToProto, (char *) stmt);
    hash_put(StmtToProto, (char *) stmt, (char *) vvs_on_polynome(sigma, pp));
  }
}
 
 
/* ========================================================================= */
/*
 * void prgm_mapping((char*) module_name):
 * 
 * It computes the placement function for all statement (i.e. nodes of "g").
 * This computation is done in three steps: initialization, edges treatment,
 * valuation.
 *
 * 1. The initialization consists in creating a prototype of placement
 * function for each statement (cf. plc_make_proto()), in computing the
 * placement function dimension and in computing the weight of the edges.
 *
 * 2. The edges treatment consists in determining some of the coefficients
 * of the prototypes using first the broadcast conditions and second the
 * distance conditions.
 *
 * 3. The valuation consists in determining the coefficients not yet
 * valuated and in building the dimensions of the placement function.
 */
bool prgm_mapping(module_name)
char*   module_name;
{
  extern plc pfunc;             /* The placement function */
  extern bdt the_bdt;           /* The timing function */
  extern graph the_dfg;
  extern int nb_nodes,          /* The number of nodes in the DFG */
             nb_dfs;            /* The number of dataflows in the DFG */
 
  extern hash_table DtfToDist;  /* Mapping from a dataflow to its distance */
  extern hash_table StmtToProto;/* Mapping from a statement to its prototype */
  extern hash_table DtfToSink;
  extern hash_table DtfToWgh;
 
  extern list prgm_parameter_l;
 
  struct  tms             chrono1, chrono2; /* Perf.mesurement */
  statement_mapping STS;
 
  /* List of the unknowns coefficients */
  list lambda, xmu_lambda, mu_lambda, mu,
       sigma, sigma1, sigma2, sigma_p, *sigma3,
       su_l,
       sorted_df_l, l, remnants_df_l, df_l;
  Psysteme M_ps;
  int dmax, i;
  entity ent;
  static_control          stco;
  statement               mod_stat;
  char *md;
 
  /* Initialize debugging functions */
  debug_on("MAPPING_DEBUG_LEVEL");
  if(get_debug_level() > 0)
    fprintf(stderr, "\n\n *** COMPUTE MAPPING for %s\n", module_name);
 
  if(get_debug_level() > 1) {
    times(&chrono1);
  }
 
  /* We get the required data: module entity, code, static_control, dataflow
   * graph, timing function.
   */
  ent = local_name_to_top_level_entity( module_name );
 
  set_current_module_entity(ent);
 
  mod_stat = (statement) db_get_memory_resource(DBR_CODE, module_name, true);
  STS = (statement_mapping) db_get_memory_resource(DBR_STATIC_CONTROL,
                                                       module_name, true);
  stco     = (static_control) GET_STATEMENT_MAPPING(STS, mod_stat);
  if ( stco == static_control_undefined) {
    pips_internal_error("This is an undefined static control !");
  }
  if ( !static_control_yes( stco )) {
    pips_internal_error("This is not a static control program !");
  }
 
  set_current_stco_map(STS);
 
  prgm_parameter_l = static_control_params(stco);
 
  if(get_debug_level() > 2) {
    fprintf(stderr, "[prgm_mapping] Structure parameters of the program: ");
    fprint_entity_list(stderr, prgm_parameter_l);
    fprintf(stderr, "\n");
  }
 
  /* The DFG */
  the_dfg = adg_pure_dfg((graph) db_get_memory_resource(DBR_ADFG, module_name, true));
 
  /* the BDT */
  the_bdt = bdt_undefined;
  the_bdt = (bdt) db_get_memory_resource(DBR_BDT, module_name, true);
 
  if(get_debug_level() > 2) {
    fprint_dfg(stderr, the_dfg);
  }
  if(get_debug_level() > 0) {
    fprint_bdt(stderr, the_bdt);
  }
  /* First we count the number of nodes and dataflows */
  nb_nodes = 0;
  nb_dfs = 0;
  for(l = graph_vertices(the_dfg); !ENDP(l); POP(l)) {
    nb_nodes++;
    for(su_l = vertex_successors(VERTEX(CAR(l))); !ENDP(su_l); POP(su_l)) {
      for(df_l = SUCC_DATAFLOWS(SUCCESSOR(CAR(su_l))); df_l != NIL; df_l = CDR(df_l)) {
        nb_dfs++;
      }
    }
  }
 
  /* We look for the broadcasts */
  broadcast(the_dfg);
 
  /* We sort the nodes of "the_dfg" in decreasing dimension order. The
   * dimension of a node is the dimension of the iteration space of its
   * instruction.
   */
  graph_vertices(the_dfg) = sort_dfg_node(graph_vertices(the_dfg));
 
  if(get_debug_level() > 2)
{
    fprintf(stderr, "[prgm_mapping] Nodes order:");
    for(l = graph_vertices(the_dfg); ! ENDP(l); POP(l))
      fprintf(stderr, " %d,", vertex_int_stmt(VERTEX(CAR(l))));
    fprintf(stderr, "\n");
  }
 
/* INITIALIZATION */
  /* We create a prototype for each statement. Each prototype is mapped to
   * its statement in the hash table "StmtToProto". An other hash table
   * "StmtToProto" associates the unknown coefficients used in the
   * prototype and the statement. The returned value "lambda" gives all
   * the coefficients that have been created.
   */
  lambda = plc_make_proto();
 
  if(get_debug_level() > 2)
{
    fprintf(stderr, "[prgm_mapping] Nodes prototypes:\n");
    plc_fprint_proto(stderr, the_dfg, StmtToProto);
    fprintf(stderr, "[prgm_mapping] LAMBDAS: ");
    fprint_entity_list(stderr, lambda);
    fprintf(stderr, "\n");
  }
 
  /* plc_make_dim() has to initialize the Mu list*/
 
  /* We compute the dimension of the placement function of each instruction,
   * and the greatest one (dmax). This is based on the timing function, if it
   * exists.
   */
  count_mu_coeff = 1;
  dmax = plc_make_dim();
 
  /* The number of mapping dimensions can be computed as a minimum, see
   * plc_make_min_dim() */
  i = ((md = getenv("MINIMUM_DIMENSION")) != NULL) ? 1 : 0;
  if(i == 1) {
    int dmin;
 
    dmin = plc_make_min_dim();
 
    user_warning("prgm_mapping",
                 "Minimum number of dimensions: %d instead of %d\n",
                 dmin, dmax);
 
    dmax = dmin;
  }
 
  /* Mapping dimension can be fixed with the environment variable
   * MAPPING_DIMENSION */
  i = ((md = getenv("MAPPING_DIMENSION")) != NULL) ? atoi(md) : dmax;
  if(i != dmax) {
    user_warning("prgm_mapping",
                 "environment variable MAPPING_DIMENSION has set the mapping dimension to %d instead of %d\n",
                 i, dmax);
 
    dmax = i;
  }
  
  /* We initialize the prgm_mapping function. */
  pfunc = make_plc(NIL);
  for(l = graph_vertices(the_dfg); l != NIL; l = CDR(l)) {
    placement new_func;
    vertex v = VERTEX(CAR(l));
    int stmt = vertex_int_stmt(v);
 
    new_func = make_placement(stmt, NIL);
    plc_placements(pfunc) = gen_nconc(plc_placements(pfunc),
                                      CONS(PLACEMENT, new_func, NIL));
  }
 
  debug(3, "prgm_mapping", "DIM des fonctions de placement : %d\n", dmax);
  if(dmax == 0) {
    for(l = plc_placements(pfunc); !ENDP(l); POP(l)) {
      placement crt_func = PLACEMENT(CAR(l));
      placement_dims(crt_func) = CONS(EXPRESSION,
                                      int_to_expression(0),
                                      NIL);
    }
 
    DB_PUT_MEMORY_RESOURCE(DBR_PLC, strdup(module_name), pfunc);
    reset_current_stco_map();
    reset_current_module_entity();
    debug_off();
    return(true);
  }
 
  /* Computation of the weight of each dataflow of the DFG. */
  edge_weight();
 
  /* We get all the dataflows of the graph */
  df_l = get_graph_dataflows(the_dfg);
  if(get_debug_level() > 5) {
    fprintf(stderr, "[prgm_mapping] Edges UNorder:\n");
    plc_fprint_dfs(stderr, df_l, DtfToSink, DtfToWgh);
  }
 
  /* We sort the dataflows in decreasing weight order */
  sorted_df_l = general_merge_sort(df_l, compare_dfs_weight);
  if(get_debug_level() > 2)
 {
    fprintf(stderr, "[prgm_mapping] Edges order:\n");
    plc_fprint_dfs(stderr, sorted_df_l, DtfToSink, DtfToWgh);
  }
 
 
/* EDGES TREATMENT */
 
/* BROADCAST CONDITIONS */
  /* We take into account the broadcast conditions */
  sigma = NIL;
  remnants_df_l = broadcast_conditions(lambda, sorted_df_l, &sigma);
  if(get_debug_level() > 2)
  {
    fprintf(stderr, "[prgm_mapping] Dif Red restriction:\n");
    fprint_vvs(stderr, sigma);
    fprintf(stderr, "[prgm_mapping] Remnants :\n");
    plc_fprint_dfs(stderr, remnants_df_l, DtfToSink, DtfToWgh);
  }
 
  for(sigma_p = sigma; !ENDP(sigma_p); POP(sigma_p))
    gen_remove(&lambda, (chunk *) var_val_variable(VAR_VAL(CAR(sigma_p))));
 
  if(get_debug_level() > 2)
  {
    fprintf(stderr, "[prgm_mapping] Prototypes after broadcast conditions:\n");
    plc_fprint_proto(stderr, the_dfg, StmtToProto);
    fprintf(stderr, "\n");
  }
 
  mu = NIL;
  sigma1 = partial_broadcast_coefficients(lambda, &mu);
 
  if(get_debug_level() > 3)
{
fprintf(stderr, "[prgm_mapping] ******* Partial broadcast sub:");
fprint_vvs(stderr, sigma1);
fprintf(stderr, "\n");
}
 
  vvs_on_prototypes(sigma1);
 
  if(get_debug_level() > 2) 
{
    fprintf(stderr, "[prgm_mapping] Prototypes after partial broadcast sub:\n");
    plc_fprint_proto(stderr, the_dfg, StmtToProto);
    fprintf(stderr, "\n");
}
 
  for(sigma_p = sigma1; !ENDP(sigma_p); POP(sigma_p)) {
    entity e = var_val_variable(VAR_VAL(CAR(sigma_p)));
    gen_remove(&lambda, (chunk *) e);
    gen_remove(&mu, (chunk *) e);
  }
 
if(get_debug_level() > 3) {
fprintf(stderr, "[prgm_mapping] ******* Remaining lambdas and Mus:\n");
fprintf(stderr, "\t LAMBDAs:");
fprint_entity_list(stderr, lambda);
fprintf(stderr, "\n");
fprintf(stderr, "\t MUs:");
fprint_entity_list(stderr, mu);
fprintf(stderr, "\n");
}
 
/*MOD : we could give "remnants_df_l" as an arg, in order to only compute the
useful distances. */
 
/* DISTANCE COMPUTATION */
  /* Computation of the distance of each dataflow. */
  plc_make_distance();
  if(get_debug_level() > 2) {
    fprintf(stderr, "[prgm_mapping] Edges distances:\n");
    plc_fprint_distance(stderr, the_dfg, DtfToDist);
  }
 
/* CUTTING CONDITIONS */
  /* We compute the list of equations that are to be nullified in order to zero
   * out all the distances.
   */
  M_ps = cutting_conditions(remnants_df_l);
  if(get_debug_level() > 2)
{
    fprintf(stderr, "[prgm_mapping] Matrix M:\n");
    fprint_psysteme(stderr, M_ps);
  }
 
  sigma2 = NIL;
  (void) solve_system_by_succ_elim(M_ps, &sigma2);
 
  if(get_debug_level() > 2) 
{
    fprintf(stderr, "Crt subs:\n");
    fprint_vvs(stderr, sigma2);
  }
    
if(get_debug_level() > 0) {
    fprintf(stderr, "[prgm_mapping] Prototypes after distance conditions:\n");
    plc_fprint_proto(stderr, the_dfg, StmtToProto);
    fprintf(stderr, "\n");
}
 
  /* We eliminate all the unknowns that are valuated by the substitution
   * computed above "sigma"; and then we cut it in two parts, one
   * containing the indices coefficients, one containing the parameters
   * coefficients, both sorted by decreasing frenquency in the
   * prototypes. Before cutting the list "lambda" into two parts, we take
   * into account the partial broadcast prototypes (contain in "pfunc") to
   * replace some of the "lambda" coeff by the "mu" coeff. The new sigma
   * is returned by this function.  */
 
  for(sigma_p = sigma2; !ENDP(sigma_p); POP(sigma_p)) {
    entity e = var_val_variable(VAR_VAL(CAR(sigma_p)));
    gen_remove(&lambda, (chunk *) e);
    gen_remove(&mu, (chunk *) e);
  }
 
if(get_debug_level() > 3) {
fprintf(stderr, "[prgm_mapping] ******* Remaining lambdas:");
fprint_entity_list(stderr, lambda);
fprintf(stderr, "\n");
fprintf(stderr, "[prgm_mapping] ******* Remaining mus:");
fprint_entity_list(stderr, mu);
fprintf(stderr, "\n");
}
 
  /* UNELIMINATED COEFF SORTING */
  sort_unknowns(&lambda, dmax);
  sort_unknowns(&mu, dmax);
 
if(get_debug_level() > 3) {
fprintf(stderr, "[prgm_mapping] ******* Sorted lambdas:");
fprint_entity_list(stderr, lambda);
fprintf(stderr, "\n");
fprintf(stderr, "[prgm_mapping] ******* Sorted mus:");
fprint_entity_list(stderr, mu);
fprintf(stderr, "\n");
}
 
  /* COEFF PARTITION */
  mu_lambda = gen_nconc(mu, lambda);
  xmu_lambda = partition_unknowns(&mu_lambda, dmax);
 
  if(get_debug_level() > 2) 
  {
    fprintf(stderr, "[prgm_mapping] \nRemaining unknowns\n");
    fprintf(stderr, "\tX COEFF: ");
    for(l = xmu_lambda; !ENDP(l); POP(l)) {
      fprintf(stderr, "(");
      fprint_entity_list(stderr, CONSP(CAR(l)));
      fprintf(stderr, ") ");
    }
    fprintf(stderr, "\tPC COEFF: ");
    fprint_entity_list(stderr, mu_lambda);
    fprintf(stderr, "\n");
 
fprint_plc_pp_dims(stderr, pfunc);
}
 
/* VALUATION */
  /* We valuate all the remaining unknowns by building successively each
   * dimension.
   */
  sigma3 = (list *) malloc(sizeof(list)*dmax);
  for(i = 0; i < dmax; i++) {
    list plcs;
 
    sigma3[i] = valuer(i, xmu_lambda, mu_lambda);
 
    if(get_debug_level() > 2) 
    {
      fprintf(stderr, "[prgm_mapping] Plc dim %d, new subs is\n", i);
      fprint_vvs(stderr, sigma3[i]);
      fprintf(stderr, "\n");
    }
 
    for(l = graph_vertices(the_dfg), plcs = plc_placements(pfunc); l != NIL;
        l = CDR(l), POP(plcs)) {
      placement crt_func = PLACEMENT(CAR(plcs));
      list dims;
      vertex v = VERTEX(CAR(l));
      int stmt = vertex_int_stmt(v);
 
      Ppolynome pp = polynome_dup((Ppolynome) hash_get(StmtToProto,
                                                       (char *) stmt));
      Ppolynome sub_pp = vvs_on_polynome(sigma3[i], pp);
      Pvecteur sub_vect = polynome_to_vecteur(sub_pp);
      expression exp = Pvecteur_to_expression(sub_vect);
 
      if(i == 0)
        dims = NIL;
      else
        dims = placement_dims(crt_func);
 
      if(exp == expression_undefined)
        exp = int_to_expression(0);
 
      placement_dims(crt_func) = gen_nconc(dims, CONS(EXPRESSION, exp, NIL));
    }
  }
 
  if(get_debug_level() > 0) {
    fprintf(stderr, "\n RESULT OF MAPPING:\n**************\n");
    df_l = get_graph_dataflows(the_dfg);
    for(i = 0; i < dmax; i++) {
      fprintf(stderr,
              "Distance for dim %d\n=================================\n", i);
      
      for(l = df_l; !ENDP(l); POP(l)) {
        dataflow df = DATAFLOW(CAR(l));
        int stmt = (int) hash_get(DtfToSink, (char *) df);
        Ppolynome pp_dist = polynome_dup((Ppolynome) hash_get(DtfToDist,
                                                              (char *) df));
 
        pp_dist = vvs_on_polynome(sigma, pp_dist);
        pp_dist = vvs_on_polynome(sigma1, pp_dist);
        pp_dist = vvs_on_polynome(sigma2, pp_dist);
        pp_dist = vvs_on_polynome(sigma3[i], pp_dist);
 
        fprintf(stderr, "Dataflow ");
        fprint_dataflow(stderr, stmt, df);
        fprintf(stderr, "\tDist = ");
        polynome_fprint(stderr, pp_dist, pu_variable_name, pu_is_inferior_var);
        fprintf(stderr, "\n");
      }
    }
  }
 
  if(get_debug_level() > 1) {
    times(&chrono2);
 
    fprintf(stderr,
            "\n*******\nTIMING:\n*******\n\tuser : %ld, system : %ld \n",
            (long) chrono2.tms_utime - chrono1.tms_utime,
            (long) chrono2.tms_stime - chrono1.tms_stime );
  }
 
  if(get_debug_level() > 0) {
    fprintf(stderr, "\n MAPPING:\n**************\n");
    fprint_plc(stderr, pfunc);
    fprintf(stderr, "\n\n *** MAPPING done\n");
  }
 
  DB_PUT_MEMORY_RESOURCE(DBR_PLC, strdup(module_name), pfunc);
 
  reset_current_stco_map();
  reset_current_module_entity();
 
  debug_off();
 
  return(true);
}