link against isl libraries first

[pet.git] / print.c

/*
 * 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 <isl/id.h>
#include <isl/space.h>
#include <isl/local_space.h>
#include <isl/aff.h>
#include <isl/ast.h>
#include <isl/ast_build.h>
#include <isl/printer.h>
#include <isl/val.h>
#include <pet.h>
#include "expr.h"
#include "print.h"
#include "scop.h"

/* Return the dimension of the domain of the embedded map
 * in the domain of "mpa".
 */
static int domain_domain_dim(__isl_keep isl_multi_pw_aff *mpa)
{
        int dim;
        isl_space *space;

        space = isl_multi_pw_aff_get_space(mpa);
        space = isl_space_unwrap(isl_space_domain(space));
        dim = isl_space_dim(space, isl_dim_in);
        isl_space_free(space);

        return dim;
}

/* Given an access expression, check if any of the arguments
 * for which an isl_ast_expr would be constructed by
 * pet_expr_build_nested_ast_exprs are not themselves access expressions.
 * If so, set *found and abort the search.
 */
static int depends_on_expressions(__isl_keep pet_expr *expr, void *user)
{
        int i, dim;
        int *found = user;

        if (expr->n_arg == 0)
                return 0;

        dim = domain_domain_dim(expr->acc.index);

        for (i = 0; i < expr->n_arg; ++i) {
                if (!isl_multi_pw_aff_involves_dims(expr->acc.index,
                                                    isl_dim_in, dim + i, 1))
                        continue;
                if (expr->args[i]->type != pet_expr_access) {
                        *found = 1;
                        return -1;
                }
        }

        return 0;
}

/* pet_stmt_build_ast_exprs is currently limited to only handle
 * some forms of data dependent accesses.
 * If pet_stmt_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
 * can safely be called on "stmt".
 */
int pet_stmt_can_build_ast_exprs(struct pet_stmt *stmt)
{
        int r;
        int found = 0;

        if (!stmt)
                return -1;

        r = pet_tree_foreach_access_expr(stmt->body,
                                        &depends_on_expressions, &found);
        if (r < 0 && !found)
                return -1;

        return !found;
}

/* pet_stmt_build_ast_exprs is currently limited to only handle
 * some forms of data dependent accesses.
 * If pet_scop_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
 * can safely be called on all statements in the scop.
 */
int pet_scop_can_build_ast_exprs(struct pet_scop *scop)
{
        int i;

        if (!scop)
                return -1;

        for (i = 0; i < scop->n_stmt; ++i) {
                int ok = pet_stmt_can_build_ast_exprs(scop->stmts[i]);
                if (ok < 0 || !ok)
                        return ok;
        }

        return 1;
}

/* Internal data structure for pet_stmt_build_ast_exprs.
 *
 * "build" is used to construct an AST expression from an index expression.
 * "fn_index" is used to transform the index expression prior to
 *      the construction of the AST expression.
 * "fn_expr" is used to transform the constructed AST expression.
 * "ref2expr" collects the results.
 */
struct pet_build_ast_expr_data {
        isl_ast_build *build;
        __isl_give isl_multi_pw_aff *(*fn_index)(
                __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
                void *user);
        void *user_index;
        __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
                __isl_keep isl_id *id, void *user);
        void *user_expr;
        isl_id_to_ast_expr *ref2expr;
};

/* Given an index expression "index" with nested expressions, replace
 * those nested expressions by parameters.  The identifiers
 * of those parameters reference the corresponding arguments
 * of "expr".  The same identifiers are used in
 * pet_expr_build_nested_ast_exprs.
 *
 * In particular, if "index" is of the form
 *
 *      { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
 *
 * then we construct the expression
 *
 *      [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
 *
 */
