PIPS
|
#include <string.h>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
Go to the source code of this file.
Macros | |
#define | HUGE 250 |
package sc More... | |
#define | level (2) |
#define | if_debug_sc_minmax_of_variable2 if(false) |
Functions | |
static bool | huge_system (Psysteme ps) |
bool | sc_value_of_variable (Psysteme ps, Variable var, Value *pval) |
bool sc_value_for_variable(Psysteme ps, Variable var, Value *pval): examine les egalites du systeme ps pour recherche une egalite de la forme: More... | |
bool | sc_minmax_of_variable (Psysteme ps, Variable var, Value *pmin, Value *pmax) |
void sc_minmax_of_variable(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin. More... | |
void | sc_minmax_of_variables (Psysteme ps1, Psysteme ps2, Pbase b) |
This function uses sc_minmax_of_variable to compute the min and max of each variable belonging to base b. More... | |
void | sc_force_variable_to_zero (Psysteme ps, Variable var) |
void sc_force_variable_to_zero(Psysteme ps, Variable var): force la variable var a prendre la valeur 0, i.e. More... | |
bool | sc_minmax_of_variable2 (volatile Psysteme ps, Variable var, Value *pmin, Value *pmax) |
void sc_minmax_of_variable2(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin. More... | |
#define level (2) |
Definition at line 46 of file sc_eval.c.
References HUGE, Ssysteme::nb_eq, and Ssysteme::nb_ineq.
Referenced by sc_minmax_of_variable().
void sc_force_variable_to_zero(Psysteme ps, Variable var): force la variable var a prendre la valeur 0, i.e.
intersection du polyedre defini par ps avec l'hyperplan var=0; on suppose que cette intersection est non vide (la faisabilite n'est pas testee).
le systeme initial ps est transforme par effet de bord.
Definition at line 251 of file sc_eval.c.
References contrainte_constante_p(), contrainte_free(), Scontrainte::succ, vect_erase_var(), and Scontrainte::vecteur.
Referenced by loop_bounds_to_tile_bounds(), make_scanning_over_one_tile(), and TestDiVariables().
void sc_minmax_of_variable(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin.
la procedure retourne la valeur false si le systeme est infaisable et true sinon
le systeme ps est detruit.
projection sur toutes les variables sauf var
cette contrainte nous donne une borne max
cette contrainte nous donne une borne min
Definition at line 143 of file sc_eval.c.
References assert, huge_system(), sc_elim_double_constraints(), sc_normalize(), sc_rn_p(), sc_value_of_variable(), Scontrainte::succ, Svecteur::succ, TCST, value_gt, value_lt, VALUE_MAX, VALUE_MIN, value_neg_p, value_pdiv, value_pos_p, value_uminus, vect_coeff(), vect_copy(), vect_rm(), Scontrainte::vecteur, VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.
Referenced by do_solve_hardware_constraints_on_nb_proc(), evaluate_var_to_complexity(), expression_and_precondition_to_integer_interval(), integer_expression_and_precondition_to_integer_interval(), integer_value_and_precondition_to_integer_interval(), loop_nest_to_tile(), main(), make_movements_loop_body_wp65(), make_scanning_over_one_tile(), make_scanning_over_tiles(), precondition_minmax_of_value(), sc_find_equalities(), sc_minmax_of_variable2(), sc_minmax_of_variables(), and set_dimensions_of_local_variable_family().
void sc_minmax_of_variable2(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin.
la procedure retourne la valeur false si le systeme est infaisable et true sinon
Le systeme ps est detruit et desalloue..
L'algorithme utilise est different de celui de sc_minmax_of_variable(). Les equations sont tout d'abord utilisees pour decomposer le systeme en un hyper-espace caracterise par un sous-ensemble des equations (par exemple les equations ayant moins de 2 variables) et un polyedre de cet hyperespace caracterise par les inegalites de ps et les egalites qui n'ont pas ete utilisees lors de la projection.
Note:
Maximum number of variables in an equation used for the projection
no obvious non-feasibility
&& sc_nbre_egalites(ps) != 0
eq might suffer in the substitution...
eq is redundant
Equalities change because of substitutions. Their dimensions may go under the present required dimension, nvar. Hence the non-equality test between d and nvar.
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
Does eq define var's value (and min==max)? Let's keep track of this but go on to check feasibility
remember eq was normalized...
Although the value might have been found, go on to check feasibility. This could be optional because it should not matter for any safe use of this function. See Note in function's header.
do not touch ps any more
sc_rm(new_ps);
keep eq
In fact, new_ps is not needed. we simply modify ps
use eq to eliminate a variable except if var value is still unknown. We then do need this equation in ps.
Let's use a variable with coefficient 1 if possible.
This test is not fully used in the curent version since value_found_p==false here. That would change if feasibility had to be checked better.
because of the !CONTRAINTE_NULLE_P() test and because of value_found_p
eq itself is going to be modified in ps. use a copy!
Print ps after projection. This really generates a lot of output on real life systems! But less than the next debug statement...
too early to use this equation eq
If there any hope to use it in the future? Yes, if its dimension is no more than nvar+1 because one of its variable might be substituted. If more variable are substituted, it's dimension is going to go down and it will be counted later... Well this is not true, it will be lost:-(
to be on the safe side till I find a better idea...
The system is not feasible. Stop
This really generates a lot of output on real life system! This is useless. Use previous debugging statement
Try to exploit the inequalities and the equalities left in ps
Exploit the reduction in size
I'm afraid of sc_minmax_of_variable() behavior... The guard should be useless
Definition at line 330 of file sc_eval.c.
References assert, base_contains_variable_p(), base_rm, BASE_UNDEFINED, CATCH, contrainte_dup(), CONTRAINTE_NULLE_P, contrainte_rm, contrainte_succ, CONTRAINTE_UNDEFINED, CONTRAINTE_UNDEFINED_P, contrainte_vecteur, egalite_normalize(), eq, fprint_Value(), fprintf(), if_debug_sc_minmax_of_variable2, level, NO_OFL_CTRL, overflow_error, sc_creer_base(), sc_dump(), sc_elim_var(), sc_minmax_of_variable(), sc_normalize(), sc_rm(), Svecteur::succ, TCST, TRY, UNCATCH, val_of, value_div, VALUE_MAX, VALUE_MIN, value_one_p, value_uminus, VALUE_ZERO, Svecteur::var, vect_dimension(), VECTEUR_NUL_P, vecteur_succ, VECTEUR_UNDEFINED_P, vecteur_val, and vecteur_var.
Referenced by partial_eval_reference().
This function uses sc_minmax_of_variable to compute the min and max of each variable belonging to base b.
If constraints on the variable are found, they are added to the systeme ps2.
Definition at line 212 of file sc_eval.c.
References assert, contrainte_make(), max, min, sc_dup(), sc_minmax_of_variable(), Svecteur::succ, TCST, VALUE_MAX, VALUE_MIN, VALUE_MONE, value_ne, VALUE_ONE, value_uminus, vect_make(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.
Referenced by movement_computation().
bool sc_value_for_variable(Psysteme ps, Variable var, Value *pval): examine les egalites du systeme ps pour recherche une egalite de la forme:
coeff*var - cste == 0
Si une telle equation est trouvee et si elle est faisable, sc_value_for_variable calcule la valeur de var pour ce systeme et la retourne par pval. Sinon, la procedure renvoie la valeur false.
Notes:
equation de la forme: k*var == 0
equation de la forme: k*var - c == 0
equation de la forme: c - k*var == 0
Definition at line 70 of file sc_eval.c.
References Scontrainte::succ, Svecteur::succ, TCST, val_of, value_div, value_mod, value_uminus, value_zero_p, Svecteur::var, Scontrainte::vecteur, and VECTEUR_NUL_P.
Referenced by sc_minmax_of_variable(), sc_minmax_of_variable_optim(), TestDependence(), and TestDiCnst().