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