isl_morph.c: extract out isl_mat_parameter_compression_ext
authorSven Verdoolaege <skimo@kotnet.org>
Fri, 19 Apr 2013 14:54:18 +0000 (19 16:54 +0200)
committerSven 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
isl_equalities.h
isl_morph.c

index bf9dc26..9589032 100644 (file)
@@ -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 <isl_mat_private.h>
@@ -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
index dae69bb..0206cd1 100644 (file)
@@ -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);
 
index adbd2bd..04991e1 100644 (file)
@@ -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