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
));
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. */
303 tree itype
= TREE_TYPE (TREE_OPERAND (e
, 0));
304 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
305 /* Signed values, even if overflow is undefined, get modulo-reduced.
306 But only if not all values of the old type fit in the new. */
307 if (! TYPE_UNSIGNED (type
)
308 && ((TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (e
, 0)))
309 && TYPE_PRECISION (type
) <= TYPE_PRECISION (itype
))
310 || TYPE_PRECISION (type
) < TYPE_PRECISION (itype
)))
311 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
315 case NON_LVALUE_EXPR
:
316 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
324 if (TYPE_UNSIGNED (type
))
325 res
= wrap (res
, TYPE_PRECISION (type
));
330 /* Returns a linear expression for tree T evaluated in PBB. */
333 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
335 scop_p scop
= PBB_SCOP (pbb
);
337 t
= scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
339 gcc_assert (!chrec_contains_undetermined (t
));
340 gcc_assert (!automatically_generated_chrec_p (t
));
342 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
345 /* Add conditional statement STMT to pbb. CODE is used as the comparison
346 operator. This allows us to invert the condition or to handle
350 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
352 loop_p loop
= gimple_bb (stmt
)->loop_father
;
353 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
354 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
360 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
364 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
368 cond
= isl_pw_aff_le_set (lhs
, rhs
);
372 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
376 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
380 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
387 cond
= isl_set_coalesce (cond
);
388 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
389 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
392 /* Add conditions to the domain of PBB. */
395 add_conditions_to_domain (poly_bb_p pbb
)
399 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
401 if (GBB_CONDITIONS (gbb
).is_empty ())
404 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
405 switch (gimple_code (stmt
))
409 /* Don't constrain on anything else than INTEGER_TYPE. */
410 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
413 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
414 enum tree_code code
= gimple_cond_code (cond_stmt
);
416 /* The conditions for ELSE-branches are inverted. */
417 if (!GBB_CONDITION_CASES (gbb
)[i
])
418 code
= invert_tree_comparison (code
, false);
420 add_condition_to_pbb (pbb
, cond_stmt
, code
);
430 /* Add constraints on the possible values of parameter P from the type
434 add_param_constraints (scop_p scop
, graphite_dim_t p
)
436 tree parameter
= scop
->scop_info
->params
[p
];
437 tree type
= TREE_TYPE (parameter
);
441 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
442 lb
= lower_bound_in_type (type
, type
);
444 lb
= TYPE_MIN_VALUE (type
);
446 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
447 ub
= upper_bound_in_type (type
, type
);
449 ub
= TYPE_MAX_VALUE (type
);
453 isl_space
*space
= isl_set_get_space (scop
->param_context
);
457 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
458 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (lb
));
460 c
= isl_constraint_set_constant_val (c
, v
);
461 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
463 scop
->param_context
= isl_set_coalesce
464 (isl_set_add_constraint (scop
->param_context
, c
));
469 isl_space
*space
= isl_set_get_space (scop
->param_context
);
473 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
475 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (ub
));
476 c
= isl_constraint_set_constant_val (c
, v
);
477 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
479 scop
->param_context
= isl_set_coalesce
480 (isl_set_add_constraint (scop
->param_context
, c
));
484 /* Add a constrain to the ACCESSES polyhedron for the alias set of
485 data reference DR. ACCESSP_NB_DIMS is the dimension of the
486 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
490 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
492 isl_constraint
*c
= isl_equality_alloc
493 (isl_local_space_from_space (isl_map_get_space (acc
)));
494 /* Positive numbers for all alias sets. */
495 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
496 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
498 return isl_map_add_constraint (acc
, c
);
501 /* Assign the affine expression INDEX to the output dimension POS of
502 MAP and return the result. */
505 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
508 int len
= isl_map_dim (map
, isl_dim_out
);
511 index_map
= isl_map_from_pw_aff (index
);
512 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
513 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
515 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
516 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
517 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
518 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
520 return isl_map_intersect (map
, index_map
);
523 /* Add to ACCESSES polyhedron equalities defining the access functions
524 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
525 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
526 PBB is the poly_bb_p that contains the data reference DR. */
529 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
531 data_reference_p dr
= dri
.dr
;
532 poly_bb_p pbb
= dri
.pbb
;
533 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
534 scop_p scop
= PBB_SCOP (pbb
);
536 for (i
= 0; i
< nb_subscripts
; i
++)
539 tree afn
= DR_ACCESS_FN (dr
, i
);
541 aff
= extract_affine (scop
, afn
,
542 isl_space_domain (isl_map_get_space (acc
)));
543 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
546 return isl_map_coalesce (acc
);
549 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
550 to extract constraints on accessed elements of the array. Returning false is
551 the conservative answer. */
554 bounds_are_valid (tree ref
, tree low
, tree high
)
559 if (!tree_fits_shwi_p (low
)
560 || !tree_fits_shwi_p (high
))
563 /* 1-element arrays at end of structures may extend over
564 their declared size. */
565 if (array_at_struct_end_p (ref
)
566 && operand_equal_p (low
, high
, 0))
569 /* Fortran has some arrays where high bound is -1 and low is 0. */
570 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
576 /* Add constrains representing the size of the accessed data to the
577 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
578 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
582 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
585 tree ref
= DR_REF (dr
);
587 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
588 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
590 if (TREE_CODE (ref
) != ARRAY_REF
)
591 return subscript_sizes
;
593 tree low
= array_ref_low_bound (ref
);
594 tree high
= array_ref_up_bound (ref
);
596 if (!bounds_are_valid (ref
, low
, high
))
599 isl_space
*space
= isl_set_get_space (subscript_sizes
);
600 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
601 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
604 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
605 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
606 isl_set_dim (valid
, isl_dim_set
));
607 scop
->param_context
= isl_set_coalesce
608 (isl_set_intersect (scop
->param_context
, valid
));
611 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
612 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
614 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
615 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
617 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
618 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
619 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
621 /* low <= sub_i <= high */
622 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
623 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
624 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
625 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
628 return isl_set_coalesce (subscript_sizes
);
631 /* Build data accesses for DRI. */
634 build_poly_dr (dr_info
&dri
)
637 isl_set
*subscript_sizes
;
638 poly_bb_p pbb
= dri
.pbb
;
639 data_reference_p dr
= dri
.dr
;
640 scop_p scop
= PBB_SCOP (pbb
);
641 isl_id
*id
= isl_id_for_dr (scop
);
644 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
645 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
646 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
647 isl_dim_out
, nb_out
);
649 acc
= isl_map_universe (space
);
650 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
653 acc
= pdr_add_alias_set (acc
, dri
);
654 acc
= pdr_add_memory_accesses (acc
, dri
);
657 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
658 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
660 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
661 subscript_sizes
= isl_set_nat_universe (space
);
662 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
664 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
667 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
668 acc
, subscript_sizes
);
672 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
673 isl_map
*acc
, isl_set
*subscript_sizes
)
675 scop_p scop
= PBB_SCOP (pbb
);
676 /* Each scalar variables has a unique alias set number starting from
677 the maximum alias set assigned to a dr. */
678 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
679 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
682 /* Add a constrain to the ACCESSES polyhedron for the alias set of
683 data reference DR. */
685 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
686 c
= isl_constraint_set_constant_si (c
, -alias_set
);
687 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
689 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
693 /* Record all cross basic block scalar variables in PBB. */
696 build_poly_sr (poly_bb_p pbb
)
698 scop_p scop
= PBB_SCOP (pbb
);
699 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
700 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
701 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
703 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
705 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
706 isl_dim_out
, nb_out
);
707 isl_id
*id
= isl_id_for_dr (scop
);
708 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
709 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
710 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
711 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
715 FOR_EACH_VEC_ELT (writes
, i
, var
)
716 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
717 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
720 FOR_EACH_VEC_ELT (reads
, i
, use
)
721 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
722 isl_set_copy (subscript_sizes
));
725 isl_set_free (subscript_sizes
);
728 /* Build data references in SCOP. */
731 build_scop_drs (scop_p scop
)
735 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
736 build_poly_dr (*dri
);
739 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
743 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
746 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
748 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
749 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
751 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
752 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
753 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
756 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
759 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
764 const sese_l
®ion
= scop
->scop_info
->region
;
765 if (!loop_in_sese_p (loop
, region
))
768 /* Recursion all the way up to the context loop. */
769 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
771 /* Then, build constraints over the loop in post-order: outer to inner. */
773 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
775 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
776 "domain for loop_%d.\n", loop
->num
);
777 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
778 isl_space
*space
= isl_set_get_space (domain
);
780 if (!loop_in_sese_p (loop
, region
))
783 isl_local_space
*ls
= isl_local_space_from_space (space
);
784 isl_constraint
*c
= isl_equality_alloc (ls
);
785 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
788 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
789 print_isl_constraint (dump_file
, c
);
791 domain
= isl_set_add_constraint (domain
, c
);
796 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
797 isl_constraint
*c
= isl_inequality_alloc (ls
);
798 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
801 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
802 print_isl_constraint (dump_file
, c
);
804 domain
= isl_set_add_constraint (domain
, c
);
806 tree nb_iters
= number_of_latch_executions (loop
);
807 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
809 /* loop_i <= cst_nb_iters */
810 isl_local_space
*ls
= isl_local_space_from_space (space
);
811 isl_constraint
*c
= isl_inequality_alloc (ls
);
812 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
814 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
815 c
= isl_constraint_set_constant_val (c
, v
);
816 return isl_set_add_constraint (domain
, c
);
818 /* loop_i <= expr_nb_iters */
819 gcc_assert (!chrec_contains_undetermined (nb_iters
));
820 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
821 gcc_assert (!chrec_contains_undetermined (nb_iters
));
823 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
824 isl_space_copy (space
));
825 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
826 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
827 isl_set_dim (valid
, isl_dim_set
));
830 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
832 ls
= isl_local_space_from_space (isl_space_copy (space
));
833 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
834 isl_dim_in
, loop_index
, 1);
835 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
836 isl_pw_aff_copy (aff_nb_iters
));
839 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
840 print_isl_set (dump_file
, le
);
842 domain
= isl_set_intersect (domain
, le
);
845 if (!max_stmt_executions (loop
, &nit
))
847 isl_pw_aff_free (aff_nb_iters
);
848 isl_space_free (space
);
852 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
853 do not know whether the loop executes at least once. */
856 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
857 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
858 x
= isl_set_project_out (x
, isl_dim_set
, 0,
859 isl_set_dim (x
, isl_dim_set
));
860 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
862 ls
= isl_local_space_from_space (space
);
863 c
= isl_inequality_alloc (ls
);
864 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
865 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
866 c
= isl_constraint_set_constant_val (c
, v
);
870 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
871 print_isl_constraint (dump_file
, c
);
874 return isl_set_add_constraint (domain
, c
);
877 /* Builds the original iteration domains for each pbb in the SCOP. */
880 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
881 int index
, loop_p context_loop
)
883 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
884 isl_set
*domain
= isl_set_copy (context
);
885 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
886 const sese_l
®ion
= scop
->scop_info
->region
;
890 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
892 loop_p loop
= pbb_loop (pbb
);
895 pbb
->iterators
= isl_set_copy (domain
);
896 pbb
->domain
= isl_set_copy (domain
);
897 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
898 isl_id_for_pbb (scop
, pbb
));
899 add_conditions_to_domain (pbb
);
903 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
905 print_isl_set (dump_file
, domain
);
910 while (loop_in_sese_p (loop
, region
)
912 loop
= loop_outer (loop
);
916 /* A statement in a different loop nest than CURRENT loop. */
917 isl_set_free (domain
);
921 /* A statement nested in the CURRENT loop. */
922 i
= build_iteration_domains (scop
, domain
, i
, current
);
926 isl_set_free (domain
);
930 /* Assign dimension for each parameter in SCOP and add constraints for the
934 build_scop_context (scop_p scop
)
936 sese_info_p region
= scop
->scop_info
;
937 unsigned nbp
= sese_nb_params (region
);
938 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
942 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
943 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
944 isl_id_for_ssa_name (scop
, e
));
946 scop
->param_context
= isl_set_universe (space
);
949 for (p
= 0; p
< nbp
; p
++)
950 add_param_constraints (scop
, p
);
953 /* Return true when loop A is nested in loop B. */
956 nested_in (loop_p a
, loop_p b
)
958 return b
== find_common_loop (a
, b
);
961 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
963 loop_at (scop_p scop
, int *index
)
965 return pbb_loop (scop
->pbbs
[*index
]);
968 /* Return the index of any pbb belonging to loop or a subloop of A. */
971 index_outermost_in_loop (loop_p a
, scop_p scop
)
973 int i
, outermost
= -1;
976 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
977 if (nested_in (pbb_loop (pbb
), a
)
979 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
982 last_depth
= loop_depth (pbb_loop (pbb
));
987 /* Return the index of any pbb belonging to loop or a subloop of A. */
990 index_pbb_in_loop (loop_p a
, scop_p scop
)
994 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
995 if (pbb_loop (pbb
) == a
)
1001 outermost_pbb_in (loop_p loop
, scop_p scop
)
1003 int x
= index_pbb_in_loop (loop
, scop
);
1005 x
= index_outermost_in_loop (loop
, scop
);
1006 return scop
->pbbs
[x
];
1009 static isl_schedule
*
1010 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
1012 gcc_assert (a
|| b
);
1020 return isl_schedule_sequence (a
, b
);
1023 struct map_to_dimension_data
{
1025 isl_union_pw_multi_aff
*res
;
1028 /* Create a function that maps the elements of SET to its N-th dimension and add
1032 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1034 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1035 int dim
= isl_set_dim (set
, isl_dim_set
);
1036 isl_space
*space
= isl_set_get_space (set
);
1038 gcc_assert (dim
>= data
->n
);
1039 isl_pw_multi_aff
*pma
1040 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1042 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1048 /* Return SET in which all inner dimensions above N are removed. */
1050 static isl_multi_union_pw_aff
*
1051 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1053 gcc_assert (n
>= 0);
1055 gcc_assert (!isl_union_set_is_empty (set
));
1057 isl_space
*space
= isl_union_set_get_space (set
);
1058 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1060 struct map_to_dimension_data data
= {n
, pwaff
};
1062 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1063 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1065 isl_union_set_free (set
);
1066 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1069 static bool schedule_error
;
1071 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1073 static isl_schedule
*
1074 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1077 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1078 isl_set
*iterators
= pbb
->iterators
;
1080 int empty
= isl_set_is_empty (iterators
);
1081 if (empty
< 0 || empty
)
1082 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1084 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1085 /* We cannot apply an empty domain to pbbs in this loop so fail.
1086 ??? Somehow drop pbbs in the loop instead. */
1087 if (isl_union_set_is_empty (domain
))
1089 schedule_error
= true;
1090 isl_union_set_free (domain
);
1094 isl_space
*space
= isl_set_get_space (iterators
);
1095 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1097 loop_p ploop
= pbb_loop (pbb
);
1098 while (loop
!= ploop
)
1101 ploop
= loop_outer (ploop
);
1104 isl_local_space
*ls
= isl_local_space_from_space (space
);
1105 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1106 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1108 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1109 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1111 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1113 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1114 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1115 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1116 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1119 /* Build schedule for the pbb at INDEX. */
1121 static isl_schedule
*
1122 build_schedule_pbb (scop_p scop
, int *index
)
1124 poly_bb_p pbb
= scop
->pbbs
[*index
];
1126 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1127 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1128 return isl_schedule_from_domain (ud
);
1131 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1133 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1135 static isl_schedule
*
1136 build_schedule_loop (scop_p scop
, int *index
)
1138 int max
= scop
->pbbs
.length ();
1139 gcc_assert (*index
< max
);
1140 loop_p loop
= loop_at (scop
, index
);
1142 isl_schedule
*s
= NULL
;
1143 while (nested_in (loop_at (scop
, index
), loop
))
1145 if (loop
== loop_at (scop
, index
))
1146 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1148 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1154 return add_loop_schedule (s
, loop
, scop
);
1157 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1158 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1159 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1160 maximal loop nest contained within CONTEXT_LOOP. */
1162 static isl_schedule
*
1163 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1164 loop_p loop
, int *index
, loop_p context_loop
)
1166 loop_p outer
= loop_outer (loop
);
1167 sese_l region
= scop
->scop_info
->region
;
1168 if (context_loop
== outer
1169 || !loop_in_sese_p (outer
, region
))
1172 int max
= scop
->pbbs
.length ();
1174 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1176 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1178 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1179 scop
, outer
, index
, context_loop
);
1182 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1183 || nested_in (loop_at (scop
, index
), outer
))
1186 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1188 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1194 /* We reached the end of the OUTER loop: embed S in OUTER. */
1195 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1196 outer
, index
, context_loop
);
1199 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1200 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1201 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1202 nest contained within CONTEXT_LOOP. */
1204 static isl_schedule
*
1205 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1207 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1209 loop_p loop
= loop_at (scop
, index
);
1210 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1211 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1214 /* Build the schedule of the SCOP. */
1217 build_original_schedule (scop_p scop
)
1219 schedule_error
= false;
1222 int n
= scop
->pbbs
.length ();
1225 poly_bb_p pbb
= scop
->pbbs
[i
];
1226 isl_schedule
*s
= NULL
;
1227 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1228 s
= build_schedule_pbb (scop
, &i
);
1230 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1232 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1238 fprintf (dump_file
, "[sese-to-poly] failed to build "
1239 "original schedule\n");
1245 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1246 print_isl_schedule (dump_file
, scop
->original_schedule
);
1248 if (!scop
->original_schedule
)
1253 /* Builds the polyhedral representation for a SESE region. */
1256 build_poly_scop (scop_p scop
)
1258 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1259 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1261 build_scop_context (scop
);
1264 unsigned n
= scop
->pbbs
.length ();
1266 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1268 build_scop_drs (scop
);
1269 build_original_schedule (scop
);
1271 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1272 isl_ctx_reset_error (scop
->isl_context
);
1273 isl_options_set_on_error (scop
->isl_context
, old_err
);
1274 if (err
!= isl_error_none
)
1275 dump_printf (MSG_MISSED_OPTIMIZATION
,
1276 "ISL error while building poly scop\n");
1278 return err
== isl_error_none
;
1280 #endif /* HAVE_isl */