PPCG 0.09.2
[ppcg.git] / ppcg.c
blobd4ca15e11c2300f278e89a0b3d75dca014e93128
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[23];
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 * Both must-writes and must-kills are allowed to kill dependences
415 * from earlier writes to subsequent reads.
416 * The must-kills are not included in the potential sources, though.
417 * The flow dependences with a must-kill as source would
418 * reflect possibly uninitialized reads.
419 * No dependences need to be introduced to protect such reads
420 * (other than those imposed by potential flows from may writes
421 * that follow the kill). Those flow dependences are therefore not needed.
422 * The dead code elimination also assumes
423 * the flow sources are non-kill instances.
425 static void compute_tagged_flow_dep_only(struct ppcg_scop *ps)
427 isl_union_pw_multi_aff *tagger;
428 isl_schedule *schedule;
429 isl_union_map *live_in;
430 isl_union_access_info *access;
431 isl_union_flow *flow;
432 isl_union_map *must_source;
433 isl_union_map *kills;
434 isl_union_map *tagged_flow;
436 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
437 schedule = isl_schedule_copy(ps->schedule);
438 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
439 kills = isl_union_map_copy(ps->tagged_must_kills);
440 must_source = isl_union_map_copy(ps->tagged_must_writes);
441 kills = isl_union_map_union(kills, must_source);
442 access = isl_union_access_info_from_sink(
443 isl_union_map_copy(ps->tagged_reads));
444 access = isl_union_access_info_set_kill(access, kills);
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 ps->tagged_dep_flow = tagged_flow;
451 live_in = isl_union_flow_get_may_no_source(flow);
452 ps->live_in = project_out_tags(live_in);
453 isl_union_flow_free(flow);
456 /* Compute ps->dep_flow from ps->tagged_dep_flow
457 * by projecting out the reference tags.
459 static void derive_flow_dep_from_tagged_flow_dep(struct ppcg_scop *ps)
461 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
462 ps->dep_flow = isl_union_map_factor_domain(ps->dep_flow);
465 /* Compute the flow dependences and the live_in accesses and store
466 * the results in ps->dep_flow and ps->live_in.
467 * A copy of the flow dependences, tagged with the reference tags
468 * is stored in ps->tagged_dep_flow.
470 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
471 * and then project out the tags.
473 static void compute_tagged_flow_dep(struct ppcg_scop *ps)
475 compute_tagged_flow_dep_only(ps);
476 derive_flow_dep_from_tagged_flow_dep(ps);
479 /* Compute the order dependences that prevent the potential live ranges
480 * from overlapping.
482 * In particular, construct a union of relations
484 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
486 * where [R[...] -> R_1[]] is the range of one or more live ranges
487 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
488 * live ranges (i.e., a write). Moreover, the read and the write
489 * access the same memory element and the read occurs before the write
490 * in the original schedule.
491 * The scheduler allows some of these dependences to be violated, provided
492 * the adjacent live ranges are all local (i.e., their domain and range
493 * are mapped to the same point by the current schedule band).
495 * Note that if a live range is not local, then we need to make
496 * sure it does not overlap with _any_ other live range, and not
497 * just with the "previous" and/or the "next" live range.
498 * We therefore add order dependences between reads and
499 * _any_ later potential write.
501 * We also need to be careful about writes without a corresponding read.
502 * They are already prevented from moving past non-local preceding
503 * intervals, but we also need to prevent them from moving past non-local
504 * following intervals. We therefore also add order dependences from
505 * potential writes that do not appear in any intervals
506 * to all later potential writes.
507 * Note that dead code elimination should have removed most of these
508 * dead writes, but the dead code elimination may not remove all dead writes,
509 * so we need to consider them to be safe.
511 * The order dependences are computed by computing the "dataflow"
512 * from the above unmatched writes and the reads to the may writes.
513 * The unmatched writes and the reads are treated as may sources
514 * such that they would not kill order dependences from earlier
515 * such writes and reads.
517 static void compute_order_dependences(struct ppcg_scop *ps)
519 isl_union_map *reads;
520 isl_union_map *shared_access;
521 isl_union_set *matched;
522 isl_union_map *unmatched;
523 isl_union_pw_multi_aff *tagger;
524 isl_schedule *schedule;
525 isl_union_access_info *access;
526 isl_union_flow *flow;
528 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
529 schedule = isl_schedule_copy(ps->schedule);
530 schedule = isl_schedule_pullback_union_pw_multi_aff(schedule, tagger);
531 reads = isl_union_map_copy(ps->tagged_reads);
532 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
533 unmatched = isl_union_map_copy(ps->tagged_may_writes);
534 unmatched = isl_union_map_subtract_domain(unmatched, matched);
535 reads = isl_union_map_union(reads, unmatched);
536 access = isl_union_access_info_from_sink(
537 isl_union_map_copy(ps->tagged_may_writes));
538 access = isl_union_access_info_set_may_source(access, reads);
539 access = isl_union_access_info_set_schedule(access, schedule);
540 flow = isl_union_access_info_compute_flow(access);
541 shared_access = isl_union_flow_get_may_dependence(flow);
542 isl_union_flow_free(flow);
544 ps->tagged_dep_order = isl_union_map_copy(shared_access);
545 ps->dep_order = isl_union_map_factor_domain(shared_access);
548 /* Compute those validity dependences of the program represented by "scop"
549 * that should be unconditionally enforced even when live-range reordering
550 * is used.
552 * In particular, compute the external false dependences
553 * as well as order dependences between sources with the same sink.
554 * The anti-dependences are already taken care of by the order dependences.
555 * The external false dependences are only used to ensure that live-in and
556 * live-out data is not overwritten by any writes inside the scop.
557 * The independences are removed from the external false dependences,
558 * but not from the order dependences between sources with the same sink.
560 * In particular, the reads from live-in data need to precede any
561 * later write to the same memory element.
562 * As to live-out data, the last writes need to remain the last writes.
563 * That is, any earlier write in the original schedule needs to precede
564 * the last write to the same memory element in the computed schedule.
565 * The possible last writes have been computed by compute_live_out.
566 * They may include kills, but if the last access is a kill,
567 * then the corresponding dependences will effectively be ignored
568 * since we do not schedule any kill statements.
570 * Note that the set of live-in and live-out accesses may be
571 * an overapproximation. There may therefore be potential writes
572 * before a live-in access and after a live-out access.
574 * In the presence of may-writes, there may be multiple live-ranges
575 * with the same sink, accessing the same memory element.
576 * The sources of these live-ranges need to be executed
577 * in the same relative order as in the original program
578 * since we do not know which of the may-writes will actually
579 * perform a write. Consider all sources that share a sink and
580 * that may write to the same memory element and compute
581 * the order dependences among them.
583 static void compute_forced_dependences(struct ppcg_scop *ps)
585 isl_union_map *shared_access;
586 isl_union_map *exposed;
587 isl_union_map *live_in;
588 isl_union_map *sink_access;
589 isl_union_map *shared_sink;
590 isl_union_access_info *access;
591 isl_union_flow *flow;
592 isl_schedule *schedule;
594 exposed = isl_union_map_copy(ps->live_out);
595 schedule = isl_schedule_copy(ps->schedule);
596 access = isl_union_access_info_from_sink(exposed);
597 access = isl_union_access_info_set_may_source(access,
598 isl_union_map_copy(ps->may_writes));
599 access = isl_union_access_info_set_schedule(access, schedule);
600 flow = isl_union_access_info_compute_flow(access);
601 shared_access = isl_union_flow_get_may_dependence(flow);
602 isl_union_flow_free(flow);
603 ps->dep_forced = shared_access;
605 schedule = isl_schedule_copy(ps->schedule);
606 access = isl_union_access_info_from_sink(
607 isl_union_map_copy(ps->may_writes));
608 access = isl_union_access_info_set_may_source(access,
609 isl_union_map_copy(ps->live_in));
610 access = isl_union_access_info_set_schedule(access, schedule);
611 flow = isl_union_access_info_compute_flow(access);
612 live_in = isl_union_flow_get_may_dependence(flow);
613 isl_union_flow_free(flow);
615 ps->dep_forced = isl_union_map_union(ps->dep_forced, live_in);
616 ps->dep_forced = isl_union_map_subtract(ps->dep_forced,
617 isl_union_map_copy(ps->independence));
619 schedule = isl_schedule_copy(ps->schedule);
620 sink_access = isl_union_map_copy(ps->tagged_dep_flow);
621 sink_access = isl_union_map_range_product(sink_access,
622 isl_union_map_copy(ps->tagged_may_writes));
623 sink_access = isl_union_map_domain_factor_domain(sink_access);
624 access = isl_union_access_info_from_sink(
625 isl_union_map_copy(sink_access));
626 access = isl_union_access_info_set_may_source(access, sink_access);
627 access = isl_union_access_info_set_schedule(access, schedule);
628 flow = isl_union_access_info_compute_flow(access);
629 shared_sink = isl_union_flow_get_may_dependence(flow);
630 isl_union_flow_free(flow);
631 ps->dep_forced = isl_union_map_union(ps->dep_forced, shared_sink);
634 /* Remove independence from the tagged flow dependences.
635 * Since the user has guaranteed that source and sink of an independence
636 * can be executed in any order, there cannot be a flow dependence
637 * between them, so they can be removed from the set of flow dependences.
638 * However, if the source of such a flow dependence is a must write,
639 * then it may have killed other potential sources, which would have
640 * to be recovered if we were to remove those flow dependences.
641 * We therefore keep the flow dependences that originate in a must write,
642 * even if it corresponds to a known independence.
644 static void remove_independences_from_tagged_flow(struct ppcg_scop *ps)
646 isl_union_map *tf;
647 isl_union_set *indep;
648 isl_union_set *mw;
650 tf = isl_union_map_copy(ps->tagged_dep_flow);
651 tf = isl_union_map_zip(tf);
652 indep = isl_union_map_wrap(isl_union_map_copy(ps->independence));
653 tf = isl_union_map_intersect_domain(tf, indep);
654 tf = isl_union_map_zip(tf);
655 mw = isl_union_map_domain(isl_union_map_copy(ps->tagged_must_writes));
656 tf = isl_union_map_subtract_domain(tf, mw);
657 ps->tagged_dep_flow = isl_union_map_subtract(ps->tagged_dep_flow, tf);
660 /* Compute the dependences of the program represented by "scop"
661 * in case live range reordering is allowed.
663 * We compute the actual live ranges and the corresponding order
664 * false dependences.
666 * The independences are removed from the flow dependences
667 * (provided the source is not a must-write) as well as
668 * from the external false dependences (by compute_forced_dependences).
670 static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
672 compute_tagged_flow_dep_only(ps);
673 remove_independences_from_tagged_flow(ps);
674 derive_flow_dep_from_tagged_flow_dep(ps);
675 compute_order_dependences(ps);
676 compute_forced_dependences(ps);
679 /* Compute the potential flow dependences and the potential live in
680 * accesses.
682 * Both must-writes and must-kills are allowed to kill dependences
683 * from earlier writes to subsequent reads, as in compute_tagged_flow_dep_only.
685 static void compute_flow_dep(struct ppcg_scop *ps)
687 isl_union_access_info *access;
688 isl_union_flow *flow;
689 isl_union_map *kills, *must_writes;
691 access = isl_union_access_info_from_sink(isl_union_map_copy(ps->reads));
692 kills = isl_union_map_copy(ps->must_kills);
693 must_writes = isl_union_map_copy(ps->must_writes);
694 kills = isl_union_map_union(kills, must_writes);
695 access = isl_union_access_info_set_kill(access, kills);
696 access = isl_union_access_info_set_may_source(access,
697 isl_union_map_copy(ps->may_writes));
698 access = isl_union_access_info_set_schedule(access,
699 isl_schedule_copy(ps->schedule));
700 flow = isl_union_access_info_compute_flow(access);
702 ps->dep_flow = isl_union_flow_get_may_dependence(flow);
703 ps->live_in = isl_union_flow_get_may_no_source(flow);
704 isl_union_flow_free(flow);
707 /* Compute the dependences of the program represented by "scop".
708 * Store the computed potential flow dependences
709 * in scop->dep_flow and the reads with potentially no corresponding writes in
710 * scop->live_in.
711 * Store the potential live out accesses in scop->live_out.
712 * Store the potential false (anti and output) dependences in scop->dep_false.
714 * If live range reordering is allowed, then we compute a separate
715 * set of order dependences and a set of external false dependences
716 * in compute_live_range_reordering_dependences.
718 static void compute_dependences(struct ppcg_scop *scop)
720 isl_union_map *may_source;
721 isl_union_access_info *access;
722 isl_union_flow *flow;
724 if (!scop)
725 return;
727 compute_live_out(scop);
729 if (scop->options->live_range_reordering)
730 compute_live_range_reordering_dependences(scop);
731 else if (scop->options->target != PPCG_TARGET_C)
732 compute_tagged_flow_dep(scop);
733 else
734 compute_flow_dep(scop);
736 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
737 isl_union_map_copy(scop->reads));
738 access = isl_union_access_info_from_sink(
739 isl_union_map_copy(scop->may_writes));
740 access = isl_union_access_info_set_kill(access,
741 isl_union_map_copy(scop->must_writes));
742 access = isl_union_access_info_set_may_source(access, may_source);
743 access = isl_union_access_info_set_schedule(access,
744 isl_schedule_copy(scop->schedule));
745 flow = isl_union_access_info_compute_flow(access);
747 scop->dep_false = isl_union_flow_get_may_dependence(flow);
748 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
749 isl_union_flow_free(flow);
752 /* Report an empty context, meaning that the original code
753 * cannot not be executed.
755 * Make a distinction between whether the original context
756 * was already empty or whether the current context
757 * (with additional constraints specified by the user) is empty.
759 static void report_empty_context(struct ppcg_scop *ps)
761 isl_bool empty;
763 if (!ps->options->debug->verbose)
764 return;
765 empty = isl_set_is_empty(ps->pet->context);
766 if (empty < 0)
767 return;
768 if (empty) {
769 fprintf(stdout, "Original code cannot be executed "
770 "under any conditions\n");
771 return;
773 empty = isl_set_is_empty(ps->context);
774 if (empty < 0)
775 return;
776 if (!empty)
777 return;
778 fprintf(stdout, "Original code cannot be executed "
779 "under specified conditions\n");
782 /* Report the eliminated dead code,
783 * if there is any and if the verbose option is set.
785 static void report_dead_code(struct ppcg_scop *ps,
786 __isl_keep isl_union_set *live)
788 isl_ctx *ctx;
789 isl_printer *p;
790 isl_union_set *dead;
792 if (!ps->options->debug->verbose)
793 return;
794 if (isl_union_set_is_equal(ps->domain, live))
795 return;
797 ctx = isl_union_set_get_ctx(live);
798 dead = isl_union_set_subtract(isl_union_set_copy(ps->domain),
799 isl_union_set_copy(live));
801 p = isl_printer_to_file(ctx, stdout);
802 p = isl_printer_print_str(p, "Eliminated dead instances: ");
803 p = isl_printer_print_union_set(p, dead);
804 p = isl_printer_end_line(p);
805 isl_printer_free(p);
807 isl_union_set_free(dead);
810 /* Eliminate dead code from ps->domain.
812 * In particular, intersect both ps->domain and the domain of
813 * ps->schedule with the (parts of) iteration
814 * domains that are needed to produce the output or for statement
815 * iterations that call functions.
816 * Also intersect the range of the dataflow dependences with
817 * this domain such that the removed instances will no longer
818 * be considered as targets of dataflow.
820 * We start with the iteration domains that call functions
821 * and the set of iterations that last write to an array
822 * (except those that are later killed).
824 * Then we add those statement iterations that produce
825 * something needed by the "live" statements iterations.
826 * We keep doing this until no more statement iterations can be added.
827 * To ensure that the procedure terminates, we compute the affine
828 * hull of the live iterations (bounded to the original iteration
829 * domains) each time we have added extra iterations.
831 static void eliminate_dead_code(struct ppcg_scop *ps)
833 isl_union_set *live;
834 isl_union_map *dep;
835 isl_union_pw_multi_aff *tagger;
837 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
838 if (!isl_union_set_is_empty(ps->call)) {
839 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
840 live = isl_union_set_coalesce(live);
843 dep = isl_union_map_copy(ps->dep_flow);
844 dep = isl_union_map_reverse(dep);
846 for (;;) {
847 isl_union_set *extra;
849 extra = isl_union_set_apply(isl_union_set_copy(live),
850 isl_union_map_copy(dep));
851 if (isl_union_set_is_subset(extra, live)) {
852 isl_union_set_free(extra);
853 break;
856 live = isl_union_set_union(live, extra);
857 live = isl_union_set_affine_hull(live);
858 live = isl_union_set_intersect(live,
859 isl_union_set_copy(ps->domain));
862 isl_union_map_free(dep);
864 report_dead_code(ps, live);
866 ps->domain = isl_union_set_intersect(ps->domain,
867 isl_union_set_copy(live));
868 ps->schedule = isl_schedule_intersect_domain(ps->schedule,
869 isl_union_set_copy(live));
870 ps->dep_flow = isl_union_map_intersect_range(ps->dep_flow,
871 isl_union_set_copy(live));
872 tagger = isl_union_pw_multi_aff_copy(ps->tagger);
873 live = isl_union_set_preimage_union_pw_multi_aff(live, tagger);
874 ps->tagged_dep_flow = isl_union_map_intersect_range(ps->tagged_dep_flow,
875 live);
878 /* Intersect "set" with the set described by "str", taking the NULL
879 * string to represent the universal set.
881 static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
882 const char *str)
884 isl_ctx *ctx;
885 isl_set *set2;
887 if (!str)
888 return set;
890 ctx = isl_set_get_ctx(set);
891 set2 = isl_set_read_from_str(ctx, str);
892 set = isl_set_intersect(set, set2);
894 return set;
897 static void *ppcg_scop_free(struct ppcg_scop *ps)
899 if (!ps)
900 return NULL;
902 isl_set_free(ps->context);
903 isl_union_set_free(ps->domain);
904 isl_union_set_free(ps->call);
905 isl_union_map_free(ps->tagged_reads);
906 isl_union_map_free(ps->reads);
907 isl_union_map_free(ps->live_in);
908 isl_union_map_free(ps->tagged_may_writes);
909 isl_union_map_free(ps->tagged_must_writes);
910 isl_union_map_free(ps->may_writes);
911 isl_union_map_free(ps->must_writes);
912 isl_union_map_free(ps->live_out);
913 isl_union_map_free(ps->tagged_must_kills);
914 isl_union_map_free(ps->must_kills);
915 isl_union_map_free(ps->tagged_dep_flow);
916 isl_union_map_free(ps->dep_flow);
917 isl_union_map_free(ps->dep_false);
918 isl_union_map_free(ps->dep_forced);
919 isl_union_map_free(ps->tagged_dep_order);
920 isl_union_map_free(ps->dep_order);
921 isl_schedule_free(ps->schedule);
922 isl_union_pw_multi_aff_free(ps->tagger);
923 isl_union_map_free(ps->independence);
924 isl_id_to_ast_expr_free(ps->names);
926 free(ps);
928 return NULL;
931 /* Extract a ppcg_scop from a pet_scop.
933 * The constructed ppcg_scop refers to elements from the pet_scop
934 * so the pet_scop should not be freed before the ppcg_scop.
936 static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
937 struct ppcg_options *options)
939 int i;
940 isl_ctx *ctx;
941 struct ppcg_scop *ps;
943 if (!scop)
944 return NULL;
946 ctx = isl_set_get_ctx(scop->context);
948 ps = isl_calloc_type(ctx, struct ppcg_scop);
949 if (!ps)
950 return NULL;
952 ps->names = collect_names(scop);
953 ps->options = options;
954 ps->start = pet_loc_get_start(scop->loc);
955 ps->end = pet_loc_get_end(scop->loc);
956 ps->context = isl_set_copy(scop->context);
957 ps->context = set_intersect_str(ps->context, options->ctx);
958 if (options->non_negative_parameters) {
959 isl_space *space = isl_set_get_space(ps->context);
960 isl_set *nn = isl_set_nat_universe(space);
961 ps->context = isl_set_intersect(ps->context, nn);
963 ps->domain = collect_non_kill_domains(scop);
964 ps->call = collect_call_domains(scop);
965 ps->tagged_reads = pet_scop_get_tagged_may_reads(scop);
966 ps->reads = pet_scop_get_may_reads(scop);
967 ps->tagged_may_writes = pet_scop_get_tagged_may_writes(scop);
968 ps->may_writes = pet_scop_get_may_writes(scop);
969 ps->tagged_must_writes = pet_scop_get_tagged_must_writes(scop);
970 ps->must_writes = pet_scop_get_must_writes(scop);
971 ps->tagged_must_kills = pet_scop_get_tagged_must_kills(scop);
972 ps->must_kills = pet_scop_get_must_kills(scop);
973 ps->schedule = isl_schedule_copy(scop->schedule);
974 ps->pet = scop;
975 ps->independence = isl_union_map_empty(isl_set_get_space(ps->context));
976 for (i = 0; i < scop->n_independence; ++i)
977 ps->independence = isl_union_map_union(ps->independence,
978 isl_union_map_copy(scop->independences[i]->filter));
980 report_empty_context(ps);
982 compute_tagger(ps);
983 compute_dependences(ps);
984 eliminate_dead_code(ps);
986 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
987 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
988 !ps->must_kills || !ps->schedule || !ps->independence || !ps->names)
989 return ppcg_scop_free(ps);
991 return ps;
994 /* Internal data structure for ppcg_transform.
996 struct ppcg_transform_data {
997 struct ppcg_options *options;
998 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
999 struct ppcg_scop *scop, void *user);
1000 void *user;
1003 /* Should we print the original code?
1004 * That is, does "scop" involve any data dependent conditions or
1005 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
1007 static int print_original(struct pet_scop *scop, struct ppcg_options *options)
1009 if (!pet_scop_can_build_ast_exprs(scop)) {
1010 if (options->debug->verbose)
1011 fprintf(stdout, "Printing original code because "
1012 "some index expressions cannot currently "
1013 "be printed\n");
1014 return 1;
1017 if (pet_scop_has_data_dependent_conditions(scop)) {
1018 if (options->debug->verbose)
1019 fprintf(stdout, "Printing original code because "
1020 "input involves data dependent conditions\n");
1021 return 1;
1024 return 0;
1027 /* Callback for pet_transform_C_source that transforms
1028 * the given pet_scop to a ppcg_scop before calling the
1029 * ppcg_transform callback.
1031 * If "scop" contains any data dependent conditions or if we may
1032 * not be able to print the transformed program, then just print
1033 * the original code.
1035 static __isl_give isl_printer *transform(__isl_take isl_printer *p,
1036 struct pet_scop *scop, void *user)
1038 struct ppcg_transform_data *data = user;
1039 struct ppcg_scop *ps;
1041 if (print_original(scop, data->options)) {
1042 p = pet_scop_print_original(scop, p);
1043 pet_scop_free(scop);
1044 return p;
1047 scop = pet_scop_align_params(scop);
1048 ps = ppcg_scop_from_pet_scop(scop, data->options);
1050 p = data->transform(p, ps, data->user);
1052 ppcg_scop_free(ps);
1053 pet_scop_free(scop);
1055 return p;
1058 /* Transform the C source file "input" by rewriting each scop
1059 * through a call to "transform".
1060 * The transformed C code is written to "out".
1062 * This is a wrapper around pet_transform_C_source that transforms
1063 * the pet_scop to a ppcg_scop before calling "fn".
1065 int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
1066 struct ppcg_options *options,
1067 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
1068 struct ppcg_scop *scop, void *user), void *user)
1070 struct ppcg_transform_data data = { options, fn, user };
1071 return pet_transform_C_source(ctx, input, out, &transform, &data);
1074 /* Check consistency of options.
1076 * Return -1 on error.
1078 static int check_options(isl_ctx *ctx)
1080 struct options *options;
1082 options = isl_ctx_peek_options(ctx, &options_args);
1083 if (!options)
1084 isl_die(ctx, isl_error_internal,
1085 "unable to find options", return -1);
1087 if (options->ppcg->openmp &&
1088 !isl_options_get_ast_build_atomic_upper_bound(ctx))
1089 isl_die(ctx, isl_error_invalid,
1090 "OpenMP requires atomic bounds", return -1);
1092 return 0;
1095 int main(int argc, char **argv)
1097 int r;
1098 isl_ctx *ctx;
1099 struct options *options;
1101 options = options_new_with_defaults();
1102 assert(options);
1104 ctx = isl_ctx_alloc_with_options(&options_args, options);
1105 ppcg_options_set_target_defaults(options->ppcg);
1106 isl_options_set_ast_build_detect_min_max(ctx, 1);
1107 isl_options_set_ast_print_macro_once(ctx, 1);
1108 isl_options_set_schedule_whole_component(ctx, 0);
1109 isl_options_set_schedule_maximize_band_depth(ctx, 1);
1110 isl_options_set_schedule_maximize_coincidence(ctx, 1);
1111 pet_options_set_encapsulate_dynamic_control(ctx, 1);
1112 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
1114 if (check_options(ctx) < 0)
1115 r = EXIT_FAILURE;
1116 else if (options->ppcg->target == PPCG_TARGET_CUDA)
1117 r = generate_cuda(ctx, options->ppcg, options->input);
1118 else if (options->ppcg->target == PPCG_TARGET_OPENCL)
1119 r = generate_opencl(ctx, options->ppcg, options->input,
1120 options->output);
1121 else
1122 r = generate_cpu(ctx, options->ppcg, options->input,
1123 options->output);
1125 isl_ctx_free(ctx);
1127 return r;