1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2024 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
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 for the parameter P. */
106 isl_id_for_parameter (scop_p s
, tree p
)
108 gcc_checking_assert (TREE_CODE (p
) == SSA_NAME
);
110 snprintf (name
, sizeof (name
), "P_%d", SSA_NAME_VERSION (p
));
111 return isl_id_alloc (s
->isl_context
, name
, p
);
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. */
120 isl_id_for_dr (scop_p s
)
122 return isl_id_alloc (s
->isl_context
, "", 0);
125 /* Extract an affine expression from the ssa_name E. */
128 extract_affine_name (int dimension
, __isl_take isl_space
*space
)
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
);
136 /* Convert WI to a isl_val with CTX. */
138 static __isl_give isl_val
*
139 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
141 if (wi::neg_p (wi
, SIGNED
))
143 widest_int mwi
= -wi
;
144 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
145 sizeof (HOST_WIDE_INT
),
148 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
152 /* Extract an affine expression from the gmp constant G. */
155 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
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
);
164 return isl_pw_aff_alloc (dom
, aff
);
167 /* Extract an affine expression from the integer_cst E. */
170 extract_affine_int (tree e
, __isl_take isl_space
*space
)
172 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
176 /* Compute pwaff mod 2^width. */
179 wrap (isl_pw_aff
*pwaff
, unsigned width
)
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
);
190 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
191 Otherwise returns -1. */
194 parameter_index_in_region (tree name
, sese_info_p region
)
198 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
204 /* Extract an affine expression from the tree E in the scop S. */
207 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
209 isl_pw_aff
*lhs
, *rhs
, *res
;
211 if (e
== chrec_dont_know
) {
212 isl_space_free (space
);
216 tree type
= TREE_TYPE (e
);
217 switch (TREE_CODE (e
))
219 case POLYNOMIAL_CHREC
:
220 res
= extract_affine_chrec (s
, e
, space
);
224 res
= extract_affine_mul (s
, e
, space
);
227 case POINTER_PLUS_EXPR
:
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
233 tree tem
= TREE_OPERAND (e
, 1);
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
);
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
);
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
);
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));
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
);
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
);
277 res
= extract_affine_int (e
, space
);
278 /* No need to wrap a single integer. */
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
));
299 case NON_LVALUE_EXPR
:
300 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
308 /* For all wrapping arithmetic wrap the result. */
309 if (TYPE_OVERFLOW_WRAPS (type
))
310 res
= wrap (res
, TYPE_PRECISION (type
));
315 /* Returns a linear expression for tree T evaluated in PBB. */
318 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
320 scop_p scop
= PBB_SCOP (pbb
);
322 t
= cached_scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
324 gcc_assert (!chrec_contains_undetermined (t
));
325 gcc_assert (!automatically_generated_chrec_p (t
));
327 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
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
335 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
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
));
345 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
349 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
353 cond
= isl_pw_aff_le_set (lhs
, rhs
);
357 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
361 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
365 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
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
));
377 /* Add conditions to the domain of PBB. */
380 add_conditions_to_domain (poly_bb_p pbb
)
384 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
386 if (GBB_CONDITIONS (gbb
).is_empty ())
389 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
390 switch (gimple_code (stmt
))
394 /* Don't constrain on anything else than INTEGRAL_TYPE_P. */
395 tree cmp_type
= TREE_TYPE (gimple_cond_lhs (stmt
));
396 if (!INTEGRAL_TYPE_P (cmp_type
))
399 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
400 enum tree_code code
= gimple_cond_code (cond_stmt
);
402 /* The conditions for ELSE-branches are inverted. */
403 if (!GBB_CONDITION_CASES (gbb
)[i
])
404 code
= invert_tree_comparison (code
, false);
406 add_condition_to_pbb (pbb
, cond_stmt
, code
);
416 /* Add constraints on the possible values of parameter P from the type
420 add_param_constraints (scop_p scop
, graphite_dim_t p
, tree parameter
)
422 tree type
= TREE_TYPE (parameter
);
426 gcc_assert (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
));
428 if (INTEGRAL_TYPE_P (type
)
429 && get_range_query (cfun
)->range_of_expr (r
, parameter
)
430 && !r
.undefined_p ())
432 min
= r
.lower_bound ();
433 max
= r
.upper_bound ();
437 min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
438 max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
441 isl_space
*space
= isl_set_get_space (scop
->param_context
);
442 isl_constraint
*c
= isl_inequality_alloc (isl_local_space_from_space (space
));
443 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
,
444 widest_int::from (min
, TYPE_SIGN (type
)));
446 c
= isl_constraint_set_constant_val (c
, v
);
447 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
448 scop
->param_context
= isl_set_coalesce
449 (isl_set_add_constraint (scop
->param_context
, c
));
451 space
= isl_set_get_space (scop
->param_context
);
452 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
453 v
= isl_val_int_from_wi (scop
->isl_context
,
454 widest_int::from (max
, TYPE_SIGN (type
)));
455 c
= isl_constraint_set_constant_val (c
, v
);
456 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
457 scop
->param_context
= isl_set_coalesce
458 (isl_set_add_constraint (scop
->param_context
, c
));
461 /* Add a constrain to the ACCESSES polyhedron for the alias set of
462 data reference DR. ACCESSP_NB_DIMS is the dimension of the
463 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
467 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
469 isl_constraint
*c
= isl_equality_alloc
470 (isl_local_space_from_space (isl_map_get_space (acc
)));
471 /* Positive numbers for all alias sets. */
472 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
473 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
475 return isl_map_add_constraint (acc
, c
);
478 /* Assign the affine expression INDEX to the output dimension POS of
479 MAP and return the result. */
482 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
485 int len
= isl_map_dim (map
, isl_dim_out
);
488 index_map
= isl_map_from_pw_aff (index
);
489 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
490 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
492 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
493 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
494 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
495 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
497 return isl_map_intersect (map
, index_map
);
500 /* Add to ACCESSES polyhedron equalities defining the access functions
501 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
502 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
503 PBB is the poly_bb_p that contains the data reference DR. */
506 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
508 data_reference_p dr
= dri
.dr
;
509 poly_bb_p pbb
= dri
.pbb
;
510 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
511 scop_p scop
= PBB_SCOP (pbb
);
513 for (i
= 0; i
< nb_subscripts
; i
++)
516 tree afn
= DR_ACCESS_FN (dr
, i
);
518 aff
= extract_affine (scop
, afn
,
519 isl_space_domain (isl_map_get_space (acc
)));
520 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
523 return isl_map_coalesce (acc
);
526 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
527 to extract constraints on accessed elements of the array. Returning false is
528 the conservative answer. */
531 bounds_are_valid (tree ref
, tree low
, tree high
)
536 if (!tree_fits_shwi_p (low
)
537 || !tree_fits_shwi_p (high
))
540 /* An array that has flexible size may extend over
541 their declared size. */
542 if (array_ref_flexible_size_p (ref
)
543 && operand_equal_p (low
, high
, 0))
546 /* Fortran has some arrays where high bound is -1 and low is 0. */
547 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
553 /* Add constrains representing the size of the accessed data to the
554 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
555 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
559 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
562 tree ref
= DR_REF (dr
);
564 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
565 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
567 if (TREE_CODE (ref
) != ARRAY_REF
)
568 return subscript_sizes
;
570 tree low
= array_ref_low_bound (ref
);
571 tree high
= array_ref_up_bound (ref
);
573 if (!bounds_are_valid (ref
, low
, high
))
576 isl_space
*space
= isl_set_get_space (subscript_sizes
);
577 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
578 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
581 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
582 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
583 isl_set_dim (valid
, isl_dim_set
));
584 scop
->param_context
= isl_set_coalesce
585 (isl_set_intersect (scop
->param_context
, valid
));
588 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
589 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
591 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
592 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
594 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
595 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
596 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
598 /* low <= sub_i <= high */
599 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
600 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
601 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
602 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
605 return isl_set_coalesce (subscript_sizes
);
608 /* Build data accesses for DRI. */
611 build_poly_dr (dr_info
&dri
)
614 isl_set
*subscript_sizes
;
615 poly_bb_p pbb
= dri
.pbb
;
616 data_reference_p dr
= dri
.dr
;
617 scop_p scop
= PBB_SCOP (pbb
);
618 isl_id
*id
= isl_id_for_dr (scop
);
621 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
622 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
623 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
624 isl_dim_out
, nb_out
);
626 acc
= isl_map_universe (space
);
627 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
630 acc
= pdr_add_alias_set (acc
, dri
);
631 acc
= pdr_add_memory_accesses (acc
, dri
);
634 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
635 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
637 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
638 subscript_sizes
= isl_set_nat_universe (space
);
639 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
641 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
644 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
645 acc
, subscript_sizes
);
649 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
650 isl_map
*acc
, isl_set
*subscript_sizes
)
652 scop_p scop
= PBB_SCOP (pbb
);
653 /* Each scalar variable has a unique alias set number starting from
654 the maximum alias set assigned to a dr. */
655 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
656 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
659 /* Add a constrain to the ACCESSES polyhedron for the alias set of
662 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
663 c
= isl_constraint_set_constant_si (c
, -alias_set
);
664 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
666 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
670 /* Record all cross basic block scalar variables in PBB. */
673 build_poly_sr (poly_bb_p pbb
)
675 scop_p scop
= PBB_SCOP (pbb
);
676 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
677 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
678 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
680 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
682 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
683 isl_dim_out
, nb_out
);
684 isl_id
*id
= isl_id_for_dr (scop
);
685 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
686 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
687 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
688 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
692 FOR_EACH_VEC_ELT (writes
, i
, var
)
693 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
694 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
697 FOR_EACH_VEC_ELT (reads
, i
, use
)
698 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
699 isl_set_copy (subscript_sizes
));
702 isl_set_free (subscript_sizes
);
705 /* Build data references in SCOP. */
708 build_scop_drs (scop_p scop
)
712 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
713 build_poly_dr (*dri
);
716 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
720 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
723 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
725 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
726 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
728 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
729 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
730 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
733 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
736 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
741 const sese_l
®ion
= scop
->scop_info
->region
;
742 if (!loop_in_sese_p (loop
, region
))
745 /* Recursion all the way up to the context loop. */
746 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
748 /* Then, build constraints over the loop in post-order: outer to inner. */
750 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
752 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
753 "domain for loop_%d.\n", loop
->num
);
754 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
755 isl_space
*space
= isl_set_get_space (domain
);
758 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
759 isl_constraint
*c
= isl_inequality_alloc (ls
);
760 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
763 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
764 print_isl_constraint (dump_file
, c
);
766 domain
= isl_set_add_constraint (domain
, c
);
768 tree nb_iters
= number_of_latch_executions (loop
);
769 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
771 /* loop_i <= cst_nb_iters */
772 isl_local_space
*ls
= isl_local_space_from_space (space
);
773 isl_constraint
*c
= isl_inequality_alloc (ls
);
774 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
776 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
777 c
= isl_constraint_set_constant_val (c
, v
);
778 return isl_set_add_constraint (domain
, c
);
780 /* loop_i <= expr_nb_iters */
781 gcc_assert (!chrec_contains_undetermined (nb_iters
));
782 nb_iters
= cached_scalar_evolution_in_region (region
, loop
, nb_iters
);
783 gcc_assert (!chrec_contains_undetermined (nb_iters
));
785 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
786 isl_space_copy (space
));
787 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
788 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
789 isl_set_dim (valid
, isl_dim_set
));
792 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
794 ls
= isl_local_space_from_space (isl_space_copy (space
));
795 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
796 isl_dim_in
, loop_index
, 1);
797 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
798 isl_pw_aff_copy (aff_nb_iters
));
801 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
802 print_isl_set (dump_file
, le
);
804 domain
= isl_set_intersect (domain
, le
);
807 if (!max_stmt_executions (loop
, &nit
))
809 isl_pw_aff_free (aff_nb_iters
);
810 isl_space_free (space
);
814 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
815 do not know whether the loop executes at least once. */
818 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
819 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
820 x
= isl_set_project_out (x
, isl_dim_set
, 0,
821 isl_set_dim (x
, isl_dim_set
));
822 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
824 ls
= isl_local_space_from_space (space
);
825 c
= isl_inequality_alloc (ls
);
826 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
827 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
828 c
= isl_constraint_set_constant_val (c
, v
);
832 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
833 print_isl_constraint (dump_file
, c
);
836 return isl_set_add_constraint (domain
, c
);
839 /* Builds the original iteration domains for each pbb in the SCOP. */
842 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
843 int index
, loop_p context_loop
)
845 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
846 isl_set
*domain
= isl_set_copy (context
);
847 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
848 const sese_l
®ion
= scop
->scop_info
->region
;
852 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
854 loop_p loop
= pbb_loop (pbb
);
857 pbb
->iterators
= isl_set_copy (domain
);
858 pbb
->domain
= isl_set_copy (domain
);
859 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
860 isl_id_for_pbb (scop
, pbb
));
861 add_conditions_to_domain (pbb
);
865 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
867 print_isl_set (dump_file
, domain
);
872 while (loop_in_sese_p (loop
, region
)
874 loop
= loop_outer (loop
);
878 /* A statement in a different loop nest than CURRENT loop. */
879 isl_set_free (domain
);
883 /* A statement nested in the CURRENT loop. */
884 i
= build_iteration_domains (scop
, domain
, i
, current
);
888 isl_set_free (domain
);
892 /* Assign dimension for each parameter in SCOP and add constraints for the
896 build_scop_context (scop_p scop
)
898 sese_info_p region
= scop
->scop_info
;
899 unsigned nbp
= sese_nb_params (region
);
900 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
904 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
905 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
906 isl_id_for_parameter (scop
, p
));
908 scop
->param_context
= isl_set_universe (space
);
910 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
911 add_param_constraints (scop
, i
, p
);
914 /* Return true when loop A is nested in loop B. */
917 nested_in (loop_p a
, loop_p b
)
919 return b
== find_common_loop (a
, b
);
922 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
924 loop_at (scop_p scop
, int *index
)
926 return pbb_loop (scop
->pbbs
[*index
]);
929 /* Return the index of any pbb belonging to loop or a subloop of A. */
932 index_outermost_in_loop (loop_p a
, scop_p scop
)
934 int i
, outermost
= -1;
937 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
938 if (nested_in (pbb_loop (pbb
), a
)
940 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
943 last_depth
= loop_depth (pbb_loop (pbb
));
948 /* Return the index of any pbb belonging to loop or a subloop of A. */
951 index_pbb_in_loop (loop_p a
, scop_p scop
)
955 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
956 if (pbb_loop (pbb
) == a
)
962 outermost_pbb_in (loop_p loop
, scop_p scop
)
964 int x
= index_pbb_in_loop (loop
, scop
);
966 x
= index_outermost_in_loop (loop
, scop
);
967 return scop
->pbbs
[x
];
970 static isl_schedule
*
971 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
981 return isl_schedule_sequence (a
, b
);
984 struct map_to_dimension_data
{
986 isl_union_pw_multi_aff
*res
;
989 /* Create a function that maps the elements of SET to its N-th dimension and add
993 add_outer_projection (__isl_take isl_set
*set
, void *user
)
995 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
996 int dim
= isl_set_dim (set
, isl_dim_set
);
997 isl_space
*space
= isl_set_get_space (set
);
999 gcc_assert (dim
>= data
->n
);
1000 isl_pw_multi_aff
*pma
1001 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1003 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1009 /* Return SET in which all inner dimensions above N are removed. */
1011 static isl_multi_union_pw_aff
*
1012 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1014 gcc_assert (n
>= 0);
1016 gcc_assert (!isl_union_set_is_empty (set
));
1018 isl_space
*space
= isl_union_set_get_space (set
);
1019 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1021 struct map_to_dimension_data data
= {n
, pwaff
};
1023 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1024 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1026 isl_union_set_free (set
);
1027 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1030 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1032 static isl_schedule
*
1033 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1036 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1037 isl_set
*iterators
= pbb
->iterators
;
1039 int empty
= isl_set_is_empty (iterators
);
1040 if (empty
< 0 || empty
)
1041 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1043 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1044 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1045 if (isl_union_set_is_empty (domain
))
1047 isl_union_set_free (domain
);
1051 isl_space
*space
= isl_set_get_space (iterators
);
1052 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1054 loop_p ploop
= pbb_loop (pbb
);
1055 while (loop
!= ploop
)
1058 ploop
= loop_outer (ploop
);
1061 isl_local_space
*ls
= isl_local_space_from_space (space
);
1062 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1063 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1065 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1066 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1068 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1070 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1071 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1072 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1073 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1076 /* Build schedule for the pbb at INDEX. */
1078 static isl_schedule
*
1079 build_schedule_pbb (scop_p scop
, int *index
)
1081 poly_bb_p pbb
= scop
->pbbs
[*index
];
1083 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1084 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1085 return isl_schedule_from_domain (ud
);
1088 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1090 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1092 static isl_schedule
*
1093 build_schedule_loop (scop_p scop
, int *index
)
1095 int max
= scop
->pbbs
.length ();
1096 gcc_assert (*index
< max
);
1097 loop_p loop
= loop_at (scop
, index
);
1099 isl_schedule
*s
= NULL
;
1100 while (nested_in (loop_at (scop
, index
), loop
))
1102 if (loop
== loop_at (scop
, index
))
1103 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1105 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1111 return add_loop_schedule (s
, loop
, scop
);
1114 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1115 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1116 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1117 maximal loop nest contained within CONTEXT_LOOP. */
1119 static isl_schedule
*
1120 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1121 loop_p loop
, int *index
, loop_p context_loop
)
1123 loop_p outer
= loop_outer (loop
);
1124 sese_l region
= scop
->scop_info
->region
;
1125 if (context_loop
== outer
1126 || !loop_in_sese_p (outer
, region
))
1129 int max
= scop
->pbbs
.length ();
1131 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1133 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1135 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1136 scop
, outer
, index
, context_loop
);
1139 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1140 || nested_in (loop_at (scop
, index
), outer
))
1143 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1145 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1151 /* We reached the end of the OUTER loop: embed S in OUTER. */
1152 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1153 outer
, index
, context_loop
);
1156 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1157 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1158 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1159 nest contained within CONTEXT_LOOP. */
1161 static isl_schedule
*
1162 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1164 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1166 loop_p loop
= loop_at (scop
, index
);
1167 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1168 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1171 /* Build the schedule of the SCOP. */
1174 build_original_schedule (scop_p scop
)
1177 int n
= scop
->pbbs
.length ();
1180 poly_bb_p pbb
= scop
->pbbs
[i
];
1181 isl_schedule
*s
= NULL
;
1182 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1183 s
= build_schedule_pbb (scop
, &i
);
1185 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1187 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1192 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1193 print_isl_schedule (dump_file
, scop
->original_schedule
);
1197 /* Builds the polyhedral representation for a SESE region. */
1200 build_poly_scop (scop_p scop
)
1202 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1203 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1205 build_scop_context (scop
);
1208 unsigned n
= scop
->pbbs
.length ();
1210 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1212 build_scop_drs (scop
);
1213 build_original_schedule (scop
);
1215 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1216 isl_ctx_reset_error (scop
->isl_context
);
1217 isl_options_set_on_error (scop
->isl_context
, old_err
);
1218 if (err
!= isl_error_none
1219 && dump_enabled_p ())
1220 dump_printf (MSG_MISSED_OPTIMIZATION
,
1221 "ISL error while building poly scop\n");
1223 return err
== isl_error_none
;
1225 #endif /* HAVE_isl */