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