PIPS
|
#include <stdio.h>
#include <stdlib.h>
#include <string.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 "matrice.h"
#include "union.h"
#include "matrix.h"
#include "sparse_sc.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 "conversion.h"
#include "scheduling.h"
#include "reindexing.h"
Go to the source code of this file.
Data Structures | |
struct | scell |
type cell that contains all information for the reindexation of More... | |
struct | mytest |
type of a test, the same as the "normal" test except that the More... | |
struct | newinst |
type of new instruction which contains information about the loop More... | |
Macros | |
#define | STRING_BDT "t" |
Name : cell.c Package : reindexing Author : Alexis Platonoff & Antoine Cloue Date : april 1995 Historic : More... | |
#define | STRING_PLC "p" |
#define | STRING_TAU "q" |
#define | STRING_FLAG "flag" |
#define | MAKE_STATEMENT(ins) |
#define | INTEGER_DEC 0 |
We define a set of constant in order to a more generic function for the insert of the declarations of the new created variables. More... | |
#define | REAL_DEC 1 |
#define | COMPLEX_DEC 2 |
#define | LOGICAL_DEC 3 |
#define | DOUBLE_DEC 4 |
#define | CHARACTER_DEC 5 |
#define | INTEGER_DECL " INTEGER" |
#define | REAL_DECL " REAL" |
#define | COMPLEX_DECL " COMPLEX" |
#define | LOGICAL_DECL " LOGICAL" |
#define | DOUBLE_DECL " DOUBLE" |
#define | CHARACTER_DECL " CHARACTER" |
#define | COLON ":" |
#define | NEWLINE "\n *" |
#define | ENDLINE "\n" |
#define | LINE_LENGHT 68 |
#define | MARGIN_LENGHT 7 |
#define | IS_MIN 0 |
#define | IS_MAX 1 |
#define | DOUBLE_PRECISION_SIZE 8 |
Typedefs | |
typedef dfg_vertex_label | vertex_label |
Internal variables More... | |
typedef dfg_arc_label | arc_label |
typedef struct scell | scell |
type cell that contains all information for the reindexation of More... | |
typedef struct scell * | Pscell |
typedef struct mytest | mytest |
type of a test, the same as the "normal" test except that the More... | |
typedef struct mytest * | Pmytest |
typedef struct newinst | newinst |
type of new instruction which contains information about the loop More... | |
typedef struct newinst * | Pnewinst |
Functions | |
static Pbase | include_time_in_base (Pscell pc, entity e) |
===================================================================== More... | |
static Pmytest | create_mytest (Psysteme ps, instruction ins1, instruction ins2) |
======================================================================= More... | |
static Pmytest | add_elt_to_test_list (Pmytest te, Pmytest lte) |
===================================================================== More... | |
static void | fprint_mytest (FILE *fp, Pmytest t) |
======================================================================= More... | |
static Pmytest | add_ltest_to_ltest (Pmytest l1, Pmytest l2) |
======================================================================= More... | |
static void | calculate_delay (expression exp, Pscell pcs, Pscell pcd, entity tau) |
======================================================================== More... | |
static void | prepare_array_bounds (Pscell pc) |
=================================================================== More... | |
void | make_array_bounds (vertex cv) |
=================================================================== More... | |
static Psysteme | include_trans_on_LC_in_sc (Psysteme ps, Pscell pc) |
======================================================================= More... | |
static reference | include_trans_on_LC_in_ref (reference re, Pscell pc) |
======================================================================= More... | |
static Psysteme | include_trans_on_LC_in_sc2 (Psysteme ps, Pscell pc, Pbase b) |
======================================================================= More... | |
list | prepare_reindexing (vertex v, bdt b, plc p) |
======================================================================= More... | |
static bool | compatible_pc_p (Pscell pcd, Pscell pcs, int s, dataflow d) |
======================================================================== More... | |
static reference | make_reindex (dataflow crt_df, int crt_m, instruction assign_i, Pscell pc) |
======================================================================== More... | |
void | substitute_expressions (expression exp, list l_ind, list l_exp) |
===================================================================== More... | |
void | substitute_loop_indices (instruction ins, list l_ind, list l_exp) |
===================================================================== More... | |
static list | build_third_comb (reference old_ref, list cls, instruction assign_i, Pscell pc, Psysteme te, Psysteme sc, int *c, list *linit, list *lmax) |
===================================================================== More... | |
static Pmytest | build_third_subcomb (reference old_ref, list cls, instruction assign_i, Pscell pc, Psysteme sc) |
===================================================================== More... | |
static list | build_second_comb (Pscell pc, list clrhs, instruction assign_i, list cls, Psysteme sc, list *linit, list *lmax) |
===================================================================== More... | |
static list | build_first_comb (Pscell pc, instruction ci, list cls, int cn, list *linit, list *lmax) |
===================================================================== More... | |
statement | re_do_it (graph the_dfg, bdt the_bdt, plc the_plc) |
====================================================================== More... | |
#define INTEGER_DEC 0 |
#define MAKE_STATEMENT | ( | ins | ) |
#define STRING_BDT "t" |
typedef dfg_arc_label arc_label |
type of a test, the same as the "normal" test except that the
condition field is not an expression but a Psysteme.
type of new instruction which contains information about the loop
bounds we will construct around it - used in build_first_comb().
type cell that contains all information for the reindexation of
an instruction. Filled during function prepare_reindexing().
typedef dfg_vertex_label vertex_label |
=====================================================================
Pmytest add_elt_to_test_list(te, lte): add a Pmytest element at the end of a Pmytest list lte.
AC 94/06/08
Definition at line 247 of file cell.c.
References aux, and mytest::succ.
Referenced by build_third_subcomb().
=======================================================================
Pmytest add_ltest_to_ltest(l1, l2): add the Pmytest list l2 at the end of the Pmytest list l1.
AC 94/06/08
Definition at line 298 of file cell.c.
References mytest::succ.
Referenced by build_second_comb().
|
static |
=====================================================================
instruction build_first_comb(pc, ci, cls, cn, linit, lmax):
Parameters: pc: Pcurrent Pscell ci: current instruction cls: list of the predecessors of the instruction cn: number of the instruction linit: list of the initialization instructions lmax: list
Result:
AC 94/04/22
Change the lhs of ci to a new array indexed by the englobing loop indices: SAIn(i1,...ip), (i1,...,ip) are the new indices of the englobing loops of ci.
construct the list of rhs
the domain of the bdt is in multiple parts, we build a comb by calling recursively build_first_comb()
the domain of the bdt is in one part
case of no right hand side reference
build the "forall p" loop around the instruction
the instruction has a constant schedule, in the system of pc->t_bounds we have the value of the bdt
put the test on global time IF t == bdt_value
If it exists, initialize the minor time and put it in the initialization list of stat called linit.
Definition at line 2882 of file cell.c.
References ADD_ELEMENT_TO_LIST, ADD_LIST_TO_LIST(), base_to_list(), build_global_time_test_with_exp(), build_second_comb(), CAR, CDR, CONS, copy_instruction(), delay_table, scell::edge_dom, ENTITY, entity_empty_label(), exp, EXPRESSION, fprint_entity_list(), fprint_list_of_exp(), fprintf(), gen_copy_seq(), gen_length(), gen_nconc(), gen_nreverse(), get_debug_level(), get_rhs_of_instruction(), get_time_ent(), hash_del(), hash_put(), INFINITY, newinst::ins, INSTRUCTION, int_to_expression(), is_execution_parallel, is_instruction_loop, is_instruction_test, IS_LOOP_BOUNDS, scell::lp, scell::ltau, make_bounds(), make_empty_statement, make_execution(), make_init_time(), make_instruction(), make_loop(), MAKE_STATEMENT, make_test(), my_lhs_subs_in_ins(), NIL, scell::Nindices, scell::p_topology, predicate_to_system(), Ssyslist::psys, Pvecteur_to_expression(), remove_minmax(), sa_print_ins(), SAI, sc_dup(), STATEMENT, STRING_BDT, STRING_TAU, Ssyslist::succ, scell::succ, scell::t_bounds, UU, and VECTEUR_NUL_P.
Referenced by re_do_it().
|
static |
=====================================================================
list build_second_comb(pc, clrhs, assign_i, cls, sc, linit, lmax): we treat here each reference of the right hand side of the instruction (rhs) and we distinguish two type of reference, the last one and the others. We first treat "the others" where we apply build_third_subcomb(), and then we apply on the last one build_third_comb().
Parameters: pc: current Pscell clrhs: current list of rhs assign_i: current instruction cls: current list of predecessors sc: current bdt domain linit: list of initialization instructions lmax:
Result:
AC 94/04/28
the case clrhs = NIL should have treated in build_first_comb()
First we treat the case where we have several reference: we build a list of "mytest" containing the copy of the instruction where the current refernce has been replaced by its value and reindexed by the function build_third_subcomb().
Now we are in the case where clrhs->cdr == NIL. We call here the function build_third_comb(). What we build here is not a list of mytest but a list of instruction.
Definition at line 2792 of file cell.c.
References ADD_LIST_TO_LIST(), add_ltest_to_ltest(), build_third_comb(), build_third_subcomb(), CAR, cons::cdr, count, fprintf(), get_debug_level(), newinst::ins, NIL, REFERENCE, remove_minmax(), and mytest::succ.
Referenced by build_first_comb().
|
static |
=====================================================================
list build_third_comb(old_ref, cls, assign_i, pc, te, sc, c, linit, lmax): make the reindexation on a reference which we know it is the last one of the instruction, so we make the reindexation on the current reference, then encapsulate the new instruction in its test C(t,p).
Parameters: old_ref: current reference cls: current list of predecessors assign_i: current instruction pc: current Pscell te: sc: current domain c: counter of the local time variables linit: lmax:
Result:
AC 94/05/15
special treatment for the old loop counters appearing as scalar variable in the instruction
get the list of dataflows
special case where we replace just the old variables by the
new ones without changing the name of the reference
Duplication because "te" is reused when there are two or more dataflows, i.e. "ldf" has two or more elements.
modify te to take t_local into account
include the information on the test
recalculate the bounds for each variable of nbase
pps2 = new_loop_bound(pps, nbase);
deux derniers parametres a revoir
build the "forall p" loop around the instruction
the list is in the wrong order: reorder it
Bounds of the local time
get a possible max for global time
We substitute the time variable by its constante value
build the loop on p's, around our ins
The substitution
encapsulate everything in a block
Add the condition introduces by algorithm_row_echelon()
Put the test on global time around it
Duplication because "te" is reused when there are two or more dataflows, i.e. "ldf" has two or more elements.
Says if the schedule is constant or not.
The local time of the scell is split into as many local time as there are dataflows. Each has its own bounds, which are computed below. However, there relation with the minor time remains the same, i.e.: t = omega*tau + l, where "l" is the lower bound calculated before (cf. prepare_reindexing) and saved into the field "t_bounds" of the scell.
take the new local time into account in the base
modify te to take t_local into account
take the test into account
we put around the ins the test C(t, p)
We need some consistency
modify te to take t_local into account
include the information on the test
recalculate the bounds for each variable of nbase
pps2 = new_loop_bound(pps, nbase);
deux derniers parametres a revoir
build the "forall p" loop around the instruction
the list is in the wrong order: reorder it
extract the list concerning the p's and reorder it
Bounds of the local time
in lb we 've got the list of the lower bound of local time (of the current dataflow). we are in the case of an instruction dependant of the time
get a possible max for global time
initialize the local time, put the test introduces by algorithm_row_echelon and put it in the initialization list of stat called linit.
HERE WE HAVE TO SUBSTITUTE minor time (tau) TO local time (var) IN THE Ps LOOP BOUNDS : var = omega*tau + l. "l" is the lower bound of the local time of the current scell, NOT the lower bound of the local time of the current dataflow (cf. above).
We substitute the time variable by its constante value
build the loop on p's
The substitution
increment the local time of omega
build test on local time: if t>ub then t=-1
build the test on global time: IF t == t_local
build the test on global time IF t == cst
encapsulate everything in a block
Put the test on global time around it
We can reuse the local time variable
We can reuse the local time variable
end of while
Definition at line 2065 of file cell.c.
References ADD_ELEMENT_TO_LIST, algorithm_row_echelon(), Ssysteme::base, base_dimension, BASE_NODE_NUMBER, base_to_list(), build_global_time_test_with_exp(), build_local_time_test(), CAR, CDR, scell::con_base, CONS, copy_instruction(), copy_reference(), DATAFLOW, dataflow_governing_pred, dataflows_on_reference(), DIVIDE_OPERATOR_NAME, scell::domain, Ssysteme::egalites, ENTITY, entity_empty_label(), entity_local_name(), entity_undefined, ENTRY_ORDER, exp, EXPRESSION, expression_normalized, expression_to_string(), fprint_dataflow(), fprint_entity_list(), fprint_psysteme(), fprintf(), gen_copy_seq(), gen_length(), gen_nconc(), gen_nreverse(), generate_optional_if(), get_bounds_expression(), get_debug_level(), get_time_ent(), include_time_in_base(), include_trans_on_LC_in_ref(), include_trans_on_LC_in_sc2(), newinst::ins, INSTRUCTION, INT, int_to_expression(), is_execution_parallel, is_instruction_loop, is_instruction_test, IS_LOOP_BOUNDS, newinst::lb, scell::lomega, scell::lp, scell::lt, scell::ltau, make_bounds(), make_empty_statement, make_entity_expression(), make_execution(), make_increment_instruction(), make_init_time(), make_instruction(), make_instruction_block(), make_loop(), make_op_exp(), make_reindex(), MAKE_STATEMENT, make_test(), make_vecteur_expression(), my_matrices_to_constraints_with_sym_cst(), nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, scell::Nbounds, NIL, scell::Nindices, NO_OFL_CTRL, NORMALIZE_EXPRESSION, normalized_linear, predicate_to_system(), Ssyslist::psys, Psysteme_to_expression(), pu_vect_fprint(), Pvecteur_to_expression(), remove_minmax(), rhs_subs_in_ins(), scell::Rmat_inv, sa_print_ins(), sc_append(), sc_chg_var(), sc_consistent_p(), sc_creer_base(), sc_dup(), sc_empty_p(), sc_make(), sc_normalize(), sc_rational_feasibility_ofl_ctrl(), sc_rn(), sc_rn_p(), sc_transform_eg_in_ineg(), separate_variables(), sl_new(), scell::Smat_inv, st_make_nice_test(), STATEMENT, scell::statement, STRING_BDT, substitute_loop_indices(), substitute_var_with_vec(), Scontrainte::succ, Ssyslist::succ, scell::t_bounds, scell::Tbase_out, newinst::ub, UU, value_abs, value_gt, value_lt, VALUE_MONE, VALUE_ONE, value_posz_p, VALUE_TO_INT, scell::var_base, vect_add(), vect_coeff(), vect_dup(), vect_erase_var(), vect_multiply(), vect_new(), vect_normalize(), and Scontrainte::vecteur.
Referenced by build_second_comb().
|
static |
=====================================================================
Pmytest build_third_subcomb(old_ref, cls, assign_i, pc, sc): make reindexation on a reference we know it is not the last one, which means that we can't build the new complete instruction. We work on the copy of the instruction, and we return a list of "mytest", the test is the possible new test introduced by the dataflows, and the reindexed instruction is in the field "true".
Parameters: old_ref: current reference cls: current list of predecessors assign_i: current instruction pc: current Pscell sc: current domain
Result:
AC 94/05/15
get the list of dataflows
special case where we replace juste the old variables by the
new ones without changing the name of the reference
make the reindexation really if the source ("m") is not the original sin, oopps!, node.
include the right conditions on the instruction we build
we put around the ins the test C(t, p)
put the new element in the list we return
Definition at line 2690 of file cell.c.
References add_elt_to_test_list(), CAR, CDR, copy_instruction(), copy_reference(), create_mytest(), DATAFLOW, dataflow_governing_pred, dataflows_on_reference(), scell::domain, ENTRY_ORDER, fprint_mytest(), fprintf(), gen_length(), get_debug_level(), include_trans_on_LC_in_ref(), include_trans_on_LC_in_sc(), newinst::ins, instruction_undefined, INT, make_reindex(), NIL, predicate_to_system(), rhs_subs_in_ins(), sc_append(), and sc_dup().
Referenced by build_second_comb().
|
static |
========================================================================
void calculate_delay(exp, pcs, pcd)
Calculates the delay if possible for the instruction of Pscell pcs that is the instruction source.
AC 94/06/29
A cst Schedule for the source
A cst schedule for the destination
Diff period for source and dest
first see if the expression has the
proper form that is : tau - d
vect2 is equal to +d in the formula
the delay is calculated by the formula:
delay = abs((lbd-lbs)/omega + d )
Definition at line 328 of file cell.c.
References CAR, CONS, CONTRAINTE_UNDEFINED_P, cst_vector_p(), delay_table, Ssysteme::egalites, entity_undefined, exp, EXPRESSION, expression_normalized, fprint_list_of_exp(), fprint_string_Value(), fprintf(), get_debug_level(), hash_del(), hash_get(), hash_put(), INFINITY, int, INT, int_to_value, is_vect_constant_p(), scell::lomega, NIL, scell::Nindices, NO_OFL_CTRL, normalized_linear, pu_variable_name(), pu_vect_fprint(), scell::statement, scell::t_bounds, TCST, value_abs, value_gt, value_mod, value_notone_p, VALUE_ONE, VALUE_TO_INT, value_uminus, VALUE_ZERO, value_zero_p, vect_chg_sgn(), vect_cl_ofl_ctrl(), vect_coeff(), vect_div(), vect_dup(), vect_new(), vect_pgcd_all(), vect_substract(), and Scontrainte::vecteur.
Referenced by make_reindex().
========================================================================
bool compatible_pc_p(pcd, pcs, s, d)
Tests if the domain on which we work, that is pcd->domain with the conditions on the edge is included in the domain of the selectionned scell pcs (we transform)
AC 94/04/07
Definition at line 1601 of file cell.c.
References dataflow_governing_pred, dataflow_transformation, dj_append_system(), DJ_UNDEFINED, scell::domain, fprint_dataflow(), fprint_list_of_exp(), fprint_psysteme(), fprintf(), get_debug_level(), include_trans_in_sc(), pa_faisabilite, pa_new, Spath::pcomp, predicate_to_system(), Spath::psys, sc_append(), sc_dup(), and scell::statement.
Referenced by make_reindex().
|
static |
=======================================================================
Pmytest create_mytest(ps, ins1, ins2): create a Pmytest.
AC 94/06/08
Definition at line 224 of file cell.c.
References mytest::false, malloc(), mytest::succ, mytest::test, and mytest::true.
Referenced by build_third_subcomb().
|
static |
=======================================================================
void fprint_mytest(fp, t): print a list of Pmytest.
AC 94/06/08
Definition at line 274 of file cell.c.
References fprint_psysteme(), fprintf(), sa_print_ins(), mytest::succ, mytest::test, and mytest::true.
Referenced by build_third_subcomb().
=====================================================================
Definition at line 199 of file cell.c.
References base_to_list(), CDR, CONS, ENTITY, gen_copy_seq(), list_to_base(), and NIL.
Referenced by build_third_comb().
=======================================================================
reference include_trans_on_LC_in_ref(re, pc): include in the reference "re" the new variables introduced by pc.
AC 94/05/10
Definition at line 829 of file cell.c.
References ADD_ELEMENT_TO_LIST, analyze_expression(), base_contains_variable_p(), base_to_list(), CAR, CDR, scell::con_base, CONS, Ssysteme::egalites, ENTITY, exp, EXPRESSION, expression_normalized, fprint_entity_list(), fprint_list_of_exp(), fprint_psysteme(), fprintf(), get_debug_level(), my_matrices_to_constraints_with_sym_cst(), NIL, scell::Nindices, NORMALIZE_EXPRESSION, normalized_linear, pips_internal_error, ppcm(), Pvecteur_to_expression(), reference_indices, reference_variable, scell::Rmat_inv, sc_make(), sc_normalize(), scell::Smat_inv, Scontrainte::succ, value_abs, value_div, value_mult, value_posz_p, scell::var_base, vect_add(), vect_coeff(), vect_dup(), vect_erase_var(), vect_multiply(), vect_normalize(), vect_substract(), Scontrainte::vecteur, and x.
Referenced by build_third_comb(), and build_third_subcomb().
=======================================================================
static Psysteme include_trans_on_LC_in_sc(ps, pc): transform the system ps with the new variable we can find in the scell pc.
AC 94/05/10
Definition at line 806 of file cell.c.
References base_to_list(), scell::Bmat_inv, change_base_in_sc(), scell::con_base, my_matrices_to_constraints_with_sym_cst(), sc_make(), scell::Tbase_out, scell::Tmat_inv, and scell::var_base.
Referenced by build_third_subcomb().
=======================================================================
static Psysteme include_trans_on_LC_in_sc2(ps, pc): transform the system ps with the new variable we can find in the scell pc.
AC 94/05/10
Definition at line 923 of file cell.c.
References base_to_list(), scell::Bmat_inv, change_base_in_sc(), scell::con_base, my_matrices_to_constraints_with_sym_cst(), sc_make(), scell::Tmat_inv, and scell::var_base.
Referenced by build_third_comb().
void make_array_bounds | ( | vertex | cv | ) |
===================================================================
void make_array_bounds(vertex cv):
Do the declaration of the array defined by the instruction corresponding to "cv". The bounds of this array are given by a hash table ("ht_ab"), see prepare_array_bounds().
The bounds of the first time dimension must be computed using the delay. If there is no delay (d < 0 or d = infinity), then these bounds are expressed from the minor time point of view, so the values given by the hash table must be translate from the local time to the minor time.
With the following notation: local lower bound = llb, local upper bound = lub, local period = lp, minor lower bound = mlb, minor upper bound = mub, minor period = mp
We have: mlb = 0 mub = (lub - llb)/lp mp = 1
AP 22/08/94
Find the array entity
Find the type of this array
No bounds => scalar variable.
Modifies the bounds of the time dimensions (see above).
Definition at line 699 of file cell.c.
References BASE_NODE_NUMBER, basic_float, basic_tag, CAR, CHARACTER_DEC, COMPLEX_DEC, concatenate(), delay_table, dfg_vertex_label_statement, DOUBLE_DEC, DOUBLE_PRECISION_SIZE, ENDP, entity_domain, entity_type, entity_undefined, ENTRY_ORDER, EXIT_ORDER, gen_find_tabulated(), get_current_module_entity(), h_node, hash_get(), ht_ab, INFINITY, int, INT, int_to_expression(), int_to_value, INTEGER_DEC, is_basic_complex, is_basic_float, is_basic_int, is_basic_logical, is_basic_string, is_normalized_linear, LOGICAL_DEC, scell::lomega, scell::ltau, make_rational_exp(), make_vecteur_expression(), malloc(), MODULE_SEP_STRING, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_tag, num, POP, RANGE, range_lower, range_upper, REAL_DEC, SA_MODULE_NAME, SAI, set_array_declaration(), strdup(), type_variable, user_error, value_abs, value_mod, value_zero_p, variable_basic, vect_div(), vect_pgcd_all(), vect_substract(), and vertex_vertex_label.
Referenced by re_do_it().
|
static |
========================================================================
reference make_reindex(crt_df, crt_m, assign_i, pc):
AC 94/04/22
first, find the good scell we should work on
gotcha the good scell, we build now the list of subscripts
that is gamma(rhs) = f(gamma(lhs))
first we transform the L application into matrices
(j) = (L)(i) <=> (j) = mL * (i) + mC * (n)
the formula we have to apply now is :
gamma_b = mB * (mL(mA(gamma_a)+mAC) + mC) + mBC
gamma_b = mB*mL*mA(gamma_a)+mB*mL*mAC+mB*mC+mBC
constant term
gotcha the good scell, we build now the list of subscripts
that is gamma(rhs) = f(gamma(lhs))
first we transform the L application into matrices
(j) = (L)(i) <=> (j) = mL * (i) + mC * (n)
the formula we have to apply now is :
gamma_b = mB * mC + mBC
constant term
calculate the delay if necessary
Definition at line 1671 of file cell.c.
References ADD_ELEMENT_TO_LIST, calculate_delay(), CAR, compatible_pc_p(), scell::con_base, CONS, constraints_with_sym_cst_to_matrices(), contrainte_make(), dataflow_reference, dataflow_transformation, Ssysteme::egalites, ENTITY, entity_undefined, exp, EXPRESSION, expression_normalized, expression_to_string(), expression_undefined_p, fprint_list_of_exp(), fprint_psysteme(), fprintf(), get_debug_level(), h_node, hash_get(), int_to_expression(), IS_NEW_ARRAY, is_normalized_linear, scell::ltau, make_normalized(), matrix_add(), matrix_fprint(), matrix_free, matrix_multiply(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_new(), matrix_normalize(), my_build_new_ref(), my_constraints_with_sym_cst_to_matrices(), my_matrices_to_constraints_with_sym_cst_2(), NIL, NORMALIZE_EXPRESSION, normalized_linear, POP, print_reference(), pu_variable_name(), pu_vect_fprint(), Pvecteur_to_expression(), scell::Rbase_out, scell::Rmat, scell::Rmat_inv, sc_add_egalite_at_end(), sc_new(), sc_rm(), scell::Smat, scell::Smat_inv, Scontrainte::succ, scell::succ, user_error, scell::var_base, vect_dup(), vect_size(), Scontrainte::vecteur, and vecteur_fprint().
Referenced by build_third_comb(), and build_third_subcomb().
|
static |
===================================================================
static void prepare_array_bounds(Pscell pc):
Compute for the instruction corresponding to the scell "pc" the size of all the dimensions of the array defined by this instruction.
These sizes are memorized in the hash table "ht_ab".
Parameters : pc: scell of the current instruction
Note: On the time dimensions, these sizes are not the true ones because they correspond to the local time bounds, not the minor time bounds. The computation of the minor bounds is done afterwards (see make_array_bounds())
AP 22/08/94
statement number ("ht_ab" key)
We get the current value of the bounds: should not exit yet
the P topology is a list of system giving the bounds of the
space loop counters ; the order is from the inner loop to the
outer loop. We reverse the order.
Idem for the T bounds
Two cases depending on whether there is a non null scheduling or not.
First the time bounds
Then the space bounds
Definition at line 503 of file cell.c.
References CAR, CDR, CONS, ENDP, ENTITY, expression_to_string(), fprintf(), gen_copy_seq(), gen_nconc(), get_debug_level(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ht_ab, ifdebug, int_to_expression(), IS_ARRAY_BOUNDS, IS_MAX, IS_MIN, scell::lp, scell::lt, make_bounds(), make_range(), merge_expressions(), Ssysteme::nb_ineq, NIL, scell::p_topology, POP, Ssyslist::psys, RANGE, range_lower, range_upper, sl_new(), scell::statement, Ssyslist::succ, scell::succ, scell::t_bounds, and user_error.
Referenced by prepare_reindexing().
=======================================================================
void prepare_reindexing(v, b, p)
It associates to the vertex v a structure scell. First it changes the base of the instruction from base (i,j,...) of loop counters to base (t, p,...) given by the time function and the placement function. All the results are put in matrix. Then we introduce a matrix called Q that mappes time x space coordinates to minor time x space coordinates using the time periodicty. Returns the list of global time variables created
AC 94/03/21
List of englobing loop counters
List of structure parameters.
Two cases : loops around, or not
first we extract the bdt corresponding to this node in the global
bdt b. idem for the plc.
we write the equations p = f(i,j,...) and put them in system ps_p. Note : we only keep those with loop indices.
we write the equations t = f(i,j,...) and put them in system ps_b we have a double loop on the schedule because of possible predicate and posible multi-dimensionnal expression. We attach a scell to each domain of the schedule.
we take care of a possible denominator. the denominator
of system ps_b has the value "den"
count the number of equalities (diff) we need to add to build an inversible system
Now we build the system on the system coming from the local
time by adding equalities coming from the placement system
who are independant with the first ones.
we first append to ps_b the vectors coming from ps_p who
are not linked with those of ps_b.
the new vector is acceptable, i.e. free
update the list of new considered entities
the vector is unacceptable, continue to search
we have to complete the system with others free vectors
Now build the matrix of base changement : t: new indices, i: old indices, n:structure parameters t = mT.i + mB.n i = mT_inv.t - (mT_inv*mB).n
calculate the inverse matrix of mT called mT_inv
we are sure that mT is reversible because it has
been built in a way where all vectors were free
we get the execution domain of the node and we will change
the old variables by the new ones (t,p...). First we find
the expression of the old variables in function of the new
ones and put the result in int_ps, then make the replacement
in old_ps. old_ps will be the "domain" of the scell.
we include the new parameters in the system of constraints
Now we have to build matrix mQ that maps normal to minor time x space coordinates, using the time period of each new variable given by omega and the its value at the origin
we separate the list of psystems in p from the one in t
this is a system in t
this is a system in p
for each system of ltime build a Pscell
tau: new indices with minor time tau = mQ.t + mC.n t = mQ_inv.tau - (mQ_inv*mC).n
case where the schedule is constant
should be matrix_undefined better than NULL
should be: Id
idem
should be: 0
we fill the scell at last !
Y a des matrices a effacer ICI !!
end of loop on schedule
No loop around the instruction
first we extract the bdt, which should be constant. The plc
is null.
The bdt is constant, but it can have different domains
we take care of a possible denominator.
Prepare the array bounds
Definition at line 952 of file cell.c.
References ADD_ELEMENT_TO_LIST, add_sc_to_sclist(), adg_number_to_statement(), algorithm_row_echelon(), analyze_expression(), Ssysteme::base, base_complete(), BASE_NODE_NUMBER, build_contraction_matrices(), build_list_of_min(), CAR, CDR, change_base_in_sc(), CONS, contrainte_make(), CONTRAINTE_UNDEFINED_P, create_new_entity(), dfg_vertex_label_exec_domain, dfg_vertex_label_statement, Ssysteme::egalites, ENDP, ENTITY, entity_local_name(), ENTRY_ORDER, exp, EXPRESSION, expression_normalized, extract_bdt(), extract_plc(), find_new_variables(), fprint_entity_list(), fprint_psysteme(), fprintf(), gen_copy_seq(), gen_length(), get_debug_level(), get_stco_from_current_map(), h_node, hash_put(), INT, is_normalized_linear, lexp, list_to_base(), lparams, make_predicate(), malloc(), matrix_add(), matrix_coef_mult(), MATRIX_DENOMINATOR, matrix_fprint(), matrix_free, matrix_general_inversion(), matrix_hermite(), matrix_multiply(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_new(), matrix_normalize(), my_constraints_with_sym_cst_to_matrices(), my_matrices_to_constraints_with_sym_cst(), nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_tag, pips_internal_error, placement_dims, POP, predicate_to_system(), prepare_array_bounds(), Ssyslist::psys, pu_vect_fprint(), sc_add_egalite(), sc_add_egalite_at_end(), sc_append(), sc_consistent_p(), sc_creer_base(), sc_dup(), sc_make(), sc_new(), sc_normalize(), sc_reverse_constraints(), sc_rn(), sc_transform_eg_in_ineg(), SCHEDULE, schedule_dims, schedule_predicate, separate_variables(), separate_variables_2(), sl_fprint(), static_control_to_indices(), STRING_BDT, STRING_PLC, Scontrainte::succ, Ssyslist::succ, newinst::succ, user_error, VALUE_MONE, value_notone_p, VALUE_ONE, vars_in_vect_p(), vect_multiply(), vect_new(), Scontrainte::vecteur, vecteurs_libres_p(), and vertex_vertex_label.
Referenced by re_do_it().
======================================================================
void re_do_it(graph the_dfg): function that redo the code by calling the different functions necessary to do the job.
AC 94/07/25
let's have a reverse DFG, i.e. the "successors" of an instruction i
are the instructions that may write the values used by i;
we prepare here the different elements of the reindexing. The default delay is -1.
Initialize the list of instructions of the body of the global time loop.
Initialize the list of instructions of initialization
now we make the reindexation in the code
loop on vertices
cls is the list of predecessors of cv
Do the reindexation
two cases here: either the list has one element and we do not have to introduce a flag but we have to increment the minor time (if it exists). Or, the list has more than one element and we have to introduce a flag and put the incrementation of the minor time in a test on the flag (if it exists). In both case, if there is no minor time then we do nothing.
This list is to be the new value of "lins".
introducing the flag
Each instruction is composed of tests perfectly nested with a non empty instruction in the true part.
create the statement: flag = true, and add it at the end of the block
Put this statement in "lstatg", the new value of "lins".
add the test on the flag
set the flag to false, i.e. reinitialization
initialize the flag to false in "linit"
increment the minor time
no flag to introduce
put all the pieces of lstatg in one statement
put the new statement in the list representing the program
end of loop on vertices
now, we have to take into account the value of the delay calculated,
i.e. we go through the code and replace each first time dimension of
each instruction by the same expression modulo the delay.
ICI il faudrait pouvoir construire les boucles sur les differentes
dimension du temps global et non 1 seule dimension !!
voir aussi le probleme des bornes de ces variables
Computation of the array bounds, one per instruction
Build the loop on the global time, the body is "sl"
We have to simplify the list of the possible upper bounds to put in our MAX expression. This is done by using the function simplify_minmax() with a context specifying that each structure parameter is positive. The list "lparams" is a global variables giving these parameters.
add the statement to all statements of initialization
"sl" becomes the lists of all the instructions of the parallel program.
Definition at line 3038 of file cell.c.
References add_delay_information(), ADD_ELEMENT_TO_LIST, adg_number_to_statement(), assignment_statement_p(), BASE_NODE_NUMBER, build_first_comb(), build_flag_assign(), build_flag_test(), CAR, CDR, contrainte_make(), create_new_entity(), delay_table, dfg_vertex_label_statement, ENDP, ENTITY, entity_empty_label(), entity_intrinsic(), ENTRY_ORDER, fprint_dfg(), fprintf(), gen_length(), get_debug_level(), get_time_ent(), graph_vertices, h_node, hash_get(), hash_put(), newinst::ins, INSTRUCTION, instruction_block, instruction_tag, instruction_test, int_to_expression(), is_execution_sequential, is_instruction_block, is_instruction_loop, is_instruction_test, IS_MAX, is_syntax_call, lparams, scell::ltau, make_array_bounds(), make_call(), make_execution(), make_expression(), make_increment_instruction(), make_instruction(), make_instruction_block(), make_loop(), make_range(), MAKE_STATEMENT, make_syntax(), my_dfg_reverse_graph(), NIL, normalized_undefined, POP, prepare_reindexing(), print_detailed_ins(), sa_print_ins(), sc_add_inegalite(), sc_creer_base(), sc_new(), simplify_minmax(), STATEMENT, statement_instruction, STRING_BDT, STRING_FLAG, test_true, the_bdt, the_dfg, user_error, UU, vect_new(), VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by reindexing().
void substitute_expressions | ( | expression | exp, |
list | l_ind, | ||
list | l_exp | ||
) |
=====================================================================
void substitute_expressions(expression exp, list l_ind, list l_exp)
Substitute in expression "exp" the loop indices contains in "l_ind" by the respective expressions contains in "l_exp". This substitution is done recursively
Parameters: exp: expression in which we do the substitution l_ind: list of the loop indices that have to be subtituted l_exp: list of the expressions used in the substitution
AP 95/09/20
Definition at line 1971 of file cell.c.
References call_arguments, CAR, CDR, ENDP, ENTITY, exp, EXPRESSION, expression_syntax, is_syntax_call, is_syntax_reference, NIL, pips_internal_error, POP, reference_indices, reference_variable, same_entity_p(), syntax_call, syntax_reference, and syntax_tag.
Referenced by substitute_loop_indices().
void substitute_loop_indices | ( | instruction | ins, |
list | l_ind, | ||
list | l_exp | ||
) |
=====================================================================
void substitute_loop_indices(instruction ins, list l_ind, list l_exp)
Substitute in instruction "ins" the loop indices contains in "l_ind" by the respective expressions contains in "l_exp".
Parameters: ins: instruction in which we do the substitution l_ind: list of the loop indices that have to be subtituted l_exp: list of the expressions used in the substitution
AP 95/09/20
There are two args: lhs = rhs, we want the references of the rhs
Definition at line 2019 of file cell.c.
References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, EXPRESSION, gen_length(), newinst::ins, instruction_call, instruction_tag, is_instruction_call, pips_internal_error, and substitute_expressions().
Referenced by build_third_comb().