prgm_mapping.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/times.h>
#include <sys/time.h>
#include "genC.h"
#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"
#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 "pipsdbm.h"
#include "resources.h"
#include "static_controlize.h"
#include "paf-util.h"
#include "pip.h"
#include "array_dfg.h"
#include "prgm_mapping.h"

Include dependency graph for prgm_mapping.c:

Go to the source code of this file.

Macros
#define	DOT   "."
	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. More...
#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 */
#define	PLC_EXT   ".plc_file"

Typedefs
typedef dfg_vertex_label	vertex_label
	Local defines. More...
typedef dfg_arc_label	arc_label

Functions
bool	print_plc (char *module_name) const
	======================================================================== More...
list	plc_make_proto ()
	======================================================================== More...
void	initialize_mu_list (int stmt, int dim)
	======================================================================== More...
int	plc_make_min_dim ()
	======================================================================== More...
int	plc_make_dim ()
	======================================================================== More...
void	plc_make_distance ()
	======================================================================== More...
Psysteme	cutting_conditions (list df_l)
	======================================================================== More...
list	sort_dfg_node (list l_nodes)
	======================================================================== More...
void	edge_weight ()
	======================================================================== More...
bool	in_list_p (chunk *c, list l)
	======================================================================== More...
void	add_to_list (chunk *c, list *l)
	======================================================================== More...
int	prototype_dimension (Ppolynome pp, list ind_l)
	======================================================================== More...
bool	is_not_trivial_p (list vvs)
	======================================================================== More...
list	valuer (int dim, list xunks, list pcunks)
	======================================================================== More...
void	sort_unknowns (list *lambda, int dmax)
	======================================================================== More...
list	partition_unknowns (list *unks, int dmax)
	======================================================================== More...
Psysteme	system_inversion_restrict (Psysteme sys, list unks_l, list var_l, list par_l, int nb_restrict, bool is_first)
	======================================================================== More...
bool	solve_system_by_succ_elim (Psysteme sys, list *sigma)
	======================================================================== More...
bool	constant_vecteur_p (Pvecteur pv)
	========================================================================= More...
Psysteme	broadcast_dimensions (placement pla, list mu_list)
	========================================================================= More...
Psysteme	completer_n_base (Psysteme sys, Psysteme dims_sys, list var_l, list par_l, int dim)
	======================================================================== More...
void	pm_matrice_scalar_mult (int scal, matrice mat_M, int m, int n)
	========================================================================= More...
list	partial_broadcast_coefficients (list var_l, list *used_mu)
	========================================================================= More...
bool	is_mu_coeff_p (entity e)
	======================================================================== More...
list	get_mu_coeff (list sigma)
	========================================================================= More...
void	vvs_on_prototypes (list sigma)
	========================================================================= More...
bool	prgm_mapping (char *module_name)
	========================================================================= More...

Variables
plc	pfunc
	Internal variables More...
graph	the_dfg
	The placement function. More...
bdt	the_bdt
	The data flow graph. More...
int	nb_nodes
	The timing function. More...
int	nb_dfs
	The number of nodes in the DFG. More...
hash_table	DtfToSink
	The number of dataflows in the DFG. More...
hash_table	DtfToDist
	Mapping from a dataflow to its sink statement. More...
hash_table	DtfToWgh
	Mapping from a dataflow to its distance. More...
hash_table	StmtToProto
	Mapping from a dataflow to its weight. More...
hash_table	StmtToPdim
	Mapping from a statement (int) to its prototype. More...
hash_table	StmtToBdim
	Mapping from a statement to the dim of its plc func. More...
hash_table	StmtToDim
	Mapping from a statement to the dim of its bdt. More...
hash_table	StmtToLamb
	Mapping from a stmt to its iteration space dim. More...
hash_table	StmtToMu
	Mapping from a stmt to its lambda coeff. More...
hash_table	UnkToFrenq
	Mapping from a stmt to its mu coeff. More...
int	count_mu_coeff
	Mapping from an entity to its frenq in the plc proto. More...
list	subs_l
list	prgm_parameter_l
	global variables More...

Macro Definition Documentation

BDT_STRING

#define BDT_STRING   "bdt"

Definition at line 90 of file prgm_mapping.c.

DOT

