add functions for manipulating the domain of a pet_context

[pet.git] / pet_check_code.c

/*
 * 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 ECOLE NORMALE SUPERIEURE ''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 ECOLE NORMALE SUPERIEURE 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
 * Ecole Normale Superieure.
 */

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <isl/arg.h>
#include <isl/aff.h>
#include <isl/options.h>
#include <isl/set.h>
#include <isl/union_map.h>
#include <isl/id_to_pw_aff.h>
#include <pet.h>

#include "aff.h"

struct options {
        struct isl_options      *isl;
        struct pet_options      *pet;
        char *schedule;
        char *code;
};

ISL_ARGS_START(struct options, options_args)
ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
ISL_ARG_CHILD(struct options, pet, NULL, &pet_options_args, "pet options")
ISL_ARG_ARG(struct options, schedule, "schedule", NULL)
ISL_ARG_ARG(struct options, code, "code", NULL)
ISL_ARGS_END

ISL_ARG_DEF(options, struct options, options_args)

static __isl_give isl_pw_aff *expr_extract_pw_aff(__isl_keep pet_expr *expr,
        __isl_keep isl_space *space);

/* Extract an affine expression from the call to floord in "expr".
 *
 * "space" is the iteration space of the statement containing the expression.
 */
static __isl_give isl_pw_aff *expr_extract_floord(__isl_keep pet_expr *expr,
        __isl_keep isl_space *space)
{
        isl_pw_aff *lhs, *rhs;
        pet_expr *arg;

        arg = pet_expr_get_arg(expr, 0);
        lhs = expr_extract_pw_aff(arg, space);
        pet_expr_free(arg);
        arg = pet_expr_get_arg(expr, 1);
        rhs = expr_extract_pw_aff(arg, space);
        pet_expr_free(arg);
        return isl_pw_aff_floor(isl_pw_aff_div(lhs, rhs));
}

/* Extract an affine expression from the call in "expr".
 *
 * "space" is the iteration space of the statement containing the expression.
 *
 * We only support calls to the "floord" function for now.
 */
static __isl_give isl_pw_aff *call_expr_extract_pw_aff(
        __isl_keep pet_expr *expr, __isl_keep isl_space *space)
{
        const char *name;

        name = pet_expr_call_get_name(expr);
        if (!name)
                return NULL;
        if (!strcmp(name, "floord"))
                return expr_extract_floord(expr, space);

        isl_die(isl_space_get_ctx(space), isl_error_unsupported,
                "unsupported expression", return NULL);
}

/* Extract an affine expression from the access to a named space in "index".
 *
 * We assume we are accessing a 0D space and
 * we turn that into an expression equal to a parameter of the same name.
 */
static __isl_give isl_pw_aff *resolve_access(__isl_take isl_multi_pw_aff *index)
{
        isl_id *id;
        isl_set *dom;
        isl_aff *aff;
        isl_local_space *ls;
        isl_pw_aff *pa;

        id = isl_multi_pw_aff_get_tuple_id(index, isl_dim_out);
        dom = isl_multi_pw_aff_domain(index);
        dom = isl_set_insert_dims(dom, isl_dim_param, 0, 1);
        dom = isl_set_set_dim_id(dom, isl_dim_param, 0, id);
        ls = isl_local_space_from_space(isl_set_get_space(dom));
        aff = isl_aff_var_on_domain(ls, isl_dim_param, 0);
        pa = isl_pw_aff_alloc(dom, aff);

        return pa;
}

/* Extract an affine expression from the access expression "expr".
 *
 * If we are accessing a (1D) anonymous space, then we are actually
 * computing an affine expression and we simply return that expression.
 * Otherwise, we try and convert the access to an affine expression in
 * resolve_access().
 */
static __isl_give isl_pw_aff *access_expr_extract_pw_aff(
        __isl_keep pet_expr *expr)
{
        isl_pw_aff *pa;
        isl_multi_pw_aff *index;

        index = pet_expr_access_get_index(expr);
        if (isl_multi_pw_aff_has_tuple_id(index, isl_dim_out)) {
                pa = resolve_access(index);
        } else {
                pa = isl_multi_pw_aff_get_pw_aff(index, 0);
                isl_multi_pw_aff_free(index);
        }
        return pa;
}

/* Extract an affine expression defined over iteration space "space"
 * from the integer expression "expr".
 */
