This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [GSoC] questions about graphite_clast_to_gimple.c


On 05/05/2014 21:11, Roman Gareev wrote:
Hi Tobias,

thank you for your reply! I have questions about types. Could you
please answer them?

I looked through them and most seem to be related to how we derive types in graphite. As I said before, this is a _very_ fragile hack
that works surprisingly well, but which is both too complex and
in the end still incorrect. Sebastian wrote this code, so I am not familiar with the details. I also don't think it is necessary to understand the details. Instead of using any code, we should start implementing the new code using 64 bit signed integers. This
should be correct in 99.9% of the cases.

One of the selling points for the new isl code generation was however,
that it will be possible to get precise information about the types
needed for code generation. There existed already a patch for an older
isl version and there is a partial patch for newer versions that Sven and me have been working on. It is not yet stable enough to be tested, but I attached it anyway for illustration. The idea is to
introduce a set of functions

+       int isl_ast_expr_has_known_size(
+               __isl_keep isl_ast_expr *expr);
+       int isl_ast_expr_is_bounded(
+               __isl_keep isl_ast_expr *expr);
+       int isl_ast_expr_is_signed(
+               __isl_keep isl_ast_expr *expr);
+       size_t isl_ast_expr_size_in_bits(
+               __isl_keep isl_ast_expr *expr);

in isl, where we can precisely compute the minimal legal type. We can then use this during code generation to derive good types.

Questions related to âtype_for_intervalâ:

1. What happens in these lines?

int precision = MAX (mpz_sizeinbase (bound_one, 2),
mpz_sizeinbase (bound_two, 2));
if (precision > BITS_PER_WORD)
{
gloog_error = true;
return integer_type_node;
}


Do we try to count maximum number of value bits in bound_one and
bound_two?

I believe.

Why can't it be greater than BITS_PER_WORD?

No idea.

2. Why do we want to generate signed types as much as possible?

Because in the code cloog generates negative values are common. To be save we generate unsigned code.

3. Why do we always have enough precision in case of precision <
wider_precision?

I have no idea (and did not bother trying to understand)

Questions related to âclast_to_gcc_expressionâ:

4. What is the idea behind this code?

if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
name = convert_to_ptrofftype (name);

Sorry, again no idea.

5. Why do we check POINTER_TYPE_P(type)? (âtypeâ has tree type and the
manual says that a tree is a pointer type)

Sorry, again no idea.

Questions related to âmax_precision_typeâ:

6. Why is type1, for example, is the maximal precision type in case of
truth of POINTER_TYPE_P (type1)?

I don't know. This really lacks comments. This may very well have a good reason, but it is hard to see as most of the other stuff for deriving the types is very much a hack.

7. Why do we have enough precision for p2 in case of p1 > p2 and signed type1?

No idea.

8. Why do we always build signed integer type in the line: âtype =
build_nonstandard_integer_type (precision, false);â?

No idea.

Questions related to âtype_for_clast_redâ:

9. Why do we use this code in case of clast_red_sum?

value_min (m1, bound_one, bound_two);
value_min (m2, b1, b2);
mpz_add (bound_one, m1, m2);

We try to derive the bounds for the sum. No idea, regarding the actual
computation.

Can bound_one be greater then bound_two? (We also consider two cases
in âtype_for_intervalâ)

I would guess not. This may be a bug.

10. Why do we assume that new bounds are min(bound_one, bound_two) and
min(b1, b2) in case of clast_red_min?

No idea. This seems incorrect.

I would have expected

bound_one = value_max(bound_one, b1)
bound_two = value_max(bound_two, b2)


Again, I do not think spending time to understand the heuristics in type_for_clast is worth it. Some are rather complex and work well, some or just buggy but have never been triggered and a small percentage actually might be reusable later (pointer handling). As the approach
has generally too little information to work reliably, I would not spend
any time on it. I pointed out the correct approach above. Going with 64bit types will bring us a very long way, and we can finish the isl patch to get it 100% right.

Cheers,
Tobias
>From 7270a84231c52edba0db65e2317a4b7dc383b109 Mon Sep 17 00:00:00 2001
From: Tobias Grosser <tobias@grosser.es>
Date: Tue, 1 Apr 2014 23:15:11 +0200
Subject: [PATCH] Derive minimal valid types for isl_ast_expr's

---
 codegen.c                                          |   3 +-
 codegen_test.sh.in                                 |  11 +
 doc/user.pod                                       |  25 +
 include/isl/ast.h                                  |   5 +
 include/isl/ast_build.h                            |   3 +
 isl_ast.c                                          | 175 +++++-
 isl_ast_build.c                                    |  19 +
 isl_ast_build_expr.c                               | 639 +++++++++++++++++----
 isl_ast_build_private.h                            |   6 +
 isl_ast_codegen.c                                  |   1 +
 isl_ast_private.h                                  |   4 +
 isl_options.c                                      |   7 +
 isl_options_private.h                              |   1 +
 .../codegen/bounds/ast_exprs/const_integer.c       |   1 +
 .../codegen/bounds/ast_exprs/const_integer.in      |   3 +
 .../codegen/bounds/ast_exprs/const_parameters.c    |   1 +
 .../codegen/bounds/ast_exprs/const_parameters.in   |   3 +
 test_inputs/codegen/bounds/ast_exprs/div.c         |   2 +
 test_inputs/codegen/bounds/ast_exprs/div.in        |   3 +
 test_inputs/codegen/bounds/ast_exprs/floord.in     |   3 +
 test_inputs/codegen/bounds/ast_exprs/max.in        |   3 +
 test_inputs/codegen/bounds/ast_exprs/min.in        |   3 +
 test_inputs/codegen/bounds/ast_exprs/product.c     |   1 +
 test_inputs/codegen/bounds/ast_exprs/product.in    |   3 +
 test_inputs/codegen/bounds/ast_exprs/select.in     |   3 +
 test_inputs/codegen/bounds/ast_exprs/sum.c         |   1 +
 test_inputs/codegen/bounds/ast_exprs/sum.in        |   3 +
 test_inputs/codegen/bounds/ast_exprs/sum2.in       |   3 +
 28 files changed, 823 insertions(+), 112 deletions(-)
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/const_integer.c
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/const_integer.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/const_parameters.c
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/const_parameters.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/div.c
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/div.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/floord.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/max.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/min.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/product.c
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/product.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/select.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/sum.c
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/sum.in
 create mode 100644 test_inputs/codegen/bounds/ast_exprs/sum2.in

diff --git a/codegen.c b/codegen.c
index e9cd692..de6acad 100644
--- a/codegen.c
+++ b/codegen.c
@@ -127,8 +127,9 @@ int main(int argc, char **argv)
 	isl_ast_build_free(build);
 
 	p = isl_printer_to_file(ctx, stdout);
-	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
+//	p = isl_printer_set_output_format(p, ISL_FORMAT_C);
 	p = isl_printer_print_ast_node(p, tree);
+	p = isl_printer_print_str(p, "\n");
 	isl_printer_free(p);
 
 	isl_ast_node_free(tree);
