pet_check_code.c

   1 /*
   2  * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  *    1. Redistributions of source code must retain the above copyright
   9  *       notice, this list of conditions and the following disclaimer.
  10  *
  11  *    2. Redistributions in binary form must reproduce the above
  12  *       copyright notice, this list of conditions and the following
  13  *       disclaimer in the documentation and/or other materials provided
  14  *       with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY ECOLE NORMALE SUPERIEURE ''AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ECOLE NORMALE SUPERIEURE OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  23  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * The views and conclusions contained in the software and documentation
  29  * are those of the authors and should not be interpreted as
  30  * representing official policies, either expressed or implied, of
  31  * Ecole Normale Superieure.
  32  */
  33
  34 #include <assert.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37 #include <isl/arg.h>
  38 #include <isl/aff.h>
  39 #include <isl/options.h>
  40 #include <isl/set.h>
  41 #include <isl/union_set.h>
  42 #include <isl/union_map.h>
  43 #include <isl/id_to_pw_aff.h>
  44 #include <isl/schedule_node.h>
  45 #include <pet.h>
  46
  47 struct options {
  48         struct isl_options      *isl;
  49         struct pet_options      *pet;
  50         char *schedule;
  51         char *code;
  52         unsigned                 tree;
  53 };
  54
  55 ISL_ARGS_START(struct options, options_args)
  56 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  57 ISL_ARG_CHILD(struct options, pet, NULL, &pet_options_args, "pet options")
  58 ISL_ARG_ARG(struct options, schedule, "schedule", NULL)
  59 ISL_ARG_ARG(struct options, code, "code", NULL)
  60 ISL_ARG_BOOL(struct options, tree, 0, "tree", 0,
  61         "input schedule is specified as schedule tree")
  62 ISL_ARGS_END
  63
  64 ISL_ARG_DEF(options, struct options, options_args)
  65
  66 /* Extract an affine expression from "expr" in the form of an isl_map.
  67  *
  68  * The domain of the created expression is that of "pc".
  69  */
  70 static __isl_give isl_map *expr_extract_map(__isl_keep pet_expr *expr,
  71         __isl_keep pet_context *pc)
  72 {
  73         isl_pw_aff *pa;
  74
  75         pa = pet_expr_extract_affine(expr, pc);
  76         return isl_map_from_pw_aff(pa);
  77 }
  78
  79 /* Extract a call from "stmt".
  80  *
  81  * The returned map is of the form
  82  *
  83  *      { domain -> function[arguments] }
  84  */
  85 static __isl_give isl_map *stmt_extract_call(struct pet_stmt *stmt)
  86 {
  87         int i, n;
  88         isl_set *domain;
  89         isl_map *call;
  90         const char *name;
  91         pet_context *pc;
  92         pet_expr *expr;
  93
  94         expr = pet_tree_expr_get_expr(stmt->body);
  95         if (!expr)
  96                 return NULL;
  97         if (pet_expr_get_type(expr) != pet_expr_call)
  98                 isl_die(pet_expr_get_ctx(expr),
  99                         isl_error_invalid, "expecting call statement",
 100                         goto error);
 101
 102         domain = isl_set_copy(stmt->domain);
 103         call = isl_map_from_domain(domain);
 104
 105         pc = pet_context_alloc(isl_set_copy(stmt->domain));
 106         n = pet_expr_get_n_arg(expr);
 107         for (i = 0; i < n; ++i) {
 108                 isl_map *map_i;
 109                 pet_expr *arg;
 110
 111                 arg = pet_expr_get_arg(expr, i);
 112                 map_i = expr_extract_map(arg, pc);
 113                 pet_expr_free(arg);
 114                 call = isl_map_flat_range_product(call, map_i);
 115         }
 116         pet_context_free(pc);
 117
 118         name = pet_expr_call_get_name(expr);
 119         call = isl_map_set_tuple_name(call, isl_dim_out, name);
 120
 121         pet_expr_free(expr);
 122         return call;
 123 error:
 124         pet_expr_free(expr);
 125         return NULL;
 126 }
 127
 128 /* Extract a mapping from the iterations domains of "scop" to
 129  * the calls in the corresponding statements.
 130  *
 131  * We skip assignment and kill statements.
 132  * Other than assignments and kill statements, all statements are assumed
 133  * to be function calls.
 134  */
 135 static __isl_give isl_union_map *scop_collect_calls(struct pet_scop *scop)
 136 {
 137         int i;
 138         isl_ctx *ctx;
 139         isl_map *call_i;
 140         isl_union_map *call;
 141
 142         if (!scop)
 143                 return NULL;
 144
 145         call = isl_union_map_empty(isl_set_get_space(scop->context));
 146         ctx = isl_set_get_ctx(scop->context);
 147
 148         for (i = 0; i < scop->n_stmt; ++i) {
 149                 struct pet_stmt *stmt;
 150
 151                 stmt = scop->stmts[i];
 152                 if (pet_stmt_is_assign(stmt))
 153                         continue;
 154                 if (pet_stmt_is_kill(stmt))
 155                         continue;
 156                 call_i = stmt_extract_call(scop->stmts[i]);
 157                 call = isl_union_map_add_map(call, call_i);
 158         }
 159
 160         return call;
 161 }
 162
 163 /* Extract a schedule on the original domains from "scop".
 164  * The original domain elements appear as calls in "scop".
 165  *
 166  * We first extract a schedule on the code iteration domains
 167  * and a mapping from the code iteration domains to the calls
 168  * (i.e., the original domain) and then combine the two.
 169  */
 170 static __isl_give isl_union_map *extract_code_schedule(struct pet_scop *scop)
 171 {
 172         isl_union_map *schedule;
 173         isl_union_map *calls;
 174
 175         schedule = isl_schedule_get_map(scop->schedule);
 176
 177         calls = scop_collect_calls(scop);
 178
 179         schedule = isl_union_map_apply_domain(schedule, calls);
 180
 181         return schedule;
 182 }
 183
 184 /* Check that schedule and code_schedule have the same domain,
 185  * i.e., that they execute the same statement instances.
 186  */
 187 static int check_domain(__isl_keep isl_union_map *schedule,
 188         __isl_keep isl_union_map *code_schedule)
 189 {
 190         isl_union_set *dom1, *dom2;
 191         int equal;
 192         isl_set *s1, *s2;
 193         isl_id *id1, *id2;
 194         int r = 0;
 195
 196         dom1 = isl_union_map_domain(isl_union_map_copy(schedule));
 197         dom2 = isl_union_map_domain(isl_union_map_copy(code_schedule));
 198         equal = isl_union_set_is_equal(dom1, dom2);
 199
 200         if (equal < 0)
 201                 r =  -1;
 202         else if (!equal) {
 203                 isl_union_set_dump(dom1);
 204                 isl_union_set_dump(dom2);
 205                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 206                         "domains not identical", r = -1);
 207         }
 208
 209         isl_union_set_free(dom1);
 210         isl_union_set_free(dom2);
 211
 212         return r;
 213 }
 214
 215 /* Check that the relative order specified by the input schedule is respected
 216  * by the schedule extracted from the code, in case the original schedule
 217  * is single valued.
 218  *
 219  * In particular, check that there is no pair of statement instances
 220  * such that the first should be scheduled _before_ the second,
 221  * but is actually scheduled _after_ the second in the code.
 222  */
 223 static int check_order_sv(__isl_keep isl_union_map *schedule,
 224         __isl_keep isl_union_map *code_schedule)
 225 {
 226         isl_union_map *t1;
 227         isl_union_map *t2;
 228         int empty;
 229
 230         t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
 231                                             isl_union_map_copy(schedule));
 232         t2 = isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule),
 233                                             isl_union_map_copy(code_schedule));
 234         t1 = isl_union_map_intersect(t1, t2);
 235         empty = isl_union_map_is_empty(t1);
 236         isl_union_map_free(t1);
 237
 238         if (empty < 0)
 239                 return -1;
 240         if (!empty)
 241                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 242                         "order not respected", return -1);
 243
 244         return 0;
 245 }
 246
 247 /* Check that the relative order specified by the input schedule is respected
 248  * by the schedule extracted from the code, in case the original schedule
 249  * is not single valued.
 250  *
 251  * In particular, check that the order imposed by the schedules on pairs
 252  * of statement instances is the same.
 253  */
 254 static int check_order_not_sv(__isl_keep isl_union_map *schedule,
 255         __isl_keep isl_union_map *code_schedule)
 256 {
 257         isl_union_map *t1;
 258         isl_union_map *t2;
 259         int equal;
 260
 261         t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
 262                                             isl_union_map_copy(schedule));
 263         t2 = isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule),
 264                                             isl_union_map_copy(code_schedule));
 265         equal = isl_union_map_is_equal(t1, t2);
 266         isl_union_map_free(t1);
 267         isl_union_map_free(t2);
 268
 269         if (equal < 0)
 270                 return -1;
 271         if (!equal)
 272                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 273                         "order not respected", return -1);
 274
 275         return 0;
 276 }
 277
 278 /* Check that the relative order specified by the input schedule is respected
 279  * by the schedule extracted from the code.
 280  *
 281  * "sv" indicated whether the original schedule is single valued.
 282  * If so, we use a cheaper test.  Otherwise, we fall back on a more
 283  * expensive test.
 284  */
 285 static int check_order(__isl_keep isl_union_map *schedule,
 286         __isl_keep isl_union_map *code_schedule, int sv)
 287 {
 288         if (sv)
 289                 return check_order_sv(schedule, code_schedule);
 290         else
 291                 return check_order_not_sv(schedule, code_schedule);
 292 }
 293
 294 /* If the original schedule was single valued ("sv" is set),
 295  * then the schedule extracted from the code should be single valued as well.
 296  */
 297 static int check_single_valued(__isl_keep isl_union_map *code_schedule, int sv)
 298 {
 299         if (!sv)
 300                 return 0;
 301
 302         sv = isl_union_map_is_single_valued(code_schedule);
 303         if (sv < 0)
 304                 return -1;
 305
 306         if (!sv)
 307                 isl_die(isl_union_map_get_ctx(code_schedule), isl_error_unknown,
 308                         "schedule not single valued", return -1);
 309
 310         return 0;
 311 }
 312
 313 /* Read a schedule and a context from the first argument and
 314  * C code from the second argument and check that the C code
 315  * corresponds to the schedule on the context.
 316  *
 317  * In particular, check that
 318  * - the domains are identical, i.e., the calls in the C code
 319  *   correspond to the domain elements of the schedule
 320  * - no function is called twice with the same arguments, provided
 321  *   the schedule is single-valued
 322  * - the calls are performed in an order that is compatible
 323  *   with the schedule
 324  *
 325  * If the schedule is not single-valued then we would have to check
 326  * that each function with a given set of arguments is called
 327  * the same number of times as there are images in the schedule,
 328  * but this is considerably more difficult.
 329  */
 330 int main(int argc, char **argv)
 331 {
 332         isl_ctx *ctx;
 333         isl_set *context;
 334         isl_union_map *input_schedule, *code_schedule;
 335         struct pet_scop *scop;
 336         struct options *options;
 337         FILE *file;
 338         int r;
 339         int sv;
 340
 341         options = options_new_with_defaults();
 342         assert(options);
 343         ctx = isl_ctx_alloc_with_options(&options_args, options);
 344         pet_options_set_signed_overflow(ctx, PET_OVERFLOW_IGNORE);
 345         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 346
 347         file = fopen(options->schedule, "r");
 348         assert(file);
 349         if (options->tree) {
 350                 isl_schedule *schedule;
 351                 isl_schedule_node *node;
 352                 enum isl_schedule_node_type type;
 353
 354                 schedule = isl_schedule_read_from_file(ctx, file);
 355                 node = isl_schedule_get_root(schedule);
 356                 isl_options_set_schedule_separate_components(ctx, 0);
 357                 input_schedule =
 358                         isl_schedule_node_get_subtree_schedule_union_map(node);
 359                 node = isl_schedule_node_child(node, 0);
 360                 type = isl_schedule_node_get_type(node);
 361                 if (type == isl_schedule_node_context) {
 362                         context = isl_schedule_node_context_get_context(node);
 363                 } else {
 364                         isl_space *space;
 365                         space = isl_union_map_get_space(input_schedule);
 366                         context = isl_set_universe(space);
 367                 }
 368                 isl_schedule_node_free(node);
 369                 isl_schedule_free(schedule);
 370         } else {
 371                 input_schedule = isl_union_map_read_from_file(ctx, file);
 372                 context = isl_set_read_from_file(ctx, file);
 373         }
 374         fclose(file);
 375
 376         scop = pet_scop_extract_from_C_source(ctx, options->code, NULL);
 377
 378         input_schedule = isl_union_map_intersect_params(input_schedule,
 379                                                 isl_set_copy(context));
 380         code_schedule = extract_code_schedule(scop);
 381         code_schedule = isl_union_map_intersect_params(code_schedule, context);
 382
 383         sv = isl_union_map_is_single_valued(input_schedule);
 384         r = sv < 0 ||
 385             check_domain(input_schedule, code_schedule) ||
 386             check_single_valued(code_schedule, sv) ||
 387             check_order(input_schedule, code_schedule, sv);
 388
 389         pet_scop_free(scop);
 390         isl_union_map_free(input_schedule);
 391         isl_union_map_free(code_schedule);
 392         isl_ctx_free(ctx);
 393
 394         return r;
 395 }