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 (wi::to_wide (t
), res
, TYPE_SIGN (TREE_TYPE (t
)));
69 /* Return an isl identifier for the polyhedral basic block PBB. */
72 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
75 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
76 return isl_id_alloc (s
->isl_context
, name
, pbb
);
79 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
81 /* Extract an affine expression from the chain of recurrence E. */
84 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
86 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
87 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
88 isl_local_space
*ls
= isl_local_space_from_space (space
);
89 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
90 isl_aff
*loop
= isl_aff_set_coefficient_si
91 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
92 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
94 /* Before multiplying, make sure that the result is affine. */
95 gcc_assert (isl_pw_aff_is_cst (rhs
)
96 || isl_pw_aff_is_cst (l
));
98 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
101 /* Extract an affine expression from the mult_expr E. */
104 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
106 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
107 isl_space_copy (space
));
108 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
110 if (!isl_pw_aff_is_cst (lhs
)
111 && !isl_pw_aff_is_cst (rhs
))
113 isl_pw_aff_free (lhs
);
114 isl_pw_aff_free (rhs
);
118 return isl_pw_aff_mul (lhs
, rhs
);
121 /* Return an isl identifier from the name of the ssa_name E. */
124 isl_id_for_ssa_name (scop_p s
, tree e
)
127 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
128 return isl_id_alloc (s
->isl_context
, name1
, e
);
131 /* Return an isl identifier for the data reference DR. Data references and
132 scalar references get the same isl_id. They need to be comparable and are
133 distinguished through the first dimension, which contains the alias set or
134 SSA_NAME_VERSION number. */
137 isl_id_for_dr (scop_p s
)
139 return isl_id_alloc (s
->isl_context
, "", 0);
142 /* Extract an affine expression from the ssa_name E. */
145 extract_affine_name (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
);
781 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
782 isl_constraint
*c
= isl_inequality_alloc (ls
);
783 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
786 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
787 print_isl_constraint (dump_file
, c
);
789 domain
= isl_set_add_constraint (domain
, c
);
791 tree nb_iters
= number_of_latch_executions (loop
);
792 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
794 /* loop_i <= cst_nb_iters */
795 isl_local_space
*ls
= isl_local_space_from_space (space
);
796 isl_constraint
*c
= isl_inequality_alloc (ls
);
797 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
799 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
800 c
= isl_constraint_set_constant_val (c
, v
);
801 return isl_set_add_constraint (domain
, c
);
803 /* loop_i <= expr_nb_iters */
804 gcc_assert (!chrec_contains_undetermined (nb_iters
));
805 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
806 gcc_assert (!chrec_contains_undetermined (nb_iters
));
808 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
809 isl_space_copy (space
));
810 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
811 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
812 isl_set_dim (valid
, isl_dim_set
));
815 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
817 ls
= isl_local_space_from_space (isl_space_copy (space
));
818 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
819 isl_dim_in
, loop_index
, 1);
820 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
821 isl_pw_aff_copy (aff_nb_iters
));
824 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
825 print_isl_set (dump_file
, le
);
827 domain
= isl_set_intersect (domain
, le
);
830 if (!max_stmt_executions (loop
, &nit
))
832 isl_pw_aff_free (aff_nb_iters
);
833 isl_space_free (space
);
837 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
838 do not know whether the loop executes at least once. */
841 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
842 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
843 x
= isl_set_project_out (x
, isl_dim_set
, 0,
844 isl_set_dim (x
, isl_dim_set
));
845 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
847 ls
= isl_local_space_from_space (space
);
848 c
= isl_inequality_alloc (ls
);
849 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
850 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
851 c
= isl_constraint_set_constant_val (c
, v
);
855 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
856 print_isl_constraint (dump_file
, c
);
859 return isl_set_add_constraint (domain
, c
);
862 /* Builds the original iteration domains for each pbb in the SCOP. */
865 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
866 int index
, loop_p context_loop
)
868 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
869 isl_set
*domain
= isl_set_copy (context
);
870 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
871 const sese_l
®ion
= scop
->scop_info
->region
;
875 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
877 loop_p loop
= pbb_loop (pbb
);
880 pbb
->iterators
= isl_set_copy (domain
);
881 pbb
->domain
= isl_set_copy (domain
);
882 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
883 isl_id_for_pbb (scop
, pbb
));
884 add_conditions_to_domain (pbb
);
888 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
890 print_isl_set (dump_file
, domain
);
895 while (loop_in_sese_p (loop
, region
)
897 loop
= loop_outer (loop
);
901 /* A statement in a different loop nest than CURRENT loop. */
902 isl_set_free (domain
);
906 /* A statement nested in the CURRENT loop. */
907 i
= build_iteration_domains (scop
, domain
, i
, current
);
911 isl_set_free (domain
);
915 /* Assign dimension for each parameter in SCOP and add constraints for the
919 build_scop_context (scop_p scop
)
921 sese_info_p region
= scop
->scop_info
;
922 unsigned nbp
= sese_nb_params (region
);
923 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
927 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
928 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
929 isl_id_for_ssa_name (scop
, e
));
931 scop
->param_context
= isl_set_universe (space
);
934 for (p
= 0; p
< nbp
; p
++)
935 add_param_constraints (scop
, p
);
938 /* Return true when loop A is nested in loop B. */
941 nested_in (loop_p a
, loop_p b
)
943 return b
== find_common_loop (a
, b
);
946 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
948 loop_at (scop_p scop
, int *index
)
950 return pbb_loop (scop
->pbbs
[*index
]);
953 /* Return the index of any pbb belonging to loop or a subloop of A. */
956 index_outermost_in_loop (loop_p a
, scop_p scop
)
958 int i
, outermost
= -1;
961 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
962 if (nested_in (pbb_loop (pbb
), a
)
964 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
967 last_depth
= loop_depth (pbb_loop (pbb
));
972 /* Return the index of any pbb belonging to loop or a subloop of A. */
975 index_pbb_in_loop (loop_p a
, scop_p scop
)
979 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
980 if (pbb_loop (pbb
) == a
)
986 outermost_pbb_in (loop_p loop
, scop_p scop
)
988 int x
= index_pbb_in_loop (loop
, scop
);
990 x
= index_outermost_in_loop (loop
, scop
);
991 return scop
->pbbs
[x
];
994 static isl_schedule
*
995 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
1005 return isl_schedule_sequence (a
, b
);
1008 struct map_to_dimension_data
{
1010 isl_union_pw_multi_aff
*res
;
1013 /* Create a function that maps the elements of SET to its N-th dimension and add
1017 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1019 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1020 int dim
= isl_set_dim (set
, isl_dim_set
);
1021 isl_space
*space
= isl_set_get_space (set
);
1023 gcc_assert (dim
>= data
->n
);
1024 isl_pw_multi_aff
*pma
1025 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1027 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1033 /* Return SET in which all inner dimensions above N are removed. */
1035 static isl_multi_union_pw_aff
*
1036 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1038 gcc_assert (n
>= 0);
1040 gcc_assert (!isl_union_set_is_empty (set
));
1042 isl_space
*space
= isl_union_set_get_space (set
);
1043 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1045 struct map_to_dimension_data data
= {n
, pwaff
};
1047 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1048 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1050 isl_union_set_free (set
);
1051 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1054 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1056 static isl_schedule
*
1057 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1060 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1061 isl_set
*iterators
= pbb
->iterators
;
1063 int empty
= isl_set_is_empty (iterators
);
1064 if (empty
< 0 || empty
)
1065 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1067 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1068 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1069 if (isl_union_set_is_empty (domain
))
1071 isl_union_set_free (domain
);
1075 isl_space
*space
= isl_set_get_space (iterators
);
1076 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1078 loop_p ploop
= pbb_loop (pbb
);
1079 while (loop
!= ploop
)
1082 ploop
= loop_outer (ploop
);
1085 isl_local_space
*ls
= isl_local_space_from_space (space
);
1086 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1087 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1089 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1090 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1092 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1094 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1095 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1096 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1097 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1100 /* Build schedule for the pbb at INDEX. */
1102 static isl_schedule
*
1103 build_schedule_pbb (scop_p scop
, int *index
)
1105 poly_bb_p pbb
= scop
->pbbs
[*index
];
1107 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1108 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1109 return isl_schedule_from_domain (ud
);
1112 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1114 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1116 static isl_schedule
*
1117 build_schedule_loop (scop_p scop
, int *index
)
1119 int max
= scop
->pbbs
.length ();
1120 gcc_assert (*index
< max
);
1121 loop_p loop
= loop_at (scop
, index
);
1123 isl_schedule
*s
= NULL
;
1124 while (nested_in (loop_at (scop
, index
), loop
))
1126 if (loop
== loop_at (scop
, index
))
1127 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1129 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1135 return add_loop_schedule (s
, loop
, scop
);
1138 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1139 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1140 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1141 maximal loop nest contained within CONTEXT_LOOP. */
1143 static isl_schedule
*
1144 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1145 loop_p loop
, int *index
, loop_p context_loop
)
1147 loop_p outer
= loop_outer (loop
);
1148 sese_l region
= scop
->scop_info
->region
;
1149 if (context_loop
== outer
1150 || !loop_in_sese_p (outer
, region
))
1153 int max
= scop
->pbbs
.length ();
1155 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1157 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1159 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1160 scop
, outer
, index
, context_loop
);
1163 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1164 || nested_in (loop_at (scop
, index
), outer
))
1167 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1169 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1175 /* We reached the end of the OUTER loop: embed S in OUTER. */
1176 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1177 outer
, index
, context_loop
);
1180 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1181 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1182 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1183 nest contained within CONTEXT_LOOP. */
1185 static isl_schedule
*
1186 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1188 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1190 loop_p loop
= loop_at (scop
, index
);
1191 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1192 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1195 /* Build the schedule of the SCOP. */
1198 build_original_schedule (scop_p scop
)
1201 int n
= scop
->pbbs
.length ();
1204 poly_bb_p pbb
= scop
->pbbs
[i
];
1205 isl_schedule
*s
= NULL
;
1206 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1207 s
= build_schedule_pbb (scop
, &i
);
1209 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1211 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1216 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1217 print_isl_schedule (dump_file
, scop
->original_schedule
);
1221 /* Builds the polyhedral representation for a SESE region. */
1224 build_poly_scop (scop_p scop
)
1226 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1227 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1229 build_scop_context (scop
);
1232 unsigned n
= scop
->pbbs
.length ();
1234 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1236 build_scop_drs (scop
);
1237 build_original_schedule (scop
);
1239 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1240 isl_ctx_reset_error (scop
->isl_context
);
1241 isl_options_set_on_error (scop
->isl_context
, old_err
);
1242 if (err
!= isl_error_none
)
1243 dump_printf (MSG_MISSED_OPTIMIZATION
,
1244 "ISL error while building poly scop\n");
1246 return err
== isl_error_none
;
1248 #endif /* HAVE_isl */