From 7dde2684397e731a77e73e212683baf37bba224d Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Wed, 29 Jan 2014 10:56:53 +0100
Subject: [PATCH] move pet_expr functions to separate file

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 Makefile.am  |    2 +
 emit.c       |    1 +
 expr.c       | 1206 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 expr.h       |   74 ++++
 parse.c      |    1 +
 print.c      |    1 +
 scan.cc      |    1 +
 scop.c       | 1190 ++-------------------------------------------------------
 scop.h       |   41 --
 scop_plus.cc |    1 +
 10 files changed, 1323 insertions(+), 1195 deletions(-)
 create mode 100644 expr.c
 create mode 100644 expr.h

diff --git a/Makefile.am b/Makefile.am
index 23f5680..a41163a 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -36,6 +36,8 @@ AM_LDFLAGS = $(CLANG_LDFLAGS)
 libpet_la_SOURCES = \
 	clang.h \
 	clang.cc \
+	expr.h \
+	expr.c \
 	filter.h \
 	filter.c \
 	options.h \
diff --git a/emit.c b/emit.c
index f390c9b..86add07 100644
--- a/emit.c
+++ b/emit.c
@@ -34,6 +34,7 @@
 
 #include <yaml.h>
 
+#include "expr.h"
 #include "scop.h"
 #include "scop_yaml.h"
 
