broadcast.c File Reference

#include <stdlib.h>
#include <stdio.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 "ri-util.h"
#include "graph.h"
#include "dg.h"
#include "paf_ri.h"
#include "constants.h"
#include "misc.h"
#include "static_controlize.h"
#include "paf-util.h"
#include "array_dfg.h"
#include "prgm_mapping.h"

Include dependency graph for broadcast.c:

Go to the source code of this file.

Typedefs
typedef dfg_vertex_label	vertex_label
	Newgen includes More...
typedef dfg_arc_label	arc_label

Functions
void	broadcast (graph g)
	======================================================================== More...
entity	base_find_var_with_rank (Pbase b, int r)
	======================================================================== More...
void	broadcast_of_dataflow (dataflow df, int stmt, predicate exec_domain)
	======================================================================== More...
list	contraintes_to_list (Pcontrainte pc)
	======================================================================== More...
Pcontrainte	list_to_contraintes (list l_pc)
	======================================================================== More...
boolean	compare_eq_occ (chunk *eq1, chunk *eq2)
	======================================================================== More...
void	fprint_l_psysteme (FILE *fp, list l_ps)
	======================================================================== More...
void	count_eq_occ (list l_ps)
	======================================================================== More...
void	sort_eq_in_systems (list l_ps)
	======================================================================== More...
void	mapping_on_broadcast (int stmt, Psysteme K)
	======================================================================== More...
list	broadcast_conditions (list lambda, list df_l, list *sigma)
	======================================================================== More...
list	stmt_bdt_directions (int stmt, list ind_l, list par_l)
	========================================================================= More...

Variables
list	prgm_parameter_l
	global variables More...

Typedef Documentation

arc_label

typedef dfg_arc_label arc_label

Definition at line 71 of file broadcast.c.

vertex_label

typedef dfg_vertex_label vertex_label

Newgen includes

C3 includes
Local defines

Definition at line 70 of file broadcast.c.

Function Documentation

base_find_var_with_rank()

entity base_find_var_with_rank	(	Pbase	b,
		int	r
	)

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

Definition at line 122 of file broadcast.c.

{
  int             i;
  Pvecteur        v = (Pvecteur) b;
 
  if (r > base_dimension(b))
    pips_internal_error("rank %d too high", r);
 
  for (i = 1; i < r; v = v->succ, i++);
 
  return ((entity) v->var);
}

References base_dimension, pips_internal_error, Svecteur::succ, and Svecteur::var.

Referenced by broadcast_of_dataflow().

Here is the caller graph for this function:

broadcast()

void broadcast

(

graph

g

)

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

List of the nodes of the DFG

List of successors of one node

List of dataflows of one successor

Statement number associated with one successor

We look for broadcasts on all nodes

We look for broadcasts on all successors of one node

We look for broadcasts on all dataflows of one successor

Definition at line 87 of file broadcast.c.

{
  list            nodes_l,      /* List of the nodes of the DFG */
                  su_l,         /* List of successors of one node */
                  df_l;         /* List of dataflows of one successor */
  int             sink_stmt;    /* Statement number associated with one
                                 * successor */
 
  /* We look for broadcasts on all nodes */
  for (nodes_l = graph_vertices(g); nodes_l != NIL; nodes_l = CDR(nodes_l)) {
    su_l = vertex_successors(VERTEX(CAR(nodes_l)));
 
    /* We look for broadcasts on all successors of one node */
    for (; su_l != NIL; su_l = CDR(su_l)) {
      successor       su = SUCCESSOR(CAR(su_l));
      vertex          sv = successor_vertex(su);
 
      sink_stmt = vertex_int_stmt(sv);
      df_l = dfg_arc_label_dataflows((dfg_arc_label) successor_arc_label(su));
 
      /* We look for broadcasts on all dataflows of one successor */
      for (; df_l != NIL; df_l = CDR(df_l))
        broadcast_of_dataflow(DATAFLOW(CAR(df_l)), sink_stmt, VERTEX_DOMAIN(sv));
    }
  }
}

References broadcast_of_dataflow(), CAR, CDR, DATAFLOW, dfg_arc_label_dataflows, graph_vertices, NIL, sink_stmt, SUCCESSOR, successor_arc_label, successor_vertex, 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:

broadcast_conditions()

list broadcast_conditions	(	list	lambda,
		list	df_l,
		list *	sigma
	)

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

add 1, because of TCST

We remove broadcast vectors contained in the time space

No condition: broadcast on all the processors

No condition yet, we'll try to zero out its distance

R is a sub-matrix of inv_A containing the (n-k) last columns.

If one condition is not are satisfied, we try to cut this edge AND we try to ensure that a subspace of the distribution space will coincide with a subspace of the broadcast space.

