]>
Commit | Line | Data |
---|---|---|
2abae5f1 | 1 | /* Translation of CLAST (CLooG AST) to Gimple. |
23a5b65a | 2 | Copyright (C) 2009-2014 Free Software Foundation, Inc. |
2abae5f1 SP |
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" | |
33ad93b9 RG |
22 | |
23 | #ifdef HAVE_cloog | |
24 | #include <isl/set.h> | |
25 | #include <isl/map.h> | |
26 | #include <isl/union_map.h> | |
27 | #include <isl/list.h> | |
28 | #include <isl/constraint.h> | |
29 | #include <isl/ilp.h> | |
30 | #include <isl/aff.h> | |
31 | #include <cloog/cloog.h> | |
32 | #include <cloog/isl/domain.h> | |
33 | #endif | |
34 | ||
2abae5f1 SP |
35 | #include "system.h" |
36 | #include "coretypes.h" | |
32a73fc4 | 37 | #include "diagnostic-core.h" |
4d648807 | 38 | #include "tree.h" |
2fb9a547 AM |
39 | #include "basic-block.h" |
40 | #include "tree-ssa-alias.h" | |
41 | #include "internal-fn.h" | |
42 | #include "gimple-expr.h" | |
43 | #include "is-a.h" | |
18f429e2 | 44 | #include "gimple.h" |
5be5c238 | 45 | #include "gimple-iterator.h" |
18f429e2 | 46 | #include "gimplify-me.h" |
442b4905 | 47 | #include "gimple-ssa.h" |
e28030cf | 48 | #include "tree-ssa-loop-manip.h" |
442b4905 AM |
49 | #include "tree-ssa-loop.h" |
50 | #include "tree-into-ssa.h" | |
7a1c57d3 | 51 | #include "tree-pass.h" |
2abae5f1 SP |
52 | #include "cfgloop.h" |
53 | #include "tree-chrec.h" | |
54 | #include "tree-data-ref.h" | |
55 | #include "tree-scalar-evolution.h" | |
2abae5f1 SP |
56 | #include "sese.h" |
57 | ||
58 | #ifdef HAVE_cloog | |
59 | #include "cloog/cloog.h" | |
2abae5f1 | 60 | #include "graphite-poly.h" |
2abae5f1 | 61 | #include "graphite-clast-to-gimple.h" |
4a8fb1a1 | 62 | #include "graphite-htab.h" |
6886e444 RG |
63 | |
64 | typedef const struct clast_expr *clast_name_p; | |
2abae5f1 | 65 | |
7e2fe488 RO |
66 | #ifndef CLOOG_LANGUAGE_C |
67 | #define CLOOG_LANGUAGE_C LANGUAGE_C | |
68 | #endif | |
69 | ||
33ad93b9 RG |
70 | |
71 | /* Converts a GMP constant VAL to a tree and returns it. */ | |
72 | ||
73 | static tree | |
74 | gmp_cst_to_tree (tree type, mpz_t val) | |
75 | { | |
76 | tree t = type ? type : integer_type_node; | |
77 | mpz_t tmp; | |
33ad93b9 RG |
78 | |
79 | mpz_init (tmp); | |
80 | mpz_set (tmp, val); | |
807e902e | 81 | wide_int wi = wi::from_mpz (t, tmp, true); |
33ad93b9 RG |
82 | mpz_clear (tmp); |
83 | ||
807e902e | 84 | return wide_int_to_tree (t, wi); |
33ad93b9 RG |
85 | } |
86 | ||
87 | /* Sets RES to the min of V1 and V2. */ | |
88 | ||
89 | static void | |
90 | value_min (mpz_t res, mpz_t v1, mpz_t v2) | |
91 | { | |
92 | if (mpz_cmp (v1, v2) < 0) | |
93 | mpz_set (res, v1); | |
94 | else | |
95 | mpz_set (res, v2); | |
96 | } | |
97 | ||
98 | /* Sets RES to the max of V1 and V2. */ | |
99 | ||
100 | static void | |
101 | value_max (mpz_t res, mpz_t v1, mpz_t v2) | |
102 | { | |
103 | if (mpz_cmp (v1, v2) < 0) | |
104 | mpz_set (res, v2); | |
105 | else | |
106 | mpz_set (res, v1); | |
107 | } | |
108 | ||
109 | ||
3c7c0158 SP |
110 | /* This flag is set when an error occurred during the translation of |
111 | CLAST to Gimple. */ | |
112 | static bool gloog_error; | |
113 | ||
2abae5f1 SP |
114 | /* Verifies properties that GRAPHITE should maintain during translation. */ |
115 | ||
116 | static inline void | |
117 | graphite_verify (void) | |
118 | { | |
119 | #ifdef ENABLE_CHECKING | |
120 | verify_loop_structure (); | |
a3b9e73c | 121 | verify_loop_closed_ssa (true); |
2abae5f1 SP |
122 | #endif |
123 | } | |
124 | ||
7b1e9596 | 125 | /* Stores the INDEX in a vector and the loop nesting LEVEL for a given |
6c6c79a9 SP |
126 | clast NAME. BOUND_ONE and BOUND_TWO represent the exact lower and |
127 | upper bounds that can be inferred from the polyhedral representation. */ | |
7a521ff2 TG |
128 | |
129 | typedef struct clast_name_index { | |
130 | int index; | |
7b1e9596 | 131 | int level; |
6c6c79a9 | 132 | mpz_t bound_one, bound_two; |
7a521ff2 | 133 | const char *name; |
6886e444 RG |
134 | /* If free_name is set, the content of name was allocated by us and needs |
135 | to be freed. */ | |
136 | char *free_name; | |
7a521ff2 TG |
137 | } *clast_name_index_p; |
138 | ||
4a8fb1a1 LC |
139 | /* Helper for hashing clast_name_index. */ |
140 | ||
141 | struct clast_index_hasher | |
142 | { | |
143 | typedef clast_name_index value_type; | |
144 | typedef clast_name_index compare_type; | |
145 | static inline hashval_t hash (const value_type *); | |
146 | static inline bool equal (const value_type *, const compare_type *); | |
147 | static inline void remove (value_type *); | |
148 | }; | |
149 | ||
150 | /* Computes a hash function for database element E. */ | |
151 | ||
152 | inline hashval_t | |
153 | clast_index_hasher::hash (const value_type *e) | |
154 | { | |
155 | hashval_t hash = 0; | |
156 | ||
157 | int length = strlen (e->name); | |
158 | int i; | |
159 | ||
160 | for (i = 0; i < length; ++i) | |
161 | hash = hash | (e->name[i] << (i % 4)); | |
162 | ||
163 | return hash; | |
164 | } | |
165 | ||
166 | /* Compares database elements ELT1 and ELT2. */ | |
167 | ||
168 | inline bool | |
169 | clast_index_hasher::equal (const value_type *elt1, const compare_type *elt2) | |
170 | { | |
171 | return strcmp (elt1->name, elt2->name) == 0; | |
172 | } | |
173 | ||
174 | /* Free the memory taken by a clast_name_index struct. */ | |
175 | ||
176 | inline void | |
177 | clast_index_hasher::remove (value_type *c) | |
178 | { | |
179 | if (c->free_name) | |
180 | free (c->free_name); | |
181 | mpz_clear (c->bound_one); | |
182 | mpz_clear (c->bound_two); | |
183 | free (c); | |
184 | } | |
185 | ||
c203e8a7 | 186 | typedef hash_table<clast_index_hasher> clast_index_htab_type; |
4a8fb1a1 | 187 | |
7a521ff2 | 188 | /* Returns a pointer to a new element of type clast_name_index_p built |
6c6c79a9 | 189 | from NAME, INDEX, LEVEL, BOUND_ONE, and BOUND_TWO. */ |
7a521ff2 TG |
190 | |
191 | static inline clast_name_index_p | |
3d9784cb | 192 | new_clast_name_index (const char *name, int index, int level, |
6c6c79a9 | 193 | mpz_t bound_one, mpz_t bound_two) |
7a521ff2 TG |
194 | { |
195 | clast_name_index_p res = XNEW (struct clast_name_index); | |
6886e444 RG |
196 | char *new_name = XNEWVEC (char, strlen (name) + 1); |
197 | strcpy (new_name, name); | |
7a521ff2 | 198 | |
6886e444 RG |
199 | res->name = new_name; |
200 | res->free_name = new_name; | |
7b1e9596 | 201 | res->level = level; |
7a521ff2 | 202 | res->index = index; |
6c6c79a9 SP |
203 | mpz_init (res->bound_one); |
204 | mpz_init (res->bound_two); | |
205 | mpz_set (res->bound_one, bound_one); | |
206 | mpz_set (res->bound_two, bound_two); | |
7a521ff2 TG |
207 | return res; |
208 | } | |
209 | ||
7b1e9596 SP |
210 | /* For a given clast NAME, returns -1 if NAME is not in the |
211 | INDEX_TABLE, otherwise returns the loop level for the induction | |
212 | variable NAME, or if it is a parameter, the parameter number in the | |
213 | vector of parameters. */ | |
214 | ||
215 | static inline int | |
c203e8a7 | 216 | clast_name_to_level (clast_name_p name, clast_index_htab_type *index_table) |
7b1e9596 SP |
217 | { |
218 | struct clast_name_index tmp; | |
4a8fb1a1 | 219 | clast_name_index **slot; |
7b1e9596 | 220 | |
7b1e9596 SP |
221 | gcc_assert (name->type == clast_expr_name); |
222 | tmp.name = ((const struct clast_name *) name)->name; | |
6886e444 | 223 | tmp.free_name = NULL; |
7b1e9596 | 224 | |
c203e8a7 | 225 | slot = index_table->find_slot (&tmp, NO_INSERT); |
7b1e9596 SP |
226 | |
227 | if (slot && *slot) | |
228 | return ((struct clast_name_index *) *slot)->level; | |
229 | ||
230 | return -1; | |
231 | } | |
232 | ||
7a521ff2 TG |
233 | /* For a given clast NAME, returns -1 if it does not correspond to any |
234 | parameter, or otherwise, returns the index in the PARAMS or | |
235 | SCATTERING_DIMENSIONS vector. */ | |
236 | ||
237 | static inline int | |
c203e8a7 | 238 | clast_name_to_index (struct clast_name *name, clast_index_htab_type *index_table) |
7a521ff2 TG |
239 | { |
240 | struct clast_name_index tmp; | |
4a8fb1a1 | 241 | clast_name_index **slot; |
7a521ff2 | 242 | |
369e3430 | 243 | tmp.name = ((const struct clast_name *) name)->name; |
6886e444 | 244 | tmp.free_name = NULL; |
4431102b | 245 | |
c203e8a7 | 246 | slot = index_table->find_slot (&tmp, NO_INSERT); |
7a521ff2 TG |
247 | |
248 | if (slot && *slot) | |
4a8fb1a1 | 249 | return (*slot)->index; |
7a521ff2 TG |
250 | |
251 | return -1; | |
252 | } | |
253 | ||
6c6c79a9 SP |
254 | /* For a given clast NAME, initializes the lower and upper bounds BOUND_ONE |
255 | and BOUND_TWO stored in the INDEX_TABLE. Returns true when NAME has been | |
3d9784cb SP |
256 | found in the INDEX_TABLE, false otherwise. */ |
257 | ||
258 | static inline bool | |
c203e8a7 TS |
259 | clast_name_to_lb_ub (struct clast_name *name, |
260 | clast_index_htab_type *index_table, mpz_t bound_one, | |
261 | mpz_t bound_two) | |
3d9784cb SP |
262 | { |
263 | struct clast_name_index tmp; | |
4a8fb1a1 | 264 | clast_name_index **slot; |
3d9784cb | 265 | |
6886e444 RG |
266 | tmp.name = name->name; |
267 | tmp.free_name = NULL; | |
3d9784cb | 268 | |
c203e8a7 | 269 | slot = index_table->find_slot (&tmp, NO_INSERT); |
3d9784cb SP |
270 | |
271 | if (slot && *slot) | |
272 | { | |
6c6c79a9 SP |
273 | mpz_set (bound_one, ((struct clast_name_index *) *slot)->bound_one); |
274 | mpz_set (bound_two, ((struct clast_name_index *) *slot)->bound_two); | |
3d9784cb SP |
275 | return true; |
276 | } | |
277 | ||
278 | return false; | |
279 | } | |
280 | ||
7b1e9596 | 281 | /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */ |
7a521ff2 TG |
282 | |
283 | static inline void | |
c203e8a7 | 284 | save_clast_name_index (clast_index_htab_type *index_table, const char *name, |
6c6c79a9 | 285 | int index, int level, mpz_t bound_one, mpz_t bound_two) |
7a521ff2 TG |
286 | { |
287 | struct clast_name_index tmp; | |
4a8fb1a1 | 288 | clast_name_index **slot; |
7a521ff2 TG |
289 | |
290 | tmp.name = name; | |
6886e444 | 291 | tmp.free_name = NULL; |
c203e8a7 | 292 | slot = index_table->find_slot (&tmp, INSERT); |
7a521ff2 TG |
293 | |
294 | if (slot) | |
556afcdc | 295 | { |
04695783 | 296 | free (*slot); |
556afcdc | 297 | |
6c6c79a9 | 298 | *slot = new_clast_name_index (name, index, level, bound_one, bound_two); |
556afcdc | 299 | } |
7a521ff2 | 300 | } |
2abae5f1 SP |
301 | \f |
302 | ||
cf7eab7d SP |
303 | /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree |
304 | induction variable in NEWIVS. | |
305 | ||
306 | PARAMS_INDEX binds CLooG's parameter name to the index of the tree | |
307 | parameter in PARAMS. */ | |
308 | ||
309 | typedef struct ivs_params { | |
9771b263 | 310 | vec<tree> params, *newivs; |
c203e8a7 | 311 | clast_index_htab_type *newivs_index, *params_index; |
cf7eab7d SP |
312 | sese region; |
313 | } *ivs_params_p; | |
314 | ||
2abae5f1 SP |
315 | /* Returns the tree variable from the name NAME that was given in |
316 | Cloog representation. */ | |
317 | ||
318 | static tree | |
6886e444 | 319 | clast_name_to_gcc (struct clast_name *name, ivs_params_p ip) |
2abae5f1 SP |
320 | { |
321 | int index; | |
2abae5f1 | 322 | |
c203e8a7 | 323 | if (ip->params.exists () && ip->params_index) |
2abae5f1 | 324 | { |
cf7eab7d | 325 | index = clast_name_to_index (name, ip->params_index); |
2abae5f1 SP |
326 | |
327 | if (index >= 0) | |
9771b263 | 328 | return ip->params[index]; |
2abae5f1 SP |
329 | } |
330 | ||
c203e8a7 | 331 | gcc_assert (ip->newivs && ip->newivs_index); |
cf7eab7d | 332 | index = clast_name_to_index (name, ip->newivs_index); |
2abae5f1 SP |
333 | gcc_assert (index >= 0); |
334 | ||
9771b263 | 335 | return (*ip->newivs)[index]; |
2abae5f1 SP |
336 | } |
337 | ||
12b30e6d | 338 | /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */ |
2abae5f1 | 339 | |
bd32f344 | 340 | static tree |
12b30e6d | 341 | max_precision_type (tree type1, tree type2) |
bd32f344 | 342 | { |
2c2aceeb | 343 | enum machine_mode mode; |
12b30e6d SP |
344 | int p1, p2, precision; |
345 | tree type; | |
346 | ||
347 | if (POINTER_TYPE_P (type1)) | |
348 | return type1; | |
349 | ||
350 | if (POINTER_TYPE_P (type2)) | |
351 | return type2; | |
352 | ||
353 | if (TYPE_UNSIGNED (type1) | |
354 | && TYPE_UNSIGNED (type2)) | |
355 | return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2; | |
356 | ||
357 | p1 = TYPE_PRECISION (type1); | |
358 | p2 = TYPE_PRECISION (type2); | |
b8132a7d SP |
359 | |
360 | if (p1 > p2) | |
361 | precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1; | |
362 | else | |
363 | precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2; | |
364 | ||
2c2aceeb SP |
365 | if (precision > BITS_PER_WORD) |
366 | { | |
367 | gloog_error = true; | |
368 | return integer_type_node; | |
369 | } | |
370 | ||
371 | mode = smallest_mode_for_size (precision, MODE_INT); | |
372 | precision = GET_MODE_PRECISION (mode); | |
373 | type = build_nonstandard_integer_type (precision, false); | |
bd32f344 SP |
374 | |
375 | if (!type) | |
376 | { | |
377 | gloog_error = true; | |
378 | return integer_type_node; | |
379 | } | |
2c2aceeb | 380 | |
bd32f344 SP |
381 | return type; |
382 | } | |
383 | ||
2abae5f1 | 384 | static tree |
cf7eab7d | 385 | clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p); |
2abae5f1 SP |
386 | |
387 | /* Converts a Cloog reduction expression R with reduction operation OP | |
388 | to a GCC expression tree of type TYPE. */ | |
389 | ||
390 | static tree | |
391 | clast_to_gcc_expression_red (tree type, enum tree_code op, | |
cf7eab7d | 392 | struct clast_reduction *r, ivs_params_p ip) |
2abae5f1 SP |
393 | { |
394 | int i; | |
cf7eab7d | 395 | tree res = clast_to_gcc_expression (type, r->elts[0], ip); |
2abae5f1 SP |
396 | tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type; |
397 | ||
398 | for (i = 1; i < r->n; i++) | |
399 | { | |
cf7eab7d | 400 | tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip); |
2abae5f1 SP |
401 | res = fold_build2 (op, type, res, t); |
402 | } | |
403 | ||
404 | return res; | |
405 | } | |
406 | ||
407 | /* Converts a Cloog AST expression E back to a GCC expression tree of | |
408 | type TYPE. */ | |
409 | ||
410 | static tree | |
cf7eab7d | 411 | clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip) |
2abae5f1 SP |
412 | { |
413 | switch (e->type) | |
414 | { | |
6886e444 RG |
415 | case clast_expr_name: |
416 | { | |
417 | return clast_name_to_gcc ((struct clast_name *) e, ip); | |
418 | } | |
4431102b | 419 | case clast_expr_term: |
2abae5f1 SP |
420 | { |
421 | struct clast_term *t = (struct clast_term *) e; | |
422 | ||
423 | if (t->var) | |
424 | { | |
a0bb35c7 | 425 | if (mpz_cmp_si (t->val, 1) == 0) |
2abae5f1 | 426 | { |
6886e444 | 427 | tree name = clast_to_gcc_expression (type, t->var, ip); |
68d3ff90 TG |
428 | |
429 | if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) | |
0d82a1c8 | 430 | name = convert_to_ptrofftype (name); |
68d3ff90 TG |
431 | |
432 | name = fold_convert (type, name); | |
433 | return name; | |
2abae5f1 SP |
434 | } |
435 | ||
a0bb35c7 | 436 | else if (mpz_cmp_si (t->val, -1) == 0) |
2abae5f1 | 437 | { |
6886e444 | 438 | tree name = clast_to_gcc_expression (type, t->var, ip); |
68d3ff90 TG |
439 | |
440 | if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) | |
0d82a1c8 | 441 | name = convert_to_ptrofftype (name); |
68d3ff90 | 442 | |
2abae5f1 | 443 | name = fold_convert (type, name); |
68d3ff90 | 444 | |
2abae5f1 SP |
445 | return fold_build1 (NEGATE_EXPR, type, name); |
446 | } | |
447 | else | |
448 | { | |
6886e444 | 449 | tree name = clast_to_gcc_expression (type, t->var, ip); |
2abae5f1 | 450 | tree cst = gmp_cst_to_tree (type, t->val); |
68d3ff90 TG |
451 | |
452 | if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type)) | |
0d82a1c8 | 453 | name = convert_to_ptrofftype (name); |
68d3ff90 | 454 | |
2abae5f1 | 455 | name = fold_convert (type, name); |
68d3ff90 | 456 | |
3c7c0158 SP |
457 | if (!POINTER_TYPE_P (type)) |
458 | return fold_build2 (MULT_EXPR, type, cst, name); | |
459 | ||
460 | gloog_error = true; | |
461 | return cst; | |
2abae5f1 SP |
462 | } |
463 | } | |
464 | else | |
465 | return gmp_cst_to_tree (type, t->val); | |
466 | } | |
467 | ||
4431102b | 468 | case clast_expr_red: |
2abae5f1 SP |
469 | { |
470 | struct clast_reduction *r = (struct clast_reduction *) e; | |
471 | ||
472 | switch (r->type) | |
473 | { | |
474 | case clast_red_sum: | |
475 | return clast_to_gcc_expression_red | |
476 | (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR, | |
cf7eab7d | 477 | r, ip); |
2abae5f1 SP |
478 | |
479 | case clast_red_min: | |
cf7eab7d | 480 | return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip); |
2abae5f1 SP |
481 | |
482 | case clast_red_max: | |
cf7eab7d | 483 | return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip); |
2abae5f1 SP |
484 | |
485 | default: | |
486 | gcc_unreachable (); | |
487 | } | |
488 | break; | |
489 | } | |
490 | ||
4431102b | 491 | case clast_expr_bin: |
2abae5f1 SP |
492 | { |
493 | struct clast_binary *b = (struct clast_binary *) e; | |
494 | struct clast_expr *lhs = (struct clast_expr *) b->LHS; | |
cf7eab7d | 495 | tree tl = clast_to_gcc_expression (type, lhs, ip); |
2abae5f1 SP |
496 | tree tr = gmp_cst_to_tree (type, b->RHS); |
497 | ||
498 | switch (b->type) | |
499 | { | |
500 | case clast_bin_fdiv: | |
501 | return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr); | |
502 | ||
503 | case clast_bin_cdiv: | |
504 | return fold_build2 (CEIL_DIV_EXPR, type, tl, tr); | |
505 | ||
506 | case clast_bin_div: | |
507 | return fold_build2 (EXACT_DIV_EXPR, type, tl, tr); | |
508 | ||
509 | case clast_bin_mod: | |
510 | return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr); | |
511 | ||
512 | default: | |
513 | gcc_unreachable (); | |
514 | } | |
515 | } | |
516 | ||
517 | default: | |
518 | gcc_unreachable (); | |
519 | } | |
520 | ||
521 | return NULL_TREE; | |
522 | } | |
523 | ||
6c6c79a9 SP |
524 | /* Return a type that could represent the values between BOUND_ONE and |
525 | BOUND_TWO. */ | |
bd32f344 SP |
526 | |
527 | static tree | |
6c6c79a9 | 528 | type_for_interval (mpz_t bound_one, mpz_t bound_two) |
bd32f344 | 529 | { |
9b0d314a | 530 | bool unsigned_p; |
bd32f344 | 531 | tree type; |
d6abd6d8 | 532 | enum machine_mode mode; |
84f2ffea | 533 | int wider_precision; |
6c6c79a9 SP |
534 | int precision = MAX (mpz_sizeinbase (bound_one, 2), |
535 | mpz_sizeinbase (bound_two, 2)); | |
bd32f344 | 536 | |
d6abd6d8 SP |
537 | if (precision > BITS_PER_WORD) |
538 | { | |
539 | gloog_error = true; | |
540 | return integer_type_node; | |
541 | } | |
542 | ||
6c6c79a9 SP |
543 | if (mpz_cmp (bound_one, bound_two) <= 0) |
544 | unsigned_p = (mpz_sgn (bound_one) >= 0); | |
9b0d314a | 545 | else |
6c6c79a9 | 546 | unsigned_p = (mpz_sgn (bound_two) >= 0); |
c6060639 | 547 | |
d6abd6d8 | 548 | mode = smallest_mode_for_size (precision, MODE_INT); |
84f2ffea SP |
549 | wider_precision = GET_MODE_PRECISION (mode); |
550 | ||
551 | /* As we want to generate signed types as much as possible, try to | |
6c6c79a9 | 552 | fit the interval [bound_one, bound_two] in a signed type. For example, |
84f2ffea SP |
553 | supposing that we have the interval [0, 100], instead of |
554 | generating unsigned char, we want to generate a signed char. */ | |
555 | if (unsigned_p && precision < wider_precision) | |
556 | unsigned_p = false; | |
557 | ||
558 | type = build_nonstandard_integer_type (wider_precision, unsigned_p); | |
d6abd6d8 | 559 | |
bd32f344 SP |
560 | if (!type) |
561 | { | |
562 | gloog_error = true; | |
563 | return integer_type_node; | |
564 | } | |
565 | ||
566 | return type; | |
567 | } | |
568 | ||
569 | /* Return a type that could represent the integer value VAL, or | |
570 | otherwise return NULL_TREE. */ | |
571 | ||
572 | static tree | |
0cdd9dcf | 573 | type_for_value (mpz_t val) |
bd32f344 | 574 | { |
0cdd9dcf | 575 | return type_for_interval (val, val); |
bd32f344 SP |
576 | } |
577 | ||
6886e444 RG |
578 | static tree |
579 | type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t); | |
580 | ||
6c6c79a9 SP |
581 | /* Return the type for the clast_term T. Initializes BOUND_ONE and |
582 | BOUND_TWO to the bounds of the term. */ | |
bd32f344 SP |
583 | |
584 | static tree | |
6c6c79a9 SP |
585 | type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t bound_one, |
586 | mpz_t bound_two) | |
bd32f344 | 587 | { |
6886e444 | 588 | tree type; |
4431102b | 589 | gcc_assert (t->expr.type == clast_expr_term); |
bd32f344 | 590 | |
6886e444 | 591 | if (!t->var) |
ef74e2ba | 592 | { |
6c6c79a9 SP |
593 | mpz_set (bound_one, t->val); |
594 | mpz_set (bound_two, t->val); | |
ef74e2ba SP |
595 | return type_for_value (t->val); |
596 | } | |
597 | ||
6886e444 | 598 | type = type_for_clast_expr (t->var, ip, bound_one, bound_two); |
ef74e2ba | 599 | |
6c6c79a9 SP |
600 | mpz_mul (bound_one, bound_one, t->val); |
601 | mpz_mul (bound_two, bound_two, t->val); | |
ef74e2ba | 602 | |
6886e444 | 603 | return max_precision_type (type, type_for_interval (bound_one, bound_two)); |
bd32f344 SP |
604 | } |
605 | ||
6c6c79a9 SP |
606 | /* Return the type for the clast_reduction R. Initializes BOUND_ONE |
607 | and BOUND_TWO to the bounds of the reduction expression. */ | |
bd32f344 SP |
608 | |
609 | static tree | |
ef74e2ba | 610 | type_for_clast_red (struct clast_reduction *r, ivs_params_p ip, |
6c6c79a9 | 611 | mpz_t bound_one, mpz_t bound_two) |
bd32f344 SP |
612 | { |
613 | int i; | |
6c6c79a9 | 614 | tree type = type_for_clast_expr (r->elts[0], ip, bound_one, bound_two); |
ef74e2ba | 615 | mpz_t b1, b2, m1, m2; |
bd32f344 SP |
616 | |
617 | if (r->n == 1) | |
ef74e2ba | 618 | return type; |
bd32f344 | 619 | |
ef74e2ba SP |
620 | mpz_init (b1); |
621 | mpz_init (b2); | |
622 | mpz_init (m1); | |
623 | mpz_init (m2); | |
bd32f344 | 624 | |
ef74e2ba SP |
625 | for (i = 1; i < r->n; i++) |
626 | { | |
627 | tree t = type_for_clast_expr (r->elts[i], ip, b1, b2); | |
628 | type = max_precision_type (type, t); | |
629 | ||
630 | switch (r->type) | |
631 | { | |
632 | case clast_red_sum: | |
6c6c79a9 | 633 | value_min (m1, bound_one, bound_two); |
ef74e2ba | 634 | value_min (m2, b1, b2); |
6c6c79a9 | 635 | mpz_add (bound_one, m1, m2); |
ef74e2ba | 636 | |
6c6c79a9 | 637 | value_max (m1, bound_one, bound_two); |
ef74e2ba | 638 | value_max (m2, b1, b2); |
6c6c79a9 | 639 | mpz_add (bound_two, m1, m2); |
ef74e2ba SP |
640 | break; |
641 | ||
642 | case clast_red_min: | |
6c6c79a9 SP |
643 | value_min (bound_one, bound_one, bound_two); |
644 | value_min (bound_two, b1, b2); | |
ef74e2ba SP |
645 | break; |
646 | ||
647 | case clast_red_max: | |
6c6c79a9 SP |
648 | value_max (bound_one, bound_one, bound_two); |
649 | value_max (bound_two, b1, b2); | |
ef74e2ba SP |
650 | break; |
651 | ||
652 | default: | |
653 | gcc_unreachable (); | |
654 | break; | |
655 | } | |
bd32f344 SP |
656 | } |
657 | ||
ef74e2ba SP |
658 | mpz_clear (b1); |
659 | mpz_clear (b2); | |
660 | mpz_clear (m1); | |
661 | mpz_clear (m2); | |
662 | ||
663 | /* Return a type that can represent the result of the reduction. */ | |
6c6c79a9 | 664 | return max_precision_type (type, type_for_interval (bound_one, bound_two)); |
bd32f344 SP |
665 | } |
666 | ||
667 | /* Return the type for the clast_binary B used in STMT. */ | |
668 | ||
669 | static tree | |
6c6c79a9 SP |
670 | type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t bound_one, |
671 | mpz_t bound_two) | |
bd32f344 | 672 | { |
ef74e2ba | 673 | mpz_t one; |
6c6c79a9 SP |
674 | tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip, |
675 | bound_one, bound_two); | |
0cdd9dcf | 676 | tree r = type_for_value (b->RHS); |
ef74e2ba SP |
677 | tree type = max_precision_type (l, r); |
678 | ||
679 | switch (b->type) | |
680 | { | |
681 | case clast_bin_fdiv: | |
6c6c79a9 SP |
682 | mpz_mdiv (bound_one, bound_one, b->RHS); |
683 | mpz_mdiv (bound_two, bound_two, b->RHS); | |
ef74e2ba SP |
684 | break; |
685 | ||
686 | case clast_bin_cdiv: | |
6c6c79a9 SP |
687 | mpz_mdiv (bound_one, bound_one, b->RHS); |
688 | mpz_mdiv (bound_two, bound_two, b->RHS); | |
ef74e2ba | 689 | mpz_init (one); |
6c6c79a9 SP |
690 | mpz_add (bound_one, bound_one, one); |
691 | mpz_add (bound_two, bound_two, one); | |
ef74e2ba SP |
692 | mpz_clear (one); |
693 | break; | |
694 | ||
695 | case clast_bin_div: | |
6c6c79a9 SP |
696 | mpz_div (bound_one, bound_one, b->RHS); |
697 | mpz_div (bound_two, bound_two, b->RHS); | |
ef74e2ba SP |
698 | break; |
699 | ||
700 | case clast_bin_mod: | |
6c6c79a9 SP |
701 | mpz_mod (bound_one, bound_one, b->RHS); |
702 | mpz_mod (bound_two, bound_two, b->RHS); | |
ef74e2ba SP |
703 | break; |
704 | ||
705 | default: | |
706 | gcc_unreachable (); | |
707 | } | |
708 | ||
709 | /* Return a type that can represent the result of the reduction. */ | |
6c6c79a9 | 710 | return max_precision_type (type, type_for_interval (bound_one, bound_two)); |
bd32f344 SP |
711 | } |
712 | ||
6886e444 RG |
713 | /* Return the type for the clast_name NAME. Initializes BOUND_ONE and |
714 | BOUND_TWO to the bounds of the term. */ | |
715 | ||
716 | static tree | |
717 | type_for_clast_name (struct clast_name *name, ivs_params_p ip, mpz_t bound_one, | |
718 | mpz_t bound_two) | |
719 | { | |
720 | bool found = false; | |
721 | ||
c203e8a7 | 722 | if (ip->params.exists () && ip->params_index) |
6886e444 RG |
723 | found = clast_name_to_lb_ub (name, ip->params_index, bound_one, bound_two); |
724 | ||
725 | if (!found) | |
726 | { | |
c203e8a7 | 727 | gcc_assert (ip->newivs && ip->newivs_index); |
6886e444 RG |
728 | found = clast_name_to_lb_ub (name, ip->newivs_index, bound_one, |
729 | bound_two); | |
730 | gcc_assert (found); | |
731 | } | |
732 | ||
733 | return TREE_TYPE (clast_name_to_gcc (name, ip)); | |
734 | } | |
735 | ||
bd32f344 SP |
736 | /* Returns the type for the CLAST expression E when used in statement |
737 | STMT. */ | |
2abae5f1 SP |
738 | |
739 | static tree | |
6c6c79a9 SP |
740 | type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t bound_one, |
741 | mpz_t bound_two) | |
2abae5f1 SP |
742 | { |
743 | switch (e->type) | |
744 | { | |
4431102b | 745 | case clast_expr_term: |
6c6c79a9 SP |
746 | return type_for_clast_term ((struct clast_term *) e, ip, |
747 | bound_one, bound_two); | |
2abae5f1 | 748 | |
4431102b | 749 | case clast_expr_red: |
6c6c79a9 SP |
750 | return type_for_clast_red ((struct clast_reduction *) e, ip, |
751 | bound_one, bound_two); | |
2abae5f1 | 752 | |
4431102b | 753 | case clast_expr_bin: |
6c6c79a9 SP |
754 | return type_for_clast_bin ((struct clast_binary *) e, ip, |
755 | bound_one, bound_two); | |
2abae5f1 | 756 | |
6886e444 RG |
757 | case clast_expr_name: |
758 | return type_for_clast_name ((struct clast_name *) e, ip, | |
759 | bound_one, bound_two); | |
760 | ||
2abae5f1 SP |
761 | default: |
762 | gcc_unreachable (); | |
763 | } | |
764 | ||
765 | return NULL_TREE; | |
766 | } | |
767 | ||
33ad93b9 | 768 | /* Returns true if the clast expression E is a constant with VALUE. */ |
2abae5f1 | 769 | |
33ad93b9 RG |
770 | static bool |
771 | clast_expr_const_value_p (struct clast_expr *e, int value) | |
2abae5f1 | 772 | { |
33ad93b9 RG |
773 | struct clast_term *t; |
774 | if (e->type != clast_expr_term) | |
775 | return false; | |
776 | t = (struct clast_term *)e; | |
777 | if (t->var) | |
778 | return false; | |
779 | return 0 == mpz_cmp_si (t->val, value); | |
2abae5f1 SP |
780 | } |
781 | ||
782 | /* Translates a clast equation CLEQ to a tree. */ | |
783 | ||
784 | static tree | |
cf7eab7d SP |
785 | graphite_translate_clast_equation (struct clast_equation *cleq, |
786 | ivs_params_p ip) | |
2abae5f1 SP |
787 | { |
788 | enum tree_code comp; | |
33ad93b9 RG |
789 | tree type, lhs, rhs, ltype, rtype; |
790 | mpz_t bound_one, bound_two; | |
791 | struct clast_expr *clhs, *crhs; | |
2abae5f1 | 792 | |
33ad93b9 RG |
793 | clhs = cleq->LHS; |
794 | crhs = cleq->RHS; | |
2abae5f1 SP |
795 | if (cleq->sign == 0) |
796 | comp = EQ_EXPR; | |
2abae5f1 SP |
797 | else if (cleq->sign > 0) |
798 | comp = GE_EXPR; | |
2abae5f1 SP |
799 | else |
800 | comp = LE_EXPR; | |
801 | ||
33ad93b9 RG |
802 | /* Special cases to reduce range of arguments to hopefully |
803 | don't need types with larger precision than the input. */ | |
804 | if (crhs->type == clast_expr_red | |
805 | && comp != EQ_EXPR) | |
806 | { | |
807 | struct clast_reduction *r = (struct clast_reduction *) crhs; | |
808 | /* X >= A+1 --> X > A and | |
809 | X <= A-1 --> X < A */ | |
810 | if (r->n == 2 | |
811 | && r->type == clast_red_sum | |
812 | && clast_expr_const_value_p (r->elts[1], comp == GE_EXPR ? 1 : -1)) | |
813 | { | |
814 | crhs = r->elts[0]; | |
815 | comp = comp == GE_EXPR ? GT_EXPR : LT_EXPR; | |
816 | } | |
817 | } | |
818 | ||
819 | mpz_init (bound_one); | |
820 | mpz_init (bound_two); | |
821 | ||
822 | ltype = type_for_clast_expr (clhs, ip, bound_one, bound_two); | |
823 | rtype = type_for_clast_expr (crhs, ip, bound_one, bound_two); | |
824 | ||
825 | mpz_clear (bound_one); | |
826 | mpz_clear (bound_two); | |
827 | type = max_precision_type (ltype, rtype); | |
828 | ||
829 | lhs = clast_to_gcc_expression (type, clhs, ip); | |
830 | rhs = clast_to_gcc_expression (type, crhs, ip); | |
831 | ||
2abae5f1 SP |
832 | return fold_build2 (comp, boolean_type_node, lhs, rhs); |
833 | } | |
834 | ||
835 | /* Creates the test for the condition in STMT. */ | |
836 | ||
837 | static tree | |
cf7eab7d SP |
838 | graphite_create_guard_cond_expr (struct clast_guard *stmt, |
839 | ivs_params_p ip) | |
2abae5f1 SP |
840 | { |
841 | tree cond = NULL; | |
842 | int i; | |
843 | ||
844 | for (i = 0; i < stmt->n; i++) | |
845 | { | |
cf7eab7d | 846 | tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip); |
2abae5f1 SP |
847 | |
848 | if (cond) | |
849 | cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq); | |
850 | else | |
851 | cond = eq; | |
852 | } | |
853 | ||
854 | return cond; | |
855 | } | |
856 | ||
857 | /* Creates a new if region corresponding to Cloog's guard. */ | |
858 | ||
859 | static edge | |
cf7eab7d SP |
860 | graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt, |
861 | ivs_params_p ip) | |
2abae5f1 | 862 | { |
cf7eab7d | 863 | tree cond_expr = graphite_create_guard_cond_expr (stmt, ip); |
2abae5f1 SP |
864 | edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); |
865 | return exit_edge; | |
866 | } | |
867 | ||
3d9784cb SP |
868 | /* Compute the lower bound LOW and upper bound UP for the parameter |
869 | PARAM in scop SCOP based on the constraints in the context. */ | |
870 | ||
871 | static void | |
872 | compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up) | |
873 | { | |
33ad93b9 RG |
874 | isl_int v; |
875 | isl_aff *aff = isl_aff_zero_on_domain | |
876 | (isl_local_space_from_space (isl_set_get_space (scop->context))); | |
877 | ||
878 | aff = isl_aff_add_coefficient_si (aff, isl_dim_param, param, 1); | |
879 | ||
880 | isl_int_init (v); | |
881 | isl_set_min (scop->context, aff, &v); | |
882 | isl_int_get_gmp (v, low); | |
883 | isl_set_max (scop->context, aff, &v); | |
884 | isl_int_get_gmp (v, up); | |
885 | isl_int_clear (v); | |
886 | isl_aff_free (aff); | |
3d9784cb SP |
887 | } |
888 | ||
bd32f344 | 889 | /* Compute the lower bound LOW and upper bound UP for the induction |
33ad93b9 | 890 | variable of loop LOOP. |
2abae5f1 | 891 | |
33ad93b9 RG |
892 | FIXME: This one is not entirely correct, as min/max expressions in the |
893 | calculation can yield to incorrect results. To be completely | |
894 | correct, we need to evaluate each subexpression generated by | |
895 | CLooG. CLooG does not yet support this, so this is as good as | |
896 | it can be. */ | |
8aab43a0 | 897 | |
33ad93b9 RG |
898 | static void |
899 | compute_bounds_for_loop (struct clast_for *loop, mpz_t low, mpz_t up) | |
bd32f344 | 900 | { |
33ad93b9 RG |
901 | isl_set *domain; |
902 | isl_aff *dimension; | |
903 | isl_local_space *local_space; | |
904 | isl_int isl_value; | |
905 | enum isl_lp_result lp_result; | |
906 | ||
907 | domain = isl_set_copy (isl_set_from_cloog_domain (loop->domain)); | |
908 | local_space = isl_local_space_from_space (isl_set_get_space (domain)); | |
909 | dimension = isl_aff_zero_on_domain (local_space); | |
910 | dimension = isl_aff_add_coefficient_si (dimension, isl_dim_in, | |
911 | isl_set_dim (domain, isl_dim_set) - 1, | |
912 | 1); | |
913 | ||
914 | isl_int_init (isl_value); | |
915 | ||
916 | lp_result = isl_set_min (domain, dimension, &isl_value); | |
917 | assert (lp_result == isl_lp_ok); | |
918 | isl_int_get_gmp (isl_value, low); | |
919 | ||
920 | lp_result = isl_set_max (domain, dimension, &isl_value); | |
921 | assert (lp_result == isl_lp_ok); | |
922 | isl_int_get_gmp (isl_value, up); | |
923 | ||
924 | isl_int_clear (isl_value); | |
925 | isl_set_free (domain); | |
926 | isl_aff_free (dimension); | |
2abae5f1 SP |
927 | } |
928 | ||
bd32f344 SP |
929 | /* Returns the type for the induction variable for the loop translated |
930 | from STMT_FOR. */ | |
2abae5f1 SP |
931 | |
932 | static tree | |
3d9784cb | 933 | type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip) |
2abae5f1 | 934 | { |
6c6c79a9 | 935 | mpz_t bound_one, bound_two; |
ef74e2ba SP |
936 | tree lb_type, ub_type; |
937 | ||
6c6c79a9 SP |
938 | mpz_init (bound_one); |
939 | mpz_init (bound_two); | |
ef74e2ba | 940 | |
6c6c79a9 SP |
941 | lb_type = type_for_clast_expr (stmt_for->LB, ip, bound_one, bound_two); |
942 | ub_type = type_for_clast_expr (stmt_for->UB, ip, bound_one, bound_two); | |
ef74e2ba | 943 | |
6c6c79a9 SP |
944 | mpz_clear (bound_one); |
945 | mpz_clear (bound_two); | |
2abae5f1 | 946 | |
3d9784cb | 947 | return max_precision_type (lb_type, ub_type); |
2abae5f1 SP |
948 | } |
949 | ||
950 | /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an | |
951 | induction variable for the new LOOP. New LOOP is attached to CFG | |
952 | starting at ENTRY_EDGE. LOOP is inserted into the loop tree and | |
953 | becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds | |
954 | CLooG's scattering name to the induction variable created for the | |
955 | loop of STMT. The new induction variable is inserted in the NEWIVS | |
6e6568db | 956 | vector and is of type TYPE. */ |
2abae5f1 SP |
957 | |
958 | static struct loop * | |
cf7eab7d SP |
959 | graphite_create_new_loop (edge entry_edge, struct clast_for *stmt, |
960 | loop_p outer, tree type, tree lb, tree ub, | |
961 | int level, ivs_params_p ip) | |
2abae5f1 | 962 | { |
3d9784cb SP |
963 | mpz_t low, up; |
964 | ||
2abae5f1 SP |
965 | tree stride = gmp_cst_to_tree (type, stmt->stride); |
966 | tree ivvar = create_tmp_var (type, "graphite_IV"); | |
967 | tree iv, iv_after_increment; | |
968 | loop_p loop = create_empty_loop_on_edge | |
969 | (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment, | |
970 | outer ? outer : entry_edge->src->loop_father); | |
971 | ||
3d9784cb SP |
972 | mpz_init (low); |
973 | mpz_init (up); | |
33ad93b9 | 974 | compute_bounds_for_loop (stmt, low, up); |
cf7eab7d | 975 | save_clast_name_index (ip->newivs_index, stmt->iterator, |
9771b263 | 976 | (*ip->newivs).length (), level, low, up); |
3d9784cb SP |
977 | mpz_clear (low); |
978 | mpz_clear (up); | |
9771b263 | 979 | (*ip->newivs).safe_push (iv); |
2abae5f1 SP |
980 | return loop; |
981 | } | |
982 | ||
2e286fd2 SP |
983 | /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the |
984 | induction variables of the loops around GBB in SESE. */ | |
2abae5f1 SP |
985 | |
986 | static void | |
9771b263 | 987 | build_iv_mapping (vec<tree> iv_map, struct clast_user_stmt *user_stmt, |
cf7eab7d | 988 | ivs_params_p ip) |
2abae5f1 SP |
989 | { |
990 | struct clast_stmt *t; | |
2e286fd2 | 991 | int depth = 0; |
2abae5f1 | 992 | CloogStatement *cs = user_stmt->statement; |
6886e444 | 993 | poly_bb_p pbb = (poly_bb_p) cs->usr; |
2e286fd2 | 994 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); |
6c6c79a9 | 995 | mpz_t bound_one, bound_two; |
ef74e2ba | 996 | |
6c6c79a9 SP |
997 | mpz_init (bound_one); |
998 | mpz_init (bound_two); | |
2abae5f1 | 999 | |
2e286fd2 | 1000 | for (t = user_stmt->substitutions; t; t = t->next, depth++) |
2abae5f1 SP |
1001 | { |
1002 | struct clast_expr *expr = (struct clast_expr *) | |
1003 | ((struct clast_assignment *)t)->RHS; | |
6c6c79a9 | 1004 | tree type = type_for_clast_expr (expr, ip, bound_one, bound_two); |
cf7eab7d SP |
1005 | tree new_name = clast_to_gcc_expression (type, expr, ip); |
1006 | loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth); | |
2e286fd2 | 1007 | |
9771b263 | 1008 | iv_map[old_loop->num] = new_name; |
2abae5f1 | 1009 | } |
ef74e2ba | 1010 | |
6c6c79a9 SP |
1011 | mpz_clear (bound_one); |
1012 | mpz_clear (bound_two); | |
2abae5f1 SP |
1013 | } |
1014 | ||
2e286fd2 | 1015 | /* Construct bb_pbb_def with BB and PBB. */ |
2abae5f1 SP |
1016 | |
1017 | static bb_pbb_def * | |
1018 | new_bb_pbb_def (basic_block bb, poly_bb_p pbb) | |
1019 | { | |
1020 | bb_pbb_def *bb_pbb_p; | |
1021 | ||
1022 | bb_pbb_p = XNEW (bb_pbb_def); | |
1023 | bb_pbb_p->bb = bb; | |
1024 | bb_pbb_p->pbb = pbb; | |
1025 | ||
1026 | return bb_pbb_p; | |
1027 | } | |
1028 | ||
1029 | /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */ | |
1030 | ||
1031 | static void | |
4a8fb1a1 | 1032 | mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, |
c203e8a7 | 1033 | bb_pbb_htab_type *bb_pbb_mapping) |
2abae5f1 SP |
1034 | { |
1035 | bb_pbb_def tmp; | |
4a8fb1a1 | 1036 | bb_pbb_def **x; |
2abae5f1 SP |
1037 | |
1038 | tmp.bb = bb; | |
c203e8a7 | 1039 | x = bb_pbb_mapping->find_slot (&tmp, INSERT); |
2abae5f1 | 1040 | |
556afcdc | 1041 | if (x && !*x) |
2abae5f1 SP |
1042 | *x = new_bb_pbb_def (bb, pbb); |
1043 | } | |
1044 | ||
585b3e19 SP |
1045 | /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */ |
1046 | ||
33ad93b9 | 1047 | poly_bb_p |
c203e8a7 | 1048 | find_pbb_via_hash (bb_pbb_htab_type *bb_pbb_mapping, basic_block bb) |
585b3e19 SP |
1049 | { |
1050 | bb_pbb_def tmp; | |
4a8fb1a1 | 1051 | bb_pbb_def **slot; |
585b3e19 SP |
1052 | |
1053 | tmp.bb = bb; | |
c203e8a7 | 1054 | slot = bb_pbb_mapping->find_slot (&tmp, NO_INSERT); |
585b3e19 SP |
1055 | |
1056 | if (slot && *slot) | |
1057 | return ((bb_pbb_def *) *slot)->pbb; | |
1058 | ||
1059 | return NULL; | |
1060 | } | |
1061 | ||
33ad93b9 RG |
1062 | /* Return the scop of the loop and initialize PBBS the set of |
1063 | poly_bb_p that belong to the LOOP. BB_PBB_MAPPING is a map created | |
1064 | by the CLAST code generator between a generated basic_block and its | |
1065 | related poly_bb_p. */ | |
585b3e19 | 1066 | |
33ad93b9 | 1067 | scop_p |
c203e8a7 | 1068 | get_loop_body_pbbs (loop_p loop, bb_pbb_htab_type *bb_pbb_mapping, |
9771b263 | 1069 | vec<poly_bb_p> *pbbs) |
585b3e19 | 1070 | { |
33ad93b9 | 1071 | unsigned i; |
585b3e19 | 1072 | basic_block *bbs = get_loop_body_in_dom_order (loop); |
33ad93b9 | 1073 | scop_p scop = NULL; |
585b3e19 SP |
1074 | |
1075 | for (i = 0; i < loop->num_nodes; i++) | |
1076 | { | |
33ad93b9 | 1077 | poly_bb_p pbb = find_pbb_via_hash (bb_pbb_mapping, bbs[i]); |
585b3e19 | 1078 | |
33ad93b9 RG |
1079 | if (pbb == NULL) |
1080 | continue; | |
585b3e19 | 1081 | |
33ad93b9 | 1082 | scop = PBB_SCOP (pbb); |
9771b263 | 1083 | (*pbbs).safe_push (pbb); |
585b3e19 SP |
1084 | } |
1085 | ||
1086 | free (bbs); | |
33ad93b9 | 1087 | return scop; |
585b3e19 SP |
1088 | } |
1089 | ||
e1f9c1cd TG |
1090 | /* Translates a clast user statement STMT to gimple. |
1091 | ||
2abae5f1 | 1092 | - NEXT_E is the edge where new generated code should be attached. |
9fa29a09 | 1093 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
cf7eab7d SP |
1094 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ |
1095 | ||
e1f9c1cd | 1096 | static edge |
cf7eab7d | 1097 | translate_clast_user (struct clast_user_stmt *stmt, edge next_e, |
c203e8a7 | 1098 | bb_pbb_htab_type *bb_pbb_mapping, ivs_params_p ip) |
e1f9c1cd | 1099 | { |
2e286fd2 | 1100 | int i, nb_loops; |
9fa29a09 | 1101 | basic_block new_bb; |
6886e444 | 1102 | poly_bb_p pbb = (poly_bb_p) stmt->statement->usr; |
2e286fd2 | 1103 | gimple_bb_p gbb = PBB_BLACK_BOX (pbb); |
9771b263 | 1104 | vec<tree> iv_map; |
e1f9c1cd | 1105 | |
fefa31b5 | 1106 | if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
e1f9c1cd TG |
1107 | return next_e; |
1108 | ||
0fc822d0 | 1109 | nb_loops = number_of_loops (cfun); |
9771b263 | 1110 | iv_map.create (nb_loops); |
2e286fd2 | 1111 | for (i = 0; i < nb_loops; i++) |
9771b263 | 1112 | iv_map.quick_push (NULL_TREE); |
2e286fd2 | 1113 | |
cf7eab7d SP |
1114 | build_iv_mapping (iv_map, stmt, ip); |
1115 | next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region, | |
bd4a54da | 1116 | next_e, iv_map, &gloog_error); |
9771b263 | 1117 | iv_map.release (); |
2e286fd2 | 1118 | |
9fa29a09 SP |
1119 | new_bb = next_e->src; |
1120 | mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping); | |
525174a2 | 1121 | mark_virtual_operands_for_renaming (cfun); |
e1f9c1cd | 1122 | update_ssa (TODO_update_ssa); |
fd2d813d | 1123 | |
9016166f | 1124 | return next_e; |
e1f9c1cd TG |
1125 | } |
1126 | ||
0dd91484 | 1127 | /* Creates a new if region protecting the loop to be executed, if the execution |
7c246f5e | 1128 | count is zero (lb > ub). */ |
6ab4e307 | 1129 | |
0dd91484 | 1130 | static edge |
cf7eab7d | 1131 | graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt, |
3d9784cb | 1132 | tree *type, tree *lb, tree *ub, |
cf7eab7d | 1133 | ivs_params_p ip) |
0dd91484 TG |
1134 | { |
1135 | tree cond_expr; | |
1136 | edge exit_edge; | |
6e6568db | 1137 | |
3d9784cb | 1138 | *type = type_for_clast_for (stmt, ip); |
cf7eab7d SP |
1139 | *lb = clast_to_gcc_expression (*type, stmt->LB, ip); |
1140 | *ub = clast_to_gcc_expression (*type, stmt->UB, ip); | |
6e6568db | 1141 | |
8b432c8b | 1142 | /* When ub is simply a constant or a parameter, use lb <= ub. */ |
6e6568db SP |
1143 | if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME) |
1144 | cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub); | |
b8132a7d | 1145 | else |
8b432c8b | 1146 | { |
6e6568db | 1147 | tree one = (POINTER_TYPE_P (*type) |
0d82a1c8 | 1148 | ? convert_to_ptrofftype (integer_one_node) |
6e6568db | 1149 | : fold_convert (*type, integer_one_node)); |
8b432c8b AM |
1150 | /* Adding +1 and using LT_EXPR helps with loop latches that have a |
1151 | loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes | |
1152 | 2^k-1 due to integer overflow, and the condition lb <= ub is true, | |
1153 | even if we do not want this. However lb < ub + 1 is false, as | |
1154 | expected. */ | |
6e6568db SP |
1155 | tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR |
1156 | : PLUS_EXPR, *type, *ub, one); | |
8b432c8b | 1157 | |
6e6568db | 1158 | cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one); |
8b432c8b | 1159 | } |
0dd91484 TG |
1160 | |
1161 | exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); | |
1162 | ||
1163 | return exit_edge; | |
1164 | } | |
1165 | ||
2e286fd2 | 1166 | static edge |
c203e8a7 | 1167 | translate_clast (loop_p, struct clast_stmt *, edge, bb_pbb_htab_type *, |
4a8fb1a1 | 1168 | int, ivs_params_p); |
0dd91484 TG |
1169 | |
1170 | /* Create the loop for a clast for statement. | |
e1f9c1cd | 1171 | |
e1f9c1cd | 1172 | - NEXT_E is the edge where new generated code should be attached. |
cf7eab7d | 1173 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ |
6e6568db | 1174 | |
e1f9c1cd | 1175 | static edge |
cf7eab7d | 1176 | translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt, |
c203e8a7 | 1177 | edge next_e, bb_pbb_htab_type *bb_pbb_mapping, |
4a8fb1a1 LC |
1178 | int level, tree type, tree lb, tree ub, |
1179 | ivs_params_p ip) | |
e1f9c1cd | 1180 | { |
cf7eab7d SP |
1181 | struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop, |
1182 | type, lb, ub, level, ip); | |
e1f9c1cd | 1183 | edge last_e = single_exit (loop); |
9fa29a09 SP |
1184 | edge to_body = single_succ_edge (loop->header); |
1185 | basic_block after = to_body->dest; | |
e1f9c1cd TG |
1186 | |
1187 | /* Create a basic block for loop close phi nodes. */ | |
1188 | last_e = single_succ_edge (split_edge (last_e)); | |
9fa29a09 SP |
1189 | |
1190 | /* Translate the body of the loop. */ | |
cf7eab7d SP |
1191 | next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping, |
1192 | level + 1, ip); | |
9fa29a09 SP |
1193 | redirect_edge_succ_nodup (next_e, after); |
1194 | set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); | |
1195 | ||
52d676b6 TG |
1196 | isl_set *domain = isl_set_from_cloog_domain (stmt->domain); |
1197 | int scheduling_dim = isl_set_n_dim (domain); | |
1198 | ||
9fa29a09 | 1199 | if (flag_loop_parallelize_all |
52d676b6 | 1200 | && loop_is_parallel_p (loop, bb_pbb_mapping, scheduling_dim)) |
9fa29a09 | 1201 | loop->can_be_parallel = true; |
e1f9c1cd | 1202 | |
9016166f | 1203 | return last_e; |
e1f9c1cd TG |
1204 | } |
1205 | ||
0dd91484 | 1206 | /* Translates a clast for statement STMT to gimple. First a guard is created |
7c246f5e TG |
1207 | protecting the loop, if it is executed zero times. In this guard we create |
1208 | the real loop structure. | |
0dd91484 | 1209 | |
0dd91484 | 1210 | - NEXT_E is the edge where new generated code should be attached. |
cf7eab7d SP |
1211 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ |
1212 | ||
0dd91484 | 1213 | static edge |
cf7eab7d | 1214 | translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e, |
c203e8a7 | 1215 | bb_pbb_htab_type *bb_pbb_mapping, int level, |
4a8fb1a1 | 1216 | ivs_params_p ip) |
0dd91484 | 1217 | { |
6e6568db | 1218 | tree type, lb, ub; |
3d9784cb | 1219 | edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type, |
cf7eab7d | 1220 | &lb, &ub, ip); |
0dd91484 | 1221 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); |
0dd91484 | 1222 | |
cf7eab7d SP |
1223 | translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level, |
1224 | type, lb, ub, ip); | |
0dd91484 TG |
1225 | return last_e; |
1226 | } | |
1227 | ||
0c43dbaf SP |
1228 | /* Translates a clast assignment STMT to gimple. |
1229 | ||
1230 | - NEXT_E is the edge where new generated code should be attached. | |
1231 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ | |
1232 | ||
1233 | static edge | |
1234 | translate_clast_assignment (struct clast_assignment *stmt, edge next_e, | |
1235 | int level, ivs_params_p ip) | |
1236 | { | |
1237 | gimple_seq stmts; | |
6c6c79a9 | 1238 | mpz_t bound_one, bound_two; |
0c43dbaf SP |
1239 | tree type, new_name, var; |
1240 | edge res = single_succ_edge (split_edge (next_e)); | |
1241 | struct clast_expr *expr = (struct clast_expr *) stmt->RHS; | |
1242 | ||
6c6c79a9 SP |
1243 | mpz_init (bound_one); |
1244 | mpz_init (bound_two); | |
1245 | type = type_for_clast_expr (expr, ip, bound_one, bound_two); | |
0c43dbaf SP |
1246 | var = create_tmp_var (type, "graphite_var"); |
1247 | new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip), | |
1248 | &stmts, true, var); | |
0c43dbaf SP |
1249 | if (stmts) |
1250 | { | |
1251 | gsi_insert_seq_on_edge (next_e, stmts); | |
1252 | gsi_commit_edge_inserts (); | |
1253 | } | |
1254 | ||
1255 | save_clast_name_index (ip->newivs_index, stmt->LHS, | |
9771b263 | 1256 | (*ip->newivs).length (), level, |
6c6c79a9 | 1257 | bound_one, bound_two); |
9771b263 | 1258 | (*ip->newivs).safe_push (new_name); |
0c43dbaf | 1259 | |
6c6c79a9 SP |
1260 | mpz_clear (bound_one); |
1261 | mpz_clear (bound_two); | |
0c43dbaf SP |
1262 | |
1263 | return res; | |
1264 | } | |
1265 | ||
e1f9c1cd TG |
1266 | /* Translates a clast guard statement STMT to gimple. |
1267 | ||
e1f9c1cd | 1268 | - NEXT_E is the edge where new generated code should be attached. |
9fa29a09 | 1269 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
cf7eab7d SP |
1270 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ |
1271 | ||
e1f9c1cd | 1272 | static edge |
cf7eab7d | 1273 | translate_clast_guard (loop_p context_loop, struct clast_guard *stmt, |
c203e8a7 | 1274 | edge next_e, bb_pbb_htab_type *bb_pbb_mapping, int level, |
cf7eab7d | 1275 | ivs_params_p ip) |
9016166f | 1276 | { |
cf7eab7d | 1277 | edge last_e = graphite_create_new_guard (next_e, stmt, ip); |
e1f9c1cd | 1278 | edge true_e = get_true_edge_from_guard_bb (next_e->dest); |
e1f9c1cd | 1279 | |
cf7eab7d | 1280 | translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip); |
9016166f | 1281 | return last_e; |
e1f9c1cd | 1282 | } |
2abae5f1 | 1283 | |
e1f9c1cd TG |
1284 | /* Translates a CLAST statement STMT to GCC representation in the |
1285 | context of a SESE. | |
1286 | ||
1287 | - NEXT_E is the edge where new generated code should be attached. | |
9fa29a09 | 1288 | - CONTEXT_LOOP is the loop in which the generated code will be placed |
e1f9c1cd | 1289 | - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */ |
cf7eab7d | 1290 | |
2abae5f1 | 1291 | static edge |
cf7eab7d | 1292 | translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e, |
c203e8a7 | 1293 | bb_pbb_htab_type *bb_pbb_mapping, int level, ivs_params_p ip) |
2abae5f1 | 1294 | { |
e3f81db1 | 1295 | if (!stmt) |
2abae5f1 SP |
1296 | return next_e; |
1297 | ||
1298 | if (CLAST_STMT_IS_A (stmt, stmt_root)) | |
9016166f | 1299 | ; /* Do nothing. */ |
2abae5f1 | 1300 | |
9016166f | 1301 | else if (CLAST_STMT_IS_A (stmt, stmt_user)) |
cf7eab7d SP |
1302 | next_e = translate_clast_user ((struct clast_user_stmt *) stmt, |
1303 | next_e, bb_pbb_mapping, ip); | |
2abae5f1 | 1304 | |
9016166f | 1305 | else if (CLAST_STMT_IS_A (stmt, stmt_for)) |
cf7eab7d SP |
1306 | next_e = translate_clast_for (context_loop, (struct clast_for *) stmt, |
1307 | next_e, bb_pbb_mapping, level, ip); | |
2abae5f1 | 1308 | |
9016166f | 1309 | else if (CLAST_STMT_IS_A (stmt, stmt_guard)) |
cf7eab7d SP |
1310 | next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt, |
1311 | next_e, bb_pbb_mapping, level, ip); | |
9016166f TG |
1312 | |
1313 | else if (CLAST_STMT_IS_A (stmt, stmt_block)) | |
cf7eab7d SP |
1314 | next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body, |
1315 | next_e, bb_pbb_mapping, level, ip); | |
0c43dbaf SP |
1316 | |
1317 | else if (CLAST_STMT_IS_A (stmt, stmt_ass)) | |
1318 | next_e = translate_clast_assignment ((struct clast_assignment *) stmt, | |
1319 | next_e, level, ip); | |
9016166f | 1320 | else |
c3284718 | 1321 | gcc_unreachable (); |
2abae5f1 | 1322 | |
9016166f TG |
1323 | recompute_all_dominators (); |
1324 | graphite_verify (); | |
1325 | ||
cf7eab7d SP |
1326 | return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping, |
1327 | level, ip); | |
2abae5f1 SP |
1328 | } |
1329 | ||
6886e444 | 1330 | /* Add parameter and iterator names to the CloogUnionDomain. */ |
2abae5f1 | 1331 | |
6886e444 RG |
1332 | static CloogUnionDomain * |
1333 | add_names_to_union_domain (scop_p scop, CloogUnionDomain *union_domain, | |
4a8fb1a1 | 1334 | int nb_scattering_dims, |
c203e8a7 | 1335 | clast_index_htab_type *params_index) |
2abae5f1 SP |
1336 | { |
1337 | sese region = SCOP_REGION (scop); | |
1338 | int i; | |
1339 | int nb_iterators = scop_max_loop_depth (scop); | |
9771b263 | 1340 | int nb_parameters = SESE_PARAMS (region).length (); |
6886e444 | 1341 | mpz_t bound_one, bound_two; |
2abae5f1 | 1342 | |
6886e444 RG |
1343 | mpz_init (bound_one); |
1344 | mpz_init (bound_two); | |
7a521ff2 TG |
1345 | |
1346 | for (i = 0; i < nb_parameters; i++) | |
1347 | { | |
9771b263 | 1348 | tree param = SESE_PARAMS (region)[i]; |
7a521ff2 TG |
1349 | const char *name = get_name (param); |
1350 | int len; | |
6886e444 | 1351 | char *parameter; |
7a521ff2 TG |
1352 | |
1353 | if (!name) | |
1354 | name = "T"; | |
1355 | ||
1356 | len = strlen (name); | |
1357 | len += 17; | |
6886e444 RG |
1358 | parameter = XNEWVEC (char, len + 1); |
1359 | snprintf (parameter, len, "%s_%d", name, SSA_NAME_VERSION (param)); | |
1360 | save_clast_name_index (params_index, parameter, i, i, bound_one, | |
1361 | bound_two); | |
1362 | union_domain = cloog_union_domain_set_name (union_domain, CLOOG_PARAM, i, | |
1363 | parameter); | |
1364 | compute_bounds_for_param (scop, i, bound_one, bound_two); | |
1365 | free (parameter); | |
7a521ff2 TG |
1366 | } |
1367 | ||
6886e444 RG |
1368 | mpz_clear (bound_one); |
1369 | mpz_clear (bound_two); | |
2abae5f1 SP |
1370 | |
1371 | for (i = 0; i < nb_iterators; i++) | |
1372 | { | |
1373 | int len = 4 + 16; | |
6886e444 RG |
1374 | char *iterator; |
1375 | iterator = XNEWVEC (char, len); | |
1376 | snprintf (iterator, len, "git_%d", i); | |
1377 | union_domain = cloog_union_domain_set_name (union_domain, CLOOG_ITER, i, | |
1378 | iterator); | |
1379 | free (iterator); | |
2abae5f1 SP |
1380 | } |
1381 | ||
6886e444 | 1382 | for (i = 0; i < nb_scattering_dims; i++) |
2abae5f1 SP |
1383 | { |
1384 | int len = 5 + 16; | |
6886e444 RG |
1385 | char *scattering; |
1386 | scattering = XNEWVEC (char, len); | |
1387 | snprintf (scattering, len, "scat_%d", i); | |
1388 | union_domain = cloog_union_domain_set_name (union_domain, CLOOG_SCAT, i, | |
1389 | scattering); | |
1390 | free (scattering); | |
2abae5f1 SP |
1391 | } |
1392 | ||
6886e444 | 1393 | return union_domain; |
2abae5f1 SP |
1394 | } |
1395 | ||
03c830c2 SP |
1396 | /* Initialize a CLooG input file. */ |
1397 | ||
1398 | static FILE * | |
1399 | init_cloog_input_file (int scop_number) | |
1400 | { | |
1401 | FILE *graphite_out_file; | |
1402 | int len = strlen (dump_base_name); | |
1403 | char *dumpname = XNEWVEC (char, len + 25); | |
1404 | char *s_scop_number = XNEWVEC (char, 15); | |
1405 | ||
1406 | memcpy (dumpname, dump_base_name, len + 1); | |
1407 | strip_off_ending (dumpname, len); | |
1408 | sprintf (s_scop_number, ".%d", scop_number); | |
1409 | strcat (dumpname, s_scop_number); | |
1410 | strcat (dumpname, ".cloog"); | |
1411 | graphite_out_file = fopen (dumpname, "w+b"); | |
1412 | ||
1413 | if (graphite_out_file == 0) | |
1414 | fatal_error ("can%'t open %s for writing: %m", dumpname); | |
1415 | ||
1416 | free (dumpname); | |
1417 | ||
1418 | return graphite_out_file; | |
1419 | } | |
1420 | ||
33ad93b9 RG |
1421 | /* Extend the scattering to NEW_DIMS scattering dimensions. */ |
1422 | ||
1423 | static | |
c3284718 | 1424 | isl_map *extend_scattering (isl_map *scattering, int new_dims) |
33ad93b9 RG |
1425 | { |
1426 | int old_dims, i; | |
1427 | isl_space *space; | |
1428 | isl_basic_map *change_scattering; | |
1429 | isl_map *change_scattering_map; | |
1430 | ||
1431 | old_dims = isl_map_dim (scattering, isl_dim_out); | |
1432 | ||
1433 | space = isl_space_alloc (isl_map_get_ctx (scattering), 0, old_dims, new_dims); | |
1434 | change_scattering = isl_basic_map_universe (isl_space_copy (space)); | |
1435 | ||
1436 | for (i = 0; i < old_dims; i++) | |
1437 | { | |
1438 | isl_constraint *c; | |
1439 | c = isl_equality_alloc | |
1440 | (isl_local_space_from_space (isl_space_copy (space))); | |
1441 | isl_constraint_set_coefficient_si (c, isl_dim_in, i, 1); | |
1442 | isl_constraint_set_coefficient_si (c, isl_dim_out, i, -1); | |
1443 | change_scattering = isl_basic_map_add_constraint (change_scattering, c); | |
1444 | } | |
1445 | ||
1446 | for (i = old_dims; i < new_dims; i++) | |
1447 | { | |
1448 | isl_constraint *c; | |
1449 | c = isl_equality_alloc | |
1450 | (isl_local_space_from_space (isl_space_copy (space))); | |
1451 | isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); | |
1452 | change_scattering = isl_basic_map_add_constraint (change_scattering, c); | |
1453 | } | |
1454 | ||
1455 | change_scattering_map = isl_map_from_basic_map (change_scattering); | |
1456 | change_scattering_map = isl_map_align_params (change_scattering_map, space); | |
1457 | return isl_map_apply_range (scattering, change_scattering_map); | |
1458 | } | |
1459 | ||
6886e444 | 1460 | /* Build cloog union domain for SCoP. */ |
2abae5f1 | 1461 | |
6886e444 | 1462 | static CloogUnionDomain * |
33ad93b9 | 1463 | build_cloog_union_domain (scop_p scop, int nb_scattering_dims) |
2abae5f1 SP |
1464 | { |
1465 | int i; | |
2abae5f1 | 1466 | poly_bb_p pbb; |
6886e444 RG |
1467 | CloogUnionDomain *union_domain = |
1468 | cloog_union_domain_alloc (scop_nb_params (scop)); | |
2abae5f1 | 1469 | |
9771b263 | 1470 | FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) |
2abae5f1 | 1471 | { |
6886e444 RG |
1472 | CloogDomain *domain; |
1473 | CloogScattering *scattering; | |
2abae5f1 SP |
1474 | |
1475 | /* Dead code elimination: when the domain of a PBB is empty, | |
1476 | don't generate code for the PBB. */ | |
c3284718 | 1477 | if (isl_set_is_empty (pbb->domain)) |
2abae5f1 SP |
1478 | continue; |
1479 | ||
c3284718 RS |
1480 | domain = cloog_domain_from_isl_set (isl_set_copy (pbb->domain)); |
1481 | scattering = cloog_scattering_from_isl_map | |
1482 | (extend_scattering (isl_map_copy (pbb->transformed), | |
1483 | nb_scattering_dims)); | |
2abae5f1 | 1484 | |
6886e444 RG |
1485 | union_domain = cloog_union_domain_add_domain (union_domain, "", domain, |
1486 | scattering, pbb); | |
2abae5f1 SP |
1487 | } |
1488 | ||
6886e444 | 1489 | return union_domain; |
2abae5f1 SP |
1490 | } |
1491 | ||
1492 | /* Return the options that will be used in GLOOG. */ | |
1493 | ||
1494 | static CloogOptions * | |
57d598f7 | 1495 | set_cloog_options (void) |
2abae5f1 | 1496 | { |
57d598f7 | 1497 | CloogOptions *options = cloog_options_malloc (cloog_state); |
2abae5f1 SP |
1498 | |
1499 | /* Change cloog output language to C. If we do use FORTRAN instead, cloog | |
1500 | will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if | |
1501 | we pass an incomplete program to cloog. */ | |
7e2fe488 | 1502 | options->language = CLOOG_LANGUAGE_C; |
2abae5f1 SP |
1503 | |
1504 | /* Enable complex equality spreading: removes dummy statements | |
1505 | (assignments) in the generated code which repeats the | |
1506 | substitution equations for statements. This is useless for | |
1507 | GLooG. */ | |
1508 | options->esp = 1; | |
1509 | ||
ac3b070a AS |
1510 | /* Silence CLooG to avoid failing tests due to debug output to stderr. */ |
1511 | options->quiet = 1; | |
2abae5f1 SP |
1512 | |
1513 | /* Allow cloog to build strides with a stride width different to one. | |
1514 | This example has stride = 4: | |
1515 | ||
1516 | for (i = 0; i < 20; i += 4) | |
1517 | A */ | |
1518 | options->strides = 1; | |
1519 | ||
33ad93b9 RG |
1520 | /* We want the clast to provide the iteration domains of the executed loops. |
1521 | This allows us to derive minimal/maximal values for the induction | |
1522 | variables. */ | |
1523 | options->save_domains = 1; | |
1524 | ||
0afe7332 TG |
1525 | /* Do not remove scalar dimensions. CLooG by default removes scalar |
1526 | dimensions very early from the input schedule. However, they are | |
1527 | necessary to correctly derive from the saved domains | |
1528 | (options->save_domains) the relationship between the generated loops | |
1529 | and the schedule dimensions they are generated from. */ | |
1530 | options->noscalars = 1; | |
1531 | ||
2abae5f1 SP |
1532 | /* Disable optimizations and make cloog generate source code closer to the |
1533 | input. This is useful for debugging, but later we want the optimized | |
1534 | code. | |
1535 | ||
1536 | XXX: We can not disable optimizations, as loop blocking is not working | |
1537 | without them. */ | |
1538 | if (0) | |
1539 | { | |
1540 | options->f = -1; | |
1541 | options->l = INT_MAX; | |
1542 | } | |
1543 | ||
1544 | return options; | |
1545 | } | |
1546 | ||
1547 | /* Prints STMT to STDERR. */ | |
1548 | ||
1549 | void | |
1550 | print_clast_stmt (FILE *file, struct clast_stmt *stmt) | |
1551 | { | |
57d598f7 | 1552 | CloogOptions *options = set_cloog_options (); |
2abae5f1 | 1553 | |
4431102b | 1554 | clast_pprint (file, stmt, 0, options); |
2abae5f1 SP |
1555 | cloog_options_free (options); |
1556 | } | |
1557 | ||
1558 | /* Prints STMT to STDERR. */ | |
1559 | ||
24e47c76 | 1560 | DEBUG_FUNCTION void |
2abae5f1 SP |
1561 | debug_clast_stmt (struct clast_stmt *stmt) |
1562 | { | |
1563 | print_clast_stmt (stderr, stmt); | |
1564 | } | |
1565 | ||
33ad93b9 RG |
1566 | /* Get the maximal number of scattering dimensions in the scop SCOP. */ |
1567 | ||
1568 | static | |
1569 | int get_max_scattering_dimensions (scop_p scop) | |
1570 | { | |
1571 | int i; | |
1572 | poly_bb_p pbb; | |
1573 | int scattering_dims = 0; | |
1574 | ||
9771b263 | 1575 | FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) |
33ad93b9 RG |
1576 | { |
1577 | int pbb_scatt_dims = isl_map_dim (pbb->transformed, isl_dim_out); | |
1578 | if (pbb_scatt_dims > scattering_dims) | |
1579 | scattering_dims = pbb_scatt_dims; | |
1580 | } | |
1581 | ||
1582 | return scattering_dims; | |
1583 | } | |
1584 | ||
6886e444 | 1585 | static CloogInput * |
c203e8a7 | 1586 | generate_cloog_input (scop_p scop, clast_index_htab_type *params_index) |
6886e444 RG |
1587 | { |
1588 | CloogUnionDomain *union_domain; | |
1589 | CloogInput *cloog_input; | |
1590 | CloogDomain *context; | |
33ad93b9 | 1591 | int nb_scattering_dims = get_max_scattering_dimensions (scop); |
6886e444 | 1592 | |
33ad93b9 | 1593 | union_domain = build_cloog_union_domain (scop, nb_scattering_dims); |
6886e444 RG |
1594 | union_domain = add_names_to_union_domain (scop, union_domain, |
1595 | nb_scattering_dims, | |
1596 | params_index); | |
33ad93b9 | 1597 | context = cloog_domain_from_isl_set (isl_set_copy (scop->context)); |
6886e444 RG |
1598 | |
1599 | cloog_input = cloog_input_alloc (context, union_domain); | |
1600 | ||
1601 | return cloog_input; | |
1602 | } | |
1603 | ||
2abae5f1 SP |
1604 | /* Translate SCOP to a CLooG program and clast. These two |
1605 | representations should be freed together: a clast cannot be used | |
1606 | without a program. */ | |
1607 | ||
6886e444 | 1608 | static struct clast_stmt * |
c203e8a7 | 1609 | scop_to_clast (scop_p scop, clast_index_htab_type *params_index) |
2abae5f1 | 1610 | { |
6886e444 RG |
1611 | CloogInput *cloog_input; |
1612 | struct clast_stmt *clast; | |
57d598f7 | 1613 | CloogOptions *options = set_cloog_options (); |
2abae5f1 | 1614 | |
6886e444 RG |
1615 | cloog_input = generate_cloog_input (scop, params_index); |
1616 | ||
1617 | /* Dump a .cloog input file, if requested. This feature is only | |
1618 | enabled in the Graphite branch. */ | |
1619 | if (0) | |
1620 | { | |
1621 | static size_t file_scop_number = 0; | |
1622 | FILE *cloog_file = init_cloog_input_file (file_scop_number); | |
1623 | cloog_input_dump_cloog (cloog_file, cloog_input, options); | |
1624 | } | |
1625 | ||
1626 | clast = cloog_clast_create_from_input (cloog_input, options); | |
2abae5f1 SP |
1627 | |
1628 | cloog_options_free (options); | |
6886e444 | 1629 | return clast; |
2abae5f1 SP |
1630 | } |
1631 | ||
1632 | /* Prints to FILE the code generated by CLooG for SCOP. */ | |
1633 | ||
1634 | void | |
1635 | print_generated_program (FILE *file, scop_p scop) | |
1636 | { | |
57d598f7 | 1637 | CloogOptions *options = set_cloog_options (); |
c203e8a7 | 1638 | clast_index_htab_type *params_index = new clast_index_htab_type (10); |
6886e444 | 1639 | struct clast_stmt *clast; |
60f87855 | 1640 | |
6886e444 | 1641 | clast = scop_to_clast (scop, params_index); |
2abae5f1 SP |
1642 | |
1643 | fprintf (file, " (clast: \n"); | |
6886e444 | 1644 | clast_pprint (file, clast, 0, options); |
2abae5f1 SP |
1645 | fprintf (file, " )\n"); |
1646 | ||
1647 | cloog_options_free (options); | |
6886e444 | 1648 | cloog_clast_free (clast); |
2abae5f1 SP |
1649 | } |
1650 | ||
1651 | /* Prints to STDERR the code generated by CLooG for SCOP. */ | |
1652 | ||
24e47c76 | 1653 | DEBUG_FUNCTION void |
2abae5f1 SP |
1654 | debug_generated_program (scop_p scop) |
1655 | { | |
1656 | print_generated_program (stderr, scop); | |
1657 | } | |
1658 | ||
2abae5f1 SP |
1659 | /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for |
1660 | the given SCOP. Return true if code generation succeeded. | |
1661 | BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping. | |
1662 | */ | |
1663 | ||
1664 | bool | |
c203e8a7 | 1665 | gloog (scop_p scop, bb_pbb_htab_type *bb_pbb_mapping) |
2abae5f1 | 1666 | { |
00f96dc9 | 1667 | auto_vec<tree, 10> newivs; |
9fa29a09 | 1668 | loop_p context_loop; |
2abae5f1 SP |
1669 | sese region = SCOP_REGION (scop); |
1670 | ifsese if_region = NULL; | |
c203e8a7 | 1671 | clast_index_htab_type *newivs_index, *params_index; |
6886e444 | 1672 | struct clast_stmt *clast; |
cf7eab7d | 1673 | struct ivs_params ip; |
87d4d0ee SP |
1674 | |
1675 | timevar_push (TV_GRAPHITE_CODE_GEN); | |
3c7c0158 | 1676 | gloog_error = false; |
87d4d0ee | 1677 | |
c203e8a7 | 1678 | params_index = new clast_index_htab_type (10); |
6886e444 RG |
1679 | |
1680 | clast = scop_to_clast (scop, params_index); | |
2abae5f1 SP |
1681 | |
1682 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1683 | { | |
1684 | fprintf (dump_file, "\nCLAST generated by CLooG: \n"); | |
6886e444 | 1685 | print_clast_stmt (dump_file, clast); |
2abae5f1 SP |
1686 | fprintf (dump_file, "\n"); |
1687 | } | |
1688 | ||
2abae5f1 SP |
1689 | recompute_all_dominators (); |
1690 | graphite_verify (); | |
1691 | ||
1692 | if_region = move_sese_in_condition (region); | |
1693 | sese_insert_phis_for_liveouts (region, | |
1694 | if_region->region->exit->src, | |
1695 | if_region->false_region->exit, | |
1696 | if_region->true_region->exit); | |
2abae5f1 SP |
1697 | recompute_all_dominators (); |
1698 | graphite_verify (); | |
7a521ff2 | 1699 | |
9fa29a09 | 1700 | context_loop = SESE_ENTRY (region)->src->loop_father; |
c203e8a7 | 1701 | newivs_index= new clast_index_htab_type (10); |
2abae5f1 | 1702 | |
cf7eab7d SP |
1703 | ip.newivs = &newivs; |
1704 | ip.newivs_index = newivs_index; | |
1705 | ip.params = SESE_PARAMS (region); | |
1706 | ip.params_index = params_index; | |
1707 | ip.region = region; | |
1708 | ||
6886e444 | 1709 | translate_clast (context_loop, clast, if_region->true_region->entry, |
cf7eab7d | 1710 | bb_pbb_mapping, 0, &ip); |
2abae5f1 | 1711 | graphite_verify (); |
94406344 | 1712 | scev_reset (); |
2abae5f1 SP |
1713 | recompute_all_dominators (); |
1714 | graphite_verify (); | |
1715 | ||
3c7c0158 SP |
1716 | if (gloog_error) |
1717 | set_ifsese_condition (if_region, integer_zero_node); | |
1718 | ||
8c54631d SP |
1719 | free (if_region->true_region); |
1720 | free (if_region->region); | |
1721 | free (if_region); | |
1722 | ||
c203e8a7 TS |
1723 | delete newivs_index; |
1724 | newivs_index = NULL; | |
1725 | delete params_index; | |
1726 | params_index = NULL; | |
6886e444 | 1727 | cloog_clast_free (clast); |
87d4d0ee SP |
1728 | timevar_pop (TV_GRAPHITE_CODE_GEN); |
1729 | ||
585b3e19 | 1730 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2abae5f1 | 1731 | { |
585b3e19 | 1732 | loop_p loop; |
585b3e19 | 1733 | int num_no_dependency = 0; |
2abae5f1 | 1734 | |
f0bd40b1 | 1735 | FOR_EACH_LOOP (loop, 0) |
585b3e19 SP |
1736 | if (loop->can_be_parallel) |
1737 | num_no_dependency++; | |
2abae5f1 | 1738 | |
585b3e19 SP |
1739 | fprintf (dump_file, "\n%d loops carried no dependency.\n", |
1740 | num_no_dependency); | |
2abae5f1 SP |
1741 | } |
1742 | ||
3c7c0158 | 1743 | return !gloog_error; |
2abae5f1 | 1744 | } |
2abae5f1 | 1745 | #endif |