ppcg.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #include <assert.h>
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <isl/ctx.h>
  18 #include <isl/flow.h>
  19 #include <isl/options.h>
  20 #include <isl/schedule.h>
  21 #include <isl/ast_build.h>
  22 #include <isl/schedule.h>
  23 #include <pet.h>
  24 #include "ppcg.h"
  25 #include "ppcg_options.h"
  26 #include "cuda.h"
  27 #include "cpu.h"
  28
  29 struct options {
  30         struct isl_options *isl;
  31         struct pet_options *pet;
  32         struct ppcg_options *ppcg;
  33         char *input;
  34         char *output;
  35 };
  36
  37 const char *ppcg_version(void);
  38 static void print_version(void)
  39 {
  40         printf("%s", ppcg_version());
  41 }
  42
  43 ISL_ARGS_START(struct options, options_args)
  44 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  45 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
  46 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
  47 ISL_ARG_STR(struct options, output, 'o', NULL,
  48         "filename", NULL, "output filename (c target)")
  49 ISL_ARG_ARG(struct options, input, "input", NULL)
  50 ISL_ARG_VERSION(print_version)
  51 ISL_ARGS_END
  52
  53 ISL_ARG_DEF(options, struct options, options_args)
  54
  55 /* Copy the base name of "input" to "name" and return its length.
  56  * "name" is not NULL terminated.
  57  *
  58  * In particular, remove all leading directory components and
  59  * the final extension, if any.
  60  */
  61 int ppcg_extract_base_name(char *name, const char *input)
  62 {
  63         const char *base;
  64         const char *ext;
  65         int len;
  66
  67         base = strrchr(input, '/');
  68         if (base)
  69                 base++;
  70         else
  71                 base = input;
  72         ext = strrchr(base, '.');
  73         len = ext ? ext - base : strlen(base);
  74
  75         memcpy(name, base, len);
  76
  77         return len;
  78 }
  79
  80 /* Is "stmt" a kill statement?
  81  */
  82 static int is_kill(struct pet_stmt *stmt)
  83 {
  84         if (stmt->body->type != pet_expr_unary)
  85                 return 0;
  86         return stmt->body->op == pet_op_kill;
  87 }
  88
  89 /* Is "stmt" not a kill statement?
  90  */
  91 static int is_not_kill(struct pet_stmt *stmt)
  92 {
  93         return !is_kill(stmt);
  94 }
  95
  96 /* Collect the iteration domains of the statements in "scop" that
  97  * satisfy "pred".
  98  */
  99 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
 100         int (*pred)(struct pet_stmt *stmt))
 101 {
 102         int i;
 103         isl_set *domain_i;
 104         isl_union_set *domain;
 105
 106         if (!scop)
 107                 return NULL;
 108
 109         domain = isl_union_set_empty(isl_set_get_space(scop->context));
 110
 111         for (i = 0; i < scop->n_stmt; ++i) {
 112                 struct pet_stmt *stmt = scop->stmts[i];
 113
 114                 if (!pred(stmt))
 115                         continue;
 116
 117                 if (stmt->n_arg > 0)
 118                         isl_die(isl_union_set_get_ctx(domain),
 119                                 isl_error_unsupported,
 120                                 "data dependent conditions not supported",
 121                                 return isl_union_set_free(domain));
 122
 123                 domain_i = isl_set_copy(scop->stmts[i]->domain);
 124                 domain = isl_union_set_add_set(domain, domain_i);
 125         }
 126
 127         return domain;
 128 }
 129
 130 /* Collect the iteration domains of the statements in "scop",
 131  * skipping kill statements.
 132  */
 133 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
 134 {
 135         return collect_domains(scop, &is_not_kill);
 136 }
 137
 138 /* Does "expr" contain any call expressions?
 139  */
 140 static int expr_has_call(struct pet_expr *expr)
 141 {
 142         int i;
 143
 144         if (expr->type == pet_expr_call)
 145                 return 1;
 146
 147         for (i = 0; i < expr->n_arg; ++i)
 148                 if (expr_has_call(expr->args[i]))
 149                         return 1;
 150
 151         return 0;
 152 }
 153
 154 /* Does "stmt" contain any call expressions?
 155  */
 156 static int has_call(struct pet_stmt *stmt)
 157 {
 158         return expr_has_call(stmt->body);
 159 }
 160
 161 /* Collect the iteration domains of the statements in "scop"
 162  * that contain a call expression.
 163  */
 164 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
 165 {
 166         return collect_domains(scop, &has_call);
 167 }
 168
 169 /* Construct a relation from the iteration domains to tagged iteration
 170  * domains with as range the reference tags that appear
 171  * in any of the reads, writes or kills.
 172  * Store the result in ps->tagger.
 173  *
 174  * For example, if the statement with iteration space S[i,j]
 175  * contains two array references R_1[] and R_2[], then ps->tagger will contain
 176  *
 177  *      { S[i,j] -> [S[i,j] -> R_1[]]; S[i,j] -> [S[i,j] -> R_2[]] }
 178  */
 179 static void compute_tagger(struct ppcg_scop *ps)
 180 {
 181         isl_union_map *tagged, *tagger;
 182
 183         tagged = isl_union_map_copy(ps->tagged_reads);
 184         tagged = isl_union_map_union(tagged,
 185                                 isl_union_map_copy(ps->tagged_may_writes));
 186         tagged = isl_union_map_union(tagged,
 187                                 isl_union_map_copy(ps->tagged_must_kills));
 188
 189         tagger = isl_union_map_universe(tagged);
 190         tagger = isl_union_set_unwrap(isl_union_map_domain(tagger));
 191         tagger = isl_union_map_reverse(isl_union_map_domain_map(tagger));
 192
 193         ps->tagger = tagger;
 194 }
 195
 196 /* Compute the live out accesses, i.e., the writes that are
 197  * potentially not killed by any kills or any other writes, and
 198  * store them in ps->live_out.
 199  *
 200  * We compute the "dependence" of any "kill" (an explicit kill
 201  * or a must write) on any may write.
 202  * The may writes with a "depending" kill are definitely killed.
 203  * The remaining may writes can potentially be live out.
 204  */
 205 static void compute_live_out(struct ppcg_scop *ps)
 206 {
 207         isl_union_map *tagger;
 208         isl_union_map *schedule;
 209         isl_union_map *empty;
 210         isl_union_map *kills;
 211         isl_union_map *exposed;
 212         isl_union_map *covering;
 213
 214         tagger = isl_union_map_copy(ps->tagger);
 215         schedule = isl_union_map_copy(ps->schedule);
 216         schedule = isl_union_map_apply_domain(schedule,
 217                                         isl_union_map_copy(tagger));
 218         empty = isl_union_map_empty(isl_union_set_get_space(ps->domain));
 219         kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
 220                                     isl_union_map_copy(ps->tagged_must_kills));
 221         isl_union_map_compute_flow(kills, empty,
 222                                 isl_union_map_copy(ps->tagged_may_writes),
 223                                 schedule, NULL, &covering, NULL, NULL);
 224         exposed = isl_union_map_copy(ps->tagged_may_writes);
 225         exposed = isl_union_map_subtract_domain(exposed,
 226                                 isl_union_map_domain(covering));
 227         exposed = isl_union_map_apply_range(tagger, exposed);
 228         ps->live_out = exposed;
 229 }
 230
 231 /* Compute the potential flow dependences and the potential live in
 232  * accesses.
 233  */
 234 static void compute_flow_dep(struct ppcg_scop *ps)
 235 {
 236         isl_union_map *may_flow;
 237         isl_union_map *may_live_in;
 238
 239         isl_union_map_compute_flow(isl_union_map_copy(ps->reads),
 240                                 isl_union_map_copy(ps->must_writes),
 241                                 isl_union_map_copy(ps->may_writes),
 242                                 isl_union_map_copy(ps->schedule),
 243                                 &ps->dep_flow, &may_flow,
 244                                 &ps->live_in, &may_live_in);
 245
 246         ps->dep_flow = isl_union_map_union(ps->dep_flow, may_flow);
 247         ps->live_in = isl_union_map_union(ps->live_in, may_live_in);
 248 }
 249
 250 /* Compute the dependences of the program represented by "scop".
 251  * Store the computed potential flow dependences
 252  * in scop->dep_flow and the reads with potentially no corresponding writes in
 253  * scop->live_in.
 254  * Store the potential live out accesses in scop->live_out.
 255  * Store the potential false (anti and output) dependences in scop->dep_false.
 256  */
 257 static void compute_dependences(struct ppcg_scop *scop)
 258 {
 259         isl_union_map *dep1, *dep2;
 260         isl_union_map *may_source;
 261
 262         if (!scop)
 263                 return;
 264
 265         compute_live_out(scop);
 266
 267         compute_flow_dep(scop);
 268
 269         may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
 270                                         isl_union_map_copy(scop->reads));
 271         isl_union_map_compute_flow(isl_union_map_copy(scop->may_writes),
 272                                 isl_union_map_copy(scop->must_writes),
 273                                 may_source, isl_union_map_copy(scop->schedule),
 274                                 &dep1, &dep2, NULL, NULL);
 275
 276         scop->dep_false = isl_union_map_union(dep1, dep2);
 277         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 278 }
 279
 280 /* Eliminate dead code from ps->domain.
 281  *
 282  * In particular, intersect ps->domain with the (parts of) iteration
 283  * domains that are needed to produce the output or for statement
 284  * iterations that call functions.
 285  *
 286  * We start with the iteration domains that call functions
 287  * and the set of iterations that last write to an array
 288  * (except those that are later killed).
 289  *
 290  * Then we add those statement iterations that produce
 291  * something needed by the "live" statements iterations.
 292  * We keep doing this until no more statement iterations can be added.
 293  * To ensure that the procedure terminates, we compute the affine
 294  * hull of the live iterations (bounded to the original iteration
 295  * domains) each time we have added extra iterations.
 296  */
 297 static void eliminate_dead_code(struct ppcg_scop *ps)
 298 {
 299         isl_union_set *live;
 300         isl_union_map *dep;
 301
 302         live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
 303         if (!isl_union_set_is_empty(ps->call)) {
 304                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 305                 live = isl_union_set_coalesce(live);
 306         }
 307
 308         dep = isl_union_map_copy(ps->dep_flow);
 309         dep = isl_union_map_reverse(dep);
 310
 311         for (;;) {
 312                 isl_union_set *extra;
 313
 314                 extra = isl_union_set_apply(isl_union_set_copy(live),
 315                                             isl_union_map_copy(dep));
 316                 if (isl_union_set_is_subset(extra, live)) {
 317                         isl_union_set_free(extra);
 318                         break;
 319                 }
 320
 321                 live = isl_union_set_union(live, extra);
 322                 live = isl_union_set_affine_hull(live);
 323                 live = isl_union_set_intersect(live,
 324                                             isl_union_set_copy(ps->domain));
 325         }
 326
 327         isl_union_map_free(dep);
 328
 329         ps->domain = isl_union_set_intersect(ps->domain, live);
 330 }
 331
 332 /* Intersect "set" with the set described by "str", taking the NULL
 333  * string to represent the universal set.
 334  */
 335 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 336         const char *str)
 337 {
 338         isl_ctx *ctx;
 339         isl_set *set2;
 340
 341         if (!str)
 342                 return set;
 343
 344         ctx = isl_set_get_ctx(set);
 345         set2 = isl_set_read_from_str(ctx, str);
 346         set = isl_set_intersect(set, set2);
 347
 348         return set;
 349 }
 350
 351 /* Does "expr" involve any data dependent accesses?
 352  */
 353 static int expr_has_data_dependent_accesses(struct pet_expr *expr)
 354 {
 355         int i;
 356
 357         for (i = 0; i < expr->n_arg; ++i)
 358                 if (expr_has_data_dependent_accesses(expr->args[i]))
 359                         return 1;
 360
 361         if (expr->type == pet_expr_access && expr->n_arg > 0)
 362                 return 1;
 363
 364         return 0;
 365 }
 366
 367 /* Does "stmt" contain any data dependent accesses?
 368  */
 369 static int stmt_has_data_dependent_accesses(struct pet_stmt *stmt)
 370 {
 371         return expr_has_data_dependent_accesses(stmt->body);
 372 }
 373
 374 /* Does "scop" contain any data dependent accesses?
 375  */
 376 static int scop_has_data_dependent_accesses(struct pet_scop *scop)
 377 {
 378         int i;
 379
 380         if (!scop)
 381                 return -1;
 382         for (i = 0; i < scop->n_stmt; ++i)
 383                 if (stmt_has_data_dependent_accesses(scop->stmts[i]))
 384                         return 1;
 385
 386         return 0;
 387 }
 388
 389 static void *ppcg_scop_free(struct ppcg_scop *ps)
 390 {
 391         if (!ps)
 392                 return NULL;
 393
 394         isl_set_free(ps->context);
 395         isl_union_set_free(ps->domain);
 396         isl_union_set_free(ps->call);
 397         isl_union_map_free(ps->tagged_reads);
 398         isl_union_map_free(ps->reads);
 399         isl_union_map_free(ps->live_in);
 400         isl_union_map_free(ps->tagged_may_writes);
 401         isl_union_map_free(ps->tagged_must_writes);
 402         isl_union_map_free(ps->may_writes);
 403         isl_union_map_free(ps->must_writes);
 404         isl_union_map_free(ps->live_out);
 405         isl_union_map_free(ps->tagged_must_kills);
 406         isl_union_map_free(ps->dep_flow);
 407         isl_union_map_free(ps->dep_false);
 408         isl_union_map_free(ps->schedule);
 409         isl_union_map_free(ps->tagger);
 410
 411         free(ps);
 412
 413         return NULL;
 414 }
 415
 416 /* Extract a ppcg_scop from a pet_scop.
 417  *
 418  * The constructed ppcg_scop refers to elements from the pet_scop
 419  * so the pet_scop should not be freed before the ppcg_scop.
 420  */
 421 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 422         struct ppcg_options *options)
 423 {
 424         isl_ctx *ctx;
 425         struct ppcg_scop *ps;
 426
 427         if (!scop)
 428                 return NULL;
 429
 430         ctx = isl_set_get_ctx(scop->context);
 431
 432         ps = isl_calloc_type(ctx, struct ppcg_scop);
 433         if (!ps)
 434                 return NULL;
 435
 436         ps->options = options;
 437         ps->start = scop->start;
 438         ps->end = scop->end;
 439         ps->context = isl_set_copy(scop->context);
 440         ps->context = set_intersect_str(ps->context, options->ctx);
 441         ps->domain = collect_non_kill_domains(scop);
 442         ps->call = collect_call_domains(scop);
 443         ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
 444         ps->reads = pet_scop_collect_may_reads(scop);
 445         ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
 446         ps->may_writes = pet_scop_collect_may_writes(scop);
 447         ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
 448         ps->must_writes = pet_scop_collect_must_writes(scop);
 449         ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
 450         ps->schedule = pet_scop_collect_schedule(scop);
 451         ps->n_type = scop->n_type;
 452         ps->types = scop->types;
 453         ps->n_array = scop->n_array;
 454         ps->arrays = scop->arrays;
 455         ps->n_stmt = scop->n_stmt;
 456         ps->stmts = scop->stmts;
 457
 458         compute_tagger(ps);
 459         compute_dependences(ps);
 460         eliminate_dead_code(ps);
 461
 462         if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
 463             !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
 464             !ps->schedule)
 465                 return ppcg_scop_free(ps);
 466
 467         return ps;
 468 }
 469
 470 /* Internal data structure for ppcg_transform.
 471  */
 472 struct ppcg_transform_data {
 473         struct ppcg_options *options;
 474         __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
 475                 struct ppcg_scop *scop, void *user);
 476         void *user;
 477 };
 478
 479 /* Callback for pet_transform_C_source that transforms
 480  * the given pet_scop to a ppcg_scop before calling the
 481  * ppcg_transform callback.
 482  */
 483 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
 484         struct pet_scop *scop, void *user)
 485 {
 486         struct ppcg_transform_data *data = user;
 487         struct ppcg_scop *ps;
 488
 489         if (pet_scop_has_data_dependent_conditions(scop)) {
 490                 p = pet_scop_print_original(scop, p);
 491                 pet_scop_free(scop);
 492                 return p;
 493         }
 494
 495         scop = pet_scop_align_params(scop);
 496         ps = ppcg_scop_from_pet_scop(scop, data->options);
 497
 498         p = data->transform(p, ps, data->user);
 499
 500         ppcg_scop_free(ps);
 501         pet_scop_free(scop);
 502
 503         return p;
 504 }
 505
 506 /* Transform the C source file "input" by rewriting each scop
 507  * through a call to "transform".
 508  * The transformed C code is written to "out".
 509  *
 510  * This is a wrapper around pet_transform_C_source that transforms
 511  * the pet_scop to a ppcg_scop before calling "fn".
 512  */
 513 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
 514         struct ppcg_options *options,
 515         __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
 516                 struct ppcg_scop *scop, void *user), void *user)
 517 {
 518         struct ppcg_transform_data data = { options, fn, user };
 519         return pet_transform_C_source(ctx, input, out, &transform, &data);
 520 }
 521
 522 /* Check consistency of options.
 523  *
 524  * Return -1 on error.
 525  */
 526 static int check_options(isl_ctx *ctx)
 527 {
 528         struct options *options;
 529
 530         options = isl_ctx_peek_options(ctx, &options_args);
 531         if (!options)
 532                 isl_die(ctx, isl_error_internal,
 533                         "unable to find options", return -1);
 534
 535         if (options->ppcg->openmp &&
 536             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 537                 isl_die(ctx, isl_error_invalid,
 538                         "OpenMP requires atomic bounds", return -1);
 539
 540         return 0;
 541 }
 542
 543 int main(int argc, char **argv)
 544 {
 545         int r;
 546         isl_ctx *ctx;
 547         struct options *options;
 548
 549         options = options_new_with_defaults();
 550         assert(options);
 551
 552         ctx = isl_ctx_alloc_with_options(&options_args, options);
 553         isl_options_set_schedule_outer_coincidence(ctx, 1);
 554         isl_options_set_schedule_maximize_band_depth(ctx, 1);
 555         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 556
 557         if (check_options(ctx) < 0)
 558                 r = EXIT_FAILURE;
 559         else if (options->ppcg->target == PPCG_TARGET_CUDA)
 560                 r = generate_cuda(ctx, options->ppcg, options->input);
 561         else
 562                 r = generate_cpu(ctx, options->ppcg, options->input,
 563                                 options->output);
 564
 565         isl_ctx_free(ctx);
 566
 567         return r;
 568 }