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)
68 #include "graphite-poly.h"
69 #include "graphite-sese-to-poly.h"
71 /* Assigns to RES the value of the INTEGER_CST T. */
74 tree_int_to_gmp (tree t
, mpz_t res
)
76 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
79 /* Return an ISL identifier for the polyhedral basic block PBB. */
82 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
85 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
86 return isl_id_alloc (s
->isl_context
, name
, pbb
);
89 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
90 We generate SCATTERING_DIMENSIONS scattering dimensions.
92 The scattering polyhedron consists of these dimensions: scattering,
93 loop_iterators, parameters.
97 | scattering_dimensions = 5
105 | Scattering polyhedron:
107 | scattering: {s1, s2, s3, s4, s5}
108 | loop_iterators: {i}
109 | parameters: {p1, p2}
111 | s1 s2 s3 s4 s5 i p1 p2 1
112 | 1 0 0 0 0 0 0 0 -4 = 0
113 | 0 1 0 0 0 -1 0 0 0 = 0
114 | 0 0 1 0 0 0 0 0 -5 = 0 */
117 build_pbb_minimal_scattering_polyhedrons (isl_aff
*static_sched
, poly_bb_p pbb
,
121 int local_dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
123 /* Remove a sequence dimension if irrelevant to domain of current pbb. */
124 int actual_nb_dim
= 0;
125 for (int i
= 0; i
< nb_sequence_dim
; i
++)
126 if (sequence_dims
[i
] <= local_dim
)
129 /* Build an array that combines sequence dimensions and loops dimensions info.
130 This is used later to compute the static scattering polyhedrons. */
131 bool *sequence_and_loop_dims
= NULL
;
132 if (local_dim
+ actual_nb_dim
> 0)
134 sequence_and_loop_dims
= XNEWVEC (bool, local_dim
+ actual_nb_dim
);
137 for (; i
< local_dim
; i
++)
139 if (sequence_dims
&& sequence_dims
[j
] == i
)
141 /* True for sequence dimension. */
142 sequence_and_loop_dims
[i
+ j
] = true;
145 /* False for loop dimension. */
146 sequence_and_loop_dims
[i
+ j
] = false;
148 /* Fake loops make things shifted by one. */
149 if (sequence_dims
&& sequence_dims
[j
] == i
)
150 sequence_and_loop_dims
[i
+ j
] = true;
153 int scattering_dimensions
= local_dim
+ actual_nb_dim
;
154 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
155 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
), isl_dim_out
,
156 scattering_dimensions
);
157 pbb
->schedule
= isl_map_universe (dm
);
160 for (int i
= 0; i
< scattering_dimensions
; i
++)
162 if (!sequence_and_loop_dims
[i
])
164 /* Iterations of this loop - loop dimension. */
165 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, k
,
171 /* Textual order inside this loop - sequence dimension. */
172 isl_space
*s
= isl_map_get_space (pbb
->schedule
);
173 isl_local_space
*ls
= isl_local_space_from_space (s
);
174 isl_constraint
*c
= isl_equality_alloc (ls
);
175 isl_val
*val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, k
);
176 gcc_assert (val
&& isl_val_is_int (val
));
177 val
= isl_val_neg (val
);
178 c
= isl_constraint_set_constant_val (c
, val
);
179 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
180 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
183 XDELETEVEC (sequence_and_loop_dims
);
184 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
187 /* Build the static schedule for BB. This function minimizes the number of
188 dimensions used for pbb sequences.
190 The following example informally defines the static schedule:
211 Static schedules for A to F:
222 build_scop_minimal_scattering (scop_p scop
)
224 gimple_poly_bb_p previous_gbb
= NULL
;
225 int *temp_for_sequence_dims
= NULL
;
229 /* Go through the pbbs to determine the minimum number of dimensions needed to
230 build the static schedule. */
232 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
234 int dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
239 /* One extra dimension for the outer fake loop. */
241 temp_for_sequence_dims
= XCNEWVEC (int, nb_dims
);
243 /* Record the number of common loops for each dimension. */
244 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
246 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
251 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
252 temp_for_sequence_dims
[prefix
] += 1;
257 /* Analyze the info in temp_for_sequence_dim and determine the minimal number
258 of sequence dimensions. A dimension that did not appear as common
259 dimension should not be considered as a sequence dimension. */
260 int nb_sequence_params
= 0;
261 for (i
= 0; i
< nb_dims
; i
++)
262 if (temp_for_sequence_dims
[i
] > 0)
263 nb_sequence_params
++;
265 int *sequence_dims
= NULL
;
266 if (nb_sequence_params
> 0)
269 sequence_dims
= XNEWVEC (int, nb_sequence_params
);
270 for (i
= 0; i
< nb_dims
; i
++)
271 if (temp_for_sequence_dims
[i
] > 0)
273 sequence_dims
[j
] = i
;
278 XDELETEVEC (temp_for_sequence_dims
);
280 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
281 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
282 isl_local_space
*local_space
= isl_local_space_from_space (dc
);
283 isl_aff
*static_sched
= isl_aff_zero_on_domain (local_space
);
285 /* We have to start schedules at 0 on the first component and
286 because we cannot compare_prefix_loops against a previous loop,
287 prefix will be equal to zero, and that index will be
288 incremented before copying. */
289 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
292 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
294 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
298 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
302 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
304 build_pbb_minimal_scattering_polyhedrons (static_sched
, pbb
,
305 sequence_dims
, nb_sequence_params
);
308 XDELETEVEC (sequence_dims
);
309 isl_aff_free (static_sched
);
312 /* Build the original schedule showing the orginal order of execution
313 of statement instances.
315 The following example shows the original schedule:
331 Static schedules for A to D expressed in a union map:
333 S_A[i0, i1] -> [0, i0, 0, i1];
334 S_B[i0] -> [0, i0, 1];
336 S_D[i0] -> [2, i0, 0]
341 build_scop_original_schedule (scop_p scop
)
346 isl_space
*space
= isl_set_get_space (scop
->param_context
);
347 isl_union_map
*res
= isl_union_map_empty (space
);
349 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
350 res
= isl_union_map_add_map (res
, isl_map_copy (pbb
->schedule
));
352 scop
->original_schedule
= res
;
356 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
358 /* Extract an affine expression from the chain of recurrence E. */
361 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
363 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
364 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
365 isl_local_space
*ls
= isl_local_space_from_space (space
);
366 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
367 isl_aff
*loop
= isl_aff_set_coefficient_si
368 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
369 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
371 /* Before multiplying, make sure that the result is affine. */
372 gcc_assert (isl_pw_aff_is_cst (rhs
)
373 || isl_pw_aff_is_cst (l
));
375 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
378 /* Extract an affine expression from the mult_expr E. */
381 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
383 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
384 isl_space_copy (space
));
385 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
387 if (!isl_pw_aff_is_cst (lhs
)
388 && !isl_pw_aff_is_cst (rhs
))
390 isl_pw_aff_free (lhs
);
391 isl_pw_aff_free (rhs
);
395 return isl_pw_aff_mul (lhs
, rhs
);
398 /* Return an ISL identifier from the name of the ssa_name E. */
401 isl_id_for_ssa_name (scop_p s
, tree e
)
403 const char *name
= get_name (e
);
407 id
= isl_id_alloc (s
->isl_context
, name
, e
);
411 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
412 id
= isl_id_alloc (s
->isl_context
, name1
, e
);
418 /* Return an ISL identifier for the data reference DR. Data references and
419 scalar references get the same isl_id. They need to be comparable and are
420 distinguished through the first dimension, which contains the alias set or
421 SSA_NAME_VERSION number. */
424 isl_id_for_dr (scop_p s
)
426 return isl_id_alloc (s
->isl_context
, "", 0);
429 /* Extract an affine expression from the ssa_name E. */
432 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
434 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
435 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
437 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
438 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
439 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
440 return isl_pw_aff_alloc (dom
, aff
);
443 /* Extract an affine expression from the gmp constant G. */
446 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
448 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
449 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
450 isl_set
*dom
= isl_set_universe (space
);
451 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
452 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
453 aff
= isl_aff_add_constant_val (aff
, v
);
455 return isl_pw_aff_alloc (dom
, aff
);
458 /* Extract an affine expression from the integer_cst E. */
461 extract_affine_int (tree e
, __isl_take isl_space
*space
)
466 tree_int_to_gmp (e
, g
);
467 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
473 /* Compute pwaff mod 2^width. */
476 wrap (isl_pw_aff
*pwaff
, unsigned width
)
480 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
481 mod
= isl_val_2exp (mod
);
482 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
487 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
488 Otherwise returns -1. */
491 parameter_index_in_region_1 (tree name
, sese_info_p region
)
496 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
498 FOR_EACH_VEC_ELT (region
->params
, i
, p
)
505 /* Extract an affine expression from the tree E in the scop S. */
508 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
510 isl_pw_aff
*lhs
, *rhs
, *res
;
512 if (e
== chrec_dont_know
) {
513 isl_space_free (space
);
517 switch (TREE_CODE (e
))
519 case POLYNOMIAL_CHREC
:
520 res
= extract_affine_chrec (s
, e
, space
);
524 res
= extract_affine_mul (s
, e
, space
);
528 case POINTER_PLUS_EXPR
:
529 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
530 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
531 res
= isl_pw_aff_add (lhs
, rhs
);
535 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
536 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
537 res
= isl_pw_aff_sub (lhs
, rhs
);
542 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
543 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
544 res
= isl_pw_aff_mul (lhs
, rhs
);
548 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
549 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
550 res
= extract_affine_name (s
, e
, space
);
554 res
= extract_affine_int (e
, space
);
555 /* No need to wrap a single integer. */
559 case NON_LVALUE_EXPR
:
560 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
568 tree type
= TREE_TYPE (e
);
569 if (TYPE_UNSIGNED (type
))
570 res
= wrap (res
, TYPE_PRECISION (type
));
575 /* Assign dimension for each parameter in SCOP. */
578 set_scop_parameter_dim (scop_p scop
)
580 sese_info_p region
= scop
->scop_info
;
581 unsigned nbp
= sese_nb_params (region
);
582 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
586 FOR_EACH_VEC_ELT (region
->params
, i
, e
)
587 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
588 isl_id_for_ssa_name (scop
, e
));
590 scop
->param_context
= isl_set_universe (space
);
593 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
594 the constraints for the surrounding loops. */
597 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
599 isl_set
*outer
, isl_set
**doms
)
602 tree nb_iters
= number_of_latch_executions (loop
);
603 sese_l region
= scop
->scop_info
->region
;
604 gcc_assert (loop_in_sese_p (loop
, region
));
606 isl_set
*inner
= isl_set_copy (outer
);
607 int pos
= isl_set_dim (outer
, isl_dim_set
);
613 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
614 isl_space
*space
= isl_set_get_space (inner
);
617 isl_constraint
*c
= isl_inequality_alloc
618 (isl_local_space_from_space (isl_space_copy (space
)));
619 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
620 inner
= isl_set_add_constraint (inner
, c
);
622 /* loop_i <= cst_nb_iters */
623 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
625 c
= isl_inequality_alloc
626 (isl_local_space_from_space (isl_space_copy (space
)));
627 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
628 tree_int_to_gmp (nb_iters
, g
);
629 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
630 c
= isl_constraint_set_constant_val (c
, v
);
631 inner
= isl_set_add_constraint (inner
, c
);
634 /* loop_i <= expr_nb_iters */
635 else if (!chrec_contains_undetermined (nb_iters
))
639 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
641 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
642 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
643 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
644 isl_set_dim (valid
, isl_dim_set
));
645 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
647 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
648 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
650 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
651 isl_pw_aff_copy (aff
));
652 inner
= isl_set_intersect (inner
, le
);
655 if (max_stmt_executions (loop
, &nit
))
657 /* Insert in the context the constraints from the
658 estimation of the number of iterations NIT and the
659 symbolic number of iterations (involving parameter
660 names) NB_ITERS. First, build the affine expression
661 "NIT - NB_ITERS" and then say that it is positive,
662 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
665 wi::to_mpz (nit
, g
, SIGNED
);
666 mpz_sub_ui (g
, g
, 1);
669 = extract_affine_gmp (g
, isl_set_get_space (inner
));
670 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
671 x
= isl_set_project_out (x
, isl_dim_set
, 0,
672 isl_set_dim (x
, isl_dim_set
));
673 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
675 isl_constraint
*c
= isl_inequality_alloc
676 (isl_local_space_from_space (isl_space_copy (space
)));
677 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
678 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
680 c
= isl_constraint_set_constant_val (c
, v
);
681 inner
= isl_set_add_constraint (inner
, c
);
684 isl_pw_aff_free (aff
);
690 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
691 isl_set_copy (inner
), doms
);
695 && loop_in_sese_p (loop
->next
, region
))
696 build_loop_iteration_domains (scop
, loop
->next
, nb
,
697 isl_set_copy (outer
), doms
);
699 doms
[loop
->num
] = inner
;
701 isl_set_free (outer
);
702 isl_space_free (space
);
706 /* Returns a linear expression for tree T evaluated in PBB. */
709 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
711 scop_p scop
= PBB_SCOP (pbb
);
713 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
714 gcc_assert (!automatically_generated_chrec_p (t
));
716 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
719 /* Add conditional statement STMT to pbb. CODE is used as the comparison
720 operator. This allows us to invert the condition or to handle
724 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
726 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
727 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
733 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
737 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
741 cond
= isl_pw_aff_le_set (lhs
, rhs
);
745 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
749 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
753 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
757 isl_pw_aff_free (lhs
);
758 isl_pw_aff_free (rhs
);
762 cond
= isl_set_coalesce (cond
);
763 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
764 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
767 /* Add conditions to the domain of PBB. */
770 add_conditions_to_domain (poly_bb_p pbb
)
774 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
776 if (GBB_CONDITIONS (gbb
).is_empty ())
779 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
780 switch (gimple_code (stmt
))
784 /* Don't constrain on anything else than INTEGER_TYPE. */
785 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
788 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
789 enum tree_code code
= gimple_cond_code (cond_stmt
);
791 /* The conditions for ELSE-branches are inverted. */
792 if (!GBB_CONDITION_CASES (gbb
)[i
])
793 code
= invert_tree_comparison (code
, false);
795 add_condition_to_pbb (pbb
, cond_stmt
, code
);
800 /* Switch statements are not supported right now - fall through. */
808 /* Traverses all the GBBs of the SCOP and add their constraints to the
809 iteration domains. */
812 add_conditions_to_constraints (scop_p scop
)
817 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
818 add_conditions_to_domain (pbb
);
821 /* Add constraints on the possible values of parameter P from the type
825 add_param_constraints (scop_p scop
, graphite_dim_t p
)
827 tree parameter
= scop
->scop_info
->params
[p
];
828 tree type
= TREE_TYPE (parameter
);
832 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
833 lb
= lower_bound_in_type (type
, type
);
835 lb
= TYPE_MIN_VALUE (type
);
837 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
838 ub
= upper_bound_in_type (type
, type
);
840 ub
= TYPE_MAX_VALUE (type
);
844 isl_space
*space
= isl_set_get_space (scop
->param_context
);
849 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
851 tree_int_to_gmp (lb
, g
);
852 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
855 c
= isl_constraint_set_constant_val (c
, v
);
856 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
858 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
863 isl_space
*space
= isl_set_get_space (scop
->param_context
);
868 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
871 tree_int_to_gmp (ub
, g
);
872 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
874 c
= isl_constraint_set_constant_val (c
, v
);
875 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
877 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
881 /* Build the context of the SCOP. The context usually contains extra
882 constraints that are added to the iteration domains that constrain
886 build_scop_context (scop_p scop
)
888 graphite_dim_t p
, n
= scop_nb_params (scop
);
890 for (p
= 0; p
< n
; p
++)
891 add_param_constraints (scop
, p
);
894 /* Build the iteration domains: the loops belonging to the current
895 SCOP, and that vary for the execution of the current basic block.
896 Returns false if there is no loop in SCOP. */
899 build_scop_iteration_domain (scop_p scop
)
901 sese_info_p region
= scop
->scop_info
;
902 int nb_loops
= number_of_loops (cfun
);
903 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
907 FOR_EACH_VEC_ELT (region
->loop_nest
, i
, loop
)
908 if (!loop_in_sese_p (loop_outer (loop
), region
->region
))
909 build_loop_iteration_domains (scop
, loop
, 0,
910 isl_set_copy (scop
->param_context
), doms
);
913 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
915 loop
= pbb_loop (pbb
);
918 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
920 pbb
->domain
= isl_set_copy (scop
->param_context
);
922 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
923 isl_id_for_pbb (scop
, pbb
));
926 for (int i
= 0; i
< nb_loops
; i
++)
928 isl_set_free (doms
[i
]);
933 /* Add a constrain to the ACCESSES polyhedron for the alias set of
934 data reference DR. ACCESSP_NB_DIMS is the dimension of the
935 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
939 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
941 isl_constraint
*c
= isl_equality_alloc
942 (isl_local_space_from_space (isl_map_get_space (acc
)));
943 /* Positive numbers for all alias sets. */
944 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
945 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
947 return isl_map_add_constraint (acc
, c
);
950 /* Add a constrain to the ACCESSES polyhedron for the alias set of
951 data reference DR. ACCESSP_NB_DIMS is the dimension of the
952 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
956 add_scalar_version_numbers (isl_map
*acc
, tree var
)
958 isl_constraint
*c
= isl_equality_alloc
959 (isl_local_space_from_space (isl_map_get_space (acc
)));
960 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
961 /* Each scalar variables has a unique alias set number starting from
963 c
= isl_constraint_set_constant_si (c
, -max_arrays
- SSA_NAME_VERSION (var
));
964 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
966 return isl_map_add_constraint (acc
, c
);
969 /* Assign the affine expression INDEX to the output dimension POS of
970 MAP and return the result. */
973 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
976 int len
= isl_map_dim (map
, isl_dim_out
);
979 index_map
= isl_map_from_pw_aff (index
);
980 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
981 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
983 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
984 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
985 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
986 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
988 return isl_map_intersect (map
, index_map
);
991 /* Add to ACCESSES polyhedron equalities defining the access functions
992 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
993 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
994 PBB is the poly_bb_p that contains the data reference DR. */
997 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
999 data_reference_p dr
= dri
.dr
;
1000 poly_bb_p pbb
= dri
.pbb
;
1001 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1002 scop_p scop
= PBB_SCOP (pbb
);
1004 for (i
= 0; i
< nb_subscripts
; i
++)
1007 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1009 aff
= extract_affine (scop
, afn
,
1010 isl_space_domain (isl_map_get_space (acc
)));
1011 acc
= set_index (acc
, i
+ 1, aff
);
1017 /* Add constrains representing the size of the accessed data to the
1018 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1019 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1023 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1024 data_reference_p dr
)
1026 tree ref
= DR_REF (dr
);
1028 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1029 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1031 if (TREE_CODE (ref
) != ARRAY_REF
)
1032 return subscript_sizes
;
1034 tree low
= array_ref_low_bound (ref
);
1035 tree high
= array_ref_up_bound (ref
);
1037 /* XXX The PPL code dealt separately with
1038 subscript - low >= 0 and high - subscript >= 0 in case one of
1039 the two bounds isn't known. Do the same here? */
1041 if (tree_fits_shwi_p (low
)
1043 && tree_fits_shwi_p (high
)
1044 /* 1-element arrays at end of structures may extend over
1045 their declared size. */
1046 && !(array_at_struct_end_p (ref
)
1047 && operand_equal_p (low
, high
, 0)))
1051 isl_set
*univ
, *lbs
, *ubs
;
1054 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1055 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1056 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1059 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1060 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1061 isl_set_dim (valid
, isl_dim_set
));
1062 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
1064 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1065 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1066 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1067 index
= isl_pw_aff_alloc (univ
, aff
);
1069 id
= isl_set_get_tuple_id (subscript_sizes
);
1070 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1071 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1073 /* low <= sub_i <= high */
1074 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1075 ubs
= isl_pw_aff_le_set (index
, ub
);
1076 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1077 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1081 return subscript_sizes
;
1084 /* Build data accesses for DRI. */
1087 build_poly_dr (dr_info
&dri
)
1090 isl_set
*subscript_sizes
;
1091 poly_bb_p pbb
= dri
.pbb
;
1092 data_reference_p dr
= dri
.dr
;
1093 scop_p scop
= PBB_SCOP (pbb
);
1094 isl_id
*id
= isl_id_for_dr (scop
);
1097 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1098 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1099 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1100 isl_dim_out
, nb_out
);
1102 acc
= isl_map_universe (space
);
1103 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_copy (id
));
1106 acc
= pdr_add_alias_set (acc
, dri
);
1107 acc
= pdr_add_memory_accesses (acc
, dri
);
1110 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1111 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1113 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1114 subscript_sizes
= isl_set_nat_universe (space
);
1115 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1117 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1120 new_poly_dr (pbb
, DR_STMT (dr
), DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1121 acc
, subscript_sizes
);
1125 build_poly_sr_1 (poly_bb_p pbb
, gimple
*stmt
, tree var
, enum poly_dr_type kind
,
1126 isl_map
*acc
, isl_set
*subscript_sizes
)
1128 int max_arrays
= PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP
);
1129 /* Each scalar variables has a unique alias set number starting from
1131 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1132 max_arrays
+ SSA_NAME_VERSION (var
));
1134 new_poly_dr (pbb
, stmt
, kind
, add_scalar_version_numbers (acc
, var
),
1138 /* Record all cross basic block scalar variables in PBB. */
1141 build_poly_sr (poly_bb_p pbb
)
1143 scop_p scop
= PBB_SCOP (pbb
);
1144 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1145 vec
<scalar_use
> reads
= gbb
->read_scalar_refs
;
1146 vec
<tree
> writes
= gbb
->write_scalar_refs
;
1148 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1150 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1151 isl_dim_out
, nb_out
);
1152 isl_id
*id
= isl_id_for_dr (scop
);
1153 space
= isl_space_set_tuple_id (space
, isl_dim_set
, isl_id_copy (id
));
1154 isl_map
*acc
= isl_map_universe (isl_space_copy (space
));
1155 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, id
);
1156 isl_set
*subscript_sizes
= isl_set_nat_universe (space
);
1160 FOR_EACH_VEC_ELT (writes
, i
, var
)
1161 build_poly_sr_1 (pbb
, SSA_NAME_DEF_STMT (var
), var
, PDR_WRITE
,
1162 isl_map_copy (acc
), isl_set_copy (subscript_sizes
));
1165 FOR_EACH_VEC_ELT (reads
, i
, use
)
1166 build_poly_sr_1 (pbb
, use
->first
, use
->second
, PDR_READ
, isl_map_copy (acc
),
1167 isl_set_copy (subscript_sizes
));
1170 isl_set_free (subscript_sizes
);
1173 /* Build data references in SCOP. */
1176 build_scop_drs (scop_p scop
)
1180 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1181 build_poly_dr (*dri
);
1184 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1185 build_poly_sr (pbb
);
1188 /* Builds the polyhedral representation for a SESE region. */
1191 build_poly_scop (scop_p scop
)
1193 set_scop_parameter_dim (scop
);
1194 build_scop_iteration_domain (scop
);
1195 build_scop_context (scop
);
1196 add_conditions_to_constraints (scop
);
1198 build_scop_drs (scop
);
1199 build_scop_minimal_scattering (scop
);
1200 build_scop_original_schedule (scop
);
1202 /* This SCoP has been translated to the polyhedral
1204 scop
->poly_scop_p
= true;
1206 #endif /* HAVE_isl */