Line data Source code
1 : /* Conversion of SESE regions to Polyhedra.
2 : Copyright (C) 2009-2026 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 668 : isl_id_for_pbb (scop_p s, poly_bb_p pbb)
55 : {
56 668 : char name[14];
57 668 : snprintf (name, sizeof (name), "S_%d", pbb_index (pbb));
58 668 : 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 1202 : extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space)
67 : {
68 1202 : isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space));
69 1202 : isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space));
70 1202 : isl_local_space *ls = isl_local_space_from_space (space);
71 1202 : unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1;
72 1202 : isl_aff *loop = isl_aff_set_coefficient_si
73 1202 : (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1);
74 1202 : isl_pw_aff *l = isl_pw_aff_from_aff (loop);
75 :
76 : /* Before multiplying, make sure that the result is affine. */
77 1202 : gcc_assert (isl_pw_aff_is_cst (rhs)
78 : || isl_pw_aff_is_cst (l));
79 :
80 1202 : 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 1 : extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space)
87 : {
88 1 : isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0),
89 : isl_space_copy (space));
90 1 : isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
91 :
92 1 : if (!isl_pw_aff_is_cst (lhs)
93 1 : && !isl_pw_aff_is_cst (rhs))
94 : {
95 0 : isl_pw_aff_free (lhs);
96 0 : isl_pw_aff_free (rhs);
97 0 : return NULL;
98 : }
99 :
100 1 : return isl_pw_aff_mul (lhs, rhs);
101 : }
102 :
103 : /* Return an isl identifier for the parameter P. */
104 :
105 : static isl_id *
106 133 : isl_id_for_parameter (scop_p s, tree p)
107 : {
108 133 : gcc_checking_assert (TREE_CODE (p) == SSA_NAME);
109 133 : char name[14];
110 133 : snprintf (name, sizeof (name), "P_%d", SSA_NAME_VERSION (p));
111 133 : 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 1400 : isl_id_for_dr (scop_p s)
121 : {
122 0 : 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 321 : extract_affine_name (int dimension, __isl_take isl_space *space)
129 : {
130 321 : isl_set *dom = isl_set_universe (isl_space_copy (space));
131 321 : isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space));
132 321 : aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1);
133 321 : 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 5014 : isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi)
140 : {
141 5014 : if (wi::neg_p (wi, SIGNED))
142 : {
143 166 : widest_int mwi = -wi;
144 332 : return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (),
145 : sizeof (HOST_WIDE_INT),
146 166 : mwi.get_val ()));
147 166 : }
148 9696 : return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT),
149 9696 : wi.get_val ());
150 : }
151 :
152 : /* Extract an affine expression from the gmp constant G. */
153 :
154 : static isl_pw_aff *
155 4172 : extract_affine_wi (const widest_int &g, __isl_take isl_space *space)
156 : {
157 4172 : isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
158 4172 : isl_aff *aff = isl_aff_zero_on_domain (ls);
159 4172 : isl_set *dom = isl_set_universe (space);
160 4172 : isl_ctx *ct = isl_aff_get_ctx (aff);
161 4172 : isl_val *v = isl_val_int_from_wi (ct, g);
162 4172 : aff = isl_aff_add_constant_val (aff, v);
163 :
164 4172 : 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 4026 : extract_affine_int (tree e, __isl_take isl_space *space)
171 : {
172 4026 : isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space);
173 4026 : return res;
174 : }
175 :
176 : /* Compute pwaff mod 2^width. */
177 :
178 : static isl_pw_aff *
179 316 : wrap (isl_pw_aff *pwaff, unsigned width)
180 : {
181 316 : isl_val *mod;
182 :
183 316 : mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width);
184 316 : mod = isl_val_2exp (mod);
185 316 : pwaff = isl_pw_aff_mod_val (pwaff, mod);
186 :
187 316 : 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 321 : parameter_index_in_region (tree name, sese_info_p region)
195 : {
196 321 : int i;
197 321 : tree p;
198 514 : FOR_EACH_VEC_ELT (region->params, i, p)
199 514 : 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 4251 : extract_affine (scop_p s, tree e, __isl_take isl_space *space)
208 : {
209 4251 : isl_pw_aff *lhs, *rhs, *res;
210 :
211 4251 : if (e == chrec_dont_know) {
212 0 : isl_space_free (space);
213 0 : return NULL;
214 : }
215 :
216 4251 : tree type = TREE_TYPE (e);
217 4251 : switch (TREE_CODE (e))
218 : {
219 1202 : case POLYNOMIAL_CHREC:
220 1202 : res = extract_affine_chrec (s, e, space);
221 1202 : break;
222 :
223 1 : case MULT_EXPR:
224 1 : res = extract_affine_mul (s, e, space);
225 1 : break;
226 :
227 0 : case POINTER_PLUS_EXPR:
228 0 : {
229 0 : 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 0 : tree tem = TREE_OPERAND (e, 1);
234 0 : STRIP_NOPS (tem);
235 0 : rhs = extract_affine (s, tem, space);
236 0 : if (TYPE_UNSIGNED (TREE_TYPE (tem)))
237 0 : rhs = wrap (rhs, TYPE_PRECISION (type) - 1);
238 0 : res = isl_pw_aff_add (lhs, rhs);
239 0 : break;
240 : }
241 :
242 156 : case PLUS_EXPR:
243 156 : lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
244 156 : rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
245 156 : res = isl_pw_aff_add (lhs, rhs);
246 156 : break;
247 :
248 14 : case MINUS_EXPR:
249 14 : lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
250 14 : rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
251 14 : res = isl_pw_aff_sub (lhs, rhs);
252 14 : break;
253 :
254 0 : case BIT_NOT_EXPR:
255 0 : lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space));
256 0 : rhs = extract_affine (s, TREE_OPERAND (e, 0), space);
257 0 : res = isl_pw_aff_sub (lhs, rhs);
258 : /* We need to always wrap the result of a bitwise operation. */
259 0 : return wrap (res, TYPE_PRECISION (type) - (TYPE_UNSIGNED (type) ? 0 : 1));
260 :
261 7 : case NEGATE_EXPR:
262 7 : lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
263 7 : rhs = extract_affine (s, integer_minus_one_node, space);
264 7 : res = isl_pw_aff_mul (lhs, rhs);
265 7 : break;
266 :
267 321 : case SSA_NAME:
268 321 : {
269 321 : gcc_assert (! defined_in_sese_p (e, s->scop_info->region));
270 321 : int dim = parameter_index_in_region (e, s->scop_info);
271 321 : gcc_assert (dim != -1);
272 : /* No need to wrap a parameter. */
273 321 : return extract_affine_name (dim, space);
274 : }
275 :
276 2394 : case INTEGER_CST:
277 2394 : res = extract_affine_int (e, space);
278 : /* No need to wrap a single integer. */
279 2394 : return res;
280 :
281 156 : CASE_CONVERT:
282 156 : {
283 156 : tree itype = TREE_TYPE (TREE_OPERAND (e, 0));
284 156 : 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 156 : if (! TYPE_UNSIGNED (type)
288 156 : && ((TYPE_UNSIGNED (itype)
289 9 : && TYPE_PRECISION (type) <= TYPE_PRECISION (itype))
290 5 : || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
291 9 : res = wrap (res, TYPE_PRECISION (type) - 1);
292 147 : else if (TYPE_UNSIGNED (type)
293 147 : && (!TYPE_UNSIGNED (itype)
294 0 : || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
295 142 : res = wrap (res, TYPE_PRECISION (type));
296 : return res;
297 : }
298 :
299 0 : case NON_LVALUE_EXPR:
300 0 : res = extract_affine (s, TREE_OPERAND (e, 0), space);
301 0 : break;
302 :
303 0 : default:
304 0 : gcc_unreachable ();
305 1380 : break;
306 : }
307 :
308 : /* For all wrapping arithmetic wrap the result. */
309 1380 : if (TYPE_OVERFLOW_WRAPS (type))
310 165 : 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 190 : create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t)
319 : {
320 190 : scop_p scop = PBB_SCOP (pbb);
321 :
322 190 : t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t);
323 :
324 190 : gcc_assert (!chrec_contains_undetermined (t));
325 190 : gcc_assert (!automatically_generated_chrec_p (t));
326 :
327 190 : 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 95 : add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
336 : {
337 95 : loop_p loop = gimple_bb (stmt)->loop_father;
338 95 : isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt));
339 95 : isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt));
340 :
341 95 : isl_set *cond;
342 95 : switch (code)
343 : {
344 0 : case LT_EXPR:
345 0 : cond = isl_pw_aff_lt_set (lhs, rhs);
346 0 : break;
347 :
348 26 : case GT_EXPR:
349 26 : cond = isl_pw_aff_gt_set (lhs, rhs);
350 26 : break;
351 :
352 28 : case LE_EXPR:
353 28 : cond = isl_pw_aff_le_set (lhs, rhs);
354 28 : break;
355 :
356 1 : case GE_EXPR:
357 1 : cond = isl_pw_aff_ge_set (lhs, rhs);
358 1 : break;
359 :
360 20 : case EQ_EXPR:
361 20 : cond = isl_pw_aff_eq_set (lhs, rhs);
362 20 : break;
363 :
364 20 : case NE_EXPR:
365 20 : cond = isl_pw_aff_ne_set (lhs, rhs);
366 20 : break;
367 :
368 0 : default:
369 0 : gcc_unreachable ();
370 : }
371 :
372 95 : cond = isl_set_coalesce (cond);
373 95 : cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
374 95 : pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond));
375 95 : }
376 :
377 : /* Add conditions to the domain of PBB. */
378 :
379 : static void
380 668 : add_conditions_to_domain (poly_bb_p pbb)
381 : {
382 668 : unsigned int i;
383 668 : gimple *stmt;
384 668 : gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
385 :
386 668 : if (GBB_CONDITIONS (gbb).is_empty ())
387 668 : return;
388 :
389 185 : FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
390 95 : switch (gimple_code (stmt))
391 : {
392 95 : case GIMPLE_COND:
393 95 : {
394 : /* Don't constrain on anything else than INTEGRAL_TYPE_P. */
395 95 : tree cmp_type = TREE_TYPE (gimple_cond_lhs (stmt));
396 95 : if (!INTEGRAL_TYPE_P (cmp_type))
397 : break;
398 :
399 95 : gcond *cond_stmt = as_a <gcond *> (stmt);
400 95 : enum tree_code code = gimple_cond_code (cond_stmt);
401 :
402 : /* The conditions for ELSE-branches are inverted. */
403 95 : if (!GBB_CONDITION_CASES (gbb)[i])
404 46 : code = invert_tree_comparison (code, false);
405 :
406 95 : add_condition_to_pbb (pbb, cond_stmt, code);
407 95 : break;
408 : }
409 :
410 0 : default:
411 0 : gcc_unreachable ();
412 95 : 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 133 : add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter)
421 : {
422 133 : tree type = TREE_TYPE (parameter);
423 133 : int_range_max r;
424 133 : wide_int min, max;
425 :
426 133 : gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
427 :
428 133 : if (INTEGRAL_TYPE_P (type)
429 264 : && get_range_query (cfun)->range_of_expr (r, parameter)
430 265 : && !r.undefined_p ())
431 : {
432 124 : min = r.lower_bound ();
433 124 : max = r.upper_bound ();
434 : }
435 : else
436 : {
437 9 : min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
438 9 : max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
439 : }
440 :
441 133 : isl_space *space = isl_set_get_space (scop->param_context);
442 133 : isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space));
443 133 : isl_val *v = isl_val_int_from_wi (scop->isl_context,
444 133 : widest_int::from (min, TYPE_SIGN (type)));
445 133 : v = isl_val_neg (v);
446 133 : c = isl_constraint_set_constant_val (c, v);
447 133 : c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
448 266 : scop->param_context = isl_set_coalesce
449 133 : (isl_set_add_constraint (scop->param_context, c));
450 :
451 133 : space = isl_set_get_space (scop->param_context);
452 133 : c = isl_inequality_alloc (isl_local_space_from_space (space));
453 133 : v = isl_val_int_from_wi (scop->isl_context,
454 133 : widest_int::from (max, TYPE_SIGN (type)));
455 133 : c = isl_constraint_set_constant_val (c, v);
456 133 : c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
457 133 : scop->param_context = isl_set_coalesce
458 133 : (isl_set_add_constraint (scop->param_context, c));
459 133 : }
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 732 : pdr_add_alias_set (isl_map *acc, dr_info &dri)
468 : {
469 732 : isl_constraint *c = isl_equality_alloc
470 732 : (isl_local_space_from_space (isl_map_get_space (acc)));
471 : /* Positive numbers for all alias sets. */
472 732 : c = isl_constraint_set_constant_si (c, -dri.alias_set);
473 732 : c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
474 :
475 732 : 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 999 : set_index (isl_map *map, int pos, isl_pw_aff *index)
483 : {
484 999 : isl_map *index_map;
485 999 : int len = isl_map_dim (map, isl_dim_out);
486 999 : isl_id *id;
487 :
488 999 : index_map = isl_map_from_pw_aff (index);
489 999 : index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos);
490 999 : index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1);
491 :
492 999 : id = isl_map_get_tuple_id (map, isl_dim_out);
493 999 : index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id);
494 999 : id = isl_map_get_tuple_id (map, isl_dim_in);
495 999 : index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id);
496 :
497 999 : 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 732 : pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
507 : {
508 732 : data_reference_p dr = dri.dr;
509 732 : poly_bb_p pbb = dri.pbb;
510 732 : int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
511 732 : scop_p scop = PBB_SCOP (pbb);
512 :
513 1731 : for (i = 0; i < nb_subscripts; i++)
514 : {
515 999 : isl_pw_aff *aff;
516 999 : tree afn = DR_ACCESS_FN (dr, i);
517 :
518 999 : aff = extract_affine (scop, afn,
519 : isl_space_domain (isl_map_get_space (acc)));
520 999 : acc = set_index (acc, nb_subscripts - i , aff);
521 : }
522 :
523 732 : 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 902 : bounds_are_valid (tree ref, tree low, tree high)
532 : {
533 902 : if (!high)
534 : return false;
535 :
536 856 : if (!tree_fits_shwi_p (low)
537 856 : || !tree_fits_shwi_p (high))
538 : return false;
539 :
540 : /* An array that has flexible size may extend over
541 : their declared size. */
542 816 : if (array_ref_flexible_size_p (ref)
543 816 : && 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 816 : 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 732 : pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
560 : data_reference_p dr)
561 : {
562 732 : tree ref = DR_REF (dr);
563 :
564 732 : int nb_subscripts = DR_NUM_DIMENSIONS (dr);
565 1634 : for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
566 : {
567 990 : if (TREE_CODE (ref) != ARRAY_REF)
568 : return subscript_sizes;
569 :
570 902 : tree low = array_ref_low_bound (ref);
571 902 : tree high = array_ref_up_bound (ref);
572 :
573 902 : if (!bounds_are_valid (ref, low, high))
574 86 : continue;
575 :
576 816 : isl_space *space = isl_set_get_space (subscript_sizes);
577 816 : isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space));
578 816 : isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space));
579 :
580 : /* high >= 0 */
581 816 : isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
582 816 : valid = isl_set_project_out (valid, isl_dim_set, 0,
583 816 : isl_set_dim (valid, isl_dim_set));
584 1632 : scop->param_context = isl_set_coalesce
585 816 : (isl_set_intersect (scop->param_context, valid));
586 :
587 816 : isl_aff *aff
588 816 : = isl_aff_zero_on_domain (isl_local_space_from_space (space));
589 816 : aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
590 816 : isl_set *univ
591 816 : = isl_set_universe (isl_space_domain (isl_aff_get_space (aff)));
592 816 : isl_pw_aff *index = isl_pw_aff_alloc (univ, aff);
593 :
594 816 : isl_id *id = isl_set_get_tuple_id (subscript_sizes);
595 816 : lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
596 816 : ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
597 :
598 : /* low <= sub_i <= high */
599 816 : isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
600 816 : isl_set *ubs = isl_pw_aff_le_set (index, ub);
601 816 : subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
602 816 : subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
603 : }
604 :
605 644 : return isl_set_coalesce (subscript_sizes);
606 : }
607 :
608 : /* Build data accesses for DRI. */
609 :
610 : static void
611 732 : build_poly_dr (dr_info &dri)
612 : {
613 732 : isl_map *acc;
614 732 : isl_set *subscript_sizes;
615 732 : poly_bb_p pbb = dri.pbb;
616 732 : data_reference_p dr = dri.dr;
617 732 : scop_p scop = PBB_SCOP (pbb);
618 732 : isl_id *id = isl_id_for_dr (scop);
619 :
620 732 : {
621 732 : isl_space *dc = isl_set_get_space (pbb->domain);
622 732 : int nb_out = 1 + DR_NUM_DIMENSIONS (dr);
623 732 : isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
624 : isl_dim_out, nb_out);
625 :
626 732 : acc = isl_map_universe (space);
627 732 : acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
628 : }
629 :
630 732 : acc = pdr_add_alias_set (acc, dri);
631 732 : acc = pdr_add_memory_accesses (acc, dri);
632 :
633 732 : {
634 732 : int nb = 1 + DR_NUM_DIMENSIONS (dr);
635 732 : isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
636 :
637 732 : space = isl_space_set_tuple_id (space, isl_dim_set, id);
638 732 : subscript_sizes = isl_set_nat_universe (space);
639 732 : subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
640 : dri.alias_set);
641 732 : subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
642 : }
643 :
644 1105 : new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
645 : acc, subscript_sizes);
646 732 : }
647 :
648 : static void
649 1453 : 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 1453 : 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 1453 : int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var);
656 1453 : 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 1453 : isl_constraint *c
662 1453 : = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc)));
663 1453 : c = isl_constraint_set_constant_si (c, -alias_set);
664 1453 : c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
665 :
666 1453 : new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c),
667 : subscript_sizes);
668 1453 : }
669 :
670 : /* Record all cross basic block scalar variables in PBB. */
671 :
672 : static void
673 668 : build_poly_sr (poly_bb_p pbb)
674 : {
675 668 : scop_p scop = PBB_SCOP (pbb);
676 668 : gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
677 668 : vec<scalar_use> &reads = gbb->read_scalar_refs;
678 668 : vec<tree> &writes = gbb->write_scalar_refs;
679 :
680 668 : isl_space *dc = isl_set_get_space (pbb->domain);
681 668 : int nb_out = 1;
682 668 : isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
683 : isl_dim_out, nb_out);
684 668 : isl_id *id = isl_id_for_dr (scop);
685 668 : space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id));
686 668 : isl_map *acc = isl_map_universe (isl_space_copy (space));
687 668 : acc = isl_map_set_tuple_id (acc, isl_dim_out, id);
688 668 : isl_set *subscript_sizes = isl_set_nat_universe (space);
689 :
690 668 : int i;
691 668 : tree var;
692 2147 : FOR_EACH_VEC_ELT (writes, i, var)
693 811 : 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 1310 : FOR_EACH_VEC_ELT (reads, i, use)
698 642 : build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc),
699 : isl_set_copy (subscript_sizes));
700 :
701 668 : isl_map_free (acc);
702 668 : isl_set_free (subscript_sizes);
703 668 : }
704 :
705 : /* Build data references in SCOP. */
706 :
707 : static void
708 201 : build_scop_drs (scop_p scop)
709 : {
710 201 : int i;
711 201 : dr_info *dri;
712 933 : FOR_EACH_VEC_ELT (scop->drs, i, dri)
713 732 : build_poly_dr (*dri);
714 :
715 : poly_bb_p pbb;
716 869 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
717 668 : build_poly_sr (pbb);
718 201 : }
719 :
720 : /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
721 :
722 : static isl_set *
723 576 : add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
724 : {
725 576 : int loop_index = isl_set_dim (domain, isl_dim_set);
726 576 : domain = isl_set_add_dims (domain, isl_dim_set, 1);
727 576 : char name[50];
728 576 : snprintf (name, sizeof(name), "i%d", loop->num);
729 576 : isl_id *label = isl_id_alloc (scop->isl_context, name, NULL);
730 576 : 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 1050 : add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
737 : loop_p context)
738 : {
739 1050 : if (loop == context)
740 : return domain;
741 917 : const sese_l ®ion = scop->scop_info->region;
742 917 : if (!loop_in_sese_p (loop, region))
743 : return domain;
744 :
745 : /* Recursion all the way up to the context loop. */
746 576 : 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 576 : int loop_index = isl_set_dim (domain, isl_dim_set);
751 576 : if (dump_file)
752 298 : fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the "
753 : "domain for loop_%d.\n", loop->num);
754 576 : domain = add_iter_domain_dimension (domain, loop, scop);
755 576 : isl_space *space = isl_set_get_space (domain);
756 :
757 : /* 0 <= loop_i */
758 576 : isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
759 576 : isl_constraint *c = isl_inequality_alloc (ls);
760 576 : c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1);
761 576 : if (dump_file)
762 : {
763 298 : fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
764 298 : print_isl_constraint (dump_file, c);
765 : }
766 576 : domain = isl_set_add_constraint (domain, c);
767 :
768 576 : tree nb_iters = number_of_latch_executions (loop);
769 576 : if (TREE_CODE (nb_iters) == INTEGER_CST)
770 : {
771 : /* loop_i <= cst_nb_iters */
772 430 : isl_local_space *ls = isl_local_space_from_space (space);
773 430 : isl_constraint *c = isl_inequality_alloc (ls);
774 430 : c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
775 430 : isl_val *v
776 430 : = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters));
777 430 : c = isl_constraint_set_constant_val (c, v);
778 430 : return isl_set_add_constraint (domain, c);
779 : }
780 : /* loop_i <= expr_nb_iters */
781 146 : gcc_assert (!chrec_contains_undetermined (nb_iters));
782 146 : nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters);
783 146 : gcc_assert (!chrec_contains_undetermined (nb_iters));
784 :
785 146 : isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters,
786 : isl_space_copy (space));
787 146 : isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters));
788 146 : valid = isl_set_project_out (valid, isl_dim_set, 0,
789 146 : isl_set_dim (valid, isl_dim_set));
790 :
791 146 : if (valid)
792 146 : scop->param_context = isl_set_intersect (scop->param_context, valid);
793 :
794 146 : ls = isl_local_space_from_space (isl_space_copy (space));
795 146 : isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls),
796 : isl_dim_in, loop_index, 1);
797 146 : isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i),
798 : isl_pw_aff_copy (aff_nb_iters));
799 146 : if (dump_file)
800 : {
801 49 : fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
802 49 : print_isl_set (dump_file, le);
803 : }
804 146 : domain = isl_set_intersect (domain, le);
805 :
806 146 : widest_int nit;
807 146 : if (!max_stmt_executions (loop, &nit))
808 : {
809 0 : isl_pw_aff_free (aff_nb_iters);
810 0 : isl_space_free (space);
811 0 : 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 146 : --nit;
817 :
818 146 : isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space));
819 146 : isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters);
820 146 : x = isl_set_project_out (x, isl_dim_set, 0,
821 146 : isl_set_dim (x, isl_dim_set));
822 146 : scop->param_context = isl_set_intersect (scop->param_context, x);
823 :
824 146 : ls = isl_local_space_from_space (space);
825 146 : c = isl_inequality_alloc (ls);
826 146 : c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
827 146 : isl_val *v = isl_val_int_from_wi (scop->isl_context, nit);
828 146 : c = isl_constraint_set_constant_val (c, v);
829 :
830 146 : if (dump_file)
831 : {
832 49 : fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
833 49 : print_isl_constraint (dump_file, c);
834 : }
835 :
836 146 : return isl_set_add_constraint (domain, c);
837 146 : }
838 :
839 : /* Builds the original iteration domains for each pbb in the SCOP. */
840 :
841 : static int
842 474 : build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
843 : int index, loop_p context_loop)
844 : {
845 474 : loop_p current = pbb_loop (scop->pbbs[index]);
846 474 : isl_set *domain = isl_set_copy (context);
847 474 : domain = add_loop_constraints (scop, domain, current, context_loop);
848 474 : const sese_l ®ion = scop->scop_info->region;
849 :
850 474 : int i;
851 474 : poly_bb_p pbb;
852 1275 : FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index)
853 : {
854 1041 : loop_p loop = pbb_loop (pbb);
855 1041 : if (current == loop)
856 : {
857 668 : pbb->iterators = isl_set_copy (domain);
858 668 : pbb->domain = isl_set_copy (domain);
859 668 : pbb->domain = isl_set_set_tuple_id (pbb->domain,
860 : isl_id_for_pbb (scop, pbb));
861 668 : add_conditions_to_domain (pbb);
862 :
863 668 : if (dump_file)
864 : {
865 343 : fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
866 : pbb_index (pbb));
867 343 : print_isl_set (dump_file, domain);
868 : }
869 668 : continue;
870 : }
871 :
872 734 : while (loop_in_sese_p (loop, region)
873 734 : && current != loop)
874 361 : loop = loop_outer (loop);
875 :
876 373 : if (current != loop)
877 : {
878 : /* A statement in a different loop nest than CURRENT loop. */
879 240 : isl_set_free (domain);
880 240 : return i;
881 : }
882 :
883 : /* A statement nested in the CURRENT loop. */
884 133 : i = build_iteration_domains (scop, domain, i, current);
885 133 : i--;
886 : }
887 :
888 234 : isl_set_free (domain);
889 234 : return i;
890 : }
891 :
892 : /* Assign dimension for each parameter in SCOP and add constraints for the
893 : parameters. */
894 :
895 : static void
896 201 : build_scop_context (scop_p scop)
897 : {
898 201 : sese_info_p region = scop->scop_info;
899 201 : unsigned nbp = sese_nb_params (region);
900 201 : isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
901 :
902 201 : unsigned i;
903 201 : tree p;
904 535 : FOR_EACH_VEC_ELT (region->params, i, p)
905 133 : space = isl_space_set_dim_id (space, isl_dim_param, i,
906 : isl_id_for_parameter (scop, p));
907 :
908 201 : scop->param_context = isl_set_universe (space);
909 :
910 334 : FOR_EACH_VEC_ELT (region->params, i, p)
911 133 : add_param_constraints (scop, i, p);
912 201 : }
913 :
914 : /* Return true when loop A is nested in loop B. */
915 :
916 : static bool
917 1142 : nested_in (loop_p a, loop_p b)
918 : {
919 252 : return b == find_common_loop (a, b);
920 : }
921 :
922 : /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
923 : static loop_p
924 2363 : loop_at (scop_p scop, int *index)
925 : {
926 2363 : 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 119 : index_outermost_in_loop (loop_p a, scop_p scop)
933 : {
934 119 : int i, outermost = -1;
935 119 : int last_depth = -1;
936 119 : poly_bb_p pbb;
937 371 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
938 252 : if (nested_in (pbb_loop (pbb), a)
939 252 : && (last_depth == -1
940 88 : || last_depth > (int) loop_depth (pbb_loop (pbb))))
941 : {
942 120 : outermost = i;
943 240 : last_depth = loop_depth (pbb_loop (pbb));
944 : }
945 119 : return outermost;
946 : }
947 :
948 : /* Return the index of any pbb belonging to loop or a subloop of A. */
949 :
950 : static int
951 533 : index_pbb_in_loop (loop_p a, scop_p scop)
952 : {
953 533 : int i;
954 533 : poly_bb_p pbb;
955 1212 : FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
956 1093 : if (pbb_loop (pbb) == a)
957 : return i;
958 : return -1;
959 : }
960 :
961 : static poly_bb_p
962 533 : outermost_pbb_in (loop_p loop, scop_p scop)
963 : {
964 533 : int x = index_pbb_in_loop (loop, scop);
965 533 : if (x == -1)
966 119 : x = index_outermost_in_loop (loop, scop);
967 533 : return scop->pbbs[x];
968 : }
969 :
970 : static isl_schedule *
971 1056 : add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
972 : {
973 1056 : gcc_assert (a || b);
974 :
975 1056 : if (!a)
976 : return b;
977 :
978 467 : if (!b)
979 : return a;
980 :
981 467 : 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 919 : add_outer_projection (__isl_take isl_set *set, void *user)
994 : {
995 919 : struct map_to_dimension_data *data = (struct map_to_dimension_data *) user;
996 919 : int dim = isl_set_dim (set, isl_dim_set);
997 919 : isl_space *space = isl_set_get_space (set);
998 :
999 919 : gcc_assert (dim >= data->n);
1000 919 : isl_pw_multi_aff *pma
1001 1838 : = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n,
1002 919 : dim - data->n);
1003 919 : data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma);
1004 :
1005 919 : isl_set_free (set);
1006 919 : 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 532 : outer_projection_mupa (__isl_take isl_union_set *set, int n)
1013 : {
1014 532 : gcc_assert (n >= 0);
1015 532 : gcc_assert (set);
1016 532 : gcc_assert (!isl_union_set_is_empty (set));
1017 :
1018 532 : isl_space *space = isl_union_set_get_space (set);
1019 532 : isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
1020 :
1021 532 : struct map_to_dimension_data data = {n, pwaff};
1022 :
1023 532 : if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
1024 0 : data.res = isl_union_pw_multi_aff_free (data.res);
1025 :
1026 532 : isl_union_set_free (set);
1027 532 : 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 533 : add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
1034 : scop_p scop)
1035 : {
1036 533 : poly_bb_p pbb = outermost_pbb_in (loop, scop);
1037 533 : isl_set *iterators = pbb->iterators;
1038 :
1039 533 : int empty = isl_set_is_empty (iterators);
1040 533 : if (empty < 0 || empty)
1041 0 : return empty < 0 ? isl_schedule_free (schedule) : schedule;
1042 :
1043 533 : 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 533 : if (isl_union_set_is_empty (domain))
1046 : {
1047 1 : isl_union_set_free (domain);
1048 1 : return schedule;
1049 : }
1050 :
1051 532 : isl_space *space = isl_set_get_space (iterators);
1052 532 : int loop_index = isl_space_dim (space, isl_dim_set) - 1;
1053 :
1054 532 : loop_p ploop = pbb_loop (pbb);
1055 673 : while (loop != ploop)
1056 : {
1057 141 : --loop_index;
1058 141 : ploop = loop_outer (ploop);
1059 : }
1060 :
1061 532 : isl_local_space *ls = isl_local_space_from_space (space);
1062 532 : isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index);
1063 532 : isl_multi_aff *prefix = isl_multi_aff_from_aff (aff);
1064 532 : char name[50];
1065 532 : snprintf (name, sizeof(name), "L_%d", loop->num);
1066 532 : isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule),
1067 : name, NULL);
1068 532 : prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
1069 :
1070 532 : int n = isl_multi_aff_dim (prefix, isl_dim_in);
1071 532 : isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
1072 532 : mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
1073 532 : return isl_schedule_insert_partial_schedule (schedule, mupa);
1074 : }
1075 :
1076 : /* Build schedule for the pbb at INDEX. */
1077 :
1078 : static isl_schedule *
1079 668 : build_schedule_pbb (scop_p scop, int *index)
1080 : {
1081 668 : poly_bb_p pbb = scop->pbbs[*index];
1082 668 : ++*index;
1083 668 : isl_set *domain = isl_set_copy (pbb->domain);
1084 668 : isl_union_set *ud = isl_union_set_from_set (domain);
1085 668 : 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 388 : build_schedule_loop (scop_p scop, int *index)
1094 : {
1095 388 : int max = scop->pbbs.length ();
1096 388 : gcc_assert (*index < max);
1097 388 : loop_p loop = loop_at (scop, index);
1098 :
1099 388 : isl_schedule *s = NULL;
1100 1245 : while (nested_in (loop_at (scop, index), loop))
1101 : {
1102 626 : if (loop == loop_at (scop, index))
1103 535 : s = add_in_sequence (s, build_schedule_pbb (scop, index));
1104 : else
1105 91 : s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop));
1106 :
1107 626 : if (*index == max)
1108 : break;
1109 : }
1110 :
1111 388 : 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 368 : embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
1121 : loop_p loop, int *index, loop_p context_loop)
1122 : {
1123 513 : loop_p outer = loop_outer (loop);
1124 513 : sese_l region = scop->scop_info->region;
1125 513 : if (context_loop == outer
1126 513 : || !loop_in_sese_p (outer, region))
1127 368 : return s;
1128 :
1129 145 : int max = scop->pbbs.length ();
1130 145 : if (*index == max
1131 58 : || (context_loop && !nested_in (loop_at (scop, index), context_loop))
1132 145 : || (!context_loop
1133 58 : && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)),
1134 : region)))
1135 108 : return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop),
1136 108 : scop, outer, index, context_loop);
1137 :
1138 : bool a_pbb;
1139 132 : while ((a_pbb = (outer == loop_at (scop, index)))
1140 66 : || nested_in (loop_at (scop, index), outer))
1141 : {
1142 53 : if (a_pbb)
1143 33 : s = add_in_sequence (s, build_schedule_pbb (scop, index));
1144 : else
1145 20 : s = add_in_sequence (s, build_schedule_loop (scop, index));
1146 :
1147 53 : if (*index == max)
1148 : break;
1149 : }
1150 :
1151 : /* We reached the end of the OUTER loop: embed S in OUTER. */
1152 37 : return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop,
1153 37 : 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 368 : build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
1163 : {
1164 736 : gcc_assert (*index != (int) scop->pbbs.length ());
1165 :
1166 368 : loop_p loop = loop_at (scop, index);
1167 368 : isl_schedule *s = build_schedule_loop (scop, index);
1168 368 : 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 201 : build_original_schedule (scop_p scop)
1175 : {
1176 201 : int i = 0;
1177 201 : int n = scop->pbbs.length ();
1178 578 : while (i < n)
1179 : {
1180 377 : poly_bb_p pbb = scop->pbbs[i];
1181 377 : isl_schedule *s = NULL;
1182 377 : if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region))
1183 100 : s = build_schedule_pbb (scop, &i);
1184 : else
1185 277 : s = build_schedule_loop_nest (scop, &i, NULL);
1186 :
1187 377 : scop->original_schedule = add_in_sequence (scop->original_schedule, s);
1188 : }
1189 :
1190 201 : if (dump_file)
1191 : {
1192 101 : fprintf (dump_file, "[sese-to-poly] original schedule:\n");
1193 101 : print_isl_schedule (dump_file, scop->original_schedule);
1194 : }
1195 201 : }
1196 :
1197 : /* Builds the polyhedral representation for a SESE region. */
1198 :
1199 : bool
1200 201 : build_poly_scop (scop_p scop)
1201 : {
1202 201 : int old_err = isl_options_get_on_error (scop->isl_context);
1203 201 : isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
1204 :
1205 201 : build_scop_context (scop);
1206 :
1207 201 : unsigned i = 0;
1208 201 : unsigned n = scop->pbbs.length ();
1209 542 : while (i < n)
1210 341 : i = build_iteration_domains (scop, scop->param_context, i, NULL);
1211 :
1212 201 : build_scop_drs (scop);
1213 201 : build_original_schedule (scop);
1214 :
1215 201 : enum isl_error err = isl_ctx_last_error (scop->isl_context);
1216 201 : isl_ctx_reset_error (scop->isl_context);
1217 201 : isl_options_set_on_error (scop->isl_context, old_err);
1218 201 : if (err != isl_error_none
1219 201 : && dump_enabled_p ())
1220 0 : dump_printf (MSG_MISSED_OPTIMIZATION,
1221 : "ISL error while building poly scop\n");
1222 :
1223 201 : return err == isl_error_none;
1224 : }
1225 : #endif /* HAVE_isl */
|
