gpu_array_ref_group: clarify documentation
[ppcg.git] / ppcg.c
blob3417902c2cab45fbcd46fabf608467270c80731b
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 * Copyright 2015 Sven Verdoolaege
5 *
6 * Use of this software is governed by the MIT license
7 *
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
12 */
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;
37 };
39 const char *ppcg_version(void);
40 static void print_version(void)
41 {
42 printf("%s", ppcg_version());
43 }
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.
59 */
60 const char *ppcg_base_name(const char *filename)
61 {
62 const char *base;
64 base = strrchr(filename, '/');
65 if (base)
66 return ++base;
67 else
68 return filename;
69 }
71 /* Copy the base name of "input" to "name" and return its length.
72 * "name" is not NULL terminated.
73 *
74 * In particular, remove all leading directory components and
75 * the final extension, if any.
76 */
77 int ppcg_extract_base_name(char *name, const char *input)
78 {
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;
90 }
92 /* Does "scop" refer to any arrays that are declared, but not
93 * exposed to the code after the scop?
94 */
95 int ppcg_scop_any_hidden_declarations(struct ppcg_scop *scop)
96 {
97 int i;
99 if (!scop)
100 return 0;
102 for (i = 0; i < scop->pet->n_array; ++i)
103 if (scop->pet->arrays[i]->declared &&
104 !scop->pet->arrays[i]->exposed)
105 return 1;
107 return 0;
110 /* Collect all variable names that are in use in "scop".
111 * In particular, collect all parameters in the context and
112 * all the array names.
113 * Store these names in an isl_id_to_ast_expr by mapping
114 * them to a dummy value (0).
115 */
116 static __isl_give isl_id_to_ast_expr *collect_names(struct pet_scop *scop)
118 int i, n;
119 isl_ctx *ctx;
120 isl_ast_expr *zero;
121 isl_id_to_ast_expr *names;
123 ctx = isl_set_get_ctx(scop->context);
125 n = isl_set_dim(scop->context, isl_dim_param);
127 names = isl_id_to_ast_expr_alloc(ctx, n + scop->n_array);
128 zero = isl_ast_expr_from_val(isl_val_zero(ctx));
130 for (i = 0; i < n; ++i) {
131 isl_id *id;
133 id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
134 names = isl_id_to_ast_expr_set(names,
135 id, isl_ast_expr_copy(zero));
138 for (i = 0; i < scop->n_array; ++i) {
139 struct pet_array *array = scop->arrays[i];
140 isl_id *id;
142 id = isl_set_get_tuple_id(array->extent);
143 names = isl_id_to_ast_expr_set(names,
144 id, isl_ast_expr_copy(zero));
147 isl_ast_expr_free(zero);
149 return names;
152 /* Return an isl_id called "prefix%d", with "%d" set to "i".
153 * If an isl_id with such a name already appears among the variable names
154 * of "scop", then adjust the name to "prefix%d_%d".
155 */
156 static __isl_give isl_id *generate_name(struct ppcg_scop *scop,
157 const char *prefix, int i)
159 int j;
160 char name[16];
161 isl_ctx *ctx;
162 isl_id *id;
163 int has_name;
165 ctx = isl_set_get_ctx(scop->context);
166 snprintf(name, sizeof(name), "%s%d", prefix, i);
167 id = isl_id_alloc(ctx, name, NULL);
169 j = 0;
170 while ((has_name = isl_id_to_ast_expr_has(scop->names, id)) == 1) {
171 isl_id_free(id);
172 snprintf(name, sizeof(name), "%s%d_%d", prefix, i, j++);
173 id = isl_id_alloc(ctx, name, NULL);
176 return has_name < 0 ? isl_id_free(id) : id;
179 /* Return a list of "n" isl_ids of the form "prefix%d".
180 * If an isl_id with such a name already appears among the variable names
181 * of "scop", then adjust the name to "prefix%d_%d".
182 */
183 __isl_give isl_id_list *ppcg_scop_generate_names(struct ppcg_scop *scop,
184 int n, const char *prefix)
186 int i;
187 char name[10];
188 isl_ctx *ctx;
189 isl_id_list *names;
191 ctx = isl_set_get_ctx(scop->context);
192 names = isl_id_list_alloc(ctx, n);
193 for (i = 0; i < n; ++i) {
194 isl_id *id;
196 id = generate_name(scop, prefix, i);
197 names = isl_id_list_add(names, id);
200 return names;
203 /* Is "stmt" not a kill statement?
204 */
205 static int is_not_kill(struct pet_stmt *stmt)
207 return !pet_stmt_is_kill(stmt);
210 /* Collect the iteration domains of the statements in "scop" that
211 * satisfy "pred".
212 */
213 static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
214 int (*pred)(struct pet_stmt *stmt))
216 int i;
217 isl_set *domain_i;
218 isl_union_set *domain;
220 if (!scop)
221 return NULL;
223 domain = isl_union_set_empty(isl_set_get_space(scop->context));
225 for (i = 0; i < scop->n_stmt; ++i) {
226 struct pet_stmt *stmt = scop->stmts[i];
228 if (!pred(stmt))
229 continue;
231 if (stmt->n_arg > 0)
232 isl_die(isl_union_set_get_ctx(domain),
233 isl_error_unsupported,
234 "data dependent conditions not supported",
235 return isl_union_set_free(domain));
237 domain_i = isl_set_copy(scop->stmts[i]->domain);
238 domain = isl_union_set_add_set(domain, domain_i);
241 return domain;
244 /* Collect the iteration domains of the statements in "scop",
245 * skipping kill statements.
246 */
247 static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
249 return collect_domains(scop, &is_not_kill);
252 /* This function is used as a callback to pet_expr_foreach_call_expr
253 * to detect if there is any call expression in the input expression.
254 * Assign the value 1 to the integer that "user" points to and
255 * abort the search since we have found what we were looking for.
256 */
257 static int set_has_call(__isl_keep pet_expr *expr, void *user)
259 int *has_call = user;
261 *has_call = 1;
263 return -1;
266 /* Does "expr" contain any call expressions?
267 */
268 static int expr_has_call(__isl_keep pet_expr *expr)
270 int has_call = 0;
272 if (pet_expr_foreach_call_expr(expr, &set_has_call, &has_call) < 0 &&
273 !has_call)
274 return -1;
276 return has_call;
279 /* This function is a callback for pet_tree_foreach_expr.
280 * If "expr" contains any call (sub)expressions, then set *has_call
281 * and abort the search.
282 */
283 static int check_call(__isl_keep pet_expr *expr, void *user)
285 int *has_call = user;
287 if (expr_has_call(expr))
288 *has_call = 1;
290 return *has_call ? -1 : 0;
293 /* Does "stmt" contain any call expressions?
294 */
295 static int has_call(struct pet_stmt *stmt)
297 int has_call = 0;
299 if (pet_tree_foreach_expr(stmt->body, &check_call, &has_call) < 0 &&
300 !has_call)
301 return -1;
303 return has_call;
306 /* Collect the iteration domains of the statements in "scop"
307 * that contain a call expression.
308 */
309 static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
311 return collect_domains(scop, &has_call);
314 /* Given a union of "tagged" access relations of the form
316 * [S_i[...] -> R_j[]] -> A_k[...]
318 * project out the "tags" (R_j[]).
319 * That is, return a union of relations of the form
321 * S_i[...] -> A_k[...]
322 */
323 static __isl_give isl_union_map *project_out_tags(
324 __isl_take isl_union_map *umap)
326 return isl_union_map_domain_factor_domain(umap);
329 /* Construct a function from tagged iteration domains to the corresponding
330 * untagged iteration domains with as range of the wrapped map in the domain
331 * the reference tags that appear in any of the reads, writes or kills.
332 * Store the result in ps->tagger.
334 * For example, if the statement with iteration space S[i,j]
335 * contains two array references R_1[] and R_2[], then ps->tagger will contain
337 * { [S[i,j] -> R_1[]] -> S[i,j]; [S[i,j] -> R_2[]] -> S[i,j] }
338 */
339 static void compute_tagger(struct ppcg_scop *ps)
341 isl_union_map *tagged;
342 isl_union_pw_multi_aff *tagger;
344 tagged = isl_union_map_copy(ps->tagged_reads);
345 tagged = isl_union_map_union(tagged,
346 isl_union_map_copy(ps->tagged_may_writes));
347 tagged = isl_union_map_union(tagged,
348 isl_union_map_copy(ps->tagged_must_kills));
349 tagged = isl_union_map_universe(tagged);
350 tagged = isl_union_set_unwrap(isl_union_map_domain(tagged));
352 tagger = isl_union_map_domain_map_union_pw_multi_aff(tagged);
354 ps->tagger = tagger;
357 /* Compute the live out accesses, i.e., the writes that are
358 * potentially not killed by any kills or any other writes, and
359 * store them in ps->live_out.
361 * We compute the "dependence" of any "kill" (an explicit kill
362 * or a must write) on any may write.
363 * The may writes with a "depending" kill are definitely killed.
364 * The remaining may writes can potentially be live out.
365 */
366 static void compute_live_out(struct ppcg_scop *ps)
368 isl_union_pw_multi_aff *tagger;
369 isl_schedule *schedule;
370 isl_union_map *kills;
371 isl_union_map *exposed;
372 isl_union_map *covering;
373 isl_union_access_info *access;
374 isl_union_flow *flow;
376 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
377 schedule = isl_schedule_copy(ps->schedule);
378 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
379 kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
380 isl_union_map_copy(ps->tagged_must_kills));
381 access = isl_union_access_info_from_sink(kills);
382 access = isl_union_access_info_set_may_source(access,
383 isl_union_map_copy(ps->tagged_may_writes));
384 access = isl_union_access_info_set_schedule(access, schedule);
385 flow = isl_union_access_info_compute_flow(access);
386 covering = isl_union_flow_get_may_dependence(flow);
387 isl_union_flow_free(flow);
388 exposed = isl_union_map_copy(ps->tagged_may_writes);
389 exposed = isl_union_map_subtract_domain(exposed,
390 isl_union_map_domain(covering));
391 ps->live_out = project_out_tags(exposed);
394 /* Compute the tagged flow dependences and the live_in accesses and store
395 * the results in ps->tagged_dep_flow and ps->live_in.
397 * We allow both the must writes and the must kills to serve as
398 * definite sources such that a subsequent read would not depend
399 * on any earlier write. The resulting flow dependences with
400 * a must kill as source reflect possibly uninitialized reads.
401 * No dependences need to be introduced to protect such reads
402 * (other than those imposed by potential flows from may writes
403 * that follow the kill). We therefore remove those flow dependences.
404 * This is also useful for the dead code elimination, which assumes
405 * the flow sources are non-kill instances.
406 */
407 static void compute_tagged_flow_dep_only(struct ppcg_scop *ps)
409 isl_union_pw_multi_aff *tagger;
410 isl_schedule *schedule;
411 isl_union_map *live_in;
412 isl_union_access_info *access;
413 isl_union_flow *flow;
414 isl_union_map *must_source;
415 isl_union_map *kills;
416 isl_union_map *tagged_flow;
418 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
419 schedule = isl_schedule_copy(ps->schedule);
420 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
421 kills = isl_union_map_copy(ps->tagged_must_kills);
422 must_source = isl_union_map_copy(ps->tagged_must_writes);
423 must_source = isl_union_map_union(must_source,
424 isl_union_map_copy(kills));
425 access = isl_union_access_info_from_sink(
426 isl_union_map_copy(ps->tagged_reads));
427 access = isl_union_access_info_set_must_source(access, must_source);
428 access = isl_union_access_info_set_may_source(access,
429 isl_union_map_copy(ps->tagged_may_writes));
430 access = isl_union_access_info_set_schedule(access, schedule);
431 flow = isl_union_access_info_compute_flow(access);
432 tagged_flow = isl_union_flow_get_may_dependence(flow);
433 tagged_flow = isl_union_map_subtract_domain(tagged_flow,
434 isl_union_map_domain(kills));
435 ps->tagged_dep_flow = tagged_flow;
436 live_in = isl_union_flow_get_may_no_source(flow);
437 ps->live_in = project_out_tags(live_in);
438 isl_union_flow_free(flow);
441 /* Compute ps->dep_flow from ps->tagged_dep_flow
442 * by projecting out the reference tags.
443 */
444 static void derive_flow_dep_from_tagged_flow_dep(struct ppcg_scop *ps)
446 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
447 ps->dep_flow = isl_union_map_factor_domain(ps->dep_flow);
450 /* Compute the flow dependences and the live_in accesses and store
451 * the results in ps->dep_flow and ps->live_in.
452 * A copy of the flow dependences, tagged with the reference tags
453 * is stored in ps->tagged_dep_flow.
455 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
456 * and then project out the tags.
457 */
458 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
460 compute_tagged_flow_dep_only(ps);
461 derive_flow_dep_from_tagged_flow_dep(ps);
464 /* Compute the order dependences that prevent the potential live ranges
465 * from overlapping.
467 * In particular, construct a union of relations
469 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
471 * where [R[...] -> R_1[]] is the range of one or more live ranges
472 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
473 * live ranges (i.e., a write). Moreover, the read and the write
474 * access the same memory element and the read occurs before the write
475 * in the original schedule.
476 * The scheduler allows some of these dependences to be violated, provided
477 * the adjacent live ranges are all local (i.e., their domain and range
478 * are mapped to the same point by the current schedule band).
480 * Note that if a live range is not local, then we need to make
481 * sure it does not overlap with _any_ other live range, and not
482 * just with the "previous" and/or the "next" live range.
483 * We therefore add order dependences between reads and
484 * _any_ later potential write.
486 * We also need to be careful about writes without a corresponding read.
487 * They are already prevented from moving past non-local preceding
488 * intervals, but we also need to prevent them from moving past non-local
489 * following intervals. We therefore also add order dependences from
490 * potential writes that do not appear in any intervals
491 * to all later potential writes.
492 * Note that dead code elimination should have removed most of these
493 * dead writes, but the dead code elimination may not remove all dead writes,
494 * so we need to consider them to be safe.
496 * The order dependences are computed by computing the "dataflow"
497 * from the above unmatched writes and the reads to the may writes.
498 * The unmatched writes and the reads are treated as may sources
499 * such that they would not kill order dependences from earlier
500 * such writes and reads.
501 */
502 static void compute_order_dependences(struct ppcg_scop *ps)
504 isl_union_map *reads;
505 isl_union_map *shared_access;
506 isl_union_set *matched;
507 isl_union_map *unmatched;
508 isl_union_pw_multi_aff *tagger;
509 isl_schedule *schedule;
510 isl_union_access_info *access;
511 isl_union_flow *flow;
513 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
514 schedule = isl_schedule_copy(ps->schedule);
515 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
516 reads = isl_union_map_copy(ps->tagged_reads);
517 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
518 unmatched = isl_union_map_copy(ps->tagged_may_writes);
519 unmatched = isl_union_map_subtract_domain(unmatched, matched);
520 reads = isl_union_map_union(reads, unmatched);
521 access = isl_union_access_info_from_sink(
522 isl_union_map_copy(ps->tagged_may_writes));
523 access = isl_union_access_info_set_may_source(access, reads);
524 access = isl_union_access_info_set_schedule(access, schedule);
525 flow = isl_union_access_info_compute_flow(access);
526 shared_access = isl_union_flow_get_may_dependence(flow);
527 isl_union_flow_free(flow);
529 ps->tagged_dep_order = isl_union_map_copy(shared_access);
530 ps->dep_order = isl_union_map_factor_domain(shared_access);
533 /* Compute those validity dependences of the program represented by "scop"
534 * that should be unconditionally enforced even when live-range reordering
535 * is used.
537 * In particular, compute the external false dependences
538 * as well as order dependences between sources with the same sink.
539 * The anti-dependences are already taken care of by the order dependences.
540 * The external false dependences are only used to ensure that live-in and
541 * live-out data is not overwritten by any writes inside the scop.
542 * The independences are removed from the external false dependences,
543 * but not from the order dependences between sources with the same sink.
545 * In particular, the reads from live-in data need to precede any
546 * later write to the same memory element.
547 * As to live-out data, the last writes need to remain the last writes.
548 * That is, any earlier write in the original schedule needs to precede
549 * the last write to the same memory element in the computed schedule.
550 * The possible last writes have been computed by compute_live_out.
551 * They may include kills, but if the last access is a kill,
552 * then the corresponding dependences will effectively be ignored
553 * since we do not schedule any kill statements.
555 * Note that the set of live-in and live-out accesses may be
556 * an overapproximation. There may therefore be potential writes
557 * before a live-in access and after a live-out access.
559 * In the presence of may-writes, there may be multiple live-ranges
560 * with the same sink, accessing the same memory element.
561 * The sources of these live-ranges need to be executed
562 * in the same relative order as in the original program
563 * since we do not know which of the may-writes will actually
564 * perform a write. Consider all sources that share a sink and
565 * that may write to the same memory element and compute
566 * the order dependences among them.
567 */
568 static void compute_forced_dependences(struct ppcg_scop *ps)
570 isl_union_map *shared_access;
571 isl_union_map *exposed;
572 isl_union_map *live_in;
573 isl_union_map *sink_access;
574 isl_union_map *shared_sink;
575 isl_union_access_info *access;
576 isl_union_flow *flow;
577 isl_schedule *schedule;
579 exposed = isl_union_map_copy(ps->live_out);
580 schedule = isl_schedule_copy(ps->schedule);
581 access = isl_union_access_info_from_sink(exposed);
582 access = isl_union_access_info_set_may_source(access,
583 isl_union_map_copy(ps->may_writes));
584 access = isl_union_access_info_set_schedule(access, schedule);
585 flow = isl_union_access_info_compute_flow(access);
586 shared_access = isl_union_flow_get_may_dependence(flow);
587 isl_union_flow_free(flow);
588 ps->dep_forced = shared_access;
590 schedule = isl_schedule_copy(ps->schedule);
591 access = isl_union_access_info_from_sink(
592 isl_union_map_copy(ps->may_writes));
593 access = isl_union_access_info_set_may_source(access,
594 isl_union_map_copy(ps->live_in));
595 access = isl_union_access_info_set_schedule(access, schedule);
596 flow = isl_union_access_info_compute_flow(access);
597 live_in = isl_union_flow_get_may_dependence(flow);
598 isl_union_flow_free(flow);
600 ps->dep_forced = isl_union_map_union(ps->dep_forced, live_in);
601 ps->dep_forced = isl_union_map_subtract(ps->dep_forced,
602 isl_union_map_copy(ps->independence));
604 schedule = isl_schedule_copy(ps->schedule);
605 sink_access = isl_union_map_copy(ps->tagged_dep_flow);
606 sink_access = isl_union_map_range_product(sink_access,
607 isl_union_map_copy(ps->tagged_may_writes));
608 sink_access = isl_union_map_domain_factor_domain(sink_access);
609 access = isl_union_access_info_from_sink(
610 isl_union_map_copy(sink_access));
611 access = isl_union_access_info_set_may_source(access, sink_access);
612 access = isl_union_access_info_set_schedule(access, schedule);
613 flow = isl_union_access_info_compute_flow(access);
614 shared_sink = isl_union_flow_get_may_dependence(flow);
615 isl_union_flow_free(flow);
616 ps->dep_forced = isl_union_map_union(ps->dep_forced, shared_sink);
619 /* Remove independence from the tagged flow dependences.
620 * Since the user has guaranteed that source and sink of an independence
621 * can be executed in any order, there cannot be a flow dependence
622 * between them, so they can be removed from the set of flow dependences.
623 * However, if the source of such a flow dependence is a must write,
624 * then it may have killed other potential sources, which would have
625 * to be recovered if we were to remove those flow dependences.
626 * We therefore keep the flow dependences that originate in a must write,
627 * even if it corresponds to a known independence.
628 */
629 static void remove_independences_from_tagged_flow(struct ppcg_scop *ps)
631 isl_union_map *tf;
632 isl_union_set *indep;
633 isl_union_set *mw;
635 tf = isl_union_map_copy(ps->tagged_dep_flow);
636 tf = isl_union_map_zip(tf);
637 indep = isl_union_map_wrap(isl_union_map_copy(ps->independence));
638 tf = isl_union_map_intersect_domain(tf, indep);
639 tf = isl_union_map_zip(tf);
640 mw = isl_union_map_domain(isl_union_map_copy(ps->tagged_must_writes));
641 tf = isl_union_map_subtract_domain(tf, mw);
642 ps->tagged_dep_flow = isl_union_map_subtract(ps->tagged_dep_flow, tf);
645 /* Compute the dependences of the program represented by "scop"
646 * in case live range reordering is allowed.
648 * We compute the actual live ranges and the corresponding order
649 * false dependences.
651 * The independences are removed from the flow dependences
652 * (provided the source is not a must-write) as well as
653 * from the external false dependences (by compute_forced_dependences).
654 */
655 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
657 compute_tagged_flow_dep_only(ps);
658 remove_independences_from_tagged_flow(ps);
659 derive_flow_dep_from_tagged_flow_dep(ps);
660 compute_order_dependences(ps);
661 compute_forced_dependences(ps);
664 /* Compute the potential flow dependences and the potential live in
665 * accesses.
666 */
667 static void compute_flow_dep(struct ppcg_scop *ps)
669 isl_union_access_info *access;
670 isl_union_flow *flow;
672 access = isl_union_access_info_from_sink(isl_union_map_copy(ps->reads));
673 access = isl_union_access_info_set_must_source(access,
674 isl_union_map_copy(ps->must_writes));
675 access = isl_union_access_info_set_may_source(access,
676 isl_union_map_copy(ps->may_writes));
677 access = isl_union_access_info_set_schedule(access,
678 isl_schedule_copy(ps->schedule));
679 flow = isl_union_access_info_compute_flow(access);
681 ps->dep_flow = isl_union_flow_get_may_dependence(flow);
682 ps->live_in = isl_union_flow_get_may_no_source(flow);
683 isl_union_flow_free(flow);
686 /* Compute the dependences of the program represented by "scop".
687 * Store the computed potential flow dependences
688 * in scop->dep_flow and the reads with potentially no corresponding writes in
689 * scop->live_in.
690 * Store the potential live out accesses in scop->live_out.
691 * Store the potential false (anti and output) dependences in scop->dep_false.
693 * If live range reordering is allowed, then we compute a separate
694 * set of order dependences and a set of external false dependences
695 * in compute_live_range_reordering_dependences.
696 */
697 static void compute_dependences(struct ppcg_scop *scop)
699 isl_union_map *may_source;
700 isl_union_access_info *access;
701 isl_union_flow *flow;
703 if (!scop)
704 return;
706 compute_live_out(scop);
708 if (scop->options->live_range_reordering)
709 compute_live_range_reordering_dependences(scop);
710 else if (scop->options->target != PPCG_TARGET_C)
711 compute_tagged_flow_dep(scop);
712 else
713 compute_flow_dep(scop);
715 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
716 isl_union_map_copy(scop->reads));
717 access = isl_union_access_info_from_sink(
718 isl_union_map_copy(scop->may_writes));
719 access = isl_union_access_info_set_must_source(access,
720 isl_union_map_copy(scop->must_writes));
721 access = isl_union_access_info_set_may_source(access, may_source);
722 access = isl_union_access_info_set_schedule(access,
723 isl_schedule_copy(scop->schedule));
724 flow = isl_union_access_info_compute_flow(access);
726 scop->dep_false = isl_union_flow_get_may_dependence(flow);
727 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
728 isl_union_flow_free(flow);
731 /* Eliminate dead code from ps->domain.
733 * In particular, intersect both ps->domain and the domain of
734 * ps->schedule with the (parts of) iteration
735 * domains that are needed to produce the output or for statement
736 * iterations that call functions.
737 * Also intersect the range of the dataflow dependences with
738 * this domain such that the removed instances will no longer
739 * be considered as targets of dataflow.
741 * We start with the iteration domains that call functions
742 * and the set of iterations that last write to an array
743 * (except those that are later killed).
745 * Then we add those statement iterations that produce
746 * something needed by the "live" statements iterations.
747 * We keep doing this until no more statement iterations can be added.
748 * To ensure that the procedure terminates, we compute the affine
749 * hull of the live iterations (bounded to the original iteration
750 * domains) each time we have added extra iterations.
751 */
752 static void eliminate_dead_code(struct ppcg_scop *ps)
754 isl_union_set *live;
755 isl_union_map *dep;
756 isl_union_pw_multi_aff *tagger;
758 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
759 if (!isl_union_set_is_empty(ps->call)) {
760 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
761 live = isl_union_set_coalesce(live);
764 dep = isl_union_map_copy(ps->dep_flow);
765 dep = isl_union_map_reverse(dep);
767 for (;;) {
768 isl_union_set *extra;
770 extra = isl_union_set_apply(isl_union_set_copy(live),
771 isl_union_map_copy(dep));
772 if (isl_union_set_is_subset(extra, live)) {
773 isl_union_set_free(extra);
774 break;
777 live = isl_union_set_union(live, extra);
778 live = isl_union_set_affine_hull(live);
779 live = isl_union_set_intersect(live,
780 isl_union_set_copy(ps->domain));
783 isl_union_map_free(dep);
785 ps->domain = isl_union_set_intersect(ps->domain,
786 isl_union_set_copy(live));
787 ps->schedule = isl_schedule_intersect_domain(ps->schedule,
788 isl_union_set_copy(live));
789 ps->dep_flow = isl_union_map_intersect_range(ps->dep_flow,
790 isl_union_set_copy(live));
791 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
792 live = isl_union_set_preimage_union_pw_multi_aff(live, tagger);
793 ps->tagged_dep_flow = isl_union_map_intersect_range(ps->tagged_dep_flow,
794 live);
797 /* Intersect "set" with the set described by "str", taking the NULL
798 * string to represent the universal set.
799 */
800 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
801 const char *str)
803 isl_ctx *ctx;
804 isl_set *set2;
806 if (!str)
807 return set;
809 ctx = isl_set_get_ctx(set);
810 set2 = isl_set_read_from_str(ctx, str);
811 set = isl_set_intersect(set, set2);
813 return set;
816 static void *ppcg_scop_free(struct ppcg_scop *ps)
818 if (!ps)
819 return NULL;
821 isl_set_free(ps->context);
822 isl_union_set_free(ps->domain);
823 isl_union_set_free(ps->call);
824 isl_union_map_free(ps->tagged_reads);
825 isl_union_map_free(ps->reads);
826 isl_union_map_free(ps->live_in);
827 isl_union_map_free(ps->tagged_may_writes);
828 isl_union_map_free(ps->tagged_must_writes);
829 isl_union_map_free(ps->may_writes);
830 isl_union_map_free(ps->must_writes);
831 isl_union_map_free(ps->live_out);
832 isl_union_map_free(ps->tagged_must_kills);
833 isl_union_map_free(ps->tagged_dep_flow);
834 isl_union_map_free(ps->dep_flow);
835 isl_union_map_free(ps->dep_false);
836 isl_union_map_free(ps->dep_forced);
837 isl_union_map_free(ps->tagged_dep_order);
838 isl_union_map_free(ps->dep_order);
839 isl_schedule_free(ps->schedule);
840 isl_union_pw_multi_aff_free(ps->tagger);
841 isl_union_map_free(ps->independence);
842 isl_id_to_ast_expr_free(ps->names);
844 free(ps);
846 return NULL;
849 /* Extract a ppcg_scop from a pet_scop.
851 * The constructed ppcg_scop refers to elements from the pet_scop
852 * so the pet_scop should not be freed before the ppcg_scop.
853 */
854 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
855 struct ppcg_options *options)
857 int i;
858 isl_ctx *ctx;
859 struct ppcg_scop *ps;
861 if (!scop)
862 return NULL;
864 ctx = isl_set_get_ctx(scop->context);
866 ps = isl_calloc_type(ctx, struct ppcg_scop);
867 if (!ps)
868 return NULL;
870 ps->names = collect_names(scop);
871 ps->options = options;
872 ps->start = pet_loc_get_start(scop->loc);
873 ps->end = pet_loc_get_end(scop->loc);
874 ps->context = isl_set_copy(scop->context);
875 ps->context = set_intersect_str(ps->context, options->ctx);
876 if (options->non_negative_parameters) {
877 isl_space *space = isl_set_get_space(ps->context);
878 isl_set *nn = isl_set_nat_universe(space);
879 ps->context = isl_set_intersect(ps->context, nn);
881 ps->domain = collect_non_kill_domains(scop);
882 ps->call = collect_call_domains(scop);
883 ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
884 ps->reads = pet_scop_collect_may_reads(scop);
885 ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
886 ps->may_writes = pet_scop_collect_may_writes(scop);
887 ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
888 ps->must_writes = pet_scop_collect_must_writes(scop);
889 ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
890 ps->schedule = isl_schedule_copy(scop->schedule);
891 ps->pet = scop;
892 ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
893 for (i = 0; i < scop->n_independence; ++i)
894 ps->independence = isl_union_map_union(ps->independence,
895 isl_union_map_copy(scop->independences[i]->filter));
897 compute_tagger(ps);
898 compute_dependences(ps);
899 eliminate_dead_code(ps);
901 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
902 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
903 !ps->schedule || !ps->independence || !ps->names)
904 return ppcg_scop_free(ps);
906 return ps;
909 /* Internal data structure for ppcg_transform.
910 */
911 struct ppcg_transform_data {
912 struct ppcg_options *options;
913 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
914 struct ppcg_scop *scop, void *user);
915 void *user;
916 };
918 /* Should we print the original code?
919 * That is, does "scop" involve any data dependent conditions or
920 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
921 */
922 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
924 if (!pet_scop_can_build_ast_exprs(scop)) {
925 if (options->debug->verbose)
926 fprintf(stdout, "Printing original code because "
927 "some index expressions cannot currently "
928 "be printed\n");
929 return 1;
932 if (pet_scop_has_data_dependent_conditions(scop)) {
933 if (options->debug->verbose)
934 fprintf(stdout, "Printing original code because "
935 "input involves data dependent conditions\n");
936 return 1;
939 return 0;
942 /* Callback for pet_transform_C_source that transforms
943 * the given pet_scop to a ppcg_scop before calling the
944 * ppcg_transform callback.
946 * If "scop" contains any data dependent conditions or if we may
947 * not be able to print the transformed program, then just print
948 * the original code.
949 */
950 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
951 struct pet_scop *scop, void *user)
953 struct ppcg_transform_data *data = user;
954 struct ppcg_scop *ps;
956 if (print_original(scop, data->options)) {
957 p = pet_scop_print_original(scop, p);
958 pet_scop_free(scop);
959 return p;
962 scop = pet_scop_align_params(scop);
963 ps = ppcg_scop_from_pet_scop(scop, data->options);
965 p = data->transform(p, ps, data->user);
967 ppcg_scop_free(ps);
968 pet_scop_free(scop);
970 return p;
973 /* Transform the C source file "input" by rewriting each scop
974 * through a call to "transform".
975 * The transformed C code is written to "out".
977 * This is a wrapper around pet_transform_C_source that transforms
978 * the pet_scop to a ppcg_scop before calling "fn".
979 */
980 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
981 struct ppcg_options *options,
982 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
983 struct ppcg_scop *scop, void *user), void *user)
985 struct ppcg_transform_data data = { options, fn, user };
986 return pet_transform_C_source(ctx, input, out, &transform, &data);
989 /* Check consistency of options.
991 * Return -1 on error.
992 */
993 static int check_options(isl_ctx *ctx)
995 struct options *options;
997 options = isl_ctx_peek_options(ctx, &options_args);
998 if (!options)
999 isl_die(ctx, isl_error_internal,
1000 "unable to find options", return -1);
1002 if (options->ppcg->openmp &&
1003 !isl_options_get_ast_build_atomic_upper_bound(ctx))
1004 isl_die(ctx, isl_error_invalid,
1005 "OpenMP requires atomic bounds", return -1);
1007 return 0;
1010 int main(int argc, char **argv)
1012 int r;
1013 isl_ctx *ctx;
1014 struct options *options;
1016 options = options_new_with_defaults();
1017 assert(options);
1019 ctx = isl_ctx_alloc_with_options(&options_args, options);
1020 isl_options_set_schedule_outer_coincidence(ctx, 1);
1021 isl_options_set_schedule_maximize_band_depth(ctx, 1);
1022 pet_options_set_encapsulate_dynamic_control(ctx, 1);
1023 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
1025 if (check_options(ctx) < 0)
1026 r = EXIT_FAILURE;
1027 else if (options->ppcg->target == PPCG_TARGET_CUDA)
1028 r = generate_cuda(ctx, options->ppcg, options->input);
1029 else if (options->ppcg->target == PPCG_TARGET_OPENCL)
1030 r = generate_opencl(ctx, options->ppcg, options->input,
1031 options->output);
1032 else
1033 r = generate_cpu(ctx, options->ppcg, options->input,
1034 options->output);
1036 isl_ctx_free(ctx);
1038 return r;