PIPS
|
#include <stdio.h>
#include <setjmp.h>
#include <string.h>
#include <stdlib.h>
#include "genC.h"
#include "ri.h"
#include "constants.h"
#include "ri-util.h"
#include "misc.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 "sparse_sc.h"
#include "complexity_ri.h"
#include "database.h"
#include "dg.h"
#include "parser_private.h"
#include "property.h"
#include "reduction.h"
#include "tiling.h"
#include "text.h"
#include "text-util.h"
#include "graph.h"
#include "paf_ri.h"
#include "paf-util.h"
#include "pipsdbm.h"
#include "resources.h"
#include "array_dfg.h"
#include "pip.h"
#include "static_controlize.h"
#include "scheduling.h"
Go to the source code of this file.
Data Structures | |
struct | n_coef |
struct | bdt_node |
struct | sys_list |
Macros | |
#define | my_polynome_fprint(fp, p) polynome_fprint(fp,p,entity_local_name,default_is_inferior_var); |
Typedefs | |
typedef dfg_arc_label | arc_label |
C3 includes More... | |
typedef dfg_vertex_label | vertex_label |
typedef struct n_coef | n_coef |
typedef struct n_coef * | Pn_coef |
typedef struct bdt_node | bdt_node |
typedef struct bdt_node * | Pbdt_node |
typedef struct sys_list | sys_list |
typedef struct sys_list * | Psys_list |
Functions | |
entity | create_var_name (char *Type, int source, int dest, int count) |
===================================================================== More... | |
static Psys_list | add_elt_to_sys_list (Psys_list ls, int s, Psysteme ps) |
===================================================================== More... | |
static void | fprint_sys_list (FILE *fp, Psys_list ls) |
===================================================================== More... | |
static Pn_coef | make_n_coef (entity e, Pvecteur v) |
===================================================================== More... | |
static Pn_coef | add_n_coef_to_list (Pn_coef l1, Pn_coef l2) |
===================================================================== More... | |
static void | fprint_coef_list (FILE *fp, Pn_coef l) |
===================================================================== More... | |
static Pn_coef | add_lcoef_to_lcoef (Pn_coef l1, Pn_coef l2) |
================================================================= More... | |
list | extract_lambda_list (list l) |
================================================================= More... | |
list | reorder_base (list l, list lu) |
================================================================= More... | |
static Pn_coef | add_lambda_list (Pn_coef lunk, list lvar) |
================================================================= More... | |
list | make_x_list (int c) |
================================================================= More... | |
static Pn_coef | add_x_list (Pn_coef lunk, list lvar, entity *me) |
================================================================= More... | |
static list | extract_var_list (Pn_coef lc) |
================================================================= More... | |
static void | clean_list_of_unk (Pn_coef *l, Psysteme *sc) |
================================================================= More... | |
list | make_list_of_n (char *n, int c) |
================================================================= More... | |
bool | is_stat_in_pred_list (int stat, list pred_list) |
===================================================================== More... | |
Psysteme | include_parameters_in_sc (Psysteme sys, int source) |
===================================================================== More... | |
static void | create_farkas_poly (Psysteme Psys, char *Type, int source, int dest, Ppolynome *p, Pn_coef *l, int *c) |
===================================================================== More... | |
static void | make_proto (hash_table h, sccs rg) |
================================================================= More... | |
bdt | build_bdt_null (vertex v) |
================================================================= More... | |
bool | if_no_pred (scc s, bdt *b) |
================================================================= More... | |
Psysteme | erase_trivial_ineg (Psysteme p) |
================================================================= More... | |
Ppolynome | include_trans_in_poly (int s, Ppolynome p, list l, int *d) |
================================================================= More... | |
Psysteme | transform_in_ineq (Psysteme sc, list l) |
================================================================= More... | |
int | get_m_coef (expression *e, int *de) |
================================================================= More... | |
bool | coef_of_M_equal (expression *exp1, expression *exp2) |
====================================================================== More... | |
bool | list_of_exp_equals_1n_p (list l1, list l2, int n) |
====================================================================== More... | |
quast | compact_quast (quast q, int n) |
====================================================================== More... | |
list | get_list_of_all_param (int s, int t) |
================================================================= More... | |
bool | is_uniform_rec (list l, Ppolynome p) |
================================================================= More... | |
Psysteme | include_trans_in_sc (int s, Psysteme sys, list l) |
================================================================= More... | |
Ppolynome | make_polynome_Xe (int xc, entity *xe) |
================================================================= More... | |
list | add_others_variables (list lvar, list n_lvar) |
================================================================= More... | |
Psysteme | make_causal_internal (int stat_dest, Psysteme sys_dest, Ppolynome poly_dest, list ldata, int stat_pred, Psysteme sys_pred, Ppolynome poly_source, int *c, int xc, entity *xe, int den) |
================================================================= More... | |
Psysteme | make_causal_external (int stat_dest, Psysteme sys_dest, Ppolynome poly_dest, list ldata, int stat_pred, Psysteme sys_pred, Ppolynome poly_source, int *c, int den) |
================================================================= More... | |
list | make_sched_proto (matrice h, int lin, int col, list lu) |
================================================================= More... | |
Psysteme | system_new_var_subst (Psysteme sys, list l) |
================================================================= More... | |
Psysteme | add_constraint_on_x (Psysteme psys, list lx) |
================================================================= More... | |
static Psysteme | make_primal (Psysteme psys, list *lvar_u, list *lvp, list lxe) |
================================================================= More... | |
list | get_exp_schedule (expression e, entity me, int d) |
================================================================= More... | |
static Psysteme | get_unsatisfied_system (list lexp, Psys_list *lsys, list *lxe, Pn_coef *lunk, entity me, int de) |
================================================================= More... | |
static void | make_list_of_unk (Pn_coef *l, Psysteme *sc, entity *me, list lx) |
================================================================= More... | |
Psysteme | get_predicate_system_of_node (int st, scc s) |
================================================================= More... | |
Psyslist | add_sc_to_sclist (Psysteme sc, Psyslist lsys) |
================================================================= More... | |
Psysteme | simplify_predicate (Psysteme ps, Psysteme ps_eq, list l) |
================================================================= More... | |
list | simplify_dimension (list ld, Psysteme ps_eq, list l) |
================================================================= More... | |
bdt | simplify_bdt (bdt b, scc s) |
================================================================= More... | |
static Psysteme | make_dual (Psysteme psys, Psysteme *pcont, Pn_coef l, list *lvar_u, list lvp) |
================================================================= More... | |
static Pn_coef | extract_stat_lunk (int stat, Pn_coef lunk) |
================================================================= More... | |
bdt | include_results_in_bdt (bdt b, bdt baux, list lexp) |
================================================================= More... | |
bool | is_mu_stat_in_sc (int stat, Psysteme sc) |
================================================================= More... | |
static bdt | analyze_quast (quast q, int stat, Pn_coef lunk, Psys_list lsys, bdt b, list lxe, entity me) |
================================================================= More... | |
bdt | make_bdt_initial (int stat, scc s) |
================================================================= More... | |
bdt | write_resulting_bdt (scc s, int stat, bdt bs, bdt bg) |
================================================================= More... | |
static bdt | search_scc_bdt (scc s) |
================================================================= More... | |
bdt | search_graph_bdt (sccs rgraph) |
================================================================= More... | |
Variables | |
hash_table | h_node |
#define my_polynome_fprint | ( | fp, | |
p | |||
) | polynome_fprint(fp,p,entity_local_name,default_is_inferior_var); |
typedef dfg_arc_label arc_label |
typedef dfg_vertex_label vertex_label |
=================================================================
Psysteme add_constraint_on_x(psys, lx): in the Psysteme psys, we add the constraints on the introduced variables Xe: Xe <= 1.
AC 94/01/27
Definition at line 1691 of file makebdt.c.
References base_add_variable(), CAR, CDR, ENTITY, entity_local_name(), gen_nreverse(), make_polynome(), NIL, polynome_decr(), polynome_to_contrainte(), and sc_add_inegalite().
Referenced by get_unsatisfied_system(), and search_scc_bdt().
=====================================================================
Psys_list add_elt_to_sys_list(ls, s, ps): add a system in the list of Psysteme.
AC 94/01/27
Definition at line 136 of file makebdt.c.
References aux, malloc(), sys_list::next, and sc_dup().
Referenced by get_unsatisfied_system(), and search_scc_bdt().
=================================================================
Pn_coef add_lambda_list(lunk, lvar): lvar contains the lambda list that we transform in a list of Pn_coef that we append to lunk.
AC 93/11/15
Definition at line 337 of file makebdt.c.
References add_n_coef_to_list(), aux, CAR, CDR, ENTITY, make_n_coef(), NIL, and VECTEUR_NUL.
Referenced by make_list_of_unk().
=================================================================
Pn_coef add_lcoef_to_lcoef(l1, l2): appends the list of Pn_coef l2 to l1.
AC 93/11/16
Definition at line 258 of file makebdt.c.
References add_n_coef_to_list(), and n_coef::next.
Referenced by add_x_list(), make_causal_external(), make_causal_internal(), and search_scc_bdt().
=====================================================================
Pn_coef add_n_coef_to_list(l1,l2): add the n_coef l2 at the end of the list l1.
AC 93/11/15
Definition at line 213 of file makebdt.c.
References n_coef::next.
Referenced by add_lambda_list(), add_lcoef_to_lcoef(), add_x_list(), clean_list_of_unk(), create_farkas_poly(), extract_stat_lunk(), and make_list_of_unk().
=================================================================
list add_others_variables(lvar, n_lvar): check if the elements of n_lvar are in lvar, if not add them in lvar.
AC 94/02/10
Definition at line 1286 of file makebdt.c.
References CAR, CDR, CONS, ENTITY, gen_append(), is_entity_in_list_p(), and NIL.
Referenced by make_causal_external(), and make_causal_internal().
=================================================================
Psyslist add_sc_to_sclist(sc,lsys): add a system in the list of systems defined by Psyslist.
AC 93/12/23
Definition at line 1985 of file makebdt.c.
References malloc(), Ssyslist::psys, and Ssyslist::succ.
Referenced by build_list_of_min(), prepare_reindexing(), search_scc_bdt(), separate_variables(), and separate_variables_2().
=================================================================
Pn_coef add_x_list(lunk, lvar, me): create the list of Pn_coef for the X, the second member is the big parameter we will use for PIP.
AC 94/01/27
Definition at line 391 of file makebdt.c.
References add_lcoef_to_lcoef(), add_n_coef_to_list(), aux, CAR, CDR, create_named_entity(), ENTITY, make_n_coef(), NIL, and vect_new().
Referenced by make_list_of_unk().
|
static |
=================================================================
bdt analyze_quast(q,lu,nb): this function substitute the new parameters that can appear, go down to each branch of the quast and analyze if all edge have been satisfied, if not find recur- sively the dimension of the schedule.
AC 94/01/27
see if there are some new parameters to replace
replace the new parameters in the predicate system
we process the true edge
we process the false edge
all the edges are satisfied, we get the schedule
some edges have not been satisfied: we get the
dimension of the schedule already calculated
and search the others
Definition at line 2446 of file makebdt.c.
References Ssysteme::base, bdt_schedules, bdt_undefined, bdt_undefined_p, CAR, clean_list_of_unk(), compact_quast(), conditional_false_quast, conditional_predicate, conditional_true_quast, CONS, dj_system_complement(), ENTITY, exp, EXPRESSION, fprint_bdt(), fprint_entity_list(), fprint_list_of_exp(), fprint_psysteme(), fprint_sys_list(), fprintf(), gen_length(), gen_nconc(), get_debug_level(), get_exp_schedule(), get_m_coef(), get_unsatisfied_system(), imprime_quast(), include_results_in_bdt(), is_mu_stat_in_sc(), is_quast_value_conditional, is_quast_value_quast_leaf, list_to_base(), make_bdt(), make_dual(), make_predicate(), make_primal(), make_schedule(), NIL, NO_OFL_CTRL, pip_solve_min_with_big(), pips_internal_error, predicate_to_system(), predicate_undefined, Ssyslist::psys, pu_vect_fprint(), quast_leaf_solution, quast_newparms, quast_quast_value, quast_undefined_p, quast_value_conditional, quast_value_quast_leaf, quast_value_tag, sc_append(), sc_dup(), sc_rational_feasibility_ofl_ctrl(), sc_rm(), SCHEDULE, schedule_dims, schedule_predicate, sys_list::sys, system_new_var_subst(), true_copy_schedule(), VAR_VAL, var_val_value, and var_val_variable.
Referenced by search_scc_bdt().
=================================================================
build_bdt_null(v): update the hash table by making the schedule null
AC 93/10/29
Definition at line 733 of file makebdt.c.
References CONS, dfg_vertex_label_statement, exp, EXPRESSION, fprint_bdt(), get_debug_level(), h_node, hash_get(), int_to_expression(), lexp, make_bdt(), make_schedule(), NIL, node(), predicate_undefined, SCHEDULE, true_copy_bdt(), and vertex_vertex_label.
Referenced by if_no_pred().
=================================================================
void clean_list_of_unk(l, sc): update the list of unknown for the problem by erasing the unknown that have been already calculated.
AC 94/01/27
Definition at line 440 of file makebdt.c.
References add_n_coef_to_list(), base, base_to_list(), extract_var_list(), is_entity_in_list_p(), list_to_base(), n_coef::n_ent, and n_coef::next.
Referenced by analyze_quast().
bool coef_of_M_equal | ( | expression * | exp1, |
expression * | exp2 | ||
) |
======================================================================
bool coef_of_M_equal(exp1, exp2): tests if two expressions have the same coefficient of "M".
AC 94/02/08
Definition at line 1017 of file makebdt.c.
References get_m_coef().
Referenced by list_of_exp_equals_1n_p().
======================================================================
quast compact_quast(q, n): try to reduce a quast when it is a condi- tional quast by testing the possible equality between the false edge and the true edge, and if it exists, suppress one.
AC 94/01/03
may be possible source of bug here
Definition at line 1080 of file makebdt.c.
References conditional_false_quast, conditional_true_quast, free_quast(), list_of_exp_equals_1n_p(), quast_leaf_solution, quast_quast_value, quast_undefined, quast_undefined_p, quast_value_conditional, quast_value_quast_leaf, quast_value_quast_leaf_p, quast_value_undefined, and quast_value_undefined_p.
Referenced by analyze_quast(), and search_scc_bdt().
|
static |
=====================================================================
create_farkas_poly() : that function creates the farkas polynom of a node, from the execution domain "psys". The coefficients created have the form NAME_i_j_k with i the statement of the source node, j the statement of the destination node (=0 in the case of a MU polynom) and k the number of the coefficient. The name NAME is given by Type. The polynome created is put in "p", each coefficient created is put in the list of Pn_coef "l" with the vector he is the coef. of, (0 in case of a Lambda coef), and "c" is a counter of tthe created coefficient.
AC 93/10/28
creation of the constant term of the polynom
exploring the Psystem, i.e. each inegality of the execution
domain, and making each component
exploring the Psystem, i.e. each inegality of the execution
domain, and making each component
Definition at line 580 of file makebdt.c.
References add_n_coef_to_list(), count, create_var_name(), fprintf(), get_debug_level(), make_n_coef(), make_polynome(), my_polynome_fprint, polynome_add(), POLYNOME_UNDEFINED_P, sc_transform_eg_in_ineg(), Scontrainte::succ, TCST, vect_aux, vect_chg_sgn(), vect_dup(), vect_new(), Scontrainte::vecteur, and vecteur_mult().
Referenced by make_causal_external(), make_causal_internal(), and make_proto().
=====================================================================
entity create_var_name(type,source,dest,count) : create the variable to iut in the vector that we construct in "create_farkas_poly". Returns an entity for printing commmodities.
AC 93/11/28
Definition at line 113 of file makebdt.c.
References asprintf, count, create_named_entity(), and free().
Referenced by create_farkas_poly().
=================================================================
Psysteme erase_trivial_ineg(p): erase from the psysteme p all inequalities like -MU<=0.
AC 93/11/22
Definition at line 796 of file makebdt.c.
References Scontrainte::succ, Svecteur::succ, Svecteur::val, value_negz_p, vect_rm(), and Scontrainte::vecteur.
Referenced by search_scc_bdt().
=================================================================
list extract_lambda_list(l): from the list l, extract the sublist of entities whose name is beginning by "LAMBDA".
AC 93/11/15
Definition at line 281 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, CAR, CDR, ENTITY, entity_local_name(), and NIL.
Referenced by make_list_of_unk().
=================================================================
static Pn_coef extract_stat_lunk(stat, lunk): creates the good second member for the dual problem based on the general second member lunk. This function is used when we search the schedule of each node in a scc one after the other.
AC 94/01/10
Definition at line 2322 of file makebdt.c.
References add_n_coef_to_list(), asprintf, entity_local_name(), free(), make_n_coef(), n_coef::n_ent, n_coef::n_vect, n_coef::next, and VECTEUR_NUL.
Referenced by search_scc_bdt().
=================================================================
list extract_var_list(lc): extract from the list of Pn_coef lc the variables and put them in a list it returns.
AC 93/11/15
Definition at line 421 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, ENTITY, and NIL.
Referenced by clean_list_of_unk(), make_causal_external(), make_causal_internal(), and make_list_of_unk().
|
static |
=====================================================================
void fprint_coef_list(fp,l): print in the file fp the list of Pn_coef l.
AC 93/11/15
Definition at line 236 of file makebdt.c.
References entity_local_name(), fprintf(), n_coef::n_ent, n_coef::n_vect, n_coef::next, and pu_vect_fprint().
Referenced by search_scc_bdt().
|
static |
=====================================================================
void fprint_sys_list(fp,ls): print in the file fp the list of systems ls.
AC 94/01/27
Definition at line 171 of file makebdt.c.
References fprint_psysteme(), fprintf(), sys_list::next, and sys_list::sys.
Referenced by analyze_quast().
list get_exp_schedule | ( | expression | e, |
entity | me, | ||
int | d | ||
) |
=================================================================
list get_exp_schedule(e,me,d): extract form the expression exp given by the resulting quast of PIP the expression of the schedule we search: it takes the expression, put the coef of "M" to 0, and change the sign of the vector.
AC 94/01/27
Definition at line 1788 of file makebdt.c.
References call_arguments, call_function, CAR, CDR, CONS, exp, EXPRESSION, expression_normalized, expression_syntax, expression_undefined_p, is_syntax_call, lexp, make_call(), make_expression(), make_syntax(), make_vecteur_expression(), NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_undefined, syntax_call, unnormalize_expression(), vect_chg_coeff(), and vect_chg_sgn().
Referenced by analyze_quast().
=================================================================
list get_list_of_all_param(s, t): get the entire list of the parame- ters for a deisganted node.
AC 94/02/08
Definition at line 1168 of file makebdt.c.
References adg_number_to_statement(), CAR, CDR, CONS, ENTITY, gen_append(), get_stco_from_current_map(), is_entity_in_list_p(), NIL, static_control_params, and static_control_to_indices().
Referenced by make_causal_external(), and make_causal_internal().
int get_m_coef | ( | expression * | e, |
int * | de | ||
) |
=================================================================
int get_m_coef(e, de): get the coefficient of the variable "m" in the expression "e".
AC 94/01/20
Definition at line 954 of file makebdt.c.
References analyze_expression(), call_arguments, CAR, entity_local_name(), exp, EXPRESSION, expression_normalized, expression_syntax, if(), NORMALIZE_EXPRESSION, normalized_linear, Svecteur::succ, syntax_call, TCST, unnormalize_expression(), Svecteur::val, VALUE_TO_INT, Svecteur::var, and VECTEUR_NUL_P.
Referenced by analyze_quast(), coef_of_M_equal(), and get_unsatisfied_system().
=================================================================
Psysteme get_predicate_system_of_node(st,s): get the system of constraints of a node of statement "st" in a given scc.
AC 93/12/20
Definition at line 1950 of file makebdt.c.
References CAR, CDR, dfg_vertex_label_exec_domain, NIL, predicate_to_system(), scc_vertices, sys_list::sys, VERTEX, vertex_int_stmt(), and vertex_vertex_label.
Referenced by make_bdt_initial(), and simplify_bdt().
|
static |
=================================================================
Psysteme get_unsatisfied_system(): we check the coefficient of "m" in the solution of the dual variable of "xe", if it is nil we update the list of system that could be unsatis- fied, the list of Xe, and we build the new system for the primal problem. lsys is updated, lunk too. "me" contains the entity "M".
AC 94/01/20
this edge is unsatisfied
we have to add the constraints X<=1
Definition at line 1846 of file makebdt.c.
References add_constraint_on_x(), ADD_ELEMENT_TO_LIST, add_elt_to_sys_list(), CAR, CDR, ENTITY, exp, EXPRESSION, fprint_list_of_exp(), fprintf(), get_debug_level(), get_m_coef(), lexp, sys_list::next, NIL, sc_append(), sc_new(), and sys_list::sys.
Referenced by analyze_quast().
=================================================================
if_no_pred(s, b): that function tests if the scc studied has only 1 vertex and no predecessor. Returns true in this case. At the same time, this function updates the field schedule of the hash table with the proper schedule, that is time=0
AC 93/10/29
Definition at line 768 of file makebdt.c.
References build_bdt_null(), CAR, CDR, NIL, scc_vertices, VERTEX, and vertex_successors.
Referenced by search_graph_bdt().
=====================================================================
Psysteme include_parameters_in_sc(sys,source): include in the systeme "sys" the parameters that it does not contain at that moment, and put them under an inequality (for example: n>=0).
AC 94/01/05
Definition at line 533 of file makebdt.c.
References adg_number_to_statement(), Ssysteme::base, base_add_variable(), CAR, CDR, contrainte_make(), Ssysteme::dimension, ENTITY, get_stco_from_current_map(), NIL, sc_add_inegalite(), sc_new(), static_control_params, sys_list::sys, system_contains_var(), and vect_new().
Referenced by make_causal_external(), make_causal_internal(), and make_proto().
=================================================================
bdt include_results_in_bdt(b, baux, lexp): in case of a multi dimensionnal bdt, this function is used to append the dimension calculated at this step (lexp) with the dimensions calculated before (b) and the dimensions calculated after (baux);
AC 94/10/27
update the predicate
update the list of expressions
Definition at line 2360 of file makebdt.c.
References bdt_schedules, bdt_undefined_p, CAR, CDR, CONS, EXPRESSION, gen_nconc(), lexp, make_predicate(), NIL, predicate_to_system(), sc_append(), SCHEDULE, schedule_dims, schedule_predicate, and sys_list::sys.
Referenced by analyze_quast().
=================================================================
Ppolynome include_trans_in_poly((int)s,(Ppolynome)p,(list)l): list contains the list of expression defining the edge trans- formation we want to apply to the node of statement s. This function replaces the old variable values by their new values in the polynome p. This is done in 2 steps; first we replace each variable by a local one,and put this one in a list; then we replace the local variable by the expression of the transformation.
AC 93/11/03
we get the list of the englobing loop of the studied node
replace all variables by a local one
replace all local variables by the transformation
Definition at line 832 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, adg_number_to_statement(), analyze_expression(), CAR, CDR, count, create_named_entity(), ENTITY, exp, EXPRESSION, expression_to_polynome(), free(), gen_free_list(), get_stco_from_current_map(), lexp, malloc(), NIL, poly_chg_var(), polynome_contains_var(), prototype_var_subst(), and static_control_to_indices().
Referenced by include_trans_in_sc(), make_causal_external(), and make_causal_internal().
=================================================================
Psysteme include_trans_in_sc(s,sys,l): include in a system the indice transformation introduced by an edge.
AC 93/12/20
Definition at line 1227 of file makebdt.c.
References Ssysteme::base, BASE_UNDEFINED, include_trans_in_poly(), Ssysteme::inegalites, polynome_to_vecteur(), sc_creer_base(), Scontrainte::succ, sys_list::sys, vect_multiply(), Scontrainte::vecteur, and vecteur_to_polynome().
Referenced by compatible_pc_p(), and search_scc_bdt().
=================================================================
bool is_mu_stat_in_sc(stat, sc): check if the system "sc" contains some variable of type "MU_stat".
AC 94/01/27
Definition at line 2411 of file makebdt.c.
References asprintf, Ssysteme::base, base_to_list(), CAR, CDR, ENTITY, entity_local_name(), free(), and NIL.
Referenced by analyze_quast().
=================================================================
bool is_uniform_rec(l, p): test if a causality condition is linear, that is independent of the structure parameters and all the loop counters.
AC 93/11/22
Definition at line 1202 of file makebdt.c.
References CAR, CDR, ENTITY, NIL, and polynome_contains_var().
Referenced by make_causal_external(), and make_causal_internal().
======================================================================
bool list_of_exp_equals_1n_p(l1,l2,n): tests the equality of 2 lists of expressions on the first n terms.
AC 94/01/25
Definition at line 1037 of file makebdt.c.
References CAR, CDR, coef_of_M_equal(), exp_equals_p(), EXPRESSION, fprint_list_of_exp(), fprintf(), and get_debug_level().
Referenced by compact_quast().
=================================================================
bdt make_bdt_initial(stat, s): write the initial bdt with as a predicate, the definition domaine of the node.
94/01/27
Definition at line 2656 of file makebdt.c.
References CONS, get_predicate_system_of_node(), make_bdt(), make_predicate(), make_schedule(), NIL, sc_dup(), and SCHEDULE.
Referenced by search_scc_bdt().
Psysteme make_causal_external | ( | int | stat_dest, |
Psysteme | sys_dest, | ||
Ppolynome | poly_dest, | ||
list | ldata, | ||
int | stat_pred, | ||
Psysteme | sys_pred, | ||
Ppolynome | poly_source, | ||
int * | c, | ||
int | den | ||
) |
=================================================================
Psysteme make_causal_external(): same function as make_causal internal, but in this case we do not introduce the new variables Xe, and we write the causality condition under the following form: Pdest - Pinit >= 1
AC 94/01/27
write the causality condition under the following form:
P_dest - P_source -1 = 0
case of a uniform causality condition
make the polynom of unknown lambda
list of the variables to identify
Now we add the conditions on the edge, caus' we livin' on
the edge
write the causality condition under the following form:
P_dest - P_source - P_lambda -1 = 0
simplify the system and transform it in inequalities
Definition at line 1460 of file makebdt.c.
References add_lcoef_to_lcoef(), add_others_variables(), Ssysteme::base, base_to_list(), CAR, create_farkas_poly(), DATAFLOW, dataflow_governing_pred, dataflow_transformation, elim_var_with_eg(), extract_var_list(), fprint_list_of_exp(), fprint_psysteme(), fprintf(), gen_nreverse(), get_debug_level(), get_list_of_all_param(), include_parameters_in_sc(), include_trans_in_poly(), is_uniform_rec(), my_polynome_fprint, my_sc_normalize(), NIL, polynome_add(), polynome_decr(), polynome_dup(), polynome_negate(), polynome_rm(), polynome_scalar_mult(), polynome_to_sc(), POLYNOME_UNDEFINED, predicate_to_system(), sc_append(), sc_dup(), sc_new(), sc_rm(), sol_ppcm(), and transform_in_ineq().
Referenced by search_scc_bdt().
Psysteme make_causal_internal | ( | int | stat_dest, |
Psysteme | sys_dest, | ||
Ppolynome | poly_dest, | ||
list | ldata, | ||
int | stat_pred, | ||
Psysteme | sys_pred, | ||
Ppolynome | poly_source, | ||
int * | c, | ||
int | xc, | ||
entity * | xe, | ||
int | den | ||
) |
=================================================================
Psysteme make_causal_internal(): build the causality condition. If the causality condition is already linear, we do not need to apply Farkas lemma to create a Lambda polynom. This function identifies the different variables and writes them in a Psystem it returns. The integer c is usefull for the creation of the parameters LAMBDA in the case of a multi-edge. This function is used in the case of an internal edge of the scc where we introduce the variable "switch" Xe. The causality condition is written as: Pdest - Pinit >= Xe
AC 94/01/27
write the causality condition under the following form:
P_dest - P_source -Xe = 0
case of a uniform causality condition
make the polynom of unknown lambda
list of the variables to identify
Now we add the conditions on the edge, caus' we livin' on
the edge
list of the variables to identify
write the causality condition under the following form:
P_dest - P_source - P_lambda -1 = 0
simplify the system and transform it in inequalities
Definition at line 1317 of file makebdt.c.
References add_lcoef_to_lcoef(), add_others_variables(), Ssysteme::base, base_to_list(), CAR, create_farkas_poly(), DATAFLOW, dataflow_governing_pred, dataflow_transformation, elim_var_with_eg(), extract_var_list(), fprint_list_of_exp(), fprintf(), gen_nreverse(), get_debug_level(), get_list_of_all_param(), include_parameters_in_sc(), include_trans_in_poly(), is_uniform_rec(), make_polynome_Xe(), my_polynome_fprint, my_sc_normalize(), NIL, polynome_add(), polynome_dup(), polynome_negate(), polynome_rm(), polynome_scalar_mult(), polynome_to_sc(), POLYNOME_UNDEFINED, predicate_to_system(), sc_append(), sc_dup(), sc_new(), sc_rm(), sol_ppcm(), and transform_in_ineq().
Referenced by search_scc_bdt().
|
static |
=================================================================
Psysteme make_dual(psys,pcont,l,lvar_u,lvp): makes the dual problem in the case of a scc containing a single node. In this case, we do not introduce a set of "v" in the second member we put directly the proper value function of the program parameters.
AC 93/12/20
for each inequalities, build the second member of the system
and at the same time the system of constraints.
build and put the economic function in 1st position in psys
Definition at line 2246 of file makebdt.c.
References Ssysteme::base, base_to_list(), CAR, CDR, CONS, contrainte_make(), create_named_entity(), ENTITY, INT, list_to_base(), my_sc_normalize(), n_coef::n_vect, n_coef::next, NIL, reorder_base(), sc_add_inegalite(), sc_creer_base(), sc_new(), Scontrainte::succ, TCST, vect_add(), vect_aux, vect_chg_sgn(), vect_dup(), vect_new(), Scontrainte::vecteur, and VECTEUR_NUL.
Referenced by analyze_quast(), and search_scc_bdt().
=================================================================
list make_list_of_n(n,c) : function that creates a list of new entities as "u1" or "u2" it returns.
AC 93/11/16
Definition at line 473 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, create_named_entity(), ENTITY, free(), malloc(), and NIL.
Referenced by make_primal().
=================================================================
void make_list_of_unk(l, sc, me, lx): build the complete list of Pn_coef for the primal problem. At the beginning, l only contains the "MU" introduced by the inequation of causality. We check if SOME "MU" have been eliminated, we build the list of Xe that we put in first position, then we append the list of LAMBDA.
AC 94/01/27
First we check if some MU have been eliminated
we add at the beginning of lout the list about the Xs
we add at the end of lout the list about the lambda
Definition at line 1904 of file makebdt.c.
References add_lambda_list(), add_n_coef_to_list(), add_x_list(), base, base_to_list(), extract_lambda_list(), extract_var_list(), is_entity_in_list_p(), list_to_base(), n_coef::n_ent, and n_coef::next.
Referenced by search_scc_bdt().
=====================================================================
Pn_coef make_n_coef(e,v): allocating the space for a Pn_coef, that is a cell containing an entity and a Pvecteur, and returns a Pn_coef.
AC 93/11/15
Definition at line 191 of file makebdt.c.
Referenced by add_lambda_list(), add_x_list(), create_farkas_poly(), and extract_stat_lunk().
=================================================================
Ppolynome make_polynome_Xe(xc, xe): make the polynom of unknown xe = "X_xc".
AC 94/01/27
Definition at line 1260 of file makebdt.c.
References asprintf, create_named_entity(), free(), and make_polynome().
Referenced by make_causal_internal().
=================================================================
Psysteme make_primal(psys,lvar_u,lvp,lxe): build the primal problem. In fact, it does more then that, because it prepares the construc- tion of the dual problem by transposing the matrice coming from the input Psysteme.
AC 93/12/20
transform the system into a matrix
Now, we begin to make the dual problem
Definition at line 1731 of file makebdt.c.
References base, base_to_list(), f(), fprint_psysteme(), fprintf(), G, gen_length(), get_debug_level(), list_to_base(), make_list_of_n(), make_sched_proto(), matrice_free, matrice_new, matrice_nulle(), matrice_transpose(), pu_matrices_to_contraintes(), sc_make(), and sc_to_matrices().
Referenced by analyze_quast(), and search_scc_bdt().
|
static |
=================================================================
void make_proto((hash_table)h, (sccs)rg): function that goes through the reverse graph "rg", and for each node of each scc, initialize the node structure associated with each node, that is, creates the Farkas polynom of each node.
AC 93/10/28
Definition at line 687 of file makebdt.c.
References CAR, CDR, count, create_farkas_poly(), dfg_vertex_label_exec_domain, dfg_vertex_label_statement, hash_put(), include_parameters_in_sc(), malloc(), bdt_node::n_bdt, bdt_node::n_poly, bdt_node::n_var, NIL, POLYNOME_UNDEFINED, predicate_system, SCC, scc_vertices, sccs_sccs, VERTEX, and vertex_vertex_label.
Referenced by search_graph_bdt().
=================================================================
list make_sched_proto(h,lin,,col,lu): make the vector-list representing the prototype of the schedule we search.
AC 93/12/06
complete the vector to the dimension of the dual problem
Definition at line 1592 of file makebdt.c.
References ACCESS, ADD_ELEMENT_TO_LIST, CDR, gen_length(), INT, NIL, and VALUE_TO_INT.
Referenced by make_primal().
=================================================================
list make_x_list(c): build a list of entity of type X_nb where nb is a number between 0 and c.
AC 94/01/27
Definition at line 361 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, create_named_entity(), ENTITY, free(), malloc(), and NIL.
=================================================================
list reorder_base(l,lu) : reorder the base list l with the unknows lu contains in first positions in the list.
AC 93/11/17
Definition at line 308 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, CAR, CDR, ENTITY, is_entity_in_list_p(), and NIL.
Referenced by make_dual().
=================================================================
bdt search_graph_bdt( (sccs) rgraph ) : function that goes through the reverse graph "rgraph" and search the set of bdt for each reduced node.
AC 93/10/27
test of the existence of a predecessor
search the set of bdt for this scc
add the found bdt to the already calculated ones
Definition at line 3001 of file makebdt.c.
References bdt_schedules, bdt_undefined, bdt_undefined_p, CAR, CDR, gen_nconc(), h_node, hash_int, hash_table_free(), hash_table_make(), if_no_pred(), make_proto(), NIL, SCC, sccs_sccs, and search_scc_bdt().
Referenced by scheduling().
=================================================================
bdt search_scc_bdt( (scc) s) : from a given scc, make for each vertex the causality condition under its Farkas form and place it in a system. Then build the primal problem, then the dual problem, and finally solve it by PIP.
AC 93/10/29
for each node of the studied scc, get the characteristics of
the node we want the schedule
for each predecessor of the studied node, make the causality
condition under its Farkas form and write it in a Psystem
test if the vertex has already its schedule, and if yes
convert it to use it in the causality condition
this edge is an internal edge, so the predececssor
has not already a schedule
get the polynom of the source
the edge is an external edge, so the predecessor
has alredy a schedule. We only consider the first
dimension of this schedule in case of a multidimen-
sionnal one.
get the list of schedules of the source
for each schedule, write the causality condition
this is a particular case where we introduce
an Xe if we want the primal problem to be
consistent with the theory.
we have to add the constraints on the Xs: X<=1
Now we have in "psys" the complete Psystem in mu-lambda to solve
We now transform it in the primal problem
Definition at line 2709 of file makebdt.c.
References add_constraint_on_x(), ADD_ELEMENT_TO_LIST, add_elt_to_sys_list(), add_lcoef_to_lcoef(), add_sc_to_sclist(), analyze_expression(), analyze_quast(), Ssysteme::base, bdt_schedules, bdt_undefined, CAR, cons::cdr, CDR, compact_quast(), count, DATAFLOW, dataflow_transformation, dfg_arc_label_dataflows, dfg_vertex_label_exec_domain, ENTITY, erase_trivial_ineg(), exp, EXPRESSION, expression_to_polynome(), extract_stat_lunk(), fprint_bdt(), fprint_coef_list(), fprint_list_of_exp(), fprint_psysteme(), fprintf(), gen_length(), get_debug_level(), h_node, hash_get(), imprime_quast(), include_trans_in_sc(), INT, lexp, list_to_base(), make_bdt_initial(), make_causal_external(), make_causal_internal(), make_dual(), make_list_of_unk(), make_primal(), my_polynome_fprint, my_sc_normalize(), bdt_node::n_bdt, bdt_node::n_poly, bdt_node::n_var, NIL, pip_solve_min_with_big(), polynome_dup(), predicate_to_system(), pu_vect_fprint(), sc_append(), sc_dup(), sc_new(), sc_rm(), scc_vertices, SCHEDULE, schedule_dims, schedule_predicate, SUCCESSOR, successor_arc_label, successor_vertex, sys_list::sys, true_copy_bdt(), VERTEX, vertex_int_stmt(), vertex_successors, vertex_vertex_label, and write_resulting_bdt().
Referenced by search_graph_bdt().
=================================================================
bdt simplify_bdt(b,s): simplify the list of schedule of a node by comparing the predicate of the schedule with the domain on which the node is defined. Moreover, replace variables by their value when it is possible in the predicate and the expression. (i.e. if I == N and dims==N+I+1 => dims==2*N+1 )
AC 93/12/20
Definition at line 2160 of file makebdt.c.
References adg_number_to_statement(), bdt_schedules, CAR, CDR, elim_var_with_eg(), find_implicit_equation(), fprint_entity_list(), fprint_psysteme(), fprintf(), gen_append(), get_debug_level(), get_predicate_system_of_node(), get_stco_from_current_map(), make_predicate(), my_sc_normalize(), NIL, predicate_to_system(), SCHEDULE, schedule_dims, schedule_predicate, schedule_statement, simplify_dimension(), simplify_predicate(), static_control_params, static_control_to_indices(), and suppress_sc_in_sc().
Referenced by write_resulting_bdt().
=================================================================
list simplify_dimension(ld, ps_eq, l): implify the different dimensions f the schedule in the list ld with the variables in l with the equalities that ps_eq contains.
AC 94/03/28
loop on the dimension of the schedule to process
loop on the variables to eliminate
try next variable
Definition at line 2056 of file makebdt.c.
References ADD_ELEMENT_TO_LIST, analyze_expression(), base_contains_variable_p(), call_arguments, CAR, CDR, CONS, ENTITY, exp, EXPRESSION, expression_normalized, expression_syntax, fprint_entity_list(), fprint_list_of_exp(), fprintf(), get_debug_level(), int_to_expression(), make_rational_exp(), NIL, NORMALIZE_EXPRESSION, normalized_linear, ppcm(), pu_vect_fprint(), Pvecteur_to_expression(), Scontrainte::succ, syntax_call, value_abs, value_div, value_mult, value_posz_p, vect_add(), vect_coeff(), vect_dup(), vect_multiply(), vect_substract(), Scontrainte::vecteur, and VECTEUR_UNDEFINED_P.
Referenced by simplify_bdt().
=================================================================
Psysteme simplify_predicate(ps, ps_eq, l): simplify the psysteme ps by replacing the new variables in l by their expression in ps_eq (in the same order).
AC 94/03/28
Definition at line 2008 of file makebdt.c.
References base_contains_variable_p(), CAR, CDR, Ssysteme::egalites, ENTITY, Ssysteme::inegalites, NIL, ppcm(), Scontrainte::succ, value_abs, value_div, value_mult, value_posz_p, vect_add(), vect_coeff(), vect_dup(), vect_multiply(), vect_substract(), and Scontrainte::vecteur.
Referenced by simplify_bdt().
=================================================================
Psysteme system_new_var_subst(sys, l): replace in a psyteme the new variables introduced by PIP by their value.
AC 93/12/20
extract the new parameter
extract the numerator
extract the denominator
Definition at line 1629 of file makebdt.c.
References analyze_expression(), Ssysteme::base, BASE_NULLE, call_arguments, CAR, CDR, exp, EXPRESSION, expression_normalized, expression_syntax, expression_to_int(), Ssysteme::inegalites, is_entity_in_list_p(), lexp, lvect, NIL, NORMALIZE_EXPRESSION, normalized_linear, sc_creer_base(), Scontrainte::succ, syntax_call, sys_list::sys, VAR_VAL, var_val_value, var_val_variable, vect_add(), vect_coeff(), vect_erase_var(), vect_multiply(), vect_normalize(), Scontrainte::vecteur, and vecteur_to_list().
Referenced by analyze_quast().
=================================================================
Psysteme transform_in_ineq((Psysteme)sc,(list)l):change a system of equalities in a system of inequalities, and at the same time, try to eliminate some lambda variables that are useless.
AC 93/11/08
in each vector, isolate a lambda variable if it exists
transform each equality in an inequality
Definition at line 902 of file makebdt.c.
References Ssysteme::base, base_contains_variable_p(), CAR, CDR, Ssysteme::egalites, ENTITY, Ssysteme::inegalites, Ssysteme::nb_eq, Ssysteme::nb_ineq, NIL, sc_creer_base(), sc_dup(), sc_elim_empty_constraints(), sc_rm(), Scontrainte::succ, value_negz_p, vect_chg_sgn(), vect_coeff(), vect_erase_var(), and Scontrainte::vecteur.
Referenced by make_causal_external(), and make_causal_internal().
=================================================================
bdt write_resulting_bdt(s, stat, bs, bg): simplify the bdt found and update the hash table.
AC 94/01/27
Definition at line 2681 of file makebdt.c.
References bdt_schedules, bdt_undefined_p, gen_nconc(), h_node, hash_get(), node(), simplify_bdt(), and true_copy_bdt().
Referenced by search_scc_bdt().
hash_table h_node |
Definition at line 85 of file makebdt.c.
Referenced by build_bdt_null(), search_graph_bdt(), search_scc_bdt(), and write_resulting_bdt().