static __isl_give isl_multi_pw_aff *parametrize_nested_exprs(
        __isl_take isl_multi_pw_aff *index, __isl_keep pet_expr *expr)
{
        int i;
        isl_ctx *ctx;
        isl_space *space, *space2;
        isl_local_space *ls;
        isl_multi_aff *ma, *ma2;

        ctx = isl_multi_pw_aff_get_ctx(index);
        space = isl_multi_pw_aff_get_domain_space(index);
        space = isl_space_unwrap(space);

        space2 = isl_space_domain(isl_space_copy(space));
        ma = isl_multi_aff_identity(isl_space_map_from_set(space2));

        space = isl_space_insert_dims(space, isl_dim_param, 0,
                                        expr->n_arg);
        for (i = 0; i < expr->n_arg; ++i) {
                isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);

                space = isl_space_set_dim_id(space, isl_dim_param, i, id);
        }
        space2 = isl_space_domain(isl_space_copy(space));
        ls = isl_local_space_from_space(space2);
        ma2 = isl_multi_aff_zero(space);
        for (i = 0; i < expr->n_arg; ++i) {
                isl_aff *aff;
                aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
                                                isl_dim_param, i);
                ma2 = isl_multi_aff_set_aff(ma2, i, aff);
        }
        isl_local_space_free(ls);

        ma = isl_multi_aff_range_product(ma, ma2);

        return isl_multi_pw_aff_pullback_multi_aff(index, ma);
}

static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
        __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data);

/* Construct an associative array from identifiers for the nested
 * expressions of "expr" to the corresponding isl_ast_expr.
 * The identifiers reference the corresponding arguments of "expr".
 * The same identifiers are used in parametrize_nested_exprs.
 * Note that we only need to construct isl_ast_expr objects for
 * those arguments that actually appear in the index expression of "expr".
 */
static __isl_give isl_id_to_ast_expr *pet_expr_build_nested_ast_exprs(
        __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
{
        int i, dim;
        isl_ctx *ctx = isl_ast_build_get_ctx(data->build);
        isl_id_to_ast_expr *id2expr;

        dim = domain_domain_dim(expr->acc.index);
        id2expr = isl_id_to_ast_expr_alloc(ctx, expr->n_arg);

        for (i = 0; i < expr->n_arg; ++i) {
                isl_id *id;
                isl_ast_expr *ast_expr;

                if (!isl_multi_pw_aff_involves_dims(expr->acc.index,
                                                    isl_dim_in, dim + i, 1))
                        continue;

                id = isl_id_alloc(ctx, NULL, expr->args[i]);
                ast_expr = pet_expr_build_ast_expr(expr->args[i], data);
                id2expr = isl_id_to_ast_expr_set(id2expr, id, ast_expr);
        }

        return id2expr;
}

/* Construct an AST expression from an access expression.
 *
 * If the expression has any arguments, we first convert those
 * to AST expressions and replace the references to those arguments
 * in the index expression by parameters.
 *
 * Then we apply the index transformation if any was provided by the user.
 *
 * If the "access" is actually an affine expression, we print is as such.
 * Otherwise, we print a proper access.
 *
 * If the original expression had any arguments, then they are plugged in now.
 *
 * Finally, we apply an AST transformation on the result, if any was provided
 * by the user.
 */
static __isl_give isl_ast_expr *pet_expr_access_build_ast_expr(
        __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
{
        isl_pw_aff *pa;
        isl_multi_pw_aff *mpa;
        isl_ast_expr *ast_expr;
        isl_id_to_ast_expr *id2expr;
        isl_ast_build *build = data->build;

        if (!expr)
                return NULL;
        if (expr->type != pet_expr_access)
                isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
                        "not an access expression", return NULL);

        mpa = isl_multi_pw_aff_copy(expr->acc.index);

        if (expr->n_arg > 0) {
                mpa = parametrize_nested_exprs(mpa, expr);
                id2expr = pet_expr_build_nested_ast_exprs(expr, data);
        }

        if (data->fn_index)
                mpa = data->fn_index(mpa, expr->acc.ref_id, data->user_index);
        mpa = isl_multi_pw_aff_coalesce(mpa);

        if (!pet_expr_is_affine(expr)) {
                ast_expr = isl_ast_build_access_from_multi_pw_aff(build, mpa);
        } else {
                pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
                ast_expr = isl_ast_build_expr_from_pw_aff(build, pa);
                isl_multi_pw_aff_free(mpa);
        }
        if (expr->n_arg > 0)
                ast_expr = isl_ast_expr_substitute_ids(ast_expr, id2expr);
        if (data->fn_expr)
                ast_expr = data->fn_expr(ast_expr, expr->acc.ref_id,
                                            data->user_index);

        return ast_expr;
}

/* A type representing a binary operation on objects of type isl_ast_expr.
 */
typedef __isl_give isl_ast_expr *(*binary_ast_op_t)(
        __isl_take isl_ast_expr *expr1, __isl_take isl_ast_expr *expr2);

/* For the supported binary operations, the corresponding function
 * performing the operation on objects of type isl_ast_expr.
 */
static binary_ast_op_t binary_ast_op[] = {
        [pet_op_add] = &isl_ast_expr_add,
        [pet_op_sub] = &isl_ast_expr_sub,
        [pet_op_last] = NULL,
};

/* Try and construct an AST expression from an operation expression.
 *
 * Only some binary operations are currently supported.
 */
static __isl_give isl_ast_expr *pet_expr_op_build_ast_expr(
        __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
{
        isl_ast_expr *lhs, *rhs;
        binary_ast_op_t ast_op;

        if (!expr)
                return NULL;
        if (expr->type != pet_expr_op)
                isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
                        "not an operation expression", return NULL);

        ast_op = binary_ast_op[expr->op];
        if (!ast_op)
                isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
                        "unsupported operation type", return NULL);

        lhs = pet_expr_build_ast_expr(expr->args[pet_bin_lhs], data);
        rhs = pet_expr_build_ast_expr(expr->args[pet_bin_rhs], data);
        return ast_op(lhs, rhs);
}