diff --git a/expr.c b/expr.c
new file mode 100644
index 0000000..d329abf
--- /dev/null
+++ b/expr.c
@@ -0,0 +1,1206 @@
+/*
+ * Copyright 2011      Leiden University. All rights reserved.
+ * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ *    1. Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *
+ *    2. Redistributions in binary form must reproduce the above
+ *       copyright notice, this list of conditions and the following
+ *       disclaimer in the documentation and/or other materials provided
+ *       with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
+ * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * The views and conclusions contained in the software and documentation
+ * are those of the authors and should not be interpreted as
+ * representing official policies, either expressed or implied, of
+ * Leiden University.
+ */
+
+#include <string.h>
+
+#include "expr.h"
+#include "filter.h"
+
+#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
+
+static char *type_str[] = {
+	[pet_expr_access] = "access",
+	[pet_expr_call] = "call",
+	[pet_expr_cast] = "cast",
+	[pet_expr_double] = "double",
+	[pet_expr_int] = "int",
+	[pet_expr_op] = "op",
+};
+
+static char *op_str[] = {
+	[pet_op_add_assign] = "+=",
+	[pet_op_sub_assign] = "-=",
+	[pet_op_mul_assign] = "*=",
+	[pet_op_div_assign] = "/=",
+	[pet_op_assign] = "=",
+	[pet_op_add] = "+",
+	[pet_op_sub] = "-",
+	[pet_op_mul] = "*",
+	[pet_op_div] = "/",
+	[pet_op_mod] = "%",
+	[pet_op_shl] = "<<",
+	[pet_op_shr] = ">>",
+	[pet_op_eq] = "==",
+	[pet_op_ne] = "!=",
+	[pet_op_le] = "<=",
+	[pet_op_ge] = ">=",
+	[pet_op_lt] = "<",
+	[pet_op_gt] = ">",
+	[pet_op_minus] = "-",
+	[pet_op_post_inc] = "++",
+	[pet_op_post_dec] = "--",
+	[pet_op_pre_inc] = "++",
+	[pet_op_pre_dec] = "--",
+	[pet_op_address_of] = "&",
+	[pet_op_and] = "&",
+	[pet_op_xor] = "^",
+	[pet_op_or] = "|",
+	[pet_op_not] = "~",
+	[pet_op_land] = "&&",
+	[pet_op_lor] = "||",
+	[pet_op_lnot] = "!",
+	[pet_op_cond] = "?:",
+	[pet_op_assume] = "assume",
+	[pet_op_kill] = "kill"
+};
+
+const char *pet_op_str(enum pet_op_type op)
+{
+	return op_str[op];
+}
+
+int pet_op_is_inc_dec(enum pet_op_type op)
+{
+	return op == pet_op_post_inc || op == pet_op_post_dec ||
+	    op == pet_op_pre_inc || op == pet_op_pre_dec;
+}
+
+const char *pet_type_str(enum pet_expr_type type)
+{
+	return type_str[type];
+}
+
+enum pet_op_type pet_str_op(const char *str)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(op_str); ++i)
+		if (!strcmp(op_str[i], str))
+			return i;
+
+	return -1;
+}
+
+enum pet_expr_type pet_str_type(const char *str)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(type_str); ++i)
+		if (!strcmp(type_str[i], str))
+			return i;
+
+	return -1;
+}
+
+/* Construct an access pet_expr from an access relation and an index expression.
+ * By default, it is considered to be a read access.
+ */
+struct pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
+	__isl_take isl_multi_pw_aff *index)
+{
+	isl_ctx *ctx = isl_map_get_ctx(access);
+	struct pet_expr *expr;
+
+	if (!index || !access)
+		goto error;
+	expr = isl_calloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_access;
+	expr->acc.access = access;
+	expr->acc.index = index;
+	expr->acc.read = 1;
+	expr->acc.write = 0;
+
+	return expr;
+error:
+	isl_map_free(access);
+	isl_multi_pw_aff_free(index);
+	return NULL;
+}
+
+/* Construct an access pet_expr from an index expression.
+ * By default, the access is considered to be a read access.
+ */
+struct pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
+{
+	isl_map *access;
+
+	access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
+	return pet_expr_from_access_and_index(access, index);
+}
+
+/* Extend the range of "access" with "n" dimensions, retaining
+ * the tuple identifier on this range.
+ *
+ * If "access" represents a member access, then extend the range
+ * of the member.
+ */
+static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
+{
+	isl_id *id;
+
+	id = isl_map_get_tuple_id(access, isl_dim_out);
+
+	if (!isl_map_range_is_wrapping(access)) {
+		access = isl_map_add_dims(access, isl_dim_out, n);
+	} else {
+		isl_map *domain;
+
+		domain = isl_map_copy(access);
+		domain = isl_map_range_factor_domain(domain);
+		access = isl_map_range_factor_range(access);
+		access = extend_range(access, n);
+		access = isl_map_range_product(domain, access);
+	}
+
+	access = isl_map_set_tuple_id(access, isl_dim_out, id);
+
+	return access;
+}
+
+/* Construct an access pet_expr from an index expression and
+ * the depth of the accessed array.
+ * By default, the access is considered to be a read access.
+ *
+ * If the number of indices is smaller than the depth of the array,
+ * then we assume that all elements of the remaining dimensions
+ * are accessed.
+ */
+struct pet_expr *pet_expr_from_index_and_depth(
+	__isl_take isl_multi_pw_aff *index, int depth)
+{
+	isl_map *access;
+	int dim;
+
+	access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
+	if (!access)
+		goto error;
+	dim = isl_map_dim(access, isl_dim_out);
+	if (dim > depth)
+		isl_die(isl_map_get_ctx(access), isl_error_internal,
+			"number of indices greater than depth",
+			access = isl_map_free(access));
+	if (dim == depth)
+		return pet_expr_from_access_and_index(access, index);
+
+	access = extend_range(access, depth - dim);
+
+	return pet_expr_from_access_and_index(access, index);
+error:
+	isl_multi_pw_aff_free(index);
+	return NULL;
+}
+
+/* Construct a pet_expr that kills the elements specified by
+ * the index expression "index" and the access relation "access".
+ */
+struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
+	__isl_take isl_multi_pw_aff *index)
+{
+	isl_ctx *ctx;
+	struct pet_expr *expr;
+
+	if (!access || !index)
+		goto error;
+
+	ctx = isl_multi_pw_aff_get_ctx(index);
+	expr = pet_expr_from_access_and_index(access, index);
+	if (!expr)
+		return NULL;
+	expr->acc.read = 0;
+	return pet_expr_new_unary(ctx, pet_op_kill, expr);
+error:
+	isl_map_free(access);
+	isl_multi_pw_aff_free(index);
+	return NULL;
+}
+
+/* Construct a unary pet_expr that performs "op" on "arg".
+ */
+struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
+	struct pet_expr *arg)
+{
+	struct pet_expr *expr;
+
+	if (!arg)
+		goto error;
+	expr = isl_alloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_op;
+	expr->op = op;
+	expr->n_arg = 1;
+	expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
+	if (!expr->args)
+		goto error;
+	expr->args[pet_un_arg] = arg;
+
+	return expr;
+error:
+	pet_expr_free(arg);
+	return NULL;
+}
+
+/* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
+ */
+struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
+	struct pet_expr *lhs, struct pet_expr *rhs)
+{
+	struct pet_expr *expr;
+
+	if (!lhs || !rhs)
+		goto error;
+	expr = isl_alloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_op;
+	expr->op = op;
+	expr->n_arg = 2;
+	expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
+	if (!expr->args)
+		goto error;
+	expr->args[pet_bin_lhs] = lhs;
+	expr->args[pet_bin_rhs] = rhs;
+
+	return expr;
+error:
+	pet_expr_free(lhs);
+	pet_expr_free(rhs);
+	return NULL;
+}
+
+/* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
+ */
+struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
+	struct pet_expr *lhs, struct pet_expr *rhs)
+{
+	struct pet_expr *expr;
+
+	if (!cond || !lhs || !rhs)
+		goto error;
+	expr = isl_alloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_op;
+	expr->op = pet_op_cond;
+	expr->n_arg = 3;
+	expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
+	if (!expr->args)
+		goto error;
+	expr->args[pet_ter_cond] = cond;
+	expr->args[pet_ter_true] = lhs;
+	expr->args[pet_ter_false] = rhs;
+
+	return expr;
+error:
+	pet_expr_free(cond);
+	pet_expr_free(lhs);
+	pet_expr_free(rhs);
+	return NULL;
+}
+
+/* Construct a call pet_expr that calls function "name" with "n_arg"
+ * arguments.  The caller is responsible for filling in the arguments.
+ */
+struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
+	unsigned n_arg)
+{
+	struct pet_expr *expr;
+
+	expr = isl_alloc_type(ctx, struct pet_expr);
+	if (!expr)
+		return NULL;
+
+	expr->type = pet_expr_call;
+	expr->n_arg = n_arg;
+	expr->name = strdup(name);
+	expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
+	if (!expr->name || !expr->args)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Construct a pet_expr that represents the cast of "arg" to "type_name".
+ */
+struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
+	struct pet_expr *arg)
+{
+	struct pet_expr *expr;
+
+	if (!arg)
+		return NULL;
+
+	expr = isl_alloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_cast;
+	expr->n_arg = 1;
+	expr->type_name = strdup(type_name);
+	expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
+	if (!expr->type_name || !expr->args)
+		goto error;
+
+	expr->args[0] = arg;
+
+	return expr;
+error:
+	pet_expr_free(arg);
+	pet_expr_free(expr);
+	return NULL;
+}
+
+/* Construct a pet_expr that represents the double "d".
+ */
+struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
+{
+	struct pet_expr *expr;
+
+	expr = isl_calloc_type(ctx, struct pet_expr);
+	if (!expr)
+		return NULL;
+
+	expr->type = pet_expr_double;
+	expr->d.val = val;
+	expr->d.s = strdup(s);
+	if (!expr->d.s)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Construct a pet_expr that represents the integer value "v".
+ */
+struct pet_expr *pet_expr_new_int(__isl_take isl_val *v)
+{
+	isl_ctx *ctx;
+	struct pet_expr *expr;
+
+	if (!v)
+		return NULL;
+
+	ctx = isl_val_get_ctx(v);
+	expr = isl_calloc_type(ctx, struct pet_expr);
+	if (!expr)
+		goto error;
+
+	expr->type = pet_expr_int;
+	expr->i = v;
+
+	return expr;
+error:
+	isl_val_free(v);
+	return NULL;
+}
+
+struct pet_expr *pet_expr_free(struct pet_expr *expr)
+{
+	int i;
+
+	if (!expr)
+		return NULL;
+
+	for (i = 0; i < expr->n_arg; ++i)
+		pet_expr_free(expr->args[i]);
+	free(expr->args);
+
+	switch (expr->type) {
+	case pet_expr_access:
+		isl_id_free(expr->acc.ref_id);
+		isl_map_free(expr->acc.access);
+		isl_multi_pw_aff_free(expr->acc.index);
+		break;
+	case pet_expr_call:
+		free(expr->name);
+		break;
+	case pet_expr_cast:
+		free(expr->type_name);
+		break;
+	case pet_expr_double:
+		free(expr->d.s);
+		break;
+	case pet_expr_int:
+		isl_val_free(expr->i);
+		break;
+	case pet_expr_op:
+		break;
+	}
+
+	free(expr);
+	return NULL;
+}
+
+/* Does "expr" represent an access to an unnamed space, i.e.,
+ * does it represent an affine expression?
+ */
+int pet_expr_is_affine(struct pet_expr *expr)
+{
+	int has_id;
+
+	if (!expr)
+		return -1;
+	if (expr->type != pet_expr_access)
+		return 0;
+
+	has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
+	if (has_id < 0)
+		return -1;
+
+	return !has_id;
+}
+
+/* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
+ */
+int pet_expr_is_scalar_access(struct pet_expr *expr)
+{
+	if (!expr)
+		return -1;
+	if (expr->type != pet_expr_access)
+		return 0;
+
+	return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
+}
+
+/* Return 1 if the two pet_exprs are equivalent.
+ */
+int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
+{
+	int i;
+
+	if (!expr1 || !expr2)
+		return 0;
+
+	if (expr1->type != expr2->type)
+		return 0;
+	if (expr1->n_arg != expr2->n_arg)
+		return 0;
+	for (i = 0; i < expr1->n_arg; ++i)
+		if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
+			return 0;
+	switch (expr1->type) {
+	case pet_expr_double:
+		if (strcmp(expr1->d.s, expr2->d.s))
+			return 0;
+		if (expr1->d.val != expr2->d.val)
+			return 0;
+		break;
+	case pet_expr_int:
+		if (!isl_val_eq(expr1->i, expr2->i))
+			return 0;
+		break;
+	case pet_expr_access:
+		if (expr1->acc.read != expr2->acc.read)
+			return 0;
+		if (expr1->acc.write != expr2->acc.write)
+			return 0;
+		if (expr1->acc.ref_id != expr2->acc.ref_id)
+			return 0;
+		if (!expr1->acc.access || !expr2->acc.access)
+			return 0;
+		if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
+			return 0;
+		if (!expr1->acc.index || !expr2->acc.index)
+			return 0;
+		if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
+							expr2->acc.index))
+			return 0;
+		break;
+	case pet_expr_op:
+		if (expr1->op != expr2->op)
+			return 0;
+		break;
+	case pet_expr_call:
+		if (strcmp(expr1->name, expr2->name))
+			return 0;
+		break;
+	case pet_expr_cast:
+		if (strcmp(expr1->type_name, expr2->type_name))
+			return 0;
+		break;
+	}
+
+	return 1;
+}
+
+/* Return the identifier of the array accessed by "expr".
+ *
+ * If "expr" represents a member access, then return the identifier
+ * of the outer structure array.
+ */
+__isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
+{
+	if (!expr)
+		return NULL;
+	if (expr->type != pet_expr_access)
+		return NULL;
+
+	if (isl_map_range_is_wrapping(expr->acc.access)) {
+		isl_space *space;
+		isl_id *id;
+
+		space = isl_map_get_space(expr->acc.access);
+		space = isl_space_range(space);
+		while (space && isl_space_is_wrapping(space))
+			space = isl_space_domain(isl_space_unwrap(space));
+		id = isl_space_get_tuple_id(space, isl_dim_set);
+		isl_space_free(space);
+
+		return id;
+	}
+
+	return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
+}
+
+/* Modify all expressions of type pet_expr_access in "expr"
+ * by calling "fn" on them.
+ */
+struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
+	struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
+	void *user)
+{
+	int i;
+
+	if (!expr)
+		return NULL;
+
+	for (i = 0; i < expr->n_arg; ++i) {
+		expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
+		if (!expr->args[i])
+			return pet_expr_free(expr);
+	}
+
+	if (expr->type == pet_expr_access)
+		expr = fn(expr, user);
+
+	return expr;
+}
+
+/* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
+ *
+ * Return -1 on error (where fn return a negative value is treated as an error).
+ * Otherwise return 0.
+ */
+int pet_expr_foreach_access_expr(struct pet_expr *expr,
+	int (*fn)(struct pet_expr *expr, void *user), void *user)
+{
+	int i;
+
+	if (!expr)
+		return -1;
+
+	for (i = 0; i < expr->n_arg; ++i)
+		if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
+			return -1;
+
+	if (expr->type == pet_expr_access)
+		return fn(expr, user);
+
+	return 0;
+}
+
+/* Internal data structure for pet_expr_writes.
+ * "id" is the identifier that we are looking for.
+ * "found" is set if we have found the identifier being written to.
+ */
+struct pet_expr_writes_data {
+	isl_id *id;
+	int found;
+};
+
+/* Given an access expression, check if it writes to data->id.
+ * If so, set data->found and abort the search.
+ */
+static int writes(struct pet_expr *expr, void *user)
+{
+	struct pet_expr_writes_data *data = user;
+	isl_id *write_id;
+
+	if (!expr->acc.write)
+		return 0;
+	if (pet_expr_is_affine(expr))
+		return 0;
+
+	write_id = pet_expr_access_get_id(expr);
+	isl_id_free(write_id);
+
+	if (!write_id)
+		return -1;
+
+	if (write_id != data->id)
+		return 0;
+
+	data->found = 1;
+	return -1;
+}
+
+/* Does expression "expr" write to "id"?
+ */
+int pet_expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
+{
+	struct pet_expr_writes_data data;
+
+	data.id = id;
+	data.found = 0;
+	if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
+	    !data.found)
+		return -1;
+
+	return data.found;
+}
+
+/* Align the parameters of expr->acc.index and expr->acc.access.
+ */
+struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr)
+{
+	if (!expr)
+		return NULL;
+	if (expr->type != pet_expr_access)
+		return pet_expr_free(expr);
+
+	expr->acc.access = isl_map_align_params(expr->acc.access,
+				isl_multi_pw_aff_get_space(expr->acc.index));
+	expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
+				isl_map_get_space(expr->acc.access));
+	if (!expr->acc.access || !expr->acc.index)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Add extra conditions on the parameters to all access relations in "expr".
+ *
+ * The conditions are not added to the index expression.  Instead, they
+ * are used to try and simplify the index expression.
+ */
+struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
+	__isl_take isl_set *cond)
+{
+	int i;
+
+	if (!expr)
+		goto error;
+
+	for (i = 0; i < expr->n_arg; ++i) {
+		expr->args[i] = pet_expr_restrict(expr->args[i],
+							isl_set_copy(cond));
+		if (!expr->args[i])
+			goto error;
+	}
+
+	if (expr->type == pet_expr_access) {
+		expr->acc.access = isl_map_intersect_params(expr->acc.access,
+							    isl_set_copy(cond));
+		expr->acc.index = isl_multi_pw_aff_gist_params(
+					expr->acc.index, isl_set_copy(cond));
+		if (!expr->acc.access || !expr->acc.index)
+			goto error;
+	}
+
+	isl_set_free(cond);
+	return expr;
+error:
+	isl_set_free(cond);
+	return pet_expr_free(expr);
+}
+
+/* Modify the access relation and index expression
+ * of the given access expression
+ * based on the given iteration space transformation.
+ * In particular, precompose the access relation and index expression
+ * with the update function.
+ *
+ * If the access has any arguments then the domain of the access relation
+ * is a wrapped mapping from the iteration space to the space of
+ * argument values.  We only need to change the domain of this wrapped
+ * mapping, so we extend the input transformation with an identity mapping
+ * on the space of argument values.
+ */
+struct pet_expr *pet_expr_access_update_domain(struct pet_expr *expr,
+	__isl_keep isl_multi_pw_aff *update)
+{
+	isl_space *space;
+
+	update = isl_multi_pw_aff_copy(update);
+
+	space = isl_map_get_space(expr->acc.access);
+	space = isl_space_domain(space);
+	if (!isl_space_is_wrapping(space))
+		isl_space_free(space);
+	else {
+		isl_multi_pw_aff *id;
+		space = isl_space_unwrap(space);
+		space = isl_space_range(space);
+		space = isl_space_map_from_set(space);
+		id = isl_multi_pw_aff_identity(space);
+		update = isl_multi_pw_aff_product(update, id);
+	}
+
+	expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
+					    expr->acc.access,
+					    isl_multi_pw_aff_copy(update));
+	expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
+					    expr->acc.index, update);
+	if (!expr->acc.access || !expr->acc.index)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
+{
+	isl_multi_pw_aff *update = user;
+
+	return pet_expr_access_update_domain(expr, update);
+}
+
+/* Modify all access relations in "expr" by precomposing them with
+ * the given iteration space transformation.
+ */
+struct pet_expr *pet_expr_update_domain(struct pet_expr *expr,
+	__isl_take isl_multi_pw_aff *update)
+{
+	expr = pet_expr_map_access(expr, &update_domain, update);
+	isl_multi_pw_aff_free(update);
+	return expr;
+}
+
+/* Add all parameters in "space" to the access relation and index expression
+ * of "expr".
+ */
+static struct pet_expr *align_params(struct pet_expr *expr, void *user)
+{
+	isl_space *space = user;
+
+	expr->acc.access = isl_map_align_params(expr->acc.access,
+						isl_space_copy(space));
+	expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
+						isl_space_copy(space));
+	if (!expr->acc.access || !expr->acc.index)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Add all parameters in "space" to all access relations and index expressions
+ * in "expr".
+ */
+struct pet_expr *pet_expr_align_params(struct pet_expr *expr,
+	__isl_take isl_space *space)
+{
+	expr = pet_expr_map_access(expr, &align_params, space);
+	isl_space_free(space);
+	return expr;
+}
+
+/* Insert an argument expression corresponding to "test" in front
+ * of the list of arguments described by *n_arg and *args.
+ */
+static struct pet_expr *insert_access_arg(struct pet_expr *expr,
+	__isl_keep isl_multi_pw_aff *test)
+{
+	int i;
+	isl_ctx *ctx = isl_multi_pw_aff_get_ctx(test);
+
+	if (!test)
+		return pet_expr_free(expr);
+
+	if (!expr->args) {
+		expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
+		if (!expr->args)
+			return pet_expr_free(expr);
+	} else {
+		struct pet_expr **ext;
+		ext = isl_calloc_array(ctx, struct pet_expr *, 1 + expr->n_arg);
+		if (!ext)
+			return pet_expr_free(expr);
+		for (i = 0; i < expr->n_arg; ++i)
+			ext[1 + i] = expr->args[i];
+		free(expr->args);
+		expr->args = ext;
+	}
+	expr->n_arg++;
+	expr->args[0] = pet_expr_from_index(isl_multi_pw_aff_copy(test));
+	if (!expr->args[0])
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Make the expression "expr" depend on the value of "test"
+ * being equal to "satisfied".
+ *
+ * If "test" is an affine expression, we simply add the conditions
+ * on the expression having the value "satisfied" to all access relations
+ * and index expressions.
+ *
+ * Otherwise, we add a filter to "expr" (which is then assumed to be
+ * an access expression) corresponding to "test" being equal to "satisfied".
+ */
+struct pet_expr *pet_expr_filter(struct pet_expr *expr,
+	__isl_take isl_multi_pw_aff *test, int satisfied)
+{
+	isl_id *id;
+	isl_ctx *ctx;
+	isl_space *space;
+	isl_pw_multi_aff *pma;
+
+	if (!expr || !test)
+		goto error;
+
+	if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
+		isl_pw_aff *pa;
+		isl_set *cond;
+
+		pa = isl_multi_pw_aff_get_pw_aff(test, 0);
+		isl_multi_pw_aff_free(test);
+		if (satisfied)
+			cond = isl_pw_aff_non_zero_set(pa);
+		else
+			cond = isl_pw_aff_zero_set(pa);
+		return pet_expr_restrict(expr, isl_set_params(cond));
+	}
+
+	ctx = isl_multi_pw_aff_get_ctx(test);
+	if (expr->type != pet_expr_access)
+		isl_die(ctx, isl_error_invalid,
+			"can only filter access expressions", goto error);
+
+	space = isl_space_domain(isl_map_get_space(expr->acc.access));
+	id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
+	pma = pet_filter_insert_pma(space, id, satisfied);
+
+	expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
+						expr->acc.access,
+						isl_pw_multi_aff_copy(pma));
+	expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
+							expr->acc.index, pma);
+	if (!expr->acc.access || !expr->acc.index)
+		goto error;
+
+	expr = insert_access_arg(expr, test);
+
+	isl_multi_pw_aff_free(test);
+	return expr;
+error:
+	isl_multi_pw_aff_free(test);
+	return pet_expr_free(expr);
+}
+
+/* Check if the given index expression accesses a (0D) array that corresponds
+ * to one of the parameters in "space".  If so, replace the array access
+ * by an access to the set of integers with as index (and value)
+ * that parameter.
+ */
+static __isl_give isl_multi_pw_aff *index_detect_parameter(
+	__isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
+{
+	isl_local_space *ls;
+	isl_id *array_id = NULL;
+	isl_aff *aff;
+	int pos = -1;
+
+	if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
+		array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
+		pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
+	}
+	isl_space_free(space);
+
+	if (pos < 0) {
+		isl_id_free(array_id);
+		return index;
+	}
+
+	space = isl_multi_pw_aff_get_domain_space(index);
+	isl_multi_pw_aff_free(index);
+
+	pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
+	if (pos < 0) {
+		space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
+		space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
+		pos = 0;
+	} else
+		isl_id_free(array_id);
+
+	ls = isl_local_space_from_space(space);
+	aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
+	index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
+
+	return index;
+}
+
+/* Check if the given access relation accesses a (0D) array that corresponds
+ * to one of the parameters in "space".  If so, replace the array access
+ * by an access to the set of integers with as index (and value)
+ * that parameter.
+ */
+static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
+	__isl_take isl_space *space)
+{
+	isl_id *array_id = NULL;
+	int pos = -1;
+
+	if (isl_map_has_tuple_id(access, isl_dim_out)) {
+		array_id = isl_map_get_tuple_id(access, isl_dim_out);
+		pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
+	}
+	isl_space_free(space);
+
+	if (pos < 0) {
+		isl_id_free(array_id);
+		return access;
+	}
+
+	pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
+	if (pos < 0) {
+		access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
+		access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
+		pos = 0;
+	} else
+		isl_id_free(array_id);
+
+	access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
+	access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
+
+	return access;
+}
+
+/* If "expr" accesses a (0D) array that corresponds to one of the parameters
+ * in "space" then replace it by a value equal to the corresponding parameter.
+ */
+static struct pet_expr *detect_parameter_accesses(struct pet_expr *expr,
+	void *user)
+{
+	isl_space *space = user;
+
+	expr->acc.access = access_detect_parameter(expr->acc.access,
+						isl_space_copy(space));
+	expr->acc.index = index_detect_parameter(expr->acc.index,
+						isl_space_copy(space));
+	if (!expr->acc.access || !expr->acc.index)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+/* Replace all accesses to (0D) arrays that correspond to one of the parameters
+ * in "space" by a value equal to the corresponding parameter.
+ */
+struct pet_expr *pet_expr_detect_parameter_accesses(struct pet_expr *expr,
+	__isl_take isl_space *space)
+{
+	expr = pet_expr_map_access(expr, &detect_parameter_accesses, space);
+	isl_space_free(space);
+	return expr;
+}
+
+/* Add a reference identifier to access expression "expr".
+ * "user" points to an integer that contains the sequence number
+ * of the next reference.
+ */
+static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
+{
+	isl_ctx *ctx;
+	char name[50];
+	int *n_ref = user;
+
+	if (!expr)
+		return expr;
+
+	ctx = isl_map_get_ctx(expr->acc.access);
+	snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
+	expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
+	if (!expr->acc.ref_id)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+struct pet_expr *pet_expr_add_ref_ids(struct pet_expr *expr, int *n_ref)
+{
+	return pet_expr_map_access(expr, &access_add_ref_id, n_ref);
+}
+
+/* Reset the user pointer on all parameter and tuple ids in
+ * the access relation and the index expressions
+ * of the access expression "expr".
+ */
+static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
+{
+	expr->acc.access = isl_map_reset_user(expr->acc.access);
+	expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
+	if (!expr->acc.access || !expr->acc.index)
+		return pet_expr_free(expr);
+
+	return expr;
+}
+
+struct pet_expr *pet_expr_anonymize(struct pet_expr *expr)
+{
+	return pet_expr_map_access(expr, &access_anonymize, NULL);
+}
+
+/* Tag the access relation "access" with "id".
+ * That is, insert the id as the range of a wrapped relation
+ * in the domain of "access".
+ *
+ * If "access" is of the form
+ *
+ *	D[i] -> A[a]
+ *
+ * then the result is of the form
+ *
+ *	[D[i] -> id[]] -> A[a]
+ */
+__isl_give isl_map *pet_expr_tag_access(struct pet_expr *expr,
+	__isl_take isl_map *access)
+{
+	isl_space *space;
+	isl_map *add_tag;
+	isl_id *id;
+
+	id = isl_id_copy(expr->acc.ref_id);
+	space = isl_space_range(isl_map_get_space(access));
+	space = isl_space_from_range(space);
+	space = isl_space_set_tuple_id(space, isl_dim_in, id);
+	add_tag = isl_map_universe(space);
+	access = isl_map_domain_product(access, add_tag);
+
+	return access;
+}
+
+/* Return the relation mapping domain iterations to all possibly
+ * accessed data elements.
+ * In particular, take the access relation and project out the values
+ * of the arguments, if any.
+ */
+__isl_give isl_map *pet_expr_access_get_may_access(struct pet_expr *expr)
+{
+	isl_map *access;
+	isl_space *space;
+	isl_map *map;
+
+	if (!expr)
+		return NULL;
+	if (expr->type != pet_expr_access)
+		return NULL;
+
+	access = isl_map_copy(expr->acc.access);
+	if (expr->n_arg == 0)
+		return access;
+
+	space = isl_space_domain(isl_map_get_space(access));
+	map = isl_map_universe(isl_space_unwrap(space));
+	map = isl_map_domain_map(map);
+	access = isl_map_apply_domain(access, map);
+
+	return access;
+}
+
+/* Return the relation mapping domain iterations to all possibly
+ * accessed data elements, with its domain tagged with the reference
+ * identifier.
+ */
+__isl_give isl_map *pet_expr_access_get_tagged_may_access(
+	struct pet_expr *expr)
+{
+	isl_map *access;
+
+	if (!expr)
+		return NULL;
+
+	access = pet_expr_access_get_may_access(expr);
+	access = pet_expr_tag_access(expr, access);
+
+	return access;
+}
+
+void pet_expr_dump_with_indent(struct pet_expr *expr, int indent)
+{
+	int i;
+
+	if (!expr)
+		return;
+
+	fprintf(stderr, "%*s", indent, "");
+
+	switch (expr->type) {
+	case pet_expr_double:
+		fprintf(stderr, "%s\n", expr->d.s);
+		break;
+	case pet_expr_int:
+		isl_val_dump(expr->i);
+		break;
+	case pet_expr_access:
+		if (expr->acc.ref_id) {
+			isl_id_dump(expr->acc.ref_id);
+			fprintf(stderr, "%*s", indent, "");
+		}
+		isl_map_dump(expr->acc.access);
+		fprintf(stderr, "%*s", indent, "");
+		isl_multi_pw_aff_dump(expr->acc.index);
+		fprintf(stderr, "%*sread: %d\n", indent + 2,
+				"", expr->acc.read);
+		fprintf(stderr, "%*swrite: %d\n", indent + 2,
+				"", expr->acc.write);
+		for (i = 0; i < expr->n_arg; ++i)
+			pet_expr_dump_with_indent(expr->args[i], indent + 2);
+		break;
+	case pet_expr_op:
+		fprintf(stderr, "%s\n", op_str[expr->op]);
+		for (i = 0; i < expr->n_arg; ++i)
+			pet_expr_dump_with_indent(expr->args[i], indent + 2);
+		break;
+	case pet_expr_call:
+		fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
+		for (i = 0; i < expr->n_arg; ++i)
+			pet_expr_dump_with_indent(expr->args[i], indent + 2);
+		break;
+	case pet_expr_cast:
+		fprintf(stderr, "(%s)\n", expr->type_name);
+		for (i = 0; i < expr->n_arg; ++i)
+			pet_expr_dump_with_indent(expr->args[i], indent + 2);
+		break;
+	}
+}
+
+void pet_expr_dump(struct pet_expr *expr)
+{
+	pet_expr_dump_with_indent(expr, 0);
+}
diff --git a/expr.h b/expr.h
new file mode 100644
index 0000000..963ff33
--- /dev/null
+++ b/expr.h
@@ -0,0 +1,74 @@
+#ifndef PET_EXPR_H
+#define PET_EXPR_H
+
+#include <pet.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+const char *pet_type_str(enum pet_expr_type type);
+enum pet_expr_type pet_str_type(const char *str);
+
+enum pet_op_type pet_str_op(const char *str);
+
+struct pet_expr *pet_expr_from_index_and_depth(
+	__isl_take isl_multi_pw_aff *index, int depth);
+struct pet_expr *pet_expr_from_access_and_index(__isl_take isl_map *access,
+	__isl_take isl_multi_pw_aff *index);
+struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
+	__isl_take isl_multi_pw_aff *index);
+struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
+	struct pet_expr *arg);
+struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
+	struct pet_expr *lhs, struct pet_expr *rhs);
+struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
+	struct pet_expr *lhs, struct pet_expr *rhs);
+struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
+	unsigned n_arg);
+struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
+	struct pet_expr *arg);
+struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d, const char *s);
+struct pet_expr *pet_expr_new_int(__isl_take isl_val *v);
+void pet_expr_dump(struct pet_expr *expr);
+
+int pet_expr_is_affine(struct pet_expr *expr);
+int pet_expr_is_scalar_access(struct pet_expr *expr);
+int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2);
+
+__isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr);
+
+int pet_expr_foreach_access_expr(struct pet_expr *expr,
+	int (*fn)(struct pet_expr *expr, void *user), void *user);
+struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
+	struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
+	void *user);
+
+int pet_expr_writes(struct pet_expr *expr, __isl_keep isl_id *id);
+
+struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr);
+struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
+	__isl_take isl_set *cond);
+struct pet_expr *pet_expr_access_update_domain(struct pet_expr *expr,
+	__isl_keep isl_multi_pw_aff *update);
+struct pet_expr *pet_expr_update_domain(struct pet_expr *expr,
+	__isl_take isl_multi_pw_aff *update);
+struct pet_expr *pet_expr_align_params(struct pet_expr *expr,
+	__isl_take isl_space *space);
+struct pet_expr *pet_expr_filter(struct pet_expr *expr,
+	__isl_take isl_multi_pw_aff *test, int satisfied);
+struct pet_expr *pet_expr_detect_parameter_accesses(struct pet_expr *expr,
+	__isl_take isl_space *space);
+struct pet_expr *pet_expr_add_ref_ids(struct pet_expr *expr, int *n_ref);
+struct pet_expr *pet_expr_anonymize(struct pet_expr *expr);
+
+__isl_give isl_map *pet_expr_tag_access(struct pet_expr *expr,
+	__isl_take isl_map *access);
+
+void pet_expr_dump_with_indent(struct pet_expr *expr, int indent);
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/parse.c b/parse.c
index fb56efd..4d788e1 100644
--- a/parse.c
+++ b/parse.c
@@ -35,6 +35,7 @@
 #include <stdlib.h>
 #include <yaml.h>
 
