1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2016 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>
58 #include <isl/val_gmp.h>
62 /* Assigns to RES the value of the INTEGER_CST T. */
65 tree_int_to_gmp (tree t
, mpz_t res
)
67 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
70 /* Return an isl identifier for the polyhedral basic block PBB. */
73 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
76 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
77 return isl_id_alloc (s
->isl_context
, name
, pbb
);
80 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
81 We generate SCATTERING_DIMENSIONS scattering dimensions.
83 The scattering polyhedron consists of these dimensions: scattering,
84 loop_iterators, parameters.
88 | scattering_dimensions = 5
96 | Scattering polyhedron:
98 | scattering: {s1, s2, s3, s4, s5}
100 | parameters: {p1, p2}
102 | s1 s2 s3 s4 s5 i p1 p2 1
103 | 1 0 0 0 0 0 0 0 -4 = 0
104 | 0 1 0 0 0 -1 0 0 0 = 0
105 | 0 0 1 0 0 0 0 0 -5 = 0 */
108 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
113 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
115 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
116 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
),
117 isl_dim_out
, scattering_dimensions
);
118 pbb
->schedule
= isl_map_universe (dm
);
120 for (int i
= 0; i
< scattering_dimensions
; i
++)
122 /* Textual order inside this loop. */
125 isl_constraint
*c
= isl_equality_alloc
126 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
128 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
129 gcc_assert (val
&& isl_val_is_int (val
));
131 val
= isl_val_neg (val
);
132 c
= isl_constraint_set_constant_val (c
, val
);
133 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
134 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
137 /* Iterations of this loop. */
138 else /* if ((i % 2) == 1) */
140 int loop
= (i
- 1) / 2;
141 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
146 /* Simplify the original schedule. */
147 pbb
->schedule
= isl_map_coalesce (pbb
->schedule
);
149 /* At the beginning, set the transformed schedule to the original. */
150 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
153 /* Build for BB the static schedule.
155 The static schedule is a Dewey numbering of the abstract syntax
156 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
158 The following example informally defines the static schedule:
177 Static schedules for A to F:
190 build_scop_scattering (scop_p scop
)
192 gimple_poly_bb_p previous_gbb
= NULL
;
193 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
194 isl_aff
*static_sched
;
196 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
197 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
199 /* We have to start schedules at 0 on the first component and
200 because we cannot compare_prefix_loops against a previous loop,
201 prefix will be equal to zero, and that index will be
202 incremented before copying. */
203 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
207 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
209 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
213 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
217 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
219 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
222 isl_aff_free (static_sched
);
225 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
227 /* Extract an affine expression from the chain of recurrence E. */
230 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
232 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
233 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
234 isl_local_space
*ls
= isl_local_space_from_space (space
);
235 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
236 isl_aff
*loop
= isl_aff_set_coefficient_si
237 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
238 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
240 /* Before multiplying, make sure that the result is affine. */
241 gcc_assert (isl_pw_aff_is_cst (rhs
)
242 || isl_pw_aff_is_cst (l
));
244 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
247 /* Extract an affine expression from the mult_expr E. */
250 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
252 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
253 isl_space_copy (space
));
254 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
256 if (!isl_pw_aff_is_cst (lhs
)
257 && !isl_pw_aff_is_cst (rhs
))
259 isl_pw_aff_free (lhs
);
260 isl_pw_aff_free (rhs
);
264 return isl_pw_aff_mul (lhs
, rhs
);
267 /* Return an isl identifier from the name of the ssa_name E. */
270 isl_id_for_ssa_name (scop_p s
, tree e
)
273 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
274 return isl_id_alloc (s
->isl_context
, name1
, e
);
277 /* Return an isl identifier for the data reference DR. Data references and
278 scalar references get the same isl_id. They need to be comparable and are
279 distinguished through the first dimension, which contains the alias set or
280 SSA_NAME_VERSION number. */
283 isl_id_for_dr (scop_p s
)
285 return isl_id_alloc (s
->isl_context
, "", 0);
288 /* Extract an affine expression from the ssa_name E. */
291 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
293 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
294 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
296 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
297 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
298 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
299 return isl_pw_aff_alloc (dom
, aff
);
302 /* Extract an affine expression from the gmp constant G. */
305 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
307 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
308 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
309 isl_set
*dom
= isl_set_universe (space
);
310 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
311 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
312 aff
= isl_aff_add_constant_val (aff
, v
);
314 return isl_pw_aff_alloc (dom
, aff
);
317 /* Extract an affine expression from the integer_cst E. */
320 extract_affine_int (tree e
, __isl_take isl_space
*space
)
325 tree_int_to_gmp (e
, g
);
326 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
332 /* Compute pwaff mod 2^width. */
335 wrap (isl_pw_aff
*pwaff
, unsigned width
)
339 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
340 mod
= isl_val_2exp (mod
);
341 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
346 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
347 Otherwise returns -1. */
350 parameter_index_in_region_1 (tree name
, sese_info_p region
)
355 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
357 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
364 /* Extract an affine expression from the tree E in the scop S. */
367 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
369 isl_pw_aff
*lhs
, *rhs
, *res
;
371 if (e
== chrec_dont_know
) {
372 isl_space_free (space
);
376 switch (TREE_CODE (e
))
378 case POLYNOMIAL_CHREC
:
379 res
= extract_affine_chrec (s
, e
, space
);
383 res
= extract_affine_mul (s
, e
, space
);
387 case POINTER_PLUS_EXPR
:
388 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
389 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
390 res
= isl_pw_aff_add (lhs
, rhs
);
394 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
395 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
396 res
= isl_pw_aff_sub (lhs
, rhs
);
401 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
402 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
403 res
= isl_pw_aff_mul (lhs
, rhs
);
407 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
408 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
409 res
= extract_affine_name (s
, e
, space
);
413 res
= extract_affine_int (e
, space
);
414 /* No need to wrap a single integer. */
418 case NON_LVALUE_EXPR
:
419 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
427 tree type
= TREE_TYPE (e
);
428 if (TYPE_UNSIGNED (type
))
429 res
= wrap (res
, TYPE_PRECISION (type
));
434 /* Returns a linear expression for tree T evaluated in PBB. */
437 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
439 scop_p scop
= PBB_SCOP (pbb
);
441 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
443 /* Bail out as we do not know the scev. */
444 if (chrec_contains_undetermined (t
))
447 gcc_assert (!automatically_generated_chrec_p (t
));
449 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
452 /* Add conditional statement STMT to pbb. CODE is used as the comparison
453 operator. This allows us to invert the condition or to handle
457 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
459 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
463 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
466 isl_pw_aff_free (lhs
);
474 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
478 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
482 cond
= isl_pw_aff_le_set (lhs
, rhs
);
486 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
490 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
494 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
498 isl_pw_aff_free (lhs
);
499 isl_pw_aff_free (rhs
);
503 cond
= isl_set_coalesce (cond
);
504 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
505 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
509 /* Add conditions to the domain of PBB. */
512 add_conditions_to_domain (poly_bb_p pbb
)
516 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
518 if (GBB_CONDITIONS (gbb
).is_empty ())
521 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
522 switch (gimple_code (stmt
))
526 /* Don't constrain on anything else than INTEGER_TYPE. */
527 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
530 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
531 enum tree_code code
= gimple_cond_code (cond_stmt
);
533 /* The conditions for ELSE-branches are inverted. */
534 if (!GBB_CONDITION_CASES (gbb
)[i
])
535 code
= invert_tree_comparison (code
, false);
537 if (!add_condition_to_pbb (pbb
, cond_stmt
, code
))
543 /* Switch statements are not supported right now - fall through. */
553 /* Traverses all the GBBs of the SCOP and add their constraints to the
554 iteration domains. */
557 add_conditions_to_constraints (scop_p scop
)
562 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
563 if (!add_conditions_to_domain (pbb
))
569 /* Add constraints on the possible values of parameter P from the type
573 add_param_constraints (scop_p scop
, graphite_dim_t p
)
575 tree parameter
= scop
->scop_info
->params
[p
];
576 tree type
= TREE_TYPE (parameter
);
580 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
581 lb
= lower_bound_in_type (type
, type
);
583 lb
= TYPE_MIN_VALUE (type
);
585 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
586 ub
= upper_bound_in_type (type
, type
);
588 ub
= TYPE_MAX_VALUE (type
);
592 isl_space
*space
= isl_set_get_space (scop
->param_context
);
597 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
599 tree_int_to_gmp (lb
, g
);
600 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
603 c
= isl_constraint_set_constant_val (c
, v
);
604 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
606 scop
->param_context
= isl_set_coalesce
607 (isl_set_add_constraint (scop
->param_context
, c
));
612 isl_space
*space
= isl_set_get_space (scop
->param_context
);
617 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
620 tree_int_to_gmp (ub
, g
);
621 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
623 c
= isl_constraint_set_constant_val (c
, v
);
624 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
626 scop
->param_context
= isl_set_coalesce
627 (isl_set_add_constraint (scop
->param_context
, c
));
631 /* Add a constrain to the ACCESSES polyhedron for the alias set of
632 data reference DR. ACCESSP_NB_DIMS is the dimension of the
633 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
637 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
639 isl_constraint
*c
= isl_equality_alloc
640 (isl_local_space_from_space (isl_map_get_space (acc
)));
641 /* Positive numbers for all alias sets. */
642 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
643 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
645 return isl_map_add_constraint (acc
, c
);
648 /* Add a constrain to the ACCESSES polyhedron for the alias set of
649 data reference DR. ACCESSP_NB_DIMS is the dimension of the
650 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
654 add_scalar_version_numbers (isl_map
*acc
, tree var
)
656 isl_constraint
*c
= isl_equality_alloc
657 (isl_local_space_from_space (isl_map_get_space (acc
)));
658 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
659 /* Each scalar variables has a unique alias set number starting from
661 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
662 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
664 return isl_map_add_constraint (acc
, c
);
667 /* Assign the affine expression INDEX to the output dimension POS of
668 MAP and return the result. */
671 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
674 int len
= isl_map_dim (map
, isl_dim_out
);
677 index_map
= isl_map_from_pw_aff (index
);
678 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
679 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
681 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
682 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
683 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
684 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
686 return isl_map_intersect (map
, index_map
);
689 /* Add to ACCESSES polyhedron equalities defining the access functions
690 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
691 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
692 PBB is the poly_bb_p that contains the data reference DR. */
695 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
697 data_reference_p dr
= dri
.dr
;
698 poly_bb_p pbb
= dri
.pbb
;
699 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
700 scop_p scop
= PBB_SCOP (pbb
);
702 for (i
= 0; i
< nb_subscripts
; i
++)
705 tree afn
= DR_ACCESS_FN (dr
, i
);
707 aff
= extract_affine (scop
, afn
,
708 isl_space_domain (isl_map_get_space (acc
)));
709 acc
= set_index (acc
, i
+ 1, aff
);
712 return isl_map_coalesce (acc
);
715 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
716 to extract constraints on accessed elements of the array. Returning false is
717 the conservative answer. */
720 bounds_are_valid (tree ref
, tree low
, tree high
)
725 if (!tree_fits_shwi_p (low
)
726 || !tree_fits_shwi_p (high
))
729 /* 1-element arrays at end of structures may extend over
730 their declared size. */
731 if (array_at_struct_end_p (ref
)
732 && operand_equal_p (low
, high
, 0))
735 /* Fortran has some arrays where high bound is -1 and low is 0. */
736 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
742 /* Add constrains representing the size of the accessed data to the
743 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
744 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
748 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
751 tree ref
= DR_REF (dr
);
753 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
754 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
756 if (TREE_CODE (ref
) != ARRAY_REF
)
757 return subscript_sizes
;
759 tree low
= array_ref_low_bound (ref
);
760 tree high
= array_ref_up_bound (ref
);
762 if (!bounds_are_valid (ref
, low
, high
))
765 isl_space
*space
= isl_set_get_space (subscript_sizes
);
766 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
767 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
770 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
771 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
772 isl_set_dim (valid
, isl_dim_set
));
773 scop
->param_context
= isl_set_coalesce
774 (isl_set_intersect (scop
->param_context
, valid
));
777 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
778 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
780 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
781 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
783 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
784 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
785 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
787 /* low <= sub_i <= high */
788 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
789 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
790 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
791 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
794 return isl_set_coalesce (subscript_sizes
);
797 /* Build data accesses for DRI. */
800 build_poly_dr (dr_info
&dri
)
803 isl_set
*subscript_sizes
;
804 poly_bb_p pbb
= dri
.pbb
;
805 data_reference_p dr
= dri
.dr
;
806 scop_p scop
= PBB_SCOP (pbb
);
807 isl_id
*id
= isl_id_for_dr (scop
);
810 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
811 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
812 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
813 isl_dim_out
, nb_out
);
815 acc
= isl_map_universe (space
);
816 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
819 acc
= pdr_add_alias_set (acc
, dri
);
820 acc
= pdr_add_memory_accesses (acc
, dri
);
823 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
824 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
826 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
827 subscript_sizes
= isl_set_nat_universe (space
);
828 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
830 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
833 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
834 acc
, subscript_sizes
);
838 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
839 isl_map
*acc
, isl_set
*subscript_sizes
)
841 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
842 /* Each scalar variables has a unique alias set number starting from
844 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
845 max_arrays
+ SSA_NAME_VERSION (var
));
847 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
851 /* Record all cross basic block scalar variables in PBB. */
854 build_poly_sr (poly_bb_p pbb
)
856 scop_p scop
= PBB_SCOP (pbb
);
857 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
858 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
859 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
861 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
863 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
864 isl_dim_out
, nb_out
);
865 isl_id
*id
= isl_id_for_dr (scop
);
866 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
867 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
868 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
869 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
873 FOR_EACH_VEC_ELT (writes
, i
, var
)
874 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
875 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
878 FOR_EACH_VEC_ELT (reads
, i
, use
)
879 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
880 isl_set_copy (subscript_sizes
));
883 isl_set_free (subscript_sizes
);
886 /* Build data references in SCOP. */
889 build_scop_drs (scop_p scop
)
893 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
894 build_poly_dr (*dri
);
897 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
901 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
904 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
909 const sese_l
®ion
= scop
->scop_info
->region
;
910 if (!loop_in_sese_p (loop
, region
))
913 /* Recursion all the way up to the context loop. */
914 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
916 /* Then, build constraints over the loop in post-order: outer to inner. */
918 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
920 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
921 "domain for loop_%d.\n", loop
->num
);
922 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
923 isl_space
*space
= isl_set_get_space (domain
);
926 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
927 isl_constraint
*c
= isl_inequality_alloc (ls
);
928 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
931 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
932 print_isl_constraint (dump_file
, c
);
934 domain
= isl_set_add_constraint (domain
, c
);
936 tree nb_iters
= number_of_latch_executions (loop
);
937 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
939 /* loop_i <= cst_nb_iters */
940 isl_local_space
*ls
= isl_local_space_from_space (space
);
941 isl_constraint
*c
= isl_inequality_alloc (ls
);
942 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
945 tree_int_to_gmp (nb_iters
, g
);
946 isl_val
*v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
948 c
= isl_constraint_set_constant_val (c
, v
);
949 return isl_set_add_constraint (domain
, c
);
951 /* loop_i <= expr_nb_iters */
952 gcc_assert (!chrec_contains_undetermined (nb_iters
));
953 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
954 gcc_assert (!chrec_contains_undetermined (nb_iters
));
956 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
957 isl_space_copy (space
));
958 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
959 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
960 isl_set_dim (valid
, isl_dim_set
));
963 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
965 ls
= isl_local_space_from_space (isl_space_copy (space
));
966 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
967 isl_dim_in
, loop_index
, 1);
968 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
969 isl_pw_aff_copy (aff_nb_iters
));
972 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
973 print_isl_set (dump_file
, le
);
975 domain
= isl_set_intersect (domain
, le
);
978 if (!max_stmt_executions (loop
, &nit
))
980 isl_pw_aff_free (aff_nb_iters
);
981 isl_space_free (space
);
985 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
986 do not know whether the loop executes at least once. */
989 wi::to_mpz (nit
, g
, SIGNED
);
990 mpz_sub_ui (g
, g
, 1);
992 isl_pw_aff
*approx
= extract_affine_gmp (g
, isl_space_copy (space
));
993 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
994 x
= isl_set_project_out (x
, isl_dim_set
, 0,
995 isl_set_dim (x
, isl_dim_set
));
996 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
998 ls
= isl_local_space_from_space (space
);
999 c
= isl_inequality_alloc (ls
);
1000 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
1001 isl_val
*v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
1003 c
= isl_constraint_set_constant_val (c
, v
);
1007 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
1008 print_isl_constraint (dump_file
, c
);
1011 return isl_set_add_constraint (domain
, c
);
1014 /* Builds the original iteration domains for each pbb in the SCOP. */
1017 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
, int index
,
1018 loop_p context_loop
)
1020 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
1021 isl_set
*domain
= isl_set_copy (context
);
1022 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
1023 const sese_l
®ion
= scop
->scop_info
->region
;
1027 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
1029 loop_p loop
= pbb_loop (pbb
);
1030 if (current
== loop
)
1032 pbb
->domain
= isl_set_copy (domain
);
1033 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1034 isl_id_for_pbb (scop
, pbb
));
1037 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
1039 print_isl_set (dump_file
, domain
);
1044 while (loop_in_sese_p (loop
, region
)
1046 loop
= loop_outer (loop
);
1048 if (current
!= loop
)
1050 /* A statement in a different loop nest than CURRENT loop. */
1051 isl_set_free (domain
);
1055 /* A statement nested in the CURRENT loop. */
1056 i
= build_iteration_domains (scop
, domain
, i
, current
);
1060 isl_set_free (domain
);
1065 /* Assign dimension for each parameter in SCOP and add constraints for the
1069 build_scop_context (scop_p scop
)
1071 sese_info_p region
= scop
->scop_info
;
1072 unsigned nbp
= sese_nb_params (region
);
1073 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
1077 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
1078 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
1079 isl_id_for_ssa_name (scop
, e
));
1081 scop
->param_context
= isl_set_universe (space
);
1084 for (p
= 0; p
< nbp
; p
++)
1085 add_param_constraints (scop
, p
);
1088 /* Builds the polyhedral representation for a SESE region. */
1091 build_poly_scop (scop_p scop
)
1093 build_scop_context (scop
);
1096 unsigned n
= scop
->pbbs
.length ();
1098 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1100 if (!add_conditions_to_constraints (scop
))
1103 build_scop_drs (scop
);
1104 build_scop_scattering (scop
);
1107 #endif /* HAVE_isl */