#define DOT   "."

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
performance purpose performance purpose Newgen includes
C3 includes
Pips includes
Macro functions

Definition at line 89 of file prgm_mapping.c.

DTF_HT_SIZE

#define DTF_HT_SIZE   200 /**hash table max size */

Definition at line 92 of file prgm_mapping.c.

ENT_HT_SIZE

#define ENT_HT_SIZE   200 /**hash table max size */

Definition at line 93 of file prgm_mapping.c.

PLC_EXT

#define PLC_EXT   ".plc_file"

Definition at line 121 of file prgm_mapping.c.

STMT_HT_SIZE

#define STMT_HT_SIZE   100 /**hash table max size */

Definition at line 91 of file prgm_mapping.c.

Typedef Documentation

arc_label

typedef dfg_arc_label arc_label

Definition at line 119 of file prgm_mapping.c.

vertex_label

typedef dfg_vertex_label vertex_label

Local defines.

Definition at line 118 of file prgm_mapping.c.

Function Documentation

add_to_list()

void add_to_list	(	chunk *	c,
		list *	l
	)

========================================================================

Definition at line 939 of file prgm_mapping.c.

{
  list ll = *l;
  if(!in_list_p(c, ll))
    *l = CONS(CHUNK, c, ll);
}

References CHUNK, CONS, and in_list_p().

Here is the call graph for this function:

broadcast_dimensions()

Psysteme broadcast_dimensions	(	placement	pla,
		list	mu_list
	)

=========================================================================

Psysteme broadcast_dimensions(placement pla, list mu_list)

Definition at line 1799 of file prgm_mapping.c.

{
  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);
}

References CAR, CHUNK, constant_vecteur_p(), contrainte_make(), ENDP, ENTITY, NIL, placement_dims, POP, prototype_factorize(), sc_add_egalite(), and sc_new().

Referenced by mapping_on_broadcast(), and partial_broadcast_coefficients().

Here is the call graph for this function:

Here is the caller graph for this function:

completer_n_base()

Psysteme completer_n_base	(	Psysteme	sys,
		Psysteme	dims_sys,
		list	var_l,
		list	par_l,
		int	dim
	)

========================================================================

Definition at line 1834 of file prgm_mapping.c.

{
  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);
}

References append_eg(), Ssysteme::base, contrainte_make(), list_to_base(), pips_internal_error, sc_add_egalite(), sc_creer_base(), sc_dup(), sc_new(), sc_rm(), Scontrainte::vecteur, and vecteurs_libres_p().

Referenced by partial_broadcast_coefficients().

Here is the call graph for this function:

Here is the caller graph for this function:

constant_vecteur_p()

bool constant_vecteur_p

(

Pvecteur

pv

)

=========================================================================

Definition at line 1785 of file prgm_mapping.c.

{
  if(pv == NULL)
    return(true);
  else
    return( (pv->succ == NULL) && (pv->var == TCST) );
}

References TCST.

Referenced by broadcast_dimensions().

Here is the caller graph for this function:

cutting_conditions()

Psysteme cutting_conditions

(

list

df_l

)

========================================================================

Mapping from a dataflow to its distance

Iteration vector of the sink statement.

Structure parameters.

sink_par_l = gen_append(static_control_params(sink_stct), CONS(ENTITY, (entity) TCST, NIL));

We transforme this polynome ("pp_dist") into two systems of equations, Mi and Mp (cf. above).

Definition at line 682 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), append_eg(), CAR, CONS, DATAFLOW, DtfToDist, DtfToSink, ENDP, ENTITY, fprint_psysteme(), fprintf(), gen_append(), get_debug_level(), get_stco_from_current_map(), hash_get(), int, NIL, nullify_factors(), polynome_dup(), polynome_rm(), POP, prgm_parameter_l, sc_new(), sc_normalize(), sink_stmt, static_control_to_indices(), and TCST.

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

edge_weight()

void edge_weight

(

)

========================================================================

We initialize the weight and sink statement hash tables

For each dataflow of the data flow graph we compute its weight.

Transformation system of equations

We append the execution domain of the sink.

We append the governing predicate. "sc_trans" is what we called Ee (the emitter set, cf. above).

Gauss-Jordan eliminations (with equalities).

Fourier-Motzkin eliminations (with inequalities).

