summaryrefslogtreecommitdiff
path: root/cloog-0.17.0/source/matrix/constraintset.c
diff options
context:
space:
mode:
Diffstat (limited to 'cloog-0.17.0/source/matrix/constraintset.c')
-rw-r--r--cloog-0.17.0/source/matrix/constraintset.c1056
1 files changed, 0 insertions, 1056 deletions
diff --git a/cloog-0.17.0/source/matrix/constraintset.c b/cloog-0.17.0/source/matrix/constraintset.c
deleted file mode 100644
index 78025f8..0000000
--- a/cloog-0.17.0/source/matrix/constraintset.c
+++ /dev/null
@@ -1,1056 +0,0 @@
-
- /**-------------------------------------------------------------------**
- ** CLooG **
- **-------------------------------------------------------------------**
- ** constraintset.c **
- **-------------------------------------------------------------------**
- ** First version: april 17th 2005 **
- **-------------------------------------------------------------------**/
-
-
-/******************************************************************************
- * CLooG : the Chunky Loop Generator (experimental) *
- ******************************************************************************
- * *
- * Copyright (C) 2005 Cedric Bastoul *
- * *
- * This library is free software; you can redistribute it and/or *
- * modify it under the terms of the GNU Lesser General Public *
- * License as published by the Free Software Foundation; either *
- * version 2.1 of the License, or (at your option) any later version. *
- * *
- * This library is distributed in the hope that it will be useful, *
- * but WITHOUT ANY WARRANTY; without even the implied warranty of *
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
- * Lesser General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this library; if not, write to the Free Software *
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
- * Boston, MA 02110-1301 USA *
- * *
- * CLooG, the Chunky Loop Generator *
- * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
- * *
- ******************************************************************************/
-/* CAUTION: the english used for comments is probably the worst you ever read,
- * please feel free to correct and improve it !
- */
-
-
-# include <stdlib.h>
-# include <stdio.h>
-# include <ctype.h>
-#include <cloog/cloog.h>
-#include <cloog/matrix/constraintset.h>
-
-
-#define ALLOC(type) (type*)malloc(sizeof(type))
-#define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
-
-
-CloogConstraint *cloog_constraint_first(CloogConstraintSet *constraints);
-CloogConstraint *cloog_constraint_next(CloogConstraint *constraint);
-
-
-CloogConstraintSet *cloog_constraint_set_from_cloog_matrix(CloogMatrix *M)
-{
- return (CloogConstraintSet *)M;
-}
-
-
-void cloog_constraint_set_free(CloogConstraintSet *constraints)
-{
- cloog_matrix_free(&constraints->M);
-}
-
-int cloog_constraint_set_contains_level(CloogConstraintSet *constraints,
- int level, int nb_parameters)
-{
- return constraints->M.NbColumns - 2 - nb_parameters >= level;
-}
-
-/* Check if the variable at position level is defined by an
- * equality. If so, return the row number. Otherwise, return -1.
- *
- * If there is an equality, we can print it directly -no ambiguity-.
- * PolyLib can give more than one equality, we use just the first one
- * (this is a PolyLib problem, but all equalities are equivalent).
- */
-CloogConstraint *cloog_constraint_set_defining_equality(CloogConstraintSet *constraints, int level)
-{
- CloogConstraint *constraint = ALLOC(CloogConstraint);
- int i;
-
- constraint->set = constraints;
- for (i = 0; i < constraints->M.NbRows; i++)
- if (cloog_int_is_zero(constraints->M.p[i][0]) &&
- !cloog_int_is_zero(constraints->M.p[i][level])) {
- constraint->line = &constraints->M.p[i];
- return constraint;
- }
- free(constraint);
- return cloog_constraint_invalid();
-}
-
-/* Check if the variable (e) at position level is defined by a
- * pair of inequalities
- * <a, i> + -m e + <b, p> + k1 >= 0
- * <-a, i> + m e + <-b, p> + k2 >= 0
- * with 0 <= k1 + k2 < m
- * If so return the row number of the upper bound and set *lower
- * to the row number of the lower bound. If not, return -1.
- *
- * If the variable at position level occurs in any other constraint,
- * then we currently return -1. The modulo guard that we would generate
- * would still be correct, but we would also need to generate
- * guards corresponding to the other constraints, and this has not
- * been implemented yet.
- */
-CloogConstraint *cloog_constraint_set_defining_inequalities(CloogConstraintSet *constraints,
- int level, CloogConstraint **lower, int nb_par)
-{
- int i, j, k;
- cloog_int_t m;
- CloogMatrix *matrix = &constraints->M;
- unsigned len = matrix->NbColumns - 2;
- unsigned nb_iter = len - nb_par;
- CloogConstraint *constraint;
-
- for (i = 0; i < matrix->NbRows; i++) {
- if (cloog_int_is_zero(matrix->p[i][level]))
- continue;
- if (cloog_int_is_zero(matrix->p[i][0]))
- return cloog_constraint_invalid();
- if (cloog_int_is_one(matrix->p[i][level]))
- return cloog_constraint_invalid();
- if (cloog_int_is_neg_one(matrix->p[i][level]))
- return cloog_constraint_invalid();
- if (cloog_seq_first_non_zero(matrix->p[i]+level+1,
- (1+nb_iter)-(level+1)) != -1)
- return cloog_constraint_invalid();
- for (j = i+1; j < matrix->NbRows; ++j) {
- if (cloog_int_is_zero(matrix->p[j][level]))
- continue;
- if (cloog_int_is_zero(matrix->p[j][0]))
- return cloog_constraint_invalid();
- if (cloog_int_is_one(matrix->p[j][level]))
- return cloog_constraint_invalid();
- if (cloog_int_is_neg_one(matrix->p[j][level]))
- return cloog_constraint_invalid();
- if (cloog_seq_first_non_zero(matrix->p[j]+level+1,
- (1+nb_iter)-(level+1)) != -1)
- return cloog_constraint_invalid();
-
- cloog_int_init(m);
- cloog_int_add(m, matrix->p[i][1+len], matrix->p[j][1+len]);
- if (cloog_int_is_neg(m) ||
- cloog_int_abs_ge(m, matrix->p[i][level])) {
- cloog_int_clear(m);
- return cloog_constraint_invalid();
- }
- cloog_int_clear(m);
-
- if (!cloog_seq_is_neg(matrix->p[i]+1, matrix->p[j]+1,
- len))
- return cloog_constraint_invalid();
- for (k = j+1; k < matrix->NbRows; ++k)
- if (!cloog_int_is_zero(matrix->p[k][level]))
- return cloog_constraint_invalid();
- *lower = ALLOC(CloogConstraint);
- constraint = ALLOC(CloogConstraint);
- (*lower)->set = constraints;
- constraint->set = constraints;
- if (cloog_int_is_pos(matrix->p[i][level])) {
- (*lower)->line = &matrix->p[i];
- constraint->line = &matrix->p[j];
- } else {
- (*lower)->line = &matrix->p[j];
- constraint->line = &matrix->p[i];
- }
- return constraint;
- }
- }
- return cloog_constraint_invalid();
-}
-
-int cloog_constraint_set_total_dimension(CloogConstraintSet *constraints)
-{
- return constraints->M.NbColumns - 2;
-}
-
-int cloog_constraint_set_n_iterators(CloogConstraintSet *constraint, int nb_par)
-{
- return cloog_constraint_set_total_dimension(constraint) - nb_par;
-}
-
-int cloog_equal_total_dimension(CloogEqualities *equal)
-{
- return cloog_constraint_set_total_dimension(equal->constraints);
-}
-
-int cloog_constraint_total_dimension(CloogConstraint *constraint)
-{
- return cloog_constraint_set_total_dimension(constraint->set);
-}
-
-
-
-/******************************************************************************
- * Equalities spreading functions *
- ******************************************************************************/
-
-
-/* Equalities are stored inside a CloogMatrix data structure called "equal".
- * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
- * dimensions + 1, the "+ 1" is because a statement can be included inside an
- * external loop without iteration domain), and (nb_scattering + nb_iterators +
- * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
- * type). The ith row corresponds to the equality "= 0" for the ith dimension
- * iterator. The first column gives the equality type (0: no equality, then
- * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
- * the current level is found, the corresponding row is updated. Then the
- * equality if it exists is used to simplify expressions (e.g. if we have
- * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
- * the pprint call, the corresponding row is reset to zero.
- */
-
-CloogEqualities *cloog_equal_alloc(int n, int nb_levels,
- int nb_parameters)
-{
- int i;
- CloogEqualities *equal = ALLOC(CloogEqualities);
-
- equal->constraints = cloog_constraint_set_from_cloog_matrix(
- cloog_matrix_alloc(n, nb_levels + nb_parameters + 1));
- equal->types = ALLOCN(int, n);
- for (i = 0; i < n; ++i)
- equal->types[i] = EQTYPE_NONE;
- return equal;
-}
-
-void cloog_equal_free(CloogEqualities *equal)
-{
- cloog_matrix_free(&equal->constraints->M);
- free(equal->types);
- free(equal);
-}
-
-int cloog_equal_count(CloogEqualities *equal)
-{
- return equal->constraints->M.NbRows;
-}
-
-CloogConstraintSet *cloog_equal_constraints(CloogEqualities *equal)
-{
- return equal->constraints;
-}
-
-
-/**
- * cloog_constraint_equal_type function :
- * This function returns the type of the equality in the constraint (line) of
- * (constraints) for the element (level). An equality is 'constant' iff all
- * other factors are null except the constant one. It is a 'pure item' iff
- * it is equal or opposite to a single variable or parameter.
- * Otherwise it is an 'affine expression'.
- * For instance:
- * i = -13 is constant, i = j, j = -M are pure items,
- * j = 2*M, i = j+1, 2*j = M are affine expressions.
- *
- * - constraints is the matrix of constraints,
- * - level is the column number in equal of the element which is 'equal to',
- **
- * - July 3rd 2002: first version, called pprint_equal_isconstant.
- * - July 6th 2002: adaptation for the 3 types.
- * - June 15th 2005: (debug) expr = domain->Constraint[line] was evaluated
- * before checking if line != ONE_TIME_LOOP. Since
- * ONE_TIME_LOOP is -1, an invalid read was possible.
- * - October 19th 2005: Removal of the once-time-loop specific processing.
- */
-static int cloog_constraint_equal_type(CloogConstraint *constraint, int level)
-{
- int i, one=0 ;
- cloog_int_t *expr;
-
- expr = *constraint->line;
-
- if (!cloog_int_is_one(expr[level]) && !cloog_int_is_neg_one(expr[level]))
- return EQTYPE_EXAFFINE;
-
- /* There is only one non null factor, and it must be +1 or -1 for
- * iterators or parameters.
- */
- for (i = 1;i <= constraint->set->M.NbColumns-2; i++)
- if (!cloog_int_is_zero(expr[i]) && (i != level)) {
- if ((!cloog_int_is_one(expr[i]) && !cloog_int_is_neg_one(expr[i])) || (one != 0))
- return EQTYPE_EXAFFINE ;
- else
- one = 1 ;
- }
- /* if the constant factor is non null, it must be alone. */
- if (one != 0) {
- if (!cloog_int_is_zero(expr[constraint->set->M.NbColumns-1]))
- return EQTYPE_EXAFFINE ;
- }
- else
- return EQTYPE_CONSTANT ;
-
- return EQTYPE_PUREITEM ;
-}
-
-
-int cloog_equal_type(CloogEqualities *equal, int level)
-{
- return equal->types[level-1];
-}
-
-
-/**
- * cloog_equal_update function:
- * this function updates a matrix of equalities where each row corresponds to
- * the equality "=0" of an affine expression such that the entry at column
- * "row" (="level") is not zero. This matrix is upper-triangular, except the
- * row number "level-1" which has to be updated for the matrix to be triangular.
- * This function achieves the processing.
- * - equal is the matrix to be updated,
- * - level gives the row that has to be updated (it is actually row "level-1"),
- * - nb_par is the number of parameters of the program.
- **
- * - September 20th 2005: first version.
- */
-static void cloog_equal_update(CloogEqualities *equal, int level, int nb_par)
-{ int i, j ;
- cloog_int_t gcd, factor_level, factor_outer, temp_level, temp_outer;
-
- cloog_int_init(gcd);
- cloog_int_init(temp_level);
- cloog_int_init(temp_outer);
- cloog_int_init(factor_level);
- cloog_int_init(factor_outer);
-
- /* For each previous level, */
- for (i=level-2;i>=0;i--)
- { /* if the corresponding iterator is inside the current equality and is equal
- * to something,
- */
- if (!cloog_int_is_zero(equal->constraints->M.p[level-1][i+1]) && equal->types[i])
- { /* Compute the Greatest Common Divisor. */
- cloog_int_gcd(gcd, equal->constraints->M.p[level-1][i+1],
- equal->constraints->M.p[i][i+1]);
-
- /* Compute the factors to apply to each row vector element. */
- cloog_int_divexact(factor_level, equal->constraints->M.p[i][i+1], gcd);
- cloog_int_divexact(factor_outer, equal->constraints->M.p[level-1][i+1], gcd);
-
- /* Now update the row 'level'. */
- /* - the iterators, up to level, */
- for (j = 1; j <= level; j++) {
- cloog_int_mul(temp_level, factor_level,
- equal->constraints->M.p[level-1][j]);
- cloog_int_mul(temp_outer, factor_outer, equal->constraints->M.p[i][j]);
- cloog_int_sub(equal->constraints->M.p[level-1][j], temp_level, temp_outer);
- }
- /* - between last useful iterator (level) and the first parameter, the
- * matrix is sparse (full of zeroes), we just do nothing there.
- * - the parameters and the scalar.
- */
- for (j = 0; j < nb_par + 1; j++) {
- cloog_int_mul(temp_level,factor_level,
- equal->constraints->M.p[level-1]
- [equal->constraints->M.NbColumns-j-1]);
- cloog_int_mul(temp_outer,factor_outer,
- equal->constraints->M.p[i][equal->constraints->M.NbColumns-j-1]);
- cloog_int_sub(equal->constraints->M.p[level-1]
- [equal->constraints->M.NbColumns-j-1],
- temp_level,temp_outer) ;
- }
- }
- }
-
- /* Normalize (divide by GCD of all elements) the updated equality. */
- cloog_seq_normalize(&(equal->constraints->M.p[level-1][1]),
- equal->constraints->M.NbColumns-1);
-
- cloog_int_clear(gcd);
- cloog_int_clear(temp_level);
- cloog_int_clear(temp_outer);
- cloog_int_clear(factor_level);
- cloog_int_clear(factor_outer);
-}
-
-
-/**
- * cloog_equal_add function:
- * This function updates the row (level-1) of the equality matrix (equal) with
- * the row that corresponds to the row (line) of the matrix (matrix).
- * - equal is the matrix of equalities,
- * - matrix is the matrix of constraints,
- * - level is the column number in matrix of the element which is 'equal to',
- * - line is the line number in matrix of the constraint we want to study,
- * - the infos structure gives the user all options on code printing and more.
- **
- * - July 2nd 2002: first version.
- * - October 19th 2005: Addition of the once-time-loop specific processing.
- */
-void cloog_equal_add(CloogEqualities *equal, CloogConstraintSet *constraints,
- int level, CloogConstraint *line, int nb_par)
-{
- int j;
- CloogConstraint *i = cloog_constraint_invalid();
- CloogMatrix *matrix = &constraints->M;
-
- /* If we are in the case of a loop running once, this means that the equality
- * comes from an inequality. Here we find this inequality.
- */
- if (!cloog_constraint_is_valid(line))
- { for (i = cloog_constraint_first(constraints);
- cloog_constraint_is_valid(i); i = cloog_constraint_next(i))
- if ((!cloog_int_is_zero(i->line[0][0]))&& (!cloog_int_is_zero(i->line[0][level])))
- { line = i ;
-
- /* Since in once-time-loops, equalities derive from inequalities, we
- * may have to offset the values. For instance if we have 2i>=3, the
- * equality is in fact i=2. This may happen when the level coefficient is
- * not 1 or -1 and the scalar value is not zero. In any other case (e.g.,
- * if the inequality is an expression including outer loop counters or
- * parameters) the once time loop would not have been detected
- * because of floord and ceild functions.
- */
- if (cloog_int_ne_si(i->line[0][level],1) &&
- cloog_int_ne_si(i->line[0][level],-1) &&
- !cloog_int_is_zero(i->line[0][matrix->NbColumns-1])) {
- cloog_int_t denominator;
-
- cloog_int_init(denominator);
- cloog_int_abs(denominator, i->line[0][level]);
- cloog_int_fdiv_q(i->line[0][matrix->NbColumns-1],
- i->line[0][matrix->NbColumns-1], denominator);
- cloog_int_set_si(i->line[0][level], cloog_int_sgn(i->line[0][level]));
- cloog_int_clear(denominator);
- }
-
- break ;
- }
- }
- assert(cloog_constraint_is_valid(line));
-
- /* We update the line of equal corresponding to level:
- * - the first element gives the equality type,
- */
- equal->types[level-1] = cloog_constraint_equal_type(line, level);
- /* - the other elements corresponding to the equality itself
- * (the iterators up to level, then the parameters and the scalar).
- */
- for (j=1;j<=level;j++)
- cloog_int_set(equal->constraints->M.p[level-1][j], line->line[0][j]);
- for (j = 0; j < nb_par + 1; j++)
- cloog_int_set(equal->constraints->M.p[level-1][equal->constraints->M.NbColumns-j-1],
- line->line[0][line->set->M.NbColumns-j-1]);
-
- if (cloog_constraint_is_valid(i))
- cloog_constraint_release(line);
- cloog_equal_update(equal, level, nb_par);
-}
-
-
-/**
- * cloog_equal_del function :
- * This function reset the equality corresponding to the iterator (level)
- * in the equality matrix (equal).
- * - July 2nd 2002: first version.
- */
-void cloog_equal_del(CloogEqualities *equal, int level)
-{
- equal->types[level-1] = EQTYPE_NONE;
-}
-
-
-
-/******************************************************************************
- * Processing functions *
- ******************************************************************************/
-
-/**
- * Function cloog_constraint_set_normalize:
- * This function will modify the constraint system in such a way that when
- * there is an equality depending on the element at level 'level', there are
- * no more (in)equalities depending on this element. For instance, try
- * test/valilache.cloog with options -f 8 -l 9, with and without the call
- * to this function. At a given moment, for the level L we will have
- * 32*P=L && L>=1 (P is a lower level), this constraint system cannot be
- * translated directly into a source code. Thus, we normalize the domain to
- * remove L from the inequalities. In our example, this leads to
- * 32*P=L && 32*P>=1, that can be transated to the code
- * if (P>=1) { L=32*P ; ... }. This function solves the DaeGon Kim bug.
- * WARNING: Remember that if there is another call to Polylib after a call to
- * this function, we have to recall this function.
- * -June 16th 2005: first version (adaptation from URGent June-7th-2005 by
- * N. Vasilache).
- * - June 21rd 2005: Adaptation for GMP.
- * - November 4th 2005: Complete rewriting, simpler and faster. It is no more an
- * adaptation from URGent.
- */
-void cloog_constraint_set_normalize(CloogConstraintSet *constraints, int level)
-{ int ref, i, j ;
- cloog_int_t factor_i, factor_ref, temp_i, temp_ref, gcd;
- CloogMatrix *matrix = &constraints->M;
-
- if (matrix == NULL)
- return ;
-
- /* Don't "normalize" the constant term. */
- if (level == matrix->NbColumns-1)
- return;
-
- /* Let us find an equality for the current level that can be propagated. */
- for (ref=0;ref<matrix->NbRows;ref++)
- if (cloog_int_is_zero(matrix->p[ref][0]) && !cloog_int_is_zero(matrix->p[ref][level])) {
- cloog_int_init(gcd);
- cloog_int_init(temp_i);
- cloog_int_init(temp_ref);
- cloog_int_init(factor_i);
- cloog_int_init(factor_ref);
-
- /* Row "ref" is the reference equality, now let us find a row to simplify.*/
- for (i=ref+1;i<matrix->NbRows;i++)
- if (!cloog_int_is_zero(matrix->p[i][level])) {
- /* Now let us set to 0 the "level" coefficient of row "j" using "ref".
- * First we compute the factors to apply to each row vector element.
- */
- cloog_int_gcd(gcd, matrix->p[ref][level], matrix->p[i][level]);
- cloog_int_divexact(factor_i, matrix->p[ref][level], gcd);
- cloog_int_divexact(factor_ref, matrix->p[i][level], gcd);
-
- /* Maybe we are simplifying an inequality: factor_i must not be <0. */
- if (cloog_int_is_neg(factor_i)) {
- cloog_int_abs(factor_i, factor_i);
- cloog_int_neg(factor_ref, factor_ref);
- }
-
- /* Now update the vector. */
- for (j=1;j<matrix->NbColumns;j++) {
- cloog_int_mul(temp_i, factor_i, matrix->p[i][j]);
- cloog_int_mul(temp_ref, factor_ref, matrix->p[ref][j]);
- cloog_int_sub(matrix->p[i][j], temp_i, temp_ref);
- }
-
- /* Normalize (divide by GCD of all elements) the updated vector. */
- cloog_seq_normalize(&(matrix->p[i][1]), matrix->NbColumns-1);
- }
-
- cloog_int_clear(gcd);
- cloog_int_clear(temp_i);
- cloog_int_clear(temp_ref);
- cloog_int_clear(factor_i);
- cloog_int_clear(factor_ref);
- break ;
- }
-}
-
-
-
-/**
- * cloog_constraint_set_copy function:
- * this functions builds and returns a "hard copy" (not a pointer copy) of a
- * CloogMatrix data structure.
- * - October 26th 2005: first version.
- */
-CloogConstraintSet *cloog_constraint_set_copy(CloogConstraintSet *constraints)
-{ int i, j ;
- CloogMatrix *copy;
- CloogMatrix *matrix = &constraints->M;
-
- copy = cloog_matrix_alloc(matrix->NbRows, matrix->NbColumns);
-
- for (i=0;i<matrix->NbRows;i++)
- for (j=0;j<matrix->NbColumns;j++)
- cloog_int_set(copy->p[i][j], matrix->p[i][j]);
-
- return cloog_constraint_set_from_cloog_matrix(copy);
-}
-
-
-/**
- * cloog_equal_vector_simplify function:
- * this function simplify an affine expression with its coefficients in
- * "vector" of length "length" thanks to an equality matrix "equal" that gives
- * for some elements of the affine expression an equality with other elements,
- * preferably constants. For instance, if the vector contains i+j+3 and the
- * equality matrix gives i=n and j=2, the vector is simplified to n+3 and is
- * returned in a new vector.
- * - vector is the array of affine expression coefficients
- * - equal is the matrix of equalities,
- * - length is the vector length,
- * - level is a level we don't want to simplify (-1 if none),
- * - nb_par is the number of parameters of the program.
- **
- * - September 20th 2005: first version.
- * - November 2nd 2005: (debug) we are simplifying inequalities, thus we are
- * not allowed to multiply the vector by a negative
- * constant.Problem found after a report of Michael
- * Classen.
- */
-struct cloog_vec *cloog_equal_vector_simplify(CloogEqualities *equal, cloog_int_t *vector,
- int length, int level, int nb_par)
-{ int i, j ;
- cloog_int_t gcd, factor_vector, factor_equal, temp_vector, temp_equal;
- struct cloog_vec *simplified;
-
- simplified = cloog_vec_alloc(length);
- cloog_seq_cpy(simplified->p, vector, length);
-
- cloog_int_init(gcd);
- cloog_int_init(temp_vector);
- cloog_int_init(temp_equal);
- cloog_int_init(factor_vector);
- cloog_int_init(factor_equal);
-
- /* For each non-null coefficient in the vector, */
- for (i=length-nb_par-2;i>0;i--)
- if (i != level)
- { /* if the coefficient in not null, and there exists a useful equality */
- if ((!cloog_int_is_zero(simplified->p[i])) && equal->types[i-1])
- { /* Compute the Greatest Common Divisor. */
- cloog_int_gcd(gcd, simplified->p[i], equal->constraints->M.p[i-1][i]);
-
- /* Compute the factors to apply to each row vector element. */
- cloog_int_divexact(factor_vector, equal->constraints->M.p[i-1][i], gcd);
- cloog_int_divexact(factor_equal, simplified->p[i], gcd);
-
- /* We are simplifying an inequality: factor_vector must not be <0. */
- if (cloog_int_is_neg(factor_vector)) {
- cloog_int_abs(factor_vector, factor_vector);
- cloog_int_neg(factor_equal, factor_equal);
- }
-
- /* Now update the vector. */
- /* - the iterators, up to the current level, */
- for (j=1;j<=length-nb_par-2;j++) {
- cloog_int_mul(temp_vector, factor_vector, simplified->p[j]);
- cloog_int_mul(temp_equal, factor_equal, equal->constraints->M.p[i-1][j]);
- cloog_int_sub(simplified->p[j], temp_vector, temp_equal);
- }
- /* - between last useful iterator (i) and the first parameter, the equal
- * matrix is sparse (full of zeroes), we just do nothing there.
- * - the parameters and the scalar.
- */
- for (j = 0; j < nb_par + 1; j++) {
- cloog_int_mul(temp_vector, factor_vector, simplified->p[length-1-j]);
- cloog_int_mul(temp_equal,factor_equal,
- equal->constraints->M.p[i-1][equal->constraints->M.NbColumns-j-1]);
- cloog_int_sub(simplified->p[length-1-j],temp_vector,temp_equal) ;
- }
- }
- }
-
- /* Normalize (divide by GCD of all elements) the updated vector. */
- cloog_seq_normalize(&simplified->p[1], length - 1);
-
- cloog_int_clear(gcd);
- cloog_int_clear(temp_vector);
- cloog_int_clear(temp_equal);
- cloog_int_clear(factor_vector);
- cloog_int_clear(factor_equal);
-
- return simplified ;
-}
-
-
-/**
- * cloog_constraint_set_simplify function:
- * this function simplify all constraints inside the matrix "matrix" thanks to
- * an equality matrix "equal" that gives for some elements of the affine
- * constraint an equality with other elements, preferably constants.
- * For instance, if a row of the matrix contains i+j+3>=0 and the equality
- * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
- * simplified constraints are returned back inside a new simplified matrix.
- * - matrix is the set of constraints to simplify,
- * - equal is the matrix of equalities,
- * - level is a level we don't want to simplify (-1 if none),
- * - nb_par is the number of parameters of the program.
- **
- * - November 4th 2005: first version.
- */
-CloogConstraintSet *cloog_constraint_set_simplify(CloogConstraintSet *constraints,
- CloogEqualities *equal, int level, int nb_par)
-{ int i, j, k ;
- struct cloog_vec *vector;
- CloogMatrix *simplified;
- CloogMatrix *matrix = &constraints->M;
-
- if (matrix == NULL)
- return NULL ;
-
- /* The simplified matrix is such that each row has been simplified thanks
- * tho the "equal" matrix. We allocate the memory for the simplified matrix,
- * then for each row of the original matrix, we compute the simplified
- * vector and we copy its content into the according simplified row.
- */
- simplified = cloog_matrix_alloc(matrix->NbRows, matrix->NbColumns);
- for (i=0;i<matrix->NbRows;i++)
- { vector = cloog_equal_vector_simplify(equal, matrix->p[i],
- matrix->NbColumns, level, nb_par);
- for (j=0;j<matrix->NbColumns;j++)
- cloog_int_set(simplified->p[i][j], vector->p[j]);
-
- cloog_vec_free(vector);
- }
-
- /* After simplification, it may happen that few constraints are the same,
- * we remove them here by replacing them with 0=0 constraints.
- */
- for (i=0;i<simplified->NbRows;i++)
- for (j=i+1;j<simplified->NbRows;j++)
- { for (k=0;k<simplified->NbColumns;k++)
- if (cloog_int_ne(simplified->p[i][k],simplified->p[j][k]))
- break ;
-
- if (k == matrix->NbColumns)
- { for (k=0;k<matrix->NbColumns;k++)
- cloog_int_set_si(simplified->p[j][k],0);
- }
- }
-
- return cloog_constraint_set_from_cloog_matrix(simplified);
-}
-
-
-/**
- * Return clast_expr corresponding to the variable "level" (1 based) in
- * the given constraint.
- */
-struct clast_expr *cloog_constraint_variable_expr(CloogConstraint *constraint,
- int level, CloogNames *names)
-{
- int total_dim, nb_iter;
- const char *name;
-
- total_dim = cloog_constraint_total_dimension(constraint);
- nb_iter = total_dim - names->nb_parameters;
-
- if (level <= nb_iter)
- name = cloog_names_name_at_level(names, level);
- else
- name = names->parameters[level - (nb_iter+1)] ;
-
- return &new_clast_name(name)->expr;
-}
-
-
-/**
- * Return true if constraint c involves variable v (zero-based).
- */
-int cloog_constraint_involves(CloogConstraint *constraint, int v)
-{
- return !cloog_int_is_zero(constraint->line[0][1+v]);
-}
-
-int cloog_constraint_is_lower_bound(CloogConstraint *constraint, int v)
-{
- return cloog_int_is_pos(constraint->line[0][1+v]);
-}
-
-int cloog_constraint_is_upper_bound(CloogConstraint *constraint, int v)
-{
- return cloog_int_is_neg(constraint->line[0][1+v]);
-}
-
-int cloog_constraint_is_equality(CloogConstraint *constraint)
-{
- return cloog_int_is_zero(constraint->line[0][0]);
-}
-
-void cloog_constraint_clear(CloogConstraint *constraint)
-{
- int k;
-
- for (k = 1; k <= constraint->set->M.NbColumns - 2; k++)
- cloog_int_set_si(constraint->line[0][k], 0);
-}
-
-CloogConstraintSet *cloog_constraint_set_drop_constraint(
- CloogConstraintSet *constraints, CloogConstraint *constraint)
-{
- cloog_constraint_clear(constraint);
- return constraints;
-}
-
-void cloog_constraint_coefficient_get(CloogConstraint *constraint,
- int var, cloog_int_t *val)
-{
- cloog_int_set(*val, constraint->line[0][1+var]);
-}
-
-void cloog_constraint_coefficient_set(CloogConstraint *constraint,
- int var, cloog_int_t val)
-{
- cloog_int_set(constraint->line[0][1+var], val);
-}
-
-void cloog_constraint_constant_get(CloogConstraint *constraint, cloog_int_t *val)
-{
- cloog_int_set(*val, constraint->line[0][constraint->set->M.NbColumns-1]);
-}
-
-/**
- * Copy the coefficient of constraint c into dst in PolyLib order,
- * i.e., first the coefficients of the variables, then the coefficients
- * of the parameters and finally the constant.
- */
-void cloog_constraint_copy_coefficients(CloogConstraint *constraint,
- cloog_int_t *dst)
-{
- cloog_seq_cpy(dst, constraint->line[0]+1, constraint->set->M.NbColumns-1);
-}
-
-CloogConstraint *cloog_constraint_invalid(void)
-{
- return NULL;
-}
-
-int cloog_constraint_is_valid(CloogConstraint *constraint)
-{
- return constraint != NULL;
-}
-
-
-/**
- * Check whether there is any need for the constraint "upper" on
- * "level" to get reduced.
- * Yes.
- */
-int cloog_constraint_needs_reduction(CloogConstraint *upper, int level)
-{
- return 1;
-}
-
-
-/**
- * Create a CloogConstraintSet containing enough information to perform
- * a reduction on the upper equality (in this case lower is an invalid
- * CloogConstraint) or the pair of inequalities upper and lower
- * from within insert_modulo_guard.
- * In the PolyLib backend, we return a CloogConstraintSet containting only
- * the upper bound. The reduction will not change the stride so there
- * will be no need to recompute the bound on the modulo expression.
- */
-CloogConstraintSet *cloog_constraint_set_for_reduction(CloogConstraint *upper,
- CloogConstraint *lower)
-{
- CloogConstraintSet *set;
-
- set = cloog_constraint_set_from_cloog_matrix(
- cloog_matrix_alloc(1, upper->set->M.NbColumns));
- cloog_seq_cpy(set->M.p[0], upper->line[0], set->M.NbColumns);
- return set;
-}
-
-
-/* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
-static void Euclid(cloog_int_t a, cloog_int_t b,
- cloog_int_t *x, cloog_int_t *y, cloog_int_t *g)
-{
- cloog_int_t c, d, e, f, tmp;
-
- cloog_int_init(c);
- cloog_int_init(d);
- cloog_int_init(e);
- cloog_int_init(f);
- cloog_int_init(tmp);
- cloog_int_abs(c, a);
- cloog_int_abs(d, b);
- cloog_int_set_si(e, 1);
- cloog_int_set_si(f, 0);
- while (cloog_int_is_pos(d)) {
- cloog_int_tdiv_q(tmp, c, d);
- cloog_int_mul(tmp, tmp, f);
- cloog_int_sub(e, e, tmp);
- cloog_int_tdiv_q(tmp, c, d);
- cloog_int_mul(tmp, tmp, d);
- cloog_int_sub(c, c, tmp);
- cloog_int_swap(c, d);
- cloog_int_swap(e, f);
- }
- cloog_int_set(*g, c);
- if (cloog_int_is_zero(a))
- cloog_int_set_si(*x, 0);
- else if (cloog_int_is_pos(a))
- cloog_int_set(*x, e);
- else cloog_int_neg(*x, e);
- if (cloog_int_is_zero(b))
- cloog_int_set_si(*y, 0);
- else {
- cloog_int_mul(tmp, a, *x);
- cloog_int_sub(tmp, c, tmp);
- cloog_int_divexact(*y, tmp, b);
- }
- cloog_int_clear(c);
- cloog_int_clear(d);
- cloog_int_clear(e);
- cloog_int_clear(f);
- cloog_int_clear(tmp);
-}
-
-/**
- * Reduce the modulo guard expressed by "contraints" using equalities
- * found in outer nesting levels (stored in "equal").
- * The modulo guard may be an equality or a pair of inequalities.
- * In case of a pair of inequalities, "constraints" only contains the
- * upper bound and *bound contains the bound on the
- * corresponding modulo expression. The bound is left untouched by
- * this function.
- */
-CloogConstraintSet *cloog_constraint_set_reduce(CloogConstraintSet *constraints,
- int level, CloogEqualities *equal, int nb_par, cloog_int_t *bound)
-{
- int i, j, k, len, len2, nb_iter;
- struct cloog_vec *line_vector2;
- cloog_int_t *line, *line2, val, x, y, g;
-
- len = constraints->M.NbColumns;
- len2 = cloog_equal_total_dimension(equal) + 2;
- nb_iter = len - 2 - nb_par;
-
- cloog_int_init(val);
- cloog_int_init(x);
- cloog_int_init(y);
- cloog_int_init(g);
-
- line_vector2 = cloog_vec_alloc(len2);
- line2 = line_vector2->p;
-
- line = constraints->M.p[0];
- if (cloog_int_is_pos(line[level]))
- cloog_seq_neg(line+1, line+1, len-1);
- cloog_int_neg(line[level], line[level]);
- assert(cloog_int_is_pos(line[level]));
-
- for (i = nb_iter; i >= 1; --i) {
- if (i == level)
- continue;
- cloog_int_fdiv_r(line[i], line[i], line[level]);
- if (cloog_int_is_zero(line[i]))
- continue;
-
- /* Look for an earlier variable that is also a multiple of line[level]
- * and check whether we can use the corresponding affine expression
- * to "reduce" the modulo guard, where reduction means that we eliminate
- * a variable, possibly at the expense of introducing other variables
- * with smaller index.
- */
- for (j = level-1; j >= 0; --j) {
- CloogConstraint *equal_constraint;
- if (cloog_equal_type(equal, j+1) != EQTYPE_EXAFFINE)
- continue;
- equal_constraint = cloog_equal_constraint(equal, j);
- cloog_constraint_coefficient_get(equal_constraint, j, &val);
- if (!cloog_int_is_divisible_by(val, line[level])) {
- cloog_constraint_release(equal_constraint);
- continue;
- }
- cloog_constraint_coefficient_get(equal_constraint, i-1, &val);
- if (cloog_int_is_divisible_by(val, line[level])) {
- cloog_constraint_release(equal_constraint);
- continue;
- }
- for (k = j; k > i; --k) {
- cloog_constraint_coefficient_get(equal_constraint, k-1, &val);
- if (cloog_int_is_zero(val))
- continue;
- if (!cloog_int_is_divisible_by(val, line[level]))
- break;
- }
- if (k > i) {
- cloog_constraint_release(equal_constraint);
- continue;
- }
- cloog_constraint_coefficient_get(equal_constraint, i-1, &val);
- Euclid(val, line[level], &x, &y, &g);
- if (!cloog_int_is_divisible_by(val, line[i])) {
- cloog_constraint_release(equal_constraint);
- continue;
- }
- cloog_int_divexact(val, line[i], g);
- cloog_int_neg(val, val);
- cloog_int_mul(val, val, x);
- cloog_int_set_si(y, 1);
- /* Add (equal->p[j][i])^{-1} * line[i] times the equality */
- cloog_constraint_copy_coefficients(equal_constraint, line2+1);
- cloog_seq_combine(line+1, y, line+1, val, line2+1, i);
- cloog_seq_combine(line+len-nb_par-1, y, line+len-nb_par-1,
- val, line2+len2-nb_par-1, nb_par+1);
- cloog_constraint_release(equal_constraint);
- break;
- }
- }
-
- cloog_vec_free(line_vector2);
-
- cloog_int_clear(val);
- cloog_int_clear(x);
- cloog_int_clear(y);
- cloog_int_clear(g);
-
- /* Make sure the line is not inverted again in the calling function. */
- cloog_int_neg(line[level], line[level]);
-
- return constraints;
-}
-
-CloogConstraint *cloog_constraint_first(CloogConstraintSet *constraints)
-{
- CloogConstraint *c;
- if (constraints->M.NbRows == 0)
- return cloog_constraint_invalid();
- c = ALLOC(CloogConstraint);
- c->set = constraints;
- c->line = &constraints->M.p[0];
- return c;
-}
-
-CloogConstraint *cloog_constraint_next(CloogConstraint *constraint)
-{
- constraint->line++;
- if (constraint->line == constraint->set->M.p + constraint->set->M.NbRows) {
- cloog_constraint_release(constraint);
- return NULL;
- }
- return constraint;
-}
-
-CloogConstraint *cloog_constraint_copy(CloogConstraint *constraint)
-{
- CloogConstraint *c = ALLOC(CloogConstraint);
- c->set = constraint->set;
- c->line = constraint->line;
- return c;
-}
-
-void cloog_constraint_release(CloogConstraint *constraint)
-{
- free(constraint);
-}
-
-int cloog_constraint_set_foreach_constraint(CloogConstraintSet *constraints,
- int (*fn)(CloogConstraint *constraint, void *user), void *user)
-{
- CloogConstraint *c;
-
- for (c = cloog_constraint_first(constraints);
- cloog_constraint_is_valid(c); c = cloog_constraint_next(c))
- if (fn(c, user) < 0) {
- cloog_constraint_release(c);
- return -1;
- }
-
- return 0;
-}
-
-CloogConstraint *cloog_equal_constraint(CloogEqualities *equal, int j)
-{
- CloogConstraint *c = ALLOC(CloogConstraint);
- c->set = equal->constraints;
- c->line = &equal->constraints->M.p[j];
- return c;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-02 02:55:31 +0000