add examples to distribution
[ppcg.git] / ppcg.c
blob81fb944fe73a12b6d9e4638461d978001761a5b2
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/id.h>
20 #include <isl/val.h>
21 #include <isl/set.h>
22 #include <isl/union_set.h>
23 #include <isl/union_map.h>
24 #include <isl/aff.h>
25 #include <isl/flow.h>
26 #include <isl/options.h>
27 #include <isl/schedule.h>
28 #include <isl/ast.h>
29 #include <isl/id_to_ast_expr.h>
30 #include <isl/ast_build.h>
31 #include <isl/schedule.h>
32 #include <pet.h>
33 #include "ppcg.h"
34 #include "ppcg_options.h"
35 #include "cuda.h"
36 #include "opencl.h"
37 #include "cpu.h"
39 struct options {
40 struct pet_options *pet;
41 struct ppcg_options *ppcg;
42 char *input;
43 char *output;
46 const char *ppcg_version(void);
47 static void print_version(void)
49 printf("%s", ppcg_version());
52 ISL_ARGS_START(struct options, options_args)
53 ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
54 ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
55 ISL_ARG_STR(struct options, output, 'o', NULL,
56 "filename", NULL, "output filename (c and opencl targets)")
57 ISL_ARG_ARG(struct options, input, "input", NULL)
58 ISL_ARG_VERSION(print_version)
59 ISL_ARGS_END
61 ISL_ARG_DEF(options, struct options, options_args)
63 /* Return a pointer to the final path component of "filename" or
64 * to "filename" itself if it does not contain any components.
66 const char *ppcg_base_name(const char *filename)
68 const char *base;
70 base = strrchr(filename, '/');
71 if (base)
72 return ++base;
73 else
74 return filename;
77 /* Copy the base name of "input" to "name" and return its length.
78 * "name" is not NULL terminated.
80 * In particular, remove all leading directory components and
81 * the final extension, if any.
83 int ppcg_extract_base_name(char *name, const char *input)
85 const char *base;
86 const char *ext;
87 int len;
89 base = ppcg_base_name(input);
90 ext = strrchr(base, '.');
91 len = ext ? ext - base : strlen(base);
93 memcpy(name, base, len);
95 return len;
98 /* Does "scop" refer to any arrays that are declared, but not
99 * exposed to the code after the scop?
101 int ppcg_scop_any_hidden_declarations(struct ppcg_scop *scop)
103 int i;
105 if (!scop)
106 return 0;
108 for (i = 0; i < scop->pet->n_array; ++i)
109 if (scop->pet->arrays[i]->declared &&
110 !scop->pet->arrays[i]->exposed)
111 return 1;
113 return 0;
116 /* Collect all variable names that are in use in "scop".
117 * In particular, collect all parameters in the context and
118 * all the array names.
119 * Store these names in an isl_id_to_ast_expr by mapping
120 * them to a dummy value (0).
122 static __isl_give isl_id_to_ast_expr *collect_names(struct pet_scop *scop)
124 int i, n;
125 isl_ctx *ctx;
126 isl_ast_expr *zero;
127 isl_id_to_ast_expr *names;
129 ctx = isl_set_get_ctx(scop->context);
131 n = isl_set_dim(scop->context, isl_dim_param);
133 names = isl_id_to_ast_expr_alloc(ctx, n + scop->n_array);
134 zero = isl_ast_expr_from_val(isl_val_zero(ctx));
136 for (i = 0; i < n; ++i) {
137 isl_id *id;
139 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
140 names = isl_id_to_ast_expr_set(names,
141 id, isl_ast_expr_copy(zero));
144 for (i = 0; i < scop->n_array; ++i) {
145 struct pet_array *array = scop->arrays[i];
146 isl_id *id;
148 id = isl_set_get_tuple_id(array->extent);
149 names = isl_id_to_ast_expr_set(names,
150 id, isl_ast_expr_copy(zero));
153 isl_ast_expr_free(zero);
155 return names;
158 /* Return an isl_id called "prefix%d", with "%d" set to "i".
159 * If an isl_id with such a name already appears among the variable names
160 * of "scop", then adjust the name to "prefix%d_%d".
162 static __isl_give isl_id *generate_name(struct ppcg_scop *scop,
163 const char *prefix, int i)
165 int j;
166 char name[16];
167 isl_ctx *ctx;
168 isl_id *id;
169 int has_name;
171 ctx = isl_set_get_ctx(scop->context);
172 snprintf(name, sizeof(name), "%s%d", prefix, i);
173 id = isl_id_alloc(ctx, name, NULL);
175 j = 0;
176 while ((has_name = isl_id_to_ast_expr_has(scop->names, id)) == 1) {
177 isl_id_free(id);
178 snprintf(name, sizeof(name), "%s%d_%d", prefix, i, j++);
179 id = isl_id_alloc(ctx, name, NULL);
182 return has_name < 0 ? isl_id_free(id) : id;
185 /* Return a list of "n" isl_ids of the form "prefix%d".
186 * If an isl_id with such a name already appears among the variable names
187 * of "scop", then adjust the name to "prefix%d_%d".
189 __isl_give isl_id_list *ppcg_scop_generate_names(struct ppcg_scop *scop,
190 int n, const char *prefix)
192 int i;
193 isl_ctx *ctx;
194 isl_id_list *names;
196 ctx = isl_set_get_ctx(scop->context);
197 names = isl_id_list_alloc(ctx, n);
198 for (i = 0; i < n; ++i) {
199 isl_id *id;
201 id = generate_name(scop, prefix, i);
202 names = isl_id_list_add(names, id);
205 return names;
208 /* Is "stmt" not a kill statement?
210 static int is_not_kill(struct pet_stmt *stmt)
212 return !pet_stmt_is_kill(stmt);
215 /* Collect the iteration domains of the statements in "scop" that
216 * satisfy "pred".
218 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
219 int (*pred)(struct pet_stmt *stmt))
221 int i;
222 isl_set *domain_i;
223 isl_union_set *domain;
225 if (!scop)
226 return NULL;
228 domain = isl_union_set_empty(isl_set_get_space(scop->context));
230 for (i = 0; i < scop->n_stmt; ++i) {
231 struct pet_stmt *stmt = scop->stmts[i];
233 if (!pred(stmt))
234 continue;
236 if (stmt->n_arg > 0)
237 isl_die(isl_union_set_get_ctx(domain),
238 isl_error_unsupported,
239 "data dependent conditions not supported",
240 return isl_union_set_free(domain));
242 domain_i = isl_set_copy(scop->stmts[i]->domain);
243 domain = isl_union_set_add_set(domain, domain_i);
246 return domain;
249 /* Collect the iteration domains of the statements in "scop",
250 * skipping kill statements.
252 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
254 return collect_domains(scop, &is_not_kill);
257 /* This function is used as a callback to pet_expr_foreach_call_expr
258 * to detect if there is any call expression in the input expression.
259 * Assign the value 1 to the integer that "user" points to and
260 * abort the search since we have found what we were looking for.
262 static int set_has_call(__isl_keep pet_expr *expr, void *user)
264 int *has_call = user;
266 *has_call = 1;
268 return -1;
271 /* Does "expr" contain any call expressions?
273 static int expr_has_call(__isl_keep pet_expr *expr)
275 int has_call = 0;
277 if (pet_expr_foreach_call_expr(expr, &set_has_call, &has_call) < 0 &&
278 !has_call)
279 return -1;
281 return has_call;
284 /* This function is a callback for pet_tree_foreach_expr.
285 * If "expr" contains any call (sub)expressions, then set *has_call
286 * and abort the search.
288 static int check_call(__isl_keep pet_expr *expr, void *user)
290 int *has_call = user;
292 if (expr_has_call(expr))
293 *has_call = 1;
295 return *has_call ? -1 : 0;
298 /* Does "stmt" contain any call expressions?
300 static int has_call(struct pet_stmt *stmt)
302 int has_call = 0;
304 if (pet_tree_foreach_expr(stmt->body, &check_call, &has_call) < 0 &&
305 !has_call)
306 return -1;
308 return has_call;
311 /* Collect the iteration domains of the statements in "scop"
312 * that contain a call expression.
314 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
316 return collect_domains(scop, &has_call);
319 /* Given a union of "tagged" access relations of the form
321 * [S_i[...] -> R_j[]] -> A_k[...]
323 * project out the "tags" (R_j[]).
324 * That is, return a union of relations of the form
326 * S_i[...] -> A_k[...]
328 static __isl_give isl_union_map *project_out_tags(
329 __isl_take isl_union_map *umap)
331 return isl_union_map_domain_factor_domain(umap);
334 /* Construct a function from tagged iteration domains to the corresponding
335 * untagged iteration domains with as range of the wrapped map in the domain
336 * the reference tags that appear in any of the reads, writes or kills.
337 * Store the result in ps->tagger.
339 * For example, if the statement with iteration space S[i,j]
340 * contains two array references R_1[] and R_2[], then ps->tagger will contain
342 * { [S[i,j] -> R_1[]] -> S[i,j]; [S[i,j] -> R_2[]] -> S[i,j] }
344 static void compute_tagger(struct ppcg_scop *ps)
346 isl_union_map *tagged;
347 isl_union_pw_multi_aff *tagger;
349 tagged = isl_union_map_copy(ps->tagged_reads);
350 tagged = isl_union_map_union(tagged,
351 isl_union_map_copy(ps->tagged_may_writes));
352 tagged = isl_union_map_union(tagged,
353 isl_union_map_copy(ps->tagged_must_kills));
354 tagged = isl_union_map_universe(tagged);
355 tagged = isl_union_set_unwrap(isl_union_map_domain(tagged));
357 tagger = isl_union_map_domain_map_union_pw_multi_aff(tagged);
359 ps->tagger = tagger;
362 /* Compute the live out accesses, i.e., the writes that are
363 * potentially not killed by any kills or any other writes, and
364 * store them in ps->live_out.
366 * We compute the "dependence" of any "kill" (an explicit kill
367 * or a must write) on any may write.
368 * The elements accessed by the may writes with a "depending" kill
369 * also accessing the element are definitely killed.
370 * The remaining may writes can potentially be live out.
372 * The result of the dependence analysis is
374 * { IW -> [IK -> A] }
376 * with IW the instance of the write statement, IK the instance of kill
377 * statement and A the element that was killed.
378 * The range factor range is
380 * { IW -> A }
382 * containing all such pairs for which there is a kill statement instance,
383 * i.e., all pairs that have been killed.
385 static void compute_live_out(struct ppcg_scop *ps)
387 isl_schedule *schedule;
388 isl_union_map *kills;
389 isl_union_map *exposed;
390 isl_union_map *covering;
391 isl_union_access_info *access;
392 isl_union_flow *flow;
394 schedule = isl_schedule_copy(ps->schedule);
395 kills = isl_union_map_union(isl_union_map_copy(ps->must_writes),
396 isl_union_map_copy(ps->must_kills));
397 access = isl_union_access_info_from_sink(kills);
398 access = isl_union_access_info_set_may_source(access,
399 isl_union_map_copy(ps->may_writes));
400 access = isl_union_access_info_set_schedule(access, schedule);
401 flow = isl_union_access_info_compute_flow(access);
402 covering = isl_union_flow_get_full_may_dependence(flow);
403 isl_union_flow_free(flow);
405 covering = isl_union_map_range_factor_range(covering);
406 exposed = isl_union_map_copy(ps->may_writes);
407 exposed = isl_union_map_subtract(exposed, covering);
408 ps->live_out = exposed;
411 /* Compute the tagged flow dependences and the live_in accesses and store
412 * the results in ps->tagged_dep_flow and ps->live_in.
414 * We allow both the must writes and the must kills to serve as
415 * definite sources such that a subsequent read would not depend
416 * on any earlier write. The resulting flow dependences with
417 * a must kill as source reflect possibly uninitialized reads.
418 * No dependences need to be introduced to protect such reads
419 * (other than those imposed by potential flows from may writes
420 * that follow the kill). We therefore remove those flow dependences.
421 * This is also useful for the dead code elimination, which assumes
422 * the flow sources are non-kill instances.
424 static void compute_tagged_flow_dep_only(struct ppcg_scop *ps)
426 isl_union_pw_multi_aff *tagger;
427 isl_schedule *schedule;
428 isl_union_map *live_in;
429 isl_union_access_info *access;
430 isl_union_flow *flow;
431 isl_union_map *must_source;
432 isl_union_map *kills;
433 isl_union_map *tagged_flow;
435 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
436 schedule = isl_schedule_copy(ps->schedule);
437 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
438 kills = isl_union_map_copy(ps->tagged_must_kills);
439 must_source = isl_union_map_copy(ps->tagged_must_writes);
440 must_source = isl_union_map_union(must_source,
441 isl_union_map_copy(kills));
442 access = isl_union_access_info_from_sink(
443 isl_union_map_copy(ps->tagged_reads));
444 access = isl_union_access_info_set_must_source(access, must_source);
445 access = isl_union_access_info_set_may_source(access,
446 isl_union_map_copy(ps->tagged_may_writes));
447 access = isl_union_access_info_set_schedule(access, schedule);
448 flow = isl_union_access_info_compute_flow(access);
449 tagged_flow = isl_union_flow_get_may_dependence(flow);
450 tagged_flow = isl_union_map_subtract_domain(tagged_flow,
451 isl_union_map_domain(kills));
452 ps->tagged_dep_flow = tagged_flow;
453 live_in = isl_union_flow_get_may_no_source(flow);
454 ps->live_in = project_out_tags(live_in);
455 isl_union_flow_free(flow);
458 /* Compute ps->dep_flow from ps->tagged_dep_flow
459 * by projecting out the reference tags.
461 static void derive_flow_dep_from_tagged_flow_dep(struct ppcg_scop *ps)
463 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
464 ps->dep_flow = isl_union_map_factor_domain(ps->dep_flow);
467 /* Compute the flow dependences and the live_in accesses and store
468 * the results in ps->dep_flow and ps->live_in.
469 * A copy of the flow dependences, tagged with the reference tags
470 * is stored in ps->tagged_dep_flow.
472 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
473 * and then project out the tags.
475 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
477 compute_tagged_flow_dep_only(ps);
478 derive_flow_dep_from_tagged_flow_dep(ps);
481 /* Compute the order dependences that prevent the potential live ranges
482 * from overlapping.
484 * In particular, construct a union of relations
486 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
488 * where [R[...] -> R_1[]] is the range of one or more live ranges
489 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
490 * live ranges (i.e., a write). Moreover, the read and the write
491 * access the same memory element and the read occurs before the write
492 * in the original schedule.
493 * The scheduler allows some of these dependences to be violated, provided
494 * the adjacent live ranges are all local (i.e., their domain and range
495 * are mapped to the same point by the current schedule band).
497 * Note that if a live range is not local, then we need to make
498 * sure it does not overlap with _any_ other live range, and not
499 * just with the "previous" and/or the "next" live range.
500 * We therefore add order dependences between reads and
501 * _any_ later potential write.
503 * We also need to be careful about writes without a corresponding read.
504 * They are already prevented from moving past non-local preceding
505 * intervals, but we also need to prevent them from moving past non-local
506 * following intervals. We therefore also add order dependences from
507 * potential writes that do not appear in any intervals
508 * to all later potential writes.
509 * Note that dead code elimination should have removed most of these
510 * dead writes, but the dead code elimination may not remove all dead writes,
511 * so we need to consider them to be safe.
513 * The order dependences are computed by computing the "dataflow"
514 * from the above unmatched writes and the reads to the may writes.
515 * The unmatched writes and the reads are treated as may sources
516 * such that they would not kill order dependences from earlier
517 * such writes and reads.
519 static void compute_order_dependences(struct ppcg_scop *ps)
521 isl_union_map *reads;
522 isl_union_map *shared_access;
523 isl_union_set *matched;
524 isl_union_map *unmatched;
525 isl_union_pw_multi_aff *tagger;
526 isl_schedule *schedule;
527 isl_union_access_info *access;
528 isl_union_flow *flow;
530 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
531 schedule = isl_schedule_copy(ps->schedule);
532 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
533 reads = isl_union_map_copy(ps->tagged_reads);
534 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
535 unmatched = isl_union_map_copy(ps->tagged_may_writes);
536 unmatched = isl_union_map_subtract_domain(unmatched, matched);
537 reads = isl_union_map_union(reads, unmatched);
538 access = isl_union_access_info_from_sink(
539 isl_union_map_copy(ps->tagged_may_writes));
540 access = isl_union_access_info_set_may_source(access, reads);
541 access = isl_union_access_info_set_schedule(access, schedule);
542 flow = isl_union_access_info_compute_flow(access);
543 shared_access = isl_union_flow_get_may_dependence(flow);
544 isl_union_flow_free(flow);
546 ps->tagged_dep_order = isl_union_map_copy(shared_access);
547 ps->dep_order = isl_union_map_factor_domain(shared_access);
550 /* Compute those validity dependences of the program represented by "scop"
551 * that should be unconditionally enforced even when live-range reordering
552 * is used.
554 * In particular, compute the external false dependences
555 * as well as order dependences between sources with the same sink.
556 * The anti-dependences are already taken care of by the order dependences.
557 * The external false dependences are only used to ensure that live-in and
558 * live-out data is not overwritten by any writes inside the scop.
559 * The independences are removed from the external false dependences,
560 * but not from the order dependences between sources with the same sink.
562 * In particular, the reads from live-in data need to precede any
563 * later write to the same memory element.
564 * As to live-out data, the last writes need to remain the last writes.
565 * That is, any earlier write in the original schedule needs to precede
566 * the last write to the same memory element in the computed schedule.
567 * The possible last writes have been computed by compute_live_out.
568 * They may include kills, but if the last access is a kill,
569 * then the corresponding dependences will effectively be ignored
570 * since we do not schedule any kill statements.
572 * Note that the set of live-in and live-out accesses may be
573 * an overapproximation. There may therefore be potential writes
574 * before a live-in access and after a live-out access.
576 * In the presence of may-writes, there may be multiple live-ranges
577 * with the same sink, accessing the same memory element.
578 * The sources of these live-ranges need to be executed
579 * in the same relative order as in the original program
580 * since we do not know which of the may-writes will actually
581 * perform a write. Consider all sources that share a sink and
582 * that may write to the same memory element and compute
583 * the order dependences among them.
585 static void compute_forced_dependences(struct ppcg_scop *ps)
587 isl_union_map *shared_access;
588 isl_union_map *exposed;
589 isl_union_map *live_in;
590 isl_union_map *sink_access;
591 isl_union_map *shared_sink;
592 isl_union_access_info *access;
593 isl_union_flow *flow;
594 isl_schedule *schedule;
596 exposed = isl_union_map_copy(ps->live_out);
597 schedule = isl_schedule_copy(ps->schedule);
598 access = isl_union_access_info_from_sink(exposed);
599 access = isl_union_access_info_set_may_source(access,
600 isl_union_map_copy(ps->may_writes));
601 access = isl_union_access_info_set_schedule(access, schedule);
602 flow = isl_union_access_info_compute_flow(access);
603 shared_access = isl_union_flow_get_may_dependence(flow);
604 isl_union_flow_free(flow);
605 ps->dep_forced = shared_access;
607 schedule = isl_schedule_copy(ps->schedule);
608 access = isl_union_access_info_from_sink(
609 isl_union_map_copy(ps->may_writes));
610 access = isl_union_access_info_set_may_source(access,
611 isl_union_map_copy(ps->live_in));
612 access = isl_union_access_info_set_schedule(access, schedule);
613 flow = isl_union_access_info_compute_flow(access);
614 live_in = isl_union_flow_get_may_dependence(flow);
615 isl_union_flow_free(flow);
617 ps->dep_forced = isl_union_map_union(ps->dep_forced, live_in);
618 ps->dep_forced = isl_union_map_subtract(ps->dep_forced,
619 isl_union_map_copy(ps->independence));
621 schedule = isl_schedule_copy(ps->schedule);
622 sink_access = isl_union_map_copy(ps->tagged_dep_flow);
623 sink_access = isl_union_map_range_product(sink_access,
624 isl_union_map_copy(ps->tagged_may_writes));
625 sink_access = isl_union_map_domain_factor_domain(sink_access);
626 access = isl_union_access_info_from_sink(
627 isl_union_map_copy(sink_access));
628 access = isl_union_access_info_set_may_source(access, sink_access);
629 access = isl_union_access_info_set_schedule(access, schedule);
630 flow = isl_union_access_info_compute_flow(access);
631 shared_sink = isl_union_flow_get_may_dependence(flow);
632 isl_union_flow_free(flow);
633 ps->dep_forced = isl_union_map_union(ps->dep_forced, shared_sink);
636 /* Remove independence from the tagged flow dependences.
637 * Since the user has guaranteed that source and sink of an independence
638 * can be executed in any order, there cannot be a flow dependence
639 * between them, so they can be removed from the set of flow dependences.
640 * However, if the source of such a flow dependence is a must write,
641 * then it may have killed other potential sources, which would have
642 * to be recovered if we were to remove those flow dependences.
643 * We therefore keep the flow dependences that originate in a must write,
644 * even if it corresponds to a known independence.
646 static void remove_independences_from_tagged_flow(struct ppcg_scop *ps)
648 isl_union_map *tf;
649 isl_union_set *indep;
650 isl_union_set *mw;
652 tf = isl_union_map_copy(ps->tagged_dep_flow);
653 tf = isl_union_map_zip(tf);
654 indep = isl_union_map_wrap(isl_union_map_copy(ps->independence));
655 tf = isl_union_map_intersect_domain(tf, indep);
656 tf = isl_union_map_zip(tf);
657 mw = isl_union_map_domain(isl_union_map_copy(ps->tagged_must_writes));
658 tf = isl_union_map_subtract_domain(tf, mw);
659 ps->tagged_dep_flow = isl_union_map_subtract(ps->tagged_dep_flow, tf);
662 /* Compute the dependences of the program represented by "scop"
663 * in case live range reordering is allowed.
665 * We compute the actual live ranges and the corresponding order
666 * false dependences.
668 * The independences are removed from the flow dependences
669 * (provided the source is not a must-write) as well as
670 * from the external false dependences (by compute_forced_dependences).
672 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
674 compute_tagged_flow_dep_only(ps);
675 remove_independences_from_tagged_flow(ps);
676 derive_flow_dep_from_tagged_flow_dep(ps);
677 compute_order_dependences(ps);
678 compute_forced_dependences(ps);
681 /* Compute the potential flow dependences and the potential live in
682 * accesses.
684 static void compute_flow_dep(struct ppcg_scop *ps)
686 isl_union_access_info *access;
687 isl_union_flow *flow;
689 access = isl_union_access_info_from_sink(isl_union_map_copy(ps->reads));
690 access = isl_union_access_info_set_must_source(access,
691 isl_union_map_copy(ps->must_writes));
692 access = isl_union_access_info_set_may_source(access,
693 isl_union_map_copy(ps->may_writes));
694 access = isl_union_access_info_set_schedule(access,
695 isl_schedule_copy(ps->schedule));
696 flow = isl_union_access_info_compute_flow(access);
698 ps->dep_flow = isl_union_flow_get_may_dependence(flow);
699 ps->live_in = isl_union_flow_get_may_no_source(flow);
700 isl_union_flow_free(flow);
703 /* Compute the dependences of the program represented by "scop".
704 * Store the computed potential flow dependences
705 * in scop->dep_flow and the reads with potentially no corresponding writes in
706 * scop->live_in.
707 * Store the potential live out accesses in scop->live_out.
708 * Store the potential false (anti and output) dependences in scop->dep_false.
710 * If live range reordering is allowed, then we compute a separate
711 * set of order dependences and a set of external false dependences
712 * in compute_live_range_reordering_dependences.
714 static void compute_dependences(struct ppcg_scop *scop)
716 isl_union_map *may_source;
717 isl_union_access_info *access;
718 isl_union_flow *flow;
720 if (!scop)
721 return;
723 compute_live_out(scop);
725 if (scop->options->live_range_reordering)
726 compute_live_range_reordering_dependences(scop);
727 else if (scop->options->target != PPCG_TARGET_C)
728 compute_tagged_flow_dep(scop);
729 else
730 compute_flow_dep(scop);
732 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
733 isl_union_map_copy(scop->reads));
734 access = isl_union_access_info_from_sink(
735 isl_union_map_copy(scop->may_writes));
736 access = isl_union_access_info_set_must_source(access,
737 isl_union_map_copy(scop->must_writes));
738 access = isl_union_access_info_set_may_source(access, may_source);
739 access = isl_union_access_info_set_schedule(access,
740 isl_schedule_copy(scop->schedule));
741 flow = isl_union_access_info_compute_flow(access);
743 scop->dep_false = isl_union_flow_get_may_dependence(flow);
744 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
745 isl_union_flow_free(flow);
748 /* Eliminate dead code from ps->domain.
750 * In particular, intersect both ps->domain and the domain of
751 * ps->schedule with the (parts of) iteration
752 * domains that are needed to produce the output or for statement
753 * iterations that call functions.
754 * Also intersect the range of the dataflow dependences with
755 * this domain such that the removed instances will no longer
756 * be considered as targets of dataflow.
758 * We start with the iteration domains that call functions
759 * and the set of iterations that last write to an array
760 * (except those that are later killed).
762 * Then we add those statement iterations that produce
763 * something needed by the "live" statements iterations.
764 * We keep doing this until no more statement iterations can be added.
765 * To ensure that the procedure terminates, we compute the affine
766 * hull of the live iterations (bounded to the original iteration
767 * domains) each time we have added extra iterations.
769 static void eliminate_dead_code(struct ppcg_scop *ps)
771 isl_union_set *live;
772 isl_union_map *dep;
773 isl_union_pw_multi_aff *tagger;
775 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
776 if (!isl_union_set_is_empty(ps->call)) {
777 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
778 live = isl_union_set_coalesce(live);
781 dep = isl_union_map_copy(ps->dep_flow);
782 dep = isl_union_map_reverse(dep);
784 for (;;) {
785 isl_union_set *extra;
787 extra = isl_union_set_apply(isl_union_set_copy(live),
788 isl_union_map_copy(dep));
789 if (isl_union_set_is_subset(extra, live)) {
790 isl_union_set_free(extra);
791 break;
794 live = isl_union_set_union(live, extra);
795 live = isl_union_set_affine_hull(live);
796 live = isl_union_set_intersect(live,
797 isl_union_set_copy(ps->domain));
800 isl_union_map_free(dep);
802 ps->domain = isl_union_set_intersect(ps->domain,
803 isl_union_set_copy(live));
804 ps->schedule = isl_schedule_intersect_domain(ps->schedule,
805 isl_union_set_copy(live));
806 ps->dep_flow = isl_union_map_intersect_range(ps->dep_flow,
807 isl_union_set_copy(live));
808 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
809 live = isl_union_set_preimage_union_pw_multi_aff(live, tagger);
810 ps->tagged_dep_flow = isl_union_map_intersect_range(ps->tagged_dep_flow,
811 live);
814 /* Intersect "set" with the set described by "str", taking the NULL
815 * string to represent the universal set.
817 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
818 const char *str)
820 isl_ctx *ctx;
821 isl_set *set2;
823 if (!str)
824 return set;
826 ctx = isl_set_get_ctx(set);
827 set2 = isl_set_read_from_str(ctx, str);
828 set = isl_set_intersect(set, set2);
830 return set;
833 static void *ppcg_scop_free(struct ppcg_scop *ps)
835 if (!ps)
836 return NULL;
838 isl_set_free(ps->context);
839 isl_union_set_free(ps->domain);
840 isl_union_set_free(ps->call);
841 isl_union_map_free(ps->tagged_reads);
842 isl_union_map_free(ps->reads);
843 isl_union_map_free(ps->live_in);
844 isl_union_map_free(ps->tagged_may_writes);
845 isl_union_map_free(ps->tagged_must_writes);
846 isl_union_map_free(ps->may_writes);
847 isl_union_map_free(ps->must_writes);
848 isl_union_map_free(ps->live_out);
849 isl_union_map_free(ps->tagged_must_kills);
850 isl_union_map_free(ps->must_kills);
851 isl_union_map_free(ps->tagged_dep_flow);
852 isl_union_map_free(ps->dep_flow);
853 isl_union_map_free(ps->dep_false);
854 isl_union_map_free(ps->dep_forced);
855 isl_union_map_free(ps->tagged_dep_order);
856 isl_union_map_free(ps->dep_order);
857 isl_schedule_free(ps->schedule);
858 isl_union_pw_multi_aff_free(ps->tagger);
859 isl_union_map_free(ps->independence);
860 isl_id_to_ast_expr_free(ps->names);
862 free(ps);
864 return NULL;
867 /* Extract a ppcg_scop from a pet_scop.
869 * The constructed ppcg_scop refers to elements from the pet_scop
870 * so the pet_scop should not be freed before the ppcg_scop.
872 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
873 struct ppcg_options *options)
875 int i;
876 isl_ctx *ctx;
877 struct ppcg_scop *ps;
879 if (!scop)
880 return NULL;
882 ctx = isl_set_get_ctx(scop->context);
884 ps = isl_calloc_type(ctx, struct ppcg_scop);
885 if (!ps)
886 return NULL;
888 ps->names = collect_names(scop);
889 ps->options = options;
890 ps->start = pet_loc_get_start(scop->loc);
891 ps->end = pet_loc_get_end(scop->loc);
892 ps->context = isl_set_copy(scop->context);
893 ps->context = set_intersect_str(ps->context, options->ctx);
894 if (options->non_negative_parameters) {
895 isl_space *space = isl_set_get_space(ps->context);
896 isl_set *nn = isl_set_nat_universe(space);
897 ps->context = isl_set_intersect(ps->context, nn);
899 ps->domain = collect_non_kill_domains(scop);
900 ps->call = collect_call_domains(scop);
901 ps->tagged_reads = pet_scop_get_tagged_may_reads(scop);
902 ps->reads = pet_scop_get_may_reads(scop);
903 ps->tagged_may_writes = pet_scop_get_tagged_may_writes(scop);
904 ps->may_writes = pet_scop_get_may_writes(scop);
905 ps->tagged_must_writes = pet_scop_get_tagged_must_writes(scop);
906 ps->must_writes = pet_scop_get_must_writes(scop);
907 ps->tagged_must_kills = pet_scop_get_tagged_must_kills(scop);
908 ps->must_kills = pet_scop_get_must_kills(scop);
909 ps->schedule = isl_schedule_copy(scop->schedule);
910 ps->pet = scop;
911 ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
912 for (i = 0; i < scop->n_independence; ++i)
913 ps->independence = isl_union_map_union(ps->independence,
914 isl_union_map_copy(scop->independences[i]->filter));
916 compute_tagger(ps);
917 compute_dependences(ps);
918 eliminate_dead_code(ps);
920 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
921 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
922 !ps->must_kills || !ps->schedule || !ps->independence || !ps->names)
923 return ppcg_scop_free(ps);
925 return ps;
928 /* Internal data structure for ppcg_transform.
930 struct ppcg_transform_data {
931 struct ppcg_options *options;
932 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
933 struct ppcg_scop *scop, void *user);
934 void *user;
937 /* Should we print the original code?
938 * That is, does "scop" involve any data dependent conditions or
939 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
941 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
943 if (!pet_scop_can_build_ast_exprs(scop)) {
944 if (options->debug->verbose)
945 fprintf(stdout, "Printing original code because "
946 "some index expressions cannot currently "
947 "be printed\n");
948 return 1;
951 if (pet_scop_has_data_dependent_conditions(scop)) {
952 if (options->debug->verbose)
953 fprintf(stdout, "Printing original code because "
954 "input involves data dependent conditions\n");
955 return 1;
958 return 0;
961 /* Callback for pet_transform_C_source that transforms
962 * the given pet_scop to a ppcg_scop before calling the
963 * ppcg_transform callback.
965 * If "scop" contains any data dependent conditions or if we may
966 * not be able to print the transformed program, then just print
967 * the original code.
969 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
970 struct pet_scop *scop, void *user)
972 struct ppcg_transform_data *data = user;
973 struct ppcg_scop *ps;
975 if (print_original(scop, data->options)) {
976 p = pet_scop_print_original(scop, p);
977 pet_scop_free(scop);
978 return p;
981 scop = pet_scop_align_params(scop);
982 ps = ppcg_scop_from_pet_scop(scop, data->options);
984 p = data->transform(p, ps, data->user);
986 ppcg_scop_free(ps);
987 pet_scop_free(scop);
989 return p;
992 /* Transform the C source file "input" by rewriting each scop
993 * through a call to "transform".
994 * The transformed C code is written to "out".
996 * This is a wrapper around pet_transform_C_source that transforms
997 * the pet_scop to a ppcg_scop before calling "fn".
999 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
1000 struct ppcg_options *options,
1001 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
1002 struct ppcg_scop *scop, void *user), void *user)
1004 struct ppcg_transform_data data = { options, fn, user };
1005 return pet_transform_C_source(ctx, input, out, &transform, &data);
1008 /* Check consistency of options.
1010 * Return -1 on error.
1012 static int check_options(isl_ctx *ctx)
1014 struct options *options;
1016 options = isl_ctx_peek_options(ctx, &options_args);
1017 if (!options)
1018 isl_die(ctx, isl_error_internal,
1019 "unable to find options", return -1);
1021 if (options->ppcg->openmp &&
1022 !isl_options_get_ast_build_atomic_upper_bound(ctx))
1023 isl_die(ctx, isl_error_invalid,
1024 "OpenMP requires atomic bounds", return -1);
1026 return 0;
1029 int main(int argc, char **argv)
1031 int r;
1032 isl_ctx *ctx;
1033 struct options *options;
1035 options = options_new_with_defaults();
1036 assert(options);
1038 ctx = isl_ctx_alloc_with_options(&options_args, options);
1039 ppcg_options_set_target_defaults(options->ppcg);
1040 isl_options_set_ast_build_detect_min_max(ctx, 1);
1041 isl_options_set_ast_print_macro_once(ctx, 1);
1042 isl_options_set_schedule_whole_component(ctx, 0);
1043 isl_options_set_schedule_maximize_band_depth(ctx, 1);
1044 isl_options_set_schedule_maximize_coincidence(ctx, 1);
1045 pet_options_set_encapsulate_dynamic_control(ctx, 1);
1046 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
1048 if (check_options(ctx) < 0)
1049 r = EXIT_FAILURE;
1050 else if (options->ppcg->target == PPCG_TARGET_CUDA)
1051 r = generate_cuda(ctx, options->ppcg, options->input);
1052 else if (options->ppcg->target == PPCG_TARGET_OPENCL)
1053 r = generate_opencl(ctx, options->ppcg, options->input,
1054 options->output);
1055 else
1056 r = generate_cpu(ctx, options->ppcg, options->input,
1057 options->output);
1059 isl_ctx_free(ctx);
1061 return r;