diff --git a/codegen_test.sh.in b/codegen_test.sh.in
index 3349bcd..58f8a17 100644
--- a/codegen_test.sh.in
+++ b/codegen_test.sh.in
@@ -19,4 +19,15 @@ for i in $srcdir/test_inputs/codegen/*.in \
 	 diff -uw $ref $test && rm $test) || failed=1
 done
 
+for i in $srcdir/test_inputs/codegen/bounds/*.in \
+		$srcdir/test_inputs/codegen/bounds/ast_exprs/*.in; do
+	echo $i;
+	base=`basename $i .in`
+	test=test-$base.c
+	dir=`dirname $i`
+	ref=$dir/$base.c
+	(./isl_codegen$EXEEXT --isl-ast-build-compute-bounds < $i > $test &&
+	 diff -uw $ref $test && rm $test) || failed=1
+done
+
 test $failed -eq 0 || exit
diff --git a/doc/user.pod b/doc/user.pod
index d88178f..99129c7 100644
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -6328,6 +6328,14 @@ the following functions.
 		__isl_keep isl_ast_expr *expr);
 	enum isl_ast_expr_type isl_ast_expr_get_type(
 		__isl_keep isl_ast_expr *expr);
+	int isl_ast_expr_has_known_size(
+	        __isl_keep isl_ast_expr *expr);
+	int isl_ast_expr_is_bounded(
+	        __isl_keep isl_ast_expr *expr);
+	int isl_ast_expr_is_signed(
+	        __isl_keep isl_ast_expr *expr);
+	size_t isl_ast_expr_size_in_bits(
+	        __isl_keep isl_ast_expr *expr);
 
 The type of an AST expression is one of
 C<isl_ast_expr_op>,
@@ -6336,6 +6344,23 @@ C<isl_ast_expr_int>.
 An C<isl_ast_expr_op> represents the result of an operation.
 An C<isl_ast_expr_id> represents an identifier.
 An C<isl_ast_expr_int> represents an integer value.
+If so, C<isl_ast_expr_is_bounded>, C<isl_ast_expr_is_signed> and
+C<isl_ast_expr_size_in_bits> can be used to check whether
+the value of the expression is bounded, whether it can attain
+negative values and the maximal number of bits required to store
+the value of the expression.  This number of bits includes the sign
+bit if (and only if) the expression can attain negative values.
+Note that the bounds are computed within a certain context and they
+are then also valid within that context.  In particular, if the expression
+is reused in a different context, then the bounds are I<not> recomputed
+automatically to reflect the new context.
+The computation of bounds on expressions can be controlled using
+the following option.
+
+	#include <isl/ast_build.h>
+	int isl_options_set_ast_build_compute_bounds(isl_ctx *ctx,
+	        int val);
+	int isl_options_get_ast_build_compute_bounds(isl_ctx *ctx);
 
 Each type of expression has its own additional properties.
 
diff --git a/include/isl/ast.h b/include/isl/ast.h
index ae70dfc..d0925bb 100644
--- a/include/isl/ast.h
+++ b/include/isl/ast.h
@@ -55,6 +55,11 @@ int isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
 __isl_give isl_ast_expr *isl_ast_expr_substitute_ids(
 	__isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr);
 
+int isl_ast_expr_has_known_size(__isl_keep isl_ast_expr *expr);
+int isl_ast_expr_is_bounded(__isl_keep isl_ast_expr *expr);
+int isl_ast_expr_is_signed(__isl_keep isl_ast_expr *expr);
+size_t isl_ast_expr_size_in_bits(__isl_keep isl_ast_expr *expr);
+
 __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
 	__isl_keep isl_ast_expr *expr);
 void isl_ast_expr_dump(__isl_keep isl_ast_expr *expr);
diff --git a/include/isl/ast_build.h b/include/isl/ast_build.h
index 4fa7b45..2dd65ba 100644
--- a/include/isl/ast_build.h
+++ b/include/isl/ast_build.h
@@ -19,6 +19,9 @@ int isl_options_get_ast_build_atomic_upper_bound(isl_ctx *ctx);
 int isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx);
 
+int isl_options_set_ast_build_compute_bounds(isl_ctx *ctx, int val);
+int isl_options_get_ast_build_compute_bounds(isl_ctx *ctx);
+
 int isl_options_set_ast_build_exploit_nested_bounds(isl_ctx *ctx, int val);
 int isl_options_get_ast_build_exploit_nested_bounds(isl_ctx *ctx);
 
diff --git a/isl_ast.c b/isl_ast.c
index 3320416..79656c5 100644
--- a/isl_ast.c
+++ b/isl_ast.c
@@ -8,6 +8,7 @@
  */
 
 #include <isl_ast_private.h>
+#include <include/isl/ast_build.h>
 
 #undef BASE
 #define BASE ast_expr
@@ -184,6 +185,11 @@ __isl_give isl_ast_expr *isl_ast_expr_dup(__isl_keep isl_ast_expr *expr)
 	if (!dup)
 		return NULL;
 
+	dup->known_size = expr->known_size;
+	dup->is_bounded = expr->is_bounded;
+	dup->is_signed = expr->is_signed;
+	dup->bits = expr->bits;
+
 	return dup;
 }
 
@@ -360,6 +366,52 @@ int isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1,
 	}
 }
 
+/* Has the size of "expr" been computed?
+ *  */
+int isl_ast_expr_has_known_size(__isl_keep isl_ast_expr *expr)
+{
+	return expr ? expr->known_size : -1;
+}
+
+/* Does "expr" have values within a bounded range (in the context
+ *  * where "expr" was created)?
+ *   */
+int isl_ast_expr_is_bounded(__isl_keep isl_ast_expr *expr)
+{
+	if (!expr)
+	        return -1;
+	if (!expr->known_size)
+	        isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+	                "size unknown", return -1);
+	return expr->is_bounded;
+}
+
+/* Does "expr" attain any negative values (in the context
+ *  * where "expr" was created)?
+ *   */
+int isl_ast_expr_is_signed(__isl_keep isl_ast_expr *expr)
+{
+	if (!expr)
+	        return -1;
+	if (!expr->known_size)
+	        isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+	                "size unknown", return -1);
+	return expr->is_signed;
+}
+
+/* How many bits are needed to represent the values attained by "expr"?
+ *  * (in the context where "expr" was created)?
+ *   */
+size_t isl_ast_expr_size_in_bits(__isl_keep isl_ast_expr *expr)
+{
+	if (!expr)
+	        return 0;
+	if (!expr->known_size)
+	        isl_die(isl_ast_expr_get_ctx(expr), isl_error_invalid,
+	                "size unknown", return 0);
+	return expr->bits;
+}
+
 /* Create a new operation expression of operation type "op",
  * with "n_arg" as yet unspecified arguments.
  */
@@ -383,6 +435,8 @@ __isl_give isl_ast_expr *isl_ast_expr_alloc_op(isl_ctx *ctx,
 	if (n_arg && !expr->u.op.args)
 		return isl_ast_expr_free(expr);
 
+	expr->known_size = 0;
+
 	return expr;
 }
 
@@ -407,6 +461,8 @@ __isl_give isl_ast_expr *isl_ast_expr_from_id(__isl_take isl_id *id)
 	expr->type = isl_ast_expr_id;
 	expr->u.id = id;
 
+	expr->known_size = 0;
+
 	return expr;
 error:
 	isl_id_free(id);
@@ -431,6 +487,11 @@ __isl_give isl_ast_expr *isl_ast_expr_alloc_int_si(isl_ctx *ctx, int i)
 	if (!expr->u.v)
 		return isl_ast_expr_free(expr);
 
+	expr->known_size = 1;
+	expr->is_bounded = 1;
+	expr->is_signed = isl_val_is_neg(expr->u.v);
+	expr->bits = isl_val_size_in_bits(expr->u.v, expr->is_signed);
+
 	return expr;
 }
 
@@ -458,6 +519,11 @@ __isl_give isl_ast_expr *isl_ast_expr_from_val(__isl_take isl_val *v)
 	expr->type = isl_ast_expr_int;
 	expr->u.v = v;
 
+	expr->known_size = 1;
+	expr->is_bounded = 1;
+	expr->is_signed = isl_val_is_neg(expr->u.v);
+	expr->bits = isl_val_size_in_bits(expr->u.v, expr->is_signed);
+
 	return expr;
 error:
 	isl_val_free(v);
@@ -1269,16 +1335,101 @@ static int sub_expr_need_parens(enum isl_ast_op_type op,
 	return 0;
 }
 
