ppcg.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <assert.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <isl/ctx.h>
  15 #include <isl/flow.h>
  16 #include <isl/options.h>
  17 #include <isl/schedule.h>
  18 #include <isl/ast_build.h>
  19 #include <pet.h>
  20 #include "ppcg.h"
  21 #include "ppcg_options.h"
  22 #include "cuda.h"
  23 #include "cpu.h"
  24
  25 struct options {
  26         struct isl_options *isl;
  27         struct pet_options *pet;
  28         struct ppcg_options *ppcg;
  29         char *input;
  30         char *output;
  31 };
  32
  33 const char *ppcg_version(void);
  34 static void print_version(void)
  35 {
  36         printf("%s", ppcg_version());
  37 }
  38
  39 ISL_ARGS_START(struct options, options_args)
  40 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
  41 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
  42 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
  43 ISL_ARG_STR(struct options, output, 'o', NULL,
  44         "filename", NULL, "output filename (c target)")
  45 ISL_ARG_ARG(struct options, input, "input", NULL)
  46 ISL_ARG_VERSION(print_version)
  47 ISL_ARGS_END
  48
  49 ISL_ARG_DEF(options, struct options, options_args)
  50
  51 /* Is "stmt" a kill statement?
  52  */
  53 static int is_kill(struct pet_stmt *stmt)
  54 {
  55         if (stmt->body->type != pet_expr_unary)
  56                 return 0;
  57         return stmt->body->op == pet_op_kill;
  58 }
  59
  60 /* Is "stmt" not a kill statement?
  61  */
  62 static int is_not_kill(struct pet_stmt *stmt)
  63 {
  64         return !is_kill(stmt);
  65 }
  66
  67 /* Collect the iteration domains of the statements in "scop" that
  68  * satisfy "pred".
  69  */
  70 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
  71         int (*pred)(struct pet_stmt *stmt))
  72 {
  73         int i;
  74         isl_set *domain_i;
  75         isl_union_set *domain;
  76
  77         if (!scop)
  78                 return NULL;
  79
  80         domain = isl_union_set_empty(isl_set_get_space(scop->context));
  81
  82         for (i = 0; i < scop->n_stmt; ++i) {
  83                 struct pet_stmt *stmt = scop->stmts[i];
  84
  85                 if (!pred(stmt))
  86                         continue;
  87                 domain_i = isl_set_copy(scop->stmts[i]->domain);
  88                 domain = isl_union_set_add_set(domain, domain_i);
  89         }
  90
  91         return domain;
  92 }
  93
  94 /* Collect the iteration domains of the statements in "scop",
  95  * skipping kill statements.
  96  */
  97 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
  98 {
  99         return collect_domains(scop, &is_not_kill);
 100 }
 101
 102 /* Does "expr" contain any call expressions?
 103  */
 104 static int expr_has_call(struct pet_expr *expr)
 105 {
 106         int i;
 107
 108         if (expr->type == pet_expr_call)
 109                 return 1;
 110
 111         for (i = 0; i < expr->n_arg; ++i)
 112                 if (expr_has_call(expr->args[i]))
 113                         return 1;
 114
 115         return 0;
 116 }
 117
 118 /* Does "stmt" contain any call expressions?
 119  */
 120 static int has_call(struct pet_stmt *stmt)
 121 {
 122         return expr_has_call(stmt->body);
 123 }
 124
 125 /* Collect the iteration domains of the statements in "scop"
 126  * that contain a call expression.
 127  */
 128 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
 129 {
 130         return collect_domains(scop, &has_call);
 131 }
 132
 133 /* Collect all kill accesses in "scop".
 134  */
 135 static __isl_give isl_union_map *collect_kills(struct pet_scop *scop)
 136 {
 137         int i;
 138         isl_union_map *kills;
 139
 140         if (!scop)
 141                 return NULL;
 142
 143         kills = isl_union_map_empty(isl_set_get_space(scop->context));
 144
 145         for (i = 0; i < scop->n_stmt; ++i) {
 146                 struct pet_stmt *stmt = scop->stmts[i];
 147                 isl_map *kill_i;
 148
 149                 if (!is_kill(stmt))
 150                         continue;
 151                 kill_i = isl_map_copy(stmt->body->args[0]->acc.access);
 152                 kill_i = isl_map_intersect_domain(kill_i,
 153                                                     isl_set_copy(stmt->domain));
 154                 kills = isl_union_map_add_map(kills, kill_i);
 155         }
 156
 157         return kills;
 158 }
 159
 160 /* Compute the dependences of the program represented by "scop".
 161  * Store the computed flow dependences
 162  * in scop->dep_flow and the reads with no corresponding writes in
 163  * scop->live_in.
 164  * Store the false (anti and output) dependences in scop->dep_false.
 165  */
 166 static void compute_dependences(struct ppcg_scop *scop)
 167 {
 168         isl_union_map *empty;
 169         isl_union_map *dep1, *dep2;
 170
 171         if (!scop)
 172                 return;
 173
 174         empty = isl_union_map_empty(isl_union_set_get_space(scop->domain));
 175         isl_union_map_compute_flow(isl_union_map_copy(scop->reads),
 176                                 isl_union_map_copy(scop->writes), empty,
 177                                 isl_union_map_copy(scop->schedule),
 178                                 &scop->dep_flow, NULL, &scop->live_in, NULL);
 179
 180         isl_union_map_compute_flow(isl_union_map_copy(scop->writes),
 181                                 isl_union_map_copy(scop->writes),
 182                                 isl_union_map_copy(scop->reads),
 183                                 isl_union_map_copy(scop->schedule),
 184                                 &dep1, &dep2, NULL, NULL);
 185
 186         scop->dep_false = isl_union_map_union(dep1, dep2);
 187         scop->dep_false = isl_union_map_coalesce(scop->dep_false);
 188 }
 189
 190 /* Eliminate dead code from ps->domain.
 191  *
 192  * In particular, intersect ps->domain with the (parts of) iteration
 193  * domains that are needed to produce the output or for statement
 194  * iterations that call functions.
 195  *
 196  * We start with the iteration domains that call functions
 197  * and the set of iterations that last write to an array
 198  * (except those that are later killed).
 199  *
 200  * Then we add those statement iterations that produce
 201  * something needed by the "live" statements iterations.
 202  * We keep doing this until no more statement iterations can be added.
 203  * To ensure that the procedure terminates, we compute the affine
 204  * hull of the live iterations (bounded to the original iteration
 205  * domains) each time we have added extra iterations.
 206  */
 207 static void eliminate_dead_code(struct ppcg_scop *ps)
 208 {
 209         isl_union_map *exposed;
 210         isl_union_set *live;
 211         isl_union_map *dep;
 212
 213         exposed = isl_union_map_union(isl_union_map_copy(ps->writes),
 214                                             isl_union_map_copy(ps->kills));
 215         exposed = isl_union_map_reverse(exposed);
 216         exposed = isl_union_map_apply_range(exposed,
 217                                             isl_union_map_copy(ps->schedule));
 218         exposed = isl_union_map_lexmax(exposed);
 219         exposed = isl_union_map_apply_range(exposed,
 220                     isl_union_map_reverse(isl_union_map_copy(ps->schedule)));
 221
 222         live = isl_union_map_range(exposed);
 223         if (!isl_union_set_is_empty(ps->call)) {
 224                 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
 225                 live = isl_union_set_coalesce(live);
 226         }
 227
 228         dep = isl_union_map_copy(ps->dep_flow);
 229         dep = isl_union_map_reverse(dep);
 230
 231         for (;;) {
 232                 isl_union_set *extra;
 233
 234                 extra = isl_union_set_apply(isl_union_set_copy(live),
 235                                             isl_union_map_copy(dep));
 236                 if (isl_union_set_is_subset(extra, live)) {
 237                         isl_union_set_free(extra);
 238                         break;
 239                 }
 240
 241                 live = isl_union_set_union(live, extra);
 242                 live = isl_union_set_affine_hull(live);
 243                 live = isl_union_set_intersect(live,
 244                                             isl_union_set_copy(ps->domain));
 245         }
 246
 247         isl_union_map_free(dep);
 248
 249         ps->domain = isl_union_set_intersect(ps->domain, live);
 250 }
 251
 252 /* Intersect "set" with the set described by "str", taking the NULL
 253  * string to represent the universal set.
 254  */
 255 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
 256         const char *str)
 257 {
 258         isl_ctx *ctx;
 259         isl_set *set2;
 260
 261         if (!str)
 262                 return set;
 263
 264         ctx = isl_set_get_ctx(set);
 265         set2 = isl_set_read_from_str(ctx, str);
 266         set = isl_set_intersect(set, set2);
 267
 268         return set;
 269 }
 270
 271 /* Extract a ppcg_scop from a pet_scop.
 272  *
 273  * The constructed ppcg_scop refers to elements from the pet_scop
 274  * so the pet_scop should not be freed before the ppcg_scop.
 275  */
 276 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
 277         struct ppcg_options *options)
 278 {
 279         isl_ctx *ctx;
 280         struct ppcg_scop *ps;
 281
 282         if (!scop)
 283                 return NULL;
 284
 285         ctx = isl_set_get_ctx(scop->context);
 286
 287         ps = isl_calloc_type(ctx, struct ppcg_scop);
 288         if (!ps)
 289                 return NULL;
 290
 291         ps->start = scop->start;
 292         ps->end = scop->end;
 293         ps->context = isl_set_copy(scop->context);
 294         ps->context = set_intersect_str(ps->context, options->ctx);
 295         ps->domain = collect_non_kill_domains(scop);
 296         ps->call = collect_call_domains(scop);
 297         ps->reads = pet_scop_collect_reads(scop);
 298         ps->writes = pet_scop_collect_writes(scop);
 299         ps->kills = collect_kills(scop);
 300         ps->schedule = pet_scop_collect_schedule(scop);
 301         ps->n_array = scop->n_array;
 302         ps->arrays = scop->arrays;
 303         ps->n_stmt = scop->n_stmt;
 304         ps->stmts = scop->stmts;
 305
 306         compute_dependences(ps);
 307         eliminate_dead_code(ps);
 308
 309         return ps;
 310 }
 311
 312 static void ppcg_scop_free(struct ppcg_scop *ps)
 313 {
 314         if (!ps)
 315                 return;
 316
 317         isl_set_free(ps->context);
 318         isl_union_set_free(ps->domain);
 319         isl_union_set_free(ps->call);
 320         isl_union_map_free(ps->reads);
 321         isl_union_map_free(ps->live_in);
 322         isl_union_map_free(ps->writes);
 323         isl_union_map_free(ps->kills);
 324         isl_union_map_free(ps->dep_flow);
 325         isl_union_map_free(ps->dep_false);
 326         isl_union_map_free(ps->schedule);
 327
 328         free(ps);
 329 }
 330
 331 /* Check consistency of options.
 332  *
 333  * Return -1 on error.
 334  */
 335 static int check_options(isl_ctx *ctx)
 336 {
 337         struct options *options;
 338
 339         options = isl_ctx_peek_options(ctx, &options_args);
 340         if (!options)
 341                 isl_die(ctx, isl_error_internal,
 342                         "unable to find options", return -1);
 343
 344         if (options->ppcg->openmp &&
 345             !isl_options_get_ast_build_atomic_upper_bound(ctx))
 346                 isl_die(ctx, isl_error_invalid,
 347                         "OpenMP requires atomic bounds", return -1);
 348
 349         return 0;
 350 }
 351
 352 /* Extract a model from the input file, transform the model and
 353  * write out the result to the output file(s).
 354  */
 355 static int transform(isl_ctx *ctx)
 356 {
 357         int r;
 358         struct pet_scop *scop;
 359         struct ppcg_scop *ps;
 360         struct options *options;
 361
 362         options = isl_ctx_peek_options(ctx, &options_args);
 363         if (!options)
 364                 isl_die(ctx, isl_error_internal,
 365                         "unable to find options", return EXIT_FAILURE);
 366
 367         scop = pet_scop_extract_from_C_source(ctx, options->input, NULL);
 368         scop = pet_scop_align_params(scop);
 369         ps = ppcg_scop_from_pet_scop(scop, options->ppcg);
 370
 371         if (options->ppcg->target == PPCG_TARGET_CUDA)
 372                 r = generate_cuda(ctx, ps, options->ppcg, options->input);
 373         else
 374                 r = generate_cpu(ctx, ps, options->ppcg, options->input,
 375                                 options->output);
 376
 377         ppcg_scop_free(ps);
 378         pet_scop_free(scop);
 379
 380         return r;
 381 }
 382
 383 int main(int argc, char **argv)
 384 {
 385         int r;
 386         isl_ctx *ctx;
 387         struct options *options;
 388
 389         options = options_new_with_defaults();
 390         assert(options);
 391
 392         ctx = isl_ctx_alloc_with_options(&options_args, options);
 393         isl_options_set_schedule_outer_zero_distance(ctx, 1);
 394         argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 395
 396         if (check_options(ctx) < 0)
 397                 r = EXIT_FAILURE;
 398         else
 399                 r = transform(ctx);
 400
 401         isl_ctx_free(ctx);
 402
 403         return r;
 404 }