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 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
149 /* Build for BB the static schedule.
151 The static schedule is a Dewey numbering of the abstract syntax
152 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
154 The following example informally defines the static schedule:
173 Static schedules for A to F:
186 build_scop_scattering (scop_p scop
)
188 gimple_poly_bb_p previous_gbb
= NULL
;
189 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
190 isl_aff
*static_sched
;
192 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
193 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
195 /* We have to start schedules at 0 on the first component and
196 because we cannot compare_prefix_loops against a previous loop,
197 prefix will be equal to zero, and that index will be
198 incremented before copying. */
199 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
203 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
205 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
209 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
213 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
215 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
218 isl_aff_free (static_sched
);
221 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
223 /* Extract an affine expression from the chain of recurrence E. */
226 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
228 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
229 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
230 isl_local_space
*ls
= isl_local_space_from_space (space
);
231 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
232 isl_aff
*loop
= isl_aff_set_coefficient_si
233 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
234 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
236 /* Before multiplying, make sure that the result is affine. */
237 gcc_assert (isl_pw_aff_is_cst (rhs
)
238 || isl_pw_aff_is_cst (l
));
240 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
243 /* Extract an affine expression from the mult_expr E. */
246 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
248 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
249 isl_space_copy (space
));
250 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
252 if (!isl_pw_aff_is_cst (lhs
)
253 && !isl_pw_aff_is_cst (rhs
))
255 isl_pw_aff_free (lhs
);
256 isl_pw_aff_free (rhs
);
260 return isl_pw_aff_mul (lhs
, rhs
);
263 /* Return an isl identifier from the name of the ssa_name E. */
266 isl_id_for_ssa_name (scop_p s
, tree e
)
269 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
270 return isl_id_alloc (s
->isl_context
, name1
, e
);
273 /* Return an isl identifier for the data reference DR. Data references and
274 scalar references get the same isl_id. They need to be comparable and are
275 distinguished through the first dimension, which contains the alias set or
276 SSA_NAME_VERSION number. */
279 isl_id_for_dr (scop_p s
)
281 return isl_id_alloc (s
->isl_context
, "", 0);
284 /* Extract an affine expression from the ssa_name E. */
287 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
289 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
290 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
292 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
293 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
294 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
295 return isl_pw_aff_alloc (dom
, aff
);
298 /* Extract an affine expression from the gmp constant G. */
301 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
303 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
304 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
305 isl_set
*dom
= isl_set_universe (space
);
306 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
307 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
308 aff
= isl_aff_add_constant_val (aff
, v
);
310 return isl_pw_aff_alloc (dom
, aff
);
313 /* Extract an affine expression from the integer_cst E. */
316 extract_affine_int (tree e
, __isl_take isl_space
*space
)
321 tree_int_to_gmp (e
, g
);
322 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
328 /* Compute pwaff mod 2^width. */
331 wrap (isl_pw_aff
*pwaff
, unsigned width
)
335 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
336 mod
= isl_val_2exp (mod
);
337 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
342 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
343 Otherwise returns -1. */
346 parameter_index_in_region_1 (tree name
, sese_info_p region
)
351 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
353 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
360 /* Extract an affine expression from the tree E in the scop S. */
363 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
365 isl_pw_aff
*lhs
, *rhs
, *res
;
367 if (e
== chrec_dont_know
) {
368 isl_space_free (space
);
372 switch (TREE_CODE (e
))
374 case POLYNOMIAL_CHREC
:
375 res
= extract_affine_chrec (s
, e
, space
);
379 res
= extract_affine_mul (s
, e
, space
);
383 case POINTER_PLUS_EXPR
:
384 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
385 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
386 res
= isl_pw_aff_add (lhs
, rhs
);
390 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
391 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
392 res
= isl_pw_aff_sub (lhs
, rhs
);
397 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
398 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
399 res
= isl_pw_aff_mul (lhs
, rhs
);
403 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
404 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
405 res
= extract_affine_name (s
, e
, space
);
409 res
= extract_affine_int (e
, space
);
410 /* No need to wrap a single integer. */
414 case NON_LVALUE_EXPR
:
415 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
423 tree type
= TREE_TYPE (e
);
424 if (TYPE_UNSIGNED (type
))
425 res
= wrap (res
, TYPE_PRECISION (type
));
430 /* Assign dimension for each parameter in SCOP. */
433 set_scop_parameter_dim (scop_p scop
)
435 sese_info_p region
= scop
->scop_info
;
436 unsigned nbp
= sese_nb_params (region
);
437 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
441 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
442 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
443 isl_id_for_ssa_name (scop
, e
));
445 scop
->param_context
= isl_set_universe (space
);
449 cleanup_loop_iter_dom (isl_set
*inner
, isl_set
*outer
, isl_space
*space
, mpz_t g
)
451 isl_set_free (inner
);
452 isl_set_free (outer
);
453 isl_space_free (space
);
458 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
459 the constraints for the surrounding loops. */
462 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
464 isl_set
*outer
, isl_set
**doms
)
467 tree nb_iters
= number_of_latch_executions (loop
);
468 const sese_l
& region
= scop
->scop_info
->region
;
469 gcc_assert (loop_in_sese_p (loop
, region
));
471 isl_set
*inner
= isl_set_copy (outer
);
472 int pos
= isl_set_dim (outer
, isl_dim_set
);
478 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
479 isl_space
*space
= isl_set_get_space (inner
);
482 isl_constraint
*c
= isl_inequality_alloc
483 (isl_local_space_from_space (isl_space_copy (space
)));
484 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
485 inner
= isl_set_add_constraint (inner
, c
);
487 /* loop_i <= cst_nb_iters */
488 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
490 c
= isl_inequality_alloc
491 (isl_local_space_from_space (isl_space_copy (space
)));
492 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
493 tree_int_to_gmp (nb_iters
, g
);
494 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
495 c
= isl_constraint_set_constant_val (c
, v
);
496 inner
= isl_set_add_constraint (inner
, c
);
499 /* loop_i <= expr_nb_iters */
500 else if (!chrec_contains_undetermined (nb_iters
))
504 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
506 /* Bail out as we do not know the scev. */
507 if (chrec_contains_undetermined (nb_iters
))
508 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
510 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
511 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
512 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
513 isl_set_dim (valid
, isl_dim_set
));
516 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
518 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
519 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
521 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
522 isl_pw_aff_copy (aff
));
523 inner
= isl_set_intersect (inner
, le
);
526 if (max_stmt_executions (loop
, &nit
))
528 /* Insert in the context the constraints from the
529 estimation of the number of iterations NIT and the
530 symbolic number of iterations (involving parameter
531 names) NB_ITERS. First, build the affine expression
532 "NIT - NB_ITERS" and then say that it is positive,
533 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
536 wi::to_mpz (nit
, g
, SIGNED
);
537 mpz_sub_ui (g
, g
, 1);
540 = extract_affine_gmp (g
, isl_set_get_space (inner
));
541 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
542 x
= isl_set_project_out (x
, isl_dim_set
, 0,
543 isl_set_dim (x
, isl_dim_set
));
544 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
546 isl_constraint
*c
= isl_inequality_alloc
547 (isl_local_space_from_space (isl_space_copy (space
)));
548 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
549 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
551 c
= isl_constraint_set_constant_val (c
, v
);
552 inner
= isl_set_add_constraint (inner
, c
);
555 isl_pw_aff_free (aff
);
561 && !build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
562 isl_set_copy (inner
), doms
))
563 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
567 && loop_in_sese_p (loop
->next
, region
)
568 && !build_loop_iteration_domains (scop
, loop
->next
, nb
,
569 isl_set_copy (outer
), doms
))
570 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
572 doms
[loop
->num
] = inner
;
574 isl_set_free (outer
);
575 isl_space_free (space
);
580 /* Returns a linear expression for tree T evaluated in PBB. */
583 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
585 scop_p scop
= PBB_SCOP (pbb
);
587 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
589 /* Bail out as we do not know the scev. */
590 if (chrec_contains_undetermined (t
))
593 gcc_assert (!automatically_generated_chrec_p (t
));
595 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
598 /* Add conditional statement STMT to pbb. CODE is used as the comparison
599 operator. This allows us to invert the condition or to handle
603 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
605 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
609 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
612 isl_pw_aff_free (lhs
);
620 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
624 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
628 cond
= isl_pw_aff_le_set (lhs
, rhs
);
632 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
636 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
640 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
644 isl_pw_aff_free (lhs
);
645 isl_pw_aff_free (rhs
);
649 cond
= isl_set_coalesce (cond
);
650 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
651 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
655 /* Add conditions to the domain of PBB. */
658 add_conditions_to_domain (poly_bb_p pbb
)
662 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
664 if (GBB_CONDITIONS (gbb
).is_empty ())
667 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
668 switch (gimple_code (stmt
))
672 /* Don't constrain on anything else than INTEGER_TYPE. */
673 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
676 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
677 enum tree_code code
= gimple_cond_code (cond_stmt
);
679 /* The conditions for ELSE-branches are inverted. */
680 if (!GBB_CONDITION_CASES (gbb
)[i
])
681 code
= invert_tree_comparison (code
, false);
683 if (!add_condition_to_pbb (pbb
, cond_stmt
, code
))
689 /* Switch statements are not supported right now - fall through. */
699 /* Traverses all the GBBs of the SCOP and add their constraints to the
700 iteration domains. */
703 add_conditions_to_constraints (scop_p scop
)
708 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
709 if (!add_conditions_to_domain (pbb
))
715 /* Add constraints on the possible values of parameter P from the type
719 add_param_constraints (scop_p scop
, graphite_dim_t p
)
721 tree parameter
= scop
->scop_info
->params
[p
];
722 tree type
= TREE_TYPE (parameter
);
726 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
727 lb
= lower_bound_in_type (type
, type
);
729 lb
= TYPE_MIN_VALUE (type
);
731 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
732 ub
= upper_bound_in_type (type
, type
);
734 ub
= TYPE_MAX_VALUE (type
);
738 isl_space
*space
= isl_set_get_space (scop
->param_context
);
743 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
745 tree_int_to_gmp (lb
, g
);
746 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
749 c
= isl_constraint_set_constant_val (c
, v
);
750 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
752 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
757 isl_space
*space
= isl_set_get_space (scop
->param_context
);
762 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
765 tree_int_to_gmp (ub
, g
);
766 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
768 c
= isl_constraint_set_constant_val (c
, v
);
769 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
771 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
775 /* Build the context of the SCOP. The context usually contains extra
776 constraints that are added to the iteration domains that constrain
780 build_scop_context (scop_p scop
)
782 graphite_dim_t p
, n
= scop_nb_params (scop
);
784 for (p
= 0; p
< n
; p
++)
785 add_param_constraints (scop
, p
);
788 /* Build the iteration domains: the loops belonging to the current
789 SCOP, and that vary for the execution of the current basic block.
790 Returns false if there is no loop in SCOP. */
793 build_scop_iteration_domain (scop_p scop
)
795 sese_info_p region
= scop
->scop_info
;
796 int nb_loops
= number_of_loops (cfun
);
797 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
801 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
802 if (!loop_in_sese_p (loop_outer (loop
), region
->region
)
803 && !build_loop_iteration_domains (scop
, loop
, 0,
804 isl_set_copy (scop
->param_context
), doms
))
811 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
813 loop
= pbb_loop (pbb
);
816 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
818 pbb
->domain
= isl_set_copy (scop
->param_context
);
820 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
821 isl_id_for_pbb (scop
, pbb
));
825 for (int i
= 0; i
< nb_loops
; i
++)
827 isl_set_free (doms
[i
]);
833 /* Add a constrain to the ACCESSES polyhedron for the alias set of
834 data reference DR. ACCESSP_NB_DIMS is the dimension of the
835 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
839 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
841 isl_constraint
*c
= isl_equality_alloc
842 (isl_local_space_from_space (isl_map_get_space (acc
)));
843 /* Positive numbers for all alias sets. */
844 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
845 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
847 return isl_map_add_constraint (acc
, c
);
850 /* Add a constrain to the ACCESSES polyhedron for the alias set of
851 data reference DR. ACCESSP_NB_DIMS is the dimension of the
852 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
856 add_scalar_version_numbers (isl_map
*acc
, tree var
)
858 isl_constraint
*c
= isl_equality_alloc
859 (isl_local_space_from_space (isl_map_get_space (acc
)));
860 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
861 /* Each scalar variables has a unique alias set number starting from
863 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
864 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
866 return isl_map_add_constraint (acc
, c
);
869 /* Assign the affine expression INDEX to the output dimension POS of
870 MAP and return the result. */
873 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
876 int len
= isl_map_dim (map
, isl_dim_out
);
879 index_map
= isl_map_from_pw_aff (index
);
880 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
881 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
883 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
884 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
885 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
886 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
888 return isl_map_intersect (map
, index_map
);
891 /* Add to ACCESSES polyhedron equalities defining the access functions
892 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
893 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
894 PBB is the poly_bb_p that contains the data reference DR. */
897 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
899 data_reference_p dr
= dri
.dr
;
900 poly_bb_p pbb
= dri
.pbb
;
901 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
902 scop_p scop
= PBB_SCOP (pbb
);
904 for (i
= 0; i
< nb_subscripts
; i
++)
907 tree afn
= DR_ACCESS_FN (dr
, i
);
909 aff
= extract_affine (scop
, afn
,
910 isl_space_domain (isl_map_get_space (acc
)));
911 acc
= set_index (acc
, i
+ 1, aff
);
917 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
918 to extract constraints on accessed elements of the array. Returning false is
919 the conservative answer. */
922 bounds_are_valid (tree ref
, tree low
, tree high
)
927 if (!tree_fits_shwi_p (low
)
928 || !tree_fits_shwi_p (high
))
931 /* 1-element arrays at end of structures may extend over
932 their declared size. */
933 if (array_at_struct_end_p (ref
)
934 && operand_equal_p (low
, high
, 0))
937 /* Fortran has some arrays where high bound is -1 and low is 0. */
938 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
944 /* Add constrains representing the size of the accessed data to the
945 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
946 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
950 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
953 tree ref
= DR_REF (dr
);
955 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
956 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
958 if (TREE_CODE (ref
) != ARRAY_REF
)
959 return subscript_sizes
;
961 tree low
= array_ref_low_bound (ref
);
962 tree high
= array_ref_up_bound (ref
);
964 if (!bounds_are_valid (ref
, low
, high
))
967 isl_space
*space
= isl_set_get_space (subscript_sizes
);
968 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
969 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
972 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
973 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
974 isl_set_dim (valid
, isl_dim_set
));
975 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
978 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
979 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
981 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
982 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
984 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
985 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
986 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
988 /* low <= sub_i <= high */
989 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
990 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
991 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
992 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
995 return subscript_sizes
;
998 /* Build data accesses for DRI. */
1001 build_poly_dr (dr_info
&dri
)
1004 isl_set
*subscript_sizes
;
1005 poly_bb_p pbb
= dri
.pbb
;
1006 data_reference_p dr
= dri
.dr
;
1007 scop_p scop
= PBB_SCOP (pbb
);
1008 isl_id
*id
= isl_id_for_dr (scop
);
1011 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1012 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1013 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1014 isl_dim_out
, nb_out
);
1016 acc
= isl_map_universe (space
);
1017 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
1020 acc
= pdr_add_alias_set (acc
, dri
);
1021 acc
= pdr_add_memory_accesses (acc
, dri
);
1024 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1025 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1027 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1028 subscript_sizes
= isl_set_nat_universe (space
);
1029 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1031 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1034 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1035 acc
, subscript_sizes
);
1039 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
1040 isl_map
*acc
, isl_set
*subscript_sizes
)
1042 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1043 /* Each scalar variables has a unique alias set number starting from
1045 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1046 max_arrays
+ SSA_NAME_VERSION (var
));
1048 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
1052 /* Record all cross basic block scalar variables in PBB. */
1055 build_poly_sr (poly_bb_p pbb
)
1057 scop_p scop
= PBB_SCOP (pbb
);
1058 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1059 vec
<scalar_use
> &reads
= gbb
->read_scalar_refs
;
1060 vec
<tree
> &writes
= gbb
->write_scalar_refs
;
1062 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1064 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1065 isl_dim_out
, nb_out
);
1066 isl_id
*id
= isl_id_for_dr (scop
);
1067 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
1068 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
1069 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
1070 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
1074 FOR_EACH_VEC_ELT (writes
, i
, var
)
1075 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
1076 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
1079 FOR_EACH_VEC_ELT (reads
, i
, use
)
1080 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
1081 isl_set_copy (subscript_sizes
));
1084 isl_set_free (subscript_sizes
);
1087 /* Build data references in SCOP. */
1090 build_scop_drs (scop_p scop
)
1094 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1095 build_poly_dr (*dri
);
1098 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1099 build_poly_sr (pbb
);
1102 /* Builds the polyhedral representation for a SESE region. */
1105 build_poly_scop (scop_p scop
)
1107 set_scop_parameter_dim (scop
);
1108 if (!build_scop_iteration_domain (scop
))
1111 build_scop_context (scop
);
1113 if (!add_conditions_to_constraints (scop
))
1116 build_scop_drs (scop
);
1117 build_scop_scattering (scop
);
1120 #endif /* HAVE_isl */