+__isl_give isl_printer *printer_print_cast(__isl_take isl_printer *p,
+	__isl_keep isl_ast_expr *expr)
+{
+
+        if (isl_printer_get_output_format(p) != ISL_FORMAT_C)
+		return p;
+
+	int size = 0;
+	int sgn = 0;
+
+	if (expr->type == isl_ast_expr_op) {
+		int i;
+		for (i = 0; i < expr->u.op.n_arg; ++i) {
+			isl_ast_expr *subexpr = expr->u.op.args[i];
+			if (!isl_ast_expr_has_known_size(subexpr)) {
+				size = 0;
+				sgn = 0;
+				break;
+			} else {
+				int new_size;
+				int new_sgn;
+				new_size = isl_ast_expr_size_in_bits(subexpr);
+				new_sgn |= isl_ast_expr_is_signed(subexpr);
+
+				if (!new_sgn && sgn)
+					new_size++;
+
+				size = new_size > size ? new_size : size;
+				sgn |= new_sgn;
+			}
+		}
+	} 
+
+	if (isl_ast_expr_has_known_size(expr)) {
+		int new_size, new_sgn;
+
+		new_size = isl_ast_expr_size_in_bits(expr);
+		new_sgn |= isl_ast_expr_is_signed(expr);
+
+		if (!new_sgn && sgn)
+			new_size++;
+
+		size = new_size > size ? new_size : size;
+		sgn |= new_sgn;
+	}
+
+	if (sgn)
+		size++;
+
+        if (1) {
+          if (size == 0) {
+            p = isl_printer_print_str(p, "toint");
+          } else {
+            p = isl_printer_print_str(p, "to");
+            if (!sgn)
+              p = isl_printer_print_str(p, "u");
+
+            p = isl_printer_print_str(p, "int");
+            p = isl_printer_print_int(p, size);
+          }
+        } else {
+          p = isl_printer_print_str(p, "(");
+          if (size == 0) {
+            p = isl_printer_print_str(p, "int");
+          } else {
+            p = isl_printer_print_str(p, "");
+            if (!sgn)
+              p = isl_printer_print_str(p, "u");
+
+            p = isl_printer_print_str(p, "int");
+            p = isl_printer_print_int(p, size);
+          }
+          p = isl_printer_print_str(p, ")");
+        }
+
+        return p;
+}
+
 /* Print "expr" as a subexpression of an "op" operation.
  * If "left" is set, then "expr" is the left-most operand.
  */
 static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p,
-	enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left)
+	enum isl_ast_op_type op, __isl_keep isl_ast_expr *expr, int left,
+	__isl_keep isl_ast_expr *parent)
 {
 	int need_parens;
 
+
 	need_parens = sub_expr_need_parens(op, expr, left);
 
+	if (isl_options_get_ast_build_compute_bounds(isl_printer_get_ctx(p))) {
+		p = printer_print_cast(p, parent);
+		need_parens = 1;
+	}
+
 	if (need_parens)
 		p = isl_printer_print_str(p, "(");
 	p = isl_printer_print_ast_expr(p, expr);
@@ -1298,10 +1449,12 @@ static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p,
 		p = isl_printer_print_str(p, op_str[expr->u.op.op]);
 		p = isl_printer_print_str(p, "(");
 	}
-	p = isl_printer_print_ast_expr(p, expr->u.op.args[0]);
+	
+	p = print_sub_expr(p, isl_ast_op_max, expr->u.op.args[0], 0, expr);
+
 	for (i = 1; i < expr->u.op.n_arg; ++i) {
 		p = isl_printer_print_str(p, ", ");
-		p = isl_printer_print_ast_expr(p, expr->u.op.args[i]);
+		p = print_sub_expr(p, isl_ast_op_max, expr->u.op.args[i], 0, expr);
 		p = isl_printer_print_str(p, ")");
 	}
 
@@ -1374,7 +1527,7 @@ __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
 		if (expr->u.op.n_arg == 1) {
 			p = isl_printer_print_str(p, op_str[expr->u.op.op]);
 			p = print_sub_expr(p, expr->u.op.op,
-						expr->u.op.args[0], 0);
+						expr->u.op.args[0], 0, expr);
 			break;
 		}
 		if (expr->u.op.op == isl_ast_op_fdiv_q) {
@@ -1403,13 +1556,13 @@ __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
 			isl_die(isl_printer_get_ctx(p), isl_error_internal,
 				"operation should have two arguments",
 				goto error);
-		p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1);
+		p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1, expr);
 		if (expr->u.op.op != isl_ast_op_member)
 			p = isl_printer_print_str(p, " ");
 		p = isl_printer_print_str(p, op_str[expr->u.op.op]);
 		if (expr->u.op.op != isl_ast_op_member)
 			p = isl_printer_print_str(p, " ");
-		p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0);
+		p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0, expr);
 		break;
 	case isl_ast_expr_id:
 		p = isl_printer_print_str(p, isl_id_get_name(expr->u.id));
@@ -1420,6 +1573,15 @@ __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p,
 	case isl_ast_expr_error:
 		break;
 	}
+    
+        if (isl_printer_get_output_format(p) == ISL_FORMAT_ISL &&
+            expr->is_bounded) {
+                p = isl_printer_print_str(p, "[");
+                if (expr->is_signed)
+                        p = isl_printer_print_str(p, "signed ");
+                p = isl_printer_print_int(p, expr->bits);
+                p = isl_printer_print_str(p, "]");
+        }
 
 	return p;
 error:
