PIPS
|
#include <string.h>
#include <stdio.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 | |
void | sc_transform_eg_in_ineg (Psysteme sc) |
Package sc. More... | |
void | sc_transform_ineg_in_eg (Psysteme sc) |
Transform the two constraints A.x <= b and -A.x <= -b of system sc into an equality A.x == b. More... | |
static int | abscmp (Pvecteur *pv1, Pvecteur *pv2) |
sc_find_equalities(Psysteme * ps) More... | |
void | sc_find_equalities (Psysteme *ps) |
sc_find_equalities(Psysteme * ps)
what: updates *ps to an equivalent system with more/better equalities. in/out: *ps how: (1) Maslov PLDI'92; (2) (a <= x <= a) => (x == a)
(1) Inspired by Vadim Maslov, PLDI'92 "delinearization". It is based on the following property (a 1 page theorem and proof in his paper):
Prop: forall a,n,m in Z, a>0, |m|<a, (an+m=0 <=> n=0, m=0) Proof: [<=] trivial; [=>] a|n|=|m|<a => |n|<1 => n=0 => m=0;
From this property, typical of dependence tests on linearized accesses, two simple equations are derived from a bigger one and inequalities. Our purpose is to identify the simpler equalities and to substitute them in the system, not to perform an actual dependence test.
The issue is to identify candidates n and m in equalities, so as to test the bounds on m and match the property conditions. We will not assume cartesian constraints on the variables, but rather compute it by projection. We will use the gcd condition before projecting to find m bounds. By doing so, we may lose some instances if a variable is in fact a constant.
FC, Apr 09 1997.
Definition at line 130 of file sc_transformation.c.
References val_of, value_abs, and value_compare.
Referenced by sc_find_equalities().
void sc_find_equalities | ( | Psysteme * | ps | ) |
FOR EACH EQUALITY
the vector is sorted by increassing absolute coeffs. the the m/an separation is performed on a per-abs(coeff) basis.
BUILD POSSIBLE AN AND M (AN + M + C == 0)
accumulate next absolute coeff in m
insert head(an) in front of m
WITH AN, COMPUTES A AND CHECK A "GCD" CONDITION ???
break...
to WHILE(an)
COMPUTE M BOUNDS, IF ANY
kills ns
the system is not feasible.
well, if m is not bounded, the larger m won't be either, thus we can shorten the an loop...
break...
now, we must compute the shifts...
an + m + c == 0, vmin <= m <= vmax ; c = a d + r, 0 <= r < a, a (n+d) + (m+r) == 0, vmin+r <= m+r <= vmax+r, (vmax+r) = a d' + r', 0 <= r' < a, vmin+r-ad' <= (m+r-ad') <= r' < a
question: -a < vmin+r-ad ? if YES: m+r-ad'==0 and n+d+d'==0 assert: vmin+r-ad<=0 (or not feasible!)
c = a d + r
vmax' = a dp + rp
delta = -ad'
CONDITION |m|<a
an modified
INSERT m==0 [ahead] and n==0 [in place of the old one]
m pointed to
KEEPS ON WITH N AND resetted M
an == VECTEUR_NUL
Definition at line 136 of file sc_transformation.c.
References abscmp(), BASE_NULLE, base_rm, contrainte_make(), contrainte_vecteur, eq, sc_add_egalite(), sc_creer_base(), sc_dup(), sc_empty(), sc_minmax_of_variable(), sc_rm(), sc_transform_ineg_in_eg(), Scontrainte::succ, Svecteur::succ, TCST, val_of, value_abs, value_addto, value_eq, value_ge, value_lt, value_max_p, value_min_p, value_minus, VALUE_MONE, value_pdiv, value_plus, value_pmod, value_uminus, VALUE_ZERO, vect_add_elem(), vect_coeff(), vect_div(), vect_dup(), vect_erase_var(), vect_new(), vect_pgcd_all(), vect_rm(), vect_sort_in_place(), VECTEUR_NUL, and VECTEUR_NUL_P.
Referenced by hpf_remapping(), hpfc_algorithm_row_echelon(), and verify_array_variable().
void sc_transform_eg_in_ineg | ( | Psysteme | sc | ) |
Package sc.
Transform each equality in two inequalities
Definition at line 44 of file sc_transformation.c.
References contrainte_dup(), CONTRAINTE_UNDEFINED_P, contraintes_free(), sc_elim_db_constraints(), Scontrainte::succ, vect_chg_sgn(), and Scontrainte::vecteur.
Referenced by algorithm_row_echelon_generic(), build_third_comb(), create_farkas_poly(), do_check_isolate_statement_preconditions_on_call(), do_group_statement_constant(), do_isolate_statement_preconditions_satisified_p(), make_rectangular_area(), make_scanning_over_one_tile(), make_scanning_over_tiles(), pa_supress_same_constraints(), pa_transform_eg_in_ineg(), prepare_reindexing(), region_to_minimal_dimensions(), sc_elim_redund_with_first_ofl_ctrl(), sc_image_computation(), sc_supress_parallel_redund_constraints(), systeme_to_loop_nest(), variable_to_dimensions(), xml_Pattern_Paving(), xml_Region_Range(), and xml_tiling().
void sc_transform_ineg_in_eg | ( | Psysteme | sc | ) |
Transform the two constraints A.x <= b and -A.x <= -b of system sc into an equality A.x == b.
True if the constraints are opposed.
??? humm, the result is not returned
Definition at line 71 of file sc_transformation.c.
References contrainte_dup(), CONTRAINTE_UNDEFINED_P, eq_set_vect_nul(), sc_elim_double_constraints(), Scontrainte::succ, vect_add(), vect_rm(), Scontrainte::vecteur, and VECTEUR_NUL_P.
Referenced by algorithm_row_echelon_generic(), hpf_remapping(), sc_cute_convex_hull(), and sc_find_equalities().