1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2015 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>
59 /* Since ISL-0.13, the extern is in val_gmp.h. */
60 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
63 #include <isl/val_gmp.h>
64 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
70 /* Assigns to RES the value of the INTEGER_CST T. */
73 tree_int_to_gmp (tree t
, mpz_t res
)
75 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
78 /* Return an ISL identifier for the polyhedral basic block PBB. */
81 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
84 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
85 return isl_id_alloc (s
->isl_context
, name
, pbb
);
88 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
89 We generate SCATTERING_DIMENSIONS scattering dimensions.
91 The scattering polyhedron consists of these dimensions: scattering,
92 loop_iterators, parameters.
96 | scattering_dimensions = 5
104 | Scattering polyhedron:
106 | scattering: {s1, s2, s3, s4, s5}
107 | loop_iterators: {i}
108 | parameters: {p1, p2}
110 | s1 s2 s3 s4 s5 i p1 p2 1
111 | 1 0 0 0 0 0 0 0 -4 = 0
112 | 0 1 0 0 0 -1 0 0 0 = 0
113 | 0 0 1 0 0 0 0 0 -5 = 0 */
116 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
121 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
123 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
124 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
),
125 isl_dim_out
, scattering_dimensions
);
126 pbb
->schedule
= isl_map_universe (dm
);
128 for (int i
= 0; i
< scattering_dimensions
; i
++)
130 /* Textual order inside this loop. */
133 isl_constraint
*c
= isl_equality_alloc
134 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
136 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
137 gcc_assert (val
&& isl_val_is_int (val
));
139 val
= isl_val_neg (val
);
140 c
= isl_constraint_set_constant_val (c
, val
);
141 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
142 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
145 /* Iterations of this loop. */
146 else /* if ((i % 2) == 1) */
148 int loop
= (i
- 1) / 2;
149 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
154 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
157 /* Build for BB the static schedule.
159 The static schedule is a Dewey numbering of the abstract syntax
160 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
162 The following example informally defines the static schedule:
181 Static schedules for A to F:
194 build_scop_scattering (scop_p scop
)
196 gimple_poly_bb_p previous_gbb
= NULL
;
197 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
198 isl_aff
*static_sched
;
200 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
201 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
203 /* We have to start schedules at 0 on the first component and
204 because we cannot compare_prefix_loops against a previous loop,
205 prefix will be equal to zero, and that index will be
206 incremented before copying. */
207 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
211 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
213 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
217 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
221 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
223 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
226 isl_aff_free (static_sched
);
229 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
231 /* Extract an affine expression from the chain of recurrence E. */
234 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
236 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
237 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
238 isl_local_space
*ls
= isl_local_space_from_space (space
);
239 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
240 isl_aff
*loop
= isl_aff_set_coefficient_si
241 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
242 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
244 /* Before multiplying, make sure that the result is affine. */
245 gcc_assert (isl_pw_aff_is_cst (rhs
)
246 || isl_pw_aff_is_cst (l
));
248 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
251 /* Extract an affine expression from the mult_expr E. */
254 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
256 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
257 isl_space_copy (space
));
258 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
260 if (!isl_pw_aff_is_cst (lhs
)
261 && !isl_pw_aff_is_cst (rhs
))
263 isl_pw_aff_free (lhs
);
264 isl_pw_aff_free (rhs
);
268 return isl_pw_aff_mul (lhs
, rhs
);
271 /* Return an ISL identifier from the name of the ssa_name E. */
274 isl_id_for_ssa_name (scop_p s
, tree e
)
277 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
278 return isl_id_alloc (s
->isl_context
, name1
, e
);
281 /* Return an ISL identifier for the data reference DR. Data references and
282 scalar references get the same isl_id. They need to be comparable and are
283 distinguished through the first dimension, which contains the alias set or
284 SSA_NAME_VERSION number. */
287 isl_id_for_dr (scop_p s
)
289 return isl_id_alloc (s
->isl_context
, "", 0);
292 /* Extract an affine expression from the ssa_name E. */
295 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
297 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
298 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
300 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
301 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
302 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
303 return isl_pw_aff_alloc (dom
, aff
);
306 /* Extract an affine expression from the gmp constant G. */
309 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
311 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
312 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
313 isl_set
*dom
= isl_set_universe (space
);
314 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
315 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
316 aff
= isl_aff_add_constant_val (aff
, v
);
318 return isl_pw_aff_alloc (dom
, aff
);
321 /* Extract an affine expression from the integer_cst E. */
324 extract_affine_int (tree e
, __isl_take isl_space
*space
)
329 tree_int_to_gmp (e
, g
);
330 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
336 /* Compute pwaff mod 2^width. */
339 wrap (isl_pw_aff
*pwaff
, unsigned width
)
343 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
344 mod
= isl_val_2exp (mod
);
345 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
350 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
351 Otherwise returns -1. */
354 parameter_index_in_region_1 (tree name
, sese_info_p region
)
359 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
361 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
368 /* Extract an affine expression from the tree E in the scop S. */
371 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
373 isl_pw_aff
*lhs
, *rhs
, *res
;
375 if (e
== chrec_dont_know
) {
376 isl_space_free (space
);
380 switch (TREE_CODE (e
))
382 case POLYNOMIAL_CHREC
:
383 res
= extract_affine_chrec (s
, e
, space
);
387 res
= extract_affine_mul (s
, e
, space
);
391 case POINTER_PLUS_EXPR
:
392 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
393 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
394 res
= isl_pw_aff_add (lhs
, rhs
);
398 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
399 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
400 res
= isl_pw_aff_sub (lhs
, rhs
);
405 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
406 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
407 res
= isl_pw_aff_mul (lhs
, rhs
);
411 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
412 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
413 res
= extract_affine_name (s
, e
, space
);
417 res
= extract_affine_int (e
, space
);
418 /* No need to wrap a single integer. */
422 case NON_LVALUE_EXPR
:
423 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
431 tree type
= TREE_TYPE (e
);
432 if (TYPE_UNSIGNED (type
))
433 res
= wrap (res
, TYPE_PRECISION (type
));
438 /* Assign dimension for each parameter in SCOP. */
441 set_scop_parameter_dim (scop_p scop
)
443 sese_info_p region
= scop
->scop_info
;
444 unsigned nbp
= sese_nb_params (region
);
445 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
449 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
450 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
451 isl_id_for_ssa_name (scop
, e
));
453 scop
->param_context
= isl_set_universe (space
);
457 cleanup_loop_iter_dom (isl_set
*inner
, isl_set
*outer
, isl_space
*space
, mpz_t g
)
459 isl_set_free (inner
);
460 isl_set_free (outer
);
461 isl_space_free (space
);
466 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
467 the constraints for the surrounding loops. */
470 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
472 isl_set
*outer
, isl_set
**doms
)
475 tree nb_iters
= number_of_latch_executions (loop
);
476 sese_l region
= scop
->scop_info
->region
;
477 gcc_assert (loop_in_sese_p (loop
, region
));
479 isl_set
*inner
= isl_set_copy (outer
);
480 int pos
= isl_set_dim (outer
, isl_dim_set
);
486 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
487 isl_space
*space
= isl_set_get_space (inner
);
490 isl_constraint
*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 inner
= isl_set_add_constraint (inner
, c
);
495 /* loop_i <= cst_nb_iters */
496 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
498 c
= isl_inequality_alloc
499 (isl_local_space_from_space (isl_space_copy (space
)));
500 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
501 tree_int_to_gmp (nb_iters
, g
);
502 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
503 c
= isl_constraint_set_constant_val (c
, v
);
504 inner
= isl_set_add_constraint (inner
, c
);
507 /* loop_i <= expr_nb_iters */
508 else if (!chrec_contains_undetermined (nb_iters
))
512 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
514 /* Bail out as we do not know the scev. */
515 if (chrec_contains_undetermined (nb_iters
))
516 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
518 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
519 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
520 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
521 isl_set_dim (valid
, isl_dim_set
));
524 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
526 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
527 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
529 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
530 isl_pw_aff_copy (aff
));
531 inner
= isl_set_intersect (inner
, le
);
534 if (max_stmt_executions (loop
, &nit
))
536 /* Insert in the context the constraints from the
537 estimation of the number of iterations NIT and the
538 symbolic number of iterations (involving parameter
539 names) NB_ITERS. First, build the affine expression
540 "NIT - NB_ITERS" and then say that it is positive,
541 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
544 wi::to_mpz (nit
, g
, SIGNED
);
545 mpz_sub_ui (g
, g
, 1);
548 = extract_affine_gmp (g
, isl_set_get_space (inner
));
549 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
550 x
= isl_set_project_out (x
, isl_dim_set
, 0,
551 isl_set_dim (x
, isl_dim_set
));
552 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
554 isl_constraint
*c
= isl_inequality_alloc
555 (isl_local_space_from_space (isl_space_copy (space
)));
556 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
557 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
559 c
= isl_constraint_set_constant_val (c
, v
);
560 inner
= isl_set_add_constraint (inner
, c
);
563 isl_pw_aff_free (aff
);
569 && !build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
570 isl_set_copy (inner
), doms
))
571 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
575 && loop_in_sese_p (loop
->next
, region
)
576 && !build_loop_iteration_domains (scop
, loop
->next
, nb
,
577 isl_set_copy (outer
), doms
))
578 return cleanup_loop_iter_dom (inner
, outer
, space
, g
);
580 doms
[loop
->num
] = inner
;
582 isl_set_free (outer
);
583 isl_space_free (space
);
588 /* Returns a linear expression for tree T evaluated in PBB. */
591 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
593 scop_p scop
= PBB_SCOP (pbb
);
595 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
597 /* Bail out as we do not know the scev. */
598 if (chrec_contains_undetermined (t
))
601 gcc_assert (!automatically_generated_chrec_p (t
));
603 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
606 /* Add conditional statement STMT to pbb. CODE is used as the comparison
607 operator. This allows us to invert the condition or to handle
611 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
613 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
617 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
620 isl_pw_aff_free (lhs
);
628 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
632 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
636 cond
= isl_pw_aff_le_set (lhs
, rhs
);
640 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
644 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
648 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
652 isl_pw_aff_free (lhs
);
653 isl_pw_aff_free (rhs
);
657 cond
= isl_set_coalesce (cond
);
658 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
659 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
663 /* Add conditions to the domain of PBB. */
666 add_conditions_to_domain (poly_bb_p pbb
)
670 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
672 if (GBB_CONDITIONS (gbb
).is_empty ())
675 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
676 switch (gimple_code (stmt
))
680 /* Don't constrain on anything else than INTEGER_TYPE. */
681 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
684 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
685 enum tree_code code
= gimple_cond_code (cond_stmt
);
687 /* The conditions for ELSE-branches are inverted. */
688 if (!GBB_CONDITION_CASES (gbb
)[i
])
689 code
= invert_tree_comparison (code
, false);
691 if (!add_condition_to_pbb (pbb
, cond_stmt
, code
))
697 /* Switch statements are not supported right now - fall through. */
707 /* Traverses all the GBBs of the SCOP and add their constraints to the
708 iteration domains. */
711 add_conditions_to_constraints (scop_p scop
)
716 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
717 if (!add_conditions_to_domain (pbb
))
723 /* Add constraints on the possible values of parameter P from the type
727 add_param_constraints (scop_p scop
, graphite_dim_t p
)
729 tree parameter
= scop
->scop_info
->params
[p
];
730 tree type
= TREE_TYPE (parameter
);
734 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
735 lb
= lower_bound_in_type (type
, type
);
737 lb
= TYPE_MIN_VALUE (type
);
739 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
740 ub
= upper_bound_in_type (type
, type
);
742 ub
= TYPE_MAX_VALUE (type
);
746 isl_space
*space
= isl_set_get_space (scop
->param_context
);
751 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
753 tree_int_to_gmp (lb
, g
);
754 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
757 c
= isl_constraint_set_constant_val (c
, v
);
758 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
760 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
765 isl_space
*space
= isl_set_get_space (scop
->param_context
);
770 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
773 tree_int_to_gmp (ub
, g
);
774 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
776 c
= isl_constraint_set_constant_val (c
, v
);
777 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
779 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
783 /* Build the context of the SCOP. The context usually contains extra
784 constraints that are added to the iteration domains that constrain
788 build_scop_context (scop_p scop
)
790 graphite_dim_t p
, n
= scop_nb_params (scop
);
792 for (p
= 0; p
< n
; p
++)
793 add_param_constraints (scop
, p
);
796 /* Build the iteration domains: the loops belonging to the current
797 SCOP, and that vary for the execution of the current basic block.
798 Returns false if there is no loop in SCOP. */
801 build_scop_iteration_domain (scop_p scop
)
803 sese_info_p region
= scop
->scop_info
;
804 int nb_loops
= number_of_loops (cfun
);
805 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
809 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
810 if (!loop_in_sese_p (loop_outer (loop
), region
->region
)
811 && !build_loop_iteration_domains (scop
, loop
, 0,
812 isl_set_copy (scop
->param_context
), doms
))
819 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
821 loop
= pbb_loop (pbb
);
824 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
826 pbb
->domain
= isl_set_copy (scop
->param_context
);
828 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
829 isl_id_for_pbb (scop
, pbb
));
833 for (int i
= 0; i
< nb_loops
; i
++)
835 isl_set_free (doms
[i
]);
841 /* Add a constrain to the ACCESSES polyhedron for the alias set of
842 data reference DR. ACCESSP_NB_DIMS is the dimension of the
843 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
847 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
849 isl_constraint
*c
= isl_equality_alloc
850 (isl_local_space_from_space (isl_map_get_space (acc
)));
851 /* Positive numbers for all alias sets. */
852 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
853 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
855 return isl_map_add_constraint (acc
, c
);
858 /* Add a constrain to the ACCESSES polyhedron for the alias set of
859 data reference DR. ACCESSP_NB_DIMS is the dimension of the
860 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
864 add_scalar_version_numbers (isl_map
*acc
, tree var
)
866 isl_constraint
*c
= isl_equality_alloc
867 (isl_local_space_from_space (isl_map_get_space (acc
)));
868 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
869 /* Each scalar variables has a unique alias set number starting from
871 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
872 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
874 return isl_map_add_constraint (acc
, c
);
877 /* Assign the affine expression INDEX to the output dimension POS of
878 MAP and return the result. */
881 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
884 int len
= isl_map_dim (map
, isl_dim_out
);
887 index_map
= isl_map_from_pw_aff (index
);
888 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
889 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
891 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
892 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
893 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
894 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
896 return isl_map_intersect (map
, index_map
);
899 /* Add to ACCESSES polyhedron equalities defining the access functions
900 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
901 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
902 PBB is the poly_bb_p that contains the data reference DR. */
905 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
907 data_reference_p dr
= dri
.dr
;
908 poly_bb_p pbb
= dri
.pbb
;
909 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
910 scop_p scop
= PBB_SCOP (pbb
);
912 for (i
= 0; i
< nb_subscripts
; i
++)
915 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
917 aff
= extract_affine (scop
, afn
,
918 isl_space_domain (isl_map_get_space (acc
)));
919 acc
= set_index (acc
, i
+ 1, aff
);
925 /* Return true when the LOW and HIGH bounds of an array reference REF are valid
926 to extract constraints on accessed elements of the array. Returning false is
927 the conservative answer. */
930 bounds_are_valid (tree ref
, tree low
, tree high
)
935 if (!tree_fits_shwi_p (low
)
936 || !tree_fits_shwi_p (high
))
939 /* 1-element arrays at end of structures may extend over
940 their declared size. */
941 if (array_at_struct_end_p (ref
)
942 && operand_equal_p (low
, high
, 0))
945 /* Fortran has some arrays where high bound is -1 and low is 0. */
946 if (integer_onep (fold_build2 (LT_EXPR
, boolean_type_node
, high
, low
)))
952 /* Add constrains representing the size of the accessed data to the
953 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
954 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
958 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
961 tree ref
= DR_REF (dr
);
963 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
964 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
966 if (TREE_CODE (ref
) != ARRAY_REF
)
967 return subscript_sizes
;
969 tree low
= array_ref_low_bound (ref
);
970 tree high
= array_ref_up_bound (ref
);
972 if (!bounds_are_valid (ref
, low
, high
))
975 isl_space
*space
= isl_set_get_space (subscript_sizes
);
976 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
977 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
980 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
981 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
982 isl_set_dim (valid
, isl_dim_set
));
983 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
986 = isl_aff_zero_on_domain (isl_local_space_from_space (space
));
987 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
989 = isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
990 isl_pw_aff
*index
= isl_pw_aff_alloc (univ
, aff
);
992 isl_id
*id
= isl_set_get_tuple_id (subscript_sizes
);
993 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
994 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
996 /* low <= sub_i <= high */
997 isl_set
*lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
998 isl_set
*ubs
= isl_pw_aff_le_set (index
, ub
);
999 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1000 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1003 return subscript_sizes
;
1006 /* Build data accesses for DRI. */
1009 build_poly_dr (dr_info
&dri
)
1012 isl_set
*subscript_sizes
;
1013 poly_bb_p pbb
= dri
.pbb
;
1014 data_reference_p dr
= dri
.dr
;
1015 scop_p scop
= PBB_SCOP (pbb
);
1016 isl_id
*id
= isl_id_for_dr (scop
);
1019 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1020 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1021 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1022 isl_dim_out
, nb_out
);
1024 acc
= isl_map_universe (space
);
1025 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
1028 acc
= pdr_add_alias_set (acc
, dri
);
1029 acc
= pdr_add_memory_accesses (acc
, dri
);
1032 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1033 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1035 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1036 subscript_sizes
= isl_set_nat_universe (space
);
1037 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1039 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1042 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1043 acc
, subscript_sizes
);
1047 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
1048 isl_map
*acc
, isl_set
*subscript_sizes
)
1050 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1051 /* Each scalar variables has a unique alias set number starting from
1053 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1054 max_arrays
+ SSA_NAME_VERSION (var
));
1056 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
1060 /* Record all cross basic block scalar variables in PBB. */
1063 build_poly_sr (poly_bb_p pbb
)
1065 scop_p scop
= PBB_SCOP (pbb
);
1066 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1067 vec
<scalar_use
> reads
= gbb
->read_scalar_refs
;
1068 vec
<tree
> writes
= gbb
->write_scalar_refs
;
1070 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1072 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1073 isl_dim_out
, nb_out
);
1074 isl_id
*id
= isl_id_for_dr (scop
);
1075 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
1076 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
1077 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
1078 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
1082 FOR_EACH_VEC_ELT (writes
, i
, var
)
1083 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
1084 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
1087 FOR_EACH_VEC_ELT (reads
, i
, use
)
1088 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
1089 isl_set_copy (subscript_sizes
));
1092 isl_set_free (subscript_sizes
);
1095 /* Build data references in SCOP. */
1098 build_scop_drs (scop_p scop
)
1102 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1103 build_poly_dr (*dri
);
1106 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1107 build_poly_sr (pbb
);
1110 /* Builds the polyhedral representation for a SESE region. */
1113 build_poly_scop (scop_p scop
)
1115 set_scop_parameter_dim (scop
);
1116 if (!build_scop_iteration_domain (scop
))
1119 build_scop_context (scop
);
1121 if (!add_conditions_to_constraints (scop
))
1124 build_scop_drs (scop
);
1125 build_scop_scattering (scop
);
1128 #endif /* HAVE_isl */