PIPS
|
#include <stdio.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.
Functions | |
bool | ineq_redund_with_sc_p (Psysteme sc, Pcontrainte ineq) |
This function returns true if the inequation ineq is redundant for the system ps and false otherwise. More... | |
bool | eq_redund_with_sc_p (Psysteme sc, Pcontrainte eq) |
bool eq_redund_with_sc_p(sc, eq) Psysteme sc; Pcontrainte eq; More... | |
Psysteme | extract_nredund_subsystem (Psysteme s1, Psysteme s2) |
Psysteme extract_nredund_subsystem(s1, s2) Psysteme s1, s2;. More... | |
void | build_sc_nredund_1pass_ofl_ctrl (Psysteme volatile *psc, int ofl_ctrl) |
Psysteme build_sc_nredund_1pass_ofl_ctrl(Psysteme ps, int ofl_ctrl) input : a system in which redundancies must be eliminated, and an integer indicating how overflow errors must be handled. More... | |
void | sc_safe_build_sc_nredund_1pass (Psysteme volatile *ps) |
void | build_sc_nredund_1pass (Psysteme volatile *ps) |
Computation of a new system sc from the system ps, where each constraint of the system ps is added to the new system sc, if the constraint is not redundant with the system sc previously computed. More... | |
void | build_sc_nredund_2pass_ofl_ctrl (Psysteme volatile *psc, int ofl_ctrl) |
void | sc_safe_build_sc_nredund_2pass (Psysteme volatile *ps) |
void | build_sc_nredund_2pass (Psysteme volatile *psc) |
void build_sc_nredund_2pass Psysteme *psc; More... | |
static bool | sc_elim_triang_integer_redund_constraint_p (Pcontrainte pc2, Pbase index_base, Pcontrainte ineq, Variable var_hr, tab_info, int *rank_max) |
This function returns true if the constraint ineq can be eliminated from the system sc and false oterwise. More... | |
Psysteme | build_integer_sc_nredund (volatile Psysteme ps, Pbase index_base, int tab_info[][4], int loop_level, int dim_h __attribute__((unused)), int n __attribute__((unused))) |
Computation of a new system sc from the system ps, where each constraint of the system ps is added to the new system sc, if the constraint is not redundant with the system sc previously computed. More... | |
bool | bound_redund_with_sc_p (Psysteme sc, Pcontrainte ineq1, Pcontrainte ineq2, Variable var) |
This function returns true if the constraint C (resulting of the combination of the two constraints ineq1 and ineq2) is redundant for the system sc, and false otherwise. More... | |
bool bound_redund_with_sc_p | ( | Psysteme | sc, |
Pcontrainte | ineq1, | ||
Pcontrainte | ineq2, | ||
Variable | var | ||
) |
This function returns true if the constraint C (resulting of the combination of the two constraints ineq1 and ineq2) is redundant for the system sc, and false otherwise.
Assume that ineq1 = coeff1 (positive) * var + E1 <=0 ineq2 = coeff2 (negative) * var +E2 <=0 C = coeff1 * E2 - coeff2 * E1 - coeff1*coeff2-coeff1 <=0
Definition at line 535 of file sc_build_sc_nredund.c.
References CATCH, contrainte_copy(), contrainte_rm, CONTRAINTE_UNDEFINED, CONTRAINTE_UNDEFINED_P, FWD_OFL_CTRL, overflow_error, TRY, UNCATCH, value_pos_p, vect_coeff(), and Scontrainte::vecteur.
Referenced by constraint_distribution().
Psysteme build_integer_sc_nredund | ( | volatile Psysteme | ps, |
Pbase | index_base, | ||
int | tab_info[][4], | ||
int | loop_level, | ||
int dim_h | __attribute__(unused), | ||
int n | __attribute__(unused) | ||
) |
Computation of a new system sc from the system ps, where each constraint of the system ps is added to the new system sc, if the constraint is not redundant with the system sc previously computed.
The difference with the function build_sc_nredund is that at least 2 constraints are kept for each variable: one for the upper bound and the other for the lower bound.
The rational set defined by ps may be enlarged by this procedure because an integer constraint negation is used.
Modifs:
this condition is true if the constraint can be eliminated from the system, that means if this is not the last constraint on the variable or if all the constraints on this variable can be eliminated (the rank of variable is greater the number of loops)
Definition at line 432 of file sc_build_sc_nredund.c.
References Ssysteme::base, base_copy(), CATCH, contrainte_copy(), contrainte_reverse(), contrainte_rm, CONTRAINTE_UNDEFINED_P, Ssysteme::dimension, Ssysteme::egalites, eq, Ssysteme::inegalites, Ssysteme::nb_ineq, OFL_CTRL, overflow_error, sc_add_inegalite(), sc_elim_triang_integer_redund_constraint_p(), sc_empty_p(), sc_new(), sc_rational_feasibility_ofl_ctrl(), search_higher_rank(), Scontrainte::succ, TRY, UNCATCH, value_sign, variable_of_rank(), vect_coeff(), and Scontrainte::vecteur.
Referenced by movement_computation(), and parallel_tiling().
void build_sc_nredund_1pass | ( | Psysteme volatile * | ps | ) |
Computation of a new system sc from the system ps, where each constraint of the system ps is added to the new system sc, if the constraint is not redundant with the system sc previously computed.
The set of equalities is copied as such and ignored by redundancy checks.
Definition at line 269 of file sc_build_sc_nredund.c.
References build_sc_nredund_1pass_ofl_ctrl(), and OFL_CTRL.
Referenced by movement_computation(), sc_projection_concat_proj_on_variables(), and sc_safe_build_sc_nredund_1pass().
Psysteme build_sc_nredund_1pass_ofl_ctrl(Psysteme ps, int ofl_ctrl) input : a system in which redundancies must be eliminated, and an integer indicating how overflow errors must be handled.
output : Computes a new system sc from the system ps, where each constraint of the system ps is added to the new system sc, if the constraint is not redundant with the system sc previously computed. modifies : comment : The set of equalities is copied as such and ignored by redundancy checks.
if ofl_ctrl == 0 overflow errors are trapped in the routine which checks if the system is feasible. if ofl_ctrl == 2 overflow errors are trapped in the sc_rational_feasibility_ofl_ctrl routine that keeps the constraint in the system whatever its redundancy characteristic if ofl_ctrl == 1 overflow errors are forwarded to the calling routine.
the redundancy elimination assumes integer points. The rational set defined by sc may be enlarged.
if more than 6 exceptions are thrown from within the loop, the loop is stopped.
Definition at line 190 of file sc_build_sc_nredund.c.
References Ssysteme::base, base_dup(), contrainte_copy(), contrainte_reverse(), contrainte_rm, CONTRAINTE_UNDEFINED_P, contraintes_copy(), Ssysteme::egalites, fprintf(), Ssysteme::inegalites, linear_number_of_exception_thrown, Ssysteme::nb_eq, Ssysteme::nb_ineq, OFL_CTRL, sc_add_inegalite(), sc_empty(), sc_empty_p(), sc_init_with_sc(), sc_rational_feasibility_ofl_ctrl(), sc_rm(), sc_rn_p(), and Scontrainte::succ.
Referenced by build_sc_nredund_1pass(), and build_sc_nredund_2pass_ofl_ctrl().
void build_sc_nredund_2pass | ( | Psysteme volatile * | psc | ) |
void build_sc_nredund_2pass Psysteme *psc;
Definition at line 331 of file sc_build_sc_nredund.c.
References build_sc_nredund_2pass_ofl_ctrl(), and OFL_CTRL.
Referenced by clean_shared_io_system(), clean_the_system(), generate_distributed_io_system(), put_variables_in_ordered_lists(), and sc_safe_build_sc_nredund_2pass().
Definition at line 275 of file sc_build_sc_nredund.c.
References assert, Ssysteme::base, build_sc_nredund_1pass_ofl_ctrl(), fprintf(), sc_belongs_p(), sc_default_dump(), sc_empty_p(), sc_normalize(), sc_rn_p(), and vect_make_dense().
Referenced by build_sc_nredund_2pass(), and sc_projection_optim_along_vecteur_ofl().
bool eq_redund_with_sc_p | ( | Psysteme | sc, |
Pcontrainte | eq | ||
) |
bool eq_redund_with_sc_p(sc, eq) Psysteme sc; Pcontrainte eq;
IN: sc, eq
OUT: returned boolean
true if eq is redundant with sc (c) FC 16/05/94
eq considered as an inequality
Definition at line 99 of file sc_build_sc_nredund.c.
References contrainte_chg_sgn(), contrainte_copy(), contrainte_free(), eq, and ineq_redund_with_sc_p().
Referenced by extract_nredund_subsystem(), and show_nredund().
Psysteme extract_nredund_subsystem(s1, s2) Psysteme s1, s2;.
IN: s1, s2 OUT: returned Psysteme
returns the constraints of s1 that are not redundant with s2
(c) FC 16/05/94
temporary
inequalities
could be inlined to avoid costly sc_copy inside ineq_redund_with_sc_p
equalities
Definition at line 127 of file sc_build_sc_nredund.c.
References contrainte_copy(), CONTRAINTE_UNDEFINED, eq, eq_redund_with_sc_p(), ineq_redund_with_sc_p(), s1, sc_make(), and Scontrainte::succ.
Referenced by create_step_regions(), GENERATION(), hpfc_simplify_condition(), and processor_loop().
bool ineq_redund_with_sc_p | ( | Psysteme | sc, |
Pcontrainte | ineq | ||
) |
This function returns true if the inequation ineq is redundant for the system ps and false otherwise.
sc and ineq are not modified by the function.
Inequality ineq may not be redundant wrt ps for rational numbers and nevertheless true is returned if it is redundant wrt integer points.
A bug found here: if we have input sc==NULL with ineq=NULL, then we'll have to test the satisfiability of a sc that has a base null and an ineq (core dump): because in sc_add_inegalite, we test only if the pointers (sc,ineg) are null. The encountered case is that the pointer not null but his all elements are null or except only one element. This means the constraint is not valid.
DN 2/1/2003 The same with eq_redund_with_sc_p Modifs:
othing to test: 0==0 is intrinsically redundant
test de sc_faisabilite avec la nouvelle inegalite
Definition at line 59 of file sc_build_sc_nredund.c.
References BASE_NULLE, base_rm, contrainte_copy(), CONTRAINTE_NULLE_P, contrainte_reverse(), OFL_CTRL, sc_add_inegalite(), sc_copy(), sc_creer_base(), sc_rational_feasibility_ofl_ctrl(), and sc_rm().
Referenced by elim_redund_sc_with_sc(), eq_redund_with_sc_p(), extract_nredund_subsystem(), loop_executed_approximation(), and show_nredund().
|
static |
This function returns true if the constraint ineq can be eliminated from the system sc and false oterwise.
It assumes that two constraints at least must be kept for constraining the variable "var_hr" in the system. the array "tab_info" contains the useful informations allowing to know the number of constraints constraining each variable as upper or lower bounds.
This condition is true if the variable is a loop index. As the constraint constrains directly the variable, this constraint must be kept if there is not enough remainding constraints
Definition at line 349 of file sc_build_sc_nredund.c.
References constraint_integer_combination(), CONTRAINTE_UNDEFINED_P, MAX, rank_of_variable(), Scontrainte::succ, value_neg_p, value_notzero_p, value_pos_p, value_sign, vect_coeff(), and Scontrainte::vecteur.
Referenced by build_integer_sc_nredund().
void sc_safe_build_sc_nredund_1pass | ( | Psysteme volatile * | ps | ) |
*ps = sc_sort_constraints_simplest_first(*ps, b); see version 1.16
Definition at line 243 of file sc_build_sc_nredund.c.
References base_copy(), base_rm, build_sc_nredund_1pass(), sc_empty(), sc_empty_p(), and sc_rn_p().
Referenced by transformer_normalize().
void sc_safe_build_sc_nredund_2pass | ( | Psysteme volatile * | ps | ) |
Definition at line 309 of file sc_build_sc_nredund.c.
References base_copy(), base_rm, build_sc_nredund_2pass(), sc_empty(), sc_empty_p(), and sc_rn_p().