We compute the number of implicit equations.

We compute the weight of the current dataflow.

We update the hash tables keyed by the dataflow with its weight and its sink statement.

Definition at line 795 of file prgm_mapping.c.

{
  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);
      }
    }
  }
}

References adg_number_to_statement(), CAR, CDR, communication_dim(), count_implicit_equation(), DATAFLOW, dataflow_governing_pred, dataflow_transformation, debug(), DtfToSink, DtfToWgh, elim_var_with_eg(), ENTITY, entity_local_name(), fprint_dataflow(), fprint_psysteme(), fprintf(), gen_length(), get_debug_level(), get_stco_from_current_map(), gov_pred, graph_vertices, hash_pointer, hash_put(), hash_table_make(), is_broadcast_p(), is_reduction_p(), make_expression_equalities(), nb_dfs, NIL, predicate_system, predicate_undefined, put_source_ind(), sc_append(), sc_dup(), sink_stmt, source_stmt, static_control_to_indices(), SUCC_DATAFLOWS, SUCCESSOR, successor_vertex, the_dfg, trans_l, VERTEX, VERTEX_DOMAIN, vertex_int_stmt(), and vertex_successors.

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

get_mu_coeff()

list get_mu_coeff

(

list

sigma

)

=========================================================================

Definition at line 2155 of file prgm_mapping.c.

{
  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);
}

References CAR, CONS, ENDP, ENTITY, is_mu_coeff_p(), NIL, POP, VAR_VAL, and var_val_variable.

Here is the call graph for this function:

in_list_p()

bool in_list_p	(	chunk *	c,
		list	l
	)

========================================================================

Definition at line 917 of file prgm_mapping.c.

{
  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);
}

References CAR, CHUNK, ENDP, and POP.

Referenced by add_to_list(), and partition_unknowns().

Here is the caller graph for this function:

initialize_mu_list()

void initialize_mu_list	(	int	stmt,
		int	dim
	)

========================================================================

Definition at line 284 of file prgm_mapping.c.

{
  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);
}

References CONS, count_mu_coeff, ENTITY, gen_nconc(), hash_put(), make_coeff(), MU_COEFF, NIL, and StmtToMu.

Referenced by plc_make_dim().

Here is the call graph for this function:

Here is the caller graph for this function:

is_mu_coeff_p()

bool is_mu_coeff_p

(

entity

e

)

========================================================================

Definition at line 2144 of file prgm_mapping.c.

{
  return(strncmp(entity_local_name(e), MU_COEFF, 4) == 0);
}

References entity_local_name(), and MU_COEFF.

Referenced by get_mu_coeff().

Here is the call graph for this function:

Here is the caller graph for this function:

is_not_trivial_p()

bool is_not_trivial_p

(

list

vvs

)

========================================================================

Mapping from a statement to its prototype

For each stmt in the dataflow graph we test if its proto is trivial

we carry on if the prototype is not trivial

Definition at line 1096 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), CAR, CDR, fprint_vvs(), fprintf(), gen_length(), get_debug_level(), get_stco_from_current_map(), graph_vertices, hash_get(), hash_int, hash_put(), hash_table_free(), hash_table_make(), int, nb_nodes, NIL, plc_fprint_proto(), polynome_dup(), polynome_fprint(), prototype_dimension(), pu_is_inferior_var(), pu_variable_name(), static_control_to_indices(), StmtToBdim, StmtToProto, the_dfg, VERTEX, vertex_int_stmt(), and vvs_on_polynome().

Referenced by solve_system_by_succ_elim().

Here is the call graph for this function:

Here is the caller graph for this function:

partial_broadcast_coefficients()

list partial_broadcast_coefficients	(	list	var_l,
		list *	used_mu
	)

=========================================================================

Construction of the directions that might be generated by the prototype.

Construction of -P.M

Construction of A.L + D

A.L + D - P.M

Definition at line 1936 of file prgm_mapping.c.

{
  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);
}