/* Try and construct an AST expression from an expression.
 *
 * Only some types of expressions are currently supported,
 * - integer values
 * - access expressions
 * - (some) operation expressions.
 */
static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
        __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
{
        if (!expr)
                return NULL;

        switch (expr->type) {
        case pet_expr_error:
                return NULL;
        case pet_expr_int:
                return isl_ast_expr_from_val(isl_val_copy(expr->i));
        case pet_expr_double:
                isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
                        "unsupported expression type", return NULL);
        case pet_expr_access:
                return pet_expr_access_build_ast_expr(expr, data);
        case pet_expr_op:
                return pet_expr_op_build_ast_expr(expr, data);
        case pet_expr_call:
                isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
                        "unsupported expression type", return NULL);
        case pet_expr_cast:
                isl_die(pet_expr_get_ctx(expr), isl_error_unsupported,
                        "unsupported expression type", return NULL);
        }

        return NULL;
}

/* Construct an AST expression from the access expression "expr" and
 * add the mapping from reference identifier to AST expression to
 * data->ref2expr.
 */
static int add_access(__isl_keep pet_expr *expr, void *user)
{
        struct pet_build_ast_expr_data *data = user;
        isl_id *id;
        isl_ast_expr *ast_expr;

        ast_expr = pet_expr_access_build_ast_expr(expr, data);

        id = isl_id_copy(expr->acc.ref_id);
        data->ref2expr = isl_id_to_ast_expr_set(data->ref2expr, id, ast_expr);

        return 0;
}

/* Construct an associative array from reference identifiers of
 * access expressions in "stmt" to the corresponding isl_ast_expr.
 * Each index expression is first transformed through "fn_index"
 * (if not NULL).  Then an AST expression is generated using "build".
 * Finally, the AST expression is transformed using "fn_expr"
 * (if not NULL).
 */
__isl_give isl_id_to_ast_expr *pet_stmt_build_ast_exprs(struct pet_stmt *stmt,
        __isl_keep isl_ast_build *build,
        __isl_give isl_multi_pw_aff *(*fn_index)(
                __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
                void *user), void *user_index,
        __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
                __isl_keep isl_id *id, void *user), void *user_expr)
{
        struct pet_build_ast_expr_data data =
                { build, fn_index, user_index, fn_expr, user_expr };
        isl_ctx *ctx;

        if (!stmt || !build)
                return NULL;

        ctx = isl_ast_build_get_ctx(build);
        data.ref2expr = isl_id_to_ast_expr_alloc(ctx, 0);
        if (pet_tree_foreach_access_expr(stmt->body, &add_access, &data) < 0)
                data.ref2expr = isl_id_to_ast_expr_free(data.ref2expr);

        return data.ref2expr;
}

/* Print the access expression "expr" to "p".
 *
 * We look up the corresponding isl_ast_expr in "ref2expr"
 * and print that to "p".
 */
static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
        __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        isl_ast_expr *ast_expr;
        int is_access;

        if (!isl_id_to_ast_expr_has(ref2expr, expr->acc.ref_id))
                isl_die(isl_printer_get_ctx(p), isl_error_internal,
                        "missing expression", return isl_printer_free(p));

        ast_expr = isl_id_to_ast_expr_get(ref2expr,
                                        isl_id_copy(expr->acc.ref_id));
        is_access = isl_ast_expr_get_type(ast_expr) == isl_ast_expr_op &&
                isl_ast_expr_get_op_type(ast_expr) == isl_ast_op_access;
        if (!is_access)
                p = isl_printer_print_str(p, "(");
        p = isl_printer_print_ast_expr(p, ast_expr);
        if (!is_access)
                p = isl_printer_print_str(p, ")");
        isl_ast_expr_free(ast_expr);

        return p;
}

