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"
71 static const unsigned ssa_name_version_typesize
= sizeof(unsigned);
73 /* Assigns to RES the value of the INTEGER_CST T. */
76 tree_int_to_gmp (tree t
, mpz_t res
)
78 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
81 /* Returns the index of the PHI argument defined in the outermost
85 phi_arg_in_outermost_loop (gphi
*phi
)
87 loop_p loop
= gimple_bb (phi
)->loop_father
;
90 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
91 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
93 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
100 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
101 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
104 remove_simple_copy_phi (gphi_iterator
*psi
)
106 gphi
*phi
= psi
->phi ();
107 tree res
= gimple_phi_result (phi
);
108 size_t entry
= phi_arg_in_outermost_loop (phi
);
109 tree init
= gimple_phi_arg_def (phi
, entry
);
110 gassign
*stmt
= gimple_build_assign (res
, init
);
111 edge e
= gimple_phi_arg_edge (phi
, entry
);
113 remove_phi_node (psi
, false);
114 gsi_insert_on_edge_immediate (e
, stmt
);
117 /* Removes an invariant phi node at position PSI by inserting on the
118 loop ENTRY edge the assignment RES = INIT. */
121 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
123 gphi
*phi
= psi
->phi ();
124 loop_p loop
= loop_containing_stmt (phi
);
125 tree res
= gimple_phi_result (phi
);
126 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
127 size_t entry
= phi_arg_in_outermost_loop (phi
);
128 edge e
= gimple_phi_arg_edge (phi
, entry
);
131 gimple_seq stmts
= NULL
;
133 if (tree_contains_chrecs (scev
, NULL
))
134 scev
= gimple_phi_arg_def (phi
, entry
);
136 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
137 stmt
= gimple_build_assign (res
, var
);
138 remove_phi_node (psi
, false);
140 gimple_seq_add_stmt (&stmts
, stmt
);
141 gsi_insert_seq_on_edge (e
, stmts
);
142 gsi_commit_edge_inserts ();
143 SSA_NAME_DEF_STMT (res
) = stmt
;
146 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
149 simple_copy_phi_p (gphi
*phi
)
151 if (gimple_phi_num_args (phi
) != 2)
154 tree res
= gimple_phi_result (phi
);
155 return (res
== gimple_phi_arg_def (phi
, 0)
156 || res
== gimple_phi_arg_def (phi
, 1));
159 /* Returns true when the phi node at position PSI is a reduction phi
160 node in REGION. Otherwise moves the pointer PSI to the next phi to
164 reduction_phi_p (sese region
, gphi_iterator
*psi
)
167 gphi
*phi
= psi
->phi ();
168 tree res
= gimple_phi_result (phi
);
170 loop
= loop_containing_stmt (phi
);
172 if (simple_copy_phi_p (phi
))
174 /* PRE introduces phi nodes like these, for an example,
175 see id-5.f in the fortran graphite testsuite:
177 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
179 remove_simple_copy_phi (psi
);
183 if (scev_analyzable_p (res
, region
))
185 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
187 if (evolution_function_is_invariant_p (scev
, loop
->num
))
188 remove_invariant_phi (region
, psi
);
195 /* All the other cases are considered reductions. */
199 /* Return an ISL identifier for the polyhedral basic block PBB. */
202 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
204 char name
[ssa_name_version_typesize
];
205 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
206 return isl_id_alloc (s
->isl_context
, name
, pbb
);
209 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
210 We generate SCATTERING_DIMENSIONS scattering dimensions.
212 The scattering polyhedron consists of these dimensions: scattering,
213 loop_iterators, parameters.
217 | scattering_dimensions = 5
225 | Scattering polyhedron:
227 | scattering: {s1, s2, s3, s4, s5}
228 | loop_iterators: {i}
229 | parameters: {p1, p2}
231 | s1 s2 s3 s4 s5 i p1 p2 1
232 | 1 0 0 0 0 0 0 0 -4 = 0
233 | 0 1 0 0 0 -1 0 0 0 = 0
234 | 0 0 1 0 0 0 0 0 -5 = 0 */
237 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
242 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
244 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
245 isl_space
*dm
= isl_space_add_dims (isl_space_from_domain (dc
),
246 isl_dim_out
, scattering_dimensions
);
247 pbb
->schedule
= isl_map_universe (dm
);
249 for (int i
= 0; i
< scattering_dimensions
; i
++)
251 /* Textual order inside this loop. */
254 isl_constraint
*c
= isl_equality_alloc
255 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
257 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
258 gcc_assert (val
&& isl_val_is_int (val
));
260 val
= isl_val_neg (val
);
261 c
= isl_constraint_set_constant_val (c
, val
);
262 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
263 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
266 /* Iterations of this loop. */
267 else /* if ((i % 2) == 1) */
269 int loop
= (i
- 1) / 2;
270 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
275 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
278 /* Build for BB the static schedule.
280 The static schedule is a Dewey numbering of the abstract syntax
281 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
283 The following example informally defines the static schedule:
302 Static schedules for A to F:
315 build_scop_scattering (scop_p scop
)
317 gimple_poly_bb_p previous_gbb
= NULL
;
318 isl_space
*dc
= isl_set_get_space (scop
->param_context
);
319 isl_aff
*static_sched
;
321 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
322 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
324 /* We have to start schedules at 0 on the first component and
325 because we cannot compare_prefix_loops against a previous loop,
326 prefix will be equal to zero, and that index will be
327 incremented before copying. */
328 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
332 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
334 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
338 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
342 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
344 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
347 isl_aff_free (static_sched
);
350 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
352 /* Extract an affine expression from the chain of recurrence E. */
355 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
357 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
358 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
359 isl_local_space
*ls
= isl_local_space_from_space (space
);
360 unsigned pos
= sese_loop_depth (SCOP_REGION (s
), get_chrec_loop (e
)) - 1;
361 isl_aff
*loop
= isl_aff_set_coefficient_si
362 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
363 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
365 /* Before multiplying, make sure that the result is affine. */
366 gcc_assert (isl_pw_aff_is_cst (rhs
)
367 || isl_pw_aff_is_cst (l
));
369 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
372 /* Extract an affine expression from the mult_expr E. */
375 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
377 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
378 isl_space_copy (space
));
379 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
381 if (!isl_pw_aff_is_cst (lhs
)
382 && !isl_pw_aff_is_cst (rhs
))
384 isl_pw_aff_free (lhs
);
385 isl_pw_aff_free (rhs
);
389 return isl_pw_aff_mul (lhs
, rhs
);
392 /* Return an ISL identifier from the name of the ssa_name E. */
395 isl_id_for_ssa_name (scop_p s
, tree e
)
397 const char *name
= get_name (e
);
401 id
= isl_id_alloc (s
->isl_context
, name
, e
);
404 char name1
[ssa_name_version_typesize
];
405 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
406 id
= isl_id_alloc (s
->isl_context
, name1
, e
);
412 /* Return an ISL identifier for the data reference DR. */
415 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
417 /* Data references all get the same isl_id. They need to be comparable
418 and are distinguished through the first dimension, which contains the
420 return isl_id_alloc (s
->isl_context
, "", 0);
423 /* Extract an affine expression from the ssa_name E. */
426 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
428 isl_id
*id
= isl_id_for_ssa_name (s
, e
);
429 int dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
431 isl_set
*dom
= isl_set_universe (isl_space_copy (space
));
432 isl_aff
*aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
433 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
434 return isl_pw_aff_alloc (dom
, aff
);
437 /* Extract an affine expression from the gmp constant G. */
440 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
442 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
443 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
444 isl_set
*dom
= isl_set_universe (space
);
445 isl_ctx
*ct
= isl_aff_get_ctx (aff
);
446 isl_val
*v
= isl_val_int_from_gmp (ct
, g
);
447 aff
= isl_aff_add_constant_val (aff
, v
);
449 return isl_pw_aff_alloc (dom
, aff
);
452 /* Extract an affine expression from the integer_cst E. */
455 extract_affine_int (tree e
, __isl_take isl_space
*space
)
460 tree_int_to_gmp (e
, g
);
461 isl_pw_aff
*res
= extract_affine_gmp (g
, space
);
467 /* Compute pwaff mod 2^width. */
470 wrap (isl_pw_aff
*pwaff
, unsigned width
)
474 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
475 mod
= isl_val_2exp (mod
);
476 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
481 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
482 Otherwise returns -1. */
485 parameter_index_in_region_1 (tree name
, sese region
)
490 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
492 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
499 /* Extract an affine expression from the tree E in the scop S. */
502 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
504 isl_pw_aff
*lhs
, *rhs
, *res
;
506 if (e
== chrec_dont_know
) {
507 isl_space_free (space
);
511 switch (TREE_CODE (e
))
513 case POLYNOMIAL_CHREC
:
514 res
= extract_affine_chrec (s
, e
, space
);
518 res
= extract_affine_mul (s
, e
, space
);
522 case POINTER_PLUS_EXPR
:
523 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
524 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
525 res
= isl_pw_aff_add (lhs
, rhs
);
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_sub (lhs
, rhs
);
536 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
537 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
538 res
= isl_pw_aff_mul (lhs
, rhs
);
542 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->region
)
543 || !invariant_in_sese_p_rec (e
, s
->region
));
544 res
= extract_affine_name (s
, e
, space
);
548 res
= extract_affine_int (e
, space
);
549 /* No need to wrap a single integer. */
553 case NON_LVALUE_EXPR
:
554 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
562 tree type
= TREE_TYPE (e
);
563 if (TYPE_UNSIGNED (type
))
564 res
= wrap (res
, TYPE_PRECISION (type
));
569 /* Assign dimension for each parameter in SCOP. */
572 set_scop_parameter_dim (scop_p scop
)
574 sese region
= SCOP_REGION (scop
);
575 unsigned nbp
= sese_nb_params (region
);
576 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, nbp
, 0);
580 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
581 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
582 isl_id_for_ssa_name (scop
, e
));
584 scop
->param_context
= isl_set_universe (space
);
587 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
588 the constraints for the surrounding loops. */
591 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
593 isl_set
*outer
, isl_set
**doms
)
596 tree nb_iters
= number_of_latch_executions (loop
);
597 sese region
= SCOP_REGION (scop
);
599 isl_set
*inner
= isl_set_copy (outer
);
600 int pos
= isl_set_dim (outer
, isl_dim_set
);
606 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
607 isl_space
*space
= isl_set_get_space (inner
);
610 isl_constraint
*c
= isl_inequality_alloc
611 (isl_local_space_from_space (isl_space_copy (space
)));
612 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
613 inner
= isl_set_add_constraint (inner
, c
);
615 /* loop_i <= cst_nb_iters */
616 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
618 c
= isl_inequality_alloc
619 (isl_local_space_from_space (isl_space_copy (space
)));
620 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
621 tree_int_to_gmp (nb_iters
, g
);
622 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
623 c
= isl_constraint_set_constant_val (c
, v
);
624 inner
= isl_set_add_constraint (inner
, c
);
627 /* loop_i <= expr_nb_iters */
628 else if (!chrec_contains_undetermined (nb_iters
))
632 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
634 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
635 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
636 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
637 isl_set_dim (valid
, isl_dim_set
));
638 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
640 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
641 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
643 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
644 isl_pw_aff_copy (aff
));
645 inner
= isl_set_intersect (inner
, le
);
648 if (max_stmt_executions (loop
, &nit
))
650 /* Insert in the context the constraints from the
651 estimation of the number of iterations NIT and the
652 symbolic number of iterations (involving parameter
653 names) NB_ITERS. First, build the affine expression
654 "NIT - NB_ITERS" and then say that it is positive,
655 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
658 wi::to_mpz (nit
, g
, SIGNED
);
659 mpz_sub_ui (g
, g
, 1);
662 = extract_affine_gmp (g
, isl_set_get_space (inner
));
663 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
664 x
= isl_set_project_out (x
, isl_dim_set
, 0,
665 isl_set_dim (x
, isl_dim_set
));
666 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
668 isl_constraint
*c
= isl_inequality_alloc
669 (isl_local_space_from_space (isl_space_copy (space
)));
670 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
671 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
673 c
= isl_constraint_set_constant_val (c
, v
);
674 inner
= isl_set_add_constraint (inner
, c
);
677 isl_pw_aff_free (aff
);
682 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
683 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
684 isl_set_copy (inner
), doms
);
688 && loop_in_sese_p (loop
->next
, region
))
689 build_loop_iteration_domains (scop
, loop
->next
, nb
,
690 isl_set_copy (outer
), doms
);
692 doms
[loop
->num
] = inner
;
694 isl_set_free (outer
);
695 isl_space_free (space
);
699 /* Returns a linear expression for tree T evaluated in PBB. */
702 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
704 scop_p scop
= PBB_SCOP (pbb
);
706 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
707 gcc_assert (!automatically_generated_chrec_p (t
));
709 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
712 /* Add conditional statement STMT to pbb. CODE is used as the comparison
713 operator. This allows us to invert the condition or to handle
717 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
719 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
720 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
726 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
730 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
734 cond
= isl_pw_aff_le_set (lhs
, rhs
);
738 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
742 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
746 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
750 isl_pw_aff_free (lhs
);
751 isl_pw_aff_free (rhs
);
755 cond
= isl_set_coalesce (cond
);
756 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
757 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
760 /* Add conditions to the domain of PBB. */
763 add_conditions_to_domain (poly_bb_p pbb
)
767 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
769 if (GBB_CONDITIONS (gbb
).is_empty ())
772 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
773 switch (gimple_code (stmt
))
777 /* Don't constrain on anything else than INTEGER_TYPE. */
778 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
781 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
782 enum tree_code code
= gimple_cond_code (cond_stmt
);
784 /* The conditions for ELSE-branches are inverted. */
785 if (!GBB_CONDITION_CASES (gbb
)[i
])
786 code
= invert_tree_comparison (code
, false);
788 add_condition_to_pbb (pbb
, cond_stmt
, code
);
793 /* Switch statements are not supported right now - fall through. */
801 /* Traverses all the GBBs of the SCOP and add their constraints to the
802 iteration domains. */
805 add_conditions_to_constraints (scop_p scop
)
810 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
811 add_conditions_to_domain (pbb
);
814 /* Add constraints on the possible values of parameter P from the type
818 add_param_constraints (scop_p scop
, graphite_dim_t p
)
820 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
821 tree type
= TREE_TYPE (parameter
);
825 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
826 lb
= lower_bound_in_type (type
, type
);
828 lb
= TYPE_MIN_VALUE (type
);
830 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
831 ub
= upper_bound_in_type (type
, type
);
833 ub
= TYPE_MAX_VALUE (type
);
837 isl_space
*space
= isl_set_get_space (scop
->param_context
);
842 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
844 tree_int_to_gmp (lb
, g
);
845 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
848 c
= isl_constraint_set_constant_val (c
, v
);
849 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
851 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
856 isl_space
*space
= isl_set_get_space (scop
->param_context
);
861 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
864 tree_int_to_gmp (ub
, g
);
865 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
867 c
= isl_constraint_set_constant_val (c
, v
);
868 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
870 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
874 /* Build the context of the SCOP. The context usually contains extra
875 constraints that are added to the iteration domains that constrain
879 build_scop_context (scop_p scop
)
881 graphite_dim_t p
, n
= scop_nb_params (scop
);
883 for (p
= 0; p
< n
; p
++)
884 add_param_constraints (scop
, p
);
887 /* Build the iteration domains: the loops belonging to the current
888 SCOP, and that vary for the execution of the current basic block.
889 Returns false if there is no loop in SCOP. */
892 build_scop_iteration_domain (scop_p scop
)
894 sese region
= SCOP_REGION (scop
);
895 int nb_loops
= number_of_loops (cfun
);
896 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
900 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
901 if (!loop_in_sese_p (loop_outer (loop
), region
))
902 build_loop_iteration_domains (scop
, loop
, 0,
903 isl_set_copy (scop
->param_context
), doms
);
906 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
908 loop
= pbb_loop (pbb
);
911 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
913 pbb
->domain
= isl_set_copy (scop
->param_context
);
915 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
916 isl_id_for_pbb (scop
, pbb
));
919 for (int i
= 0; i
< nb_loops
; i
++)
921 isl_set_free (doms
[i
]);
926 /* Add a constrain to the ACCESSES polyhedron for the alias set of
927 data reference DR. ACCESSP_NB_DIMS is the dimension of the
928 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
932 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
935 int alias_set_num
= 0;
936 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
938 if (bap
&& bap
->alias_set
)
939 alias_set_num
= *(bap
->alias_set
);
941 c
= isl_equality_alloc
942 (isl_local_space_from_space (isl_map_get_space (acc
)));
943 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
944 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
946 return isl_map_add_constraint (acc
, c
);
949 /* Assign the affine expression INDEX to the output dimension POS of
950 MAP and return the result. */
953 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
956 int len
= isl_map_dim (map
, isl_dim_out
);
959 index_map
= isl_map_from_pw_aff (index
);
960 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
961 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
963 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
964 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
965 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
966 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
968 return isl_map_intersect (map
, index_map
);
971 /* Add to ACCESSES polyhedron equalities defining the access functions
972 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
973 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
974 PBB is the poly_bb_p that contains the data reference DR. */
977 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
979 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
980 scop_p scop
= PBB_SCOP (pbb
);
982 for (i
= 0; i
< nb_subscripts
; i
++)
985 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
987 aff
= extract_affine (scop
, afn
,
988 isl_space_domain (isl_map_get_space (acc
)));
989 acc
= set_index (acc
, i
+ 1, aff
);
995 /* Add constrains representing the size of the accessed data to the
996 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
997 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1001 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1002 data_reference_p dr
)
1004 tree ref
= DR_REF (dr
);
1006 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1007 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1009 if (TREE_CODE (ref
) != ARRAY_REF
)
1010 return subscript_sizes
;
1012 tree low
= array_ref_low_bound (ref
);
1013 tree high
= array_ref_up_bound (ref
);
1015 /* XXX The PPL code dealt separately with
1016 subscript - low >= 0 and high - subscript >= 0 in case one of
1017 the two bounds isn't known. Do the same here? */
1019 if (tree_fits_shwi_p (low
)
1021 && tree_fits_shwi_p (high
)
1022 /* 1-element arrays at end of structures may extend over
1023 their declared size. */
1024 && !(array_at_struct_end_p (ref
)
1025 && operand_equal_p (low
, high
, 0)))
1029 isl_set
*univ
, *lbs
, *ubs
;
1032 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1033 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1034 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1037 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1038 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1039 isl_set_dim (valid
, isl_dim_set
));
1040 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
1042 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1043 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1044 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1045 index
= isl_pw_aff_alloc (univ
, aff
);
1047 id
= isl_set_get_tuple_id (subscript_sizes
);
1048 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1049 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1051 /* low <= sub_i <= high */
1052 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1053 ubs
= isl_pw_aff_le_set (index
, ub
);
1054 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1055 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1059 return subscript_sizes
;
1062 /* Build data accesses for DR in PBB. */
1065 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1067 int dr_base_object_set
;
1069 isl_set
*subscript_sizes
;
1070 scop_p scop
= PBB_SCOP (pbb
);
1073 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1074 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1075 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1076 isl_dim_out
, nb_out
);
1078 acc
= isl_map_universe (space
);
1079 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1082 acc
= pdr_add_alias_set (acc
, dr
);
1083 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1086 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1087 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1088 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1089 int alias_set_num
= 0;
1090 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1092 if (bap
&& bap
->alias_set
)
1093 alias_set_num
= *(bap
->alias_set
);
1095 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1096 subscript_sizes
= isl_set_nat_universe (space
);
1097 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1099 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1102 gcc_assert (dr
->aux
);
1103 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1105 new_poly_dr (pbb
, dr_base_object_set
,
1106 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1107 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1110 /* Write to FILE the alias graph of data references in DIMACS format. */
1113 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1114 vec
<data_reference_p
> drs
)
1116 int num_vertex
= drs
.length ();
1118 data_reference_p dr1
, dr2
;
1121 if (num_vertex
== 0)
1124 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1125 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1126 if (dr_may_alias_p (dr1
, dr2
, true))
1129 fprintf (file
, "$\n");
1132 fprintf (file
, "c %s\n", comment
);
1134 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1136 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1137 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1138 if (dr_may_alias_p (dr1
, dr2
, true))
1139 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1144 /* Write to FILE the alias graph of data references in DOT format. */
1147 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1148 vec
<data_reference_p
> drs
)
1150 int num_vertex
= drs
.length ();
1151 data_reference_p dr1
, dr2
;
1154 if (num_vertex
== 0)
1157 fprintf (file
, "$\n");
1160 fprintf (file
, "c %s\n", comment
);
1162 /* First print all the vertices. */
1163 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1164 fprintf (file
, "n%d;\n", i
);
1166 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1167 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1168 if (dr_may_alias_p (dr1
, dr2
, true))
1169 fprintf (file
, "n%d n%d\n", i
, j
);
1174 /* Write to FILE the alias graph of data references in ECC format. */
1177 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1178 vec
<data_reference_p
> drs
)
1180 int num_vertex
= drs
.length ();
1181 data_reference_p dr1
, dr2
;
1184 if (num_vertex
== 0)
1187 fprintf (file
, "$\n");
1190 fprintf (file
, "c %s\n", comment
);
1192 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1193 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1194 if (dr_may_alias_p (dr1
, dr2
, true))
1195 fprintf (file
, "%d %d\n", i
, j
);
1200 /* Check if DR1 and DR2 are in the same object set. */
1203 dr_same_base_object_p (const struct data_reference
*dr1
,
1204 const struct data_reference
*dr2
)
1206 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1209 /* Uses DFS component number as representative of alias-sets. Also tests for
1210 optimality by verifying if every connected component is a clique. Returns
1211 true (1) if the above test is true, and false (0) otherwise. */
1214 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1216 int num_vertices
= drs
.length ();
1217 struct graph
*g
= new_graph (num_vertices
);
1218 data_reference_p dr1
, dr2
;
1220 int num_connected_components
;
1221 int v_indx1
, v_indx2
, num_vertices_in_component
;
1224 struct graph_edge
*e
;
1225 int this_component_is_clique
;
1226 int all_components_are_cliques
= 1;
1228 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1229 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1230 if (dr_may_alias_p (dr1
, dr2
, true))
1236 all_vertices
= XNEWVEC (int, num_vertices
);
1237 vertices
= XNEWVEC (int, num_vertices
);
1238 for (i
= 0; i
< num_vertices
; i
++)
1239 all_vertices
[i
] = i
;
1241 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1243 for (i
= 0; i
< g
->n_vertices
; i
++)
1245 data_reference_p dr
= drs
[i
];
1246 base_alias_pair
*bap
;
1248 gcc_assert (dr
->aux
);
1249 bap
= (base_alias_pair
*)(dr
->aux
);
1251 bap
->alias_set
= XNEW (int);
1252 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1255 /* Verify if the DFS numbering results in optimal solution. */
1256 for (i
= 0; i
< num_connected_components
; i
++)
1258 num_vertices_in_component
= 0;
1259 /* Get all vertices whose DFS component number is the same as i. */
1260 for (j
= 0; j
< num_vertices
; j
++)
1261 if (g
->vertices
[j
].component
== i
)
1262 vertices
[num_vertices_in_component
++] = j
;
1264 /* Now test if the vertices in 'vertices' form a clique, by testing
1265 for edges among each pair. */
1266 this_component_is_clique
= 1;
1267 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1269 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1271 /* Check if the two vertices are connected by iterating
1272 through all the edges which have one of these are source. */
1273 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1276 if (e
->src
== vertices
[v_indx1
])
1282 this_component_is_clique
= 0;
1286 if (!this_component_is_clique
)
1287 all_components_are_cliques
= 0;
1291 free (all_vertices
);
1294 return all_components_are_cliques
;
1297 /* Group each data reference in DRS with its base object set num. */
1300 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1302 int num_vertex
= drs
.length ();
1303 struct graph
*g
= new_graph (num_vertex
);
1304 data_reference_p dr1
, dr2
;
1308 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1309 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1310 if (dr_same_base_object_p (dr1
, dr2
))
1316 queue
= XNEWVEC (int, num_vertex
);
1317 for (i
= 0; i
< num_vertex
; i
++)
1320 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1322 for (i
= 0; i
< g
->n_vertices
; i
++)
1324 data_reference_p dr
= drs
[i
];
1325 base_alias_pair
*bap
;
1327 gcc_assert (dr
->aux
);
1328 bap
= (base_alias_pair
*)(dr
->aux
);
1330 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1337 /* Build the data references for PBB. */
1340 build_pbb_drs (poly_bb_p pbb
)
1343 data_reference_p dr
;
1344 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1346 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1347 build_poly_dr (dr
, pbb
);
1350 /* Dump to file the alias graphs for the data references in DRS. */
1353 dump_alias_graphs (vec
<data_reference_p
> drs
)
1356 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1358 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1361 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1362 current_function_name ());
1363 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1364 fclose (file_dimacs
);
1367 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1370 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1371 current_function_name ());
1372 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1376 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1379 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1380 current_function_name ());
1381 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1386 /* Build data references in SCOP. */
1389 build_scop_drs (scop_p scop
)
1394 /* Remove all the PBBs that do not have data references: these basic
1395 blocks are not handled in the polyhedral representation. */
1396 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1397 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1399 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
1401 SCOP_BBS (scop
).ordered_remove (i
);
1405 data_reference_p dr
;
1406 auto_vec
<data_reference_p
, 3> drs
;
1407 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1408 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1411 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1412 dr
->aux
= XNEW (base_alias_pair
);
1414 if (!build_alias_set_optimal_p (drs
))
1416 /* TODO: Add support when building alias set is not optimal. */
1420 build_base_obj_set_for_drs (drs
);
1422 /* When debugging, enable the following code. This cannot be used
1423 in production compilers. */
1425 dump_alias_graphs (drs
);
1429 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1430 build_pbb_drs (pbb
);
1433 /* Analyze all the data references of STMTS and add them to the
1434 GBB_DATA_REFS vector of BB. */
1437 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1439 sese region
= SCOP_REGION (scop
);
1440 if (!bb_in_sese_p (bb
, region
))
1443 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1444 loop_p loop
= bb
->loop_father
;
1445 if (!loop_in_sese_p (loop
, region
))
1448 gimple_poly_bb_p gbb
= gbb_from_bb (bb
);
1452 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1454 if (is_gimple_debug (stmt
))
1457 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1458 &GBB_DATA_REFS (gbb
));
1462 /* Insert STMT at the end of the STMTS sequence and then insert the
1463 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1467 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1468 gimple_stmt_iterator insert_gsi
)
1470 gimple_stmt_iterator gsi
;
1471 auto_vec
<gimple
*, 3> x
;
1473 gimple_seq_add_stmt (&stmts
, stmt
);
1474 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1475 x
.safe_push (gsi_stmt (gsi
));
1477 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1478 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1481 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1484 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1486 gimple_stmt_iterator gsi
;
1487 auto_vec
<gimple
*, 3> x
;
1489 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1490 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1492 gimple_seq_add_stmt (&stmts
, stmt
);
1494 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1495 x
.safe_push (gsi_stmt (gsi
));
1497 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
1499 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
1500 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1504 gsi
= gsi_for_stmt (after_stmt
);
1505 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1508 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
1511 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
1514 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
1516 vec
<data_reference_p
> drs
;
1518 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1519 gimple_poly_bb_p gbb1
= new_gimple_poly_bb (bb
, drs
);
1520 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
1521 int index
, n
= SCOP_BBS (scop
).length ();
1523 /* The INDEX of PBB in SCOP_BBS. */
1524 for (index
= 0; index
< n
; index
++)
1525 if (SCOP_BBS (scop
)[index
] == pbb
)
1528 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1529 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1530 isl_id_for_pbb (scop
, pbb1
));
1532 GBB_PBB (gbb1
) = pbb1
;
1533 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1534 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1535 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
1538 /* Insert on edge E the assignment "RES := EXPR". */
1541 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
1543 gimple_seq stmts
= NULL
;
1544 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1545 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1546 auto_vec
<gimple
*, 3> x
;
1548 gimple_seq_add_stmt (&stmts
, stmt
);
1549 gimple_stmt_iterator gsi
;
1550 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1551 x
.safe_push (gsi_stmt (gsi
));
1553 gsi_insert_seq_on_edge (e
, stmts
);
1554 gsi_commit_edge_inserts ();
1555 basic_block bb
= gimple_bb (stmt
);
1557 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1560 if (!gbb_from_bb (bb
))
1561 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
1563 analyze_drs_in_stmts (scop
, bb
, x
);
1566 /* Creates a zero dimension array of the same type as VAR. */
1569 create_zero_dim_array (tree var
, const char *base_name
)
1571 tree index_type
= build_index_type (integer_zero_node
);
1572 tree elt_type
= TREE_TYPE (var
);
1573 tree array_type
= build_array_type (elt_type
, index_type
);
1574 tree base
= create_tmp_var (array_type
, base_name
);
1576 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1580 /* Returns true when PHI is a loop close phi node. */
1583 scalar_close_phi_node_p (gimple
*phi
)
1585 if (gimple_code (phi
) != GIMPLE_PHI
1586 || virtual_operand_p (gimple_phi_result (phi
)))
1589 /* Note that loop close phi nodes should have a single argument
1590 because we translated the representation into a canonical form
1591 before Graphite: see canonicalize_loop_closed_ssa_form. */
1592 return (gimple_phi_num_args (phi
) == 1);
1595 /* For a definition DEF in REGION, propagates the expression EXPR in
1596 all the uses of DEF outside REGION. */
1599 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
1602 bool replaced_once
= false;
1604 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
1606 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
1609 imm_use_iterator imm_iter
;
1611 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1612 if (!is_gimple_debug (use_stmt
)
1613 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
1616 use_operand_p use_p
;
1618 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1619 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
1620 && (replaced_once
= true))
1621 replace_exp (use_p
, expr
);
1623 update_stmt (use_stmt
);
1628 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
1629 gsi_commit_edge_inserts ();
1633 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1634 dimension array for it. */
1637 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
1639 sese region
= SCOP_REGION (scop
);
1640 gimple
*phi
= gsi_stmt (*psi
);
1641 tree res
= gimple_phi_result (phi
);
1642 basic_block bb
= gimple_bb (phi
);
1643 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1644 tree arg
= gimple_phi_arg_def (phi
, 0);
1647 /* Note that loop close phi nodes should have a single argument
1648 because we translated the representation into a canonical form
1649 before Graphite: see canonicalize_loop_closed_ssa_form. */
1650 gcc_assert (gimple_phi_num_args (phi
) == 1);
1652 /* The phi node can be a non close phi node, when its argument is
1653 invariant, or a default definition. */
1654 if (is_gimple_min_invariant (arg
)
1655 || SSA_NAME_IS_DEFAULT_DEF (arg
))
1657 propagate_expr_outside_region (res
, arg
, region
);
1662 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
1664 propagate_expr_outside_region (res
, arg
, region
);
1665 stmt
= gimple_build_assign (res
, arg
);
1666 remove_phi_node (psi
, false);
1667 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1671 /* If res is scev analyzable and is not a scalar value, it is safe
1672 to ignore the close phi node: it will be code generated in the
1673 out of Graphite pass. */
1674 else if (scev_analyzable_p (res
, region
))
1676 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
1679 if (!loop_in_sese_p (loop
, region
))
1681 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
1682 scev
= scalar_evolution_in_region (region
, loop
, arg
);
1683 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
1686 scev
= scalar_evolution_in_region (region
, loop
, res
);
1688 if (tree_does_not_contain_chrecs (scev
))
1689 propagate_expr_outside_region (res
, scev
, region
);
1696 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
1698 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1700 if (TREE_CODE (arg
) == SSA_NAME
)
1701 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1702 SSA_NAME_DEF_STMT (arg
));
1704 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
1705 zero_dim_array
, arg
);
1708 remove_phi_node (psi
, false);
1709 SSA_NAME_DEF_STMT (res
) = stmt
;
1711 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1714 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1715 dimension array for it. */
1718 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
1720 gphi
*phi
= psi
->phi ();
1721 basic_block bb
= gimple_bb (phi
);
1722 tree res
= gimple_phi_result (phi
);
1723 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
1725 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1727 tree arg
= gimple_phi_arg_def (phi
, i
);
1728 edge e
= gimple_phi_arg_edge (phi
, i
);
1730 /* Avoid the insertion of code in the loop latch to please the
1731 pattern matching of the vectorizer. */
1732 if (TREE_CODE (arg
) == SSA_NAME
1733 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
1734 && e
->src
== bb
->loop_father
->latch
)
1735 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1736 SSA_NAME_DEF_STMT (arg
));
1738 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
1741 gimple
*stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1742 remove_phi_node (psi
, false);
1743 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1746 /* Rewrite the degenerate phi node at position PSI from the degenerate
1747 form "x = phi (y, y, ..., y)" to "x = y". */
1750 rewrite_degenerate_phi (gphi_iterator
*psi
)
1752 gphi
*phi
= psi
->phi ();
1753 tree res
= gimple_phi_result (phi
);
1755 basic_block bb
= gimple_bb (phi
);
1756 tree rhs
= degenerate_phi_result (phi
);
1759 gimple
*stmt
= gimple_build_assign (res
, rhs
);
1760 remove_phi_node (psi
, false);
1762 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1763 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1766 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1769 rewrite_reductions_out_of_ssa (scop_p scop
)
1772 sese region
= SCOP_REGION (scop
);
1774 FOR_EACH_BB_FN (bb
, cfun
)
1775 if (bb_in_sese_p (bb
, region
))
1776 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
1778 gphi
*phi
= psi
.phi ();
1780 if (virtual_operand_p (gimple_phi_result (phi
)))
1786 if (gimple_phi_num_args (phi
) > 1
1787 && degenerate_phi_result (phi
))
1788 rewrite_degenerate_phi (&psi
);
1790 else if (scalar_close_phi_node_p (phi
))
1791 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1793 else if (reduction_phi_p (region
, &psi
))
1794 rewrite_phi_out_of_ssa (scop
, &psi
);
1797 update_ssa (TODO_update_ssa
);
1798 #ifdef ENABLE_CHECKING
1799 verify_loop_closed_ssa (true);
1803 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
1804 read from ZERO_DIM_ARRAY. */
1807 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
1808 tree def
, gimple
*use_stmt
)
1810 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1812 tree name
= copy_ssa_name (def
);
1813 gimple
*name_stmt
= gimple_build_assign (name
, zero_dim_array
);
1815 gimple_assign_set_lhs (name_stmt
, name
);
1816 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
1819 use_operand_p use_p
;
1820 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1821 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
1822 replace_exp (use_p
, name
);
1824 update_stmt (use_stmt
);
1827 /* For every definition DEF in the SCOP that is used outside the scop,
1828 insert a closing-scop definition in the basic block just after this
1832 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
1834 tree var
= create_tmp_reg (TREE_TYPE (def
));
1835 tree new_name
= make_ssa_name (var
, stmt
);
1836 bool needs_copy
= false;
1837 sese region
= SCOP_REGION (scop
);
1839 imm_use_iterator imm_iter
;
1841 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1843 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
1845 use_operand_p use_p
;
1846 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1848 SET_USE (use_p
, new_name
);
1850 update_stmt (use_stmt
);
1855 /* Insert in the empty BB just after the scop a use of DEF such
1856 that the rewrite of cross_bb_scalar_dependences won't insert
1857 arrays everywhere else. */
1860 gimple
*assign
= gimple_build_assign (new_name
, def
);
1861 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
1863 update_stmt (assign
);
1864 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
1868 /* Rewrite the scalar dependences crossing the boundary of the BB
1869 containing STMT with an array. Return true when something has been
1873 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
1875 sese region
= SCOP_REGION (scop
);
1876 gimple
*stmt
= gsi_stmt (*gsi
);
1877 imm_use_iterator imm_iter
;
1879 tree zero_dim_array
= NULL_TREE
;
1883 switch (gimple_code (stmt
))
1886 def
= gimple_assign_lhs (stmt
);
1890 def
= gimple_call_lhs (stmt
);
1898 || !is_gimple_reg (def
))
1901 if (scev_analyzable_p (def
, region
))
1903 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
1904 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
1906 if (tree_contains_chrecs (scev
, NULL
))
1909 propagate_expr_outside_region (def
, scev
, region
);
1913 basic_block def_bb
= gimple_bb (stmt
);
1915 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
1917 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1918 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
1921 gphi_iterator psi
= gsi_for_phi (phi
);
1923 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
1924 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1926 rewrite_phi_out_of_ssa (scop
, &psi
);
1929 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1930 if (gimple_code (use_stmt
) != GIMPLE_PHI
1931 && def_bb
!= gimple_bb (use_stmt
)
1932 && !is_gimple_debug (use_stmt
)
1935 if (!zero_dim_array
)
1937 zero_dim_array
= create_zero_dim_array
1938 (def
, "Cross_BB_scalar_dependence");
1939 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
1940 SSA_NAME_DEF_STMT (def
));
1944 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
1948 update_ssa (TODO_update_ssa
);
1953 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1956 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
1959 gimple_stmt_iterator psi
;
1960 sese region
= SCOP_REGION (scop
);
1961 bool changed
= false;
1963 /* Create an extra empty BB after the scop. */
1964 split_edge (SESE_EXIT (region
));
1966 FOR_EACH_BB_FN (bb
, cfun
)
1967 if (bb_in_sese_p (bb
, region
))
1968 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1969 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
1974 update_ssa (TODO_update_ssa
);
1975 #ifdef ENABLE_CHECKING
1976 verify_loop_closed_ssa (true);
1981 /* Builds the polyhedral representation for a SESE region. */
1984 build_poly_scop (scop_p scop
)
1986 set_scop_parameter_dim (scop
);
1987 build_scop_iteration_domain (scop
);
1988 build_scop_context (scop
);
1989 add_conditions_to_constraints (scop
);
1991 /* Rewrite out of SSA only after having translated the
1992 representation to the polyhedral representation to avoid scev
1993 analysis failures. That means that these functions will insert
1994 new data references that they create in the right place. */
1995 rewrite_reductions_out_of_ssa (scop
);
1996 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
1998 build_scop_drs (scop
);
1999 build_scop_scattering (scop
);
2001 /* This SCoP has been translated to the polyhedral
2003 POLY_SCOP_P (scop
) = true;
2005 #endif /* HAVE_isl */