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
+ * reference, we are careful to only change aff->v and aff->ls together.
+ */
+static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
+{
+ unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
+ isl_local_space *ls;
+ isl_vec *v;
+
+ ls = isl_local_space_copy(aff->ls);
+ ls = isl_local_space_swap_div(ls, a, b);
+ v = isl_vec_copy(aff->v);
+ v = isl_vec_cow(v);
+ if (!ls || !v)
+ goto error;
+
+ isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]);
+ isl_vec_free(aff->v);
+ aff->v = v;
+ isl_local_space_free(aff->ls);
+ aff->ls = ls;
+
+ return aff;
+error:
+ isl_vec_free(v);
+ isl_local_space_free(ls);
+ 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,
+ * 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.
+ * Moreover, this function is currently only called on isl_affs
+ * with a single reference.
+ */
+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) {
+ int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
+ if (cmp < 0)
+ break;
+ if (cmp == 0)
+ aff = merge_divs(aff, j, j + 1);
+ else
+ aff = swap_div(aff, j, j + 1);
+ if (!aff)
+ return NULL;
+ }
+ }
+
+ return aff;
+}
+
/* Normalize the representation of "aff".
*
* This function should only be called of "new" isl_affs, i.e.,
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;
}
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;
projects / platform / upstream / isl.git / blobdiff