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