References ACCESS, adg_number_to_statement(), append_eg(), broadcast_dimensions(), CAR, completer_n_base(), compose_vvs(), contrainte_make(), crt_stmt, DENOMINATOR, Ssysteme::egalites, elim_var_with_eg(), ENDP, ENTITY, fprint_entity_list(), fprint_pla_pp_dims(), fprint_psysteme(), fprint_vvs(), fprintf(), gen_append(), gen_length(), get_debug_level(), get_stco_from_current_map(), hash_get(), int, list_to_base(), make_vvs_from_sc(), matrice_fprint(), matrice_free, matrice_new, matrice_nulle(), matrice_transpose(), matrices_to_contraintes_with_sym_cst(), Ssysteme::nb_eq, NIL, pfunc, PLACEMENT, placement_dims, placement_statement, plc_placements, pm_matrice_scalar_mult(), POP, prgm_parameter_l, prototype_factorize(), pu_contraintes_to_matrices(), sc_add_egalite(), sc_creer_base(), sc_make(), sc_new(), static_control_to_indices(), StmtToMu, StmtToPdim, StmtToProto, TCST, vect_coeff(), and VECTEUR_NUL_P.

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

partition_unknowns()

list partition_unknowns	(	list *	unks,
		int	dmax
	)

========================================================================

Definition at line 1498 of file prgm_mapping.c.

{
  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);
}

References CAR, CDR, CONS, CONSP, ENDP, ENTITY, entity_undefined, fprint_entity_list(), fprintf(), gen_append(), gen_nconc(), gen_remove(), get_debug_level(), graph_vertices, hash_get(), in_list_p(), is_index_coeff_p(), NIL, polynome_fprint(), POP, prototype_factorize(), pu_is_inferior_var(), pu_variable_name(), StmtToProto, the_dfg, VECTEUR_NUL_P, VERTEX, and vertex_int_stmt().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

plc_make_dim()

int plc_make_dim

(

)

========================================================================

For each node of the data flow graph we compute its dimension.

We compute the dimension of the current node

We compute the dimension of the timing function of the current node

Definition at line 365 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), bdt_schedules, bdt_undefined, CAR, CDR, ENDP, ENTITY, EXPRESSION, expression_constant_p(), expression_normalized, gen_length(), get_stco_from_current_map(), graph_vertices, hash_pointer, hash_put(), hash_table_make(), initialize_mu_list(), nb_nodes, NIL, NORMALIZE_EXPRESSION, normalized_linear, POP, SCHEDULE, schedule_dims, schedule_statement, static_control_to_indices(), StmtToBdim, StmtToMu, StmtToPdim, the_bdt, the_dfg, vect_coeff(), VERTEX, and vertex_int_stmt().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

plc_make_distance()

void plc_make_distance

(

)

========================================================================

Mapping from a stmt to its prototype

Mapping from a dataflow to its distance

We create the hash table.

Prototype of the source statement.

Iteration vector of the source statement.

Prototype of the sink statement.

For each dataflow of the data flow graph we compute a distance.

Transformations of the dataflows.

There should be as much transformation expressions as source indices in the source iteration vector.

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.

We now compute the distance : D = PI(sink, x) - PI(source, h(x)) Still, it is a polynome ("pp_dist").

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.

We put this polynome in the hash table.

Definition at line 453 of file prgm_mapping.c.

{
  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);
 
      }
    }
  }
}

References adg_number_to_statement(), Ssysteme::base, base_to_list(), CAR, CDR, DATAFLOW, dataflow_governing_pred, dataflow_transformation, dfg_arc_label_dataflows, DtfToDist, elim_var_with_eg(), ENTITY, entity_local_name(), EXPRESSION, expression_to_polynome(), expression_to_string(), find_implicit_equation(), fprint_dataflow(), fprint_psysteme(), fprint_vvs(), fprintf(), gen_length(), get_debug_level(), get_stco_from_current_map(), gov_pred, graph_vertices, hash_get(), hash_pointer, hash_put(), hash_table_make(), make_vvs_from_sc(), nb_dfs, NIL, pips_assert, polynome_add(), polynome_dup(), polynome_fprint(), polynome_mult(), polynome_negate(), POLYNOME_NUL, predicate_system, predicate_undefined, prototype_factorize(), prototype_var_subst(), pu_is_inferior_var(), pu_variable_name(), sc_intersection(), sc_new(), sink_stmt, source_stmt, static_control_to_indices(), StmtToProto, SUCCESSOR, successor_arc_label, successor_vertex, the_dfg, trans_l, vecteur_to_polynome(), VERTEX, VERTEX_DOMAIN, vertex_int_stmt(), vertex_successors, and vvs_on_polynome().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