+#include "expr.h"
 #include "scop.h"
 #include "scop_yaml.h"
 
diff --git a/print.c b/print.c
index 17e7362..8ae4ba0 100644
--- a/print.c
+++ b/print.c
@@ -36,6 +36,7 @@
 #include <isl/ast.h>
 #include <isl/ast_build.h>
 #include <pet.h>
+#include "expr.h"
 #include "print.h"
 #include "scop.h"
 
diff --git a/scan.cc b/scan.cc
index cb95428..3af9fbc 100644
--- a/scan.cc
+++ b/scan.cc
@@ -48,6 +48,7 @@
 #include <isl/set.h>
 
 #include "clang.h"
+#include "expr.h"
 #include "options.h"
 #include "scan.h"
 #include "scop.h"
diff --git a/scop.c b/scop.c
index d4f472a..3e3e602 100644
--- a/scop.c
+++ b/scop.c
@@ -36,824 +36,37 @@
 #include <isl/constraint.h>
 #include <isl/union_set.h>
 
+#include "expr.h"
 #include "filter.h"
 #include "scop.h"
 #include "print.h"
 
-#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
-
-static char *type_str[] = {
-	[pet_expr_access] = "access",
-	[pet_expr_call] = "call",
-	[pet_expr_cast] = "cast",
-	[pet_expr_double] = "double",
-	[pet_expr_int] = "int",
-	[pet_expr_op] = "op",
-};
-
-static char *op_str[] = {
-	[pet_op_add_assign] = "+=",
-	[pet_op_sub_assign] = "-=",
-	[pet_op_mul_assign] = "*=",
-	[pet_op_div_assign] = "/=",
-	[pet_op_assign] = "=",
-	[pet_op_add] = "+",
-	[pet_op_sub] = "-",
-	[pet_op_mul] = "*",
-	[pet_op_div] = "/",
-	[pet_op_mod] = "%",
-	[pet_op_shl] = "<<",
-	[pet_op_shr] = ">>",
-	[pet_op_eq] = "==",
-	[pet_op_ne] = "!=",
-	[pet_op_le] = "<=",
-	[pet_op_ge] = ">=",
-	[pet_op_lt] = "<",
-	[pet_op_gt] = ">",
-	[pet_op_minus] = "-",
-	[pet_op_post_inc] = "++",
-	[pet_op_post_dec] = "--",
-	[pet_op_pre_inc] = "++",
-	[pet_op_pre_dec] = "--",
-	[pet_op_address_of] = "&",
-	[pet_op_and] = "&",
-	[pet_op_xor] = "^",
-	[pet_op_or] = "|",
-	[pet_op_not] = "~",
-	[pet_op_land] = "&&",
-	[pet_op_lor] = "||",
-	[pet_op_lnot] = "!",
-	[pet_op_cond] = "?:",
-	[pet_op_assume] = "assume",
-	[pet_op_kill] = "kill"
-};
-
-/* pet_scop with extra information that is used during parsing and printing.
- *
- * In particular, we keep track of conditions under which we want
- * to skip the rest of the current loop iteration (skip[pet_skip_now])
- * and of conditions under which we want to skip subsequent
- * loop iterations (skip[pet_skip_later]).
- *
- * The conditions are represented as index expressions defined
- * over a zero-dimensional domain.  The index expression is either
- * a boolean affine expression or an access to a variable, which
- * is assumed to attain values zero and one.  The condition holds
- * if the variable has value one or if the affine expression
- * has value one (typically for only part of the parameter space).
- *
- * A missing condition (skip[type] == NULL) means that we don't want
- * to skip anything.
- *
- * Additionally, we keep track of the original input file
- * inside pet_transform_C_source.
- */
-struct pet_scop_ext {
-	struct pet_scop scop;
-
-	isl_multi_pw_aff *skip[2];
-	FILE *input;
-};
-
-const char *pet_op_str(enum pet_op_type op)
-{
-	return op_str[op];
-}
-
-int pet_op_is_inc_dec(enum pet_op_type op)
-{
-	return op == pet_op_post_inc || op == pet_op_post_dec ||
-	    op == pet_op_pre_inc || op == pet_op_pre_dec;
-}
-
-const char *pet_type_str(enum pet_expr_type type)
-{
-	return type_str[type];
-}
-
-enum pet_op_type pet_str_op(const char *str)
-{
-	int i;
-
-	for (i = 0; i < ARRAY_SIZE(op_str); ++i)
-		if (!strcmp(op_str[i], str))
-			return i;
-
-	return -1;
-}
-
-enum pet_expr_type pet_str_type(const char *str)
-{
-	int i;
-
-	for (i = 0; i < ARRAY_SIZE(type_str); ++i)
-		if (!strcmp(type_str[i], str))
-			return i;
-
-	return -1;
-}
-
-/* Construct an access pet_expr from an access relation and an index expression.
- * By default, it is considered to be a read access.
- */
-struct pet_expr *pet_expr_from_access_and_index( __isl_take isl_map *access,
-	__isl_take isl_multi_pw_aff *index)
-{
-	isl_ctx *ctx = isl_map_get_ctx(access);
-	struct pet_expr *expr;
-
-	if (!index || !access)
-		goto error;
-	expr = isl_calloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_access;
-	expr->acc.access = access;
-	expr->acc.index = index;
-	expr->acc.read = 1;
-	expr->acc.write = 0;
-
-	return expr;
-error:
-	isl_map_free(access);
-	isl_multi_pw_aff_free(index);
-	return NULL;
-}
-
-/* Construct an access pet_expr from an index expression.
- * By default, the access is considered to be a read access.
- */
-struct pet_expr *pet_expr_from_index(__isl_take isl_multi_pw_aff *index)
-{
-	isl_map *access;
-
-	access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
-	return pet_expr_from_access_and_index(access, index);
-}
-
-/* Extend the range of "access" with "n" dimensions, retaining
- * the tuple identifier on this range.
- *
- * If "access" represents a member access, then extend the range
- * of the member.
- */
-static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n)
-{
-	isl_id *id;
-
-	id = isl_map_get_tuple_id(access, isl_dim_out);
-
-	if (!isl_map_range_is_wrapping(access)) {
-		access = isl_map_add_dims(access, isl_dim_out, n);
-	} else {
-		isl_map *domain;
-
-		domain = isl_map_copy(access);
-		domain = isl_map_range_factor_domain(domain);
-		access = isl_map_range_factor_range(access);
-		access = extend_range(access, n);
-		access = isl_map_range_product(domain, access);
-	}
-
-	access = isl_map_set_tuple_id(access, isl_dim_out, id);
-
-	return access;
-}
-
-/* Construct an access pet_expr from an index expression and
- * the depth of the accessed array.
- * By default, the access is considered to be a read access.
- *
- * If the number of indices is smaller than the depth of the array,
- * then we assume that all elements of the remaining dimensions
- * are accessed.
- */
-struct pet_expr *pet_expr_from_index_and_depth(
-	__isl_take isl_multi_pw_aff *index, int depth)
-{
-	isl_map *access;
-	int dim;
-
-	access = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index));
-	if (!access)
-		goto error;
-	dim = isl_map_dim(access, isl_dim_out);
-	if (dim > depth)
-		isl_die(isl_map_get_ctx(access), isl_error_internal,
-			"number of indices greater than depth",
-			access = isl_map_free(access));
-	if (dim == depth)
-		return pet_expr_from_access_and_index(access, index);
-
-	access = extend_range(access, depth - dim);
-
-	return pet_expr_from_access_and_index(access, index);
-error:
-	isl_multi_pw_aff_free(index);
-	return NULL;
-}
-
-/* Construct a pet_expr that kills the elements specified by
- * the index expression "index" and the access relation "access".
- */
-struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
-	__isl_take isl_multi_pw_aff *index)
-{
-	isl_ctx *ctx;
-	struct pet_expr *expr;
-
-	if (!access || !index)
-		goto error;
-
-	ctx = isl_multi_pw_aff_get_ctx(index);
-	expr = pet_expr_from_access_and_index(access, index);
-	if (!expr)
-		return NULL;
-	expr->acc.read = 0;
-	return pet_expr_new_unary(ctx, pet_op_kill, expr);
-error:
-	isl_map_free(access);
-	isl_multi_pw_aff_free(index);
-	return NULL;
-}
-
-/* Construct a unary pet_expr that performs "op" on "arg".
- */
-struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
-	struct pet_expr *arg)
-{
-	struct pet_expr *expr;
-
-	if (!arg)
-		goto error;
-	expr = isl_alloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_op;
-	expr->op = op;
-	expr->n_arg = 1;
-	expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
-	if (!expr->args)
-		goto error;
-	expr->args[pet_un_arg] = arg;
-
-	return expr;
-error:
-	pet_expr_free(arg);
-	return NULL;
-}
-
-/* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
- */
-struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
-	struct pet_expr *lhs, struct pet_expr *rhs)
-{
-	struct pet_expr *expr;
-
-	if (!lhs || !rhs)
-		goto error;
-	expr = isl_alloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_op;
-	expr->op = op;
-	expr->n_arg = 2;
-	expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
-	if (!expr->args)
-		goto error;
-	expr->args[pet_bin_lhs] = lhs;
-	expr->args[pet_bin_rhs] = rhs;
-
-	return expr;
-error:
-	pet_expr_free(lhs);
-	pet_expr_free(rhs);
-	return NULL;
-}
-
-/* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
- */
-struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
-	struct pet_expr *lhs, struct pet_expr *rhs)
-{
-	struct pet_expr *expr;
-
-	if (!cond || !lhs || !rhs)
-		goto error;
-	expr = isl_alloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_op;
-	expr->op = pet_op_cond;
-	expr->n_arg = 3;
-	expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
-	if (!expr->args)
-		goto error;
-	expr->args[pet_ter_cond] = cond;
-	expr->args[pet_ter_true] = lhs;
-	expr->args[pet_ter_false] = rhs;
-
-	return expr;
-error:
-	pet_expr_free(cond);
-	pet_expr_free(lhs);
-	pet_expr_free(rhs);
-	return NULL;
-}
-
-/* Construct a call pet_expr that calls function "name" with "n_arg"
- * arguments.  The caller is responsible for filling in the arguments.
- */
-struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
-	unsigned n_arg)
-{
-	struct pet_expr *expr;
-
-	expr = isl_alloc_type(ctx, struct pet_expr);
-	if (!expr)
-		return NULL;
-
-	expr->type = pet_expr_call;
-	expr->n_arg = n_arg;
-	expr->name = strdup(name);
-	expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
-	if (!expr->name || !expr->args)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
-/* Construct a pet_expr that represents the cast of "arg" to "type_name".
- */
-struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
-	struct pet_expr *arg)
-{
-	struct pet_expr *expr;
-
-	if (!arg)
-		return NULL;
-
-	expr = isl_alloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_cast;
-	expr->n_arg = 1;
-	expr->type_name = strdup(type_name);
-	expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
-	if (!expr->type_name || !expr->args)
-		goto error;
-
-	expr->args[0] = arg;
-
-	return expr;
-error:
-	pet_expr_free(arg);
-	pet_expr_free(expr);
-	return NULL;
-}
-
-/* Construct a pet_expr that represents the double "d".
- */
-struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double val, const char *s)
-{
-	struct pet_expr *expr;
-
-	expr = isl_calloc_type(ctx, struct pet_expr);
-	if (!expr)
-		return NULL;
-
-	expr->type = pet_expr_double;
-	expr->d.val = val;
-	expr->d.s = strdup(s);
-	if (!expr->d.s)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
-/* Construct a pet_expr that represents the integer value "v".
- */
-struct pet_expr *pet_expr_new_int(__isl_take isl_val *v)
-{
-	isl_ctx *ctx;
-	struct pet_expr *expr;
-
-	if (!v)
-		return NULL;
-
-	ctx = isl_val_get_ctx(v);
-	expr = isl_calloc_type(ctx, struct pet_expr);
-	if (!expr)
-		goto error;
-
-	expr->type = pet_expr_int;
-	expr->i = v;
-
-	return expr;
-error:
-	isl_val_free(v);
-	return NULL;
-}
-
-struct pet_expr *pet_expr_free(struct pet_expr *expr)
-{
-	int i;
-
-	if (!expr)
-		return NULL;
-
-	for (i = 0; i < expr->n_arg; ++i)
-		pet_expr_free(expr->args[i]);
-	free(expr->args);
-
-	switch (expr->type) {
-	case pet_expr_access:
-		isl_id_free(expr->acc.ref_id);
-		isl_map_free(expr->acc.access);
-		isl_multi_pw_aff_free(expr->acc.index);
-		break;
-	case pet_expr_call:
-		free(expr->name);
-		break;
-	case pet_expr_cast:
-		free(expr->type_name);
-		break;
-	case pet_expr_double:
-		free(expr->d.s);
-		break;
-	case pet_expr_int:
-		isl_val_free(expr->i);
-		break;
-	case pet_expr_op:
-		break;
-	}
-
-	free(expr);
-	return NULL;
-}
-
-static void expr_dump(struct pet_expr *expr, int indent)
-{
-	int i;
-
-	if (!expr)
-		return;
-
-	fprintf(stderr, "%*s", indent, "");
-
-	switch (expr->type) {
-	case pet_expr_double:
-		fprintf(stderr, "%s\n", expr->d.s);
-		break;
-	case pet_expr_int:
-		isl_val_dump(expr->i);
-		break;
-	case pet_expr_access:
-		if (expr->acc.ref_id) {
-			isl_id_dump(expr->acc.ref_id);
-			fprintf(stderr, "%*s", indent, "");
-		}
-		isl_map_dump(expr->acc.access);
-		fprintf(stderr, "%*s", indent, "");
-		isl_multi_pw_aff_dump(expr->acc.index);
-		fprintf(stderr, "%*sread: %d\n", indent + 2,
-				"", expr->acc.read);
-		fprintf(stderr, "%*swrite: %d\n", indent + 2,
-				"", expr->acc.write);
-		for (i = 0; i < expr->n_arg; ++i)
-			expr_dump(expr->args[i], indent + 2);
-		break;
-	case pet_expr_op:
-		fprintf(stderr, "%s\n", op_str[expr->op]);
-		for (i = 0; i < expr->n_arg; ++i)
-			expr_dump(expr->args[i], indent + 2);
-		break;
-	case pet_expr_call:
-		fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
-		for (i = 0; i < expr->n_arg; ++i)
-			expr_dump(expr->args[i], indent + 2);
-		break;
-	case pet_expr_cast:
-		fprintf(stderr, "(%s)\n", expr->type_name);
-		for (i = 0; i < expr->n_arg; ++i)
-			expr_dump(expr->args[i], indent + 2);
-		break;
-	}
-}
-
-void pet_expr_dump(struct pet_expr *expr)
-{
-	expr_dump(expr, 0);
-}
-
-/* Does "expr" represent an access to an unnamed space, i.e.,
- * does it represent an affine expression?
- */
-int pet_expr_is_affine(struct pet_expr *expr)
-{
-	int has_id;
-
-	if (!expr)
-		return -1;
-	if (expr->type != pet_expr_access)
-		return 0;
-
-	has_id = isl_map_has_tuple_id(expr->acc.access, isl_dim_out);
-	if (has_id < 0)
-		return -1;
-
-	return !has_id;
-}
-
-/* Return the identifier of the array accessed by "expr".
- *
- * If "expr" represents a member access, then return the identifier
- * of the outer structure array.
- */
-__isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr)
-{
-	if (!expr)
-		return NULL;
-	if (expr->type != pet_expr_access)
-		return NULL;
-
-	if (isl_map_range_is_wrapping(expr->acc.access)) {
-		isl_space *space;
-		isl_id *id;
-
-		space = isl_map_get_space(expr->acc.access);
-		space = isl_space_range(space);
-		while (space && isl_space_is_wrapping(space))
-			space = isl_space_domain(isl_space_unwrap(space));
-		id = isl_space_get_tuple_id(space, isl_dim_set);
-		isl_space_free(space);
-
-		return id;
-	}
-
-	return isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
-}
-
-/* Align the parameters of expr->acc.index and expr->acc.access.
- */
-struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr)
-{
-	if (!expr)
-		return NULL;
-	if (expr->type != pet_expr_access)
-		return pet_expr_free(expr);
-
-	expr->acc.access = isl_map_align_params(expr->acc.access,
-				isl_multi_pw_aff_get_space(expr->acc.index));
-	expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
-				isl_map_get_space(expr->acc.access));
-	if (!expr->acc.access || !expr->acc.index)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
-/* Does "expr" represent an access to a scalar, i.e., zero-dimensional array?
- */
-int pet_expr_is_scalar_access(struct pet_expr *expr)
-{
-	if (!expr)
-		return -1;
-	if (expr->type != pet_expr_access)
-		return 0;
-
-	return isl_map_dim(expr->acc.access, isl_dim_out) == 0;
-}
-
-/* Return 1 if the two pet_exprs are equivalent.
- */
-int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
-{
-	int i;
-
-	if (!expr1 || !expr2)
-		return 0;
-
-	if (expr1->type != expr2->type)
-		return 0;
-	if (expr1->n_arg != expr2->n_arg)
-		return 0;
-	for (i = 0; i < expr1->n_arg; ++i)
-		if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
-			return 0;
-	switch (expr1->type) {
-	case pet_expr_double:
-		if (strcmp(expr1->d.s, expr2->d.s))
-			return 0;
-		if (expr1->d.val != expr2->d.val)
-			return 0;
-		break;
-	case pet_expr_int:
-		if (!isl_val_eq(expr1->i, expr2->i))
-			return 0;
-		break;
-	case pet_expr_access:
-		if (expr1->acc.read != expr2->acc.read)
-			return 0;
-		if (expr1->acc.write != expr2->acc.write)
-			return 0;
-		if (expr1->acc.ref_id != expr2->acc.ref_id)
-			return 0;
-		if (!expr1->acc.access || !expr2->acc.access)
-			return 0;
-		if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
-			return 0;
-		if (!expr1->acc.index || !expr2->acc.index)
-			return 0;
-		if (!isl_multi_pw_aff_plain_is_equal(expr1->acc.index,
-							expr2->acc.index))
-			return 0;
-		break;
-	case pet_expr_op:
-		if (expr1->op != expr2->op)
-			return 0;
-		break;
-	case pet_expr_call:
-		if (strcmp(expr1->name, expr2->name))
-			return 0;
-		break;
-	case pet_expr_cast:
-		if (strcmp(expr1->type_name, expr2->type_name))
-			return 0;
-		break;
-	}
-
-	return 1;
-}
-
-/* Add extra conditions on the parameters to all access relations in "expr".
- *
- * The conditions are not added to the index expression.  Instead, they
- * are used to try and simplify the index expression.
- */
-struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
-	__isl_take isl_set *cond)
-{
-	int i;
-
-	if (!expr)
-		goto error;
-
-	for (i = 0; i < expr->n_arg; ++i) {
-		expr->args[i] = pet_expr_restrict(expr->args[i],
-							isl_set_copy(cond));
-		if (!expr->args[i])
-			goto error;
-	}
-
-	if (expr->type == pet_expr_access) {
-		expr->acc.access = isl_map_intersect_params(expr->acc.access,
-							    isl_set_copy(cond));
-		expr->acc.index = isl_multi_pw_aff_gist_params(
-					expr->acc.index, isl_set_copy(cond));
-		if (!expr->acc.access || !expr->acc.index)
-			goto error;
-	}
-
-	isl_set_free(cond);
-	return expr;
-error:
-	isl_set_free(cond);
-	return pet_expr_free(expr);
-}
-
-/* Tag the access relation "access" with "id".
- * That is, insert the id as the range of a wrapped relation
- * in the domain of "access".
- *
- * If "access" is of the form
- *
- *	D[i] -> A[a]
- *
- * then the result is of the form
- *
- *	[D[i] -> id[]] -> A[a]
- */
-static __isl_give isl_map *tag_access(__isl_take isl_map *access,
-	__isl_take isl_id *id)
-{
-	isl_space *space;
-	isl_map *add_tag;
-
-	space = isl_space_range(isl_map_get_space(access));
-	space = isl_space_from_range(space);
-	space = isl_space_set_tuple_id(space, isl_dim_in, id);
-	add_tag = isl_map_universe(space);
-	access = isl_map_domain_product(access, add_tag);
-
-	return access;
-}
-
-/* Modify all expressions of type pet_expr_access in "expr"
- * by calling "fn" on them.
- */
-struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
-	struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
-	void *user)
-{
-	int i;
-
-	if (!expr)
-		return NULL;
-
-	for (i = 0; i < expr->n_arg; ++i) {
-		expr->args[i] = pet_expr_map_access(expr->args[i], fn, user);
-		if (!expr->args[i])
-			return pet_expr_free(expr);
-	}
-
-	if (expr->type == pet_expr_access)
-		expr = fn(expr, user);
-
-	return expr;
-}
-
-/* Call "fn" on each of the subexpressions of "expr" of type pet_expr_access.
+/* pet_scop with extra information that is used during parsing and printing.
  *
- * Return -1 on error (where fn return a negative value is treated as an error).
- * Otherwise return 0.
- */
-int pet_expr_foreach_access_expr(struct pet_expr *expr,
-	int (*fn)(struct pet_expr *expr, void *user), void *user)
-{
-	int i;
-
-	if (!expr)
-		return -1;
-
-	for (i = 0; i < expr->n_arg; ++i)
-		if (pet_expr_foreach_access_expr(expr->args[i], fn, user) < 0)
-			return -1;
-
-	if (expr->type == pet_expr_access)
-		return fn(expr, user);
-
-	return 0;
-}
-
-/* Modify the access relation and index expression
- * of the given access expression
- * based on the given iteration space transformation.
- * In particular, precompose the access relation and index expression
- * with the update function.
+ * In particular, we keep track of conditions under which we want
+ * to skip the rest of the current loop iteration (skip[pet_skip_now])
+ * and of conditions under which we want to skip subsequent
+ * loop iterations (skip[pet_skip_later]).
+ *
+ * The conditions are represented as index expressions defined
+ * over a zero-dimensional domain.  The index expression is either
+ * a boolean affine expression or an access to a variable, which
+ * is assumed to attain values zero and one.  The condition holds
+ * if the variable has value one or if the affine expression
+ * has value one (typically for only part of the parameter space).
+ *
+ * A missing condition (skip[type] == NULL) means that we don't want
+ * to skip anything.
  *
- * If the access has any arguments then the domain of the access relation
- * is a wrapped mapping from the iteration space to the space of
- * argument values.  We only need to change the domain of this wrapped
- * mapping, so we extend the input transformation with an identity mapping
- * on the space of argument values.
+ * Additionally, we keep track of the original input file
+ * inside pet_transform_C_source.
  */
