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 /* Returns the index of the PHI argument defined in the outermost
82 phi_arg_in_outermost_loop (gphi
*phi
)
84 loop_p loop
= gimple_bb (phi
)->loop_father
;
87 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
88 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
90 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
97 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
98 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
101 remove_simple_copy_phi (gphi_iterator
*psi
)
103 gphi
*phi
= psi
->phi ();
104 tree res
= gimple_phi_result (phi
);
105 size_t entry
= phi_arg_in_outermost_loop (phi
);
106 tree init
= gimple_phi_arg_def (phi
, entry
);
107 gassign
*stmt
= gimple_build_assign (res
, init
);
108 edge e
= gimple_phi_arg_edge (phi
, entry
);
110 remove_phi_node (psi
, false);
111 gsi_insert_on_edge_immediate (e
, stmt
);
114 /* Removes an invariant phi node at position PSI by inserting on the
115 loop ENTRY edge the assignment RES = INIT. */
118 remove_invariant_phi (sese_l
®ion
, gphi_iterator
*psi
)
120 gphi
*phi
= psi
->phi ();
121 loop_p loop
= loop_containing_stmt (phi
);
122 tree res
= gimple_phi_result (phi
);
123 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
124 size_t entry
= phi_arg_in_outermost_loop (phi
);
125 edge e
= gimple_phi_arg_edge (phi
, entry
);
128 gimple_seq stmts
= NULL
;
130 if (tree_contains_chrecs (scev
, NULL
))
131 scev
= gimple_phi_arg_def (phi
, entry
);
133 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
134 stmt
= gimple_build_assign (res
, var
);
135 remove_phi_node (psi
, false);
137 gimple_seq_add_stmt (&stmts
, stmt
);
138 gsi_insert_seq_on_edge (e
, stmts
);
139 gsi_commit_edge_inserts ();
140 SSA_NAME_DEF_STMT (res
) = stmt
;
143 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
146 simple_copy_phi_p (gphi
*phi
)
148 if (gimple_phi_num_args (phi
) != 2)
151 tree res
= gimple_phi_result (phi
);
152 return (res
== gimple_phi_arg_def (phi
, 0)
153 || res
== gimple_phi_arg_def (phi
, 1));
156 /* Returns true when the phi node at position PSI is a reduction phi
157 node in REGION. Otherwise moves the pointer PSI to the next phi to
161 reduction_phi_p (sese_l
®ion
, gphi_iterator
*psi
)
164 gphi
*phi
= psi
->phi ();
165 tree res
= gimple_phi_result (phi
);
167 loop
= loop_containing_stmt (phi
);
169 if (simple_copy_phi_p (phi
))
171 /* PRE introduces phi nodes like these, for an example,
172 see id-5.f in the fortran graphite testsuite:
174 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
176 remove_simple_copy_phi (psi
);
180 if (scev_analyzable_p (res
, region
))
182 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
184 if (evolution_function_is_invariant_p (scev
, loop
->num
))
185 remove_invariant_phi (region
, psi
);
192 /* All the other cases are considered reductions. */
196 /* Return an ISL identifier for the polyhedral basic block PBB. */
199 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
202 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
203 return isl_id_alloc (s
->isl_context
, name
, pbb
);
206 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
207 We generate SCATTERING_DIMENSIONS scattering dimensions.
209 The scattering polyhedron consists of these dimensions: scattering,
210 loop_iterators, parameters.
214 | scattering_dimensions = 5
222 | Scattering polyhedron:
224 | scattering: {s1, s2, s3, s4, s5}
225 | loop_iterators: {i}
226 | parameters: {p1, p2}
228 | s1 s2 s3 s4 s5 i p1 p2 1
229 | 1 0 0 0 0 0 0 0 -4 = 0
230 | 0 1 0 0 0 -1 0 0 0 = 0
231 | 0 0 1 0 0 0 0 0 -5 = 0 */
234 build_pbb_minimal_scattering_polyhedrons (isl_aff
*static_sched
, poly_bb_p pbb
,
238 int local_dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
240 /* Remove a sequence dimension if irrelevant to domain of current pbb. */
241 int actual_nb_dim
= 0;
242 for (int i
= 0; i
< nb_sequence_dim
; i
++)
243 if (sequence_dims
[i
] <= local_dim
)
246 /* Build an array that combines sequence dimensions and loops dimensions info.
247 This is used later to compute the static scattering polyhedrons. */
248 bool *sequence_and_loop_dims
= NULL
;
249 if (local_dim
+ actual_nb_dim
> 0)
251 sequence_and_loop_dims
= XNEWVEC (bool, local_dim
+ actual_nb_dim
);
254 for (; i
< local_dim
; i
++)
256 if (sequence_dims
&& sequence_dims
[j
] == i
)
258 /* True for sequence dimension. */
259 sequence_and_loop_dims
[i
+ j
] = true;
262 /* False for loop dimension. */
263 sequence_and_loop_dims
[i
+ j
] = false;
265 /* Fake loops make things shifted by one. */
266 if (sequence_dims
&& sequence_dims
[j
] == i
)
267 sequence_and_loop_dims
[i
+ j
] = true;
270 int scattering_dimensions
= local_dim
+ actual_nb_dim
;
271 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
272 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
), isl_dim_out
,
273 scattering_dimensions
);
274 pbb
->schedule
= isl_map_universe (dm
);
277 for (int i
= 0; i
< scattering_dimensions
; i
++)
279 if (!sequence_and_loop_dims
[i
])
281 /* Iterations of this loop - loop dimension. */
282 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, k
,
288 /* Textual order inside this loop - sequence dimension. */
289 isl_space
*s
= isl_map_get_space (pbb
->schedule
);
290 isl_local_space
*ls
= isl_local_space_from_space (s
);
291 isl_constraint
*c
= isl_equality_alloc (ls
);
292 isl_val
*val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, k
);
293 gcc_assert (val
&& isl_val_is_int (val
));
294 val
= isl_val_neg (val
);
295 c
= isl_constraint_set_constant_val (c
, val
);
296 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
297 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
300 XDELETEVEC (sequence_and_loop_dims
);
301 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
304 /* Build the static schedule for BB. This function minimizes the number of
305 dimensions used for pbb sequences.
307 The following example informally defines the static schedule:
328 Static schedules for A to F:
339 build_scop_minimal_scattering (scop_p scop
)
341 gimple_poly_bb_p previous_gbb
= NULL
;
342 int *temp_for_sequence_dims
= NULL
;
346 /* Go through the pbbs to determine the minimum number of dimensions needed to
347 build the static schedule. */
349 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
351 int dim
= isl_set_dim (pbb
->domain
, isl_dim_set
);
356 /* One extra dimension for the outer fake loop. */
358 temp_for_sequence_dims
= XCNEWVEC (int, nb_dims
);
360 /* Record the number of common loops for each dimension. */
361 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
363 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
368 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
369 temp_for_sequence_dims
[prefix
] += 1;
374 /* Analyze the info in temp_for_sequence_dim and determine the minimal number
375 of sequence dimensions. A dimension that did not appear as common
376 dimension should not be considered as a sequence dimension. */
377 int nb_sequence_params
= 0;
378 for (i
= 0; i
< nb_dims
; i
++)
379 if (temp_for_sequence_dims
[i
] > 0)
380 nb_sequence_params
++;
382 int *sequence_dims
= NULL
;
383 if (nb_sequence_params
> 0)
386 sequence_dims
= XNEWVEC (int, nb_sequence_params
);
387 for (i
= 0; i
< nb_dims
; i
++)
388 if (temp_for_sequence_dims
[i
] > 0)
390 sequence_dims
[j
] = i
;
395 XDELETEVEC (temp_for_sequence_dims
);
397 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
398 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
399 isl_local_space
*local_space
= isl_local_space_from_space (dc
);
400 isl_aff
*static_sched
= isl_aff_zero_on_domain (local_space
);
402 /* We have to start schedules at 0 on the first component and
403 because we cannot compare_prefix_loops against a previous loop,
404 prefix will be equal to zero, and that index will be
405 incremented before copying. */
406 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
409 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
411 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
415 prefix
= nb_common_loops (scop
->scop_info
->region
, previous_gbb
, gbb
);
419 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
421 build_pbb_minimal_scattering_polyhedrons (static_sched
, pbb
,
422 sequence_dims
, nb_sequence_params
);
425 XDELETEVEC (sequence_dims
);
426 isl_aff_free (static_sched
);
429 /* Build the original schedule showing the orginal order of execution
430 of statement instances.
432 The following example shows the original schedule:
448 Static schedules for A to D expressed in a union map:
450 { S_A[i0, i1] -> [i0, i1]; S_B[i0] -> [i0]; S_C[] -> []; S_9[i0] -> [i0] }
455 build_scop_original_schedule (scop_p scop
)
457 isl_space
*space
= isl_set_get_space (scop
->param_context
);
458 isl_union_map
*res
= isl_union_map_empty (space
);
462 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
464 int nb_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
);
465 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
466 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
),
467 isl_dim_out
, nb_dimensions
);
468 isl_map
*mp
= isl_map_universe (dm
);
469 for (int i
= 0; i
< nb_dimensions
; i
++)
470 mp
= isl_map_equate (mp
, isl_dim_in
, i
, isl_dim_out
, i
);
472 res
= isl_union_map_add_map (res
, mp
);
474 scop
->original_schedule
= res
;
478 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
480 /* Extract an affine expression from the chain of recurrence E. */
483 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
485 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
486 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
487 isl_local_space
*ls
= isl_local_space_from_space (space
);
488 unsigned pos
= sese_loop_depth (s
->scop_info
->region
, get_chrec_loop (e
)) - 1;
489 isl_aff
*loop
= isl_aff_set_coefficient_si
490 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
491 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
493 /* Before multiplying, make sure that the result is affine. */
494 gcc_assert (isl_pw_aff_is_cst (rhs
)
495 || isl_pw_aff_is_cst (l
));
497 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
500 /* Extract an affine expression from the mult_expr E. */
503 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
505 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
506 isl_space_copy (space
));
507 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
509 if (!isl_pw_aff_is_cst (lhs
)
510 && !isl_pw_aff_is_cst (rhs
))
512 isl_pw_aff_free (lhs
);
513 isl_pw_aff_free (rhs
);
517 return isl_pw_aff_mul (lhs
, rhs
);
520 /* Return an ISL identifier from the name of the ssa_name E. */
523 isl_id_for_ssa_name (scop_p s
, tree e
)
525 const char *name
= get_name (e
);
529 id
= isl_id_alloc (s
->isl_context
, name
, e
);
533 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
534 id
= isl_id_alloc (s
->isl_context
, name1
, e
);
540 /* Return an ISL identifier for the data reference DR. */
543 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
545 /* Data references all get the same isl_id. They need to be comparable
546 and are distinguished through the first dimension, which contains the
548 return isl_id_alloc (s
->isl_context
, "", 0);
551 /* Extract an affine expression from the ssa_name E. */
554 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
556 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
557 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
559 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
560 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
561 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
562 return isl_pw_aff_alloc (dom
, aff
);
565 /* Extract an affine expression from the gmp constant G. */
568 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
570 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
571 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
572 isl_set
*dom
= isl_set_universe (space
);
573 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
574 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
575 aff
= isl_aff_add_constant_val (aff
, v
);
577 return isl_pw_aff_alloc (dom
, aff
);
580 /* Extract an affine expression from the integer_cst E. */
583 extract_affine_int (tree e
, __isl_take isl_space
*space
)
588 tree_int_to_gmp (e
, g
);
589 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
595 /* Compute pwaff mod 2^width. */
598 wrap (isl_pw_aff
*pwaff
, unsigned width
)
602 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
603 mod
= isl_val_2exp (mod
);
604 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
609 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
610 Otherwise returns -1. */
613 parameter_index_in_region_1 (tree name
, sese_info_p region
)
618 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
620 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
627 /* Extract an affine expression from the tree E in the scop S. */
630 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
632 isl_pw_aff
*lhs
, *rhs
, *res
;
634 if (e
== chrec_dont_know
) {
635 isl_space_free (space
);
639 switch (TREE_CODE (e
))
641 case POLYNOMIAL_CHREC
:
642 res
= extract_affine_chrec (s
, e
, space
);
646 res
= extract_affine_mul (s
, e
, space
);
650 case POINTER_PLUS_EXPR
:
651 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
652 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
653 res
= isl_pw_aff_add (lhs
, rhs
);
657 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
658 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
659 res
= isl_pw_aff_sub (lhs
, rhs
);
664 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
665 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
666 res
= isl_pw_aff_mul (lhs
, rhs
);
670 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->scop_info
)
671 || !invariant_in_sese_p_rec (e
, s
->scop_info
->region
, NULL
));
672 res
= extract_affine_name (s
, e
, space
);
676 res
= extract_affine_int (e
, space
);
677 /* No need to wrap a single integer. */
681 case NON_LVALUE_EXPR
:
682 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
690 tree type
= TREE_TYPE (e
);
691 if (TYPE_UNSIGNED (type
))
692 res
= wrap (res
, TYPE_PRECISION (type
));
697 /* Assign dimension for each parameter in SCOP. */
700 set_scop_parameter_dim (scop_p scop
)
702 sese_info_p region
= scop
->scop_info
;
703 unsigned nbp
= sese_nb_params (region
);
704 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
708 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
709 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
710 isl_id_for_ssa_name (scop
, e
));
712 scop
->param_context
= isl_set_universe (space
);
715 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
716 the constraints for the surrounding loops. */
719 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
721 isl_set
*outer
, isl_set
**doms
)
724 tree nb_iters
= number_of_latch_executions (loop
);
725 sese_l region
= scop
->scop_info
->region
;
726 gcc_assert (loop_in_sese_p (loop
, region
));
728 isl_set
*inner
= isl_set_copy (outer
);
729 int pos
= isl_set_dim (outer
, isl_dim_set
);
735 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
736 isl_space
*space
= isl_set_get_space (inner
);
739 isl_constraint
*c
= isl_inequality_alloc
740 (isl_local_space_from_space (isl_space_copy (space
)));
741 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
742 inner
= isl_set_add_constraint (inner
, c
);
744 /* loop_i <= cst_nb_iters */
745 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
747 c
= isl_inequality_alloc
748 (isl_local_space_from_space (isl_space_copy (space
)));
749 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
750 tree_int_to_gmp (nb_iters
, g
);
751 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
752 c
= isl_constraint_set_constant_val (c
, v
);
753 inner
= isl_set_add_constraint (inner
, c
);
756 /* loop_i <= expr_nb_iters */
757 else if (!chrec_contains_undetermined (nb_iters
))
761 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
763 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
764 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
765 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
766 isl_set_dim (valid
, isl_dim_set
));
767 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
769 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
770 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
772 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
773 isl_pw_aff_copy (aff
));
774 inner
= isl_set_intersect (inner
, le
);
777 if (max_stmt_executions (loop
, &nit
))
779 /* Insert in the context the constraints from the
780 estimation of the number of iterations NIT and the
781 symbolic number of iterations (involving parameter
782 names) NB_ITERS. First, build the affine expression
783 "NIT - NB_ITERS" and then say that it is positive,
784 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
787 wi::to_mpz (nit
, g
, SIGNED
);
788 mpz_sub_ui (g
, g
, 1);
791 = extract_affine_gmp (g
, isl_set_get_space (inner
));
792 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
793 x
= isl_set_project_out (x
, isl_dim_set
, 0,
794 isl_set_dim (x
, isl_dim_set
));
795 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
797 isl_constraint
*c
= isl_inequality_alloc
798 (isl_local_space_from_space (isl_space_copy (space
)));
799 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
800 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
802 c
= isl_constraint_set_constant_val (c
, v
);
803 inner
= isl_set_add_constraint (inner
, c
);
806 isl_pw_aff_free (aff
);
812 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
813 isl_set_copy (inner
), doms
);
817 && loop_in_sese_p (loop
->next
, region
))
818 build_loop_iteration_domains (scop
, loop
->next
, nb
,
819 isl_set_copy (outer
), doms
);
821 doms
[loop
->num
] = inner
;
823 isl_set_free (outer
);
824 isl_space_free (space
);
828 /* Returns a linear expression for tree T evaluated in PBB. */
831 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
833 scop_p scop
= PBB_SCOP (pbb
);
835 t
= scalar_evolution_in_region (scop
->scop_info
->region
, pbb_loop (pbb
), t
);
836 gcc_assert (!automatically_generated_chrec_p (t
));
838 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
841 /* Add conditional statement STMT to pbb. CODE is used as the comparison
842 operator. This allows us to invert the condition or to handle
846 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
848 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
849 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
855 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
859 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
863 cond
= isl_pw_aff_le_set (lhs
, rhs
);
867 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
871 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
875 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
879 isl_pw_aff_free (lhs
);
880 isl_pw_aff_free (rhs
);
884 cond
= isl_set_coalesce (cond
);
885 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
886 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
889 /* Add conditions to the domain of PBB. */
892 add_conditions_to_domain (poly_bb_p pbb
)
896 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
898 if (GBB_CONDITIONS (gbb
).is_empty ())
901 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
902 switch (gimple_code (stmt
))
906 /* Don't constrain on anything else than INTEGER_TYPE. */
907 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
910 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
911 enum tree_code code
= gimple_cond_code (cond_stmt
);
913 /* The conditions for ELSE-branches are inverted. */
914 if (!GBB_CONDITION_CASES (gbb
)[i
])
915 code
= invert_tree_comparison (code
, false);
917 add_condition_to_pbb (pbb
, cond_stmt
, code
);
922 /* Switch statements are not supported right now - fall through. */
930 /* Traverses all the GBBs of the SCOP and add their constraints to the
931 iteration domains. */
934 add_conditions_to_constraints (scop_p scop
)
939 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
940 add_conditions_to_domain (pbb
);
943 /* Add constraints on the possible values of parameter P from the type
947 add_param_constraints (scop_p scop
, graphite_dim_t p
)
949 tree parameter
= SESE_PARAMS (scop
->scop_info
)[p
];
950 tree type
= TREE_TYPE (parameter
);
954 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
955 lb
= lower_bound_in_type (type
, type
);
957 lb
= TYPE_MIN_VALUE (type
);
959 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
960 ub
= upper_bound_in_type (type
, type
);
962 ub
= TYPE_MAX_VALUE (type
);
966 isl_space
*space
= isl_set_get_space (scop
->param_context
);
971 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
973 tree_int_to_gmp (lb
, g
);
974 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
977 c
= isl_constraint_set_constant_val (c
, v
);
978 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
980 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
985 isl_space
*space
= isl_set_get_space (scop
->param_context
);
990 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
993 tree_int_to_gmp (ub
, g
);
994 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
996 c
= isl_constraint_set_constant_val (c
, v
);
997 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
999 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
1003 /* Build the context of the SCOP. The context usually contains extra
1004 constraints that are added to the iteration domains that constrain
1008 build_scop_context (scop_p scop
)
1010 graphite_dim_t p
, n
= scop_nb_params (scop
);
1012 for (p
= 0; p
< n
; p
++)
1013 add_param_constraints (scop
, p
);
1016 /* Build the iteration domains: the loops belonging to the current
1017 SCOP, and that vary for the execution of the current basic block.
1018 Returns false if there is no loop in SCOP. */
1021 build_scop_iteration_domain (scop_p scop
)
1023 sese_info_p region
= scop
->scop_info
;
1024 int nb_loops
= number_of_loops (cfun
);
1025 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1029 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1030 if (!loop_in_sese_p (loop_outer (loop
), region
->region
))
1031 build_loop_iteration_domains (scop
, loop
, 0,
1032 isl_set_copy (scop
->param_context
), doms
);
1035 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1037 loop
= pbb_loop (pbb
);
1039 if (doms
[loop
->num
])
1040 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1042 pbb
->domain
= isl_set_copy (scop
->param_context
);
1044 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1045 isl_id_for_pbb (scop
, pbb
));
1048 for (int i
= 0; i
< nb_loops
; i
++)
1050 isl_set_free (doms
[i
]);
1055 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1056 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1057 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1061 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
1063 isl_constraint
*c
= isl_equality_alloc
1064 (isl_local_space_from_space (isl_map_get_space (acc
)));
1065 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
1066 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1068 return isl_map_add_constraint (acc
, c
);
1071 /* Assign the affine expression INDEX to the output dimension POS of
1072 MAP and return the result. */
1075 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1078 int len
= isl_map_dim (map
, isl_dim_out
);
1081 index_map
= isl_map_from_pw_aff (index
);
1082 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1083 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1085 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1086 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1087 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1088 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1090 return isl_map_intersect (map
, index_map
);
1093 /* Add to ACCESSES polyhedron equalities defining the access functions
1094 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1095 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1096 PBB is the poly_bb_p that contains the data reference DR. */
1099 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
1101 data_reference_p dr
= dri
.dr
;
1102 poly_bb_p pbb
= dri
.pbb
;
1103 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1104 scop_p scop
= PBB_SCOP (pbb
);
1106 for (i
= 0; i
< nb_subscripts
; i
++)
1109 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1111 aff
= extract_affine (scop
, afn
,
1112 isl_space_domain (isl_map_get_space (acc
)));
1113 acc
= set_index (acc
, i
+ 1, aff
);
1119 /* Add constrains representing the size of the accessed data to the
1120 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1121 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1125 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1126 data_reference_p dr
)
1128 tree ref
= DR_REF (dr
);
1130 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1131 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1133 if (TREE_CODE (ref
) != ARRAY_REF
)
1134 return subscript_sizes
;
1136 tree low
= array_ref_low_bound (ref
);
1137 tree high
= array_ref_up_bound (ref
);
1139 /* XXX The PPL code dealt separately with
1140 subscript - low >= 0 and high - subscript >= 0 in case one of
1141 the two bounds isn't known. Do the same here? */
1143 if (tree_fits_shwi_p (low
)
1145 && tree_fits_shwi_p (high
)
1146 /* 1-element arrays at end of structures may extend over
1147 their declared size. */
1148 && !(array_at_struct_end_p (ref
)
1149 && operand_equal_p (low
, high
, 0)))
1153 isl_set
*univ
, *lbs
, *ubs
;
1156 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1157 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1158 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1161 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1162 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1163 isl_set_dim (valid
, isl_dim_set
));
1164 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
1166 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1167 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1168 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1169 index
= isl_pw_aff_alloc (univ
, aff
);
1171 id
= isl_set_get_tuple_id (subscript_sizes
);
1172 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1173 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1175 /* low <= sub_i <= high */
1176 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1177 ubs
= isl_pw_aff_le_set (index
, ub
);
1178 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1179 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1183 return subscript_sizes
;
1186 /* Build data accesses for DR in PBB. */
1189 build_poly_dr (dr_info
&dri
)
1192 isl_set
*subscript_sizes
;
1193 poly_bb_p pbb
= dri
.pbb
;
1194 data_reference_p dr
= dri
.dr
;
1195 scop_p scop
= PBB_SCOP (pbb
);
1198 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1199 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1200 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1201 isl_dim_out
, nb_out
);
1203 acc
= isl_map_universe (space
);
1204 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1207 acc
= pdr_add_alias_set (acc
, dri
);
1208 acc
= pdr_add_memory_accesses (acc
, dri
);
1211 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1212 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1213 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1215 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1216 subscript_sizes
= isl_set_nat_universe (space
);
1217 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1219 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1223 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1224 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1227 /* Compute alias-sets for all data references in DRS. */
1230 build_alias_set (scop_p scop
)
1232 int num_vertices
= scop
->drs
.length ();
1233 struct graph
*g
= new_graph (num_vertices
);
1238 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1239 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1240 if (dr_may_alias_p (dr1
->dr
, dr2
->dr
, true))
1246 all_vertices
= XNEWVEC (int, num_vertices
);
1247 for (i
= 0; i
< num_vertices
; i
++)
1248 all_vertices
[i
] = i
;
1250 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1251 free (all_vertices
);
1253 for (i
= 0; i
< g
->n_vertices
; i
++)
1254 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1259 /* Build data references in SCOP. */
1262 build_scop_drs (scop_p scop
)
1267 /* Remove all the PBBs that do not have data references: these basic
1268 blocks are not handled in the polyhedral representation. */
1269 for (i
= 0; scop
->pbbs
.iterate (i
, &pbb
); i
++)
1270 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1272 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
1274 scop
->pbbs
.ordered_remove (i
);
1278 data_reference_p dr
;
1279 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1281 FOR_EACH_VEC_ELT (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
)
1282 scop
->drs
.safe_push (dr_info (dr
, pbb
));
1284 build_alias_set (scop
);
1287 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1288 build_poly_dr (*dri
);
1291 /* Analyze all the data references of STMTS and add them to the
1292 GBB_DATA_REFS vector of BB. */
1295 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1297 sese_l region
= scop
->scop_info
->region
;
1298 if (!bb_in_sese_p (bb
, region
))
1301 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1302 loop_p loop
= bb
->loop_father
;
1303 if (!loop_in_sese_p (loop
, region
))
1306 gimple_poly_bb_p gbb
= gbb_from_bb (bb
);
1310 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1312 if (is_gimple_debug (stmt
))
1315 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1316 &GBB_DATA_REFS (gbb
));
1320 /* Insert STMT at the end of the STMTS sequence and then insert the
1321 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1325 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1326 gimple_stmt_iterator insert_gsi
)
1328 gimple_stmt_iterator gsi
;
1329 auto_vec
<gimple
*, 3> x
;
1331 gimple_seq_add_stmt (&stmts
, stmt
);
1332 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1333 x
.safe_push (gsi_stmt (gsi
));
1335 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1336 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1339 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1342 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1344 gimple_stmt_iterator gsi
;
1345 auto_vec
<gimple
*, 3> x
;
1347 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1348 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1350 gimple_seq_add_stmt (&stmts
, stmt
);
1352 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1353 x
.safe_push (gsi_stmt (gsi
));
1355 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
1357 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
1358 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1362 gsi
= gsi_for_stmt (after_stmt
);
1363 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1366 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
1369 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
1372 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
1374 vec
<data_reference_p
> drs
;
1376 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1377 gimple_poly_bb_p gbb1
= new_gimple_poly_bb (bb
, drs
);
1378 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
1379 int index
, n
= scop
->pbbs
.length ();
1381 for (index
= 0; index
< n
; index
++)
1382 if (scop
->pbbs
[index
] == pbb
)
1385 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1386 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1387 isl_id_for_pbb (scop
, pbb1
));
1389 GBB_PBB (gbb1
) = pbb1
;
1390 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1391 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1392 scop
->pbbs
.safe_insert (index
+ 1, pbb1
);
1395 /* Insert on edge E the assignment "RES := EXPR". */
1398 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
1400 gimple_seq stmts
= NULL
;
1401 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1402 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1403 auto_vec
<gimple
*, 3> x
;
1405 gimple_seq_add_stmt (&stmts
, stmt
);
1406 gimple_stmt_iterator gsi
;
1407 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1408 x
.safe_push (gsi_stmt (gsi
));
1410 gsi_insert_seq_on_edge (e
, stmts
);
1411 gsi_commit_edge_inserts ();
1412 basic_block bb
= gimple_bb (stmt
);
1414 if (!bb_in_sese_p (bb
, scop
->scop_info
->region
))
1417 if (!gbb_from_bb (bb
))
1418 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
1420 analyze_drs_in_stmts (scop
, bb
, x
);
1423 /* Creates a zero dimension array of the same type as VAR. */
1426 create_zero_dim_array (tree var
, const char *base_name
)
1428 tree index_type
= build_index_type (integer_zero_node
);
1429 tree elt_type
= TREE_TYPE (var
);
1430 tree array_type
= build_array_type (elt_type
, index_type
);
1431 tree base
= create_tmp_var (array_type
, base_name
);
1433 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1437 /* Returns true when PHI is a loop close phi node. */
1440 scalar_close_phi_node_p (gimple
*phi
)
1442 if (gimple_code (phi
) != GIMPLE_PHI
1443 || virtual_operand_p (gimple_phi_result (phi
)))
1446 /* Note that loop close phi nodes should have a single argument
1447 because we translated the representation into a canonical form
1448 before Graphite: see canonicalize_loop_closed_ssa_form. */
1449 return (gimple_phi_num_args (phi
) == 1);
1452 /* For a definition DEF in REGION, propagates the expression EXPR in
1453 all the uses of DEF outside REGION. */
1456 propagate_expr_outside_region (tree def
, tree expr
, sese_l
®ion
)
1459 bool replaced_once
= false;
1461 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
1463 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
1466 imm_use_iterator imm_iter
;
1468 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1469 if (!is_gimple_debug (use_stmt
)
1470 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
1473 use_operand_p use_p
;
1475 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1476 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
1477 && (replaced_once
= true))
1478 replace_exp (use_p
, expr
);
1480 update_stmt (use_stmt
);
1485 gsi_insert_seq_on_edge (region
.entry
, stmts
);
1486 gsi_commit_edge_inserts ();
1490 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1491 dimension array for it. */
1494 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
1496 sese_l region
= scop
->scop_info
->region
;
1497 gimple
*phi
= gsi_stmt (*psi
);
1498 tree res
= gimple_phi_result (phi
);
1499 basic_block bb
= gimple_bb (phi
);
1500 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1501 tree arg
= gimple_phi_arg_def (phi
, 0);
1504 /* Note that loop close phi nodes should have a single argument
1505 because we translated the representation into a canonical form
1506 before Graphite: see canonicalize_loop_closed_ssa_form. */
1507 gcc_assert (gimple_phi_num_args (phi
) == 1);
1509 /* The phi node can be a non close phi node, when its argument is
1510 invariant, or a default definition. */
1511 if (is_gimple_min_invariant (arg
)
1512 || SSA_NAME_IS_DEFAULT_DEF (arg
))
1514 propagate_expr_outside_region (res
, arg
, region
);
1519 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
1521 propagate_expr_outside_region (res
, arg
, region
);
1522 stmt
= gimple_build_assign (res
, arg
);
1523 remove_phi_node (psi
, false);
1524 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1528 /* If res is scev analyzable and is not a scalar value, it is safe
1529 to ignore the close phi node: it will be code generated in the
1530 out of Graphite pass. */
1531 else if (scev_analyzable_p (res
, region
))
1533 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
1536 if (!loop_in_sese_p (loop
, region
))
1538 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
1539 scev
= scalar_evolution_in_region (region
, loop
, arg
);
1540 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
1543 scev
= scalar_evolution_in_region (region
, loop
, res
);
1545 if (tree_does_not_contain_chrecs (scev
))
1546 propagate_expr_outside_region (res
, scev
, region
);
1553 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
1555 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1557 if (TREE_CODE (arg
) == SSA_NAME
)
1558 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1559 SSA_NAME_DEF_STMT (arg
));
1561 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
1562 zero_dim_array
, arg
);
1565 remove_phi_node (psi
, false);
1566 SSA_NAME_DEF_STMT (res
) = stmt
;
1568 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1571 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1572 dimension array for it. */
1575 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
1577 gphi
*phi
= psi
->phi ();
1578 basic_block bb
= gimple_bb (phi
);
1579 tree res
= gimple_phi_result (phi
);
1580 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
1582 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1584 tree arg
= gimple_phi_arg_def (phi
, i
);
1585 edge e
= gimple_phi_arg_edge (phi
, i
);
1587 /* Avoid the insertion of code in the loop latch to please the
1588 pattern matching of the vectorizer. */
1589 if (TREE_CODE (arg
) == SSA_NAME
1590 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
1591 && e
->src
== bb
->loop_father
->latch
)
1592 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1593 SSA_NAME_DEF_STMT (arg
));
1595 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
1598 gimple
*stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1599 remove_phi_node (psi
, false);
1600 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1603 /* Rewrite the degenerate phi node at position PSI from the degenerate
1604 form "x = phi (y, y, ..., y)" to "x = y". */
1607 rewrite_degenerate_phi (gphi_iterator
*psi
)
1609 gphi
*phi
= psi
->phi ();
1610 tree res
= gimple_phi_result (phi
);
1612 basic_block bb
= gimple_bb (phi
);
1613 tree rhs
= degenerate_phi_result (phi
);
1616 gimple
*stmt
= gimple_build_assign (res
, rhs
);
1617 remove_phi_node (psi
, false);
1619 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1620 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1623 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1626 rewrite_reductions_out_of_ssa (scop_p scop
)
1630 FOR_EACH_VEC_ELT (scop
->scop_info
->bbs
, i
, bb
)
1631 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
1633 gphi
*phi
= psi
.phi ();
1635 if (virtual_operand_p (gimple_phi_result (phi
)))
1641 if (gimple_phi_num_args (phi
) > 1
1642 && degenerate_phi_result (phi
))
1643 rewrite_degenerate_phi (&psi
);
1645 else if (scalar_close_phi_node_p (phi
))
1646 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1648 else if (reduction_phi_p (scop
->scop_info
->region
, &psi
))
1649 rewrite_phi_out_of_ssa (scop
, &psi
);
1652 update_ssa (TODO_update_ssa
);
1653 checking_verify_loop_closed_ssa (true);
1656 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
1657 read from ZERO_DIM_ARRAY. */
1660 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
1661 tree def
, gimple
*use_stmt
)
1663 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1665 tree name
= copy_ssa_name (def
);
1666 gimple
*name_stmt
= gimple_build_assign (name
, zero_dim_array
);
1668 gimple_assign_set_lhs (name_stmt
, name
);
1669 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
1672 use_operand_p use_p
;
1673 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1674 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
1675 replace_exp (use_p
, name
);
1677 update_stmt (use_stmt
);
1680 /* For every definition DEF in the SCOP that is used outside the scop,
1681 insert a closing-scop definition in the basic block just after this
1685 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
1687 tree var
= create_tmp_reg (TREE_TYPE (def
));
1688 tree new_name
= make_ssa_name (var
, stmt
);
1689 bool needs_copy
= false;
1690 sese_l region
= scop
->scop_info
->region
;
1692 imm_use_iterator imm_iter
;
1694 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1696 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
1698 use_operand_p use_p
;
1699 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1701 SET_USE (use_p
, new_name
);
1703 update_stmt (use_stmt
);
1708 /* Insert in the empty BB just after the scop a use of DEF such
1709 that the rewrite of cross_bb_scalar_dependences won't insert
1710 arrays everywhere else. */
1713 gimple
*assign
= gimple_build_assign (new_name
, def
);
1714 gimple_stmt_iterator psi
= gsi_after_labels (region
.exit
->dest
);
1716 update_stmt (assign
);
1717 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
1721 /* Rewrite the scalar dependences crossing the boundary of the BB
1722 containing STMT with an array. Return true when something has been
1726 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
1728 sese_l region
= scop
->scop_info
->region
;
1729 gimple
*stmt
= gsi_stmt (*gsi
);
1730 imm_use_iterator imm_iter
;
1732 tree zero_dim_array
= NULL_TREE
;
1736 switch (gimple_code (stmt
))
1739 def
= gimple_assign_lhs (stmt
);
1743 def
= gimple_call_lhs (stmt
);
1751 || !is_gimple_reg (def
))
1754 if (scev_analyzable_p (def
, region
))
1756 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
1757 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
1759 if (tree_contains_chrecs (scev
, NULL
))
1762 propagate_expr_outside_region (def
, scev
, region
);
1766 basic_block def_bb
= gimple_bb (stmt
);
1768 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
1770 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1771 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
1774 gphi_iterator psi
= gsi_for_phi (phi
);
1776 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
1777 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1779 rewrite_phi_out_of_ssa (scop
, &psi
);
1782 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1783 if (gimple_code (use_stmt
) != GIMPLE_PHI
1784 && def_bb
!= gimple_bb (use_stmt
)
1785 && !is_gimple_debug (use_stmt
)
1788 if (!zero_dim_array
)
1790 zero_dim_array
= create_zero_dim_array
1791 (def
, "Cross_BB_scalar_dependence");
1792 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
1793 SSA_NAME_DEF_STMT (def
));
1797 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
1801 update_ssa (TODO_update_ssa
);
1806 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1809 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
1811 gimple_stmt_iterator psi
;
1812 sese_l region
= scop
->scop_info
->region
;
1813 bool changed
= false;
1815 /* Create an extra empty BB after the scop. */
1816 split_edge (region
.exit
);
1820 FOR_EACH_VEC_ELT (scop
->scop_info
->bbs
, i
, bb
)
1821 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1822 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
1827 update_ssa (TODO_update_ssa
);
1828 checking_verify_loop_closed_ssa (true);
1832 /* Builds the polyhedral representation for a SESE region. */
1835 build_poly_scop (scop_p scop
)
1837 set_scop_parameter_dim (scop
);
1838 build_scop_iteration_domain (scop
);
1839 build_scop_context (scop
);
1840 add_conditions_to_constraints (scop
);
1842 /* Rewrite out of SSA only after having translated the
1843 representation to the polyhedral representation to avoid scev
1844 analysis failures. That means that these functions will insert
1845 new data references that they create in the right place. */
1846 rewrite_reductions_out_of_ssa (scop
);
1847 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
1849 build_scop_drs (scop
);
1850 build_scop_minimal_scattering (scop
);
1851 build_scop_original_schedule (scop
);
1853 /* This SCoP has been translated to the polyhedral
1855 scop
->poly_scop_p
= true;
1857 #endif /* HAVE_isl */