gpu.c: create_kernel_vars: improve error handling
[ppcg.git] / ppcg.c
blobc32a0ae1fb49807011879bff4b6519daadc8cbbc
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <assert.h>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <isl/ctx.h>
19 #include <isl/flow.h>
20 #include <isl/options.h>
21 #include <isl/schedule.h>
22 #include <isl/ast_build.h>
23 #include <isl/schedule.h>
24 #include <pet.h>
25 #include "ppcg.h"
26 #include "ppcg_options.h"
27 #include "cuda.h"
28 #include "opencl.h"
29 #include "cpu.h"
31 struct options {
32 struct isl_options *isl;
33 struct pet_options *pet;
34 struct ppcg_options *ppcg;
35 char *input;
36 char *output;
39 const char *ppcg_version(void);
40 static void print_version(void)
42 printf("%s", ppcg_version());
45 ISL_ARGS_START(struct options, options_args)
46 ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
47 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
48 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
49 ISL_ARG_STR(struct options, output, 'o', NULL,
50 "filename", NULL, "output filename (c and opencl targets)")
51 ISL_ARG_ARG(struct options, input, "input", NULL)
52 ISL_ARG_VERSION(print_version)
53 ISL_ARGS_END
55 ISL_ARG_DEF(options, struct options, options_args)
57 /* Return a pointer to the final path component of "filename" or
58 * to "filename" itself if it does not contain any components.
60 const char *ppcg_base_name(const char *filename)
62 const char *base;
64 base = strrchr(filename, '/');
65 if (base)
66 return ++base;
67 else
68 return filename;
71 /* Copy the base name of "input" to "name" and return its length.
72 * "name" is not NULL terminated.
74 * In particular, remove all leading directory components and
75 * the final extension, if any.
77 int ppcg_extract_base_name(char *name, const char *input)
79 const char *base;
80 const char *ext;
81 int len;
83 base = ppcg_base_name(input);
84 ext = strrchr(base, '.');
85 len = ext ? ext - base : strlen(base);
87 memcpy(name, base, len);
89 return len;
92 /* Collect all variable names that are in use in "scop".
93 * In particular, collect all parameters in the context and
94 * all the array names.
95 * Store these names in an isl_id_to_ast_expr by mapping
96 * them to a dummy value (0).
98 static __isl_give isl_id_to_ast_expr *collect_names(struct pet_scop *scop)
100 int i, n;
101 isl_ctx *ctx;
102 isl_ast_expr *zero;
103 isl_id_to_ast_expr *names;
105 ctx = isl_set_get_ctx(scop->context);
107 n = isl_set_dim(scop->context, isl_dim_param);
109 names = isl_id_to_ast_expr_alloc(ctx, n + scop->n_array);
110 zero = isl_ast_expr_from_val(isl_val_zero(ctx));
112 for (i = 0; i < n; ++i) {
113 isl_id *id;
115 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
116 names = isl_id_to_ast_expr_set(names,
117 id, isl_ast_expr_copy(zero));
120 for (i = 0; i < scop->n_array; ++i) {
121 struct pet_array *array = scop->arrays[i];
122 isl_id *id;
124 id = isl_set_get_tuple_id(array->extent);
125 names = isl_id_to_ast_expr_set(names,
126 id, isl_ast_expr_copy(zero));
129 isl_ast_expr_free(zero);
131 return names;
134 /* Return an isl_id called "prefix%d", with "%d" set to "i".
135 * If an isl_id with such a name already appears among the variable names
136 * of "scop", then adjust the name to "prefix%d_%d".
138 static __isl_give isl_id *generate_name(struct ppcg_scop *scop,
139 const char *prefix, int i)
141 int j;
142 char name[16];
143 isl_ctx *ctx;
144 isl_id *id;
145 int has_name;
147 ctx = isl_set_get_ctx(scop->context);
148 snprintf(name, sizeof(name), "%s%d", prefix, i);
149 id = isl_id_alloc(ctx, name, NULL);
151 j = 0;
152 while ((has_name = isl_id_to_ast_expr_has(scop->names, id)) == 1) {
153 isl_id_free(id);
154 snprintf(name, sizeof(name), "%s%d_%d", prefix, i, j++);
155 id = isl_id_alloc(ctx, name, NULL);
158 return has_name < 0 ? isl_id_free(id) : id;
161 /* Return a list of "n" isl_ids of the form "prefix%d".
162 * If an isl_id with such a name already appears among the variable names
163 * of "scop", then adjust the name to "prefix%d_%d".
165 __isl_give isl_id_list *ppcg_scop_generate_names(struct ppcg_scop *scop,
166 int n, const char *prefix)
168 int i;
169 char name[10];
170 isl_ctx *ctx;
171 isl_id_list *names;
173 ctx = isl_set_get_ctx(scop->context);
174 names = isl_id_list_alloc(ctx, n);
175 for (i = 0; i < n; ++i) {
176 isl_id *id;
178 id = generate_name(scop, prefix, i);
179 names = isl_id_list_add(names, id);
182 return names;
185 /* Is "stmt" not a kill statement?
187 static int is_not_kill(struct pet_stmt *stmt)
189 return !pet_stmt_is_kill(stmt);
192 /* Collect the iteration domains of the statements in "scop" that
193 * satisfy "pred".
195 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
196 int (*pred)(struct pet_stmt *stmt))
198 int i;
199 isl_set *domain_i;
200 isl_union_set *domain;
202 if (!scop)
203 return NULL;
205 domain = isl_union_set_empty(isl_set_get_space(scop->context));
207 for (i = 0; i < scop->n_stmt; ++i) {
208 struct pet_stmt *stmt = scop->stmts[i];
210 if (!pred(stmt))
211 continue;
213 if (stmt->n_arg > 0)
214 isl_die(isl_union_set_get_ctx(domain),
215 isl_error_unsupported,
216 "data dependent conditions not supported",
217 return isl_union_set_free(domain));
219 domain_i = isl_set_copy(scop->stmts[i]->domain);
220 domain = isl_union_set_add_set(domain, domain_i);
223 return domain;
226 /* Collect the iteration domains of the statements in "scop",
227 * skipping kill statements.
229 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
231 return collect_domains(scop, &is_not_kill);
234 /* This function is used as a callback to pet_expr_foreach_call_expr
235 * to detect if there is any call expression in the input expression.
236 * Assign the value 1 to the integer that "user" points to and
237 * abort the search since we have found what we were looking for.
239 static int set_has_call(__isl_keep pet_expr *expr, void *user)
241 int *has_call = user;
243 *has_call = 1;
245 return -1;
248 /* Does "expr" contain any call expressions?
250 static int expr_has_call(__isl_keep pet_expr *expr)
252 int has_call = 0;
254 if (pet_expr_foreach_call_expr(expr, &set_has_call, &has_call) < 0 &&
255 !has_call)
256 return -1;
258 return has_call;
261 /* This function is a callback for pet_tree_foreach_expr.
262 * If "expr" contains any call (sub)expressions, then set *has_call
263 * and abort the search.
265 static int check_call(__isl_keep pet_expr *expr, void *user)
267 int *has_call = user;
269 if (expr_has_call(expr))
270 *has_call = 1;
272 return *has_call ? -1 : 0;
275 /* Does "stmt" contain any call expressions?
277 static int has_call(struct pet_stmt *stmt)
279 int has_call = 0;
281 if (pet_tree_foreach_expr(stmt->body, &check_call, &has_call) < 0 &&
282 !has_call)
283 return -1;
285 return has_call;
288 /* Collect the iteration domains of the statements in "scop"
289 * that contain a call expression.
291 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
293 return collect_domains(scop, &has_call);
296 /* Given a union of "tagged" access relations of the form
298 * [S_i[...] -> R_j[]] -> A_k[...]
300 * project out the "tags" (R_j[]).
301 * That is, return a union of relations of the form
303 * S_i[...] -> A_k[...]
305 static __isl_give isl_union_map *project_out_tags(
306 __isl_take isl_union_map *umap)
308 return isl_union_map_domain_factor_domain(umap);
311 /* Construct a function from tagged iteration domains to the corresponding
312 * untagged iteration domains with as range of the wrapped map in the domain
313 * the reference tags that appear in any of the reads, writes or kills.
314 * Store the result in ps->tagger.
316 * For example, if the statement with iteration space S[i,j]
317 * contains two array references R_1[] and R_2[], then ps->tagger will contain
319 * { [S[i,j] -> R_1[]] -> S[i,j]; [S[i,j] -> R_2[]] -> S[i,j] }
321 static void compute_tagger(struct ppcg_scop *ps)
323 isl_union_map *tagged;
324 isl_union_pw_multi_aff *tagger;
326 tagged = isl_union_map_copy(ps->tagged_reads);
327 tagged = isl_union_map_union(tagged,
328 isl_union_map_copy(ps->tagged_may_writes));
329 tagged = isl_union_map_union(tagged,
330 isl_union_map_copy(ps->tagged_must_kills));
331 tagged = isl_union_map_universe(tagged);
332 tagged = isl_union_set_unwrap(isl_union_map_domain(tagged));
334 tagger = isl_union_map_domain_map_union_pw_multi_aff(tagged);
336 ps->tagger = tagger;
339 /* Compute the live out accesses, i.e., the writes that are
340 * potentially not killed by any kills or any other writes, and
341 * store them in ps->live_out.
343 * We compute the "dependence" of any "kill" (an explicit kill
344 * or a must write) on any may write.
345 * The may writes with a "depending" kill are definitely killed.
346 * The remaining may writes can potentially be live out.
348 static void compute_live_out(struct ppcg_scop *ps)
350 isl_union_pw_multi_aff *tagger;
351 isl_schedule *schedule;
352 isl_union_map *kills;
353 isl_union_map *exposed;
354 isl_union_map *covering;
355 isl_union_access_info *access;
356 isl_union_flow *flow;
358 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
359 schedule = isl_schedule_copy(ps->schedule);
360 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
361 kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
362 isl_union_map_copy(ps->tagged_must_kills));
363 access = isl_union_access_info_from_sink(kills);
364 access = isl_union_access_info_set_may_source(access,
365 isl_union_map_copy(ps->tagged_may_writes));
366 access = isl_union_access_info_set_schedule(access, schedule);
367 flow = isl_union_access_info_compute_flow(access);
368 covering = isl_union_flow_get_may_dependence(flow);
369 isl_union_flow_free(flow);
370 exposed = isl_union_map_copy(ps->tagged_may_writes);
371 exposed = isl_union_map_subtract_domain(exposed,
372 isl_union_map_domain(covering));
373 ps->live_out = project_out_tags(exposed);
376 /* Compute the flow dependences and the live_in accesses and store
377 * the results in ps->dep_flow and ps->live_in.
378 * A copy of the flow dependences, tagged with the reference tags
379 * is stored in ps->tagged_dep_flow.
381 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
382 * and then project out the tags.
384 * We allow both the must writes and the must kills to serve as
385 * definite sources such that a subsequent read would not depend
386 * on any earlier write. The resulting flow dependences with
387 * a must kill as source reflect possibly uninitialized reads.
388 * No dependences need to be introduced to protect such reads
389 * (other than those imposed by potential flows from may writes
390 * that follow the kill). We therefore those flow dependences.
391 * This is also useful for the dead code elimination, which assumes
392 * the flow sources are non-kill instances.
394 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
396 isl_union_pw_multi_aff *tagger;
397 isl_schedule *schedule;
398 isl_union_map *live_in;
399 isl_union_access_info *access;
400 isl_union_flow *flow;
401 isl_union_map *must_source;
402 isl_union_map *kills;
403 isl_union_map *tagged_flow;
405 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
406 schedule = isl_schedule_copy(ps->schedule);
407 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
408 kills = isl_union_map_copy(ps->tagged_must_kills);
409 must_source = isl_union_map_copy(ps->tagged_must_writes);
410 must_source = isl_union_map_union(must_source,
411 isl_union_map_copy(kills));
412 access = isl_union_access_info_from_sink(
413 isl_union_map_copy(ps->tagged_reads));
414 access = isl_union_access_info_set_must_source(access, must_source);
415 access = isl_union_access_info_set_may_source(access,
416 isl_union_map_copy(ps->tagged_may_writes));
417 access = isl_union_access_info_set_schedule(access, schedule);
418 flow = isl_union_access_info_compute_flow(access);
419 tagged_flow = isl_union_flow_get_may_dependence(flow);
420 tagged_flow = isl_union_map_subtract_domain(tagged_flow,
421 isl_union_map_domain(kills));
422 ps->tagged_dep_flow = tagged_flow;
423 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
424 ps->dep_flow = isl_union_map_factor_domain(ps->dep_flow);
425 live_in = isl_union_flow_get_may_no_source(flow);
426 ps->live_in = project_out_tags(live_in);
427 isl_union_flow_free(flow);
430 /* Compute the order dependences that prevent the potential live ranges
431 * from overlapping.
432 * "before" contains all pairs of statement iterations where
433 * the first is executed before the second according to the original schedule.
435 * In particular, construct a union of relations
437 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
439 * where [R[...] -> R_1[]] is the range of one or more live ranges
440 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
441 * live ranges (i.e., a write). Moreover, the read and the write
442 * access the same memory element and the read occurs before the write
443 * in the original schedule.
444 * The scheduler allows some of these dependences to be violated, provided
445 * the adjacent live ranges are all local (i.e., their domain and range
446 * are mapped to the same point by the current schedule band).
448 * Note that if a live range is not local, then we need to make
449 * sure it does not overlap with _any_ other live range, and not
450 * just with the "previous" and/or the "next" live range.
451 * We therefore add order dependences between reads and
452 * _any_ later potential write.
454 * We also need to be careful about writes without a corresponding read.
455 * They are already prevented from moving past non-local preceding
456 * intervals, but we also need to prevent them from moving past non-local
457 * following intervals. We therefore also add order dependences from
458 * potential writes that do not appear in any intervals
459 * to all later potential writes.
460 * Note that dead code elimination should have removed most of these
461 * dead writes, but the dead code elimination may not remove all dead writes,
462 * so we need to consider them to be safe.
464 static void compute_order_dependences(struct ppcg_scop *ps,
465 __isl_take isl_union_map *before)
467 isl_union_map *reads;
468 isl_union_map *shared_access;
469 isl_union_set *matched;
470 isl_union_map *unmatched;
471 isl_union_set *domain;
473 reads = isl_union_map_copy(ps->tagged_reads);
474 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
475 unmatched = isl_union_map_copy(ps->tagged_may_writes);
476 unmatched = isl_union_map_subtract_domain(unmatched, matched);
477 reads = isl_union_map_union(reads, unmatched);
478 shared_access = isl_union_map_copy(ps->tagged_may_writes);
479 shared_access = isl_union_map_reverse(shared_access);
480 shared_access = isl_union_map_apply_range(reads, shared_access);
481 shared_access = isl_union_map_zip(shared_access);
482 shared_access = isl_union_map_intersect_domain(shared_access,
483 isl_union_map_wrap(before));
484 domain = isl_union_map_domain(isl_union_map_copy(shared_access));
485 shared_access = isl_union_map_zip(shared_access);
486 ps->dep_order = isl_union_set_unwrap(domain);
487 ps->tagged_dep_order = shared_access;
490 /* Compute those validity dependences of the program represented by "scop"
491 * that should be unconditionally enforced even when live-range reordering
492 * is used.
493 * "before" contains all pairs of statement iterations where
494 * the first is executed before the second according to the original schedule.
496 * In particular, compute the external false dependences
497 * as well as order dependences between sources with the same sink.
498 * The anti-dependences are already taken care of by the order dependences.
499 * The external false dependences are only used to ensure that live-in and
500 * live-out data is not overwritten by any writes inside the scop.
502 * In particular, the reads from live-in data need to precede any
503 * later write to the same memory element.
504 * As to live-out data, the last writes need to remain the last writes.
505 * That is, any earlier write in the original schedule needs to precede
506 * the last write to the same memory element in the computed schedule.
507 * The possible last writes have been computed by compute_live_out.
508 * They may include kills, but if the last access is a kill,
509 * then the corresponding dependences will effectively be ignored
510 * since we do not schedule any kill statements.
512 * Note that the set of live-in and live-out accesses may be
513 * an overapproximation. There may therefore be potential writes
514 * before a live-in access and after a live-out access.
516 * In the presence of may-writes, there may be multiple live-ranges
517 * with the same sink, accessing the same memory element.
518 * The sources of these live-ranges need to be executed
519 * in the same relative order as in the original program
520 * since we do not know which of the may-writes will actually
521 * perform a write. Consider all sources that share a sink and
522 * that may write to the same memory element and compute
523 * the order dependences among them.
525 static void compute_forced_dependences(struct ppcg_scop *ps,
526 __isl_take isl_union_map *before)
528 isl_union_map *shared_access;
529 isl_union_map *exposed;
530 isl_union_map *live_in;
531 isl_union_map *sink_access;
532 isl_union_map *shared_sink;
533 isl_union_access_info *access;
534 isl_union_flow *flow;
535 isl_schedule *schedule;
537 exposed = isl_union_map_copy(ps->live_out);
539 exposed = isl_union_map_reverse(exposed);
540 shared_access = isl_union_map_copy(ps->may_writes);
541 shared_access = isl_union_map_apply_range(shared_access, exposed);
543 ps->dep_forced = shared_access;
545 live_in = isl_union_map_apply_range(isl_union_map_copy(ps->live_in),
546 isl_union_map_reverse(isl_union_map_copy(ps->may_writes)));
548 ps->dep_forced = isl_union_map_union(ps->dep_forced, live_in);
549 ps->dep_forced = isl_union_map_intersect(ps->dep_forced, before);
551 schedule = isl_schedule_copy(ps->schedule);
552 sink_access = isl_union_map_copy(ps->tagged_dep_flow);
553 sink_access = isl_union_map_range_product(sink_access,
554 isl_union_map_copy(ps->tagged_may_writes));
555 sink_access = isl_union_map_domain_factor_domain(sink_access);
556 access = isl_union_access_info_from_sink(
557 isl_union_map_copy(sink_access));
558 access = isl_union_access_info_set_may_source(access, sink_access);
559 access = isl_union_access_info_set_schedule(access, schedule);
560 flow = isl_union_access_info_compute_flow(access);
561 shared_sink = isl_union_flow_get_may_dependence(flow);
562 isl_union_flow_free(flow);
563 ps->dep_forced = isl_union_map_union(ps->dep_forced, shared_sink);
566 /* Compute the dependences of the program represented by "scop"
567 * in case live range reordering is allowed.
569 * We compute the actual live ranges and the corresponding order
570 * false dependences.
572 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
574 isl_union_map *before;
575 isl_union_map *schedule;
577 schedule = isl_schedule_get_map(ps->schedule);
578 before = isl_union_map_lex_lt_union_map(schedule,
579 isl_union_map_copy(schedule));
581 compute_tagged_flow_dep(ps);
582 compute_order_dependences(ps, isl_union_map_copy(before));
583 compute_forced_dependences(ps, before);
586 /* Compute the potential flow dependences and the potential live in
587 * accesses.
589 static void compute_flow_dep(struct ppcg_scop *ps)
591 isl_union_access_info *access;
592 isl_union_flow *flow;
594 access = isl_union_access_info_from_sink(isl_union_map_copy(ps->reads));
595 access = isl_union_access_info_set_must_source(access,
596 isl_union_map_copy(ps->must_writes));
597 access = isl_union_access_info_set_may_source(access,
598 isl_union_map_copy(ps->may_writes));
599 access = isl_union_access_info_set_schedule(access,
600 isl_schedule_copy(ps->schedule));
601 flow = isl_union_access_info_compute_flow(access);
603 ps->dep_flow = isl_union_flow_get_may_dependence(flow);
604 ps->live_in = isl_union_flow_get_may_no_source(flow);
605 isl_union_flow_free(flow);
608 /* Compute the dependences of the program represented by "scop".
609 * Store the computed potential flow dependences
610 * in scop->dep_flow and the reads with potentially no corresponding writes in
611 * scop->live_in.
612 * Store the potential live out accesses in scop->live_out.
613 * Store the potential false (anti and output) dependences in scop->dep_false.
615 * If live range reordering is allowed, then we compute a separate
616 * set of order dependences and a set of external false dependences
617 * in compute_live_range_reordering_dependences.
619 static void compute_dependences(struct ppcg_scop *scop)
621 isl_union_map *may_source;
622 isl_union_access_info *access;
623 isl_union_flow *flow;
625 if (!scop)
626 return;
628 compute_live_out(scop);
630 if (scop->options->live_range_reordering)
631 compute_live_range_reordering_dependences(scop);
632 else if (scop->options->target != PPCG_TARGET_C)
633 compute_tagged_flow_dep(scop);
634 else
635 compute_flow_dep(scop);
637 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
638 isl_union_map_copy(scop->reads));
639 access = isl_union_access_info_from_sink(
640 isl_union_map_copy(scop->may_writes));
641 access = isl_union_access_info_set_must_source(access,
642 isl_union_map_copy(scop->must_writes));
643 access = isl_union_access_info_set_may_source(access, may_source);
644 access = isl_union_access_info_set_schedule(access,
645 isl_schedule_copy(scop->schedule));
646 flow = isl_union_access_info_compute_flow(access);
648 scop->dep_false = isl_union_flow_get_may_dependence(flow);
649 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
650 isl_union_flow_free(flow);
653 /* Eliminate dead code from ps->domain.
655 * In particular, intersect both ps->domain and the domain of
656 * ps->schedule with the (parts of) iteration
657 * domains that are needed to produce the output or for statement
658 * iterations that call functions.
659 * Also intersect the range of the dataflow dependences with
660 * this domain such that the removed instances will no longer
661 * be considered as targets of dataflow.
663 * We start with the iteration domains that call functions
664 * and the set of iterations that last write to an array
665 * (except those that are later killed).
667 * Then we add those statement iterations that produce
668 * something needed by the "live" statements iterations.
669 * We keep doing this until no more statement iterations can be added.
670 * To ensure that the procedure terminates, we compute the affine
671 * hull of the live iterations (bounded to the original iteration
672 * domains) each time we have added extra iterations.
674 static void eliminate_dead_code(struct ppcg_scop *ps)
676 isl_union_set *live;
677 isl_union_map *dep;
678 isl_union_pw_multi_aff *tagger;
680 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
681 if (!isl_union_set_is_empty(ps->call)) {
682 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
683 live = isl_union_set_coalesce(live);
686 dep = isl_union_map_copy(ps->dep_flow);
687 dep = isl_union_map_reverse(dep);
689 for (;;) {
690 isl_union_set *extra;
692 extra = isl_union_set_apply(isl_union_set_copy(live),
693 isl_union_map_copy(dep));
694 if (isl_union_set_is_subset(extra, live)) {
695 isl_union_set_free(extra);
696 break;
699 live = isl_union_set_union(live, extra);
700 live = isl_union_set_affine_hull(live);
701 live = isl_union_set_intersect(live,
702 isl_union_set_copy(ps->domain));
705 isl_union_map_free(dep);
707 ps->domain = isl_union_set_intersect(ps->domain,
708 isl_union_set_copy(live));
709 ps->schedule = isl_schedule_intersect_domain(ps->schedule,
710 isl_union_set_copy(live));
711 ps->dep_flow = isl_union_map_intersect_range(ps->dep_flow,
712 isl_union_set_copy(live));
713 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
714 live = isl_union_set_preimage_union_pw_multi_aff(live, tagger);
715 ps->tagged_dep_flow = isl_union_map_intersect_range(ps->tagged_dep_flow,
716 live);
719 /* Intersect "set" with the set described by "str", taking the NULL
720 * string to represent the universal set.
722 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
723 const char *str)
725 isl_ctx *ctx;
726 isl_set *set2;
728 if (!str)
729 return set;
731 ctx = isl_set_get_ctx(set);
732 set2 = isl_set_read_from_str(ctx, str);
733 set = isl_set_intersect(set, set2);
735 return set;
738 static void *ppcg_scop_free(struct ppcg_scop *ps)
740 if (!ps)
741 return NULL;
743 isl_set_free(ps->context);
744 isl_union_set_free(ps->domain);
745 isl_union_set_free(ps->call);
746 isl_union_map_free(ps->tagged_reads);
747 isl_union_map_free(ps->reads);
748 isl_union_map_free(ps->live_in);
749 isl_union_map_free(ps->tagged_may_writes);
750 isl_union_map_free(ps->tagged_must_writes);
751 isl_union_map_free(ps->may_writes);
752 isl_union_map_free(ps->must_writes);
753 isl_union_map_free(ps->live_out);
754 isl_union_map_free(ps->tagged_must_kills);
755 isl_union_map_free(ps->tagged_dep_flow);
756 isl_union_map_free(ps->dep_flow);
757 isl_union_map_free(ps->dep_false);
758 isl_union_map_free(ps->dep_forced);
759 isl_union_map_free(ps->tagged_dep_order);
760 isl_union_map_free(ps->dep_order);
761 isl_schedule_free(ps->schedule);
762 isl_union_pw_multi_aff_free(ps->tagger);
763 isl_union_map_free(ps->independence);
764 isl_id_to_ast_expr_free(ps->names);
766 free(ps);
768 return NULL;
771 /* Extract a ppcg_scop from a pet_scop.
773 * The constructed ppcg_scop refers to elements from the pet_scop
774 * so the pet_scop should not be freed before the ppcg_scop.
776 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
777 struct ppcg_options *options)
779 int i;
780 isl_ctx *ctx;
781 struct ppcg_scop *ps;
783 if (!scop)
784 return NULL;
786 ctx = isl_set_get_ctx(scop->context);
788 ps = isl_calloc_type(ctx, struct ppcg_scop);
789 if (!ps)
790 return NULL;
792 ps->names = collect_names(scop);
793 ps->options = options;
794 ps->start = pet_loc_get_start(scop->loc);
795 ps->end = pet_loc_get_end(scop->loc);
796 ps->context = isl_set_copy(scop->context);
797 ps->context = set_intersect_str(ps->context, options->ctx);
798 ps->domain = collect_non_kill_domains(scop);
799 ps->call = collect_call_domains(scop);
800 ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
801 ps->reads = pet_scop_collect_may_reads(scop);
802 ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
803 ps->may_writes = pet_scop_collect_may_writes(scop);
804 ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
805 ps->must_writes = pet_scop_collect_must_writes(scop);
806 ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
807 ps->schedule = isl_schedule_copy(scop->schedule);
808 ps->pet = scop;
809 ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
810 for (i = 0; i < scop->n_independence; ++i)
811 ps->independence = isl_union_map_union(ps->independence,
812 isl_union_map_copy(scop->independences[i]->filter));
814 compute_tagger(ps);
815 compute_dependences(ps);
816 eliminate_dead_code(ps);
818 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
819 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
820 !ps->schedule || !ps->independence || !ps->names)
821 return ppcg_scop_free(ps);
823 return ps;
826 /* Internal data structure for ppcg_transform.
828 struct ppcg_transform_data {
829 struct ppcg_options *options;
830 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
831 struct ppcg_scop *scop, void *user);
832 void *user;
835 /* Should we print the original code?
836 * That is, does "scop" involve any data dependent conditions or
837 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
839 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
841 if (!pet_scop_can_build_ast_exprs(scop)) {
842 if (options->debug->verbose)
843 fprintf(stdout, "Printing original code because "
844 "some index expressions cannot currently "
845 "be printed\n");
846 return 1;
849 if (pet_scop_has_data_dependent_conditions(scop)) {
850 if (options->debug->verbose)
851 fprintf(stdout, "Printing original code because "
852 "input involves data dependent conditions\n");
853 return 1;
856 return 0;
859 /* Callback for pet_transform_C_source that transforms
860 * the given pet_scop to a ppcg_scop before calling the
861 * ppcg_transform callback.
863 * If "scop" contains any data dependent conditions or if we may
864 * not be able to print the transformed program, then just print
865 * the original code.
867 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
868 struct pet_scop *scop, void *user)
870 struct ppcg_transform_data *data = user;
871 struct ppcg_scop *ps;
873 if (print_original(scop, data->options)) {
874 p = pet_scop_print_original(scop, p);
875 pet_scop_free(scop);
876 return p;
879 scop = pet_scop_align_params(scop);
880 ps = ppcg_scop_from_pet_scop(scop, data->options);
882 p = data->transform(p, ps, data->user);
884 ppcg_scop_free(ps);
885 pet_scop_free(scop);
887 return p;
890 /* Transform the C source file "input" by rewriting each scop
891 * through a call to "transform".
892 * The transformed C code is written to "out".
894 * This is a wrapper around pet_transform_C_source that transforms
895 * the pet_scop to a ppcg_scop before calling "fn".
897 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
898 struct ppcg_options *options,
899 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
900 struct ppcg_scop *scop, void *user), void *user)
902 struct ppcg_transform_data data = { options, fn, user };
903 return pet_transform_C_source(ctx, input, out, &transform, &data);
906 /* Check consistency of options.
908 * Return -1 on error.
910 static int check_options(isl_ctx *ctx)
912 struct options *options;
914 options = isl_ctx_peek_options(ctx, &options_args);
915 if (!options)
916 isl_die(ctx, isl_error_internal,
917 "unable to find options", return -1);
919 if (options->ppcg->openmp &&
920 !isl_options_get_ast_build_atomic_upper_bound(ctx))
921 isl_die(ctx, isl_error_invalid,
922 "OpenMP requires atomic bounds", return -1);
924 return 0;
927 int main(int argc, char **argv)
929 int r;
930 isl_ctx *ctx;
931 struct options *options;
933 options = options_new_with_defaults();
934 assert(options);
936 ctx = isl_ctx_alloc_with_options(&options_args, options);
937 isl_options_set_schedule_outer_coincidence(ctx, 1);
938 isl_options_set_schedule_maximize_band_depth(ctx, 1);
939 pet_options_set_encapsulate_dynamic_control(ctx, 1);
940 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
942 if (check_options(ctx) < 0)
943 r = EXIT_FAILURE;
944 else if (options->ppcg->target == PPCG_TARGET_CUDA)
945 r = generate_cuda(ctx, options->ppcg, options->input);
946 else if (options->ppcg->target == PPCG_TARGET_OPENCL)
947 r = generate_opencl(ctx, options->ppcg, options->input,
948 options->output);
949 else
950 r = generate_cpu(ctx, options->ppcg, options->input,
951 options->output);
953 isl_ctx_free(ctx);
955 return r;