static __isl_give isl_pw_aff *int_expr_extract_pw_aff(
        __isl_keep  pet_expr *expr, __isl_keep isl_space *space)
{
        isl_local_space *ls;
        isl_aff *aff;

        ls = isl_local_space_from_space(isl_space_copy(space));
        aff = isl_aff_zero_on_domain(ls);
        aff = isl_aff_add_constant_val(aff, pet_expr_int_get_val(expr));
        return isl_pw_aff_from_aff(aff);
}

/* Extract an affine expression from the operation in "expr".
 *
 * "space" is the iteration space of the statement containing the expression.
 *
 * We only handle the kinds of expressions that we would expect
 * as arguments to a function call in code generated by isl.
 */
static __isl_give isl_pw_aff *op_expr_extract_pw_aff(__isl_keep pet_expr *expr,
        __isl_keep isl_space *space)
{
        isl_pw_aff *pa, *pa1, *pa2;
        pet_expr *arg;
        enum pet_op_type type;

        switch (pet_expr_get_n_arg(expr)) {
        case 1:
                if (pet_expr_op_get_type(expr) == pet_op_minus) {
                        arg = pet_expr_get_arg(expr, 0);
                        pa = expr_extract_pw_aff(arg, space);
                        pet_expr_free(arg);
                        return isl_pw_aff_neg(pa);
                }
                assert(0);
        case 2:
                arg = pet_expr_get_arg(expr, 0);
                pa1 = expr_extract_pw_aff(arg, space);
                pet_expr_free(arg);
                arg = pet_expr_get_arg(expr, 1);
                pa2 = expr_extract_pw_aff(arg, space);
                pet_expr_free(arg);
                type = pet_expr_op_get_type(expr);
                switch (type) {
                case pet_op_mul:
                        pa = isl_pw_aff_mul(pa1, pa2);
                        break;
                case pet_op_add:
                        pa = isl_pw_aff_add(pa1, pa2);
                        break;
                case pet_op_sub:
                        pa = isl_pw_aff_sub(pa1, pa2);
                        break;
                case pet_op_div:
                        pa = isl_pw_aff_tdiv_q(pa1, pa2);
                        break;
                case pet_op_mod:
                        pa = isl_pw_aff_tdiv_r(pa1, pa2);
                        break;
                case pet_op_eq:
                case pet_op_ne:
                case pet_op_le:
                case pet_op_ge:
                case pet_op_lt:
                case pet_op_gt:
                        pa = pet_comparison(type, pa1, pa2);
                        break;
                case pet_op_land:
                case pet_op_lor:
                        pa = pet_boolean(type, pa1, pa2);
                        break;
                default:
                        assert(0);
                }
                return pa;
        case 3:
                arg = pet_expr_get_arg(expr, 0);
                pa = expr_extract_pw_aff(arg, space);
                pet_expr_free(arg);
                arg = pet_expr_get_arg(expr, 1);
                pa1 = expr_extract_pw_aff(arg, space);
                pet_expr_free(arg);
                arg = pet_expr_get_arg(expr, 2);
                pa2 = expr_extract_pw_aff(arg, space);
                pet_expr_free(arg);
                return isl_pw_aff_cond(pa, pa1, pa2);
        default:
                assert(0);
        }
}

/* Extract an affine expression from "expr" in the form of an isl_pw_aff.
 *
 * "space" is the iteration space of the statement containing the expression.
 *
 * We only handle the kinds of expressions that we would expect
 * as arguments to a function call in code generated by isl.
 */
static __isl_give isl_pw_aff *expr_extract_pw_aff(__isl_keep pet_expr *expr,
        __isl_keep isl_space *space)
{
        switch (pet_expr_get_type(expr)) {
        case pet_expr_int:
                return int_expr_extract_pw_aff(expr, space);
        case pet_expr_access:
                return access_expr_extract_pw_aff(expr);
        case pet_expr_op:
                return op_expr_extract_pw_aff(expr, space);
        case pet_expr_call:
                return call_expr_extract_pw_aff(expr, space);
        case pet_expr_cast:
        case pet_expr_double:
        case pet_expr_error:
                assert(0);
        }
}

/* Extract an affine expression from "expr" in the form of an isl_map.
 *
 * "space" is the iteration space of the statement containing the expression.
 */