-static struct pet_expr *update_domain(struct pet_expr *expr, void *user)
-{
-	isl_multi_pw_aff *update = user;
-	isl_space *space;
-
-	update = isl_multi_pw_aff_copy(update);
-
-	space = isl_map_get_space(expr->acc.access);
-	space = isl_space_domain(space);
-	if (!isl_space_is_wrapping(space))
-		isl_space_free(space);
-	else {
-		isl_multi_pw_aff *id;
-		space = isl_space_unwrap(space);
-		space = isl_space_range(space);
-		space = isl_space_map_from_set(space);
-		id = isl_multi_pw_aff_identity(space);
-		update = isl_multi_pw_aff_product(update, id);
-	}
-
-	expr->acc.access = isl_map_preimage_domain_multi_pw_aff(
-					    expr->acc.access,
-					    isl_multi_pw_aff_copy(update));
-	expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff(
-					    expr->acc.index, update);
-	if (!expr->acc.access || !expr->acc.index)
-		return pet_expr_free(expr);
-
-	return expr;
-}
+struct pet_scop_ext {
+	struct pet_scop scop;
 
-/* Modify all access relations in "expr" by precomposing them with
- * the given iteration space transformation.
- */
-static struct pet_expr *expr_update_domain(struct pet_expr *expr,
-	__isl_take isl_multi_pw_aff *update)
-{
-	expr = pet_expr_map_access(expr, &update_domain, update);
-	isl_multi_pw_aff_free(update);
-	return expr;
-}
+	isl_multi_pw_aff *skip[2];
+	FILE *input;
+};
 
 /* Construct a pet_stmt with given line number and statement
  * number from a pet_expr.
@@ -892,7 +105,7 @@ struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
 
 	dim = isl_space_from_domain(dim);
 	add_name = isl_multi_pw_aff_zero(dim);
-	expr = expr_update_domain(expr, add_name);
+	expr = pet_expr_update_domain(expr, add_name);
 
 	stmt->line = line;
 	stmt->domain = dom;
@@ -961,9 +174,9 @@ static void stmt_dump(struct pet_stmt *stmt, int indent)
 	isl_set_dump(stmt->domain);
 	fprintf(stderr, "%*s", indent, "");
 	isl_map_dump(stmt->schedule);
-	expr_dump(stmt->body, indent);
+	pet_expr_dump_with_indent(stmt->body, indent);
 	for (i = 0; i < stmt->n_arg; ++i)
-		expr_dump(stmt->args[i], indent + 2);
+		pet_expr_dump_with_indent(stmt->args[i], indent + 2);
 }
 
 void pet_stmt_dump(struct pet_stmt *stmt)
@@ -2089,7 +1302,7 @@ static struct pet_expr *embed_access(struct pet_expr *expr, void *user)
 {
 	struct pet_embed_access *data = user;
 
-	expr = update_domain(expr, data->extend);
+	expr = pet_expr_access_update_domain(expr, data->extend);
 	if (!expr)
 		return NULL;
 
@@ -2556,67 +1769,6 @@ static int args_insert_access(unsigned *n_arg, struct pet_expr ***args,
 	return 0;
 }
 
-/* Make the expression "expr" depend on the value of "test"
- * being equal to "satisfied".
- *
- * If "test" is an affine expression, we simply add the conditions
- * on the expression having the value "satisfied" to all access relations
- * and index expressions.
- *
- * Otherwise, we add a filter to "expr" (which is then assumed to be
- * an access expression) corresponding to "test" being equal to "satisfied".
- */
-struct pet_expr *pet_expr_filter(struct pet_expr *expr,
-	__isl_take isl_multi_pw_aff *test, int satisfied)
-{
-	isl_id *id;
-	isl_ctx *ctx;
-	isl_space *space;
-	isl_pw_multi_aff *pma;
-
-	if (!expr || !test)
-		goto error;
-
-	if (!isl_multi_pw_aff_has_tuple_id(test, isl_dim_out)) {
-		isl_pw_aff *pa;
-		isl_set *cond;
-
-		pa = isl_multi_pw_aff_get_pw_aff(test, 0);
-		isl_multi_pw_aff_free(test);
-		if (satisfied)
-			cond = isl_pw_aff_non_zero_set(pa);
-		else
-			cond = isl_pw_aff_zero_set(pa);
-		return pet_expr_restrict(expr, isl_set_params(cond));
-	}
-
-	ctx = isl_multi_pw_aff_get_ctx(test);
-	if (expr->type != pet_expr_access)
-		isl_die(ctx, isl_error_invalid,
-			"can only filter access expressions", goto error);
-
-	space = isl_space_domain(isl_map_get_space(expr->acc.access));
-	id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out);
-	pma = pet_filter_insert_pma(space, id, satisfied);
-
-	expr->acc.access = isl_map_preimage_domain_pw_multi_aff(
-						expr->acc.access,
-						isl_pw_multi_aff_copy(pma));
-	expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff(
-							expr->acc.index, pma);
-	if (!expr->acc.access || !expr->acc.index)
-		goto error;
-
-	if (args_insert_access(&expr->n_arg, &expr->args, test) < 0)
-		goto error;
-
-	isl_multi_pw_aff_free(test);
-	return expr;
-error:
-	isl_multi_pw_aff_free(test);
-	return pet_expr_free(expr);
-}
-
 /* Look through the applications in "scop" for any that can be
  * applied to the filter expressed by "map" and "satisified".
  * If there is any, then apply it to "map" and return the result.
@@ -3096,34 +2248,6 @@ static __isl_give isl_space *scop_collect_params(struct pet_scop *scop,
 	return space;
 }
 
-/* Add all parameters in "space" to the access relation and index expression
- * of "expr".
- */
-static struct pet_expr *propagate_params(struct pet_expr *expr, void *user)
-{
-	isl_space *space = user;
-
-	expr->acc.access = isl_map_align_params(expr->acc.access,
-						isl_space_copy(space));
-	expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index,
-						isl_space_copy(space));
-	if (!expr->acc.access || !expr->acc.index)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
-/* Add all parameters in "space" to all access relations and index expressions
- * in "expr".
- */
-static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
-	__isl_take isl_space *space)
-{
-	expr = pet_expr_map_access(expr, &propagate_params, space);
-	isl_space_free(space);
-	return expr;
-}
-
 /* Add all parameters in "space" to the domain, schedule and
  * all access relations in "stmt".
  */
