2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
16 #include <isl/options.h>
17 #include <isl/schedule.h>
18 #include <isl/ast_build.h>
19 #include <isl/schedule.h>
22 #include "ppcg_options.h"
27 struct isl_options
*isl
;
28 struct pet_options
*pet
;
29 struct ppcg_options
*ppcg
;
34 const char *ppcg_version(void);
35 static void print_version(void)
37 printf("%s", ppcg_version());
40 ISL_ARGS_START(struct options
, options_args
)
41 ISL_ARG_CHILD(struct options
, isl
, "isl", &isl_options_args
, "isl options")
42 ISL_ARG_CHILD(struct options
, pet
, "pet", &pet_options_args
, "pet options")
43 ISL_ARG_CHILD(struct options
, ppcg
, NULL
, &ppcg_options_args
, "ppcg options")
44 ISL_ARG_STR(struct options
, output
, 'o', NULL
,
45 "filename", NULL
, "output filename (c target)")
46 ISL_ARG_ARG(struct options
, input
, "input", NULL
)
47 ISL_ARG_VERSION(print_version
)
50 ISL_ARG_DEF(options
, struct options
, options_args
)
52 /* Is "stmt" a kill statement?
54 static int is_kill(struct pet_stmt
*stmt
)
56 if (stmt
->body
->type
!= pet_expr_unary
)
58 return stmt
->body
->op
== pet_op_kill
;
61 /* Is "stmt" not a kill statement?
63 static int is_not_kill(struct pet_stmt
*stmt
)
65 return !is_kill(stmt
);
68 /* Collect the iteration domains of the statements in "scop" that
71 static __isl_give isl_union_set
*collect_domains(struct pet_scop
*scop
,
72 int (*pred
)(struct pet_stmt
*stmt
))
76 isl_union_set
*domain
;
81 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
83 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
84 struct pet_stmt
*stmt
= scop
->stmts
[i
];
90 isl_die(isl_union_set_get_ctx(domain
),
91 isl_error_unsupported
,
92 "data dependent conditions not supported",
93 return isl_union_set_free(domain
));
95 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
96 domain
= isl_union_set_add_set(domain
, domain_i
);
102 /* Collect the iteration domains of the statements in "scop",
103 * skipping kill statements.
105 static __isl_give isl_union_set
*collect_non_kill_domains(struct pet_scop
*scop
)
107 return collect_domains(scop
, &is_not_kill
);
110 /* Does "expr" contain any call expressions?
112 static int expr_has_call(struct pet_expr
*expr
)
116 if (expr
->type
== pet_expr_call
)
119 for (i
= 0; i
< expr
->n_arg
; ++i
)
120 if (expr_has_call(expr
->args
[i
]))
126 /* Does "stmt" contain any call expressions?
128 static int has_call(struct pet_stmt
*stmt
)
130 return expr_has_call(stmt
->body
);
133 /* Collect the iteration domains of the statements in "scop"
134 * that contain a call expression.
136 static __isl_give isl_union_set
*collect_call_domains(struct pet_scop
*scop
)
138 return collect_domains(scop
, &has_call
);
141 /* Collect all kill accesses in "scop".
143 static __isl_give isl_union_map
*collect_kills(struct pet_scop
*scop
)
146 isl_union_map
*kills
;
151 kills
= isl_union_map_empty(isl_set_get_space(scop
->context
));
153 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
154 struct pet_stmt
*stmt
= scop
->stmts
[i
];
159 kill_i
= isl_map_copy(stmt
->body
->args
[0]->acc
.access
);
160 kill_i
= isl_map_intersect_domain(kill_i
,
161 isl_set_copy(stmt
->domain
));
162 kills
= isl_union_map_add_map(kills
, kill_i
);
168 /* Compute the dependences of the program represented by "scop".
169 * Store the computed flow dependences
170 * in scop->dep_flow and the reads with no corresponding writes in
172 * Store the false (anti and output) dependences in scop->dep_false.
174 static void compute_dependences(struct ppcg_scop
*scop
)
176 isl_union_map
*empty
;
177 isl_union_map
*dep1
, *dep2
;
182 empty
= isl_union_map_empty(isl_union_set_get_space(scop
->domain
));
183 isl_union_map_compute_flow(isl_union_map_copy(scop
->reads
),
184 isl_union_map_copy(scop
->writes
), empty
,
185 isl_union_map_copy(scop
->schedule
),
186 &scop
->dep_flow
, NULL
, &scop
->live_in
, NULL
);
188 isl_union_map_compute_flow(isl_union_map_copy(scop
->writes
),
189 isl_union_map_copy(scop
->writes
),
190 isl_union_map_copy(scop
->reads
),
191 isl_union_map_copy(scop
->schedule
),
192 &dep1
, &dep2
, NULL
, NULL
);
194 scop
->dep_false
= isl_union_map_union(dep1
, dep2
);
195 scop
->dep_false
= isl_union_map_coalesce(scop
->dep_false
);
198 /* Eliminate dead code from ps->domain.
200 * In particular, intersect ps->domain with the (parts of) iteration
201 * domains that are needed to produce the output or for statement
202 * iterations that call functions.
204 * We start with the iteration domains that call functions
205 * and the set of iterations that last write to an array
206 * (except those that are later killed).
208 * Then we add those statement iterations that produce
209 * something needed by the "live" statements iterations.
210 * We keep doing this until no more statement iterations can be added.
211 * To ensure that the procedure terminates, we compute the affine
212 * hull of the live iterations (bounded to the original iteration
213 * domains) each time we have added extra iterations.
215 static void eliminate_dead_code(struct ppcg_scop
*ps
)
217 isl_union_map
*exposed
;
221 exposed
= isl_union_map_union(isl_union_map_copy(ps
->writes
),
222 isl_union_map_copy(ps
->kills
));
223 exposed
= isl_union_map_reverse(exposed
);
224 exposed
= isl_union_map_apply_range(exposed
,
225 isl_union_map_copy(ps
->schedule
));
226 exposed
= isl_union_map_lexmax(exposed
);
227 exposed
= isl_union_map_apply_range(exposed
,
228 isl_union_map_reverse(isl_union_map_copy(ps
->schedule
)));
230 live
= isl_union_map_range(exposed
);
231 if (!isl_union_set_is_empty(ps
->call
)) {
232 live
= isl_union_set_union(live
, isl_union_set_copy(ps
->call
));
233 live
= isl_union_set_coalesce(live
);
236 dep
= isl_union_map_copy(ps
->dep_flow
);
237 dep
= isl_union_map_reverse(dep
);
240 isl_union_set
*extra
;
242 extra
= isl_union_set_apply(isl_union_set_copy(live
),
243 isl_union_map_copy(dep
));
244 if (isl_union_set_is_subset(extra
, live
)) {
245 isl_union_set_free(extra
);
249 live
= isl_union_set_union(live
, extra
);
250 live
= isl_union_set_affine_hull(live
);
251 live
= isl_union_set_intersect(live
,
252 isl_union_set_copy(ps
->domain
));
255 isl_union_map_free(dep
);
257 ps
->domain
= isl_union_set_intersect(ps
->domain
, live
);
260 /* Intersect "set" with the set described by "str", taking the NULL
261 * string to represent the universal set.
263 static __isl_give isl_set
*set_intersect_str(__isl_take isl_set
*set
,
272 ctx
= isl_set_get_ctx(set
);
273 set2
= isl_set_read_from_str(ctx
, str
);
274 set
= isl_set_intersect(set
, set2
);
279 /* Does "expr" involve any data dependent accesses?
281 static int expr_has_data_dependent_accesses(struct pet_expr
*expr
)
285 for (i
= 0; i
< expr
->n_arg
; ++i
)
286 if (expr_has_data_dependent_accesses(expr
->args
[i
]))
289 if (expr
->type
== pet_expr_access
&& expr
->n_arg
> 0)
295 /* Does "stmt" contain any data dependent accesses?
297 static int stmt_has_data_dependent_accesses(struct pet_stmt
*stmt
)
299 return expr_has_data_dependent_accesses(stmt
->body
);
302 /* Does "scop" contain any data dependent accesses?
304 static int scop_has_data_dependent_accesses(struct pet_scop
*scop
)
310 for (i
= 0; i
< scop
->n_stmt
; ++i
)
311 if (stmt_has_data_dependent_accesses(scop
->stmts
[i
]))
317 static void *ppcg_scop_free(struct ppcg_scop
*ps
)
322 isl_set_free(ps
->context
);
323 isl_union_set_free(ps
->domain
);
324 isl_union_set_free(ps
->call
);
325 isl_union_map_free(ps
->reads
);
326 isl_union_map_free(ps
->live_in
);
327 isl_union_map_free(ps
->writes
);
328 isl_union_map_free(ps
->kills
);
329 isl_union_map_free(ps
->dep_flow
);
330 isl_union_map_free(ps
->dep_false
);
331 isl_union_map_free(ps
->schedule
);
338 /* Extract a ppcg_scop from a pet_scop.
340 * The constructed ppcg_scop refers to elements from the pet_scop
341 * so the pet_scop should not be freed before the ppcg_scop.
343 static struct ppcg_scop
*ppcg_scop_from_pet_scop(struct pet_scop
*scop
,
344 struct ppcg_options
*options
)
347 struct ppcg_scop
*ps
;
352 ctx
= isl_set_get_ctx(scop
->context
);
354 if (scop_has_data_dependent_accesses(scop
))
355 isl_die(ctx
, isl_error_unsupported
,
356 "data dependent accesses not supported",
359 ps
= isl_calloc_type(ctx
, struct ppcg_scop
);
363 ps
->start
= scop
->start
;
365 ps
->context
= isl_set_copy(scop
->context
);
366 ps
->context
= set_intersect_str(ps
->context
, options
->ctx
);
367 ps
->domain
= collect_non_kill_domains(scop
);
368 ps
->call
= collect_call_domains(scop
);
369 ps
->reads
= pet_scop_collect_reads(scop
);
370 ps
->writes
= pet_scop_collect_writes(scop
);
371 ps
->kills
= collect_kills(scop
);
372 ps
->schedule
= pet_scop_collect_schedule(scop
);
373 ps
->n_array
= scop
->n_array
;
374 ps
->arrays
= scop
->arrays
;
375 ps
->n_stmt
= scop
->n_stmt
;
376 ps
->stmts
= scop
->stmts
;
378 compute_dependences(ps
);
379 eliminate_dead_code(ps
);
381 if (!ps
->context
|| !ps
->domain
|| !ps
->call
|| !ps
->reads
||
382 !ps
->writes
|| !ps
->kills
|| !ps
->schedule
)
383 return ppcg_scop_free(ps
);
388 /* Check consistency of options.
390 * Return -1 on error.
392 static int check_options(isl_ctx
*ctx
)
394 struct options
*options
;
396 options
= isl_ctx_peek_options(ctx
, &options_args
);
398 isl_die(ctx
, isl_error_internal
,
399 "unable to find options", return -1);
401 if (options
->ppcg
->openmp
&&
402 !isl_options_get_ast_build_atomic_upper_bound(ctx
))
403 isl_die(ctx
, isl_error_invalid
,
404 "OpenMP requires atomic bounds", return -1);
409 /* Extract a model from the input file, transform the model and
410 * write out the result to the output file(s).
412 static int transform(isl_ctx
*ctx
)
415 struct pet_scop
*scop
;
416 struct ppcg_scop
*ps
;
417 struct options
*options
;
419 options
= isl_ctx_peek_options(ctx
, &options_args
);
421 isl_die(ctx
, isl_error_internal
,
422 "unable to find options", return EXIT_FAILURE
);
424 scop
= pet_scop_extract_from_C_source(ctx
, options
->input
, NULL
);
425 scop
= pet_scop_align_params(scop
);
426 ps
= ppcg_scop_from_pet_scop(scop
, options
->ppcg
);
428 if (options
->ppcg
->target
== PPCG_TARGET_CUDA
)
429 r
= generate_cuda(ctx
, ps
, options
->ppcg
, options
->input
);
431 r
= generate_cpu(ctx
, ps
, options
->ppcg
, options
->input
,
440 int main(int argc
, char **argv
)
444 struct options
*options
;
446 options
= options_new_with_defaults();
449 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
450 isl_options_set_schedule_outer_zero_distance(ctx
, 1);
451 isl_options_set_schedule_maximize_band_depth(ctx
, 1);
452 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
454 if (check_options(ctx
) < 0)