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_l
®ion
, 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_l
®ion
, 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
->pbbs
, i
, pbb
)
334 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
338 prefix
= nb_common_loops (scop
->region
->region
, 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 (s
->region
->region
, 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_info_p 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
->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_info_p region
= scop
->region
;
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_l region
= scop
->region
->region
;
598 gcc_assert (loop_in_sese_p (loop
, region
));
600 isl_set
*inner
= isl_set_copy (outer
);
601 int pos
= isl_set_dim (outer
, isl_dim_set
);
607 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
608 isl_space
*space
= isl_set_get_space (inner
);
611 isl_constraint
*c
= isl_inequality_alloc
612 (isl_local_space_from_space (isl_space_copy (space
)));
613 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
614 inner
= isl_set_add_constraint (inner
, c
);
616 /* loop_i <= cst_nb_iters */
617 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
619 c
= isl_inequality_alloc
620 (isl_local_space_from_space (isl_space_copy (space
)));
621 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
622 tree_int_to_gmp (nb_iters
, g
);
623 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
624 c
= isl_constraint_set_constant_val (c
, v
);
625 inner
= isl_set_add_constraint (inner
, c
);
628 /* loop_i <= expr_nb_iters */
629 else if (!chrec_contains_undetermined (nb_iters
))
633 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
635 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
636 isl_set
*valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
637 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
638 isl_set_dim (valid
, isl_dim_set
));
639 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
641 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
642 isl_aff
*al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
644 isl_set
*le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
645 isl_pw_aff_copy (aff
));
646 inner
= isl_set_intersect (inner
, le
);
649 if (max_stmt_executions (loop
, &nit
))
651 /* Insert in the context the constraints from the
652 estimation of the number of iterations NIT and the
653 symbolic number of iterations (involving parameter
654 names) NB_ITERS. First, build the affine expression
655 "NIT - NB_ITERS" and then say that it is positive,
656 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
659 wi::to_mpz (nit
, g
, SIGNED
);
660 mpz_sub_ui (g
, g
, 1);
663 = extract_affine_gmp (g
, isl_set_get_space (inner
));
664 isl_set
*x
= isl_pw_aff_ge_set (approx
, aff
);
665 x
= isl_set_project_out (x
, isl_dim_set
, 0,
666 isl_set_dim (x
, isl_dim_set
));
667 scop
->param_context
= isl_set_intersect (scop
->param_context
, x
);
669 isl_constraint
*c
= isl_inequality_alloc
670 (isl_local_space_from_space (isl_space_copy (space
)));
671 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
672 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
674 c
= isl_constraint_set_constant_val (c
, v
);
675 inner
= isl_set_add_constraint (inner
, c
);
678 isl_pw_aff_free (aff
);
684 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
685 isl_set_copy (inner
), doms
);
689 && loop_in_sese_p (loop
->next
, region
))
690 build_loop_iteration_domains (scop
, loop
->next
, nb
,
691 isl_set_copy (outer
), doms
);
693 doms
[loop
->num
] = inner
;
695 isl_set_free (outer
);
696 isl_space_free (space
);
700 /* Returns a linear expression for tree T evaluated in PBB. */
703 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
705 scop_p scop
= PBB_SCOP (pbb
);
707 t
= scalar_evolution_in_region (scop
->region
->region
, pbb_loop (pbb
), t
);
708 gcc_assert (!automatically_generated_chrec_p (t
));
710 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
713 /* Add conditional statement STMT to pbb. CODE is used as the comparison
714 operator. This allows us to invert the condition or to handle
718 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
720 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
721 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
727 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
731 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
735 cond
= isl_pw_aff_le_set (lhs
, rhs
);
739 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
743 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
747 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
751 isl_pw_aff_free (lhs
);
752 isl_pw_aff_free (rhs
);
756 cond
= isl_set_coalesce (cond
);
757 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
758 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
761 /* Add conditions to the domain of PBB. */
764 add_conditions_to_domain (poly_bb_p pbb
)
768 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
770 if (GBB_CONDITIONS (gbb
).is_empty ())
773 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
774 switch (gimple_code (stmt
))
778 /* Don't constrain on anything else than INTEGER_TYPE. */
779 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
782 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
783 enum tree_code code
= gimple_cond_code (cond_stmt
);
785 /* The conditions for ELSE-branches are inverted. */
786 if (!GBB_CONDITION_CASES (gbb
)[i
])
787 code
= invert_tree_comparison (code
, false);
789 add_condition_to_pbb (pbb
, cond_stmt
, code
);
794 /* Switch statements are not supported right now - fall through. */
802 /* Traverses all the GBBs of the SCOP and add their constraints to the
803 iteration domains. */
806 add_conditions_to_constraints (scop_p scop
)
811 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
812 add_conditions_to_domain (pbb
);
815 /* Add constraints on the possible values of parameter P from the type
819 add_param_constraints (scop_p scop
, graphite_dim_t p
)
821 tree parameter
= SESE_PARAMS (scop
->region
)[p
];
822 tree type
= TREE_TYPE (parameter
);
826 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
827 lb
= lower_bound_in_type (type
, type
);
829 lb
= TYPE_MIN_VALUE (type
);
831 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
832 ub
= upper_bound_in_type (type
, type
);
834 ub
= TYPE_MAX_VALUE (type
);
838 isl_space
*space
= isl_set_get_space (scop
->param_context
);
843 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
845 tree_int_to_gmp (lb
, g
);
846 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
849 c
= isl_constraint_set_constant_val (c
, v
);
850 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
852 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
857 isl_space
*space
= isl_set_get_space (scop
->param_context
);
862 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
865 tree_int_to_gmp (ub
, g
);
866 v
= isl_val_int_from_gmp (scop
->isl_context
, g
);
868 c
= isl_constraint_set_constant_val (c
, v
);
869 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
871 scop
->param_context
= isl_set_add_constraint (scop
->param_context
, c
);
875 /* Build the context of the SCOP. The context usually contains extra
876 constraints that are added to the iteration domains that constrain
880 build_scop_context (scop_p scop
)
882 graphite_dim_t p
, n
= scop_nb_params (scop
);
884 for (p
= 0; p
< n
; p
++)
885 add_param_constraints (scop
, p
);
888 /* Build the iteration domains: the loops belonging to the current
889 SCOP, and that vary for the execution of the current basic block.
890 Returns false if there is no loop in SCOP. */
893 build_scop_iteration_domain (scop_p scop
)
895 sese_info_p region
= scop
->region
;
896 int nb_loops
= number_of_loops (cfun
);
897 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
901 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
902 if (!loop_in_sese_p (loop_outer (loop
), region
->region
))
903 build_loop_iteration_domains (scop
, loop
, 0,
904 isl_set_copy (scop
->param_context
), doms
);
907 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
909 loop
= pbb_loop (pbb
);
912 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
914 pbb
->domain
= isl_set_copy (scop
->param_context
);
916 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
917 isl_id_for_pbb (scop
, pbb
));
920 for (int i
= 0; i
< nb_loops
; i
++)
922 isl_set_free (doms
[i
]);
927 /* Add a constrain to the ACCESSES polyhedron for the alias set of
928 data reference DR. ACCESSP_NB_DIMS is the dimension of the
929 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
933 pdr_add_alias_set (isl_map
*acc
, dr_info
&dri
)
935 isl_constraint
*c
= isl_equality_alloc
936 (isl_local_space_from_space (isl_map_get_space (acc
)));
937 c
= isl_constraint_set_constant_si (c
, -dri
.alias_set
);
938 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
940 return isl_map_add_constraint (acc
, c
);
943 /* Assign the affine expression INDEX to the output dimension POS of
944 MAP and return the result. */
947 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
950 int len
= isl_map_dim (map
, isl_dim_out
);
953 index_map
= isl_map_from_pw_aff (index
);
954 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
955 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
957 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
958 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
959 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
960 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
962 return isl_map_intersect (map
, index_map
);
965 /* Add to ACCESSES polyhedron equalities defining the access functions
966 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
967 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
968 PBB is the poly_bb_p that contains the data reference DR. */
971 pdr_add_memory_accesses (isl_map
*acc
, dr_info
&dri
)
973 data_reference_p dr
= dri
.dr
;
974 poly_bb_p pbb
= dri
.pbb
;
975 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
976 scop_p scop
= PBB_SCOP (pbb
);
978 for (i
= 0; i
< nb_subscripts
; i
++)
981 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
983 aff
= extract_affine (scop
, afn
,
984 isl_space_domain (isl_map_get_space (acc
)));
985 acc
= set_index (acc
, i
+ 1, aff
);
991 /* Add constrains representing the size of the accessed data to the
992 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
993 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
997 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1000 tree ref
= DR_REF (dr
);
1002 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1003 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1005 if (TREE_CODE (ref
) != ARRAY_REF
)
1006 return subscript_sizes
;
1008 tree low
= array_ref_low_bound (ref
);
1009 tree high
= array_ref_up_bound (ref
);
1011 /* XXX The PPL code dealt separately with
1012 subscript - low >= 0 and high - subscript >= 0 in case one of
1013 the two bounds isn't known. Do the same here? */
1015 if (tree_fits_shwi_p (low
)
1017 && tree_fits_shwi_p (high
)
1018 /* 1-element arrays at end of structures may extend over
1019 their declared size. */
1020 && !(array_at_struct_end_p (ref
)
1021 && operand_equal_p (low
, high
, 0)))
1025 isl_set
*univ
, *lbs
, *ubs
;
1028 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1029 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1030 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1033 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1034 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1035 isl_set_dim (valid
, isl_dim_set
));
1036 scop
->param_context
= isl_set_intersect (scop
->param_context
, valid
);
1038 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1039 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1040 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1041 index
= isl_pw_aff_alloc (univ
, aff
);
1043 id
= isl_set_get_tuple_id (subscript_sizes
);
1044 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1045 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1047 /* low <= sub_i <= high */
1048 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1049 ubs
= isl_pw_aff_le_set (index
, ub
);
1050 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1051 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1055 return subscript_sizes
;
1058 /* Build data accesses for DR in PBB. */
1061 build_poly_dr (dr_info
&dri
)
1064 isl_set
*subscript_sizes
;
1065 poly_bb_p pbb
= dri
.pbb
;
1066 data_reference_p dr
= dri
.dr
;
1067 scop_p scop
= PBB_SCOP (pbb
);
1070 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1071 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1072 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1073 isl_dim_out
, nb_out
);
1075 acc
= isl_map_universe (space
);
1076 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1079 acc
= pdr_add_alias_set (acc
, dri
);
1080 acc
= pdr_add_memory_accesses (acc
, dri
);
1083 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1084 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1085 isl_space
*space
= isl_space_set_alloc (scop
->isl_context
, 0, nb
);
1087 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1088 subscript_sizes
= isl_set_nat_universe (space
);
1089 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1091 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1095 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1096 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1099 /* Compute alias-sets for all data references in DRS. */
1102 build_alias_set (scop_p scop
)
1104 int num_vertices
= scop
->drs
.length ();
1105 struct graph
*g
= new_graph (num_vertices
);
1106 dr_info
dr1 (0), dr2 (0);
1110 FOR_EACH_VEC_ELT (scop
->drs
, i
, dr1
)
1111 for (j
= i
+1; scop
->drs
.iterate (j
, &dr2
); j
++)
1112 if (dr_may_alias_p (dr1
.dr
, dr2
.dr
, true))
1118 all_vertices
= XNEWVEC (int, num_vertices
);
1119 for (i
= 0; i
< num_vertices
; i
++)
1120 all_vertices
[i
] = i
;
1122 graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1123 free (all_vertices
);
1125 for (i
= 0; i
< g
->n_vertices
; i
++)
1126 scop
->drs
[i
].alias_set
= g
->vertices
[i
].component
+ 1;
1131 /* Build data references in SCOP. */
1134 build_scop_drs (scop_p scop
)
1139 /* Remove all the PBBs that do not have data references: these basic
1140 blocks are not handled in the polyhedral representation. */
1141 for (i
= 0; scop
->pbbs
.iterate (i
, &pbb
); i
++)
1142 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1144 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
1146 scop
->pbbs
.ordered_remove (i
);
1150 data_reference_p dr
;
1151 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
1153 FOR_EACH_VEC_ELT (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
)
1154 scop
->drs
.safe_push (dr_info (dr
, -1, pbb
));
1156 build_alias_set (scop
);
1159 FOR_EACH_VEC_ELT (scop
->drs
, i
, dri
)
1160 build_poly_dr (dri
);
1163 /* Analyze all the data references of STMTS and add them to the
1164 GBB_DATA_REFS vector of BB. */
1167 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1169 sese_l region
= scop
->region
->region
;
1170 if (!bb_in_sese_p (bb
, region
))
1173 loop_p nest
= outermost_loop_in_sese (region
, bb
);
1174 loop_p loop
= bb
->loop_father
;
1175 if (!loop_in_sese_p (loop
, region
))
1178 gimple_poly_bb_p gbb
= gbb_from_bb (bb
);
1182 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1184 if (is_gimple_debug (stmt
))
1187 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1188 &GBB_DATA_REFS (gbb
));
1192 /* Insert STMT at the end of the STMTS sequence and then insert the
1193 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1197 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1198 gimple_stmt_iterator insert_gsi
)
1200 gimple_stmt_iterator gsi
;
1201 auto_vec
<gimple
*, 3> x
;
1203 gimple_seq_add_stmt (&stmts
, stmt
);
1204 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1205 x
.safe_push (gsi_stmt (gsi
));
1207 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1208 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1211 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1214 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1216 gimple_stmt_iterator gsi
;
1217 auto_vec
<gimple
*, 3> x
;
1219 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1220 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1222 gimple_seq_add_stmt (&stmts
, stmt
);
1224 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1225 x
.safe_push (gsi_stmt (gsi
));
1227 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
1229 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
1230 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1234 gsi
= gsi_for_stmt (after_stmt
);
1235 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1238 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
1241 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
1244 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
1246 vec
<data_reference_p
> drs
;
1248 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1249 gimple_poly_bb_p gbb1
= new_gimple_poly_bb (bb
, drs
);
1250 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
1251 int index
, n
= scop
->pbbs
.length ();
1253 for (index
= 0; index
< n
; index
++)
1254 if (scop
->pbbs
[index
] == pbb
)
1257 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1258 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1259 isl_id_for_pbb (scop
, pbb1
));
1261 GBB_PBB (gbb1
) = pbb1
;
1262 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1263 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1264 scop
->pbbs
.safe_insert (index
+ 1, pbb1
);
1267 /* Insert on edge E the assignment "RES := EXPR". */
1270 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
1272 gimple_seq stmts
= NULL
;
1273 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1274 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1275 auto_vec
<gimple
*, 3> x
;
1277 gimple_seq_add_stmt (&stmts
, stmt
);
1278 gimple_stmt_iterator gsi
;
1279 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1280 x
.safe_push (gsi_stmt (gsi
));
1282 gsi_insert_seq_on_edge (e
, stmts
);
1283 gsi_commit_edge_inserts ();
1284 basic_block bb
= gimple_bb (stmt
);
1286 if (!bb_in_sese_p (bb
, scop
->region
->region
))
1289 if (!gbb_from_bb (bb
))
1290 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
1292 analyze_drs_in_stmts (scop
, bb
, x
);
1295 /* Creates a zero dimension array of the same type as VAR. */
1298 create_zero_dim_array (tree var
, const char *base_name
)
1300 tree index_type
= build_index_type (integer_zero_node
);
1301 tree elt_type
= TREE_TYPE (var
);
1302 tree array_type
= build_array_type (elt_type
, index_type
);
1303 tree base
= create_tmp_var (array_type
, base_name
);
1305 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1309 /* Returns true when PHI is a loop close phi node. */
1312 scalar_close_phi_node_p (gimple
*phi
)
1314 if (gimple_code (phi
) != GIMPLE_PHI
1315 || virtual_operand_p (gimple_phi_result (phi
)))
1318 /* Note that loop close phi nodes should have a single argument
1319 because we translated the representation into a canonical form
1320 before Graphite: see canonicalize_loop_closed_ssa_form. */
1321 return (gimple_phi_num_args (phi
) == 1);
1324 /* For a definition DEF in REGION, propagates the expression EXPR in
1325 all the uses of DEF outside REGION. */
1328 propagate_expr_outside_region (tree def
, tree expr
, sese_l
®ion
)
1331 bool replaced_once
= false;
1333 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
1335 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
1338 imm_use_iterator imm_iter
;
1340 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1341 if (!is_gimple_debug (use_stmt
)
1342 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
1345 use_operand_p use_p
;
1347 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1348 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
1349 && (replaced_once
= true))
1350 replace_exp (use_p
, expr
);
1352 update_stmt (use_stmt
);
1357 gsi_insert_seq_on_edge (region
.entry
, stmts
);
1358 gsi_commit_edge_inserts ();
1362 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1363 dimension array for it. */
1366 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
1368 sese_l region
= scop
->region
->region
;
1369 gimple
*phi
= gsi_stmt (*psi
);
1370 tree res
= gimple_phi_result (phi
);
1371 basic_block bb
= gimple_bb (phi
);
1372 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1373 tree arg
= gimple_phi_arg_def (phi
, 0);
1376 /* Note that loop close phi nodes should have a single argument
1377 because we translated the representation into a canonical form
1378 before Graphite: see canonicalize_loop_closed_ssa_form. */
1379 gcc_assert (gimple_phi_num_args (phi
) == 1);
1381 /* The phi node can be a non close phi node, when its argument is
1382 invariant, or a default definition. */
1383 if (is_gimple_min_invariant (arg
)
1384 || SSA_NAME_IS_DEFAULT_DEF (arg
))
1386 propagate_expr_outside_region (res
, arg
, region
);
1391 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
1393 propagate_expr_outside_region (res
, arg
, region
);
1394 stmt
= gimple_build_assign (res
, arg
);
1395 remove_phi_node (psi
, false);
1396 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1400 /* If res is scev analyzable and is not a scalar value, it is safe
1401 to ignore the close phi node: it will be code generated in the
1402 out of Graphite pass. */
1403 else if (scev_analyzable_p (res
, region
))
1405 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
1408 if (!loop_in_sese_p (loop
, region
))
1410 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
1411 scev
= scalar_evolution_in_region (region
, loop
, arg
);
1412 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
1415 scev
= scalar_evolution_in_region (region
, loop
, res
);
1417 if (tree_does_not_contain_chrecs (scev
))
1418 propagate_expr_outside_region (res
, scev
, region
);
1425 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
1427 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1429 if (TREE_CODE (arg
) == SSA_NAME
)
1430 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1431 SSA_NAME_DEF_STMT (arg
));
1433 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
1434 zero_dim_array
, arg
);
1437 remove_phi_node (psi
, false);
1438 SSA_NAME_DEF_STMT (res
) = stmt
;
1440 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1443 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1444 dimension array for it. */
1447 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
1449 gphi
*phi
= psi
->phi ();
1450 basic_block bb
= gimple_bb (phi
);
1451 tree res
= gimple_phi_result (phi
);
1452 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
1454 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1456 tree arg
= gimple_phi_arg_def (phi
, i
);
1457 edge e
= gimple_phi_arg_edge (phi
, i
);
1459 /* Avoid the insertion of code in the loop latch to please the
1460 pattern matching of the vectorizer. */
1461 if (TREE_CODE (arg
) == SSA_NAME
1462 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
1463 && e
->src
== bb
->loop_father
->latch
)
1464 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1465 SSA_NAME_DEF_STMT (arg
));
1467 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
1470 gimple
*stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1471 remove_phi_node (psi
, false);
1472 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1475 /* Rewrite the degenerate phi node at position PSI from the degenerate
1476 form "x = phi (y, y, ..., y)" to "x = y". */
1479 rewrite_degenerate_phi (gphi_iterator
*psi
)
1481 gphi
*phi
= psi
->phi ();
1482 tree res
= gimple_phi_result (phi
);
1484 basic_block bb
= gimple_bb (phi
);
1485 tree rhs
= degenerate_phi_result (phi
);
1488 gimple
*stmt
= gimple_build_assign (res
, rhs
);
1489 remove_phi_node (psi
, false);
1491 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1492 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1495 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1498 rewrite_reductions_out_of_ssa (scop_p scop
)
1501 sese_l region
= scop
->region
->region
;
1503 FOR_EACH_BB_FN (bb
, cfun
)
1504 if (bb_in_sese_p (bb
, region
))
1505 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
1507 gphi
*phi
= psi
.phi ();
1509 if (virtual_operand_p (gimple_phi_result (phi
)))
1515 if (gimple_phi_num_args (phi
) > 1
1516 && degenerate_phi_result (phi
))
1517 rewrite_degenerate_phi (&psi
);
1519 else if (scalar_close_phi_node_p (phi
))
1520 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1522 else if (reduction_phi_p (region
, &psi
))
1523 rewrite_phi_out_of_ssa (scop
, &psi
);
1526 update_ssa (TODO_update_ssa
);
1527 #ifdef ENABLE_CHECKING
1528 verify_loop_closed_ssa (true);
1532 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
1533 read from ZERO_DIM_ARRAY. */
1536 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
1537 tree def
, gimple
*use_stmt
)
1539 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1541 tree name
= copy_ssa_name (def
);
1542 gimple
*name_stmt
= gimple_build_assign (name
, zero_dim_array
);
1544 gimple_assign_set_lhs (name_stmt
, name
);
1545 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
1548 use_operand_p use_p
;
1549 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1550 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
1551 replace_exp (use_p
, name
);
1553 update_stmt (use_stmt
);
1556 /* For every definition DEF in the SCOP that is used outside the scop,
1557 insert a closing-scop definition in the basic block just after this
1561 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
1563 tree var
= create_tmp_reg (TREE_TYPE (def
));
1564 tree new_name
= make_ssa_name (var
, stmt
);
1565 bool needs_copy
= false;
1566 sese_l region
= scop
->region
->region
;
1568 imm_use_iterator imm_iter
;
1570 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1572 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
1574 use_operand_p use_p
;
1575 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1577 SET_USE (use_p
, new_name
);
1579 update_stmt (use_stmt
);
1584 /* Insert in the empty BB just after the scop a use of DEF such
1585 that the rewrite of cross_bb_scalar_dependences won't insert
1586 arrays everywhere else. */
1589 gimple
*assign
= gimple_build_assign (new_name
, def
);
1590 gimple_stmt_iterator psi
= gsi_after_labels (region
.exit
->dest
);
1592 update_stmt (assign
);
1593 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
1597 /* Rewrite the scalar dependences crossing the boundary of the BB
1598 containing STMT with an array. Return true when something has been
1602 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
1604 sese_l region
= scop
->region
->region
;
1605 gimple
*stmt
= gsi_stmt (*gsi
);
1606 imm_use_iterator imm_iter
;
1608 tree zero_dim_array
= NULL_TREE
;
1612 switch (gimple_code (stmt
))
1615 def
= gimple_assign_lhs (stmt
);
1619 def
= gimple_call_lhs (stmt
);
1627 || !is_gimple_reg (def
))
1630 if (scev_analyzable_p (def
, region
))
1632 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
1633 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
1635 if (tree_contains_chrecs (scev
, NULL
))
1638 propagate_expr_outside_region (def
, scev
, region
);
1642 basic_block def_bb
= gimple_bb (stmt
);
1644 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
1646 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1647 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
1650 gphi_iterator psi
= gsi_for_phi (phi
);
1652 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
1653 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1655 rewrite_phi_out_of_ssa (scop
, &psi
);
1658 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1659 if (gimple_code (use_stmt
) != GIMPLE_PHI
1660 && def_bb
!= gimple_bb (use_stmt
)
1661 && !is_gimple_debug (use_stmt
)
1664 if (!zero_dim_array
)
1666 zero_dim_array
= create_zero_dim_array
1667 (def
, "Cross_BB_scalar_dependence");
1668 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
1669 SSA_NAME_DEF_STMT (def
));
1673 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
1677 update_ssa (TODO_update_ssa
);
1682 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1685 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
1688 gimple_stmt_iterator psi
;
1689 sese_l region
= scop
->region
->region
;
1690 bool changed
= false;
1692 /* Create an extra empty BB after the scop. */
1693 split_edge (region
.exit
);
1695 FOR_EACH_BB_FN (bb
, cfun
)
1696 if (bb_in_sese_p (bb
, region
))
1697 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1698 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
1703 update_ssa (TODO_update_ssa
);
1704 #ifdef ENABLE_CHECKING
1705 verify_loop_closed_ssa (true);
1710 /* Builds the polyhedral representation for a SESE region. */
1713 build_poly_scop (scop_p scop
)
1715 set_scop_parameter_dim (scop
);
1716 build_scop_iteration_domain (scop
);
1717 build_scop_context (scop
);
1718 add_conditions_to_constraints (scop
);
1720 /* Rewrite out of SSA only after having translated the
1721 representation to the polyhedral representation to avoid scev
1722 analysis failures. That means that these functions will insert
1723 new data references that they create in the right place. */
1724 rewrite_reductions_out_of_ssa (scop
);
1725 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
1727 build_scop_drs (scop
);
1728 build_scop_scattering (scop
);
1730 /* This SCoP has been translated to the polyhedral
1732 POLY_SCOP_P (scop
) = true;
1734 #endif /* HAVE_isl */