ppcg.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <assert.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <isl/ctx.h>
  15 #include <isl/flow.h>
  16 #include <isl/options.h>
  17 #include <isl/schedule.h>
  18 #include <isl/ast_build.h>
  19 #include <isl/schedule.h>
  20 #include <pet.h>
  21 #include "ppcg.h"
  22 #include "ppcg_options.h"
  23 #include "cuda.h"
  24 #include "cpu.h"
  25
  26 struct options {
  27         struct isl_options *isl;
  28         struct pet_options *pet;
  29         struct ppcg_options *ppcg;
  30         char *input;
  31         char *output;
  32 };
  33
  34 const char *ppcg_version(void);
  35 static void print_version(void)
  36 {
  37         printf("%s", ppcg_version());
  38 }
  39
  40 ISL_ARGS_START(struct options, options_args)
  41 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  42 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
  43 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
  44 ISL_ARG_STR(struct options, output, 'o', NULL,
  45         "filename", NULL, "output filename (c target)")
  46 ISL_ARG_ARG(struct options, input, "input", NULL)
  47 ISL_ARG_VERSION(print_version)
  48 ISL_ARGS_END
  49
  50 ISL_ARG_DEF(options, struct options, options_args)
  51
  52 /* Is "stmt" a kill statement?
  53  */
  54 static int is_kill(struct pet_stmt *stmt)
  55 {
  56         if (stmt->body->type != pet_expr_unary)
  57                 return 0;
  58         return stmt->body->op == pet_op_kill;
  59 }
  60
  61 /* Is "stmt" not a kill statement?
  62  */
  63 static int is_not_kill(struct pet_stmt *stmt)
  64 {
  65         return !is_kill(stmt);
  66 }
  67
  68 /* Collect the iteration domains of the statements in "scop" that
  69  * satisfy "pred".
  70  */
  71 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
  72         int (*pred)(struct pet_stmt *stmt))
  73 {
  74         int i;
  75         isl_set *domain_i;
  76         isl_union_set *domain;
  77
  78         if (!scop)
  79                 return NULL;
  80
  81         domain = isl_union_set_empty(isl_set_get_space(scop->context));
  82
  83         for (i = 0; i < scop->n_stmt; ++i) {
  84                 struct pet_stmt *stmt = scop->stmts[i];
  85
  86                 if (!pred(stmt))
  87                         continue;
  88
  89                 if (stmt->n_arg > 0)
  90                         isl_die(isl_union_set_get_ctx(domain),
  91                                 isl_error_unsupported,
  92                                 "data dependent conditions not supported",
  93                                 return isl_union_set_free(domain));
  94
  95                 domain_i = isl_set_copy(scop->stmts[i]->domain);
  96                 domain = isl_union_set_add_set(domain, domain_i);
  97         }
  98
  99         return domain;
 100 }
 101
 102 /* Collect the iteration domains of the statements in "scop",
 103  * skipping kill statements.
 104  */
 105 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
 106 {
 107         return collect_domains(scop, &is_not_kill);
 108 }
 109
 110 /* Does "expr" contain any call expressions?
 111  */
 112 static int expr_has_call(struct pet_expr *expr)
 113 {
 114         int i;
 115
 116         if (expr->type == pet_expr_call)
 117                 return 1;
 118
 119         for (i = 0; i < expr->n_arg; ++i)
 120                 if (expr_has_call(expr->args[i]))
 121                         return 1;
 122
 123         return 0;
 124 }
 125
 126 /* Does "stmt" contain any call expressions?
 127  */
 128 static int has_call(struct pet_stmt *stmt)
 129 {
 130         return expr_has_call(stmt->body);
 131 }
 132
 133 /* Collect the iteration domains of the statements in "scop"
 134  * that contain a call expression.
 135  */
 136 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
 137 {
 138         return collect_domains(scop, &has_call);
 139 }
 140
 141 /* Collect all kill accesses in "scop".
 142  */
 143 static __isl_give isl_union_map *collect_kills(struct pet_scop *scop)
 144 {
 145         int i;
 146         isl_union_map *kills;
 147
 148         if (!scop)
 149                 return NULL;
 150
 151         kills = isl_union_map_empty(isl_set_get_space(scop->context));
 152
 153         for (i = 0; i < scop->n_stmt; ++i) {
 154                 struct pet_stmt *stmt = scop->stmts[i];
 155                 isl_map *kill_i;
 156
 157                 if (!is_kill(stmt))
 158                         continue;
 159                 kill_i = isl_map_copy(stmt->body->args[0]->acc.access);
 160                 kill_i = isl_map_intersect_domain(kill_i,
 161                                                     isl_set_copy(stmt->domain));
 162                 kills = isl_union_map_add_map(kills, kill_i);
 163         }
 164
 165         return kills;
 166 }
 167
 168 /* Compute the dependences of the program represented by "scop".
 169  * Store the computed flow dependences
 170  * in scop->dep_flow and the reads with no corresponding writes in
 171  * scop->live_in.
 172  * Store the false (anti and output) dependences in scop->dep_false.
 173  */
 174 static void compute_dependences(struct ppcg_scop *scop)
 175 {
 176         isl_union_map *empty;
 177         isl_union_map *dep1, *dep2;
 178
 179         if (!scop)
 180                 return;
 181
 182         empty = isl_union_map_empty(isl_union_set_get_space(scop->domain));
 183         isl_union_map_compute_flow(isl_union_map_copy(scop->reads),
 184                                 isl_union_map_copy(scop->writes), empty,
 185                                 isl_union_map_copy(scop->schedule),
 186                                 &scop->dep_flow, NULL, &scop->live_in, NULL);
 187
 188         isl_union_map_compute_flow(isl_union_map_copy(scop->writes),
 189                                 isl_union_map_copy(scop->writes),
 190                                 isl_union_map_copy(scop->reads),
 191                                 isl_union_map_copy(scop->schedule),
 192                                 &dep1, &dep2, NULL, NULL);
 193
 194         scop->dep_false = isl_union_map_union(dep1, dep2);
 195         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 196 }
 197
 198 /* Eliminate dead code from ps->domain.
 199  *
 200  * In particular, intersect ps->domain with the (parts of) iteration
 201  * domains that are needed to produce the output or for statement
 202  * iterations that call functions.
 203  *
 204  * We start with the iteration domains that call functions
 205  * and the set of iterations that last write to an array
 206  * (except those that are later killed).
 207  *
 208  * Then we add those statement iterations that produce
 209  * something needed by the "live" statements iterations.
 210  * We keep doing this until no more statement iterations can be added.
 211  * To ensure that the procedure terminates, we compute the affine
 212  * hull of the live iterations (bounded to the original iteration
 213  * domains) each time we have added extra iterations.
 214  */
 215 static void eliminate_dead_code(struct ppcg_scop *ps)
 216 {
 217         isl_union_map *exposed;
 218         isl_union_set *live;
 219         isl_union_map *dep;
 220
 221         exposed = isl_union_map_union(isl_union_map_copy(ps->writes),
 222                                             isl_union_map_copy(ps->kills));
 223         exposed = isl_union_map_reverse(exposed);
 224         exposed = isl_union_map_apply_range(exposed,
 225                                             isl_union_map_copy(ps->schedule));
 226         exposed = isl_union_map_lexmax(exposed);
 227         exposed = isl_union_map_apply_range(exposed,
 228                     isl_union_map_reverse(isl_union_map_copy(ps->schedule)));
 229
 230         live = isl_union_map_range(exposed);
 231         if (!isl_union_set_is_empty(ps->call)) {
 232                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 233                 live = isl_union_set_coalesce(live);
 234         }
 235
 236         dep = isl_union_map_copy(ps->dep_flow);
 237         dep = isl_union_map_reverse(dep);
 238
 239         for (;;) {
 240                 isl_union_set *extra;
 241
 242                 extra = isl_union_set_apply(isl_union_set_copy(live),
 243                                             isl_union_map_copy(dep));
 244                 if (isl_union_set_is_subset(extra, live)) {
 245                         isl_union_set_free(extra);
 246                         break;
 247                 }
 248
 249                 live = isl_union_set_union(live, extra);
 250                 live = isl_union_set_affine_hull(live);
 251                 live = isl_union_set_intersect(live,
 252                                             isl_union_set_copy(ps->domain));
 253         }
 254
 255         isl_union_map_free(dep);
 256
 257         ps->domain = isl_union_set_intersect(ps->domain, live);
 258 }
 259
 260 /* Intersect "set" with the set described by "str", taking the NULL
 261  * string to represent the universal set.
 262  */
 263 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 264         const char *str)
 265 {
 266         isl_ctx *ctx;
 267         isl_set *set2;
 268
 269         if (!str)
 270                 return set;
 271
 272         ctx = isl_set_get_ctx(set);
 273         set2 = isl_set_read_from_str(ctx, str);
 274         set = isl_set_intersect(set, set2);
 275
 276         return set;
 277 }
 278
 279 /* Does "expr" involve any data dependent accesses?
 280  */
 281 static int expr_has_data_dependent_accesses(struct pet_expr *expr)
 282 {
 283         int i;
 284
 285         for (i = 0; i < expr->n_arg; ++i)
 286                 if (expr_has_data_dependent_accesses(expr->args[i]))
 287                         return 1;
 288
 289         if (expr->type == pet_expr_access && expr->n_arg > 0)
 290                 return 1;
 291
 292         return 0;
 293 }
 294
 295 /* Does "stmt" contain any data dependent accesses?
 296  */
 297 static int stmt_has_data_dependent_accesses(struct pet_stmt *stmt)
 298 {
 299         return expr_has_data_dependent_accesses(stmt->body);
 300 }
 301
 302 /* Does "scop" contain any data dependent accesses?
 303  */
 304 static int scop_has_data_dependent_accesses(struct pet_scop *scop)
 305 {
 306         int i;
 307
 308         if (!scop)
 309                 return -1;
 310         for (i = 0; i < scop->n_stmt; ++i)
 311                 if (stmt_has_data_dependent_accesses(scop->stmts[i]))
 312                         return 1;
 313
 314         return 0;
 315 }
 316
 317 static void *ppcg_scop_free(struct ppcg_scop *ps)
 318 {
 319         if (!ps)
 320                 return NULL;
 321
 322         isl_set_free(ps->context);
 323         isl_union_set_free(ps->domain);
 324         isl_union_set_free(ps->call);
 325         isl_union_map_free(ps->reads);
 326         isl_union_map_free(ps->live_in);
 327         isl_union_map_free(ps->writes);
 328         isl_union_map_free(ps->kills);
 329         isl_union_map_free(ps->dep_flow);
 330         isl_union_map_free(ps->dep_false);
 331         isl_union_map_free(ps->schedule);
 332
 333         free(ps);
 334
 335         return NULL;
 336 }
 337
 338 /* Extract a ppcg_scop from a pet_scop.
 339  *
 340  * The constructed ppcg_scop refers to elements from the pet_scop
 341  * so the pet_scop should not be freed before the ppcg_scop.
 342  */
 343 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 344         struct ppcg_options *options)
 345 {
 346         isl_ctx *ctx;
 347         struct ppcg_scop *ps;
 348
 349         if (!scop)
 350                 return NULL;
 351
 352         ctx = isl_set_get_ctx(scop->context);
 353
 354         if (scop_has_data_dependent_accesses(scop))
 355                 isl_die(ctx, isl_error_unsupported,
 356                         "data dependent accesses not supported",
 357                         return NULL);
 358
 359         ps = isl_calloc_type(ctx, struct ppcg_scop);
 360         if (!ps)
 361                 return NULL;
 362
 363         ps->start = scop->start;
 364         ps->end = scop->end;
 365         ps->context = isl_set_copy(scop->context);
 366         ps->context = set_intersect_str(ps->context, options->ctx);
 367         ps->domain = collect_non_kill_domains(scop);
 368         ps->call = collect_call_domains(scop);
 369         ps->reads = pet_scop_collect_reads(scop);
 370         ps->writes = pet_scop_collect_writes(scop);
 371         ps->kills = collect_kills(scop);
 372         ps->schedule = pet_scop_collect_schedule(scop);
 373         ps->n_array = scop->n_array;
 374         ps->arrays = scop->arrays;
 375         ps->n_stmt = scop->n_stmt;
 376         ps->stmts = scop->stmts;
 377
 378         compute_dependences(ps);
 379         eliminate_dead_code(ps);
 380
 381         if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
 382             !ps->writes || !ps->kills || !ps->schedule)
 383                 return ppcg_scop_free(ps);
 384
 385         return ps;
 386 }
 387
 388 /* Check consistency of options.
 389  *
 390  * Return -1 on error.
 391  */
 392 static int check_options(isl_ctx *ctx)
 393 {
 394         struct options *options;
 395
 396         options = isl_ctx_peek_options(ctx, &options_args);
 397         if (!options)
 398                 isl_die(ctx, isl_error_internal,
 399                         "unable to find options", return -1);
 400
 401         if (options->ppcg->openmp &&
 402             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 403                 isl_die(ctx, isl_error_invalid,
 404                         "OpenMP requires atomic bounds", return -1);
 405
 406         return 0;
 407 }
 408
 409 /* Extract a model from the input file, transform the model and
 410  * write out the result to the output file(s).
 411  */
 412 static int transform(isl_ctx *ctx)
 413 {
 414         int r;
 415         struct pet_scop *scop;
 416         struct ppcg_scop *ps;
 417         struct options *options;
 418
 419         options = isl_ctx_peek_options(ctx, &options_args);
 420         if (!options)
 421                 isl_die(ctx, isl_error_internal,
 422                         "unable to find options", return EXIT_FAILURE);
 423
 424         scop = pet_scop_extract_from_C_source(ctx, options->input, NULL);
 425         scop = pet_scop_align_params(scop);
 426         ps = ppcg_scop_from_pet_scop(scop, options->ppcg);
 427
 428         if (options->ppcg->target == PPCG_TARGET_CUDA)
 429                 r = generate_cuda(ctx, ps, options->ppcg, options->input);
 430         else
 431                 r = generate_cpu(ctx, ps, options->ppcg, options->input,
 432                                 options->output);
 433
 434         ppcg_scop_free(ps);
 435         pet_scop_free(scop);
 436
 437         return r;
 438 }
 439
 440 int main(int argc, char **argv)
 441 {
 442         int r;
 443         isl_ctx *ctx;
 444         struct options *options;
 445
 446         options = options_new_with_defaults();
 447         assert(options);
 448
 449         ctx = isl_ctx_alloc_with_options(&options_args, options);
 450         isl_options_set_schedule_outer_zero_distance(ctx, 1);
 451         isl_options_set_schedule_maximize_band_depth(ctx, 1);
 452         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 453
 454         if (check_options(ctx) < 0)
 455                 r = EXIT_FAILURE;
 456         else
 457                 r = transform(ctx);
 458
 459         isl_ctx_free(ctx);
 460
 461         return r;
 462 }