Definition at line 728 of file broadcast.c.

{
  extern hash_table StmtToLamb, DtfToSink, StmtToPdim;
 
  list            l, rem_df_l = NIL, acc_df_l = NIL, l_M_local = NIL, ml, dl;
 
  for (l = df_l; !ENDP(l); POP(l)) {
    dataflow        df = DATAFLOW(CAR(l));
    communication   com = dataflow_communication(df);
    predicate       bp = predicate_undefined;
 
    if (get_debug_level() > 4) {
      fprintf(stderr, "[broadcast_conditions] \t\t\tDF: ");
      fprint_dataflow(stderr, 0, df);
      fprintf(stderr, "\n");
    }
    if (is_broadcast_p(df)) {
      bp = communication_broadcast(com);
    }
    if (get_debug_level() > 4) {
      fprintf(stderr, "[broadcast_conditions] \t\t\tComm pred: ");
      if (bp == predicate_undefined)
        fprintf(stderr, "predicate_undefined");
      else
        fprint_pred(stderr, bp);
      fprintf(stderr, "\n");
    }
    if (bp == predicate_undefined)
      rem_df_l = gen_nconc(rem_df_l, CONS(DATAFLOW, df, NIL));
    else {
      list            ind_l, par_l, proto_lambda, l_bdir, bl;
      Psysteme        ps_pdir = (Psysteme) predicate_system(bp), ps_bdir;
      Pcontrainte     pc, prec_pc, new_pc;
      int             stmt = (int) hash_get(DtfToSink, (char *) df),
      n, m1, m2, i,
                      j, k, p_dim;
      static_control  stct = get_stco_from_current_map(adg_number_to_statement(stmt));
      matrice         A, B, inv_A, R, Rt, Bz;
 
      k = ps_pdir->nb_eq;
      ind_l = static_control_to_indices(stct);
      par_l = gen_append(prgm_parameter_l, NIL);
      m1 = gen_length(ind_l);
      m2 = gen_length(par_l) + 1;       /* add 1, because of TCST */
 
      p_dim = (int) hash_get(StmtToPdim, (char *) stmt);
      l_bdir = stmt_bdt_directions(stmt, ind_l, par_l);
 
      /* We remove broadcast vectors contained in the time space */
      for (bl = l_bdir; !ENDP(bl); POP(bl)) {
        ps_bdir = (Psysteme) CHUNK(CAR(bl));
        if (ps_bdir->nb_eq > 0) {
          prec_pc = NULL;
          for (pc = ps_pdir->egalites; pc != NULL; pc = pc->succ) {
            Psysteme        ps_aux = sc_dup(ps_bdir);
            sc_add_egalite(ps_aux, contrainte_make(pc->vecteur));
 
            if (vecteurs_libres_p(ps_aux, list_to_base(ind_l),
                                  list_to_base(par_l))) {
              prec_pc = pc;
            } else {
              (ps_pdir->nb_eq)--;
              if (prec_pc == NULL) {
                ps_pdir->egalites = pc->succ;
              } else {
                prec_pc->succ = pc->succ;
              }
            }
          }
 
          if (get_debug_level() > 4) {
            fprintf(stderr, "[broadcast_conditions] \t\t\tk before elim bdt = %d\n", k);
          }
          k = ps_pdir->nb_eq;
        }
      }
 
      if (get_debug_level() > 4) {
        fprintf(stderr, "[broadcast_conditions] \t\t\tk = %d\n", k);
      }
      if (k == m1) {
        /* No condition: broadcast on all the processors */
      } else if (k == 0) {
        /* No condition yet, we'll try to zero out its distance */
        rem_df_l = gen_nconc(rem_df_l, CONS(DATAFLOW, df, NIL));
      } else {
        Psysteme        M_local, ps_eps;
 
        acc_df_l = gen_nconc(acc_df_l, CONS(DATAFLOW, df, NIL));
 
        ps_eps = completer_base(ps_pdir, ind_l, par_l);
 
        if (get_debug_level() > 4) {
          fprintf(stderr, "[broadcast_conditions] \t\t\tFull sys\n");
          fprint_psysteme(stderr, ps_eps);
          fprintf(stderr, "\n");
        }
        n = ps_eps->nb_eq;
        if (m1 != n)
          user_error("broadcast_conditions", "m1 should be equal to n\n");
 
        A = matrice_new(n, n);
        B = matrice_new(n, m2);
        contraintes_with_sym_cst_to_matrices(ps_eps->egalites,
                                             list_to_base(ind_l),
                                       list_to_base(par_l), A, B, n, n, m2);
 
        inv_A = matrice_new(n, n);
        matrice_general_inversion(A, inv_A, n);
 
        /* R is a sub-matrix of inv_A containing the (n-k) last columns. */
        R = matrice_new(n, n - k);
        for (i = 1; i <= n; i++)
          for (j = 1; j <= (n - k); j++)
            ACCESS(R, n, i, j) = ACCESS(inv_A, n, i, j + k);
        R[0] = 1;
 
        Rt = matrice_new((n - k), n);
        matrice_transpose(R, Rt, n, (n - k));
 
        proto_lambda = get_stmt_index_coeff(stmt, StmtToLamb);
 
        Bz = matrice_new((n - k), 1);
        matrice_nulle(Bz, (n - k), 1);
        pu_matrices_to_contraintes(&new_pc, list_to_base(proto_lambda),
                                   Rt, Bz, (n - k), n);
 
        matrice_free(A);
        matrice_free(B);
        matrice_free(inv_A);
        matrice_free(R);
        matrice_free(Rt);
        matrice_free(Bz);
 
        M_local = sc_make(new_pc, NULL);
 
        if (get_debug_level() > 4) {
          fprintf(stderr, "[broadcast_conditions] \t\t\tM_local:\n");
          fprint_psysteme(stderr, M_local);
          fprintf(stderr, "\n");
        }
        l_M_local = gen_nconc(l_M_local, CONS(CHUNK, (chunk *) M_local, NIL));
      }
    }
  }
  /*
   * We have a list of systems, each system is a list of equations. We sort
   * each list of equations so as to have first the equations that appear the
   * most often in all the systems.
   * 
   * Thus, these equations are treated first.
   */
  sort_eq_in_systems(l_M_local);
 
  for (dl = acc_df_l, ml = l_M_local; !ENDP(dl); POP(dl), POP(ml)) {
    dataflow        df = DATAFLOW(CAR(dl));
    Psysteme        M_local = (Psysteme) CHUNK(CAR(ml));
 
    if (get_debug_level() > 4) {
      fprintf(stderr, "[broadcast_conditions] \t\t\tSIGMA before:\n");
      fprint_vvs(stderr, *sigma);
      fprintf(stderr, "\n");
    }
    /* If one condition is not are satisfied, we try to cut this edge AND we
     * try to ensure that a subspace of the distribution space will coincide
     * with a subspace of the broadcast space.
     */
    if (!solve_system_by_succ_elim(M_local, sigma)) {
      int stmt = (int) hash_get(DtfToSink, (char *) df);
 
      rem_df_l = gen_nconc(rem_df_l, CONS(DATAFLOW, df, NIL));
      mapping_on_broadcast(stmt,
                           (Psysteme) predicate_system
                           (communication_broadcast
                            (dataflow_communication(df))));
    }
 
    if (get_debug_level() > 4) {
      fprintf(stderr, "[broadcast_conditions] \t\t\tSIGMA after:\n");
      fprint_vvs(stderr, *sigma);
      fprintf(stderr, "\n");
    }
  }
 
  return (rem_df_l);
}

