privately export pet_stmt_is_affine_assume

[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_set.h>
#include <isl/union_map.h>
#include <isl/id_to_pw_aff.h>
#include <isl/schedule_node.h>
#include <pet.h>

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

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_ARG_BOOL(struct options, tree, 0, "tree", 0,
        "input schedule is specified as schedule tree")
ISL_ARGS_END

ISL_ARG_DEF(options, struct options, options_args)

/* Extract an affine expression from "expr" in the form of an isl_map.
 *
 * The domain of the created expression is that of "pc".
 */
static __isl_give isl_map *expr_extract_map(__isl_keep pet_expr *expr,
        __isl_keep pet_context *pc)
{
        isl_pw_aff *pa;

        pa = pet_expr_extract_affine(expr, pc);
        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;
        pet_context *pc;
        pet_expr *expr;

        expr = pet_tree_expr_get_expr(stmt->body);
        if (!expr)
                return NULL;
        if (pet_expr_get_type(expr) != pet_expr_call)
                isl_die(pet_expr_get_ctx(expr),
                        isl_error_invalid, "expecting call statement",
                        goto error);

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

        pc = pet_context_alloc(isl_set_copy(stmt->domain));
        n = pet_expr_get_n_arg(expr);
        for (i = 0; i < n; ++i) {
                isl_map *map_i;
                pet_expr *arg;

                arg = pet_expr_get_arg(expr, i);
                map_i = expr_extract_map(arg, pc);
                pet_expr_free(arg);
                call = isl_map_flat_range_product(call, map_i);
        }
        pet_context_free(pc);

        name = pet_expr_call_get_name(expr);
        call = isl_map_set_tuple_name(call, isl_dim_out, name);

        pet_expr_free(expr);
        return call;
error:
        pet_expr_free(expr);
        return NULL;
}

/* 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_schedule *schedule;
        isl_union_map *schedule_map;
        isl_union_map *calls;

        schedule = pet_scop_get_schedule(scop);
        schedule_map = isl_schedule_get_map(schedule);
        isl_schedule_free(schedule);

        calls = scop_collect_calls(scop);

        schedule_map = isl_union_map_apply_domain(schedule_map, calls);

        return schedule_map;
}

/* 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 *input_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);
        if (options->tree) {
                isl_schedule *schedule;
                isl_schedule_node *node;
                enum isl_schedule_node_type type;

                schedule = isl_schedule_read_from_file(ctx, file);
                node = isl_schedule_get_root(schedule);
                isl_options_set_schedule_separate_components(ctx, 0);
                input_schedule =
                        isl_schedule_node_get_subtree_schedule_union_map(node);
                node = isl_schedule_node_child(node, 0);
                type = isl_schedule_node_get_type(node);
                if (type == isl_schedule_node_context) {
                        context = isl_schedule_node_context_get_context(node);
                } else {
                        isl_space *space;
                        space = isl_union_map_get_space(input_schedule);
                        context = isl_set_universe(space);
                }
                isl_schedule_node_free(node);
                isl_schedule_free(schedule);
        } else {
                input_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);

        input_schedule = isl_union_map_intersect_params(input_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(input_schedule);
        r = sv < 0 ||
            check_domain(input_schedule, code_schedule) ||
            check_single_valued(code_schedule, sv) ||
            check_order(input_schedule, code_schedule, sv);

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

        return r;
}