/* Is "op" a postfix operator?
 */
static int is_postfix(enum pet_op_type op)
{
        switch (op) {
        case pet_op_post_inc:
        case pet_op_post_dec:
                return 1;
        default:
                return 0;
        }
}

static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
        __isl_keep pet_expr *expr, int outer,
        __isl_keep isl_id_to_ast_expr *ref2expr);

/* Print operation expression "expr" to "p".
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_op(__isl_take isl_printer *p,
        __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        switch (expr->n_arg) {
        case 1:
                if (!is_postfix(expr->op))
                        p = isl_printer_print_str(p, pet_op_str(expr->op));
                p = print_pet_expr(p, expr->args[pet_un_arg], 0, ref2expr);
                if (is_postfix(expr->op))
                        p = isl_printer_print_str(p, pet_op_str(expr->op));
                break;
        case 2:
                p = print_pet_expr(p, expr->args[pet_bin_lhs], 0,
                                        ref2expr);
                p = isl_printer_print_str(p, " ");
                p = isl_printer_print_str(p, pet_op_str(expr->op));
                p = isl_printer_print_str(p, " ");
                p = print_pet_expr(p, expr->args[pet_bin_rhs], 0,
                                        ref2expr);
                break;
        case 3:
                p = print_pet_expr(p, expr->args[pet_ter_cond], 0,
                                        ref2expr);
                p = isl_printer_print_str(p, " ? ");
                p = print_pet_expr(p, expr->args[pet_ter_true], 0,
                                        ref2expr);
                p = isl_printer_print_str(p, " : ");
                p = print_pet_expr(p, expr->args[pet_ter_false], 0,
                                        ref2expr);
                break;
        }

        return p;
}

/* Print "expr" to "p".
 *
 * If "outer" is set, then we are printing the outer expression statement.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
        __isl_keep pet_expr *expr, int outer,
        __isl_keep isl_id_to_ast_expr *ref2expr)
{
        int i;

        switch (expr->type) {
        case pet_expr_error:
                p = isl_printer_free(p);
                break;
        case pet_expr_int:
                p = isl_printer_print_val(p, expr->i);
                break;
        case pet_expr_double:
                p = isl_printer_print_str(p, expr->d.s);
                break;
        case pet_expr_access:
                p = print_access(p, expr, ref2expr);
                break;
        case pet_expr_op:
                if (!outer)
                        p = isl_printer_print_str(p, "(");
                p = print_op(p, expr, ref2expr);
                if (!outer)
                        p = isl_printer_print_str(p, ")");
                break;
        case pet_expr_call:
                p = isl_printer_print_str(p, expr->c.name);
                p = isl_printer_print_str(p, "(");
                for (i = 0; i < expr->n_arg; ++i) {
                        if (i)
                                p = isl_printer_print_str(p, ", ");
                        p = print_pet_expr(p, expr->args[i], 1, ref2expr);
                }
                p = isl_printer_print_str(p, ")");
                break;
        case pet_expr_cast:
                if (!outer)
                        p = isl_printer_print_str(p, "(");
                p = isl_printer_print_str(p, "(");
                p = isl_printer_print_str(p, expr->type_name);
                p = isl_printer_print_str(p, ") ");
                p = print_pet_expr(p, expr->args[0], 0, ref2expr);
                if (!outer)
                        p = isl_printer_print_str(p, ")");
                break;
        }

        return p;
}

static __isl_give isl_printer *print_pet_tree(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, int in_block,
        __isl_keep isl_id_to_ast_expr *ref2expr);

/* Print "tree" to "p", where "tree" is of type pet_tree_block.
 *
 * If "in_block" is set, then the caller has just printed a block,
 * so there is no need to print one for this node.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_tree_block(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, int in_block,
        __isl_keep isl_id_to_ast_expr *ref2expr)
{
        int i, n;

        if (!in_block) {
                p = isl_printer_start_line(p);
                p = isl_printer_print_str(p, "{");
                p = isl_printer_end_line(p);
                p = isl_printer_indent(p, 2);
        }

        n = pet_tree_block_n_child(tree);

        for (i = 0; i < n; ++i) {
                pet_tree *child;

                child = pet_tree_block_get_child(tree, i);
                p = print_pet_tree(p, child, 0, ref2expr);
                pet_tree_free(child);
        }

        if (!in_block) {
                p = isl_printer_indent(p, -2);
                p = isl_printer_start_line(p);
                p = isl_printer_print_str(p, "}");
                p = isl_printer_end_line(p);
        }

        return p;
}

/* Print "tree" to "p", where "tree" is of type pet_tree_if or
 * pet_tree_if_else..
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_tree_if(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *expr;
        pet_tree *body;

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "if (");
        expr = pet_tree_if_get_cond(tree);
        p = print_pet_expr(p, expr, 1, ref2expr);
        pet_expr_free(expr);
        p = isl_printer_print_str(p, ") {");
        p = isl_printer_end_line(p);

        p = isl_printer_indent(p, 2);
        body = pet_tree_if_get_then(tree);
        p = print_pet_tree(p, body, 1, ref2expr);
        pet_tree_free(body);
        p = isl_printer_indent(p, -2);

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "}");

        if (pet_tree_get_type(tree) == pet_tree_if_else) {
                p = isl_printer_print_str(p, " else {");
                p = isl_printer_end_line(p);

                p = isl_printer_indent(p, 2);
                body = pet_tree_if_get_else(tree);
                p = print_pet_tree(p, body, 1, ref2expr);
                pet_tree_free(body);
                p = isl_printer_indent(p, -2);

                p = isl_printer_start_line(p);
                p = isl_printer_print_str(p, "}");
        }

        p = isl_printer_end_line(p);

        return p;
}

/* Print "tree" to "p", where "tree" is of type pet_tree_for.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_tree_for(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *expr_iv, *expr;
        pet_tree *body;

        expr_iv = pet_tree_loop_get_var(tree);

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "for (");
        p = print_pet_expr(p, expr_iv, 1, ref2expr);
        p = isl_printer_print_str(p, " = ");
        expr = pet_tree_loop_get_init(tree);
        p = print_pet_expr(p, expr, 0, ref2expr);
        pet_expr_free(expr);
        p = isl_printer_print_str(p, "; ");
        expr = pet_tree_loop_get_cond(tree);
        p = print_pet_expr(p, expr, 1, ref2expr);
        pet_expr_free(expr);
        p = isl_printer_print_str(p, "; ");
        p = print_pet_expr(p, expr_iv, 1, ref2expr);
        p = isl_printer_print_str(p, " += ");
        expr = pet_tree_loop_get_inc(tree);
        p = print_pet_expr(p, expr, 0, ref2expr);
        pet_expr_free(expr);
        p = isl_printer_print_str(p, ") {");
        p = isl_printer_end_line(p);

        pet_expr_free(expr_iv);

        p = isl_printer_indent(p, 2);
        body = pet_tree_loop_get_body(tree);
        p = print_pet_tree(p, body, 1, ref2expr);
        pet_tree_free(body);
        p = isl_printer_indent(p, -2);

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "}");
        p = isl_printer_end_line(p);

        return p;
}

/* Print "tree" to "p", where "tree" is of type pet_tree_while or
 * pet_tree_infinite_loop.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 *
 * pet_tree_loop_get_cond returns "1" when called on a tree of type
 * pet_tree_infinite_loop, so we can treat them in the same way
 * as trees of type pet_tree_while.
 */
