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/>. */
24 /* Workaround for GMP 5.1.3 bug, see PR56019. */
27 #include <isl/constraint.h>
30 #include <isl/union_map.h>
31 #include <isl/constraint.h>
35 /* Since ISL-0.13, the extern is in val_gmp.h. */
36 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
39 #include <isl/val_gmp.h>
40 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
45 #include "coretypes.h"
52 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "gimplify-me.h"
57 #include "tree-ssa-loop-manip.h"
58 #include "tree-ssa-loop-niter.h"
59 #include "tree-ssa-loop.h"
60 #include "tree-into-ssa.h"
61 #include "tree-pass.h"
63 #include "tree-data-ref.h"
64 #include "tree-scalar-evolution.h"
66 #include "graphite-poly.h"
67 #include "tree-ssa-propagate.h"
68 #include "graphite-sese-to-poly.h"
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_minimal_scattering_polyhedrons (isl_aff
*static_sched
, poly_bb_p pbb
,
120 int local_dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
122 /* Remove a sequence dimension if irrelevant to domain of current pbb. */
123 int actual_nb_dim
= 0;
124 for (int i
= 0; i
< nb_sequence_dim
; i
++)
125 if (sequence_dims
[i
] <= local_dim
)
128 /* Build an array that combines sequence dimensions and loops dimensions info.
129 This is used later to compute the static scattering polyhedrons. */
130 bool *sequence_and_loop_dims
= NULL
;
131 if (local_dim
+ actual_nb_dim
> 0)
133 sequence_and_loop_dims
= XNEWVEC (bool, local_dim
+ actual_nb_dim
);
136 for (; i
< local_dim
; i
++)
138 if (sequence_dims
&& sequence_dims
[j
] == i
)
140 /* True for sequence dimension. */
141 sequence_and_loop_dims
[i
+ j
] = true;
144 /* False for loop dimension. */
145 sequence_and_loop_dims
[i
+ j
] = false;
147 /* Fake loops make things shifted by one. */
148 if (sequence_dims
&& sequence_dims
[j
] == i
)
149 sequence_and_loop_dims
[i
+ j
] = true;
152 int scattering_dimensions
= local_dim
+ actual_nb_dim
;
153 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
154 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
), isl_dim_out
,
155 scattering_dimensions
);
156 pbb
->schedule
= isl_map_universe (dm
);
159 for (int i
= 0; i
< scattering_dimensions
; i
++)
161 if (!sequence_and_loop_dims
[i
])
163 /* Iterations of this loop - loop dimension. */
164 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, k
,
170 /* Textual order inside this loop - sequence dimension. */
171 isl_space
*s
= isl_map_get_space (pbb
->schedule
);
172 isl_local_space
*ls
= isl_local_space_from_space (s
);
173 isl_constraint
*c
= isl_equality_alloc (ls
);
174 isl_val
*val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, k
);
175 gcc_assert (val
&& isl_val_is_int (val
));
176 val
= isl_val_neg (val
);
177 c
= isl_constraint_set_constant_val (c
, val
);
178 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
179 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
182 XDELETEVEC (sequence_and_loop_dims
);
183 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
186 /* Build the static schedule for BB. This function minimizes the number of
187 dimensions used for pbb sequences.
189 The following example informally defines the static schedule:
210 Static schedules for A to F:
221 build_scop_minimal_scattering (scop_p scop
)
223 gimple_poly_bb_p previous_gbb
= NULL
;
224 int *temp_for_sequence_dims
= NULL
;
228 /* Go through the pbbs to determine the minimum number of dimensions needed to
229 build the static schedule. */
231 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
233 int dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
238 /* One extra dimension for the outer fake loop. */
240 temp_for_sequence_dims
= XCNEWVEC (int, nb_dims
);
242 /* Record the number of common loops for each dimension. */
243 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
245 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
250 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
251 temp_for_sequence_dims
[prefix
] += 1;
256 /* Analyze the info in temp_for_sequence_dim and determine the minimal number
257 of sequence dimensions. A dimension that did not appear as common
258 dimension should not be considered as a sequence dimension. */
259 int nb_sequence_params
= 0;
260 for (i
= 0; i
< nb_dims
; i
++)
261 if (temp_for_sequence_dims
[i
] > 0)
262 nb_sequence_params
++;
264 int *sequence_dims
= NULL
;
265 if (nb_sequence_params
> 0)
268 sequence_dims
= XNEWVEC (int, nb_sequence_params
);
269 for (i
= 0; i
< nb_dims
; i
++)
270 if (temp_for_sequence_dims
[i
] > 0)
272 sequence_dims
[j
] = i
;
277 XDELETEVEC (temp_for_sequence_dims
);
279 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
280 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
281 isl_local_space
*local_space
= isl_local_space_from_space (dc
);
282 isl_aff
*static_sched
= isl_aff_zero_on_domain (local_space
);
284 /* We have to start schedules at 0 on the first component and
285 because we cannot compare_prefix_loops against a previous loop,
286 prefix will be equal to zero, and that index will be
287 incremented before copying. */
288 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
291 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
293 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
297 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
301 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
303 build_pbb_minimal_scattering_polyhedrons (static_sched
, pbb
,
304 sequence_dims
, nb_sequence_params
);
307 XDELETEVEC (sequence_dims
);
308 isl_aff_free (static_sched
);
311 /* Build the original schedule showing the orginal order of execution
312 of statement instances.
314 The following example shows the original schedule:
330 Static schedules for A to D expressed in a union map:
332 S_A[i0, i1] -> [0, i0, 0, i1];
333 S_B[i0] -> [0, i0, 1];
335 S_D[i0] -> [2, i0, 0]
340 build_scop_original_schedule (scop_p scop
)
345 isl_space
*space
= isl_set_get_space (scop
->param_context
);
346 isl_union_map
*res
= isl_union_map_empty (space
);
348 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
349 res
= isl_union_map_add_map (res
, isl_map_copy (pbb
->schedule
));
351 scop
->original_schedule
= res
;
355 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
357 /* Extract an affine expression from the chain of recurrence E. */
360 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
362 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
363 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
364 isl_local_space
*ls
= isl_local_space_from_space (space
);
365 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
366 isl_aff
*loop
= isl_aff_set_coefficient_si
367 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
368 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
370 /* Before multiplying, make sure that the result is affine. */
371 gcc_assert (isl_pw_aff_is_cst (rhs
)
372 || isl_pw_aff_is_cst (l
));
374 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
377 /* Extract an affine expression from the mult_expr E. */
380 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
382 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
383 isl_space_copy (space
));
384 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
386 if (!isl_pw_aff_is_cst (lhs
)
387 && !isl_pw_aff_is_cst (rhs
))
389 isl_pw_aff_free (lhs
);
390 isl_pw_aff_free (rhs
);
394 return isl_pw_aff_mul (lhs
, rhs
);
397 /* Return an ISL identifier from the name of the ssa_name E. */
400 isl_id_for_ssa_name (scop_p s
, tree e
)
402 const char *name
= get_name (e
);
406 id
= isl_id_alloc (s
->isl_context
, name
, e
);
410 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
411 id
= isl_id_alloc (s
->isl_context
, name1
, e
);
417 /* Return an ISL identifier for the data reference DR. Data references and
418 scalar references get the same isl_id. They need to be comparable and are
419 distinguished through the first dimension, which contains the alias set or
420 SSA_NAME_VERSION number. */
423 isl_id_for_dr (scop_p s
)
425 return isl_id_alloc (s
->isl_context
, "", 0);
428 /* Extract an affine expression from the ssa_name E. */
431 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
433 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
434 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
436 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
437 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
438 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
439 return isl_pw_aff_alloc (dom
, aff
);
442 /* Extract an affine expression from the gmp constant G. */
445 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
447 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
448 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
449 isl_set
*dom
= isl_set_universe (space
);
450 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
451 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
452 aff
= isl_aff_add_constant_val (aff
, v
);
454 return isl_pw_aff_alloc (dom
, aff
);
457 /* Extract an affine expression from the integer_cst E. */
460 extract_affine_int (tree e
, __isl_take isl_space
*space
)
465 tree_int_to_gmp (e
, g
);
466 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
472 /* Compute pwaff mod 2^width. */
475 wrap (isl_pw_aff
*pwaff
, unsigned width
)
479 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
480 mod
= isl_val_2exp (mod
);
481 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
486 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
487 Otherwise returns -1. */
490 parameter_index_in_region_1 (tree name
, sese_info_p region
)
495 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
497 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
504 /* Extract an affine expression from the tree E in the scop S. */
507 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
509 isl_pw_aff
*lhs
, *rhs
, *res
;
511 if (e
== chrec_dont_know
) {
512 isl_space_free (space
);
516 switch (TREE_CODE (e
))
518 case POLYNOMIAL_CHREC
:
519 res
= extract_affine_chrec (s
, e
, space
);
523 res
= extract_affine_mul (s
, e
, space
);
527 case POINTER_PLUS_EXPR
:
528 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
529 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
530 res
= isl_pw_aff_add (lhs
, rhs
);
534 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
535 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
536 res
= isl_pw_aff_sub (lhs
, rhs
);
541 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
542 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
543 res
= isl_pw_aff_mul (lhs
, rhs
);
547 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
548 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
549 res
= extract_affine_name (s
, e
, space
);
553 res
= extract_affine_int (e
, space
);
554 /* No need to wrap a single integer. */
558 case NON_LVALUE_EXPR
:
559 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
567 tree type
= TREE_TYPE (e
);
568 if (TYPE_UNSIGNED (type
))
569 res
= wrap (res
, TYPE_PRECISION (type
));
574 /* Assign dimension for each parameter in SCOP. */
577 set_scop_parameter_dim (scop_p scop
)
579 sese_info_p region
= scop
->scop_info
;
580 unsigned nbp
= sese_nb_params (region
);
581 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
585 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
586 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
587 isl_id_for_ssa_name (scop
, e
));
589 scop
->param_context
= isl_set_universe (space
);
592 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
593 the constraints for the surrounding loops. */
596 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
598 isl_set
*outer
, isl_set
**doms
)
601 tree nb_iters
= number_of_latch_executions (loop
);
602 sese_l region
= scop
->scop_info
->region
;
603 gcc_assert (loop_in_sese_p (loop
, region
));
605 isl_set
*inner
= isl_set_copy (outer
);
606 int pos
= isl_set_dim (outer
, isl_dim_set
);
612 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
613 isl_space
*space
= isl_set_get_space (inner
);
616 isl_constraint
*c
= isl_inequality_alloc
617 (isl_local_space_from_space (isl_space_copy (space
)));
618 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
619 inner
= isl_set_add_constraint (inner
, c
);
621 /* loop_i <= cst_nb_iters */
622 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
624 c
= isl_inequality_alloc
625 (isl_local_space_from_space (isl_space_copy (space
)));
626 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
627 tree_int_to_gmp (nb_iters
, g
);
628 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
629 c
= isl_constraint_set_constant_val (c
, v
);
630 inner
= isl_set_add_constraint (inner
, c
);
633 /* loop_i <= expr_nb_iters */
634 else if (!chrec_contains_undetermined (nb_iters
))
638 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
640 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
641 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
642 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
643 isl_set_dim (valid
, isl_dim_set
));
644 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
646 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
647 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
649 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
650 isl_pw_aff_copy (aff
));
651 inner
= isl_set_intersect (inner
, le
);
654 if (max_stmt_executions (loop
, &nit
))
656 /* Insert in the context the constraints from the
657 estimation of the number of iterations NIT and the
658 symbolic number of iterations (involving parameter
659 names) NB_ITERS. First, build the affine expression
660 "NIT - NB_ITERS" and then say that it is positive,
661 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
664 wi::to_mpz (nit
, g
, SIGNED
);
665 mpz_sub_ui (g
, g
, 1);
668 = extract_affine_gmp (g
, isl_set_get_space (inner
));
669 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
670 x
= isl_set_project_out (x
, isl_dim_set
, 0,
671 isl_set_dim (x
, isl_dim_set
));
672 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
674 isl_constraint
*c
= isl_inequality_alloc
675 (isl_local_space_from_space (isl_space_copy (space
)));
676 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
677 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
679 c
= isl_constraint_set_constant_val (c
, v
);
680 inner
= isl_set_add_constraint (inner
, c
);
683 isl_pw_aff_free (aff
);
689 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
690 isl_set_copy (inner
), doms
);
694 && loop_in_sese_p (loop
->next
, region
))
695 build_loop_iteration_domains (scop
, loop
->next
, nb
,
696 isl_set_copy (outer
), doms
);
698 doms
[loop
->num
] = inner
;
700 isl_set_free (outer
);
701 isl_space_free (space
);
705 /* Returns a linear expression for tree T evaluated in PBB. */
708 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
710 scop_p scop
= PBB_SCOP (pbb
);
712 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
713 gcc_assert (!automatically_generated_chrec_p (t
));
715 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
718 /* Add conditional statement STMT to pbb. CODE is used as the comparison
719 operator. This allows us to invert the condition or to handle
723 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
725 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
726 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
732 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
736 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
740 cond
= isl_pw_aff_le_set (lhs
, rhs
);
744 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
748 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
752 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
756 isl_pw_aff_free (lhs
);
757 isl_pw_aff_free (rhs
);
761 cond
= isl_set_coalesce (cond
);
762 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
763 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
766 /* Add conditions to the domain of PBB. */
769 add_conditions_to_domain (poly_bb_p pbb
)
773 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
775 if (GBB_CONDITIONS (gbb
).is_empty ())
778 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
779 switch (gimple_code (stmt
))
783 /* Don't constrain on anything else than INTEGER_TYPE. */
784 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
787 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
788 enum tree_code code
= gimple_cond_code (cond_stmt
);
790 /* The conditions for ELSE-branches are inverted. */
791 if (!GBB_CONDITION_CASES (gbb
)[i
])
792 code
= invert_tree_comparison (code
, false);
794 add_condition_to_pbb (pbb
, cond_stmt
, code
);
799 /* Switch statements are not supported right now - fall through. */
807 /* Traverses all the GBBs of the SCOP and add their constraints to the
808 iteration domains. */
811 add_conditions_to_constraints (scop_p scop
)
816 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
817 add_conditions_to_domain (pbb
);
820 /* Add constraints on the possible values of parameter P from the type
824 add_param_constraints (scop_p scop
, graphite_dim_t p
)
826 tree parameter
= scop
->scop_info
->params
[p
];
827 tree type
= TREE_TYPE (parameter
);
831 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
832 lb
= lower_bound_in_type (type
, type
);
834 lb
= TYPE_MIN_VALUE (type
);
836 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
837 ub
= upper_bound_in_type (type
, type
);
839 ub
= TYPE_MAX_VALUE (type
);
843 isl_space
*space
= isl_set_get_space (scop
->param_context
);
848 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
850 tree_int_to_gmp (lb
, g
);
851 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
854 c
= isl_constraint_set_constant_val (c
, v
);
855 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
857 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
862 isl_space
*space
= isl_set_get_space (scop
->param_context
);
867 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
870 tree_int_to_gmp (ub
, g
);
871 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
873 c
= isl_constraint_set_constant_val (c
, v
);
874 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
876 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
880 /* Build the context of the SCOP. The context usually contains extra
881 constraints that are added to the iteration domains that constrain
885 build_scop_context (scop_p scop
)
887 graphite_dim_t p
, n
= scop_nb_params (scop
);
889 for (p
= 0; p
< n
; p
++)
890 add_param_constraints (scop
, p
);
893 /* Build the iteration domains: the loops belonging to the current
894 SCOP, and that vary for the execution of the current basic block.
895 Returns false if there is no loop in SCOP. */
898 build_scop_iteration_domain (scop_p scop
)
900 sese_info_p region
= scop
->scop_info
;
901 int nb_loops
= number_of_loops (cfun
);
902 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
906 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
907 if (!loop_in_sese_p (loop_outer (loop
), region
->region
))
908 build_loop_iteration_domains (scop
, loop
, 0,
909 isl_set_copy (scop
->param_context
), doms
);
912 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
914 loop
= pbb_loop (pbb
);
917 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
919 pbb
->domain
= isl_set_copy (scop
->param_context
);
921 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
922 isl_id_for_pbb (scop
, pbb
));
925 for (int i
= 0; i
< nb_loops
; i
++)
927 isl_set_free (doms
[i
]);
932 /* Add a constrain to the ACCESSES polyhedron for the alias set of
933 data reference DR. ACCESSP_NB_DIMS is the dimension of the
934 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
938 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
940 isl_constraint
*c
= isl_equality_alloc
941 (isl_local_space_from_space (isl_map_get_space (acc
)));
942 /* Positive numbers for all alias sets. */
943 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
944 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
946 return isl_map_add_constraint (acc
, c
);
949 /* Add a constrain to the ACCESSES polyhedron for the alias set of
950 data reference DR. ACCESSP_NB_DIMS is the dimension of the
951 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
955 add_scalar_version_numbers (isl_map
*acc
, tree var
)
957 isl_constraint
*c
= isl_equality_alloc
958 (isl_local_space_from_space (isl_map_get_space (acc
)));
959 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
960 /* Each scalar variables has a unique alias set number starting from
962 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
963 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
965 return isl_map_add_constraint (acc
, c
);
968 /* Assign the affine expression INDEX to the output dimension POS of
969 MAP and return the result. */
972 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
975 int len
= isl_map_dim (map
, isl_dim_out
);
978 index_map
= isl_map_from_pw_aff (index
);
979 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
980 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
982 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
983 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
984 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
985 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
987 return isl_map_intersect (map
, index_map
);
990 /* Add to ACCESSES polyhedron equalities defining the access functions
991 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
992 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
993 PBB is the poly_bb_p that contains the data reference DR. */
996 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
998 data_reference_p dr
= dri
.dr
;
999 poly_bb_p pbb
= dri
.pbb
;
1000 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1001 scop_p scop
= PBB_SCOP (pbb
);
1003 for (i
= 0; i
< nb_subscripts
; i
++)
1006 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1008 aff
= extract_affine (scop
, afn
,
1009 isl_space_domain (isl_map_get_space (acc
)));
1010 acc
= set_index (acc
, i
+ 1, aff
);
1016 /* Add constrains representing the size of the accessed data to the
1017 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1018 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1022 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1023 data_reference_p dr
)
1025 tree ref
= DR_REF (dr
);
1027 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1028 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1030 if (TREE_CODE (ref
) != ARRAY_REF
)
1031 return subscript_sizes
;
1033 tree low
= array_ref_low_bound (ref
);
1034 tree high
= array_ref_up_bound (ref
);
1036 /* XXX The PPL code dealt separately with
1037 subscript - low >= 0 and high - subscript >= 0 in case one of
1038 the two bounds isn't known. Do the same here? */
1040 if (tree_fits_shwi_p (low
)
1042 && tree_fits_shwi_p (high
)
1043 /* 1-element arrays at end of structures may extend over
1044 their declared size. */
1045 && !(array_at_struct_end_p (ref
)
1046 && operand_equal_p (low
, high
, 0)))
1050 isl_set
*univ
, *lbs
, *ubs
;
1053 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1054 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1055 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1058 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1059 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1060 isl_set_dim (valid
, isl_dim_set
));
1061 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
1063 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1064 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1065 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1066 index
= isl_pw_aff_alloc (univ
, aff
);
1068 id
= isl_set_get_tuple_id (subscript_sizes
);
1069 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1070 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1072 /* low <= sub_i <= high */
1073 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1074 ubs
= isl_pw_aff_le_set (index
, ub
);
1075 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1076 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1080 return subscript_sizes
;
1083 /* Build data accesses for DRI. */
1086 build_poly_dr (dr_info
&dri
)
1089 isl_set
*subscript_sizes
;
1090 poly_bb_p pbb
= dri
.pbb
;
1091 data_reference_p dr
= dri
.dr
;
1092 scop_p scop
= PBB_SCOP (pbb
);
1093 isl_id
*id
= isl_id_for_dr (scop
);
1096 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1097 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1098 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1099 isl_dim_out
, nb_out
);
1101 acc
= isl_map_universe (space
);
1102 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
1105 acc
= pdr_add_alias_set (acc
, dri
);
1106 acc
= pdr_add_memory_accesses (acc
, dri
);
1109 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1110 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1112 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1113 subscript_sizes
= isl_set_nat_universe (space
);
1114 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1116 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1119 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1120 acc
, subscript_sizes
);
1124 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
1125 isl_map
*acc
, isl_set
*subscript_sizes
)
1127 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1128 /* Each scalar variables has a unique alias set number starting from
1130 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1131 max_arrays
+ SSA_NAME_VERSION (var
));
1133 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
1137 /* Record all cross basic block scalar variables in PBB. */
1140 build_poly_sr (poly_bb_p pbb
)
1142 scop_p scop
= PBB_SCOP (pbb
);
1143 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1144 vec
<scalar_use
> reads
= gbb
->read_scalar_refs
;
1145 vec
<tree
> writes
= gbb
->write_scalar_refs
;
1147 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1149 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1150 isl_dim_out
, nb_out
);
1151 isl_id
*id
= isl_id_for_dr (scop
);
1152 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
1153 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
1154 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
1155 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
1159 FOR_EACH_VEC_ELT (writes
, i
, var
)
1160 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
1161 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
1164 FOR_EACH_VEC_ELT (reads
, i
, use
)
1165 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
1166 isl_set_copy (subscript_sizes
));
1169 isl_set_free (subscript_sizes
);
1172 /* Build data references in SCOP. */
1175 build_scop_drs (scop_p scop
)
1179 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1180 build_poly_dr (*dri
);
1183 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1184 build_poly_sr (pbb
);
1187 /* Builds the polyhedral representation for a SESE region. */
1190 build_poly_scop (scop_p scop
)
1192 set_scop_parameter_dim (scop
);
1193 build_scop_iteration_domain (scop
);
1194 build_scop_context (scop
);
1195 add_conditions_to_constraints (scop
);
1197 build_scop_drs (scop
);
1198 build_scop_minimal_scattering (scop
);
1199 build_scop_original_schedule (scop
);
1201 /* This SCoP has been translated to the polyhedral
1203 scop
->poly_scop_p
= true;
1205 #endif /* HAVE_isl */