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                 domain_i = isl_set_copy(scop->stmts[i]->domain);
  89                 domain = isl_union_set_add_set(domain, domain_i);
  90         }
  91
  92         return domain;
  93 }
  94
  95 /* Collect the iteration domains of the statements in "scop",
  96  * skipping kill statements.
  97  */
  98 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
  99 {
 100         return collect_domains(scop, &is_not_kill);
 101 }
 102
 103 /* Does "expr" contain any call expressions?
 104  */
 105 static int expr_has_call(struct pet_expr *expr)
 106 {
 107         int i;
 108
 109         if (expr->type == pet_expr_call)
 110                 return 1;
 111
 112         for (i = 0; i < expr->n_arg; ++i)
 113                 if (expr_has_call(expr->args[i]))
 114                         return 1;
 115
 116         return 0;
 117 }
 118
 119 /* Does "stmt" contain any call expressions?
 120  */
 121 static int has_call(struct pet_stmt *stmt)
 122 {
 123         return expr_has_call(stmt->body);
 124 }
 125
 126 /* Collect the iteration domains of the statements in "scop"
 127  * that contain a call expression.
 128  */
 129 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
 130 {
 131         return collect_domains(scop, &has_call);
 132 }
 133
 134 /* Collect all kill accesses in "scop".
 135  */
 136 static __isl_give isl_union_map *collect_kills(struct pet_scop *scop)
 137 {
 138         int i;
 139         isl_union_map *kills;
 140
 141         if (!scop)
 142                 return NULL;
 143
 144         kills = isl_union_map_empty(isl_set_get_space(scop->context));
 145
 146         for (i = 0; i < scop->n_stmt; ++i) {
 147                 struct pet_stmt *stmt = scop->stmts[i];
 148                 isl_map *kill_i;
 149
 150                 if (!is_kill(stmt))
 151                         continue;
 152                 kill_i = isl_map_copy(stmt->body->args[0]->acc.access);
 153                 kill_i = isl_map_intersect_domain(kill_i,
 154                                                     isl_set_copy(stmt->domain));
 155                 kills = isl_union_map_add_map(kills, kill_i);
 156         }
 157
 158         return kills;
 159 }
 160
 161 /* Compute the dependences of the program represented by "scop".
 162  * Store the computed flow dependences
 163  * in scop->dep_flow and the reads with no corresponding writes in
 164  * scop->live_in.
 165  * Store the false (anti and output) dependences in scop->dep_false.
 166  */
 167 static void compute_dependences(struct ppcg_scop *scop)
 168 {
 169         isl_union_map *empty;
 170         isl_union_map *dep1, *dep2;
 171
 172         if (!scop)
 173                 return;
 174
 175         empty = isl_union_map_empty(isl_union_set_get_space(scop->domain));
 176         isl_union_map_compute_flow(isl_union_map_copy(scop->reads),
 177                                 isl_union_map_copy(scop->writes), empty,
 178                                 isl_union_map_copy(scop->schedule),
 179                                 &scop->dep_flow, NULL, &scop->live_in, NULL);
 180
 181         isl_union_map_compute_flow(isl_union_map_copy(scop->writes),
 182                                 isl_union_map_copy(scop->writes),
 183                                 isl_union_map_copy(scop->reads),
 184                                 isl_union_map_copy(scop->schedule),
 185                                 &dep1, &dep2, NULL, NULL);
 186
 187         scop->dep_false = isl_union_map_union(dep1, dep2);
 188         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 189 }
 190
 191 /* Eliminate dead code from ps->domain.
 192  *
 193  * In particular, intersect ps->domain with the (parts of) iteration
 194  * domains that are needed to produce the output or for statement
 195  * iterations that call functions.
 196  *
 197  * We start with the iteration domains that call functions
 198  * and the set of iterations that last write to an array
 199  * (except those that are later killed).
 200  *
 201  * Then we add those statement iterations that produce
 202  * something needed by the "live" statements iterations.
 203  * We keep doing this until no more statement iterations can be added.
 204  * To ensure that the procedure terminates, we compute the affine
 205  * hull of the live iterations (bounded to the original iteration
 206  * domains) each time we have added extra iterations.
 207  */
 208 static void eliminate_dead_code(struct ppcg_scop *ps)
 209 {
 210         isl_union_map *exposed;
 211         isl_union_set *live;
 212         isl_union_map *dep;
 213
 214         exposed = isl_union_map_union(isl_union_map_copy(ps->writes),
 215                                             isl_union_map_copy(ps->kills));
 216         exposed = isl_union_map_reverse(exposed);
 217         exposed = isl_union_map_apply_range(exposed,
 218                                             isl_union_map_copy(ps->schedule));
 219         exposed = isl_union_map_lexmax(exposed);
 220         exposed = isl_union_map_apply_range(exposed,
 221                     isl_union_map_reverse(isl_union_map_copy(ps->schedule)));
 222
 223         live = isl_union_map_range(exposed);
 224         if (!isl_union_set_is_empty(ps->call)) {
 225                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 226                 live = isl_union_set_coalesce(live);
 227         }
 228
 229         dep = isl_union_map_copy(ps->dep_flow);
 230         dep = isl_union_map_reverse(dep);
 231
 232         for (;;) {
 233                 isl_union_set *extra;
 234
 235                 extra = isl_union_set_apply(isl_union_set_copy(live),
 236                                             isl_union_map_copy(dep));
 237                 if (isl_union_set_is_subset(extra, live)) {
 238                         isl_union_set_free(extra);
 239                         break;
 240                 }
 241
 242                 live = isl_union_set_union(live, extra);
 243                 live = isl_union_set_affine_hull(live);
 244                 live = isl_union_set_intersect(live,
 245                                             isl_union_set_copy(ps->domain));
 246         }
 247
 248         isl_union_map_free(dep);
 249
 250         ps->domain = isl_union_set_intersect(ps->domain, live);
 251 }
 252
 253 /* Intersect "set" with the set described by "str", taking the NULL
 254  * string to represent the universal set.
 255  */
 256 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 257         const char *str)
 258 {
 259         isl_ctx *ctx;
 260         isl_set *set2;
 261
 262         if (!str)
 263                 return set;
 264
 265         ctx = isl_set_get_ctx(set);
 266         set2 = isl_set_read_from_str(ctx, str);
 267         set = isl_set_intersect(set, set2);
 268
 269         return set;
 270 }
 271
 272 /* Does "expr" involve any data dependent accesses?
 273  */
 274 static int expr_has_data_dependent_accesses(struct pet_expr *expr)
 275 {
 276         int i;
 277
 278         for (i = 0; i < expr->n_arg; ++i)
 279                 if (expr_has_data_dependent_accesses(expr->args[i]))
 280                         return 1;
 281
 282         if (expr->type == pet_expr_access && expr->n_arg > 0)
 283                 return 1;
 284
 285         return 0;
 286 }
 287
 288 /* Does "stmt" contain any data dependent accesses?
 289  */
 290 static int stmt_has_data_dependent_accesses(struct pet_stmt *stmt)
 291 {
 292         return expr_has_data_dependent_accesses(stmt->body);
 293 }
 294
 295 /* Does "scop" contain any data dependent accesses?
 296  */
 297 static int scop_has_data_dependent_accesses(struct pet_scop *scop)
 298 {
 299         int i;
 300
 301         if (!scop)
 302                 return -1;
 303         for (i = 0; i < scop->n_stmt; ++i)
 304                 if (stmt_has_data_dependent_accesses(scop->stmts[i]))
 305                         return 1;
 306
 307         return 0;
 308 }
 309
 310 /* Extract a ppcg_scop from a pet_scop.
 311  *
 312  * The constructed ppcg_scop refers to elements from the pet_scop
 313  * so the pet_scop should not be freed before the ppcg_scop.
 314  */
 315 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 316         struct ppcg_options *options)
 317 {
 318         isl_ctx *ctx;
 319         struct ppcg_scop *ps;
 320
 321         if (!scop)
 322                 return NULL;
 323
 324         ctx = isl_set_get_ctx(scop->context);
 325
 326         if (scop_has_data_dependent_accesses(scop))
 327                 isl_die(ctx, isl_error_unsupported,
 328                         "data dependent accesses not supported",
 329                         return NULL);
 330
 331         ps = isl_calloc_type(ctx, struct ppcg_scop);
 332         if (!ps)
 333                 return NULL;
 334
 335         ps->start = scop->start;
 336         ps->end = scop->end;
 337         ps->context = isl_set_copy(scop->context);
 338         ps->context = set_intersect_str(ps->context, options->ctx);
 339         ps->domain = collect_non_kill_domains(scop);
 340         ps->call = collect_call_domains(scop);
 341         ps->reads = pet_scop_collect_reads(scop);
 342         ps->writes = pet_scop_collect_writes(scop);
 343         ps->kills = collect_kills(scop);
 344         ps->schedule = pet_scop_collect_schedule(scop);
 345         ps->n_array = scop->n_array;
 346         ps->arrays = scop->arrays;
 347         ps->n_stmt = scop->n_stmt;
 348         ps->stmts = scop->stmts;
 349
 350         compute_dependences(ps);
 351         eliminate_dead_code(ps);
 352
 353         return ps;
 354 }
 355
 356 static void ppcg_scop_free(struct ppcg_scop *ps)
 357 {
 358         if (!ps)
 359                 return;
 360
 361         isl_set_free(ps->context);
 362         isl_union_set_free(ps->domain);
 363         isl_union_set_free(ps->call);
 364         isl_union_map_free(ps->reads);
 365         isl_union_map_free(ps->live_in);
 366         isl_union_map_free(ps->writes);
 367         isl_union_map_free(ps->kills);
 368         isl_union_map_free(ps->dep_flow);
 369         isl_union_map_free(ps->dep_false);
 370         isl_union_map_free(ps->schedule);
 371
 372         free(ps);
 373 }
 374
 375 /* Check consistency of options.
 376  *
 377  * Return -1 on error.
 378  */
 379 static int check_options(isl_ctx *ctx)
 380 {
 381         struct options *options;
 382
 383         options = isl_ctx_peek_options(ctx, &options_args);
 384         if (!options)
 385                 isl_die(ctx, isl_error_internal,
 386                         "unable to find options", return -1);
 387
 388         if (options->ppcg->openmp &&
 389             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 390                 isl_die(ctx, isl_error_invalid,
 391                         "OpenMP requires atomic bounds", return -1);
 392
 393         return 0;
 394 }
 395
 396 /* Extract a model from the input file, transform the model and
 397  * write out the result to the output file(s).
 398  */
 399 static int transform(isl_ctx *ctx)
 400 {
 401         int r;
 402         struct pet_scop *scop;
 403         struct ppcg_scop *ps;
 404         struct options *options;
 405
 406         options = isl_ctx_peek_options(ctx, &options_args);
 407         if (!options)
 408                 isl_die(ctx, isl_error_internal,
 409                         "unable to find options", return EXIT_FAILURE);
 410
 411         scop = pet_scop_extract_from_C_source(ctx, options->input, NULL);
 412         scop = pet_scop_align_params(scop);
 413         ps = ppcg_scop_from_pet_scop(scop, options->ppcg);
 414
 415         if (options->ppcg->target == PPCG_TARGET_CUDA)
 416                 r = generate_cuda(ctx, ps, options->ppcg, options->input);
 417         else
 418                 r = generate_cpu(ctx, ps, options->ppcg, options->input,
 419                                 options->output);
 420
 421         ppcg_scop_free(ps);
 422         pet_scop_free(scop);
 423
 424         return r;
 425 }
 426
 427 int main(int argc, char **argv)
 428 {
 429         int r;
 430         isl_ctx *ctx;
 431         struct options *options;
 432
 433         options = options_new_with_defaults();
 434         assert(options);
 435
 436         ctx = isl_ctx_alloc_with_options(&options_args, options);
 437         isl_options_set_schedule_outer_zero_distance(ctx, 1);
 438         isl_options_set_schedule_maximize_band_depth(ctx, 1);
 439         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 440
 441         if (check_options(ctx) < 0)
 442                 r = EXIT_FAILURE;
 443         else
 444                 r = transform(ctx);
 445
 446         isl_ctx_free(ctx);
 447
 448         return r;
 449 }