@@ -1612,6 +1774,7 @@ static __isl_give isl_printer *print_for_c(__isl_take isl_printer *p,
 	const char *type;
 
 	type = isl_options_get_ast_iterator_type(isl_printer_get_ctx(p));
+
 	if (!node->u.f.degenerate) {
 		id = isl_ast_expr_get_id(node->u.f.iterator);
 		name = isl_id_get_name(id);
diff --git a/isl_ast_build.c b/isl_ast_build.c
index fa01bed..5bd30a5 100644
--- a/isl_ast_build.c
+++ b/isl_ast_build.c
@@ -36,6 +36,24 @@ __isl_give isl_map *isl_ast_build_map_to_iterator(
 	return map;
 }
 
+/* Initialize the local copy of the "compute_bounds" option
+ * from the associated isl_ctx.
+ */
+__isl_give isl_ast_build *isl_ast_build_init_options(
+	__isl_take isl_ast_build *build)
+{
+	isl_ctx *ctx;
+
+	build = isl_ast_build_cow(build);
+	if (!build)
+	        return NULL;
+	
+	ctx = isl_ast_build_get_ctx(build);
+	build->compute_bounds = isl_options_get_ast_build_compute_bounds(ctx);
+
+	return build;
+}
+
 /* Initialize the information derived during the AST generation to default
  * values for a schedule domain in "space".
  *
@@ -166,6 +184,7 @@ __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
 		return NULL;
 
 	dup->ref = 1;
+	dup->compute_bounds = build->compute_bounds;
 	dup->outer_pos = build->outer_pos;
 	dup->depth = build->depth;
 	dup->iterators = isl_id_list_copy(build->iterators);
diff --git a/isl_ast_build_expr.c b/isl_ast_build_expr.c
index b0fdbb9..bdb8871 100644
--- a/isl_ast_build_expr.c
+++ b/isl_ast_build_expr.c
@@ -12,6 +12,172 @@
 #include <isl_ast_private.h>
 #include <isl_ast_build_private.h>
 
+static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr);
+
+/* Compute the minimum of the integer affine expression "obj" over the points
+ * in build->domain and put the result in *opt.
+ */
+__isl_give isl_val *isl_ast_build_min(__isl_keep isl_ast_build *build,
+	__isl_keep isl_aff *obj)
+{
+	if (!build)
+		return NULL;
+
+	return isl_set_min_val(build->domain, obj);
+}
+
+/* Compute the maximum of the integer affine expression "obj" over the points
+ * in build->domain and put the result in *opt.
+ */
+__isl_give isl_val *isl_ast_build_max(__isl_keep isl_ast_build *build,
+	__isl_keep isl_aff *obj)
+{
+	if (!build)
+		return NULL;
+
+	return isl_set_max_val(build->domain, obj);
+}
+
+/* If the ast_build_compute_bounds is set, then compute bounds on "expr"
+ * based on the possible value of "aff" over build->domain.
+ */
+__isl_give isl_ast_expr *isl_ast_build_set_size(
+	__isl_keep isl_ast_build *build, __isl_take isl_ast_expr *expr,
+	__isl_keep isl_aff *aff)
+{
+	isl_val *res;
+	size_t bits;
+
+	if (!build || !expr)
+		return NULL;
+
+	if (!build->compute_bounds)
+		return expr;
+
+	isl_aff *tmp;
+	tmp = isl_aff_floor(isl_aff_copy(aff));
+	res = isl_ast_build_min(build, tmp);
+	isl_aff_free(tmp);
+
+	if (!isl_val_is_int(res)) {
+		isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+			"could not derive bounds",  goto error);
+	}
+
+	expr->is_signed = isl_val_is_neg(res);
+	expr->bits = isl_val_size_in_bits(res, expr->is_signed);
+	isl_val_free(res);
+
+	tmp = isl_aff_ceil(isl_aff_copy(aff));
+	res = isl_ast_build_max(build, tmp);
+	isl_aff_free(tmp);
+
+	if (!isl_val_is_int(res)) {
+		isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+			"could not derive bounds",  goto error);
+	}
+
+	expr->is_bounded = 1;
+	bits = isl_val_size_in_bits(res, expr->is_signed);
+	isl_val_free(res);
+
+	if (bits > expr->bits)
+		expr->bits = bits;
+
+	expr->known_size = 1;
+	return expr;
+
+error:
+	return isl_ast_expr_free(expr);
+}
+
+/* Data structure that holds an isl_ast_expr and its corresponding
+ * isl_aff.
+ */
+struct isl_ast_expr_constructor {
+	isl_ast_expr *expr;
+	isl_aff *aff;
+};
+typedef struct isl_ast_expr_constructor isl_ast_expr_constructor;
+
+__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff(__isl_take isl_aff *aff,
+	__isl_keep isl_ast_build *build);
+
+static void *isl_ast_expr_constructor_free(
+	__isl_take isl_ast_expr_constructor *cons)
+{
+	if (!cons)
+		return NULL;
+
+	isl_ast_expr_free(cons->expr);
+	isl_aff_free(cons->aff);
+	free(cons);
+	return NULL;
+}
+
+static __isl_give isl_ast_expr *isl_ast_expr_constructor_get_ast_expr(
+	__isl_take isl_ast_expr_constructor *cons)
+{
+	if (!cons)
+		return NULL;
+
+	return isl_ast_expr_copy(cons->expr);
+}
+
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_alloc(
+	__isl_take isl_local_space *ls)
+{
+	isl_ast_expr_constructor *cons;
+	isl_ctx *ctx;
+
+	if (!ls)
+		return NULL;
+
+	ctx = isl_local_space_get_ctx(ls);
+	cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+	if (!cons)
+		goto error;
+
+	cons->expr = isl_ast_expr_alloc_int_si(ctx, 0);
+	cons->aff = isl_aff_zero_on_domain(ls);
+
+	if (!cons->expr || !cons->aff)
+		return isl_ast_expr_constructor_free(cons);
+
+	return cons;
+error:
+	isl_local_space_free(ls);
+	return NULL;
+}
+
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_val(
+	__isl_take isl_local_space *ls, __isl_take isl_val *v,
+	__isl_keep isl_ast_build *build)
+{
+	isl_ast_expr_constructor *cons;
+	isl_ctx *ctx;
+
+	if (!ls)
+		return NULL;
+
+	ctx = isl_local_space_get_ctx(ls);
+	cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+	if (!cons)
+		goto error;
+
+	cons->aff = isl_aff_zero_on_domain(ls);
+	cons->aff = isl_aff_add_constant_val(cons->aff, isl_val_copy(v));
+	cons->expr = isl_ast_expr_from_val(v);
+
+	if (!cons->expr || !cons->aff)
+		return isl_ast_expr_constructor_free(cons);
+
+	return cons;
+error:
+	isl_local_space_free(ls);
+	return NULL;
+}
+
 /* Compute the "opposite" of the (numerator of the) argument of a div
  * with denonimator "d".
  *
@@ -29,6 +195,185 @@ static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
 	return aff;
 }
 
+/* Set the size of cons->expr based on range of values attained
+ * by cons->aff over build->domain.
+ */
+static void isl_ast_expr_constructor_set_size(
+	__isl_keep isl_ast_expr_constructor *cons,
+	__isl_keep isl_ast_build *build)
+{
+	cons->expr = isl_ast_build_set_size(build, cons->expr, cons->aff);
+}
+
+/* Add cons2->expr to cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add(
+		__isl_take isl_ast_expr_constructor *cons1,
+	__isl_take isl_ast_expr_constructor *cons2,
+	__isl_keep isl_ast_build *build)
+{
+	if (!cons1 || !cons2)
+		goto error;
+
+	if (isl_aff_plain_is_zero(cons1->aff)) {
+		isl_ast_expr_constructor_free(cons1);
+		return cons2;
+	}
+
+	if (isl_aff_plain_is_zero(cons2->aff)) {
+		isl_ast_expr_constructor_free(cons2);
+		return cons1;
+	}
+
+	cons1->expr = isl_ast_expr_add(cons1->expr,
+					isl_ast_expr_copy(cons2->expr));
+	cons1->aff = isl_aff_add(cons1->aff, isl_aff_copy(cons2->aff));
+	isl_ast_expr_constructor_set_size(cons1, build);
+
+	isl_ast_expr_constructor_free(cons2);
+
+	if (!cons1->expr || !cons1->aff)
+		return isl_ast_expr_constructor_free(cons1);
+	return cons1;
+error:
+	isl_ast_expr_constructor_free(cons2);
+	return isl_ast_expr_constructor_free(cons1);
+}
+
+/* Subtract cons2->expr from cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ *
+ * If cons2->expr is zero, we simply return cons1->expr.
+ * If cons1->expr is zero, we return
+ *
+ *      (isl_ast_op_minus, cons2->expr)
+ *
+ * Otherwise, we return
+ *
+ *      (isl_ast_op_sub, cons1->expr, cons2->expr)
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_sub(
+	__isl_take isl_ast_expr_constructor *cons1,
+	__isl_take isl_ast_expr_constructor *cons2,
+	__isl_keep isl_ast_build *build)
+{
+	if (!cons1 || !cons2)
+		goto error;
+
+	if (isl_aff_plain_is_zero(cons2->aff)) {
+		isl_ast_expr_constructor_free(cons2);
+		return cons1;
+	}
+
+	if (isl_aff_plain_is_zero(cons1->aff)) {
+		cons2->aff = isl_aff_neg(cons2->aff);
+		cons2->expr = isl_ast_expr_neg(cons2->expr);
+		isl_ast_expr_constructor_free(cons1);
+		isl_ast_expr_constructor_set_size(cons2, build);
+		if (!cons2->expr || !cons2->aff)
+			return isl_ast_expr_constructor_free(cons2);
+		return cons2;
+	}
+
+	cons1->expr = isl_ast_expr_sub(cons1->expr,
+					isl_ast_expr_copy(cons2->expr));
+	cons1->aff = isl_aff_sub(cons1->aff, isl_aff_copy(cons2->aff));
+	isl_ast_expr_constructor_set_size(cons1, build);
+
+	isl_ast_expr_constructor_free(cons2);
+
+	if (!cons1->expr || !cons1->aff)
+		return isl_ast_expr_constructor_free(cons1);
+	return cons1;
+error:
+	isl_ast_expr_constructor_free(cons2);
+	return isl_ast_expr_constructor_free(cons1);
+}
+
+/* Return an isl_ast_expr_constructor that represents
+ *
+ *      v * (aff mod d)
+ *
+ * v is assumed to be non-negative.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_mod(
+	__isl_take isl_val *v, __isl_keep isl_aff *aff,
+	__isl_take isl_val *d,
+	__isl_keep isl_ast_build *build)
+{
+	isl_ctx *ctx;
+	isl_ast_expr_constructor *cons;
+	isl_ast_expr *c;
+
+	if (!aff) {
+		isl_val_free(v);
+		isl_val_free(d);
+		return NULL;
+	}
+
+	ctx = isl_aff_get_ctx(aff);
+	cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+	if (!cons) {
+		isl_val_free(v);
+		isl_val_free(d);
+		return NULL;
+	}
+
+	cons->aff = isl_aff_copy(aff);
+	cons->expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
+
+	c = isl_ast_expr_from_val(isl_val_copy(d));
+	cons->expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r,
+						cons->expr, c);
+	cons->aff = isl_aff_mod_val(cons->aff, d);
+
+	isl_ast_expr_constructor_set_size(cons, build);
+
+	if (!isl_val_is_one(v)) {
+		c = isl_ast_expr_from_val(isl_val_copy(v));
+		cons->expr = isl_ast_expr_mul(c, cons->expr);
+		cons->aff = isl_aff_scale_val(cons->aff, isl_val_copy(v));
+		isl_ast_expr_constructor_set_size(cons, build);
+	}
+
+	if (!cons->expr || !cons->aff) {
+		isl_val_free(v);
+		return isl_ast_expr_constructor_free(cons);
+	}
+
+
+	isl_val_free(v);
+	return cons;
+}
+
+/* Devide cons2->expr by cons1->expr and compute the size of the result.
+ * The result is simplified in terms of build->domain.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_div(
+		__isl_take isl_ast_expr_constructor *cons1,
+	__isl_take isl_ast_expr_constructor *cons2,
+	__isl_keep isl_ast_build *build)
+{
+	if (!cons1 || !cons2)
+		goto error;
+
+	cons1->expr = isl_ast_expr_div(cons1->expr,
+					isl_ast_expr_copy(cons2->expr));
+	cons1->aff = isl_aff_div(cons1->aff, isl_aff_copy(cons2->aff));
+	isl_ast_expr_constructor_set_size(cons1, build);
+
+	isl_ast_expr_constructor_free(cons2);
+
+	if (!cons1->expr || !cons1->aff)
+		return isl_ast_expr_constructor_free(cons1);
+	return cons1;
+error:
+	isl_ast_expr_constructor_free(cons2);
+	return isl_ast_expr_constructor_free(cons1);
+}
+
 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
  * The result is simplified in terms of build->domain.
  *
@@ -127,6 +472,12 @@ static __isl_give isl_ast_expr *var(int *change_sign,
 	return isl_ast_expr_from_id(id);
 }
 
+/* Add an expression for "v" to cons->expr.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int(
+	__isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v,
+	__isl_keep isl_ast_build *build);
+
 /* Does "expr" represent the zero integer?
  */
 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
