From 574daacec0c3c0b3e3734f4f5ea75dace276fa64 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 19 Apr 2013 16:54:18 +0200 Subject: [PATCH] isl_morph.c: extract out isl_mat_parameter_compression_ext Signed-off-by: Sven Verdoolaege --- isl_equalities.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ isl_equalities.h | 2 ++ isl_morph.c | 28 ++++------------------------ 3 files changed, 62 insertions(+), 24 deletions(-) diff --git a/isl_equalities.c b/isl_equalities.c index bf9dc26f..9589032c 100644 --- a/isl_equalities.c +++ b/isl_equalities.c @@ -1,10 +1,13 @@ /* * 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 @@ -374,6 +377,59 @@ error: /* 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) +{ + isl_ctx *ctx; + isl_vec *d; + int n_row, n_col; + + if (!A) + return isl_mat_free(B); + + ctx = isl_mat_get_ctx(A); + n_row = A->n_row; + n_col = A->n_col; + A = isl_mat_left_hermite(A, 0, NULL, NULL); + A = isl_mat_drop_cols(A, n_row, n_col - n_row); + A = isl_mat_lin_to_aff(A); + A = isl_mat_right_inverse(A); + d = isl_vec_alloc(ctx, n_row); + if (A) + d = isl_vec_set(d, A->row[0][0]); + A = isl_mat_drop_rows(A, 0, 1); + A = isl_mat_drop_cols(A, 0, 1); + B = isl_mat_product(A, B); + + return isl_mat_parameter_compression(B, d); +} + +/* Given a set of equalities + * * M x - c = 0 * * this function computes a unimodular transformation from a lower-dimensional diff --git a/isl_equalities.h b/isl_equalities.h index dae69bbb..0206cd1c 100644 --- a/isl_equalities.h +++ b/isl_equalities.h @@ -21,6 +21,8 @@ __isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, __isl_give isl_mat **T2); struct isl_mat *isl_mat_parameter_compression( struct isl_mat *B, struct isl_vec *d); +__isl_give isl_mat *isl_mat_parameter_compression_ext(__isl_take isl_mat *B, + __isl_take isl_mat *A); struct isl_basic_set *isl_basic_set_remove_equalities( struct isl_basic_set *bset, struct isl_mat **T, struct isl_mat **T2); diff --git a/isl_morph.c b/isl_morph.c index adbd2bda..04991e17 100644 --- a/isl_morph.c +++ b/isl_morph.c @@ -479,14 +479,11 @@ error: * * Let the equalities be given as * - * B(p) + A x = 0 + * B(p) + A x = 0. * - * and let [H 0] be the Hermite Normal Form of A, then + * We use isl_mat_parameter_compression_ext to compute the compression * - * H^-1 B(p) - * - * needs to be integer, so we impose that each row is divisible by - * the denominator. + * p = T p'. */ __isl_give isl_morph *isl_basic_set_parameter_compression( __isl_keep isl_basic_set *bset) @@ -496,7 +493,6 @@ __isl_give isl_morph *isl_basic_set_parameter_compression( unsigned n_div; int n_eq; isl_mat *H, *B; - isl_vec *d; isl_mat *map, *inv; isl_basic_set *dom, *ran; @@ -522,21 +518,10 @@ __isl_give isl_morph *isl_basic_set_parameter_compression( isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid, "input not gaussed", return NULL); - d = isl_vec_alloc(bset->ctx, n_eq); B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam); H = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 1 + nparam, nvar + n_div); - H = isl_mat_left_hermite(H, 0, NULL, NULL); - H = isl_mat_drop_cols(H, n_eq, (nvar + n_div) - n_eq); - H = isl_mat_lin_to_aff(H); - H = isl_mat_right_inverse(H); - if (!H || !d) - goto error; - d = isl_vec_set(d, H->row[0][0]); - H = isl_mat_drop_rows(H, 0, 1); - H = isl_mat_drop_cols(H, 0, 1); - B = isl_mat_product(H, B); - inv = isl_mat_parameter_compression(B, d); + inv = isl_mat_parameter_compression_ext(B, H); inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar)); map = isl_mat_right_inverse(isl_mat_copy(inv)); @@ -544,11 +529,6 @@ __isl_give isl_morph *isl_basic_set_parameter_compression( ran = isl_basic_set_universe(isl_space_copy(bset->dim)); return isl_morph_alloc(dom, ran, map, inv); -error: - isl_mat_free(H); - isl_mat_free(B); - isl_vec_free(d); - return NULL; } /* Add stride constraints to "bset" based on the inverse mapping -- 2.11.4.GIT