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