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
));
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 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1071 static isl_schedule
*
1072 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1075 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1076 isl_set
*iterators
= pbb
->iterators
;
1078 int empty
= isl_set_is_empty (iterators
);
1079 if (empty
< 0 || empty
)
1080 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1082 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1083 /* We cannot apply an empty domain to pbbs in this loop so return early. */
1084 if (isl_union_set_is_empty (domain
))
1086 isl_union_set_free (domain
);
1090 isl_space
*space
= isl_set_get_space (iterators
);
1091 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1093 loop_p ploop
= pbb_loop (pbb
);
1094 while (loop
!= ploop
)
1097 ploop
= loop_outer (ploop
);
1100 isl_local_space
*ls
= isl_local_space_from_space (space
);
1101 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1102 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1104 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1105 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1107 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1109 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1110 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1111 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1112 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1115 /* Build schedule for the pbb at INDEX. */
1117 static isl_schedule
*
1118 build_schedule_pbb (scop_p scop
, int *index
)
1120 poly_bb_p pbb
= scop
->pbbs
[*index
];
1122 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1123 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1124 return isl_schedule_from_domain (ud
);
1127 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1129 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1131 static isl_schedule
*
1132 build_schedule_loop (scop_p scop
, int *index
)
1134 int max
= scop
->pbbs
.length ();
1135 gcc_assert (*index
< max
);
1136 loop_p loop
= loop_at (scop
, index
);
1138 isl_schedule
*s
= NULL
;
1139 while (nested_in (loop_at (scop
, index
), loop
))
1141 if (loop
== loop_at (scop
, index
))
1142 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1144 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1150 return add_loop_schedule (s
, loop
, scop
);
1153 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1154 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1155 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1156 maximal loop nest contained within CONTEXT_LOOP. */
1158 static isl_schedule
*
1159 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1160 loop_p loop
, int *index
, loop_p context_loop
)
1162 loop_p outer
= loop_outer (loop
);
1163 sese_l region
= scop
->scop_info
->region
;
1164 if (context_loop
== outer
1165 || !loop_in_sese_p (outer
, region
))
1168 int max
= scop
->pbbs
.length ();
1170 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1172 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1174 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1175 scop
, outer
, index
, context_loop
);
1178 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1179 || nested_in (loop_at (scop
, index
), outer
))
1182 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1184 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1190 /* We reached the end of the OUTER loop: embed S in OUTER. */
1191 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1192 outer
, index
, context_loop
);
1195 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1196 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1197 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1198 nest contained within CONTEXT_LOOP. */
1200 static isl_schedule
*
1201 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1203 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1205 loop_p loop
= loop_at (scop
, index
);
1206 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1207 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1210 /* Build the schedule of the SCOP. */
1213 build_original_schedule (scop_p scop
)
1216 int n
= scop
->pbbs
.length ();
1219 poly_bb_p pbb
= scop
->pbbs
[i
];
1220 isl_schedule
*s
= NULL
;
1221 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1222 s
= build_schedule_pbb (scop
, &i
);
1224 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1226 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1231 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1232 print_isl_schedule (dump_file
, scop
->original_schedule
);
1234 if (!scop
->original_schedule
)
1239 /* Builds the polyhedral representation for a SESE region. */
1242 build_poly_scop (scop_p scop
)
1244 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1245 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
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
);
1257 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1258 isl_ctx_reset_error (scop
->isl_context
);
1259 isl_options_set_on_error (scop
->isl_context
, old_err
);
1260 if (err
!= isl_error_none
)
1261 dump_printf (MSG_MISSED_OPTIMIZATION
,
1262 "ISL error while building poly scop\n");
1264 return err
== isl_error_none
;
1266 #endif /* HAVE_isl */