| |
| /**-------------------------------------------------------------------** |
| ** 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; |
| } |