static __isl_give isl_printer *print_pet_tree_while(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *expr;
        pet_tree *body;

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "while (");
        expr = pet_tree_loop_get_cond(tree);
        p = print_pet_expr(p, expr, 1, ref2expr);
        pet_expr_free(expr);
        p = isl_printer_print_str(p, ") {");
        p = isl_printer_end_line(p);

        p = isl_printer_indent(p, 2);
        body = pet_tree_loop_get_body(tree);
        p = print_pet_tree(p, body, 1, ref2expr);
        pet_tree_free(body);
        p = isl_printer_indent(p, -2);

        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "}");
        p = isl_printer_end_line(p);

        return p;
}

/* Print "tree" to "p", where "tree" is of type pet_tree_decl_init.
 *
 * We assume all variables have already been declared, so we
 * only print the assignment implied by the declaration initialization.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_tree_decl_init(
        __isl_take isl_printer *p, __isl_keep pet_tree *tree,
        __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *var, *init;

        p = isl_printer_start_line(p);

        var = pet_tree_decl_get_var(tree);
        p = print_pet_expr(p, var, 1, ref2expr);
        pet_expr_free(var);

        p = isl_printer_print_str(p, " = ");

        init = pet_tree_decl_get_init(tree);
        p = print_pet_expr(p, init, 1, ref2expr);
        pet_expr_free(init);

        p = isl_printer_print_str(p, ";");
        p = isl_printer_end_line(p);

        return p;
}

/* Print "tree" to "p", where "tree" is of type pet_tree_return.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 */
static __isl_give isl_printer *print_pet_tree_return(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *expr;

        expr = pet_tree_expr_get_expr(tree);
        p = isl_printer_start_line(p);
        p = isl_printer_print_str(p, "return ");
        p = print_pet_expr(p, expr, 1, ref2expr);
        p = isl_printer_print_str(p, ";");
        p = isl_printer_end_line(p);
        pet_expr_free(expr);

        return p;
}