@@ -198,38 +549,6 @@ error:
 	return NULL;
 }
 
-/* Return an isl_ast_expr that represents
- *
- *	v * (aff mod d)
- *
- * v is assumed to be non-negative.
- * The result is simplified in terms of build->domain.
- */
-static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
-	__isl_keep isl_aff *aff, __isl_keep isl_val *d,
-	__isl_keep isl_ast_build *build)
-{
-	isl_ctx *ctx;
-	isl_ast_expr *expr;
-	isl_ast_expr *c;
-
-	if (!aff)
-		return NULL;
-
-	ctx = isl_aff_get_ctx(aff);
-	expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
-
-	c = isl_ast_expr_from_val(isl_val_copy(d));
-	expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
-
-	if (!isl_val_is_one(v)) {
-		c = isl_ast_expr_from_val(isl_val_copy(v));
-		expr = isl_ast_expr_mul(c, expr);
-	}
-
-	return expr;
-}
-
 /* Create an isl_ast_expr that scales "expr" by "v".
  *
  * If v is 1, we simply return expr.
@@ -241,33 +560,78 @@ static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
  *
  *	(isl_ast_op_mul, expr(v), expr)
  */
-static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
-	__isl_take isl_val *v)
+static __isl_give isl_ast_expr_constructor *scale(
+	__isl_take isl_ast_expr_constructor *cons,
+	__isl_take isl_val *v, __isl_keep isl_ast_build *build)
 {
 	isl_ast_expr *c;
 
-	if (!expr || !v)
+	if (!cons || !v)
 		goto error;
 	if (isl_val_is_one(v)) {
 		isl_val_free(v);
-		return expr;
+		return cons;
 	}
 
 	if (isl_val_is_negone(v)) {
 		isl_val_free(v);
-		expr = isl_ast_expr_neg(expr);
+		cons->expr = isl_ast_expr_neg(cons->expr);
+		cons->aff = isl_aff_neg(cons->aff);
 	} else {
-		c = isl_ast_expr_from_val(v);
-		expr = isl_ast_expr_mul(c, expr);
+		c = isl_ast_expr_from_val(isl_val_copy(v));
+		cons->expr = isl_ast_expr_mul(c, cons->expr);
+		cons->aff = isl_aff_scale_val(cons->aff, v);
 	}
 
-	return expr;
+	isl_ast_expr_constructor_set_size(cons, build);
+
+	return cons;
 error:
 	isl_val_free(v);
-	isl_ast_expr_free(expr);
+	isl_ast_expr_constructor_free(cons);
 	return NULL;
 }
 
+/* Create an isl_ast_expr evaluating "v" times the specified dimension of "ls".
+ * The result is simplified in terms of build->domain.
+ *
+ * Let e be the expression for the specified dimension.
+ * If v is 1, we simply return e.
+ * If v is -1, we return
+ *
+ *	(isl_ast_op_minus, e)
+ *
+ * Otherwise, we return
+ *
+ *	(isl_ast_op_mul, expr(v), e)
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_term(
+	int *change_sign,
+	__isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
+	__isl_keep isl_ast_build *build)
+{
+	isl_ctx *ctx;
+	isl_ast_expr_constructor *cons;
+
+	if (!ls)
+		return NULL;
+
+	ctx = isl_local_space_get_ctx(ls);
+	cons = isl_alloc_type(ctx, isl_ast_expr_constructor);
+	if (!cons)
+		return NULL;
+
+	*change_sign = 0;
+
+	cons->expr = var(change_sign, ls, type, pos, build);
+	cons->aff = isl_aff_var_on_domain(isl_local_space_copy(ls), type, pos);
+	isl_ast_expr_constructor_set_size(cons, build);
+
+	if (!cons->expr || !cons->aff)
+		return isl_ast_expr_constructor_free(cons);
+	return cons;
+}
+
 /* Add an expression for "*v" times the specified dimension of "ls"
  * to expr.
  *
@@ -288,29 +652,33 @@ error:
  *	(isl_ast_op_add, expr, e)
  *
  */
-static __isl_give isl_ast_expr *isl_ast_expr_add_term(
-	__isl_take isl_ast_expr *expr,
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_term(
+	__isl_take isl_ast_expr_constructor *cons,
 	__isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
 	__isl_take isl_val *v, __isl_keep isl_ast_build *build)
 {
-	isl_ast_expr *term;
 	int change_sign;
+	isl_ast_expr_constructor *term;
 
-	if (!expr)
+	if (!cons)
 		return NULL;
 
 	change_sign = 0;
-	term = var(&change_sign, ls, type, pos, build);
+
+	term = isl_ast_expr_constructor_term(&change_sign, ls, type, pos, build);
+
 	if (change_sign)
 		v = isl_val_neg(v);
 
-	if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
+	if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) {
 		v = isl_val_neg(v);
-		term = scale(term, v);
-		return ast_expr_sub(expr, term);
+		term = scale(term, v, build);
+		cons = isl_ast_expr_constructor_sub(cons, term, build);
+		return cons;
 	} else {
-		term = scale(term, v);
-		return ast_expr_add(expr, term);
+		term = scale(term, v, build);
+		cons = isl_ast_expr_constructor_add(cons, term, build);
+		return cons;
 	}
 }
 
@@ -345,6 +713,41 @@ error:
 	return NULL;
 }
 
