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 /* Given a union of "tagged" access relations of the form
 170  *
 171  *      [S_i[...] -> R_j[]] -> A_k[...]
 172  *
 173  * project out the "tags" (R_j[]).
 174  * That is, return a union of relations of the form
 175  *
 176  *      S_i[...] -> A_k[...]
 177  */
 178 static __isl_give isl_union_map *project_out_tags(
 179         __isl_take isl_union_map *umap)
 180 {
 181         isl_union_map *proj;
 182
 183         proj = isl_union_map_universe(isl_union_map_copy(umap));
 184         proj = isl_union_set_unwrap(isl_union_map_domain(proj));
 185         proj = isl_union_map_domain_map(proj);
 186
 187         umap = isl_union_map_apply_domain(umap, proj);
 188
 189         return umap;
 190 }
 191
 192 /* Construct a relation from the iteration domains to tagged iteration
 193  * domains with as range the reference tags that appear
 194  * in any of the reads, writes or kills.
 195  * Store the result in ps->tagger.
 196  *
 197  * For example, if the statement with iteration space S[i,j]
 198  * contains two array references R_1[] and R_2[], then ps->tagger will contain
 199  *
 200  *      { S[i,j] -> [S[i,j] -> R_1[]]; S[i,j] -> [S[i,j] -> R_2[]] }
 201  */
 202 static void compute_tagger(struct ppcg_scop *ps)
 203 {
 204         isl_union_map *tagged, *tagger;
 205
 206         tagged = isl_union_map_copy(ps->tagged_reads);
 207         tagged = isl_union_map_union(tagged,
 208                                 isl_union_map_copy(ps->tagged_may_writes));
 209         tagged = isl_union_map_union(tagged,
 210                                 isl_union_map_copy(ps->tagged_must_kills));
 211
 212         tagger = isl_union_map_universe(tagged);
 213         tagger = isl_union_set_unwrap(isl_union_map_domain(tagger));
 214         tagger = isl_union_map_reverse(isl_union_map_domain_map(tagger));
 215
 216         ps->tagger = tagger;
 217 }
 218
 219 /* Compute the live out accesses, i.e., the writes that are
 220  * potentially not killed by any kills or any other writes, and
 221  * store them in ps->live_out.
 222  *
 223  * We compute the "dependence" of any "kill" (an explicit kill
 224  * or a must write) on any may write.
 225  * The may writes with a "depending" kill are definitely killed.
 226  * The remaining may writes can potentially be live out.
 227  */
 228 static void compute_live_out(struct ppcg_scop *ps)
 229 {
 230         isl_union_map *tagger;
 231         isl_union_map *schedule;
 232         isl_union_map *empty;
 233         isl_union_map *kills;
 234         isl_union_map *exposed;
 235         isl_union_map *covering;
 236
 237         tagger = isl_union_map_copy(ps->tagger);
 238         schedule = isl_union_map_copy(ps->schedule);
 239         schedule = isl_union_map_apply_domain(schedule,
 240                                         isl_union_map_copy(tagger));
 241         empty = isl_union_map_empty(isl_union_set_get_space(ps->domain));
 242         kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
 243                                     isl_union_map_copy(ps->tagged_must_kills));
 244         isl_union_map_compute_flow(kills, empty,
 245                                 isl_union_map_copy(ps->tagged_may_writes),
 246                                 schedule, NULL, &covering, NULL, NULL);
 247         exposed = isl_union_map_copy(ps->tagged_may_writes);
 248         exposed = isl_union_map_subtract_domain(exposed,
 249                                 isl_union_map_domain(covering));
 250         exposed = isl_union_map_apply_range(tagger, exposed);
 251         ps->live_out = exposed;
 252 }
 253
 254 /* Compute the flow dependences and the live_in accesses and store
 255  * the results in ps->dep_flow and ps->live_in.
 256  * A copy of the flow dependences, tagged with the reference tags
 257  * is stored in ps->tagged_dep_flow.
 258  *
 259  * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
 260  * and then project out the tags.
 261  */
 262 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
 263 {
 264         isl_union_map *tagger;
 265         isl_union_map *schedule;
 266         isl_union_map *may_flow;
 267         isl_union_map *live_in, *may_live_in;
 268
 269         tagger = isl_union_map_copy(ps->tagger);
 270         schedule = isl_union_map_copy(ps->schedule);
 271         schedule = isl_union_map_apply_domain(schedule, tagger);
 272         isl_union_map_compute_flow(isl_union_map_copy(ps->tagged_reads),
 273                                 isl_union_map_copy(ps->tagged_must_writes),
 274                                 isl_union_map_copy(ps->tagged_may_writes),
 275                                 schedule, &ps->tagged_dep_flow, &may_flow,
 276                                 &live_in, &may_live_in);
 277         ps->tagged_dep_flow = isl_union_map_union(ps->tagged_dep_flow,
 278                                                         may_flow);
 279         ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
 280         ps->dep_flow = isl_union_map_zip(ps->dep_flow);
 281         ps->dep_flow = isl_union_set_unwrap(isl_union_map_domain(ps->dep_flow));
 282         live_in = isl_union_map_union(live_in, may_live_in);
 283         ps->live_in = project_out_tags(live_in);
 284 }
 285
 286 /* Compute the potential flow dependences and the potential live in
 287  * accesses.
 288  */
 289 static void compute_flow_dep(struct ppcg_scop *ps)
 290 {
 291         isl_union_map *may_flow;
 292         isl_union_map *may_live_in;
 293
 294         isl_union_map_compute_flow(isl_union_map_copy(ps->reads),
 295                                 isl_union_map_copy(ps->must_writes),
 296                                 isl_union_map_copy(ps->may_writes),
 297                                 isl_union_map_copy(ps->schedule),
 298                                 &ps->dep_flow, &may_flow,
 299                                 &ps->live_in, &may_live_in);
 300
 301         ps->dep_flow = isl_union_map_union(ps->dep_flow, may_flow);
 302         ps->live_in = isl_union_map_union(ps->live_in, may_live_in);
 303 }
 304
 305 /* Compute the dependences of the program represented by "scop".
 306  * Store the computed potential flow dependences
 307  * in scop->dep_flow and the reads with potentially no corresponding writes in
 308  * scop->live_in.
 309  * Store the potential live out accesses in scop->live_out.
 310  * Store the potential false (anti and output) dependences in scop->dep_false.
 311  */
 312 static void compute_dependences(struct ppcg_scop *scop)
 313 {
 314         isl_union_map *dep1, *dep2;
 315         isl_union_map *may_source;
 316
 317         if (!scop)
 318                 return;
 319
 320         compute_live_out(scop);
 321
 322         if (scop->options->target != PPCG_TARGET_C)
 323                 compute_tagged_flow_dep(scop);
 324         else
 325                 compute_flow_dep(scop);
 326
 327         may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
 328                                         isl_union_map_copy(scop->reads));
 329         isl_union_map_compute_flow(isl_union_map_copy(scop->may_writes),
 330                                 isl_union_map_copy(scop->must_writes),
 331                                 may_source, isl_union_map_copy(scop->schedule),
 332                                 &dep1, &dep2, NULL, NULL);
 333
 334         scop->dep_false = isl_union_map_union(dep1, dep2);
 335         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 336 }
 337
 338 /* Eliminate dead code from ps->domain.
 339  *
 340  * In particular, intersect ps->domain with the (parts of) iteration
 341  * domains that are needed to produce the output or for statement
 342  * iterations that call functions.
 343  *
 344  * We start with the iteration domains that call functions
 345  * and the set of iterations that last write to an array
 346  * (except those that are later killed).
 347  *
 348  * Then we add those statement iterations that produce
 349  * something needed by the "live" statements iterations.
 350  * We keep doing this until no more statement iterations can be added.
 351  * To ensure that the procedure terminates, we compute the affine
 352  * hull of the live iterations (bounded to the original iteration
 353  * domains) each time we have added extra iterations.
 354  */
 355 static void eliminate_dead_code(struct ppcg_scop *ps)
 356 {
 357         isl_union_set *live;
 358         isl_union_map *dep;
 359
 360         live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
 361         if (!isl_union_set_is_empty(ps->call)) {
 362                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 363                 live = isl_union_set_coalesce(live);
 364         }
 365
 366         dep = isl_union_map_copy(ps->dep_flow);
 367         dep = isl_union_map_reverse(dep);
 368
 369         for (;;) {
 370                 isl_union_set *extra;
 371
 372                 extra = isl_union_set_apply(isl_union_set_copy(live),
 373                                             isl_union_map_copy(dep));
 374                 if (isl_union_set_is_subset(extra, live)) {
 375                         isl_union_set_free(extra);
 376                         break;
 377                 }
 378
 379                 live = isl_union_set_union(live, extra);
 380                 live = isl_union_set_affine_hull(live);
 381                 live = isl_union_set_intersect(live,
 382                                             isl_union_set_copy(ps->domain));
 383         }
 384
 385         isl_union_map_free(dep);
 386
 387         ps->domain = isl_union_set_intersect(ps->domain, live);
 388 }
 389
 390 /* Intersect "set" with the set described by "str", taking the NULL
 391  * string to represent the universal set.
 392  */
 393 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 394         const char *str)
 395 {
 396         isl_ctx *ctx;
 397         isl_set *set2;
 398
 399         if (!str)
 400                 return set;
 401
 402         ctx = isl_set_get_ctx(set);
 403         set2 = isl_set_read_from_str(ctx, str);
 404         set = isl_set_intersect(set, set2);
 405
 406         return set;
 407 }
 408
 409 /* Does "expr" involve any data dependent accesses?
 410  */
 411 static int expr_has_data_dependent_accesses(struct pet_expr *expr)
 412 {
 413         int i;
 414
 415         for (i = 0; i < expr->n_arg; ++i)
 416                 if (expr_has_data_dependent_accesses(expr->args[i]))
 417                         return 1;
 418
 419         if (expr->type == pet_expr_access && expr->n_arg > 0)
 420                 return 1;
 421
 422         return 0;
 423 }
 424
 425 /* Does "stmt" contain any data dependent accesses?
 426  */
 427 static int stmt_has_data_dependent_accesses(struct pet_stmt *stmt)
 428 {
 429         return expr_has_data_dependent_accesses(stmt->body);
 430 }
 431
 432 /* Does "scop" contain any data dependent accesses?
 433  */
 434 static int scop_has_data_dependent_accesses(struct pet_scop *scop)
 435 {
 436         int i;
 437
 438         if (!scop)
 439                 return -1;
 440         for (i = 0; i < scop->n_stmt; ++i)
 441                 if (stmt_has_data_dependent_accesses(scop->stmts[i]))
 442                         return 1;
 443
 444         return 0;
 445 }
 446
 447 static void *ppcg_scop_free(struct ppcg_scop *ps)
 448 {
 449         if (!ps)
 450                 return NULL;
 451
 452         isl_set_free(ps->context);
 453         isl_union_set_free(ps->domain);
 454         isl_union_set_free(ps->call);
 455         isl_union_map_free(ps->tagged_reads);
 456         isl_union_map_free(ps->reads);
 457         isl_union_map_free(ps->live_in);
 458         isl_union_map_free(ps->tagged_may_writes);
 459         isl_union_map_free(ps->tagged_must_writes);
 460         isl_union_map_free(ps->may_writes);
 461         isl_union_map_free(ps->must_writes);
 462         isl_union_map_free(ps->live_out);
 463         isl_union_map_free(ps->tagged_must_kills);
 464         isl_union_map_free(ps->tagged_dep_flow);
 465         isl_union_map_free(ps->dep_flow);
 466         isl_union_map_free(ps->dep_false);
 467         isl_union_map_free(ps->schedule);
 468         isl_union_map_free(ps->tagger);
 469
 470         free(ps);
 471
 472         return NULL;
 473 }
 474
 475 /* Extract a ppcg_scop from a pet_scop.
 476  *
 477  * The constructed ppcg_scop refers to elements from the pet_scop
 478  * so the pet_scop should not be freed before the ppcg_scop.
 479  */
 480 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 481         struct ppcg_options *options)
 482 {
 483         isl_ctx *ctx;
 484         struct ppcg_scop *ps;
 485
 486         if (!scop)
 487                 return NULL;
 488
 489         ctx = isl_set_get_ctx(scop->context);
 490
 491         ps = isl_calloc_type(ctx, struct ppcg_scop);
 492         if (!ps)
 493                 return NULL;
 494
 495         ps->options = options;
 496         ps->start = scop->start;
 497         ps->end = scop->end;
 498         ps->context = isl_set_copy(scop->context);
 499         ps->context = set_intersect_str(ps->context, options->ctx);
 500         ps->domain = collect_non_kill_domains(scop);
 501         ps->call = collect_call_domains(scop);
 502         ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
 503         ps->reads = pet_scop_collect_may_reads(scop);
 504         ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
 505         ps->may_writes = pet_scop_collect_may_writes(scop);
 506         ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
 507         ps->must_writes = pet_scop_collect_must_writes(scop);
 508         ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
 509         ps->schedule = pet_scop_collect_schedule(scop);
 510         ps->n_type = scop->n_type;
 511         ps->types = scop->types;
 512         ps->n_array = scop->n_array;
 513         ps->arrays = scop->arrays;
 514         ps->n_stmt = scop->n_stmt;
 515         ps->stmts = scop->stmts;
 516
 517         compute_tagger(ps);
 518         compute_dependences(ps);
 519         eliminate_dead_code(ps);
 520
 521         if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
 522             !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
 523             !ps->schedule)
 524                 return ppcg_scop_free(ps);
 525
 526         return ps;
 527 }
 528
 529 /* Internal data structure for ppcg_transform.
 530  */
 531 struct ppcg_transform_data {
 532         struct ppcg_options *options;
 533         __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
 534                 struct ppcg_scop *scop, void *user);
 535         void *user;
 536 };
 537
 538 /* Callback for pet_transform_C_source that transforms
 539  * the given pet_scop to a ppcg_scop before calling the
 540  * ppcg_transform callback.
 541  */
 542 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
 543         struct pet_scop *scop, void *user)
 544 {
 545         struct ppcg_transform_data *data = user;
 546         struct ppcg_scop *ps;
 547
 548         if (pet_scop_has_data_dependent_conditions(scop)) {
 549                 p = pet_scop_print_original(scop, p);
 550                 pet_scop_free(scop);
 551                 return p;
 552         }
 553
 554         scop = pet_scop_align_params(scop);
 555         ps = ppcg_scop_from_pet_scop(scop, data->options);
 556
 557         p = data->transform(p, ps, data->user);
 558
 559         ppcg_scop_free(ps);
 560         pet_scop_free(scop);
 561
 562         return p;
 563 }
 564
 565 /* Transform the C source file "input" by rewriting each scop
 566  * through a call to "transform".
 567  * The transformed C code is written to "out".
 568  *
 569  * This is a wrapper around pet_transform_C_source that transforms
 570  * the pet_scop to a ppcg_scop before calling "fn".
 571  */
 572 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
 573         struct ppcg_options *options,
 574         __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
 575                 struct ppcg_scop *scop, void *user), void *user)
 576 {
 577         struct ppcg_transform_data data = { options, fn, user };
 578         return pet_transform_C_source(ctx, input, out, &transform, &data);
 579 }
 580
 581 /* Check consistency of options.
 582  *
 583  * Return -1 on error.
 584  */
 585 static int check_options(isl_ctx *ctx)
 586 {
 587         struct options *options;
 588
 589         options = isl_ctx_peek_options(ctx, &options_args);
 590         if (!options)
 591                 isl_die(ctx, isl_error_internal,
 592                         "unable to find options", return -1);
 593
 594         if (options->ppcg->openmp &&
 595             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 596                 isl_die(ctx, isl_error_invalid,
 597                         "OpenMP requires atomic bounds", return -1);
 598
 599         return 0;
 600 }
 601
 602 int main(int argc, char **argv)
 603 {
 604         int r;
 605         isl_ctx *ctx;
 606         struct options *options;
 607
 608         options = options_new_with_defaults();
 609         assert(options);
 610
 611         ctx = isl_ctx_alloc_with_options(&options_args, options);
 612         isl_options_set_schedule_outer_coincidence(ctx, 1);
 613         isl_options_set_schedule_maximize_band_depth(ctx, 1);
 614         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 615
 616         if (check_options(ctx) < 0)
 617                 r = EXIT_FAILURE;
 618         else if (options->ppcg->target == PPCG_TARGET_CUDA)
 619                 r = generate_cuda(ctx, options->ppcg, options->input);
 620         else
 621                 r = generate_cpu(ctx, options->ppcg, options->input,
 622                                 options->output);
 623
 624         isl_ctx_free(ctx);
 625
 626         return r;
 627 }