static __isl_give isl_map *expr_extract_map(__isl_keep pet_expr *expr,
        __isl_keep isl_space *space)
{
        isl_pw_aff *pa;

        pa = expr_extract_pw_aff(expr, space);
        return isl_map_from_pw_aff(pa);
}

/* Extract a call from "stmt".
 *
 * The returned map is of the form
 *
 *      { domain -> function[arguments] }
 */
static __isl_give isl_map *stmt_extract_call(struct pet_stmt *stmt)
{
        int i, n;
        isl_set *domain;
        isl_map *call;
        const char *name;

        domain = isl_set_copy(stmt->domain);
        call = isl_map_from_domain(domain);

        assert(pet_expr_get_type(stmt->body) == pet_expr_call);

        n = pet_expr_get_n_arg(stmt->body);
        for (i = 0; i < n; ++i) {
                isl_map *map_i;
                isl_space *space;
                pet_expr *arg;

                arg = pet_expr_get_arg(stmt->body, i);
                space = pet_stmt_get_space(stmt);
                map_i = expr_extract_map(arg, space);
                isl_space_free(space);
                pet_expr_free(arg);
                call = isl_map_flat_range_product(call, map_i);
        }

        name = pet_expr_call_get_name(stmt->body);
        call = isl_map_set_tuple_name(call, isl_dim_out, name);

        return call;
}

/* Extract a mapping from the iterations domains of "scop" to
 * the calls in the corresponding statements.
 *
 * We skip assignment and kill statements.
 * Other than assignments and kill statements, all statements are assumed
 * to be function calls.
 */
static __isl_give isl_union_map *scop_collect_calls(struct pet_scop *scop)
{
        int i;
        isl_ctx *ctx;
        isl_map *call_i;
        isl_union_map *call;

        if (!scop)
                return NULL;

        call = isl_union_map_empty(isl_set_get_space(scop->context));
        ctx = isl_set_get_ctx(scop->context);

        for (i = 0; i < scop->n_stmt; ++i) {
                struct pet_stmt *stmt;

                stmt = scop->stmts[i];
                if (pet_stmt_is_assign(stmt))
                        continue;
                if (pet_stmt_is_kill(stmt))
                        continue;
                call_i = stmt_extract_call(scop->stmts[i]);
                call = isl_union_map_add_map(call, call_i);
        }

        return call;
}

/* Extract a schedule on the original domains from "scop".
 * The original domain elements appear as calls in "scop".
 *
 * We first extract a schedule on the code iteration domains
 * and a mapping from the code iteration domains to the calls
 * (i.e., the original domain) and then combine the two.
 */
static __isl_give isl_union_map *extract_code_schedule(struct pet_scop *scop)
{
        isl_union_map *schedule;
        isl_union_map *calls;

        schedule = pet_scop_collect_schedule(scop);

        calls = scop_collect_calls(scop);

        schedule = isl_union_map_apply_domain(schedule, calls);

        return schedule;
}

/* Check that schedule and code_schedule have the same domain,
 * i.e., that they execute the same statement instances.
 */
static int check_domain(__isl_keep isl_union_map *schedule,
        __isl_keep isl_union_map *code_schedule)
{
        isl_union_set *dom1, *dom2;
        int equal;
        isl_set *s1, *s2;;
        isl_id *id1, *id2;
        int r = 0;

        dom1 = isl_union_map_domain(isl_union_map_copy(schedule));
        dom2 = isl_union_map_domain(isl_union_map_copy(code_schedule));
        equal = isl_union_set_is_equal(dom1, dom2);

        if (equal < 0)
                r =  -1;
        else if (!equal) {
                isl_union_set_dump(dom1);
                isl_union_set_dump(dom2);
                isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
                        "domains not identical", r = -1);
        }

        isl_union_set_free(dom1);
        isl_union_set_free(dom2);

        return r;
}

/* Check that the relative order specified by the input schedule is respected
 * by the schedule extracted from the code, in case the original schedule
 * is single valued.
 *
 * In particular, check that there is no pair of statement instances
 * such that the first should be scheduled _before_ the second,
 * but is actually scheduled _after_ the second in the code.
 */