@@ -3141,12 +2265,12 @@ static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
 						isl_space_copy(space));
 
 	for (i = 0; i < stmt->n_arg; ++i) {
-		stmt->args[i] = expr_propagate_params(stmt->args[i],
+		stmt->args[i] = pet_expr_align_params(stmt->args[i],
 						isl_space_copy(space));
 		if (!stmt->args[i])
 			goto error;
 	}
-	stmt->body = expr_propagate_params(stmt->body, isl_space_copy(space));
+	stmt->body = pet_expr_align_params(stmt->body, isl_space_copy(space));
 
 	if (!stmt->domain || !stmt->schedule || !stmt->body)
 		goto error;
@@ -3241,113 +2365,6 @@ struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
 	return scop;
 }
 
-/* Check if the given index expression accesses a (0D) array that corresponds
- * to one of the parameters in "space".  If so, replace the array access
- * by an access to the set of integers with as index (and value)
- * that parameter.
- */
-static __isl_give isl_multi_pw_aff *index_detect_parameter(
-	__isl_take isl_multi_pw_aff *index, __isl_take isl_space *space)
-{
-	isl_local_space *ls;
-	isl_id *array_id = NULL;
-	isl_aff *aff;
-	int pos = -1;
-
-	if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
-		array_id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
-		pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
-	}
-	isl_space_free(space);
-
-	if (pos < 0) {
-		isl_id_free(array_id);
-		return index;
-	}
-
-	space = isl_multi_pw_aff_get_domain_space(index);
-	isl_multi_pw_aff_free(index);
-
-	pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
-	if (pos < 0) {
-		space = isl_space_insert_dims(space, isl_dim_param, 0, 1);
-		space = isl_space_set_dim_id(space, isl_dim_param, 0, array_id);
-		pos = 0;
-	} else
-		isl_id_free(array_id);
-
-	ls = isl_local_space_from_space(space);
-	aff = isl_aff_var_on_domain(ls, isl_dim_param, pos);
-	index = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
-
-	return index;
-}
-
-/* Check if the given access relation accesses a (0D) array that corresponds
- * to one of the parameters in "space".  If so, replace the array access
- * by an access to the set of integers with as index (and value)
- * that parameter.
- */
-static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
-	__isl_take isl_space *space)
-{
-	isl_id *array_id = NULL;
-	int pos = -1;
-
-	if (isl_map_has_tuple_id(access, isl_dim_out)) {
-		array_id = isl_map_get_tuple_id(access, isl_dim_out);
-		pos = isl_space_find_dim_by_id(space, isl_dim_param, array_id);
-	}
-	isl_space_free(space);
-
-	if (pos < 0) {
-		isl_id_free(array_id);
-		return access;
-	}
-
-	pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
-	if (pos < 0) {
-		access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
-		access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
-		pos = 0;
-	} else
-		isl_id_free(array_id);
-
-	access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
-	access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
-
-	return access;
-}
-
-/* If "expr" accesses a (0D) array that corresponds to one of the parameters
- * in "space" then replace it by a value equal to the corresponding parameter.
- */
-static struct pet_expr *detect_parameter_accesses(struct pet_expr *expr,
-	void *user)
-{
-	isl_space *space = user;
-
-	expr->acc.access = access_detect_parameter(expr->acc.access,
-						isl_space_copy(space));
-	expr->acc.index = index_detect_parameter(expr->acc.index,
-						isl_space_copy(space));
-	if (!expr->acc.access || !expr->acc.index)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
-/* Replace all accesses to (0D) arrays that correspond to one of the parameters
- * in "space" by a value equal to the corresponding parameter.
- */
-static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
-	__isl_take isl_space *space)
-{
-	expr = pet_expr_map_access(expr, &detect_parameter_accesses, space);
-	isl_space_free(space);
-	return expr;
-}
-
 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
  * in "space" by a value equal to the corresponding parameter.
  */
