1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2020 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"
50 #include <isl/constraint.h>
53 #include <isl/union_map.h>
54 #include <isl/constraint.h>
60 /* Return an isl identifier for the polyhedral basic block PBB. */
63 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
66 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
67 return isl_id_alloc (s
->isl_context
, name
, pbb
);
70 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
72 /* Extract an affine expression from the chain of recurrence E. */
75 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
77 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
78 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
79 isl_local_space
*ls
= isl_local_space_from_space (space
);
80 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
81 isl_aff
*loop
= isl_aff_set_coefficient_si
82 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
83 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
85 /* Before multiplying, make sure that the result is affine. */
86 gcc_assert (isl_pw_aff_is_cst (rhs
)
87 || isl_pw_aff_is_cst (l
));
89 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
92 /* Extract an affine expression from the mult_expr E. */
95 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
97 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
98 isl_space_copy (space
));
99 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
101 if (!isl_pw_aff_is_cst (lhs
)
102 && !isl_pw_aff_is_cst (rhs
))
104 isl_pw_aff_free (lhs
);
105 isl_pw_aff_free (rhs
);
109 return isl_pw_aff_mul (lhs
, rhs
);
112 /* Return an isl identifier from the name of the ssa_name E. */
115 isl_id_for_ssa_name (scop_p s
, tree e
)
118 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
119 return isl_id_alloc (s
->isl_context
, name1
, e
);
122 /* Return an isl identifier for the data reference DR. Data references and
123 scalar references get the same isl_id. They need to be comparable and are
124 distinguished through the first dimension, which contains the alias set or
125 SSA_NAME_VERSION number. */
128 isl_id_for_dr (scop_p s
)
130 return isl_id_alloc (s
->isl_context
, "", 0);
133 /* Extract an affine expression from the ssa_name E. */
136 extract_affine_name (int dimension
, __isl_take isl_space
*space
)
138 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
139 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
140 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
141 return isl_pw_aff_alloc (dom
, aff
);
144 /* Convert WI to a isl_val with CTX. */
146 static __isl_give isl_val
*
147 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
149 if (wi::neg_p (wi
, SIGNED
))
151 widest_int mwi
= -wi
;
152 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
153 sizeof (HOST_WIDE_INT
),
156 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
160 /* Extract an affine expression from the gmp constant G. */
163 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
165 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
166 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
167 isl_set
*dom
= isl_set_universe (space
);
168 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
169 isl_val
*v
= isl_val_int_from_wi (ct
, g
);
170 aff
= isl_aff_add_constant_val (aff
, v
);
172 return isl_pw_aff_alloc (dom
, aff
);
175 /* Extract an affine expression from the integer_cst E. */
178 extract_affine_int (tree e
, __isl_take isl_space
*space
)
180 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
184 /* Compute pwaff mod 2^width. */
187 wrap (isl_pw_aff
*pwaff
, unsigned width
)
191 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
192 mod
= isl_val_2exp (mod
);
193 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
198 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
199 Otherwise returns -1. */
202 parameter_index_in_region (tree name
, sese_info_p region
)
206 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
212 /* Extract an affine expression from the tree E in the scop S. */
215 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
217 isl_pw_aff
*lhs
, *rhs
, *res
;
219 if (e
== chrec_dont_know
) {
220 isl_space_free (space
);
224 tree type
= TREE_TYPE (e
);
225 switch (TREE_CODE (e
))
227 case POLYNOMIAL_CHREC
:
228 res
= extract_affine_chrec (s
, e
, space
);
232 res
= extract_affine_mul (s
, e
, space
);
235 case POINTER_PLUS_EXPR
:
237 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
238 /* The RHS of a pointer-plus expression is to be interpreted
239 as signed value. Try to look through a sign-changing conversion
241 tree tem
= TREE_OPERAND (e
, 1);
243 rhs
= extract_affine (s
, tem
, space
);
244 if (TYPE_UNSIGNED (TREE_TYPE (tem
)))
245 rhs
= wrap (rhs
, TYPE_PRECISION (type
) - 1);
246 res
= isl_pw_aff_add (lhs
, rhs
);
251 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
252 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
253 res
= isl_pw_aff_add (lhs
, rhs
);
257 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
258 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
259 res
= isl_pw_aff_sub (lhs
, rhs
);
263 lhs
= extract_affine (s
, integer_minus_one_node
, isl_space_copy (space
));
264 rhs
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
265 res
= isl_pw_aff_sub (lhs
, rhs
);
266 /* We need to always wrap the result of a bitwise operation. */
267 return wrap (res
, TYPE_PRECISION (type
) - (TYPE_UNSIGNED (type
) ? 0 : 1));
270 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
271 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
272 res
= isl_pw_aff_mul (lhs
, rhs
);
277 gcc_assert (! defined_in_sese_p (e
, s
->scop_info
->region
));
278 int dim
= parameter_index_in_region (e
, s
->scop_info
);
279 gcc_assert (dim
!= -1);
280 /* No need to wrap a parameter. */
281 return extract_affine_name (dim
, space
);
285 res
= extract_affine_int (e
, space
);
286 /* No need to wrap a single integer. */
291 tree itype
= TREE_TYPE (TREE_OPERAND (e
, 0));
292 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
293 /* Signed values, even if overflow is undefined, get modulo-reduced.
294 But only if not all values of the old type fit in the new. */
295 if (! TYPE_UNSIGNED (type
)
296 && ((TYPE_UNSIGNED (itype
)
297 && TYPE_PRECISION (type
) <= TYPE_PRECISION (itype
))
298 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
299 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
300 else if (TYPE_UNSIGNED (type
)
301 && (!TYPE_UNSIGNED (itype
)
302 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
303 res
= wrap (res
, TYPE_PRECISION (type
));
307 case NON_LVALUE_EXPR
:
308 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
316 /* For all wrapping arithmetic wrap the result. */
317 if (TYPE_OVERFLOW_WRAPS (type
))
318 res
= wrap (res
, TYPE_PRECISION (type
));
323 /* Returns a linear expression for tree T evaluated in PBB. */
326 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
328 scop_p scop
= PBB_SCOP (pbb
);
330 t
= cached_scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
332 gcc_assert (!chrec_contains_undetermined (t
));
333 gcc_assert (!automatically_generated_chrec_p (t
));
335 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
338 /* Add conditional statement STMT to pbb. CODE is used as the comparison
339 operator. This allows us to invert the condition or to handle
343 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
345 loop_p loop
= gimple_bb (stmt
)->loop_father
;
346 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
347 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
353 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
357 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
361 cond
= isl_pw_aff_le_set (lhs
, rhs
);
365 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
369 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
373 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
380 cond
= isl_set_coalesce (cond
);
381 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
382 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
385 /* Add conditions to the domain of PBB. */
388 add_conditions_to_domain (poly_bb_p pbb
)
392 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
394 if (GBB_CONDITIONS (gbb
).is_empty ())
397 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
398 switch (gimple_code (stmt
))
402 /* Don't constrain on anything else than INTEGER_TYPE. */
403 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
406 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
407 enum tree_code code
= gimple_cond_code (cond_stmt
);
409 /* The conditions for ELSE-branches are inverted. */
410 if (!GBB_CONDITION_CASES (gbb
)[i
])
411 code
= invert_tree_comparison (code
, false);
413 add_condition_to_pbb (pbb
, cond_stmt
, code
);
423 /* Add constraints on the possible values of parameter P from the type
427 add_param_constraints (scop_p scop
, graphite_dim_t p
, tree parameter
)
429 tree type
= TREE_TYPE (parameter
);
432 gcc_assert (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
));
434 if (INTEGRAL_TYPE_P (type
)
435 && get_range_info (parameter
, &min
, &max
) == VR_RANGE
)
439 min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
440 max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
443 isl_space
*space
= isl_set_get_space (scop
->param_context
);
444 isl_constraint
*c
= isl_inequality_alloc (isl_local_space_from_space (space
));
445 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
,
446 widest_int::from (min
, TYPE_SIGN (type
)));
448 c
= isl_constraint_set_constant_val (c
, v
);
449 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
450 scop
->param_context
= isl_set_coalesce
451 (isl_set_add_constraint (scop
->param_context
, c
));
453 space
= isl_set_get_space (scop
->param_context
);
454 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
455 v
= isl_val_int_from_wi (scop
->isl_context
,
456 widest_int::from (max
, 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
));
463 /* Add a constrain to the ACCESSES polyhedron for the alias set of
464 data reference DR. ACCESSP_NB_DIMS is the dimension of the
465 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
469 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
471 isl_constraint
*c
= isl_equality_alloc
472 (isl_local_space_from_space (isl_map_get_space (acc
)));
473 /* Positive numbers for all alias sets. */
474 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
475 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
477 return isl_map_add_constraint (acc
, c
);
480 /* Assign the affine expression INDEX to the output dimension POS of
481 MAP and return the result. */
484 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
487 int len
= isl_map_dim (map
, isl_dim_out
);
490 index_map
= isl_map_from_pw_aff (index
);
491 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
492 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
494 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
495 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
496 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
497 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
499 return isl_map_intersect (map
, index_map
);
502 /* Add to ACCESSES polyhedron equalities defining the access functions
503 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
504 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
505 PBB is the poly_bb_p that contains the data reference DR. */
508 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
510 data_reference_p dr
= dri
.dr
;
511 poly_bb_p pbb
= dri
.pbb
;
512 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
513 scop_p scop
= PBB_SCOP (pbb
);
515 for (i
= 0; i
< nb_subscripts
; i
++)
518 tree afn
= DR_ACCESS_FN (dr
, i
);
520 aff
= extract_affine (scop
, afn
,
521 isl_space_domain (isl_map_get_space (acc
)));
522 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
525 return isl_map_coalesce (acc
);
528 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
529 to extract constraints on accessed elements of the array. Returning false is
530 the conservative answer. */
533 bounds_are_valid (tree ref
, tree low
, tree high
)
538 if (!tree_fits_shwi_p (low
)
539 || !tree_fits_shwi_p (high
))
542 /* 1-element arrays at end of structures may extend over
543 their declared size. */
544 if (array_at_struct_end_p (ref
)
545 && operand_equal_p (low
, high
, 0))
548 /* Fortran has some arrays where high bound is -1 and low is 0. */
549 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
555 /* Add constrains representing the size of the accessed data to the
556 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
557 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
561 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
564 tree ref
= DR_REF (dr
);
566 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
567 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
569 if (TREE_CODE (ref
) != ARRAY_REF
)
570 return subscript_sizes
;
572 tree low
= array_ref_low_bound (ref
);
573 tree high
= array_ref_up_bound (ref
);
575 if (!bounds_are_valid (ref
, low
, high
))
578 isl_space
*space
= isl_set_get_space (subscript_sizes
);
579 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
580 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
583 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
584 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
585 isl_set_dim (valid
, isl_dim_set
));
586 scop
->param_context
= isl_set_coalesce
587 (isl_set_intersect (scop
->param_context
, valid
));
590 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
591 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
593 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
594 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
596 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
597 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
598 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
600 /* low <= sub_i <= high */
601 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
602 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
603 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
604 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
607 return isl_set_coalesce (subscript_sizes
);
610 /* Build data accesses for DRI. */
613 build_poly_dr (dr_info
&dri
)
616 isl_set
*subscript_sizes
;
617 poly_bb_p pbb
= dri
.pbb
;
618 data_reference_p dr
= dri
.dr
;
619 scop_p scop
= PBB_SCOP (pbb
);
620 isl_id
*id
= isl_id_for_dr (scop
);
623 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
624 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
625 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
626 isl_dim_out
, nb_out
);
628 acc
= isl_map_universe (space
);
629 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
632 acc
= pdr_add_alias_set (acc
, dri
);
633 acc
= pdr_add_memory_accesses (acc
, dri
);
636 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
637 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
639 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
640 subscript_sizes
= isl_set_nat_universe (space
);
641 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
643 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
646 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
647 acc
, subscript_sizes
);
651 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
652 isl_map
*acc
, isl_set
*subscript_sizes
)
654 scop_p scop
= PBB_SCOP (pbb
);
655 /* Each scalar variables has a unique alias set number starting from
656 the maximum alias set assigned to a dr. */
657 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
658 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
661 /* Add a constrain to the ACCESSES polyhedron for the alias set of
662 data reference DR. */
664 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
665 c
= isl_constraint_set_constant_si (c
, -alias_set
);
666 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
668 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
672 /* Record all cross basic block scalar variables in PBB. */
675 build_poly_sr (poly_bb_p pbb
)
677 scop_p scop
= PBB_SCOP (pbb
);
678 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
679 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
680 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
682 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
684 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
685 isl_dim_out
, nb_out
);
686 isl_id
*id
= isl_id_for_dr (scop
);
687 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
688 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
689 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
690 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
694 FOR_EACH_VEC_ELT (writes
, i
, var
)
695 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
696 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
699 FOR_EACH_VEC_ELT (reads
, i
, use
)
700 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
701 isl_set_copy (subscript_sizes
));
704 isl_set_free (subscript_sizes
);
707 /* Build data references in SCOP. */
710 build_scop_drs (scop_p scop
)
714 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
715 build_poly_dr (*dri
);
718 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
722 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
725 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
727 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
728 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
730 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
731 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
732 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
735 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
738 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
743 const sese_l
®ion
= scop
->scop_info
->region
;
744 if (!loop_in_sese_p (loop
, region
))
747 /* Recursion all the way up to the context loop. */
748 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
750 /* Then, build constraints over the loop in post-order: outer to inner. */
752 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
754 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
755 "domain for loop_%d.\n", loop
->num
);
756 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
757 isl_space
*space
= isl_set_get_space (domain
);
760 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
761 isl_constraint
*c
= isl_inequality_alloc (ls
);
762 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
765 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
766 print_isl_constraint (dump_file
, c
);
768 domain
= isl_set_add_constraint (domain
, c
);
770 tree nb_iters
= number_of_latch_executions (loop
);
771 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
773 /* loop_i <= cst_nb_iters */
774 isl_local_space
*ls
= isl_local_space_from_space (space
);
775 isl_constraint
*c
= isl_inequality_alloc (ls
);
776 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
778 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
779 c
= isl_constraint_set_constant_val (c
, v
);
780 return isl_set_add_constraint (domain
, c
);
782 /* loop_i <= expr_nb_iters */
783 gcc_assert (!chrec_contains_undetermined (nb_iters
));
784 nb_iters
= cached_scalar_evolution_in_region (region
, loop
, nb_iters
);
785 gcc_assert (!chrec_contains_undetermined (nb_iters
));
787 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
788 isl_space_copy (space
));
789 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
790 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
791 isl_set_dim (valid
, isl_dim_set
));
794 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
796 ls
= isl_local_space_from_space (isl_space_copy (space
));
797 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
798 isl_dim_in
, loop_index
, 1);
799 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
800 isl_pw_aff_copy (aff_nb_iters
));
803 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
804 print_isl_set (dump_file
, le
);
806 domain
= isl_set_intersect (domain
, le
);
809 if (!max_stmt_executions (loop
, &nit
))
811 isl_pw_aff_free (aff_nb_iters
);
812 isl_space_free (space
);
816 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
817 do not know whether the loop executes at least once. */
820 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
821 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
822 x
= isl_set_project_out (x
, isl_dim_set
, 0,
823 isl_set_dim (x
, isl_dim_set
));
824 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
826 ls
= isl_local_space_from_space (space
);
827 c
= isl_inequality_alloc (ls
);
828 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
829 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
830 c
= isl_constraint_set_constant_val (c
, v
);
834 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
835 print_isl_constraint (dump_file
, c
);
838 return isl_set_add_constraint (domain
, c
);
841 /* Builds the original iteration domains for each pbb in the SCOP. */
844 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
845 int index
, loop_p context_loop
)
847 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
848 isl_set
*domain
= isl_set_copy (context
);
849 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
850 const sese_l
®ion
= scop
->scop_info
->region
;
854 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
856 loop_p loop
= pbb_loop (pbb
);
859 pbb
->iterators
= isl_set_copy (domain
);
860 pbb
->domain
= isl_set_copy (domain
);
861 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
862 isl_id_for_pbb (scop
, pbb
));
863 add_conditions_to_domain (pbb
);
867 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
869 print_isl_set (dump_file
, domain
);
874 while (loop_in_sese_p (loop
, region
)
876 loop
= loop_outer (loop
);
880 /* A statement in a different loop nest than CURRENT loop. */
881 isl_set_free (domain
);
885 /* A statement nested in the CURRENT loop. */
886 i
= build_iteration_domains (scop
, domain
, i
, current
);
890 isl_set_free (domain
);
894 /* Assign dimension for each parameter in SCOP and add constraints for the
898 build_scop_context (scop_p scop
)
900 sese_info_p region
= scop
->scop_info
;
901 unsigned nbp
= sese_nb_params (region
);
902 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
906 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
907 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
908 isl_id_for_ssa_name (scop
, e
));
910 scop
->param_context
= isl_set_universe (space
);
912 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
913 add_param_constraints (scop
, i
, e
);
916 /* Return true when loop A is nested in loop B. */
919 nested_in (loop_p a
, loop_p b
)
921 return b
== find_common_loop (a
, b
);
924 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
926 loop_at (scop_p scop
, int *index
)
928 return pbb_loop (scop
->pbbs
[*index
]);
931 /* Return the index of any pbb belonging to loop or a subloop of A. */
934 index_outermost_in_loop (loop_p a
, scop_p scop
)
936 int i
, outermost
= -1;
939 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
940 if (nested_in (pbb_loop (pbb
), a
)
942 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
945 last_depth
= loop_depth (pbb_loop (pbb
));
950 /* Return the index of any pbb belonging to loop or a subloop of A. */
953 index_pbb_in_loop (loop_p a
, scop_p scop
)
957 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
958 if (pbb_loop (pbb
) == a
)
964 outermost_pbb_in (loop_p loop
, scop_p scop
)
966 int x
= index_pbb_in_loop (loop
, scop
);
968 x
= index_outermost_in_loop (loop
, scop
);
969 return scop
->pbbs
[x
];
972 static isl_schedule
*
973 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
983 return isl_schedule_sequence (a
, b
);
986 struct map_to_dimension_data
{
988 isl_union_pw_multi_aff
*res
;
991 /* Create a function that maps the elements of SET to its N-th dimension and add
995 add_outer_projection (__isl_take isl_set
*set
, void *user
)
997 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
998 int dim
= isl_set_dim (set
, isl_dim_set
);
999 isl_space
*space
= isl_set_get_space (set
);
1001 gcc_assert (dim
>= data
->n
);
1002 isl_pw_multi_aff
*pma
1003 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1005 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1011 /* Return SET in which all inner dimensions above N are removed. */
1013 static isl_multi_union_pw_aff
*
1014 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1016 gcc_assert (n
>= 0);
1018 gcc_assert (!isl_union_set_is_empty (set
));
1020 isl_space
*space
= isl_union_set_get_space (set
);
1021 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1023 struct map_to_dimension_data data
= {n
, pwaff
};
1025 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1026 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1028 isl_union_set_free (set
);
1029 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1032 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1034 static isl_schedule
*
1035 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1038 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1039 isl_set
*iterators
= pbb
->iterators
;
1041 int empty
= isl_set_is_empty (iterators
);
1042 if (empty
< 0 || empty
)
1043 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1045 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1046 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1047 if (isl_union_set_is_empty (domain
))
1049 isl_union_set_free (domain
);
1053 isl_space
*space
= isl_set_get_space (iterators
);
1054 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1056 loop_p ploop
= pbb_loop (pbb
);
1057 while (loop
!= ploop
)
1060 ploop
= loop_outer (ploop
);
1063 isl_local_space
*ls
= isl_local_space_from_space (space
);
1064 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1065 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1067 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1068 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1070 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1072 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1073 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1074 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1075 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1078 /* Build schedule for the pbb at INDEX. */
1080 static isl_schedule
*
1081 build_schedule_pbb (scop_p scop
, int *index
)
1083 poly_bb_p pbb
= scop
->pbbs
[*index
];
1085 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1086 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1087 return isl_schedule_from_domain (ud
);
1090 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1092 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1094 static isl_schedule
*
1095 build_schedule_loop (scop_p scop
, int *index
)
1097 int max
= scop
->pbbs
.length ();
1098 gcc_assert (*index
< max
);
1099 loop_p loop
= loop_at (scop
, index
);
1101 isl_schedule
*s
= NULL
;
1102 while (nested_in (loop_at (scop
, index
), loop
))
1104 if (loop
== loop_at (scop
, index
))
1105 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1107 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1113 return add_loop_schedule (s
, loop
, scop
);
1116 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1117 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1118 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1119 maximal loop nest contained within CONTEXT_LOOP. */
1121 static isl_schedule
*
1122 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1123 loop_p loop
, int *index
, loop_p context_loop
)
1125 loop_p outer
= loop_outer (loop
);
1126 sese_l region
= scop
->scop_info
->region
;
1127 if (context_loop
== outer
1128 || !loop_in_sese_p (outer
, region
))
1131 int max
= scop
->pbbs
.length ();
1133 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1135 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1137 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1138 scop
, outer
, index
, context_loop
);
1141 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1142 || nested_in (loop_at (scop
, index
), outer
))
1145 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1147 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1153 /* We reached the end of the OUTER loop: embed S in OUTER. */
1154 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1155 outer
, index
, context_loop
);
1158 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1159 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1160 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1161 nest contained within CONTEXT_LOOP. */
1163 static isl_schedule
*
1164 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1166 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1168 loop_p loop
= loop_at (scop
, index
);
1169 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1170 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1173 /* Build the schedule of the SCOP. */
1176 build_original_schedule (scop_p scop
)
1179 int n
= scop
->pbbs
.length ();
1182 poly_bb_p pbb
= scop
->pbbs
[i
];
1183 isl_schedule
*s
= NULL
;
1184 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1185 s
= build_schedule_pbb (scop
, &i
);
1187 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1189 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1194 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1195 print_isl_schedule (dump_file
, scop
->original_schedule
);
1199 /* Builds the polyhedral representation for a SESE region. */
1202 build_poly_scop (scop_p scop
)
1204 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1205 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1207 build_scop_context (scop
);
1210 unsigned n
= scop
->pbbs
.length ();
1212 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1214 build_scop_drs (scop
);
1215 build_original_schedule (scop
);
1217 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1218 isl_ctx_reset_error (scop
->isl_context
);
1219 isl_options_set_on_error (scop
->isl_context
, old_err
);
1220 if (err
!= isl_error_none
1221 && dump_enabled_p ())
1222 dump_printf (MSG_MISSED_OPTIMIZATION
,
1223 "ISL error while building poly scop\n");
1225 return err
== isl_error_none
;
1227 #endif /* HAVE_isl */