static int check_order_sv(__isl_keep isl_union_map *schedule,
        __isl_keep isl_union_map *code_schedule)
{
        isl_union_map *t1;
        isl_union_map *t2;
        int empty;

        t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
                                            isl_union_map_copy(schedule));
        t2 = isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule),
                                            isl_union_map_copy(code_schedule));
        t1 = isl_union_map_intersect(t1, t2);
        empty = isl_union_map_is_empty(t1);
        isl_union_map_free(t1);

        if (empty < 0)
                return -1;
        if (!empty)
                isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
                        "order not respected", return -1);

        return 0;
}

/* Check that the relative order specified by the input schedule is respected
 * by the schedule extracted from the code, in case the original schedule
 * is not single valued.
 *
 * In particular, check that the order imposed by the schedules on pairs
 * of statement instances is the same.
 */
static int check_order_not_sv(__isl_keep isl_union_map *schedule,
        __isl_keep isl_union_map *code_schedule)
{
        isl_union_map *t1;
        isl_union_map *t2;
        int equal;

        t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
                                            isl_union_map_copy(schedule));
        t2 = isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule),
                                            isl_union_map_copy(code_schedule));
        equal = isl_union_map_is_equal(t1, t2);
        isl_union_map_free(t1);
        isl_union_map_free(t2);

        if (equal < 0)
                return -1;
        if (!equal)
                isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
                        "order not respected", return -1);

        return 0;
}

/* Check that the relative order specified by the input schedule is respected
 * by the schedule extracted from the code.
 *
 * "sv" indicated whether the original schedule is single valued.
 * If so, we use a cheaper test.  Otherwise, we fall back on a more
 * expensive test.
 */
static int check_order(__isl_keep isl_union_map *schedule,
        __isl_keep isl_union_map *code_schedule, int sv)
{
        if (sv)
                return check_order_sv(schedule, code_schedule);
        else
                return check_order_not_sv(schedule, code_schedule);
}

/* If the original schedule was single valued ("sv" is set),
 * then the schedule extracted from the code should be single valued as well.
 */
static int check_single_valued(__isl_keep isl_union_map *code_schedule, int sv)
{
        if (!sv)
                return 0;

        sv = isl_union_map_is_single_valued(code_schedule);
        if (sv < 0)
                return -1;

        if (!sv)
                isl_die(isl_union_map_get_ctx(code_schedule), isl_error_unknown,
                        "schedule not single valued", return -1);

        return 0;
}

/* Read a schedule and a context from the first argument and
 * C code from the second argument and check that the C code
 * corresponds to the schedule on the context.
 *
 * In particular, check that
 * - the domains are identical, i.e., the calls in the C code
 *   correspond to the domain elements of the schedule
 * - no function is called twice with the same arguments, provided
 *   the schedule is single-valued
 * - the calls are performed in an order that is compatible
 *   with the schedule
 *
 * If the schedule is not single-valued then we would have to check
 * that each function with a given set of arguments is called
 * the same number of times as there are images in the schedule,
 * but this is considerably more difficult.
 */
int main(int argc, char **argv)
{
        isl_ctx *ctx;
        isl_set *context;
        isl_union_map *schedule, *code_schedule;
        struct pet_scop *scop;
        struct options *options;
        FILE *file;
        int r;
        int sv;

        options = options_new_with_defaults();
        assert(options);
        ctx = isl_ctx_alloc_with_options(&options_args, options);
        pet_options_set_signed_overflow(ctx, PET_OVERFLOW_IGNORE);
        argc = options_parse(options, argc, argv, ISL_ARG_ALL);

        file = fopen(options->schedule, "r");
        assert(file);
        schedule = isl_union_map_read_from_file(ctx, file);
        context = isl_set_read_from_file(ctx, file);
        fclose(file);

        scop = pet_scop_extract_from_C_source(ctx, options->code, NULL);

        schedule = isl_union_map_intersect_params(schedule,
                                                isl_set_copy(context));
        code_schedule = extract_code_schedule(scop);
        code_schedule = isl_union_map_intersect_params(code_schedule, context);

        sv = isl_union_map_is_single_valued(schedule);
        r = sv < 0 ||
            check_domain(schedule, code_schedule) ||
            check_single_valued(code_schedule, sv) ||
            check_order(schedule, code_schedule, sv);

        pet_scop_free(scop);
        isl_union_map_free(schedule);
        isl_union_map_free(code_schedule);
        isl_ctx_free(ctx);

        return r;
}