]>
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 | ||
248081bc SP |
550 | /* Java does not initialize long_long_integer_type_node. */ |
551 | #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype) | |
552 | ||
68d3ff90 TG |
553 | /* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC |
554 | land. The selected type is big enough to include the original loop | |
555 | iteration variable, but signed to work with the subtractions CLooG | |
556 | may have introduced. If such a type is not available, we fail. | |
557 | ||
558 | TODO: Do not always return long_long, but the smallest possible | |
559 | type, that still holds the original type. | |
560 | ||
561 | TODO: Get the types using CLooG instead. This enables further | |
562 | optimizations, but needs CLooG support. */ | |
2abae5f1 SP |
563 | |
564 | static tree | |
565 | gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb) | |
566 | { | |
567 | struct ivtype_map_elt_s tmp; | |
568 | PTR *slot; | |
569 | ||
570 | tmp.cloog_iv = cloog_iv; | |
571 | slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT); | |
572 | ||
573 | if (slot && *slot) | |
68d3ff90 TG |
574 | { |
575 | tree type = ((ivtype_map_elt) *slot)->type; | |
576 | int type_precision = TYPE_PRECISION (type); | |
577 | ||
578 | /* Find the smallest signed type possible. */ | |
579 | if (!TYPE_UNSIGNED (type)) | |
580 | { | |
581 | if (type_precision <= TYPE_PRECISION (integer_type_node)) | |
582 | return integer_type_node; | |
583 | ||
584 | if (type_precision <= TYPE_PRECISION (long_integer_type_node)) | |
585 | return long_integer_type_node; | |
586 | ||
248081bc SP |
587 | if (type_precision <= TYPE_PRECISION (my_long_long)) |
588 | return my_long_long; | |
68d3ff90 TG |
589 | |
590 | gcc_unreachable (); | |
591 | } | |
592 | ||
593 | if (type_precision < TYPE_PRECISION (integer_type_node)) | |
594 | return integer_type_node; | |
595 | ||
596 | if (type_precision < TYPE_PRECISION (long_integer_type_node)) | |
597 | return long_integer_type_node; | |
598 | ||
248081bc SP |
599 | if (type_precision < TYPE_PRECISION (my_long_long)) |
600 | return my_long_long; | |
68d3ff90 TG |
601 | |
602 | /* There is no signed type available, that is large enough to hold the | |
603 | original value. */ | |
604 | gcc_unreachable (); | |
605 | } | |
2abae5f1 | 606 | |
248081bc | 607 | return my_long_long; |
2abae5f1 SP |
608 | } |
609 | ||
248081bc SP |
610 | #undef my_long_long |
611 | ||
2abae5f1 SP |
612 | /* Returns the induction variable for the loop that gets translated to |
613 | STMT. */ | |
614 | ||
615 | static tree | |
616 | gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for) | |
617 | { | |
618 | struct clast_stmt *stmt = (struct clast_stmt *) stmt_for; | |
619 | struct clast_user_stmt *body = clast_get_body_of_loop (stmt); | |
620 | const char *cloog_iv = stmt_for->iterator; | |
621 | CloogStatement *cs = body->statement; | |
622 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
623 | ||
624 | return gcc_type_for_cloog_iv (cloog_iv, PBB_BLACK_BOX (pbb)); | |
625 | } | |
626 | ||
627 | /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an | |
628 | induction variable for the new LOOP. New LOOP is attached to CFG | |
629 | starting at ENTRY_EDGE. LOOP is inserted into the loop tree and | |
630 | becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds | |
631 | CLooG's scattering name to the induction variable created for the | |
632 | loop of STMT. The new induction variable is inserted in the NEWIVS | |
633 | vector. */ | |
634 | ||
635 | static struct loop * | |
636 | graphite_create_new_loop (sese region, edge entry_edge, | |
637 | struct clast_for *stmt, | |
638 | loop_p outer, VEC (tree, heap) **newivs, | |
7a521ff2 | 639 | htab_t newivs_index, htab_t params_index) |
2abae5f1 SP |
640 | { |
641 | tree type = gcc_type_for_iv_of_clast_loop (stmt); | |
642 | tree lb = clast_to_gcc_expression (type, stmt->LB, region, *newivs, | |
7a521ff2 | 643 | newivs_index, params_index); |
2abae5f1 | 644 | tree ub = clast_to_gcc_expression (type, stmt->UB, region, *newivs, |
7a521ff2 | 645 | newivs_index, params_index); |
2abae5f1 SP |
646 | tree stride = gmp_cst_to_tree (type, stmt->stride); |
647 | tree ivvar = create_tmp_var (type, "graphite_IV"); | |
648 | tree iv, iv_after_increment; | |
649 | loop_p loop = create_empty_loop_on_edge | |
650 | (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, | |
651 | outer ? outer : entry_edge->src->loop_father); | |
652 | ||
653 | add_referenced_var (ivvar); | |
654 | ||
655 | save_clast_name_index (newivs_index, stmt->iterator, | |
656 | VEC_length (tree, *newivs)); | |
657 | VEC_safe_push (tree, heap, *newivs, iv); | |
658 | return loop; | |
659 | } | |
660 | ||
661 | /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction | |
662 | variables of the loops around GBB in SESE. */ | |
663 | ||
664 | static void | |
665 | build_iv_mapping (htab_t map, sese region, | |
666 | VEC (tree, heap) *newivs, htab_t newivs_index, | |
7a521ff2 TG |
667 | struct clast_user_stmt *user_stmt, |
668 | htab_t params_index) | |
2abae5f1 SP |
669 | { |
670 | struct clast_stmt *t; | |
671 | int index = 0; | |
672 | CloogStatement *cs = user_stmt->statement; | |
673 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
674 | ||
675 | for (t = user_stmt->substitutions; t; t = t->next, index++) | |
676 | { | |
677 | struct clast_expr *expr = (struct clast_expr *) | |
678 | ((struct clast_assignment *)t)->RHS; | |
679 | tree type = gcc_type_for_clast_expr (expr, region, newivs, | |
7a521ff2 | 680 | newivs_index, params_index); |
2abae5f1 SP |
681 | tree old_name = pbb_to_depth_to_oldiv (pbb, index); |
682 | tree e = clast_to_gcc_expression (type, expr, region, newivs, | |
7a521ff2 | 683 | newivs_index, params_index); |
2abae5f1 SP |
684 | set_rename (map, old_name, e); |
685 | } | |
686 | } | |
687 | ||
688 | /* Helper function for htab_traverse. */ | |
689 | ||
690 | static int | |
691 | copy_renames (void **slot, void *s) | |
692 | { | |
693 | struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; | |
694 | htab_t res = (htab_t) s; | |
695 | tree old_name = entry->old_name; | |
696 | tree expr = entry->expr; | |
697 | struct rename_map_elt_s tmp; | |
698 | PTR *x; | |
699 | ||
700 | tmp.old_name = old_name; | |
701 | x = htab_find_slot (res, &tmp, INSERT); | |
702 | ||
556afcdc | 703 | if (x && !*x) |
2abae5f1 SP |
704 | *x = new_rename_map_elt (old_name, expr); |
705 | ||
706 | return 1; | |
707 | } | |
708 | ||
709 | /* Construct bb_pbb_def with BB and PBB. */ | |
710 | ||
711 | static bb_pbb_def * | |
712 | new_bb_pbb_def (basic_block bb, poly_bb_p pbb) | |
713 | { | |
714 | bb_pbb_def *bb_pbb_p; | |
715 | ||
716 | bb_pbb_p = XNEW (bb_pbb_def); | |
717 | bb_pbb_p->bb = bb; | |
718 | bb_pbb_p->pbb = pbb; | |
719 | ||
720 | return bb_pbb_p; | |
721 | } | |
722 | ||
723 | /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */ | |
724 | ||
725 | static void | |
726 | mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping) | |
727 | { | |
728 | bb_pbb_def tmp; | |
729 | PTR *x; | |
730 | ||
731 | tmp.bb = bb; | |
732 | x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT); | |
733 | ||
556afcdc | 734 | if (x && !*x) |
2abae5f1 SP |
735 | *x = new_bb_pbb_def (bb, pbb); |
736 | } | |
737 | ||
585b3e19 SP |
738 | /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */ |
739 | ||
740 | static poly_bb_p | |
741 | find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb) | |
742 | { | |
743 | bb_pbb_def tmp; | |
744 | PTR *slot; | |
745 | ||
746 | tmp.bb = bb; | |
747 | slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT); | |
748 | ||
749 | if (slot && *slot) | |
750 | return ((bb_pbb_def *) *slot)->pbb; | |
751 | ||
752 | return NULL; | |
753 | } | |
754 | ||
755 | /* Check data dependency in LOOP at scattering level LEVEL. | |
756 | BB_PBB_MAPPING is a basic_block and it's related poly_bb_p | |
757 | mapping. */ | |
758 | ||
759 | static bool | |
760 | dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level) | |
761 | { | |
762 | unsigned i,j; | |
763 | basic_block *bbs = get_loop_body_in_dom_order (loop); | |
764 | ||
765 | for (i = 0; i < loop->num_nodes; i++) | |
766 | { | |
767 | poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]); | |
768 | ||
769 | if (pbb1 == NULL) | |
770 | continue; | |
771 | ||
772 | for (j = 0; j < loop->num_nodes; j++) | |
773 | { | |
774 | poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]); | |
775 | ||
776 | if (pbb2 == NULL) | |
777 | continue; | |
778 | ||
779 | if (dependency_between_pbbs_p (pbb1, pbb2, level)) | |
780 | { | |
781 | free (bbs); | |
782 | return true; | |
783 | } | |
784 | } | |
785 | } | |
786 | ||
787 | free (bbs); | |
788 | ||
789 | return false; | |
790 | } | |
791 | ||
e1f9c1cd | 792 | static edge |
9fa29a09 SP |
793 | translate_clast (sese, loop_p, struct clast_stmt *, edge, htab_t, |
794 | VEC (tree, heap) **, htab_t, htab_t, int, htab_t); | |
2abae5f1 | 795 | |
e1f9c1cd TG |
796 | /* Translates a clast user statement STMT to gimple. |
797 | ||
798 | - REGION is the sese region we used to generate the scop. | |
2abae5f1 | 799 | - NEXT_E is the edge where new generated code should be attached. |
9fa29a09 | 800 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
2abae5f1 SP |
801 | - RENAME_MAP contains a set of tuples of new names associated to |
802 | the original variables names. | |
803 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
e1f9c1cd TG |
804 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in |
805 | the sese region. */ | |
806 | static edge | |
9016166f | 807 | translate_clast_user (sese region, struct clast_user_stmt *stmt, edge next_e, |
e1f9c1cd | 808 | htab_t rename_map, VEC (tree, heap) **newivs, |
9016166f | 809 | htab_t newivs_index, htab_t bb_pbb_mapping, |
e1f9c1cd TG |
810 | htab_t params_index) |
811 | { | |
9fa29a09 SP |
812 | gimple_bb_p gbb; |
813 | basic_block new_bb; | |
9016166f | 814 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement); |
9fa29a09 | 815 | gbb = PBB_BLACK_BOX (pbb); |
e1f9c1cd TG |
816 | |
817 | if (GBB_BB (gbb) == ENTRY_BLOCK_PTR) | |
818 | return next_e; | |
819 | ||
9016166f TG |
820 | build_iv_mapping (rename_map, region, *newivs, newivs_index, stmt, |
821 | params_index); | |
e1f9c1cd TG |
822 | next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), region, |
823 | next_e, rename_map); | |
9fa29a09 SP |
824 | new_bb = next_e->src; |
825 | mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping); | |
e1f9c1cd | 826 | update_ssa (TODO_update_ssa); |
fd2d813d | 827 | |
9016166f | 828 | return next_e; |
e1f9c1cd TG |
829 | } |
830 | ||
0dd91484 | 831 | /* Creates a new if region protecting the loop to be executed, if the execution |
7c246f5e | 832 | count is zero (lb > ub). */ |
0dd91484 TG |
833 | static edge |
834 | graphite_create_new_loop_guard (sese region, edge entry_edge, | |
835 | struct clast_for *stmt, | |
836 | VEC (tree, heap) *newivs, | |
837 | htab_t newivs_index, htab_t params_index) | |
838 | { | |
839 | tree cond_expr; | |
840 | edge exit_edge; | |
841 | tree type = gcc_type_for_iv_of_clast_loop (stmt); | |
842 | tree lb = clast_to_gcc_expression (type, stmt->LB, region, newivs, | |
843 | newivs_index, params_index); | |
844 | tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs, | |
845 | newivs_index, params_index); | |
846 | ||
847 | /* XXX: Adding +1 and using LT_EXPR helps with loop latches that have a | |
7c246f5e TG |
848 | loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes |
849 | 2^{32|64}, and the condition lb <= ub is true, even if we do not want this. | |
850 | However lb < ub + 1 is false, as expected. | |
851 | There might be a problem with cases where ub is 2^32. */ | |
0dd91484 TG |
852 | tree one; |
853 | Value gmp_one; | |
854 | value_init (gmp_one); | |
855 | value_set_si (gmp_one, 1); | |
856 | one = gmp_cst_to_tree (type, gmp_one); | |
857 | value_clear (gmp_one); | |
858 | ||
859 | ub = fold_build2 (PLUS_EXPR, type, ub, one); | |
860 | cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub); | |
861 | ||
862 | exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); | |
863 | ||
864 | return exit_edge; | |
865 | } | |
866 | ||
867 | ||
868 | /* Create the loop for a clast for statement. | |
e1f9c1cd TG |
869 | |
870 | - REGION is the sese region we used to generate the scop. | |
871 | - NEXT_E is the edge where new generated code should be attached. | |
e1f9c1cd TG |
872 | - RENAME_MAP contains a set of tuples of new names associated to |
873 | the original variables names. | |
874 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
875 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
876 | the sese region. */ | |
877 | static edge | |
e1496917 SP |
878 | translate_clast_for_loop (sese region, loop_p context_loop, |
879 | struct clast_for *stmt, edge next_e, | |
880 | htab_t rename_map, VEC (tree, heap) **newivs, | |
881 | htab_t newivs_index, htab_t bb_pbb_mapping, | |
882 | int level, htab_t params_index) | |
e1f9c1cd | 883 | { |
9fa29a09 SP |
884 | struct loop *loop = graphite_create_new_loop (region, next_e, stmt, |
885 | context_loop, newivs, | |
886 | newivs_index, params_index); | |
e1f9c1cd | 887 | edge last_e = single_exit (loop); |
9fa29a09 SP |
888 | edge to_body = single_succ_edge (loop->header); |
889 | basic_block after = to_body->dest; | |
e1f9c1cd TG |
890 | |
891 | /* Create a basic block for loop close phi nodes. */ | |
892 | last_e = single_succ_edge (split_edge (last_e)); | |
9fa29a09 SP |
893 | |
894 | /* Translate the body of the loop. */ | |
895 | next_e = translate_clast (region, loop, stmt->body, to_body, rename_map, | |
896 | newivs, newivs_index, bb_pbb_mapping, level + 1, | |
897 | params_index); | |
898 | redirect_edge_succ_nodup (next_e, after); | |
899 | set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); | |
900 | ||
901 | /* Remove from rename_map all the tuples containing variables | |
902 | defined in loop's body. */ | |
e1f9c1cd TG |
903 | insert_loop_close_phis (rename_map, loop); |
904 | ||
9fa29a09 SP |
905 | if (flag_loop_parallelize_all |
906 | && !dependency_in_loop_p (loop, bb_pbb_mapping, | |
907 | get_scattering_level (level))) | |
908 | loop->can_be_parallel = true; | |
e1f9c1cd | 909 | |
9016166f | 910 | return last_e; |
e1f9c1cd TG |
911 | } |
912 | ||
0dd91484 | 913 | /* Translates a clast for statement STMT to gimple. First a guard is created |
7c246f5e TG |
914 | protecting the loop, if it is executed zero times. In this guard we create |
915 | the real loop structure. | |
0dd91484 TG |
916 | |
917 | - REGION is the sese region we used to generate the scop. | |
918 | - NEXT_E is the edge where new generated code should be attached. | |
919 | - RENAME_MAP contains a set of tuples of new names associated to | |
920 | the original variables names. | |
921 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
922 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
923 | the sese region. */ | |
924 | static edge | |
e1496917 SP |
925 | translate_clast_for (sese region, loop_p context_loop, struct clast_for *stmt, |
926 | edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, | |
9fa29a09 | 927 | htab_t newivs_index, htab_t bb_pbb_mapping, int level, |
0dd91484 TG |
928 | htab_t params_index) |
929 | { | |
930 | edge last_e = graphite_create_new_loop_guard (region, next_e, stmt, *newivs, | |
931 | newivs_index, params_index); | |
932 | ||
933 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); | |
934 | edge false_e = get_false_edge_from_guard_bb (next_e->dest); | |
935 | edge exit_true_e = single_succ_edge (true_e->dest); | |
936 | edge exit_false_e = single_succ_edge (false_e->dest); | |
937 | ||
938 | htab_t before_guard = htab_create (10, rename_map_elt_info, | |
939 | eq_rename_map_elts, free); | |
940 | htab_traverse (rename_map, copy_renames, before_guard); | |
941 | ||
e1496917 SP |
942 | next_e = translate_clast_for_loop (region, context_loop, stmt, true_e, |
943 | rename_map, newivs, | |
9fa29a09 | 944 | newivs_index, bb_pbb_mapping, level, |
0dd91484 TG |
945 | params_index); |
946 | ||
947 | insert_guard_phis (last_e->src, exit_true_e, exit_false_e, | |
948 | before_guard, rename_map); | |
949 | ||
950 | htab_delete (before_guard); | |
951 | ||
952 | return last_e; | |
953 | } | |
954 | ||
e1f9c1cd TG |
955 | /* Translates a clast guard statement STMT to gimple. |
956 | ||
957 | - REGION is the sese region we used to generate the scop. | |
958 | - NEXT_E is the edge where new generated code should be attached. | |
9fa29a09 | 959 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
e1f9c1cd TG |
960 | - RENAME_MAP contains a set of tuples of new names associated to |
961 | the original variables names. | |
962 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. | |
963 | - PARAMS_INDEX connects the cloog parameters with the gimple parameters in | |
964 | the sese region. */ | |
965 | static edge | |
9fa29a09 SP |
966 | translate_clast_guard (sese region, loop_p context_loop, |
967 | struct clast_guard *stmt, edge next_e, | |
9016166f | 968 | htab_t rename_map, VEC (tree, heap) **newivs, |
9fa29a09 | 969 | htab_t newivs_index, htab_t bb_pbb_mapping, int level, |
9016166f TG |
970 | htab_t params_index) |
971 | { | |
972 | edge last_e = graphite_create_new_guard (region, next_e, stmt, *newivs, | |
973 | newivs_index, params_index); | |
974 | ||
e1f9c1cd TG |
975 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); |
976 | edge false_e = get_false_edge_from_guard_bb (next_e->dest); | |
977 | edge exit_true_e = single_succ_edge (true_e->dest); | |
978 | edge exit_false_e = single_succ_edge (false_e->dest); | |
9016166f | 979 | |
e1f9c1cd TG |
980 | htab_t before_guard = htab_create (10, rename_map_elt_info, |
981 | eq_rename_map_elts, free); | |
e1f9c1cd | 982 | htab_traverse (rename_map, copy_renames, before_guard); |
9016166f | 983 | |
9fa29a09 | 984 | next_e = translate_clast (region, context_loop, stmt->then, true_e, |
9016166f | 985 | rename_map, newivs, newivs_index, bb_pbb_mapping, |
9fa29a09 | 986 | level, params_index); |
9016166f | 987 | |
e1f9c1cd TG |
988 | insert_guard_phis (last_e->src, exit_true_e, exit_false_e, |
989 | before_guard, rename_map); | |
990 | ||
991 | htab_delete (before_guard); | |
e1f9c1cd | 992 | |
9016166f | 993 | return last_e; |
e1f9c1cd | 994 | } |
2abae5f1 | 995 | |
e1f9c1cd TG |
996 | /* Translates a CLAST statement STMT to GCC representation in the |
997 | context of a SESE. | |
998 | ||
999 | - NEXT_E is the edge where new generated code should be attached. | |
9fa29a09 | 1000 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
e1f9c1cd TG |
1001 | - RENAME_MAP contains a set of tuples of new names associated to |
1002 | the original variables names. | |
1003 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ | |
2abae5f1 | 1004 | static edge |
9fa29a09 | 1005 | translate_clast (sese region, loop_p context_loop, struct clast_stmt *stmt, |
e1f9c1cd | 1006 | edge next_e, htab_t rename_map, VEC (tree, heap) **newivs, |
9fa29a09 | 1007 | htab_t newivs_index, htab_t bb_pbb_mapping, int level, |
7a521ff2 | 1008 | htab_t params_index) |
2abae5f1 | 1009 | { |
e3f81db1 | 1010 | if (!stmt) |
2abae5f1 SP |
1011 | return next_e; |
1012 | ||
1013 | if (CLAST_STMT_IS_A (stmt, stmt_root)) | |
9016166f | 1014 | ; /* Do nothing. */ |
2abae5f1 | 1015 | |
9016166f TG |
1016 | else if (CLAST_STMT_IS_A (stmt, stmt_user)) |
1017 | next_e = translate_clast_user (region, (struct clast_user_stmt *) stmt, | |
1018 | next_e, rename_map, newivs, newivs_index, | |
1019 | bb_pbb_mapping, params_index); | |
2abae5f1 | 1020 | |
9016166f | 1021 | else if (CLAST_STMT_IS_A (stmt, stmt_for)) |
9fa29a09 SP |
1022 | next_e = translate_clast_for (region, context_loop, |
1023 | (struct clast_for *) stmt, next_e, | |
1024 | rename_map, newivs, newivs_index, | |
1025 | bb_pbb_mapping, level, params_index); | |
2abae5f1 | 1026 | |
9016166f | 1027 | else if (CLAST_STMT_IS_A (stmt, stmt_guard)) |
9fa29a09 SP |
1028 | next_e = translate_clast_guard (region, context_loop, |
1029 | (struct clast_guard *) stmt, next_e, | |
9016166f | 1030 | rename_map, newivs, newivs_index, |
9fa29a09 | 1031 | bb_pbb_mapping, level, params_index); |
9016166f TG |
1032 | |
1033 | else if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
9fa29a09 SP |
1034 | next_e = translate_clast (region, context_loop, |
1035 | ((struct clast_block *) stmt)->body, | |
9016166f | 1036 | next_e, rename_map, newivs, newivs_index, |
9fa29a09 | 1037 | bb_pbb_mapping, level, params_index); |
9016166f TG |
1038 | else |
1039 | gcc_unreachable(); | |
2abae5f1 | 1040 | |
9016166f TG |
1041 | recompute_all_dominators (); |
1042 | graphite_verify (); | |
1043 | ||
9fa29a09 SP |
1044 | return translate_clast (region, context_loop, stmt->next, next_e, |
1045 | rename_map, newivs, newivs_index, | |
1046 | bb_pbb_mapping, level, params_index); | |
2abae5f1 SP |
1047 | } |
1048 | ||
1049 | /* Returns the first cloog name used in EXPR. */ | |
1050 | ||
1051 | static const char * | |
1052 | find_cloog_iv_in_expr (struct clast_expr *expr) | |
1053 | { | |
1054 | struct clast_term *term = (struct clast_term *) expr; | |
bd7742f8 SP |
1055 | struct clast_reduction *red; |
1056 | int i; | |
2abae5f1 SP |
1057 | |
1058 | if (expr->type == expr_term) | |
1059 | return term->var; | |
1060 | ||
bd7742f8 SP |
1061 | if (expr->type != expr_red) |
1062 | return NULL; | |
2abae5f1 | 1063 | |
bd7742f8 SP |
1064 | red = (struct clast_reduction *) expr; |
1065 | for (i = 0; i < red->n; i++) | |
1066 | { | |
1067 | const char *res = find_cloog_iv_in_expr (red->elts[i]); | |
2abae5f1 | 1068 | |
bd7742f8 SP |
1069 | if (res) |
1070 | return res; | |
2abae5f1 SP |
1071 | } |
1072 | ||
1073 | return NULL; | |
1074 | } | |
1075 | ||
bd7742f8 SP |
1076 | /* Build for USER_STMT a map between the CLAST induction variables and |
1077 | the corresponding GCC old induction variables. This information is | |
1078 | stored on each GRAPHITE_BB. */ | |
2abae5f1 SP |
1079 | |
1080 | static void | |
1081 | compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt) | |
1082 | { | |
1083 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
1084 | struct clast_stmt *t; | |
1085 | int index = 0; | |
1086 | ||
1087 | for (t = user_stmt->substitutions; t; t = t->next, index++) | |
1088 | { | |
1089 | PTR *slot; | |
1090 | struct ivtype_map_elt_s tmp; | |
b8698a0f | 1091 | struct clast_expr *expr = (struct clast_expr *) |
2abae5f1 SP |
1092 | ((struct clast_assignment *)t)->RHS; |
1093 | ||
1094 | /* Create an entry (clast_var, type). */ | |
1095 | tmp.cloog_iv = find_cloog_iv_in_expr (expr); | |
1096 | if (!tmp.cloog_iv) | |
1097 | continue; | |
1098 | ||
1099 | slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); | |
1100 | ||
556afcdc | 1101 | if (slot && !*slot) |
2abae5f1 SP |
1102 | { |
1103 | tree oldiv = pbb_to_depth_to_oldiv (pbb, index); | |
68d3ff90 | 1104 | tree type = TREE_TYPE (oldiv); |
2abae5f1 SP |
1105 | *slot = new_ivtype_map_elt (tmp.cloog_iv, type); |
1106 | } | |
1107 | } | |
1108 | } | |
1109 | ||
1110 | /* Walk the CLAST tree starting from STMT and build for each | |
1111 | clast_user_stmt a map between the CLAST induction variables and the | |
1112 | corresponding GCC old induction variables. This information is | |
1113 | stored on each GRAPHITE_BB. */ | |
1114 | ||
1115 | static void | |
1116 | compute_cloog_iv_types (struct clast_stmt *stmt) | |
1117 | { | |
1118 | if (!stmt) | |
1119 | return; | |
1120 | ||
1121 | if (CLAST_STMT_IS_A (stmt, stmt_root)) | |
1122 | goto next; | |
1123 | ||
1124 | if (CLAST_STMT_IS_A (stmt, stmt_user)) | |
1125 | { | |
1126 | CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; | |
1127 | poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs); | |
1128 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); | |
1129 | ||
1130 | if (!GBB_CLOOG_IV_TYPES (gbb)) | |
1131 | GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info, | |
1132 | eq_ivtype_map_elts, free); | |
1133 | ||
1134 | compute_cloog_iv_types_1 (pbb, (struct clast_user_stmt *) stmt); | |
1135 | goto next; | |
1136 | } | |
1137 | ||
1138 | if (CLAST_STMT_IS_A (stmt, stmt_for)) | |
1139 | { | |
1140 | struct clast_stmt *s = ((struct clast_for *) stmt)->body; | |
1141 | compute_cloog_iv_types (s); | |
1142 | goto next; | |
1143 | } | |
1144 | ||
1145 | if (CLAST_STMT_IS_A (stmt, stmt_guard)) | |
1146 | { | |
1147 | struct clast_stmt *s = ((struct clast_guard *) stmt)->then; | |
1148 | compute_cloog_iv_types (s); | |
1149 | goto next; | |
1150 | } | |
1151 | ||
1152 | if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
1153 | { | |
1154 | struct clast_stmt *s = ((struct clast_block *) stmt)->body; | |
1155 | compute_cloog_iv_types (s); | |
1156 | goto next; | |
1157 | } | |
1158 | ||
1159 | gcc_unreachable (); | |
1160 | ||
1161 | next: | |
1162 | compute_cloog_iv_types (stmt->next); | |
1163 | } | |
1164 | ||
1165 | /* Free the SCATTERING domain list. */ | |
1166 | ||
1167 | static void | |
1168 | free_scattering (CloogDomainList *scattering) | |
1169 | { | |
1170 | while (scattering) | |
1171 | { | |
1172 | CloogDomain *dom = cloog_domain (scattering); | |
1173 | CloogDomainList *next = cloog_next_domain (scattering); | |
1174 | ||
1175 | cloog_domain_free (dom); | |
1176 | free (scattering); | |
1177 | scattering = next; | |
1178 | } | |
1179 | } | |
1180 | ||
1181 | /* Initialize Cloog's parameter names from the names used in GIMPLE. | |
1182 | Initialize Cloog's iterator names, using 'graphite_iterator_%d' | |
1183 | from 0 to scop_nb_loops (scop). */ | |
1184 | ||
1185 | static void | |
1186 | initialize_cloog_names (scop_p scop, CloogProgram *prog) | |
1187 | { | |
1188 | sese region = SCOP_REGION (scop); | |
1189 | int i; | |
1190 | int nb_iterators = scop_max_loop_depth (scop); | |
1191 | int nb_scattering = cloog_program_nb_scattdims (prog); | |
7a521ff2 | 1192 | int nb_parameters = VEC_length (tree, SESE_PARAMS (region)); |
2abae5f1 SP |
1193 | char **iterators = XNEWVEC (char *, nb_iterators * 2); |
1194 | char **scattering = XNEWVEC (char *, nb_scattering); | |
7a521ff2 | 1195 | char **parameters= XNEWVEC (char *, nb_parameters); |
2abae5f1 SP |
1196 | |
1197 | cloog_program_set_names (prog, cloog_names_malloc ()); | |
7a521ff2 TG |
1198 | |
1199 | for (i = 0; i < nb_parameters; i++) | |
1200 | { | |
1201 | tree param = VEC_index (tree, SESE_PARAMS(region), i); | |
1202 | const char *name = get_name (param); | |
1203 | int len; | |
1204 | ||
1205 | if (!name) | |
1206 | name = "T"; | |
1207 | ||
1208 | len = strlen (name); | |
1209 | len += 17; | |
1210 | parameters[i] = XNEWVEC (char, len + 1); | |
1211 | snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param)); | |
1212 | } | |
1213 | ||
1214 | cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters); | |
1215 | cloog_names_set_parameters (cloog_program_names (prog), parameters); | |
2abae5f1 SP |
1216 | |
1217 | for (i = 0; i < nb_iterators; i++) | |
1218 | { | |
1219 | int len = 4 + 16; | |
1220 | iterators[i] = XNEWVEC (char, len); | |
1221 | snprintf (iterators[i], len, "git_%d", i); | |
1222 | } | |
1223 | ||
1224 | cloog_names_set_nb_iterators (cloog_program_names (prog), | |
1225 | nb_iterators); | |
1226 | cloog_names_set_iterators (cloog_program_names (prog), | |
1227 | iterators); | |
1228 | ||
1229 | for (i = 0; i < nb_scattering; i++) | |
1230 | { | |
1231 | int len = 5 + 16; | |
1232 | scattering[i] = XNEWVEC (char, len); | |
1233 | snprintf (scattering[i], len, "scat_%d", i); | |
1234 | } | |
1235 | ||
1236 | cloog_names_set_nb_scattering (cloog_program_names (prog), | |
1237 | nb_scattering); | |
1238 | cloog_names_set_scattering (cloog_program_names (prog), | |
1239 | scattering); | |
1240 | } | |
1241 | ||
1242 | /* Build cloog program for SCoP. */ | |
1243 | ||
1244 | static void | |
1245 | build_cloog_prog (scop_p scop, CloogProgram *prog) | |
1246 | { | |
1247 | int i; | |
1248 | int max_nb_loops = scop_max_loop_depth (scop); | |
1249 | poly_bb_p pbb; | |
1250 | CloogLoop *loop_list = NULL; | |
1251 | CloogBlockList *block_list = NULL; | |
1252 | CloogDomainList *scattering = NULL; | |
1253 | int nbs = 2 * max_nb_loops + 1; | |
1254 | int *scaldims; | |
1255 | ||
1256 | cloog_program_set_context | |
1257 | (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop))); | |
1258 | nbs = unify_scattering_dimensions (scop); | |
1259 | scaldims = (int *) xmalloc (nbs * (sizeof (int))); | |
1260 | cloog_program_set_nb_scattdims (prog, nbs); | |
1261 | initialize_cloog_names (scop, prog); | |
1262 | ||
1263 | for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) | |
1264 | { | |
1265 | CloogStatement *stmt; | |
1266 | CloogBlock *block; | |
1267 | ||
1268 | /* Dead code elimination: when the domain of a PBB is empty, | |
1269 | don't generate code for the PBB. */ | |
1270 | if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb))) | |
1271 | continue; | |
1272 | ||
1273 | /* Build the new statement and its block. */ | |
d48e288d | 1274 | stmt = cloog_statement_alloc (pbb_index (pbb)); |
2abae5f1 SP |
1275 | block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb)); |
1276 | cloog_statement_set_usr (stmt, pbb); | |
1277 | ||
1278 | /* Build loop list. */ | |
1279 | { | |
1280 | CloogLoop *new_loop_list = cloog_loop_malloc (); | |
1281 | cloog_loop_set_next (new_loop_list, loop_list); | |
1282 | cloog_loop_set_domain | |
1283 | (new_loop_list, | |
1284 | new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb))); | |
1285 | cloog_loop_set_block (new_loop_list, block); | |
1286 | loop_list = new_loop_list; | |
1287 | } | |
1288 | ||
1289 | /* Build block list. */ | |
1290 | { | |
1291 | CloogBlockList *new_block_list = cloog_block_list_malloc (); | |
1292 | ||
1293 | cloog_block_list_set_next (new_block_list, block_list); | |
1294 | cloog_block_list_set_block (new_block_list, block); | |
1295 | block_list = new_block_list; | |
1296 | } | |
1297 | ||
1298 | /* Build scattering list. */ | |
1299 | { | |
1300 | /* XXX: Replace with cloog_domain_list_alloc(), when available. */ | |
1301 | CloogDomainList *new_scattering | |
1302 | = (CloogDomainList *) xmalloc (sizeof (CloogDomainList)); | |
1303 | ppl_Polyhedron_t scat; | |
1304 | CloogDomain *dom; | |
1305 | ||
1306 | scat = PBB_TRANSFORMED_SCATTERING (pbb); | |
1307 | dom = new_Cloog_Domain_from_ppl_Polyhedron (scat); | |
1308 | ||
1309 | cloog_set_next_domain (new_scattering, scattering); | |
1310 | cloog_set_domain (new_scattering, dom); | |
1311 | scattering = new_scattering; | |
1312 | } | |
1313 | } | |
1314 | ||
1315 | cloog_program_set_loop (prog, loop_list); | |
1316 | cloog_program_set_blocklist (prog, block_list); | |
1317 | ||
1318 | for (i = 0; i < nbs; i++) | |
1319 | scaldims[i] = 0 ; | |
1320 | ||
1321 | cloog_program_set_scaldims (prog, scaldims); | |
1322 | ||
1323 | /* Extract scalar dimensions to simplify the code generation problem. */ | |
1324 | cloog_program_extract_scalars (prog, scattering); | |
1325 | ||
1326 | /* Apply scattering. */ | |
1327 | cloog_program_scatter (prog, scattering); | |
1328 | free_scattering (scattering); | |
1329 | ||
1330 | /* Iterators corresponding to scalar dimensions have to be extracted. */ | |
1331 | cloog_names_scalarize (cloog_program_names (prog), nbs, | |
1332 | cloog_program_scaldims (prog)); | |
1333 | ||
1334 | /* Free blocklist. */ | |
1335 | { | |
1336 | CloogBlockList *next = cloog_program_blocklist (prog); | |
1337 | ||
1338 | while (next) | |
1339 | { | |
1340 | CloogBlockList *toDelete = next; | |
1341 | next = cloog_block_list_next (next); | |
1342 | cloog_block_list_set_next (toDelete, NULL); | |
1343 | cloog_block_list_set_block (toDelete, NULL); | |
1344 | cloog_block_list_free (toDelete); | |
1345 | } | |
1346 | cloog_program_set_blocklist (prog, NULL); | |
1347 | } | |
1348 | } | |
1349 | ||
1350 | /* Return the options that will be used in GLOOG. */ | |
1351 | ||
1352 | static CloogOptions * | |
1353 | set_cloog_options (void) | |
1354 | { | |
1355 | CloogOptions *options = cloog_options_malloc (); | |
1356 | ||
1357 | /* Change cloog output language to C. If we do use FORTRAN instead, cloog | |
1358 | will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if | |
1359 | we pass an incomplete program to cloog. */ | |
1360 | options->language = LANGUAGE_C; | |
1361 | ||
1362 | /* Enable complex equality spreading: removes dummy statements | |
1363 | (assignments) in the generated code which repeats the | |
1364 | substitution equations for statements. This is useless for | |
1365 | GLooG. */ | |
1366 | options->esp = 1; | |
1367 | ||
1368 | /* Enable C pretty-printing mode: normalizes the substitution | |
1369 | equations for statements. */ | |
1370 | options->cpp = 1; | |
1371 | ||
1372 | /* Allow cloog to build strides with a stride width different to one. | |
1373 | This example has stride = 4: | |
1374 | ||
1375 | for (i = 0; i < 20; i += 4) | |
1376 | A */ | |
1377 | options->strides = 1; | |
1378 | ||
1379 | /* Disable optimizations and make cloog generate source code closer to the | |
1380 | input. This is useful for debugging, but later we want the optimized | |
1381 | code. | |
1382 | ||
1383 | XXX: We can not disable optimizations, as loop blocking is not working | |
1384 | without them. */ | |
1385 | if (0) | |
1386 | { | |
1387 | options->f = -1; | |
1388 | options->l = INT_MAX; | |
1389 | } | |
1390 | ||
1391 | return options; | |
1392 | } | |
1393 | ||
1394 | /* Prints STMT to STDERR. */ | |
1395 | ||
1396 | void | |
1397 | print_clast_stmt (FILE *file, struct clast_stmt *stmt) | |
1398 | { | |
1399 | CloogOptions *options = set_cloog_options (); | |
1400 | ||
1401 | pprint (file, stmt, 0, options); | |
1402 | cloog_options_free (options); | |
1403 | } | |
1404 | ||
1405 | /* Prints STMT to STDERR. */ | |
1406 | ||
1407 | void | |
1408 | debug_clast_stmt (struct clast_stmt *stmt) | |
1409 | { | |
1410 | print_clast_stmt (stderr, stmt); | |
1411 | } | |
1412 | ||
1413 | /* Translate SCOP to a CLooG program and clast. These two | |
1414 | representations should be freed together: a clast cannot be used | |
1415 | without a program. */ | |
1416 | ||
1417 | cloog_prog_clast | |
1418 | scop_to_clast (scop_p scop) | |
1419 | { | |
1420 | CloogOptions *options = set_cloog_options (); | |
1421 | cloog_prog_clast pc; | |
1422 | ||
1423 | /* Connect new cloog prog generation to graphite. */ | |
1424 | pc.prog = cloog_program_malloc (); | |
1425 | build_cloog_prog (scop, pc.prog); | |
1426 | pc.prog = cloog_program_generate (pc.prog, options); | |
1427 | pc.stmt = cloog_clast_create (pc.prog, options); | |
1428 | ||
1429 | cloog_options_free (options); | |
1430 | return pc; | |
1431 | } | |
1432 | ||
1433 | /* Prints to FILE the code generated by CLooG for SCOP. */ | |
1434 | ||
1435 | void | |
1436 | print_generated_program (FILE *file, scop_p scop) | |
1437 | { | |
1438 | CloogOptions *options = set_cloog_options (); | |
1439 | cloog_prog_clast pc = scop_to_clast (scop); | |
1440 | ||
1441 | fprintf (file, " (prog: \n"); | |
1442 | cloog_program_print (file, pc.prog); | |
1443 | fprintf (file, " )\n"); | |
1444 | ||
1445 | fprintf (file, " (clast: \n"); | |
1446 | pprint (file, pc.stmt, 0, options); | |
1447 | fprintf (file, " )\n"); | |
1448 | ||
1449 | cloog_options_free (options); | |
1450 | cloog_clast_free (pc.stmt); | |
1451 | cloog_program_free (pc.prog); | |
1452 | } | |
1453 | ||
1454 | /* Prints to STDERR the code generated by CLooG for SCOP. */ | |
1455 | ||
1456 | void | |
1457 | debug_generated_program (scop_p scop) | |
1458 | { | |
1459 | print_generated_program (stderr, scop); | |
1460 | } | |
1461 | ||
a7bf45de SP |
1462 | /* Add CLooG names to parameter index. The index is used to translate |
1463 | back from CLooG names to GCC trees. */ | |
7a521ff2 TG |
1464 | |
1465 | static void | |
1466 | create_params_index (htab_t index_table, CloogProgram *prog) { | |
1467 | CloogNames* names = cloog_program_names (prog); | |
1468 | int nb_parameters = cloog_names_nb_parameters (names); | |
1469 | char **parameters = cloog_names_parameters (names); | |
1470 | int i; | |
1471 | ||
1472 | for (i = 0; i < nb_parameters; i++) | |
1473 | save_clast_name_index (index_table, parameters[i], i); | |
1474 | } | |
1475 | ||
2abae5f1 SP |
1476 | /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for |
1477 | the given SCOP. Return true if code generation succeeded. | |
1478 | BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping. | |
1479 | */ | |
1480 | ||
1481 | bool | |
a1954f72 | 1482 | gloog (scop_p scop, VEC (scop_p, heap) *scops, htab_t bb_pbb_mapping) |
2abae5f1 | 1483 | { |
2abae5f1 | 1484 | VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10); |
9fa29a09 | 1485 | loop_p context_loop; |
2abae5f1 SP |
1486 | sese region = SCOP_REGION (scop); |
1487 | ifsese if_region = NULL; | |
7a521ff2 | 1488 | htab_t rename_map, newivs_index, params_index; |
87d4d0ee | 1489 | cloog_prog_clast pc; |
a1954f72 | 1490 | int i; |
87d4d0ee SP |
1491 | |
1492 | timevar_push (TV_GRAPHITE_CODE_GEN); | |
3c7c0158 | 1493 | gloog_error = false; |
87d4d0ee SP |
1494 | |
1495 | pc = scop_to_clast (scop); | |
2abae5f1 SP |
1496 | |
1497 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1498 | { | |
1499 | fprintf (dump_file, "\nCLAST generated by CLooG: \n"); | |
1500 | print_clast_stmt (dump_file, pc.stmt); | |
1501 | fprintf (dump_file, "\n"); | |
1502 | } | |
1503 | ||
2abae5f1 SP |
1504 | recompute_all_dominators (); |
1505 | graphite_verify (); | |
1506 | ||
1507 | if_region = move_sese_in_condition (region); | |
1508 | sese_insert_phis_for_liveouts (region, | |
1509 | if_region->region->exit->src, | |
1510 | if_region->false_region->exit, | |
1511 | if_region->true_region->exit); | |
2abae5f1 SP |
1512 | recompute_all_dominators (); |
1513 | graphite_verify (); | |
7a521ff2 | 1514 | |
9fa29a09 | 1515 | context_loop = SESE_ENTRY (region)->src->loop_father; |
2abae5f1 | 1516 | compute_cloog_iv_types (pc.stmt); |
2abae5f1 SP |
1517 | rename_map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free); |
1518 | newivs_index = htab_create (10, clast_name_index_elt_info, | |
1519 | eq_clast_name_indexes, free); | |
7a521ff2 TG |
1520 | params_index = htab_create (10, clast_name_index_elt_info, |
1521 | eq_clast_name_indexes, free); | |
1522 | ||
1523 | create_params_index (params_index, pc.prog); | |
2abae5f1 | 1524 | |
1124098b JJ |
1525 | translate_clast (region, context_loop, pc.stmt, |
1526 | if_region->true_region->entry, | |
1527 | rename_map, &newivs, newivs_index, | |
1528 | bb_pbb_mapping, 1, params_index); | |
2abae5f1 SP |
1529 | graphite_verify (); |
1530 | sese_adjust_liveout_phis (region, rename_map, | |
1531 | if_region->region->exit->src, | |
1532 | if_region->false_region->exit, | |
1533 | if_region->true_region->exit); | |
a7bf45de SP |
1534 | scev_reset_htab (); |
1535 | rename_nb_iterations (rename_map); | |
a1954f72 SP |
1536 | |
1537 | for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) | |
1538 | rename_sese_parameters (rename_map, SCOP_REGION (scop)); | |
1539 | ||
2abae5f1 SP |
1540 | recompute_all_dominators (); |
1541 | graphite_verify (); | |
1542 | ||
3c7c0158 SP |
1543 | if (gloog_error) |
1544 | set_ifsese_condition (if_region, integer_zero_node); | |
1545 | ||
8c54631d SP |
1546 | free (if_region->true_region); |
1547 | free (if_region->region); | |
1548 | free (if_region); | |
1549 | ||
2abae5f1 SP |
1550 | htab_delete (rename_map); |
1551 | htab_delete (newivs_index); | |
7a521ff2 | 1552 | htab_delete (params_index); |
2abae5f1 SP |
1553 | VEC_free (tree, heap, newivs); |
1554 | cloog_clast_free (pc.stmt); | |
1555 | cloog_program_free (pc.prog); | |
87d4d0ee SP |
1556 | timevar_pop (TV_GRAPHITE_CODE_GEN); |
1557 | ||
585b3e19 | 1558 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2abae5f1 | 1559 | { |
585b3e19 SP |
1560 | loop_p loop; |
1561 | loop_iterator li; | |
1562 | int num_no_dependency = 0; | |
2abae5f1 | 1563 | |
585b3e19 SP |
1564 | FOR_EACH_LOOP (li, loop, 0) |
1565 | if (loop->can_be_parallel) | |
1566 | num_no_dependency++; | |
2abae5f1 | 1567 | |
585b3e19 SP |
1568 | fprintf (dump_file, "\n%d loops carried no dependency.\n", |
1569 | num_no_dependency); | |
2abae5f1 SP |
1570 | } |
1571 | ||
3c7c0158 | 1572 | return !gloog_error; |
2abae5f1 SP |
1573 | } |
1574 | ||
1575 | #endif |