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