print more understandable error message in case of unbounded arrays
[ppcg.git] / ppcg.c
Commit [+]AuthorDateLineData
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +02001/*
2 * Copyright 2011 INRIA Saclay
07563074 Sven Verdoolaege2013-08-22 10:23:33 +02003 * Copyright 2013 Ecole Normale Superieure
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +02004 *
2fa5ab39 Sven Verdoolaege2013-07-24 11:48:28 +02005 * Use of this software is governed by the MIT license
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +02006 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
07563074 Sven Verdoolaege2013-08-22 10:23:33 +020010 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +020011 */
12
13#include <assert.h>
14#include <stdio.h>
bcb2edca Sven Verdoolaege2013-01-02 17:47:36 +010015#include <stdlib.h>
816e0351 Sven Verdoolaege2013-07-08 11:12:31 +020016#include <string.h>
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020017#include <isl/ctx.h>
dea8e27a Sven Verdoolaege2012-11-09 13:51:46 +010018#include <isl/flow.h>
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020019#include <isl/options.h>
5c4963d4 Sven Verdoolaege2011-11-13 17:25:18 +010020#include <isl/schedule.h>
1a3f57a7 Riyadh Baghdadi2012-11-22 02:29:42 +010021#include <isl/ast_build.h>
af7f6c30 Sven Verdoolaege2012-03-26 17:58:33 +020022#include <isl/schedule.h>
7ba7fe1a Sven Verdoolaege2011-07-10 18:11:52 +020023#include <pet.h>
8c4af29e Sven Verdoolaege2012-10-16 20:22:01 +020024#include "ppcg.h"
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020025#include "ppcg_options.h"
fa06bb71 Sven Verdoolaege2012-08-03 10:02:04 +020026#include "cuda.h"
1b7331de Tobias Grosser2012-03-16 17:14:44 +010027#include "cpu.h"
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +020028
29struct options {
30 struct isl_options *isl;
10f86770 Sven Verdoolaege2011-11-14 11:21:07 +010031 struct pet_options *pet;
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +020032 struct ppcg_options *ppcg;
33 char *input;
e36b4e1d Sven Verdoolaege2012-11-15 13:19:55 +010034 char *output;
9f18b065
SV
Sven Verdoolaege2011-06-21 17:40:50 +020035};
36
ff7bd0dd
SV
Sven Verdoolaege2012-09-13 17:04:55 +020037const char *ppcg_version(void);
38static void print_version(void)
39{
40 printf("%s", ppcg_version());
41}
42
8dc11600
SV
Sven Verdoolaege2011-11-11 21:26:21 +010043ISL_ARGS_START(struct options, options_args)
44ISL_ARG_CHILD(struct options, isl, "isl", &isl_options_args, "isl options")
10f86770 Sven Verdoolaege2011-11-14 11:21:07 +010045ISL_ARG_CHILD(struct options, pet, "pet", &pet_options_args, "pet options")
49244a45 Tobias Grosser2012-03-01 13:57:24 +010046ISL_ARG_CHILD(struct options, ppcg, NULL, &ppcg_options_args, "ppcg options")
e36b4e1d
SV
Sven Verdoolaege2012-11-15 13:19:55 +010047ISL_ARG_STR(struct options, output, 'o', NULL,
48 "filename", NULL, "output filename (c target)")
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020049ISL_ARG_ARG(struct options, input, "input", NULL)
ff7bd0dd Sven Verdoolaege2012-09-13 17:04:55 +020050ISL_ARG_VERSION(print_version)
8dc11600 Sven Verdoolaege2011-11-11 21:26:21 +010051ISL_ARGS_END
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020052
8dc11600 Sven Verdoolaege2011-11-11 21:26:21 +010053ISL_ARG_DEF(options, struct options, options_args)
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +020054
816e0351
SV
Sven Verdoolaege2013-07-08 11:12:31 +020055/* Copy the base name of "input" to "name" and return its length.
56 * "name" is not NULL terminated.
57 *
58 * In particular, remove all leading directory components and
59 * the final extension, if any.
60 */
61int ppcg_extract_base_name(char *name, const char *input)
62{
63 const char *base;
64 const char *ext;
65 int len;
66
67 base = strrchr(input, '/');
68 if (base)
69 base++;
70 else
71 base = input;
72 ext = strrchr(base, '.');
73 len = ext ? ext - base : strlen(base);
74
75 memcpy(name, base, len);
76
77 return len;
78}
79
62b08530
SV
Sven Verdoolaege2012-10-16 10:14:45 +020080/* Is "stmt" a kill statement?
81 */
82static int is_kill(struct pet_stmt *stmt)
83{
84 if (stmt->body->type != pet_expr_unary)
85 return 0;
86 return stmt->body->op == pet_op_kill;
87}
88
89/* Is "stmt" not a kill statement?
90 */
91static int is_not_kill(struct pet_stmt *stmt)
92{
93 return !is_kill(stmt);
94}
95
96/* Collect the iteration domains of the statements in "scop" that
97 * satisfy "pred".
98 */
99static __isl_give isl_union_set *collect_domains(struct pet_scop *scop,
100 int (*pred)(struct pet_stmt *stmt))
101{
102 int i;
103 isl_set *domain_i;
104 isl_union_set *domain;
105
106 if (!scop)
107 return NULL;
108
109 domain = isl_union_set_empty(isl_set_get_space(scop->context));
110
111 for (i = 0; i < scop->n_stmt; ++i) {
112 struct pet_stmt *stmt = scop->stmts[i];
113
114 if (!pred(stmt))
115 continue;
d0ebae26
SV
Sven Verdoolaege2013-07-25 11:22:08 +0200116
117 if (stmt->n_arg > 0)
118 isl_die(isl_union_set_get_ctx(domain),
119 isl_error_unsupported,
120 "data dependent conditions not supported",
121 return isl_union_set_free(domain));
122
62b08530
SV
Sven Verdoolaege2012-10-16 10:14:45 +0200123 domain_i = isl_set_copy(scop->stmts[i]->domain);
124 domain = isl_union_set_add_set(domain, domain_i);
125 }
126
127 return domain;
128}
129
130/* Collect the iteration domains of the statements in "scop",
131 * skipping kill statements.
132 */
133static __isl_give isl_union_set *collect_non_kill_domains(struct pet_scop *scop)
134{
135 return collect_domains(scop, &is_not_kill);
136}
137
8b2a4f27
SV
Sven Verdoolaege2012-11-10 15:01:02 +0100138/* Does "expr" contain any call expressions?
139 */
140static int expr_has_call(struct pet_expr *expr)
141{
142 int i;
143
144 if (expr->type == pet_expr_call)
145 return 1;
146
147 for (i = 0; i < expr->n_arg; ++i)
148 if (expr_has_call(expr->args[i]))
149 return 1;
150
151 return 0;
152}
153
154/* Does "stmt" contain any call expressions?
155 */
156static int has_call(struct pet_stmt *stmt)
157{
158 return expr_has_call(stmt->body);
159}
160
161/* Collect the iteration domains of the statements in "scop"
162 * that contain a call expression.
163 */
164static __isl_give isl_union_set *collect_call_domains(struct pet_scop *scop)
165{
166 return collect_domains(scop, &has_call);
167}
168
c27d9a37
SV
Sven Verdoolaege2013-02-22 16:53:08 +0100169/* Given a union of "tagged" access relations of the form
170 *
171 * [S_i[...] -> R_j[]] -> A_k[...]
172 *
173 * project out the "tags" (R_j[]).
174 * That is, return a union of relations of the form
175 *
176 * S_i[...] -> A_k[...]
177 */
178static __isl_give isl_union_map *project_out_tags(
179 __isl_take isl_union_map *umap)
180{
181 isl_union_map *proj;
182
183 proj = isl_union_map_universe(isl_union_map_copy(umap));
184 proj = isl_union_set_unwrap(isl_union_map_domain(proj));
185 proj = isl_union_map_domain_map(proj);
186
187 umap = isl_union_map_apply_domain(umap, proj);
188
189 return umap;
190}
191
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200192/* Construct a relation from the iteration domains to tagged iteration
193 * domains with as range the reference tags that appear
194 * in any of the reads, writes or kills.
195 * Store the result in ps->tagger.
52222211 Sven Verdoolaege2013-02-22 17:08:09 +0100196 *
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200197 * For example, if the statement with iteration space S[i,j]
198 * contains two array references R_1[] and R_2[], then ps->tagger will contain
199 *
200 * { S[i,j] -> [S[i,j] -> R_1[]]; S[i,j] -> [S[i,j] -> R_2[]] }
201 */
202static void compute_tagger(struct ppcg_scop *ps)
203{
204 isl_union_map *tagged, *tagger;
205
206 tagged = isl_union_map_copy(ps->tagged_reads);
207 tagged = isl_union_map_union(tagged,
208 isl_union_map_copy(ps->tagged_may_writes));
209 tagged = isl_union_map_union(tagged,
210 isl_union_map_copy(ps->tagged_must_kills));
211
212 tagger = isl_union_map_universe(tagged);
213 tagger = isl_union_set_unwrap(isl_union_map_domain(tagger));
214 tagger = isl_union_map_reverse(isl_union_map_domain_map(tagger));
215
216 ps->tagger = tagger;
217}
218
219/* Compute the live out accesses, i.e., the writes that are
220 * potentially not killed by any kills or any other writes, and
221 * store them in ps->live_out.
222 *
223 * We compute the "dependence" of any "kill" (an explicit kill
224 * or a must write) on any may write.
225 * The may writes with a "depending" kill are definitely killed.
226 * The remaining may writes can potentially be live out.
52222211
SV
Sven Verdoolaege2013-02-22 17:08:09 +0100227 */
228static void compute_live_out(struct ppcg_scop *ps)
229{
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200230 isl_union_map *tagger;
231 isl_union_map *schedule;
232 isl_union_map *empty;
233 isl_union_map *kills;
52222211 Sven Verdoolaege2013-02-22 17:08:09 +0100234 isl_union_map *exposed;
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200235 isl_union_map *covering;
52222211 Sven Verdoolaege2013-02-22 17:08:09 +0100236
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200237 tagger = isl_union_map_copy(ps->tagger);
238 schedule = isl_union_map_copy(ps->schedule);
239 schedule = isl_union_map_apply_domain(schedule,
240 isl_union_map_copy(tagger));
241 empty = isl_union_map_empty(isl_union_set_get_space(ps->domain));
242 kills = isl_union_map_union(isl_union_map_copy(ps->tagged_must_writes),
243 isl_union_map_copy(ps->tagged_must_kills));
244 isl_union_map_compute_flow(kills, empty,
245 isl_union_map_copy(ps->tagged_may_writes),
246 schedule, NULL, &covering, NULL, NULL);
247 exposed = isl_union_map_copy(ps->tagged_may_writes);
248 exposed = isl_union_map_subtract_domain(exposed,
249 isl_union_map_domain(covering));
250 exposed = isl_union_map_apply_range(tagger, exposed);
52222211
SV
Sven Verdoolaege2013-02-22 17:08:09 +0100251 ps->live_out = exposed;
252}
253
c27d9a37
SV
Sven Verdoolaege2013-02-22 16:53:08 +0100254/* Compute the flow dependences and the live_in accesses and store
255 * the results in ps->dep_flow and ps->live_in.
256 * A copy of the flow dependences, tagged with the reference tags
257 * is stored in ps->tagged_dep_flow.
258 *
259 * We first compute ps->tagged_dep_flow, i.e., the tagged flow dependences
260 * and then project out the tags.
261 */
262static void compute_tagged_flow_dep(struct ppcg_scop *ps)
263{
264 isl_union_map *tagger;
265 isl_union_map *schedule;
266 isl_union_map *may_flow;
267 isl_union_map *live_in, *may_live_in;
268
269 tagger = isl_union_map_copy(ps->tagger);
270 schedule = isl_union_map_copy(ps->schedule);
271 schedule = isl_union_map_apply_domain(schedule, tagger);
272 isl_union_map_compute_flow(isl_union_map_copy(ps->tagged_reads),
273 isl_union_map_copy(ps->tagged_must_writes),
274 isl_union_map_copy(ps->tagged_may_writes),
275 schedule, &ps->tagged_dep_flow, &may_flow,
276 &live_in, &may_live_in);
277 ps->tagged_dep_flow = isl_union_map_union(ps->tagged_dep_flow,
278 may_flow);
279 ps->dep_flow = isl_union_map_copy(ps->tagged_dep_flow);
280 ps->dep_flow = isl_union_map_zip(ps->dep_flow);
281 ps->dep_flow = isl_union_set_unwrap(isl_union_map_domain(ps->dep_flow));
282 live_in = isl_union_map_union(live_in, may_live_in);
283 ps->live_in = project_out_tags(live_in);
284}
285
bc47e699
SV
Sven Verdoolaege2012-11-14 16:38:21 +0100286/* Compute the order dependences that prevent the potential live ranges
287 * from overlapping.
288 * "before" contains all pairs of statement iterations where
289 * the first is executed before the second according to the original schedule.
290 *
291 * In particular, construct a union of relations
292 *
293 * [R[...] -> R_1[]] -> [W[...] -> R_2[]]
294 *
295 * where [R[...] -> R_1[]] is the range of one or more live ranges
296 * (i.e., a read) and [W[...] -> R_2[]] is the domain of one or more
297 * live ranges (i.e., a write). Moreover, the read and the write
298 * access the same memory element and the read occurs before the write
299 * in the original schedule.
300 * The scheduler allows some of these dependences to be violated, provided
301 * the adjacent live ranges are all local (i.e., their domain and range
302 * are mapped to the same point by the current schedule band).
303 *
304 * Note that if a live range is not local, then we need to make
305 * sure it does not overlap with _any_ other live range, and not
306 * just with the "previous" and/or the "next" live range.
307 * We therefore add order dependences between reads and
308 * _any_ later potential write.
309 *
310 * We also need to be careful about writes without a corresponding read.
311 * They are already prevented from moving past non-local preceding
312 * intervals, but we also need to prevent them from moving past non-local
313 * following intervals. We therefore also add order dependences from
314 * potential writes that do not appear in any intervals
315 * to all later potential writes.
316 * Note that dead code elimination should have removed most of these
317 * dead writes, but the dead code elimination may not remove all dead writes,
318 * so we need to consider them to be safe.
319 */
320static void compute_order_dependences(struct ppcg_scop *ps,
321 __isl_take isl_union_map *before)
322{
323 isl_union_map *reads;
324 isl_union_map *shared_access;
325 isl_union_set *matched;
326 isl_union_map *unmatched;
327 isl_union_set *domain;
328
329 reads = isl_union_map_copy(ps->tagged_reads);
330 matched = isl_union_map_domain(isl_union_map_copy(ps->tagged_dep_flow));
331 unmatched = isl_union_map_copy(ps->tagged_may_writes);
332 unmatched = isl_union_map_subtract_domain(unmatched, matched);
333 reads = isl_union_map_union(reads, unmatched);
334 shared_access = isl_union_map_copy(ps->tagged_may_writes);
335 shared_access = isl_union_map_reverse(shared_access);
336 shared_access = isl_union_map_apply_range(reads, shared_access);
337 shared_access = isl_union_map_zip(shared_access);
338 shared_access = isl_union_map_intersect_domain(shared_access,
339 isl_union_map_wrap(before));
340 domain = isl_union_map_domain(isl_union_map_copy(shared_access));
341 shared_access = isl_union_map_zip(shared_access);
342 ps->dep_order = isl_union_set_unwrap(domain);
343 ps->tagged_dep_order = shared_access;
344}
345
346/* Compute the external false dependences of the program represented by "scop"
347 * in case live range reordering is allowed.
348 * "before" contains all pairs of statement iterations where
349 * the first is executed before the second according to the original schedule.
350 *
351 * The anti-dependences are already taken care of by the order dependences.
352 * The external false dependences are only used to ensure that live-in and
353 * live-out data is not overwritten by any writes inside the scop.
354 *
355 * In particular, the reads from live-in data need to precede any
356 * later write to the same memory element.
357 * As to live-out data, the last writes need to remain the last writes.
358 * That is, any earlier write in the original schedule needs to precede
359 * the last write to the same memory element in the computed schedule.
360 * The possible last writes have been computed by compute_live_out.
361 * They may include kills, but if the last access is a kill,
362 * then the corresponding dependences will effectively be ignored
363 * since we do not schedule any kill statements.
364 *
365 * Note that the set of live-in and live-out accesses may be
366 * an overapproximation. There may therefore be potential writes
367 * before a live-in access and after a live-out access.
368 */
369static void compute_external_false_dependences(struct ppcg_scop *ps,
370 __isl_take isl_union_map *before)
371{
372 isl_union_map *shared_access;
373 isl_union_map *exposed;
374 isl_union_map *live_in;
375
376 exposed = isl_union_map_copy(ps->live_out);
377
378 exposed = isl_union_map_reverse(exposed);
379 shared_access = isl_union_map_copy(ps->may_writes);
380 shared_access = isl_union_map_apply_range(shared_access, exposed);
381
382 ps->dep_external = shared_access;
383
384 live_in = isl_union_map_apply_range(isl_union_map_copy(ps->live_in),
385 isl_union_map_reverse(isl_union_map_copy(ps->may_writes)));
386
387 ps->dep_external = isl_union_map_union(ps->dep_external, live_in);
388 ps->dep_external = isl_union_map_intersect(ps->dep_external, before);
389}
390
391/* Compute the dependences of the program represented by "scop"
392 * in case live range reordering is allowed.
393 *
394 * We compute the actual live ranges and the corresponding order
395 * false dependences.
396 */
397static void compute_live_range_reordering_dependences(struct ppcg_scop *ps)
398{
399 isl_union_map *before;
400
401 before = isl_union_map_lex_lt_union_map(
402 isl_union_map_copy(ps->schedule),
403 isl_union_map_copy(ps->schedule));
404
405 compute_tagged_flow_dep(ps);
406 compute_order_dependences(ps, isl_union_map_copy(before));
407 compute_external_false_dependences(ps, before);
408}
409
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200410/* Compute the potential flow dependences and the potential live in
411 * accesses.
cf1f8936
SV
Sven Verdoolaege2013-08-22 10:39:01 +0200412 */
413static void compute_flow_dep(struct ppcg_scop *ps)
414{
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200415 isl_union_map *may_flow;
416 isl_union_map *may_live_in;
cf1f8936 Sven Verdoolaege2013-08-22 10:39:01 +0200417
cf1f8936 Sven Verdoolaege2013-08-22 10:39:01 +0200418 isl_union_map_compute_flow(isl_union_map_copy(ps->reads),
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200419 isl_union_map_copy(ps->must_writes),
420 isl_union_map_copy(ps->may_writes),
cf1f8936 Sven Verdoolaege2013-08-22 10:39:01 +0200421 isl_union_map_copy(ps->schedule),
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200422 &ps->dep_flow, &may_flow,
423 &ps->live_in, &may_live_in);
424
425 ps->dep_flow = isl_union_map_union(ps->dep_flow, may_flow);
426 ps->live_in = isl_union_map_union(ps->live_in, may_live_in);
cf1f8936
SV
Sven Verdoolaege2013-08-22 10:39:01 +0200427}
428
bb5bb59d Sven Verdoolaege2012-11-14 11:06:53 +0100429/* Compute the dependences of the program represented by "scop".
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200430 * Store the computed potential flow dependences
431 * in scop->dep_flow and the reads with potentially no corresponding writes in
dea8e27a Sven Verdoolaege2012-11-09 13:51:46 +0100432 * scop->live_in.
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200433 * Store the potential live out accesses in scop->live_out.
434 * Store the potential false (anti and output) dependences in scop->dep_false.
bc47e699
SV
Sven Verdoolaege2012-11-14 16:38:21 +0100435 *
436 * If live range reordering is allowed, then we compute a separate
437 * set of order dependences and a set of external false dependences
438 * in compute_live_range_reordering_dependences.
dea8e27a
SV
Sven Verdoolaege2012-11-09 13:51:46 +0100439 */
440static void compute_dependences(struct ppcg_scop *scop)
441{
bb5bb59d Sven Verdoolaege2012-11-14 11:06:53 +0100442 isl_union_map *dep1, *dep2;
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200443 isl_union_map *may_source;
dea8e27a
SV
Sven Verdoolaege2012-11-09 13:51:46 +0100444
445 if (!scop)
446 return;
447
52222211
SV
Sven Verdoolaege2013-02-22 17:08:09 +0100448 compute_live_out(scop);
449
bc47e699
SV
Sven Verdoolaege2012-11-14 16:38:21 +0100450 if (scop->options->live_range_reordering)
451 compute_live_range_reordering_dependences(scop);
452 else if (scop->options->target != PPCG_TARGET_C)
c27d9a37
SV
Sven Verdoolaege2013-02-22 16:53:08 +0100453 compute_tagged_flow_dep(scop);
454 else
455 compute_flow_dep(scop);
bb5bb59d Sven Verdoolaege2012-11-14 11:06:53 +0100456
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200457 may_source = isl_union_map_union(isl_union_map_copy(scop->may_writes),
458 isl_union_map_copy(scop->reads));
459 isl_union_map_compute_flow(isl_union_map_copy(scop->may_writes),
460 isl_union_map_copy(scop->must_writes),
461 may_source, isl_union_map_copy(scop->schedule),
bb5bb59d
SV
Sven Verdoolaege2012-11-14 11:06:53 +0100462 &dep1, &dep2, NULL, NULL);
463
464 scop->dep_false = isl_union_map_union(dep1, dep2);
465 scop->dep_false = isl_union_map_coalesce(scop->dep_false);
dea8e27a
SV
Sven Verdoolaege2012-11-09 13:51:46 +0100466}
467
ceedeca3
SV
Sven Verdoolaege2012-04-15 14:42:55 +0200468/* Eliminate dead code from ps->domain.
469 *
470 * In particular, intersect ps->domain with the (parts of) iteration
471 * domains that are needed to produce the output or for statement
472 * iterations that call functions.
473 *
474 * We start with the iteration domains that call functions
475 * and the set of iterations that last write to an array
476 * (except those that are later killed).
477 *
478 * Then we add those statement iterations that produce
479 * something needed by the "live" statements iterations.
480 * We keep doing this until no more statement iterations can be added.
481 * To ensure that the procedure terminates, we compute the affine
482 * hull of the live iterations (bounded to the original iteration
483 * domains) each time we have added extra iterations.
484 */
485static void eliminate_dead_code(struct ppcg_scop *ps)
486{
ceedeca3
SV
Sven Verdoolaege2012-04-15 14:42:55 +0200487 isl_union_set *live;
488 isl_union_map *dep;
489
52222211 Sven Verdoolaege2013-02-22 17:08:09 +0100490 live = isl_union_map_domain(isl_union_map_copy(ps->live_out));
a9964d95
SV
Sven Verdoolaege2013-02-06 14:20:24 +0100491 if (!isl_union_set_is_empty(ps->call)) {
492 live = isl_union_set_union(live, isl_union_set_copy(ps->call));
493 live = isl_union_set_coalesce(live);
494 }
ceedeca3
SV
Sven Verdoolaege2012-04-15 14:42:55 +0200495
496 dep = isl_union_map_copy(ps->dep_flow);
497 dep = isl_union_map_reverse(dep);
498
499 for (;;) {
500 isl_union_set *extra;
501
502 extra = isl_union_set_apply(isl_union_set_copy(live),
503 isl_union_map_copy(dep));
504 if (isl_union_set_is_subset(extra, live)) {
505 isl_union_set_free(extra);
506 break;
507 }
508
509 live = isl_union_set_union(live, extra);
510 live = isl_union_set_affine_hull(live);
511 live = isl_union_set_intersect(live,
512 isl_union_set_copy(ps->domain));
513 }
514
515 isl_union_map_free(dep);
516
517 ps->domain = isl_union_set_intersect(ps->domain, live);
518}
519
987346fb
SV
Sven Verdoolaege2012-11-14 18:00:39 +0100520/* Intersect "set" with the set described by "str", taking the NULL
521 * string to represent the universal set.
522 */
523static __isl_give isl_set *set_intersect_str(__isl_take isl_set *set,
524 const char *str)
525{
526 isl_ctx *ctx;
527 isl_set *set2;
528
529 if (!str)
530 return set;
531
532 ctx = isl_set_get_ctx(set);
533 set2 = isl_set_read_from_str(ctx, str);
534 set = isl_set_intersect(set, set2);
535
536 return set;
537}
538
de49db13
SV
Sven Verdoolaege2013-07-01 18:44:23 +0200539/* Does "expr" involve any data dependent accesses?
540 */
541static int expr_has_data_dependent_accesses(struct pet_expr *expr)
542{
543 int i;
544
545 for (i = 0; i < expr->n_arg; ++i)
546 if (expr_has_data_dependent_accesses(expr->args[i]))
547 return 1;
548
549 if (expr->type == pet_expr_access && expr->n_arg > 0)
550 return 1;
551
552 return 0;
553}
554
555/* Does "stmt" contain any data dependent accesses?
556 */
557static int stmt_has_data_dependent_accesses(struct pet_stmt *stmt)
558{
559 return expr_has_data_dependent_accesses(stmt->body);
560}
561
562/* Does "scop" contain any data dependent accesses?
563 */
564static int scop_has_data_dependent_accesses(struct pet_scop *scop)
565{
566 int i;
567
568 if (!scop)
569 return -1;
570 for (i = 0; i < scop->n_stmt; ++i)
571 if (stmt_has_data_dependent_accesses(scop->stmts[i]))
572 return 1;
573
574 return 0;
575}
576
d0ebae26
SV
Sven Verdoolaege2013-07-25 11:22:08 +0200577static void *ppcg_scop_free(struct ppcg_scop *ps)
578{
579 if (!ps)
580 return NULL;
581
582 isl_set_free(ps->context);
583 isl_union_set_free(ps->domain);
584 isl_union_set_free(ps->call);
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200585 isl_union_map_free(ps->tagged_reads);
d0ebae26
SV
Sven Verdoolaege2013-07-25 11:22:08 +0200586 isl_union_map_free(ps->reads);
587 isl_union_map_free(ps->live_in);
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200588 isl_union_map_free(ps->tagged_may_writes);
589 isl_union_map_free(ps->tagged_must_writes);
590 isl_union_map_free(ps->may_writes);
591 isl_union_map_free(ps->must_writes);
52222211 Sven Verdoolaege2013-02-22 17:08:09 +0100592 isl_union_map_free(ps->live_out);
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200593 isl_union_map_free(ps->tagged_must_kills);
c27d9a37 Sven Verdoolaege2013-02-22 16:53:08 +0100594 isl_union_map_free(ps->tagged_dep_flow);
d0ebae26
SV
Sven Verdoolaege2013-07-25 11:22:08 +0200595 isl_union_map_free(ps->dep_flow);
596 isl_union_map_free(ps->dep_false);
bc47e699
SV
Sven Verdoolaege2012-11-14 16:38:21 +0100597 isl_union_map_free(ps->dep_external);
598 isl_union_map_free(ps->tagged_dep_order);
599 isl_union_map_free(ps->dep_order);
d0ebae26 Sven Verdoolaege2013-07-25 11:22:08 +0200600 isl_union_map_free(ps->schedule);
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200601 isl_union_map_free(ps->tagger);
d0ebae26
SV
Sven Verdoolaege2013-07-25 11:22:08 +0200602
603 free(ps);
604
605 return NULL;
606}
607
8c4af29e
SV
Sven Verdoolaege2012-10-16 20:22:01 +0200608/* Extract a ppcg_scop from a pet_scop.
609 *
610 * The constructed ppcg_scop refers to elements from the pet_scop
611 * so the pet_scop should not be freed before the ppcg_scop.
612 */
987346fb
SV
Sven Verdoolaege2012-11-14 18:00:39 +0100613static struct ppcg_scop *ppcg_scop_from_pet_scop(struct pet_scop *scop,
614 struct ppcg_options *options)
8c4af29e
SV
Sven Verdoolaege2012-10-16 20:22:01 +0200615{
616 isl_ctx *ctx;
617 struct ppcg_scop *ps;
618
619 if (!scop)
620 return NULL;
621
622 ctx = isl_set_get_ctx(scop->context);
623
624 ps = isl_calloc_type(ctx, struct ppcg_scop);
625 if (!ps)
626 return NULL;
627
e44f8df1 Sven Verdoolaege2012-05-15 09:58:35 +0200628 ps->options = options;
64fc4213
SV
Sven Verdoolaege2013-02-07 14:59:17 +0100629 ps->start = scop->start;
630 ps->end = scop->end;
8c4af29e Sven Verdoolaege2012-10-16 20:22:01 +0200631 ps->context = isl_set_copy(scop->context);
987346fb Sven Verdoolaege2012-11-14 18:00:39 +0100632 ps->context = set_intersect_str(ps->context, options->ctx);
62b08530 Sven Verdoolaege2012-10-16 10:14:45 +0200633 ps->domain = collect_non_kill_domains(scop);
8b2a4f27 Sven Verdoolaege2012-11-10 15:01:02 +0100634 ps->call = collect_call_domains(scop);
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200635 ps->tagged_reads = pet_scop_collect_tagged_may_reads(scop);
75d33034 Sven Verdoolaege2013-08-10 17:28:24 +0200636 ps->reads = pet_scop_collect_may_reads(scop);
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200637 ps->tagged_may_writes = pet_scop_collect_tagged_may_writes(scop);
638 ps->may_writes = pet_scop_collect_may_writes(scop);
639 ps->tagged_must_writes = pet_scop_collect_tagged_must_writes(scop);
640 ps->must_writes = pet_scop_collect_must_writes(scop);
641 ps->tagged_must_kills = pet_scop_collect_tagged_must_kills(scop);
8c4af29e Sven Verdoolaege2012-10-16 20:22:01 +0200642 ps->schedule = pet_scop_collect_schedule(scop);
89cf2962
SV
Sven Verdoolaege2013-08-12 23:14:50 +0200643 ps->n_type = scop->n_type;
644 ps->types = scop->types;
8c4af29e
SV
Sven Verdoolaege2012-10-16 20:22:01 +0200645 ps->n_array = scop->n_array;
646 ps->arrays = scop->arrays;
647 ps->n_stmt = scop->n_stmt;
648 ps->stmts = scop->stmts;
649
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200650 compute_tagger(ps);
dea8e27a Sven Verdoolaege2012-11-09 13:51:46 +0100651 compute_dependences(ps);
ceedeca3 Sven Verdoolaege2012-04-15 14:42:55 +0200652 eliminate_dead_code(ps);
dea8e27a Sven Verdoolaege2012-11-09 13:51:46 +0100653
d0ebae26 Sven Verdoolaege2013-07-25 11:22:08 +0200654 if (!ps->context || !ps->domain || !ps->call || !ps->reads ||
07563074
SV
Sven Verdoolaege2013-08-22 10:23:33 +0200655 !ps->may_writes || !ps->must_writes || !ps->tagged_must_kills ||
656 !ps->schedule)
d0ebae26 Sven Verdoolaege2013-07-25 11:22:08 +0200657 return ppcg_scop_free(ps);
8c4af29e Sven Verdoolaege2012-10-16 20:22:01 +0200658
d0ebae26 Sven Verdoolaege2013-07-25 11:22:08 +0200659 return ps;
8c4af29e
SV
Sven Verdoolaege2012-10-16 20:22:01 +0200660}
661
3d3fd47e
SV
Sven Verdoolaege2013-07-05 23:19:31 +0200662/* Internal data structure for ppcg_transform.
663 */
664struct ppcg_transform_data {
665 struct ppcg_options *options;
666 __isl_give isl_printer *(*transform)(__isl_take isl_printer *p,
667 struct ppcg_scop *scop, void *user);
668 void *user;
669};
670
671/* Callback for pet_transform_C_source that transforms
672 * the given pet_scop to a ppcg_scop before calling the
673 * ppcg_transform callback.
674 */
675static __isl_give isl_printer *transform(__isl_take isl_printer *p,
676 struct pet_scop *scop, void *user)
677{
678 struct ppcg_transform_data *data = user;
679 struct ppcg_scop *ps;
680
07563074 Sven Verdoolaege2013-08-22 10:23:33 +0200681 if (pet_scop_has_data_dependent_conditions(scop)) {
abe3c306
SV
Sven Verdoolaege2013-07-26 11:50:04 +0200682 p = pet_scop_print_original(scop, p);
683 pet_scop_free(scop);
684 return p;
685 }
686
3d3fd47e
SV
Sven Verdoolaege2013-07-05 23:19:31 +0200687 scop = pet_scop_align_params(scop);
688 ps = ppcg_scop_from_pet_scop(scop, data->options);
689
690 p = data->transform(p, ps, data->user);
691
692 ppcg_scop_free(ps);
693 pet_scop_free(scop);
694
695 return p;
696}
697
698/* Transform the C source file "input" by rewriting each scop
699 * through a call to "transform".
700 * The transformed C code is written to "out".
701 *
702 * This is a wrapper around pet_transform_C_source that transforms
703 * the pet_scop to a ppcg_scop before calling "fn".
704 */
705int ppcg_transform(isl_ctx *ctx, const char *input, FILE *out,
706 struct ppcg_options *options,
707 __isl_give isl_printer *(*fn)(__isl_take isl_printer *p,
708 struct ppcg_scop *scop, void *user), void *user)
709{
710 struct ppcg_transform_data data = { options, fn, user };
711 return pet_transform_C_source(ctx, input, out, &transform, &data);
712}
713
b68fc83f
SV
Sven Verdoolaege2013-01-02 17:52:16 +0100714/* Check consistency of options.
715 *
716 * Return -1 on error.
717 */
718static int check_options(isl_ctx *ctx)
719{
720 struct options *options;
721
722 options = isl_ctx_peek_options(ctx, &options_args);
723 if (!options)
724 isl_die(ctx, isl_error_internal,
725 "unable to find options", return -1);
726
727 if (options->ppcg->openmp &&
728 !isl_options_get_ast_build_atomic_upper_bound(ctx))
729 isl_die(ctx, isl_error_invalid,
730 "OpenMP requires atomic bounds", return -1);
731
732 return 0;
733}
734
bcb2edca
SV
Sven Verdoolaege2013-01-02 17:47:36 +0100735int main(int argc, char **argv)
736{
737 int r;
738 isl_ctx *ctx;
739 struct options *options;
740
741 options = options_new_with_defaults();
742 assert(options);
743
744 ctx = isl_ctx_alloc_with_options(&options_args, options);
df38baac Sven Verdoolaege2013-08-27 15:26:07 +0200745 isl_options_set_schedule_outer_coincidence(ctx, 1);
af7f6c30 Sven Verdoolaege2012-03-26 17:58:33 +0200746 isl_options_set_schedule_maximize_band_depth(ctx, 1);
bcb2edca
SV
Sven Verdoolaege2013-01-02 17:47:36 +0100747 argc = options_parse(options, argc, argv, ISL_ARG_ALL);
748
b68fc83f
SV
Sven Verdoolaege2013-01-02 17:52:16 +0100749 if (check_options(ctx) < 0)
750 r = EXIT_FAILURE;
3d3fd47e
SV
Sven Verdoolaege2013-07-05 23:19:31 +0200751 else if (options->ppcg->target == PPCG_TARGET_CUDA)
752 r = generate_cuda(ctx, options->ppcg, options->input);
b68fc83f Sven Verdoolaege2013-01-02 17:52:16 +0100753 else
3d3fd47e
SV
Sven Verdoolaege2013-07-05 23:19:31 +0200754 r = generate_cpu(ctx, options->ppcg, options->input,
755 options->output);
bcb2edca Sven Verdoolaege2013-01-02 17:47:36 +0100756
7ba7fe1a Sven Verdoolaege2011-07-10 18:11:52 +0200757 isl_ctx_free(ctx);
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +0200758
7ba7fe1a Sven Verdoolaege2011-07-10 18:11:52 +0200759 return r;
9f18b065 Sven Verdoolaege2011-06-21 17:40:50 +0200760}