1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010 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/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
31 #include "tree-dump.h"
34 #include "tree-chrec.h"
35 #include "tree-data-ref.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-pass.h"
39 #include "value-prof.h"
40 #include "pointer-set.h"
46 #include "graphite-ppl.h"
48 #include "graphite-poly.h"
49 #include "graphite-scop-detection.h"
50 #include "graphite-sese-to-poly.h"
52 /* Returns the index of the PHI argument defined in the outermost
56 phi_arg_in_outermost_loop (gimple phi
)
58 loop_p loop
= gimple_bb (phi
)->loop_father
;
61 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
62 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
64 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
71 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
72 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
75 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
77 gimple phi
= gsi_stmt (*psi
);
78 tree res
= gimple_phi_result (phi
);
79 size_t entry
= phi_arg_in_outermost_loop (phi
);
80 tree init
= gimple_phi_arg_def (phi
, entry
);
81 gimple stmt
= gimple_build_assign (res
, init
);
82 edge e
= gimple_phi_arg_edge (phi
, entry
);
84 remove_phi_node (psi
, false);
85 gsi_insert_on_edge_immediate (e
, stmt
);
86 SSA_NAME_DEF_STMT (res
) = stmt
;
89 /* Removes an invariant phi node at position PSI by inserting on the
90 loop ENTRY edge the assignment RES = INIT. */
93 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
95 gimple phi
= gsi_stmt (*psi
);
96 loop_p loop
= loop_containing_stmt (phi
);
97 tree res
= gimple_phi_result (phi
);
98 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
99 size_t entry
= phi_arg_in_outermost_loop (phi
);
100 edge e
= gimple_phi_arg_edge (phi
, entry
);
104 gimple_stmt_iterator gsi
;
106 if (tree_contains_chrecs (scev
, NULL
))
107 scev
= gimple_phi_arg_def (phi
, entry
);
109 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
110 stmt
= gimple_build_assign (res
, var
);
111 remove_phi_node (psi
, false);
114 stmts
= gimple_seq_alloc ();
116 gsi
= gsi_last (stmts
);
117 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
118 gsi_insert_seq_on_edge (e
, stmts
);
119 gsi_commit_edge_inserts ();
120 SSA_NAME_DEF_STMT (res
) = stmt
;
123 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
126 simple_copy_phi_p (gimple phi
)
130 if (gimple_phi_num_args (phi
) != 2)
133 res
= gimple_phi_result (phi
);
134 return (res
== gimple_phi_arg_def (phi
, 0)
135 || res
== gimple_phi_arg_def (phi
, 1));
138 /* Returns true when the phi node at position PSI is a reduction phi
139 node in REGION. Otherwise moves the pointer PSI to the next phi to
143 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
146 gimple phi
= gsi_stmt (*psi
);
147 tree res
= gimple_phi_result (phi
);
149 loop
= loop_containing_stmt (phi
);
151 if (simple_copy_phi_p (phi
))
153 /* PRE introduces phi nodes like these, for an example,
154 see id-5.f in the fortran graphite testsuite:
156 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
158 remove_simple_copy_phi (psi
);
162 if (scev_analyzable_p (res
, region
))
164 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
166 if (evolution_function_is_invariant_p (scev
, loop
->num
))
167 remove_invariant_phi (region
, psi
);
174 /* All the other cases are considered reductions. */
178 /* Store the GRAPHITE representation of BB. */
181 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
183 struct gimple_bb
*gbb
;
185 gbb
= XNEW (struct gimple_bb
);
188 GBB_DATA_REFS (gbb
) = drs
;
189 GBB_CONDITIONS (gbb
) = NULL
;
190 GBB_CONDITION_CASES (gbb
) = NULL
;
196 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
199 struct data_reference
*dr
;
201 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
204 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
207 free (bap
->alias_set
);
216 free_gimple_bb (struct gimple_bb
*gbb
)
218 free_data_refs_aux (GBB_DATA_REFS (gbb
));
219 free_data_refs (GBB_DATA_REFS (gbb
));
221 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
222 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
223 GBB_BB (gbb
)->aux
= 0;
227 /* Deletes all gimple bbs in SCOP. */
230 remove_gbbs_in_scop (scop_p scop
)
235 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
236 free_gimple_bb (PBB_BLACK_BOX (pbb
));
239 /* Deletes all scops in SCOPS. */
242 free_scops (VEC (scop_p
, heap
) *scops
)
247 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
249 remove_gbbs_in_scop (scop
);
250 free_sese (SCOP_REGION (scop
));
254 VEC_free (scop_p
, heap
, scops
);
257 /* Generates a polyhedral black box only if the bb contains interesting
261 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
263 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
264 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
265 gimple_stmt_iterator gsi
;
267 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
269 gimple stmt
= gsi_stmt (gsi
);
270 if (!is_gimple_debug (stmt
))
271 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
274 return new_gimple_bb (bb
, drs
);
277 /* Returns true if all predecessors of BB, that are not dominated by BB, are
278 marked in MAP. The predecessors dominated by BB are loop latches and will
279 be handled after BB. */
282 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
287 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
288 if (!TEST_BIT (map
, e
->src
->index
)
289 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
295 /* Compare the depth of two basic_block's P1 and P2. */
298 compare_bb_depths (const void *p1
, const void *p2
)
300 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
301 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
302 int d1
= loop_depth (bb1
->loop_father
);
303 int d2
= loop_depth (bb2
->loop_father
);
314 /* Sort the basic blocks from DOM such that the first are the ones at
315 a deepest loop level. */
318 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
320 VEC_qsort (basic_block
, dom
, compare_bb_depths
);
323 /* Recursive helper function for build_scops_bbs. */
326 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
328 sese region
= SCOP_REGION (scop
);
329 VEC (basic_block
, heap
) *dom
;
332 if (TEST_BIT (visited
, bb
->index
)
333 || !bb_in_sese_p (bb
, region
))
336 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
337 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
338 SET_BIT (visited
, bb
->index
);
340 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
345 graphite_sort_dominated_info (dom
);
347 while (!VEC_empty (basic_block
, dom
))
352 FOR_EACH_VEC_ELT (basic_block
, dom
, i
, dom_bb
)
353 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
355 build_scop_bbs_1 (scop
, visited
, dom_bb
);
356 VEC_unordered_remove (basic_block
, dom
, i
);
361 VEC_free (basic_block
, heap
, dom
);
364 /* Gather the basic blocks belonging to the SCOP. */
367 build_scop_bbs (scop_p scop
)
369 sbitmap visited
= sbitmap_alloc (last_basic_block
);
370 sese region
= SCOP_REGION (scop
);
372 sbitmap_zero (visited
);
373 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
374 sbitmap_free (visited
);
377 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
378 We generate SCATTERING_DIMENSIONS scattering dimensions.
380 CLooG 0.15.0 and previous versions require, that all
381 scattering functions of one CloogProgram have the same number of
382 scattering dimensions, therefore we allow to specify it. This
383 should be removed in future versions of CLooG.
385 The scattering polyhedron consists of these dimensions: scattering,
386 loop_iterators, parameters.
390 | scattering_dimensions = 5
391 | used_scattering_dimensions = 3
399 | Scattering polyhedron:
401 | scattering: {s1, s2, s3, s4, s5}
402 | loop_iterators: {i}
403 | parameters: {p1, p2}
405 | s1 s2 s3 s4 s5 i p1 p2 1
406 | 1 0 0 0 0 0 0 0 -4 = 0
407 | 0 1 0 0 0 -1 0 0 0 = 0
408 | 0 0 1 0 0 0 0 0 -5 = 0 */
411 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
412 poly_bb_p pbb
, int scattering_dimensions
)
415 scop_p scop
= PBB_SCOP (pbb
);
416 int nb_iterators
= pbb_dim_iter_domain (pbb
);
417 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
418 int nb_params
= scop_nb_params (scop
);
420 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
423 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
426 ppl_new_Coefficient (&c
);
427 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
428 ppl_new_C_Polyhedron_from_space_dimension
429 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
431 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
433 for (i
= 0; i
< scattering_dimensions
; i
++)
435 ppl_Constraint_t cstr
;
436 ppl_Linear_Expression_t expr
;
438 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
440 ppl_assign_Coefficient_from_mpz_t (c
, v
);
441 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
443 /* Textual order inside this loop. */
446 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
447 ppl_Coefficient_to_mpz_t (c
, v
);
449 ppl_assign_Coefficient_from_mpz_t (c
, v
);
450 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
453 /* Iterations of this loop. */
454 else /* if ((i % 2) == 1) */
456 int loop
= (i
- 1) / 2;
459 ppl_assign_Coefficient_from_mpz_t (c
, v
);
460 ppl_Linear_Expression_add_to_coefficient
461 (expr
, scattering_dimensions
+ loop
, c
);
464 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
465 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
466 ppl_delete_Linear_Expression (expr
);
467 ppl_delete_Constraint (cstr
);
471 ppl_delete_Coefficient (c
);
473 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
476 /* Build for BB the static schedule.
478 The static schedule is a Dewey numbering of the abstract syntax
479 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
481 The following example informally defines the static schedule:
500 Static schedules for A to F:
513 build_scop_scattering (scop_p scop
)
517 gimple_bb_p previous_gbb
= NULL
;
518 ppl_Linear_Expression_t static_schedule
;
523 ppl_new_Coefficient (&c
);
524 ppl_new_Linear_Expression (&static_schedule
);
526 /* We have to start schedules at 0 on the first component and
527 because we cannot compare_prefix_loops against a previous loop,
528 prefix will be equal to zero, and that index will be
529 incremented before copying. */
531 ppl_assign_Coefficient_from_mpz_t (c
, v
);
532 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
534 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
536 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
537 ppl_Linear_Expression_t common
;
539 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
542 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
547 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
548 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
552 ppl_assign_Coefficient_from_mpz_t (c
, v
);
553 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
554 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
557 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
559 ppl_delete_Linear_Expression (common
);
563 ppl_delete_Coefficient (c
);
564 ppl_delete_Linear_Expression (static_schedule
);
567 /* Add the value K to the dimension D of the linear expression EXPR. */
570 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
574 ppl_Coefficient_t coef
;
576 ppl_new_Coefficient (&coef
);
577 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
579 ppl_Coefficient_to_mpz_t (coef
, val
);
581 mpz_add (val
, val
, k
);
583 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
584 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
586 ppl_delete_Coefficient (coef
);
589 /* In the context of scop S, scan E, the right hand side of a scalar
590 evolution function in loop VAR, and translate it to a linear
594 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
595 ppl_Linear_Expression_t expr
)
599 loop_p loop
= get_loop (var
);
600 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
603 /* Scalar evolutions should happen in the sese region. */
604 gcc_assert (sese_loop_depth (s
, loop
) > 0);
606 /* We can not deal with parametric strides like:
612 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
615 mpz_set_si (val
, int_cst_value (e
));
616 add_value_to_dim (l
, expr
, val
);
621 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
622 linear expression EXPR. K is the multiplier of the constant. */
625 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, mpz_t k
)
628 ppl_Coefficient_t coef
;
629 int v
= int_cst_value (cst
);
634 /* Necessary to not get "-1 = 2^n - 1". */
636 mpz_sub_ui (val
, val
, -v
);
638 mpz_add_ui (val
, val
, v
);
640 mpz_mul (val
, val
, k
);
641 ppl_new_Coefficient (&coef
);
642 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
643 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
645 ppl_delete_Coefficient (coef
);
648 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
649 Otherwise returns -1. */
652 parameter_index_in_region_1 (tree name
, sese region
)
657 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
659 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (region
), i
, p
)
666 /* When the parameter NAME is in REGION, returns its index in
667 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
668 and returns the index of NAME. */
671 parameter_index_in_region (tree name
, sese region
)
675 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
677 i
= parameter_index_in_region_1 (name
, region
);
681 gcc_assert (SESE_ADD_PARAMS (region
));
683 i
= VEC_length (tree
, SESE_PARAMS (region
));
684 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
688 /* In the context of sese S, scan the expression E and translate it to
689 a linear expression C. When parsing a symbolic multiplication, K
690 represents the constant multiplier of an expression containing
694 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
697 if (e
== chrec_dont_know
)
700 switch (TREE_CODE (e
))
702 case POLYNOMIAL_CHREC
:
703 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
704 CHREC_VARIABLE (e
), c
);
705 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
709 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
714 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
716 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
717 mpz_mul (val
, val
, k
);
718 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
722 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
729 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
731 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
732 mpz_mul (val
, val
, k
);
733 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
737 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
742 case POINTER_PLUS_EXPR
:
743 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
744 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
749 ppl_Linear_Expression_t tmp_expr
= NULL
;
753 ppl_dimension_type dim
;
754 ppl_Linear_Expression_space_dimension (c
, &dim
);
755 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
758 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
759 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
763 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
765 ppl_delete_Linear_Expression (tmp_expr
);
773 ppl_Linear_Expression_t tmp_expr
= NULL
;
777 ppl_dimension_type dim
;
778 ppl_Linear_Expression_space_dimension (c
, &dim
);
779 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
782 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
786 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
788 ppl_delete_Linear_Expression (tmp_expr
);
796 ppl_Linear_Expression_t tmp_expr
= NULL
;
800 ppl_dimension_type dim
;
801 ppl_Linear_Expression_space_dimension (c
, &dim
);
802 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
805 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
809 ppl_Coefficient_t coef
;
812 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
814 ppl_delete_Linear_Expression (tmp_expr
);
815 mpz_init (minus_one
);
816 mpz_set_si (minus_one
, -1);
817 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
818 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
819 mpz_clear (minus_one
);
820 ppl_delete_Coefficient (coef
);
828 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
832 ppl_dimension_type dim
;
833 ppl_Linear_Expression_space_dimension (c
, &dim
);
834 p
+= dim
- sese_nb_params (s
);
835 add_value_to_dim (p
, c
, k
);
842 scan_tree_for_params_int (e
, c
, k
);
846 case NON_LVALUE_EXPR
:
847 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
856 /* Find parameters with respect to REGION in BB. We are looking in memory
857 access functions, conditions and loop bounds. */
860 find_params_in_bb (sese region
, gimple_bb_p gbb
)
866 loop_p loop
= GBB_BB (gbb
)->loop_father
;
872 /* Find parameters in the access functions of data references. */
873 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
874 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
875 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
877 /* Find parameters in conditional statements. */
878 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
880 tree lhs
= scalar_evolution_in_region (region
, loop
,
881 gimple_cond_lhs (stmt
));
882 tree rhs
= scalar_evolution_in_region (region
, loop
,
883 gimple_cond_rhs (stmt
));
885 scan_tree_for_params (region
, lhs
, NULL
, one
);
886 scan_tree_for_params (region
, rhs
, NULL
, one
);
892 /* Record the parameters used in the SCOP. A variable is a parameter
893 in a scop if it does not vary during the execution of that scop. */
896 find_scop_parameters (scop_p scop
)
900 sese region
= SCOP_REGION (scop
);
907 /* Find the parameters used in the loop bounds. */
908 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
910 tree nb_iters
= number_of_latch_executions (loop
);
912 if (!chrec_contains_symbols (nb_iters
))
915 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
916 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
921 /* Find the parameters used in data accesses. */
922 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
923 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
925 scop_set_nb_params (scop
, sese_nb_params (region
));
926 SESE_ADD_PARAMS (region
) = false;
928 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
929 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
932 /* Insert in the SCOP context constraints from the estimation of the
933 number of iterations. UB_EXPR is a linear expression describing
934 the number of iterations in a loop. This expression is bounded by
935 the estimation NIT. */
938 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
939 ppl_dimension_type dim
,
940 ppl_Linear_Expression_t ub_expr
)
943 ppl_Linear_Expression_t nb_iters_le
;
944 ppl_Polyhedron_t pol
;
945 ppl_Coefficient_t coef
;
948 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
949 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
952 /* Construct the negated number of last iteration in VAL. */
954 mpz_set_double_int (val
, nit
, false);
955 mpz_sub_ui (val
, val
, 1);
958 /* NB_ITERS_LE holds the number of last iteration in
959 parametrical form. Subtract estimated number of last
960 iteration and assert that result is not positive. */
961 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
962 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
963 ppl_delete_Coefficient (coef
);
964 ppl_new_Constraint (&ub
, nb_iters_le
,
965 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
966 ppl_Polyhedron_add_constraint (pol
, ub
);
968 /* Remove all but last GDIM dimensions from POL to obtain
969 only the constraints on the parameters. */
971 graphite_dim_t gdim
= scop_nb_params (scop
);
972 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
975 for (i
= 0; i
< dim
- gdim
; i
++)
978 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
982 /* Add the constraints on the parameters to the SCoP context. */
984 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
986 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
987 (&constraints_ps
, pol
);
988 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
989 (SCOP_CONTEXT (scop
), constraints_ps
);
990 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
993 ppl_delete_Polyhedron (pol
);
994 ppl_delete_Linear_Expression (nb_iters_le
);
995 ppl_delete_Constraint (ub
);
999 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1000 the constraints for the surrounding loops. */
1003 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1004 ppl_Polyhedron_t outer_ph
, int nb
,
1005 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1008 ppl_Polyhedron_t ph
;
1009 tree nb_iters
= number_of_latch_executions (loop
);
1010 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1011 sese region
= SCOP_REGION (scop
);
1014 ppl_const_Constraint_System_t pcs
;
1015 ppl_dimension_type
*map
1016 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1018 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1019 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1020 ppl_Polyhedron_add_constraints (ph
, pcs
);
1022 for (i
= 0; i
< (int) nb
; i
++)
1024 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1028 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1034 ppl_Constraint_t lb
;
1035 ppl_Linear_Expression_t lb_expr
;
1037 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1038 ppl_set_coef (lb_expr
, nb
, 1);
1039 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1040 ppl_delete_Linear_Expression (lb_expr
);
1041 ppl_Polyhedron_add_constraint (ph
, lb
);
1042 ppl_delete_Constraint (lb
);
1045 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1047 ppl_Constraint_t ub
;
1048 ppl_Linear_Expression_t ub_expr
;
1050 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1052 /* loop_i <= cst_nb_iters */
1053 ppl_set_coef (ub_expr
, nb
, -1);
1054 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1055 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1056 ppl_Polyhedron_add_constraint (ph
, ub
);
1057 ppl_delete_Linear_Expression (ub_expr
);
1058 ppl_delete_Constraint (ub
);
1060 else if (!chrec_contains_undetermined (nb_iters
))
1063 ppl_Constraint_t ub
;
1064 ppl_Linear_Expression_t ub_expr
;
1068 mpz_set_si (one
, 1);
1069 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1070 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1071 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1074 if (estimated_loop_iterations (loop
, true, &nit
))
1075 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1077 /* loop_i <= expr_nb_iters */
1078 ppl_set_coef (ub_expr
, nb
, -1);
1079 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1080 ppl_Polyhedron_add_constraint (ph
, ub
);
1081 ppl_delete_Linear_Expression (ub_expr
);
1082 ppl_delete_Constraint (ub
);
1087 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1088 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1092 && loop_in_sese_p (loop
->next
, region
))
1093 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1095 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1096 (&domains
[loop
->num
], ph
);
1098 ppl_delete_Polyhedron (ph
);
1101 /* Returns a linear expression for tree T evaluated in PBB. */
1103 static ppl_Linear_Expression_t
1104 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1107 ppl_Linear_Expression_t res
;
1108 ppl_dimension_type dim
;
1109 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1110 loop_p loop
= pbb_loop (pbb
);
1112 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1113 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1115 t
= scalar_evolution_in_region (region
, loop
, t
);
1116 gcc_assert (!automatically_generated_chrec_p (t
));
1119 mpz_set_si (one
, 1);
1120 scan_tree_for_params (region
, t
, res
, one
);
1126 /* Returns the ppl constraint type from the gimple tree code CODE. */
1128 static enum ppl_enum_Constraint_Type
1129 ppl_constraint_type_from_tree_code (enum tree_code code
)
1133 /* We do not support LT and GT to be able to work with C_Polyhedron.
1134 As we work on integer polyhedron "a < b" can be expressed by
1141 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1144 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1147 return PPL_CONSTRAINT_TYPE_EQUAL
;
1154 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1155 CODE is used as the comparison operator. This allows us to invert the
1156 condition or to handle inequalities. */
1159 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1160 poly_bb_p pbb
, enum tree_code code
)
1163 ppl_Coefficient_t c
;
1164 ppl_Linear_Expression_t left
, right
;
1165 ppl_Constraint_t cstr
;
1166 enum ppl_enum_Constraint_Type type
;
1168 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1169 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1171 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1172 the left or the right side of the expression. */
1173 if (code
== LT_EXPR
)
1177 ppl_new_Coefficient (&c
);
1178 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1179 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1180 ppl_delete_Coefficient (c
);
1185 else if (code
== GT_EXPR
)
1189 ppl_new_Coefficient (&c
);
1190 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1191 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1192 ppl_delete_Coefficient (c
);
1198 type
= ppl_constraint_type_from_tree_code (code
);
1200 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1202 ppl_new_Constraint (&cstr
, left
, type
);
1203 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1205 ppl_delete_Constraint (cstr
);
1206 ppl_delete_Linear_Expression (left
);
1207 ppl_delete_Linear_Expression (right
);
1210 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1211 operator. This allows us to invert the condition or to handle
1215 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1217 if (code
== NE_EXPR
)
1219 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1220 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1221 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1223 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1224 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1225 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
, right
);
1226 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1229 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1232 /* Add conditions to the domain of PBB. */
1235 add_conditions_to_domain (poly_bb_p pbb
)
1239 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1241 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1244 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
1245 switch (gimple_code (stmt
))
1249 enum tree_code code
= gimple_cond_code (stmt
);
1251 /* The conditions for ELSE-branches are inverted. */
1252 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1253 code
= invert_tree_comparison (code
, false);
1255 add_condition_to_pbb (pbb
, stmt
, code
);
1260 /* Switch statements are not supported right now - fall throught. */
1268 /* Traverses all the GBBs of the SCOP and add their constraints to the
1269 iteration domains. */
1272 add_conditions_to_constraints (scop_p scop
)
1277 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1278 add_conditions_to_domain (pbb
);
1281 /* Structure used to pass data to dom_walk. */
1285 VEC (gimple
, heap
) **conditions
, **cases
;
1289 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1290 edge between BB and its predecessor is not a loop exit edge, and
1291 the last statement of the single predecessor is a COND_EXPR. */
1294 single_pred_cond_non_loop_exit (basic_block bb
)
1296 if (single_pred_p (bb
))
1298 edge e
= single_pred_edge (bb
);
1299 basic_block pred
= e
->src
;
1302 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1305 stmt
= last_stmt (pred
);
1307 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1314 /* Call-back for dom_walk executed before visiting the dominated
1318 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1321 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1322 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1323 VEC (gimple
, heap
) **cases
= data
->cases
;
1327 if (!bb_in_sese_p (bb
, data
->region
))
1330 stmt
= single_pred_cond_non_loop_exit (bb
);
1334 edge e
= single_pred_edge (bb
);
1336 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1338 if (e
->flags
& EDGE_TRUE_VALUE
)
1339 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1341 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1344 gbb
= gbb_from_bb (bb
);
1348 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1349 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1353 /* Call-back for dom_walk executed after visiting the dominated
1357 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1360 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1361 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1362 VEC (gimple
, heap
) **cases
= data
->cases
;
1364 if (!bb_in_sese_p (bb
, data
->region
))
1367 if (single_pred_cond_non_loop_exit (bb
))
1369 VEC_pop (gimple
, *conditions
);
1370 VEC_pop (gimple
, *cases
);
1374 /* Record all conditions in REGION. */
1377 build_sese_conditions (sese region
)
1379 struct dom_walk_data walk_data
;
1380 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1381 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1384 data
.conditions
= &conditions
;
1385 data
.cases
= &cases
;
1386 data
.region
= region
;
1388 walk_data
.dom_direction
= CDI_DOMINATORS
;
1389 walk_data
.initialize_block_local_data
= NULL
;
1390 walk_data
.before_dom_children
= build_sese_conditions_before
;
1391 walk_data
.after_dom_children
= build_sese_conditions_after
;
1392 walk_data
.global_data
= &data
;
1393 walk_data
.block_local_data_size
= 0;
1395 init_walk_dominator_tree (&walk_data
);
1396 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1397 fini_walk_dominator_tree (&walk_data
);
1399 VEC_free (gimple
, heap
, conditions
);
1400 VEC_free (gimple
, heap
, cases
);
1403 /* Add constraints on the possible values of parameter P from the type
1407 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1409 ppl_Constraint_t cstr
;
1410 ppl_Linear_Expression_t le
;
1411 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1412 tree type
= TREE_TYPE (parameter
);
1413 tree lb
= NULL_TREE
;
1414 tree ub
= NULL_TREE
;
1416 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1417 lb
= lower_bound_in_type (type
, type
);
1419 lb
= TYPE_MIN_VALUE (type
);
1421 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1422 ub
= upper_bound_in_type (type
, type
);
1424 ub
= TYPE_MAX_VALUE (type
);
1428 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1429 ppl_set_coef (le
, p
, -1);
1430 ppl_set_inhomogeneous_tree (le
, lb
);
1431 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1432 ppl_Polyhedron_add_constraint (context
, cstr
);
1433 ppl_delete_Linear_Expression (le
);
1434 ppl_delete_Constraint (cstr
);
1439 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1440 ppl_set_coef (le
, p
, -1);
1441 ppl_set_inhomogeneous_tree (le
, ub
);
1442 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1443 ppl_Polyhedron_add_constraint (context
, cstr
);
1444 ppl_delete_Linear_Expression (le
);
1445 ppl_delete_Constraint (cstr
);
1449 /* Build the context of the SCOP. The context usually contains extra
1450 constraints that are added to the iteration domains that constrain
1454 build_scop_context (scop_p scop
)
1456 ppl_Polyhedron_t context
;
1457 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1458 graphite_dim_t p
, n
= scop_nb_params (scop
);
1460 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1462 for (p
= 0; p
< n
; p
++)
1463 add_param_constraints (scop
, context
, p
);
1465 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1467 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1468 (SCOP_CONTEXT (scop
), ps
);
1470 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1471 ppl_delete_Polyhedron (context
);
1474 /* Build the iteration domains: the loops belonging to the current
1475 SCOP, and that vary for the execution of the current basic block.
1476 Returns false if there is no loop in SCOP. */
1479 build_scop_iteration_domain (scop_p scop
)
1482 sese region
= SCOP_REGION (scop
);
1484 ppl_Polyhedron_t ph
;
1486 int nb_loops
= number_of_loops ();
1487 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1488 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1490 for (i
= 0; i
< nb_loops
; i
++)
1493 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1495 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
1496 if (!loop_in_sese_p (loop_outer (loop
), region
))
1497 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1499 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1500 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1501 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1502 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1503 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1505 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1506 (&PBB_DOMAIN (pbb
), ph
);
1508 for (i
= 0; i
< nb_loops
; i
++)
1510 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1512 ppl_delete_Polyhedron (ph
);
1516 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1517 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1518 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1522 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1523 ppl_dimension_type accessp_nb_dims
,
1524 ppl_dimension_type dom_nb_dims
)
1526 ppl_Linear_Expression_t alias
;
1527 ppl_Constraint_t cstr
;
1528 int alias_set_num
= 0;
1529 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1531 if (bap
&& bap
->alias_set
)
1532 alias_set_num
= *(bap
->alias_set
);
1534 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1536 ppl_set_coef (alias
, dom_nb_dims
, 1);
1537 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1538 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1539 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1541 ppl_delete_Linear_Expression (alias
);
1542 ppl_delete_Constraint (cstr
);
1545 /* Add to ACCESSES polyhedron equalities defining the access functions
1546 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1547 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1548 PBB is the poly_bb_p that contains the data reference DR. */
1551 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1552 ppl_dimension_type accessp_nb_dims
,
1553 ppl_dimension_type dom_nb_dims
,
1556 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1558 scop_p scop
= PBB_SCOP (pbb
);
1559 sese region
= SCOP_REGION (scop
);
1563 for (i
= 0; i
< nb_subscripts
; i
++)
1565 ppl_Linear_Expression_t fn
, access
;
1566 ppl_Constraint_t cstr
;
1567 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1568 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1570 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1571 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1574 scan_tree_for_params (region
, afn
, fn
, v
);
1575 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1577 ppl_set_coef (access
, subscript
, -1);
1578 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1579 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1581 ppl_delete_Linear_Expression (fn
);
1582 ppl_delete_Linear_Expression (access
);
1583 ppl_delete_Constraint (cstr
);
1589 /* Add constrains representing the size of the accessed data to the
1590 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1591 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1595 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1596 ppl_dimension_type accessp_nb_dims
,
1597 ppl_dimension_type dom_nb_dims
)
1599 tree ref
= DR_REF (dr
);
1600 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1602 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1604 ppl_Linear_Expression_t expr
;
1605 ppl_Constraint_t cstr
;
1606 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1609 if (TREE_CODE (ref
) != ARRAY_REF
)
1612 low
= array_ref_low_bound (ref
);
1614 /* subscript - low >= 0 */
1615 if (host_integerp (low
, 0))
1617 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1618 ppl_set_coef (expr
, subscript
, 1);
1620 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1622 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1623 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1624 ppl_delete_Linear_Expression (expr
);
1625 ppl_delete_Constraint (cstr
);
1628 high
= array_ref_up_bound (ref
);
1630 /* high - subscript >= 0 */
1631 if (high
&& host_integerp (high
, 0)
1632 /* 1-element arrays at end of structures may extend over
1633 their declared size. */
1634 && !(array_at_struct_end_p (ref
)
1635 && operand_equal_p (low
, high
, 0)))
1637 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1638 ppl_set_coef (expr
, subscript
, -1);
1640 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1642 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1643 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1644 ppl_delete_Linear_Expression (expr
);
1645 ppl_delete_Constraint (cstr
);
1650 /* Build data accesses for DR in PBB. */
1653 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1655 ppl_Polyhedron_t accesses
;
1656 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1657 ppl_dimension_type dom_nb_dims
;
1658 ppl_dimension_type accessp_nb_dims
;
1659 int dr_base_object_set
;
1661 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1663 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1665 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1667 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1668 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1669 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1671 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1673 ppl_delete_Polyhedron (accesses
);
1675 gcc_assert (dr
->aux
);
1676 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1678 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
,
1679 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1680 dr
, DR_NUM_DIMENSIONS (dr
));
1683 /* Write to FILE the alias graph of data references in DIMACS format. */
1686 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1687 VEC (data_reference_p
, heap
) *drs
)
1689 int num_vertex
= VEC_length (data_reference_p
, drs
);
1691 data_reference_p dr1
, dr2
;
1694 if (num_vertex
== 0)
1697 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1698 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1699 if (dr_may_alias_p (dr1
, dr2
))
1702 fprintf (file
, "$\n");
1705 fprintf (file
, "c %s\n", comment
);
1707 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1709 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1710 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1711 if (dr_may_alias_p (dr1
, dr2
))
1712 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1717 /* Write to FILE the alias graph of data references in DOT format. */
1720 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1721 VEC (data_reference_p
, heap
) *drs
)
1723 int num_vertex
= VEC_length (data_reference_p
, drs
);
1724 data_reference_p dr1
, dr2
;
1727 if (num_vertex
== 0)
1730 fprintf (file
, "$\n");
1733 fprintf (file
, "c %s\n", comment
);
1735 /* First print all the vertices. */
1736 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1737 fprintf (file
, "n%d;\n", i
);
1739 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1740 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1741 if (dr_may_alias_p (dr1
, dr2
))
1742 fprintf (file
, "n%d n%d\n", i
, j
);
1747 /* Write to FILE the alias graph of data references in ECC format. */
1750 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1751 VEC (data_reference_p
, heap
) *drs
)
1753 int num_vertex
= VEC_length (data_reference_p
, drs
);
1754 data_reference_p dr1
, dr2
;
1757 if (num_vertex
== 0)
1760 fprintf (file
, "$\n");
1763 fprintf (file
, "c %s\n", comment
);
1765 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1766 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1767 if (dr_may_alias_p (dr1
, dr2
))
1768 fprintf (file
, "%d %d\n", i
, j
);
1773 /* Check if DR1 and DR2 are in the same object set. */
1776 dr_same_base_object_p (const struct data_reference
*dr1
,
1777 const struct data_reference
*dr2
)
1779 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1782 /* Uses DFS component number as representative of alias-sets. Also tests for
1783 optimality by verifying if every connected component is a clique. Returns
1784 true (1) if the above test is true, and false (0) otherwise. */
1787 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1789 int num_vertices
= VEC_length (data_reference_p
, drs
);
1790 struct graph
*g
= new_graph (num_vertices
);
1791 data_reference_p dr1
, dr2
;
1793 int num_connected_components
;
1794 int v_indx1
, v_indx2
, num_vertices_in_component
;
1797 struct graph_edge
*e
;
1798 int this_component_is_clique
;
1799 int all_components_are_cliques
= 1;
1801 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1802 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1803 if (dr_may_alias_p (dr1
, dr2
))
1809 all_vertices
= XNEWVEC (int, num_vertices
);
1810 vertices
= XNEWVEC (int, num_vertices
);
1811 for (i
= 0; i
< num_vertices
; i
++)
1812 all_vertices
[i
] = i
;
1814 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1816 for (i
= 0; i
< g
->n_vertices
; i
++)
1818 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1819 base_alias_pair
*bap
;
1821 gcc_assert (dr
->aux
);
1822 bap
= (base_alias_pair
*)(dr
->aux
);
1824 bap
->alias_set
= XNEW (int);
1825 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1828 /* Verify if the DFS numbering results in optimal solution. */
1829 for (i
= 0; i
< num_connected_components
; i
++)
1831 num_vertices_in_component
= 0;
1832 /* Get all vertices whose DFS component number is the same as i. */
1833 for (j
= 0; j
< num_vertices
; j
++)
1834 if (g
->vertices
[j
].component
== i
)
1835 vertices
[num_vertices_in_component
++] = j
;
1837 /* Now test if the vertices in 'vertices' form a clique, by testing
1838 for edges among each pair. */
1839 this_component_is_clique
= 1;
1840 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1842 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1844 /* Check if the two vertices are connected by iterating
1845 through all the edges which have one of these are source. */
1846 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1849 if (e
->src
== vertices
[v_indx1
])
1855 this_component_is_clique
= 0;
1859 if (!this_component_is_clique
)
1860 all_components_are_cliques
= 0;
1864 free (all_vertices
);
1867 return all_components_are_cliques
;
1870 /* Group each data reference in DRS with its base object set num. */
1873 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1875 int num_vertex
= VEC_length (data_reference_p
, drs
);
1876 struct graph
*g
= new_graph (num_vertex
);
1877 data_reference_p dr1
, dr2
;
1881 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1882 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1883 if (dr_same_base_object_p (dr1
, dr2
))
1889 queue
= XNEWVEC (int, num_vertex
);
1890 for (i
= 0; i
< num_vertex
; i
++)
1893 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1895 for (i
= 0; i
< g
->n_vertices
; i
++)
1897 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1898 base_alias_pair
*bap
;
1900 gcc_assert (dr
->aux
);
1901 bap
= (base_alias_pair
*)(dr
->aux
);
1903 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1910 /* Build the data references for PBB. */
1913 build_pbb_drs (poly_bb_p pbb
)
1916 data_reference_p dr
;
1917 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1919 FOR_EACH_VEC_ELT (data_reference_p
, gbb_drs
, j
, dr
)
1920 build_poly_dr (dr
, pbb
);
1923 /* Dump to file the alias graphs for the data references in DRS. */
1926 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
1929 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1931 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1934 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1935 current_function_name ());
1936 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1937 fclose (file_dimacs
);
1940 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1943 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1944 current_function_name ());
1945 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1949 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1952 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1953 current_function_name ());
1954 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1959 /* Build data references in SCOP. */
1962 build_scop_drs (scop_p scop
)
1966 data_reference_p dr
;
1967 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1969 /* Remove all the PBBs that do not have data references: these basic
1970 blocks are not handled in the polyhedral representation. */
1971 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1972 if (VEC_empty (data_reference_p
, GBB_DATA_REFS (PBB_BLACK_BOX (pbb
))))
1974 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1975 VEC_ordered_remove (poly_bb_p
, SCOP_BBS (scop
), i
);
1979 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1980 for (j
= 0; VEC_iterate (data_reference_p
,
1981 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
1982 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1984 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr
)
1985 dr
->aux
= XNEW (base_alias_pair
);
1987 if (!build_alias_set_optimal_p (drs
))
1989 /* TODO: Add support when building alias set is not optimal. */
1993 build_base_obj_set_for_drs (drs
);
1995 /* When debugging, enable the following code. This cannot be used
1996 in production compilers. */
1998 dump_alias_graphs (drs
);
2000 VEC_free (data_reference_p
, heap
, drs
);
2002 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2003 build_pbb_drs (pbb
);
2006 /* Return a gsi at the position of the phi node STMT. */
2008 static gimple_stmt_iterator
2009 gsi_for_phi_node (gimple stmt
)
2011 gimple_stmt_iterator psi
;
2012 basic_block bb
= gimple_bb (stmt
);
2014 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2015 if (stmt
== gsi_stmt (psi
))
2022 /* Analyze all the data references of STMTS and add them to the
2023 GBB_DATA_REFS vector of BB. */
2026 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, VEC (gimple
, heap
) *stmts
)
2033 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2036 nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
2037 gbb
= gbb_from_bb (bb
);
2039 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
2040 if (!is_gimple_debug (stmt
))
2041 graphite_find_data_references_in_stmt (nest
, stmt
,
2042 &GBB_DATA_REFS (gbb
));
2045 /* Insert STMT at the end of the STMTS sequence and then insert the
2046 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2050 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
2051 gimple_stmt_iterator insert_gsi
)
2053 gimple_stmt_iterator gsi
;
2054 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2057 stmts
= gimple_seq_alloc ();
2059 gsi
= gsi_last (stmts
);
2060 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2061 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2062 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2064 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2065 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2066 VEC_free (gimple
, heap
, x
);
2069 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2072 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2075 gimple_stmt_iterator si
;
2076 gimple_stmt_iterator gsi
;
2077 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2078 gimple stmt
= gimple_build_assign (res
, var
);
2079 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2082 stmts
= gimple_seq_alloc ();
2083 si
= gsi_last (stmts
);
2084 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2085 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2086 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2088 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2090 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2091 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2095 gsi
= gsi_for_stmt (after_stmt
);
2096 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2099 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2100 VEC_free (gimple
, heap
, x
);
2103 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2106 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2108 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2109 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2110 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2111 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2112 int index
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
2114 /* The INDEX of PBB in SCOP_BBS. */
2115 for (index
= 0; index
< n
; index
++)
2116 if (VEC_index (poly_bb_p
, SCOP_BBS (scop
), index
) == pbb
)
2119 GBB_PBB (gbb1
) = pbb1
;
2120 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2121 (&PBB_DOMAIN (pbb1
), PBB_DOMAIN (pbb
));
2122 GBB_CONDITIONS (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITIONS (gbb
));
2123 GBB_CONDITION_CASES (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
2124 VEC_safe_insert (poly_bb_p
, heap
, SCOP_BBS (scop
), index
+ 1, pbb1
);
2127 /* Insert on edge E the assignment "RES := EXPR". */
2130 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2132 gimple_stmt_iterator gsi
;
2134 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2135 gimple stmt
= gimple_build_assign (res
, var
);
2137 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2140 stmts
= gimple_seq_alloc ();
2142 gsi
= gsi_last (stmts
);
2143 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2144 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2145 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2147 gsi_insert_seq_on_edge (e
, stmts
);
2148 gsi_commit_edge_inserts ();
2149 bb
= gimple_bb (stmt
);
2151 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2154 if (!gbb_from_bb (bb
))
2155 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2157 analyze_drs_in_stmts (scop
, bb
, x
);
2158 VEC_free (gimple
, heap
, x
);
2161 /* Creates a zero dimension array of the same type as VAR. */
2164 create_zero_dim_array (tree var
, const char *base_name
)
2166 tree index_type
= build_index_type (integer_zero_node
);
2167 tree elt_type
= TREE_TYPE (var
);
2168 tree array_type
= build_array_type (elt_type
, index_type
);
2169 tree base
= create_tmp_var (array_type
, base_name
);
2171 add_referenced_var (base
);
2173 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2177 /* Returns true when PHI is a loop close phi node. */
2180 scalar_close_phi_node_p (gimple phi
)
2182 if (gimple_code (phi
) != GIMPLE_PHI
2183 || !is_gimple_reg (gimple_phi_result (phi
)))
2186 /* Note that loop close phi nodes should have a single argument
2187 because we translated the representation into a canonical form
2188 before Graphite: see canonicalize_loop_closed_ssa_form. */
2189 return (gimple_phi_num_args (phi
) == 1);
2192 /* For a definition DEF in REGION, propagates the expression EXPR in
2193 all the uses of DEF outside REGION. */
2196 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2198 imm_use_iterator imm_iter
;
2201 bool replaced_once
= false;
2203 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2205 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2208 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2209 if (!is_gimple_debug (use_stmt
)
2210 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2213 use_operand_p use_p
;
2215 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2216 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2217 && (replaced_once
= true))
2218 replace_exp (use_p
, expr
);
2220 update_stmt (use_stmt
);
2225 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2226 gsi_commit_edge_inserts ();
2230 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2231 dimension array for it. */
2234 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2236 sese region
= SCOP_REGION (scop
);
2237 gimple phi
= gsi_stmt (*psi
);
2238 tree res
= gimple_phi_result (phi
);
2239 tree var
= SSA_NAME_VAR (res
);
2240 basic_block bb
= gimple_bb (phi
);
2241 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2242 tree arg
= gimple_phi_arg_def (phi
, 0);
2245 /* Note that loop close phi nodes should have a single argument
2246 because we translated the representation into a canonical form
2247 before Graphite: see canonicalize_loop_closed_ssa_form. */
2248 gcc_assert (gimple_phi_num_args (phi
) == 1);
2250 /* The phi node can be a non close phi node, when its argument is
2251 invariant, or a default definition. */
2252 if (is_gimple_min_invariant (arg
)
2253 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2255 propagate_expr_outside_region (res
, arg
, region
);
2260 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2262 propagate_expr_outside_region (res
, arg
, region
);
2263 stmt
= gimple_build_assign (res
, arg
);
2264 remove_phi_node (psi
, false);
2265 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2266 SSA_NAME_DEF_STMT (res
) = stmt
;
2270 /* If res is scev analyzable and is not a scalar value, it is safe
2271 to ignore the close phi node: it will be code generated in the
2272 out of Graphite pass. */
2273 else if (scev_analyzable_p (res
, region
))
2275 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2278 if (!loop_in_sese_p (loop
, region
))
2280 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2281 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2282 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2285 scev
= scalar_evolution_in_region (region
, loop
, res
);
2287 if (tree_does_not_contain_chrecs (scev
))
2288 propagate_expr_outside_region (res
, scev
, region
);
2295 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2297 stmt
= gimple_build_assign (res
, zero_dim_array
);
2299 if (TREE_CODE (arg
) == SSA_NAME
)
2300 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2301 SSA_NAME_DEF_STMT (arg
));
2303 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2304 zero_dim_array
, arg
);
2307 remove_phi_node (psi
, false);
2308 SSA_NAME_DEF_STMT (res
) = stmt
;
2310 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2313 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2314 dimension array for it. */
2317 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2320 gimple phi
= gsi_stmt (*psi
);
2321 basic_block bb
= gimple_bb (phi
);
2322 tree res
= gimple_phi_result (phi
);
2323 tree var
= SSA_NAME_VAR (res
);
2324 tree zero_dim_array
= create_zero_dim_array (var
, "phi_out_of_ssa");
2328 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2330 tree arg
= gimple_phi_arg_def (phi
, i
);
2331 edge e
= gimple_phi_arg_edge (phi
, i
);
2333 /* Avoid the insertion of code in the loop latch to please the
2334 pattern matching of the vectorizer. */
2335 if (TREE_CODE (arg
) == SSA_NAME
2336 && e
->src
== bb
->loop_father
->latch
)
2337 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2338 SSA_NAME_DEF_STMT (arg
));
2340 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2343 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2345 stmt
= gimple_build_assign (res
, var
);
2346 remove_phi_node (psi
, false);
2347 SSA_NAME_DEF_STMT (res
) = stmt
;
2349 insert_stmts (scop
, stmt
, stmts
, gsi_after_labels (bb
));
2352 /* Rewrite the degenerate phi node at position PSI from the degenerate
2353 form "x = phi (y, y, ..., y)" to "x = y". */
2356 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2360 gimple_stmt_iterator gsi
;
2361 gimple phi
= gsi_stmt (*psi
);
2362 tree res
= gimple_phi_result (phi
);
2365 bb
= gimple_bb (phi
);
2366 rhs
= degenerate_phi_result (phi
);
2369 stmt
= gimple_build_assign (res
, rhs
);
2370 remove_phi_node (psi
, false);
2371 SSA_NAME_DEF_STMT (res
) = stmt
;
2373 gsi
= gsi_after_labels (bb
);
2374 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2377 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2380 rewrite_reductions_out_of_ssa (scop_p scop
)
2383 gimple_stmt_iterator psi
;
2384 sese region
= SCOP_REGION (scop
);
2387 if (bb_in_sese_p (bb
, region
))
2388 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2390 gimple phi
= gsi_stmt (psi
);
2392 if (!is_gimple_reg (gimple_phi_result (phi
)))
2398 if (gimple_phi_num_args (phi
) > 1
2399 && degenerate_phi_result (phi
))
2400 rewrite_degenerate_phi (&psi
);
2402 else if (scalar_close_phi_node_p (phi
))
2403 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2405 else if (reduction_phi_p (region
, &psi
))
2406 rewrite_phi_out_of_ssa (scop
, &psi
);
2409 update_ssa (TODO_update_ssa
);
2410 #ifdef ENABLE_CHECKING
2411 verify_loop_closed_ssa (true);
2415 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2416 read from ZERO_DIM_ARRAY. */
2419 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2420 tree def
, gimple use_stmt
)
2422 tree var
= SSA_NAME_VAR (def
);
2423 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2424 tree name
= make_ssa_name (var
, name_stmt
);
2426 use_operand_p use_p
;
2428 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2430 gimple_assign_set_lhs (name_stmt
, name
);
2431 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2433 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2434 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2435 replace_exp (use_p
, name
);
2437 update_stmt (use_stmt
);
2440 /* For every definition DEF in the SCOP that is used outside the scop,
2441 insert a closing-scop definition in the basic block just after this
2445 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2447 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2448 tree new_name
= make_ssa_name (var
, stmt
);
2449 bool needs_copy
= false;
2450 use_operand_p use_p
;
2451 imm_use_iterator imm_iter
;
2453 sese region
= SCOP_REGION (scop
);
2455 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2457 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2459 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2461 SET_USE (use_p
, new_name
);
2463 update_stmt (use_stmt
);
2468 /* Insert in the empty BB just after the scop a use of DEF such
2469 that the rewrite of cross_bb_scalar_dependences won't insert
2470 arrays everywhere else. */
2473 gimple assign
= gimple_build_assign (new_name
, def
);
2474 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2476 add_referenced_var (var
);
2477 SSA_NAME_DEF_STMT (new_name
) = assign
;
2478 update_stmt (assign
);
2479 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2483 /* Rewrite the scalar dependences crossing the boundary of the BB
2484 containing STMT with an array. Return true when something has been
2488 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2490 sese region
= SCOP_REGION (scop
);
2491 gimple stmt
= gsi_stmt (*gsi
);
2492 imm_use_iterator imm_iter
;
2495 tree zero_dim_array
= NULL_TREE
;
2499 switch (gimple_code (stmt
))
2502 def
= gimple_assign_lhs (stmt
);
2506 def
= gimple_call_lhs (stmt
);
2514 || !is_gimple_reg (def
))
2517 if (scev_analyzable_p (def
, region
))
2519 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2520 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2522 if (tree_contains_chrecs (scev
, NULL
))
2525 propagate_expr_outside_region (def
, scev
, region
);
2529 def_bb
= gimple_bb (stmt
);
2531 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2533 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2534 if (gimple_code (use_stmt
) == GIMPLE_PHI
2537 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2539 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2540 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2542 rewrite_phi_out_of_ssa (scop
, &psi
);
2545 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2546 if (gimple_code (use_stmt
) != GIMPLE_PHI
2547 && def_bb
!= gimple_bb (use_stmt
)
2548 && !is_gimple_debug (use_stmt
)
2551 if (!zero_dim_array
)
2553 zero_dim_array
= create_zero_dim_array
2554 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2555 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2556 SSA_NAME_DEF_STMT (def
));
2560 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2567 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2570 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2573 gimple_stmt_iterator psi
;
2574 sese region
= SCOP_REGION (scop
);
2575 bool changed
= false;
2577 /* Create an extra empty BB after the scop. */
2578 split_edge (SESE_EXIT (region
));
2581 if (bb_in_sese_p (bb
, region
))
2582 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2583 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2588 update_ssa (TODO_update_ssa
);
2589 #ifdef ENABLE_CHECKING
2590 verify_loop_closed_ssa (true);
2595 /* Returns the number of pbbs that are in loops contained in SCOP. */
2598 nb_pbbs_in_loops (scop_p scop
)
2604 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2605 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2611 /* Return the number of data references in BB that write in
2615 nb_data_writes_in_bb (basic_block bb
)
2618 gimple_stmt_iterator gsi
;
2620 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2621 if (gimple_vdef (gsi_stmt (gsi
)))
2627 /* Splits at STMT the basic block BB represented as PBB in the
2631 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2633 edge e1
= split_block (bb
, stmt
);
2634 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2638 /* Splits STMT out of its current BB. This is done for reduction
2639 statements for which we want to ignore data dependences. */
2642 split_reduction_stmt (scop_p scop
, gimple stmt
)
2644 basic_block bb
= gimple_bb (stmt
);
2645 poly_bb_p pbb
= pbb_from_bb (bb
);
2646 gimple_bb_p gbb
= gbb_from_bb (bb
);
2649 data_reference_p dr
;
2651 /* Do not split basic blocks with no writes to memory: the reduction
2652 will be the only write to memory. */
2653 if (nb_data_writes_in_bb (bb
) == 0)
2656 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2658 /* Split once more only when the reduction stmt is not the only one
2659 left in the original BB. */
2660 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2662 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2664 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2667 /* A part of the data references will end in a different basic block
2668 after the split: move the DRs from the original GBB to the newly
2670 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
2672 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2676 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2677 VEC_safe_push (data_reference_p
, heap
, GBB_DATA_REFS (gbb1
), dr
);
2678 VEC_ordered_remove (data_reference_p
, GBB_DATA_REFS (gbb
), i
);
2686 /* Return true when stmt is a reduction operation. */
2689 is_reduction_operation_p (gimple stmt
)
2691 enum tree_code code
;
2693 gcc_assert (is_gimple_assign (stmt
));
2694 code
= gimple_assign_rhs_code (stmt
);
2696 return flag_associative_math
2697 && commutative_tree_code (code
)
2698 && associative_tree_code (code
);
2701 /* Returns true when PHI contains an argument ARG. */
2704 phi_contains_arg (gimple phi
, tree arg
)
2708 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2709 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2715 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2718 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2722 if (TREE_CODE (arg
) != SSA_NAME
)
2725 stmt
= SSA_NAME_DEF_STMT (arg
);
2727 if (gimple_code (stmt
) == GIMPLE_NOP
2728 || gimple_code (stmt
) == GIMPLE_CALL
)
2731 if (gimple_code (stmt
) == GIMPLE_PHI
)
2733 if (phi_contains_arg (stmt
, lhs
))
2738 if (!is_gimple_assign (stmt
))
2741 if (gimple_num_ops (stmt
) == 2)
2742 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2744 if (is_reduction_operation_p (stmt
))
2746 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2749 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2755 /* Detect commutative and associative scalar reductions starting at
2756 the STMT. Return the phi node of the reduction cycle, or NULL. */
2759 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2760 VEC (gimple
, heap
) **in
,
2761 VEC (gimple
, heap
) **out
)
2763 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2768 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2769 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2773 /* Detect commutative and associative scalar reductions starting at
2774 STMT. Return the phi node of the reduction cycle, or NULL. */
2777 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2778 VEC (gimple
, heap
) **out
)
2780 tree lhs
= gimple_assign_lhs (stmt
);
2782 if (gimple_num_ops (stmt
) == 2)
2783 return detect_commutative_reduction_arg (lhs
, stmt
,
2784 gimple_assign_rhs1 (stmt
),
2787 if (is_reduction_operation_p (stmt
))
2789 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2790 gimple_assign_rhs1 (stmt
),
2793 : detect_commutative_reduction_arg (lhs
, stmt
,
2794 gimple_assign_rhs2 (stmt
),
2801 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2804 follow_inital_value_to_phi (tree arg
, tree lhs
)
2808 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2811 stmt
= SSA_NAME_DEF_STMT (arg
);
2813 if (gimple_code (stmt
) == GIMPLE_PHI
2814 && phi_contains_arg (stmt
, lhs
))
2821 /* Return the argument of the loop PHI that is the inital value coming
2822 from outside the loop. */
2825 edge_initial_value_for_loop_phi (gimple phi
)
2829 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2831 edge e
= gimple_phi_arg_edge (phi
, i
);
2833 if (loop_depth (e
->src
->loop_father
)
2834 < loop_depth (e
->dest
->loop_father
))
2841 /* Return the argument of the loop PHI that is the inital value coming
2842 from outside the loop. */
2845 initial_value_for_loop_phi (gimple phi
)
2849 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2851 edge e
= gimple_phi_arg_edge (phi
, i
);
2853 if (loop_depth (e
->src
->loop_father
)
2854 < loop_depth (e
->dest
->loop_father
))
2855 return gimple_phi_arg_def (phi
, i
);
2861 /* Detect commutative and associative scalar reductions belonging to
2862 the SCOP starting at the loop closed phi node STMT. Return the phi
2863 node of the reduction cycle, or NULL. */
2866 detect_commutative_reduction (scop_p scop
, gimple stmt
, VEC (gimple
, heap
) **in
,
2867 VEC (gimple
, heap
) **out
)
2869 if (scalar_close_phi_node_p (stmt
))
2871 tree arg
= gimple_phi_arg_def (stmt
, 0);
2872 gimple def
, loop_phi
;
2874 if (TREE_CODE (arg
) != SSA_NAME
)
2877 /* Note that loop close phi nodes should have a single argument
2878 because we translated the representation into a canonical form
2879 before Graphite: see canonicalize_loop_closed_ssa_form. */
2880 gcc_assert (gimple_phi_num_args (stmt
) == 1);
2882 def
= SSA_NAME_DEF_STMT (arg
);
2883 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
)))
2886 loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
);
2890 tree lhs
= gimple_phi_result (stmt
);
2891 tree init
= initial_value_for_loop_phi (loop_phi
);
2892 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2894 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2895 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2902 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2903 return detect_commutative_reduction_assign (stmt
, in
, out
);
2908 /* Translate the scalar reduction statement STMT to an array RED
2909 knowing that its recursive phi node is LOOP_PHI. */
2912 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2913 gimple stmt
, gimple loop_phi
)
2915 tree res
= gimple_phi_result (loop_phi
);
2916 gimple assign
= gimple_build_assign (res
, red
);
2917 gimple_stmt_iterator gsi
;
2919 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2921 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2922 gsi
= gsi_for_stmt (stmt
);
2924 insert_stmts (scop
, assign
, NULL
, gsi
);
2927 /* Removes the PHI node and resets all the debug stmts that are using
2931 remove_phi (gimple phi
)
2933 imm_use_iterator imm_iter
;
2935 use_operand_p use_p
;
2936 gimple_stmt_iterator gsi
;
2937 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2941 def
= PHI_RESULT (phi
);
2942 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2944 stmt
= USE_STMT (use_p
);
2946 if (is_gimple_debug (stmt
))
2948 gimple_debug_bind_reset_value (stmt
);
2949 VEC_safe_push (gimple
, heap
, update
, stmt
);
2953 FOR_EACH_VEC_ELT (gimple
, update
, i
, stmt
)
2956 VEC_free (gimple
, heap
, update
);
2958 gsi
= gsi_for_phi_node (phi
);
2959 remove_phi_node (&gsi
, false);
2962 /* Rewrite out of SSA the reduction described by the loop phi nodes
2963 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2966 IN: stmt, loop_n, ..., loop_0
2967 OUT: stmt, close_n, ..., close_0
2969 the first element is the reduction statement, and the next elements
2970 are the loop and close phi nodes of each of the outer loops. */
2973 translate_scalar_reduction_to_array (scop_p scop
,
2974 VEC (gimple
, heap
) *in
,
2975 VEC (gimple
, heap
) *out
)
2979 tree red
= NULL_TREE
;
2981 FOR_EACH_VEC_ELT (gimple
, in
, i
, loop_phi
)
2983 gimple close_phi
= VEC_index (gimple
, out
, i
);
2987 gimple stmt
= loop_phi
;
2988 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2989 poly_bb_p pbb
= pbb_from_bb (bb
);
2990 PBB_IS_REDUCTION (pbb
) = true;
2991 gcc_assert (close_phi
== loop_phi
);
2993 red
= create_zero_dim_array
2994 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2995 translate_scalar_reduction_to_array_for_stmt
2996 (scop
, red
, stmt
, VEC_index (gimple
, in
, 1));
3000 if (i
== VEC_length (gimple
, in
) - 1)
3002 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
), red
,
3004 insert_out_of_ssa_copy_on_edge
3005 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3006 red
, initial_value_for_loop_phi (loop_phi
));
3009 remove_phi (loop_phi
);
3010 remove_phi (close_phi
);
3014 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3015 true when something has been changed. */
3018 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3022 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
3023 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
3025 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3026 res
= VEC_length (gimple
, in
) > 0;
3028 translate_scalar_reduction_to_array (scop
, in
, out
);
3030 VEC_free (gimple
, heap
, in
);
3031 VEC_free (gimple
, heap
, out
);
3035 /* Rewrites all the commutative reductions from LOOP out of SSA.
3036 Returns true when something has been changed. */
3039 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3042 gimple_stmt_iterator gsi
;
3043 edge exit
= single_exit (loop
);
3045 bool changed
= false;
3050 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3051 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3052 && is_gimple_reg (res
)
3053 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3054 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3055 (scop
, gsi_stmt (gsi
));
3060 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3063 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3067 bool changed
= false;
3068 sese region
= SCOP_REGION (scop
);
3070 FOR_EACH_LOOP (li
, loop
, 0)
3071 if (loop_in_sese_p (loop
, region
))
3072 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3077 gsi_commit_edge_inserts ();
3078 update_ssa (TODO_update_ssa
);
3079 #ifdef ENABLE_CHECKING
3080 verify_loop_closed_ssa (true);
3085 /* Java does not initialize long_long_integer_type_node. */
3086 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
3088 /* Can all ivs be represented by a signed integer?
3089 As CLooG might generate negative values in its expressions, signed loop ivs
3090 are required in the backend. */
3093 scop_ivs_can_be_represented (scop_p scop
)
3097 gimple_stmt_iterator psi
;
3099 FOR_EACH_LOOP (li
, loop
, 0)
3101 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3104 for (psi
= gsi_start_phis (loop
->header
);
3105 !gsi_end_p (psi
); gsi_next (&psi
))
3107 gimple phi
= gsi_stmt (psi
);
3108 tree res
= PHI_RESULT (phi
);
3109 tree type
= TREE_TYPE (res
);
3111 if (TYPE_UNSIGNED (type
)
3112 && TYPE_PRECISION (type
) >= TYPE_PRECISION (my_long_long
))
3122 /* Builds the polyhedral representation for a SESE region. */
3125 build_poly_scop (scop_p scop
)
3127 sese region
= SCOP_REGION (scop
);
3128 graphite_dim_t max_dim
;
3130 build_scop_bbs (scop
);
3132 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3133 Once CLooG is fixed, remove this guard. Anyways, it makes no
3134 sense to optimize a scop containing only PBBs that do not belong
3136 if (nb_pbbs_in_loops (scop
) == 0)
3139 if (!scop_ivs_can_be_represented (scop
))
3142 build_sese_loop_nests (region
);
3143 build_sese_conditions (region
);
3144 find_scop_parameters (scop
);
3146 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3147 if (scop_nb_params (scop
) > max_dim
)
3150 build_scop_iteration_domain (scop
);
3151 build_scop_context (scop
);
3152 add_conditions_to_constraints (scop
);
3154 /* Rewrite out of SSA only after having translated the
3155 representation to the polyhedral representation to avoid scev
3156 analysis failures. That means that these functions will insert
3157 new data references that they create in the right place. */
3158 if (flag_associative_math
)
3159 rewrite_commutative_reductions_out_of_ssa (scop
);
3160 rewrite_reductions_out_of_ssa (scop
);
3161 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3163 build_scop_drs (scop
);
3165 build_scop_scattering (scop
);
3167 /* This SCoP has been translated to the polyhedral
3169 POLY_SCOP_P (scop
) = true;