plc_make_min_dim()

int plc_make_min_dim

(

)

========================================================================

For each node of the data flow graph we compute its dimension.

We compute the dimension of the current node

We get the dimension of the timing and placement function of the current node

Definition at line 313 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), CAR, CDR, gen_length(), get_stco_from_current_map(), graph_vertices, hash_get(), hash_pointer, hash_table_make(), int, nb_nodes, NIL, static_control_to_indices(), StmtToBdim, StmtToMu, StmtToPdim, the_bdt, the_dfg, VERTEX, and vertex_int_stmt().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

plc_make_proto()

list plc_make_proto

(

)

========================================================================

the DFG

Mapping from a statement to its prototype

Mapping from a statement to its lambda coeff

We create the hash table that will contain the prototype

We initialize the counter of coefficients in order to have all unknowns represented by different entities.

For each node of the data flow graph we compute a prototype.

We get the "static_control" associated to the statement.

We get the list of indices of the englobing loops and structure parameters.

First, we initialize the polynome in building the constant term.

Then, for each index (ind) we build the monome ind*COEFF#, and add it to the polynome.

Then, for each parameter (par) we build the monome par*COEFF#, and add it to the polynome.

We put the new prototype on the hash table.

Definition at line 190 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), CAR, CDR, CONS, CONST_COEFF, dfg_vertex_label_statement, ENDP, ENTITY, gen_append(), gen_nconc(), get_stco_from_current_map(), graph_vertices, hash_int, hash_put(), hash_table_make(), INDEX_COEFF, make_coeff(), make_polynome(), nb_nodes, NIL, PARAM_COEFF, polynome_add(), polynome_mult(), POP, prgm_parameter_l, static_control_to_indices(), StmtToLamb, StmtToProto, the_dfg, VERTEX, and vertex_vertex_label.

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

pm_matrice_scalar_mult()

void pm_matrice_scalar_mult	(	int	scal,
		matrice	mat_M,
		int	m,
		int	n
	)

=========================================================================

Definition at line 1878 of file prgm_mapping.c.

{
  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);
    }
  }
}

References ACCESS.

Referenced by partial_broadcast_coefficients().

Here is the caller graph for this function:

prgm_mapping()

bool prgm_mapping

(

char*

module_name

)

=========================================================================

The placement function

The timing function

The number of nodes in the DFG

The number of dataflows in the DFG

Mapping from a dataflow to its distance

Mapping from a statement to its prototype

Perf.mesurement

List of the unknowns coefficients

Initialize debugging functions

We get the required data: module entity, code, static_control, dataflow graph, timing function.

The DFG

the BDT

First we count the number of nodes and dataflows

We look for the broadcasts

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.

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.

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.

The number of mapping dimensions can be computed as a minimum, see plc_make_min_dim()

Mapping dimension can be fixed with the environment variable MAPPING_DIMENSION

We initialize the prgm_mapping function.

Computation of the weight of each dataflow of the DFG.

We get all the dataflows of the graph

We sort the dataflows in decreasing weight order

EDGES TREATMENT

BROADCAST CONDITIONS

We take into account the broadcast conditions

OD : 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.

CUTTING CONDITIONS

We compute the list of equations that are to be nullified in order to zero out all the distances.

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.

UNELIMINATED COEFF SORTING

COEFF PARTITION

VALUATION

We valuate all the remaining unknowns by building successively each dimension.

Parameters

module_name

odule

Definition at line 2213 of file prgm_mapping.c.

{
  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);
}