@@ -3357,7 +2374,7 @@ static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
 	if (!stmt)
 		goto error;
 
-	stmt->body = expr_detect_parameter_accesses(stmt->body,
+	stmt->body = pet_expr_detect_parameter_accesses(stmt->body,
 							isl_space_copy(space));
 
 	if (!stmt->domain || !stmt->schedule || !stmt->body)
@@ -3414,52 +2431,6 @@ struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
 	return scop;
 }
 
-/* Return the relation mapping domain iterations to all possibly
- * accessed data elements.
- * In particular, take the access relation and project out the values
- * of the arguments, if any.
- */
-__isl_give isl_map *pet_expr_access_get_may_access(struct pet_expr *expr)
-{
-	isl_map *access;
-	isl_space *space;
-	isl_map *map;
-
-	if (!expr)
-		return NULL;
-	if (expr->type != pet_expr_access)
-		return NULL;
-
-	access = isl_map_copy(expr->acc.access);
-	if (expr->n_arg == 0)
-		return access;
-
-	space = isl_space_domain(isl_map_get_space(access));
-	map = isl_map_universe(isl_space_unwrap(space));
-	map = isl_map_domain_map(map);
-	access = isl_map_apply_domain(access, map);
-
-	return access;
-}
-
-/* Return the relation mapping domain iterations to all possibly
- * accessed data elements, with its domain tagged with the reference
- * identifier.
- */
-__isl_give isl_map *pet_expr_access_get_tagged_may_access(
-	struct pet_expr *expr)
-{
-	isl_map *access;
-
-	if (!expr)
-		return NULL;
-
-	access = pet_expr_access_get_may_access(expr);
-	access = tag_access(access, isl_id_copy(expr->acc.ref_id));
-
-	return access;
-}
-
 /* Add the access relation of the access expression "expr" to "accesses" and
  * return the result.
  * The domain of the access relation is intersected with "domain".
@@ -3474,7 +2445,7 @@ static __isl_give isl_union_map *expr_collect_access(struct pet_expr *expr,
 	access = pet_expr_access_get_may_access(expr);
 	access = isl_map_intersect_domain(access, isl_set_copy(domain));
 	if (tag)
-		access = tag_access(access, isl_id_copy(expr->acc.ref_id));
+		access = pet_expr_tag_access(expr, access);
 	return isl_union_map_add_map(accesses, access);
 }
 
@@ -3808,61 +2779,11 @@ __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
 	return schedule;
 }
 
-/* Internal data structure for expr_writes.
- * "id" is the identifier that we are looking for.
- * "found" is set if we have found the identifier being written to.
- */
-struct pet_expr_writes_data {
-	isl_id *id;
-	int found;
-};
-
-/* Given an access expression, check if it writes to data->id.
- * If so, set data->found and abort the search.
- */
-static int writes(struct pet_expr *expr, void *user)
-{
-	struct pet_expr_writes_data *data = user;
-	isl_id *write_id;
-
-	if (!expr->acc.write)
-		return 0;
-	if (pet_expr_is_affine(expr))
-		return 0;
-
-	write_id = pet_expr_access_get_id(expr);
-	isl_id_free(write_id);
-
-	if (!write_id)
-		return -1;
-
-	if (write_id != data->id)
-		return 0;
-
-	data->found = 1;
-	return -1;
-}
-
-/* Does expression "expr" write to "id"?
- */
-static int expr_writes(struct pet_expr *expr, __isl_keep isl_id *id)
-{
-	struct pet_expr_writes_data data;
-
-	data.id = id;
-	data.found = 0;
-	if (pet_expr_foreach_access_expr(expr, &writes, &data) < 0 &&
-	    !data.found)
-		return -1;
-
-	return data.found;
-}
-
 /* Does statement "stmt" write to "id"?
  */
 static int stmt_writes(struct pet_stmt *stmt, __isl_keep isl_id *id)
 {
-	return expr_writes(stmt->body, id);
+	return pet_expr_writes(stmt->body, id);
 }
 
 /* Is there any write access in "scop" that accesses "id"?
@@ -3883,28 +2804,6 @@ int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id)
 	return 0;
 }
 
-/* Add a reference identifier to access expression "expr".
- * "user" points to an integer that contains the sequence number
- * of the next reference.
- */
-static struct pet_expr *access_add_ref_id(struct pet_expr *expr, void *user)
-{
-	isl_ctx *ctx;
-	char name[50];
-	int *n_ref = user;
-
-	if (!expr)
-		return expr;
-
-	ctx = isl_map_get_ctx(expr->acc.access);
-	snprintf(name, sizeof(name), "__pet_ref_%d", (*n_ref)++);
-	expr->acc.ref_id = isl_id_alloc(ctx, name, NULL);
-	if (!expr->acc.ref_id)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
 /* Add a reference identifier to all access expressions in "stmt".
  * "n_ref" points to an integer that contains the sequence number
  * of the next reference.
@@ -3917,13 +2816,12 @@ static struct pet_stmt *stmt_add_ref_ids(struct pet_stmt *stmt, int *n_ref)
 		return NULL;
 
 	for (i = 0; i < stmt->n_arg; ++i) {
-		stmt->args[i] = pet_expr_map_access(stmt->args[i],
-						    &access_add_ref_id, n_ref);
+		stmt->args[i] = pet_expr_add_ref_ids(stmt->args[i], n_ref);
 		if (!stmt->args[i])
 			return pet_stmt_free(stmt);
 	}
 
-	stmt->body = pet_expr_map_access(stmt->body, &access_add_ref_id, n_ref);
+	stmt->body = pet_expr_add_ref_ids(stmt->body, n_ref);
 	if (!stmt->body)
 		return pet_stmt_free(stmt);
 
@@ -3965,20 +2863,6 @@ static struct pet_array *array_anonymize(struct pet_array *array)
 	return array;
 }
 
-/* Reset the user pointer on all parameter and tuple ids in
- * the access relation and the index expressions
- * of the access expression "expr".
- */
-static struct pet_expr *access_anonymize(struct pet_expr *expr, void *user)
-{
-	expr->acc.access = isl_map_reset_user(expr->acc.access);
-	expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index);
-	if (!expr->acc.access || !expr->acc.index)
-		return pet_expr_free(expr);
-
-	return expr;
-}
-
 /* Reset the user pointer on all parameter and tuple ids in "stmt".
  */
 static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
