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
);
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 (scop
), 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_BBS (scop
), 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 (scop
))[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 region
= SCOP_REGION (scop
);
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
))
903 build_loop_iteration_domains (scop
, loop
, 0,
904 isl_set_copy (scop
->param_context
), doms
);
907 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), 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_BBS (scop
).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_BBS (scop
).ordered_remove (i
);
1150 data_reference_p dr
;
1151 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), 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 region
= SCOP_REGION (scop
);
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_BBS (scop
).length ();
1253 /* The INDEX of PBB in SCOP_BBS. */
1254 for (index
= 0; index
< n
; index
++)
1255 if (SCOP_BBS (scop
)[index
] == pbb
)
1258 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1259 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1260 isl_id_for_pbb (scop
, pbb1
));
1262 GBB_PBB (gbb1
) = pbb1
;
1263 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1264 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1265 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
1268 /* Insert on edge E the assignment "RES := EXPR". */
1271 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
1273 gimple_seq stmts
= NULL
;
1274 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1275 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1276 auto_vec
<gimple
*, 3> x
;
1278 gimple_seq_add_stmt (&stmts
, stmt
);
1279 gimple_stmt_iterator gsi
;
1280 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1281 x
.safe_push (gsi_stmt (gsi
));
1283 gsi_insert_seq_on_edge (e
, stmts
);
1284 gsi_commit_edge_inserts ();
1285 basic_block bb
= gimple_bb (stmt
);
1287 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
1290 if (!gbb_from_bb (bb
))
1291 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
1293 analyze_drs_in_stmts (scop
, bb
, x
);
1296 /* Creates a zero dimension array of the same type as VAR. */
1299 create_zero_dim_array (tree var
, const char *base_name
)
1301 tree index_type
= build_index_type (integer_zero_node
);
1302 tree elt_type
= TREE_TYPE (var
);
1303 tree array_type
= build_array_type (elt_type
, index_type
);
1304 tree base
= create_tmp_var (array_type
, base_name
);
1306 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1310 /* Returns true when PHI is a loop close phi node. */
1313 scalar_close_phi_node_p (gimple
*phi
)
1315 if (gimple_code (phi
) != GIMPLE_PHI
1316 || virtual_operand_p (gimple_phi_result (phi
)))
1319 /* Note that loop close phi nodes should have a single argument
1320 because we translated the representation into a canonical form
1321 before Graphite: see canonicalize_loop_closed_ssa_form. */
1322 return (gimple_phi_num_args (phi
) == 1);
1325 /* For a definition DEF in REGION, propagates the expression EXPR in
1326 all the uses of DEF outside REGION. */
1329 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
1332 bool replaced_once
= false;
1334 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
1336 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
1339 imm_use_iterator imm_iter
;
1341 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1342 if (!is_gimple_debug (use_stmt
)
1343 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
1346 use_operand_p use_p
;
1348 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1349 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
1350 && (replaced_once
= true))
1351 replace_exp (use_p
, expr
);
1353 update_stmt (use_stmt
);
1358 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
1359 gsi_commit_edge_inserts ();
1363 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1364 dimension array for it. */
1367 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
1369 sese region
= SCOP_REGION (scop
);
1370 gimple
*phi
= gsi_stmt (*psi
);
1371 tree res
= gimple_phi_result (phi
);
1372 basic_block bb
= gimple_bb (phi
);
1373 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1374 tree arg
= gimple_phi_arg_def (phi
, 0);
1377 /* Note that loop close phi nodes should have a single argument
1378 because we translated the representation into a canonical form
1379 before Graphite: see canonicalize_loop_closed_ssa_form. */
1380 gcc_assert (gimple_phi_num_args (phi
) == 1);
1382 /* The phi node can be a non close phi node, when its argument is
1383 invariant, or a default definition. */
1384 if (is_gimple_min_invariant (arg
)
1385 || SSA_NAME_IS_DEFAULT_DEF (arg
))
1387 propagate_expr_outside_region (res
, arg
, region
);
1392 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
1394 propagate_expr_outside_region (res
, arg
, region
);
1395 stmt
= gimple_build_assign (res
, arg
);
1396 remove_phi_node (psi
, false);
1397 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1401 /* If res is scev analyzable and is not a scalar value, it is safe
1402 to ignore the close phi node: it will be code generated in the
1403 out of Graphite pass. */
1404 else if (scev_analyzable_p (res
, region
))
1406 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
1409 if (!loop_in_sese_p (loop
, region
))
1411 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
1412 scev
= scalar_evolution_in_region (region
, loop
, arg
);
1413 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
1416 scev
= scalar_evolution_in_region (region
, loop
, res
);
1418 if (tree_does_not_contain_chrecs (scev
))
1419 propagate_expr_outside_region (res
, scev
, region
);
1426 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
1428 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1430 if (TREE_CODE (arg
) == SSA_NAME
)
1431 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1432 SSA_NAME_DEF_STMT (arg
));
1434 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
1435 zero_dim_array
, arg
);
1438 remove_phi_node (psi
, false);
1439 SSA_NAME_DEF_STMT (res
) = stmt
;
1441 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1444 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1445 dimension array for it. */
1448 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
1450 gphi
*phi
= psi
->phi ();
1451 basic_block bb
= gimple_bb (phi
);
1452 tree res
= gimple_phi_result (phi
);
1453 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
1455 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1457 tree arg
= gimple_phi_arg_def (phi
, i
);
1458 edge e
= gimple_phi_arg_edge (phi
, i
);
1460 /* Avoid the insertion of code in the loop latch to please the
1461 pattern matching of the vectorizer. */
1462 if (TREE_CODE (arg
) == SSA_NAME
1463 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
1464 && e
->src
== bb
->loop_father
->latch
)
1465 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
1466 SSA_NAME_DEF_STMT (arg
));
1468 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
1471 gimple
*stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
1472 remove_phi_node (psi
, false);
1473 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
1476 /* Rewrite the degenerate phi node at position PSI from the degenerate
1477 form "x = phi (y, y, ..., y)" to "x = y". */
1480 rewrite_degenerate_phi (gphi_iterator
*psi
)
1482 gphi
*phi
= psi
->phi ();
1483 tree res
= gimple_phi_result (phi
);
1485 basic_block bb
= gimple_bb (phi
);
1486 tree rhs
= degenerate_phi_result (phi
);
1489 gimple
*stmt
= gimple_build_assign (res
, rhs
);
1490 remove_phi_node (psi
, false);
1492 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1493 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1496 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1499 rewrite_reductions_out_of_ssa (scop_p scop
)
1502 sese region
= SCOP_REGION (scop
);
1504 FOR_EACH_BB_FN (bb
, cfun
)
1505 if (bb_in_sese_p (bb
, region
))
1506 for (gphi_iterator psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
1508 gphi
*phi
= psi
.phi ();
1510 if (virtual_operand_p (gimple_phi_result (phi
)))
1516 if (gimple_phi_num_args (phi
) > 1
1517 && degenerate_phi_result (phi
))
1518 rewrite_degenerate_phi (&psi
);
1520 else if (scalar_close_phi_node_p (phi
))
1521 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1523 else if (reduction_phi_p (region
, &psi
))
1524 rewrite_phi_out_of_ssa (scop
, &psi
);
1527 update_ssa (TODO_update_ssa
);
1528 #ifdef ENABLE_CHECKING
1529 verify_loop_closed_ssa (true);
1533 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
1534 read from ZERO_DIM_ARRAY. */
1537 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
1538 tree def
, gimple
*use_stmt
)
1540 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
1542 tree name
= copy_ssa_name (def
);
1543 gimple
*name_stmt
= gimple_build_assign (name
, zero_dim_array
);
1545 gimple_assign_set_lhs (name_stmt
, name
);
1546 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
1549 use_operand_p use_p
;
1550 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
1551 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
1552 replace_exp (use_p
, name
);
1554 update_stmt (use_stmt
);
1557 /* For every definition DEF in the SCOP that is used outside the scop,
1558 insert a closing-scop definition in the basic block just after this
1562 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
1564 tree var
= create_tmp_reg (TREE_TYPE (def
));
1565 tree new_name
= make_ssa_name (var
, stmt
);
1566 bool needs_copy
= false;
1567 sese region
= SCOP_REGION (scop
);
1569 imm_use_iterator imm_iter
;
1571 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1573 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
1575 use_operand_p use_p
;
1576 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1578 SET_USE (use_p
, new_name
);
1580 update_stmt (use_stmt
);
1585 /* Insert in the empty BB just after the scop a use of DEF such
1586 that the rewrite of cross_bb_scalar_dependences won't insert
1587 arrays everywhere else. */
1590 gimple
*assign
= gimple_build_assign (new_name
, def
);
1591 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
1593 update_stmt (assign
);
1594 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
1598 /* Rewrite the scalar dependences crossing the boundary of the BB
1599 containing STMT with an array. Return true when something has been
1603 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
1605 sese region
= SCOP_REGION (scop
);
1606 gimple
*stmt
= gsi_stmt (*gsi
);
1607 imm_use_iterator imm_iter
;
1609 tree zero_dim_array
= NULL_TREE
;
1613 switch (gimple_code (stmt
))
1616 def
= gimple_assign_lhs (stmt
);
1620 def
= gimple_call_lhs (stmt
);
1628 || !is_gimple_reg (def
))
1631 if (scev_analyzable_p (def
, region
))
1633 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
1634 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
1636 if (tree_contains_chrecs (scev
, NULL
))
1639 propagate_expr_outside_region (def
, scev
, region
);
1643 basic_block def_bb
= gimple_bb (stmt
);
1645 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
1647 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1648 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
1651 gphi_iterator psi
= gsi_for_phi (phi
);
1653 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
1654 rewrite_close_phi_out_of_ssa (scop
, &psi
);
1656 rewrite_phi_out_of_ssa (scop
, &psi
);
1659 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
1660 if (gimple_code (use_stmt
) != GIMPLE_PHI
1661 && def_bb
!= gimple_bb (use_stmt
)
1662 && !is_gimple_debug (use_stmt
)
1665 if (!zero_dim_array
)
1667 zero_dim_array
= create_zero_dim_array
1668 (def
, "Cross_BB_scalar_dependence");
1669 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
1670 SSA_NAME_DEF_STMT (def
));
1674 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
1678 update_ssa (TODO_update_ssa
);
1683 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1686 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
1689 gimple_stmt_iterator psi
;
1690 sese region
= SCOP_REGION (scop
);
1691 bool changed
= false;
1693 /* Create an extra empty BB after the scop. */
1694 split_edge (SESE_EXIT (region
));
1696 FOR_EACH_BB_FN (bb
, cfun
)
1697 if (bb_in_sese_p (bb
, region
))
1698 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1699 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
1704 update_ssa (TODO_update_ssa
);
1705 #ifdef ENABLE_CHECKING
1706 verify_loop_closed_ssa (true);
1711 /* Builds the polyhedral representation for a SESE region. */
1714 build_poly_scop (scop_p scop
)
1716 set_scop_parameter_dim (scop
);
1717 build_scop_iteration_domain (scop
);
1718 build_scop_context (scop
);
1719 add_conditions_to_constraints (scop
);
1721 /* Rewrite out of SSA only after having translated the
1722 representation to the polyhedral representation to avoid scev
1723 analysis failures. That means that these functions will insert
1724 new data references that they create in the right place. */
1725 rewrite_reductions_out_of_ssa (scop
);
1726 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
1728 build_scop_drs (scop
);
1729 build_scop_scattering (scop
);
1731 /* This SCoP has been translated to the polyhedral
1733 POLY_SCOP_P (scop
) = true;
1735 #endif /* HAVE_isl */