1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2018 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"
35 #include "fold-const.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.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"
46 #include "tree-data-ref.h"
47 #include "tree-scalar-evolution.h"
49 #include "tree-ssa-propagate.h"
51 #include <isl/constraint.h>
54 #include <isl/union_map.h>
55 #include <isl/constraint.h>
61 /* Assigns to RES the value of the INTEGER_CST T. */
64 tree_int_to_gmp (tree t
, mpz_t res
)
66 wi::to_mpz (wi::to_wide (t
), res
, TYPE_SIGN (TREE_TYPE (t
)));
69 /* Return an isl identifier for the polyhedral basic block PBB. */
72 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
75 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
76 return isl_id_alloc (s
->isl_context
, name
, pbb
);
79 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
81 /* Extract an affine expression from the chain of recurrence E. */
84 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
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
);
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
));
98 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
101 /* Extract an affine expression from the mult_expr E. */
104 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
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
);
110 if (!isl_pw_aff_is_cst (lhs
)
111 && !isl_pw_aff_is_cst (rhs
))
113 isl_pw_aff_free (lhs
);
114 isl_pw_aff_free (rhs
);
118 return isl_pw_aff_mul (lhs
, rhs
);
121 /* Return an isl identifier from the name of the ssa_name E. */
124 isl_id_for_ssa_name (scop_p s
, tree e
)
127 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
128 return isl_id_alloc (s
->isl_context
, name1
, e
);
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. */
137 isl_id_for_dr (scop_p s
)
139 return isl_id_alloc (s
->isl_context
, "", 0);
142 /* Extract an affine expression from the ssa_name E. */
145 extract_affine_name (int dimension
, __isl_take isl_space
*space
)
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
);
153 /* Convert WI to a isl_val with CTX. */
155 static __isl_give isl_val
*
156 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
158 if (wi::neg_p (wi
, SIGNED
))
160 widest_int mwi
= -wi
;
161 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
162 sizeof (HOST_WIDE_INT
),
165 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
169 /* Extract an affine expression from the gmp constant G. */
172 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
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
);
181 return isl_pw_aff_alloc (dom
, aff
);
184 /* Extract an affine expression from the integer_cst E. */
187 extract_affine_int (tree e
, __isl_take isl_space
*space
)
189 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
193 /* Compute pwaff mod 2^width. */
196 wrap (isl_pw_aff
*pwaff
, unsigned width
)
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
);
207 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
208 Otherwise returns -1. */
211 parameter_index_in_region (tree name
, sese_info_p region
)
215 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
221 /* Extract an affine expression from the tree E in the scop S. */
224 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
226 isl_pw_aff
*lhs
, *rhs
, *res
;
228 if (e
== chrec_dont_know
) {
229 isl_space_free (space
);
233 tree type
= TREE_TYPE (e
);
234 switch (TREE_CODE (e
))
236 case POLYNOMIAL_CHREC
:
237 res
= extract_affine_chrec (s
, e
, space
);
241 res
= extract_affine_mul (s
, e
, space
);
244 case POINTER_PLUS_EXPR
:
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
250 tree tem
= TREE_OPERAND (e
, 1);
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
);
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
);
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
);
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 /* We need to always wrap the result of a bitwise operation. */
276 return wrap (res
, TYPE_PRECISION (type
) - (TYPE_UNSIGNED (type
) ? 0 : 1));
279 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
280 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
281 res
= isl_pw_aff_mul (lhs
, rhs
);
286 gcc_assert (! defined_in_sese_p (e
, s
->scop_info
->region
));
287 int dim
= parameter_index_in_region (e
, s
->scop_info
);
288 gcc_assert (dim
!= -1);
289 /* No need to wrap a parameter. */
290 return extract_affine_name (dim
, space
);
294 res
= extract_affine_int (e
, space
);
295 /* No need to wrap a single integer. */
300 tree itype
= TREE_TYPE (TREE_OPERAND (e
, 0));
301 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
302 /* Signed values, even if overflow is undefined, get modulo-reduced.
303 But only if not all values of the old type fit in the new. */
304 if (! TYPE_UNSIGNED (type
)
305 && ((TYPE_UNSIGNED (itype
)
306 && TYPE_PRECISION (type
) <= TYPE_PRECISION (itype
))
307 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
308 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
309 else if (TYPE_UNSIGNED (type
)
310 && (!TYPE_UNSIGNED (itype
)
311 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
312 res
= wrap (res
, TYPE_PRECISION (type
));
316 case NON_LVALUE_EXPR
:
317 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
325 /* For all wrapping arithmetic wrap the result. */
326 if (TYPE_OVERFLOW_WRAPS (type
))
327 res
= wrap (res
, TYPE_PRECISION (type
));
332 /* Returns a linear expression for tree T evaluated in PBB. */
335 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
337 scop_p scop
= PBB_SCOP (pbb
);
339 t
= scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
341 gcc_assert (!chrec_contains_undetermined (t
));
342 gcc_assert (!automatically_generated_chrec_p (t
));
344 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
347 /* Add conditional statement STMT to pbb. CODE is used as the comparison
348 operator. This allows us to invert the condition or to handle
352 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
354 loop_p loop
= gimple_bb (stmt
)->loop_father
;
355 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
356 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
362 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
366 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
370 cond
= isl_pw_aff_le_set (lhs
, rhs
);
374 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
378 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
382 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
389 cond
= isl_set_coalesce (cond
);
390 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
391 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
394 /* Add conditions to the domain of PBB. */
397 add_conditions_to_domain (poly_bb_p pbb
)
401 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
403 if (GBB_CONDITIONS (gbb
).is_empty ())
406 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
407 switch (gimple_code (stmt
))
411 /* Don't constrain on anything else than INTEGER_TYPE. */
412 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
415 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
416 enum tree_code code
= gimple_cond_code (cond_stmt
);
418 /* The conditions for ELSE-branches are inverted. */
419 if (!GBB_CONDITION_CASES (gbb
)[i
])
420 code
= invert_tree_comparison (code
, false);
422 add_condition_to_pbb (pbb
, cond_stmt
, code
);
432 /* Add constraints on the possible values of parameter P from the type
436 add_param_constraints (scop_p scop
, graphite_dim_t p
, tree parameter
)
438 tree type
= TREE_TYPE (parameter
);
441 gcc_assert (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
));
443 if (INTEGRAL_TYPE_P (type
)
444 && get_range_info (parameter
, &min
, &max
) == VR_RANGE
)
448 min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
449 max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
452 isl_space
*space
= isl_set_get_space (scop
->param_context
);
453 isl_constraint
*c
= isl_inequality_alloc (isl_local_space_from_space (space
));
454 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
,
455 widest_int::from (min
, TYPE_SIGN (type
)));
457 c
= isl_constraint_set_constant_val (c
, v
);
458 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
459 scop
->param_context
= isl_set_coalesce
460 (isl_set_add_constraint (scop
->param_context
, c
));
462 space
= isl_set_get_space (scop
->param_context
);
463 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
464 v
= isl_val_int_from_wi (scop
->isl_context
,
465 widest_int::from (max
, TYPE_SIGN (type
)));
466 c
= isl_constraint_set_constant_val (c
, v
);
467 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
468 scop
->param_context
= isl_set_coalesce
469 (isl_set_add_constraint (scop
->param_context
, c
));
472 /* Add a constrain to the ACCESSES polyhedron for the alias set of
473 data reference DR. ACCESSP_NB_DIMS is the dimension of the
474 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
478 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
480 isl_constraint
*c
= isl_equality_alloc
481 (isl_local_space_from_space (isl_map_get_space (acc
)));
482 /* Positive numbers for all alias sets. */
483 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
484 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
486 return isl_map_add_constraint (acc
, c
);
489 /* Assign the affine expression INDEX to the output dimension POS of
490 MAP and return the result. */
493 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
496 int len
= isl_map_dim (map
, isl_dim_out
);
499 index_map
= isl_map_from_pw_aff (index
);
500 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
501 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
503 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
504 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
505 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
506 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
508 return isl_map_intersect (map
, index_map
);
511 /* Add to ACCESSES polyhedron equalities defining the access functions
512 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
513 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
514 PBB is the poly_bb_p that contains the data reference DR. */
517 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
519 data_reference_p dr
= dri
.dr
;
520 poly_bb_p pbb
= dri
.pbb
;
521 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
522 scop_p scop
= PBB_SCOP (pbb
);
524 for (i
= 0; i
< nb_subscripts
; i
++)
527 tree afn
= DR_ACCESS_FN (dr
, i
);
529 aff
= extract_affine (scop
, afn
,
530 isl_space_domain (isl_map_get_space (acc
)));
531 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
534 return isl_map_coalesce (acc
);
537 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
538 to extract constraints on accessed elements of the array. Returning false is
539 the conservative answer. */
542 bounds_are_valid (tree ref
, tree low
, tree high
)
547 if (!tree_fits_shwi_p (low
)
548 || !tree_fits_shwi_p (high
))
551 /* 1-element arrays at end of structures may extend over
552 their declared size. */
553 if (array_at_struct_end_p (ref
)
554 && operand_equal_p (low
, high
, 0))
557 /* Fortran has some arrays where high bound is -1 and low is 0. */
558 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
564 /* Add constrains representing the size of the accessed data to the
565 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
566 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
570 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
573 tree ref
= DR_REF (dr
);
575 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
576 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
578 if (TREE_CODE (ref
) != ARRAY_REF
)
579 return subscript_sizes
;
581 tree low
= array_ref_low_bound (ref
);
582 tree high
= array_ref_up_bound (ref
);
584 if (!bounds_are_valid (ref
, low
, high
))
587 isl_space
*space
= isl_set_get_space (subscript_sizes
);
588 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
589 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
592 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
593 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
594 isl_set_dim (valid
, isl_dim_set
));
595 scop
->param_context
= isl_set_coalesce
596 (isl_set_intersect (scop
->param_context
, valid
));
599 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
600 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
602 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
603 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
605 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
606 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
607 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
609 /* low <= sub_i <= high */
610 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
611 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
612 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
613 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
616 return isl_set_coalesce (subscript_sizes
);
619 /* Build data accesses for DRI. */
622 build_poly_dr (dr_info
&dri
)
625 isl_set
*subscript_sizes
;
626 poly_bb_p pbb
= dri
.pbb
;
627 data_reference_p dr
= dri
.dr
;
628 scop_p scop
= PBB_SCOP (pbb
);
629 isl_id
*id
= isl_id_for_dr (scop
);
632 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
633 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
634 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
635 isl_dim_out
, nb_out
);
637 acc
= isl_map_universe (space
);
638 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
641 acc
= pdr_add_alias_set (acc
, dri
);
642 acc
= pdr_add_memory_accesses (acc
, dri
);
645 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
646 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
648 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
649 subscript_sizes
= isl_set_nat_universe (space
);
650 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
652 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
655 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
656 acc
, subscript_sizes
);
660 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
661 isl_map
*acc
, isl_set
*subscript_sizes
)
663 scop_p scop
= PBB_SCOP (pbb
);
664 /* Each scalar variables has a unique alias set number starting from
665 the maximum alias set assigned to a dr. */
666 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
667 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
670 /* Add a constrain to the ACCESSES polyhedron for the alias set of
671 data reference DR. */
673 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
674 c
= isl_constraint_set_constant_si (c
, -alias_set
);
675 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
677 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
681 /* Record all cross basic block scalar variables in PBB. */
684 build_poly_sr (poly_bb_p pbb
)
686 scop_p scop
= PBB_SCOP (pbb
);
687 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
688 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
689 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
691 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
693 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
694 isl_dim_out
, nb_out
);
695 isl_id
*id
= isl_id_for_dr (scop
);
696 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
697 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
698 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
699 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
703 FOR_EACH_VEC_ELT (writes
, i
, var
)
704 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
705 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
708 FOR_EACH_VEC_ELT (reads
, i
, use
)
709 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
710 isl_set_copy (subscript_sizes
));
713 isl_set_free (subscript_sizes
);
716 /* Build data references in SCOP. */
719 build_scop_drs (scop_p scop
)
723 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
724 build_poly_dr (*dri
);
727 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
731 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
734 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
736 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
737 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
739 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
740 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
741 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
744 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
747 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
752 const sese_l
®ion
= scop
->scop_info
->region
;
753 if (!loop_in_sese_p (loop
, region
))
756 /* Recursion all the way up to the context loop. */
757 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
759 /* Then, build constraints over the loop in post-order: outer to inner. */
761 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
763 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
764 "domain for loop_%d.\n", loop
->num
);
765 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
766 isl_space
*space
= isl_set_get_space (domain
);
769 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
770 isl_constraint
*c
= isl_inequality_alloc (ls
);
771 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
774 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
775 print_isl_constraint (dump_file
, c
);
777 domain
= isl_set_add_constraint (domain
, c
);
779 tree nb_iters
= number_of_latch_executions (loop
);
780 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
782 /* loop_i <= cst_nb_iters */
783 isl_local_space
*ls
= isl_local_space_from_space (space
);
784 isl_constraint
*c
= isl_inequality_alloc (ls
);
785 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
787 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
788 c
= isl_constraint_set_constant_val (c
, v
);
789 return isl_set_add_constraint (domain
, c
);
791 /* loop_i <= expr_nb_iters */
792 gcc_assert (!chrec_contains_undetermined (nb_iters
));
793 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
794 gcc_assert (!chrec_contains_undetermined (nb_iters
));
796 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
797 isl_space_copy (space
));
798 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
799 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
800 isl_set_dim (valid
, isl_dim_set
));
803 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
805 ls
= isl_local_space_from_space (isl_space_copy (space
));
806 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
807 isl_dim_in
, loop_index
, 1);
808 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
809 isl_pw_aff_copy (aff_nb_iters
));
812 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
813 print_isl_set (dump_file
, le
);
815 domain
= isl_set_intersect (domain
, le
);
818 if (!max_stmt_executions (loop
, &nit
))
820 isl_pw_aff_free (aff_nb_iters
);
821 isl_space_free (space
);
825 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
826 do not know whether the loop executes at least once. */
829 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
830 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
831 x
= isl_set_project_out (x
, isl_dim_set
, 0,
832 isl_set_dim (x
, isl_dim_set
));
833 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
835 ls
= isl_local_space_from_space (space
);
836 c
= isl_inequality_alloc (ls
);
837 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
838 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
839 c
= isl_constraint_set_constant_val (c
, v
);
843 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
844 print_isl_constraint (dump_file
, c
);
847 return isl_set_add_constraint (domain
, c
);
850 /* Builds the original iteration domains for each pbb in the SCOP. */
853 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
854 int index
, loop_p context_loop
)
856 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
857 isl_set
*domain
= isl_set_copy (context
);
858 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
859 const sese_l
®ion
= scop
->scop_info
->region
;
863 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
865 loop_p loop
= pbb_loop (pbb
);
868 pbb
->iterators
= isl_set_copy (domain
);
869 pbb
->domain
= isl_set_copy (domain
);
870 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
871 isl_id_for_pbb (scop
, pbb
));
872 add_conditions_to_domain (pbb
);
876 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
878 print_isl_set (dump_file
, domain
);
883 while (loop_in_sese_p (loop
, region
)
885 loop
= loop_outer (loop
);
889 /* A statement in a different loop nest than CURRENT loop. */
890 isl_set_free (domain
);
894 /* A statement nested in the CURRENT loop. */
895 i
= build_iteration_domains (scop
, domain
, i
, current
);
899 isl_set_free (domain
);
903 /* Assign dimension for each parameter in SCOP and add constraints for the
907 build_scop_context (scop_p scop
)
909 sese_info_p region
= scop
->scop_info
;
910 unsigned nbp
= sese_nb_params (region
);
911 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
915 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
916 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
917 isl_id_for_ssa_name (scop
, e
));
919 scop
->param_context
= isl_set_universe (space
);
921 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
922 add_param_constraints (scop
, i
, e
);
925 /* Return true when loop A is nested in loop B. */
928 nested_in (loop_p a
, loop_p b
)
930 return b
== find_common_loop (a
, b
);
933 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
935 loop_at (scop_p scop
, int *index
)
937 return pbb_loop (scop
->pbbs
[*index
]);
940 /* Return the index of any pbb belonging to loop or a subloop of A. */
943 index_outermost_in_loop (loop_p a
, scop_p scop
)
945 int i
, outermost
= -1;
948 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
949 if (nested_in (pbb_loop (pbb
), a
)
951 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
954 last_depth
= loop_depth (pbb_loop (pbb
));
959 /* Return the index of any pbb belonging to loop or a subloop of A. */
962 index_pbb_in_loop (loop_p a
, scop_p scop
)
966 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
967 if (pbb_loop (pbb
) == a
)
973 outermost_pbb_in (loop_p loop
, scop_p scop
)
975 int x
= index_pbb_in_loop (loop
, scop
);
977 x
= index_outermost_in_loop (loop
, scop
);
978 return scop
->pbbs
[x
];
981 static isl_schedule
*
982 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
992 return isl_schedule_sequence (a
, b
);
995 struct map_to_dimension_data
{
997 isl_union_pw_multi_aff
*res
;
1000 /* Create a function that maps the elements of SET to its N-th dimension and add
1004 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1006 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1007 int dim
= isl_set_dim (set
, isl_dim_set
);
1008 isl_space
*space
= isl_set_get_space (set
);
1010 gcc_assert (dim
>= data
->n
);
1011 isl_pw_multi_aff
*pma
1012 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1014 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1020 /* Return SET in which all inner dimensions above N are removed. */
1022 static isl_multi_union_pw_aff
*
1023 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1025 gcc_assert (n
>= 0);
1027 gcc_assert (!isl_union_set_is_empty (set
));
1029 isl_space
*space
= isl_union_set_get_space (set
);
1030 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1032 struct map_to_dimension_data data
= {n
, pwaff
};
1034 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1035 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1037 isl_union_set_free (set
);
1038 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1041 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1043 static isl_schedule
*
1044 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1047 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1048 isl_set
*iterators
= pbb
->iterators
;
1050 int empty
= isl_set_is_empty (iterators
);
1051 if (empty
< 0 || empty
)
1052 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1054 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1055 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1056 if (isl_union_set_is_empty (domain
))
1058 isl_union_set_free (domain
);
1062 isl_space
*space
= isl_set_get_space (iterators
);
1063 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1065 loop_p ploop
= pbb_loop (pbb
);
1066 while (loop
!= ploop
)
1069 ploop
= loop_outer (ploop
);
1072 isl_local_space
*ls
= isl_local_space_from_space (space
);
1073 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1074 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1076 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1077 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1079 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1081 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1082 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1083 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1084 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1087 /* Build schedule for the pbb at INDEX. */
1089 static isl_schedule
*
1090 build_schedule_pbb (scop_p scop
, int *index
)
1092 poly_bb_p pbb
= scop
->pbbs
[*index
];
1094 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1095 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1096 return isl_schedule_from_domain (ud
);
1099 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1101 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1103 static isl_schedule
*
1104 build_schedule_loop (scop_p scop
, int *index
)
1106 int max
= scop
->pbbs
.length ();
1107 gcc_assert (*index
< max
);
1108 loop_p loop
= loop_at (scop
, index
);
1110 isl_schedule
*s
= NULL
;
1111 while (nested_in (loop_at (scop
, index
), loop
))
1113 if (loop
== loop_at (scop
, index
))
1114 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1116 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1122 return add_loop_schedule (s
, loop
, scop
);
1125 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1126 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1127 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1128 maximal loop nest contained within CONTEXT_LOOP. */
1130 static isl_schedule
*
1131 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1132 loop_p loop
, int *index
, loop_p context_loop
)
1134 loop_p outer
= loop_outer (loop
);
1135 sese_l region
= scop
->scop_info
->region
;
1136 if (context_loop
== outer
1137 || !loop_in_sese_p (outer
, region
))
1140 int max
= scop
->pbbs
.length ();
1142 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1144 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1146 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1147 scop
, outer
, index
, context_loop
);
1150 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1151 || nested_in (loop_at (scop
, index
), outer
))
1154 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1156 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1162 /* We reached the end of the OUTER loop: embed S in OUTER. */
1163 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1164 outer
, index
, context_loop
);
1167 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1168 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1169 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1170 nest contained within CONTEXT_LOOP. */
1172 static isl_schedule
*
1173 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1175 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1177 loop_p loop
= loop_at (scop
, index
);
1178 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1179 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1182 /* Build the schedule of the SCOP. */
1185 build_original_schedule (scop_p scop
)
1188 int n
= scop
->pbbs
.length ();
1191 poly_bb_p pbb
= scop
->pbbs
[i
];
1192 isl_schedule
*s
= NULL
;
1193 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1194 s
= build_schedule_pbb (scop
, &i
);
1196 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1198 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1203 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1204 print_isl_schedule (dump_file
, scop
->original_schedule
);
1208 /* Builds the polyhedral representation for a SESE region. */
1211 build_poly_scop (scop_p scop
)
1213 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1214 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1216 build_scop_context (scop
);
1219 unsigned n
= scop
->pbbs
.length ();
1221 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1223 build_scop_drs (scop
);
1224 build_original_schedule (scop
);
1226 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1227 isl_ctx_reset_error (scop
->isl_context
);
1228 isl_options_set_on_error (scop
->isl_context
, old_err
);
1229 if (err
!= isl_error_none
)
1230 dump_printf (MSG_MISSED_OPTIMIZATION
,
1231 "ISL error while building poly scop\n");
1233 return err
== isl_error_none
;
1235 #endif /* HAVE_isl */