@@ -3996,14 +2880,12 @@ static struct pet_stmt *stmt_anonymize(struct pet_stmt *stmt)
 		return pet_stmt_free(stmt);
 
 	for (i = 0; i < stmt->n_arg; ++i) {
-		stmt->args[i] = pet_expr_map_access(stmt->args[i],
-						    &access_anonymize, NULL);
+		stmt->args[i] = pet_expr_anonymize(stmt->args[i]);
 		if (!stmt->args[i])
 			return pet_stmt_free(stmt);
 	}
 
-	stmt->body = pet_expr_map_access(stmt->body,
-						    &access_anonymize, NULL);
+	stmt->body = pet_expr_anonymize(stmt->body);
 	if (!stmt->body)
 		return pet_stmt_free(stmt);
 
diff --git a/scop.h b/scop.h
index 23ce5d4..4cdaf20 100644
--- a/scop.h
+++ b/scop.h
@@ -15,39 +15,6 @@ extern "C" {
  */
 enum pet_skip { pet_skip_now = 0, pet_skip_later = 1 };
 
-const char *pet_type_str(enum pet_expr_type type);
-enum pet_expr_type pet_str_type(const char *str);
-
-enum pet_op_type pet_str_op(const char *str);
-
-struct pet_expr *pet_expr_from_index_and_depth(
-	__isl_take isl_multi_pw_aff *index, int depth);
-struct pet_expr *pet_expr_from_access_and_index(__isl_take isl_map *access,
-	__isl_take isl_multi_pw_aff *index);
-struct pet_expr *pet_expr_kill_from_access_and_index(__isl_take isl_map *access,
-	__isl_take isl_multi_pw_aff *index);
-struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
-	struct pet_expr *arg);
-struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
-	struct pet_expr *lhs, struct pet_expr *rhs);
-struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
-	struct pet_expr *lhs, struct pet_expr *rhs);
-struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
-	unsigned n_arg);
-struct pet_expr *pet_expr_new_cast(isl_ctx *ctx, const char *type_name,
-	struct pet_expr *arg);
-struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d, const char *s);
-struct pet_expr *pet_expr_new_int(__isl_take isl_val *v);
-void pet_expr_dump(struct pet_expr *expr);
-
-int pet_expr_is_affine(struct pet_expr *expr);
-__isl_give isl_id *pet_expr_access_get_id(struct pet_expr *expr);
-struct pet_expr *pet_expr_access_align_params(struct pet_expr *expr);
-int pet_expr_is_scalar_access(struct pet_expr *expr);
-int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2);
-struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
-	__isl_take isl_set *cond);
-
 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line,
 	__isl_take isl_id *label, int id, struct pet_expr *expr);
 void pet_stmt_dump(struct pet_stmt *stmt);
