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