isl_aff_normalize: combine identical divs

[platform/upstream/isl.git] / isl_aff.c

diff --git a/isl_aff.c b/isl_aff.c
index 40b925f..dc519cb 100644 (file)
--- a/isl_aff.c
+++ b/isl_aff.c
@@ -648,6 +648,86 @@ __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
        return aff;
 }
 
+/* Given two affine expressions "p" of length p_len (including the
+ * denominator and the constant term) and "subs" of length subs_len,
+ * plug in "subs" for the variable at position "pos".
+ * The variables of "subs" and "p" are assumed to match up to subs_len,
+ * but "p" may have additional variables.
+ * "v" is an initialized isl_int that can be used internally.
+ *
+ * In particular, if "p" represents the expression
+ *
+ *     (a i + g)/m
+ *
+ * with i the variable at position "pos" and "subs" represents the expression
+ *
+ *     f/d
+ *
+ * then the result represents the expression
+ *
+ *     (a f + d g)/(m d)
+ *
+ */
+void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
+       int p_len, int subs_len, isl_int v)
+{
+       isl_int_set(v, p[1 + pos]);
+       isl_int_set_si(p[1 + pos], 0);
+       isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
+       isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
+       isl_int_mul(p[0], p[0], subs[0]);
+}
+
+/* Look for any divs in the aff->ls with a denominator equal to one
+ * and plug them into the affine expression and any subsequent divs
+ * that may reference the div.
+ */
+static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff)
+{
+       int i, n;
+       int len;
+       isl_int v;
+       isl_vec *vec;
+       isl_local_space *ls;
+       unsigned pos;
+
+       if (!aff)
+               return NULL;
+
+       n = isl_local_space_dim(aff->ls, isl_dim_div);
+       len = aff->v->size;
+       for (i = 0; i < n; ++i) {
+               if (!isl_int_is_one(aff->ls->div->row[i][0]))
+                       continue;
+               ls = isl_local_space_copy(aff->ls);
+               ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
+                                           aff->ls->div->row[i], len, i + 1);
+               vec = isl_vec_copy(aff->v);
+               vec = isl_vec_cow(vec);
+               if (!ls || !vec)
+                       goto error;
+
+               isl_int_init(v);
+
+               pos = isl_local_space_offset(aff->ls, isl_dim_div) + i;
+               isl_seq_substitute(vec->el, pos, aff->ls->div->row[i],
+                                       len, len, v);
+
+               isl_int_clear(v);
+
+               isl_vec_free(aff->v);
+               aff->v = vec;
+               isl_local_space_free(aff->ls);
+               aff->ls = ls;
+       }
+
+       return aff;
+error:
+       isl_vec_free(vec);
+       isl_local_space_free(ls);
+       return isl_aff_free(aff);
+}
+
 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
  *
  * Even though this function is only called on isl_affs with a single
@@ -679,8 +759,32 @@ error:
        return isl_aff_free(aff);
 }
 
+/* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
+ *
+ * We currently do not actually remove div "b", but simply add its
+ * coefficient to that of "a" and then zero it out.
+ */
+static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b)
+{
+       unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
+
+       if (isl_int_is_zero(aff->v->el[1 + off + b]))
+               return aff;
+
+       aff->v = isl_vec_cow(aff->v);
+       if (!aff->v)
+               return isl_aff_free(aff);
+
+       isl_int_add(aff->v->el[1 + off + a],
+                   aff->v->el[1 + off + a], aff->v->el[1 + off + b]);
+       isl_int_set_si(aff->v->el[1 + off + b], 0);
+
+       return aff;
+}
+
 /* Sort the divs in the local space of "aff" according to
- * the comparison function "cmp_row" in isl_local_space.c
+ * the comparison function "cmp_row" in isl_local_space.c,
+ * combining the coefficients of identical divs.
  *
  * Reordering divs does not change the semantics of "aff",
  * so there is no need to call isl_aff_cow.
@@ -690,16 +794,22 @@ error:
 static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
 {
        int i, j, n;
+       unsigned off;
 
        if (!aff)
                return NULL;
 
+       off = isl_local_space_offset(aff->ls, isl_dim_div);
        n = isl_aff_dim(aff, isl_dim_div);
        for (i = 1; i < n; ++i) {
                for (j = i - 1; j >= 0; --j) {
-                       if (isl_mat_cmp_div(aff->ls->div, j, j + 1) <= 0)
+                       int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
+                       if (cmp < 0)
                                break;
-                       aff = swap_div(aff, j, j + 1);
+                       if (cmp == 0)
+                               aff = merge_divs(aff, j, j + 1);
+                       else
+                               aff = swap_div(aff, j, j + 1);
                        if (!aff)
                                return NULL;
                }
@@ -721,6 +831,7 @@ __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
        aff->v = isl_vec_normalize(aff->v);
        if (!aff->v)
                return isl_aff_free(aff);
+       aff = plug_in_integral_divs(aff);
        aff = sort_divs(aff);
        aff = isl_aff_remove_unused_divs(aff);
        return aff;
@@ -3089,11 +3200,8 @@ __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
        pos += isl_local_space_offset(aff->ls, type);
 
        isl_int_init(v);
-       isl_int_set(v, aff->v->el[1 + pos]);
-       isl_int_set_si(aff->v->el[1 + pos], 0);
-       isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
-                       v, subs->v->el + 1, subs->v->size - 1);
-       isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
+       isl_seq_substitute(aff->v->el, pos, subs->v->el,
+                           aff->v->size, subs->v->size, v);
        isl_int_clear(v);
 
        return aff;