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