References A, ACCESS, adg_number_to_statement(), B, CAR, CHUNK, communication_broadcast, completer_base(), CONS, contrainte_make(), contraintes_with_sym_cst_to_matrices(), DATAFLOW, dataflow_communication, DtfToSink, Ssysteme::egalites, ENDP, fprint_dataflow(), fprint_pred(), fprint_psysteme(), fprint_vvs(), fprintf(), gen_append(), gen_length(), gen_nconc(), get_debug_level(), get_stco_from_current_map(), get_stmt_index_coeff(), hash_get(), int, is_broadcast_p(), list_to_base(), mapping_on_broadcast(), matrice_free, matrice_general_inversion(), matrice_new, matrice_nulle(), matrice_transpose(), Ssysteme::nb_eq, NIL, POP, predicate_system, predicate_undefined, prgm_parameter_l, pu_matrices_to_contraintes(), sc_add_egalite(), sc_dup(), sc_make(), solve_system_by_succ_elim(), sort_eq_in_systems(), static_control_to_indices(), stmt_bdt_directions(), StmtToLamb, StmtToPdim, Scontrainte::succ, user_error, Scontrainte::vecteur, and vecteurs_libres_p().

Referenced by prgm_mapping().

Here is the call graph for this function:

Here is the caller graph for this function:

broadcast_of_dataflow()

void broadcast_of_dataflow	(	dataflow	df,
		int	stmt,
		predicate	exec_domain
	)

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

Matrix of transformation equations (n x m)

Left matrix for the hermite decomposition (n x n)

Right matrix for the hermite decomposition (m x m)

Matrix of Hermite (n x m)