References adg_pure_dfg(), bdt_undefined, broadcast(), broadcast_conditions(), CAR, CDR, compare_dfs_weight(), CONS, CONSP, count_mu_coeff, cutting_conditions(), DATAFLOW, db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug(), debug_off, debug_on, DtfToDist, DtfToSink, DtfToWgh, edge_weight(), ENDP, exp, EXPRESSION, expression_undefined, fprint_bdt(), fprint_dataflow(), fprint_dfg(), fprint_entity_list(), fprint_plc(), fprint_plc_pp_dims(), fprint_psysteme(), fprint_vvs(), fprintf(), gen_nconc(), gen_remove(), general_merge_sort(), get_debug_level(), get_graph_dataflows(), GET_STATEMENT_MAPPING, graph_vertices, hash_get(), int, int_to_expression(), local_name_to_top_level_entity(), make_placement(), make_plc(), malloc(), mod_stat, module_name(), nb_dfs, nb_nodes, NIL, partial_broadcast_coefficients(), partition_unknowns(), pfunc, pips_internal_error, PLACEMENT, placement_dims, plc_fprint_dfs(), plc_fprint_distance(), plc_fprint_proto(), plc_make_dim(), plc_make_distance(), plc_make_min_dim(), plc_make_proto(), plc_placements, polynome_dup(), polynome_fprint(), polynome_to_vecteur(), POP, prgm_parameter_l, pu_is_inferior_var(), pu_variable_name(), Pvecteur_to_expression(), reset_current_module_entity(), reset_current_stco_map(), set_current_module_entity(), set_current_stco_map(), solve_system_by_succ_elim(), sort_dfg_node(), sort_unknowns(), static_control_params, static_control_undefined, static_control_yes, StmtToProto, strdup(), STS, SUCC_DATAFLOWS, SUCCESSOR, the_bdt, the_dfg, user_warning, valuer(), VAR_VAL, var_val_variable, VERTEX, vertex_int_stmt(), vertex_successors, vvs_on_polynome(), and vvs_on_prototypes().

print_plc()

bool print_plc

(

char*

module_name

)

const

========================================================================

Definition at line 124 of file prgm_mapping.c.

{
  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);
}

References concatenate(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_FILE_RESOURCE, debug_off, debug_on, fprint_plc(), fprintf(), free(), get_debug_level(), module_name(), PLC_EXT, safe_fclose(), safe_fopen(), strdup(), and user_log().

Here is the call graph for this function:

prototype_dimension()

int prototype_dimension	(	Ppolynome	pp,
		list	ind_l
	)

========================================================================

We construct A.L, in which each line correspond to the factor of one index in "pp".

L is the list of variables contained in AL.

OLD VERSION

Definition at line 985 of file prgm_mapping.c.

{
  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);
}

References Ssysteme::base, base_dimension, CAR, contrainte_make(), dim_H(), Ssysteme::egalites, ENDP, ENTITY, fprint_entity_list(), fprint_psysteme(), fprintf(), get_debug_level(), matrice_fprint(), matrice_free, matrice_hermite(), matrice_new, Ssysteme::nb_eq, polynome_fprint(), POP, prototype_factorize(), pu_contraintes_to_matrices(), pu_is_inferior_var(), pu_variable_name(), pu_vect_fprint(), sc_add_egalite(), sc_creer_base(), and sc_new().

Referenced by is_not_trivial_p().

Here is the call graph for this function:

Here is the caller graph for this function:

solve_system_by_succ_elim()

bool solve_system_by_succ_elim	(	Psysteme	sys,
		list *	sigma
	)

========================================================================

We walk through all the equations of M_ps.

We apply on this expression the substitution "sigma"

We create the elementary substitution with a variable not yet eliminated.

esult = true;

We apply it on all prototypes, if none becomes trivial ...

esult = true;

Definition at line 1722 of file prgm_mapping.c.

{
  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);
}

References compose_vvs(), fprint_vvs(), fprintf(), get_debug_level(), is_not_trivial_p(), NIL, plc_make_vvs_with_vector(), pu_egalite_fprint(), pu_variable_name(), pu_vect_fprint(), Scontrainte::succ, Scontrainte::vecteur, and vvs_on_vecteur().

Referenced by broadcast_conditions(), and prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

sort_dfg_node()

list sort_dfg_node

(

list

l_nodes

)

========================================================================

For each node of the data flow graph we compute its dimension.

Definition at line 748 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), CAR, CDR, compare_nodes_dim(), gen_length(), general_merge_sort(), get_stco_from_current_map(), hash_int, hash_put(), hash_table_free(), hash_table_make(), nb_nodes, NIL, static_control_to_indices(), StmtToDim, VERTEX, and vertex_int_stmt().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

sort_unknowns()

void sort_unknowns	(	list *	lambda,
		int	dmax
	)

========================================================================

void sort_unknowns(list *lambda, int dmax) :

Definition at line 1441 of file prgm_mapping.c.

