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_map.h>
  42 #include <isl/id_to_pw_aff.h>
  43 #include <pet.h>
  44
  45 struct options {
  46         struct isl_options      *isl;
  47         struct pet_options      *pet;
  48         char *schedule;
  49         char *code;
  50 };
  51
  52 ISL_ARGS_START(struct options, options_args)
  53 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  54 ISL_ARG_CHILD(struct options, pet, NULL, &pet_options_args, "pet options")
  55 ISL_ARG_ARG(struct options, schedule, "schedule", NULL)
  56 ISL_ARG_ARG(struct options, code, "code", NULL)
  57 ISL_ARGS_END
  58
  59 ISL_ARG_DEF(options, struct options, options_args)
  60
  61 /* Extract an affine expression from "expr" in the form of an isl_map.
  62  *
  63  * The domain of the created expression is that of "pc".
  64  */
  65 static __isl_give isl_map *expr_extract_map(__isl_keep pet_expr *expr,
  66         __isl_keep pet_context *pc)
  67 {
  68         isl_pw_aff *pa;
  69
  70         pa = pet_expr_extract_affine(expr, pc);
  71         return isl_map_from_pw_aff(pa);
  72 }
  73
  74 /* Extract a call from "stmt".
  75  *
  76  * The returned map is of the form
  77  *
  78  *      { domain -> function[arguments] }
  79  */
  80 static __isl_give isl_map *stmt_extract_call(struct pet_stmt *stmt)
  81 {
  82         int i, n;
  83         isl_set *domain;
  84         isl_map *call;
  85         const char *name;
  86         pet_context *pc;
  87         pet_expr *expr;
  88
  89         expr = pet_tree_expr_get_expr(stmt->body);
  90         if (!expr)
  91                 return NULL;
  92         if (pet_expr_get_type(expr) != pet_expr_call)
  93                 isl_die(pet_expr_get_ctx(expr),
  94                         isl_error_invalid, "expecting call statement",
  95                         goto error);
  96
  97         domain = isl_set_copy(stmt->domain);
  98         call = isl_map_from_domain(domain);
  99
 100         pc = pet_context_alloc(isl_set_copy(stmt->domain));
 101         n = pet_expr_get_n_arg(expr);
 102         for (i = 0; i < n; ++i) {
 103                 isl_map *map_i;
 104                 pet_expr *arg;
 105
 106                 arg = pet_expr_get_arg(expr, i);
 107                 map_i = expr_extract_map(arg, pc);
 108                 pet_expr_free(arg);
 109                 call = isl_map_flat_range_product(call, map_i);
 110         }
 111         pet_context_free(pc);
 112
 113         name = pet_expr_call_get_name(expr);
 114         call = isl_map_set_tuple_name(call, isl_dim_out, name);
 115
 116         pet_expr_free(expr);
 117         return call;
 118 error:
 119         pet_expr_free(expr);
 120         return NULL;
 121 }
 122
 123 /* Extract a mapping from the iterations domains of "scop" to
 124  * the calls in the corresponding statements.
 125  *
 126  * We skip assignment and kill statements.
 127  * Other than assignments and kill statements, all statements are assumed
 128  * to be function calls.
 129  */
 130 static __isl_give isl_union_map *scop_collect_calls(struct pet_scop *scop)
 131 {
 132         int i;
 133         isl_ctx *ctx;
 134         isl_map *call_i;
 135         isl_union_map *call;
 136
 137         if (!scop)
 138                 return NULL;
 139
 140         call = isl_union_map_empty(isl_set_get_space(scop->context));
 141         ctx = isl_set_get_ctx(scop->context);
 142
 143         for (i = 0; i < scop->n_stmt; ++i) {
 144                 struct pet_stmt *stmt;
 145
 146                 stmt = scop->stmts[i];
 147                 if (pet_stmt_is_assign(stmt))
 148                         continue;
 149                 if (pet_stmt_is_kill(stmt))
 150                         continue;
 151                 call_i = stmt_extract_call(scop->stmts[i]);
 152                 call = isl_union_map_add_map(call, call_i);
 153         }
 154
 155         return call;
 156 }
 157
 158 /* Extract a schedule on the original domains from "scop".
 159  * The original domain elements appear as calls in "scop".
 160  *
 161  * We first extract a schedule on the code iteration domains
 162  * and a mapping from the code iteration domains to the calls
 163  * (i.e., the original domain) and then combine the two.
 164  */
 165 static __isl_give isl_union_map *extract_code_schedule(struct pet_scop *scop)
 166 {
 167         isl_union_map *schedule;
 168         isl_union_map *calls;
 169
 170         schedule = pet_scop_collect_schedule(scop);
 171
 172         calls = scop_collect_calls(scop);
 173
 174         schedule = isl_union_map_apply_domain(schedule, calls);
 175
 176         return schedule;
 177 }
 178
 179 /* Check that schedule and code_schedule have the same domain,
 180  * i.e., that they execute the same statement instances.
 181  */
 182 static int check_domain(__isl_keep isl_union_map *schedule,
 183         __isl_keep isl_union_map *code_schedule)
 184 {
 185         isl_union_set *dom1, *dom2;
 186         int equal;
 187         isl_set *s1, *s2;;
 188         isl_id *id1, *id2;
 189         int r = 0;
 190
 191         dom1 = isl_union_map_domain(isl_union_map_copy(schedule));
 192         dom2 = isl_union_map_domain(isl_union_map_copy(code_schedule));
 193         equal = isl_union_set_is_equal(dom1, dom2);
 194
 195         if (equal < 0)
 196                 r =  -1;
 197         else if (!equal) {
 198                 isl_union_set_dump(dom1);
 199                 isl_union_set_dump(dom2);
 200                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 201                         "domains not identical", r = -1);
 202         }
 203
 204         isl_union_set_free(dom1);
 205         isl_union_set_free(dom2);
 206
 207         return r;
 208 }
 209
 210 /* Check that the relative order specified by the input schedule is respected
 211  * by the schedule extracted from the code, in case the original schedule
 212  * is single valued.
 213  *
 214  * In particular, check that there is no pair of statement instances
 215  * such that the first should be scheduled _before_ the second,
 216  * but is actually scheduled _after_ the second in the code.
 217  */
 218 static int check_order_sv(__isl_keep isl_union_map *schedule,
 219         __isl_keep isl_union_map *code_schedule)
 220 {
 221         isl_union_map *t1;
 222         isl_union_map *t2;
 223         int empty;
 224
 225         t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
 226                                             isl_union_map_copy(schedule));
 227         t2 = isl_union_map_lex_gt_union_map(isl_union_map_copy(code_schedule),
 228                                             isl_union_map_copy(code_schedule));
 229         t1 = isl_union_map_intersect(t1, t2);
 230         empty = isl_union_map_is_empty(t1);
 231         isl_union_map_free(t1);
 232
 233         if (empty < 0)
 234                 return -1;
 235         if (!empty)
 236                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 237                         "order not respected", return -1);
 238
 239         return 0;
 240 }
 241
 242 /* Check that the relative order specified by the input schedule is respected
 243  * by the schedule extracted from the code, in case the original schedule
 244  * is not single valued.
 245  *
 246  * In particular, check that the order imposed by the schedules on pairs
 247  * of statement instances is the same.
 248  */
 249 static int check_order_not_sv(__isl_keep isl_union_map *schedule,
 250         __isl_keep isl_union_map *code_schedule)
 251 {
 252         isl_union_map *t1;
 253         isl_union_map *t2;
 254         int equal;
 255
 256         t1 = isl_union_map_lex_lt_union_map(isl_union_map_copy(schedule),
 257                                             isl_union_map_copy(schedule));
 258         t2 = isl_union_map_lex_lt_union_map(isl_union_map_copy(code_schedule),
 259                                             isl_union_map_copy(code_schedule));
 260         equal = isl_union_map_is_equal(t1, t2);
 261         isl_union_map_free(t1);
 262         isl_union_map_free(t2);
 263
 264         if (equal < 0)
 265                 return -1;
 266         if (!equal)
 267                 isl_die(isl_union_map_get_ctx(schedule), isl_error_unknown,
 268                         "order not respected", return -1);
 269
 270         return 0;
 271 }
 272
 273 /* Check that the relative order specified by the input schedule is respected
 274  * by the schedule extracted from the code.
 275  *
 276  * "sv" indicated whether the original schedule is single valued.
 277  * If so, we use a cheaper test.  Otherwise, we fall back on a more
 278  * expensive test.
 279  */
 280 static int check_order(__isl_keep isl_union_map *schedule,
 281         __isl_keep isl_union_map *code_schedule, int sv)
 282 {
 283         if (sv)
 284                 return check_order_sv(schedule, code_schedule);
 285         else
 286                 return check_order_not_sv(schedule, code_schedule);
 287 }
 288
 289 /* If the original schedule was single valued ("sv" is set),
 290  * then the schedule extracted from the code should be single valued as well.
 291  */
 292 static int check_single_valued(__isl_keep isl_union_map *code_schedule, int sv)
 293 {
 294         if (!sv)
 295                 return 0;
 296
 297         sv = isl_union_map_is_single_valued(code_schedule);
 298         if (sv < 0)
 299                 return -1;
 300
 301         if (!sv)
 302                 isl_die(isl_union_map_get_ctx(code_schedule), isl_error_unknown,
 303                         "schedule not single valued", return -1);
 304
 305         return 0;
 306 }
 307
 308 /* Read a schedule and a context from the first argument and
 309  * C code from the second argument and check that the C code
 310  * corresponds to the schedule on the context.
 311  *
 312  * In particular, check that
 313  * - the domains are identical, i.e., the calls in the C code
 314  *   correspond to the domain elements of the schedule
 315  * - no function is called twice with the same arguments, provided
 316  *   the schedule is single-valued
 317  * - the calls are performed in an order that is compatible
 318  *   with the schedule
 319  *
 320  * If the schedule is not single-valued then we would have to check
 321  * that each function with a given set of arguments is called
 322  * the same number of times as there are images in the schedule,
 323  * but this is considerably more difficult.
 324  */
 325 int main(int argc, char **argv)
 326 {
 327         isl_ctx *ctx;
 328         isl_set *context;
 329         isl_union_map *schedule, *code_schedule;
 330         struct pet_scop *scop;
 331         struct options *options;
 332         FILE *file;
 333         int r;
 334         int sv;
 335
 336         options = options_new_with_defaults();
 337         assert(options);
 338         ctx = isl_ctx_alloc_with_options(&options_args, options);
 339         pet_options_set_signed_overflow(ctx, PET_OVERFLOW_IGNORE);
 340         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 341
 342         file = fopen(options->schedule, "r");
 343         assert(file);
 344         schedule = isl_union_map_read_from_file(ctx, file);
 345         context = isl_set_read_from_file(ctx, file);
 346         fclose(file);
 347
 348         scop = pet_scop_extract_from_C_source(ctx, options->code, NULL);
 349
 350         schedule = isl_union_map_intersect_params(schedule,
 351                                                 isl_set_copy(context));
 352         code_schedule = extract_code_schedule(scop);
 353         code_schedule = isl_union_map_intersect_params(code_schedule, context);
 354
 355         sv = isl_union_map_is_single_valued(schedule);
 356         r = sv < 0 ||
 357             check_domain(schedule, code_schedule) ||
 358             check_single_valued(code_schedule, sv) ||
 359             check_order(schedule, code_schedule, sv);
 360
 361         pet_scop_free(scop);
 362         isl_union_map_free(schedule);
 363         isl_union_map_free(code_schedule);
 364         isl_ctx_free(ctx);
 365
 366         return r;
 367 }