1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
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 (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 (scop_p s
, tree e
, __isl_take isl_space
*space
)
147 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
148 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
150 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
151 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
152 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
153 return isl_pw_aff_alloc (dom
, aff
);
156 /* Convert WI to a isl_val with CTX. */
158 static __isl_give isl_val
*
159 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
161 if (wi::neg_p (wi
, SIGNED
))
163 widest_int mwi
= -wi
;
164 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
165 sizeof (HOST_WIDE_INT
),
168 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
172 /* Extract an affine expression from the gmp constant G. */
175 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
177 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
178 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
179 isl_set
*dom
= isl_set_universe (space
);
180 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
181 isl_val
*v
= isl_val_int_from_wi (ct
, g
);
182 aff
= isl_aff_add_constant_val (aff
, v
);
184 return isl_pw_aff_alloc (dom
, aff
);
187 /* Extract an affine expression from the integer_cst E. */
190 extract_affine_int (tree e
, __isl_take isl_space
*space
)
192 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
196 /* Compute pwaff mod 2^width. */
199 wrap (isl_pw_aff
*pwaff
, unsigned width
)
203 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
204 mod
= isl_val_2exp (mod
);
205 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
210 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
211 Otherwise returns -1. */
214 parameter_index_in_region_1 (tree name
, sese_info_p region
)
219 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
221 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
228 /* Extract an affine expression from the tree E in the scop S. */
231 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
233 isl_pw_aff
*lhs
, *rhs
, *res
;
235 if (e
== chrec_dont_know
) {
236 isl_space_free (space
);
240 tree type
= TREE_TYPE (e
);
241 switch (TREE_CODE (e
))
243 case POLYNOMIAL_CHREC
:
244 res
= extract_affine_chrec (s
, e
, space
);
248 res
= extract_affine_mul (s
, e
, space
);
251 case POINTER_PLUS_EXPR
:
253 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
254 /* The RHS of a pointer-plus expression is to be interpreted
255 as signed value. Try to look through a sign-changing conversion
257 tree tem
= TREE_OPERAND (e
, 1);
259 rhs
= extract_affine (s
, tem
, space
);
260 if (TYPE_UNSIGNED (TREE_TYPE (tem
)))
261 rhs
= wrap (rhs
, TYPE_PRECISION (type
) - 1);
262 res
= isl_pw_aff_add (lhs
, rhs
);
267 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
268 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
269 res
= isl_pw_aff_add (lhs
, rhs
);
273 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
274 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
275 res
= isl_pw_aff_sub (lhs
, rhs
);
279 lhs
= extract_affine (s
, integer_minus_one_node
, isl_space_copy (space
));
280 rhs
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
281 res
= isl_pw_aff_sub (lhs
, rhs
);
285 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
286 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
287 res
= isl_pw_aff_mul (lhs
, rhs
);
291 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
292 || defined_in_sese_p (e
, s
->scop_info
->region
));
293 res
= extract_affine_name (s
, e
, space
);
297 res
= extract_affine_int (e
, space
);
298 /* No need to wrap a single integer. */
302 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
303 /* signed values, even if overflow is undefined, get modulo-reduced. */
304 if (! TYPE_UNSIGNED (type
))
305 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
308 case NON_LVALUE_EXPR
:
309 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
317 if (TYPE_UNSIGNED (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
= 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
)
429 tree parameter
= scop
->scop_info
->params
[p
];
430 tree type
= TREE_TYPE (parameter
);
434 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
435 lb
= lower_bound_in_type (type
, type
);
437 lb
= TYPE_MIN_VALUE (type
);
439 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
440 ub
= upper_bound_in_type (type
, type
);
442 ub
= TYPE_MAX_VALUE (type
);
446 isl_space
*space
= isl_set_get_space (scop
->param_context
);
450 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
451 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (lb
));
453 c
= isl_constraint_set_constant_val (c
, v
);
454 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
456 scop
->param_context
= isl_set_coalesce
457 (isl_set_add_constraint (scop
->param_context
, c
));
462 isl_space
*space
= isl_set_get_space (scop
->param_context
);
466 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
468 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (ub
));
469 c
= isl_constraint_set_constant_val (c
, v
);
470 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
472 scop
->param_context
= isl_set_coalesce
473 (isl_set_add_constraint (scop
->param_context
, c
));
477 /* Add a constrain to the ACCESSES polyhedron for the alias set of
478 data reference DR. ACCESSP_NB_DIMS is the dimension of the
479 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
483 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
485 isl_constraint
*c
= isl_equality_alloc
486 (isl_local_space_from_space (isl_map_get_space (acc
)));
487 /* Positive numbers for all alias sets. */
488 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
489 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
491 return isl_map_add_constraint (acc
, c
);
494 /* Add a constrain to the ACCESSES polyhedron for the alias set of
495 data reference DR. ACCESSP_NB_DIMS is the dimension of the
496 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
500 add_scalar_version_numbers (isl_map
*acc
, tree var
)
502 isl_constraint
*c
= isl_equality_alloc
503 (isl_local_space_from_space (isl_map_get_space (acc
)));
504 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
505 /* Each scalar variables has a unique alias set number starting from
507 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
508 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
510 return isl_map_add_constraint (acc
, c
);
513 /* Assign the affine expression INDEX to the output dimension POS of
514 MAP and return the result. */
517 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
520 int len
= isl_map_dim (map
, isl_dim_out
);
523 index_map
= isl_map_from_pw_aff (index
);
524 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
525 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
527 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
528 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
529 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
530 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
532 return isl_map_intersect (map
, index_map
);
535 /* Add to ACCESSES polyhedron equalities defining the access functions
536 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
537 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
538 PBB is the poly_bb_p that contains the data reference DR. */
541 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
543 data_reference_p dr
= dri
.dr
;
544 poly_bb_p pbb
= dri
.pbb
;
545 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
546 scop_p scop
= PBB_SCOP (pbb
);
548 for (i
= 0; i
< nb_subscripts
; i
++)
551 tree afn
= DR_ACCESS_FN (dr
, i
);
553 aff
= extract_affine (scop
, afn
,
554 isl_space_domain (isl_map_get_space (acc
)));
555 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
558 return isl_map_coalesce (acc
);
561 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
562 to extract constraints on accessed elements of the array. Returning false is
563 the conservative answer. */
566 bounds_are_valid (tree ref
, tree low
, tree high
)
571 if (!tree_fits_shwi_p (low
)
572 || !tree_fits_shwi_p (high
))
575 /* 1-element arrays at end of structures may extend over
576 their declared size. */
577 if (array_at_struct_end_p (ref
)
578 && operand_equal_p (low
, high
, 0))
581 /* Fortran has some arrays where high bound is -1 and low is 0. */
582 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
588 /* Add constrains representing the size of the accessed data to the
589 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
590 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
594 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
597 tree ref
= DR_REF (dr
);
599 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
600 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
602 if (TREE_CODE (ref
) != ARRAY_REF
)
603 return subscript_sizes
;
605 tree low
= array_ref_low_bound (ref
);
606 tree high
= array_ref_up_bound (ref
);
608 if (!bounds_are_valid (ref
, low
, high
))
611 isl_space
*space
= isl_set_get_space (subscript_sizes
);
612 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
613 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
616 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
617 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
618 isl_set_dim (valid
, isl_dim_set
));
619 scop
->param_context
= isl_set_coalesce
620 (isl_set_intersect (scop
->param_context
, valid
));
623 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
624 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
626 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
627 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
629 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
630 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
631 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
633 /* low <= sub_i <= high */
634 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
635 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
636 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
637 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
640 return isl_set_coalesce (subscript_sizes
);
643 /* Build data accesses for DRI. */
646 build_poly_dr (dr_info
&dri
)
649 isl_set
*subscript_sizes
;
650 poly_bb_p pbb
= dri
.pbb
;
651 data_reference_p dr
= dri
.dr
;
652 scop_p scop
= PBB_SCOP (pbb
);
653 isl_id
*id
= isl_id_for_dr (scop
);
656 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
657 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
658 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
659 isl_dim_out
, nb_out
);
661 acc
= isl_map_universe (space
);
662 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
665 acc
= pdr_add_alias_set (acc
, dri
);
666 acc
= pdr_add_memory_accesses (acc
, dri
);
669 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
670 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
672 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
673 subscript_sizes
= isl_set_nat_universe (space
);
674 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
676 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
679 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
680 acc
, subscript_sizes
);
684 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
685 isl_map
*acc
, isl_set
*subscript_sizes
)
687 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
688 /* Each scalar variables has a unique alias set number starting from
690 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
691 max_arrays
+ SSA_NAME_VERSION (var
));
693 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
697 /* Record all cross basic block scalar variables in PBB. */
700 build_poly_sr (poly_bb_p pbb
)
702 scop_p scop
= PBB_SCOP (pbb
);
703 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
704 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
705 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
707 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
709 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
710 isl_dim_out
, nb_out
);
711 isl_id
*id
= isl_id_for_dr (scop
);
712 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
713 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
714 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
715 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
719 FOR_EACH_VEC_ELT (writes
, i
, var
)
720 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
721 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
724 FOR_EACH_VEC_ELT (reads
, i
, use
)
725 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
726 isl_set_copy (subscript_sizes
));
729 isl_set_free (subscript_sizes
);
732 /* Build data references in SCOP. */
735 build_scop_drs (scop_p scop
)
739 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
740 build_poly_dr (*dri
);
743 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
747 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
750 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
752 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
753 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
755 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
756 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
757 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
760 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
763 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
768 const sese_l
®ion
= scop
->scop_info
->region
;
769 if (!loop_in_sese_p (loop
, region
))
772 /* Recursion all the way up to the context loop. */
773 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
775 /* Then, build constraints over the loop in post-order: outer to inner. */
777 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
779 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
780 "domain for loop_%d.\n", loop
->num
);
781 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
782 isl_space
*space
= isl_set_get_space (domain
);
785 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
786 isl_constraint
*c
= isl_inequality_alloc (ls
);
787 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
790 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
791 print_isl_constraint (dump_file
, c
);
793 domain
= isl_set_add_constraint (domain
, c
);
795 tree nb_iters
= number_of_latch_executions (loop
);
796 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
798 /* loop_i <= cst_nb_iters */
799 isl_local_space
*ls
= isl_local_space_from_space (space
);
800 isl_constraint
*c
= isl_inequality_alloc (ls
);
801 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
803 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
804 c
= isl_constraint_set_constant_val (c
, v
);
805 return isl_set_add_constraint (domain
, c
);
807 /* loop_i <= expr_nb_iters */
808 gcc_assert (!chrec_contains_undetermined (nb_iters
));
809 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
810 gcc_assert (!chrec_contains_undetermined (nb_iters
));
812 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
813 isl_space_copy (space
));
814 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
815 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
816 isl_set_dim (valid
, isl_dim_set
));
819 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
821 ls
= isl_local_space_from_space (isl_space_copy (space
));
822 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
823 isl_dim_in
, loop_index
, 1);
824 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
825 isl_pw_aff_copy (aff_nb_iters
));
828 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
829 print_isl_set (dump_file
, le
);
831 domain
= isl_set_intersect (domain
, le
);
834 if (!max_stmt_executions (loop
, &nit
))
836 isl_pw_aff_free (aff_nb_iters
);
837 isl_space_free (space
);
841 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
842 do not know whether the loop executes at least once. */
845 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
846 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
847 x
= isl_set_project_out (x
, isl_dim_set
, 0,
848 isl_set_dim (x
, isl_dim_set
));
849 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
851 ls
= isl_local_space_from_space (space
);
852 c
= isl_inequality_alloc (ls
);
853 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
854 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
855 c
= isl_constraint_set_constant_val (c
, v
);
859 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
860 print_isl_constraint (dump_file
, c
);
863 return isl_set_add_constraint (domain
, c
);
866 /* Builds the original iteration domains for each pbb in the SCOP. */
869 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
870 int index
, loop_p context_loop
)
872 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
873 isl_set
*domain
= isl_set_copy (context
);
874 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
875 const sese_l
®ion
= scop
->scop_info
->region
;
879 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
881 loop_p loop
= pbb_loop (pbb
);
884 pbb
->iterators
= isl_set_copy (domain
);
885 pbb
->domain
= isl_set_copy (domain
);
886 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
887 isl_id_for_pbb (scop
, pbb
));
888 add_conditions_to_domain (pbb
);
892 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
894 print_isl_set (dump_file
, domain
);
899 while (loop_in_sese_p (loop
, region
)
901 loop
= loop_outer (loop
);
905 /* A statement in a different loop nest than CURRENT loop. */
906 isl_set_free (domain
);
910 /* A statement nested in the CURRENT loop. */
911 i
= build_iteration_domains (scop
, domain
, i
, current
);
915 isl_set_free (domain
);
919 /* Assign dimension for each parameter in SCOP and add constraints for the
923 build_scop_context (scop_p scop
)
925 sese_info_p region
= scop
->scop_info
;
926 unsigned nbp
= sese_nb_params (region
);
927 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
931 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
932 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
933 isl_id_for_ssa_name (scop
, e
));
935 scop
->param_context
= isl_set_universe (space
);
938 for (p
= 0; p
< nbp
; p
++)
939 add_param_constraints (scop
, p
);
942 /* Return true when loop A is nested in loop B. */
945 nested_in (loop_p a
, loop_p b
)
947 return b
== find_common_loop (a
, b
);
950 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
952 loop_at (scop_p scop
, int *index
)
954 return pbb_loop (scop
->pbbs
[*index
]);
957 /* Return the index of any pbb belonging to loop or a subloop of A. */
960 index_outermost_in_loop (loop_p a
, scop_p scop
)
962 int i
, outermost
= -1;
965 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
966 if (nested_in (pbb_loop (pbb
), a
)
968 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
971 last_depth
= loop_depth (pbb_loop (pbb
));
976 /* Return the index of any pbb belonging to loop or a subloop of A. */
979 index_pbb_in_loop (loop_p a
, scop_p scop
)
983 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
984 if (pbb_loop (pbb
) == a
)
990 outermost_pbb_in (loop_p loop
, scop_p scop
)
992 int x
= index_pbb_in_loop (loop
, scop
);
994 x
= index_outermost_in_loop (loop
, scop
);
995 return scop
->pbbs
[x
];
998 static isl_schedule
*
999 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
1001 gcc_assert (a
|| b
);
1009 return isl_schedule_sequence (a
, b
);
1012 struct map_to_dimension_data
{
1014 isl_union_pw_multi_aff
*res
;
1017 /* Create a function that maps the elements of SET to its N-th dimension and add
1021 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1023 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1024 int dim
= isl_set_dim (set
, isl_dim_set
);
1025 isl_space
*space
= isl_set_get_space (set
);
1027 gcc_assert (dim
>= data
->n
);
1028 isl_pw_multi_aff
*pma
1029 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1031 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1037 /* Return SET in which all inner dimensions above N are removed. */
1039 static isl_multi_union_pw_aff
*
1040 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1042 gcc_assert (n
>= 0);
1044 gcc_assert (!isl_union_set_is_empty (set
));
1046 isl_space
*space
= isl_union_set_get_space (set
);
1047 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1049 struct map_to_dimension_data data
= {n
, pwaff
};
1051 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1052 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1054 isl_union_set_free (set
);
1055 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1058 static bool schedule_error
;
1060 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1062 static isl_schedule
*
1063 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1066 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1067 isl_set
*iterators
= pbb
->iterators
;
1069 int empty
= isl_set_is_empty (iterators
);
1070 if (empty
< 0 || empty
)
1071 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1073 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1074 /* We cannot apply an empty domain to pbbs in this loop so fail.
1075 ??? Somehow drop pbbs in the loop instead. */
1076 if (isl_union_set_is_empty (domain
))
1078 schedule_error
= true;
1079 isl_union_set_free (domain
);
1083 isl_space
*space
= isl_set_get_space (iterators
);
1084 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1086 loop_p ploop
= pbb_loop (pbb
);
1087 while (loop
!= ploop
)
1090 ploop
= loop_outer (ploop
);
1093 isl_local_space
*ls
= isl_local_space_from_space (space
);
1094 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1095 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1097 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1098 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1100 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1102 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1103 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1104 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1105 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1108 /* Build schedule for the pbb at INDEX. */
1110 static isl_schedule
*
1111 build_schedule_pbb (scop_p scop
, int *index
)
1113 poly_bb_p pbb
= scop
->pbbs
[*index
];
1115 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1116 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1117 return isl_schedule_from_domain (ud
);
1120 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1122 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1124 static isl_schedule
*
1125 build_schedule_loop (scop_p scop
, int *index
)
1127 int max
= scop
->pbbs
.length ();
1128 gcc_assert (*index
< max
);
1129 loop_p loop
= loop_at (scop
, index
);
1131 isl_schedule
*s
= NULL
;
1132 while (nested_in (loop_at (scop
, index
), loop
))
1134 if (loop
== loop_at (scop
, index
))
1135 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1137 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1143 return add_loop_schedule (s
, loop
, scop
);
1146 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1147 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1148 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1149 maximal loop nest contained within CONTEXT_LOOP. */
1151 static isl_schedule
*
1152 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1153 loop_p loop
, int *index
, loop_p context_loop
)
1155 loop_p outer
= loop_outer (loop
);
1156 sese_l region
= scop
->scop_info
->region
;
1157 if (context_loop
== outer
1158 || !loop_in_sese_p (outer
, region
))
1161 int max
= scop
->pbbs
.length ();
1163 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1165 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1167 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1168 scop
, outer
, index
, context_loop
);
1171 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1172 || nested_in (loop_at (scop
, index
), outer
))
1175 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1177 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1183 /* We reached the end of the OUTER loop: embed S in OUTER. */
1184 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1185 outer
, index
, context_loop
);
1188 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1189 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1190 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1191 nest contained within CONTEXT_LOOP. */
1193 static isl_schedule
*
1194 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1196 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1198 loop_p loop
= loop_at (scop
, index
);
1199 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1200 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1203 /* Build the schedule of the SCOP. */
1206 build_original_schedule (scop_p scop
)
1208 schedule_error
= false;
1211 int n
= scop
->pbbs
.length ();
1214 poly_bb_p pbb
= scop
->pbbs
[i
];
1215 isl_schedule
*s
= NULL
;
1216 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1217 s
= build_schedule_pbb (scop
, &i
);
1219 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1221 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1227 fprintf (dump_file
, "[sese-to-poly] failed to build "
1228 "original schedule\n");
1234 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1235 print_isl_schedule (dump_file
, scop
->original_schedule
);
1237 if (!scop
->original_schedule
)
1242 /* Builds the polyhedral representation for a SESE region. */
1245 build_poly_scop (scop_p scop
)
1247 build_scop_context (scop
);
1250 unsigned n
= scop
->pbbs
.length ();
1252 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1254 build_scop_drs (scop
);
1255 build_original_schedule (scop
);
1258 #endif /* HAVE_isl */