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 "opencl.h"
  28 #include "cpu.h"
  29
  30 struct options {
  31         struct isl_options *isl;
  32         struct pet_options *pet;
  33         struct ppcg_options *ppcg;
  34         char *input;
  35         char *output;
  36 };
  37
  38 const char *ppcg_version(void);
  39 static void print_version(void)
  40 {
  41         printf("%s", ppcg_version());
  42 }
  43
  44 ISL_ARGS_START(struct options, options_args)
  45 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  46 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
  47 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
  48 ISL_ARG_STR(struct options, output, 'o', NULL,
  49         "filename", NULL, "output filename (c and opencl targets)")
  50 ISL_ARG_ARG(struct options, input, "input", NULL)
  51 ISL_ARG_VERSION(print_version)
  52 ISL_ARGS_END
  53
  54 ISL_ARG_DEF(options, struct options, options_args)
  55
  56 /* Return a pointer to the final path component of "filename" or
  57  * to "filename" itself if it does not contain any components.
  58  */
  59 const char *ppcg_base_name(const char *filename)
  60 {
  61         const char *base;
  62
  63         base = strrchr(filename, '/');
  64         if (base)
  65                 return ++base;
  66         else
  67                 return filename;
  68 }
  69
  70 /* Copy the base name of "input" to "name" and return its length.
  71  * "name" is not NULL terminated.
  72  *
  73  * In particular, remove all leading directory components and
  74  * the final extension, if any.
  75  */
  76 int ppcg_extract_base_name(char *name, const char *input)
  77 {
  78         const char *base;
  79         const char *ext;
  80         int len;
  81
  82         base = ppcg_base_name(input);
  83         ext = strrchr(base, '.');
  84         len = ext ? ext - base : strlen(base);
  85
  86         memcpy(name, base, len);
  87
  88         return len;
  89 }
  90
  91 /* Is "stmt" not a kill statement?
  92  */
  93 static int is_not_kill(struct pet_stmt *stmt)
  94 {
  95         return !pet_stmt_is_kill(stmt);
  96 }
  97
  98 /* Collect the iteration domains of the statements in "scop" that
  99  * satisfy "pred".
 100  */
 101 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
 102         int (*pred)(struct pet_stmt *stmt))
 103 {
 104         int i;
 105         isl_set *domain_i;
 106         isl_union_set *domain;
 107
 108         if (!scop)
 109                 return NULL;
 110
 111         domain = isl_union_set_empty(isl_set_get_space(scop->context));
 112
 113         for (i = 0; i < scop->n_stmt; ++i) {
 114                 struct pet_stmt *stmt = scop->stmts[i];
 115
 116                 if (!pred(stmt))
 117                         continue;
 118
 119                 if (stmt->n_arg > 0)
 120                         isl_die(isl_union_set_get_ctx(domain),
 121                                 isl_error_unsupported,
 122                                 "data dependent conditions not supported",
 123                                 return isl_union_set_free(domain));
 124
 125                 domain_i = isl_set_copy(scop->stmts[i]->domain);
 126                 domain = isl_union_set_add_set(domain, domain_i);
 127         }
 128
 129         return domain;
 130 }
 131
 132 /* Collect the iteration domains of the statements in "scop",
 133  * skipping kill statements.
 134  */
 135 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
 136 {
 137         return collect_domains(scop, &is_not_kill);
 138 }
 139
 140 /* This function is used as a callback to pet_expr_foreach_call_expr
 141  * to detect if there is any call expression in the input expression.
 142  * Assign the value 1 to the integer that "user" points to and
 143  * abort the search since we have found what we were looking for.
 144  */
 145 static int set_has_call(__isl_keep pet_expr *expr, void *user)
 146 {
 147         int *has_call = user;
 148
 149         *has_call = 1;
 150
 151         return -1;
 152 }
 153
 154 /* Does "expr" contain any call expressions?
 155  */
 156 static int expr_has_call(__isl_keep pet_expr *expr)
 157 {
 158         int has_call = 0;
 159
 160         if (pet_expr_foreach_call_expr(expr, &set_has_call, &has_call) < 0 &&
 161             !has_call)
 162                 return -1;
 163
 164         return has_call;
 165 }
 166
 167 /* This function is a callback for pet_tree_foreach_expr.
 168  * If "expr" contains any call (sub)expressions, then set *has_call
 169  * and abort the search.
 170  */
 171 static int check_call(__isl_keep pet_expr *expr, void *user)
 172 {
 173         int *has_call = user;
 174
 175         if (expr_has_call(expr))
 176                 *has_call = 1;
 177
 178         return *has_call ? -1 : 0;
 179 }
 180
 181 /* Does "stmt" contain any call expressions?
 182  */
 183 static int has_call(struct pet_stmt *stmt)
 184 {
 185         int has_call = 0;
 186
 187         if (pet_tree_foreach_expr(stmt->body, &check_call, &has_call) < 0 &&
 188             !has_call)
 189                 return -1;
 190
 191         return has_call;
 192 }
 193
 194 /* Collect the iteration domains of the statements in "scop"
 195  * that contain a call expression.
 196  */
 197 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
 198 {
 199         return collect_domains(scop, &has_call);
 200 }
 201
 202 /* Given a union of "tagged" access relations of the form
 203  *
 204  *      [S_i[...] -> R_j[]] -> A_k[...]
 205  *
 206  * project out the "tags" (R_j[]).
 207  * That is, return a union of relations of the form
 208  *
 209  *      S_i[...] -> A_k[...]
 210  */
 211 static __isl_give isl_union_map *project_out_tags(
 212         __isl_take isl_union_map *umap)
 213 {
 214         isl_union_map *proj;
 215
 216         proj = isl_union_map_universe(isl_union_map_copy(umap));
 217         proj = isl_union_set_unwrap(isl_union_map_domain(proj));
 218         proj = isl_union_map_domain_map(proj);
 219
 220         umap = isl_union_map_apply_domain(umap, proj);
 221
 222         return umap;
 223 }
 224
 225 /* Construct a relation from the iteration domains to tagged iteration
 226  * domains with as range the reference tags that appear
 227  * in any of the reads, writes or kills.
 228  * Store the result in ps->tagger.
 229  *
 230  * For example, if the statement with iteration space S[i,j]
 231  * contains two array references R_1[] and R_2[], then ps->tagger will contain
 232  *
 233  *      { S[i,j] -> [S[i,j] -> R_1[]]; S[i,j] -> [S[i,j] -> R_2[]] }
 234  */
 235 static void compute_tagger(struct ppcg_scop *ps)
 236 {
 237         isl_union_map *tagged, *tagger;
 238
 239         tagged = isl_union_map_copy(ps->tagged_reads);
 240         tagged = isl_union_map_union(tagged,
 241                                 isl_union_map_copy(ps->tagged_may_writes));
 242         tagged = isl_union_map_union(tagged,
 243                                 isl_union_map_copy(ps->tagged_must_kills));
 244
 245         tagger = isl_union_map_universe(tagged);
 246         tagger = isl_union_set_unwrap(isl_union_map_domain(tagger));
 247         tagger = isl_union_map_reverse(isl_union_map_domain_map(tagger));
 248
 249         ps->tagger = tagger;
 250 }
 251
 252 /* Compute the live out accesses, i.e., the writes that are
 253  * potentially not killed by any kills or any other writes, and
 254  * store them in ps->live_out.
 255  *
 256  * We compute the "dependence" of any "kill" (an explicit kill
 257  * or a must write) on any may write.
 258  * The may writes with a "depending" kill are definitely killed.
 259  * The remaining may writes can potentially be live out.
 260  */
 261 static void compute_live_out(struct ppcg_scop *ps)
 262 {
 263         isl_union_map *tagger;
 264         isl_union_map *schedule;
 265         isl_union_map *empty;
 266         isl_union_map *kills;
 267         isl_union_map *exposed;
 268         isl_union_map *covering;
 269
 270         tagger = isl_union_map_copy(ps->tagger);
 271         schedule = isl_union_map_copy(ps->schedule);
 272         schedule = isl_union_map_apply_domain(schedule,
 273                                         isl_union_map_copy(tagger));
 274         empty = isl_union_map_empty(isl_union_set_get_space(ps->domain));
 275         kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
 276                                     isl_union_map_copy(ps->tagged_must_kills));
 277         isl_union_map_compute_flow(kills, empty,
 278                                 isl_union_map_copy(ps->tagged_may_writes),
 279                                 schedule, NULL, &covering, NULL, NULL);
 280         exposed = isl_union_map_copy(ps->tagged_may_writes);
 281         exposed = isl_union_map_subtract_domain(exposed,
 282                                 isl_union_map_domain(covering));
 283         exposed = isl_union_map_apply_range(tagger, exposed);
 284         ps->live_out = exposed;
 285 }
 286
 287 /* Compute the flow dependences and the live_in accesses and store
 288  * the results in ps->dep_flow and ps->live_in.
 289  * A copy of the flow dependences, tagged with the reference tags
 290  * is stored in ps->tagged_dep_flow.
 291  *
 292  * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
 293  * and then project out the tags.
 294  */
 295 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
 296 {
 297         isl_union_map *tagger;
 298         isl_union_map *schedule;
 299         isl_union_map *may_flow;
 300         isl_union_map *live_in, *may_live_in;
 301
 302         tagger = isl_union_map_copy(ps->tagger);
 303         schedule = isl_union_map_copy(ps->schedule);
 304         schedule = isl_union_map_apply_domain(schedule, tagger);
 305         isl_union_map_compute_flow(isl_union_map_copy(ps->tagged_reads),
 306                                 isl_union_map_copy(ps->tagged_must_writes),
 307                                 isl_union_map_copy(ps->tagged_may_writes),
 308                                 schedule, &ps->tagged_dep_flow, &may_flow,
 309                                 &live_in, &may_live_in);
 310         ps->tagged_dep_flow = isl_union_map_union(ps->tagged_dep_flow,
 311                                                         may_flow);
 312         ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
 313         ps->dep_flow = isl_union_map_zip(ps->dep_flow);
 314         ps->dep_flow = isl_union_set_unwrap(isl_union_map_domain(ps->dep_flow));
 315         live_in = isl_union_map_union(live_in, may_live_in);
 316         ps->live_in = project_out_tags(live_in);
 317 }
 318
 319 /* Compute the order dependences that prevent the potential live ranges
 320  * from overlapping.
 321  * "before" contains all pairs of statement iterations where
 322  * the first is executed before the second according to the original schedule.
 323  *
 324  * In particular, construct a union of relations
 325  *
 326  *      [R[...] -> R_1[]] -> [W[...] -> R_2[]]
 327  *
 328  * where [R[...] -> R_1[]] is the range of one or more live ranges
 329  * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
 330  * live ranges (i.e., a write).  Moreover, the read and the write
 331  * access the same memory element and the read occurs before the write
 332  * in the original schedule.
 333  * The scheduler allows some of these dependences to be violated, provided
 334  * the adjacent live ranges are all local (i.e., their domain and range
 335  * are mapped to the same point by the current schedule band).
 336  *
 337  * Note that if a live range is not local, then we need to make
 338  * sure it does not overlap with _any_ other live range, and not
 339  * just with the "previous" and/or the "next" live range.
 340  * We therefore add order dependences between reads and
 341  * _any_ later potential write.
 342  *
 343  * We also need to be careful about writes without a corresponding read.
 344  * They are already prevented from moving past non-local preceding
 345  * intervals, but we also need to prevent them from moving past non-local
 346  * following intervals.  We therefore also add order dependences from
 347  * potential writes that do not appear in any intervals
 348  * to all later potential writes.
 349  * Note that dead code elimination should have removed most of these
 350  * dead writes, but the dead code elimination may not remove all dead writes,
 351  * so we need to consider them to be safe.
 352  */
 353 static void compute_order_dependences(struct ppcg_scop *ps,
 354         __isl_take isl_union_map *before)
 355 {
 356         isl_union_map *reads;
 357         isl_union_map *shared_access;
 358         isl_union_set *matched;
 359         isl_union_map *unmatched;
 360         isl_union_set *domain;
 361
 362         reads = isl_union_map_copy(ps->tagged_reads);
 363         matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
 364         unmatched = isl_union_map_copy(ps->tagged_may_writes);
 365         unmatched = isl_union_map_subtract_domain(unmatched, matched);
 366         reads = isl_union_map_union(reads, unmatched);
 367         shared_access = isl_union_map_copy(ps->tagged_may_writes);
 368         shared_access = isl_union_map_reverse(shared_access);
 369         shared_access = isl_union_map_apply_range(reads, shared_access);
 370         shared_access = isl_union_map_zip(shared_access);
 371         shared_access = isl_union_map_intersect_domain(shared_access,
 372                                                 isl_union_map_wrap(before));
 373         domain = isl_union_map_domain(isl_union_map_copy(shared_access));
 374         shared_access = isl_union_map_zip(shared_access);
 375         ps->dep_order = isl_union_set_unwrap(domain);
 376         ps->tagged_dep_order = shared_access;
 377 }
 378
 379 /* Compute the external false dependences of the program represented by "scop"
 380  * in case live range reordering is allowed.
 381  * "before" contains all pairs of statement iterations where
 382  * the first is executed before the second according to the original schedule.
 383  *
 384  * The anti-dependences are already taken care of by the order dependences.
 385  * The external false dependences are only used to ensure that live-in and
 386  * live-out data is not overwritten by any writes inside the scop.
 387  *
 388  * In particular, the reads from live-in data need to precede any
 389  * later write to the same memory element.
 390  * As to live-out data, the last writes need to remain the last writes.
 391  * That is, any earlier write in the original schedule needs to precede
 392  * the last write to the same memory element in the computed schedule.
 393  * The possible last writes have been computed by compute_live_out.
 394  * They may include kills, but if the last access is a kill,
 395  * then the corresponding dependences will effectively be ignored
 396  * since we do not schedule any kill statements.
 397  *
 398  * Note that the set of live-in and live-out accesses may be
 399  * an overapproximation.  There may therefore be potential writes
 400  * before a live-in access and after a live-out access.
 401  */
 402 static void compute_external_false_dependences(struct ppcg_scop *ps,
 403         __isl_take isl_union_map *before)
 404 {
 405         isl_union_map *shared_access;
 406         isl_union_map *exposed;
 407         isl_union_map *live_in;
 408
 409         exposed = isl_union_map_copy(ps->live_out);
 410
 411         exposed = isl_union_map_reverse(exposed);
 412         shared_access = isl_union_map_copy(ps->may_writes);
 413         shared_access = isl_union_map_apply_range(shared_access, exposed);
 414
 415         ps->dep_external = shared_access;
 416
 417         live_in = isl_union_map_apply_range(isl_union_map_copy(ps->live_in),
 418                     isl_union_map_reverse(isl_union_map_copy(ps->may_writes)));
 419
 420         ps->dep_external = isl_union_map_union(ps->dep_external, live_in);
 421         ps->dep_external = isl_union_map_intersect(ps->dep_external, before);
 422 }
 423
 424 /* Compute the dependences of the program represented by "scop"
 425  * in case live range reordering is allowed.
 426  *
 427  * We compute the actual live ranges and the corresponding order
 428  * false dependences.
 429  */
 430 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
 431 {
 432         isl_union_map *before;
 433
 434         before = isl_union_map_lex_lt_union_map(
 435                         isl_union_map_copy(ps->schedule),
 436                         isl_union_map_copy(ps->schedule));
 437
 438         compute_tagged_flow_dep(ps);
 439         compute_order_dependences(ps, isl_union_map_copy(before));
 440         compute_external_false_dependences(ps, before);
 441 }
 442
 443 /* Compute the potential flow dependences and the potential live in
 444  * accesses.
 445  */
 446 static void compute_flow_dep(struct ppcg_scop *ps)
 447 {
 448         isl_union_map *may_flow;
 449         isl_union_map *may_live_in;
 450
 451         isl_union_map_compute_flow(isl_union_map_copy(ps->reads),
 452                                 isl_union_map_copy(ps->must_writes),
 453                                 isl_union_map_copy(ps->may_writes),
 454                                 isl_union_map_copy(ps->schedule),
 455                                 &ps->dep_flow, &may_flow,
 456                                 &ps->live_in, &may_live_in);
 457
 458         ps->dep_flow = isl_union_map_union(ps->dep_flow, may_flow);
 459         ps->live_in = isl_union_map_union(ps->live_in, may_live_in);
 460 }
 461
 462 /* Compute the dependences of the program represented by "scop".
 463  * Store the computed potential flow dependences
 464  * in scop->dep_flow and the reads with potentially no corresponding writes in
 465  * scop->live_in.
 466  * Store the potential live out accesses in scop->live_out.
 467  * Store the potential false (anti and output) dependences in scop->dep_false.
 468  *
 469  * If live range reordering is allowed, then we compute a separate
 470  * set of order dependences and a set of external false dependences
 471  * in compute_live_range_reordering_dependences.
 472  */
 473 static void compute_dependences(struct ppcg_scop *scop)
 474 {
 475         isl_union_map *dep1, *dep2;
 476         isl_union_map *may_source;
 477
 478         if (!scop)
 479                 return;
 480
 481         compute_live_out(scop);
 482
 483         if (scop->options->live_range_reordering)
 484                 compute_live_range_reordering_dependences(scop);
 485         else if (scop->options->target != PPCG_TARGET_C)
 486                 compute_tagged_flow_dep(scop);
 487         else
 488                 compute_flow_dep(scop);
 489
 490         may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
 491                                         isl_union_map_copy(scop->reads));
 492         isl_union_map_compute_flow(isl_union_map_copy(scop->may_writes),
 493                                 isl_union_map_copy(scop->must_writes),
 494                                 may_source, isl_union_map_copy(scop->schedule),
 495                                 &dep1, &dep2, NULL, NULL);
 496
 497         scop->dep_false = isl_union_map_union(dep1, dep2);
 498         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 499 }
 500
 501 /* Eliminate dead code from ps->domain.
 502  *
 503  * In particular, intersect ps->domain with the (parts of) iteration
 504  * domains that are needed to produce the output or for statement
 505  * iterations that call functions.
 506  *
 507  * We start with the iteration domains that call functions
 508  * and the set of iterations that last write to an array
 509  * (except those that are later killed).
 510  *
 511  * Then we add those statement iterations that produce
 512  * something needed by the "live" statements iterations.
 513  * We keep doing this until no more statement iterations can be added.
 514  * To ensure that the procedure terminates, we compute the affine
 515  * hull of the live iterations (bounded to the original iteration
 516  * domains) each time we have added extra iterations.
 517  */
 518 static void eliminate_dead_code(struct ppcg_scop *ps)
 519 {
 520         isl_union_set *live;
 521         isl_union_map *dep;
 522
 523         live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
 524         if (!isl_union_set_is_empty(ps->call)) {
 525                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 526                 live = isl_union_set_coalesce(live);
 527         }
 528
 529         dep = isl_union_map_copy(ps->dep_flow);
 530         dep = isl_union_map_reverse(dep);
 531
 532         for (;;) {
 533                 isl_union_set *extra;
 534
 535                 extra = isl_union_set_apply(isl_union_set_copy(live),
 536                                             isl_union_map_copy(dep));
 537                 if (isl_union_set_is_subset(extra, live)) {
 538                         isl_union_set_free(extra);
 539                         break;
 540                 }
 541
 542                 live = isl_union_set_union(live, extra);
 543                 live = isl_union_set_affine_hull(live);
 544                 live = isl_union_set_intersect(live,
 545                                             isl_union_set_copy(ps->domain));
 546         }
 547
 548         isl_union_map_free(dep);
 549
 550         ps->domain = isl_union_set_intersect(ps->domain, live);
 551 }
 552
 553 /* Intersect "set" with the set described by "str", taking the NULL
 554  * string to represent the universal set.
 555  */
 556 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 557         const char *str)
 558 {
 559         isl_ctx *ctx;
 560         isl_set *set2;
 561
 562         if (!str)
 563                 return set;
 564
 565         ctx = isl_set_get_ctx(set);
 566         set2 = isl_set_read_from_str(ctx, str);
 567         set = isl_set_intersect(set, set2);
 568
 569         return set;
 570 }
 571
 572 static void *ppcg_scop_free(struct ppcg_scop *ps)
 573 {
 574         if (!ps)
 575                 return NULL;
 576
 577         isl_set_free(ps->context);
 578         isl_union_set_free(ps->domain);
 579         isl_union_set_free(ps->call);
 580         isl_union_map_free(ps->tagged_reads);
 581         isl_union_map_free(ps->reads);
 582         isl_union_map_free(ps->live_in);
 583         isl_union_map_free(ps->tagged_may_writes);
 584         isl_union_map_free(ps->tagged_must_writes);
 585         isl_union_map_free(ps->may_writes);
 586         isl_union_map_free(ps->must_writes);
 587         isl_union_map_free(ps->live_out);
 588         isl_union_map_free(ps->tagged_must_kills);
 589         isl_union_map_free(ps->tagged_dep_flow);
 590         isl_union_map_free(ps->dep_flow);
 591         isl_union_map_free(ps->dep_false);
 592         isl_union_map_free(ps->dep_external);
 593         isl_union_map_free(ps->tagged_dep_order);
 594         isl_union_map_free(ps->dep_order);
 595         isl_union_map_free(ps->schedule);
 596         isl_union_map_free(ps->tagger);
 597         isl_union_map_free(ps->independence);
 598
 599         free(ps);
 600
 601         return NULL;
 602 }
 603
 604 /* Extract a ppcg_scop from a pet_scop.
 605  *
 606  * The constructed ppcg_scop refers to elements from the pet_scop
 607  * so the pet_scop should not be freed before the ppcg_scop.
 608  */
 609 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 610         struct ppcg_options *options)
 611 {
 612         int i;
 613         isl_ctx *ctx;
 614         struct ppcg_scop *ps;
 615
 616         if (!scop)
 617                 return NULL;
 618
 619         ctx = isl_set_get_ctx(scop->context);
 620
 621         ps = isl_calloc_type(ctx, struct ppcg_scop);
 622         if (!ps)
 623                 return NULL;
 624
 625         ps->options = options;
 626         ps->start = pet_loc_get_start(scop->loc);
 627         ps->end = pet_loc_get_end(scop->loc);
 628         ps->context = isl_set_copy(scop->context);
 629         ps->context = set_intersect_str(ps->context, options->ctx);
 630         ps->domain = collect_non_kill_domains(scop);
 631         ps->call = collect_call_domains(scop);
 632         ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
 633         ps->reads = pet_scop_collect_may_reads(scop);
 634         ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
 635         ps->may_writes = pet_scop_collect_may_writes(scop);
 636         ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
 637         ps->must_writes = pet_scop_collect_must_writes(scop);
 638         ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
 639         ps->schedule = pet_scop_collect_schedule(scop);
 640         ps->pet = scop;
 641         ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
 642         for (i = 0; i < scop->n_independence; ++i)
 643                 ps->independence = isl_union_map_union(ps->independence,
 644                         isl_union_map_copy(scop->independences[i]->filter));
 645
 646         compute_tagger(ps);
 647         compute_dependences(ps);
 648         eliminate_dead_code(ps);
 649
 650         if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
 651             !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
 652             !ps->schedule || !ps->independence)
 653                 return ppcg_scop_free(ps);
 654
 655         return ps;
 656 }
 657
 658 /* Internal data structure for ppcg_transform.
 659  */
 660 struct ppcg_transform_data {
 661         struct ppcg_options *options;
 662         __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
 663                 struct ppcg_scop *scop, void *user);
 664         void *user;
 665 };
 666
 667 /* Should we print the original code?
 668  * That is, does "scop" involve any data dependent conditions or
 669  * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
 670  */
 671 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
 672 {
 673         if (!pet_scop_can_build_ast_exprs(scop)) {
 674                 if (options->debug->verbose)
 675                         fprintf(stdout, "Printing original code because "
 676                                 "some index expressions cannot currently "
 677                                 "be printed\n");
 678                 return 1;
 679         }
 680
 681         if (pet_scop_has_data_dependent_conditions(scop)) {
 682                 if (options->debug->verbose)
 683                         fprintf(stdout, "Printing original code because "
 684                                 "input involves data dependent conditions\n");
 685                 return 1;
 686         }
 687
 688         return 0;
 689 }
 690
 691 /* Callback for pet_transform_C_source that transforms
 692  * the given pet_scop to a ppcg_scop before calling the
 693  * ppcg_transform callback.
 694  *
 695  * If "scop" contains any data dependent conditions or if we may
 696  * not be able to print the transformed program, then just print
 697  * the original code.
 698  */
 699 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
 700         struct pet_scop *scop, void *user)
 701 {
 702         struct ppcg_transform_data *data = user;
 703         struct ppcg_scop *ps;
 704
 705         if (print_original(scop, data->options)) {
 706                 p = pet_scop_print_original(scop, p);
 707                 pet_scop_free(scop);
 708                 return p;
 709         }
 710
 711         scop = pet_scop_align_params(scop);
 712         ps = ppcg_scop_from_pet_scop(scop, data->options);
 713
 714         p = data->transform(p, ps, data->user);
 715
 716         ppcg_scop_free(ps);
 717         pet_scop_free(scop);
 718
 719         return p;
 720 }
 721
 722 /* Transform the C source file "input" by rewriting each scop
 723  * through a call to "transform".
 724  * The transformed C code is written to "out".
 725  *
 726  * This is a wrapper around pet_transform_C_source that transforms
 727  * the pet_scop to a ppcg_scop before calling "fn".
 728  */
 729 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
 730         struct ppcg_options *options,
 731         __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
 732                 struct ppcg_scop *scop, void *user), void *user)
 733 {
 734         struct ppcg_transform_data data = { options, fn, user };
 735         return pet_transform_C_source(ctx, input, out, &transform, &data);
 736 }
 737
 738 /* Check consistency of options.
 739  *
 740  * Return -1 on error.
 741  */
 742 static int check_options(isl_ctx *ctx)
 743 {
 744         struct options *options;
 745
 746         options = isl_ctx_peek_options(ctx, &options_args);
 747         if (!options)
 748                 isl_die(ctx, isl_error_internal,
 749                         "unable to find options", return -1);
 750
 751         if (options->ppcg->openmp &&
 752             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 753                 isl_die(ctx, isl_error_invalid,
 754                         "OpenMP requires atomic bounds", return -1);
 755
 756         return 0;
 757 }
 758
 759 int main(int argc, char **argv)
 760 {
 761         int r;
 762         isl_ctx *ctx;
 763         struct options *options;
 764
 765         options = options_new_with_defaults();
 766         assert(options);
 767
 768         ctx = isl_ctx_alloc_with_options(&options_args, options);
 769         isl_options_set_schedule_outer_coincidence(ctx, 1);
 770         isl_options_set_schedule_maximize_band_depth(ctx, 1);
 771         pet_options_set_encapsulate_dynamic_control(ctx, 1);
 772         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 773
 774         if (check_options(ctx) < 0)
 775                 r = EXIT_FAILURE;
 776         else if (options->ppcg->target == PPCG_TARGET_CUDA)
 777                 r = generate_cuda(ctx, options->ppcg, options->input);
 778         else if (options->ppcg->target == PPCG_TARGET_OPENCL)
 779                 r = generate_opencl(ctx, options->ppcg, options->input,
 780                                 options->output);
 781         else
 782                 r = generate_cpu(ctx, options->ppcg, options->input,
 783                                 options->output);
 784
 785         isl_ctx_free(ctx);
 786
 787         return r;
 788 }