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