+/* Add an expression for "v" to expr.
+ */
+static __isl_give isl_ast_expr_constructor *isl_ast_expr_constructor_add_int(
+	__isl_take isl_ast_expr_constructor *cons, __isl_take isl_val *v,
+	__isl_keep isl_ast_build *build)
+{
+	isl_local_space *ls;
+	isl_ast_expr_constructor *cons_int;
+
+	if (!cons || !v)
+		goto error;
+
+	if (isl_val_is_zero(v)) {
+		isl_val_free(v);
+		return cons;
+	}
+
+	ls = isl_aff_get_domain_local_space(cons->aff);
+
+	if (isl_val_is_neg(v) && !ast_expr_is_zero(cons->expr)) {
+		v = isl_val_neg(v);
+		cons_int = isl_ast_expr_constructor_val(ls, v, build);
+		cons = isl_ast_expr_constructor_sub(cons, cons_int, build);
+	} else {
+		cons_int = isl_ast_expr_constructor_val(ls, v, build);
+		cons = isl_ast_expr_constructor_add(cons, cons_int, build);
+	}
+
+	return cons;
+error:
+	isl_ast_expr_constructor_free(cons);
+	isl_val_free(v);
+	return NULL;
+}
+
 /* Internal data structure used inside extract_modulos.
  *
  * If any modulo expressions are detected in "aff", then the
@@ -371,8 +774,8 @@ struct isl_extract_mod_data {
 	isl_ast_build *build;
 	isl_aff *aff;
 
-	isl_ast_expr *pos;
-	isl_ast_expr *neg;
+	isl_ast_expr_constructor *pos;
+	isl_ast_expr_constructor *neg;
 
 	isl_aff *add;
 
@@ -400,20 +803,22 @@ struct isl_extract_mod_data {
  * to data->neg or data->pos depending on the sign of -f.
  */
 static int extract_term_and_mod(struct isl_extract_mod_data *data,
-	__isl_take isl_aff *term, __isl_take isl_aff *arg)
+	__isl_take isl_aff *term, __isl_take isl_aff *arg,
+	__isl_keep isl_ast_build *build)
 {
-	isl_ast_expr *expr;
+	isl_ast_expr_constructor *cons;
 	int s;
 
 	data->v = isl_val_div(data->v, isl_val_copy(data->d));
 	s = isl_val_sgn(data->v);
 	data->v = isl_val_abs(data->v);
-	expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
+	cons = isl_ast_expr_constructor_mod(isl_val_copy(data->v), arg,
+						isl_val_copy(data->d), data->build);
 	isl_aff_free(arg);
 	if (s > 0)
-		data->neg = ast_expr_add(data->neg, expr);
+		data->neg = isl_ast_expr_constructor_add(data->neg, cons, build);
 	else
-		data->pos = ast_expr_add(data->pos, expr);
+		data->pos = isl_ast_expr_constructor_add(data->pos, cons, build);
 	data->aff = isl_aff_set_coefficient_si(data->aff,
 						isl_dim_div, data->i, 0);
 	if (s < 0)
@@ -448,10 +853,11 @@ static int extract_term_and_mod(struct isl_extract_mod_data *data,
  *
  * to data->neg or data->pos depending on the sign of -f.
  */
-static int extract_mod(struct isl_extract_mod_data *data)
+static int extract_mod(struct isl_extract_mod_data *data,
+	__isl_keep isl_ast_build *build)
 {
 	return extract_term_and_mod(data, isl_aff_copy(data->div),
-			isl_aff_copy(data->div));
+			isl_aff_copy(data->div), build);
 }
 
 /* Given that data->v * div_i in data->aff is of the form
@@ -472,7 +878,8 @@ static int extract_mod(struct isl_extract_mod_data *data)
  *
  * This function may modify data->div.
  */
-static int extract_nonneg_mod(struct isl_extract_mod_data *data)
+static int extract_nonneg_mod(struct isl_extract_mod_data *data,
+	__isl_take isl_ast_build *build)
 {
 	int mod;
 
@@ -480,7 +887,7 @@ static int extract_nonneg_mod(struct isl_extract_mod_data *data)
 	if (mod < 0)
 		goto error;
 	if (mod)
-		return extract_mod(data);
+		return extract_mod(data, build);
 
 	data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
 	mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
@@ -488,7 +895,7 @@ static int extract_nonneg_mod(struct isl_extract_mod_data *data)
 		goto error;
 	if (mod) {
 		data->v = isl_val_neg(data->v);
-		return extract_mod(data);
+		return extract_mod(data, build);
 	}
 
 	return 0;
@@ -679,7 +1086,8 @@ static int check_parallel_or_opposite(__isl_take isl_constraint *c, void *user)
  * Alternatively, we could first compute the dual of the domain
  * and plug in the constraints on the coefficients.
  */
-static int try_extract_mod(struct isl_extract_mod_data *data)
+static int try_extract_mod(struct isl_extract_mod_data *data,
+	__isl_keep isl_ast_build *build)
 {
 	isl_basic_set *hull;
 	isl_val *v1, *v2;
@@ -691,7 +1099,7 @@ static int try_extract_mod(struct isl_extract_mod_data *data)
 	int n = isl_aff_dim(data->div, isl_dim_div);
 
 	if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
-		return extract_nonneg_mod(data);
+		return extract_nonneg_mod(data, build);
 
 	hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
 	hull = isl_basic_set_remove_divs(hull);
@@ -705,7 +1113,7 @@ static int try_extract_mod(struct isl_extract_mod_data *data)
 		isl_aff_free(data->nonneg);
 		if (r < 0)
 			goto error;
-		return extract_nonneg_mod(data);
+		return extract_nonneg_mod(data, build);
 	}
 
 	v1 = isl_aff_get_constant_val(data->div);
@@ -733,7 +1141,7 @@ static int try_extract_mod(struct isl_extract_mod_data *data)
 	}
 
 	return extract_term_and_mod(data,
-				    isl_aff_copy(data->div), data->nonneg);
+				    isl_aff_copy(data->div), data->nonneg, build);
 error:
 	data->aff = isl_aff_free(data->aff);
 	return -1;
@@ -770,13 +1178,14 @@ error:
  *
  * and still extract a modulo.
  */
-static int extract_modulo(struct isl_extract_mod_data *data)
+static int extract_modulo(struct isl_extract_mod_data *data,
+	__isl_keep isl_ast_build *build)
 {
 	data->div = isl_aff_get_div(data->aff, data->i);
 	data->d = isl_aff_get_denominator_val(data->div);
 	if (isl_val_is_divisible_by(data->v, data->d)) {
 		data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
-		if (try_extract_mod(data) < 0)
+		if (try_extract_mod(data, build) < 0)
 			data->aff = isl_aff_free(data->aff);
 	}
 	isl_aff_free(data->div);
@@ -808,10 +1217,11 @@ static int extract_modulo(struct isl_extract_mod_data *data)
  * If f < 0, we add ((-f) * (a mod m)) to *pos.
  */
 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
-	__isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
+	__isl_keep isl_ast_expr_constructor **cons_pos,
+	__isl_keep isl_ast_expr_constructor **cons_neg,
 	__isl_keep isl_ast_build *build)
 {
-	struct isl_extract_mod_data data = { build, aff, *pos, *neg };
+	struct isl_extract_mod_data data = { build, aff, *cons_pos, *cons_neg };
 	isl_ctx *ctx;
 	int n;
 
@@ -833,7 +1243,7 @@ static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
 			isl_val_free(data.v);
 			continue;
 		}
-		if (extract_modulo(&data) < 0)
+		if (extract_modulo(&data, build) < 0)
 			data.aff = isl_aff_free(data.aff);
 		isl_val_free(data.v);
 		if (!data.aff)
@@ -843,8 +1253,8 @@ static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
 	if (data.add)
 		data.aff = isl_aff_add(data.aff, data.add);
 
-	*pos = data.pos;
-	*neg = data.neg;
+	*cons_pos = data.pos;
+	*cons_neg = data.neg;
 	return data.aff;
 }
 
@@ -857,12 +1267,12 @@ static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
  * Return aff1 and add (aff2 / d) to *expr.
  */
 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
-	__isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
+	__isl_keep isl_ast_expr_constructor **cons, __isl_keep isl_ast_build *build)
 {
 	int i, j, n;
 	isl_aff *rat = NULL;
 	isl_local_space *ls = NULL;
-	isl_ast_expr *rat_expr;
+	isl_ast_expr_constructor *rat_cons;
 	isl_val *v, *d;
 	enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
 	enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
@@ -911,14 +1321,12 @@ static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
 		rat = isl_aff_add(rat, rat_0);
 	}
 