@@ -85,8 +52,6 @@ struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
 struct pet_scop *pet_scop_restrict_context(struct pet_scop *scop,
 	__isl_take isl_set *context);
 struct pet_scop *pet_scop_reset_context(struct pet_scop *scop);
-struct pet_expr *pet_expr_filter(struct pet_expr *expr,
-	__isl_take isl_multi_pw_aff *test, int satisfied);
 struct pet_scop *pet_scop_filter(struct pet_scop *scop,
 	__isl_take isl_multi_pw_aff *test, int satisfied);
 struct pet_scop *pet_scop_merge_filters(struct pet_scop *scop);
@@ -101,12 +66,6 @@ struct pet_scop *pet_scop_gist(struct pet_scop *scop,
 struct pet_scop *pet_scop_add_ref_ids(struct pet_scop *scop);
 struct pet_scop *pet_scop_anonymize(struct pet_scop *scop);
 
-int pet_expr_foreach_access_expr(struct pet_expr *expr,
-	int (*fn)(struct pet_expr *expr, void *user), void *user);
-struct pet_expr *pet_expr_map_access(struct pet_expr *expr,
-	struct pet_expr *(*fn)(struct pet_expr *expr, void *user),
-	void *user);
-
 int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id);
 
 int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type);
diff --git a/scop_plus.cc b/scop_plus.cc
index 19f9202..90f43fc 100644
--- a/scop_plus.cc
+++ b/scop_plus.cc
@@ -36,6 +36,7 @@
 #include <vector>
 
 #include "clang.h"
+#include "expr.h"
 #include "scop_plus.h"
 
 using namespace std;
-- 
2.11.4.GIT