ppcg.c

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