{
  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;
}

References CAR, CDR, compare_unks_frenq(), CONS, debug(), ENDP, ENT_HT_SIZE, ENTITY, entity_local_name(), free(), gen_nconc(), general_merge_sort(), graph_vertices, hash_get(), hash_pointer, hash_put(), hash_table_free(), hash_table_make(), is_index_coeff_p(), malloc(), NIL, pl, POP, prototype_factorize(), StmtToProto, the_dfg, UnkToFrenq, vect_size(), VERTEX, and vertex_int_stmt().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

system_inversion_restrict()

Psysteme system_inversion_restrict	(	Psysteme	sys,
		list	unks_l,
		list	var_l,
		list	par_l,
		int	nb_restrict,
		bool	is_first
	)

========================================================================

Definition at line 1663 of file prgm_mapping.c.

{
  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));
}

References A, ACCESS, B, completer_base(), contraintes_with_sym_cst_to_matrices(), Ssysteme::egalites, gen_length(), list_to_base(), matrice_free, matrice_general_inversion(), matrice_new, matrice_nulle(), matrice_transpose(), Ssysteme::nb_eq, pu_matrices_to_contraintes(), and sc_make().

Here is the call graph for this function:

valuer()

list valuer	(	int	dim,
		list	xunks,
		list	pcunks
	)

========================================================================

(void) polynome_free(sub_pp);

We sort the unknowns in order to have the auxiliary variables first

Definition at line 1189 of file prgm_mapping.c.

{
  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);
}

References adg_number_to_statement(), apply_farkas(), AUXIL_COEFF, Ssysteme::base, base_to_list(), CAR, CDR, compare_coeff(), compose_vvs(), CONS, CONSP, contrainte_dup(), contrainte_make(), Ssysteme::egalites, elim_var_with_eg(), ENDP, ENTITY, exp, EXPRESSION, expression_constant_p(), expression_normalized, expression_to_int(), find_or_create_coeff(), fprint_entity_list(), fprint_psysteme(), fprint_vvs(), fprintf(), gen_concatenate(), gen_nconc(), general_merge_sort(), get_debug_level(), get_stco_from_current_map(), graph_vertices, hash_get(), imprime_quast(), is_quast_value_conditional, is_quast_value_quast_leaf, list_to_base(), make_vvs(), make_vvs_from_sc(), Ssysteme::nb_eq, NIL, NO_OFL_CTRL, NORMALIZE_EXPRESSION, normalized_linear, nullify_factors(), offset, pip_integer_min(), polynome_dup(), polynome_fprint(), polynome_free(), POP, predicate_system, prgm_parameter_l, pu_is_inferior_var(), pu_variable_name(), quast_leaf_solution, quast_quast_value, quast_undefined, quast_value_quast_leaf, quast_value_tag, quast_value_undefined, sc_add_egalite(), sc_add_inegalite(), sc_creer_base(), sc_new(), sc_normalize(), static_control_to_indices(), StmtToProto, Scontrainte::succ, TCST, the_dfg, user_error, VAR_VAL, var_val_value, vect_cl2_ofl_ctrl(), vect_multiply(), vect_new(), vect_rm(), VERTEX, VERTEX_DOMAIN, vertex_int_stmt(), vvs_on_polynome(), vvs_on_systeme(), and vvs_on_vvs().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

vvs_on_prototypes()

void vvs_on_prototypes

(

list

sigma

)

=========================================================================

Definition at line 2175 of file prgm_mapping.c.

{
  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));
  }
}

References CAR, CDR, graph_vertices, hash_del(), hash_get(), hash_put(), NIL, StmtToProto, the_dfg, VERTEX, vertex_int_stmt(), and vvs_on_polynome().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

count_mu_coeff

int count_mu_coeff

Mapping from an entity to its frenq in the plc proto.

Definition at line 113 of file prgm_mapping.c.

Referenced by initialize_mu_list(), and prgm_mapping().

DtfToDist

hash_table DtfToDist

Mapping from a dataflow to its sink statement.

Definition at line 104 of file prgm_mapping.c.

Referenced by cutting_conditions(), plc_fprint_distance(), plc_make_distance(), and prgm_mapping().

DtfToSink

hash_table DtfToSink

The number of dataflows in the DFG.

