2 * Copyright 2011 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
19 #include <isl/options.h>
20 #include <isl/schedule.h>
21 #include <isl/ast_build.h>
22 #include <isl/schedule.h>
25 #include "ppcg_options.h"
31 struct isl_options
*isl
;
32 struct pet_options
*pet
;
33 struct ppcg_options
*ppcg
;
38 const char *ppcg_version(void);
39 static void print_version(void)
41 printf("%s", ppcg_version());
44 ISL_ARGS_START(struct options
, options_args
)
45 ISL_ARG_CHILD(struct options
, 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
)
54 ISL_ARG_DEF(options
, struct options
, options_args
)
56 /* Return a pointer to the final path component of "filename" or
57 * to "filename" itself if it does not contain any components.
59 const char *ppcg_base_name(const char *filename
)
63 base
= strrchr(filename
, '/');
70 /* Copy the base name of "input" to "name" and return its length.
71 * "name" is not NULL terminated.
73 * In particular, remove all leading directory components and
74 * the final extension, if any.
76 int ppcg_extract_base_name(char *name
, const char *input
)
82 base
= ppcg_base_name(input
);
83 ext
= strrchr(base
, '.');
84 len
= ext
? ext
- base
: strlen(base
);
86 memcpy(name
, base
, len
);
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).
97 static __isl_give isl_id_to_ast_expr
*collect_names(struct pet_scop
*scop
)
102 isl_id_to_ast_expr
*names
;
104 ctx
= isl_set_get_ctx(scop
->context
);
106 n
= isl_set_dim(scop
->context
, isl_dim_param
);
108 names
= isl_id_to_ast_expr_alloc(ctx
, n
+ scop
->n_array
);
109 zero
= isl_ast_expr_from_val(isl_val_zero(ctx
));
111 for (i
= 0; i
< n
; ++i
) {
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
));
119 for (i
= 0; i
< scop
->n_array
; ++i
) {
120 struct pet_array
*array
= scop
->arrays
[i
];
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
));
128 isl_ast_expr_free(zero
);
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".
137 static __isl_give isl_id
*generate_name(struct ppcg_scop
*scop
,
138 const char *prefix
, int i
)
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
);
151 while ((has_name
= isl_id_to_ast_expr_has(scop
->names
, id
)) == 1) {
153 snprintf(name
, sizeof(name
), "%s%d_%d", prefix
, i
, j
++);
154 id
= isl_id_alloc(ctx
, name
, NULL
);
157 return has_name
< 0 ? isl_id_free(id
) : id
;
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".
164 __isl_give isl_id_list
*ppcg_scop_generate_names(struct ppcg_scop
*scop
,
165 int n
, const char *prefix
)
172 ctx
= isl_set_get_ctx(scop
->context
);
173 names
= isl_id_list_alloc(ctx
, n
);
174 for (i
= 0; i
< n
; ++i
) {
177 id
= generate_name(scop
, prefix
, i
);
178 names
= isl_id_list_add(names
, id
);
184 /* Is "stmt" not a kill statement?
186 static int is_not_kill(struct pet_stmt
*stmt
)
188 return !pet_stmt_is_kill(stmt
);
191 /* Collect the iteration domains of the statements in "scop" that
194 static __isl_give isl_union_set
*collect_domains(struct pet_scop
*scop
,
195 int (*pred
)(struct pet_stmt
*stmt
))
199 isl_union_set
*domain
;
204 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
206 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
207 struct pet_stmt
*stmt
= scop
->stmts
[i
];
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
));
218 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
219 domain
= isl_union_set_add_set(domain
, domain_i
);
225 /* Collect the iteration domains of the statements in "scop",
226 * skipping kill statements.
228 static __isl_give isl_union_set
*collect_non_kill_domains(struct pet_scop
*scop
)
230 return collect_domains(scop
, &is_not_kill
);
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.
238 static int set_has_call(__isl_keep pet_expr
*expr
, void *user
)
240 int *has_call
= user
;
247 /* Does "expr" contain any call expressions?
249 static int expr_has_call(__isl_keep pet_expr
*expr
)
253 if (pet_expr_foreach_call_expr(expr
, &set_has_call
, &has_call
) < 0 &&
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.
264 static int check_call(__isl_keep pet_expr
*expr
, void *user
)
266 int *has_call
= user
;
268 if (expr_has_call(expr
))
271 return *has_call
? -1 : 0;
274 /* Does "stmt" contain any call expressions?
276 static int has_call(struct pet_stmt
*stmt
)
280 if (pet_tree_foreach_expr(stmt
->body
, &check_call
, &has_call
) < 0 &&
287 /* Collect the iteration domains of the statements in "scop"
288 * that contain a call expression.
290 static __isl_give isl_union_set
*collect_call_domains(struct pet_scop
*scop
)
292 return collect_domains(scop
, &has_call
);
295 /* Given a union of "tagged" access relations of the form
297 * [S_i[...] -> R_j[]] -> A_k[...]
299 * project out the "tags" (R_j[]).
300 * That is, return a union of relations of the form
302 * S_i[...] -> A_k[...]
304 static __isl_give isl_union_map
*project_out_tags(
305 __isl_take isl_union_map
*umap
)
307 return isl_union_map_domain_factor_domain(umap
);
310 /* Construct a relation from the iteration domains to tagged iteration
311 * domains with as range the reference tags that appear
312 * in any of the reads, writes or kills.
313 * Store the result in ps->tagger.
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
318 * { S[i,j] -> [S[i,j] -> R_1[]]; S[i,j] -> [S[i,j] -> R_2[]] }
320 static void compute_tagger(struct ppcg_scop
*ps
)
322 isl_union_map
*tagged
, *tagger
;
324 tagged
= isl_union_map_copy(ps
->tagged_reads
);
325 tagged
= isl_union_map_union(tagged
,
326 isl_union_map_copy(ps
->tagged_may_writes
));
327 tagged
= isl_union_map_union(tagged
,
328 isl_union_map_copy(ps
->tagged_must_kills
));
330 tagger
= isl_union_map_universe(tagged
);
331 tagger
= isl_union_set_unwrap(isl_union_map_domain(tagger
));
332 tagger
= isl_union_map_reverse(isl_union_map_domain_map(tagger
));
337 /* Compute the live out accesses, i.e., the writes that are
338 * potentially not killed by any kills or any other writes, and
339 * store them in ps->live_out.
341 * We compute the "dependence" of any "kill" (an explicit kill
342 * or a must write) on any may write.
343 * The may writes with a "depending" kill are definitely killed.
344 * The remaining may writes can potentially be live out.
346 static void compute_live_out(struct ppcg_scop
*ps
)
348 isl_union_map
*tagger
;
349 isl_union_map
*schedule
;
350 isl_union_map
*kills
;
351 isl_union_map
*exposed
;
352 isl_union_map
*covering
;
353 isl_union_access_info
*access
;
354 isl_union_flow
*flow
;
356 tagger
= isl_union_map_copy(ps
->tagger
);
357 schedule
= isl_schedule_get_map(ps
->schedule
);
358 schedule
= isl_union_map_apply_domain(schedule
, tagger
);
359 kills
= isl_union_map_union(isl_union_map_copy(ps
->tagged_must_writes
),
360 isl_union_map_copy(ps
->tagged_must_kills
));
361 access
= isl_union_access_info_from_sink(kills
);
362 access
= isl_union_access_info_set_may_source(access
,
363 isl_union_map_copy(ps
->tagged_may_writes
));
364 access
= isl_union_access_info_set_schedule_map(access
, schedule
);
365 flow
= isl_union_access_info_compute_flow(access
);
366 covering
= isl_union_flow_get_may_dependence(flow
);
367 isl_union_flow_free(flow
);
368 exposed
= isl_union_map_copy(ps
->tagged_may_writes
);
369 exposed
= isl_union_map_subtract_domain(exposed
,
370 isl_union_map_domain(covering
));
371 ps
->live_out
= project_out_tags(exposed
);
374 /* Compute the flow dependences and the live_in accesses and store
375 * the results in ps->dep_flow and ps->live_in.
376 * A copy of the flow dependences, tagged with the reference tags
377 * is stored in ps->tagged_dep_flow.
379 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
380 * and then project out the tags.
382 * We allow both the must writes and the must kills to serve as
383 * definite sources such that a subsequent read would not depend
384 * on any earlier write. The resulting flow dependences with
385 * a must kill as source reflect possibly uninitialized reads.
386 * No dependences need to be introduced to protect such reads
387 * (other than those imposed by potential flows from may writes
388 * that follow the kill). We therefore those flow dependences.
389 * This is also useful for the dead code elimination, which assumes
390 * the flow sources are non-kill instances.
392 static void compute_tagged_flow_dep(struct ppcg_scop
*ps
)
394 isl_union_map
*tagger
;
395 isl_union_map
*schedule
;
396 isl_union_map
*live_in
;
397 isl_union_access_info
*access
;
398 isl_union_flow
*flow
;
399 isl_union_map
*must_source
;
400 isl_union_map
*kills
;
401 isl_union_map
*tagged_flow
;
403 tagger
= isl_union_map_copy(ps
->tagger
);
404 schedule
= isl_schedule_get_map(ps
->schedule
);
405 schedule
= isl_union_map_apply_domain(schedule
, tagger
);
406 kills
= isl_union_map_copy(ps
->tagged_must_kills
);
407 must_source
= isl_union_map_copy(ps
->tagged_must_writes
);
408 must_source
= isl_union_map_union(must_source
,
409 isl_union_map_copy(kills
));
410 access
= isl_union_access_info_from_sink(
411 isl_union_map_copy(ps
->tagged_reads
));
412 access
= isl_union_access_info_set_must_source(access
, must_source
);
413 access
= isl_union_access_info_set_may_source(access
,
414 isl_union_map_copy(ps
->tagged_may_writes
));
415 access
= isl_union_access_info_set_schedule_map(access
, schedule
);
416 flow
= isl_union_access_info_compute_flow(access
);
417 tagged_flow
= isl_union_flow_get_may_dependence(flow
);
418 tagged_flow
= isl_union_map_subtract_domain(tagged_flow
,
419 isl_union_map_domain(kills
));
420 ps
->tagged_dep_flow
= tagged_flow
;
421 ps
->dep_flow
= isl_union_map_copy(ps
->tagged_dep_flow
);
422 ps
->dep_flow
= isl_union_map_factor_domain(ps
->dep_flow
);
423 live_in
= isl_union_flow_get_may_no_source(flow
);
424 ps
->live_in
= project_out_tags(live_in
);
425 isl_union_flow_free(flow
);
428 /* Compute the order dependences that prevent the potential live ranges
430 * "before" contains all pairs of statement iterations where
431 * the first is executed before the second according to the original schedule.
433 * In particular, construct a union of relations
435 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
437 * where [R[...] -> R_1[]] is the range of one or more live ranges
438 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
439 * live ranges (i.e., a write). Moreover, the read and the write
440 * access the same memory element and the read occurs before the write
441 * in the original schedule.
442 * The scheduler allows some of these dependences to be violated, provided
443 * the adjacent live ranges are all local (i.e., their domain and range
444 * are mapped to the same point by the current schedule band).
446 * Note that if a live range is not local, then we need to make
447 * sure it does not overlap with _any_ other live range, and not
448 * just with the "previous" and/or the "next" live range.
449 * We therefore add order dependences between reads and
450 * _any_ later potential write.
452 * We also need to be careful about writes without a corresponding read.
453 * They are already prevented from moving past non-local preceding
454 * intervals, but we also need to prevent them from moving past non-local
455 * following intervals. We therefore also add order dependences from
456 * potential writes that do not appear in any intervals
457 * to all later potential writes.
458 * Note that dead code elimination should have removed most of these
459 * dead writes, but the dead code elimination may not remove all dead writes,
460 * so we need to consider them to be safe.
462 static void compute_order_dependences(struct ppcg_scop
*ps
,
463 __isl_take isl_union_map
*before
)
465 isl_union_map
*reads
;
466 isl_union_map
*shared_access
;
467 isl_union_set
*matched
;
468 isl_union_map
*unmatched
;
469 isl_union_set
*domain
;
471 reads
= isl_union_map_copy(ps
->tagged_reads
);
472 matched
= isl_union_map_domain(isl_union_map_copy(ps
->tagged_dep_flow
));
473 unmatched
= isl_union_map_copy(ps
->tagged_may_writes
);
474 unmatched
= isl_union_map_subtract_domain(unmatched
, matched
);
475 reads
= isl_union_map_union(reads
, unmatched
);
476 shared_access
= isl_union_map_copy(ps
->tagged_may_writes
);
477 shared_access
= isl_union_map_reverse(shared_access
);
478 shared_access
= isl_union_map_apply_range(reads
, shared_access
);
479 shared_access
= isl_union_map_zip(shared_access
);
480 shared_access
= isl_union_map_intersect_domain(shared_access
,
481 isl_union_map_wrap(before
));
482 domain
= isl_union_map_domain(isl_union_map_copy(shared_access
));
483 shared_access
= isl_union_map_zip(shared_access
);
484 ps
->dep_order
= isl_union_set_unwrap(domain
);
485 ps
->tagged_dep_order
= shared_access
;
488 /* Compute the external false dependences of the program represented by "scop"
489 * in case live range reordering is allowed.
490 * "before" contains all pairs of statement iterations where
491 * the first is executed before the second according to the original schedule.
493 * The anti-dependences are already taken care of by the order dependences.
494 * The external false dependences are only used to ensure that live-in and
495 * live-out data is not overwritten by any writes inside the scop.
497 * In particular, the reads from live-in data need to precede any
498 * later write to the same memory element.
499 * As to live-out data, the last writes need to remain the last writes.
500 * That is, any earlier write in the original schedule needs to precede
501 * the last write to the same memory element in the computed schedule.
502 * The possible last writes have been computed by compute_live_out.
503 * They may include kills, but if the last access is a kill,
504 * then the corresponding dependences will effectively be ignored
505 * since we do not schedule any kill statements.
507 * Note that the set of live-in and live-out accesses may be
508 * an overapproximation. There may therefore be potential writes
509 * before a live-in access and after a live-out access.
511 static void compute_external_false_dependences(struct ppcg_scop
*ps
,
512 __isl_take isl_union_map
*before
)
514 isl_union_map
*shared_access
;
515 isl_union_map
*exposed
;
516 isl_union_map
*live_in
;
518 exposed
= isl_union_map_copy(ps
->live_out
);
520 exposed
= isl_union_map_reverse(exposed
);
521 shared_access
= isl_union_map_copy(ps
->may_writes
);
522 shared_access
= isl_union_map_apply_range(shared_access
, exposed
);
524 ps
->dep_external
= shared_access
;
526 live_in
= isl_union_map_apply_range(isl_union_map_copy(ps
->live_in
),
527 isl_union_map_reverse(isl_union_map_copy(ps
->may_writes
)));
529 ps
->dep_external
= isl_union_map_union(ps
->dep_external
, live_in
);
530 ps
->dep_external
= isl_union_map_intersect(ps
->dep_external
, before
);
533 /* Compute the dependences of the program represented by "scop"
534 * in case live range reordering is allowed.
536 * We compute the actual live ranges and the corresponding order
539 static void compute_live_range_reordering_dependences(struct ppcg_scop
*ps
)
541 isl_union_map
*before
;
542 isl_union_map
*schedule
;
544 schedule
= isl_schedule_get_map(ps
->schedule
);
545 before
= isl_union_map_lex_lt_union_map(schedule
,
546 isl_union_map_copy(schedule
));
548 compute_tagged_flow_dep(ps
);
549 compute_order_dependences(ps
, isl_union_map_copy(before
));
550 compute_external_false_dependences(ps
, before
);
553 /* Compute the potential flow dependences and the potential live in
556 static void compute_flow_dep(struct ppcg_scop
*ps
)
558 isl_union_access_info
*access
;
559 isl_union_flow
*flow
;
561 access
= isl_union_access_info_from_sink(isl_union_map_copy(ps
->reads
));
562 access
= isl_union_access_info_set_must_source(access
,
563 isl_union_map_copy(ps
->must_writes
));
564 access
= isl_union_access_info_set_may_source(access
,
565 isl_union_map_copy(ps
->may_writes
));
566 access
= isl_union_access_info_set_schedule_map(access
,
567 isl_schedule_get_map(ps
->schedule
));
568 flow
= isl_union_access_info_compute_flow(access
);
570 ps
->dep_flow
= isl_union_flow_get_may_dependence(flow
);
571 ps
->live_in
= isl_union_flow_get_may_no_source(flow
);
572 isl_union_flow_free(flow
);
575 /* Compute the dependences of the program represented by "scop".
576 * Store the computed potential flow dependences
577 * in scop->dep_flow and the reads with potentially no corresponding writes in
579 * Store the potential live out accesses in scop->live_out.
580 * Store the potential false (anti and output) dependences in scop->dep_false.
582 * If live range reordering is allowed, then we compute a separate
583 * set of order dependences and a set of external false dependences
584 * in compute_live_range_reordering_dependences.
586 static void compute_dependences(struct ppcg_scop
*scop
)
588 isl_union_map
*may_source
;
589 isl_union_access_info
*access
;
590 isl_union_flow
*flow
;
595 compute_live_out(scop
);
597 if (scop
->options
->live_range_reordering
)
598 compute_live_range_reordering_dependences(scop
);
599 else if (scop
->options
->target
!= PPCG_TARGET_C
)
600 compute_tagged_flow_dep(scop
);
602 compute_flow_dep(scop
);
604 may_source
= isl_union_map_union(isl_union_map_copy(scop
->may_writes
),
605 isl_union_map_copy(scop
->reads
));
606 access
= isl_union_access_info_from_sink(
607 isl_union_map_copy(scop
->may_writes
));
608 access
= isl_union_access_info_set_must_source(access
,
609 isl_union_map_copy(scop
->must_writes
));
610 access
= isl_union_access_info_set_may_source(access
, may_source
);
611 access
= isl_union_access_info_set_schedule_map(access
,
612 isl_schedule_get_map(scop
->schedule
));
613 flow
= isl_union_access_info_compute_flow(access
);
615 scop
->dep_false
= isl_union_flow_get_may_dependence(flow
);
616 scop
->dep_false
= isl_union_map_coalesce(scop
->dep_false
);
617 isl_union_flow_free(flow
);
620 /* Eliminate dead code from ps->domain.
622 * In particular, intersect both ps->domain and the domain of
623 * ps->schedule with the (parts of) iteration
624 * domains that are needed to produce the output or for statement
625 * iterations that call functions.
626 * Also intersect the range of the dataflow dependences with
627 * this domain such that the removed instances will no longer
628 * be considered as targets of dataflow.
630 * We start with the iteration domains that call functions
631 * and the set of iterations that last write to an array
632 * (except those that are later killed).
634 * Then we add those statement iterations that produce
635 * something needed by the "live" statements iterations.
636 * We keep doing this until no more statement iterations can be added.
637 * To ensure that the procedure terminates, we compute the affine
638 * hull of the live iterations (bounded to the original iteration
639 * domains) each time we have added extra iterations.
641 static void eliminate_dead_code(struct ppcg_scop
*ps
)
645 isl_union_map
*tagger
;
647 live
= isl_union_map_domain(isl_union_map_copy(ps
->live_out
));
648 if (!isl_union_set_is_empty(ps
->call
)) {
649 live
= isl_union_set_union(live
, isl_union_set_copy(ps
->call
));
650 live
= isl_union_set_coalesce(live
);
653 dep
= isl_union_map_copy(ps
->dep_flow
);
654 dep
= isl_union_map_reverse(dep
);
657 isl_union_set
*extra
;
659 extra
= isl_union_set_apply(isl_union_set_copy(live
),
660 isl_union_map_copy(dep
));
661 if (isl_union_set_is_subset(extra
, live
)) {
662 isl_union_set_free(extra
);
666 live
= isl_union_set_union(live
, extra
);
667 live
= isl_union_set_affine_hull(live
);
668 live
= isl_union_set_intersect(live
,
669 isl_union_set_copy(ps
->domain
));
672 isl_union_map_free(dep
);
674 ps
->domain
= isl_union_set_intersect(ps
->domain
,
675 isl_union_set_copy(live
));
676 ps
->schedule
= isl_schedule_intersect_domain(ps
->schedule
,
677 isl_union_set_copy(live
));
678 ps
->dep_flow
= isl_union_map_intersect_range(ps
->dep_flow
,
679 isl_union_set_copy(live
));
680 tagger
= isl_union_map_copy(ps
->tagger
);
681 live
= isl_union_set_apply(live
, tagger
);
682 ps
->tagged_dep_flow
= isl_union_map_intersect_range(ps
->tagged_dep_flow
,
686 /* Intersect "set" with the set described by "str", taking the NULL
687 * string to represent the universal set.
689 static __isl_give isl_set
*set_intersect_str(__isl_take isl_set
*set
,
698 ctx
= isl_set_get_ctx(set
);
699 set2
= isl_set_read_from_str(ctx
, str
);
700 set
= isl_set_intersect(set
, set2
);
705 static void *ppcg_scop_free(struct ppcg_scop
*ps
)
710 isl_set_free(ps
->context
);
711 isl_union_set_free(ps
->domain
);
712 isl_union_set_free(ps
->call
);
713 isl_union_map_free(ps
->tagged_reads
);
714 isl_union_map_free(ps
->reads
);
715 isl_union_map_free(ps
->live_in
);
716 isl_union_map_free(ps
->tagged_may_writes
);
717 isl_union_map_free(ps
->tagged_must_writes
);
718 isl_union_map_free(ps
->may_writes
);
719 isl_union_map_free(ps
->must_writes
);
720 isl_union_map_free(ps
->live_out
);
721 isl_union_map_free(ps
->tagged_must_kills
);
722 isl_union_map_free(ps
->tagged_dep_flow
);
723 isl_union_map_free(ps
->dep_flow
);
724 isl_union_map_free(ps
->dep_false
);
725 isl_union_map_free(ps
->dep_external
);
726 isl_union_map_free(ps
->tagged_dep_order
);
727 isl_union_map_free(ps
->dep_order
);
728 isl_schedule_free(ps
->schedule
);
729 isl_union_map_free(ps
->tagger
);
730 isl_union_map_free(ps
->independence
);
731 isl_id_to_ast_expr_free(ps
->names
);
738 /* Extract a ppcg_scop from a pet_scop.
740 * The constructed ppcg_scop refers to elements from the pet_scop
741 * so the pet_scop should not be freed before the ppcg_scop.
743 static struct ppcg_scop
*ppcg_scop_from_pet_scop(struct pet_scop
*scop
,
744 struct ppcg_options
*options
)
748 struct ppcg_scop
*ps
;
753 ctx
= isl_set_get_ctx(scop
->context
);
755 ps
= isl_calloc_type(ctx
, struct ppcg_scop
);
759 ps
->names
= collect_names(scop
);
760 ps
->options
= options
;
761 ps
->start
= pet_loc_get_start(scop
->loc
);
762 ps
->end
= pet_loc_get_end(scop
->loc
);
763 ps
->context
= isl_set_copy(scop
->context
);
764 ps
->context
= set_intersect_str(ps
->context
, options
->ctx
);
765 ps
->domain
= collect_non_kill_domains(scop
);
766 ps
->call
= collect_call_domains(scop
);
767 ps
->tagged_reads
= pet_scop_collect_tagged_may_reads(scop
);
768 ps
->reads
= pet_scop_collect_may_reads(scop
);
769 ps
->tagged_may_writes
= pet_scop_collect_tagged_may_writes(scop
);
770 ps
->may_writes
= pet_scop_collect_may_writes(scop
);
771 ps
->tagged_must_writes
= pet_scop_collect_tagged_must_writes(scop
);
772 ps
->must_writes
= pet_scop_collect_must_writes(scop
);
773 ps
->tagged_must_kills
= pet_scop_collect_tagged_must_kills(scop
);
774 ps
->schedule
= isl_schedule_copy(scop
->schedule
);
776 ps
->independence
= isl_union_map_empty(isl_set_get_space(ps
->context
));
777 for (i
= 0; i
< scop
->n_independence
; ++i
)
778 ps
->independence
= isl_union_map_union(ps
->independence
,
779 isl_union_map_copy(scop
->independences
[i
]->filter
));
782 compute_dependences(ps
);
783 eliminate_dead_code(ps
);
785 if (!ps
->context
|| !ps
->domain
|| !ps
->call
|| !ps
->reads
||
786 !ps
->may_writes
|| !ps
->must_writes
|| !ps
->tagged_must_kills
||
787 !ps
->schedule
|| !ps
->independence
|| !ps
->names
)
788 return ppcg_scop_free(ps
);
793 /* Internal data structure for ppcg_transform.
795 struct ppcg_transform_data
{
796 struct ppcg_options
*options
;
797 __isl_give isl_printer
*(*transform
)(__isl_take isl_printer
*p
,
798 struct ppcg_scop
*scop
, void *user
);
802 /* Should we print the original code?
803 * That is, does "scop" involve any data dependent conditions or
804 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
806 static int print_original(struct pet_scop
*scop
, struct ppcg_options
*options
)
808 if (!pet_scop_can_build_ast_exprs(scop
)) {
809 if (options
->debug
->verbose
)
810 fprintf(stdout
, "Printing original code because "
811 "some index expressions cannot currently "
816 if (pet_scop_has_data_dependent_conditions(scop
)) {
817 if (options
->debug
->verbose
)
818 fprintf(stdout
, "Printing original code because "
819 "input involves data dependent conditions\n");
826 /* Callback for pet_transform_C_source that transforms
827 * the given pet_scop to a ppcg_scop before calling the
828 * ppcg_transform callback.
830 * If "scop" contains any data dependent conditions or if we may
831 * not be able to print the transformed program, then just print
834 static __isl_give isl_printer
*transform(__isl_take isl_printer
*p
,
835 struct pet_scop
*scop
, void *user
)
837 struct ppcg_transform_data
*data
= user
;
838 struct ppcg_scop
*ps
;
840 if (print_original(scop
, data
->options
)) {
841 p
= pet_scop_print_original(scop
, p
);
846 scop
= pet_scop_align_params(scop
);
847 ps
= ppcg_scop_from_pet_scop(scop
, data
->options
);
849 p
= data
->transform(p
, ps
, data
->user
);
857 /* Transform the C source file "input" by rewriting each scop
858 * through a call to "transform".
859 * The transformed C code is written to "out".
861 * This is a wrapper around pet_transform_C_source that transforms
862 * the pet_scop to a ppcg_scop before calling "fn".
864 int ppcg_transform(isl_ctx
*ctx
, const char *input
, FILE *out
,
865 struct ppcg_options
*options
,
866 __isl_give isl_printer
*(*fn
)(__isl_take isl_printer
*p
,
867 struct ppcg_scop
*scop
, void *user
), void *user
)
869 struct ppcg_transform_data data
= { options
, fn
, user
};
870 return pet_transform_C_source(ctx
, input
, out
, &transform
, &data
);
873 /* Check consistency of options.
875 * Return -1 on error.
877 static int check_options(isl_ctx
*ctx
)
879 struct options
*options
;
881 options
= isl_ctx_peek_options(ctx
, &options_args
);
883 isl_die(ctx
, isl_error_internal
,
884 "unable to find options", return -1);
886 if (options
->ppcg
->openmp
&&
887 !isl_options_get_ast_build_atomic_upper_bound(ctx
))
888 isl_die(ctx
, isl_error_invalid
,
889 "OpenMP requires atomic bounds", return -1);
894 int main(int argc
, char **argv
)
898 struct options
*options
;
900 options
= options_new_with_defaults();
903 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
904 isl_options_set_schedule_outer_coincidence(ctx
, 1);
905 isl_options_set_schedule_maximize_band_depth(ctx
, 1);
906 pet_options_set_encapsulate_dynamic_control(ctx
, 1);
907 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
909 if (check_options(ctx
) < 0)
911 else if (options
->ppcg
->target
== PPCG_TARGET_CUDA
)
912 r
= generate_cuda(ctx
, options
->ppcg
, options
->input
);
913 else if (options
->ppcg
->target
== PPCG_TARGET_OPENCL
)
914 r
= generate_opencl(ctx
, options
->ppcg
, options
->input
,
917 r
= generate_cpu(ctx
, options
->ppcg
, options
->input
,