]>
Commit | Line | Data |
---|---|---|
2abae5f1 SP |
1 | /* Translation of CLAST (CLooG AST) to Gimple. |
2 | Copyright (C) 2009 Free Software Foundation, Inc. | |
3 | Contributed by Sebastian Pop <sebastian.pop@amd.com>. | |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "ggc.h" | |
26 | #include "tree.h" | |
27 | #include "rtl.h" | |
28 | #include "basic-block.h" | |
29 | #include "diagnostic.h" | |
30 | #include "tree-flow.h" | |
31 | #include "toplev.h" | |
32 | #include "tree-dump.h" | |
33 | #include "timevar.h" | |
34 | #include "cfgloop.h" | |
35 | #include "tree-chrec.h" | |
36 | #include "tree-data-ref.h" | |
37 | #include "tree-scalar-evolution.h" | |
38 | #include "tree-pass.h" | |
39 | #include "domwalk.h" | |
40 | #include "value-prof.h" | |
41 | #include "pointer-set.h" | |
42 | #include "gimple.h" | |
43 | #include "sese.h" | |
44 | ||
45 | #ifdef HAVE_cloog | |
46 | #include "cloog/cloog.h" | |
47 | #include "ppl_c.h" | |
48 | #include "graphite-ppl.h" | |
49 | #include "graphite.h" | |
50 | #include "graphite-poly.h" | |
51 | #include "graphite-scop-detection.h" | |
52 | #include "graphite-clast-to-gimple.h" | |
53 | #include "graphite-dependences.h" | |
54 | ||
55 | /* Verifies properties that GRAPHITE should maintain during translation. */ | |
56 | ||
57 | static inline void | |
58 | graphite_verify (void) | |
59 | { | |
60 | #ifdef ENABLE_CHECKING | |
61 | verify_loop_structure (); | |
62 | verify_dominators (CDI_DOMINATORS); | |
63 | verify_dominators (CDI_POST_DOMINATORS); | |
64 | verify_ssa (false); | |
65 | verify_loop_closed_ssa (); | |
66 | #endif | |
67 | } | |
68 | ||
7a521ff2 TG |
69 | /* Stores the INDEX in a vector for a given clast NAME. */ |
70 | ||
71 | typedef struct clast_name_index { | |
72 | int index; | |
73 | const char *name; | |
74 | } *clast_name_index_p; | |
75 | ||
76 | /* Returns a pointer to a new element of type clast_name_index_p built | |
77 | from NAME and INDEX. */ | |
78 | ||
79 | static inline clast_name_index_p | |
80 | new_clast_name_index (const char *name, int index) | |
81 | { | |
82 | clast_name_index_p res = XNEW (struct clast_name_index); | |
83 | ||
84 | res->name = name; | |
85 | res->index = index; | |
86 | return res; | |
87 | } | |
88 | ||
89 | /* For a given clast NAME, returns -1 if it does not correspond to any | |
90 | parameter, or otherwise, returns the index in the PARAMS or | |
91 | SCATTERING_DIMENSIONS vector. */ | |
92 | ||
93 | static inline int | |
94 | clast_name_to_index (const char *name, htab_t index_table) | |
95 | { | |
96 | struct clast_name_index tmp; | |
97 | PTR *slot; | |
98 | ||
99 | tmp.name = name; | |
100 | slot = htab_find_slot (index_table, &tmp, NO_INSERT); | |
101 | ||
102 | if (slot && *slot) | |
103 | return ((struct clast_name_index *) *slot)->index; | |
104 | ||
105 | return -1; | |
106 | } | |
107 | ||
108 | /* Records in INDEX_TABLE the INDEX for NAME. */ | |
109 | ||
110 | static inline void | |
111 | save_clast_name_index (htab_t index_table, const char *name, int index) | |
112 | { | |
113 | struct clast_name_index tmp; | |
114 | PTR *slot; | |
115 | ||
116 | tmp.name = name; | |
117 | slot = htab_find_slot (index_table, &tmp, INSERT); | |
118 | ||
119 | if (slot) | |
120 | *slot = new_clast_name_index (name, index); | |
121 | } | |
122 | ||
123 | /* Print to stderr the element ELT. */ | |
124 | ||
125 | static inline void | |
126 | debug_clast_name_index (clast_name_index_p elt) | |
127 | { | |
128 | fprintf (stderr, "(index = %d, name = %s)\n", elt->index, elt->name); | |
129 | } | |
130 | ||
131 | /* Helper function for debug_rename_map. */ | |
132 | ||
133 | static inline int | |
134 | debug_clast_name_indexes_1 (void **slot, void *s ATTRIBUTE_UNUSED) | |
135 | { | |
136 | struct clast_name_index *entry = (struct clast_name_index *) *slot; | |
137 | debug_clast_name_index (entry); | |
138 | return 1; | |
139 | } | |
140 | ||
141 | /* Print to stderr all the elements of MAP. */ | |
142 | ||
143 | void | |
144 | debug_clast_name_indexes (htab_t map) | |
145 | { | |
146 | htab_traverse (map, debug_clast_name_indexes_1, NULL); | |
147 | } | |
148 | ||
149 | /* Computes a hash function for database element ELT. */ | |
150 | ||
151 | static inline hashval_t | |
152 | clast_name_index_elt_info (const void *elt) | |
153 | { | |
154 | return htab_hash_pointer (((const struct clast_name_index *) elt)->name); | |
155 | } | |
156 | ||
157 | /* Compares database elements E1 and E2. */ | |
158 | ||
159 | static inline int | |
160 | eq_clast_name_indexes (const void *e1, const void *e2) | |
161 | { | |
162 | const struct clast_name_index *elt1 = (const struct clast_name_index *) e1; | |
163 | const struct clast_name_index *elt2 = (const struct clast_name_index *) e2; | |
164 | ||
165 | return (elt1->name == elt2->name); | |
166 | } | |
167 | ||
168 | ||
2abae5f1 SP |
169 | /* For a given loop DEPTH in the loop nest of the original black box |
170 | PBB, return the old induction variable associated to that loop. */ | |
171 | ||
172 | static inline tree | |
173 | pbb_to_depth_to_oldiv (poly_bb_p pbb, int depth) | |
174 | { | |
175 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
176 | sese region = SCOP_REGION (PBB_SCOP (pbb)); | |
177 | loop_p loop = gbb_loop_at_index (gbb, region, depth); | |
178 | ||
8e6ef139 | 179 | return loop->single_iv; |
2abae5f1 SP |
180 | } |
181 | ||
182 | /* For a given scattering dimension, return the new induction variable | |
183 | associated to it. */ | |
184 | ||
185 | static inline tree | |
186 | newivs_to_depth_to_newiv (VEC (tree, heap) *newivs, int depth) | |
187 | { | |
188 | return VEC_index (tree, newivs, depth); | |
189 | } | |
190 | ||
191 | \f | |
192 | ||
193 | /* Returns the tree variable from the name NAME that was given in | |
194 | Cloog representation. */ | |
195 | ||
196 | static tree | |
197 | clast_name_to_gcc (const char *name, sese region, VEC (tree, heap) *newivs, | |
7a521ff2 | 198 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
199 | { |
200 | int index; | |
201 | VEC (tree, heap) *params = SESE_PARAMS (region); | |
2abae5f1 SP |
202 | |
203 | if (params && params_index) | |
204 | { | |
205 | index = clast_name_to_index (name, params_index); | |
206 | ||
207 | if (index >= 0) | |
208 | return VEC_index (tree, params, index); | |
209 | } | |
210 | ||
211 | gcc_assert (newivs && newivs_index); | |
212 | index = clast_name_to_index (name, newivs_index); | |
213 | gcc_assert (index >= 0); | |
214 | ||
215 | return newivs_to_depth_to_newiv (newivs, index); | |
216 | } | |
217 | ||
218 | /* Returns the maximal precision type for expressions E1 and E2. */ | |
219 | ||
220 | static inline tree | |
221 | max_precision_type (tree e1, tree e2) | |
222 | { | |
223 | tree type1 = TREE_TYPE (e1); | |
224 | tree type2 = TREE_TYPE (e2); | |
225 | return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2; | |
226 | } | |
227 | ||
228 | static tree | |
229 | clast_to_gcc_expression (tree, struct clast_expr *, sese, VEC (tree, heap) *, | |
7a521ff2 | 230 | htab_t, htab_t); |
2abae5f1 SP |
231 | |
232 | /* Converts a Cloog reduction expression R with reduction operation OP | |
233 | to a GCC expression tree of type TYPE. */ | |
234 | ||
235 | static tree | |
236 | clast_to_gcc_expression_red (tree type, enum tree_code op, | |
237 | struct clast_reduction *r, | |
238 | sese region, VEC (tree, heap) *newivs, | |
7a521ff2 | 239 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
240 | { |
241 | int i; | |
242 | tree res = clast_to_gcc_expression (type, r->elts[0], region, newivs, | |
7a521ff2 | 243 | newivs_index, params_index); |
2abae5f1 SP |
244 | tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type; |
245 | ||
246 | for (i = 1; i < r->n; i++) | |
247 | { | |
248 | tree t = clast_to_gcc_expression (operand_type, r->elts[i], region, | |
7a521ff2 | 249 | newivs, newivs_index, params_index); |
2abae5f1 SP |
250 | res = fold_build2 (op, type, res, t); |
251 | } | |
252 | ||
253 | return res; | |
254 | } | |
255 | ||
256 | /* Converts a Cloog AST expression E back to a GCC expression tree of | |
257 | type TYPE. */ | |
258 | ||
259 | static tree | |
260 | clast_to_gcc_expression (tree type, struct clast_expr *e, | |
261 | sese region, VEC (tree, heap) *newivs, | |
7a521ff2 | 262 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
263 | { |
264 | switch (e->type) | |
265 | { | |
266 | case expr_term: | |
267 | { | |
268 | struct clast_term *t = (struct clast_term *) e; | |
269 | ||
270 | if (t->var) | |
271 | { | |
272 | if (value_one_p (t->val)) | |
273 | { | |
274 | tree name = clast_name_to_gcc (t->var, region, newivs, | |
7a521ff2 | 275 | newivs_index, params_index); |
2abae5f1 SP |
276 | return fold_convert (type, name); |
277 | } | |
278 | ||
279 | else if (value_mone_p (t->val)) | |
280 | { | |
281 | tree name = clast_name_to_gcc (t->var, region, newivs, | |
7a521ff2 | 282 | newivs_index, params_index); |
2abae5f1 SP |
283 | name = fold_convert (type, name); |
284 | return fold_build1 (NEGATE_EXPR, type, name); | |
285 | } | |
286 | else | |
287 | { | |
288 | tree name = clast_name_to_gcc (t->var, region, newivs, | |
7a521ff2 | 289 | newivs_index, params_index); |
2abae5f1 SP |
290 | tree cst = gmp_cst_to_tree (type, t->val); |
291 | name = fold_convert (type, name); | |
292 | return fold_build2 (MULT_EXPR, type, cst, name); | |
293 | } | |
294 | } | |
295 | else | |
296 | return gmp_cst_to_tree (type, t->val); | |
297 | } | |
298 | ||
299 | case expr_red: | |
300 | { | |
301 | struct clast_reduction *r = (struct clast_reduction *) e; | |
302 | ||
303 | switch (r->type) | |
304 | { | |
305 | case clast_red_sum: | |
306 | return clast_to_gcc_expression_red | |
307 | (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR, | |
7a521ff2 | 308 | r, region, newivs, newivs_index, params_index); |
2abae5f1 SP |
309 | |
310 | case clast_red_min: | |
311 | return clast_to_gcc_expression_red (type, MIN_EXPR, r, region, | |
7a521ff2 TG |
312 | newivs, newivs_index, |
313 | params_index); | |
2abae5f1 SP |
314 | |
315 | case clast_red_max: | |
316 | return clast_to_gcc_expression_red (type, MAX_EXPR, r, region, | |
7a521ff2 TG |
317 | newivs, newivs_index, |
318 | params_index); | |
2abae5f1 SP |
319 | |
320 | default: | |
321 | gcc_unreachable (); | |
322 | } | |
323 | break; | |
324 | } | |
325 | ||
326 | case expr_bin: | |
327 | { | |
328 | struct clast_binary *b = (struct clast_binary *) e; | |
329 | struct clast_expr *lhs = (struct clast_expr *) b->LHS; | |
330 | tree tl = clast_to_gcc_expression (type, lhs, region, newivs, | |
7a521ff2 | 331 | newivs_index, params_index); |
2abae5f1 SP |
332 | tree tr = gmp_cst_to_tree (type, b->RHS); |
333 | ||
334 | switch (b->type) | |
335 | { | |
336 | case clast_bin_fdiv: | |
337 | return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr); | |
338 | ||
339 | case clast_bin_cdiv: | |
340 | return fold_build2 (CEIL_DIV_EXPR, type, tl, tr); | |
341 | ||
342 | case clast_bin_div: | |
343 | return fold_build2 (EXACT_DIV_EXPR, type, tl, tr); | |
344 | ||
345 | case clast_bin_mod: | |
346 | return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr); | |
347 | ||
348 | default: | |
349 | gcc_unreachable (); | |
350 | } | |
351 | } | |
352 | ||
353 | default: | |
354 | gcc_unreachable (); | |
355 | } | |
356 | ||
357 | return NULL_TREE; | |
358 | } | |
359 | ||
360 | /* Returns the type for the expression E. */ | |
361 | ||
362 | static tree | |
363 | gcc_type_for_clast_expr (struct clast_expr *e, | |
364 | sese region, VEC (tree, heap) *newivs, | |
7a521ff2 | 365 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
366 | { |
367 | switch (e->type) | |
368 | { | |
369 | case expr_term: | |
370 | { | |
371 | struct clast_term *t = (struct clast_term *) e; | |
372 | ||
373 | if (t->var) | |
374 | return TREE_TYPE (clast_name_to_gcc (t->var, region, newivs, | |
7a521ff2 | 375 | newivs_index, params_index)); |
2abae5f1 SP |
376 | else |
377 | return NULL_TREE; | |
378 | } | |
379 | ||
380 | case expr_red: | |
381 | { | |
382 | struct clast_reduction *r = (struct clast_reduction *) e; | |
383 | ||
384 | if (r->n == 1) | |
385 | return gcc_type_for_clast_expr (r->elts[0], region, newivs, | |
7a521ff2 | 386 | newivs_index, params_index); |
2abae5f1 SP |
387 | else |
388 | { | |
389 | int i; | |
390 | for (i = 0; i < r->n; i++) | |
391 | { | |
392 | tree type = gcc_type_for_clast_expr (r->elts[i], region, | |
7a521ff2 TG |
393 | newivs, newivs_index, |
394 | params_index); | |
2abae5f1 SP |
395 | if (type) |
396 | return type; | |
397 | } | |
398 | return NULL_TREE; | |
399 | } | |
400 | } | |
401 | ||
402 | case expr_bin: | |
403 | { | |
404 | struct clast_binary *b = (struct clast_binary *) e; | |
405 | struct clast_expr *lhs = (struct clast_expr *) b->LHS; | |
406 | return gcc_type_for_clast_expr (lhs, region, newivs, | |
7a521ff2 | 407 | newivs_index, params_index); |
2abae5f1 SP |
408 | } |
409 | ||
410 | default: | |
411 | gcc_unreachable (); | |
412 | } | |
413 | ||
414 | return NULL_TREE; | |
415 | } | |
416 | ||
417 | /* Returns the type for the equation CLEQ. */ | |
418 | ||
419 | static tree | |
420 | gcc_type_for_clast_eq (struct clast_equation *cleq, | |
421 | sese region, VEC (tree, heap) *newivs, | |
7a521ff2 | 422 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
423 | { |
424 | tree type = gcc_type_for_clast_expr (cleq->LHS, region, newivs, | |
7a521ff2 | 425 | newivs_index, params_index); |
2abae5f1 SP |
426 | if (type) |
427 | return type; | |
428 | ||
7a521ff2 TG |
429 | return gcc_type_for_clast_expr (cleq->RHS, region, newivs, newivs_index, |
430 | params_index); | |
2abae5f1 SP |
431 | } |
432 | ||
433 | /* Translates a clast equation CLEQ to a tree. */ | |
434 | ||
435 | static tree | |
436 | graphite_translate_clast_equation (sese region, | |
437 | struct clast_equation *cleq, | |
438 | VEC (tree, heap) *newivs, | |
7a521ff2 | 439 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
440 | { |
441 | enum tree_code comp; | |
7a521ff2 TG |
442 | tree type = gcc_type_for_clast_eq (cleq, region, newivs, newivs_index, |
443 | params_index); | |
2abae5f1 | 444 | tree lhs = clast_to_gcc_expression (type, cleq->LHS, region, newivs, |
7a521ff2 | 445 | newivs_index, params_index); |
2abae5f1 | 446 | tree rhs = clast_to_gcc_expression (type, cleq->RHS, region, newivs, |
7a521ff2 | 447 | newivs_index, params_index); |
2abae5f1 SP |
448 | |
449 | if (cleq->sign == 0) | |
450 | comp = EQ_EXPR; | |
451 | ||
452 | else if (cleq->sign > 0) | |
453 | comp = GE_EXPR; | |
454 | ||
455 | else | |
456 | comp = LE_EXPR; | |
457 | ||
458 | return fold_build2 (comp, boolean_type_node, lhs, rhs); | |
459 | } | |
460 | ||
461 | /* Creates the test for the condition in STMT. */ | |
462 | ||
463 | static tree | |
464 | graphite_create_guard_cond_expr (sese region, struct clast_guard *stmt, | |
465 | VEC (tree, heap) *newivs, | |
7a521ff2 | 466 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
467 | { |
468 | tree cond = NULL; | |
469 | int i; | |
470 | ||
471 | for (i = 0; i < stmt->n; i++) | |
472 | { | |
473 | tree eq = graphite_translate_clast_equation (region, &stmt->eq[i], | |
7a521ff2 TG |
474 | newivs, newivs_index, |
475 | params_index); | |
2abae5f1 SP |
476 | |
477 | if (cond) | |
478 | cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq); | |
479 | else | |
480 | cond = eq; | |
481 | } | |
482 | ||
483 | return cond; | |
484 | } | |
485 | ||
486 | /* Creates a new if region corresponding to Cloog's guard. */ | |
487 | ||
488 | static edge | |
489 | graphite_create_new_guard (sese region, edge entry_edge, | |
490 | struct clast_guard *stmt, | |
491 | VEC (tree, heap) *newivs, | |
7a521ff2 | 492 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
493 | { |
494 | tree cond_expr = graphite_create_guard_cond_expr (region, stmt, newivs, | |
7a521ff2 | 495 | newivs_index, params_index); |
2abae5f1 SP |
496 | edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); |
497 | return exit_edge; | |
498 | } | |
499 | ||
500 | /* Walks a CLAST and returns the first statement in the body of a | |
501 | loop. */ | |
502 | ||
503 | static struct clast_user_stmt * | |
504 | clast_get_body_of_loop (struct clast_stmt *stmt) | |
505 | { | |
506 | if (!stmt | |
507 | || CLAST_STMT_IS_A (stmt, stmt_user)) | |
508 | return (struct clast_user_stmt *) stmt; | |
509 | ||
510 | if (CLAST_STMT_IS_A (stmt, stmt_for)) | |
511 | return clast_get_body_of_loop (((struct clast_for *) stmt)->body); | |
512 | ||
513 | if (CLAST_STMT_IS_A (stmt, stmt_guard)) | |
514 | return clast_get_body_of_loop (((struct clast_guard *) stmt)->then); | |
515 | ||
516 | if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
517 | return clast_get_body_of_loop (((struct clast_block *) stmt)->body); | |
518 | ||
519 | gcc_unreachable (); | |
520 | } | |
521 | ||
522 | /* Given a CLOOG_IV, returns the type that it should have in GCC land. | |
523 | If the information is not available, i.e. in the case one of the | |
524 | transforms created the loop, just return integer_type_node. */ | |
525 | ||
526 | static tree | |
527 | gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb) | |
528 | { | |
529 | struct ivtype_map_elt_s tmp; | |
530 | PTR *slot; | |
531 | ||
532 | tmp.cloog_iv = cloog_iv; | |
533 | slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT); | |
534 | ||
535 | if (slot && *slot) | |
536 | return ((ivtype_map_elt) *slot)->type; | |
537 | ||
538 | return integer_type_node; | |
539 | } | |
540 | ||
541 | /* Returns the induction variable for the loop that gets translated to | |
542 | STMT. */ | |
543 | ||
544 | static tree | |
545 | gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for) | |
546 | { | |
547 | struct clast_stmt *stmt = (struct clast_stmt *) stmt_for; | |
548 | struct clast_user_stmt *body = clast_get_body_of_loop (stmt); | |
549 | const char *cloog_iv = stmt_for->iterator; | |
550 | CloogStatement *cs = body->statement; | |
551 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
552 | ||
553 | return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb)); | |
554 | } | |
555 | ||
556 | /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an | |
557 | induction variable for the new LOOP. New LOOP is attached to CFG | |
558 | starting at ENTRY_EDGE. LOOP is inserted into the loop tree and | |
559 | becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds | |
560 | CLooG's scattering name to the induction variable created for the | |
561 | loop of STMT. The new induction variable is inserted in the NEWIVS | |
562 | vector. */ | |
563 | ||
564 | static struct loop * | |
565 | graphite_create_new_loop (sese region, edge entry_edge, | |
566 | struct clast_for *stmt, | |
567 | loop_p outer, VEC (tree, heap) **newivs, | |
7a521ff2 | 568 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
569 | { |
570 | tree type = gcc_type_for_iv_of_clast_loop (stmt); | |
571 | tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs, | |
7a521ff2 | 572 | newivs_index, params_index); |
2abae5f1 | 573 | tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs, |
7a521ff2 | 574 | newivs_index, params_index); |
2abae5f1 SP |
575 | tree stride = gmp_cst_to_tree (type, stmt->stride); |
576 | tree ivvar = create_tmp_var (type, "graphite_IV"); | |
577 | tree iv, iv_after_increment; | |
578 | loop_p loop = create_empty_loop_on_edge | |
579 | (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, | |
580 | outer ? outer : entry_edge->src->loop_father); | |
581 | ||
582 | add_referenced_var (ivvar); | |
583 | ||
584 | save_clast_name_index (newivs_index, stmt->iterator, | |
585 | VEC_length (tree, *newivs)); | |
586 | VEC_safe_push (tree, heap, *newivs, iv); | |
587 | return loop; | |
588 | } | |
589 | ||
590 | /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction | |
591 | variables of the loops around GBB in SESE. */ | |
592 | ||
593 | static void | |
594 | build_iv_mapping (htab_t map, sese region, | |
595 | VEC (tree, heap) *newivs, htab_t newivs_index, | |
7a521ff2 TG |
596 | struct clast_user_stmt *user_stmt, |
597 | htab_t params_index) | |
2abae5f1 SP |
598 | { |
599 | struct clast_stmt *t; | |
600 | int index = 0; | |
601 | CloogStatement *cs = user_stmt->statement; | |
602 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
603 | ||
604 | for (t = user_stmt->substitutions; t; t = t->next, index++) | |
605 | { | |
606 | struct clast_expr *expr = (struct clast_expr *) | |
607 | ((struct clast_assignment *)t)->RHS; | |
608 | tree type = gcc_type_for_clast_expr (expr, region, newivs, | |
7a521ff2 | 609 | newivs_index, params_index); |
2abae5f1 SP |
610 | tree old_name = pbb_to_depth_to_oldiv (pbb, index); |
611 | tree e = clast_to_gcc_expression (type, expr, region, newivs, | |
7a521ff2 | 612 | newivs_index, params_index); |
2abae5f1 SP |
613 | set_rename (map, old_name, e); |
614 | } | |
615 | } | |
616 | ||
617 | /* Helper function for htab_traverse. */ | |
618 | ||
619 | static int | |
620 | copy_renames (void **slot, void *s) | |
621 | { | |
622 | struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; | |
623 | htab_t res = (htab_t) s; | |
624 | tree old_name = entry->old_name; | |
625 | tree expr = entry->expr; | |
626 | struct rename_map_elt_s tmp; | |
627 | PTR *x; | |
628 | ||
629 | tmp.old_name = old_name; | |
630 | x = htab_find_slot (res, &tmp, INSERT); | |
631 | ||
632 | if (!*x) | |
633 | *x = new_rename_map_elt (old_name, expr); | |
634 | ||
635 | return 1; | |
636 | } | |
637 | ||
638 | /* Construct bb_pbb_def with BB and PBB. */ | |
639 | ||
640 | static bb_pbb_def * | |
641 | new_bb_pbb_def (basic_block bb, poly_bb_p pbb) | |
642 | { | |
643 | bb_pbb_def *bb_pbb_p; | |
644 | ||
645 | bb_pbb_p = XNEW (bb_pbb_def); | |
646 | bb_pbb_p->bb = bb; | |
647 | bb_pbb_p->pbb = pbb; | |
648 | ||
649 | return bb_pbb_p; | |
650 | } | |
651 | ||
652 | /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */ | |
653 | ||
654 | static void | |
655 | mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping) | |
656 | { | |
657 | bb_pbb_def tmp; | |
658 | PTR *x; | |
659 | ||
660 | tmp.bb = bb; | |
661 | x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT); | |
662 | ||
663 | if (!*x) | |
664 | *x = new_bb_pbb_def (bb, pbb); | |
665 | } | |
666 | ||
585b3e19 SP |
667 | /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */ |
668 | ||
669 | static poly_bb_p | |
670 | find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb) | |
671 | { | |
672 | bb_pbb_def tmp; | |
673 | PTR *slot; | |
674 | ||
675 | tmp.bb = bb; | |
676 | slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT); | |
677 | ||
678 | if (slot && *slot) | |
679 | return ((bb_pbb_def *) *slot)->pbb; | |
680 | ||
681 | return NULL; | |
682 | } | |
683 | ||
684 | /* Check data dependency in LOOP at scattering level LEVEL. | |
685 | BB_PBB_MAPPING is a basic_block and it's related poly_bb_p | |
686 | mapping. */ | |
687 | ||
688 | static bool | |
689 | dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level) | |
690 | { | |
691 | unsigned i,j; | |
692 | basic_block *bbs = get_loop_body_in_dom_order (loop); | |
693 | ||
694 | for (i = 0; i < loop->num_nodes; i++) | |
695 | { | |
696 | poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]); | |
697 | ||
698 | if (pbb1 == NULL) | |
699 | continue; | |
700 | ||
701 | for (j = 0; j < loop->num_nodes; j++) | |
702 | { | |
703 | poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]); | |
704 | ||
705 | if (pbb2 == NULL) | |
706 | continue; | |
707 | ||
708 | if (dependency_between_pbbs_p (pbb1, pbb2, level)) | |
709 | { | |
710 | free (bbs); | |
711 | return true; | |
712 | } | |
713 | } | |
714 | } | |
715 | ||
716 | free (bbs); | |
717 | ||
718 | return false; | |
719 | } | |
720 | ||
e1f9c1cd | 721 | static edge |
fd2d813d TG |
722 | translate_clast (sese, struct clast_stmt *, edge, htab_t, VEC (tree, heap) **, |
723 | htab_t, htab_t, htab_t); | |
2abae5f1 | 724 | |
e1f9c1cd TG |
725 | /* Translates a clast user statement STMT to gimple. |
726 | ||
727 | - REGION is the sese region we used to generate the scop. | |
2abae5f1 | 728 | - NEXT_E is the edge where new generated code should be attached. |
2abae5f1 SP |
729 | - RENAME_MAP contains a set of tuples of new names associated to |
730 | the original variables names. | |
731 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
e1f9c1cd TG |
732 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in |
733 | the sese region. */ | |
734 | static edge | |
9016166f | 735 | translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e, |
e1f9c1cd | 736 | htab_t rename_map, VEC (tree, heap) **newivs, |
9016166f | 737 | htab_t newivs_index, htab_t bb_pbb_mapping, |
e1f9c1cd TG |
738 | htab_t params_index) |
739 | { | |
9016166f | 740 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement); |
fd2d813d | 741 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); |
e1f9c1cd TG |
742 | |
743 | if (GBB_BB (gbb) == ENTRY_BLOCK_PTR) | |
744 | return next_e; | |
745 | ||
9016166f TG |
746 | build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt, |
747 | params_index); | |
e1f9c1cd TG |
748 | next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region, |
749 | next_e, rename_map); | |
fd2d813d | 750 | mark_bb_with_pbb (pbb, next_e->src, bb_pbb_mapping); |
e1f9c1cd | 751 | update_ssa (TODO_update_ssa); |
fd2d813d | 752 | |
9016166f | 753 | return next_e; |
e1f9c1cd TG |
754 | } |
755 | ||
fd2d813d | 756 | /* Mark a loop parallel, if the graphite dependency check cannot find any |
7c246f5e TG |
757 | dependencies. This triggers parallel code generation in the autopar pass. |
758 | */ | |
fd2d813d TG |
759 | static void |
760 | try_mark_loop_parallel (sese region, loop_p loop, htab_t bb_pbb_mapping) | |
761 | { | |
762 | loop_p outermost_loop = SESE_ENTRY (region)->src->loop_father; | |
763 | int level = loop_depth (loop) - loop_depth (outermost_loop); | |
764 | ||
765 | if (flag_loop_parallelize_all | |
766 | && !dependency_in_loop_p (loop, bb_pbb_mapping, | |
767 | get_scattering_level (level))) | |
768 | loop->can_be_parallel = true; | |
769 | } | |
770 | ||
0dd91484 | 771 | static tree gcc_type_for_iv_of_clast_loop (struct clast_for *); |
fd2d813d | 772 | |
0dd91484 TG |
773 | |
774 | /* Creates a new if region protecting the loop to be executed, if the execution | |
7c246f5e | 775 | count is zero (lb > ub). */ |
0dd91484 TG |
776 | static edge |
777 | graphite_create_new_loop_guard (sese region, edge entry_edge, | |
778 | struct clast_for *stmt, | |
779 | VEC (tree, heap) *newivs, | |
780 | htab_t newivs_index, htab_t params_index) | |
781 | { | |
782 | tree cond_expr; | |
783 | edge exit_edge; | |
784 | tree type = gcc_type_for_iv_of_clast_loop (stmt); | |
785 | tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs, | |
786 | newivs_index, params_index); | |
787 | tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs, | |
788 | newivs_index, params_index); | |
789 | ||
790 | /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a | |
7c246f5e TG |
791 | loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes |
792 | 2^{32|64}, and the condition lb <= ub is true, even if we do not want this. | |
793 | However lb < ub + 1 is false, as expected. | |
794 | There might be a problem with cases where ub is 2^32. */ | |
0dd91484 TG |
795 | tree one; |
796 | Value gmp_one; | |
797 | value_init (gmp_one); | |
798 | value_set_si (gmp_one, 1); | |
799 | one = gmp_cst_to_tree (type, gmp_one); | |
800 | value_clear (gmp_one); | |
801 | ||
802 | ub = fold_build2 (PLUS_EXPR, type, ub, one); | |
803 | cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub); | |
804 | ||
805 | exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); | |
806 | ||
807 | return exit_edge; | |
808 | } | |
809 | ||
810 | ||
811 | /* Create the loop for a clast for statement. | |
e1f9c1cd TG |
812 | |
813 | - REGION is the sese region we used to generate the scop. | |
814 | - NEXT_E is the edge where new generated code should be attached. | |
e1f9c1cd TG |
815 | - RENAME_MAP contains a set of tuples of new names associated to |
816 | the original variables names. | |
817 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
818 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
819 | the sese region. */ | |
820 | static edge | |
0dd91484 | 821 | translate_clast_for_loop (sese region, struct clast_for *stmt, edge next_e, |
fd2d813d TG |
822 | htab_t rename_map, VEC (tree, heap) **newivs, |
823 | htab_t newivs_index, htab_t bb_pbb_mapping, | |
e1f9c1cd TG |
824 | htab_t params_index) |
825 | { | |
fd2d813d TG |
826 | loop_p context_loop = next_e->dest->loop_father; |
827 | loop_p loop = graphite_create_new_loop (region, next_e, stmt, context_loop, | |
828 | newivs, newivs_index, params_index); | |
e1f9c1cd | 829 | edge last_e = single_exit (loop); |
fd2d813d TG |
830 | edge body = single_succ_edge (loop->header); |
831 | ||
832 | next_e = translate_clast (region, stmt->body, body, rename_map, newivs, | |
833 | newivs_index, bb_pbb_mapping, params_index); | |
e1f9c1cd TG |
834 | |
835 | /* Create a basic block for loop close phi nodes. */ | |
836 | last_e = single_succ_edge (split_edge (last_e)); | |
e1f9c1cd TG |
837 | insert_loop_close_phis (rename_map, loop); |
838 | ||
fd2d813d | 839 | try_mark_loop_parallel (region, loop, bb_pbb_mapping); |
e1f9c1cd | 840 | |
9016166f | 841 | return last_e; |
e1f9c1cd TG |
842 | } |
843 | ||
0dd91484 | 844 | /* Translates a clast for statement STMT to gimple. First a guard is created |
7c246f5e TG |
845 | protecting the loop, if it is executed zero times. In this guard we create |
846 | the real loop structure. | |
0dd91484 TG |
847 | |
848 | - REGION is the sese region we used to generate the scop. | |
849 | - NEXT_E is the edge where new generated code should be attached. | |
850 | - RENAME_MAP contains a set of tuples of new names associated to | |
851 | the original variables names. | |
852 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
853 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
854 | the sese region. */ | |
855 | static edge | |
856 | translate_clast_for (sese region, struct clast_for *stmt, edge next_e, | |
857 | htab_t rename_map, VEC (tree, heap) **newivs, | |
858 | htab_t newivs_index, htab_t bb_pbb_mapping, | |
859 | htab_t params_index) | |
860 | { | |
861 | edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs, | |
862 | newivs_index, params_index); | |
863 | ||
864 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); | |
865 | edge false_e = get_false_edge_from_guard_bb (next_e->dest); | |
866 | edge exit_true_e = single_succ_edge (true_e->dest); | |
867 | edge exit_false_e = single_succ_edge (false_e->dest); | |
868 | ||
869 | htab_t before_guard = htab_create (10, rename_map_elt_info, | |
870 | eq_rename_map_elts, free); | |
871 | htab_traverse (rename_map, copy_renames, before_guard); | |
872 | ||
873 | next_e = translate_clast_for_loop (region, stmt, true_e, rename_map, newivs, | |
874 | newivs_index, bb_pbb_mapping, | |
875 | params_index); | |
876 | ||
877 | insert_guard_phis (last_e->src, exit_true_e, exit_false_e, | |
878 | before_guard, rename_map); | |
879 | ||
880 | htab_delete (before_guard); | |
881 | ||
882 | return last_e; | |
883 | } | |
884 | ||
e1f9c1cd TG |
885 | /* Translates a clast guard statement STMT to gimple. |
886 | ||
887 | - REGION is the sese region we used to generate the scop. | |
888 | - NEXT_E is the edge where new generated code should be attached. | |
e1f9c1cd TG |
889 | - RENAME_MAP contains a set of tuples of new names associated to |
890 | the original variables names. | |
891 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
892 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
893 | the sese region. */ | |
894 | static edge | |
fd2d813d | 895 | translate_clast_guard (sese region, struct clast_guard *stmt, edge next_e, |
9016166f | 896 | htab_t rename_map, VEC (tree, heap) **newivs, |
fd2d813d | 897 | htab_t newivs_index, htab_t bb_pbb_mapping, |
9016166f TG |
898 | htab_t params_index) |
899 | { | |
900 | edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs, | |
901 | newivs_index, params_index); | |
902 | ||
e1f9c1cd TG |
903 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); |
904 | edge false_e = get_false_edge_from_guard_bb (next_e->dest); | |
905 | edge exit_true_e = single_succ_edge (true_e->dest); | |
906 | edge exit_false_e = single_succ_edge (false_e->dest); | |
9016166f | 907 | |
e1f9c1cd TG |
908 | htab_t before_guard = htab_create (10, rename_map_elt_info, |
909 | eq_rename_map_elts, free); | |
e1f9c1cd | 910 | htab_traverse (rename_map, copy_renames, before_guard); |
9016166f | 911 | |
fd2d813d | 912 | next_e = translate_clast (region, stmt->then, true_e, |
9016166f | 913 | rename_map, newivs, newivs_index, bb_pbb_mapping, |
fd2d813d | 914 | params_index); |
9016166f | 915 | |
e1f9c1cd TG |
916 | insert_guard_phis (last_e->src, exit_true_e, exit_false_e, |
917 | before_guard, rename_map); | |
918 | ||
919 | htab_delete (before_guard); | |
e1f9c1cd | 920 | |
9016166f | 921 | return last_e; |
e1f9c1cd | 922 | } |
2abae5f1 | 923 | |
e1f9c1cd TG |
924 | /* Translates a CLAST statement STMT to GCC representation in the |
925 | context of a SESE. | |
926 | ||
927 | - NEXT_E is the edge where new generated code should be attached. | |
e1f9c1cd TG |
928 | - RENAME_MAP contains a set of tuples of new names associated to |
929 | the original variables names. | |
930 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ | |
2abae5f1 | 931 | static edge |
fd2d813d | 932 | translate_clast (sese region, struct clast_stmt *stmt, |
e1f9c1cd | 933 | edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, |
fd2d813d | 934 | htab_t newivs_index, htab_t bb_pbb_mapping, |
7a521ff2 | 935 | htab_t params_index) |
2abae5f1 SP |
936 | { |
937 | if (!stmt) | |
938 | return next_e; | |
939 | ||
940 | if (CLAST_STMT_IS_A (stmt, stmt_root)) | |
9016166f | 941 | ; /* Do nothing. */ |
2abae5f1 | 942 | |
9016166f TG |
943 | else if (CLAST_STMT_IS_A (stmt, stmt_user)) |
944 | next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt, | |
945 | next_e, rename_map, newivs, newivs_index, | |
946 | bb_pbb_mapping, params_index); | |
2abae5f1 | 947 | |
9016166f | 948 | else if (CLAST_STMT_IS_A (stmt, stmt_for)) |
fd2d813d TG |
949 | next_e = translate_clast_for (region, |
950 | (struct clast_for *) stmt, next_e, rename_map, | |
951 | newivs, newivs_index, bb_pbb_mapping, | |
952 | params_index); | |
2abae5f1 | 953 | |
9016166f | 954 | else if (CLAST_STMT_IS_A (stmt, stmt_guard)) |
fd2d813d | 955 | next_e = translate_clast_guard (region, (struct clast_guard *) stmt, next_e, |
9016166f | 956 | rename_map, newivs, newivs_index, |
fd2d813d | 957 | bb_pbb_mapping, params_index); |
9016166f TG |
958 | |
959 | else if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
fd2d813d | 960 | next_e = translate_clast (region, ((struct clast_block *) stmt)->body, |
9016166f | 961 | next_e, rename_map, newivs, newivs_index, |
fd2d813d | 962 | bb_pbb_mapping, params_index); |
9016166f TG |
963 | else |
964 | gcc_unreachable(); | |
2abae5f1 | 965 | |
9016166f TG |
966 | recompute_all_dominators (); |
967 | graphite_verify (); | |
968 | ||
fd2d813d TG |
969 | return translate_clast (region, stmt->next, next_e, rename_map, newivs, |
970 | newivs_index, bb_pbb_mapping, params_index); | |
2abae5f1 SP |
971 | } |
972 | ||
973 | /* Returns the first cloog name used in EXPR. */ | |
974 | ||
975 | static const char * | |
976 | find_cloog_iv_in_expr (struct clast_expr *expr) | |
977 | { | |
978 | struct clast_term *term = (struct clast_term *) expr; | |
979 | ||
980 | if (expr->type == expr_term | |
981 | && !term->var) | |
982 | return NULL; | |
983 | ||
984 | if (expr->type == expr_term) | |
985 | return term->var; | |
986 | ||
987 | if (expr->type == expr_red) | |
988 | { | |
989 | int i; | |
990 | struct clast_reduction *red = (struct clast_reduction *) expr; | |
991 | ||
992 | for (i = 0; i < red->n; i++) | |
993 | { | |
994 | const char *res = find_cloog_iv_in_expr ((red)->elts[i]); | |
995 | ||
996 | if (res) | |
997 | return res; | |
998 | } | |
999 | } | |
1000 | ||
1001 | return NULL; | |
1002 | } | |
1003 | ||
1004 | /* Build for a clast_user_stmt USER_STMT a map between the CLAST | |
1005 | induction variables and the corresponding GCC old induction | |
1006 | variables. This information is stored on each GRAPHITE_BB. */ | |
1007 | ||
1008 | static void | |
1009 | compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt) | |
1010 | { | |
1011 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
1012 | struct clast_stmt *t; | |
1013 | int index = 0; | |
1014 | ||
1015 | for (t = user_stmt->substitutions; t; t = t->next, index++) | |
1016 | { | |
1017 | PTR *slot; | |
1018 | struct ivtype_map_elt_s tmp; | |
b8698a0f | 1019 | struct clast_expr *expr = (struct clast_expr *) |
2abae5f1 SP |
1020 | ((struct clast_assignment *)t)->RHS; |
1021 | ||
1022 | /* Create an entry (clast_var, type). */ | |
1023 | tmp.cloog_iv = find_cloog_iv_in_expr (expr); | |
1024 | if (!tmp.cloog_iv) | |
1025 | continue; | |
1026 | ||
1027 | slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); | |
1028 | ||
1029 | if (!*slot) | |
1030 | { | |
1031 | tree oldiv = pbb_to_depth_to_oldiv (pbb, index); | |
1032 | tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node; | |
1033 | *slot = new_ivtype_map_elt (tmp.cloog_iv, type); | |
1034 | } | |
1035 | } | |
1036 | } | |
1037 | ||
1038 | /* Walk the CLAST tree starting from STMT and build for each | |
1039 | clast_user_stmt a map between the CLAST induction variables and the | |
1040 | corresponding GCC old induction variables. This information is | |
1041 | stored on each GRAPHITE_BB. */ | |
1042 | ||
1043 | static void | |
1044 | compute_cloog_iv_types (struct clast_stmt *stmt) | |
1045 | { | |
1046 | if (!stmt) | |
1047 | return; | |
1048 | ||
1049 | if (CLAST_STMT_IS_A (stmt, stmt_root)) | |
1050 | goto next; | |
1051 | ||
1052 | if (CLAST_STMT_IS_A (stmt, stmt_user)) | |
1053 | { | |
1054 | CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; | |
1055 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
1056 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
1057 | ||
1058 | if (!GBB_CLOOG_IV_TYPES (gbb)) | |
1059 | GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info, | |
1060 | eq_ivtype_map_elts, free); | |
1061 | ||
1062 | compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt); | |
1063 | goto next; | |
1064 | } | |
1065 | ||
1066 | if (CLAST_STMT_IS_A (stmt, stmt_for)) | |
1067 | { | |
1068 | struct clast_stmt *s = ((struct clast_for *) stmt)->body; | |
1069 | compute_cloog_iv_types (s); | |
1070 | goto next; | |
1071 | } | |
1072 | ||
1073 | if (CLAST_STMT_IS_A (stmt, stmt_guard)) | |
1074 | { | |
1075 | struct clast_stmt *s = ((struct clast_guard *) stmt)->then; | |
1076 | compute_cloog_iv_types (s); | |
1077 | goto next; | |
1078 | } | |
1079 | ||
1080 | if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
1081 | { | |
1082 | struct clast_stmt *s = ((struct clast_block *) stmt)->body; | |
1083 | compute_cloog_iv_types (s); | |
1084 | goto next; | |
1085 | } | |
1086 | ||
1087 | gcc_unreachable (); | |
1088 | ||
1089 | next: | |
1090 | compute_cloog_iv_types (stmt->next); | |
1091 | } | |
1092 | ||
1093 | /* Free the SCATTERING domain list. */ | |
1094 | ||
1095 | static void | |
1096 | free_scattering (CloogDomainList *scattering) | |
1097 | { | |
1098 | while (scattering) | |
1099 | { | |
1100 | CloogDomain *dom = cloog_domain (scattering); | |
1101 | CloogDomainList *next = cloog_next_domain (scattering); | |
1102 | ||
1103 | cloog_domain_free (dom); | |
1104 | free (scattering); | |
1105 | scattering = next; | |
1106 | } | |
1107 | } | |
1108 | ||
1109 | /* Initialize Cloog's parameter names from the names used in GIMPLE. | |
1110 | Initialize Cloog's iterator names, using 'graphite_iterator_%d' | |
1111 | from 0 to scop_nb_loops (scop). */ | |
1112 | ||
1113 | static void | |
1114 | initialize_cloog_names (scop_p scop, CloogProgram *prog) | |
1115 | { | |
1116 | sese region = SCOP_REGION (scop); | |
1117 | int i; | |
1118 | int nb_iterators = scop_max_loop_depth (scop); | |
1119 | int nb_scattering = cloog_program_nb_scattdims (prog); | |
7a521ff2 | 1120 | int nb_parameters = VEC_length (tree, SESE_PARAMS (region)); |
2abae5f1 SP |
1121 | char **iterators = XNEWVEC (char *, nb_iterators * 2); |
1122 | char **scattering = XNEWVEC (char *, nb_scattering); | |
7a521ff2 | 1123 | char **parameters= XNEWVEC (char *, nb_parameters); |
2abae5f1 SP |
1124 | |
1125 | cloog_program_set_names (prog, cloog_names_malloc ()); | |
7a521ff2 TG |
1126 | |
1127 | for (i = 0; i < nb_parameters; i++) | |
1128 | { | |
1129 | tree param = VEC_index (tree, SESE_PARAMS(region), i); | |
1130 | const char *name = get_name (param); | |
1131 | int len; | |
1132 | ||
1133 | if (!name) | |
1134 | name = "T"; | |
1135 | ||
1136 | len = strlen (name); | |
1137 | len += 17; | |
1138 | parameters[i] = XNEWVEC (char, len + 1); | |
1139 | snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param)); | |
1140 | } | |
1141 | ||
1142 | cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters); | |
1143 | cloog_names_set_parameters (cloog_program_names (prog), parameters); | |
2abae5f1 SP |
1144 | |
1145 | for (i = 0; i < nb_iterators; i++) | |
1146 | { | |
1147 | int len = 4 + 16; | |
1148 | iterators[i] = XNEWVEC (char, len); | |
1149 | snprintf (iterators[i], len, "git_%d", i); | |
1150 | } | |
1151 | ||
1152 | cloog_names_set_nb_iterators (cloog_program_names (prog), | |
1153 | nb_iterators); | |
1154 | cloog_names_set_iterators (cloog_program_names (prog), | |
1155 | iterators); | |
1156 | ||
1157 | for (i = 0; i < nb_scattering; i++) | |
1158 | { | |
1159 | int len = 5 + 16; | |
1160 | scattering[i] = XNEWVEC (char, len); | |
1161 | snprintf (scattering[i], len, "scat_%d", i); | |
1162 | } | |
1163 | ||
1164 | cloog_names_set_nb_scattering (cloog_program_names (prog), | |
1165 | nb_scattering); | |
1166 | cloog_names_set_scattering (cloog_program_names (prog), | |
1167 | scattering); | |
1168 | } | |
1169 | ||
1170 | /* Build cloog program for SCoP. */ | |
1171 | ||
1172 | static void | |
1173 | build_cloog_prog (scop_p scop, CloogProgram *prog) | |
1174 | { | |
1175 | int i; | |
1176 | int max_nb_loops = scop_max_loop_depth (scop); | |
1177 | poly_bb_p pbb; | |
1178 | CloogLoop *loop_list = NULL; | |
1179 | CloogBlockList *block_list = NULL; | |
1180 | CloogDomainList *scattering = NULL; | |
1181 | int nbs = 2 * max_nb_loops + 1; | |
1182 | int *scaldims; | |
1183 | ||
1184 | cloog_program_set_context | |
1185 | (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop))); | |
1186 | nbs = unify_scattering_dimensions (scop); | |
1187 | scaldims = (int *) xmalloc (nbs * (sizeof (int))); | |
1188 | cloog_program_set_nb_scattdims (prog, nbs); | |
1189 | initialize_cloog_names (scop, prog); | |
1190 | ||
1191 | for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | |
1192 | { | |
1193 | CloogStatement *stmt; | |
1194 | CloogBlock *block; | |
1195 | ||
1196 | /* Dead code elimination: when the domain of a PBB is empty, | |
1197 | don't generate code for the PBB. */ | |
1198 | if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb))) | |
1199 | continue; | |
1200 | ||
1201 | /* Build the new statement and its block. */ | |
d48e288d | 1202 | stmt = cloog_statement_alloc (pbb_index (pbb)); |
2abae5f1 SP |
1203 | block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb)); |
1204 | cloog_statement_set_usr (stmt, pbb); | |
1205 | ||
1206 | /* Build loop list. */ | |
1207 | { | |
1208 | CloogLoop *new_loop_list = cloog_loop_malloc (); | |
1209 | cloog_loop_set_next (new_loop_list, loop_list); | |
1210 | cloog_loop_set_domain | |
1211 | (new_loop_list, | |
1212 | new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb))); | |
1213 | cloog_loop_set_block (new_loop_list, block); | |
1214 | loop_list = new_loop_list; | |
1215 | } | |
1216 | ||
1217 | /* Build block list. */ | |
1218 | { | |
1219 | CloogBlockList *new_block_list = cloog_block_list_malloc (); | |
1220 | ||
1221 | cloog_block_list_set_next (new_block_list, block_list); | |
1222 | cloog_block_list_set_block (new_block_list, block); | |
1223 | block_list = new_block_list; | |
1224 | } | |
1225 | ||
1226 | /* Build scattering list. */ | |
1227 | { | |
1228 | /* XXX: Replace with cloog_domain_list_alloc(), when available. */ | |
1229 | CloogDomainList *new_scattering | |
1230 | = (CloogDomainList *) xmalloc (sizeof (CloogDomainList)); | |
1231 | ppl_Polyhedron_t scat; | |
1232 | CloogDomain *dom; | |
1233 | ||
1234 | scat = PBB_TRANSFORMED_SCATTERING (pbb); | |
1235 | dom = new_Cloog_Domain_from_ppl_Polyhedron (scat); | |
1236 | ||
1237 | cloog_set_next_domain (new_scattering, scattering); | |
1238 | cloog_set_domain (new_scattering, dom); | |
1239 | scattering = new_scattering; | |
1240 | } | |
1241 | } | |
1242 | ||
1243 | cloog_program_set_loop (prog, loop_list); | |
1244 | cloog_program_set_blocklist (prog, block_list); | |
1245 | ||
1246 | for (i = 0; i < nbs; i++) | |
1247 | scaldims[i] = 0 ; | |
1248 | ||
1249 | cloog_program_set_scaldims (prog, scaldims); | |
1250 | ||
1251 | /* Extract scalar dimensions to simplify the code generation problem. */ | |
1252 | cloog_program_extract_scalars (prog, scattering); | |
1253 | ||
1254 | /* Apply scattering. */ | |
1255 | cloog_program_scatter (prog, scattering); | |
1256 | free_scattering (scattering); | |
1257 | ||
1258 | /* Iterators corresponding to scalar dimensions have to be extracted. */ | |
1259 | cloog_names_scalarize (cloog_program_names (prog), nbs, | |
1260 | cloog_program_scaldims (prog)); | |
1261 | ||
1262 | /* Free blocklist. */ | |
1263 | { | |
1264 | CloogBlockList *next = cloog_program_blocklist (prog); | |
1265 | ||
1266 | while (next) | |
1267 | { | |
1268 | CloogBlockList *toDelete = next; | |
1269 | next = cloog_block_list_next (next); | |
1270 | cloog_block_list_set_next (toDelete, NULL); | |
1271 | cloog_block_list_set_block (toDelete, NULL); | |
1272 | cloog_block_list_free (toDelete); | |
1273 | } | |
1274 | cloog_program_set_blocklist (prog, NULL); | |
1275 | } | |
1276 | } | |
1277 | ||
1278 | /* Return the options that will be used in GLOOG. */ | |
1279 | ||
1280 | static CloogOptions * | |
1281 | set_cloog_options (void) | |
1282 | { | |
1283 | CloogOptions *options = cloog_options_malloc (); | |
1284 | ||
1285 | /* Change cloog output language to C. If we do use FORTRAN instead, cloog | |
1286 | will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if | |
1287 | we pass an incomplete program to cloog. */ | |
1288 | options->language = LANGUAGE_C; | |
1289 | ||
1290 | /* Enable complex equality spreading: removes dummy statements | |
1291 | (assignments) in the generated code which repeats the | |
1292 | substitution equations for statements. This is useless for | |
1293 | GLooG. */ | |
1294 | options->esp = 1; | |
1295 | ||
1296 | /* Enable C pretty-printing mode: normalizes the substitution | |
1297 | equations for statements. */ | |
1298 | options->cpp = 1; | |
1299 | ||
1300 | /* Allow cloog to build strides with a stride width different to one. | |
1301 | This example has stride = 4: | |
1302 | ||
1303 | for (i = 0; i < 20; i += 4) | |
1304 | A */ | |
1305 | options->strides = 1; | |
1306 | ||
1307 | /* Disable optimizations and make cloog generate source code closer to the | |
1308 | input. This is useful for debugging, but later we want the optimized | |
1309 | code. | |
1310 | ||
1311 | XXX: We can not disable optimizations, as loop blocking is not working | |
1312 | without them. */ | |
1313 | if (0) | |
1314 | { | |
1315 | options->f = -1; | |
1316 | options->l = INT_MAX; | |
1317 | } | |
1318 | ||
1319 | return options; | |
1320 | } | |
1321 | ||
1322 | /* Prints STMT to STDERR. */ | |
1323 | ||
1324 | void | |
1325 | print_clast_stmt (FILE *file, struct clast_stmt *stmt) | |
1326 | { | |
1327 | CloogOptions *options = set_cloog_options (); | |
1328 | ||
1329 | pprint (file, stmt, 0, options); | |
1330 | cloog_options_free (options); | |
1331 | } | |
1332 | ||
1333 | /* Prints STMT to STDERR. */ | |
1334 | ||
1335 | void | |
1336 | debug_clast_stmt (struct clast_stmt *stmt) | |
1337 | { | |
1338 | print_clast_stmt (stderr, stmt); | |
1339 | } | |
1340 | ||
1341 | /* Translate SCOP to a CLooG program and clast. These two | |
1342 | representations should be freed together: a clast cannot be used | |
1343 | without a program. */ | |
1344 | ||
1345 | cloog_prog_clast | |
1346 | scop_to_clast (scop_p scop) | |
1347 | { | |
1348 | CloogOptions *options = set_cloog_options (); | |
1349 | cloog_prog_clast pc; | |
1350 | ||
1351 | /* Connect new cloog prog generation to graphite. */ | |
1352 | pc.prog = cloog_program_malloc (); | |
1353 | build_cloog_prog (scop, pc.prog); | |
1354 | pc.prog = cloog_program_generate (pc.prog, options); | |
1355 | pc.stmt = cloog_clast_create (pc.prog, options); | |
1356 | ||
1357 | cloog_options_free (options); | |
1358 | return pc; | |
1359 | } | |
1360 | ||
1361 | /* Prints to FILE the code generated by CLooG for SCOP. */ | |
1362 | ||
1363 | void | |
1364 | print_generated_program (FILE *file, scop_p scop) | |
1365 | { | |
1366 | CloogOptions *options = set_cloog_options (); | |
1367 | cloog_prog_clast pc = scop_to_clast (scop); | |
1368 | ||
1369 | fprintf (file, " (prog: \n"); | |
1370 | cloog_program_print (file, pc.prog); | |
1371 | fprintf (file, " )\n"); | |
1372 | ||
1373 | fprintf (file, " (clast: \n"); | |
1374 | pprint (file, pc.stmt, 0, options); | |
1375 | fprintf (file, " )\n"); | |
1376 | ||
1377 | cloog_options_free (options); | |
1378 | cloog_clast_free (pc.stmt); | |
1379 | cloog_program_free (pc.prog); | |
1380 | } | |
1381 | ||
1382 | /* Prints to STDERR the code generated by CLooG for SCOP. */ | |
1383 | ||
1384 | void | |
1385 | debug_generated_program (scop_p scop) | |
1386 | { | |
1387 | print_generated_program (stderr, scop); | |
1388 | } | |
1389 | ||
7a521ff2 TG |
1390 | /* Add CLooG names to parameter index. The index is used to translate back from |
1391 | * CLooG names to GCC trees. */ | |
1392 | ||
1393 | static void | |
1394 | create_params_index (htab_t index_table, CloogProgram *prog) { | |
1395 | CloogNames* names = cloog_program_names (prog); | |
1396 | int nb_parameters = cloog_names_nb_parameters (names); | |
1397 | char **parameters = cloog_names_parameters (names); | |
1398 | int i; | |
1399 | ||
1400 | for (i = 0; i < nb_parameters; i++) | |
1401 | save_clast_name_index (index_table, parameters[i], i); | |
1402 | } | |
1403 | ||
2abae5f1 SP |
1404 | /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for |
1405 | the given SCOP. Return true if code generation succeeded. | |
1406 | BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping. | |
1407 | */ | |
1408 | ||
1409 | bool | |
1410 | gloog (scop_p scop, htab_t bb_pbb_mapping) | |
1411 | { | |
1412 | edge new_scop_exit_edge = NULL; | |
1413 | VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10); | |
2abae5f1 SP |
1414 | sese region = SCOP_REGION (scop); |
1415 | ifsese if_region = NULL; | |
7a521ff2 | 1416 | htab_t rename_map, newivs_index, params_index; |
87d4d0ee SP |
1417 | cloog_prog_clast pc; |
1418 | ||
1419 | timevar_push (TV_GRAPHITE_CODE_GEN); | |
1420 | ||
1421 | pc = scop_to_clast (scop); | |
2abae5f1 SP |
1422 | |
1423 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1424 | { | |
1425 | fprintf (dump_file, "\nCLAST generated by CLooG: \n"); | |
1426 | print_clast_stmt (dump_file, pc.stmt); | |
1427 | fprintf (dump_file, "\n"); | |
1428 | } | |
1429 | ||
2abae5f1 SP |
1430 | recompute_all_dominators (); |
1431 | graphite_verify (); | |
1432 | ||
1433 | if_region = move_sese_in_condition (region); | |
1434 | sese_insert_phis_for_liveouts (region, | |
1435 | if_region->region->exit->src, | |
1436 | if_region->false_region->exit, | |
1437 | if_region->true_region->exit); | |
2abae5f1 SP |
1438 | recompute_all_dominators (); |
1439 | graphite_verify (); | |
7a521ff2 | 1440 | |
2abae5f1 | 1441 | compute_cloog_iv_types (pc.stmt); |
2abae5f1 SP |
1442 | rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free); |
1443 | newivs_index = htab_create (10, clast_name_index_elt_info, | |
1444 | eq_clast_name_indexes, free); | |
7a521ff2 TG |
1445 | params_index = htab_create (10, clast_name_index_elt_info, |
1446 | eq_clast_name_indexes, free); | |
1447 | ||
1448 | create_params_index (params_index, pc.prog); | |
2abae5f1 | 1449 | |
fd2d813d | 1450 | new_scop_exit_edge = translate_clast (region, pc.stmt, |
2abae5f1 SP |
1451 | if_region->true_region->entry, |
1452 | rename_map, &newivs, newivs_index, | |
fd2d813d | 1453 | bb_pbb_mapping, params_index); |
2abae5f1 SP |
1454 | graphite_verify (); |
1455 | sese_adjust_liveout_phis (region, rename_map, | |
1456 | if_region->region->exit->src, | |
1457 | if_region->false_region->exit, | |
1458 | if_region->true_region->exit); | |
1459 | recompute_all_dominators (); | |
1460 | graphite_verify (); | |
1461 | ||
8c54631d SP |
1462 | free (if_region->true_region); |
1463 | free (if_region->region); | |
1464 | free (if_region); | |
1465 | ||
2abae5f1 SP |
1466 | htab_delete (rename_map); |
1467 | htab_delete (newivs_index); | |
7a521ff2 | 1468 | htab_delete (params_index); |
2abae5f1 SP |
1469 | VEC_free (tree, heap, newivs); |
1470 | cloog_clast_free (pc.stmt); | |
1471 | cloog_program_free (pc.prog); | |
87d4d0ee SP |
1472 | timevar_pop (TV_GRAPHITE_CODE_GEN); |
1473 | ||
585b3e19 | 1474 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2abae5f1 | 1475 | { |
585b3e19 SP |
1476 | loop_p loop; |
1477 | loop_iterator li; | |
1478 | int num_no_dependency = 0; | |
2abae5f1 | 1479 | |
585b3e19 SP |
1480 | FOR_EACH_LOOP (li, loop, 0) |
1481 | if (loop->can_be_parallel) | |
1482 | num_no_dependency++; | |
2abae5f1 | 1483 | |
585b3e19 SP |
1484 | fprintf (dump_file, "\n%d loops carried no dependency.\n", |
1485 | num_no_dependency); | |
2abae5f1 SP |
1486 | } |
1487 | ||
585b3e19 | 1488 | return true; |
2abae5f1 SP |
1489 | } |
1490 | ||
1491 | #endif |