PIPS
|
#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 "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.
Macros | |
#define | IS_LOWER 0 |
#define | IS_UPPER 1 |
Functions | |
void | set_array_declaration (entity var_to_decl, list lrange) |
Name : bounds.c Package : reindexing Author : Alexis Platonoff Date : March 1995 Historic : More... | |
expression | constraint_to_bound (Pcontrainte pc, entity ent, list lvar, list lrange, int lower_or_upper, int array_or_loop) |
=================================================================== More... | |
expression | bound_compute (Psysteme sc, entity ent, list lvar, list lrange, int lower_or_upper, int array_or_loop) |
=================================================================== More... | |
range | make_bounds (Psysteme ps, entity ent, int array_or_loop, list lvar, list lrange) |
===================================================================== More... | |
void | get_bounds_expression (Psyslist sys, list lt, list *lb, list *ub) |
===================================================================== More... | |
Psyslist | separate_variables (Psysteme ps, list l, Psysteme *sp, int c) |
======================================================================== More... | |
Psyslist | separate_variables_2 (Psysteme ps, list l, Psysteme *sp, int c) |
======================================================================== More... | |
expression bound_compute | ( | Psysteme | sc, |
entity | ent, | ||
list | lvar, | ||
list | lrange, | ||
int | lower_or_upper, | ||
int | array_or_loop | ||
) |
===================================================================
Definition at line 356 of file bounds.c.
References constraint_to_bound(), expression_undefined, fprintf(), get_debug_level(), IS_LOWER, IS_MAX, IS_MIN, merge_expressions(), Scontrainte::succ, and user_error.
Referenced by make_bounds().
expression constraint_to_bound | ( | Pcontrainte | pc, |
entity | ent, | ||
list | lvar, | ||
list | lrange, | ||
int | lower_or_upper, | ||
int | array_or_loop | ||
) |
===================================================================
"val" corresponds to the absolute value of the coefficient of "e" in the constraint.
"vect" represents the term of the constraints that does not contains "e". We have : (e+vect <= 0) or (-e+vect <= 0), whether it is a lower or upper bound.
In the case of the upper bound, we have to change the sign of "vect" in order to have a positive coefficient for "e".
We build this Pcontrainte which will be used as a list of Pvecteur.
In the case of ARRAY BOUNDS, we substitute in "vect" all the var of "lvar" that have a non zero coeff by their min or max value, which is given by "lrange".
We replace the current var by whether its lower or upper bound, it depends on the sign of its coefficient. It also depends on the kind of bound we have to build.
lower_or_upper == IS_UPPER
This expression by which we replace the current var can be of two forms. The first, a single linear expression, is just substitute. The second, a MAX or MIN expression has to be switch in as many expressions as there are linear expressions in this expression.
We apply the substitution on all the vectors of our list.
For each vector of our list, we duplicate it in order to take into account all the arguments of this MIN or MAX function.
We walk through all these arguments.
This "arg" is not the last one, so we duplicate our vector before substituting.
This is not the last argument, so the successor is our current vector which has been just duplicated.
We now build the expression that represent the bound of our variable "e". This expression is a single linear one if "lvect" contains only one vector, otherwise, it is a MIN or MAX expression, depending on whether it is a lower or upper bound.
lower_or_upper == IS_UPPER
Definition at line 154 of file bounds.c.
References ADD_ELEMENT_TO_LIST, call_arguments, CAR, CDR, contrainte_make(), ENDP, ENTITY, entity_intrinsic(), entity_local_name(), EXPRESSION, expression_syntax, expression_to_string(), expression_undefined, fprint_psysteme(), fprintf(), gen_length(), get_debug_level(), IS_ARRAY_BOUNDS, IS_LOWER, is_normalized_linear, is_syntax_call, IS_UPPER, lvect, make_call(), make_expression(), make_rational_exp(), make_syntax(), min_or_max_expression_p(), NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_tag, normalized_undefined, POP, pu_variable_name(), pu_vect_fprint(), RANGE, range_lower, range_upper, sc_make(), Scontrainte::succ, syntax_call, user_error, value_absolute, value_notzero_p, value_sign, vect_chg_sgn(), vect_coeff(), vect_del_var(), vect_dup(), vect_var_subst(), Scontrainte::vecteur, and vecteur_fprint().
Referenced by bound_compute().
=====================================================================
void get_bounds_expression(sys, lt, lb, ub)
From the list of Psysteme psys, we determine the value of each lower and upper bound of the local time.
Lower bounds are in the inequalities of "sys" ; upper bounds are in the equalities.
AC 94/06/13
Lower and upper bounds are now in the inequalities. So, first, we have to sort these ineq in two groups, one for the lower bound and one for the upper bound.
AP 95/01/30
Sort the inequalities
Only one lower bound
More than one lower bound, build a max
Only one upper bound
More than one upper bound, build a min
Definition at line 497 of file bounds.c.
References ADD_ELEMENT_TO_LIST, CAR, cons::cdr, CONS, contrainte_dup(), ENTITY, entity_intrinsic(), EXPRESSION, expression_to_string(), expression_undefined, fprint_psysteme(), fprintf(), get_debug_level(), ifdebug, Ssysteme::inegalites, is_syntax_call, make_call(), make_expression(), make_rational_exp(), make_syntax(), Ssysteme::nb_ineq, NIL, normalized_undefined, Ssyslist::psys, sc_add_inegalite(), sc_new(), Scontrainte::succ, user_error, value_absolute, value_posz_p, vect_chg_sgn(), vect_coeff(), vect_del_var(), vect_dup(), and Scontrainte::vecteur.
Referenced by build_third_comb().
=====================================================================
range make_bounds(ps, ent, array_or_loop, list lvar, list lrange)
Builds the bounds of variable "ent" from the psysteme "ps". "array_or_loop" gives which kind of bounds we want: IS_LOOP_BOUNDS or IS_ARRAY_BOUNDS. For the first, these bounds will be used in a loop, so we just have to get the constraints of "ps" and use them to build these bounds (in the bounds of a given loop may appear other loop indices from englobing loops). On the contrary, for the second, these bounds will be used in an array dimension declaration, so we first have to eliminate the other variables (in "lvar") using their bounds (in "lrange") before building these bounds.
AP 95/01/20
the psysteme should have two constraints, one for the lb and the other for the ub, but we don't know which one is what. In fact, it may have more constraints, in which case the lower or/and upper bounds are expressed by MIN or MAX functions.
We compute these lower and upper bounds.
Definition at line 413 of file bounds.c.
References bound_compute(), CAR, contrainte_dup(), ENDP, entity_local_name(), expression_to_string(), fprint_entity_list(), fprint_psysteme(), fprintf(), get_debug_level(), ifdebug, int_to_expression(), IS_LOWER, IS_UPPER, make_range(), POP, RANGE, sc_add_inegalite(), sc_new(), Scontrainte::succ, user_error, value_posz_p, vect_coeff(), Scontrainte::vecteur, words_range(), and words_to_string().
Referenced by build_first_comb(), build_third_comb(), and prepare_array_bounds().
========================================================================
Psyslist separate_variables(ps, l)
We have a psystem ps containing all variables in l, and we want to have a list of psystem where each system is containing the variable of its rank.
Ex: variable t1, t2, p1. => we will have 3 systems, ps1, ps2, ps3. ps1 = f(n, t1) (n structure parameters); ps2 = f(t1, n, t2); ps3 = f(p1, t1, t2);
We also separate the bounds and put the constraints on the upper bound in the equalities and the constraints on the lower bound in the inequalities.
AC 94/04/05
add inequalities on the max
Definition at line 622 of file bounds.c.
References add_sc_to_sclist(), base_contains_variable_p(), CAR, cons::cdr, contrainte_dup(), contrainte_make(), Ssysteme::egalites, ENTITY, entity_local_name(), fprintf(), gen_nreverse(), get_debug_level(), NIL, sc_add_egalite(), sc_add_inegalite(), sc_append(), sc_dup(), sc_new(), sc_normalize(), sl_fprint(), Scontrainte::succ, Ssyslist::succ, value_neg_p, vect_chg_sgn(), vect_coeff(), vect_dup(), Scontrainte::vecteur, and VECTEUR_NUL.
Referenced by build_third_comb(), and prepare_reindexing().
========================================================================
Psyslist separate_variables_2(ps, l): we have a psystem ps containing all variables in l, and we want to have a list of psystem where each system is containing the variable of its rank. Ex: variable t1, t2, p1. => we will have 3 systems, ps1, ps2, ps3. ps1 = f(n, t1) (n structure parameters); ps2 = f(t1, n, t2); ps3 = f(p1, t1, t2);
same function as above but we do not distinguish the min from the max.
AC 94/04/05
add inequalities on the max
add inequalities on the max
Definition at line 711 of file bounds.c.
References add_sc_to_sclist(), base_contains_variable_p(), CAR, cons::cdr, contrainte_dup(), Ssysteme::egalites, ENTITY, entity_local_name(), fprintf(), gen_nreverse(), get_debug_level(), NIL, reverse_psyslist(), sc_add_inegalite(), sc_append(), sc_dup(), sc_new(), sc_normalize(), sl_fprint(), Scontrainte::succ, Ssyslist::succ, Scontrainte::vecteur, and VECTEUR_NUL.
Referenced by prepare_reindexing().
Name : bounds.c Package : reindexing Author : Alexis Platonoff Date : March 1995 Historic :
Documents: SOON Comments : This file contains the functions dealing with the bounds of the variables and the loops. Ansi includes
Newgen includes
C3 includes
Pips includes
=================================================================== void set_array_declaration(entity var_to_decl, list lrange)
Set the dimensions of entity "var_to_decl" with the ranges of "lrange".
Definition at line 95 of file bounds.c.
References CAR, CONS, DIMENSION, ENDP, entity_type, expression_equal_integer_p(), gen_nconc(), make_dimension(), NIL, POP, RANGE, range_increment, range_lower, range_upper, type_variable, user_error, and variable_dimensions.
Referenced by make_array_bounds().