1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2017 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
35 #include "fold-const.h"
36 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
40 #include "tree-ssa-loop-manip.h"
41 #include "tree-ssa-loop-niter.h"
42 #include "tree-ssa-loop.h"
43 #include "tree-into-ssa.h"
44 #include "tree-pass.h"
46 #include "tree-data-ref.h"
47 #include "tree-scalar-evolution.h"
49 #include "tree-ssa-propagate.h"
51 #include <isl/constraint.h>
54 #include <isl/union_map.h>
55 #include <isl/constraint.h>
61 /* Assigns to RES the value of the INTEGER_CST T. */
64 tree_int_to_gmp (tree t
, mpz_t res
)
66 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
69 /* Return an isl identifier for the polyhedral basic block PBB. */
72 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
75 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
76 return isl_id_alloc (s
->isl_context
, name
, pbb
);
79 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
81 /* Extract an affine expression from the chain of recurrence E. */
84 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
86 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
87 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
88 isl_local_space
*ls
= isl_local_space_from_space (space
);
89 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
90 isl_aff
*loop
= isl_aff_set_coefficient_si
91 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
92 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
94 /* Before multiplying, make sure that the result is affine. */
95 gcc_assert (isl_pw_aff_is_cst (rhs
)
96 || isl_pw_aff_is_cst (l
));
98 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
101 /* Extract an affine expression from the mult_expr E. */
104 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
106 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
107 isl_space_copy (space
));
108 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
110 if (!isl_pw_aff_is_cst (lhs
)
111 && !isl_pw_aff_is_cst (rhs
))
113 isl_pw_aff_free (lhs
);
114 isl_pw_aff_free (rhs
);
118 return isl_pw_aff_mul (lhs
, rhs
);
121 /* Return an isl identifier from the name of the ssa_name E. */
124 isl_id_for_ssa_name (scop_p s
, tree e
)
127 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
128 return isl_id_alloc (s
->isl_context
, name1
, e
);
131 /* Return an isl identifier for the data reference DR. Data references and
132 scalar references get the same isl_id. They need to be comparable and are
133 distinguished through the first dimension, which contains the alias set or
134 SSA_NAME_VERSION number. */
137 isl_id_for_dr (scop_p s
)
139 return isl_id_alloc (s
->isl_context
, "", 0);
142 /* Extract an affine expression from the ssa_name E. */
145 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
147 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
148 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
150 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
151 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
152 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
153 return isl_pw_aff_alloc (dom
, aff
);
156 /* Convert WI to a isl_val with CTX. */
158 static __isl_give isl_val
*
159 isl_val_int_from_wi (isl_ctx
*ctx
, const widest_int
&wi
)
161 if (wi::neg_p (wi
, SIGNED
))
163 widest_int mwi
= -wi
;
164 return isl_val_neg (isl_val_int_from_chunks (ctx
, mwi
.get_len (),
165 sizeof (HOST_WIDE_INT
),
168 return isl_val_int_from_chunks (ctx
, wi
.get_len (), sizeof (HOST_WIDE_INT
),
172 /* Extract an affine expression from the gmp constant G. */
175 extract_affine_wi (const widest_int
&g
, __isl_take isl_space
*space
)
177 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
178 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
179 isl_set
*dom
= isl_set_universe (space
);
180 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
181 isl_val
*v
= isl_val_int_from_wi (ct
, g
);
182 aff
= isl_aff_add_constant_val (aff
, v
);
184 return isl_pw_aff_alloc (dom
, aff
);
187 /* Extract an affine expression from the integer_cst E. */
190 extract_affine_int (tree e
, __isl_take isl_space
*space
)
192 isl_pw_aff
*res
= extract_affine_wi (wi::to_widest (e
), space
);
196 /* Compute pwaff mod 2^width. */
199 wrap (isl_pw_aff
*pwaff
, unsigned width
)
203 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
204 mod
= isl_val_2exp (mod
);
205 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
210 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
211 Otherwise returns -1. */
214 parameter_index_in_region_1 (tree name
, sese_info_p region
)
219 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
221 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
228 /* Extract an affine expression from the tree E in the scop S. */
231 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
233 isl_pw_aff
*lhs
, *rhs
, *res
;
235 if (e
== chrec_dont_know
) {
236 isl_space_free (space
);
240 tree type
= TREE_TYPE (e
);
241 switch (TREE_CODE (e
))
243 case POLYNOMIAL_CHREC
:
244 res
= extract_affine_chrec (s
, e
, space
);
248 res
= extract_affine_mul (s
, e
, space
);
251 case POINTER_PLUS_EXPR
:
253 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
254 /* The RHS of a pointer-plus expression is to be interpreted
255 as signed value. Try to look through a sign-changing conversion
257 tree tem
= TREE_OPERAND (e
, 1);
259 rhs
= extract_affine (s
, tem
, space
);
260 if (TYPE_UNSIGNED (TREE_TYPE (tem
)))
261 rhs
= wrap (rhs
, TYPE_PRECISION (type
) - 1);
262 res
= isl_pw_aff_add (lhs
, rhs
);
267 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
268 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
269 res
= isl_pw_aff_add (lhs
, rhs
);
273 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
274 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
275 res
= isl_pw_aff_sub (lhs
, rhs
);
279 lhs
= extract_affine (s
, integer_minus_one_node
, isl_space_copy (space
));
280 rhs
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
281 res
= isl_pw_aff_sub (lhs
, rhs
);
285 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
286 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
287 res
= isl_pw_aff_mul (lhs
, rhs
);
291 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
292 || defined_in_sese_p (e
, s
->scop_info
->region
));
293 res
= extract_affine_name (s
, e
, space
);
297 res
= extract_affine_int (e
, space
);
298 /* No need to wrap a single integer. */
302 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
303 /* signed values, even if overflow is undefined, get modulo-reduced. */
304 if (! TYPE_UNSIGNED (type
))
305 res
= wrap (res
, TYPE_PRECISION (type
) - 1);
308 case NON_LVALUE_EXPR
:
309 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
317 if (TYPE_UNSIGNED (type
))
318 res
= wrap (res
, TYPE_PRECISION (type
));
323 /* Returns a linear expression for tree T evaluated in PBB. */
326 create_pw_aff_from_tree (poly_bb_p pbb
, loop_p loop
, tree t
)
328 scop_p scop
= PBB_SCOP (pbb
);
330 t
= scalar_evolution_in_region (scop
->scop_info
->region
, loop
, t
);
332 gcc_assert (!chrec_contains_undetermined (t
));
333 gcc_assert (!automatically_generated_chrec_p (t
));
335 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
338 /* Add conditional statement STMT to pbb. CODE is used as the comparison
339 operator. This allows us to invert the condition or to handle
343 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
345 loop_p loop
= gimple_bb (stmt
)->loop_father
;
346 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_lhs (stmt
));
347 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, loop
, gimple_cond_rhs (stmt
));
353 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
357 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
361 cond
= isl_pw_aff_le_set (lhs
, rhs
);
365 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
369 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
373 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
380 cond
= isl_set_coalesce (cond
);
381 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
382 pbb
->domain
= isl_set_coalesce (isl_set_intersect (pbb
->domain
, cond
));
385 /* Add conditions to the domain of PBB. */
388 add_conditions_to_domain (poly_bb_p pbb
)
392 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
394 if (GBB_CONDITIONS (gbb
).is_empty ())
397 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
398 switch (gimple_code (stmt
))
402 /* Don't constrain on anything else than INTEGER_TYPE. */
403 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
406 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
407 enum tree_code code
= gimple_cond_code (cond_stmt
);
409 /* The conditions for ELSE-branches are inverted. */
410 if (!GBB_CONDITION_CASES (gbb
)[i
])
411 code
= invert_tree_comparison (code
, false);
413 add_condition_to_pbb (pbb
, cond_stmt
, code
);
423 /* Add constraints on the possible values of parameter P from the type
427 add_param_constraints (scop_p scop
, graphite_dim_t p
)
429 tree parameter
= scop
->scop_info
->params
[p
];
430 tree type
= TREE_TYPE (parameter
);
434 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
435 lb
= lower_bound_in_type (type
, type
);
437 lb
= TYPE_MIN_VALUE (type
);
439 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
440 ub
= upper_bound_in_type (type
, type
);
442 ub
= TYPE_MAX_VALUE (type
);
446 isl_space
*space
= isl_set_get_space (scop
->param_context
);
450 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
451 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (lb
));
453 c
= isl_constraint_set_constant_val (c
, v
);
454 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
456 scop
->param_context
= isl_set_coalesce
457 (isl_set_add_constraint (scop
->param_context
, c
));
462 isl_space
*space
= isl_set_get_space (scop
->param_context
);
466 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
468 v
= isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (ub
));
469 c
= isl_constraint_set_constant_val (c
, v
);
470 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
472 scop
->param_context
= isl_set_coalesce
473 (isl_set_add_constraint (scop
->param_context
, c
));
477 /* Add a constrain to the ACCESSES polyhedron for the alias set of
478 data reference DR. ACCESSP_NB_DIMS is the dimension of the
479 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
483 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
485 isl_constraint
*c
= isl_equality_alloc
486 (isl_local_space_from_space (isl_map_get_space (acc
)));
487 /* Positive numbers for all alias sets. */
488 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
489 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
491 return isl_map_add_constraint (acc
, c
);
494 /* Assign the affine expression INDEX to the output dimension POS of
495 MAP and return the result. */
498 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
501 int len
= isl_map_dim (map
, isl_dim_out
);
504 index_map
= isl_map_from_pw_aff (index
);
505 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
506 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
508 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
509 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
510 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
511 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
513 return isl_map_intersect (map
, index_map
);
516 /* Add to ACCESSES polyhedron equalities defining the access functions
517 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
518 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
519 PBB is the poly_bb_p that contains the data reference DR. */
522 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
524 data_reference_p dr
= dri
.dr
;
525 poly_bb_p pbb
= dri
.pbb
;
526 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
527 scop_p scop
= PBB_SCOP (pbb
);
529 for (i
= 0; i
< nb_subscripts
; i
++)
532 tree afn
= DR_ACCESS_FN (dr
, i
);
534 aff
= extract_affine (scop
, afn
,
535 isl_space_domain (isl_map_get_space (acc
)));
536 acc
= set_index (acc
, nb_subscripts
- i
, aff
);
539 return isl_map_coalesce (acc
);
542 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
543 to extract constraints on accessed elements of the array. Returning false is
544 the conservative answer. */
547 bounds_are_valid (tree ref
, tree low
, tree high
)
552 if (!tree_fits_shwi_p (low
)
553 || !tree_fits_shwi_p (high
))
556 /* 1-element arrays at end of structures may extend over
557 their declared size. */
558 if (array_at_struct_end_p (ref
)
559 && operand_equal_p (low
, high
, 0))
562 /* Fortran has some arrays where high bound is -1 and low is 0. */
563 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
569 /* Add constrains representing the size of the accessed data to the
570 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
571 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
575 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
578 tree ref
= DR_REF (dr
);
580 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
581 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
583 if (TREE_CODE (ref
) != ARRAY_REF
)
584 return subscript_sizes
;
586 tree low
= array_ref_low_bound (ref
);
587 tree high
= array_ref_up_bound (ref
);
589 if (!bounds_are_valid (ref
, low
, high
))
592 isl_space
*space
= isl_set_get_space (subscript_sizes
);
593 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
594 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
597 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
598 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
599 isl_set_dim (valid
, isl_dim_set
));
600 scop
->param_context
= isl_set_coalesce
601 (isl_set_intersect (scop
->param_context
, valid
));
604 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
605 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
607 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
608 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
610 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
611 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
612 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
614 /* low <= sub_i <= high */
615 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
616 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
617 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
618 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
621 return isl_set_coalesce (subscript_sizes
);
624 /* Build data accesses for DRI. */
627 build_poly_dr (dr_info
&dri
)
630 isl_set
*subscript_sizes
;
631 poly_bb_p pbb
= dri
.pbb
;
632 data_reference_p dr
= dri
.dr
;
633 scop_p scop
= PBB_SCOP (pbb
);
634 isl_id
*id
= isl_id_for_dr (scop
);
637 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
638 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
639 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
640 isl_dim_out
, nb_out
);
642 acc
= isl_map_universe (space
);
643 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
646 acc
= pdr_add_alias_set (acc
, dri
);
647 acc
= pdr_add_memory_accesses (acc
, dri
);
650 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
651 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
653 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
654 subscript_sizes
= isl_set_nat_universe (space
);
655 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
657 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
660 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
661 acc
, subscript_sizes
);
665 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
666 isl_map
*acc
, isl_set
*subscript_sizes
)
668 scop_p scop
= PBB_SCOP (pbb
);
669 /* Each scalar variables has a unique alias set number starting from
670 the maximum alias set assigned to a dr. */
671 int alias_set
= scop
->max_alias_set
+ SSA_NAME_VERSION (var
);
672 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
675 /* Add a constrain to the ACCESSES polyhedron for the alias set of
676 data reference DR. */
678 = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc
)));
679 c
= isl_constraint_set_constant_si (c
, -alias_set
);
680 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
682 new_poly_dr (pbb
, stmt
, kind
, isl_map_add_constraint (acc
, c
),
686 /* Record all cross basic block scalar variables in PBB. */
689 build_poly_sr (poly_bb_p pbb
)
691 scop_p scop
= PBB_SCOP (pbb
);
692 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
693 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
694 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
696 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
698 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
699 isl_dim_out
, nb_out
);
700 isl_id
*id
= isl_id_for_dr (scop
);
701 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
702 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
703 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
704 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
708 FOR_EACH_VEC_ELT (writes
, i
, var
)
709 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
710 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
713 FOR_EACH_VEC_ELT (reads
, i
, use
)
714 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
715 isl_set_copy (subscript_sizes
));
718 isl_set_free (subscript_sizes
);
721 /* Build data references in SCOP. */
724 build_scop_drs (scop_p scop
)
728 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
729 build_poly_dr (*dri
);
732 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
736 /* Add to the iteration DOMAIN one extra dimension for LOOP->num. */
739 add_iter_domain_dimension (__isl_take isl_set
*domain
, loop_p loop
, scop_p scop
)
741 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
742 domain
= isl_set_add_dims (domain
, isl_dim_set
, 1);
744 snprintf (name
, sizeof(name
), "i%d", loop
->num
);
745 isl_id
*label
= isl_id_alloc (scop
->isl_context
, name
, NULL
);
746 return isl_set_set_dim_id (domain
, isl_dim_set
, loop_index
, label
);
749 /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */
752 add_loop_constraints (scop_p scop
, __isl_take isl_set
*domain
, loop_p loop
,
757 const sese_l
®ion
= scop
->scop_info
->region
;
758 if (!loop_in_sese_p (loop
, region
))
761 /* Recursion all the way up to the context loop. */
762 domain
= add_loop_constraints (scop
, domain
, loop_outer (loop
), context
);
764 /* Then, build constraints over the loop in post-order: outer to inner. */
766 int loop_index
= isl_set_dim (domain
, isl_dim_set
);
768 fprintf (dump_file
, "[sese-to-poly] adding one extra dimension to the "
769 "domain for loop_%d.\n", loop
->num
);
770 domain
= add_iter_domain_dimension (domain
, loop
, scop
);
771 isl_space
*space
= isl_set_get_space (domain
);
774 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
775 isl_constraint
*c
= isl_inequality_alloc (ls
);
776 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, 1);
779 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
780 print_isl_constraint (dump_file
, c
);
782 domain
= isl_set_add_constraint (domain
, c
);
784 tree nb_iters
= number_of_latch_executions (loop
);
785 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
787 /* loop_i <= cst_nb_iters */
788 isl_local_space
*ls
= isl_local_space_from_space (space
);
789 isl_constraint
*c
= isl_inequality_alloc (ls
);
790 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
792 = isl_val_int_from_wi (scop
->isl_context
, wi::to_widest (nb_iters
));
793 c
= isl_constraint_set_constant_val (c
, v
);
794 return isl_set_add_constraint (domain
, c
);
796 /* loop_i <= expr_nb_iters */
797 gcc_assert (!chrec_contains_undetermined (nb_iters
));
798 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
799 gcc_assert (!chrec_contains_undetermined (nb_iters
));
801 isl_pw_aff
*aff_nb_iters
= extract_affine (scop
, nb_iters
,
802 isl_space_copy (space
));
803 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters
));
804 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
805 isl_set_dim (valid
, isl_dim_set
));
808 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
810 ls
= isl_local_space_from_space (isl_space_copy (space
));
811 isl_aff
*loop_i
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
812 isl_dim_in
, loop_index
, 1);
813 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i
),
814 isl_pw_aff_copy (aff_nb_iters
));
817 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
818 print_isl_set (dump_file
, le
);
820 domain
= isl_set_intersect (domain
, le
);
823 if (!max_stmt_executions (loop
, &nit
))
825 isl_pw_aff_free (aff_nb_iters
);
826 isl_space_free (space
);
830 /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
831 do not know whether the loop executes at least once. */
834 isl_pw_aff
*approx
= extract_affine_wi (nit
, isl_space_copy (space
));
835 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff_nb_iters
);
836 x
= isl_set_project_out (x
, isl_dim_set
, 0,
837 isl_set_dim (x
, isl_dim_set
));
838 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
840 ls
= isl_local_space_from_space (space
);
841 c
= isl_inequality_alloc (ls
);
842 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, loop_index
, -1);
843 isl_val
*v
= isl_val_int_from_wi (scop
->isl_context
, nit
);
844 c
= isl_constraint_set_constant_val (c
, v
);
848 fprintf (dump_file
, "[sese-to-poly] adding constraint to the domain: ");
849 print_isl_constraint (dump_file
, c
);
852 return isl_set_add_constraint (domain
, c
);
855 /* Builds the original iteration domains for each pbb in the SCOP. */
858 build_iteration_domains (scop_p scop
, __isl_keep isl_set
*context
,
859 int index
, loop_p context_loop
)
861 loop_p current
= pbb_loop (scop
->pbbs
[index
]);
862 isl_set
*domain
= isl_set_copy (context
);
863 domain
= add_loop_constraints (scop
, domain
, current
, context_loop
);
864 const sese_l
®ion
= scop
->scop_info
->region
;
868 FOR_EACH_VEC_ELT_FROM (scop
->pbbs
, i
, pbb
, index
)
870 loop_p loop
= pbb_loop (pbb
);
873 pbb
->iterators
= isl_set_copy (domain
);
874 pbb
->domain
= isl_set_copy (domain
);
875 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
876 isl_id_for_pbb (scop
, pbb
));
877 add_conditions_to_domain (pbb
);
881 fprintf (dump_file
, "[sese-to-poly] set pbb_%d->domain: ",
883 print_isl_set (dump_file
, domain
);
888 while (loop_in_sese_p (loop
, region
)
890 loop
= loop_outer (loop
);
894 /* A statement in a different loop nest than CURRENT loop. */
895 isl_set_free (domain
);
899 /* A statement nested in the CURRENT loop. */
900 i
= build_iteration_domains (scop
, domain
, i
, current
);
904 isl_set_free (domain
);
908 /* Assign dimension for each parameter in SCOP and add constraints for the
912 build_scop_context (scop_p scop
)
914 sese_info_p region
= scop
->scop_info
;
915 unsigned nbp
= sese_nb_params (region
);
916 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
920 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
921 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
922 isl_id_for_ssa_name (scop
, e
));
924 scop
->param_context
= isl_set_universe (space
);
927 for (p
= 0; p
< nbp
; p
++)
928 add_param_constraints (scop
, p
);
931 /* Return true when loop A is nested in loop B. */
934 nested_in (loop_p a
, loop_p b
)
936 return b
== find_common_loop (a
, b
);
939 /* Return the loop at a specific SCOP->pbbs[*INDEX]. */
941 loop_at (scop_p scop
, int *index
)
943 return pbb_loop (scop
->pbbs
[*index
]);
946 /* Return the index of any pbb belonging to loop or a subloop of A. */
949 index_outermost_in_loop (loop_p a
, scop_p scop
)
951 int i
, outermost
= -1;
954 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
955 if (nested_in (pbb_loop (pbb
), a
)
957 || last_depth
> (int) loop_depth (pbb_loop (pbb
))))
960 last_depth
= loop_depth (pbb_loop (pbb
));
965 /* Return the index of any pbb belonging to loop or a subloop of A. */
968 index_pbb_in_loop (loop_p a
, scop_p scop
)
972 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
973 if (pbb_loop (pbb
) == a
)
979 outermost_pbb_in (loop_p loop
, scop_p scop
)
981 int x
= index_pbb_in_loop (loop
, scop
);
983 x
= index_outermost_in_loop (loop
, scop
);
984 return scop
->pbbs
[x
];
987 static isl_schedule
*
988 add_in_sequence (__isl_take isl_schedule
*a
, __isl_take isl_schedule
*b
)
998 return isl_schedule_sequence (a
, b
);
1001 struct map_to_dimension_data
{
1003 isl_union_pw_multi_aff
*res
;
1006 /* Create a function that maps the elements of SET to its N-th dimension and add
1010 add_outer_projection (__isl_take isl_set
*set
, void *user
)
1012 struct map_to_dimension_data
*data
= (struct map_to_dimension_data
*) user
;
1013 int dim
= isl_set_dim (set
, isl_dim_set
);
1014 isl_space
*space
= isl_set_get_space (set
);
1016 gcc_assert (dim
>= data
->n
);
1017 isl_pw_multi_aff
*pma
1018 = isl_pw_multi_aff_project_out_map (space
, isl_dim_set
, data
->n
,
1020 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff (data
->res
, pma
);
1026 /* Return SET in which all inner dimensions above N are removed. */
1028 static isl_multi_union_pw_aff
*
1029 outer_projection_mupa (__isl_take isl_union_set
*set
, int n
)
1031 gcc_assert (n
>= 0);
1033 gcc_assert (!isl_union_set_is_empty (set
));
1035 isl_space
*space
= isl_union_set_get_space (set
);
1036 isl_union_pw_multi_aff
*pwaff
= isl_union_pw_multi_aff_empty (space
);
1038 struct map_to_dimension_data data
= {n
, pwaff
};
1040 if (isl_union_set_foreach_set (set
, &add_outer_projection
, &data
) < 0)
1041 data
.res
= isl_union_pw_multi_aff_free (data
.res
);
1043 isl_union_set_free (set
);
1044 return isl_multi_union_pw_aff_from_union_pw_multi_aff (data
.res
);
1047 static bool schedule_error
;
1049 /* Embed SCHEDULE in the constraints of the LOOP domain. */
1051 static isl_schedule
*
1052 add_loop_schedule (__isl_take isl_schedule
*schedule
, loop_p loop
,
1055 poly_bb_p pbb
= outermost_pbb_in (loop
, scop
);
1056 isl_set
*iterators
= pbb
->iterators
;
1058 int empty
= isl_set_is_empty (iterators
);
1059 if (empty
< 0 || empty
)
1060 return empty
< 0 ? isl_schedule_free (schedule
) : schedule
;
1062 isl_union_set
*domain
= isl_schedule_get_domain (schedule
);
1063 /* We cannot apply an empty domain to pbbs in this loop so fail.
1064 ??? Somehow drop pbbs in the loop instead. */
1065 if (isl_union_set_is_empty (domain
))
1067 schedule_error
= true;
1068 isl_union_set_free (domain
);
1072 isl_space
*space
= isl_set_get_space (iterators
);
1073 int loop_index
= isl_space_dim (space
, isl_dim_set
) - 1;
1075 loop_p ploop
= pbb_loop (pbb
);
1076 while (loop
!= ploop
)
1079 ploop
= loop_outer (ploop
);
1082 isl_local_space
*ls
= isl_local_space_from_space (space
);
1083 isl_aff
*aff
= isl_aff_var_on_domain (ls
, isl_dim_set
, loop_index
);
1084 isl_multi_aff
*prefix
= isl_multi_aff_from_aff (aff
);
1086 snprintf (name
, sizeof(name
), "L_%d", loop
->num
);
1087 isl_id
*label
= isl_id_alloc (isl_schedule_get_ctx (schedule
),
1089 prefix
= isl_multi_aff_set_tuple_id (prefix
, isl_dim_out
, label
);
1091 int n
= isl_multi_aff_dim (prefix
, isl_dim_in
);
1092 isl_multi_union_pw_aff
*mupa
= outer_projection_mupa (domain
, n
);
1093 mupa
= isl_multi_union_pw_aff_apply_multi_aff (mupa
, prefix
);
1094 return isl_schedule_insert_partial_schedule (schedule
, mupa
);
1097 /* Build schedule for the pbb at INDEX. */
1099 static isl_schedule
*
1100 build_schedule_pbb (scop_p scop
, int *index
)
1102 poly_bb_p pbb
= scop
->pbbs
[*index
];
1104 isl_set
*domain
= isl_set_copy (pbb
->domain
);
1105 isl_union_set
*ud
= isl_union_set_from_set (domain
);
1106 return isl_schedule_from_domain (ud
);
1109 static isl_schedule
*build_schedule_loop_nest (scop_p
, int *, loop_p
);
1111 /* Build the schedule of the loop containing the SCOP pbb at INDEX. */
1113 static isl_schedule
*
1114 build_schedule_loop (scop_p scop
, int *index
)
1116 int max
= scop
->pbbs
.length ();
1117 gcc_assert (*index
< max
);
1118 loop_p loop
= loop_at (scop
, index
);
1120 isl_schedule
*s
= NULL
;
1121 while (nested_in (loop_at (scop
, index
), loop
))
1123 if (loop
== loop_at (scop
, index
))
1124 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1126 s
= add_in_sequence (s
, build_schedule_loop_nest (scop
, index
, loop
));
1132 return add_loop_schedule (s
, loop
, scop
);
1135 /* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops.
1136 When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
1137 SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the
1138 maximal loop nest contained within CONTEXT_LOOP. */
1140 static isl_schedule
*
1141 embed_in_surrounding_loops (__isl_take isl_schedule
*s
, scop_p scop
,
1142 loop_p loop
, int *index
, loop_p context_loop
)
1144 loop_p outer
= loop_outer (loop
);
1145 sese_l region
= scop
->scop_info
->region
;
1146 if (context_loop
== outer
1147 || !loop_in_sese_p (outer
, region
))
1150 int max
= scop
->pbbs
.length ();
1152 || (context_loop
&& !nested_in (loop_at (scop
, index
), context_loop
))
1154 && !loop_in_sese_p (find_common_loop (outer
, loop_at (scop
, index
)),
1156 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
),
1157 scop
, outer
, index
, context_loop
);
1160 while ((a_pbb
= (outer
== loop_at (scop
, index
)))
1161 || nested_in (loop_at (scop
, index
), outer
))
1164 s
= add_in_sequence (s
, build_schedule_pbb (scop
, index
));
1166 s
= add_in_sequence (s
, build_schedule_loop (scop
, index
));
1172 /* We reached the end of the OUTER loop: embed S in OUTER. */
1173 return embed_in_surrounding_loops (add_loop_schedule (s
, outer
, scop
), scop
,
1174 outer
, index
, context_loop
);
1177 /* Build schedule for the full loop nest containing the pbb at INDEX. When
1178 CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
1179 surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop
1180 nest contained within CONTEXT_LOOP. */
1182 static isl_schedule
*
1183 build_schedule_loop_nest (scop_p scop
, int *index
, loop_p context_loop
)
1185 gcc_assert (*index
!= (int) scop
->pbbs
.length ());
1187 loop_p loop
= loop_at (scop
, index
);
1188 isl_schedule
*s
= build_schedule_loop (scop
, index
);
1189 return embed_in_surrounding_loops (s
, scop
, loop
, index
, context_loop
);
1192 /* Build the schedule of the SCOP. */
1195 build_original_schedule (scop_p scop
)
1197 schedule_error
= false;
1200 int n
= scop
->pbbs
.length ();
1203 poly_bb_p pbb
= scop
->pbbs
[i
];
1204 isl_schedule
*s
= NULL
;
1205 if (!loop_in_sese_p (pbb_loop (pbb
), scop
->scop_info
->region
))
1206 s
= build_schedule_pbb (scop
, &i
);
1208 s
= build_schedule_loop_nest (scop
, &i
, NULL
);
1210 scop
->original_schedule
= add_in_sequence (scop
->original_schedule
, s
);
1216 fprintf (dump_file
, "[sese-to-poly] failed to build "
1217 "original schedule\n");
1223 fprintf (dump_file
, "[sese-to-poly] original schedule:\n");
1224 print_isl_schedule (dump_file
, scop
->original_schedule
);
1226 if (!scop
->original_schedule
)
1231 /* Builds the polyhedral representation for a SESE region. */
1234 build_poly_scop (scop_p scop
)
1236 int old_err
= isl_options_get_on_error (scop
->isl_context
);
1237 isl_options_set_on_error (scop
->isl_context
, ISL_ON_ERROR_CONTINUE
);
1239 build_scop_context (scop
);
1242 unsigned n
= scop
->pbbs
.length ();
1244 i
= build_iteration_domains (scop
, scop
->param_context
, i
, NULL
);
1246 build_scop_drs (scop
);
1247 build_original_schedule (scop
);
1249 enum isl_error err
= isl_ctx_last_error (scop
->isl_context
);
1250 isl_ctx_reset_error (scop
->isl_context
);
1251 isl_options_set_on_error (scop
->isl_context
, old_err
);
1252 if (err
!= isl_error_none
)
1253 dump_printf (MSG_MISSED_OPTIMIZATION
,
1254 "ISL error while building poly scop\n");
1256 return err
== isl_error_none
;
1258 #endif /* HAVE_isl */