1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2022 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
34 #include "fold-const.h"
35 #include "gimple-iterator.h"
37 #include "gimplify-me.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"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
48 #include "tree-ssa-propagate.h"
51 /* Return an isl identifier for the polyhedral basic block PBB. */
54 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
57 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
58 return isl_id_alloc (s
->isl_context
, name
, pbb
);
61 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
63 /* Extract an affine expression from the chain of recurrence E. */
66 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
68 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
69 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
70 isl_local_space
*ls
= isl_local_space_from_space (space
);
71 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
72 isl_aff
*loop
= isl_aff_set_coefficient_si
73 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
74 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
76 /* Before multiplying, make sure that the result is affine. */
77 gcc_assert (isl_pw_aff_is_cst (rhs
)
78 || isl_pw_aff_is_cst (l
));
80 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
83 /* Extract an affine expression from the mult_expr E. */
86 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
88 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
89 isl_space_copy (space
));
90 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
92 if (!isl_pw_aff_is_cst (lhs
)
93 && !isl_pw_aff_is_cst (rhs
))
95 isl_pw_aff_free (lhs
);
96 isl_pw_aff_free (rhs
);
100 return isl_pw_aff_mul (lhs
, rhs
);
103 /* Return an isl identifier from the name of the ssa_name E. */
106 isl_id_for_ssa_name (scop_p s
, tree e
)
109 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
110 return isl_id_alloc (s
->isl_context
, name1
, e
);
113 /* Return an isl identifier for the data reference DR. Data references and
114 scalar references get the same isl_id. They need to be comparable and are
115 distinguished through the first dimension, which contains the alias set or
116 SSA_NAME_VERSION number. */
119 isl_id_for_dr (scop_p s
)
121 return isl_id_alloc (s
->isl_context
, "", 0);
124 /* Extract an affine expression from the ssa_name E. */
127 extract_affine_name (int dimension
, __isl_take isl_space
*space
)
129 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
130 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
131 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
132 return isl_pw_aff_alloc (dom
, aff
);
135 /* Convert WI to a isl_val with CTX. */
137 static __isl_give isl_val
*
138 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
140 if (wi::neg_p (wi
, SIGNED
))
142 widest_int mwi
= -wi
;
143 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
144 sizeof (HOST_WIDE_INT
),
147 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
151 /* Extract an affine expression from the gmp constant G. */
154 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
156 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
157 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
158 isl_set
*dom
= isl_set_universe (space
);
159 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
160 isl_val
*v
= isl_val_int_from_wi (ct
, g
);
161 aff
= isl_aff_add_constant_val (aff
, v
);
163 return isl_pw_aff_alloc (dom
, aff
);
166 /* Extract an affine expression from the integer_cst E. */
169 extract_affine_int (tree e
, __isl_take isl_space
*space
)
171 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
175 /* Compute pwaff mod 2^width. */
178 wrap (isl_pw_aff
*pwaff
, unsigned width
)
182 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
183 mod
= isl_val_2exp (mod
);
184 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
189 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
190 Otherwise returns -1. */
193 parameter_index_in_region (tree name
, sese_info_p region
)
197 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
203 /* Extract an affine expression from the tree E in the scop S. */
206 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
208 isl_pw_aff
*lhs
, *rhs
, *res
;
210 if (e
== chrec_dont_know
) {
211 isl_space_free (space
);
215 tree type
= TREE_TYPE (e
);
216 switch (TREE_CODE (e
))
218 case POLYNOMIAL_CHREC
:
219 res
= extract_affine_chrec (s
, e
, space
);
223 res
= extract_affine_mul (s
, e
, space
);
226 case POINTER_PLUS_EXPR
:
228 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
229 /* The RHS of a pointer-plus expression is to be interpreted
230 as signed value. Try to look through a sign-changing conversion
232 tree tem
= TREE_OPERAND (e
, 1);
234 rhs
= extract_affine (s
, tem
, space
);
235 if (TYPE_UNSIGNED (TREE_TYPE (tem
)))
236 rhs
= wrap (rhs
, TYPE_PRECISION (type
) - 1);
237 res
= isl_pw_aff_add (lhs
, rhs
);
242 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
243 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
244 res
= isl_pw_aff_add (lhs
, rhs
);
248 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
249 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
250 res
= isl_pw_aff_sub (lhs
, rhs
);
254 lhs
= extract_affine (s
, integer_minus_one_node
, isl_space_copy (space
));
255 rhs
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
256 res
= isl_pw_aff_sub (lhs
, rhs
);
257 /* We need to always wrap the result of a bitwise operation. */
258 return wrap (res
, TYPE_PRECISION (type
) - (TYPE_UNSIGNED (type
) ? 0 : 1));
261 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
262 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
263 res
= isl_pw_aff_mul (lhs
, rhs
);
268 gcc_assert (! defined_in_sese_p (e
, s
->scop_info
->region
));
269 int dim
= parameter_index_in_region (e
, s
->scop_info
);
270 gcc_assert (dim
!= -1);
271 /* No need to wrap a parameter. */
272 return extract_affine_name (dim
, space
);
276 res
= extract_affine_int (e
, space
);
277 /* No need to wrap a single integer. */
282 tree itype
= TREE_TYPE (TREE_OPERAND (e
, 0));
283 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
284 /* Signed values, even if overflow is undefined, get modulo-reduced.
285 But only if not all values of the old type fit in the new. */
286 if (! TYPE_UNSIGNED (type
)
287 && ((TYPE_UNSIGNED (itype
)
288 && TYPE_PRECISION (type
) <= TYPE_PRECISION (itype
))
289 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
290 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
291 else if (TYPE_UNSIGNED (type
)
292 && (!TYPE_UNSIGNED (itype
)
293 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
294 res
= wrap (res
, TYPE_PRECISION (type
));
298 case NON_LVALUE_EXPR
:
299 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
307 /* For all wrapping arithmetic wrap the result. */
308 if (TYPE_OVERFLOW_WRAPS (type
))
309 res
= wrap (res
, TYPE_PRECISION (type
));
314 /* Returns a linear expression for tree T evaluated in PBB. */
317 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
319 scop_p scop
= PBB_SCOP (pbb
);
321 t
= cached_scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
323 gcc_assert (!chrec_contains_undetermined (t
));
324 gcc_assert (!automatically_generated_chrec_p (t
));
326 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
329 /* Add conditional statement STMT to pbb. CODE is used as the comparison
330 operator. This allows us to invert the condition or to handle
334 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
336 loop_p loop
= gimple_bb (stmt
)->loop_father
;
337 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
338 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
344 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
348 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
352 cond
= isl_pw_aff_le_set (lhs
, rhs
);
356 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
360 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
364 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
371 cond
= isl_set_coalesce (cond
);
372 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
373 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
376 /* Add conditions to the domain of PBB. */
379 add_conditions_to_domain (poly_bb_p pbb
)
383 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
385 if (GBB_CONDITIONS (gbb
).is_empty ())
388 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
389 switch (gimple_code (stmt
))
393 /* Don't constrain on anything else than INTEGER_TYPE. */
394 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
397 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
398 enum tree_code code
= gimple_cond_code (cond_stmt
);
400 /* The conditions for ELSE-branches are inverted. */
401 if (!GBB_CONDITION_CASES (gbb
)[i
])
402 code
= invert_tree_comparison (code
, false);
404 add_condition_to_pbb (pbb
, cond_stmt
, code
);
414 /* Add constraints on the possible values of parameter P from the type
418 add_param_constraints (scop_p scop
, graphite_dim_t p
, tree parameter
)
420 tree type
= TREE_TYPE (parameter
);
424 gcc_assert (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
));
426 if (INTEGRAL_TYPE_P (type
)
427 && get_range_query (cfun
)->range_of_expr (r
, parameter
)
428 && !r
.undefined_p ())
430 min
= r
.lower_bound ();
431 max
= r
.upper_bound ();
435 min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
436 max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
439 isl_space
*space
= isl_set_get_space (scop
->param_context
);
440 isl_constraint
*c
= isl_inequality_alloc (isl_local_space_from_space (space
));
441 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
,
442 widest_int::from (min
, TYPE_SIGN (type
)));
444 c
= isl_constraint_set_constant_val (c
, v
);
445 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
446 scop
->param_context
= isl_set_coalesce
447 (isl_set_add_constraint (scop
->param_context
, c
));
449 space
= isl_set_get_space (scop
->param_context
);
450 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
451 v
= isl_val_int_from_wi (scop
->isl_context
,
452 widest_int::from (max
, TYPE_SIGN (type
)));
453 c
= isl_constraint_set_constant_val (c
, v
);
454 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
455 scop
->param_context
= isl_set_coalesce
456 (isl_set_add_constraint (scop
->param_context
, c
));
459 /* Add a constrain to the ACCESSES polyhedron for the alias set of
460 data reference DR. ACCESSP_NB_DIMS is the dimension of the
461 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
465 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
467 isl_constraint
*c
= isl_equality_alloc
468 (isl_local_space_from_space (isl_map_get_space (acc
)));
469 /* Positive numbers for all alias sets. */
470 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
471 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
473 return isl_map_add_constraint (acc
, c
);
476 /* Assign the affine expression INDEX to the output dimension POS of
477 MAP and return the result. */
480 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
483 int len
= isl_map_dim (map
, isl_dim_out
);
486 index_map
= isl_map_from_pw_aff (index
);
487 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
488 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
490 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
491 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
492 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
493 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
495 return isl_map_intersect (map
, index_map
);
498 /* Add to ACCESSES polyhedron equalities defining the access functions
499 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
500 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
501 PBB is the poly_bb_p that contains the data reference DR. */
504 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
506 data_reference_p dr
= dri
.dr
;
507 poly_bb_p pbb
= dri
.pbb
;
508 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
509 scop_p scop
= PBB_SCOP (pbb
);
511 for (i
= 0; i
< nb_subscripts
; i
++)
514 tree afn
= DR_ACCESS_FN (dr
, i
);
516 aff
= extract_affine (scop
, afn
,
517 isl_space_domain (isl_map_get_space (acc
)));
518 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
521 return isl_map_coalesce (acc
);
524 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
525 to extract constraints on accessed elements of the array. Returning false is
526 the conservative answer. */
529 bounds_are_valid (tree ref
, tree low
, tree high
)
534 if (!tree_fits_shwi_p (low
)
535 || !tree_fits_shwi_p (high
))
538 /* 1-element arrays at end of structures may extend over
539 their declared size. */
540 if (array_at_struct_end_p (ref
)
541 && operand_equal_p (low
, high
, 0))
544 /* Fortran has some arrays where high bound is -1 and low is 0. */
545 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
551 /* Add constrains representing the size of the accessed data to the
552 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
553 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
557 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
560 tree ref
= DR_REF (dr
);
562 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
563 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
565 if (TREE_CODE (ref
) != ARRAY_REF
)
566 return subscript_sizes
;
568 tree low
= array_ref_low_bound (ref
);
569 tree high
= array_ref_up_bound (ref
);
571 if (!bounds_are_valid (ref
, low
, high
))
574 isl_space
*space
= isl_set_get_space (subscript_sizes
);
575 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
576 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
579 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
580 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
581 isl_set_dim (valid
, isl_dim_set
));
582 scop
->param_context
= isl_set_coalesce
583 (isl_set_intersect (scop
->param_context
, valid
));
586 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
587 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
589 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
590 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
592 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
593 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
594 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
596 /* low <= sub_i <= high */
597 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
598 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
599 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
600 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
603 return isl_set_coalesce (subscript_sizes
);
606 /* Build data accesses for DRI. */
609 build_poly_dr (dr_info
&dri
)
612 isl_set
*subscript_sizes
;
613 poly_bb_p pbb
= dri
.pbb
;
614 data_reference_p dr
= dri
.dr
;
615 scop_p scop
= PBB_SCOP (pbb
);
616 isl_id
*id
= isl_id_for_dr (scop
);
619 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
620 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
621 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
622 isl_dim_out
, nb_out
);
624 acc
= isl_map_universe (space
);
625 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
628 acc
= pdr_add_alias_set (acc
, dri
);
629 acc
= pdr_add_memory_accesses (acc
, dri
);
632 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
633 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
635 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
636 subscript_sizes
= isl_set_nat_universe (space
);
637 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
639 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
642 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
643 acc
, subscript_sizes
);
647 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
648 isl_map
*acc
, isl_set
*subscript_sizes
)
650 scop_p scop
= PBB_SCOP (pbb
);
651 /* Each scalar variables has a unique alias set number starting from
652 the maximum alias set assigned to a dr. */
653 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
654 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
657 /* Add a constrain to the ACCESSES polyhedron for the alias set of
658 data reference DR. */
660 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
661 c
= isl_constraint_set_constant_si (c
, -alias_set
);
662 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
664 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
668 /* Record all cross basic block scalar variables in PBB. */
671 build_poly_sr (poly_bb_p pbb
)
673 scop_p scop
= PBB_SCOP (pbb
);
674 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
675 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
676 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
678 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
680 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
681 isl_dim_out
, nb_out
);
682 isl_id
*id
= isl_id_for_dr (scop
);
683 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
684 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
685 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
686 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
690 FOR_EACH_VEC_ELT (writes
, i
, var
)
691 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
692 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
695 FOR_EACH_VEC_ELT (reads
, i
, use
)
696 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
697 isl_set_copy (subscript_sizes
));
700 isl_set_free (subscript_sizes
);
703 /* Build data references in SCOP. */
706 build_scop_drs (scop_p scop
)
710 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
711 build_poly_dr (*dri
);
714 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
718 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
721 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
723 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
724 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
726 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
727 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
728 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
731 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
734 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
739 const sese_l
®ion
= scop
->scop_info
->region
;
740 if (!loop_in_sese_p (loop
, region
))
743 /* Recursion all the way up to the context loop. */
744 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
746 /* Then, build constraints over the loop in post-order: outer to inner. */
748 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
750 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
751 "domain for loop_%d.\n", loop
->num
);
752 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
753 isl_space
*space
= isl_set_get_space (domain
);
756 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
757 isl_constraint
*c
= isl_inequality_alloc (ls
);
758 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
761 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
762 print_isl_constraint (dump_file
, c
);
764 domain
= isl_set_add_constraint (domain
, c
);
766 tree nb_iters
= number_of_latch_executions (loop
);
767 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
769 /* loop_i <= cst_nb_iters */
770 isl_local_space
*ls
= isl_local_space_from_space (space
);
771 isl_constraint
*c
= isl_inequality_alloc (ls
);
772 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
774 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
775 c
= isl_constraint_set_constant_val (c
, v
);
776 return isl_set_add_constraint (domain
, c
);
778 /* loop_i <= expr_nb_iters */
779 gcc_assert (!chrec_contains_undetermined (nb_iters
));
780 nb_iters
= cached_scalar_evolution_in_region (region
, loop
, nb_iters
);
781 gcc_assert (!chrec_contains_undetermined (nb_iters
));
783 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
784 isl_space_copy (space
));
785 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
786 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
787 isl_set_dim (valid
, isl_dim_set
));
790 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
792 ls
= isl_local_space_from_space (isl_space_copy (space
));
793 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
794 isl_dim_in
, loop_index
, 1);
795 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
796 isl_pw_aff_copy (aff_nb_iters
));
799 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
800 print_isl_set (dump_file
, le
);
802 domain
= isl_set_intersect (domain
, le
);
805 if (!max_stmt_executions (loop
, &nit
))
807 isl_pw_aff_free (aff_nb_iters
);
808 isl_space_free (space
);
812 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
813 do not know whether the loop executes at least once. */
816 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
817 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
818 x
= isl_set_project_out (x
, isl_dim_set
, 0,
819 isl_set_dim (x
, isl_dim_set
));
820 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
822 ls
= isl_local_space_from_space (space
);
823 c
= isl_inequality_alloc (ls
);
824 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
825 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
826 c
= isl_constraint_set_constant_val (c
, v
);
830 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
831 print_isl_constraint (dump_file
, c
);
834 return isl_set_add_constraint (domain
, c
);
837 /* Builds the original iteration domains for each pbb in the SCOP. */
840 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
841 int index
, loop_p context_loop
)
843 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
844 isl_set
*domain
= isl_set_copy (context
);
845 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
846 const sese_l
®ion
= scop
->scop_info
->region
;
850 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
852 loop_p loop
= pbb_loop (pbb
);
855 pbb
->iterators
= isl_set_copy (domain
);
856 pbb
->domain
= isl_set_copy (domain
);
857 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
858 isl_id_for_pbb (scop
, pbb
));
859 add_conditions_to_domain (pbb
);
863 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
865 print_isl_set (dump_file
, domain
);
870 while (loop_in_sese_p (loop
, region
)
872 loop
= loop_outer (loop
);
876 /* A statement in a different loop nest than CURRENT loop. */
877 isl_set_free (domain
);
881 /* A statement nested in the CURRENT loop. */
882 i
= build_iteration_domains (scop
, domain
, i
, current
);
886 isl_set_free (domain
);
890 /* Assign dimension for each parameter in SCOP and add constraints for the
894 build_scop_context (scop_p scop
)
896 sese_info_p region
= scop
->scop_info
;
897 unsigned nbp
= sese_nb_params (region
);
898 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
902 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
903 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
904 isl_id_for_ssa_name (scop
, e
));
906 scop
->param_context
= isl_set_universe (space
);
908 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
909 add_param_constraints (scop
, i
, e
);
912 /* Return true when loop A is nested in loop B. */
915 nested_in (loop_p a
, loop_p b
)
917 return b
== find_common_loop (a
, b
);
920 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
922 loop_at (scop_p scop
, int *index
)
924 return pbb_loop (scop
->pbbs
[*index
]);
927 /* Return the index of any pbb belonging to loop or a subloop of A. */
930 index_outermost_in_loop (loop_p a
, scop_p scop
)
932 int i
, outermost
= -1;
935 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
936 if (nested_in (pbb_loop (pbb
), a
)
938 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
941 last_depth
= loop_depth (pbb_loop (pbb
));
946 /* Return the index of any pbb belonging to loop or a subloop of A. */
949 index_pbb_in_loop (loop_p a
, scop_p scop
)
953 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
954 if (pbb_loop (pbb
) == a
)
960 outermost_pbb_in (loop_p loop
, scop_p scop
)
962 int x
= index_pbb_in_loop (loop
, scop
);
964 x
= index_outermost_in_loop (loop
, scop
);
965 return scop
->pbbs
[x
];
968 static isl_schedule
*
969 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
979 return isl_schedule_sequence (a
, b
);
982 struct map_to_dimension_data
{
984 isl_union_pw_multi_aff
*res
;
987 /* Create a function that maps the elements of SET to its N-th dimension and add
991 add_outer_projection (__isl_take isl_set
*set
, void *user
)
993 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
994 int dim
= isl_set_dim (set
, isl_dim_set
);
995 isl_space
*space
= isl_set_get_space (set
);
997 gcc_assert (dim
>= data
->n
);
998 isl_pw_multi_aff
*pma
999 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1001 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1007 /* Return SET in which all inner dimensions above N are removed. */
1009 static isl_multi_union_pw_aff
*
1010 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1012 gcc_assert (n
>= 0);
1014 gcc_assert (!isl_union_set_is_empty (set
));
1016 isl_space
*space
= isl_union_set_get_space (set
);
1017 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1019 struct map_to_dimension_data data
= {n
, pwaff
};
1021 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1022 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1024 isl_union_set_free (set
);
1025 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1028 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1030 static isl_schedule
*
1031 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1034 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1035 isl_set
*iterators
= pbb
->iterators
;
1037 int empty
= isl_set_is_empty (iterators
);
1038 if (empty
< 0 || empty
)
1039 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1041 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1042 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1043 if (isl_union_set_is_empty (domain
))
1045 isl_union_set_free (domain
);
1049 isl_space
*space
= isl_set_get_space (iterators
);
1050 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1052 loop_p ploop
= pbb_loop (pbb
);
1053 while (loop
!= ploop
)
1056 ploop
= loop_outer (ploop
);
1059 isl_local_space
*ls
= isl_local_space_from_space (space
);
1060 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1061 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1063 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1064 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1066 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1068 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1069 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1070 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1071 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1074 /* Build schedule for the pbb at INDEX. */
1076 static isl_schedule
*
1077 build_schedule_pbb (scop_p scop
, int *index
)
1079 poly_bb_p pbb
= scop
->pbbs
[*index
];
1081 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1082 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1083 return isl_schedule_from_domain (ud
);
1086 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1088 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1090 static isl_schedule
*
1091 build_schedule_loop (scop_p scop
, int *index
)
1093 int max
= scop
->pbbs
.length ();
1094 gcc_assert (*index
< max
);
1095 loop_p loop
= loop_at (scop
, index
);
1097 isl_schedule
*s
= NULL
;
1098 while (nested_in (loop_at (scop
, index
), loop
))
1100 if (loop
== loop_at (scop
, index
))
1101 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1103 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1109 return add_loop_schedule (s
, loop
, scop
);
1112 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1113 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1114 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1115 maximal loop nest contained within CONTEXT_LOOP. */
1117 static isl_schedule
*
1118 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1119 loop_p loop
, int *index
, loop_p context_loop
)
1121 loop_p outer
= loop_outer (loop
);
1122 sese_l region
= scop
->scop_info
->region
;
1123 if (context_loop
== outer
1124 || !loop_in_sese_p (outer
, region
))
1127 int max
= scop
->pbbs
.length ();
1129 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1131 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1133 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1134 scop
, outer
, index
, context_loop
);
1137 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1138 || nested_in (loop_at (scop
, index
), outer
))
1141 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1143 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1149 /* We reached the end of the OUTER loop: embed S in OUTER. */
1150 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1151 outer
, index
, context_loop
);
1154 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1155 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1156 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1157 nest contained within CONTEXT_LOOP. */
1159 static isl_schedule
*
1160 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1162 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1164 loop_p loop
= loop_at (scop
, index
);
1165 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1166 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1169 /* Build the schedule of the SCOP. */
1172 build_original_schedule (scop_p scop
)
1175 int n
= scop
->pbbs
.length ();
1178 poly_bb_p pbb
= scop
->pbbs
[i
];
1179 isl_schedule
*s
= NULL
;
1180 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1181 s
= build_schedule_pbb (scop
, &i
);
1183 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1185 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1190 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1191 print_isl_schedule (dump_file
, scop
->original_schedule
);
1195 /* Builds the polyhedral representation for a SESE region. */
1198 build_poly_scop (scop_p scop
)
1200 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1201 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1203 build_scop_context (scop
);
1206 unsigned n
= scop
->pbbs
.length ();
1208 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1210 build_scop_drs (scop
);
1211 build_original_schedule (scop
);
1213 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1214 isl_ctx_reset_error (scop
->isl_context
);
1215 isl_options_set_on_error (scop
->isl_context
, old_err
);
1216 if (err
!= isl_error_none
1217 && dump_enabled_p ())
1218 dump_printf (MSG_MISSED_OPTIMIZATION
,
1219 "ISL error while building poly scop\n");
1221 return err
== isl_error_none
;
1223 #endif /* HAVE_isl */