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