-	isl_local_space_free(ls);
-
 	aff = isl_aff_sub(aff, isl_aff_copy(rat));
 	aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
 
-	rat_expr = isl_ast_expr_from_aff(rat, build);
-	rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
-	*expr = ast_expr_add(*expr, rat_expr);
+	rat_cons = ast_expr_constructor_from_aff(rat, build);
+	rat_cons = isl_ast_expr_constructor_div(rat_cons, isl_ast_expr_constructor_val(ls, d, build), build);
+	*cons = isl_ast_expr_constructor_add(*cons, rat_cons, build);
 
 	return aff;
 error:
@@ -937,14 +1345,13 @@ error:
  * Finally, if the affine expression has a non-trivial denominator,
  * we divide the resulting isl_ast_expr by this denominator.
  */
-__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
+__isl_give isl_ast_expr_constructor *ast_expr_constructor_from_aff(__isl_take isl_aff *aff,
 	__isl_keep isl_ast_build *build)
 {
 	int i, j;
 	int n;
 	isl_val *v;
-	isl_ctx *ctx = isl_aff_get_ctx(aff);
-	isl_ast_expr *expr, *expr_neg;
+	isl_ast_expr_constructor *cons, *cons_neg;
 	enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
 	enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
 	isl_local_space *ls;
@@ -952,36 +1359,50 @@ __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
 	if (!aff)
 		return NULL;
 
-	expr = isl_ast_expr_alloc_int_si(ctx, 0);
-	expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
-
-	aff = extract_rational(aff, &expr, build);
-
-	aff = extract_modulos(aff, &expr, &expr_neg, build);
-	expr = ast_expr_sub(expr, expr_neg);
-
 	ls = isl_aff_get_domain_local_space(aff);
+	cons = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+	cons_neg = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+	aff = extract_rational(aff, &cons, build);
+	aff = extract_modulos(aff, &cons, &cons_neg, build);
+
+	cons = isl_ast_expr_constructor_sub(cons, cons_neg, build);
 
 	for (i = 0; i < 3; ++i) {
 		n = isl_aff_dim(aff, t[i]);
 		for (j = 0; j < n; ++j) {
 			v = isl_aff_get_coefficient_val(aff, t[i], j);
 			if (!v)
-				expr = isl_ast_expr_free(expr);
+				cons = isl_ast_expr_constructor_free(cons);
 			if (isl_val_is_zero(v)) {
 				isl_val_free(v);
 				continue;
 			}
-			expr = isl_ast_expr_add_term(expr,
+			cons = isl_ast_expr_constructor_add_term(cons,
 							ls, l[i], j, v, build);
 		}
 	}
 
 	v = isl_aff_get_constant_val(aff);
-	expr = isl_ast_expr_add_int(expr, v);
+	cons = isl_ast_expr_constructor_add_int(cons, v, build);
 
 	isl_local_space_free(ls);
 	isl_aff_free(aff);
+	return cons;
+}
+
+/* Construct an isl_ast_expr that evaluates the affine expression "aff",
+ * The result is simplified in terms of build->domain.
+ */
+__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
+	__isl_keep isl_ast_build *build)
+{
+	isl_ast_expr_constructor *cons;
+	isl_ast_expr *expr;
+
+	cons = ast_expr_constructor_from_aff(aff, build);
+	expr = isl_ast_expr_constructor_get_ast_expr(cons);
+	isl_ast_expr_constructor_free(cons);
+
 	return expr;
 }
 
@@ -989,7 +1410,8 @@ __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
  * with sign equal to "sign".
  * The result is simplified in terms of build->domain.
  */
-static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
+static __isl_give isl_ast_expr_constructor *add_signed_terms(
+	__isl_take isl_ast_expr_constructor *cons,
 	__isl_keep isl_aff *aff, int sign, __isl_keep isl_ast_build *build)
 {
 	int i, j;
@@ -1009,14 +1431,14 @@ static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
 				continue;
 			}
 			v = isl_val_abs(v);
-			expr = isl_ast_expr_add_term(expr,
+			cons = isl_ast_expr_constructor_add_term(cons,
 						ls, l[i], j, v, build);
 		}
 	}
 
 	isl_local_space_free(ls);
 
