1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010, 2011 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"
24 #include "tree-flow.h"
25 #include "tree-dump.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-sese-to-poly.h"
39 /* Returns the index of the PHI argument defined in the outermost
43 phi_arg_in_outermost_loop (gimple phi
)
45 loop_p loop
= gimple_bb (phi
)->loop_father
;
48 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
49 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
51 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
58 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
59 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
62 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
64 gimple phi
= gsi_stmt (*psi
);
65 tree res
= gimple_phi_result (phi
);
66 size_t entry
= phi_arg_in_outermost_loop (phi
);
67 tree init
= gimple_phi_arg_def (phi
, entry
);
68 gimple stmt
= gimple_build_assign (res
, init
);
69 edge e
= gimple_phi_arg_edge (phi
, entry
);
71 remove_phi_node (psi
, false);
72 gsi_insert_on_edge_immediate (e
, stmt
);
73 SSA_NAME_DEF_STMT (res
) = stmt
;
76 /* Removes an invariant phi node at position PSI by inserting on the
77 loop ENTRY edge the assignment RES = INIT. */
80 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
82 gimple phi
= gsi_stmt (*psi
);
83 loop_p loop
= loop_containing_stmt (phi
);
84 tree res
= gimple_phi_result (phi
);
85 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
86 size_t entry
= phi_arg_in_outermost_loop (phi
);
87 edge e
= gimple_phi_arg_edge (phi
, entry
);
90 gimple_seq stmts
= NULL
;
92 if (tree_contains_chrecs (scev
, NULL
))
93 scev
= gimple_phi_arg_def (phi
, entry
);
95 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
96 stmt
= gimple_build_assign (res
, var
);
97 remove_phi_node (psi
, false);
99 gimple_seq_add_stmt (&stmts
, stmt
);
100 gsi_insert_seq_on_edge (e
, stmts
);
101 gsi_commit_edge_inserts ();
102 SSA_NAME_DEF_STMT (res
) = stmt
;
105 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
108 simple_copy_phi_p (gimple phi
)
112 if (gimple_phi_num_args (phi
) != 2)
115 res
= gimple_phi_result (phi
);
116 return (res
== gimple_phi_arg_def (phi
, 0)
117 || res
== gimple_phi_arg_def (phi
, 1));
120 /* Returns true when the phi node at position PSI is a reduction phi
121 node in REGION. Otherwise moves the pointer PSI to the next phi to
125 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
128 gimple phi
= gsi_stmt (*psi
);
129 tree res
= gimple_phi_result (phi
);
131 loop
= loop_containing_stmt (phi
);
133 if (simple_copy_phi_p (phi
))
135 /* PRE introduces phi nodes like these, for an example,
136 see id-5.f in the fortran graphite testsuite:
138 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
140 remove_simple_copy_phi (psi
);
144 if (scev_analyzable_p (res
, region
))
146 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
148 if (evolution_function_is_invariant_p (scev
, loop
->num
))
149 remove_invariant_phi (region
, psi
);
156 /* All the other cases are considered reductions. */
160 /* Store the GRAPHITE representation of BB. */
163 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
165 struct gimple_bb
*gbb
;
167 gbb
= XNEW (struct gimple_bb
);
170 GBB_DATA_REFS (gbb
) = drs
;
171 GBB_CONDITIONS (gbb
) = NULL
;
172 GBB_CONDITION_CASES (gbb
) = NULL
;
178 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
181 struct data_reference
*dr
;
183 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
186 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
188 free (bap
->alias_set
);
197 free_gimple_bb (struct gimple_bb
*gbb
)
199 free_data_refs_aux (GBB_DATA_REFS (gbb
));
200 free_data_refs (GBB_DATA_REFS (gbb
));
202 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
203 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
204 GBB_BB (gbb
)->aux
= 0;
208 /* Deletes all gimple bbs in SCOP. */
211 remove_gbbs_in_scop (scop_p scop
)
216 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
217 free_gimple_bb (PBB_BLACK_BOX (pbb
));
220 /* Deletes all scops in SCOPS. */
223 free_scops (VEC (scop_p
, heap
) *scops
)
228 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
230 remove_gbbs_in_scop (scop
);
231 free_sese (SCOP_REGION (scop
));
235 VEC_free (scop_p
, heap
, scops
);
238 /* Same as outermost_loop_in_sese, returns the outermost loop
239 containing BB in REGION, but makes sure that the returned loop
240 belongs to the REGION, and so this returns the first loop in the
241 REGION when the loop containing BB does not belong to REGION. */
244 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
246 loop_p nest
= outermost_loop_in_sese (region
, bb
);
248 if (loop_in_sese_p (nest
, region
))
251 /* When the basic block BB does not belong to a loop in the region,
252 return the first loop in the region. */
255 if (loop_in_sese_p (nest
, region
))
264 /* Generates a polyhedral black box only if the bb contains interesting
268 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
270 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
271 sese region
= SCOP_REGION (scop
);
272 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
273 gimple_stmt_iterator gsi
;
275 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
277 gimple stmt
= gsi_stmt (gsi
);
280 if (is_gimple_debug (stmt
))
283 loop
= loop_containing_stmt (stmt
);
284 if (!loop_in_sese_p (loop
, region
))
287 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
290 return new_gimple_bb (bb
, drs
);
293 /* Returns true if all predecessors of BB, that are not dominated by BB, are
294 marked in MAP. The predecessors dominated by BB are loop latches and will
295 be handled after BB. */
298 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
303 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
304 if (!TEST_BIT (map
, e
->src
->index
)
305 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
311 /* Compare the depth of two basic_block's P1 and P2. */
314 compare_bb_depths (const void *p1
, const void *p2
)
316 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
317 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
318 int d1
= loop_depth (bb1
->loop_father
);
319 int d2
= loop_depth (bb2
->loop_father
);
330 /* Sort the basic blocks from DOM such that the first are the ones at
331 a deepest loop level. */
334 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
336 VEC_qsort (basic_block
, dom
, compare_bb_depths
);
339 /* Recursive helper function for build_scops_bbs. */
342 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
344 sese region
= SCOP_REGION (scop
);
345 VEC (basic_block
, heap
) *dom
;
348 if (TEST_BIT (visited
, bb
->index
)
349 || !bb_in_sese_p (bb
, region
))
352 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
353 VEC_safe_push (poly_bb_p
, heap
, SCOP_BBS (scop
), pbb
);
354 SET_BIT (visited
, bb
->index
);
356 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
361 graphite_sort_dominated_info (dom
);
363 while (!VEC_empty (basic_block
, dom
))
368 FOR_EACH_VEC_ELT (basic_block
, dom
, i
, dom_bb
)
369 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
371 build_scop_bbs_1 (scop
, visited
, dom_bb
);
372 VEC_unordered_remove (basic_block
, dom
, i
);
377 VEC_free (basic_block
, heap
, dom
);
380 /* Gather the basic blocks belonging to the SCOP. */
383 build_scop_bbs (scop_p scop
)
385 sbitmap visited
= sbitmap_alloc (last_basic_block
);
386 sese region
= SCOP_REGION (scop
);
388 sbitmap_zero (visited
);
389 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
390 sbitmap_free (visited
);
393 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
394 We generate SCATTERING_DIMENSIONS scattering dimensions.
396 CLooG 0.15.0 and previous versions require, that all
397 scattering functions of one CloogProgram have the same number of
398 scattering dimensions, therefore we allow to specify it. This
399 should be removed in future versions of CLooG.
401 The scattering polyhedron consists of these dimensions: scattering,
402 loop_iterators, parameters.
406 | scattering_dimensions = 5
407 | used_scattering_dimensions = 3
415 | Scattering polyhedron:
417 | scattering: {s1, s2, s3, s4, s5}
418 | loop_iterators: {i}
419 | parameters: {p1, p2}
421 | s1 s2 s3 s4 s5 i p1 p2 1
422 | 1 0 0 0 0 0 0 0 -4 = 0
423 | 0 1 0 0 0 -1 0 0 0 = 0
424 | 0 0 1 0 0 0 0 0 -5 = 0 */
427 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
428 poly_bb_p pbb
, int scattering_dimensions
)
431 scop_p scop
= PBB_SCOP (pbb
);
432 int nb_iterators
= pbb_dim_iter_domain (pbb
);
433 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
434 int nb_params
= scop_nb_params (scop
);
436 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
439 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
442 ppl_new_Coefficient (&c
);
443 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
444 ppl_new_C_Polyhedron_from_space_dimension
445 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
447 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
449 for (i
= 0; i
< scattering_dimensions
; i
++)
451 ppl_Constraint_t cstr
;
452 ppl_Linear_Expression_t expr
;
454 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
456 ppl_assign_Coefficient_from_mpz_t (c
, v
);
457 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
459 /* Textual order inside this loop. */
462 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
463 ppl_Coefficient_to_mpz_t (c
, v
);
465 ppl_assign_Coefficient_from_mpz_t (c
, v
);
466 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
469 /* Iterations of this loop. */
470 else /* if ((i % 2) == 1) */
472 int loop
= (i
- 1) / 2;
475 ppl_assign_Coefficient_from_mpz_t (c
, v
);
476 ppl_Linear_Expression_add_to_coefficient
477 (expr
, scattering_dimensions
+ loop
, c
);
480 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
481 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
482 ppl_delete_Linear_Expression (expr
);
483 ppl_delete_Constraint (cstr
);
487 ppl_delete_Coefficient (c
);
489 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
492 /* Build for BB the static schedule.
494 The static schedule is a Dewey numbering of the abstract syntax
495 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
497 The following example informally defines the static schedule:
516 Static schedules for A to F:
529 build_scop_scattering (scop_p scop
)
533 gimple_bb_p previous_gbb
= NULL
;
534 ppl_Linear_Expression_t static_schedule
;
539 ppl_new_Coefficient (&c
);
540 ppl_new_Linear_Expression (&static_schedule
);
542 /* We have to start schedules at 0 on the first component and
543 because we cannot compare_prefix_loops against a previous loop,
544 prefix will be equal to zero, and that index will be
545 incremented before copying. */
547 ppl_assign_Coefficient_from_mpz_t (c
, v
);
548 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
550 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
552 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
553 ppl_Linear_Expression_t common
;
555 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
558 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
563 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
564 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
568 ppl_assign_Coefficient_from_mpz_t (c
, v
);
569 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
570 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
573 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
575 ppl_delete_Linear_Expression (common
);
579 ppl_delete_Coefficient (c
);
580 ppl_delete_Linear_Expression (static_schedule
);
583 /* Add the value K to the dimension D of the linear expression EXPR. */
586 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
590 ppl_Coefficient_t coef
;
592 ppl_new_Coefficient (&coef
);
593 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
595 ppl_Coefficient_to_mpz_t (coef
, val
);
597 mpz_add (val
, val
, k
);
599 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
600 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
602 ppl_delete_Coefficient (coef
);
605 /* In the context of scop S, scan E, the right hand side of a scalar
606 evolution function in loop VAR, and translate it to a linear
610 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
611 ppl_Linear_Expression_t expr
)
615 loop_p loop
= get_loop (var
);
616 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
619 /* Scalar evolutions should happen in the sese region. */
620 gcc_assert (sese_loop_depth (s
, loop
) > 0);
622 /* We can not deal with parametric strides like:
628 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
631 tree_int_to_gmp (e
, val
);
632 add_value_to_dim (l
, expr
, val
);
637 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
638 linear expression EXPR. K is the multiplier of the constant. */
641 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, mpz_t k
)
644 ppl_Coefficient_t coef
;
645 tree type
= TREE_TYPE (cst
);
649 /* Necessary to not get "-1 = 2^n - 1". */
650 mpz_set_double_int (val
, double_int_sext (tree_to_double_int (cst
),
651 TYPE_PRECISION (type
)), false);
653 mpz_mul (val
, val
, k
);
654 ppl_new_Coefficient (&coef
);
655 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
656 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
658 ppl_delete_Coefficient (coef
);
661 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
662 Otherwise returns -1. */
665 parameter_index_in_region_1 (tree name
, sese region
)
670 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
672 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (region
), i
, p
)
679 /* When the parameter NAME is in REGION, returns its index in
680 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
681 and returns the index of NAME. */
684 parameter_index_in_region (tree name
, sese region
)
688 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
690 i
= parameter_index_in_region_1 (name
, region
);
694 gcc_assert (SESE_ADD_PARAMS (region
));
696 i
= VEC_length (tree
, SESE_PARAMS (region
));
697 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
701 /* In the context of sese S, scan the expression E and translate it to
702 a linear expression C. When parsing a symbolic multiplication, K
703 represents the constant multiplier of an expression containing
707 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
710 if (e
== chrec_dont_know
)
713 switch (TREE_CODE (e
))
715 case POLYNOMIAL_CHREC
:
716 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
717 CHREC_VARIABLE (e
), c
);
718 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
722 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
727 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
729 tree_int_to_gmp (TREE_OPERAND (e
, 1), val
);
730 mpz_mul (val
, val
, k
);
731 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
735 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
742 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
744 tree_int_to_gmp (TREE_OPERAND (e
, 0), val
);
745 mpz_mul (val
, val
, k
);
746 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
750 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
755 case POINTER_PLUS_EXPR
:
756 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
757 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
762 ppl_Linear_Expression_t tmp_expr
= NULL
;
766 ppl_dimension_type dim
;
767 ppl_Linear_Expression_space_dimension (c
, &dim
);
768 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
771 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
772 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
776 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
778 ppl_delete_Linear_Expression (tmp_expr
);
786 ppl_Linear_Expression_t tmp_expr
= NULL
;
790 ppl_dimension_type dim
;
791 ppl_Linear_Expression_space_dimension (c
, &dim
);
792 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
795 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
799 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
801 ppl_delete_Linear_Expression (tmp_expr
);
809 ppl_Linear_Expression_t tmp_expr
= NULL
;
813 ppl_dimension_type dim
;
814 ppl_Linear_Expression_space_dimension (c
, &dim
);
815 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
818 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
822 ppl_Coefficient_t coef
;
825 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
827 ppl_delete_Linear_Expression (tmp_expr
);
828 mpz_init (minus_one
);
829 mpz_set_si (minus_one
, -1);
830 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
831 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
832 mpz_clear (minus_one
);
833 ppl_delete_Coefficient (coef
);
841 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
845 ppl_dimension_type dim
;
846 ppl_Linear_Expression_space_dimension (c
, &dim
);
847 p
+= dim
- sese_nb_params (s
);
848 add_value_to_dim (p
, c
, k
);
855 scan_tree_for_params_int (e
, c
, k
);
859 case NON_LVALUE_EXPR
:
860 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
872 /* Find parameters with respect to REGION in BB. We are looking in memory
873 access functions, conditions and loop bounds. */
876 find_params_in_bb (sese region
, gimple_bb_p gbb
)
882 loop_p loop
= GBB_BB (gbb
)->loop_father
;
888 /* Find parameters in the access functions of data references. */
889 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
890 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
891 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
893 /* Find parameters in conditional statements. */
894 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
896 tree lhs
= scalar_evolution_in_region (region
, loop
,
897 gimple_cond_lhs (stmt
));
898 tree rhs
= scalar_evolution_in_region (region
, loop
,
899 gimple_cond_rhs (stmt
));
901 scan_tree_for_params (region
, lhs
, NULL
, one
);
902 scan_tree_for_params (region
, rhs
, NULL
, one
);
908 /* Record the parameters used in the SCOP. A variable is a parameter
909 in a scop if it does not vary during the execution of that scop. */
912 find_scop_parameters (scop_p scop
)
916 sese region
= SCOP_REGION (scop
);
923 /* Find the parameters used in the loop bounds. */
924 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
926 tree nb_iters
= number_of_latch_executions (loop
);
928 if (!chrec_contains_symbols (nb_iters
))
931 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
932 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
937 /* Find the parameters used in data accesses. */
938 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
939 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
941 scop_set_nb_params (scop
, sese_nb_params (region
));
942 SESE_ADD_PARAMS (region
) = false;
944 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
945 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
948 /* Insert in the SCOP context constraints from the estimation of the
949 number of iterations. UB_EXPR is a linear expression describing
950 the number of iterations in a loop. This expression is bounded by
951 the estimation NIT. */
954 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
955 ppl_dimension_type dim
,
956 ppl_Linear_Expression_t ub_expr
)
959 ppl_Linear_Expression_t nb_iters_le
;
960 ppl_Polyhedron_t pol
;
961 ppl_Coefficient_t coef
;
964 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
965 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
968 /* Construct the negated number of last iteration in VAL. */
970 mpz_set_double_int (val
, nit
, false);
971 mpz_sub_ui (val
, val
, 1);
974 /* NB_ITERS_LE holds the number of last iteration in
975 parametrical form. Subtract estimated number of last
976 iteration and assert that result is not positive. */
977 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
978 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
979 ppl_delete_Coefficient (coef
);
980 ppl_new_Constraint (&ub
, nb_iters_le
,
981 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
982 ppl_Polyhedron_add_constraint (pol
, ub
);
984 /* Remove all but last GDIM dimensions from POL to obtain
985 only the constraints on the parameters. */
987 graphite_dim_t gdim
= scop_nb_params (scop
);
988 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
991 for (i
= 0; i
< dim
- gdim
; i
++)
994 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
998 /* Add the constraints on the parameters to the SCoP context. */
1000 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1002 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1003 (&constraints_ps
, pol
);
1004 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1005 (SCOP_CONTEXT (scop
), constraints_ps
);
1006 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1009 ppl_delete_Polyhedron (pol
);
1010 ppl_delete_Linear_Expression (nb_iters_le
);
1011 ppl_delete_Constraint (ub
);
1015 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1016 the constraints for the surrounding loops. */
1019 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1020 ppl_Polyhedron_t outer_ph
, int nb
,
1021 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1024 ppl_Polyhedron_t ph
;
1025 tree nb_iters
= number_of_latch_executions (loop
);
1026 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1027 sese region
= SCOP_REGION (scop
);
1030 ppl_const_Constraint_System_t pcs
;
1031 ppl_dimension_type
*map
1032 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1034 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1035 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1036 ppl_Polyhedron_add_constraints (ph
, pcs
);
1038 for (i
= 0; i
< (int) nb
; i
++)
1040 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1044 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1050 ppl_Constraint_t lb
;
1051 ppl_Linear_Expression_t lb_expr
;
1053 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1054 ppl_set_coef (lb_expr
, nb
, 1);
1055 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1056 ppl_delete_Linear_Expression (lb_expr
);
1057 ppl_Polyhedron_add_constraint (ph
, lb
);
1058 ppl_delete_Constraint (lb
);
1061 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1063 ppl_Constraint_t ub
;
1064 ppl_Linear_Expression_t ub_expr
;
1066 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1068 /* loop_i <= cst_nb_iters */
1069 ppl_set_coef (ub_expr
, nb
, -1);
1070 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1071 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1072 ppl_Polyhedron_add_constraint (ph
, ub
);
1073 ppl_delete_Linear_Expression (ub_expr
);
1074 ppl_delete_Constraint (ub
);
1076 else if (!chrec_contains_undetermined (nb_iters
))
1079 ppl_Constraint_t ub
;
1080 ppl_Linear_Expression_t ub_expr
;
1084 mpz_set_si (one
, 1);
1085 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1086 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1087 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1090 if (max_stmt_executions (loop
, &nit
))
1091 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1093 /* loop_i <= expr_nb_iters */
1094 ppl_set_coef (ub_expr
, nb
, -1);
1095 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1096 ppl_Polyhedron_add_constraint (ph
, ub
);
1097 ppl_delete_Linear_Expression (ub_expr
);
1098 ppl_delete_Constraint (ub
);
1103 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1104 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1108 && loop_in_sese_p (loop
->next
, region
))
1109 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1111 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1112 (&domains
[loop
->num
], ph
);
1114 ppl_delete_Polyhedron (ph
);
1117 /* Returns a linear expression for tree T evaluated in PBB. */
1119 static ppl_Linear_Expression_t
1120 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1123 ppl_Linear_Expression_t res
;
1124 ppl_dimension_type dim
;
1125 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1126 loop_p loop
= pbb_loop (pbb
);
1128 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1129 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1131 t
= scalar_evolution_in_region (region
, loop
, t
);
1132 gcc_assert (!automatically_generated_chrec_p (t
));
1135 mpz_set_si (one
, 1);
1136 scan_tree_for_params (region
, t
, res
, one
);
1142 /* Returns the ppl constraint type from the gimple tree code CODE. */
1144 static enum ppl_enum_Constraint_Type
1145 ppl_constraint_type_from_tree_code (enum tree_code code
)
1149 /* We do not support LT and GT to be able to work with C_Polyhedron.
1150 As we work on integer polyhedron "a < b" can be expressed by
1157 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1160 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1163 return PPL_CONSTRAINT_TYPE_EQUAL
;
1170 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1171 CODE is used as the comparison operator. This allows us to invert the
1172 condition or to handle inequalities. */
1175 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1176 poly_bb_p pbb
, enum tree_code code
)
1179 ppl_Coefficient_t c
;
1180 ppl_Linear_Expression_t left
, right
;
1181 ppl_Constraint_t cstr
;
1182 enum ppl_enum_Constraint_Type type
;
1184 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1185 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1187 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1188 the left or the right side of the expression. */
1189 if (code
== LT_EXPR
)
1193 ppl_new_Coefficient (&c
);
1194 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1195 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1196 ppl_delete_Coefficient (c
);
1201 else if (code
== GT_EXPR
)
1205 ppl_new_Coefficient (&c
);
1206 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1207 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1208 ppl_delete_Coefficient (c
);
1214 type
= ppl_constraint_type_from_tree_code (code
);
1216 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1218 ppl_new_Constraint (&cstr
, left
, type
);
1219 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1221 ppl_delete_Constraint (cstr
);
1222 ppl_delete_Linear_Expression (left
);
1223 ppl_delete_Linear_Expression (right
);
1226 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1227 operator. This allows us to invert the condition or to handle
1231 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1233 if (code
== NE_EXPR
)
1235 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1236 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1237 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1239 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1240 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1241 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
, right
);
1242 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1245 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1248 /* Add conditions to the domain of PBB. */
1251 add_conditions_to_domain (poly_bb_p pbb
)
1255 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1257 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1260 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
1261 switch (gimple_code (stmt
))
1265 enum tree_code code
= gimple_cond_code (stmt
);
1267 /* The conditions for ELSE-branches are inverted. */
1268 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1269 code
= invert_tree_comparison (code
, false);
1271 add_condition_to_pbb (pbb
, stmt
, code
);
1276 /* Switch statements are not supported right now - fall throught. */
1284 /* Traverses all the GBBs of the SCOP and add their constraints to the
1285 iteration domains. */
1288 add_conditions_to_constraints (scop_p scop
)
1293 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1294 add_conditions_to_domain (pbb
);
1297 /* Structure used to pass data to dom_walk. */
1301 VEC (gimple
, heap
) **conditions
, **cases
;
1305 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1306 edge between BB and its predecessor is not a loop exit edge, and
1307 the last statement of the single predecessor is a COND_EXPR. */
1310 single_pred_cond_non_loop_exit (basic_block bb
)
1312 if (single_pred_p (bb
))
1314 edge e
= single_pred_edge (bb
);
1315 basic_block pred
= e
->src
;
1318 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1321 stmt
= last_stmt (pred
);
1323 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1330 /* Call-back for dom_walk executed before visiting the dominated
1334 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1337 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1338 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1339 VEC (gimple
, heap
) **cases
= data
->cases
;
1343 if (!bb_in_sese_p (bb
, data
->region
))
1346 stmt
= single_pred_cond_non_loop_exit (bb
);
1350 edge e
= single_pred_edge (bb
);
1352 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1354 if (e
->flags
& EDGE_TRUE_VALUE
)
1355 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1357 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1360 gbb
= gbb_from_bb (bb
);
1364 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1365 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1369 /* Call-back for dom_walk executed after visiting the dominated
1373 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1376 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1377 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1378 VEC (gimple
, heap
) **cases
= data
->cases
;
1380 if (!bb_in_sese_p (bb
, data
->region
))
1383 if (single_pred_cond_non_loop_exit (bb
))
1385 VEC_pop (gimple
, *conditions
);
1386 VEC_pop (gimple
, *cases
);
1390 /* Record all conditions in REGION. */
1393 build_sese_conditions (sese region
)
1395 struct dom_walk_data walk_data
;
1396 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1397 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1400 data
.conditions
= &conditions
;
1401 data
.cases
= &cases
;
1402 data
.region
= region
;
1404 walk_data
.dom_direction
= CDI_DOMINATORS
;
1405 walk_data
.initialize_block_local_data
= NULL
;
1406 walk_data
.before_dom_children
= build_sese_conditions_before
;
1407 walk_data
.after_dom_children
= build_sese_conditions_after
;
1408 walk_data
.global_data
= &data
;
1409 walk_data
.block_local_data_size
= 0;
1411 init_walk_dominator_tree (&walk_data
);
1412 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1413 fini_walk_dominator_tree (&walk_data
);
1415 VEC_free (gimple
, heap
, conditions
);
1416 VEC_free (gimple
, heap
, cases
);
1419 /* Add constraints on the possible values of parameter P from the type
1423 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1425 ppl_Constraint_t cstr
;
1426 ppl_Linear_Expression_t le
;
1427 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1428 tree type
= TREE_TYPE (parameter
);
1429 tree lb
= NULL_TREE
;
1430 tree ub
= NULL_TREE
;
1432 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1433 lb
= lower_bound_in_type (type
, type
);
1435 lb
= TYPE_MIN_VALUE (type
);
1437 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1438 ub
= upper_bound_in_type (type
, type
);
1440 ub
= TYPE_MAX_VALUE (type
);
1444 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1445 ppl_set_coef (le
, p
, -1);
1446 ppl_set_inhomogeneous_tree (le
, lb
);
1447 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1448 ppl_Polyhedron_add_constraint (context
, cstr
);
1449 ppl_delete_Linear_Expression (le
);
1450 ppl_delete_Constraint (cstr
);
1455 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1456 ppl_set_coef (le
, p
, -1);
1457 ppl_set_inhomogeneous_tree (le
, ub
);
1458 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1459 ppl_Polyhedron_add_constraint (context
, cstr
);
1460 ppl_delete_Linear_Expression (le
);
1461 ppl_delete_Constraint (cstr
);
1465 /* Build the context of the SCOP. The context usually contains extra
1466 constraints that are added to the iteration domains that constrain
1470 build_scop_context (scop_p scop
)
1472 ppl_Polyhedron_t context
;
1473 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1474 graphite_dim_t p
, n
= scop_nb_params (scop
);
1476 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1478 for (p
= 0; p
< n
; p
++)
1479 add_param_constraints (scop
, context
, p
);
1481 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1483 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1484 (SCOP_CONTEXT (scop
), ps
);
1486 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1487 ppl_delete_Polyhedron (context
);
1490 /* Build the iteration domains: the loops belonging to the current
1491 SCOP, and that vary for the execution of the current basic block.
1492 Returns false if there is no loop in SCOP. */
1495 build_scop_iteration_domain (scop_p scop
)
1498 sese region
= SCOP_REGION (scop
);
1500 ppl_Polyhedron_t ph
;
1502 int nb_loops
= number_of_loops ();
1503 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1504 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1506 for (i
= 0; i
< nb_loops
; i
++)
1509 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1511 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
1512 if (!loop_in_sese_p (loop_outer (loop
), region
))
1513 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1515 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1516 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1517 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1518 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1519 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1521 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1522 (&PBB_DOMAIN (pbb
), ph
);
1524 for (i
= 0; i
< nb_loops
; i
++)
1526 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1528 ppl_delete_Polyhedron (ph
);
1532 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1533 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1534 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1538 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1539 ppl_dimension_type accessp_nb_dims
,
1540 ppl_dimension_type dom_nb_dims
)
1542 ppl_Linear_Expression_t alias
;
1543 ppl_Constraint_t cstr
;
1544 int alias_set_num
= 0;
1545 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1547 if (bap
&& bap
->alias_set
)
1548 alias_set_num
= *(bap
->alias_set
);
1550 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1552 ppl_set_coef (alias
, dom_nb_dims
, 1);
1553 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1554 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1555 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1557 ppl_delete_Linear_Expression (alias
);
1558 ppl_delete_Constraint (cstr
);
1561 /* Add to ACCESSES polyhedron equalities defining the access functions
1562 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1563 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1564 PBB is the poly_bb_p that contains the data reference DR. */
1567 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1568 ppl_dimension_type accessp_nb_dims
,
1569 ppl_dimension_type dom_nb_dims
,
1572 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1574 scop_p scop
= PBB_SCOP (pbb
);
1575 sese region
= SCOP_REGION (scop
);
1579 for (i
= 0; i
< nb_subscripts
; i
++)
1581 ppl_Linear_Expression_t fn
, access
;
1582 ppl_Constraint_t cstr
;
1583 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1584 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1586 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1587 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1590 scan_tree_for_params (region
, afn
, fn
, v
);
1591 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1593 ppl_set_coef (access
, subscript
, -1);
1594 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1595 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1597 ppl_delete_Linear_Expression (fn
);
1598 ppl_delete_Linear_Expression (access
);
1599 ppl_delete_Constraint (cstr
);
1605 /* Add constrains representing the size of the accessed data to the
1606 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1607 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1611 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1612 ppl_dimension_type accessp_nb_dims
,
1613 ppl_dimension_type dom_nb_dims
)
1615 tree ref
= DR_REF (dr
);
1616 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1618 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1620 ppl_Linear_Expression_t expr
;
1621 ppl_Constraint_t cstr
;
1622 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1625 if (TREE_CODE (ref
) != ARRAY_REF
)
1628 low
= array_ref_low_bound (ref
);
1630 /* subscript - low >= 0 */
1631 if (host_integerp (low
, 0))
1635 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1636 ppl_set_coef (expr
, subscript
, 1);
1638 minus_low
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (low
), low
);
1639 ppl_set_inhomogeneous_tree (expr
, minus_low
);
1641 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1642 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1643 ppl_delete_Linear_Expression (expr
);
1644 ppl_delete_Constraint (cstr
);
1647 high
= array_ref_up_bound (ref
);
1649 /* high - subscript >= 0 */
1650 if (high
&& host_integerp (high
, 0)
1651 /* 1-element arrays at end of structures may extend over
1652 their declared size. */
1653 && !(array_at_struct_end_p (ref
)
1654 && operand_equal_p (low
, high
, 0)))
1656 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1657 ppl_set_coef (expr
, subscript
, -1);
1659 ppl_set_inhomogeneous_tree (expr
, high
);
1661 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1662 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1663 ppl_delete_Linear_Expression (expr
);
1664 ppl_delete_Constraint (cstr
);
1669 /* Build data accesses for DR in PBB. */
1672 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1674 ppl_Polyhedron_t accesses
;
1675 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1676 ppl_dimension_type dom_nb_dims
;
1677 ppl_dimension_type accessp_nb_dims
;
1678 int dr_base_object_set
;
1680 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1682 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1684 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1686 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1687 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1688 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1690 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1692 ppl_delete_Polyhedron (accesses
);
1694 gcc_assert (dr
->aux
);
1695 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1697 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
,
1698 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1699 dr
, DR_NUM_DIMENSIONS (dr
));
1702 /* Write to FILE the alias graph of data references in DIMACS format. */
1705 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1706 VEC (data_reference_p
, heap
) *drs
)
1708 int num_vertex
= VEC_length (data_reference_p
, drs
);
1710 data_reference_p dr1
, dr2
;
1713 if (num_vertex
== 0)
1716 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1717 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1718 if (dr_may_alias_p (dr1
, dr2
, true))
1721 fprintf (file
, "$\n");
1724 fprintf (file
, "c %s\n", comment
);
1726 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1728 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1729 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1730 if (dr_may_alias_p (dr1
, dr2
, true))
1731 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1736 /* Write to FILE the alias graph of data references in DOT format. */
1739 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1740 VEC (data_reference_p
, heap
) *drs
)
1742 int num_vertex
= VEC_length (data_reference_p
, drs
);
1743 data_reference_p dr1
, dr2
;
1746 if (num_vertex
== 0)
1749 fprintf (file
, "$\n");
1752 fprintf (file
, "c %s\n", comment
);
1754 /* First print all the vertices. */
1755 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1756 fprintf (file
, "n%d;\n", i
);
1758 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1759 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1760 if (dr_may_alias_p (dr1
, dr2
, true))
1761 fprintf (file
, "n%d n%d\n", i
, j
);
1766 /* Write to FILE the alias graph of data references in ECC format. */
1769 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1770 VEC (data_reference_p
, heap
) *drs
)
1772 int num_vertex
= VEC_length (data_reference_p
, drs
);
1773 data_reference_p dr1
, dr2
;
1776 if (num_vertex
== 0)
1779 fprintf (file
, "$\n");
1782 fprintf (file
, "c %s\n", comment
);
1784 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1785 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1786 if (dr_may_alias_p (dr1
, dr2
, true))
1787 fprintf (file
, "%d %d\n", i
, j
);
1792 /* Check if DR1 and DR2 are in the same object set. */
1795 dr_same_base_object_p (const struct data_reference
*dr1
,
1796 const struct data_reference
*dr2
)
1798 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1801 /* Uses DFS component number as representative of alias-sets. Also tests for
1802 optimality by verifying if every connected component is a clique. Returns
1803 true (1) if the above test is true, and false (0) otherwise. */
1806 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1808 int num_vertices
= VEC_length (data_reference_p
, drs
);
1809 struct graph
*g
= new_graph (num_vertices
);
1810 data_reference_p dr1
, dr2
;
1812 int num_connected_components
;
1813 int v_indx1
, v_indx2
, num_vertices_in_component
;
1816 struct graph_edge
*e
;
1817 int this_component_is_clique
;
1818 int all_components_are_cliques
= 1;
1820 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1821 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1822 if (dr_may_alias_p (dr1
, dr2
, true))
1828 all_vertices
= XNEWVEC (int, num_vertices
);
1829 vertices
= XNEWVEC (int, num_vertices
);
1830 for (i
= 0; i
< num_vertices
; i
++)
1831 all_vertices
[i
] = i
;
1833 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1835 for (i
= 0; i
< g
->n_vertices
; i
++)
1837 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1838 base_alias_pair
*bap
;
1840 gcc_assert (dr
->aux
);
1841 bap
= (base_alias_pair
*)(dr
->aux
);
1843 bap
->alias_set
= XNEW (int);
1844 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1847 /* Verify if the DFS numbering results in optimal solution. */
1848 for (i
= 0; i
< num_connected_components
; i
++)
1850 num_vertices_in_component
= 0;
1851 /* Get all vertices whose DFS component number is the same as i. */
1852 for (j
= 0; j
< num_vertices
; j
++)
1853 if (g
->vertices
[j
].component
== i
)
1854 vertices
[num_vertices_in_component
++] = j
;
1856 /* Now test if the vertices in 'vertices' form a clique, by testing
1857 for edges among each pair. */
1858 this_component_is_clique
= 1;
1859 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1861 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1863 /* Check if the two vertices are connected by iterating
1864 through all the edges which have one of these are source. */
1865 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1868 if (e
->src
== vertices
[v_indx1
])
1874 this_component_is_clique
= 0;
1878 if (!this_component_is_clique
)
1879 all_components_are_cliques
= 0;
1883 free (all_vertices
);
1886 return all_components_are_cliques
;
1889 /* Group each data reference in DRS with its base object set num. */
1892 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1894 int num_vertex
= VEC_length (data_reference_p
, drs
);
1895 struct graph
*g
= new_graph (num_vertex
);
1896 data_reference_p dr1
, dr2
;
1900 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1901 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1902 if (dr_same_base_object_p (dr1
, dr2
))
1908 queue
= XNEWVEC (int, num_vertex
);
1909 for (i
= 0; i
< num_vertex
; i
++)
1912 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1914 for (i
= 0; i
< g
->n_vertices
; i
++)
1916 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1917 base_alias_pair
*bap
;
1919 gcc_assert (dr
->aux
);
1920 bap
= (base_alias_pair
*)(dr
->aux
);
1922 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1929 /* Build the data references for PBB. */
1932 build_pbb_drs (poly_bb_p pbb
)
1935 data_reference_p dr
;
1936 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1938 FOR_EACH_VEC_ELT (data_reference_p
, gbb_drs
, j
, dr
)
1939 build_poly_dr (dr
, pbb
);
1942 /* Dump to file the alias graphs for the data references in DRS. */
1945 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
1948 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1950 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1953 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1954 current_function_name ());
1955 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1956 fclose (file_dimacs
);
1959 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1962 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1963 current_function_name ());
1964 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1968 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1971 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1972 current_function_name ());
1973 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1978 /* Build data references in SCOP. */
1981 build_scop_drs (scop_p scop
)
1985 data_reference_p dr
;
1986 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1988 /* Remove all the PBBs that do not have data references: these basic
1989 blocks are not handled in the polyhedral representation. */
1990 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1991 if (VEC_empty (data_reference_p
, GBB_DATA_REFS (PBB_BLACK_BOX (pbb
))))
1993 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1994 VEC_ordered_remove (poly_bb_p
, SCOP_BBS (scop
), i
);
1998 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1999 for (j
= 0; VEC_iterate (data_reference_p
,
2000 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2001 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2003 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr
)
2004 dr
->aux
= XNEW (base_alias_pair
);
2006 if (!build_alias_set_optimal_p (drs
))
2008 /* TODO: Add support when building alias set is not optimal. */
2012 build_base_obj_set_for_drs (drs
);
2014 /* When debugging, enable the following code. This cannot be used
2015 in production compilers. */
2017 dump_alias_graphs (drs
);
2019 VEC_free (data_reference_p
, heap
, drs
);
2021 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2022 build_pbb_drs (pbb
);
2025 /* Return a gsi at the position of the phi node STMT. */
2027 static gimple_stmt_iterator
2028 gsi_for_phi_node (gimple stmt
)
2030 gimple_stmt_iterator psi
;
2031 basic_block bb
= gimple_bb (stmt
);
2033 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2034 if (stmt
== gsi_stmt (psi
))
2041 /* Analyze all the data references of STMTS and add them to the
2042 GBB_DATA_REFS vector of BB. */
2045 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, VEC (gimple
, heap
) *stmts
)
2051 sese region
= SCOP_REGION (scop
);
2053 if (!bb_in_sese_p (bb
, region
))
2056 nest
= outermost_loop_in_sese_1 (region
, bb
);
2057 gbb
= gbb_from_bb (bb
);
2059 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, stmt
)
2063 if (is_gimple_debug (stmt
))
2066 loop
= loop_containing_stmt (stmt
);
2067 if (!loop_in_sese_p (loop
, region
))
2070 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
2071 &GBB_DATA_REFS (gbb
));
2075 /* Insert STMT at the end of the STMTS sequence and then insert the
2076 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2080 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
2081 gimple_stmt_iterator insert_gsi
)
2083 gimple_stmt_iterator gsi
;
2084 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2086 gimple_seq_add_stmt (&stmts
, stmt
);
2087 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2088 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2090 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2091 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2092 VEC_free (gimple
, heap
, x
);
2095 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2098 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2101 gimple_stmt_iterator gsi
;
2102 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2103 gimple stmt
= gimple_build_assign (res
, var
);
2104 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2106 gimple_seq_add_stmt (&stmts
, stmt
);
2107 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2108 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2110 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2112 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2113 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2117 gsi
= gsi_for_stmt (after_stmt
);
2118 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2121 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2122 VEC_free (gimple
, heap
, x
);
2125 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2128 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2130 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2131 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2132 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2133 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2134 int index
, n
= VEC_length (poly_bb_p
, SCOP_BBS (scop
));
2136 /* The INDEX of PBB in SCOP_BBS. */
2137 for (index
= 0; index
< n
; index
++)
2138 if (VEC_index (poly_bb_p
, SCOP_BBS (scop
), index
) == pbb
)
2141 if (PBB_DOMAIN (pbb
))
2142 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2143 (&PBB_DOMAIN (pbb1
), PBB_DOMAIN (pbb
));
2145 GBB_PBB (gbb1
) = pbb1
;
2146 GBB_CONDITIONS (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITIONS (gbb
));
2147 GBB_CONDITION_CASES (gbb1
) = VEC_copy (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
2148 VEC_safe_insert (poly_bb_p
, heap
, SCOP_BBS (scop
), index
+ 1, pbb1
);
2151 /* Insert on edge E the assignment "RES := EXPR". */
2154 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2156 gimple_stmt_iterator gsi
;
2157 gimple_seq stmts
= NULL
;
2158 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2159 gimple stmt
= gimple_build_assign (res
, var
);
2161 VEC (gimple
, heap
) *x
= VEC_alloc (gimple
, heap
, 3);
2163 gimple_seq_add_stmt (&stmts
, stmt
);
2164 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2165 VEC_safe_push (gimple
, heap
, x
, gsi_stmt (gsi
));
2167 gsi_insert_seq_on_edge (e
, stmts
);
2168 gsi_commit_edge_inserts ();
2169 bb
= gimple_bb (stmt
);
2171 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2174 if (!gbb_from_bb (bb
))
2175 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2177 analyze_drs_in_stmts (scop
, bb
, x
);
2178 VEC_free (gimple
, heap
, x
);
2181 /* Creates a zero dimension array of the same type as VAR. */
2184 create_zero_dim_array (tree var
, const char *base_name
)
2186 tree index_type
= build_index_type (integer_zero_node
);
2187 tree elt_type
= TREE_TYPE (var
);
2188 tree array_type
= build_array_type (elt_type
, index_type
);
2189 tree base
= create_tmp_var (array_type
, base_name
);
2191 add_referenced_var (base
);
2193 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2197 /* Returns true when PHI is a loop close phi node. */
2200 scalar_close_phi_node_p (gimple phi
)
2202 if (gimple_code (phi
) != GIMPLE_PHI
2203 || !is_gimple_reg (gimple_phi_result (phi
)))
2206 /* Note that loop close phi nodes should have a single argument
2207 because we translated the representation into a canonical form
2208 before Graphite: see canonicalize_loop_closed_ssa_form. */
2209 return (gimple_phi_num_args (phi
) == 1);
2212 /* For a definition DEF in REGION, propagates the expression EXPR in
2213 all the uses of DEF outside REGION. */
2216 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2218 imm_use_iterator imm_iter
;
2221 bool replaced_once
= false;
2223 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2225 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2228 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2229 if (!is_gimple_debug (use_stmt
)
2230 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2233 use_operand_p use_p
;
2235 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2236 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2237 && (replaced_once
= true))
2238 replace_exp (use_p
, expr
);
2240 update_stmt (use_stmt
);
2245 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2246 gsi_commit_edge_inserts ();
2250 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2251 dimension array for it. */
2254 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2256 sese region
= SCOP_REGION (scop
);
2257 gimple phi
= gsi_stmt (*psi
);
2258 tree res
= gimple_phi_result (phi
);
2259 tree var
= SSA_NAME_VAR (res
);
2260 basic_block bb
= gimple_bb (phi
);
2261 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2262 tree arg
= gimple_phi_arg_def (phi
, 0);
2265 /* Note that loop close phi nodes should have a single argument
2266 because we translated the representation into a canonical form
2267 before Graphite: see canonicalize_loop_closed_ssa_form. */
2268 gcc_assert (gimple_phi_num_args (phi
) == 1);
2270 /* The phi node can be a non close phi node, when its argument is
2271 invariant, or a default definition. */
2272 if (is_gimple_min_invariant (arg
)
2273 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2275 propagate_expr_outside_region (res
, arg
, region
);
2280 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2282 propagate_expr_outside_region (res
, arg
, region
);
2283 stmt
= gimple_build_assign (res
, arg
);
2284 remove_phi_node (psi
, false);
2285 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2286 SSA_NAME_DEF_STMT (res
) = stmt
;
2290 /* If res is scev analyzable and is not a scalar value, it is safe
2291 to ignore the close phi node: it will be code generated in the
2292 out of Graphite pass. */
2293 else if (scev_analyzable_p (res
, region
))
2295 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2298 if (!loop_in_sese_p (loop
, region
))
2300 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2301 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2302 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2305 scev
= scalar_evolution_in_region (region
, loop
, res
);
2307 if (tree_does_not_contain_chrecs (scev
))
2308 propagate_expr_outside_region (res
, scev
, region
);
2315 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2317 stmt
= gimple_build_assign (res
, zero_dim_array
);
2319 if (TREE_CODE (arg
) == SSA_NAME
)
2320 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2321 SSA_NAME_DEF_STMT (arg
));
2323 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2324 zero_dim_array
, arg
);
2327 remove_phi_node (psi
, false);
2328 SSA_NAME_DEF_STMT (res
) = stmt
;
2330 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2333 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2334 dimension array for it. */
2337 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2340 gimple phi
= gsi_stmt (*psi
);
2341 basic_block bb
= gimple_bb (phi
);
2342 tree res
= gimple_phi_result (phi
);
2343 tree var
= SSA_NAME_VAR (res
);
2344 tree zero_dim_array
= create_zero_dim_array (var
, "phi_out_of_ssa");
2348 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2350 tree arg
= gimple_phi_arg_def (phi
, i
);
2351 edge e
= gimple_phi_arg_edge (phi
, i
);
2353 /* Avoid the insertion of code in the loop latch to please the
2354 pattern matching of the vectorizer. */
2355 if (TREE_CODE (arg
) == SSA_NAME
2356 && e
->src
== bb
->loop_father
->latch
)
2357 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2358 SSA_NAME_DEF_STMT (arg
));
2360 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2363 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2365 stmt
= gimple_build_assign (res
, var
);
2366 remove_phi_node (psi
, false);
2367 SSA_NAME_DEF_STMT (res
) = stmt
;
2369 insert_stmts (scop
, stmt
, stmts
, gsi_after_labels (bb
));
2372 /* Rewrite the degenerate phi node at position PSI from the degenerate
2373 form "x = phi (y, y, ..., y)" to "x = y". */
2376 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2380 gimple_stmt_iterator gsi
;
2381 gimple phi
= gsi_stmt (*psi
);
2382 tree res
= gimple_phi_result (phi
);
2385 bb
= gimple_bb (phi
);
2386 rhs
= degenerate_phi_result (phi
);
2389 stmt
= gimple_build_assign (res
, rhs
);
2390 remove_phi_node (psi
, false);
2391 SSA_NAME_DEF_STMT (res
) = stmt
;
2393 gsi
= gsi_after_labels (bb
);
2394 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2397 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2400 rewrite_reductions_out_of_ssa (scop_p scop
)
2403 gimple_stmt_iterator psi
;
2404 sese region
= SCOP_REGION (scop
);
2407 if (bb_in_sese_p (bb
, region
))
2408 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2410 gimple phi
= gsi_stmt (psi
);
2412 if (!is_gimple_reg (gimple_phi_result (phi
)))
2418 if (gimple_phi_num_args (phi
) > 1
2419 && degenerate_phi_result (phi
))
2420 rewrite_degenerate_phi (&psi
);
2422 else if (scalar_close_phi_node_p (phi
))
2423 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2425 else if (reduction_phi_p (region
, &psi
))
2426 rewrite_phi_out_of_ssa (scop
, &psi
);
2429 update_ssa (TODO_update_ssa
);
2430 #ifdef ENABLE_CHECKING
2431 verify_loop_closed_ssa (true);
2435 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2436 read from ZERO_DIM_ARRAY. */
2439 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2440 tree def
, gimple use_stmt
)
2442 tree var
= SSA_NAME_VAR (def
);
2443 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2444 tree name
= make_ssa_name (var
, name_stmt
);
2446 use_operand_p use_p
;
2448 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2450 gimple_assign_set_lhs (name_stmt
, name
);
2451 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2453 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2454 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2455 replace_exp (use_p
, name
);
2457 update_stmt (use_stmt
);
2460 /* For every definition DEF in the SCOP that is used outside the scop,
2461 insert a closing-scop definition in the basic block just after this
2465 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2467 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2468 tree new_name
= make_ssa_name (var
, stmt
);
2469 bool needs_copy
= false;
2470 use_operand_p use_p
;
2471 imm_use_iterator imm_iter
;
2473 sese region
= SCOP_REGION (scop
);
2475 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2477 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2479 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2481 SET_USE (use_p
, new_name
);
2483 update_stmt (use_stmt
);
2488 /* Insert in the empty BB just after the scop a use of DEF such
2489 that the rewrite of cross_bb_scalar_dependences won't insert
2490 arrays everywhere else. */
2493 gimple assign
= gimple_build_assign (new_name
, def
);
2494 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2496 add_referenced_var (var
);
2497 SSA_NAME_DEF_STMT (new_name
) = assign
;
2498 update_stmt (assign
);
2499 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2503 /* Rewrite the scalar dependences crossing the boundary of the BB
2504 containing STMT with an array. Return true when something has been
2508 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2510 sese region
= SCOP_REGION (scop
);
2511 gimple stmt
= gsi_stmt (*gsi
);
2512 imm_use_iterator imm_iter
;
2515 tree zero_dim_array
= NULL_TREE
;
2519 switch (gimple_code (stmt
))
2522 def
= gimple_assign_lhs (stmt
);
2526 def
= gimple_call_lhs (stmt
);
2534 || !is_gimple_reg (def
))
2537 if (scev_analyzable_p (def
, region
))
2539 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2540 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2542 if (tree_contains_chrecs (scev
, NULL
))
2545 propagate_expr_outside_region (def
, scev
, region
);
2549 def_bb
= gimple_bb (stmt
);
2551 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2553 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2554 if (gimple_code (use_stmt
) == GIMPLE_PHI
2557 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2559 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2560 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2562 rewrite_phi_out_of_ssa (scop
, &psi
);
2565 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2566 if (gimple_code (use_stmt
) != GIMPLE_PHI
2567 && def_bb
!= gimple_bb (use_stmt
)
2568 && !is_gimple_debug (use_stmt
)
2571 if (!zero_dim_array
)
2573 zero_dim_array
= create_zero_dim_array
2574 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2575 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2576 SSA_NAME_DEF_STMT (def
));
2580 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2587 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2590 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2593 gimple_stmt_iterator psi
;
2594 sese region
= SCOP_REGION (scop
);
2595 bool changed
= false;
2597 /* Create an extra empty BB after the scop. */
2598 split_edge (SESE_EXIT (region
));
2601 if (bb_in_sese_p (bb
, region
))
2602 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2603 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2608 update_ssa (TODO_update_ssa
);
2609 #ifdef ENABLE_CHECKING
2610 verify_loop_closed_ssa (true);
2615 /* Returns the number of pbbs that are in loops contained in SCOP. */
2618 nb_pbbs_in_loops (scop_p scop
)
2624 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2625 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2631 /* Return the number of data references in BB that write in
2635 nb_data_writes_in_bb (basic_block bb
)
2638 gimple_stmt_iterator gsi
;
2640 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2641 if (gimple_vdef (gsi_stmt (gsi
)))
2647 /* Splits at STMT the basic block BB represented as PBB in the
2651 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2653 edge e1
= split_block (bb
, stmt
);
2654 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2658 /* Splits STMT out of its current BB. This is done for reduction
2659 statements for which we want to ignore data dependences. */
2662 split_reduction_stmt (scop_p scop
, gimple stmt
)
2664 basic_block bb
= gimple_bb (stmt
);
2665 poly_bb_p pbb
= pbb_from_bb (bb
);
2666 gimple_bb_p gbb
= gbb_from_bb (bb
);
2669 data_reference_p dr
;
2671 /* Do not split basic blocks with no writes to memory: the reduction
2672 will be the only write to memory. */
2673 if (nb_data_writes_in_bb (bb
) == 0
2674 /* Or if we have already marked BB as a reduction. */
2675 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2678 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2680 /* Split once more only when the reduction stmt is not the only one
2681 left in the original BB. */
2682 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2684 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2686 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2689 /* A part of the data references will end in a different basic block
2690 after the split: move the DRs from the original GBB to the newly
2692 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
2694 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2698 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2699 VEC_safe_push (data_reference_p
, heap
, GBB_DATA_REFS (gbb1
), dr
);
2700 VEC_ordered_remove (data_reference_p
, GBB_DATA_REFS (gbb
), i
);
2708 /* Return true when stmt is a reduction operation. */
2711 is_reduction_operation_p (gimple stmt
)
2713 enum tree_code code
;
2715 gcc_assert (is_gimple_assign (stmt
));
2716 code
= gimple_assign_rhs_code (stmt
);
2718 return flag_associative_math
2719 && commutative_tree_code (code
)
2720 && associative_tree_code (code
);
2723 /* Returns true when PHI contains an argument ARG. */
2726 phi_contains_arg (gimple phi
, tree arg
)
2730 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2731 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2737 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2740 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2744 if (TREE_CODE (arg
) != SSA_NAME
)
2747 stmt
= SSA_NAME_DEF_STMT (arg
);
2749 if (gimple_code (stmt
) == GIMPLE_NOP
2750 || gimple_code (stmt
) == GIMPLE_CALL
)
2753 if (gimple_code (stmt
) == GIMPLE_PHI
)
2755 if (phi_contains_arg (stmt
, lhs
))
2760 if (!is_gimple_assign (stmt
))
2763 if (gimple_num_ops (stmt
) == 2)
2764 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2766 if (is_reduction_operation_p (stmt
))
2768 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2771 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2777 /* Detect commutative and associative scalar reductions starting at
2778 the STMT. Return the phi node of the reduction cycle, or NULL. */
2781 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2782 VEC (gimple
, heap
) **in
,
2783 VEC (gimple
, heap
) **out
)
2785 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2790 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2791 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2795 /* Detect commutative and associative scalar reductions starting at
2796 STMT. Return the phi node of the reduction cycle, or NULL. */
2799 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2800 VEC (gimple
, heap
) **out
)
2802 tree lhs
= gimple_assign_lhs (stmt
);
2804 if (gimple_num_ops (stmt
) == 2)
2805 return detect_commutative_reduction_arg (lhs
, stmt
,
2806 gimple_assign_rhs1 (stmt
),
2809 if (is_reduction_operation_p (stmt
))
2811 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2812 gimple_assign_rhs1 (stmt
),
2815 : detect_commutative_reduction_arg (lhs
, stmt
,
2816 gimple_assign_rhs2 (stmt
),
2823 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2826 follow_inital_value_to_phi (tree arg
, tree lhs
)
2830 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2833 stmt
= SSA_NAME_DEF_STMT (arg
);
2835 if (gimple_code (stmt
) == GIMPLE_PHI
2836 && phi_contains_arg (stmt
, lhs
))
2843 /* Return the argument of the loop PHI that is the initial value coming
2844 from outside the loop. */
2847 edge_initial_value_for_loop_phi (gimple phi
)
2851 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2853 edge e
= gimple_phi_arg_edge (phi
, i
);
2855 if (loop_depth (e
->src
->loop_father
)
2856 < loop_depth (e
->dest
->loop_father
))
2863 /* Return the argument of the loop PHI that is the initial value coming
2864 from outside the loop. */
2867 initial_value_for_loop_phi (gimple phi
)
2871 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2873 edge e
= gimple_phi_arg_edge (phi
, i
);
2875 if (loop_depth (e
->src
->loop_father
)
2876 < loop_depth (e
->dest
->loop_father
))
2877 return gimple_phi_arg_def (phi
, i
);
2883 /* Returns true when DEF is used outside the reduction cycle of
2887 used_outside_reduction (tree def
, gimple loop_phi
)
2889 use_operand_p use_p
;
2890 imm_use_iterator imm_iter
;
2891 loop_p loop
= loop_containing_stmt (loop_phi
);
2893 /* In LOOP, DEF should be used only in LOOP_PHI. */
2894 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2896 gimple stmt
= USE_STMT (use_p
);
2898 if (stmt
!= loop_phi
2899 && !is_gimple_debug (stmt
)
2900 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2907 /* Detect commutative and associative scalar reductions belonging to
2908 the SCOP starting at the loop closed phi node STMT. Return the phi
2909 node of the reduction cycle, or NULL. */
2912 detect_commutative_reduction (scop_p scop
, gimple stmt
, VEC (gimple
, heap
) **in
,
2913 VEC (gimple
, heap
) **out
)
2915 if (scalar_close_phi_node_p (stmt
))
2917 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2918 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2920 if (TREE_CODE (arg
) != SSA_NAME
)
2923 /* Note that loop close phi nodes should have a single argument
2924 because we translated the representation into a canonical form
2925 before Graphite: see canonicalize_loop_closed_ssa_form. */
2926 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2928 def
= SSA_NAME_DEF_STMT (arg
);
2929 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2930 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2933 lhs
= gimple_phi_result (close_phi
);
2934 init
= initial_value_for_loop_phi (loop_phi
);
2935 phi
= follow_inital_value_to_phi (init
, lhs
);
2937 if (phi
&& (used_outside_reduction (lhs
, phi
)
2938 || !has_single_use (gimple_phi_result (phi
))))
2941 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2942 VEC_safe_push (gimple
, heap
, *out
, close_phi
);
2946 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2947 return detect_commutative_reduction_assign (stmt
, in
, out
);
2952 /* Translate the scalar reduction statement STMT to an array RED
2953 knowing that its recursive phi node is LOOP_PHI. */
2956 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2957 gimple stmt
, gimple loop_phi
)
2959 tree res
= gimple_phi_result (loop_phi
);
2960 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2961 gimple_stmt_iterator gsi
;
2963 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2965 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2966 gsi
= gsi_for_stmt (stmt
);
2968 insert_stmts (scop
, assign
, NULL
, gsi
);
2971 /* Removes the PHI node and resets all the debug stmts that are using
2975 remove_phi (gimple phi
)
2977 imm_use_iterator imm_iter
;
2979 use_operand_p use_p
;
2980 gimple_stmt_iterator gsi
;
2981 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2985 def
= PHI_RESULT (phi
);
2986 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2988 stmt
= USE_STMT (use_p
);
2990 if (is_gimple_debug (stmt
))
2992 gimple_debug_bind_reset_value (stmt
);
2993 VEC_safe_push (gimple
, heap
, update
, stmt
);
2997 FOR_EACH_VEC_ELT (gimple
, update
, i
, stmt
)
3000 VEC_free (gimple
, heap
, update
);
3002 gsi
= gsi_for_phi_node (phi
);
3003 remove_phi_node (&gsi
, false);
3006 /* Helper function for for_each_index. For each INDEX of the data
3007 reference REF, returns true when its indices are valid in the loop
3008 nest LOOP passed in as DATA. */
3011 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
3014 basic_block header
, def_bb
;
3017 if (TREE_CODE (*index
) != SSA_NAME
)
3020 loop
= *((loop_p
*) data
);
3021 header
= loop
->header
;
3022 stmt
= SSA_NAME_DEF_STMT (*index
);
3027 def_bb
= gimple_bb (stmt
);
3032 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
3035 /* When the result of a CLOSE_PHI is written to a memory location,
3036 return a pointer to that memory reference, otherwise return
3040 close_phi_written_to_memory (gimple close_phi
)
3042 imm_use_iterator imm_iter
;
3043 use_operand_p use_p
;
3045 tree res
, def
= gimple_phi_result (close_phi
);
3047 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
3048 if ((stmt
= USE_STMT (use_p
))
3049 && gimple_code (stmt
) == GIMPLE_ASSIGN
3050 && (res
= gimple_assign_lhs (stmt
)))
3052 switch (TREE_CODE (res
))
3062 tree arg
= gimple_phi_arg_def (close_phi
, 0);
3063 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
3065 /* FIXME: this restriction is for id-{24,25}.f and
3066 could be handled by duplicating the computation of
3067 array indices before the loop of the close_phi. */
3068 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
3080 /* Rewrite out of SSA the reduction described by the loop phi nodes
3081 IN, and the close phi nodes OUT. IN and OUT are structured by loop
3084 IN: stmt, loop_n, ..., loop_0
3085 OUT: stmt, close_n, ..., close_0
3087 the first element is the reduction statement, and the next elements
3088 are the loop and close phi nodes of each of the outer loops. */
3091 translate_scalar_reduction_to_array (scop_p scop
,
3092 VEC (gimple
, heap
) *in
,
3093 VEC (gimple
, heap
) *out
)
3096 unsigned int i
= VEC_length (gimple
, out
) - 1;
3097 tree red
= close_phi_written_to_memory (VEC_index (gimple
, out
, i
));
3099 FOR_EACH_VEC_ELT (gimple
, in
, i
, loop_phi
)
3101 gimple close_phi
= VEC_index (gimple
, out
, i
);
3105 gimple stmt
= loop_phi
;
3106 basic_block bb
= split_reduction_stmt (scop
, stmt
);
3107 poly_bb_p pbb
= pbb_from_bb (bb
);
3108 PBB_IS_REDUCTION (pbb
) = true;
3109 gcc_assert (close_phi
== loop_phi
);
3112 red
= create_zero_dim_array
3113 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3115 translate_scalar_reduction_to_array_for_stmt
3116 (scop
, red
, stmt
, VEC_index (gimple
, in
, 1));
3120 if (i
== VEC_length (gimple
, in
) - 1)
3122 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3123 unshare_expr (red
), close_phi
);
3124 insert_out_of_ssa_copy_on_edge
3125 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3126 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3129 remove_phi (loop_phi
);
3130 remove_phi (close_phi
);
3134 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3135 true when something has been changed. */
3138 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3142 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
3143 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
3145 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3146 res
= VEC_length (gimple
, in
) > 1;
3148 translate_scalar_reduction_to_array (scop
, in
, out
);
3150 VEC_free (gimple
, heap
, in
);
3151 VEC_free (gimple
, heap
, out
);
3155 /* Rewrites all the commutative reductions from LOOP out of SSA.
3156 Returns true when something has been changed. */
3159 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3162 gimple_stmt_iterator gsi
;
3163 edge exit
= single_exit (loop
);
3165 bool changed
= false;
3170 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3171 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3172 && is_gimple_reg (res
)
3173 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3174 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3175 (scop
, gsi_stmt (gsi
));
3180 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3183 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3187 bool changed
= false;
3188 sese region
= SCOP_REGION (scop
);
3190 FOR_EACH_LOOP (li
, loop
, 0)
3191 if (loop_in_sese_p (loop
, region
))
3192 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3197 gsi_commit_edge_inserts ();
3198 update_ssa (TODO_update_ssa
);
3199 #ifdef ENABLE_CHECKING
3200 verify_loop_closed_ssa (true);
3205 /* Can all ivs be represented by a signed integer?
3206 As CLooG might generate negative values in its expressions, signed loop ivs
3207 are required in the backend. */
3210 scop_ivs_can_be_represented (scop_p scop
)
3214 gimple_stmt_iterator psi
;
3216 FOR_EACH_LOOP (li
, loop
, 0)
3218 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3221 for (psi
= gsi_start_phis (loop
->header
);
3222 !gsi_end_p (psi
); gsi_next (&psi
))
3224 gimple phi
= gsi_stmt (psi
);
3225 tree res
= PHI_RESULT (phi
);
3226 tree type
= TREE_TYPE (res
);
3228 if (TYPE_UNSIGNED (type
)
3229 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3237 /* Builds the polyhedral representation for a SESE region. */
3240 build_poly_scop (scop_p scop
)
3242 sese region
= SCOP_REGION (scop
);
3243 graphite_dim_t max_dim
;
3245 build_scop_bbs (scop
);
3247 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3248 Once CLooG is fixed, remove this guard. Anyways, it makes no
3249 sense to optimize a scop containing only PBBs that do not belong
3251 if (nb_pbbs_in_loops (scop
) == 0)
3254 if (!scop_ivs_can_be_represented (scop
))
3257 if (flag_associative_math
)
3258 rewrite_commutative_reductions_out_of_ssa (scop
);
3260 build_sese_loop_nests (region
);
3261 build_sese_conditions (region
);
3262 find_scop_parameters (scop
);
3264 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3265 if (scop_nb_params (scop
) > max_dim
)
3268 build_scop_iteration_domain (scop
);
3269 build_scop_context (scop
);
3270 add_conditions_to_constraints (scop
);
3272 /* Rewrite out of SSA only after having translated the
3273 representation to the polyhedral representation to avoid scev
3274 analysis failures. That means that these functions will insert
3275 new data references that they create in the right place. */
3276 rewrite_reductions_out_of_ssa (scop
);
3277 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3279 build_scop_drs (scop
);
3281 build_scop_scattering (scop
);
3283 /* This SCoP has been translated to the polyhedral
3285 POLY_SCOP_P (scop
) = true;