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