Sub-matrix of Q: the m-r last columns

Number of transformation equations

Number of englobing loops

Rank of H

Equations of broadcast vectors

Governing predicate

Communication of the dataflow

Base of index of the englobing loops

Equations of transformations

Equations of broadcast vectors

List of the transformations

Transformation system of equations

Englobing loops indices (li) and structure parameters (lp)

Base of the index of the englobing loops

We compute the size the matrix A

Create the basis of the new sc

Definition at line 170 of file broadcast.c.

{
  matrice         A,            /* Matrix of transformation equations (n x m) */
                  B, P,         /* Left matrix for the hermite decomposition
                                 * (n x n) */
                  Q,            /* Right matrix for the hermite decomposition
                                 * (m x m) */
                  H,            /* Matrix of Hermite (n x m) */
                  Q_r;          /* Sub-matrix of Q: the m-r last columns */
  int             n,            /* Number of transformation equations */
                  m,            /* Number of englobing loops */
                  r,            /* Rank of H */
                  i, j;
  Value           det_p, det_q;
  predicate       new_pred,     /* Equations of broadcast vectors */
                  gov_pred;     /* Governing predicate */
  communication   comm;         /* Communication of the dataflow */
  Pbase           b_loop_ind;   /* Base of index of the englobing loops */
  Psysteme        sc_trans,     /* Equations of transformations */
                  diff_sc;      /* Equations of broadcast vectors */
  list            trans_l,      /* List of the transformations */
                  li, lp;
  static_control  stct;
 
  trans_l = dataflow_transformation(df);
  gov_pred = dataflow_governing_pred(df);
  comm = dataflow_communication(df);
  diff_sc = sc_new();
 
  /* Transformation system of equations */
  sc_trans = make_expression_equalities(trans_l);
 
  /* Englobing loops indices (li) and structure parameters (lp) */
  stct = get_stco_from_current_map(adg_number_to_statement(stmt));
  li = static_control_to_indices(stct);
  lp = gen_append(prgm_parameter_l, NIL);
 
  /* Base of the index of the englobing loops */
  b_loop_ind = list_to_base(li);
 
  /* We compute the size the matrix A */
  n = sc_trans->nb_eq;
  m = base_dimension(b_loop_ind);
 
  if (n == 0) {
    /*
     * The number of equations is zero (no equations for the transformation
     * means that the source instruction is not inside a loop body) then each
     * index of the base (indices of the loop nest containing the sink
     * instruction) loop is a broadcast vector.
     */
    for (j = 1; j <= m; j++) {
      entity          ent = base_find_var_with_rank(b_loop_ind, j);
      sc_add_egalite(diff_sc, contrainte_make(vect_new((char *) ent, 1)));
    }
  } else if (m == 0) {
    /*
     * There is no englobing index for the sink statement, this means that
     * this statement is not inside a loop body, so, it is not a broadcast.
     */
  } else {
    /*
     * n > 0: we compute the matrix H and the associated matrices P and Q.
     * The kernal of A is not of dim 0 only if its rank (r) is less than its
     * number of columns (m).
     */
    A = matrice_new(n, m);
    B = matrice_new(n, 1);
    pu_contraintes_to_matrices(sc_trans->egalites, b_loop_ind, A, B, n, m);
 
    P = matrice_new(n, n);
    Q = matrice_new(m, m);
    H = matrice_new(n, m);
    matrice_hermite(A, n, m, P, H, Q, &det_p, &det_q);
 
    r = matrice_hermite_rank(H, n, m);
    if (r > n)
      r = n;
    if (r > m)
      r = m;
 
    if (m - r > 0) {
      Q_r = matrice_new(m, m - r);
      for (i = 1; i <= m; i++)
        for (j = 1; j <= m - r; j++)
          ACCESS(Q_r, m, i, j) = ACCESS(Q, m, i, j + r);
      Q_r[0] = DENOMINATOR(Q);
 
      for (j = 1; j <= m - r; j++) {
        Pvecteur        vect = NULL;
        for (i = 1; i <= m; i++) {
          entity          ent = base_find_var_with_rank(b_loop_ind, i);
          vect = vect_add(vect_new((char *) ent, ACCESS(Q_r, m, i, j)), vect);
        }
        sc_add_egalite(diff_sc, contrainte_make(vect));
      }
    }
  }
 
  /*
   * We update the dataflow communication of "df" only if the systeme has at
   * least one equation, i.e. one broadcast vector.
   */
  if (diff_sc->nb_eq != 0) {
    Psysteme        sc_ed, sc_gp, df_domain, impl_sc;
    Pcontrainte     pd, pdprec;
 
    /*
     * We make sure that each broadcast vector is a real one, i.e. the set of
     * values it can take has strictly more than one value. For this, we get
     * the implicit equation of the dataflow domain, the execution domain of
     * the sink intersection the governing predicate.
     */
    if (exec_domain == predicate_undefined)
      sc_ed = sc_new();
    else
      sc_ed = (Psysteme) predicate_system(exec_domain);
    if (gov_pred == predicate_undefined)
      sc_gp = sc_new();
    else
      sc_gp = (Psysteme) predicate_system(gov_pred);
 
    df_domain = sc_new();
    df_domain = sc_intersection(df_domain, sc_ed, sc_gp);
 
    impl_sc = find_implicit_equation(df_domain);
 
    if (impl_sc != NULL) {
      for (pd = diff_sc->egalites, pdprec = NULL; pd != NULL; pd = pd->succ) {
        Psysteme        aux_ps = sc_dup(impl_sc);
 
        sc_add_egalite(aux_ps, contrainte_make(vect_dup(pd->vecteur)));
        aux_ps->base = NULL;
        sc_creer_base(aux_ps);
        aux_ps = sc_normalize(aux_ps);
 
        /*
         * We remove the current diffusion vector if it corresponds to one of
         * the implicit equations.
         */
        if ((aux_ps == NULL) || (aux_ps->nb_eq == impl_sc->nb_eq)) {
          diff_sc->nb_eq = diff_sc->nb_eq - 1;
          if (pdprec == NULL)
            diff_sc->egalites = pd->succ;
          else {
            pdprec->succ = pd->succ;
          }
        } else
          pdprec = pd;
      }
    }
    if (diff_sc->nb_eq != 0) {
 
      /* Create the basis of the new sc */
      sc_creer_base(diff_sc);
 
      new_pred = make_predicate((char *) diff_sc);
      if (comm == communication_undefined)
        comm = make_communication(new_pred, predicate_undefined,
                                  predicate_undefined);
      else
        communication_broadcast(comm) = new_pred;
 
      dataflow_communication(df) = comm;
    } else
      sc_rm(diff_sc);
  } else
    sc_rm(diff_sc);
}