/* Print "tree" to "p".
 *
 * If "in_block" is set, then the caller has just printed a block,
 * so there is no need to print one for this node.
 *
 * The access subexpressions are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 *
 * We assume all variables have already been declared,
 * so there is nothing to print for nodes of type pet_tree_decl.
 */
static __isl_give isl_printer *print_pet_tree(__isl_take isl_printer *p,
        __isl_keep pet_tree *tree, int in_block,
        __isl_keep isl_id_to_ast_expr *ref2expr)
{
        pet_expr *expr;
        enum pet_tree_type type;

        type = pet_tree_get_type(tree);
        switch (type) {
        case pet_tree_error:
                return isl_printer_free(p);
        case pet_tree_block:
                return print_pet_tree_block(p, tree, in_block, ref2expr);
        case pet_tree_break:
        case pet_tree_continue:
                p = isl_printer_start_line(p);
                if (type == pet_tree_break)
                        p = isl_printer_print_str(p, "break;");
                else
                        p = isl_printer_print_str(p, "continue;");
                return isl_printer_end_line(p);
        case pet_tree_expr:
                expr = pet_tree_expr_get_expr(tree);
                p = isl_printer_start_line(p);
                p = print_pet_expr(p, expr, 1, ref2expr);
                p = isl_printer_print_str(p, ";");
                p = isl_printer_end_line(p);
                pet_expr_free(expr);
                break;
        case pet_tree_return:
                return print_pet_tree_return(p, tree, ref2expr);
        case pet_tree_if:
        case pet_tree_if_else:
                return print_pet_tree_if(p, tree, ref2expr);
        case pet_tree_for:
                return print_pet_tree_for(p, tree, ref2expr);
        case pet_tree_while:
        case pet_tree_infinite_loop:
                return print_pet_tree_while(p, tree, ref2expr);
        case pet_tree_decl:
                return p;
        case pet_tree_decl_init:
                return print_pet_tree_decl_init(p, tree, ref2expr);
        }

        return p;
}

/* Print "stmt" to "p".
 *
 * The access expressions in "stmt" are replaced by the isl_ast_expr
 * associated to its reference identifier in "ref2expr".
 *
 * If the statement is an assume or a kill statement, then we print nothing.
 */
__isl_give isl_printer *pet_stmt_print_body(struct pet_stmt *stmt,
        __isl_take isl_printer *p, __isl_keep isl_id_to_ast_expr *ref2expr)
{
        if (!stmt)
                return isl_printer_free(p);
        if (pet_stmt_is_assume(stmt))
                return p;
        if (pet_stmt_is_kill(stmt))
                return p;
        p = print_pet_tree(p, stmt->body, 0, ref2expr);

        return p;
}

/* Copy the contents of "input" from offset "start" to "end" to "output".
 */
int copy(FILE *input, FILE *output, long start, long end)
{
        char buffer[1024];
        size_t n, m;

        if (end < 0) {
                fseek(input, 0, SEEK_END);
                end = ftell(input);
        }

        fseek(input, start, SEEK_SET);

        while (start < end) {
                n = end - start;
                if (n > 1024)
                        n = 1024;
                n = fread(buffer, 1, n, input);
                if (n <= 0)
                        return -1;
                m = fwrite(buffer, 1, n, output);
                if (n != m)
                        return -1;
                start += n;
        }

        return 0;
}