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,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
22 #include <isl/union_set.h>
23 #include <isl/union_map.h>
26 #include <isl/options.h>
27 #include <isl/schedule.h>
29 #include <isl/id_to_ast_expr.h>
30 #include <isl/ast_build.h>
31 #include <isl/schedule.h>
34 #include "ppcg_options.h"
40 struct pet_options
*pet
;
41 struct ppcg_options
*ppcg
;
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
)
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
)
70 base
= strrchr(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
)
89 base
= ppcg_base_name(input
);
90 ext
= strrchr(base
, '.');
91 len
= ext
? ext
- base
: strlen(base
);
93 memcpy(name
, base
, 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
)
108 for (i
= 0; i
< scop
->pet
->n_array
; ++i
)
109 if (scop
->pet
->arrays
[i
]->declared
&&
110 !scop
->pet
->arrays
[i
]->exposed
)
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
)
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
) {
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
];
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
);
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
)
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
);
176 while ((has_name
= isl_id_to_ast_expr_has(scop
->names
, id
)) == 1) {
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
)
196 ctx
= isl_set_get_ctx(scop
->context
);
197 names
= isl_id_list_alloc(ctx
, n
);
198 for (i
= 0; i
< n
; ++i
) {
201 id
= generate_name(scop
, prefix
, i
);
202 names
= isl_id_list_add(names
, id
);
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
218 static __isl_give isl_union_set
*collect_domains(struct pet_scop
*scop
,
219 int (*pred
)(struct pet_stmt
*stmt
))
223 isl_union_set
*domain
;
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
];
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
);
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
;
271 /* Does "expr" contain any call expressions?
273 static int expr_has_call(__isl_keep pet_expr
*expr
)
277 if (pet_expr_foreach_call_expr(expr
, &set_has_call
, &has_call
) < 0 &&
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
))
295 return *has_call
? -1 : 0;
298 /* Does "stmt" contain any call expressions?
300 static int has_call(struct pet_stmt
*stmt
)
304 if (pet_tree_foreach_expr(stmt
->body
, &check_call
, &has_call
) < 0 &&
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
);
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
382 * containing all such pairs for which there is a kill statement instance,
383 * i.e., all pairs that have been killed.
385 static void compute_live_out(struct ppcg_scop
*ps
)
387 isl_schedule
*schedule
;
388 isl_union_map
*kills
;
389 isl_union_map
*exposed
;
390 isl_union_map
*covering
;
391 isl_union_access_info
*access
;
392 isl_union_flow
*flow
;
394 schedule
= isl_schedule_copy(ps
->schedule
);
395 kills
= isl_union_map_union(isl_union_map_copy(ps
->must_writes
),
396 isl_union_map_copy(ps
->must_kills
));
397 access
= isl_union_access_info_from_sink(kills
);
398 access
= isl_union_access_info_set_may_source(access
,
399 isl_union_map_copy(ps
->may_writes
));
400 access
= isl_union_access_info_set_schedule(access
, schedule
);
401 flow
= isl_union_access_info_compute_flow(access
);
402 covering
= isl_union_flow_get_full_may_dependence(flow
);
403 isl_union_flow_free(flow
);
405 covering
= isl_union_map_range_factor_range(covering
);
406 exposed
= isl_union_map_copy(ps
->may_writes
);
407 exposed
= isl_union_map_subtract(exposed
, covering
);
408 ps
->live_out
= exposed
;
411 /* Compute the tagged flow dependences and the live_in accesses and store
412 * the results in ps->tagged_dep_flow and ps->live_in.
414 * We allow both the must writes and the must kills to serve as
415 * definite sources such that a subsequent read would not depend
416 * on any earlier write. The resulting flow dependences with
417 * a must kill as source reflect possibly uninitialized reads.
418 * No dependences need to be introduced to protect such reads
419 * (other than those imposed by potential flows from may writes
420 * that follow the kill). We therefore remove those flow dependences.
421 * This is also useful for the dead code elimination, which assumes
422 * the flow sources are non-kill instances.
424 static void compute_tagged_flow_dep_only(struct ppcg_scop
*ps
)
426 isl_union_pw_multi_aff
*tagger
;
427 isl_schedule
*schedule
;
428 isl_union_map
*live_in
;
429 isl_union_access_info
*access
;
430 isl_union_flow
*flow
;
431 isl_union_map
*must_source
;
432 isl_union_map
*kills
;
433 isl_union_map
*tagged_flow
;
435 tagger
= isl_union_pw_multi_aff_copy(ps
->tagger
);
436 schedule
= isl_schedule_copy(ps
->schedule
);
437 schedule
= isl_schedule_pullback_union_pw_multi_aff(schedule
, tagger
);
438 kills
= isl_union_map_copy(ps
->tagged_must_kills
);
439 must_source
= isl_union_map_copy(ps
->tagged_must_writes
);
440 must_source
= isl_union_map_union(must_source
,
441 isl_union_map_copy(kills
));
442 access
= isl_union_access_info_from_sink(
443 isl_union_map_copy(ps
->tagged_reads
));
444 access
= isl_union_access_info_set_must_source(access
, must_source
);
445 access
= isl_union_access_info_set_may_source(access
,
446 isl_union_map_copy(ps
->tagged_may_writes
));
447 access
= isl_union_access_info_set_schedule(access
, schedule
);
448 flow
= isl_union_access_info_compute_flow(access
);
449 tagged_flow
= isl_union_flow_get_may_dependence(flow
);
450 tagged_flow
= isl_union_map_subtract_domain(tagged_flow
,
451 isl_union_map_domain(kills
));
452 ps
->tagged_dep_flow
= tagged_flow
;
453 live_in
= isl_union_flow_get_may_no_source(flow
);
454 ps
->live_in
= project_out_tags(live_in
);
455 isl_union_flow_free(flow
);
458 /* Compute ps->dep_flow from ps->tagged_dep_flow
459 * by projecting out the reference tags.
461 static void derive_flow_dep_from_tagged_flow_dep(struct ppcg_scop
*ps
)
463 ps
->dep_flow
= isl_union_map_copy(ps
->tagged_dep_flow
);
464 ps
->dep_flow
= isl_union_map_factor_domain(ps
->dep_flow
);
467 /* Compute the flow dependences and the live_in accesses and store
468 * the results in ps->dep_flow and ps->live_in.
469 * A copy of the flow dependences, tagged with the reference tags
470 * is stored in ps->tagged_dep_flow.
472 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
473 * and then project out the tags.
475 static void compute_tagged_flow_dep(struct ppcg_scop
*ps
)
477 compute_tagged_flow_dep_only(ps
);
478 derive_flow_dep_from_tagged_flow_dep(ps
);
481 /* Compute the order dependences that prevent the potential live ranges
484 * In particular, construct a union of relations
486 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
488 * where [R[...] -> R_1[]] is the range of one or more live ranges
489 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
490 * live ranges (i.e., a write). Moreover, the read and the write
491 * access the same memory element and the read occurs before the write
492 * in the original schedule.
493 * The scheduler allows some of these dependences to be violated, provided
494 * the adjacent live ranges are all local (i.e., their domain and range
495 * are mapped to the same point by the current schedule band).
497 * Note that if a live range is not local, then we need to make
498 * sure it does not overlap with _any_ other live range, and not
499 * just with the "previous" and/or the "next" live range.
500 * We therefore add order dependences between reads and
501 * _any_ later potential write.
503 * We also need to be careful about writes without a corresponding read.
504 * They are already prevented from moving past non-local preceding
505 * intervals, but we also need to prevent them from moving past non-local
506 * following intervals. We therefore also add order dependences from
507 * potential writes that do not appear in any intervals
508 * to all later potential writes.
509 * Note that dead code elimination should have removed most of these
510 * dead writes, but the dead code elimination may not remove all dead writes,
511 * so we need to consider them to be safe.
513 * The order dependences are computed by computing the "dataflow"
514 * from the above unmatched writes and the reads to the may writes.
515 * The unmatched writes and the reads are treated as may sources
516 * such that they would not kill order dependences from earlier
517 * such writes and reads.
519 static void compute_order_dependences(struct ppcg_scop
*ps
)
521 isl_union_map
*reads
;
522 isl_union_map
*shared_access
;
523 isl_union_set
*matched
;
524 isl_union_map
*unmatched
;
525 isl_union_pw_multi_aff
*tagger
;
526 isl_schedule
*schedule
;
527 isl_union_access_info
*access
;
528 isl_union_flow
*flow
;
530 tagger
= isl_union_pw_multi_aff_copy(ps
->tagger
);
531 schedule
= isl_schedule_copy(ps
->schedule
);
532 schedule
= isl_schedule_pullback_union_pw_multi_aff(schedule
, tagger
);
533 reads
= isl_union_map_copy(ps
->tagged_reads
);
534 matched
= isl_union_map_domain(isl_union_map_copy(ps
->tagged_dep_flow
));
535 unmatched
= isl_union_map_copy(ps
->tagged_may_writes
);
536 unmatched
= isl_union_map_subtract_domain(unmatched
, matched
);
537 reads
= isl_union_map_union(reads
, unmatched
);
538 access
= isl_union_access_info_from_sink(
539 isl_union_map_copy(ps
->tagged_may_writes
));
540 access
= isl_union_access_info_set_may_source(access
, reads
);
541 access
= isl_union_access_info_set_schedule(access
, schedule
);
542 flow
= isl_union_access_info_compute_flow(access
);
543 shared_access
= isl_union_flow_get_may_dependence(flow
);
544 isl_union_flow_free(flow
);
546 ps
->tagged_dep_order
= isl_union_map_copy(shared_access
);
547 ps
->dep_order
= isl_union_map_factor_domain(shared_access
);
550 /* Compute those validity dependences of the program represented by "scop"
551 * that should be unconditionally enforced even when live-range reordering
554 * In particular, compute the external false dependences
555 * as well as order dependences between sources with the same sink.
556 * The anti-dependences are already taken care of by the order dependences.
557 * The external false dependences are only used to ensure that live-in and
558 * live-out data is not overwritten by any writes inside the scop.
559 * The independences are removed from the external false dependences,
560 * but not from the order dependences between sources with the same sink.
562 * In particular, the reads from live-in data need to precede any
563 * later write to the same memory element.
564 * As to live-out data, the last writes need to remain the last writes.
565 * That is, any earlier write in the original schedule needs to precede
566 * the last write to the same memory element in the computed schedule.
567 * The possible last writes have been computed by compute_live_out.
568 * They may include kills, but if the last access is a kill,
569 * then the corresponding dependences will effectively be ignored
570 * since we do not schedule any kill statements.
572 * Note that the set of live-in and live-out accesses may be
573 * an overapproximation. There may therefore be potential writes
574 * before a live-in access and after a live-out access.
576 * In the presence of may-writes, there may be multiple live-ranges
577 * with the same sink, accessing the same memory element.
578 * The sources of these live-ranges need to be executed
579 * in the same relative order as in the original program
580 * since we do not know which of the may-writes will actually
581 * perform a write. Consider all sources that share a sink and
582 * that may write to the same memory element and compute
583 * the order dependences among them.
585 static void compute_forced_dependences(struct ppcg_scop
*ps
)
587 isl_union_map
*shared_access
;
588 isl_union_map
*exposed
;
589 isl_union_map
*live_in
;
590 isl_union_map
*sink_access
;
591 isl_union_map
*shared_sink
;
592 isl_union_access_info
*access
;
593 isl_union_flow
*flow
;
594 isl_schedule
*schedule
;
596 exposed
= isl_union_map_copy(ps
->live_out
);
597 schedule
= isl_schedule_copy(ps
->schedule
);
598 access
= isl_union_access_info_from_sink(exposed
);
599 access
= isl_union_access_info_set_may_source(access
,
600 isl_union_map_copy(ps
->may_writes
));
601 access
= isl_union_access_info_set_schedule(access
, schedule
);
602 flow
= isl_union_access_info_compute_flow(access
);
603 shared_access
= isl_union_flow_get_may_dependence(flow
);
604 isl_union_flow_free(flow
);
605 ps
->dep_forced
= shared_access
;
607 schedule
= isl_schedule_copy(ps
->schedule
);
608 access
= isl_union_access_info_from_sink(
609 isl_union_map_copy(ps
->may_writes
));
610 access
= isl_union_access_info_set_may_source(access
,
611 isl_union_map_copy(ps
->live_in
));
612 access
= isl_union_access_info_set_schedule(access
, schedule
);
613 flow
= isl_union_access_info_compute_flow(access
);
614 live_in
= isl_union_flow_get_may_dependence(flow
);
615 isl_union_flow_free(flow
);
617 ps
->dep_forced
= isl_union_map_union(ps
->dep_forced
, live_in
);
618 ps
->dep_forced
= isl_union_map_subtract(ps
->dep_forced
,
619 isl_union_map_copy(ps
->independence
));
621 schedule
= isl_schedule_copy(ps
->schedule
);
622 sink_access
= isl_union_map_copy(ps
->tagged_dep_flow
);
623 sink_access
= isl_union_map_range_product(sink_access
,
624 isl_union_map_copy(ps
->tagged_may_writes
));
625 sink_access
= isl_union_map_domain_factor_domain(sink_access
);
626 access
= isl_union_access_info_from_sink(
627 isl_union_map_copy(sink_access
));
628 access
= isl_union_access_info_set_may_source(access
, sink_access
);
629 access
= isl_union_access_info_set_schedule(access
, schedule
);
630 flow
= isl_union_access_info_compute_flow(access
);
631 shared_sink
= isl_union_flow_get_may_dependence(flow
);
632 isl_union_flow_free(flow
);
633 ps
->dep_forced
= isl_union_map_union(ps
->dep_forced
, shared_sink
);
636 /* Remove independence from the tagged flow dependences.
637 * Since the user has guaranteed that source and sink of an independence
638 * can be executed in any order, there cannot be a flow dependence
639 * between them, so they can be removed from the set of flow dependences.
640 * However, if the source of such a flow dependence is a must write,
641 * then it may have killed other potential sources, which would have
642 * to be recovered if we were to remove those flow dependences.
643 * We therefore keep the flow dependences that originate in a must write,
644 * even if it corresponds to a known independence.
646 static void remove_independences_from_tagged_flow(struct ppcg_scop
*ps
)
649 isl_union_set
*indep
;
652 tf
= isl_union_map_copy(ps
->tagged_dep_flow
);
653 tf
= isl_union_map_zip(tf
);
654 indep
= isl_union_map_wrap(isl_union_map_copy(ps
->independence
));
655 tf
= isl_union_map_intersect_domain(tf
, indep
);
656 tf
= isl_union_map_zip(tf
);
657 mw
= isl_union_map_domain(isl_union_map_copy(ps
->tagged_must_writes
));
658 tf
= isl_union_map_subtract_domain(tf
, mw
);
659 ps
->tagged_dep_flow
= isl_union_map_subtract(ps
->tagged_dep_flow
, tf
);
662 /* Compute the dependences of the program represented by "scop"
663 * in case live range reordering is allowed.
665 * We compute the actual live ranges and the corresponding order
668 * The independences are removed from the flow dependences
669 * (provided the source is not a must-write) as well as
670 * from the external false dependences (by compute_forced_dependences).
672 static void compute_live_range_reordering_dependences(struct ppcg_scop
*ps
)
674 compute_tagged_flow_dep_only(ps
);
675 remove_independences_from_tagged_flow(ps
);
676 derive_flow_dep_from_tagged_flow_dep(ps
);
677 compute_order_dependences(ps
);
678 compute_forced_dependences(ps
);
681 /* Compute the potential flow dependences and the potential live in
684 static void compute_flow_dep(struct ppcg_scop
*ps
)
686 isl_union_access_info
*access
;
687 isl_union_flow
*flow
;
689 access
= isl_union_access_info_from_sink(isl_union_map_copy(ps
->reads
));
690 access
= isl_union_access_info_set_must_source(access
,
691 isl_union_map_copy(ps
->must_writes
));
692 access
= isl_union_access_info_set_may_source(access
,
693 isl_union_map_copy(ps
->may_writes
));
694 access
= isl_union_access_info_set_schedule(access
,
695 isl_schedule_copy(ps
->schedule
));
696 flow
= isl_union_access_info_compute_flow(access
);
698 ps
->dep_flow
= isl_union_flow_get_may_dependence(flow
);
699 ps
->live_in
= isl_union_flow_get_may_no_source(flow
);
700 isl_union_flow_free(flow
);
703 /* Compute the dependences of the program represented by "scop".
704 * Store the computed potential flow dependences
705 * in scop->dep_flow and the reads with potentially no corresponding writes in
707 * Store the potential live out accesses in scop->live_out.
708 * Store the potential false (anti and output) dependences in scop->dep_false.
710 * If live range reordering is allowed, then we compute a separate
711 * set of order dependences and a set of external false dependences
712 * in compute_live_range_reordering_dependences.
714 static void compute_dependences(struct ppcg_scop
*scop
)
716 isl_union_map
*may_source
;
717 isl_union_access_info
*access
;
718 isl_union_flow
*flow
;
723 compute_live_out(scop
);
725 if (scop
->options
->live_range_reordering
)
726 compute_live_range_reordering_dependences(scop
);
727 else if (scop
->options
->target
!= PPCG_TARGET_C
)
728 compute_tagged_flow_dep(scop
);
730 compute_flow_dep(scop
);
732 may_source
= isl_union_map_union(isl_union_map_copy(scop
->may_writes
),
733 isl_union_map_copy(scop
->reads
));
734 access
= isl_union_access_info_from_sink(
735 isl_union_map_copy(scop
->may_writes
));
736 access
= isl_union_access_info_set_must_source(access
,
737 isl_union_map_copy(scop
->must_writes
));
738 access
= isl_union_access_info_set_may_source(access
, may_source
);
739 access
= isl_union_access_info_set_schedule(access
,
740 isl_schedule_copy(scop
->schedule
));
741 flow
= isl_union_access_info_compute_flow(access
);
743 scop
->dep_false
= isl_union_flow_get_may_dependence(flow
);
744 scop
->dep_false
= isl_union_map_coalesce(scop
->dep_false
);
745 isl_union_flow_free(flow
);
748 /* Eliminate dead code from ps->domain.
750 * In particular, intersect both ps->domain and the domain of
751 * ps->schedule with the (parts of) iteration
752 * domains that are needed to produce the output or for statement
753 * iterations that call functions.
754 * Also intersect the range of the dataflow dependences with
755 * this domain such that the removed instances will no longer
756 * be considered as targets of dataflow.
758 * We start with the iteration domains that call functions
759 * and the set of iterations that last write to an array
760 * (except those that are later killed).
762 * Then we add those statement iterations that produce
763 * something needed by the "live" statements iterations.
764 * We keep doing this until no more statement iterations can be added.
765 * To ensure that the procedure terminates, we compute the affine
766 * hull of the live iterations (bounded to the original iteration
767 * domains) each time we have added extra iterations.
769 static void eliminate_dead_code(struct ppcg_scop
*ps
)
773 isl_union_pw_multi_aff
*tagger
;
775 live
= isl_union_map_domain(isl_union_map_copy(ps
->live_out
));
776 if (!isl_union_set_is_empty(ps
->call
)) {
777 live
= isl_union_set_union(live
, isl_union_set_copy(ps
->call
));
778 live
= isl_union_set_coalesce(live
);
781 dep
= isl_union_map_copy(ps
->dep_flow
);
782 dep
= isl_union_map_reverse(dep
);
785 isl_union_set
*extra
;
787 extra
= isl_union_set_apply(isl_union_set_copy(live
),
788 isl_union_map_copy(dep
));
789 if (isl_union_set_is_subset(extra
, live
)) {
790 isl_union_set_free(extra
);
794 live
= isl_union_set_union(live
, extra
);
795 live
= isl_union_set_affine_hull(live
);
796 live
= isl_union_set_intersect(live
,
797 isl_union_set_copy(ps
->domain
));
800 isl_union_map_free(dep
);
802 ps
->domain
= isl_union_set_intersect(ps
->domain
,
803 isl_union_set_copy(live
));
804 ps
->schedule
= isl_schedule_intersect_domain(ps
->schedule
,
805 isl_union_set_copy(live
));
806 ps
->dep_flow
= isl_union_map_intersect_range(ps
->dep_flow
,
807 isl_union_set_copy(live
));
808 tagger
= isl_union_pw_multi_aff_copy(ps
->tagger
);
809 live
= isl_union_set_preimage_union_pw_multi_aff(live
, tagger
);
810 ps
->tagged_dep_flow
= isl_union_map_intersect_range(ps
->tagged_dep_flow
,
814 /* Intersect "set" with the set described by "str", taking the NULL
815 * string to represent the universal set.
817 static __isl_give isl_set
*set_intersect_str(__isl_take isl_set
*set
,
826 ctx
= isl_set_get_ctx(set
);
827 set2
= isl_set_read_from_str(ctx
, str
);
828 set
= isl_set_intersect(set
, set2
);
833 static void *ppcg_scop_free(struct ppcg_scop
*ps
)
838 isl_set_free(ps
->context
);
839 isl_union_set_free(ps
->domain
);
840 isl_union_set_free(ps
->call
);
841 isl_union_map_free(ps
->tagged_reads
);
842 isl_union_map_free(ps
->reads
);
843 isl_union_map_free(ps
->live_in
);
844 isl_union_map_free(ps
->tagged_may_writes
);
845 isl_union_map_free(ps
->tagged_must_writes
);
846 isl_union_map_free(ps
->may_writes
);
847 isl_union_map_free(ps
->must_writes
);
848 isl_union_map_free(ps
->live_out
);
849 isl_union_map_free(ps
->tagged_must_kills
);
850 isl_union_map_free(ps
->must_kills
);
851 isl_union_map_free(ps
->tagged_dep_flow
);
852 isl_union_map_free(ps
->dep_flow
);
853 isl_union_map_free(ps
->dep_false
);
854 isl_union_map_free(ps
->dep_forced
);
855 isl_union_map_free(ps
->tagged_dep_order
);
856 isl_union_map_free(ps
->dep_order
);
857 isl_schedule_free(ps
->schedule
);
858 isl_union_pw_multi_aff_free(ps
->tagger
);
859 isl_union_map_free(ps
->independence
);
860 isl_id_to_ast_expr_free(ps
->names
);
867 /* Extract a ppcg_scop from a pet_scop.
869 * The constructed ppcg_scop refers to elements from the pet_scop
870 * so the pet_scop should not be freed before the ppcg_scop.
872 static struct ppcg_scop
*ppcg_scop_from_pet_scop(struct pet_scop
*scop
,
873 struct ppcg_options
*options
)
877 struct ppcg_scop
*ps
;
882 ctx
= isl_set_get_ctx(scop
->context
);
884 ps
= isl_calloc_type(ctx
, struct ppcg_scop
);
888 ps
->names
= collect_names(scop
);
889 ps
->options
= options
;
890 ps
->start
= pet_loc_get_start(scop
->loc
);
891 ps
->end
= pet_loc_get_end(scop
->loc
);
892 ps
->context
= isl_set_copy(scop
->context
);
893 ps
->context
= set_intersect_str(ps
->context
, options
->ctx
);
894 if (options
->non_negative_parameters
) {
895 isl_space
*space
= isl_set_get_space(ps
->context
);
896 isl_set
*nn
= isl_set_nat_universe(space
);
897 ps
->context
= isl_set_intersect(ps
->context
, nn
);
899 ps
->domain
= collect_non_kill_domains(scop
);
900 ps
->call
= collect_call_domains(scop
);
901 ps
->tagged_reads
= pet_scop_get_tagged_may_reads(scop
);
902 ps
->reads
= pet_scop_get_may_reads(scop
);
903 ps
->tagged_may_writes
= pet_scop_get_tagged_may_writes(scop
);
904 ps
->may_writes
= pet_scop_get_may_writes(scop
);
905 ps
->tagged_must_writes
= pet_scop_get_tagged_must_writes(scop
);
906 ps
->must_writes
= pet_scop_get_must_writes(scop
);
907 ps
->tagged_must_kills
= pet_scop_get_tagged_must_kills(scop
);
908 ps
->must_kills
= pet_scop_get_must_kills(scop
);
909 ps
->schedule
= isl_schedule_copy(scop
->schedule
);
911 ps
->independence
= isl_union_map_empty(isl_set_get_space(ps
->context
));
912 for (i
= 0; i
< scop
->n_independence
; ++i
)
913 ps
->independence
= isl_union_map_union(ps
->independence
,
914 isl_union_map_copy(scop
->independences
[i
]->filter
));
917 compute_dependences(ps
);
918 eliminate_dead_code(ps
);
920 if (!ps
->context
|| !ps
->domain
|| !ps
->call
|| !ps
->reads
||
921 !ps
->may_writes
|| !ps
->must_writes
|| !ps
->tagged_must_kills
||
922 !ps
->must_kills
|| !ps
->schedule
|| !ps
->independence
|| !ps
->names
)
923 return ppcg_scop_free(ps
);
928 /* Internal data structure for ppcg_transform.
930 struct ppcg_transform_data
{
931 struct ppcg_options
*options
;
932 __isl_give isl_printer
*(*transform
)(__isl_take isl_printer
*p
,
933 struct ppcg_scop
*scop
, void *user
);
937 /* Should we print the original code?
938 * That is, does "scop" involve any data dependent conditions or
939 * nested expressions that cannot be handled by pet_stmt_build_ast_exprs?
941 static int print_original(struct pet_scop
*scop
, struct ppcg_options
*options
)
943 if (!pet_scop_can_build_ast_exprs(scop
)) {
944 if (options
->debug
->verbose
)
945 fprintf(stdout
, "Printing original code because "
946 "some index expressions cannot currently "
951 if (pet_scop_has_data_dependent_conditions(scop
)) {
952 if (options
->debug
->verbose
)
953 fprintf(stdout
, "Printing original code because "
954 "input involves data dependent conditions\n");
961 /* Callback for pet_transform_C_source that transforms
962 * the given pet_scop to a ppcg_scop before calling the
963 * ppcg_transform callback.
965 * If "scop" contains any data dependent conditions or if we may
966 * not be able to print the transformed program, then just print
969 static __isl_give isl_printer
*transform(__isl_take isl_printer
*p
,
970 struct pet_scop
*scop
, void *user
)
972 struct ppcg_transform_data
*data
= user
;
973 struct ppcg_scop
*ps
;
975 if (print_original(scop
, data
->options
)) {
976 p
= pet_scop_print_original(scop
, p
);
981 scop
= pet_scop_align_params(scop
);
982 ps
= ppcg_scop_from_pet_scop(scop
, data
->options
);
984 p
= data
->transform(p
, ps
, data
->user
);
992 /* Transform the C source file "input" by rewriting each scop
993 * through a call to "transform".
994 * The transformed C code is written to "out".
996 * This is a wrapper around pet_transform_C_source that transforms
997 * the pet_scop to a ppcg_scop before calling "fn".
999 int ppcg_transform(isl_ctx
*ctx
, const char *input
, FILE *out
,
1000 struct ppcg_options
*options
,
1001 __isl_give isl_printer
*(*fn
)(__isl_take isl_printer
*p
,
1002 struct ppcg_scop
*scop
, void *user
), void *user
)
1004 struct ppcg_transform_data data
= { options
, fn
, user
};
1005 return pet_transform_C_source(ctx
, input
, out
, &transform
, &data
);
1008 /* Check consistency of options.
1010 * Return -1 on error.
1012 static int check_options(isl_ctx
*ctx
)
1014 struct options
*options
;
1016 options
= isl_ctx_peek_options(ctx
, &options_args
);
1018 isl_die(ctx
, isl_error_internal
,
1019 "unable to find options", return -1);
1021 if (options
->ppcg
->openmp
&&
1022 !isl_options_get_ast_build_atomic_upper_bound(ctx
))
1023 isl_die(ctx
, isl_error_invalid
,
1024 "OpenMP requires atomic bounds", return -1);
1029 int main(int argc
, char **argv
)
1033 struct options
*options
;
1035 options
= options_new_with_defaults();
1038 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
1039 ppcg_options_set_target_defaults(options
->ppcg
);
1040 isl_options_set_ast_build_detect_min_max(ctx
, 1);
1041 isl_options_set_ast_print_macro_once(ctx
, 1);
1042 isl_options_set_schedule_whole_component(ctx
, 0);
1043 isl_options_set_schedule_maximize_band_depth(ctx
, 1);
1044 isl_options_set_schedule_maximize_coincidence(ctx
, 1);
1045 pet_options_set_encapsulate_dynamic_control(ctx
, 1);
1046 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
1048 if (check_options(ctx
) < 0)
1050 else if (options
->ppcg
->target
== PPCG_TARGET_CUDA
)
1051 r
= generate_cuda(ctx
, options
->ppcg
, options
->input
);
1052 else if (options
->ppcg
->target
== PPCG_TARGET_OPENCL
)
1053 r
= generate_opencl(ctx
, options
->ppcg
, options
->input
,
1056 r
= generate_cpu(ctx
, options
->ppcg
, options
->input
,