References A, ACCESS, adg_number_to_statement(), B, Ssysteme::base, base_dimension, base_find_var_with_rank(), communication_broadcast, communication_undefined, contrainte_make(), dataflow_communication, dataflow_governing_pred, dataflow_transformation, DENOMINATOR, Ssysteme::egalites, find_implicit_equation(), gen_append(), get_stco_from_current_map(), gov_pred, list_to_base(), make_communication(), make_expression_equalities(), make_predicate(), matrice_hermite(), matrice_hermite_rank(), matrice_new, Ssysteme::nb_eq, NIL, predicate_system, predicate_undefined, prgm_parameter_l, pu_contraintes_to_matrices(), Q, sc_add_egalite(), sc_creer_base(), sc_dup(), sc_intersection(), sc_new(), sc_normalize(), sc_rm(), static_control_to_indices(), Scontrainte::succ, trans_l, vect_add(), vect_dup(), vect_new(), and Scontrainte::vecteur.

Referenced by broadcast().

Here is the call graph for this function:

Here is the caller graph for this function:

compare_eq_occ()

boolean compare_eq_occ	(	chunk *	eq1,
		chunk *	eq2
	)

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

Definition at line 394 of file broadcast.c.

{
  Pcontrainte     c1, c2;
  c1 = (Pcontrainte) eq1;
  c2 = (Pcontrainte) eq2;
 
  return (*(c1->eq_sat) >= *(c2->eq_sat));
}

References Scontrainte::eq_sat.

Referenced by sort_eq_in_systems().

Here is the caller graph for this function:

contraintes_to_list()

list contraintes_to_list

(

Pcontrainte

pc

)

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

Definition at line 346 of file broadcast.c.

{
  Pcontrainte     cpc, spc;
  list            l_pc = NIL;
 
  for (cpc = pc; cpc != NULL;) {
    spc = cpc;
    cpc = cpc->succ;
    spc->succ = NULL;
    l_pc = gen_nconc(l_pc, CONS(CHUNK, (chunk *) spc, NIL));
  }
  return (l_pc);
}

References CHUNK, CONS, gen_nconc(), NIL, and Scontrainte::succ.

Referenced by sort_eq_in_systems().

Here is the call graph for this function:

Here is the caller graph for this function:

count_eq_occ()

void count_eq_occ

(

list

l_ps

)

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

Initialization of eq_sat to 1, each equation appears at least once.

We count the occurence of each equation in all the others systems

Definition at line 431 of file broadcast.c.

