Revise -mdisable-fpregs option and add new -msoft-mult option
[official-gcc.git] / gcc / graphite-sese-to-poly.c
blob99ea0327b1a782f8459cd1d0f448460e3008608f
1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2021 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 from the name of the ssa_name E. */
105 static isl_id *
106 isl_id_for_ssa_name (scop_p s, tree e)
108 char name1[14];
109 snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e));
110 return isl_id_alloc (s->isl_context, name1, e);
113 /* Return an isl identifier for the data reference DR. Data references and
114 scalar references get the same isl_id. They need to be comparable and are
115 distinguished through the first dimension, which contains the alias set or
116 SSA_NAME_VERSION number. */
118 static isl_id *
119 isl_id_for_dr (scop_p s)
121 return isl_id_alloc (s->isl_context, "", 0);
124 /* Extract an affine expression from the ssa_name E. */
126 static isl_pw_aff *
127 extract_affine_name (int dimension, __isl_take isl_space *space)
129 isl_set *dom = isl_set_universe (isl_space_copy (space));
130 isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space));
131 aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1);
132 return isl_pw_aff_alloc (dom, aff);
135 /* Convert WI to a isl_val with CTX. */
137 static __isl_give isl_val *
138 isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi)
140 if (wi::neg_p (wi, SIGNED))
142 widest_int mwi = -wi;
143 return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (),
144 sizeof (HOST_WIDE_INT),
145 mwi.get_val ()));
147 return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT),
148 wi.get_val ());
151 /* Extract an affine expression from the gmp constant G. */
153 static isl_pw_aff *
154 extract_affine_wi (const widest_int &g, __isl_take isl_space *space)
156 isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
157 isl_aff *aff = isl_aff_zero_on_domain (ls);
158 isl_set *dom = isl_set_universe (space);
159 isl_ctx *ct = isl_aff_get_ctx (aff);
160 isl_val *v = isl_val_int_from_wi (ct, g);
161 aff = isl_aff_add_constant_val (aff, v);
163 return isl_pw_aff_alloc (dom, aff);
166 /* Extract an affine expression from the integer_cst E. */
168 static isl_pw_aff *
169 extract_affine_int (tree e, __isl_take isl_space *space)
171 isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space);
172 return res;
175 /* Compute pwaff mod 2^width. */
177 static isl_pw_aff *
178 wrap (isl_pw_aff *pwaff, unsigned width)
180 isl_val *mod;
182 mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width);
183 mod = isl_val_2exp (mod);
184 pwaff = isl_pw_aff_mod_val (pwaff, mod);
186 return pwaff;
189 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
190 Otherwise returns -1. */
192 static inline int
193 parameter_index_in_region (tree name, sese_info_p region)
195 int i;
196 tree p;
197 FOR_EACH_VEC_ELT (region->params, i, p)
198 if (p == name)
199 return i;
200 return -1;
203 /* Extract an affine expression from the tree E in the scop S. */
205 static isl_pw_aff *
206 extract_affine (scop_p s, tree e, __isl_take isl_space *space)
208 isl_pw_aff *lhs, *rhs, *res;
210 if (e == chrec_dont_know) {
211 isl_space_free (space);
212 return NULL;
215 tree type = TREE_TYPE (e);
216 switch (TREE_CODE (e))
218 case POLYNOMIAL_CHREC:
219 res = extract_affine_chrec (s, e, space);
220 break;
222 case MULT_EXPR:
223 res = extract_affine_mul (s, e, space);
224 break;
226 case POINTER_PLUS_EXPR:
228 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
229 /* The RHS of a pointer-plus expression is to be interpreted
230 as signed value. Try to look through a sign-changing conversion
231 first. */
232 tree tem = TREE_OPERAND (e, 1);
233 STRIP_NOPS (tem);
234 rhs = extract_affine (s, tem, space);
235 if (TYPE_UNSIGNED (TREE_TYPE (tem)))
236 rhs = wrap (rhs, TYPE_PRECISION (type) - 1);
237 res = isl_pw_aff_add (lhs, rhs);
238 break;
241 case PLUS_EXPR:
242 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
243 rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
244 res = isl_pw_aff_add (lhs, rhs);
245 break;
247 case MINUS_EXPR:
248 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
249 rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
250 res = isl_pw_aff_sub (lhs, rhs);
251 break;
253 case BIT_NOT_EXPR:
254 lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space));
255 rhs = extract_affine (s, TREE_OPERAND (e, 0), space);
256 res = isl_pw_aff_sub (lhs, rhs);
257 /* We need to always wrap the result of a bitwise operation. */
258 return wrap (res, TYPE_PRECISION (type) - (TYPE_UNSIGNED (type) ? 0 : 1));
260 case NEGATE_EXPR:
261 lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
262 rhs = extract_affine (s, integer_minus_one_node, space);
263 res = isl_pw_aff_mul (lhs, rhs);
264 break;
266 case SSA_NAME:
268 gcc_assert (! defined_in_sese_p (e, s->scop_info->region));
269 int dim = parameter_index_in_region (e, s->scop_info);
270 gcc_assert (dim != -1);
271 /* No need to wrap a parameter. */
272 return extract_affine_name (dim, space);
275 case INTEGER_CST:
276 res = extract_affine_int (e, space);
277 /* No need to wrap a single integer. */
278 return res;
280 CASE_CONVERT:
282 tree itype = TREE_TYPE (TREE_OPERAND (e, 0));
283 res = extract_affine (s, TREE_OPERAND (e, 0), space);
284 /* Signed values, even if overflow is undefined, get modulo-reduced.
285 But only if not all values of the old type fit in the new. */
286 if (! TYPE_UNSIGNED (type)
287 && ((TYPE_UNSIGNED (itype)
288 && TYPE_PRECISION (type) <= TYPE_PRECISION (itype))
289 || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
290 res = wrap (res, TYPE_PRECISION (type) - 1);
291 else if (TYPE_UNSIGNED (type)
292 && (!TYPE_UNSIGNED (itype)
293 || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
294 res = wrap (res, TYPE_PRECISION (type));
295 return res;
298 case NON_LVALUE_EXPR:
299 res = extract_affine (s, TREE_OPERAND (e, 0), space);
300 break;
302 default:
303 gcc_unreachable ();
304 break;
307 /* For all wrapping arithmetic wrap the result. */
308 if (TYPE_OVERFLOW_WRAPS (type))
309 res = wrap (res, TYPE_PRECISION (type));
311 return res;
314 /* Returns a linear expression for tree T evaluated in PBB. */
316 static isl_pw_aff *
317 create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t)
319 scop_p scop = PBB_SCOP (pbb);
321 t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t);
323 gcc_assert (!chrec_contains_undetermined (t));
324 gcc_assert (!automatically_generated_chrec_p (t));
326 return extract_affine (scop, t, isl_set_get_space (pbb->domain));
329 /* Add conditional statement STMT to pbb. CODE is used as the comparison
330 operator. This allows us to invert the condition or to handle
331 inequalities. */
333 static void
334 add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
336 loop_p loop = gimple_bb (stmt)->loop_father;
337 isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt));
338 isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt));
340 isl_set *cond;
341 switch (code)
343 case LT_EXPR:
344 cond = isl_pw_aff_lt_set (lhs, rhs);
345 break;
347 case GT_EXPR:
348 cond = isl_pw_aff_gt_set (lhs, rhs);
349 break;
351 case LE_EXPR:
352 cond = isl_pw_aff_le_set (lhs, rhs);
353 break;
355 case GE_EXPR:
356 cond = isl_pw_aff_ge_set (lhs, rhs);
357 break;
359 case EQ_EXPR:
360 cond = isl_pw_aff_eq_set (lhs, rhs);
361 break;
363 case NE_EXPR:
364 cond = isl_pw_aff_ne_set (lhs, rhs);
365 break;
367 default:
368 gcc_unreachable ();
371 cond = isl_set_coalesce (cond);
372 cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
373 pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond));
376 /* Add conditions to the domain of PBB. */
378 static void
379 add_conditions_to_domain (poly_bb_p pbb)
381 unsigned int i;
382 gimple *stmt;
383 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
385 if (GBB_CONDITIONS (gbb).is_empty ())
386 return;
388 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
389 switch (gimple_code (stmt))
391 case GIMPLE_COND:
393 /* Don't constrain on anything else than INTEGER_TYPE. */
394 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE)
395 break;
397 gcond *cond_stmt = as_a <gcond *> (stmt);
398 enum tree_code code = gimple_cond_code (cond_stmt);
400 /* The conditions for ELSE-branches are inverted. */
401 if (!GBB_CONDITION_CASES (gbb)[i])
402 code = invert_tree_comparison (code, false);
404 add_condition_to_pbb (pbb, cond_stmt, code);
405 break;
408 default:
409 gcc_unreachable ();
410 break;
414 /* Add constraints on the possible values of parameter P from the type
415 of P. */
417 static void
418 add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter)
420 tree type = TREE_TYPE (parameter);
421 value_range r;
422 wide_int min, max;
424 gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
426 if (INTEGRAL_TYPE_P (type)
427 && get_range_query (cfun)->range_of_expr (r, parameter)
428 && !r.undefined_p ())
430 min = r.lower_bound ();
431 max = r.upper_bound ();
433 else
435 min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
436 max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
439 isl_space *space = isl_set_get_space (scop->param_context);
440 isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space));
441 isl_val *v = isl_val_int_from_wi (scop->isl_context,
442 widest_int::from (min, TYPE_SIGN (type)));
443 v = isl_val_neg (v);
444 c = isl_constraint_set_constant_val (c, v);
445 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
446 scop->param_context = isl_set_coalesce
447 (isl_set_add_constraint (scop->param_context, c));
449 space = isl_set_get_space (scop->param_context);
450 c = isl_inequality_alloc (isl_local_space_from_space (space));
451 v = isl_val_int_from_wi (scop->isl_context,
452 widest_int::from (max, TYPE_SIGN (type)));
453 c = isl_constraint_set_constant_val (c, v);
454 c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
455 scop->param_context = isl_set_coalesce
456 (isl_set_add_constraint (scop->param_context, c));
459 /* Add a constrain to the ACCESSES polyhedron for the alias set of
460 data reference DR. ACCESSP_NB_DIMS is the dimension of the
461 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
462 domain. */
464 static isl_map *
465 pdr_add_alias_set (isl_map *acc, dr_info &dri)
467 isl_constraint *c = isl_equality_alloc
468 (isl_local_space_from_space (isl_map_get_space (acc)));
469 /* Positive numbers for all alias sets. */
470 c = isl_constraint_set_constant_si (c, -dri.alias_set);
471 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
473 return isl_map_add_constraint (acc, c);
476 /* Assign the affine expression INDEX to the output dimension POS of
477 MAP and return the result. */
479 static isl_map *
480 set_index (isl_map *map, int pos, isl_pw_aff *index)
482 isl_map *index_map;
483 int len = isl_map_dim (map, isl_dim_out);
484 isl_id *id;
486 index_map = isl_map_from_pw_aff (index);
487 index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos);
488 index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1);
490 id = isl_map_get_tuple_id (map, isl_dim_out);
491 index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id);
492 id = isl_map_get_tuple_id (map, isl_dim_in);
493 index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id);
495 return isl_map_intersect (map, index_map);
498 /* Add to ACCESSES polyhedron equalities defining the access functions
499 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
500 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
501 PBB is the poly_bb_p that contains the data reference DR. */
503 static isl_map *
504 pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
506 data_reference_p dr = dri.dr;
507 poly_bb_p pbb = dri.pbb;
508 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
509 scop_p scop = PBB_SCOP (pbb);
511 for (i = 0; i < nb_subscripts; i++)
513 isl_pw_aff *aff;
514 tree afn = DR_ACCESS_FN (dr, i);
516 aff = extract_affine (scop, afn,
517 isl_space_domain (isl_map_get_space (acc)));
518 acc = set_index (acc, nb_subscripts - i , aff);
521 return isl_map_coalesce (acc);
524 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
525 to extract constraints on accessed elements of the array. Returning false is
526 the conservative answer. */
528 static bool
529 bounds_are_valid (tree ref, tree low, tree high)
531 if (!high)
532 return false;
534 if (!tree_fits_shwi_p (low)
535 || !tree_fits_shwi_p (high))
536 return false;
538 /* 1-element arrays at end of structures may extend over
539 their declared size. */
540 if (array_at_struct_end_p (ref)
541 && operand_equal_p (low, high, 0))
542 return false;
544 /* Fortran has some arrays where high bound is -1 and low is 0. */
545 if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low)))
546 return false;
548 return true;
551 /* Add constrains representing the size of the accessed data to the
552 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
553 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
554 domain. */
556 static isl_set *
557 pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
558 data_reference_p dr)
560 tree ref = DR_REF (dr);
562 int nb_subscripts = DR_NUM_DIMENSIONS (dr);
563 for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
565 if (TREE_CODE (ref) != ARRAY_REF)
566 return subscript_sizes;
568 tree low = array_ref_low_bound (ref);
569 tree high = array_ref_up_bound (ref);
571 if (!bounds_are_valid (ref, low, high))
572 continue;
574 isl_space *space = isl_set_get_space (subscript_sizes);
575 isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space));
576 isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space));
578 /* high >= 0 */
579 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
580 valid = isl_set_project_out (valid, isl_dim_set, 0,
581 isl_set_dim (valid, isl_dim_set));
582 scop->param_context = isl_set_coalesce
583 (isl_set_intersect (scop->param_context, valid));
585 isl_aff *aff
586 = isl_aff_zero_on_domain (isl_local_space_from_space (space));
587 aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
588 isl_set *univ
589 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff)));
590 isl_pw_aff *index = isl_pw_aff_alloc (univ, aff);
592 isl_id *id = isl_set_get_tuple_id (subscript_sizes);
593 lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
594 ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
596 /* low <= sub_i <= high */
597 isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
598 isl_set *ubs = isl_pw_aff_le_set (index, ub);
599 subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
600 subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
603 return isl_set_coalesce (subscript_sizes);
606 /* Build data accesses for DRI. */
608 static void
609 build_poly_dr (dr_info &dri)
611 isl_map *acc;
612 isl_set *subscript_sizes;
613 poly_bb_p pbb = dri.pbb;
614 data_reference_p dr = dri.dr;
615 scop_p scop = PBB_SCOP (pbb);
616 isl_id *id = isl_id_for_dr (scop);
619 isl_space *dc = isl_set_get_space (pbb->domain);
620 int nb_out = 1 + DR_NUM_DIMENSIONS (dr);
621 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
622 isl_dim_out, nb_out);
624 acc = isl_map_universe (space);
625 acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
628 acc = pdr_add_alias_set (acc, dri);
629 acc = pdr_add_memory_accesses (acc, dri);
632 int nb = 1 + DR_NUM_DIMENSIONS (dr);
633 isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
635 space = isl_space_set_tuple_id (space, isl_dim_set, id);
636 subscript_sizes = isl_set_nat_universe (space);
637 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
638 dri.alias_set);
639 subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
642 new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
643 acc, subscript_sizes);
646 static void
647 build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
648 isl_map *acc, isl_set *subscript_sizes)
650 scop_p scop = PBB_SCOP (pbb);
651 /* Each scalar variables has a unique alias set number starting from
652 the maximum alias set assigned to a dr. */
653 int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var);
654 subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
655 alias_set);
657 /* Add a constrain to the ACCESSES polyhedron for the alias set of
658 data reference DR. */
659 isl_constraint *c
660 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc)));
661 c = isl_constraint_set_constant_si (c, -alias_set);
662 c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
664 new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c),
665 subscript_sizes);
668 /* Record all cross basic block scalar variables in PBB. */
670 static void
671 build_poly_sr (poly_bb_p pbb)
673 scop_p scop = PBB_SCOP (pbb);
674 gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
675 vec<scalar_use> &reads = gbb->read_scalar_refs;
676 vec<tree> &writes = gbb->write_scalar_refs;
678 isl_space *dc = isl_set_get_space (pbb->domain);
679 int nb_out = 1;
680 isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
681 isl_dim_out, nb_out);
682 isl_id *id = isl_id_for_dr (scop);
683 space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id));
684 isl_map *acc = isl_map_universe (isl_space_copy (space));
685 acc = isl_map_set_tuple_id (acc, isl_dim_out, id);
686 isl_set *subscript_sizes = isl_set_nat_universe (space);
688 int i;
689 tree var;
690 FOR_EACH_VEC_ELT (writes, i, var)
691 build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE,
692 isl_map_copy (acc), isl_set_copy (subscript_sizes));
694 scalar_use *use;
695 FOR_EACH_VEC_ELT (reads, i, use)
696 build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc),
697 isl_set_copy (subscript_sizes));
699 isl_map_free (acc);
700 isl_set_free (subscript_sizes);
703 /* Build data references in SCOP. */
705 static void
706 build_scop_drs (scop_p scop)
708 int i;
709 dr_info *dri;
710 FOR_EACH_VEC_ELT (scop->drs, i, dri)
711 build_poly_dr (*dri);
713 poly_bb_p pbb;
714 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
715 build_poly_sr (pbb);
718 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
720 static isl_set *
721 add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
723 int loop_index = isl_set_dim (domain, isl_dim_set);
724 domain = isl_set_add_dims (domain, isl_dim_set, 1);
725 char name[50];
726 snprintf (name, sizeof(name), "i%d", loop->num);
727 isl_id *label = isl_id_alloc (scop->isl_context, name, NULL);
728 return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label);
731 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
733 static isl_set *
734 add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
735 loop_p context)
737 if (loop == context)
738 return domain;
739 const sese_l &region = scop->scop_info->region;
740 if (!loop_in_sese_p (loop, region))
741 return domain;
743 /* Recursion all the way up to the context loop. */
744 domain = add_loop_constraints (scop, domain, loop_outer (loop), context);
746 /* Then, build constraints over the loop in post-order: outer to inner. */
748 int loop_index = isl_set_dim (domain, isl_dim_set);
749 if (dump_file)
750 fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the "
751 "domain for loop_%d.\n", loop->num);
752 domain = add_iter_domain_dimension (domain, loop, scop);
753 isl_space *space = isl_set_get_space (domain);
755 /* 0 <= loop_i */
756 isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
757 isl_constraint *c = isl_inequality_alloc (ls);
758 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1);
759 if (dump_file)
761 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
762 print_isl_constraint (dump_file, c);
764 domain = isl_set_add_constraint (domain, c);
766 tree nb_iters = number_of_latch_executions (loop);
767 if (TREE_CODE (nb_iters) == INTEGER_CST)
769 /* loop_i <= cst_nb_iters */
770 isl_local_space *ls = isl_local_space_from_space (space);
771 isl_constraint *c = isl_inequality_alloc (ls);
772 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
773 isl_val *v
774 = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters));
775 c = isl_constraint_set_constant_val (c, v);
776 return isl_set_add_constraint (domain, c);
778 /* loop_i <= expr_nb_iters */
779 gcc_assert (!chrec_contains_undetermined (nb_iters));
780 nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters);
781 gcc_assert (!chrec_contains_undetermined (nb_iters));
783 isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters,
784 isl_space_copy (space));
785 isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters));
786 valid = isl_set_project_out (valid, isl_dim_set, 0,
787 isl_set_dim (valid, isl_dim_set));
789 if (valid)
790 scop->param_context = isl_set_intersect (scop->param_context, valid);
792 ls = isl_local_space_from_space (isl_space_copy (space));
793 isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls),
794 isl_dim_in, loop_index, 1);
795 isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i),
796 isl_pw_aff_copy (aff_nb_iters));
797 if (dump_file)
799 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
800 print_isl_set (dump_file, le);
802 domain = isl_set_intersect (domain, le);
804 widest_int nit;
805 if (!max_stmt_executions (loop, &nit))
807 isl_pw_aff_free (aff_nb_iters);
808 isl_space_free (space);
809 return domain;
812 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
813 do not know whether the loop executes at least once. */
814 --nit;
816 isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space));
817 isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters);
818 x = isl_set_project_out (x, isl_dim_set, 0,
819 isl_set_dim (x, isl_dim_set));
820 scop->param_context = isl_set_intersect (scop->param_context, x);
822 ls = isl_local_space_from_space (space);
823 c = isl_inequality_alloc (ls);
824 c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
825 isl_val *v = isl_val_int_from_wi (scop->isl_context, nit);
826 c = isl_constraint_set_constant_val (c, v);
828 if (dump_file)
830 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
831 print_isl_constraint (dump_file, c);
834 return isl_set_add_constraint (domain, c);
837 /* Builds the original iteration domains for each pbb in the SCOP. */
839 static int
840 build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
841 int index, loop_p context_loop)
843 loop_p current = pbb_loop (scop->pbbs[index]);
844 isl_set *domain = isl_set_copy (context);
845 domain = add_loop_constraints (scop, domain, current, context_loop);
846 const sese_l &region = scop->scop_info->region;
848 int i;
849 poly_bb_p pbb;
850 FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index)
852 loop_p loop = pbb_loop (pbb);
853 if (current == loop)
855 pbb->iterators = isl_set_copy (domain);
856 pbb->domain = isl_set_copy (domain);
857 pbb->domain = isl_set_set_tuple_id (pbb->domain,
858 isl_id_for_pbb (scop, pbb));
859 add_conditions_to_domain (pbb);
861 if (dump_file)
863 fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
864 pbb_index (pbb));
865 print_isl_set (dump_file, domain);
867 continue;
870 while (loop_in_sese_p (loop, region)
871 && current != loop)
872 loop = loop_outer (loop);
874 if (current != loop)
876 /* A statement in a different loop nest than CURRENT loop. */
877 isl_set_free (domain);
878 return i;
881 /* A statement nested in the CURRENT loop. */
882 i = build_iteration_domains (scop, domain, i, current);
883 i--;
886 isl_set_free (domain);
887 return i;
890 /* Assign dimension for each parameter in SCOP and add constraints for the
891 parameters. */
893 static void
894 build_scop_context (scop_p scop)
896 sese_info_p region = scop->scop_info;
897 unsigned nbp = sese_nb_params (region);
898 isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
900 unsigned i;
901 tree e;
902 FOR_EACH_VEC_ELT (region->params, i, e)
903 space = isl_space_set_dim_id (space, isl_dim_param, i,
904 isl_id_for_ssa_name (scop, e));
906 scop->param_context = isl_set_universe (space);
908 FOR_EACH_VEC_ELT (region->params, i, e)
909 add_param_constraints (scop, i, e);
912 /* Return true when loop A is nested in loop B. */
914 static bool
915 nested_in (loop_p a, loop_p b)
917 return b == find_common_loop (a, b);
920 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
921 static loop_p
922 loop_at (scop_p scop, int *index)
924 return pbb_loop (scop->pbbs[*index]);
927 /* Return the index of any pbb belonging to loop or a subloop of A. */
929 static int
930 index_outermost_in_loop (loop_p a, scop_p scop)
932 int i, outermost = -1;
933 int last_depth = -1;
934 poly_bb_p pbb;
935 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
936 if (nested_in (pbb_loop (pbb), a)
937 && (last_depth == -1
938 || last_depth > (int) loop_depth (pbb_loop (pbb))))
940 outermost = i;
941 last_depth = loop_depth (pbb_loop (pbb));
943 return outermost;
946 /* Return the index of any pbb belonging to loop or a subloop of A. */
948 static int
949 index_pbb_in_loop (loop_p a, scop_p scop)
951 int i;
952 poly_bb_p pbb;
953 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
954 if (pbb_loop (pbb) == a)
955 return i;
956 return -1;
959 static poly_bb_p
960 outermost_pbb_in (loop_p loop, scop_p scop)
962 int x = index_pbb_in_loop (loop, scop);
963 if (x == -1)
964 x = index_outermost_in_loop (loop, scop);
965 return scop->pbbs[x];
968 static isl_schedule *
969 add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
971 gcc_assert (a || b);
973 if (!a)
974 return b;
976 if (!b)
977 return a;
979 return isl_schedule_sequence (a, b);
982 struct map_to_dimension_data {
983 int n;
984 isl_union_pw_multi_aff *res;
987 /* Create a function that maps the elements of SET to its N-th dimension and add
988 it to USER->res. */
990 static isl_stat
991 add_outer_projection (__isl_take isl_set *set, void *user)
993 struct map_to_dimension_data *data = (struct map_to_dimension_data *) user;
994 int dim = isl_set_dim (set, isl_dim_set);
995 isl_space *space = isl_set_get_space (set);
997 gcc_assert (dim >= data->n);
998 isl_pw_multi_aff *pma
999 = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n,
1000 dim - data->n);
1001 data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma);
1003 isl_set_free (set);
1004 return isl_stat_ok;
1007 /* Return SET in which all inner dimensions above N are removed. */
1009 static isl_multi_union_pw_aff *
1010 outer_projection_mupa (__isl_take isl_union_set *set, int n)
1012 gcc_assert (n >= 0);
1013 gcc_assert (set);
1014 gcc_assert (!isl_union_set_is_empty (set));
1016 isl_space *space = isl_union_set_get_space (set);
1017 isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
1019 struct map_to_dimension_data data = {n, pwaff};
1021 if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
1022 data.res = isl_union_pw_multi_aff_free (data.res);
1024 isl_union_set_free (set);
1025 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
1028 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1030 static isl_schedule *
1031 add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
1032 scop_p scop)
1034 poly_bb_p pbb = outermost_pbb_in (loop, scop);
1035 isl_set *iterators = pbb->iterators;
1037 int empty = isl_set_is_empty (iterators);
1038 if (empty < 0 || empty)
1039 return empty < 0 ? isl_schedule_free (schedule) : schedule;
1041 isl_union_set *domain = isl_schedule_get_domain (schedule);
1042 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1043 if (isl_union_set_is_empty (domain))
1045 isl_union_set_free (domain);
1046 return schedule;
1049 isl_space *space = isl_set_get_space (iterators);
1050 int loop_index = isl_space_dim (space, isl_dim_set) - 1;
1052 loop_p ploop = pbb_loop (pbb);
1053 while (loop != ploop)
1055 --loop_index;
1056 ploop = loop_outer (ploop);
1059 isl_local_space *ls = isl_local_space_from_space (space);
1060 isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index);
1061 isl_multi_aff *prefix = isl_multi_aff_from_aff (aff);
1062 char name[50];
1063 snprintf (name, sizeof(name), "L_%d", loop->num);
1064 isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule),
1065 name, NULL);
1066 prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
1068 int n = isl_multi_aff_dim (prefix, isl_dim_in);
1069 isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
1070 mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
1071 return isl_schedule_insert_partial_schedule (schedule, mupa);
1074 /* Build schedule for the pbb at INDEX. */
1076 static isl_schedule *
1077 build_schedule_pbb (scop_p scop, int *index)
1079 poly_bb_p pbb = scop->pbbs[*index];
1080 ++*index;
1081 isl_set *domain = isl_set_copy (pbb->domain);
1082 isl_union_set *ud = isl_union_set_from_set (domain);
1083 return isl_schedule_from_domain (ud);
1086 static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p);
1088 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1090 static isl_schedule *
1091 build_schedule_loop (scop_p scop, int *index)
1093 int max = scop->pbbs.length ();
1094 gcc_assert (*index < max);
1095 loop_p loop = loop_at (scop, index);
1097 isl_schedule *s = NULL;
1098 while (nested_in (loop_at (scop, index), loop))
1100 if (loop == loop_at (scop, index))
1101 s = add_in_sequence (s, build_schedule_pbb (scop, index));
1102 else
1103 s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop));
1105 if (*index == max)
1106 break;
1109 return add_loop_schedule (s, loop, scop);
1112 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1113 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1114 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1115 maximal loop nest contained within CONTEXT_LOOP. */
1117 static isl_schedule *
1118 embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
1119 loop_p loop, int *index, loop_p context_loop)
1121 loop_p outer = loop_outer (loop);
1122 sese_l region = scop->scop_info->region;
1123 if (context_loop == outer
1124 || !loop_in_sese_p (outer, region))
1125 return s;
1127 int max = scop->pbbs.length ();
1128 if (*index == max
1129 || (context_loop && !nested_in (loop_at (scop, index), context_loop))
1130 || (!context_loop
1131 && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)),
1132 region)))
1133 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop),
1134 scop, outer, index, context_loop);
1136 bool a_pbb;
1137 while ((a_pbb = (outer == loop_at (scop, index)))
1138 || nested_in (loop_at (scop, index), outer))
1140 if (a_pbb)
1141 s = add_in_sequence (s, build_schedule_pbb (scop, index));
1142 else
1143 s = add_in_sequence (s, build_schedule_loop (scop, index));
1145 if (*index == max)
1146 break;
1149 /* We reached the end of the OUTER loop: embed S in OUTER. */
1150 return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop,
1151 outer, index, context_loop);
1154 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1155 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1156 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1157 nest contained within CONTEXT_LOOP. */
1159 static isl_schedule *
1160 build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
1162 gcc_assert (*index != (int) scop->pbbs.length ());
1164 loop_p loop = loop_at (scop, index);
1165 isl_schedule *s = build_schedule_loop (scop, index);
1166 return embed_in_surrounding_loops (s, scop, loop, index, context_loop);
1169 /* Build the schedule of the SCOP. */
1171 static void
1172 build_original_schedule (scop_p scop)
1174 int i = 0;
1175 int n = scop->pbbs.length ();
1176 while (i < n)
1178 poly_bb_p pbb = scop->pbbs[i];
1179 isl_schedule *s = NULL;
1180 if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region))
1181 s = build_schedule_pbb (scop, &i);
1182 else
1183 s = build_schedule_loop_nest (scop, &i, NULL);
1185 scop->original_schedule = add_in_sequence (scop->original_schedule, s);
1188 if (dump_file)
1190 fprintf (dump_file, "[sese-to-poly] original schedule:\n");
1191 print_isl_schedule (dump_file, scop->original_schedule);
1195 /* Builds the polyhedral representation for a SESE region. */
1197 bool
1198 build_poly_scop (scop_p scop)
1200 int old_err = isl_options_get_on_error (scop->isl_context);
1201 isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
1203 build_scop_context (scop);
1205 unsigned i = 0;
1206 unsigned n = scop->pbbs.length ();
1207 while (i < n)
1208 i = build_iteration_domains (scop, scop->param_context, i, NULL);
1210 build_scop_drs (scop);
1211 build_original_schedule (scop);
1213 enum isl_error err = isl_ctx_last_error (scop->isl_context);
1214 isl_ctx_reset_error (scop->isl_context);
1215 isl_options_set_on_error (scop->isl_context, old_err);
1216 if (err != isl_error_none
1217 && dump_enabled_p ())
1218 dump_printf (MSG_MISSED_OPTIMIZATION,
1219 "ISL error while building poly scop\n");
1221 return err == isl_error_none;
1223 #endif /* HAVE_isl */