c++: Implement C++23 P2266R1, Simpler implicit move [PR101165]
[official-gcc.git] / gcc / graphite-sese-to-poly.cc
blob51ba3af204f2d3f7684a420552ad27bf9da2d736
1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2022 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
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.
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.
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/>. */
21 #define INCLUDE_ISL
23 #include "config.h"
25 #ifdef HAVE_isl
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"
51 /* Return an isl identifier for the polyhedral basic block PBB. */
53 static isl_id *
54 isl_id_for_pbb (scop_p s, poly_bb_p pbb)
56 char name[14];
57 snprintf (name, sizeof (name), "S_%d", pbb_index (pbb));
58 return isl_id_alloc (s->isl_context, name, pbb);
61 static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space);
63 /* Extract an affine expression from the chain of recurrence E. */
65 static isl_pw_aff *
66 extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space)
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);
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));
80 return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l));
83 /* Extract an affine expression from the mult_expr E. */
85 static isl_pw_aff *
86 extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space)
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);
92 if (!isl_pw_aff_is_cst (lhs)
93 && !isl_pw_aff_is_cst (rhs))
95 isl_pw_aff_free (lhs);
96 isl_pw_aff_free (rhs);
97 return NULL;
100 return isl_pw_aff_mul (lhs, rhs);
103 /* Return an isl identifier for the parameter P. */
105 static isl_id *
106 isl_id_for_parameter (scop_p s, tree p)
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);
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. */
119 static isl_id *
120 isl_id_for_dr (scop_p s)
122 return isl_id_alloc (s->isl_context, "", 0);
125 /* Extract an affine expression from the ssa_name E. */
127 static isl_pw_aff *
128 extract_affine_name (int dimension, __isl_take isl_space *space)
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);
136 /* Convert WI to a isl_val with CTX. */
138 static __isl_give isl_val *
139 isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi)
141 if (wi::neg_p (wi, SIGNED))
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 ()));
148 return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT),
149 wi.get_val ());
152 /* Extract an affine expression from the gmp constant G. */
154 static isl_pw_aff *
155 extract_affine_wi (const widest_int &g, __isl_take isl_space *space)
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);
164 return isl_pw_aff_alloc (dom, aff);
167 /* Extract an affine expression from the integer_cst E. */
169 static isl_pw_aff *
170 extract_affine_int (tree e, __isl_take isl_space *space)
172 isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space);
173 return res;
176 /* Compute pwaff mod 2^width. */
178 static isl_pw_aff *
179 wrap (isl_pw_aff *pwaff, unsigned width)
181 isl_val *mod;
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);
187 return pwaff;
190 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
191 Otherwise returns -1. */
193 static inline int
194 parameter_index_in_region (tree name, sese_info_p region)
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;
204 /* Extract an affine expression from the tree E in the scop S. */
206 static isl_pw_aff *
207 extract_affine (scop_p s, tree e, __isl_take isl_space *space)
209 isl_pw_aff *lhs, *rhs, *res;
211 if (e == chrec_dont_know) {
212 isl_space_free (space);
213 return NULL;
216 tree type = TREE_TYPE (e);
217 switch (TREE_CODE (e))
219 case POLYNOMIAL_CHREC:
220 res = extract_affine_chrec (s, e, space);
221 break;
223 case MULT_EXPR:
224 res = extract_affine_mul (s, e, space);
225 break;
227 case POINTER_PLUS_EXPR:
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;
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;
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;
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));
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;
267 case SSA_NAME:
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);
276 case INTEGER_CST:
277 res = extract_affine_int (e, space);
278 /* No need to wrap a single integer. */
279 return res;
281 CASE_CONVERT:
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;
299 case NON_LVALUE_EXPR:
300 res = extract_affine (s, TREE_OPERAND (e, 0), space);
301 break;
303 default:
304 gcc_unreachable ();
305 break;
308 /* For all wrapping arithmetic wrap the result. */
309 if (TYPE_OVERFLOW_WRAPS (type))
310 res = wrap (res, TYPE_PRECISION (type));
312 return res;
315 /* Returns a linear expression for tree T evaluated in PBB. */
317 static isl_pw_aff *
318 create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t)
320 scop_p scop = PBB_SCOP (pbb);
322 t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t);
324 gcc_assert (!chrec_contains_undetermined (t));
325 gcc_assert (!automatically_generated_chrec_p (t));
327 return extract_affine (scop, t, isl_set_get_space (pbb->domain));
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. */
334 static void
335 add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
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));
341 isl_set *cond;
342 switch (code)
344 case LT_EXPR:
345 cond = isl_pw_aff_lt_set (lhs, rhs);
346 break;
348 case GT_EXPR:
349 cond = isl_pw_aff_gt_set (lhs, rhs);
350 break;
352 case LE_EXPR:
353 cond = isl_pw_aff_le_set (lhs, rhs);
354 break;
356 case GE_EXPR:
357 cond = isl_pw_aff_ge_set (lhs, rhs);
358 break;
360 case EQ_EXPR:
361 cond = isl_pw_aff_eq_set (lhs, rhs);
362 break;
364 case NE_EXPR:
365 cond = isl_pw_aff_ne_set (lhs, rhs);
366 break;
368 default:
369 gcc_unreachable ();
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));
377 /* Add conditions to the domain of PBB. */
379 static void
380 add_conditions_to_domain (poly_bb_p pbb)
382 unsigned int i;
383 gimple *stmt;
384 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
386 if (GBB_CONDITIONS (gbb).is_empty ())
387 return;
389 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
390 switch (gimple_code (stmt))
392 case GIMPLE_COND:
394 /* Don't constrain on anything else than INTEGER_TYPE. */
395 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE)
396 break;
398 gcond *cond_stmt = as_a <gcond *> (stmt);
399 enum tree_code code = gimple_cond_code (cond_stmt);
401 /* The conditions for ELSE-branches are inverted. */
402 if (!GBB_CONDITION_CASES (gbb)[i])
403 code = invert_tree_comparison (code, false);
405 add_condition_to_pbb (pbb, cond_stmt, code);
406 break;
409 default:
410 gcc_unreachable ();
411 break;
415 /* Add constraints on the possible values of parameter P from the type
416 of P. */
418 static void
419 add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter)
421 tree type = TREE_TYPE (parameter);
422 value_range r;
423 wide_int min, max;
425 gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
427 if (INTEGRAL_TYPE_P (type)
428 && get_range_query (cfun)->range_of_expr (r, parameter)
429 && !r.undefined_p ())
431 min = r.lower_bound ();
432 max = r.upper_bound ();
434 else
436 min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
437 max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
440 isl_space *space = isl_set_get_space (scop->param_context);
441 isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space));
442 isl_val *v = isl_val_int_from_wi (scop->isl_context,
443 widest_int::from (min, TYPE_SIGN (type)));
444 v = isl_val_neg (v);
445 c = isl_constraint_set_constant_val (c, v);
446 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
447 scop->param_context = isl_set_coalesce
448 (isl_set_add_constraint (scop->param_context, c));
450 space = isl_set_get_space (scop->param_context);
451 c = isl_inequality_alloc (isl_local_space_from_space (space));
452 v = isl_val_int_from_wi (scop->isl_context,
453 widest_int::from (max, TYPE_SIGN (type)));
454 c = isl_constraint_set_constant_val (c, v);
455 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
456 scop->param_context = isl_set_coalesce
457 (isl_set_add_constraint (scop->param_context, c));
460 /* Add a constrain to the ACCESSES polyhedron for the alias set of
461 data reference DR. ACCESSP_NB_DIMS is the dimension of the
462 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
463 domain. */
465 static isl_map *
466 pdr_add_alias_set (isl_map *acc, dr_info &dri)
468 isl_constraint *c = isl_equality_alloc
469 (isl_local_space_from_space (isl_map_get_space (acc)));
470 /* Positive numbers for all alias sets. */
471 c = isl_constraint_set_constant_si (c, -dri.alias_set);
472 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
474 return isl_map_add_constraint (acc, c);
477 /* Assign the affine expression INDEX to the output dimension POS of
478 MAP and return the result. */
480 static isl_map *
481 set_index (isl_map *map, int pos, isl_pw_aff *index)
483 isl_map *index_map;
484 int len = isl_map_dim (map, isl_dim_out);
485 isl_id *id;
487 index_map = isl_map_from_pw_aff (index);
488 index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos);
489 index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1);
491 id = isl_map_get_tuple_id (map, isl_dim_out);
492 index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id);
493 id = isl_map_get_tuple_id (map, isl_dim_in);
494 index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id);
496 return isl_map_intersect (map, index_map);
499 /* Add to ACCESSES polyhedron equalities defining the access functions
500 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
501 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
502 PBB is the poly_bb_p that contains the data reference DR. */
504 static isl_map *
505 pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
507 data_reference_p dr = dri.dr;
508 poly_bb_p pbb = dri.pbb;
509 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
510 scop_p scop = PBB_SCOP (pbb);
512 for (i = 0; i < nb_subscripts; i++)
514 isl_pw_aff *aff;
515 tree afn = DR_ACCESS_FN (dr, i);
517 aff = extract_affine (scop, afn,
518 isl_space_domain (isl_map_get_space (acc)));
519 acc = set_index (acc, nb_subscripts - i , aff);
522 return isl_map_coalesce (acc);
525 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
526 to extract constraints on accessed elements of the array. Returning false is
527 the conservative answer. */
529 static bool
530 bounds_are_valid (tree ref, tree low, tree high)
532 if (!high)
533 return false;
535 if (!tree_fits_shwi_p (low)
536 || !tree_fits_shwi_p (high))
537 return false;
539 /* 1-element arrays at end of structures may extend over
540 their declared size. */
541 if (array_at_struct_end_p (ref)
542 && operand_equal_p (low, high, 0))
543 return false;
545 /* Fortran has some arrays where high bound is -1 and low is 0. */
546 if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low)))
547 return false;
549 return true;
552 /* Add constrains representing the size of the accessed data to the
553 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
554 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
555 domain. */
557 static isl_set *
558 pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
559 data_reference_p dr)
561 tree ref = DR_REF (dr);
563 int nb_subscripts = DR_NUM_DIMENSIONS (dr);
564 for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
566 if (TREE_CODE (ref) != ARRAY_REF)
567 return subscript_sizes;
569 tree low = array_ref_low_bound (ref);
570 tree high = array_ref_up_bound (ref);
572 if (!bounds_are_valid (ref, low, high))
573 continue;
575 isl_space *space = isl_set_get_space (subscript_sizes);
576 isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space));
577 isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space));
579 /* high >= 0 */
580 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
581 valid = isl_set_project_out (valid, isl_dim_set, 0,
582 isl_set_dim (valid, isl_dim_set));
583 scop->param_context = isl_set_coalesce
584 (isl_set_intersect (scop->param_context, valid));
586 isl_aff *aff
587 = isl_aff_zero_on_domain (isl_local_space_from_space (space));
588 aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
589 isl_set *univ
590 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff)));
591 isl_pw_aff *index = isl_pw_aff_alloc (univ, aff);
593 isl_id *id = isl_set_get_tuple_id (subscript_sizes);
594 lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
595 ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
597 /* low <= sub_i <= high */
598 isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
599 isl_set *ubs = isl_pw_aff_le_set (index, ub);
600 subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
601 subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
604 return isl_set_coalesce (subscript_sizes);
607 /* Build data accesses for DRI. */
609 static void
610 build_poly_dr (dr_info &dri)
612 isl_map *acc;
613 isl_set *subscript_sizes;
614 poly_bb_p pbb = dri.pbb;
615 data_reference_p dr = dri.dr;
616 scop_p scop = PBB_SCOP (pbb);
617 isl_id *id = isl_id_for_dr (scop);
620 isl_space *dc = isl_set_get_space (pbb->domain);
621 int nb_out = 1 + DR_NUM_DIMENSIONS (dr);
622 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
623 isl_dim_out, nb_out);
625 acc = isl_map_universe (space);
626 acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
629 acc = pdr_add_alias_set (acc, dri);
630 acc = pdr_add_memory_accesses (acc, dri);
633 int nb = 1 + DR_NUM_DIMENSIONS (dr);
634 isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
636 space = isl_space_set_tuple_id (space, isl_dim_set, id);
637 subscript_sizes = isl_set_nat_universe (space);
638 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
639 dri.alias_set);
640 subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
643 new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
644 acc, subscript_sizes);
647 static void
648 build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
649 isl_map *acc, isl_set *subscript_sizes)
651 scop_p scop = PBB_SCOP (pbb);
652 /* Each scalar variable has a unique alias set number starting from
653 the maximum alias set assigned to a dr. */
654 int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var);
655 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
656 alias_set);
658 /* Add a constrain to the ACCESSES polyhedron for the alias set of
659 the reference. */
660 isl_constraint *c
661 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc)));
662 c = isl_constraint_set_constant_si (c, -alias_set);
663 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
665 new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c),
666 subscript_sizes);
669 /* Record all cross basic block scalar variables in PBB. */
671 static void
672 build_poly_sr (poly_bb_p pbb)
674 scop_p scop = PBB_SCOP (pbb);
675 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
676 vec<scalar_use> &reads = gbb->read_scalar_refs;
677 vec<tree> &writes = gbb->write_scalar_refs;
679 isl_space *dc = isl_set_get_space (pbb->domain);
680 int nb_out = 1;
681 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
682 isl_dim_out, nb_out);
683 isl_id *id = isl_id_for_dr (scop);
684 space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id));
685 isl_map *acc = isl_map_universe (isl_space_copy (space));
686 acc = isl_map_set_tuple_id (acc, isl_dim_out, id);
687 isl_set *subscript_sizes = isl_set_nat_universe (space);
689 int i;
690 tree var;
691 FOR_EACH_VEC_ELT (writes, i, var)
692 build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE,
693 isl_map_copy (acc), isl_set_copy (subscript_sizes));
695 scalar_use *use;
696 FOR_EACH_VEC_ELT (reads, i, use)
697 build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc),
698 isl_set_copy (subscript_sizes));
700 isl_map_free (acc);
701 isl_set_free (subscript_sizes);
704 /* Build data references in SCOP. */
706 static void
707 build_scop_drs (scop_p scop)
709 int i;
710 dr_info *dri;
711 FOR_EACH_VEC_ELT (scop->drs, i, dri)
712 build_poly_dr (*dri);
714 poly_bb_p pbb;
715 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
716 build_poly_sr (pbb);
719 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
721 static isl_set *
722 add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
724 int loop_index = isl_set_dim (domain, isl_dim_set);
725 domain = isl_set_add_dims (domain, isl_dim_set, 1);
726 char name[50];
727 snprintf (name, sizeof(name), "i%d", loop->num);
728 isl_id *label = isl_id_alloc (scop->isl_context, name, NULL);
729 return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label);
732 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
734 static isl_set *
735 add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
736 loop_p context)
738 if (loop == context)
739 return domain;
740 const sese_l &region = scop->scop_info->region;
741 if (!loop_in_sese_p (loop, region))
742 return domain;
744 /* Recursion all the way up to the context loop. */
745 domain = add_loop_constraints (scop, domain, loop_outer (loop), context);
747 /* Then, build constraints over the loop in post-order: outer to inner. */
749 int loop_index = isl_set_dim (domain, isl_dim_set);
750 if (dump_file)
751 fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the "
752 "domain for loop_%d.\n", loop->num);
753 domain = add_iter_domain_dimension (domain, loop, scop);
754 isl_space *space = isl_set_get_space (domain);
756 /* 0 <= loop_i */
757 isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
758 isl_constraint *c = isl_inequality_alloc (ls);
759 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1);
760 if (dump_file)
762 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
763 print_isl_constraint (dump_file, c);
765 domain = isl_set_add_constraint (domain, c);
767 tree nb_iters = number_of_latch_executions (loop);
768 if (TREE_CODE (nb_iters) == INTEGER_CST)
770 /* loop_i <= cst_nb_iters */
771 isl_local_space *ls = isl_local_space_from_space (space);
772 isl_constraint *c = isl_inequality_alloc (ls);
773 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
774 isl_val *v
775 = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters));
776 c = isl_constraint_set_constant_val (c, v);
777 return isl_set_add_constraint (domain, c);
779 /* loop_i <= expr_nb_iters */
780 gcc_assert (!chrec_contains_undetermined (nb_iters));
781 nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters);
782 gcc_assert (!chrec_contains_undetermined (nb_iters));
784 isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters,
785 isl_space_copy (space));
786 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters));
787 valid = isl_set_project_out (valid, isl_dim_set, 0,
788 isl_set_dim (valid, isl_dim_set));
790 if (valid)
791 scop->param_context = isl_set_intersect (scop->param_context, valid);
793 ls = isl_local_space_from_space (isl_space_copy (space));
794 isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls),
795 isl_dim_in, loop_index, 1);
796 isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i),
797 isl_pw_aff_copy (aff_nb_iters));
798 if (dump_file)
800 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
801 print_isl_set (dump_file, le);
803 domain = isl_set_intersect (domain, le);
805 widest_int nit;
806 if (!max_stmt_executions (loop, &nit))
808 isl_pw_aff_free (aff_nb_iters);
809 isl_space_free (space);
810 return domain;
813 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
814 do not know whether the loop executes at least once. */
815 --nit;
817 isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space));
818 isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters);
819 x = isl_set_project_out (x, isl_dim_set, 0,
820 isl_set_dim (x, isl_dim_set));
821 scop->param_context = isl_set_intersect (scop->param_context, x);
823 ls = isl_local_space_from_space (space);
824 c = isl_inequality_alloc (ls);
825 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
826 isl_val *v = isl_val_int_from_wi (scop->isl_context, nit);
827 c = isl_constraint_set_constant_val (c, v);
829 if (dump_file)
831 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
832 print_isl_constraint (dump_file, c);
835 return isl_set_add_constraint (domain, c);
838 /* Builds the original iteration domains for each pbb in the SCOP. */
840 static int
841 build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
842 int index, loop_p context_loop)
844 loop_p current = pbb_loop (scop->pbbs[index]);
845 isl_set *domain = isl_set_copy (context);
846 domain = add_loop_constraints (scop, domain, current, context_loop);
847 const sese_l &region = scop->scop_info->region;
849 int i;
850 poly_bb_p pbb;
851 FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index)
853 loop_p loop = pbb_loop (pbb);
854 if (current == loop)
856 pbb->iterators = isl_set_copy (domain);
857 pbb->domain = isl_set_copy (domain);
858 pbb->domain = isl_set_set_tuple_id (pbb->domain,
859 isl_id_for_pbb (scop, pbb));
860 add_conditions_to_domain (pbb);
862 if (dump_file)
864 fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
865 pbb_index (pbb));
866 print_isl_set (dump_file, domain);
868 continue;
871 while (loop_in_sese_p (loop, region)
872 && current != loop)
873 loop = loop_outer (loop);
875 if (current != loop)
877 /* A statement in a different loop nest than CURRENT loop. */
878 isl_set_free (domain);
879 return i;
882 /* A statement nested in the CURRENT loop. */
883 i = build_iteration_domains (scop, domain, i, current);
884 i--;
887 isl_set_free (domain);
888 return i;
891 /* Assign dimension for each parameter in SCOP and add constraints for the
892 parameters. */
894 static void
895 build_scop_context (scop_p scop)
897 sese_info_p region = scop->scop_info;
898 unsigned nbp = sese_nb_params (region);
899 isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
901 unsigned i;
902 tree p;
903 FOR_EACH_VEC_ELT (region->params, i, p)
904 space = isl_space_set_dim_id (space, isl_dim_param, i,
905 isl_id_for_parameter (scop, p));
907 scop->param_context = isl_set_universe (space);
909 FOR_EACH_VEC_ELT (region->params, i, p)
910 add_param_constraints (scop, i, p);
913 /* Return true when loop A is nested in loop B. */
915 static bool
916 nested_in (loop_p a, loop_p b)
918 return b == find_common_loop (a, b);
921 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
922 static loop_p
923 loop_at (scop_p scop, int *index)
925 return pbb_loop (scop->pbbs[*index]);
928 /* Return the index of any pbb belonging to loop or a subloop of A. */
930 static int
931 index_outermost_in_loop (loop_p a, scop_p scop)
933 int i, outermost = -1;
934 int last_depth = -1;
935 poly_bb_p pbb;
936 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
937 if (nested_in (pbb_loop (pbb), a)
938 && (last_depth == -1
939 || last_depth > (int) loop_depth (pbb_loop (pbb))))
941 outermost = i;
942 last_depth = loop_depth (pbb_loop (pbb));
944 return outermost;
947 /* Return the index of any pbb belonging to loop or a subloop of A. */
949 static int
950 index_pbb_in_loop (loop_p a, scop_p scop)
952 int i;
953 poly_bb_p pbb;
954 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
955 if (pbb_loop (pbb) == a)
956 return i;
957 return -1;
960 static poly_bb_p
961 outermost_pbb_in (loop_p loop, scop_p scop)
963 int x = index_pbb_in_loop (loop, scop);
964 if (x == -1)
965 x = index_outermost_in_loop (loop, scop);
966 return scop->pbbs[x];
969 static isl_schedule *
970 add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
972 gcc_assert (a || b);
974 if (!a)
975 return b;
977 if (!b)
978 return a;
980 return isl_schedule_sequence (a, b);
983 struct map_to_dimension_data {
984 int n;
985 isl_union_pw_multi_aff *res;
988 /* Create a function that maps the elements of SET to its N-th dimension and add
989 it to USER->res. */
991 static isl_stat
992 add_outer_projection (__isl_take isl_set *set, void *user)
994 struct map_to_dimension_data *data = (struct map_to_dimension_data *) user;
995 int dim = isl_set_dim (set, isl_dim_set);
996 isl_space *space = isl_set_get_space (set);
998 gcc_assert (dim >= data->n);
999 isl_pw_multi_aff *pma
1000 = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n,
1001 dim - data->n);
1002 data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma);
1004 isl_set_free (set);
1005 return isl_stat_ok;
1008 /* Return SET in which all inner dimensions above N are removed. */
1010 static isl_multi_union_pw_aff *
1011 outer_projection_mupa (__isl_take isl_union_set *set, int n)
1013 gcc_assert (n >= 0);
1014 gcc_assert (set);
1015 gcc_assert (!isl_union_set_is_empty (set));
1017 isl_space *space = isl_union_set_get_space (set);
1018 isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
1020 struct map_to_dimension_data data = {n, pwaff};
1022 if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
1023 data.res = isl_union_pw_multi_aff_free (data.res);
1025 isl_union_set_free (set);
1026 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
1029 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1031 static isl_schedule *
1032 add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
1033 scop_p scop)
1035 poly_bb_p pbb = outermost_pbb_in (loop, scop);
1036 isl_set *iterators = pbb->iterators;
1038 int empty = isl_set_is_empty (iterators);
1039 if (empty < 0 || empty)
1040 return empty < 0 ? isl_schedule_free (schedule) : schedule;
1042 isl_union_set *domain = isl_schedule_get_domain (schedule);
1043 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1044 if (isl_union_set_is_empty (domain))
1046 isl_union_set_free (domain);
1047 return schedule;
1050 isl_space *space = isl_set_get_space (iterators);
1051 int loop_index = isl_space_dim (space, isl_dim_set) - 1;
1053 loop_p ploop = pbb_loop (pbb);
1054 while (loop != ploop)
1056 --loop_index;
1057 ploop = loop_outer (ploop);
1060 isl_local_space *ls = isl_local_space_from_space (space);
1061 isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index);
1062 isl_multi_aff *prefix = isl_multi_aff_from_aff (aff);
1063 char name[50];
1064 snprintf (name, sizeof(name), "L_%d", loop->num);
1065 isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule),
1066 name, NULL);
1067 prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
1069 int n = isl_multi_aff_dim (prefix, isl_dim_in);
1070 isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
1071 mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
1072 return isl_schedule_insert_partial_schedule (schedule, mupa);
1075 /* Build schedule for the pbb at INDEX. */
1077 static isl_schedule *
1078 build_schedule_pbb (scop_p scop, int *index)
1080 poly_bb_p pbb = scop->pbbs[*index];
1081 ++*index;
1082 isl_set *domain = isl_set_copy (pbb->domain);
1083 isl_union_set *ud = isl_union_set_from_set (domain);
1084 return isl_schedule_from_domain (ud);
1087 static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p);
1089 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1091 static isl_schedule *
1092 build_schedule_loop (scop_p scop, int *index)
1094 int max = scop->pbbs.length ();
1095 gcc_assert (*index < max);
1096 loop_p loop = loop_at (scop, index);
1098 isl_schedule *s = NULL;
1099 while (nested_in (loop_at (scop, index), loop))
1101 if (loop == loop_at (scop, index))
1102 s = add_in_sequence (s, build_schedule_pbb (scop, index));
1103 else
1104 s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop));
1106 if (*index == max)
1107 break;
1110 return add_loop_schedule (s, loop, scop);
1113 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1114 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1115 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1116 maximal loop nest contained within CONTEXT_LOOP. */
1118 static isl_schedule *
1119 embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
1120 loop_p loop, int *index, loop_p context_loop)
1122 loop_p outer = loop_outer (loop);
1123 sese_l region = scop->scop_info->region;
1124 if (context_loop == outer
1125 || !loop_in_sese_p (outer, region))
1126 return s;
1128 int max = scop->pbbs.length ();
1129 if (*index == max
1130 || (context_loop && !nested_in (loop_at (scop, index), context_loop))
1131 || (!context_loop
1132 && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)),
1133 region)))
1134 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop),
1135 scop, outer, index, context_loop);
1137 bool a_pbb;
1138 while ((a_pbb = (outer == loop_at (scop, index)))
1139 || nested_in (loop_at (scop, index), outer))
1141 if (a_pbb)
1142 s = add_in_sequence (s, build_schedule_pbb (scop, index));
1143 else
1144 s = add_in_sequence (s, build_schedule_loop (scop, index));
1146 if (*index == max)
1147 break;
1150 /* We reached the end of the OUTER loop: embed S in OUTER. */
1151 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop,
1152 outer, index, context_loop);
1155 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1156 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1157 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1158 nest contained within CONTEXT_LOOP. */
1160 static isl_schedule *
1161 build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
1163 gcc_assert (*index != (int) scop->pbbs.length ());
1165 loop_p loop = loop_at (scop, index);
1166 isl_schedule *s = build_schedule_loop (scop, index);
1167 return embed_in_surrounding_loops (s, scop, loop, index, context_loop);
1170 /* Build the schedule of the SCOP. */
1172 static void
1173 build_original_schedule (scop_p scop)
1175 int i = 0;
1176 int n = scop->pbbs.length ();
1177 while (i < n)
1179 poly_bb_p pbb = scop->pbbs[i];
1180 isl_schedule *s = NULL;
1181 if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region))
1182 s = build_schedule_pbb (scop, &i);
1183 else
1184 s = build_schedule_loop_nest (scop, &i, NULL);
1186 scop->original_schedule = add_in_sequence (scop->original_schedule, s);
1189 if (dump_file)
1191 fprintf (dump_file, "[sese-to-poly] original schedule:\n");
1192 print_isl_schedule (dump_file, scop->original_schedule);
1196 /* Builds the polyhedral representation for a SESE region. */
1198 bool
1199 build_poly_scop (scop_p scop)
1201 int old_err = isl_options_get_on_error (scop->isl_context);
1202 isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
1204 build_scop_context (scop);
1206 unsigned i = 0;
1207 unsigned n = scop->pbbs.length ();
1208 while (i < n)
1209 i = build_iteration_domains (scop, scop->param_context, i, NULL);
1211 build_scop_drs (scop);
1212 build_original_schedule (scop);
1214 enum isl_error err = isl_ctx_last_error (scop->isl_context);
1215 isl_ctx_reset_error (scop->isl_context);
1216 isl_options_set_on_error (scop->isl_context, old_err);
1217 if (err != isl_error_none
1218 && dump_enabled_p ())
1219 dump_printf (MSG_MISSED_OPTIMIZATION,
1220 "ISL error while building poly scop\n");
1222 return err == isl_error_none;
1224 #endif /* HAVE_isl */