summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: 76f7009)
rawpatchinlineside by side (parent: 76f7009)
| author | Sven Verdoolaege <skimo@kotnet.org> | |
| Fri, 19 Apr 2013 14:54:18 +0000 (19 16:54 +0200) | ||
| committer | Sven Verdoolaege <skimo@kotnet.org> | |
| Mon, 22 Apr 2013 07:38:20 +0000 (22 09:38 +0200) |
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
| isl_equalities.c | patchblobblamehistory | |
| isl_equalities.h | patchblobblamehistory | |
| isl_morph.c | patchblobblamehistory |
diff --git a/isl_equalities.c b/isl_equalities.c
--- a/isl_equalities.c
+++ b/isl_equalities.c
/*
* 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>
/* 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
--- a/isl_equalities.h
+++ b/isl_equalities.h
__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
--- a/isl_morph.c
+++ b/isl_morph.c
*
* 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)
unsigned n_div;
int n_eq;
isl_mat *H, *B;
- isl_vec *d;
isl_mat *map, *inv;
isl_basic_set *dom, *ran;
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));
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