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>
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 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
82 /* Extract an affine expression from the chain of recurrence E. */
85 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
87 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
88 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
89 isl_local_space
*ls
= isl_local_space_from_space (space
);
90 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
91 isl_aff
*loop
= isl_aff_set_coefficient_si
92 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
93 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
95 /* Before multiplying, make sure that the result is affine. */
96 gcc_assert (isl_pw_aff_is_cst (rhs
)
97 || isl_pw_aff_is_cst (l
));
99 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
102 /* Extract an affine expression from the mult_expr E. */
105 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
107 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
108 isl_space_copy (space
));
109 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
111 if (!isl_pw_aff_is_cst (lhs
)
112 && !isl_pw_aff_is_cst (rhs
))
114 isl_pw_aff_free (lhs
);
115 isl_pw_aff_free (rhs
);
119 return isl_pw_aff_mul (lhs
, rhs
);
122 /* Return an isl identifier from the name of the ssa_name E. */
125 isl_id_for_ssa_name (scop_p s
, tree e
)
128 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
129 return isl_id_alloc (s
->isl_context
, name1
, e
);
132 /* Return an isl identifier for the data reference DR. Data references and
133 scalar references get the same isl_id. They need to be comparable and are
134 distinguished through the first dimension, which contains the alias set or
135 SSA_NAME_VERSION number. */
138 isl_id_for_dr (scop_p s
)
140 return isl_id_alloc (s
->isl_context
, "", 0);
143 /* Extract an affine expression from the ssa_name E. */
146 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
148 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
149 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
151 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
152 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
153 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
154 return isl_pw_aff_alloc (dom
, aff
);
157 /* Extract an affine expression from the gmp constant G. */
160 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
162 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
163 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
164 isl_set
*dom
= isl_set_universe (space
);
165 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
166 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
167 aff
= isl_aff_add_constant_val (aff
, v
);
169 return isl_pw_aff_alloc (dom
, aff
);
172 /* Extract an affine expression from the integer_cst E. */
175 extract_affine_int (tree e
, __isl_take isl_space
*space
)
180 tree_int_to_gmp (e
, g
);
181 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
187 /* Compute pwaff mod 2^width. */
190 wrap (isl_pw_aff
*pwaff
, unsigned width
)
194 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
195 mod
= isl_val_2exp (mod
);
196 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
201 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
202 Otherwise returns -1. */
205 parameter_index_in_region_1 (tree name
, sese_info_p region
)
210 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
212 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
219 /* Extract an affine expression from the tree E in the scop S. */
222 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
224 isl_pw_aff
*lhs
, *rhs
, *res
;
226 if (e
== chrec_dont_know
) {
227 isl_space_free (space
);
231 switch (TREE_CODE (e
))
233 case POLYNOMIAL_CHREC
:
234 res
= extract_affine_chrec (s
, e
, space
);
238 res
= extract_affine_mul (s
, e
, space
);
242 case POINTER_PLUS_EXPR
:
243 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
244 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
245 res
= isl_pw_aff_add (lhs
, rhs
);
249 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
250 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
251 res
= isl_pw_aff_sub (lhs
, rhs
);
256 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
257 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
258 res
= isl_pw_aff_mul (lhs
, rhs
);
262 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
263 || defined_in_sese_p (e
, s
->scop_info
->region
));
264 res
= extract_affine_name (s
, e
, space
);
268 res
= extract_affine_int (e
, space
);
269 /* No need to wrap a single integer. */
273 case NON_LVALUE_EXPR
:
274 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
282 tree type
= TREE_TYPE (e
);
283 if (TYPE_UNSIGNED (type
))
284 res
= wrap (res
, TYPE_PRECISION (type
));
289 /* Returns a linear expression for tree T evaluated in PBB. */
292 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
294 scop_p scop
= PBB_SCOP (pbb
);
296 t
= scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
298 gcc_assert (!chrec_contains_undetermined (t
));
299 gcc_assert (!automatically_generated_chrec_p (t
));
301 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
304 /* Add conditional statement STMT to pbb. CODE is used as the comparison
305 operator. This allows us to invert the condition or to handle
309 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
311 loop_p loop
= gimple_bb (stmt
)->loop_father
;
312 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
313 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
319 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
323 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
327 cond
= isl_pw_aff_le_set (lhs
, rhs
);
331 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
335 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
339 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
346 cond
= isl_set_coalesce (cond
);
347 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
348 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
351 /* Add conditions to the domain of PBB. */
354 add_conditions_to_domain (poly_bb_p pbb
)
358 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
360 if (GBB_CONDITIONS (gbb
).is_empty ())
363 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
364 switch (gimple_code (stmt
))
368 /* Don't constrain on anything else than INTEGER_TYPE. */
369 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
372 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
373 enum tree_code code
= gimple_cond_code (cond_stmt
);
375 /* The conditions for ELSE-branches are inverted. */
376 if (!GBB_CONDITION_CASES (gbb
)[i
])
377 code
= invert_tree_comparison (code
, false);
379 add_condition_to_pbb (pbb
, cond_stmt
, code
);
389 /* Add constraints on the possible values of parameter P from the type
393 add_param_constraints (scop_p scop
, graphite_dim_t p
)
395 tree parameter
= scop
->scop_info
->params
[p
];
396 tree type
= TREE_TYPE (parameter
);
400 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
401 lb
= lower_bound_in_type (type
, type
);
403 lb
= TYPE_MIN_VALUE (type
);
405 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
406 ub
= upper_bound_in_type (type
, type
);
408 ub
= TYPE_MAX_VALUE (type
);
412 isl_space
*space
= isl_set_get_space (scop
->param_context
);
417 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
419 tree_int_to_gmp (lb
, g
);
420 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
423 c
= isl_constraint_set_constant_val (c
, v
);
424 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
426 scop
->param_context
= isl_set_coalesce
427 (isl_set_add_constraint (scop
->param_context
, c
));
432 isl_space
*space
= isl_set_get_space (scop
->param_context
);
437 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
440 tree_int_to_gmp (ub
, g
);
441 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
443 c
= isl_constraint_set_constant_val (c
, v
);
444 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
446 scop
->param_context
= isl_set_coalesce
447 (isl_set_add_constraint (scop
->param_context
, c
));
451 /* Add a constrain to the ACCESSES polyhedron for the alias set of
452 data reference DR. ACCESSP_NB_DIMS is the dimension of the
453 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
457 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
459 isl_constraint
*c
= isl_equality_alloc
460 (isl_local_space_from_space (isl_map_get_space (acc
)));
461 /* Positive numbers for all alias sets. */
462 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
463 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
465 return isl_map_add_constraint (acc
, c
);
468 /* Add a constrain to the ACCESSES polyhedron for the alias set of
469 data reference DR. ACCESSP_NB_DIMS is the dimension of the
470 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
474 add_scalar_version_numbers (isl_map
*acc
, tree var
)
476 isl_constraint
*c
= isl_equality_alloc
477 (isl_local_space_from_space (isl_map_get_space (acc
)));
478 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
479 /* Each scalar variables has a unique alias set number starting from
481 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
482 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
484 return isl_map_add_constraint (acc
, c
);
487 /* Assign the affine expression INDEX to the output dimension POS of
488 MAP and return the result. */
491 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
494 int len
= isl_map_dim (map
, isl_dim_out
);
497 index_map
= isl_map_from_pw_aff (index
);
498 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
499 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
501 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
502 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
503 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
504 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
506 return isl_map_intersect (map
, index_map
);
509 /* Add to ACCESSES polyhedron equalities defining the access functions
510 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
511 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
512 PBB is the poly_bb_p that contains the data reference DR. */
515 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
517 data_reference_p dr
= dri
.dr
;
518 poly_bb_p pbb
= dri
.pbb
;
519 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
520 scop_p scop
= PBB_SCOP (pbb
);
522 for (i
= 0; i
< nb_subscripts
; i
++)
525 tree afn
= DR_ACCESS_FN (dr
, i
);
527 aff
= extract_affine (scop
, afn
,
528 isl_space_domain (isl_map_get_space (acc
)));
529 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
532 return isl_map_coalesce (acc
);
535 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
536 to extract constraints on accessed elements of the array. Returning false is
537 the conservative answer. */
540 bounds_are_valid (tree ref
, tree low
, tree high
)
545 if (!tree_fits_shwi_p (low
)
546 || !tree_fits_shwi_p (high
))
549 /* 1-element arrays at end of structures may extend over
550 their declared size. */
551 if (array_at_struct_end_p (ref
)
552 && operand_equal_p (low
, high
, 0))
555 /* Fortran has some arrays where high bound is -1 and low is 0. */
556 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
562 /* Add constrains representing the size of the accessed data to the
563 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
564 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
568 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
571 tree ref
= DR_REF (dr
);
573 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
574 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
576 if (TREE_CODE (ref
) != ARRAY_REF
)
577 return subscript_sizes
;
579 tree low
= array_ref_low_bound (ref
);
580 tree high
= array_ref_up_bound (ref
);
582 if (!bounds_are_valid (ref
, low
, high
))
585 isl_space
*space
= isl_set_get_space (subscript_sizes
);
586 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
587 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
590 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
591 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
592 isl_set_dim (valid
, isl_dim_set
));
593 scop
->param_context
= isl_set_coalesce
594 (isl_set_intersect (scop
->param_context
, valid
));
597 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
598 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
600 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
601 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
603 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
604 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
605 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
607 /* low <= sub_i <= high */
608 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
609 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
610 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
611 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
614 return isl_set_coalesce (subscript_sizes
);
617 /* Build data accesses for DRI. */
620 build_poly_dr (dr_info
&dri
)
623 isl_set
*subscript_sizes
;
624 poly_bb_p pbb
= dri
.pbb
;
625 data_reference_p dr
= dri
.dr
;
626 scop_p scop
= PBB_SCOP (pbb
);
627 isl_id
*id
= isl_id_for_dr (scop
);
630 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
631 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
632 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
633 isl_dim_out
, nb_out
);
635 acc
= isl_map_universe (space
);
636 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
639 acc
= pdr_add_alias_set (acc
, dri
);
640 acc
= pdr_add_memory_accesses (acc
, dri
);
643 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
644 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
646 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
647 subscript_sizes
= isl_set_nat_universe (space
);
648 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
650 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
653 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
654 acc
, subscript_sizes
);
658 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
659 isl_map
*acc
, isl_set
*subscript_sizes
)
661 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
662 /* Each scalar variables has a unique alias set number starting from
664 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
665 max_arrays
+ SSA_NAME_VERSION (var
));
667 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
671 /* Record all cross basic block scalar variables in PBB. */
674 build_poly_sr (poly_bb_p pbb
)
676 scop_p scop
= PBB_SCOP (pbb
);
677 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
678 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
679 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
681 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
683 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
684 isl_dim_out
, nb_out
);
685 isl_id
*id
= isl_id_for_dr (scop
);
686 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
687 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
688 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
689 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
693 FOR_EACH_VEC_ELT (writes
, i
, var
)
694 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
695 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
698 FOR_EACH_VEC_ELT (reads
, i
, use
)
699 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
700 isl_set_copy (subscript_sizes
));
703 isl_set_free (subscript_sizes
);
706 /* Build data references in SCOP. */
709 build_scop_drs (scop_p scop
)
713 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
714 build_poly_dr (*dri
);
717 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
721 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
724 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
726 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
727 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
729 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
730 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
731 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
734 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
737 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
742 const sese_l
®ion
= scop
->scop_info
->region
;
743 if (!loop_in_sese_p (loop
, region
))
746 /* Recursion all the way up to the context loop. */
747 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
749 /* Then, build constraints over the loop in post-order: outer to inner. */
751 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
753 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
754 "domain for loop_%d.\n", loop
->num
);
755 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
756 isl_space
*space
= isl_set_get_space (domain
);
759 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
760 isl_constraint
*c
= isl_inequality_alloc (ls
);
761 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
764 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
765 print_isl_constraint (dump_file
, c
);
767 domain
= isl_set_add_constraint (domain
, c
);
769 tree nb_iters
= number_of_latch_executions (loop
);
770 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
772 /* loop_i <= cst_nb_iters */
773 isl_local_space
*ls
= isl_local_space_from_space (space
);
774 isl_constraint
*c
= isl_inequality_alloc (ls
);
775 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
778 tree_int_to_gmp (nb_iters
, g
);
779 isl_val
*v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
781 c
= isl_constraint_set_constant_val (c
, v
);
782 return isl_set_add_constraint (domain
, c
);
784 /* loop_i <= expr_nb_iters */
785 gcc_assert (!chrec_contains_undetermined (nb_iters
));
786 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
787 gcc_assert (!chrec_contains_undetermined (nb_iters
));
789 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
790 isl_space_copy (space
));
791 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
792 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
793 isl_set_dim (valid
, isl_dim_set
));
796 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
798 ls
= isl_local_space_from_space (isl_space_copy (space
));
799 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
800 isl_dim_in
, loop_index
, 1);
801 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
802 isl_pw_aff_copy (aff_nb_iters
));
805 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
806 print_isl_set (dump_file
, le
);
808 domain
= isl_set_intersect (domain
, le
);
811 if (!max_stmt_executions (loop
, &nit
))
813 isl_pw_aff_free (aff_nb_iters
);
814 isl_space_free (space
);
818 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
819 do not know whether the loop executes at least once. */
822 wi::to_mpz (nit
, g
, SIGNED
);
823 mpz_sub_ui (g
, g
, 1);
825 isl_pw_aff
*approx
= extract_affine_gmp (g
, isl_space_copy (space
));
826 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
827 x
= isl_set_project_out (x
, isl_dim_set
, 0,
828 isl_set_dim (x
, isl_dim_set
));
829 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
831 ls
= isl_local_space_from_space (space
);
832 c
= isl_inequality_alloc (ls
);
833 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
834 isl_val
*v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
836 c
= isl_constraint_set_constant_val (c
, v
);
840 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
841 print_isl_constraint (dump_file
, c
);
844 return isl_set_add_constraint (domain
, c
);
847 /* Builds the original iteration domains for each pbb in the SCOP. */
850 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
851 int index
, loop_p context_loop
)
853 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
854 isl_set
*domain
= isl_set_copy (context
);
855 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
856 const sese_l
®ion
= scop
->scop_info
->region
;
860 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
862 loop_p loop
= pbb_loop (pbb
);
865 pbb
->iterators
= isl_set_copy (domain
);
866 pbb
->domain
= isl_set_copy (domain
);
867 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
868 isl_id_for_pbb (scop
, pbb
));
869 add_conditions_to_domain (pbb
);
873 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
875 print_isl_set (dump_file
, domain
);
880 while (loop_in_sese_p (loop
, region
)
882 loop
= loop_outer (loop
);
886 /* A statement in a different loop nest than CURRENT loop. */
887 isl_set_free (domain
);
891 /* A statement nested in the CURRENT loop. */
892 i
= build_iteration_domains (scop
, domain
, i
, current
);
896 isl_set_free (domain
);
900 /* Assign dimension for each parameter in SCOP and add constraints for the
904 build_scop_context (scop_p scop
)
906 sese_info_p region
= scop
->scop_info
;
907 unsigned nbp
= sese_nb_params (region
);
908 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
912 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
913 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
914 isl_id_for_ssa_name (scop
, e
));
916 scop
->param_context
= isl_set_universe (space
);
919 for (p
= 0; p
< nbp
; p
++)
920 add_param_constraints (scop
, p
);
923 /* Return true when loop A is nested in loop B. */
926 nested_in (loop_p a
, loop_p b
)
928 return b
== find_common_loop (a
, b
);
931 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
933 loop_at (scop_p scop
, int *index
)
935 return pbb_loop (scop
->pbbs
[*index
]);
938 /* Return the index of any pbb belonging to loop or a subloop of A. */
941 index_outermost_in_loop (loop_p a
, scop_p scop
)
943 int i
, outermost
= -1;
946 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
947 if (nested_in (pbb_loop (pbb
), a
)
949 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
952 last_depth
= loop_depth (pbb_loop (pbb
));
957 /* Return the index of any pbb belonging to loop or a subloop of A. */
960 index_pbb_in_loop (loop_p a
, scop_p scop
)
964 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
965 if (pbb_loop (pbb
) == a
)
971 outermost_pbb_in (loop_p loop
, scop_p scop
)
973 int x
= index_pbb_in_loop (loop
, scop
);
975 x
= index_outermost_in_loop (loop
, scop
);
976 return scop
->pbbs
[x
];
979 static isl_schedule
*
980 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
990 return isl_schedule_sequence (a
, b
);
993 struct map_to_dimension_data
{
995 isl_union_pw_multi_aff
*res
;
998 /* Create a function that maps the elements of SET to its N-th dimension and add
1002 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1004 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1005 int dim
= isl_set_dim (set
, isl_dim_set
);
1006 isl_space
*space
= isl_set_get_space (set
);
1008 gcc_assert (dim
>= data
->n
);
1009 isl_pw_multi_aff
*pma
1010 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1012 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1018 /* Return SET in which all inner dimensions above N are removed. */
1020 static isl_multi_union_pw_aff
*
1021 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1023 gcc_assert (n
>= 0);
1025 gcc_assert (!isl_union_set_is_empty (set
));
1027 isl_space
*space
= isl_union_set_get_space (set
);
1028 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1030 struct map_to_dimension_data data
= {n
, pwaff
};
1032 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1033 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1035 isl_union_set_free (set
);
1036 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1039 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1041 static isl_schedule
*
1042 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1045 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1046 isl_set
*iterators
= pbb
->iterators
;
1048 int empty
= isl_set_is_empty (iterators
);
1049 if (empty
< 0 || empty
)
1050 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1052 isl_space
*space
= isl_set_get_space (iterators
);
1053 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1055 loop_p ploop
= pbb_loop (pbb
);
1056 while (loop
!= ploop
)
1059 ploop
= loop_outer (ploop
);
1062 isl_local_space
*ls
= isl_local_space_from_space (space
);
1063 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1064 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1066 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1067 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1069 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1071 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1072 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1073 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1074 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1075 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1078 /* Build schedule for the pbb at INDEX. */
1080 static isl_schedule
*
1081 build_schedule_pbb (scop_p scop
, int *index
)
1083 poly_bb_p pbb
= scop
->pbbs
[*index
];
1085 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1086 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1087 return isl_schedule_from_domain (ud
);
1090 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1092 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1094 static isl_schedule
*
1095 build_schedule_loop (scop_p scop
, int *index
)
1097 int max
= scop
->pbbs
.length ();
1098 gcc_assert (*index
< max
);
1099 loop_p loop
= loop_at (scop
, index
);
1101 isl_schedule
*s
= NULL
;
1102 while (nested_in (loop_at (scop
, index
), loop
))
1104 if (loop
== loop_at (scop
, index
))
1105 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1107 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1113 return add_loop_schedule (s
, loop
, scop
);
1116 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1117 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1118 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1119 maximal loop nest contained within CONTEXT_LOOP. */
1121 static isl_schedule
*
1122 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1123 loop_p loop
, int *index
, loop_p context_loop
)
1125 loop_p outer
= loop_outer (loop
);
1126 sese_l region
= scop
->scop_info
->region
;
1127 if (context_loop
== outer
1128 || !loop_in_sese_p (outer
, region
))
1131 int max
= scop
->pbbs
.length ();
1133 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1135 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1137 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1138 scop
, outer
, index
, context_loop
);
1141 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1142 || nested_in (loop_at (scop
, index
), outer
))
1145 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1147 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1153 /* We reached the end of the OUTER loop: embed S in OUTER. */
1154 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1155 outer
, index
, context_loop
);
1158 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1159 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1160 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1161 nest contained within CONTEXT_LOOP. */
1163 static isl_schedule
*
1164 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1166 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1168 loop_p loop
= loop_at (scop
, index
);
1169 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1170 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1173 /* Build the schedule of the SCOP. */
1176 build_original_schedule (scop_p scop
)
1179 int n
= scop
->pbbs
.length ();
1182 poly_bb_p pbb
= scop
->pbbs
[i
];
1183 isl_schedule
*s
= NULL
;
1184 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1185 s
= build_schedule_pbb (scop
, &i
);
1187 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1189 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1194 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1195 print_isl_schedule (dump_file
, scop
->original_schedule
);
1197 if (!scop
->original_schedule
)
1202 /* Builds the polyhedral representation for a SESE region. */
1205 build_poly_scop (scop_p scop
)
1207 build_scop_context (scop
);
1210 unsigned n
= scop
->pbbs
.length ();
1212 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1214 build_scop_drs (scop
);
1215 build_original_schedule (scop
);
1218 #endif /* HAVE_isl */