-	return expr;
+	return cons;
 }
 
 /* Should the constant term "v" be considered positive?
@@ -1065,28 +1487,35 @@ static int constant_is_considered_positive(__isl_keep isl_val *v,
 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
 	__isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
 {
-	isl_ctx *ctx;
 	isl_ast_expr *expr_pos;
 	isl_ast_expr *expr_neg;
 	isl_ast_expr *expr;
+	isl_ast_expr_constructor *cons_pos, *cons_neg;
 	isl_aff *aff;
 	isl_val *v;
 	int eq;
+	isl_local_space *ls;
 	enum isl_ast_op_type type;
 
 	if (!constraint)
 		return NULL;
 
 	aff = isl_constraint_get_aff(constraint);
+	ls = isl_aff_get_domain_local_space(aff);
+
+	cons_pos = isl_ast_expr_constructor_alloc(isl_local_space_copy(ls));
+	cons_neg = isl_ast_expr_constructor_alloc(ls);
+
+	aff = extract_modulos(aff, &cons_pos, &cons_neg, build);
 
-	ctx = isl_constraint_get_ctx(constraint);
-	expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
-	expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
+	cons_pos = add_signed_terms(cons_pos, aff, 1, build);
+	cons_neg = add_signed_terms(cons_neg, aff, -1, build);
 
-	aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
+	expr_pos = isl_ast_expr_constructor_get_ast_expr(cons_pos);
+	expr_neg = isl_ast_expr_constructor_get_ast_expr(cons_neg);
 
-	expr_pos = add_signed_terms(expr_pos, aff, 1, build);
-	expr_neg = add_signed_terms(expr_neg, aff, -1, build);
+	isl_ast_expr_constructor_free(cons_pos);
+	isl_ast_expr_constructor_free(cons_neg);
 
 	v = isl_aff_get_constant_val(aff);
 	if (constant_is_considered_positive(v, expr_pos, expr_neg)) {
diff --git a/isl_ast_build_private.h b/isl_ast_build_private.h
index fe80be7..790d9d6 100644
--- a/isl_ast_build_private.h
+++ b/isl_ast_build_private.h
@@ -17,6 +17,8 @@ enum isl_ast_build_domain_type {
  * generated.  That is, it (mostly) contains information about outer
  * loops that can be used to simplify inner loops.
  *
+ * "compute_bounds" is a local copy of the corresponding option.
+ *
  * "domain" represents constraints on the internal schedule domain,
  * corresponding to the context of the AST generation and the constraints
  * implied by the loops that have already been generated.
@@ -120,6 +122,8 @@ enum isl_ast_build_domain_type {
 struct isl_ast_build {
 	int ref;
 
+	int compute_bounds;
+
 	int outer_pos;
 	int depth;
 
@@ -160,6 +164,8 @@ struct isl_ast_build {
 	int single_valued;
 };
 
+__isl_give isl_ast_build *isl_ast_build_init_options(
+	__isl_take isl_ast_build *context);
 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
 	__isl_take isl_ast_build *build);
 __isl_give isl_ast_build *isl_ast_build_increase_depth(
diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c
index 3626b68..27ec84e 100644
--- a/isl_ast_codegen.c
+++ b/isl_ast_codegen.c
@@ -3803,6 +3803,7 @@ __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
 
 	build = isl_ast_build_copy(build);
 	build = isl_ast_build_set_single_valued(build, 0);
+	build = isl_ast_build_init_options(build);
 	schedule = isl_union_map_coalesce(schedule);
 	executed = isl_union_map_reverse(schedule);
 	list = generate_code(executed, isl_ast_build_copy(build), 0);
diff --git a/isl_ast_private.h b/isl_ast_private.h
index c1bf334..9819800 100644
--- a/isl_ast_private.h
+++ b/isl_ast_private.h
@@ -16,6 +16,10 @@ struct isl_ast_expr {
 
 	isl_ctx *ctx;
 
+	unsigned known_size : 1;
+	unsigned is_bounded : 1;
+	unsigned is_signed : 1;
+	size_t bits;
 	enum isl_ast_expr_type type;
 
 	union {
diff --git a/isl_options.c b/isl_options.c
index efeb261..37fcd75 100644
--- a/isl_options.c
+++ b/isl_options.c
@@ -155,6 +155,8 @@ ISL_ARG_BOOL(struct isl_options, ast_build_atomic_upper_bound, 0,
 	"ast-build-atomic-upper-bound", 1, "generate atomic upper bounds")
 ISL_ARG_BOOL(struct isl_options, ast_build_prefer_pdiv, 0,
 	"ast-build-prefer-pdiv", 1, "prefer pdiv operation over fdiv")
+ISL_ARG_BOOL(struct isl_options, ast_build_compute_bounds, 1,
+	"ast-build-compute-bounds", 1, "compute bounds on isl_ast_expr objects")
 ISL_ARG_BOOL(struct isl_options, ast_build_exploit_nested_bounds, 0,
 	"ast-build-exploit-nested-bounds", 1,
 	"simplify conditions based on bounds of nested for loops")
@@ -262,6 +264,11 @@ ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
 	ast_build_prefer_pdiv)
 
 ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+	ast_build_compute_bounds)
+ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
+	ast_build_compute_bounds)
+
+ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
 	ast_build_exploit_nested_bounds)
 ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args,
 	ast_build_exploit_nested_bounds)
diff --git a/isl_options_private.h b/isl_options_private.h
index bb73d68..76a3365 100644
--- a/isl_options_private.h
+++ b/isl_options_private.h
@@ -52,6 +52,7 @@ struct isl_options {
 
 	int			ast_build_atomic_upper_bound;
 	int			ast_build_prefer_pdiv;
+	int			ast_build_compute_bounds;
 	int			ast_build_exploit_nested_bounds;
 	int			ast_build_group_coscheduled;
 	int			ast_build_separation_bounds;
diff --git a/test_inputs/codegen/bounds/ast_exprs/const_integer.c b/test_inputs/codegen/bounds/ast_exprs/const_integer.c
new file mode 100644
index 0000000..04c0f8e
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/const_integer.c
@@ -0,0 +1 @@
+A(0, 1, 2, 3, 4, -1, -2, -3, -4);
diff --git a/test_inputs/codegen/bounds/ast_exprs/const_integer.in b/test_inputs/codegen/bounds/ast_exprs/const_integer.in
new file mode 100644
index 0000000..fc26c49
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/const_integer.in
@@ -0,0 +1,3 @@
+{ A[0, 1, 2, 3, 4, -1, -2, -3, -4] -> [0]}
+{ :}
+{ }
diff --git a/test_inputs/codegen/bounds/ast_exprs/const_parameters.c b/test_inputs/codegen/bounds/ast_exprs/const_parameters.c
new file mode 100644
index 0000000..4157eb6
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/const_parameters.c
@@ -0,0 +1 @@
+A(n1, n2, n3, n4);
diff --git a/test_inputs/codegen/bounds/ast_exprs/const_parameters.in b/test_inputs/codegen/bounds/ast_exprs/const_parameters.in
new file mode 100644
index 0000000..d376124
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/const_parameters.in
@@ -0,0 +1,3 @@
+[n1, n2, n3, n4] -> { A[n1, n2, n3, n4] -> [0]}
+[n1, n2, n3, n4] ->  { : 0 <= n1 < 2 and 0 <= n2 < 4 and 0 <= n3 < 8 and -1 <= n4 < 8}
+[n1, n2, n3, n4] ->  { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/div.c b/test_inputs/codegen/bounds/ast_exprs/div.c
new file mode 100644
index 0000000..331b098
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/div.c
@@ -0,0 +1,2 @@
+if ((uint3)((uint4)(n) % (uint4)(8)) == (uint3)(0))
+  A((uint4)(n) / (uint4)(8));
diff --git a/test_inputs/codegen/bounds/ast_exprs/div.in b/test_inputs/codegen/bounds/ast_exprs/div.in
new file mode 100644
index 0000000..cecdf7e
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/div.in
@@ -0,0 +1,3 @@
+[n,m] -> { A[(n/8)] -> [0]  }
+[n,m] -> { : 0 <= n < 16 and 0 <= m < 8}
+[n,m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/floord.in b/test_inputs/codegen/bounds/ast_exprs/floord.in
new file mode 100644
index 0000000..aa0f8b0
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/floord.in
@@ -0,0 +1,3 @@
+[n, m] -> { A[i] -> [i,j]: 0 <= i < (n/7) and -5 <= j < (m/7)}
+[n, m] -> { : 0 <= n < 16 and -2 <= m < 16}
+[n, m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/max.in b/test_inputs/codegen/bounds/ast_exprs/max.in
new file mode 100644
index 0000000..c71c3b8
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/max.in
@@ -0,0 +1,3 @@
+[n,m] -> { A[i] -> [i]: n <= i and m <= i and i < 100}
+[n,m] -> { : 0 <= n < 16 and 0 <= m < 8}
+[n,m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/min.in b/test_inputs/codegen/bounds/ast_exprs/min.in
new file mode 100644
index 0000000..5274be7
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/min.in
@@ -0,0 +1,3 @@
+[n,m] -> { A[i] -> [i]: 0 <= i and i < n and i < m}
+[n,m] -> { : 0 <= n < 16 and 0 <= m < 8}
+[n,m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/product.c b/test_inputs/codegen/bounds/ast_exprs/product.c
new file mode 100644
index 0000000..f897b90
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/product.c
@@ -0,0 +1 @@
+A(0, m, -(int3)(m), (uint6)(16) * (uint6)(m), (int7)(-16) * (int7)(m));
diff --git a/test_inputs/codegen/bounds/ast_exprs/product.in b/test_inputs/codegen/bounds/ast_exprs/product.in
new file mode 100644
index 0000000..cbf584f
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/product.in
@@ -0,0 +1,3 @@
+[m] -> { A[0 *m, 1 * m, -1 *m, 16 * m, -16 * m] -> [0]}
+[m] -> { : 0 < m < 4}
+[m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/select.in b/test_inputs/codegen/bounds/ast_exprs/select.in
new file mode 100644
index 0000000..59782ca
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/select.in
@@ -0,0 +1,3 @@
+[n,m] -> { A[n] -> [0]: n > m; A[m] -> [0]: n <= m }
+[n,m] -> { : 0 <= n < 4 and 0 <= m < 8}
+[n,m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/sum.c b/test_inputs/codegen/bounds/ast_exprs/sum.c
new file mode 100644
index 0000000..0477336
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/sum.c
@@ -0,0 +1 @@
+A((uint7)((uint4)(2) * (uint4)(n)) + (uint7)((uint7)(4) * (uint7)(m)), (int7)((uint4)(2) * (uint4)(n)) - (int7)((uint7)(4) * (uint7)(m)), (int6)(-2) * (int6)(m));
diff --git a/test_inputs/codegen/bounds/ast_exprs/sum.in b/test_inputs/codegen/bounds/ast_exprs/sum.in
new file mode 100644
index 0000000..2aa81a2
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/sum.in
@@ -0,0 +1,3 @@
+[n,m] -> { A[2 * n + 4 * m, 2 * n - 4 * m, 0 - 2*m] -> [0]}
+[n,m] -> { : 0 <= n <= 4 and 0 <= m <= 16}
+[n,m] -> { }
diff --git a/test_inputs/codegen/bounds/ast_exprs/sum2.in b/test_inputs/codegen/bounds/ast_exprs/sum2.in
new file mode 100644
index 0000000..9189e72
--- /dev/null
+++ b/test_inputs/codegen/bounds/ast_exprs/sum2.in
@@ -0,0 +1,3 @@
+[n,m,o,p] -> { A[n+m, n+o, n+p] -> [0]}
+[n,m,o,p] -> { : 0 <= n,m,o< 4 and n+o < 4 and -1 <= p <= 1}
+[n,m,o,p] -> { }
-- 
1.8.3.2


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]