1/* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2023 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 INTEGER_TYPE. */
395 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE)
396 break;
397
398 gcond *cond_stmt = as_a <gcond *> (stmt);
399 enum tree_code code = gimple_cond_code (cond_stmt);
400
401 /* The conditions for ELSE-branches are inverted. */
402 if (!GBB_CONDITION_CASES (gbb)[i])
403 code = invert_tree_comparison (code, false);
404
405 add_condition_to_pbb (pbb, cond_stmt, code);
406 break;
407 }
408
409 default:
410 gcc_unreachable ();
411 break;
412 }
413}
414
415/* Add constraints on the possible values of parameter P from the type
416 of P. */
417
418static void
419add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter)
420{
421 tree type = TREE_TYPE (parameter);
422 value_range r;
423 wide_int min, max;
424
425 gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
426
427 if (INTEGRAL_TYPE_P (type)
428 && get_range_query (cfun)->range_of_expr (r, parameter)
429 && !r.undefined_p ())
430 {
431 min = r.lower_bound ();
432 max = r.upper_bound ();
433 }
434 else
435 {
436 min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
437 max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
438 }
439
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));
449
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));
458}
459
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. */
464
465static isl_map *
466pdr_add_alias_set (isl_map *acc, dr_info &dri)
467{
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);
473
474 return isl_map_add_constraint (acc, c);
475}
476
477/* Assign the affine expression INDEX to the output dimension POS of
478 MAP and return the result. */
479
480static isl_map *
481set_index (isl_map *map, int pos, isl_pw_aff *index)
482{
483 isl_map *index_map;
484 int len = isl_map_dim (map, isl_dim_out);
485 isl_id *id;
486
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);
490
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);
495
496 return isl_map_intersect (map, index_map);
497}
498
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. */
503
504static isl_map *
505pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
506{
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);
511
512 for (i = 0; i < nb_subscripts; i++)
513 {
514 isl_pw_aff *aff;
515 tree afn = DR_ACCESS_FN (dr, i);
516
517 aff = extract_affine (scop, afn,
518 isl_space_domain (isl_map_get_space (acc)));
519 acc = set_index (acc, nb_subscripts - i , aff);
520 }
521
522 return isl_map_coalesce (acc);
523}
524
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. */
528
529static bool
530bounds_are_valid (tree ref, tree low, tree high)
531{
532 if (!high)
533 return false;
534
535 if (!tree_fits_shwi_p (low)
536 || !tree_fits_shwi_p (high))
537 return false;
538
539 /* An array that has flexible size may extend over
540 their declared size. */
541 if (array_ref_flexible_size_p (ref)
542 && operand_equal_p (low, high, 0))
543 return false;
544
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;
548
549 return true;
550}
551
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. */
556
557static isl_set *
558pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
559 data_reference_p dr)
560{
561 tree ref = DR_REF (dr);
562
563 int nb_subscripts = DR_NUM_DIMENSIONS (dr);
564 for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
565 {
566 if (TREE_CODE (ref) != ARRAY_REF)
567 return subscript_sizes;
568
569 tree low = array_ref_low_bound (ref);
570 tree high = array_ref_up_bound (ref);
571
572 if (!bounds_are_valid (ref, low, high))
573 continue;
574
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));
578
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));
585
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);
592
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);
596
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);
602 }
603
604 return isl_set_coalesce (subscript_sizes);
605}
606
607/* Build data accesses for DRI. */
608
609static void
610build_poly_dr (dr_info &dri)
611{
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);
618
619 {
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);
624
625 acc = isl_map_universe (space);
626 acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
627 }
628
629 acc = pdr_add_alias_set (acc, dri);
630 acc = pdr_add_memory_accesses (acc, dri);
631
632 {
633 int nb = 1 + DR_NUM_DIMENSIONS (dr);
634 isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
635
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);
641 }
642
643 new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
644 acc, subscript_sizes);
645}
646
647static void
648build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
649 isl_map *acc, isl_set *subscript_sizes)
650{
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);
657
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);
664
665 new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c),
666 subscript_sizes);
667}
668
669/* Record all cross basic block scalar variables in PBB. */
670
671static void
672build_poly_sr (poly_bb_p pbb)
673{
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;
678
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);
688
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));
694
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));
699
700 isl_map_free (acc);
701 isl_set_free (subscript_sizes);
702}
703
704/* Build data references in SCOP. */
705
706static void
707build_scop_drs (scop_p scop)
708{
709 int i;
710 dr_info *dri;
711 FOR_EACH_VEC_ELT (scop->drs, i, dri)
712 build_poly_dr (*dri);
713
714 poly_bb_p pbb;
715 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
716 build_poly_sr (pbb);
717}
718
719/* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
720
721static isl_set *
722add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
723{
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);
730}
731
732/* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
733
734static isl_set *
735add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
736 loop_p context)
737{
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;
743
744 /* Recursion all the way up to the context loop. */
745 domain = add_loop_constraints (scop, domain, loop_outer (loop), context);
746
747 /* Then, build constraints over the loop in post-order: outer to inner. */
748
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);
755
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)
761 {
762 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
763 print_isl_constraint (dump_file, c);
764 }
765 domain = isl_set_add_constraint (domain, c);
766
767 tree nb_iters = number_of_latch_executions (loop);
768 if (TREE_CODE (nb_iters) == INTEGER_CST)
769 {
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);
778 }
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));
783
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));
789
790 if (valid)
791 scop->param_context = isl_set_intersect (scop->param_context, valid);
792
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)
799 {
800 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
801 print_isl_set (dump_file, le);
802 }
803 domain = isl_set_intersect (domain, le);
804
805 widest_int nit;
806 if (!max_stmt_executions (loop, &nit))
807 {
808 isl_pw_aff_free (aff_nb_iters);
809 isl_space_free (space);
810 return domain;
811 }
812
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;
816
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);
822
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);
828
829 if (dump_file)
830 {
831 fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
832 print_isl_constraint (dump_file, c);
833 }
834
835 return isl_set_add_constraint (domain, c);
836}
837
838/* Builds the original iteration domains for each pbb in the SCOP. */
839
840static int
841build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
842 int index, loop_p context_loop)
843{
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;
848
849 int i;
850 poly_bb_p pbb;
851 FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index)
852 {
853 loop_p loop = pbb_loop (pbb);
854 if (current == loop)
855 {
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);
861
862 if (dump_file)
863 {
864 fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
865 pbb_index (pbb));
866 print_isl_set (dump_file, domain);
867 }
868 continue;
869 }
870
871 while (loop_in_sese_p (loop, region)
872 && current != loop)
873 loop = loop_outer (loop);
874
875 if (current != loop)
876 {
877 /* A statement in a different loop nest than CURRENT loop. */
878 isl_set_free (domain);
879 return i;
880 }
881
882 /* A statement nested in the CURRENT loop. */
883 i = build_iteration_domains (scop, domain, i, current);
884 i--;
885 }
886
887 isl_set_free (domain);
888 return i;
889}
890
891/* Assign dimension for each parameter in SCOP and add constraints for the
892 parameters. */
893
894static void
895build_scop_context (scop_p scop)
896{
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);
900
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));
906
907 scop->param_context = isl_set_universe (space);
908
909 FOR_EACH_VEC_ELT (region->params, i, p)
910 add_param_constraints (scop, i, p);
911}
912
913/* Return true when loop A is nested in loop B. */
914
915static bool
916nested_in (loop_p a, loop_p b)
917{
918 return b == find_common_loop (a, b);
919}
920
921/* Return the loop at a specific SCOP->pbbs[*INDEX]. */
922static loop_p
923loop_at (scop_p scop, int *index)
924{
925 return pbb_loop (scop->pbbs[*index]);
926}
927
928/* Return the index of any pbb belonging to loop or a subloop of A. */
929
930static int
931index_outermost_in_loop (loop_p a, scop_p scop)
932{
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))))
940 {
941 outermost = i;
942 last_depth = loop_depth (pbb_loop (pbb));
943 }
944 return outermost;
945}
946
947/* Return the index of any pbb belonging to loop or a subloop of A. */
948
949static int
950index_pbb_in_loop (loop_p a, scop_p scop)
951{
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;
958}
959
960static poly_bb_p
961outermost_pbb_in (loop_p loop, scop_p scop)
962{
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];
967}
968
969static isl_schedule *
970add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
971{
972 gcc_assert (a || b);
973
974 if (!a)
975 return b;
976
977 if (!b)
978 return a;
979
980 return isl_schedule_sequence (a, b);
981}
982
983struct map_to_dimension_data {
984 int n;
985 isl_union_pw_multi_aff *res;
986};
987
988/* Create a function that maps the elements of SET to its N-th dimension and add
989 it to USER->res. */
990
991static isl_stat
992add_outer_projection (__isl_take isl_set *set, void *user)
993{
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);
997
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);
1003
1004 isl_set_free (set);
1005 return isl_stat_ok;
1006}
1007
1008/* Return SET in which all inner dimensions above N are removed. */
1009
1010static isl_multi_union_pw_aff *
1011outer_projection_mupa (__isl_take isl_union_set *set, int n)
1012{
1013 gcc_assert (n >= 0);
1014 gcc_assert (set);
1015 gcc_assert (!isl_union_set_is_empty (set));
1016
1017 isl_space *space = isl_union_set_get_space (set);
1018 isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
1019
1020 struct map_to_dimension_data data = {n, pwaff};
1021
1022 if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
1023 data.res = isl_union_pw_multi_aff_free (data.res);
1024
1025 isl_union_set_free (set);
1026 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
1027}
1028
1029/* Embed SCHEDULE in the constraints of the LOOP domain. */
1030
1031static isl_schedule *
1032add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
1033 scop_p scop)
1034{
1035 poly_bb_p pbb = outermost_pbb_in (loop, scop);
1036 isl_set *iterators = pbb->iterators;
1037
1038 int empty = isl_set_is_empty (iterators);
1039 if (empty < 0 || empty)
1040 return empty < 0 ? isl_schedule_free (schedule) : schedule;
1041
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))
1045 {
1046 isl_union_set_free (domain);
1047 return schedule;
1048 }
1049
1050 isl_space *space = isl_set_get_space (iterators);
1051 int loop_index = isl_space_dim (space, isl_dim_set) - 1;
1052
1053 loop_p ploop = pbb_loop (pbb);
1054 while (loop != ploop)
1055 {
1056 --loop_index;
1057 ploop = loop_outer (ploop);
1058 }
1059
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);
1068
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);
1073}
1074
1075/* Build schedule for the pbb at INDEX. */
1076
1077static isl_schedule *
1078build_schedule_pbb (scop_p scop, int *index)
1079{
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);
1085}
1086
1087static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p);
1088
1089/* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1090
1091static isl_schedule *
1092build_schedule_loop (scop_p scop, int *index)
1093{
1094 int max = scop->pbbs.length ();
1095 gcc_assert (*index < max);
1096 loop_p loop = loop_at (scop, index);
1097
1098 isl_schedule *s = NULL;
1099 while (nested_in (loop_at (scop, index), loop))
1100 {
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));
1105
1106 if (*index == max)
1107 break;
1108 }
1109
1110 return add_loop_schedule (s, loop, scop);
1111}
1112
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. */
1117
1118static isl_schedule *
1119embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
1120 loop_p loop, int *index, loop_p context_loop)
1121{
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;
1127
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);
1136
1137 bool a_pbb;
1138 while ((a_pbb = (outer == loop_at (scop, index)))
1139 || nested_in (loop_at (scop, index), outer))
1140 {
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));
1145
1146 if (*index == max)
1147 break;
1148 }
1149
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);
1153}
1154
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. */
1159
1160static isl_schedule *
1161build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
1162{
1163 gcc_assert (*index != (int) scop->pbbs.length ());
1164
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);
1168}
1169
1170/* Build the schedule of the SCOP. */
1171
1172static void
1173build_original_schedule (scop_p scop)
1174{
1175 int i = 0;
1176 int n = scop->pbbs.length ();
1177 while (i < n)
1178 {
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);
1185
1186 scop->original_schedule = add_in_sequence (scop->original_schedule, s);
1187 }
1188
1189 if (dump_file)
1190 {
1191 fprintf (dump_file, "[sese-to-poly] original schedule:\n");
1192 print_isl_schedule (dump_file, scop->original_schedule);
1193 }
1194}
1195
1196/* Builds the polyhedral representation for a SESE region. */
1197
1198bool
1199build_poly_scop (scop_p scop)
1200{
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);
1203
1204 build_scop_context (scop);
1205
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);
1210
1211 build_scop_drs (scop);
1212 build_original_schedule (scop);
1213
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");
1221
1222 return err == isl_error_none;
1223}
1224#endif /* HAVE_isl */
1225

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