2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
15 #include <isl/options.h>
16 #include <isl/schedule.h>
19 #include "ppcg_options.h"
24 struct isl_options
*isl
;
25 struct pet_options
*pet
;
26 struct ppcg_options
*ppcg
;
31 const char *ppcg_version(void);
32 static void print_version(void)
34 printf("%s", ppcg_version());
37 ISL_ARGS_START(struct options
, options_args
)
38 ISL_ARG_CHILD(struct options
, isl
, "isl", &isl_options_args
, "isl options")
39 ISL_ARG_CHILD(struct options
, pet
, "pet", &pet_options_args
, "pet options")
40 ISL_ARG_CHILD(struct options
, ppcg
, NULL
, &ppcg_options_args
, "ppcg options")
41 ISL_ARG_STR(struct options
, output
, 'o', NULL
,
42 "filename", NULL
, "output filename (c target)")
43 ISL_ARG_ARG(struct options
, input
, "input", NULL
)
44 ISL_ARG_VERSION(print_version
)
47 ISL_ARG_DEF(options
, struct options
, options_args
)
49 /* Is "stmt" a kill statement?
51 static int is_kill(struct pet_stmt
*stmt
)
53 if (stmt
->body
->type
!= pet_expr_unary
)
55 return stmt
->body
->op
== pet_op_kill
;
58 /* Is "stmt" not a kill statement?
60 static int is_not_kill(struct pet_stmt
*stmt
)
62 return !is_kill(stmt
);
65 /* Collect the iteration domains of the statements in "scop" that
68 static __isl_give isl_union_set
*collect_domains(struct pet_scop
*scop
,
69 int (*pred
)(struct pet_stmt
*stmt
))
73 isl_union_set
*domain
;
78 domain
= isl_union_set_empty(isl_set_get_space(scop
->context
));
80 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
81 struct pet_stmt
*stmt
= scop
->stmts
[i
];
85 domain_i
= isl_set_copy(scop
->stmts
[i
]->domain
);
86 domain
= isl_union_set_add_set(domain
, domain_i
);
92 /* Collect the iteration domains of the statements in "scop",
93 * skipping kill statements.
95 static __isl_give isl_union_set
*collect_non_kill_domains(struct pet_scop
*scop
)
97 return collect_domains(scop
, &is_not_kill
);
100 /* Does "expr" contain any call expressions?
102 static int expr_has_call(struct pet_expr
*expr
)
106 if (expr
->type
== pet_expr_call
)
109 for (i
= 0; i
< expr
->n_arg
; ++i
)
110 if (expr_has_call(expr
->args
[i
]))
116 /* Does "stmt" contain any call expressions?
118 static int has_call(struct pet_stmt
*stmt
)
120 return expr_has_call(stmt
->body
);
123 /* Collect the iteration domains of the statements in "scop"
124 * that contain a call expression.
126 static __isl_give isl_union_set
*collect_call_domains(struct pet_scop
*scop
)
128 return collect_domains(scop
, &has_call
);
131 /* Collect all kill accesses in "scop".
133 static __isl_give isl_union_map
*collect_kills(struct pet_scop
*scop
)
136 isl_union_map
*kills
;
141 kills
= isl_union_map_empty(isl_set_get_space(scop
->context
));
143 for (i
= 0; i
< scop
->n_stmt
; ++i
) {
144 struct pet_stmt
*stmt
= scop
->stmts
[i
];
149 kill_i
= isl_map_copy(stmt
->body
->args
[0]->acc
.access
);
150 kill_i
= isl_map_intersect_domain(kill_i
,
151 isl_set_copy(stmt
->domain
));
152 kills
= isl_union_map_add_map(kills
, kill_i
);
158 /* Compute the dependences of the program represented by "scop".
159 * Store the computed flow dependences
160 * in scop->dep_flow and the reads with no corresponding writes in
162 * Store the false (anti and output) dependences in scop->dep_false.
164 static void compute_dependences(struct ppcg_scop
*scop
)
166 isl_union_map
*empty
;
167 isl_union_map
*dep1
, *dep2
;
172 empty
= isl_union_map_empty(isl_union_set_get_space(scop
->domain
));
173 isl_union_map_compute_flow(isl_union_map_copy(scop
->reads
),
174 isl_union_map_copy(scop
->writes
), empty
,
175 isl_union_map_copy(scop
->schedule
),
176 &scop
->dep_flow
, NULL
, &scop
->live_in
, NULL
);
178 isl_union_map_compute_flow(isl_union_map_copy(scop
->writes
),
179 isl_union_map_copy(scop
->writes
),
180 isl_union_map_copy(scop
->reads
),
181 isl_union_map_copy(scop
->schedule
),
182 &dep1
, &dep2
, NULL
, NULL
);
184 scop
->dep_false
= isl_union_map_union(dep1
, dep2
);
185 scop
->dep_false
= isl_union_map_coalesce(scop
->dep_false
);
188 /* Eliminate dead code from ps->domain.
190 * In particular, intersect ps->domain with the (parts of) iteration
191 * domains that are needed to produce the output or for statement
192 * iterations that call functions.
194 * We start with the iteration domains that call functions
195 * and the set of iterations that last write to an array
196 * (except those that are later killed).
198 * Then we add those statement iterations that produce
199 * something needed by the "live" statements iterations.
200 * We keep doing this until no more statement iterations can be added.
201 * To ensure that the procedure terminates, we compute the affine
202 * hull of the live iterations (bounded to the original iteration
203 * domains) each time we have added extra iterations.
205 static void eliminate_dead_code(struct ppcg_scop
*ps
)
207 isl_union_map
*exposed
;
211 exposed
= isl_union_map_union(isl_union_map_copy(ps
->writes
),
212 isl_union_map_copy(ps
->kills
));
213 exposed
= isl_union_map_reverse(exposed
);
214 exposed
= isl_union_map_apply_range(exposed
,
215 isl_union_map_copy(ps
->schedule
));
216 exposed
= isl_union_map_lexmax(exposed
);
217 exposed
= isl_union_map_apply_range(exposed
,
218 isl_union_map_reverse(isl_union_map_copy(ps
->schedule
)));
220 live
= isl_union_map_range(exposed
);
221 live
= isl_union_set_union(live
, isl_union_set_copy(ps
->call
));
223 dep
= isl_union_map_copy(ps
->dep_flow
);
224 dep
= isl_union_map_reverse(dep
);
227 isl_union_set
*extra
;
229 extra
= isl_union_set_apply(isl_union_set_copy(live
),
230 isl_union_map_copy(dep
));
231 if (isl_union_set_is_subset(extra
, live
)) {
232 isl_union_set_free(extra
);
236 live
= isl_union_set_union(live
, extra
);
237 live
= isl_union_set_affine_hull(live
);
238 live
= isl_union_set_intersect(live
,
239 isl_union_set_copy(ps
->domain
));
242 isl_union_map_free(dep
);
244 ps
->domain
= isl_union_set_intersect(ps
->domain
, live
);
247 /* Extract a ppcg_scop from a pet_scop.
249 * The constructed ppcg_scop refers to elements from the pet_scop
250 * so the pet_scop should not be freed before the ppcg_scop.
252 static struct ppcg_scop
*ppcg_scop_from_pet_scop(struct pet_scop
*scop
)
255 struct ppcg_scop
*ps
;
260 ctx
= isl_set_get_ctx(scop
->context
);
262 ps
= isl_calloc_type(ctx
, struct ppcg_scop
);
266 ps
->context
= isl_set_copy(scop
->context
);
267 ps
->domain
= collect_non_kill_domains(scop
);
268 ps
->call
= collect_call_domains(scop
);
269 ps
->reads
= pet_scop_collect_reads(scop
);
270 ps
->writes
= pet_scop_collect_writes(scop
);
271 ps
->kills
= collect_kills(scop
);
272 ps
->schedule
= pet_scop_collect_schedule(scop
);
273 ps
->n_array
= scop
->n_array
;
274 ps
->arrays
= scop
->arrays
;
275 ps
->n_stmt
= scop
->n_stmt
;
276 ps
->stmts
= scop
->stmts
;
278 compute_dependences(ps
);
279 eliminate_dead_code(ps
);
284 static void ppcg_scop_free(struct ppcg_scop
*ps
)
289 isl_set_free(ps
->context
);
290 isl_union_set_free(ps
->domain
);
291 isl_union_set_free(ps
->call
);
292 isl_union_map_free(ps
->reads
);
293 isl_union_map_free(ps
->live_in
);
294 isl_union_map_free(ps
->writes
);
295 isl_union_map_free(ps
->kills
);
296 isl_union_map_free(ps
->dep_flow
);
297 isl_union_map_free(ps
->dep_false
);
298 isl_union_map_free(ps
->schedule
);
303 int main(int argc
, char **argv
)
307 struct options
*options
;
308 struct pet_scop
*scop
;
309 struct ppcg_scop
*ps
;
311 options
= options_new_with_defaults();
314 ctx
= isl_ctx_alloc_with_options(&options_args
, options
);
315 isl_options_set_schedule_outer_zero_distance(ctx
, 1);
316 argc
= options_parse(options
, argc
, argv
, ISL_ARG_ALL
);
318 scop
= pet_scop_extract_from_C_source(ctx
, options
->input
, NULL
);
319 scop
= pet_scop_align_params(scop
);
320 ps
= ppcg_scop_from_pet_scop(scop
);
322 if (options
->ppcg
->target
== PPCG_TARGET_CUDA
)
323 r
= generate_cuda(ctx
, ps
, options
->ppcg
, options
->input
);
325 r
= generate_cpu(ctx
, ps
, options
->ppcg
, options
->input
,