{
  list            l, ll;
  int             c = 0, cc;
 
  /* Initialization of eq_sat to 1, each equation appears at least once. */
  for (l = l_ps; !ENDP(l); POP(l)) {
    Psysteme        ps = (Psysteme) CHUNK(CAR(l));
    Pcontrainte     pc = ps->egalites;
    for (; pc != NULL; pc = pc->succ) {
      pc->eq_sat = (int *) malloc(sizeof(int));
      *(pc->eq_sat) = 1;
    }
  }
 
  /* We count the occurence of each equation in all the others systems */
  for (l = l_ps; !ENDP(l); POP(l)) {
    Psysteme        ps = (Psysteme) CHUNK(CAR(l));
    Pcontrainte     pc = ps->egalites;
    c++;
    for (; pc != NULL; pc = pc->succ) {
      Pvecteur        pv = pc->vecteur;
      cc = 0;
      for (ll = l_ps; !ENDP(ll); POP(ll)) {
        cc++;
        if (cc > c) {
          Psysteme        pps = (Psysteme) CHUNK(CAR(ll));
          Pcontrainte     ppc = pps->egalites;
          for (; ppc != NULL; ppc = ppc->succ) {
            Pvecteur        ppv = ppc->vecteur;
            if ((vect_substract(pv, ppv) == VECTEUR_NUL) ||
                (vect_add(pv, ppv) == VECTEUR_NUL)) {
              (*(ppc->eq_sat))++;
              (*(pc->eq_sat))++;
            }
          }
        }
      }
    }
  }
}

References CAR, CHUNK, Ssysteme::egalites, ENDP, Scontrainte::eq_sat, malloc(), POP, Scontrainte::succ, vect_add(), vect_substract(), Scontrainte::vecteur, and VECTEUR_NUL.

Referenced by sort_eq_in_systems().

Here is the call graph for this function:

Here is the caller graph for this function:

fprint_l_psysteme()

void fprint_l_psysteme	(	FILE *	fp,
		list	l_ps
	)

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

Definition at line 407 of file broadcast.c.

{
  list            l;
  int             i = 1;
  for (l = l_ps; !ENDP(l); POP(l)) {
    fprintf(fp, "Syst %d:\n", i++);
    fprint_psysteme(fp, (Psysteme) CHUNK(CAR(l)));
  }
}

References CAR, CHUNK, ENDP, fprint_psysteme(), fprintf(), and POP.

Here is the call graph for this function:

list_to_contraintes()

Pcontrainte list_to_contraintes

(

list

l_pc

)

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

Definition at line 364 of file broadcast.c.

{
  Pcontrainte pc = CONTRAINTE_UNDEFINED, cpc = CONTRAINTE_UNDEFINED;
  list        l;
 
  for (l = l_pc; !ENDP(l); POP(l)) {
    Pcontrainte     spc = (Pcontrainte) CHUNK(CAR(l));
    if (CONTRAINTE_UNDEFINED_P(pc)) {
      pc = spc;
      cpc = pc;
    } else {
      cpc->succ = spc;
      cpc = spc;
    }
  }
  return (pc);
}

References CAR, CHUNK, CONTRAINTE_UNDEFINED, CONTRAINTE_UNDEFINED_P, ENDP, POP, and Scontrainte::succ.

Referenced by sort_eq_in_systems().

Here is the caller graph for this function:

mapping_on_broadcast()

void mapping_on_broadcast	(	int	stmt,
		Psysteme	K
	)

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

We get the placement function of statement "stmt".

Don't do anything if all the placement function dimensions' are already mapped.

First, it gets the dimensions already mapped, they constitutes a space A.

Second, it looks for the greatest subspace K' of K (the broadcast space) such as A and K' are disjoint.

Third, it maps some of the remaining dimensions of the placement function with some of the dimension of K'.

To each dimension of the placement function, we have associated a variable mu.

Definition at line 532 of file broadcast.c.

{
  extern plc pfunc;
  extern hash_table StmtToPdim, StmtToMu, StmtToLamb;
 
  list plcs, ind_l, mu_list, la_list;
  Psysteme A, Kp;
  placement stmt_plc = placement_undefined;
  static_control stct;
  Pbase ind_base;
  int p_dim;
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] BEGIN **********\n");
fprintf(stderr, "[mapping_on_broadcast] with stmt %d and K: \n", stmt);
fprint_psysteme(stderr, K);
}
 
  /* We get the placement function of statement "stmt". */
  for(plcs = plc_placements(pfunc); stmt_plc == placement_undefined; POP(plcs)) {
    placement crt_plc = PLACEMENT(CAR(plcs));
    if(stmt == placement_statement(crt_plc))
      stmt_plc = crt_plc;
  }
 
  /* Don't do anything if all the placement function dimensions' are already
   * mapped.
   */
  p_dim = (int) hash_get(StmtToPdim, (char *) stmt);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] dim(PLC) = %d, already mapped:\n", p_dim);
