update pet for support for recent clangs
[ppcg.git] / ppcg.c
blobfa9c1b0cfce01b26ea676ff78864db96ac1307a7
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 pet_options *pet;
33 struct ppcg_options *ppcg;
34 char *input;
35 char *output;
38 const char *ppcg_version(void);
39 static void print_version(void)
41 printf("%s", ppcg_version());
44 ISL_ARGS_START(struct options, options_args)
45 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
46 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
47 ISL_ARG_STR(struct options, output, 'o', NULL,
48 "filename", NULL, "output filename (c and opencl targets)")
49 ISL_ARG_ARG(struct options, input, "input", NULL)
50 ISL_ARG_VERSION(print_version)
51 ISL_ARGS_END
53 ISL_ARG_DEF(options, struct options, options_args)
55 /* Return a pointer to the final path component of "filename" or
56 * to "filename" itself if it does not contain any components.
58 const char *ppcg_base_name(const char *filename)
60 const char *base;
62 base = strrchr(filename, '/');
63 if (base)
64 return ++base;
65 else
66 return filename;
69 /* Copy the base name of "input" to "name" and return its length.
70 * "name" is not NULL terminated.
72 * In particular, remove all leading directory components and
73 * the final extension, if any.
75 int ppcg_extract_base_name(char *name, const char *input)
77 const char *base;
78 const char *ext;
79 int len;
81 base = ppcg_base_name(input);
82 ext = strrchr(base, '.');
83 len = ext ? ext - base : strlen(base);
85 memcpy(name, base, len);
87 return len;
90 /* Does "scop" refer to any arrays that are declared, but not
91 * exposed to the code after the scop?
93 int ppcg_scop_any_hidden_declarations(struct ppcg_scop *scop)
95 int i;
97 if (!scop)
98 return 0;
100 for (i = 0; i < scop->pet->n_array; ++i)
101 if (scop->pet->arrays[i]->declared &&
102 !scop->pet->arrays[i]->exposed)
103 return 1;
105 return 0;
108 /* Collect all variable names that are in use in "scop".
109 * In particular, collect all parameters in the context and
110 * all the array names.
111 * Store these names in an isl_id_to_ast_expr by mapping
112 * them to a dummy value (0).
114 static __isl_give isl_id_to_ast_expr *collect_names(struct pet_scop *scop)
116 int i, n;
117 isl_ctx *ctx;
118 isl_ast_expr *zero;
119 isl_id_to_ast_expr *names;
121 ctx = isl_set_get_ctx(scop->context);
123 n = isl_set_dim(scop->context, isl_dim_param);
125 names = isl_id_to_ast_expr_alloc(ctx, n + scop->n_array);
126 zero = isl_ast_expr_from_val(isl_val_zero(ctx));
128 for (i = 0; i < n; ++i) {
129 isl_id *id;
131 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
132 names = isl_id_to_ast_expr_set(names,
133 id, isl_ast_expr_copy(zero));
136 for (i = 0; i < scop->n_array; ++i) {
137 struct pet_array *array = scop->arrays[i];
138 isl_id *id;
140 id = isl_set_get_tuple_id(array->extent);
141 names = isl_id_to_ast_expr_set(names,
142 id, isl_ast_expr_copy(zero));
145 isl_ast_expr_free(zero);
147 return names;
150 /* Return an isl_id called "prefix%d", with "%d" set to "i".
151 * If an isl_id with such a name already appears among the variable names
152 * of "scop", then adjust the name to "prefix%d_%d".
154 static __isl_give isl_id *generate_name(struct ppcg_scop *scop,
155 const char *prefix, int i)
157 int j;
158 char name[16];
159 isl_ctx *ctx;
160 isl_id *id;
161 int has_name;
163 ctx = isl_set_get_ctx(scop->context);
164 snprintf(name, sizeof(name), "%s%d", prefix, i);
165 id = isl_id_alloc(ctx, name, NULL);
167 j = 0;
168 while ((has_name = isl_id_to_ast_expr_has(scop->names, id)) == 1) {
169 isl_id_free(id);
170 snprintf(name, sizeof(name), "%s%d_%d", prefix, i, j++);
171 id = isl_id_alloc(ctx, name, NULL);
174 return has_name < 0 ? isl_id_free(id) : id;
177 /* Return a list of "n" isl_ids of the form "prefix%d".
178 * If an isl_id with such a name already appears among the variable names
179 * of "scop", then adjust the name to "prefix%d_%d".
181 __isl_give isl_id_list *ppcg_scop_generate_names(struct ppcg_scop *scop,
182 int n, const char *prefix)
184 int i;
185 isl_ctx *ctx;
186 isl_id_list *names;
188 ctx = isl_set_get_ctx(scop->context);
189 names = isl_id_list_alloc(ctx, n);
190 for (i = 0; i < n; ++i) {
191 isl_id *id;
193 id = generate_name(scop, prefix, i);
194 names = isl_id_list_add(names, id);
197 return names;
200 /* Is "stmt" not a kill statement?
202 static int is_not_kill(struct pet_stmt *stmt)
204 return !pet_stmt_is_kill(stmt);
207 /* Collect the iteration domains of the statements in "scop" that
208 * satisfy "pred".
210 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
211 int (*pred)(struct pet_stmt *stmt))
213 int i;
214 isl_set *domain_i;
215 isl_union_set *domain;
217 if (!scop)
218 return NULL;
220 domain = isl_union_set_empty(isl_set_get_space(scop->context));
222 for (i = 0; i < scop->n_stmt; ++i) {
223 struct pet_stmt *stmt = scop->stmts[i];
225 if (!pred(stmt))
226 continue;
228 if (stmt->n_arg > 0)
229 isl_die(isl_union_set_get_ctx(domain),
230 isl_error_unsupported,
231 "data dependent conditions not supported",
232 return isl_union_set_free(domain));
234 domain_i = isl_set_copy(scop->stmts[i]->domain);
235 domain = isl_union_set_add_set(domain, domain_i);
238 return domain;
241 /* Collect the iteration domains of the statements in "scop",
242 * skipping kill statements.
244 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
246 return collect_domains(scop, &is_not_kill);
249 /* This function is used as a callback to pet_expr_foreach_call_expr
250 * to detect if there is any call expression in the input expression.
251 * Assign the value 1 to the integer that "user" points to and
252 * abort the search since we have found what we were looking for.
254 static int set_has_call(__isl_keep pet_expr *expr, void *user)
256 int *has_call = user;
258 *has_call = 1;
260 return -1;
263 /* Does "expr" contain any call expressions?
265 static int expr_has_call(__isl_keep pet_expr *expr)
267 int has_call = 0;
269 if (pet_expr_foreach_call_expr(expr, &set_has_call, &has_call) < 0 &&
270 !has_call)
271 return -1;
273 return has_call;
276 /* This function is a callback for pet_tree_foreach_expr.
277 * If "expr" contains any call (sub)expressions, then set *has_call
278 * and abort the search.
280 static int check_call(__isl_keep pet_expr *expr, void *user)
282 int *has_call = user;
284 if (expr_has_call(expr))
285 *has_call = 1;
287 return *has_call ? -1 : 0;
290 /* Does "stmt" contain any call expressions?
292 static int has_call(struct pet_stmt *stmt)
294 int has_call = 0;
296 if (pet_tree_foreach_expr(stmt->body, &check_call, &has_call) < 0 &&
297 !has_call)
298 return -1;
300 return has_call;
303 /* Collect the iteration domains of the statements in "scop"
304 * that contain a call expression.
306 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
308 return collect_domains(scop, &has_call);
311 /* Given a union of "tagged" access relations of the form
313 * [S_i[...] -> R_j[]] -> A_k[...]
315 * project out the "tags" (R_j[]).
316 * That is, return a union of relations of the form
318 * S_i[...] -> A_k[...]
320 static __isl_give isl_union_map *project_out_tags(
321 __isl_take isl_union_map *umap)
323 return isl_union_map_domain_factor_domain(umap);
326 /* Construct a function from tagged iteration domains to the corresponding
327 * untagged iteration domains with as range of the wrapped map in the domain
328 * the reference tags that appear in any of the reads, writes or kills.
329 * Store the result in ps->tagger.
331 * For example, if the statement with iteration space S[i,j]
332 * contains two array references R_1[] and R_2[], then ps->tagger will contain
334 * { [S[i,j] -> R_1[]] -> S[i,j]; [S[i,j] -> R_2[]] -> S[i,j] }
336 static void compute_tagger(struct ppcg_scop *ps)
338 isl_union_map *tagged;
339 isl_union_pw_multi_aff *tagger;
341 tagged = isl_union_map_copy(ps->tagged_reads);
342 tagged = isl_union_map_union(tagged,
343 isl_union_map_copy(ps->tagged_may_writes));
344 tagged = isl_union_map_union(tagged,
345 isl_union_map_copy(ps->tagged_must_kills));
346 tagged = isl_union_map_universe(tagged);
347 tagged = isl_union_set_unwrap(isl_union_map_domain(tagged));
349 tagger = isl_union_map_domain_map_union_pw_multi_aff(tagged);
351 ps->tagger = tagger;
354 /* Compute the live out accesses, i.e., the writes that are
355 * potentially not killed by any kills or any other writes, and
356 * store them in ps->live_out.
358 * We compute the "dependence" of any "kill" (an explicit kill
359 * or a must write) on any may write.
360 * The elements accessed by the may writes with a "depending" kill
361 * also accessing the element are definitely killed.
362 * The remaining may writes can potentially be live out.
364 * The result of the dependence analysis is
366 * { IW -> [IK -> A] }
368 * with IW the instance of the write statement, IK the instance of kill
369 * statement and A the element that was killed.
370 * The range factor range is
372 * { IW -> A }
374 * containing all such pairs for which there is a kill statement instance,
375 * i.e., all pairs that have been killed.
377 static void compute_live_out(struct ppcg_scop *ps)
379 isl_schedule *schedule;
380 isl_union_map *kills;
381 isl_union_map *exposed;
382 isl_union_map *covering;
383 isl_union_access_info *access;
384 isl_union_flow *flow;
386 schedule = isl_schedule_copy(ps->schedule);
387 kills = isl_union_map_union(isl_union_map_copy(ps->must_writes),
388 isl_union_map_copy(ps->must_kills));
389 access = isl_union_access_info_from_sink(kills);
390 access = isl_union_access_info_set_may_source(access,
391 isl_union_map_copy(ps->may_writes));
392 access = isl_union_access_info_set_schedule(access, schedule);
393 flow = isl_union_access_info_compute_flow(access);
394 covering = isl_union_flow_get_full_may_dependence(flow);
395 isl_union_flow_free(flow);
397 covering = isl_union_map_range_factor_range(covering);
398 exposed = isl_union_map_copy(ps->may_writes);
399 exposed = isl_union_map_subtract(exposed, covering);
400 ps->live_out = exposed;
403 /* Compute the tagged flow dependences and the live_in accesses and store
404 * the results in ps->tagged_dep_flow and ps->live_in.
406 * We allow both the must writes and the must kills to serve as
407 * definite sources such that a subsequent read would not depend
408 * on any earlier write. The resulting flow dependences with
409 * a must kill as source reflect possibly uninitialized reads.
410 * No dependences need to be introduced to protect such reads
411 * (other than those imposed by potential flows from may writes
412 * that follow the kill). We therefore remove those flow dependences.
413 * This is also useful for the dead code elimination, which assumes
414 * the flow sources are non-kill instances.
416 static void compute_tagged_flow_dep_only(struct ppcg_scop *ps)
418 isl_union_pw_multi_aff *tagger;
419 isl_schedule *schedule;
420 isl_union_map *live_in;
421 isl_union_access_info *access;
422 isl_union_flow *flow;
423 isl_union_map *must_source;
424 isl_union_map *kills;
425 isl_union_map *tagged_flow;
427 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
428 schedule = isl_schedule_copy(ps->schedule);
429 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
430 kills = isl_union_map_copy(ps->tagged_must_kills);
431 must_source = isl_union_map_copy(ps->tagged_must_writes);
432 must_source = isl_union_map_union(must_source,
433 isl_union_map_copy(kills));
434 access = isl_union_access_info_from_sink(
435 isl_union_map_copy(ps->tagged_reads));
436 access = isl_union_access_info_set_must_source(access, must_source);
437 access = isl_union_access_info_set_may_source(access,
438 isl_union_map_copy(ps->tagged_may_writes));
439 access = isl_union_access_info_set_schedule(access, schedule);
440 flow = isl_union_access_info_compute_flow(access);
441 tagged_flow = isl_union_flow_get_may_dependence(flow);
442 tagged_flow = isl_union_map_subtract_domain(tagged_flow,
443 isl_union_map_domain(kills));
444 ps->tagged_dep_flow = tagged_flow;
445 live_in = isl_union_flow_get_may_no_source(flow);
446 ps->live_in = project_out_tags(live_in);
447 isl_union_flow_free(flow);
450 /* Compute ps->dep_flow from ps->tagged_dep_flow
451 * by projecting out the reference tags.
453 static void derive_flow_dep_from_tagged_flow_dep(struct ppcg_scop *ps)
455 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
456 ps->dep_flow = isl_union_map_factor_domain(ps->dep_flow);
459 /* Compute the flow dependences and the live_in accesses and store
460 * the results in ps->dep_flow and ps->live_in.
461 * A copy of the flow dependences, tagged with the reference tags
462 * is stored in ps->tagged_dep_flow.
464 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
465 * and then project out the tags.
467 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
469 compute_tagged_flow_dep_only(ps);
470 derive_flow_dep_from_tagged_flow_dep(ps);
473 /* Compute the order dependences that prevent the potential live ranges
474 * from overlapping.
476 * In particular, construct a union of relations
478 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
480 * where [R[...] -> R_1[]] is the range of one or more live ranges
481 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
482 * live ranges (i.e., a write). Moreover, the read and the write
483 * access the same memory element and the read occurs before the write
484 * in the original schedule.
485 * The scheduler allows some of these dependences to be violated, provided
486 * the adjacent live ranges are all local (i.e., their domain and range
487 * are mapped to the same point by the current schedule band).
489 * Note that if a live range is not local, then we need to make
490 * sure it does not overlap with _any_ other live range, and not
491 * just with the "previous" and/or the "next" live range.
492 * We therefore add order dependences between reads and
493 * _any_ later potential write.
495 * We also need to be careful about writes without a corresponding read.
496 * They are already prevented from moving past non-local preceding
497 * intervals, but we also need to prevent them from moving past non-local
498 * following intervals. We therefore also add order dependences from
499 * potential writes that do not appear in any intervals
500 * to all later potential writes.
501 * Note that dead code elimination should have removed most of these
502 * dead writes, but the dead code elimination may not remove all dead writes,
503 * so we need to consider them to be safe.
505 * The order dependences are computed by computing the "dataflow"
506 * from the above unmatched writes and the reads to the may writes.
507 * The unmatched writes and the reads are treated as may sources
508 * such that they would not kill order dependences from earlier
509 * such writes and reads.
511 static void compute_order_dependences(struct ppcg_scop *ps)
513 isl_union_map *reads;
514 isl_union_map *shared_access;
515 isl_union_set *matched;
516 isl_union_map *unmatched;
517 isl_union_pw_multi_aff *tagger;
518 isl_schedule *schedule;
519 isl_union_access_info *access;
520 isl_union_flow *flow;
522 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
523 schedule = isl_schedule_copy(ps->schedule);
524 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
525 reads = isl_union_map_copy(ps->tagged_reads);
526 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
527 unmatched = isl_union_map_copy(ps->tagged_may_writes);
528 unmatched = isl_union_map_subtract_domain(unmatched, matched);
529 reads = isl_union_map_union(reads, unmatched);
530 access = isl_union_access_info_from_sink(
531 isl_union_map_copy(ps->tagged_may_writes));
532 access = isl_union_access_info_set_may_source(access, reads);
533 access = isl_union_access_info_set_schedule(access, schedule);
534 flow = isl_union_access_info_compute_flow(access);
535 shared_access = isl_union_flow_get_may_dependence(flow);
536 isl_union_flow_free(flow);
538 ps->tagged_dep_order = isl_union_map_copy(shared_access);
539 ps->dep_order = isl_union_map_factor_domain(shared_access);
542 /* Compute those validity dependences of the program represented by "scop"
543 * that should be unconditionally enforced even when live-range reordering
544 * is used.
546 * In particular, compute the external false dependences
547 * as well as order dependences between sources with the same sink.
548 * The anti-dependences are already taken care of by the order dependences.
549 * The external false dependences are only used to ensure that live-in and
550 * live-out data is not overwritten by any writes inside the scop.
551 * The independences are removed from the external false dependences,
552 * but not from the order dependences between sources with the same sink.
554 * In particular, the reads from live-in data need to precede any
555 * later write to the same memory element.
556 * As to live-out data, the last writes need to remain the last writes.
557 * That is, any earlier write in the original schedule needs to precede
558 * the last write to the same memory element in the computed schedule.
559 * The possible last writes have been computed by compute_live_out.
560 * They may include kills, but if the last access is a kill,
561 * then the corresponding dependences will effectively be ignored
562 * since we do not schedule any kill statements.
564 * Note that the set of live-in and live-out accesses may be
565 * an overapproximation. There may therefore be potential writes
566 * before a live-in access and after a live-out access.
568 * In the presence of may-writes, there may be multiple live-ranges
569 * with the same sink, accessing the same memory element.
570 * The sources of these live-ranges need to be executed
571 * in the same relative order as in the original program
572 * since we do not know which of the may-writes will actually
573 * perform a write. Consider all sources that share a sink and
574 * that may write to the same memory element and compute
575 * the order dependences among them.
577 static void compute_forced_dependences(struct ppcg_scop *ps)
579 isl_union_map *shared_access;
580 isl_union_map *exposed;
581 isl_union_map *live_in;
582 isl_union_map *sink_access;
583 isl_union_map *shared_sink;
584 isl_union_access_info *access;
585 isl_union_flow *flow;
586 isl_schedule *schedule;
588 exposed = isl_union_map_copy(ps->live_out);
589 schedule = isl_schedule_copy(ps->schedule);
590 access = isl_union_access_info_from_sink(exposed);
591 access = isl_union_access_info_set_may_source(access,
592 isl_union_map_copy(ps->may_writes));
593 access = isl_union_access_info_set_schedule(access, schedule);
594 flow = isl_union_access_info_compute_flow(access);
595 shared_access = isl_union_flow_get_may_dependence(flow);
596 isl_union_flow_free(flow);
597 ps->dep_forced = shared_access;
599 schedule = isl_schedule_copy(ps->schedule);
600 access = isl_union_access_info_from_sink(
601 isl_union_map_copy(ps->may_writes));
602 access = isl_union_access_info_set_may_source(access,
603 isl_union_map_copy(ps->live_in));
604 access = isl_union_access_info_set_schedule(access, schedule);
605 flow = isl_union_access_info_compute_flow(access);
606 live_in = isl_union_flow_get_may_dependence(flow);
607 isl_union_flow_free(flow);
609 ps->dep_forced = isl_union_map_union(ps->dep_forced, live_in);
610 ps->dep_forced = isl_union_map_subtract(ps->dep_forced,
611 isl_union_map_copy(ps->independence));
613 schedule = isl_schedule_copy(ps->schedule);
614 sink_access = isl_union_map_copy(ps->tagged_dep_flow);
615 sink_access = isl_union_map_range_product(sink_access,
616 isl_union_map_copy(ps->tagged_may_writes));
617 sink_access = isl_union_map_domain_factor_domain(sink_access);
618 access = isl_union_access_info_from_sink(
619 isl_union_map_copy(sink_access));
620 access = isl_union_access_info_set_may_source(access, sink_access);
621 access = isl_union_access_info_set_schedule(access, schedule);
622 flow = isl_union_access_info_compute_flow(access);
623 shared_sink = isl_union_flow_get_may_dependence(flow);
624 isl_union_flow_free(flow);
625 ps->dep_forced = isl_union_map_union(ps->dep_forced, shared_sink);
628 /* Remove independence from the tagged flow dependences.
629 * Since the user has guaranteed that source and sink of an independence
630 * can be executed in any order, there cannot be a flow dependence
631 * between them, so they can be removed from the set of flow dependences.
632 * However, if the source of such a flow dependence is a must write,
633 * then it may have killed other potential sources, which would have
634 * to be recovered if we were to remove those flow dependences.
635 * We therefore keep the flow dependences that originate in a must write,
636 * even if it corresponds to a known independence.
638 static void remove_independences_from_tagged_flow(struct ppcg_scop *ps)
640 isl_union_map *tf;
641 isl_union_set *indep;
642 isl_union_set *mw;
644 tf = isl_union_map_copy(ps->tagged_dep_flow);
645 tf = isl_union_map_zip(tf);
646 indep = isl_union_map_wrap(isl_union_map_copy(ps->independence));
647 tf = isl_union_map_intersect_domain(tf, indep);
648 tf = isl_union_map_zip(tf);
649 mw = isl_union_map_domain(isl_union_map_copy(ps->tagged_must_writes));
650 tf = isl_union_map_subtract_domain(tf, mw);
651 ps->tagged_dep_flow = isl_union_map_subtract(ps->tagged_dep_flow, tf);
654 /* Compute the dependences of the program represented by "scop"
655 * in case live range reordering is allowed.
657 * We compute the actual live ranges and the corresponding order
658 * false dependences.
660 * The independences are removed from the flow dependences
661 * (provided the source is not a must-write) as well as
662 * from the external false dependences (by compute_forced_dependences).
664 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
666 compute_tagged_flow_dep_only(ps);
667 remove_independences_from_tagged_flow(ps);
668 derive_flow_dep_from_tagged_flow_dep(ps);
669 compute_order_dependences(ps);
670 compute_forced_dependences(ps);
673 /* Compute the potential flow dependences and the potential live in
674 * accesses.
676 static void compute_flow_dep(struct ppcg_scop *ps)
678 isl_union_access_info *access;
679 isl_union_flow *flow;
681 access = isl_union_access_info_from_sink(isl_union_map_copy(ps->reads));
682 access = isl_union_access_info_set_must_source(access,
683 isl_union_map_copy(ps->must_writes));
684 access = isl_union_access_info_set_may_source(access,
685 isl_union_map_copy(ps->may_writes));
686 access = isl_union_access_info_set_schedule(access,
687 isl_schedule_copy(ps->schedule));
688 flow = isl_union_access_info_compute_flow(access);
690 ps->dep_flow = isl_union_flow_get_may_dependence(flow);
691 ps->live_in = isl_union_flow_get_may_no_source(flow);
692 isl_union_flow_free(flow);
695 /* Compute the dependences of the program represented by "scop".
696 * Store the computed potential flow dependences
697 * in scop->dep_flow and the reads with potentially no corresponding writes in
698 * scop->live_in.
699 * Store the potential live out accesses in scop->live_out.
700 * Store the potential false (anti and output) dependences in scop->dep_false.
702 * If live range reordering is allowed, then we compute a separate
703 * set of order dependences and a set of external false dependences
704 * in compute_live_range_reordering_dependences.
706 static void compute_dependences(struct ppcg_scop *scop)
708 isl_union_map *may_source;
709 isl_union_access_info *access;
710 isl_union_flow *flow;
712 if (!scop)
713 return;
715 compute_live_out(scop);
717 if (scop->options->live_range_reordering)
718 compute_live_range_reordering_dependences(scop);
719 else if (scop->options->target != PPCG_TARGET_C)
720 compute_tagged_flow_dep(scop);
721 else
722 compute_flow_dep(scop);
724 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
725 isl_union_map_copy(scop->reads));
726 access = isl_union_access_info_from_sink(
727 isl_union_map_copy(scop->may_writes));
728 access = isl_union_access_info_set_must_source(access,
729 isl_union_map_copy(scop->must_writes));
730 access = isl_union_access_info_set_may_source(access, may_source);
731 access = isl_union_access_info_set_schedule(access,
732 isl_schedule_copy(scop->schedule));
733 flow = isl_union_access_info_compute_flow(access);
735 scop->dep_false = isl_union_flow_get_may_dependence(flow);
736 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
737 isl_union_flow_free(flow);
740 /* Eliminate dead code from ps->domain.
742 * In particular, intersect both ps->domain and the domain of
743 * ps->schedule with the (parts of) iteration
744 * domains that are needed to produce the output or for statement
745 * iterations that call functions.
746 * Also intersect the range of the dataflow dependences with
747 * this domain such that the removed instances will no longer
748 * be considered as targets of dataflow.
750 * We start with the iteration domains that call functions
751 * and the set of iterations that last write to an array
752 * (except those that are later killed).
754 * Then we add those statement iterations that produce
755 * something needed by the "live" statements iterations.
756 * We keep doing this until no more statement iterations can be added.
757 * To ensure that the procedure terminates, we compute the affine
758 * hull of the live iterations (bounded to the original iteration
759 * domains) each time we have added extra iterations.
761 static void eliminate_dead_code(struct ppcg_scop *ps)
763 isl_union_set *live;
764 isl_union_map *dep;
765 isl_union_pw_multi_aff *tagger;
767 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
768 if (!isl_union_set_is_empty(ps->call)) {
769 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
770 live = isl_union_set_coalesce(live);
773 dep = isl_union_map_copy(ps->dep_flow);
774 dep = isl_union_map_reverse(dep);
776 for (;;) {
777 isl_union_set *extra;
779 extra = isl_union_set_apply(isl_union_set_copy(live),
780 isl_union_map_copy(dep));
781 if (isl_union_set_is_subset(extra, live)) {
782 isl_union_set_free(extra);
783 break;
786 live = isl_union_set_union(live, extra);
787 live = isl_union_set_affine_hull(live);
788 live = isl_union_set_intersect(live,
789 isl_union_set_copy(ps->domain));
792 isl_union_map_free(dep);
794 ps->domain = isl_union_set_intersect(ps->domain,
795 isl_union_set_copy(live));
796 ps->schedule = isl_schedule_intersect_domain(ps->schedule,
797 isl_union_set_copy(live));
798 ps->dep_flow = isl_union_map_intersect_range(ps->dep_flow,
799 isl_union_set_copy(live));
800 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
801 live = isl_union_set_preimage_union_pw_multi_aff(live, tagger);
802 ps->tagged_dep_flow = isl_union_map_intersect_range(ps->tagged_dep_flow,
803 live);
806 /* Intersect "set" with the set described by "str", taking the NULL
807 * string to represent the universal set.
809 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
810 const char *str)
812 isl_ctx *ctx;
813 isl_set *set2;
815 if (!str)
816 return set;
818 ctx = isl_set_get_ctx(set);
819 set2 = isl_set_read_from_str(ctx, str);
820 set = isl_set_intersect(set, set2);
822 return set;
825 static void *ppcg_scop_free(struct ppcg_scop *ps)
827 if (!ps)
828 return NULL;
830 isl_set_free(ps->context);
831 isl_union_set_free(ps->domain);
832 isl_union_set_free(ps->call);
833 isl_union_map_free(ps->tagged_reads);
834 isl_union_map_free(ps->reads);
835 isl_union_map_free(ps->live_in);
836 isl_union_map_free(ps->tagged_may_writes);
837 isl_union_map_free(ps->tagged_must_writes);
838 isl_union_map_free(ps->may_writes);
839 isl_union_map_free(ps->must_writes);
840 isl_union_map_free(ps->live_out);
841 isl_union_map_free(ps->tagged_must_kills);
842 isl_union_map_free(ps->must_kills);
843 isl_union_map_free(ps->tagged_dep_flow);
844 isl_union_map_free(ps->dep_flow);
845 isl_union_map_free(ps->dep_false);
846 isl_union_map_free(ps->dep_forced);
847 isl_union_map_free(ps->tagged_dep_order);
848 isl_union_map_free(ps->dep_order);
849 isl_schedule_free(ps->schedule);
850 isl_union_pw_multi_aff_free(ps->tagger);
851 isl_union_map_free(ps->independence);
852 isl_id_to_ast_expr_free(ps->names);
854 free(ps);
856 return NULL;
859 /* Extract a ppcg_scop from a pet_scop.
861 * The constructed ppcg_scop refers to elements from the pet_scop
862 * so the pet_scop should not be freed before the ppcg_scop.
864 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
865 struct ppcg_options *options)
867 int i;
868 isl_ctx *ctx;
869 struct ppcg_scop *ps;
871 if (!scop)
872 return NULL;
874 ctx = isl_set_get_ctx(scop->context);
876 ps = isl_calloc_type(ctx, struct ppcg_scop);
877 if (!ps)
878 return NULL;
880 ps->names = collect_names(scop);
881 ps->options = options;
882 ps->start = pet_loc_get_start(scop->loc);
883 ps->end = pet_loc_get_end(scop->loc);
884 ps->context = isl_set_copy(scop->context);
885 ps->context = set_intersect_str(ps->context, options->ctx);
886 if (options->non_negative_parameters) {
887 isl_space *space = isl_set_get_space(ps->context);
888 isl_set *nn = isl_set_nat_universe(space);
889 ps->context = isl_set_intersect(ps->context, nn);
891 ps->domain = collect_non_kill_domains(scop);
892 ps->call = collect_call_domains(scop);
893 ps->tagged_reads = pet_scop_get_tagged_may_reads(scop);
894 ps->reads = pet_scop_get_may_reads(scop);
895 ps->tagged_may_writes = pet_scop_get_tagged_may_writes(scop);
896 ps->may_writes = pet_scop_get_may_writes(scop);
897 ps->tagged_must_writes = pet_scop_get_tagged_must_writes(scop);
898 ps->must_writes = pet_scop_get_must_writes(scop);
899 ps->tagged_must_kills = pet_scop_get_tagged_must_kills(scop);
900 ps->must_kills = pet_scop_get_must_kills(scop);
901 ps->schedule = isl_schedule_copy(scop->schedule);
902 ps->pet = scop;
903 ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
904 for (i = 0; i < scop->n_independence; ++i)
905 ps->independence = isl_union_map_union(ps->independence,
906 isl_union_map_copy(scop->independences[i]->filter));
908 compute_tagger(ps);
909 compute_dependences(ps);
910 eliminate_dead_code(ps);
912 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
913 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
914 !ps->must_kills || !ps->schedule || !ps->independence || !ps->names)
915 return ppcg_scop_free(ps);
917 return ps;
920 /* Internal data structure for ppcg_transform.
922 struct ppcg_transform_data {
923 struct ppcg_options *options;
924 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
925 struct ppcg_scop *scop, void *user);
926 void *user;
929 /* Should we print the original code?
930 * That is, does "scop" involve any data dependent conditions or
931 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
933 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
935 if (!pet_scop_can_build_ast_exprs(scop)) {
936 if (options->debug->verbose)
937 fprintf(stdout, "Printing original code because "
938 "some index expressions cannot currently "
939 "be printed\n");
940 return 1;
943 if (pet_scop_has_data_dependent_conditions(scop)) {
944 if (options->debug->verbose)
945 fprintf(stdout, "Printing original code because "
946 "input involves data dependent conditions\n");
947 return 1;
950 return 0;
953 /* Callback for pet_transform_C_source that transforms
954 * the given pet_scop to a ppcg_scop before calling the
955 * ppcg_transform callback.
957 * If "scop" contains any data dependent conditions or if we may
958 * not be able to print the transformed program, then just print
959 * the original code.
961 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
962 struct pet_scop *scop, void *user)
964 struct ppcg_transform_data *data = user;
965 struct ppcg_scop *ps;
967 if (print_original(scop, data->options)) {
968 p = pet_scop_print_original(scop, p);
969 pet_scop_free(scop);
970 return p;
973 scop = pet_scop_align_params(scop);
974 ps = ppcg_scop_from_pet_scop(scop, data->options);
976 p = data->transform(p, ps, data->user);
978 ppcg_scop_free(ps);
979 pet_scop_free(scop);
981 return p;
984 /* Transform the C source file "input" by rewriting each scop
985 * through a call to "transform".
986 * The transformed C code is written to "out".
988 * This is a wrapper around pet_transform_C_source that transforms
989 * the pet_scop to a ppcg_scop before calling "fn".
991 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
992 struct ppcg_options *options,
993 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
994 struct ppcg_scop *scop, void *user), void *user)
996 struct ppcg_transform_data data = { options, fn, user };
997 return pet_transform_C_source(ctx, input, out, &transform, &data);
1000 /* Check consistency of options.
1002 * Return -1 on error.
1004 static int check_options(isl_ctx *ctx)
1006 struct options *options;
1008 options = isl_ctx_peek_options(ctx, &options_args);
1009 if (!options)
1010 isl_die(ctx, isl_error_internal,
1011 "unable to find options", return -1);
1013 if (options->ppcg->openmp &&
1014 !isl_options_get_ast_build_atomic_upper_bound(ctx))
1015 isl_die(ctx, isl_error_invalid,
1016 "OpenMP requires atomic bounds", return -1);
1018 return 0;
1021 int main(int argc, char **argv)
1023 int r;
1024 isl_ctx *ctx;
1025 struct options *options;
1027 options = options_new_with_defaults();
1028 assert(options);
1030 ctx = isl_ctx_alloc_with_options(&options_args, options);
1031 ppcg_options_set_target_defaults(options->ppcg);
1032 isl_options_set_ast_build_detect_min_max(ctx, 1);
1033 isl_options_set_ast_print_macro_once(ctx, 1);
1034 isl_options_set_schedule_whole_component(ctx, 0);
1035 isl_options_set_schedule_maximize_band_depth(ctx, 1);
1036 isl_options_set_schedule_maximize_coincidence(ctx, 1);
1037 pet_options_set_encapsulate_dynamic_control(ctx, 1);
1038 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
1040 if (check_options(ctx) < 0)
1041 r = EXIT_FAILURE;
1042 else if (options->ppcg->target == PPCG_TARGET_CUDA)
1043 r = generate_cuda(ctx, options->ppcg, options->input);
1044 else if (options->ppcg->target == PPCG_TARGET_OPENCL)
1045 r = generate_opencl(ctx, options->ppcg, options->input,
1046 options->output);
1047 else
1048 r = generate_cpu(ctx, options->ppcg, options->input,
1049 options->output);
1051 isl_ctx_free(ctx);
1053 return r;