1 | /* Conversion of SESE regions to Polyhedra. |
2 | Copyright (C) 2009-2024 Free Software Foundation, Inc. |
3 | Contributed by Sebastian Pop <sebastian.pop@amd.com>. |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify |
8 | it under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 | GNU General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #define INCLUDE_ISL |
22 | |
23 | #include "config.h" |
24 | |
25 | #ifdef HAVE_isl |
26 | |
27 | #include "system.h" |
28 | #include "coretypes.h" |
29 | #include "backend.h" |
30 | #include "cfghooks.h" |
31 | #include "tree.h" |
32 | #include "gimple.h" |
33 | #include "ssa.h" |
34 | #include "fold-const.h" |
35 | #include "gimple-iterator.h" |
36 | #include "gimplify.h" |
37 | #include "gimplify-me.h" |
38 | #include "tree-cfg.h" |
39 | #include "tree-ssa-loop-manip.h" |
40 | #include "tree-ssa-loop-niter.h" |
41 | #include "tree-ssa-loop.h" |
42 | #include "tree-into-ssa.h" |
43 | #include "tree-pass.h" |
44 | #include "cfgloop.h" |
45 | #include "tree-data-ref.h" |
46 | #include "tree-scalar-evolution.h" |
47 | #include "domwalk.h" |
48 | #include "tree-ssa-propagate.h" |
49 | #include "graphite.h" |
50 | |
51 | /* Return an isl identifier for the polyhedral basic block PBB. */ |
52 | |
53 | static isl_id * |
54 | isl_id_for_pbb (scop_p s, poly_bb_p pbb) |
55 | { |
56 | char name[14]; |
57 | snprintf (name, sizeof (name), "S_%d" , pbb_index (pbb)); |
58 | return isl_id_alloc (s->isl_context, name, pbb); |
59 | } |
60 | |
61 | static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); |
62 | |
63 | /* Extract an affine expression from the chain of recurrence E. */ |
64 | |
65 | static isl_pw_aff * |
66 | extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space) |
67 | { |
68 | isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space)); |
69 | isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space)); |
70 | isl_local_space *ls = isl_local_space_from_space (space); |
71 | unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1; |
72 | isl_aff *loop = isl_aff_set_coefficient_si |
73 | (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1); |
74 | isl_pw_aff *l = isl_pw_aff_from_aff (loop); |
75 | |
76 | /* Before multiplying, make sure that the result is affine. */ |
77 | gcc_assert (isl_pw_aff_is_cst (rhs) |
78 | || isl_pw_aff_is_cst (l)); |
79 | |
80 | return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l)); |
81 | } |
82 | |
83 | /* Extract an affine expression from the mult_expr E. */ |
84 | |
85 | static isl_pw_aff * |
86 | extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space) |
87 | { |
88 | isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0), |
89 | isl_space_copy (space)); |
90 | isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space); |
91 | |
92 | if (!isl_pw_aff_is_cst (lhs) |
93 | && !isl_pw_aff_is_cst (rhs)) |
94 | { |
95 | isl_pw_aff_free (lhs); |
96 | isl_pw_aff_free (rhs); |
97 | return NULL; |
98 | } |
99 | |
100 | return isl_pw_aff_mul (lhs, rhs); |
101 | } |
102 | |
103 | /* Return an isl identifier for the parameter P. */ |
104 | |
105 | static isl_id * |
106 | isl_id_for_parameter (scop_p s, tree p) |
107 | { |
108 | gcc_checking_assert (TREE_CODE (p) == SSA_NAME); |
109 | char name[14]; |
110 | snprintf (name, sizeof (name), "P_%d" , SSA_NAME_VERSION (p)); |
111 | return isl_id_alloc (s->isl_context, name, p); |
112 | } |
113 | |
114 | /* Return an isl identifier for the data reference DR. Data references and |
115 | scalar references get the same isl_id. They need to be comparable and are |
116 | distinguished through the first dimension, which contains the alias set or |
117 | SSA_NAME_VERSION number. */ |
118 | |
119 | static isl_id * |
120 | isl_id_for_dr (scop_p s) |
121 | { |
122 | return isl_id_alloc (s->isl_context, "" , 0); |
123 | } |
124 | |
125 | /* Extract an affine expression from the ssa_name E. */ |
126 | |
127 | static isl_pw_aff * |
128 | extract_affine_name (int dimension, __isl_take isl_space *space) |
129 | { |
130 | isl_set *dom = isl_set_universe (isl_space_copy (space)); |
131 | isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space)); |
132 | aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1); |
133 | return isl_pw_aff_alloc (dom, aff); |
134 | } |
135 | |
136 | /* Convert WI to a isl_val with CTX. */ |
137 | |
138 | static __isl_give isl_val * |
139 | isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi) |
140 | { |
141 | if (wi::neg_p (wi, SIGNED)) |
142 | { |
143 | widest_int mwi = -wi; |
144 | return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (), |
145 | sizeof (HOST_WIDE_INT), |
146 | mwi.get_val ())); |
147 | } |
148 | return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT), |
149 | wi.get_val ()); |
150 | } |
151 | |
152 | /* Extract an affine expression from the gmp constant G. */ |
153 | |
154 | static isl_pw_aff * |
155 | extract_affine_wi (const widest_int &g, __isl_take isl_space *space) |
156 | { |
157 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); |
158 | isl_aff *aff = isl_aff_zero_on_domain (ls); |
159 | isl_set *dom = isl_set_universe (space); |
160 | isl_ctx *ct = isl_aff_get_ctx (aff); |
161 | isl_val *v = isl_val_int_from_wi (ct, g); |
162 | aff = isl_aff_add_constant_val (aff, v); |
163 | |
164 | return isl_pw_aff_alloc (dom, aff); |
165 | } |
166 | |
167 | /* Extract an affine expression from the integer_cst E. */ |
168 | |
169 | static isl_pw_aff * |
170 | extract_affine_int (tree e, __isl_take isl_space *space) |
171 | { |
172 | isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space); |
173 | return res; |
174 | } |
175 | |
176 | /* Compute pwaff mod 2^width. */ |
177 | |
178 | static isl_pw_aff * |
179 | wrap (isl_pw_aff *pwaff, unsigned width) |
180 | { |
181 | isl_val *mod; |
182 | |
183 | mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width); |
184 | mod = isl_val_2exp (mod); |
185 | pwaff = isl_pw_aff_mod_val (pwaff, mod); |
186 | |
187 | return pwaff; |
188 | } |
189 | |
190 | /* When parameter NAME is in REGION, returns its index in SESE_PARAMS. |
191 | Otherwise returns -1. */ |
192 | |
193 | static inline int |
194 | parameter_index_in_region (tree name, sese_info_p region) |
195 | { |
196 | int i; |
197 | tree p; |
198 | FOR_EACH_VEC_ELT (region->params, i, p) |
199 | if (p == name) |
200 | return i; |
201 | return -1; |
202 | } |
203 | |
204 | /* Extract an affine expression from the tree E in the scop S. */ |
205 | |
206 | static isl_pw_aff * |
207 | extract_affine (scop_p s, tree e, __isl_take isl_space *space) |
208 | { |
209 | isl_pw_aff *lhs, *rhs, *res; |
210 | |
211 | if (e == chrec_dont_know) { |
212 | isl_space_free (space); |
213 | return NULL; |
214 | } |
215 | |
216 | tree type = TREE_TYPE (e); |
217 | switch (TREE_CODE (e)) |
218 | { |
219 | case POLYNOMIAL_CHREC: |
220 | res = extract_affine_chrec (s, e, space); |
221 | break; |
222 | |
223 | case MULT_EXPR: |
224 | res = extract_affine_mul (s, e, space); |
225 | break; |
226 | |
227 | case POINTER_PLUS_EXPR: |
228 | { |
229 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
230 | /* The RHS of a pointer-plus expression is to be interpreted |
231 | as signed value. Try to look through a sign-changing conversion |
232 | first. */ |
233 | tree tem = TREE_OPERAND (e, 1); |
234 | STRIP_NOPS (tem); |
235 | rhs = extract_affine (s, tem, space); |
236 | if (TYPE_UNSIGNED (TREE_TYPE (tem))) |
237 | rhs = wrap (rhs, TYPE_PRECISION (type) - 1); |
238 | res = isl_pw_aff_add (lhs, rhs); |
239 | break; |
240 | } |
241 | |
242 | case PLUS_EXPR: |
243 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
244 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); |
245 | res = isl_pw_aff_add (lhs, rhs); |
246 | break; |
247 | |
248 | case MINUS_EXPR: |
249 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
250 | rhs = extract_affine (s, TREE_OPERAND (e, 1), space); |
251 | res = isl_pw_aff_sub (lhs, rhs); |
252 | break; |
253 | |
254 | case BIT_NOT_EXPR: |
255 | lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space)); |
256 | rhs = extract_affine (s, TREE_OPERAND (e, 0), space); |
257 | res = isl_pw_aff_sub (lhs, rhs); |
258 | /* We need to always wrap the result of a bitwise operation. */ |
259 | return wrap (res, TYPE_PRECISION (type) - (TYPE_UNSIGNED (type) ? 0 : 1)); |
260 | |
261 | case NEGATE_EXPR: |
262 | lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space)); |
263 | rhs = extract_affine (s, integer_minus_one_node, space); |
264 | res = isl_pw_aff_mul (lhs, rhs); |
265 | break; |
266 | |
267 | case SSA_NAME: |
268 | { |
269 | gcc_assert (! defined_in_sese_p (e, s->scop_info->region)); |
270 | int dim = parameter_index_in_region (e, s->scop_info); |
271 | gcc_assert (dim != -1); |
272 | /* No need to wrap a parameter. */ |
273 | return extract_affine_name (dim, space); |
274 | } |
275 | |
276 | case INTEGER_CST: |
277 | res = extract_affine_int (e, space); |
278 | /* No need to wrap a single integer. */ |
279 | return res; |
280 | |
281 | CASE_CONVERT: |
282 | { |
283 | tree itype = TREE_TYPE (TREE_OPERAND (e, 0)); |
284 | res = extract_affine (s, TREE_OPERAND (e, 0), space); |
285 | /* Signed values, even if overflow is undefined, get modulo-reduced. |
286 | But only if not all values of the old type fit in the new. */ |
287 | if (! TYPE_UNSIGNED (type) |
288 | && ((TYPE_UNSIGNED (itype) |
289 | && TYPE_PRECISION (type) <= TYPE_PRECISION (itype)) |
290 | || TYPE_PRECISION (type) < TYPE_PRECISION (itype))) |
291 | res = wrap (res, TYPE_PRECISION (type) - 1); |
292 | else if (TYPE_UNSIGNED (type) |
293 | && (!TYPE_UNSIGNED (itype) |
294 | || TYPE_PRECISION (type) < TYPE_PRECISION (itype))) |
295 | res = wrap (res, TYPE_PRECISION (type)); |
296 | return res; |
297 | } |
298 | |
299 | case NON_LVALUE_EXPR: |
300 | res = extract_affine (s, TREE_OPERAND (e, 0), space); |
301 | break; |
302 | |
303 | default: |
304 | gcc_unreachable (); |
305 | break; |
306 | } |
307 | |
308 | /* For all wrapping arithmetic wrap the result. */ |
309 | if (TYPE_OVERFLOW_WRAPS (type)) |
310 | res = wrap (res, TYPE_PRECISION (type)); |
311 | |
312 | return res; |
313 | } |
314 | |
315 | /* Returns a linear expression for tree T evaluated in PBB. */ |
316 | |
317 | static isl_pw_aff * |
318 | create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t) |
319 | { |
320 | scop_p scop = PBB_SCOP (pbb); |
321 | |
322 | t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t); |
323 | |
324 | gcc_assert (!chrec_contains_undetermined (t)); |
325 | gcc_assert (!automatically_generated_chrec_p (t)); |
326 | |
327 | return extract_affine (scop, t, isl_set_get_space (pbb->domain)); |
328 | } |
329 | |
330 | /* Add conditional statement STMT to pbb. CODE is used as the comparison |
331 | operator. This allows us to invert the condition or to handle |
332 | inequalities. */ |
333 | |
334 | static void |
335 | add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) |
336 | { |
337 | loop_p loop = gimple_bb (stmt)->loop_father; |
338 | isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt)); |
339 | isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt)); |
340 | |
341 | isl_set *cond; |
342 | switch (code) |
343 | { |
344 | case LT_EXPR: |
345 | cond = isl_pw_aff_lt_set (lhs, rhs); |
346 | break; |
347 | |
348 | case GT_EXPR: |
349 | cond = isl_pw_aff_gt_set (lhs, rhs); |
350 | break; |
351 | |
352 | case LE_EXPR: |
353 | cond = isl_pw_aff_le_set (lhs, rhs); |
354 | break; |
355 | |
356 | case GE_EXPR: |
357 | cond = isl_pw_aff_ge_set (lhs, rhs); |
358 | break; |
359 | |
360 | case EQ_EXPR: |
361 | cond = isl_pw_aff_eq_set (lhs, rhs); |
362 | break; |
363 | |
364 | case NE_EXPR: |
365 | cond = isl_pw_aff_ne_set (lhs, rhs); |
366 | break; |
367 | |
368 | default: |
369 | gcc_unreachable (); |
370 | } |
371 | |
372 | cond = isl_set_coalesce (cond); |
373 | cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); |
374 | pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond)); |
375 | } |
376 | |
377 | /* Add conditions to the domain of PBB. */ |
378 | |
379 | static void |
380 | add_conditions_to_domain (poly_bb_p pbb) |
381 | { |
382 | unsigned int i; |
383 | gimple *stmt; |
384 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
385 | |
386 | if (GBB_CONDITIONS (gbb).is_empty ()) |
387 | return; |
388 | |
389 | FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) |
390 | switch (gimple_code (stmt)) |
391 | { |
392 | case GIMPLE_COND: |
393 | { |
394 | /* Don't constrain on anything else than INTEGRAL_TYPE_P. */ |
395 | tree cmp_type = TREE_TYPE (gimple_cond_lhs (stmt)); |
396 | if (!INTEGRAL_TYPE_P (cmp_type)) |
397 | break; |
398 | |
399 | gcond *cond_stmt = as_a <gcond *> (stmt); |
400 | enum tree_code code = gimple_cond_code (cond_stmt); |
401 | |
402 | /* The conditions for ELSE-branches are inverted. */ |
403 | if (!GBB_CONDITION_CASES (gbb)[i]) |
404 | code = invert_tree_comparison (code, false); |
405 | |
406 | add_condition_to_pbb (pbb, cond_stmt, code); |
407 | break; |
408 | } |
409 | |
410 | default: |
411 | gcc_unreachable (); |
412 | break; |
413 | } |
414 | } |
415 | |
416 | /* Add constraints on the possible values of parameter P from the type |
417 | of P. */ |
418 | |
419 | static void |
420 | add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter) |
421 | { |
422 | tree type = TREE_TYPE (parameter); |
423 | value_range r; |
424 | wide_int min, max; |
425 | |
426 | gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)); |
427 | |
428 | if (INTEGRAL_TYPE_P (type) |
429 | && get_range_query (cfun)->range_of_expr (r, parameter) |
430 | && !r.undefined_p ()) |
431 | { |
432 | min = r.lower_bound (); |
433 | max = r.upper_bound (); |
434 | } |
435 | else |
436 | { |
437 | min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); |
438 | max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); |
439 | } |
440 | |
441 | isl_space *space = isl_set_get_space (scop->param_context); |
442 | isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space)); |
443 | isl_val *v = isl_val_int_from_wi (scop->isl_context, |
444 | widest_int::from (min, TYPE_SIGN (type))); |
445 | v = isl_val_neg (v); |
446 | c = isl_constraint_set_constant_val (c, v); |
447 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1); |
448 | scop->param_context = isl_set_coalesce |
449 | (isl_set_add_constraint (scop->param_context, c)); |
450 | |
451 | space = isl_set_get_space (scop->param_context); |
452 | c = isl_inequality_alloc (isl_local_space_from_space (space)); |
453 | v = isl_val_int_from_wi (scop->isl_context, |
454 | widest_int::from (max, TYPE_SIGN (type))); |
455 | c = isl_constraint_set_constant_val (c, v); |
456 | c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1); |
457 | scop->param_context = isl_set_coalesce |
458 | (isl_set_add_constraint (scop->param_context, c)); |
459 | } |
460 | |
461 | /* Add a constrain to the ACCESSES polyhedron for the alias set of |
462 | data reference DR. ACCESSP_NB_DIMS is the dimension of the |
463 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration |
464 | domain. */ |
465 | |
466 | static isl_map * |
467 | pdr_add_alias_set (isl_map *acc, dr_info &dri) |
468 | { |
469 | isl_constraint *c = isl_equality_alloc |
470 | (isl_local_space_from_space (isl_map_get_space (acc))); |
471 | /* Positive numbers for all alias sets. */ |
472 | c = isl_constraint_set_constant_si (c, -dri.alias_set); |
473 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); |
474 | |
475 | return isl_map_add_constraint (acc, c); |
476 | } |
477 | |
478 | /* Assign the affine expression INDEX to the output dimension POS of |
479 | MAP and return the result. */ |
480 | |
481 | static isl_map * |
482 | set_index (isl_map *map, int pos, isl_pw_aff *index) |
483 | { |
484 | isl_map *index_map; |
485 | int len = isl_map_dim (map, isl_dim_out); |
486 | isl_id *id; |
487 | |
488 | index_map = isl_map_from_pw_aff (index); |
489 | index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos); |
490 | index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1); |
491 | |
492 | id = isl_map_get_tuple_id (map, isl_dim_out); |
493 | index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id); |
494 | id = isl_map_get_tuple_id (map, isl_dim_in); |
495 | index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id); |
496 | |
497 | return isl_map_intersect (map, index_map); |
498 | } |
499 | |
500 | /* Add to ACCESSES polyhedron equalities defining the access functions |
501 | to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES |
502 | polyhedron, DOM_NB_DIMS is the dimension of the iteration domain. |
503 | PBB is the poly_bb_p that contains the data reference DR. */ |
504 | |
505 | static isl_map * |
506 | pdr_add_memory_accesses (isl_map *acc, dr_info &dri) |
507 | { |
508 | data_reference_p dr = dri.dr; |
509 | poly_bb_p pbb = dri.pbb; |
510 | int i, nb_subscripts = DR_NUM_DIMENSIONS (dr); |
511 | scop_p scop = PBB_SCOP (pbb); |
512 | |
513 | for (i = 0; i < nb_subscripts; i++) |
514 | { |
515 | isl_pw_aff *aff; |
516 | tree afn = DR_ACCESS_FN (dr, i); |
517 | |
518 | aff = extract_affine (scop, afn, |
519 | isl_space_domain (isl_map_get_space (acc))); |
520 | acc = set_index (acc, nb_subscripts - i , aff); |
521 | } |
522 | |
523 | return isl_map_coalesce (acc); |
524 | } |
525 | |
526 | /* Return true when the LOW and HIGH bounds of an array reference REF are valid |
527 | to extract constraints on accessed elements of the array. Returning false is |
528 | the conservative answer. */ |
529 | |
530 | static bool |
531 | bounds_are_valid (tree ref, tree low, tree high) |
532 | { |
533 | if (!high) |
534 | return false; |
535 | |
536 | if (!tree_fits_shwi_p (low) |
537 | || !tree_fits_shwi_p (high)) |
538 | return false; |
539 | |
540 | /* An array that has flexible size may extend over |
541 | their declared size. */ |
542 | if (array_ref_flexible_size_p (ref) |
543 | && operand_equal_p (low, high, 0)) |
544 | return false; |
545 | |
546 | /* Fortran has some arrays where high bound is -1 and low is 0. */ |
547 | if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low))) |
548 | return false; |
549 | |
550 | return true; |
551 | } |
552 | |
553 | /* Add constrains representing the size of the accessed data to the |
554 | ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the |
555 | ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration |
556 | domain. */ |
557 | |
558 | static isl_set * |
559 | pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop, |
560 | data_reference_p dr) |
561 | { |
562 | tree ref = DR_REF (dr); |
563 | |
564 | int nb_subscripts = DR_NUM_DIMENSIONS (dr); |
565 | for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0)) |
566 | { |
567 | if (TREE_CODE (ref) != ARRAY_REF) |
568 | return subscript_sizes; |
569 | |
570 | tree low = array_ref_low_bound (ref); |
571 | tree high = array_ref_up_bound (ref); |
572 | |
573 | if (!bounds_are_valid (ref, low, high)) |
574 | continue; |
575 | |
576 | isl_space *space = isl_set_get_space (subscript_sizes); |
577 | isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space)); |
578 | isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space)); |
579 | |
580 | /* high >= 0 */ |
581 | isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub)); |
582 | valid = isl_set_project_out (valid, isl_dim_set, 0, |
583 | isl_set_dim (valid, isl_dim_set)); |
584 | scop->param_context = isl_set_coalesce |
585 | (isl_set_intersect (scop->param_context, valid)); |
586 | |
587 | isl_aff *aff |
588 | = isl_aff_zero_on_domain (isl_local_space_from_space (space)); |
589 | aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1); |
590 | isl_set *univ |
591 | = isl_set_universe (isl_space_domain (isl_aff_get_space (aff))); |
592 | isl_pw_aff *index = isl_pw_aff_alloc (univ, aff); |
593 | |
594 | isl_id *id = isl_set_get_tuple_id (subscript_sizes); |
595 | lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id)); |
596 | ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id); |
597 | |
598 | /* low <= sub_i <= high */ |
599 | isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb); |
600 | isl_set *ubs = isl_pw_aff_le_set (index, ub); |
601 | subscript_sizes = isl_set_intersect (subscript_sizes, lbs); |
602 | subscript_sizes = isl_set_intersect (subscript_sizes, ubs); |
603 | } |
604 | |
605 | return isl_set_coalesce (subscript_sizes); |
606 | } |
607 | |
608 | /* Build data accesses for DRI. */ |
609 | |
610 | static void |
611 | build_poly_dr (dr_info &dri) |
612 | { |
613 | isl_map *acc; |
614 | isl_set *subscript_sizes; |
615 | poly_bb_p pbb = dri.pbb; |
616 | data_reference_p dr = dri.dr; |
617 | scop_p scop = PBB_SCOP (pbb); |
618 | isl_id *id = isl_id_for_dr (scop); |
619 | |
620 | { |
621 | isl_space *dc = isl_set_get_space (pbb->domain); |
622 | int nb_out = 1 + DR_NUM_DIMENSIONS (dr); |
623 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), |
624 | isl_dim_out, nb_out); |
625 | |
626 | acc = isl_map_universe (space); |
627 | acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id)); |
628 | } |
629 | |
630 | acc = pdr_add_alias_set (acc, dri); |
631 | acc = pdr_add_memory_accesses (acc, dri); |
632 | |
633 | { |
634 | int nb = 1 + DR_NUM_DIMENSIONS (dr); |
635 | isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb); |
636 | |
637 | space = isl_space_set_tuple_id (space, isl_dim_set, id); |
638 | subscript_sizes = isl_set_nat_universe (space); |
639 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, |
640 | dri.alias_set); |
641 | subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr); |
642 | } |
643 | |
644 | new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, |
645 | acc, subscript_sizes); |
646 | } |
647 | |
648 | static void |
649 | build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind, |
650 | isl_map *acc, isl_set *subscript_sizes) |
651 | { |
652 | scop_p scop = PBB_SCOP (pbb); |
653 | /* Each scalar variable has a unique alias set number starting from |
654 | the maximum alias set assigned to a dr. */ |
655 | int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var); |
656 | subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0, |
657 | alias_set); |
658 | |
659 | /* Add a constrain to the ACCESSES polyhedron for the alias set of |
660 | the reference. */ |
661 | isl_constraint *c |
662 | = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc))); |
663 | c = isl_constraint_set_constant_si (c, -alias_set); |
664 | c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1); |
665 | |
666 | new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c), |
667 | subscript_sizes); |
668 | } |
669 | |
670 | /* Record all cross basic block scalar variables in PBB. */ |
671 | |
672 | static void |
673 | build_poly_sr (poly_bb_p pbb) |
674 | { |
675 | scop_p scop = PBB_SCOP (pbb); |
676 | gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); |
677 | vec<scalar_use> &reads = gbb->read_scalar_refs; |
678 | vec<tree> &writes = gbb->write_scalar_refs; |
679 | |
680 | isl_space *dc = isl_set_get_space (pbb->domain); |
681 | int nb_out = 1; |
682 | isl_space *space = isl_space_add_dims (isl_space_from_domain (dc), |
683 | isl_dim_out, nb_out); |
684 | isl_id *id = isl_id_for_dr (scop); |
685 | space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id)); |
686 | isl_map *acc = isl_map_universe (isl_space_copy (space)); |
687 | acc = isl_map_set_tuple_id (acc, isl_dim_out, id); |
688 | isl_set *subscript_sizes = isl_set_nat_universe (space); |
689 | |
690 | int i; |
691 | tree var; |
692 | FOR_EACH_VEC_ELT (writes, i, var) |
693 | build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE, |
694 | isl_map_copy (acc), isl_set_copy (subscript_sizes)); |
695 | |
696 | scalar_use *use; |
697 | FOR_EACH_VEC_ELT (reads, i, use) |
698 | build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc), |
699 | isl_set_copy (subscript_sizes)); |
700 | |
701 | isl_map_free (acc); |
702 | isl_set_free (subscript_sizes); |
703 | } |
704 | |
705 | /* Build data references in SCOP. */ |
706 | |
707 | static void |
708 | build_scop_drs (scop_p scop) |
709 | { |
710 | int i; |
711 | dr_info *dri; |
712 | FOR_EACH_VEC_ELT (scop->drs, i, dri) |
713 | build_poly_dr (*dri); |
714 | |
715 | poly_bb_p pbb; |
716 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
717 | build_poly_sr (pbb); |
718 | } |
719 | |
720 | /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */ |
721 | |
722 | static isl_set * |
723 | add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop) |
724 | { |
725 | int loop_index = isl_set_dim (domain, isl_dim_set); |
726 | domain = isl_set_add_dims (domain, isl_dim_set, 1); |
727 | char name[50]; |
728 | snprintf (name, sizeof(name), "i%d" , loop->num); |
729 | isl_id *label = isl_id_alloc (scop->isl_context, name, NULL); |
730 | return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label); |
731 | } |
732 | |
733 | /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */ |
734 | |
735 | static isl_set * |
736 | add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop, |
737 | loop_p context) |
738 | { |
739 | if (loop == context) |
740 | return domain; |
741 | const sese_l ®ion = scop->scop_info->region; |
742 | if (!loop_in_sese_p (loop, region)) |
743 | return domain; |
744 | |
745 | /* Recursion all the way up to the context loop. */ |
746 | domain = add_loop_constraints (scop, domain, loop_outer (loop), context); |
747 | |
748 | /* Then, build constraints over the loop in post-order: outer to inner. */ |
749 | |
750 | int loop_index = isl_set_dim (domain, isl_dim_set); |
751 | if (dump_file) |
752 | fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the " |
753 | "domain for loop_%d.\n" , loop->num); |
754 | domain = add_iter_domain_dimension (domain, loop, scop); |
755 | isl_space *space = isl_set_get_space (domain); |
756 | |
757 | /* 0 <= loop_i */ |
758 | isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space)); |
759 | isl_constraint *c = isl_inequality_alloc (ls); |
760 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1); |
761 | if (dump_file) |
762 | { |
763 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: " ); |
764 | print_isl_constraint (dump_file, c); |
765 | } |
766 | domain = isl_set_add_constraint (domain, c); |
767 | |
768 | tree nb_iters = number_of_latch_executions (loop); |
769 | if (TREE_CODE (nb_iters) == INTEGER_CST) |
770 | { |
771 | /* loop_i <= cst_nb_iters */ |
772 | isl_local_space *ls = isl_local_space_from_space (space); |
773 | isl_constraint *c = isl_inequality_alloc (ls); |
774 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); |
775 | isl_val *v |
776 | = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters)); |
777 | c = isl_constraint_set_constant_val (c, v); |
778 | return isl_set_add_constraint (domain, c); |
779 | } |
780 | /* loop_i <= expr_nb_iters */ |
781 | gcc_assert (!chrec_contains_undetermined (nb_iters)); |
782 | nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters); |
783 | gcc_assert (!chrec_contains_undetermined (nb_iters)); |
784 | |
785 | isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters, |
786 | isl_space_copy (space)); |
787 | isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters)); |
788 | valid = isl_set_project_out (valid, isl_dim_set, 0, |
789 | isl_set_dim (valid, isl_dim_set)); |
790 | |
791 | if (valid) |
792 | scop->param_context = isl_set_intersect (scop->param_context, valid); |
793 | |
794 | ls = isl_local_space_from_space (isl_space_copy (space)); |
795 | isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls), |
796 | isl_dim_in, loop_index, 1); |
797 | isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i), |
798 | isl_pw_aff_copy (aff_nb_iters)); |
799 | if (dump_file) |
800 | { |
801 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: " ); |
802 | print_isl_set (dump_file, le); |
803 | } |
804 | domain = isl_set_intersect (domain, le); |
805 | |
806 | widest_int nit; |
807 | if (!max_stmt_executions (loop, &nit)) |
808 | { |
809 | isl_pw_aff_free (aff_nb_iters); |
810 | isl_space_free (space); |
811 | return domain; |
812 | } |
813 | |
814 | /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we |
815 | do not know whether the loop executes at least once. */ |
816 | --nit; |
817 | |
818 | isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space)); |
819 | isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters); |
820 | x = isl_set_project_out (x, isl_dim_set, 0, |
821 | isl_set_dim (x, isl_dim_set)); |
822 | scop->param_context = isl_set_intersect (scop->param_context, x); |
823 | |
824 | ls = isl_local_space_from_space (space); |
825 | c = isl_inequality_alloc (ls); |
826 | c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1); |
827 | isl_val *v = isl_val_int_from_wi (scop->isl_context, nit); |
828 | c = isl_constraint_set_constant_val (c, v); |
829 | |
830 | if (dump_file) |
831 | { |
832 | fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: " ); |
833 | print_isl_constraint (dump_file, c); |
834 | } |
835 | |
836 | return isl_set_add_constraint (domain, c); |
837 | } |
838 | |
839 | /* Builds the original iteration domains for each pbb in the SCOP. */ |
840 | |
841 | static int |
842 | build_iteration_domains (scop_p scop, __isl_keep isl_set *context, |
843 | int index, loop_p context_loop) |
844 | { |
845 | loop_p current = pbb_loop (scop->pbbs[index]); |
846 | isl_set *domain = isl_set_copy (context); |
847 | domain = add_loop_constraints (scop, domain, current, context_loop); |
848 | const sese_l ®ion = scop->scop_info->region; |
849 | |
850 | int i; |
851 | poly_bb_p pbb; |
852 | FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index) |
853 | { |
854 | loop_p loop = pbb_loop (pbb); |
855 | if (current == loop) |
856 | { |
857 | pbb->iterators = isl_set_copy (domain); |
858 | pbb->domain = isl_set_copy (domain); |
859 | pbb->domain = isl_set_set_tuple_id (pbb->domain, |
860 | isl_id_for_pbb (scop, pbb)); |
861 | add_conditions_to_domain (pbb); |
862 | |
863 | if (dump_file) |
864 | { |
865 | fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: " , |
866 | pbb_index (pbb)); |
867 | print_isl_set (dump_file, domain); |
868 | } |
869 | continue; |
870 | } |
871 | |
872 | while (loop_in_sese_p (loop, region) |
873 | && current != loop) |
874 | loop = loop_outer (loop); |
875 | |
876 | if (current != loop) |
877 | { |
878 | /* A statement in a different loop nest than CURRENT loop. */ |
879 | isl_set_free (domain); |
880 | return i; |
881 | } |
882 | |
883 | /* A statement nested in the CURRENT loop. */ |
884 | i = build_iteration_domains (scop, domain, i, current); |
885 | i--; |
886 | } |
887 | |
888 | isl_set_free (domain); |
889 | return i; |
890 | } |
891 | |
892 | /* Assign dimension for each parameter in SCOP and add constraints for the |
893 | parameters. */ |
894 | |
895 | static void |
896 | build_scop_context (scop_p scop) |
897 | { |
898 | sese_info_p region = scop->scop_info; |
899 | unsigned nbp = sese_nb_params (region); |
900 | isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); |
901 | |
902 | unsigned i; |
903 | tree p; |
904 | FOR_EACH_VEC_ELT (region->params, i, p) |
905 | space = isl_space_set_dim_id (space, isl_dim_param, i, |
906 | isl_id_for_parameter (scop, p)); |
907 | |
908 | scop->param_context = isl_set_universe (space); |
909 | |
910 | FOR_EACH_VEC_ELT (region->params, i, p) |
911 | add_param_constraints (scop, i, p); |
912 | } |
913 | |
914 | /* Return true when loop A is nested in loop B. */ |
915 | |
916 | static bool |
917 | nested_in (loop_p a, loop_p b) |
918 | { |
919 | return b == find_common_loop (a, b); |
920 | } |
921 | |
922 | /* Return the loop at a specific SCOP->pbbs[*INDEX]. */ |
923 | static loop_p |
924 | loop_at (scop_p scop, int *index) |
925 | { |
926 | return pbb_loop (scop->pbbs[*index]); |
927 | } |
928 | |
929 | /* Return the index of any pbb belonging to loop or a subloop of A. */ |
930 | |
931 | static int |
932 | index_outermost_in_loop (loop_p a, scop_p scop) |
933 | { |
934 | int i, outermost = -1; |
935 | int last_depth = -1; |
936 | poly_bb_p pbb; |
937 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
938 | if (nested_in (pbb_loop (pbb), a) |
939 | && (last_depth == -1 |
940 | || last_depth > (int) loop_depth (pbb_loop (pbb)))) |
941 | { |
942 | outermost = i; |
943 | last_depth = loop_depth (pbb_loop (pbb)); |
944 | } |
945 | return outermost; |
946 | } |
947 | |
948 | /* Return the index of any pbb belonging to loop or a subloop of A. */ |
949 | |
950 | static int |
951 | index_pbb_in_loop (loop_p a, scop_p scop) |
952 | { |
953 | int i; |
954 | poly_bb_p pbb; |
955 | FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) |
956 | if (pbb_loop (pbb) == a) |
957 | return i; |
958 | return -1; |
959 | } |
960 | |
961 | static poly_bb_p |
962 | outermost_pbb_in (loop_p loop, scop_p scop) |
963 | { |
964 | int x = index_pbb_in_loop (loop, scop); |
965 | if (x == -1) |
966 | x = index_outermost_in_loop (loop, scop); |
967 | return scop->pbbs[x]; |
968 | } |
969 | |
970 | static isl_schedule * |
971 | add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b) |
972 | { |
973 | gcc_assert (a || b); |
974 | |
975 | if (!a) |
976 | return b; |
977 | |
978 | if (!b) |
979 | return a; |
980 | |
981 | return isl_schedule_sequence (a, b); |
982 | } |
983 | |
984 | struct map_to_dimension_data { |
985 | int n; |
986 | isl_union_pw_multi_aff *res; |
987 | }; |
988 | |
989 | /* Create a function that maps the elements of SET to its N-th dimension and add |
990 | it to USER->res. */ |
991 | |
992 | static isl_stat |
993 | add_outer_projection (__isl_take isl_set *set, void *user) |
994 | { |
995 | struct map_to_dimension_data *data = (struct map_to_dimension_data *) user; |
996 | int dim = isl_set_dim (set, isl_dim_set); |
997 | isl_space *space = isl_set_get_space (set); |
998 | |
999 | gcc_assert (dim >= data->n); |
1000 | isl_pw_multi_aff *pma |
1001 | = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n, |
1002 | dim - data->n); |
1003 | data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma); |
1004 | |
1005 | isl_set_free (set); |
1006 | return isl_stat_ok; |
1007 | } |
1008 | |
1009 | /* Return SET in which all inner dimensions above N are removed. */ |
1010 | |
1011 | static isl_multi_union_pw_aff * |
1012 | outer_projection_mupa (__isl_take isl_union_set *set, int n) |
1013 | { |
1014 | gcc_assert (n >= 0); |
1015 | gcc_assert (set); |
1016 | gcc_assert (!isl_union_set_is_empty (set)); |
1017 | |
1018 | isl_space *space = isl_union_set_get_space (set); |
1019 | isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space); |
1020 | |
1021 | struct map_to_dimension_data data = {n, pwaff}; |
1022 | |
1023 | if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0) |
1024 | data.res = isl_union_pw_multi_aff_free (data.res); |
1025 | |
1026 | isl_union_set_free (set); |
1027 | return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res); |
1028 | } |
1029 | |
1030 | /* Embed SCHEDULE in the constraints of the LOOP domain. */ |
1031 | |
1032 | static isl_schedule * |
1033 | add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop, |
1034 | scop_p scop) |
1035 | { |
1036 | poly_bb_p pbb = outermost_pbb_in (loop, scop); |
1037 | isl_set *iterators = pbb->iterators; |
1038 | |
1039 | int empty = isl_set_is_empty (iterators); |
1040 | if (empty < 0 || empty) |
1041 | return empty < 0 ? isl_schedule_free (schedule) : schedule; |
1042 | |
1043 | isl_union_set *domain = isl_schedule_get_domain (schedule); |
1044 | /* We cannot apply an empty domain to pbbs in this loop so return early. */ |
1045 | if (isl_union_set_is_empty (domain)) |
1046 | { |
1047 | isl_union_set_free (domain); |
1048 | return schedule; |
1049 | } |
1050 | |
1051 | isl_space *space = isl_set_get_space (iterators); |
1052 | int loop_index = isl_space_dim (space, isl_dim_set) - 1; |
1053 | |
1054 | loop_p ploop = pbb_loop (pbb); |
1055 | while (loop != ploop) |
1056 | { |
1057 | --loop_index; |
1058 | ploop = loop_outer (ploop); |
1059 | } |
1060 | |
1061 | isl_local_space *ls = isl_local_space_from_space (space); |
1062 | isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index); |
1063 | isl_multi_aff *prefix = isl_multi_aff_from_aff (aff); |
1064 | char name[50]; |
1065 | snprintf (name, sizeof(name), "L_%d" , loop->num); |
1066 | isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule), |
1067 | name, NULL); |
1068 | prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label); |
1069 | |
1070 | int n = isl_multi_aff_dim (prefix, isl_dim_in); |
1071 | isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n); |
1072 | mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix); |
1073 | return isl_schedule_insert_partial_schedule (schedule, mupa); |
1074 | } |
1075 | |
1076 | /* Build schedule for the pbb at INDEX. */ |
1077 | |
1078 | static isl_schedule * |
1079 | build_schedule_pbb (scop_p scop, int *index) |
1080 | { |
1081 | poly_bb_p pbb = scop->pbbs[*index]; |
1082 | ++*index; |
1083 | isl_set *domain = isl_set_copy (pbb->domain); |
1084 | isl_union_set *ud = isl_union_set_from_set (domain); |
1085 | return isl_schedule_from_domain (ud); |
1086 | } |
1087 | |
1088 | static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p); |
1089 | |
1090 | /* Build the schedule of the loop containing the SCOP pbb at INDEX. */ |
1091 | |
1092 | static isl_schedule * |
1093 | build_schedule_loop (scop_p scop, int *index) |
1094 | { |
1095 | int max = scop->pbbs.length (); |
1096 | gcc_assert (*index < max); |
1097 | loop_p loop = loop_at (scop, index); |
1098 | |
1099 | isl_schedule *s = NULL; |
1100 | while (nested_in (loop_at (scop, index), loop)) |
1101 | { |
1102 | if (loop == loop_at (scop, index)) |
1103 | s = add_in_sequence (s, build_schedule_pbb (scop, index)); |
1104 | else |
1105 | s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop)); |
1106 | |
1107 | if (*index == max) |
1108 | break; |
1109 | } |
1110 | |
1111 | return add_loop_schedule (s, loop, scop); |
1112 | } |
1113 | |
1114 | /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops. |
1115 | When CONTEXT_LOOP is null, embed the schedule in all loops contained in the |
1116 | SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the |
1117 | maximal loop nest contained within CONTEXT_LOOP. */ |
1118 | |
1119 | static isl_schedule * |
1120 | embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop, |
1121 | loop_p loop, int *index, loop_p context_loop) |
1122 | { |
1123 | loop_p outer = loop_outer (loop); |
1124 | sese_l region = scop->scop_info->region; |
1125 | if (context_loop == outer |
1126 | || !loop_in_sese_p (outer, region)) |
1127 | return s; |
1128 | |
1129 | int max = scop->pbbs.length (); |
1130 | if (*index == max |
1131 | || (context_loop && !nested_in (loop_at (scop, index), context_loop)) |
1132 | || (!context_loop |
1133 | && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)), |
1134 | region))) |
1135 | return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), |
1136 | scop, outer, index, context_loop); |
1137 | |
1138 | bool a_pbb; |
1139 | while ((a_pbb = (outer == loop_at (scop, index))) |
1140 | || nested_in (loop_at (scop, index), outer)) |
1141 | { |
1142 | if (a_pbb) |
1143 | s = add_in_sequence (s, build_schedule_pbb (scop, index)); |
1144 | else |
1145 | s = add_in_sequence (s, build_schedule_loop (scop, index)); |
1146 | |
1147 | if (*index == max) |
1148 | break; |
1149 | } |
1150 | |
1151 | /* We reached the end of the OUTER loop: embed S in OUTER. */ |
1152 | return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop, |
1153 | outer, index, context_loop); |
1154 | } |
1155 | |
1156 | /* Build schedule for the full loop nest containing the pbb at INDEX. When |
1157 | CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP |
1158 | surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop |
1159 | nest contained within CONTEXT_LOOP. */ |
1160 | |
1161 | static isl_schedule * |
1162 | build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop) |
1163 | { |
1164 | gcc_assert (*index != (int) scop->pbbs.length ()); |
1165 | |
1166 | loop_p loop = loop_at (scop, index); |
1167 | isl_schedule *s = build_schedule_loop (scop, index); |
1168 | return embed_in_surrounding_loops (s, scop, loop, index, context_loop); |
1169 | } |
1170 | |
1171 | /* Build the schedule of the SCOP. */ |
1172 | |
1173 | static void |
1174 | build_original_schedule (scop_p scop) |
1175 | { |
1176 | int i = 0; |
1177 | int n = scop->pbbs.length (); |
1178 | while (i < n) |
1179 | { |
1180 | poly_bb_p pbb = scop->pbbs[i]; |
1181 | isl_schedule *s = NULL; |
1182 | if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region)) |
1183 | s = build_schedule_pbb (scop, &i); |
1184 | else |
1185 | s = build_schedule_loop_nest (scop, &i, NULL); |
1186 | |
1187 | scop->original_schedule = add_in_sequence (scop->original_schedule, s); |
1188 | } |
1189 | |
1190 | if (dump_file) |
1191 | { |
1192 | fprintf (dump_file, "[sese-to-poly] original schedule:\n" ); |
1193 | print_isl_schedule (dump_file, scop->original_schedule); |
1194 | } |
1195 | } |
1196 | |
1197 | /* Builds the polyhedral representation for a SESE region. */ |
1198 | |
1199 | bool |
1200 | build_poly_scop (scop_p scop) |
1201 | { |
1202 | int old_err = isl_options_get_on_error (scop->isl_context); |
1203 | isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE); |
1204 | |
1205 | build_scop_context (scop); |
1206 | |
1207 | unsigned i = 0; |
1208 | unsigned n = scop->pbbs.length (); |
1209 | while (i < n) |
1210 | i = build_iteration_domains (scop, scop->param_context, i, NULL); |
1211 | |
1212 | build_scop_drs (scop); |
1213 | build_original_schedule (scop); |
1214 | |
1215 | enum isl_error err = isl_ctx_last_error (scop->isl_context); |
1216 | isl_ctx_reset_error (scop->isl_context); |
1217 | isl_options_set_on_error (scop->isl_context, old_err); |
1218 | if (err != isl_error_none |
1219 | && dump_enabled_p ()) |
1220 | dump_printf (MSG_MISSED_OPTIMIZATION, |
1221 | "ISL error while building poly scop\n" ); |
1222 | |
1223 | return err == isl_error_none; |
1224 | } |
1225 | #endif /* HAVE_isl */ |
1226 | |