fprint_pla_pp_dims(stderr, stmt_plc);
}
 
  if(gen_length(placement_dims(stmt_plc)) == p_dim)
    return;
 
  stct = get_stco_from_current_map(adg_number_to_statement(stmt));
  ind_l = static_control_to_indices(stct);
  ind_base = list_to_base(ind_l);
 
  mu_list = (list) hash_get(StmtToMu, (char *) stmt);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Mu :");
fprint_entity_list(stderr, mu_list);
fprintf(stderr, "\n");
}
 
/* First, it gets the dimensions already mapped, they constitutes a space A. */
  A = broadcast_dimensions(stmt_plc, mu_list);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Space A:\n");
fprint_psysteme(stderr, A);
}
 
/* Second, it looks for the greatest subspace K' of K (the broadcast space)
 * such as A and K' are disjoint.
 */
{
  Pcontrainte K_dims;
  Psysteme Ps;
 
  if( (A != SC_EMPTY) && (A->nb_eq != 0) ) {
    Kp = sc_new();
 
    for(K_dims = K->egalites; K_dims != NULL; K_dims = K_dims->succ) {
      Ps = sc_dup(A);
 
      sc_add_egalite(Ps, contrainte_dup(K_dims));
 
      if(vecteurs_libres_p(Ps, ind_base, BASE_NULLE))
        sc_add_egalite(Kp, contrainte_dup(K_dims));
 
      sc_rm(Ps);
    }
  }
  else
    Kp = K;
}
 
  sc_rm(A);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Space K':\n");
fprint_psysteme(stderr, Kp);
}
 
/* Third, it maps some of the remaining dimensions of the placement function
 * with some of the dimension of K'.
 */
  if(Kp->nb_eq != 0) {
    list new_dims = NIL, mu_l, par_l;
    Pcontrainte Kp_dims;
    int count_dim, i;
 
 
    /* To each dimension of the placement function, we have associated a
     * variable mu.
     */
    mu_l = mu_list;
    la_list = (list) hash_get(StmtToLamb, (char *) stmt);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Mu :");
fprint_entity_list(stderr, mu_l);
fprintf(stderr, "\n");
fprintf(stderr, "[mapping_on_broadcast] Lambda :");
fprint_entity_list(stderr, la_list);
fprintf(stderr, "\n");
}
 
 
    Kp_dims = Kp->egalites;
    count_dim = gen_length(placement_dims(stmt_plc));
    for(i = 0; i<count_dim; i++) { POP(mu_l); }
    for(; (Kp_dims != NULL) && (count_dim < p_dim); Kp_dims = Kp_dims->succ) {
      Ppolynome new_pp;
      list lam_l = la_list;
 
      par_l = gen_append(prgm_parameter_l, NIL);
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Params :");
fprint_entity_list(stderr, par_l);
fprintf(stderr, "\n");
}
 
      new_pp = make_polynome(1.0, (Variable) ENTITY(CAR(lam_l)), (Value) 1);
 
      for(i = 0; i<=gen_length(ind_l); i++) { POP(lam_l); }
      for(; !ENDP(lam_l); POP(lam_l), POP(par_l)) {
        polynome_add(&new_pp,
                     polynome_mult(make_polynome(1.0,
                                                 (Variable) ENTITY(CAR(par_l)),
                                                 (Value) 1),
                                   make_polynome(1.0,
                                                 (Variable) ENTITY(CAR(lam_l)),
                                                 (Value) 1)));
      }
      polynome_add(&new_pp,
                   polynome_mult(make_polynome(1.0,
                                               (Variable) ENTITY(CAR(mu_l)),
                                               (Value) 1),
                                 vecteur_to_polynome(Kp_dims->vecteur)));
 
      new_dims = gen_nconc(new_dims, CONS(CHUNK, (chunk *) new_pp, NIL));
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] K' current dim : ");
pu_vect_fprint(stderr, Kp_dims->vecteur);
fprintf(stderr, "\n");
fprintf(stderr, "[mapping_on_broadcast] PLC added dim %d : ", count_dim);
polynome_fprint(stderr, new_pp, pu_variable_name, pu_is_inferior_var);
fprintf(stderr, "\n");
}
 
      POP(mu_l);
      count_dim++;
    }
 
    placement_dims(stmt_plc) = gen_nconc(placement_dims(stmt_plc), new_dims);
  }
 