Definition at line 103 of file prgm_mapping.c.

Referenced by broadcast_conditions(), cutting_conditions(), edge_weight(), and prgm_mapping().

DtfToWgh

hash_table DtfToWgh

Mapping from a dataflow to its distance.

Definition at line 105 of file prgm_mapping.c.

Referenced by compare_dfs_weight(), edge_weight(), plc_fprint_dfs(), and prgm_mapping().

nb_dfs

int nb_dfs

The number of nodes in the DFG.

Definition at line 102 of file prgm_mapping.c.

Referenced by edge_weight(), plc_make_distance(), and prgm_mapping().

nb_nodes

int nb_nodes

The timing function.

Definition at line 101 of file prgm_mapping.c.

Referenced by do_kernelize(), is_not_trivial_p(), plc_make_dim(), plc_make_min_dim(), plc_make_proto(), prgm_mapping(), reindexing(), and sort_dfg_node().

pfunc

plc pfunc

Internal variables

Global variables

Definition at line 98 of file prgm_mapping.c.

Referenced by mapping_on_broadcast(), partial_broadcast_coefficients(), and prgm_mapping().

prgm_parameter_l

list prgm_parameter_l

global variables

lint

Definition at line 115 of file prgm_mapping.c.

Referenced by apply_farkas(), broadcast_conditions(), broadcast_of_dataflow(), cutting_conditions(), mapping_on_broadcast(), partial_broadcast_coefficients(), plc_make_proto(), prgm_mapping(), and valuer().

StmtToBdim

hash_table StmtToBdim

Mapping from a statement to the dim of its plc func.

Definition at line 108 of file prgm_mapping.c.

Referenced by is_not_trivial_p(), plc_make_dim(), and plc_make_min_dim().

StmtToDim

hash_table StmtToDim

Mapping from a statement to the dim of its bdt.

Definition at line 109 of file prgm_mapping.c.

Referenced by compare_nodes_dim(), and sort_dfg_node().

StmtToLamb

hash_table StmtToLamb

Mapping from a stmt to its iteration space dim.

Definition at line 110 of file prgm_mapping.c.

Referenced by broadcast_conditions(), mapping_on_broadcast(), and plc_make_proto().

StmtToMu

hash_table StmtToMu

Mapping from a stmt to its lambda coeff.

Definition at line 111 of file prgm_mapping.c.

Referenced by initialize_mu_list(), mapping_on_broadcast(), partial_broadcast_coefficients(), plc_make_dim(), and plc_make_min_dim().

StmtToPdim

hash_table StmtToPdim

Mapping from a statement (int) to its prototype.

Definition at line 107 of file prgm_mapping.c.

Referenced by broadcast_conditions(), mapping_on_broadcast(), partial_broadcast_coefficients(), plc_make_dim(), and plc_make_min_dim().

StmtToProto

hash_table StmtToProto

Mapping from a dataflow to its weight.

Definition at line 106 of file prgm_mapping.c.

Referenced by is_not_trivial_p(), partial_broadcast_coefficients(), partition_unknowns(), plc_fprint_proto(), plc_make_distance(), plc_make_proto(), prgm_mapping(), sort_unknowns(), valuer(), and vvs_on_prototypes().

subs_l

list subs_l

Definition at line 114 of file prgm_mapping.c.

the_bdt

bdt the_bdt

The data flow graph.

Definition at line 100 of file prgm_mapping.c.

Referenced by plc_make_dim(), plc_make_min_dim(), prgm_mapping(), print_bdt(), re_do_it(), reindexing(), and stmt_bdt_directions().

the_dfg

graph the_dfg

The placement function.

Definition at line 99 of file prgm_mapping.c.

Referenced by edge_weight(), is_not_trivial_p(), partition_unknowns(), plc_make_dim(), plc_make_distance(), plc_make_min_dim(), plc_make_proto(), prgm_mapping(), print_array_dfg(), re_do_it(), reindexing(), sa_do_it(), single_assign(), sort_unknowns(), valuer(), and vvs_on_prototypes().

UnkToFrenq

hash_table UnkToFrenq

Mapping from a stmt to its mu coeff.

Definition at line 112 of file prgm_mapping.c.

Referenced by compare_unks_frenq(), and sort_unknowns().