/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France */ #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl_seq.h> #include "isl_map_private.h" #include "isl_equalities.h" #include <isl_val_private.h> /* Given a set of modulo constraints * * c + A y = 0 mod d * * this function computes a particular solution y_0 * * The input is given as a matrix B = [ c A ] and a vector d. * * The output is matrix containing the solution y_0 or * a zero-column matrix if the constraints admit no integer solution. * * The given set of constrains is equivalent to * * c + A y = -D x * * with D = diag d and x a fresh set of variables. * Reducing both c and A modulo d does not change the * value of y in the solution and may lead to smaller coefficients. * Let M = [ D A ] and [ H 0 ] = M U, the Hermite normal form of M. * Then * [ x ] * M [ y ] = - c * and so * [ x ] * [ H 0 ] U^{-1} [ y ] = - c * Let * [ A ] [ x ] * [ B ] = U^{-1} [ y ] * then * H A + 0 B = -c * * so B may be chosen arbitrarily, e.g., B = 0, and then * * [ x ] = [ -c ] * U^{-1} [ y ] = [ 0 ] * or * [ x ] [ -c ] * [ y ] = U [ 0 ] * specifically, * * y = U_{2,1} (-c) * * If any of the coordinates of this y are non-integer * then the constraints admit no integer solution and * a zero-column matrix is returned. */ static __isl_give isl_mat *particular_solution(__isl_keep isl_mat *B, __isl_keep isl_vec *d) { … } /* Compute and return the matrix * * U_1^{-1} diag(d_1, 1, ..., 1) * * with U_1 the unimodular completion of the first (and only) row of B. * The columns of this matrix generate the lattice that satisfies * the single (linear) modulo constraint. */ static __isl_take isl_mat *parameter_compression_1(__isl_keep isl_mat *B, __isl_keep isl_vec *d) { … } /* Compute a common lattice of solutions to the linear modulo * constraints specified by B and d. * See also the documentation of isl_mat_parameter_compression. * We put the matrix * * A = [ L_1^{-T} L_2^{-T} ... L_k^{-T} ] * * on a common denominator. This denominator D is the lcm of modulos d. * Since L_i = U_i^{-1} diag(d_i, 1, ... 1), we have * L_i^{-T} = U_i^T diag(d_i, 1, ... 1)^{-T} = U_i^T diag(1/d_i, 1, ..., 1). * Putting this on the common denominator, we have * D * L_i^{-T} = U_i^T diag(D/d_i, D, ..., D). */ static __isl_give isl_mat *parameter_compression_multi(__isl_keep isl_mat *B, __isl_keep isl_vec *d) { … } /* Given a set of modulo constraints * * c + A y = 0 mod d * * this function returns an affine transformation T, * * y = T y' * * that bijectively maps the integer vectors y' to integer * vectors y that satisfy the modulo constraints. * * This function is inspired by Section 2.5.3 * of B. Meister, "Stating and Manipulating Periodicity in the Polytope * Model. Applications to Program Analysis and Optimization". * However, the implementation only follows the algorithm of that * section for computing a particular solution and not for computing * a general homogeneous solution. The latter is incomplete and * may remove some valid solutions. * Instead, we use an adaptation of the algorithm in Section 7 of * B. Meister, S. Verdoolaege, "Polynomial Approximations in the Polytope * Model: Bringing the Power of Quasi-Polynomials to the Masses". * * The input is given as a matrix B = [ c A ] and a vector d. * Each element of the vector d corresponds to a row in B. * The output is a lower triangular matrix. * If no integer vector y satisfies the given constraints then * a matrix with zero columns is returned. * * We first compute a particular solution y_0 to the given set of * modulo constraints in particular_solution. If no such solution * exists, then we return a zero-columned transformation matrix. * Otherwise, we compute the generic solution to * * A y = 0 mod d * * That is we want to compute G such that * * y = G y'' * * with y'' integer, describes the set of solutions. * * We first remove the common factors of each row. * In particular if gcd(A_i,d_i) != 1, then we divide the whole * row i (including d_i) by this common factor. If afterwards gcd(A_i) != 1, * then we divide this row of A by the common factor, unless gcd(A_i) = 0. * In the later case, we simply drop the row (in both A and d). * * If there are no rows left in A, then G is the identity matrix. Otherwise, * for each row i, we now determine the lattice of integer vectors * that satisfies this row. Let U_i be the unimodular extension of the * row A_i. This unimodular extension exists because gcd(A_i) = 1. * The first component of * * y' = U_i y * * needs to be a multiple of d_i. Let y' = diag(d_i, 1, ..., 1) y''. * Then, * * y = U_i^{-1} diag(d_i, 1, ..., 1) y'' * * for arbitrary integer vectors y''. That is, y belongs to the lattice * generated by the columns of L_i = U_i^{-1} diag(d_i, 1, ..., 1). * If there is only one row, then G = L_1. * * If there is more than one row left, we need to compute the intersection * of the lattices. That is, we need to compute an L such that * * L = L_i L_i' for all i * * with L_i' some integer matrices. Let A be constructed as follows * * A = [ L_1^{-T} L_2^{-T} ... L_k^{-T} ] * * and computed the Hermite Normal Form of A = [ H 0 ] U * Then, * * L_i^{-T} = H U_{1,i} * * or * * H^{-T} = L_i U_{1,i}^T * * In other words G = L = H^{-T}. * To ensure that G is lower triangular, we compute and use its Hermite * normal form. * * The affine transformation matrix returned is then * * [ 1 0 ] * [ y_0 G ] * * as any y = y_0 + G y' with y' integer is a solution to the original * modulo constraints. */ __isl_give isl_mat *isl_mat_parameter_compression(__isl_take isl_mat *B, __isl_take isl_vec *d) { … } /* Given a set of equalities * * B(y) + A x = 0 (*) * * compute and return an affine transformation T, * * y = T y' * * that bijectively maps the integer vectors y' to integer * vectors y that satisfy the modulo constraints for some value of x. * * Let [H 0] be the Hermite Normal Form of A, i.e., * * A = [H 0] Q * * Then y is a solution of (*) iff * * H^-1 B(y) (= - [I 0] Q x) * * is an integer vector. Let d be the common denominator of H^-1. * We impose * * d H^-1 B(y) = 0 mod d * * and compute the solution using isl_mat_parameter_compression. */ __isl_give isl_mat *isl_mat_parameter_compression_ext(__isl_take isl_mat *B, __isl_take isl_mat *A) { … } /* Return a compression matrix that indicates that there are no solutions * to the original constraints. In particular, return a zero-column * matrix with 1 + dim rows. If "T2" is not NULL, then assign *T2 * the inverse of this matrix. *T2 may already have been assigned * matrix, so free it first. * "free1", "free2" and "free3" are temporary matrices that are * not useful when an empty compression is returned. They are * simply freed. */ static __isl_give isl_mat *empty_compression(isl_ctx *ctx, unsigned dim, __isl_give isl_mat **T2, __isl_take isl_mat *free1, __isl_take isl_mat *free2, __isl_take isl_mat *free3) { … } /* Given a matrix that maps a (possibly) parametric domain to * a parametric domain, add in rows that map the "nparam" parameters onto * themselves. */ static __isl_give isl_mat *insert_parameter_rows(__isl_take isl_mat *mat, unsigned nparam) { … } /* Given a set of equalities * * -C(y) + M x = 0 * * this function computes a unimodular transformation from a lower-dimensional * space to the original space that bijectively maps the integer points x' * in the lower-dimensional space to the integer points x in the original * space that satisfy the equalities. * * The input is given as a matrix B = [ -C M ] and the output is a * matrix that maps [1 x'] to [1 x]. * The number of equality constraints in B is assumed to be smaller than * or equal to the number of variables x. * "first" is the position of the first x variable. * The preceding variables are considered to be y-variables. * If T2 is not NULL, then *T2 is set to a matrix mapping [1 x] to [1 x']. * * First compute the (left) Hermite normal form of M, * * M [U1 U2] = M U = H = [H1 0] * or * M = H Q = [H1 0] [Q1] * [Q2] * * with U, Q unimodular, Q = U^{-1} (and H lower triangular). * Define the transformed variables as * * x = [U1 U2] [ x1' ] = [U1 U2] [Q1] x * [ x2' ] [Q2] * * The equalities then become * * -C(y) + H1 x1' = 0 or x1' = H1^{-1} C(y) = C'(y) * * If the denominator of the constant term does not divide the * the common denominator of the coefficients of y, then every * integer point is mapped to a non-integer point and then the original set * has no integer solutions (since the x' are a unimodular transformation * of the x). In this case, a zero-column matrix is returned. * Otherwise, the transformation is given by * * x = U1 H1^{-1} C(y) + U2 x2' * * The inverse transformation is simply * * x2' = Q2 x */ __isl_give isl_mat *isl_mat_final_variable_compression(__isl_take isl_mat *B, int first, __isl_give isl_mat **T2) { … } /* Given a set of equalities * * M x - c = 0 * * this function computes a unimodular transformation from a lower-dimensional * space to the original space that bijectively maps the integer points x' * in the lower-dimensional space to the integer points x in the original * space that satisfy the equalities. * * The input is given as a matrix B = [ -c M ] and the output is a * matrix that maps [1 x'] to [1 x]. * The number of equality constraints in B is assumed to be smaller than * or equal to the number of variables x. * If T2 is not NULL, then *T2 is set to a matrix mapping [1 x] to [1 x']. */ __isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, __isl_give isl_mat **T2) { … } /* Return "bset" and set *T and *T2 to the identity transformation * on "bset" (provided T and T2 are not NULL). */ static __isl_give isl_basic_set *return_with_identity( __isl_take isl_basic_set *bset, __isl_give isl_mat **T, __isl_give isl_mat **T2) { … } /* Use the n equalities of bset to unimodularly transform the * variables x such that n transformed variables x1' have a constant value * and rewrite the constraints of bset in terms of the remaining * transformed variables x2'. The matrix pointed to by T maps * the new variables x2' back to the original variables x, while T2 * maps the original variables to the new variables. */ static __isl_give isl_basic_set *compress_variables( __isl_take isl_basic_set *bset, __isl_give isl_mat **T, __isl_give isl_mat **T2) { … } __isl_give isl_basic_set *isl_basic_set_remove_equalities( __isl_take isl_basic_set *bset, __isl_give isl_mat **T, __isl_give isl_mat **T2) { … } /* Check if dimension dim belongs to a residue class * i_dim \equiv r mod m * with m != 1 and if so return m in *modulo and r in *residue. * As a special case, when i_dim has a fixed value v, then * *modulo is set to 0 and *residue to v. * * If i_dim does not belong to such a residue class, then *modulo * is set to 1 and *residue is set to 0. */ isl_stat isl_basic_set_dim_residue_class(__isl_keep isl_basic_set *bset, int pos, isl_int *modulo, isl_int *residue) { … } /* Check if dimension dim belongs to a residue class * i_dim \equiv r mod m * with m != 1 and if so return m in *modulo and r in *residue. * As a special case, when i_dim has a fixed value v, then * *modulo is set to 0 and *residue to v. * * If i_dim does not belong to such a residue class, then *modulo * is set to 1 and *residue is set to 0. */ isl_stat isl_set_dim_residue_class(__isl_keep isl_set *set, int pos, isl_int *modulo, isl_int *residue) { … } /* Check if dimension "dim" belongs to a residue class * i_dim \equiv r mod m * with m != 1 and if so return m in *modulo and r in *residue. * As a special case, when i_dim has a fixed value v, then * *modulo is set to 0 and *residue to v. * * If i_dim does not belong to such a residue class, then *modulo * is set to 1 and *residue is set to 0. */ isl_stat isl_set_dim_residue_class_val(__isl_keep isl_set *set, int pos, __isl_give isl_val **modulo, __isl_give isl_val **residue) { … }
Codebase Browser
llvm