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

source code of gcc/graphite-sese-to-poly.cc