if (get_debug_level() > 5) {
fprintf(stderr, "[mapping_on_broadcast] Dims now mapped:\n");
fprint_pla_pp_dims(stderr, stmt_plc);
 
fprintf(stderr, "[mapping_on_broadcast] END **********\n\n");
}
 
}

References A, adg_number_to_statement(), BASE_NULLE, broadcast_dimensions(), CAR, CHUNK, CONS, contrainte_dup(), Ssysteme::egalites, ENDP, ENTITY, fprint_entity_list(), fprint_pla_pp_dims(), fprint_psysteme(), fprintf(), gen_append(), gen_length(), gen_nconc(), get_debug_level(), get_stco_from_current_map(), hash_get(), int, list_to_base(), make_polynome(), Ssysteme::nb_eq, NIL, pfunc, PLACEMENT, placement_dims, placement_statement, placement_undefined, plc_placements, polynome_add(), polynome_fprint(), polynome_mult(), POP, prgm_parameter_l, pu_is_inferior_var(), pu_variable_name(), pu_vect_fprint(), sc_add_egalite(), sc_dup(), sc_new(), sc_rm(), static_control_to_indices(), StmtToLamb, StmtToMu, StmtToPdim, Scontrainte::succ, Scontrainte::vecteur, vecteur_to_polynome(), and vecteurs_libres_p().

Referenced by broadcast_conditions().

Here is the call graph for this function:

Here is the caller graph for this function:

sort_eq_in_systems()

void sort_eq_in_systems

(

list

l_ps

)

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

We count the occurence of each equation

We sort the list of equations of each systems using these numbers

Definition at line 490 of file broadcast.c.

{
  list            l, l_eq, sl_eq;
  Psysteme        crt_ps;
 
  if (gen_length(l_ps) <= 1)
    return;
 
  /* We count the occurence of each equation */
  count_eq_occ(l_ps);
 
  /* We sort the list of equations of each systems using these numbers */
  for (l = l_ps; !ENDP(l); POP(l)) {
    crt_ps = (Psysteme) CHUNK(CAR(l));
 
    /*
     * Our sorting function (general_merge_sort()) works upon NewGen
     * lists. So we have to transform our chained Pcontrainte(s) into a
     * list of Pcontrainte(s), each Pcontrainte having no successor. After
     * sorting, we transform it back into chained Pcontrainte(s).  */
    l_eq = contraintes_to_list(crt_ps->egalites);
    sl_eq = general_merge_sort(l_eq, compare_eq_occ);
    crt_ps->egalites = list_to_contraintes(sl_eq);
  }
}

References CAR, CHUNK, compare_eq_occ(), contraintes_to_list(), count_eq_occ(), Ssysteme::egalites, ENDP, gen_length(), general_merge_sort(), list_to_contraintes(), and POP.

Referenced by broadcast_conditions().

Here is the call graph for this function:

Here is the caller graph for this function:

stmt_bdt_directions()

list stmt_bdt_directions	(	int	stmt,
		list	ind_l,
		list	par_l
	)

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

Definition at line 919 of file broadcast.c.

{
  extern bdt      the_bdt;
  list            l_dirs = NIL;
 
  if (the_bdt != bdt_undefined) {
    list            bl;
    bool         sc_found = false;
    for (bl = bdt_schedules(the_bdt); (bl != NIL) && (!sc_found); bl = CDR(bl)) {
      schedule        sc = SCHEDULE(CAR(bl));
      if (schedule_statement(sc) == stmt) {
        list            dl;
        Psysteme        ps = sc_new();
        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) {
              Psysteme        aux_ps = sc_dup(ps);
              sc_add_egalite(aux_ps, contrainte_make(pv));
 
              if (vecteurs_libres_p(aux_ps, list_to_base(ind_l), list_to_base(par_l))) {
                ps = aux_ps;
              } else {
              }
            }
          }
        }
        sc_creer_base(ps);
        l_dirs = gen_nconc(l_dirs, CONS(CHUNK, (chunk *) ps, NIL));
      }
    }
  }
  return (l_dirs);
}

References bdt_schedules, bdt_undefined, CAR, CDR, CHUNK, CONS, contrainte_make(), ENDP, ENTITY, EXPRESSION, expression_constant_p(), expression_normalized, gen_nconc(), list_to_base(), NIL, NORMALIZE_EXPRESSION, normalized_linear, POP, sc_add_egalite(), sc_creer_base(), sc_dup(), sc_new(), SCHEDULE, schedule_dims, schedule_statement, the_bdt, vect_coeff(), and vecteurs_libres_p().

Referenced by broadcast_conditions().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

prgm_parameter_l

list prgm_parameter_l

extern

global variables

Definition at line 115 of file prgm_mapping.c.

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