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"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
47 #include "graphite-ppl.h"
49 #include "graphite-poly.h"
50 #include "graphite-scop-detection.h"
51 #include "graphite-sese-to-poly.h"
53 /* Check if VAR is used in a phi node, that is no loop header. */
56 var_used_in_not_loop_header_phi_node (tree var
)
58 imm_use_iterator imm_iter
;
62 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
64 basic_block bb
= gimple_bb (stmt
);
66 if (gimple_code (stmt
) == GIMPLE_PHI
67 && bb
->loop_father
->header
!= bb
)
74 /* Returns the index of the PHI argument defined in the outermost
78 phi_arg_in_outermost_loop (gimple phi
)
80 loop_p loop
= gimple_bb (phi
)->loop_father
;
83 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
84 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
86 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
94 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
97 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
99 gimple phi
= gsi_stmt (*psi
);
100 tree res
= gimple_phi_result (phi
);
101 size_t entry
= phi_arg_in_outermost_loop (phi
);
102 tree init
= gimple_phi_arg_def (phi
, entry
);
103 gimple stmt
= gimple_build_assign (res
, init
);
104 edge e
= gimple_phi_arg_edge (phi
, entry
);
106 remove_phi_node (psi
, false);
107 gsi_insert_on_edge_immediate (e
, stmt
);
108 SSA_NAME_DEF_STMT (res
) = stmt
;
111 /* Removes an invariant phi node at position PSI by inserting on the
112 loop ENTRY edge the assignment RES = INIT. */
115 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
117 gimple phi
= gsi_stmt (*psi
);
118 loop_p loop
= loop_containing_stmt (phi
);
119 tree res
= gimple_phi_result (phi
);
120 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
121 size_t entry
= phi_arg_in_outermost_loop (phi
);
122 edge e
= gimple_phi_arg_edge (phi
, entry
);
126 gimple_stmt_iterator gsi
;
128 if (tree_contains_chrecs (scev
, NULL
))
129 scev
= gimple_phi_arg_def (phi
, entry
);
131 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
132 stmt
= gimple_build_assign (res
, var
);
133 remove_phi_node (psi
, false);
136 stmts
= gimple_seq_alloc ();
138 gsi
= gsi_last (stmts
);
139 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
140 gsi_insert_seq_on_edge (e
, stmts
);
141 gsi_commit_edge_inserts ();
142 SSA_NAME_DEF_STMT (res
) = stmt
;
145 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
148 simple_copy_phi_p (gimple phi
)
152 if (gimple_phi_num_args (phi
) != 2)
155 res
= gimple_phi_result (phi
);
156 return (res
== gimple_phi_arg_def (phi
, 0)
157 || res
== gimple_phi_arg_def (phi
, 1));
160 /* Returns true when the phi node at position PSI is a reduction phi
161 node in REGION. Otherwise moves the pointer PSI to the next phi to
165 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
168 gimple phi
= gsi_stmt (*psi
);
169 tree res
= gimple_phi_result (phi
);
171 loop
= loop_containing_stmt (phi
);
173 if (simple_copy_phi_p (phi
))
175 /* PRE introduces phi nodes like these, for an example,
176 see id-5.f in the fortran graphite testsuite:
178 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
180 remove_simple_copy_phi (psi
);
184 if (scev_analyzable_p (res
, region
))
186 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
188 if (evolution_function_is_invariant_p (scev
, loop
->num
))
189 remove_invariant_phi (region
, psi
);
196 /* All the other cases are considered reductions. */
200 /* Returns true when BB will be represented in graphite. Return false
201 for the basic blocks that contain code eliminated in the code
202 generation pass: i.e. induction variables and exit conditions. */
205 graphite_stmt_p (sese region
, basic_block bb
,
206 VEC (data_reference_p
, heap
) *drs
)
208 gimple_stmt_iterator gsi
;
209 loop_p loop
= bb
->loop_father
;
211 if (VEC_length (data_reference_p
, drs
) > 0)
214 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
216 gimple stmt
= gsi_stmt (gsi
);
218 switch (gimple_code (stmt
))
221 /* Control flow expressions can be ignored, as they are
222 represented in the iteration domains and will be
223 regenerated by graphite. */
231 tree var
= gimple_assign_lhs (stmt
);
233 /* We need these bbs to be able to construct the phi nodes. */
234 if (var_used_in_not_loop_header_phi_node (var
))
237 var
= scalar_evolution_in_region (region
, loop
, var
);
238 if (chrec_contains_undetermined (var
))
252 /* Store the GRAPHITE representation of BB. */
255 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
257 struct gimple_bb
*gbb
;
259 gbb
= XNEW (struct gimple_bb
);
262 GBB_DATA_REFS (gbb
) = drs
;
263 GBB_CONDITIONS (gbb
) = NULL
;
264 GBB_CONDITION_CASES (gbb
) = NULL
;
270 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
273 struct data_reference
*dr
;
275 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
278 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
281 free (bap
->alias_set
);
290 free_gimple_bb (struct gimple_bb
*gbb
)
292 free_data_refs_aux (GBB_DATA_REFS (gbb
));
293 free_data_refs (GBB_DATA_REFS (gbb
));
295 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
296 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
297 GBB_BB (gbb
)->aux
= 0;
301 /* Deletes all gimple bbs in SCOP. */
304 remove_gbbs_in_scop (scop_p scop
)
309 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
310 free_gimple_bb (PBB_BLACK_BOX (pbb
));
313 /* Deletes all scops in SCOPS. */
316 free_scops (VEC (scop_p
, heap
) *scops
)
321 FOR_EACH_VEC_ELT (scop_p
, scops
, i
, scop
)
323 remove_gbbs_in_scop (scop
);
324 free_sese (SCOP_REGION (scop
));
328 VEC_free (scop_p
, heap
, scops
);
331 /* Generates a polyhedral black box only if the bb contains interesting
335 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
337 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
338 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
339 gimple_stmt_iterator gsi
;
341 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
343 gimple stmt
= gsi_stmt (gsi
);
344 if (!is_gimple_debug (stmt
))
345 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
348 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
349 free_data_refs (drs
);
351 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
355 /* Returns true if all predecessors of BB, that are not dominated by BB, are
356 marked in MAP. The predecessors dominated by BB are loop latches and will
357 be handled after BB. */
360 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
365 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
366 if (!TEST_BIT (map
, e
->src
->index
)
367 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
373 /* Compare the depth of two basic_block's P1 and P2. */
376 compare_bb_depths (const void *p1
, const void *p2
)
378 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
379 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
380 int d1
= loop_depth (bb1
->loop_father
);
381 int d2
= loop_depth (bb2
->loop_father
);
392 /* Sort the basic blocks from DOM such that the first are the ones at
393 a deepest loop level. */
396 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
398 size_t len
= VEC_length (basic_block
, dom
);
400 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
404 /* Recursive helper function for build_scops_bbs. */
407 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
409 sese region
= SCOP_REGION (scop
);
410 VEC (basic_block
, heap
) *dom
;
412 if (TEST_BIT (visited
, bb
->index
)
413 || !bb_in_sese_p (bb
, region
))
416 try_generate_gimple_bb (scop
, bb
, reductions
);
417 SET_BIT (visited
, bb
->index
);
419 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
424 graphite_sort_dominated_info (dom
);
426 while (!VEC_empty (basic_block
, dom
))
431 FOR_EACH_VEC_ELT (basic_block
, dom
, i
, dom_bb
)
432 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
434 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
435 VEC_unordered_remove (basic_block
, dom
, i
);
440 VEC_free (basic_block
, heap
, dom
);
443 /* Gather the basic blocks belonging to the SCOP. */
446 build_scop_bbs (scop_p scop
, sbitmap reductions
)
448 sbitmap visited
= sbitmap_alloc (last_basic_block
);
449 sese region
= SCOP_REGION (scop
);
451 sbitmap_zero (visited
);
452 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
453 sbitmap_free (visited
);
456 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
457 We generate SCATTERING_DIMENSIONS scattering dimensions.
459 CLooG 0.15.0 and previous versions require, that all
460 scattering functions of one CloogProgram have the same number of
461 scattering dimensions, therefore we allow to specify it. This
462 should be removed in future versions of CLooG.
464 The scattering polyhedron consists of these dimensions: scattering,
465 loop_iterators, parameters.
469 | scattering_dimensions = 5
470 | used_scattering_dimensions = 3
478 | Scattering polyhedron:
480 | scattering: {s1, s2, s3, s4, s5}
481 | loop_iterators: {i}
482 | parameters: {p1, p2}
484 | s1 s2 s3 s4 s5 i p1 p2 1
485 | 1 0 0 0 0 0 0 0 -4 = 0
486 | 0 1 0 0 0 -1 0 0 0 = 0
487 | 0 0 1 0 0 0 0 0 -5 = 0 */
490 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
491 poly_bb_p pbb
, int scattering_dimensions
)
494 scop_p scop
= PBB_SCOP (pbb
);
495 int nb_iterators
= pbb_dim_iter_domain (pbb
);
496 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
497 int nb_params
= scop_nb_params (scop
);
499 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
502 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
505 ppl_new_Coefficient (&c
);
506 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
507 ppl_new_C_Polyhedron_from_space_dimension
508 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
510 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
512 for (i
= 0; i
< scattering_dimensions
; i
++)
514 ppl_Constraint_t cstr
;
515 ppl_Linear_Expression_t expr
;
517 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
519 ppl_assign_Coefficient_from_mpz_t (c
, v
);
520 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
522 /* Textual order inside this loop. */
525 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
526 ppl_Coefficient_to_mpz_t (c
, v
);
528 ppl_assign_Coefficient_from_mpz_t (c
, v
);
529 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
532 /* Iterations of this loop. */
533 else /* if ((i % 2) == 1) */
535 int loop
= (i
- 1) / 2;
538 ppl_assign_Coefficient_from_mpz_t (c
, v
);
539 ppl_Linear_Expression_add_to_coefficient
540 (expr
, scattering_dimensions
+ loop
, c
);
543 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
544 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
545 ppl_delete_Linear_Expression (expr
);
546 ppl_delete_Constraint (cstr
);
550 ppl_delete_Coefficient (c
);
552 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
555 /* Build for BB the static schedule.
557 The static schedule is a Dewey numbering of the abstract syntax
558 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
560 The following example informally defines the static schedule:
579 Static schedules for A to F:
592 build_scop_scattering (scop_p scop
)
596 gimple_bb_p previous_gbb
= NULL
;
597 ppl_Linear_Expression_t static_schedule
;
602 ppl_new_Coefficient (&c
);
603 ppl_new_Linear_Expression (&static_schedule
);
605 /* We have to start schedules at 0 on the first component and
606 because we cannot compare_prefix_loops against a previous loop,
607 prefix will be equal to zero, and that index will be
608 incremented before copying. */
610 ppl_assign_Coefficient_from_mpz_t (c
, v
);
611 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
613 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
615 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
616 ppl_Linear_Expression_t common
;
618 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
621 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
626 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
627 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
631 ppl_assign_Coefficient_from_mpz_t (c
, v
);
632 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
633 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
636 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
638 ppl_delete_Linear_Expression (common
);
642 ppl_delete_Coefficient (c
);
643 ppl_delete_Linear_Expression (static_schedule
);
646 /* Add the value K to the dimension D of the linear expression EXPR. */
649 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
653 ppl_Coefficient_t coef
;
655 ppl_new_Coefficient (&coef
);
656 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
658 ppl_Coefficient_to_mpz_t (coef
, val
);
660 mpz_add (val
, val
, k
);
662 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
663 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
665 ppl_delete_Coefficient (coef
);
668 /* In the context of scop S, scan E, the right hand side of a scalar
669 evolution function in loop VAR, and translate it to a linear
673 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
674 ppl_Linear_Expression_t expr
)
678 loop_p loop
= get_loop (var
);
679 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
682 /* Scalar evolutions should happen in the sese region. */
683 gcc_assert (sese_loop_depth (s
, loop
) > 0);
685 /* We can not deal with parametric strides like:
691 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
694 mpz_set_si (val
, int_cst_value (e
));
695 add_value_to_dim (l
, expr
, val
);
700 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
701 linear expression EXPR. K is the multiplier of the constant. */
704 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, mpz_t k
)
707 ppl_Coefficient_t coef
;
708 int v
= int_cst_value (cst
);
713 /* Necessary to not get "-1 = 2^n - 1". */
715 mpz_sub_ui (val
, val
, -v
);
717 mpz_add_ui (val
, val
, v
);
719 mpz_mul (val
, val
, k
);
720 ppl_new_Coefficient (&coef
);
721 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
722 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
724 ppl_delete_Coefficient (coef
);
727 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
728 Otherwise returns -1. */
731 parameter_index_in_region_1 (tree name
, sese region
)
736 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
738 FOR_EACH_VEC_ELT (tree
, SESE_PARAMS (region
), i
, p
)
745 /* When the parameter NAME is in REGION, returns its index in
746 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
747 and returns the index of NAME. */
750 parameter_index_in_region (tree name
, sese region
)
754 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
756 i
= parameter_index_in_region_1 (name
, region
);
760 gcc_assert (SESE_ADD_PARAMS (region
));
762 i
= VEC_length (tree
, SESE_PARAMS (region
));
763 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
767 /* In the context of sese S, scan the expression E and translate it to
768 a linear expression C. When parsing a symbolic multiplication, K
769 represents the constant multiplier of an expression containing
773 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
776 if (e
== chrec_dont_know
)
779 switch (TREE_CODE (e
))
781 case POLYNOMIAL_CHREC
:
782 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
783 CHREC_VARIABLE (e
), c
);
784 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
788 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
793 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
795 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
796 mpz_mul (val
, val
, k
);
797 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
801 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
808 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
810 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
811 mpz_mul (val
, val
, k
);
812 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
816 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
821 case POINTER_PLUS_EXPR
:
822 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
823 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
828 ppl_Linear_Expression_t tmp_expr
= NULL
;
832 ppl_dimension_type dim
;
833 ppl_Linear_Expression_space_dimension (c
, &dim
);
834 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
837 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
838 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
842 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
844 ppl_delete_Linear_Expression (tmp_expr
);
852 ppl_Linear_Expression_t tmp_expr
= NULL
;
856 ppl_dimension_type dim
;
857 ppl_Linear_Expression_space_dimension (c
, &dim
);
858 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
861 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
865 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
867 ppl_delete_Linear_Expression (tmp_expr
);
875 ppl_Linear_Expression_t tmp_expr
= NULL
;
879 ppl_dimension_type dim
;
880 ppl_Linear_Expression_space_dimension (c
, &dim
);
881 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
884 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
888 ppl_Coefficient_t coef
;
891 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
893 ppl_delete_Linear_Expression (tmp_expr
);
894 mpz_init (minus_one
);
895 mpz_set_si (minus_one
, -1);
896 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
897 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
898 mpz_clear (minus_one
);
899 ppl_delete_Coefficient (coef
);
907 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
911 ppl_dimension_type dim
;
912 ppl_Linear_Expression_space_dimension (c
, &dim
);
913 p
+= dim
- sese_nb_params (s
);
914 add_value_to_dim (p
, c
, k
);
921 scan_tree_for_params_int (e
, c
, k
);
925 case NON_LVALUE_EXPR
:
926 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
935 /* Find parameters with respect to REGION in BB. We are looking in memory
936 access functions, conditions and loop bounds. */
939 find_params_in_bb (sese region
, gimple_bb_p gbb
)
945 loop_p loop
= GBB_BB (gbb
)->loop_father
;
951 /* Find parameters in the access functions of data references. */
952 FOR_EACH_VEC_ELT (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
)
953 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
954 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
956 /* Find parameters in conditional statements. */
957 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
959 tree lhs
= scalar_evolution_in_region (region
, loop
,
960 gimple_cond_lhs (stmt
));
961 tree rhs
= scalar_evolution_in_region (region
, loop
,
962 gimple_cond_rhs (stmt
));
964 scan_tree_for_params (region
, lhs
, NULL
, one
);
965 scan_tree_for_params (region
, rhs
, NULL
, one
);
971 /* Record the parameters used in the SCOP. A variable is a parameter
972 in a scop if it does not vary during the execution of that scop. */
975 find_scop_parameters (scop_p scop
)
979 sese region
= SCOP_REGION (scop
);
986 /* Find the parameters used in the loop bounds. */
987 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
989 tree nb_iters
= number_of_latch_executions (loop
);
991 if (!chrec_contains_symbols (nb_iters
))
994 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
995 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1000 /* Find the parameters used in data accesses. */
1001 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1002 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1004 scop_set_nb_params (scop
, sese_nb_params (region
));
1005 SESE_ADD_PARAMS (region
) = false;
1007 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1008 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1011 /* Returns a gimple_bb from BB. */
1013 static inline gimple_bb_p
1014 gbb_from_bb (basic_block bb
)
1016 return (gimple_bb_p
) bb
->aux
;
1019 /* Insert in the SCOP context constraints from the estimation of the
1020 number of iterations. UB_EXPR is a linear expression describing
1021 the number of iterations in a loop. This expression is bounded by
1022 the estimation NIT. */
1025 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
1026 ppl_dimension_type dim
,
1027 ppl_Linear_Expression_t ub_expr
)
1030 ppl_Linear_Expression_t nb_iters_le
;
1031 ppl_Polyhedron_t pol
;
1032 ppl_Coefficient_t coef
;
1033 ppl_Constraint_t ub
;
1035 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1036 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1037 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1040 /* Construct the negated number of last iteration in VAL. */
1042 mpz_set_double_int (val
, nit
, false);
1043 mpz_sub_ui (val
, val
, 1);
1046 /* NB_ITERS_LE holds the number of last iteration in
1047 parametrical form. Subtract estimated number of last
1048 iteration and assert that result is not positive. */
1049 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1050 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1051 ppl_delete_Coefficient (coef
);
1052 ppl_new_Constraint (&ub
, nb_iters_le
,
1053 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1054 ppl_Polyhedron_add_constraint (pol
, ub
);
1056 /* Remove all but last GDIM dimensions from POL to obtain
1057 only the constraints on the parameters. */
1059 graphite_dim_t gdim
= scop_nb_params (scop
);
1060 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
1063 for (i
= 0; i
< dim
- gdim
; i
++)
1066 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
1070 /* Add the constraints on the parameters to the SCoP context. */
1072 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1074 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1075 (&constraints_ps
, pol
);
1076 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1077 (SCOP_CONTEXT (scop
), constraints_ps
);
1078 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1081 ppl_delete_Polyhedron (pol
);
1082 ppl_delete_Linear_Expression (nb_iters_le
);
1083 ppl_delete_Constraint (ub
);
1087 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1088 the constraints for the surrounding loops. */
1091 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1092 ppl_Polyhedron_t outer_ph
, int nb
,
1093 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1096 ppl_Polyhedron_t ph
;
1097 tree nb_iters
= number_of_latch_executions (loop
);
1098 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1099 sese region
= SCOP_REGION (scop
);
1102 ppl_const_Constraint_System_t pcs
;
1103 ppl_dimension_type
*map
1104 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1106 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1107 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1108 ppl_Polyhedron_add_constraints (ph
, pcs
);
1110 for (i
= 0; i
< (int) nb
; i
++)
1112 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1116 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1122 ppl_Constraint_t lb
;
1123 ppl_Linear_Expression_t lb_expr
;
1125 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1126 ppl_set_coef (lb_expr
, nb
, 1);
1127 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1128 ppl_delete_Linear_Expression (lb_expr
);
1129 ppl_Polyhedron_add_constraint (ph
, lb
);
1130 ppl_delete_Constraint (lb
);
1133 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1135 ppl_Constraint_t ub
;
1136 ppl_Linear_Expression_t ub_expr
;
1138 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1140 /* loop_i <= cst_nb_iters */
1141 ppl_set_coef (ub_expr
, nb
, -1);
1142 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1143 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1144 ppl_Polyhedron_add_constraint (ph
, ub
);
1145 ppl_delete_Linear_Expression (ub_expr
);
1146 ppl_delete_Constraint (ub
);
1148 else if (!chrec_contains_undetermined (nb_iters
))
1151 ppl_Constraint_t ub
;
1152 ppl_Linear_Expression_t ub_expr
;
1156 mpz_set_si (one
, 1);
1157 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1158 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1159 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1162 if (estimated_loop_iterations (loop
, true, &nit
))
1163 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1165 /* loop_i <= expr_nb_iters */
1166 ppl_set_coef (ub_expr
, nb
, -1);
1167 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1168 ppl_Polyhedron_add_constraint (ph
, ub
);
1169 ppl_delete_Linear_Expression (ub_expr
);
1170 ppl_delete_Constraint (ub
);
1175 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1176 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1180 && loop_in_sese_p (loop
->next
, region
))
1181 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1183 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1184 (&domains
[loop
->num
], ph
);
1186 ppl_delete_Polyhedron (ph
);
1189 /* Returns a linear expression for tree T evaluated in PBB. */
1191 static ppl_Linear_Expression_t
1192 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1195 ppl_Linear_Expression_t res
;
1196 ppl_dimension_type dim
;
1197 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1198 loop_p loop
= pbb_loop (pbb
);
1200 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1201 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1203 t
= scalar_evolution_in_region (region
, loop
, t
);
1204 gcc_assert (!automatically_generated_chrec_p (t
));
1207 mpz_set_si (one
, 1);
1208 scan_tree_for_params (region
, t
, res
, one
);
1214 /* Returns the ppl constraint type from the gimple tree code CODE. */
1216 static enum ppl_enum_Constraint_Type
1217 ppl_constraint_type_from_tree_code (enum tree_code code
)
1221 /* We do not support LT and GT to be able to work with C_Polyhedron.
1222 As we work on integer polyhedron "a < b" can be expressed by
1229 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1232 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1235 return PPL_CONSTRAINT_TYPE_EQUAL
;
1242 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1243 CODE is used as the comparison operator. This allows us to invert the
1244 condition or to handle inequalities. */
1247 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1248 poly_bb_p pbb
, enum tree_code code
)
1251 ppl_Coefficient_t c
;
1252 ppl_Linear_Expression_t left
, right
;
1253 ppl_Constraint_t cstr
;
1254 enum ppl_enum_Constraint_Type type
;
1256 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1257 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1259 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1260 the left or the right side of the expression. */
1261 if (code
== LT_EXPR
)
1265 ppl_new_Coefficient (&c
);
1266 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1267 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1268 ppl_delete_Coefficient (c
);
1273 else if (code
== GT_EXPR
)
1277 ppl_new_Coefficient (&c
);
1278 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1279 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1280 ppl_delete_Coefficient (c
);
1286 type
= ppl_constraint_type_from_tree_code (code
);
1288 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1290 ppl_new_Constraint (&cstr
, left
, type
);
1291 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1293 ppl_delete_Constraint (cstr
);
1294 ppl_delete_Linear_Expression (left
);
1295 ppl_delete_Linear_Expression (right
);
1298 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1299 operator. This allows us to invert the condition or to handle
1303 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1305 if (code
== NE_EXPR
)
1307 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1308 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1309 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1311 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1312 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1313 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
, right
);
1314 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1317 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1320 /* Add conditions to the domain of PBB. */
1323 add_conditions_to_domain (poly_bb_p pbb
)
1327 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1329 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1332 FOR_EACH_VEC_ELT (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
)
1333 switch (gimple_code (stmt
))
1337 enum tree_code code
= gimple_cond_code (stmt
);
1339 /* The conditions for ELSE-branches are inverted. */
1340 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1341 code
= invert_tree_comparison (code
, false);
1343 add_condition_to_pbb (pbb
, stmt
, code
);
1348 /* Switch statements are not supported right now - fall throught. */
1356 /* Structure used to pass data to dom_walk. */
1360 VEC (gimple
, heap
) **conditions
, **cases
;
1364 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1365 edge between BB and its predecessor is not a loop exit edge, and
1366 the last statement of the single predecessor is a COND_EXPR. */
1369 single_pred_cond_non_loop_exit (basic_block bb
)
1371 if (single_pred_p (bb
))
1373 edge e
= single_pred_edge (bb
);
1374 basic_block pred
= e
->src
;
1377 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1380 stmt
= last_stmt (pred
);
1382 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1389 /* Call-back for dom_walk executed before visiting the dominated
1393 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1396 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1397 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1398 VEC (gimple
, heap
) **cases
= data
->cases
;
1402 if (!bb_in_sese_p (bb
, data
->region
))
1405 stmt
= single_pred_cond_non_loop_exit (bb
);
1409 edge e
= single_pred_edge (bb
);
1411 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1413 if (e
->flags
& EDGE_TRUE_VALUE
)
1414 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1416 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1419 gbb
= gbb_from_bb (bb
);
1423 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1424 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1428 /* Call-back for dom_walk executed after visiting the dominated
1432 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1435 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1436 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1437 VEC (gimple
, heap
) **cases
= data
->cases
;
1439 if (!bb_in_sese_p (bb
, data
->region
))
1442 if (single_pred_cond_non_loop_exit (bb
))
1444 VEC_pop (gimple
, *conditions
);
1445 VEC_pop (gimple
, *cases
);
1449 /* Record all conditions in REGION. */
1452 build_sese_conditions (sese region
)
1454 struct dom_walk_data walk_data
;
1455 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1456 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1459 data
.conditions
= &conditions
;
1460 data
.cases
= &cases
;
1461 data
.region
= region
;
1463 walk_data
.dom_direction
= CDI_DOMINATORS
;
1464 walk_data
.initialize_block_local_data
= NULL
;
1465 walk_data
.before_dom_children
= build_sese_conditions_before
;
1466 walk_data
.after_dom_children
= build_sese_conditions_after
;
1467 walk_data
.global_data
= &data
;
1468 walk_data
.block_local_data_size
= 0;
1470 init_walk_dominator_tree (&walk_data
);
1471 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1472 fini_walk_dominator_tree (&walk_data
);
1474 VEC_free (gimple
, heap
, conditions
);
1475 VEC_free (gimple
, heap
, cases
);
1478 /* Traverses all the GBBs of the SCOP and add their constraints to the
1479 iteration domains. */
1482 add_conditions_to_constraints (scop_p scop
)
1487 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1488 add_conditions_to_domain (pbb
);
1491 /* Add constraints on the possible values of parameter P from the type
1495 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1497 ppl_Constraint_t cstr
;
1498 ppl_Linear_Expression_t le
;
1499 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1500 tree type
= TREE_TYPE (parameter
);
1501 tree lb
= NULL_TREE
;
1502 tree ub
= NULL_TREE
;
1504 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1505 lb
= lower_bound_in_type (type
, type
);
1507 lb
= TYPE_MIN_VALUE (type
);
1509 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1510 ub
= upper_bound_in_type (type
, type
);
1512 ub
= TYPE_MAX_VALUE (type
);
1516 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1517 ppl_set_coef (le
, p
, -1);
1518 ppl_set_inhomogeneous_tree (le
, lb
);
1519 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1520 ppl_Polyhedron_add_constraint (context
, cstr
);
1521 ppl_delete_Linear_Expression (le
);
1522 ppl_delete_Constraint (cstr
);
1527 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1528 ppl_set_coef (le
, p
, -1);
1529 ppl_set_inhomogeneous_tree (le
, ub
);
1530 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1531 ppl_Polyhedron_add_constraint (context
, cstr
);
1532 ppl_delete_Linear_Expression (le
);
1533 ppl_delete_Constraint (cstr
);
1537 /* Build the context of the SCOP. The context usually contains extra
1538 constraints that are added to the iteration domains that constrain
1542 build_scop_context (scop_p scop
)
1544 ppl_Polyhedron_t context
;
1545 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1546 graphite_dim_t p
, n
= scop_nb_params (scop
);
1548 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1550 for (p
= 0; p
< n
; p
++)
1551 add_param_constraints (scop
, context
, p
);
1553 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1555 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1556 (SCOP_CONTEXT (scop
), ps
);
1558 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1559 ppl_delete_Polyhedron (context
);
1562 /* Build the iteration domains: the loops belonging to the current
1563 SCOP, and that vary for the execution of the current basic block.
1564 Returns false if there is no loop in SCOP. */
1567 build_scop_iteration_domain (scop_p scop
)
1570 sese region
= SCOP_REGION (scop
);
1572 ppl_Polyhedron_t ph
;
1574 int nb_loops
= number_of_loops ();
1575 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1576 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1578 for (i
= 0; i
< nb_loops
; i
++)
1581 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1583 FOR_EACH_VEC_ELT (loop_p
, SESE_LOOP_NEST (region
), i
, loop
)
1584 if (!loop_in_sese_p (loop_outer (loop
), region
))
1585 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1587 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
1588 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1589 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1590 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1591 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1593 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1594 (&PBB_DOMAIN (pbb
), ph
);
1596 for (i
= 0; i
< nb_loops
; i
++)
1598 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1600 ppl_delete_Polyhedron (ph
);
1604 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1605 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1606 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1610 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1611 ppl_dimension_type accessp_nb_dims
,
1612 ppl_dimension_type dom_nb_dims
)
1614 ppl_Linear_Expression_t alias
;
1615 ppl_Constraint_t cstr
;
1616 int alias_set_num
= 0;
1617 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1619 if (bap
&& bap
->alias_set
)
1620 alias_set_num
= *(bap
->alias_set
);
1622 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1624 ppl_set_coef (alias
, dom_nb_dims
, 1);
1625 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1626 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1627 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1629 ppl_delete_Linear_Expression (alias
);
1630 ppl_delete_Constraint (cstr
);
1633 /* Add to ACCESSES polyhedron equalities defining the access functions
1634 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1635 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1636 PBB is the poly_bb_p that contains the data reference DR. */
1639 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1640 ppl_dimension_type accessp_nb_dims
,
1641 ppl_dimension_type dom_nb_dims
,
1644 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1646 scop_p scop
= PBB_SCOP (pbb
);
1647 sese region
= SCOP_REGION (scop
);
1651 for (i
= 0; i
< nb_subscripts
; i
++)
1653 ppl_Linear_Expression_t fn
, access
;
1654 ppl_Constraint_t cstr
;
1655 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1656 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1658 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1659 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1662 scan_tree_for_params (region
, afn
, fn
, v
);
1663 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1665 ppl_set_coef (access
, subscript
, -1);
1666 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1667 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1669 ppl_delete_Linear_Expression (fn
);
1670 ppl_delete_Linear_Expression (access
);
1671 ppl_delete_Constraint (cstr
);
1677 /* Add constrains representing the size of the accessed data to the
1678 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1679 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1683 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1684 ppl_dimension_type accessp_nb_dims
,
1685 ppl_dimension_type dom_nb_dims
)
1687 tree ref
= DR_REF (dr
);
1688 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1690 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1692 ppl_Linear_Expression_t expr
;
1693 ppl_Constraint_t cstr
;
1694 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1697 if (TREE_CODE (ref
) != ARRAY_REF
)
1700 low
= array_ref_low_bound (ref
);
1702 /* subscript - low >= 0 */
1703 if (host_integerp (low
, 0))
1705 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1706 ppl_set_coef (expr
, subscript
, 1);
1708 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1710 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1711 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1712 ppl_delete_Linear_Expression (expr
);
1713 ppl_delete_Constraint (cstr
);
1716 high
= array_ref_up_bound (ref
);
1718 /* high - subscript >= 0 */
1719 if (high
&& host_integerp (high
, 0)
1720 /* 1-element arrays at end of structures may extend over
1721 their declared size. */
1722 && !(array_at_struct_end_p (ref
)
1723 && operand_equal_p (low
, high
, 0)))
1725 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1726 ppl_set_coef (expr
, subscript
, -1);
1728 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1730 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1731 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1732 ppl_delete_Linear_Expression (expr
);
1733 ppl_delete_Constraint (cstr
);
1738 /* Build data accesses for DR in PBB. */
1741 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1743 ppl_Polyhedron_t accesses
;
1744 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1745 ppl_dimension_type dom_nb_dims
;
1746 ppl_dimension_type accessp_nb_dims
;
1747 int dr_base_object_set
;
1749 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1751 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1753 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1755 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1756 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1757 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1759 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1761 ppl_delete_Polyhedron (accesses
);
1763 gcc_assert (dr
->aux
);
1764 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1766 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
,
1767 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1768 dr
, DR_NUM_DIMENSIONS (dr
));
1771 /* Write to FILE the alias graph of data references in DIMACS format. */
1774 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1775 VEC (data_reference_p
, heap
) *drs
)
1777 int num_vertex
= VEC_length (data_reference_p
, drs
);
1779 data_reference_p dr1
, dr2
;
1782 if (num_vertex
== 0)
1785 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1786 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1787 if (dr_may_alias_p (dr1
, dr2
))
1790 fprintf (file
, "$\n");
1793 fprintf (file
, "c %s\n", comment
);
1795 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1797 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1798 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1799 if (dr_may_alias_p (dr1
, dr2
))
1800 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1805 /* Write to FILE the alias graph of data references in DOT format. */
1808 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1809 VEC (data_reference_p
, heap
) *drs
)
1811 int num_vertex
= VEC_length (data_reference_p
, drs
);
1812 data_reference_p dr1
, dr2
;
1815 if (num_vertex
== 0)
1818 fprintf (file
, "$\n");
1821 fprintf (file
, "c %s\n", comment
);
1823 /* First print all the vertices. */
1824 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1825 fprintf (file
, "n%d;\n", i
);
1827 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1828 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1829 if (dr_may_alias_p (dr1
, dr2
))
1830 fprintf (file
, "n%d n%d\n", i
, j
);
1835 /* Write to FILE the alias graph of data references in ECC format. */
1838 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1839 VEC (data_reference_p
, heap
) *drs
)
1841 int num_vertex
= VEC_length (data_reference_p
, drs
);
1842 data_reference_p dr1
, dr2
;
1845 if (num_vertex
== 0)
1848 fprintf (file
, "$\n");
1851 fprintf (file
, "c %s\n", comment
);
1853 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1854 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1855 if (dr_may_alias_p (dr1
, dr2
))
1856 fprintf (file
, "%d %d\n", i
, j
);
1861 /* Check if DR1 and DR2 are in the same object set. */
1864 dr_same_base_object_p (const struct data_reference
*dr1
,
1865 const struct data_reference
*dr2
)
1867 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1870 /* Uses DFS component number as representative of alias-sets. Also tests for
1871 optimality by verifying if every connected component is a clique. Returns
1872 true (1) if the above test is true, and false (0) otherwise. */
1875 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1877 int num_vertices
= VEC_length (data_reference_p
, drs
);
1878 struct graph
*g
= new_graph (num_vertices
);
1879 data_reference_p dr1
, dr2
;
1881 int num_connected_components
;
1882 int v_indx1
, v_indx2
, num_vertices_in_component
;
1885 struct graph_edge
*e
;
1886 int this_component_is_clique
;
1887 int all_components_are_cliques
= 1;
1889 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1890 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1891 if (dr_may_alias_p (dr1
, dr2
))
1897 all_vertices
= XNEWVEC (int, num_vertices
);
1898 vertices
= XNEWVEC (int, num_vertices
);
1899 for (i
= 0; i
< num_vertices
; i
++)
1900 all_vertices
[i
] = i
;
1902 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1904 for (i
= 0; i
< g
->n_vertices
; i
++)
1906 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1907 base_alias_pair
*bap
;
1909 gcc_assert (dr
->aux
);
1910 bap
= (base_alias_pair
*)(dr
->aux
);
1912 bap
->alias_set
= XNEW (int);
1913 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1916 /* Verify if the DFS numbering results in optimal solution. */
1917 for (i
= 0; i
< num_connected_components
; i
++)
1919 num_vertices_in_component
= 0;
1920 /* Get all vertices whose DFS component number is the same as i. */
1921 for (j
= 0; j
< num_vertices
; j
++)
1922 if (g
->vertices
[j
].component
== i
)
1923 vertices
[num_vertices_in_component
++] = j
;
1925 /* Now test if the vertices in 'vertices' form a clique, by testing
1926 for edges among each pair. */
1927 this_component_is_clique
= 1;
1928 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1930 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1932 /* Check if the two vertices are connected by iterating
1933 through all the edges which have one of these are source. */
1934 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1937 if (e
->src
== vertices
[v_indx1
])
1943 this_component_is_clique
= 0;
1947 if (!this_component_is_clique
)
1948 all_components_are_cliques
= 0;
1952 free (all_vertices
);
1955 return all_components_are_cliques
;
1958 /* Group each data reference in DRS with it's base object set num. */
1961 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1963 int num_vertex
= VEC_length (data_reference_p
, drs
);
1964 struct graph
*g
= new_graph (num_vertex
);
1965 data_reference_p dr1
, dr2
;
1969 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr1
)
1970 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1971 if (dr_same_base_object_p (dr1
, dr2
))
1977 queue
= XNEWVEC (int, num_vertex
);
1978 for (i
= 0; i
< num_vertex
; i
++)
1981 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1983 for (i
= 0; i
< g
->n_vertices
; i
++)
1985 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1986 base_alias_pair
*bap
;
1988 gcc_assert (dr
->aux
);
1989 bap
= (base_alias_pair
*)(dr
->aux
);
1991 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1998 /* Build the data references for PBB. */
2001 build_pbb_drs (poly_bb_p pbb
)
2004 data_reference_p dr
;
2005 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2007 FOR_EACH_VEC_ELT (data_reference_p
, gbb_drs
, j
, dr
)
2008 build_poly_dr (dr
, pbb
);
2011 /* Dump to file the alias graphs for the data references in DRS. */
2014 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2017 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2019 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2022 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2023 current_function_name ());
2024 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2025 fclose (file_dimacs
);
2028 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2031 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2032 current_function_name ());
2033 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2037 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2040 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2041 current_function_name ());
2042 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2047 /* Build data references in SCOP. */
2050 build_scop_drs (scop_p scop
)
2054 data_reference_p dr
;
2055 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2057 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2058 for (j
= 0; VEC_iterate (data_reference_p
,
2059 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2060 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2062 FOR_EACH_VEC_ELT (data_reference_p
, drs
, i
, dr
)
2063 dr
->aux
= XNEW (base_alias_pair
);
2065 if (!build_alias_set_optimal_p (drs
))
2067 /* TODO: Add support when building alias set is not optimal. */
2071 build_base_obj_set_for_drs (drs
);
2073 /* When debugging, enable the following code. This cannot be used
2074 in production compilers. */
2076 dump_alias_graphs (drs
);
2078 VEC_free (data_reference_p
, heap
, drs
);
2080 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2081 build_pbb_drs (pbb
);
2084 /* Return a gsi at the position of the phi node STMT. */
2086 static gimple_stmt_iterator
2087 gsi_for_phi_node (gimple stmt
)
2089 gimple_stmt_iterator psi
;
2090 basic_block bb
= gimple_bb (stmt
);
2092 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2093 if (stmt
== gsi_stmt (psi
))
2100 /* Insert the assignment "RES := VAR" just after AFTER_STMT. */
2103 insert_out_of_ssa_copy (tree res
, tree var
, gimple after_stmt
)
2107 gimple_stmt_iterator si
;
2108 gimple_stmt_iterator gsi
;
2110 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2111 stmt
= gimple_build_assign (res
, var
);
2113 stmts
= gimple_seq_alloc ();
2114 si
= gsi_last (stmts
);
2115 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2117 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2119 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2120 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2124 gsi
= gsi_for_stmt (after_stmt
);
2125 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2129 /* Insert on edge E the assignment "RES := EXPR". */
2132 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2134 gimple_stmt_iterator gsi
;
2136 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2137 gimple stmt
= gimple_build_assign (res
, var
);
2140 stmts
= gimple_seq_alloc ();
2142 gsi
= gsi_last (stmts
);
2143 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2144 gsi_insert_seq_on_edge (e
, stmts
);
2145 gsi_commit_edge_inserts ();
2148 /* Creates a zero dimension array of the same type as VAR. */
2151 create_zero_dim_array (tree var
, const char *base_name
)
2153 tree index_type
= build_index_type (integer_zero_node
);
2154 tree elt_type
= TREE_TYPE (var
);
2155 tree array_type
= build_array_type (elt_type
, index_type
);
2156 tree base
= create_tmp_var (array_type
, base_name
);
2158 add_referenced_var (base
);
2160 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2164 /* Returns true when PHI is a loop close phi node. */
2167 scalar_close_phi_node_p (gimple phi
)
2169 if (gimple_code (phi
) != GIMPLE_PHI
2170 || !is_gimple_reg (gimple_phi_result (phi
)))
2173 /* Note that loop close phi nodes should have a single argument
2174 because we translated the representation into a canonical form
2175 before Graphite: see canonicalize_loop_closed_ssa_form. */
2176 return (gimple_phi_num_args (phi
) == 1);
2179 /* For a definition DEF in REGION, propagates the expression EXPR in
2180 all the uses of DEF outside REGION. */
2183 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2185 imm_use_iterator imm_iter
;
2188 bool replaced_once
= false;
2190 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2192 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2195 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2196 if (!is_gimple_debug (use_stmt
)
2197 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2200 use_operand_p use_p
;
2202 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2203 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2204 && (replaced_once
= true))
2205 replace_exp (use_p
, expr
);
2207 update_stmt (use_stmt
);
2212 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2213 gsi_commit_edge_inserts ();
2217 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2218 dimension array for it. */
2221 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
, sese region
)
2223 gimple phi
= gsi_stmt (*psi
);
2224 tree res
= gimple_phi_result (phi
);
2225 tree var
= SSA_NAME_VAR (res
);
2226 basic_block bb
= gimple_bb (phi
);
2227 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2228 tree arg
= gimple_phi_arg_def (phi
, 0);
2231 /* Note that loop close phi nodes should have a single argument
2232 because we translated the representation into a canonical form
2233 before Graphite: see canonicalize_loop_closed_ssa_form. */
2234 gcc_assert (gimple_phi_num_args (phi
) == 1);
2236 /* The phi node can be a non close phi node, when its argument is
2237 invariant, or a default definition. */
2238 if (is_gimple_min_invariant (arg
)
2239 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2241 propagate_expr_outside_region (res
, arg
, region
);
2246 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2248 propagate_expr_outside_region (res
, arg
, region
);
2249 stmt
= gimple_build_assign (res
, arg
);
2250 remove_phi_node (psi
, false);
2251 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2252 SSA_NAME_DEF_STMT (res
) = stmt
;
2256 /* If res is scev analyzable and is not a scalar value, it is safe
2257 to ignore the close phi node: it will be code generated in the
2258 out of Graphite pass. */
2259 else if (scev_analyzable_p (res
, region
))
2261 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2264 if (!loop_in_sese_p (loop
, region
))
2266 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2267 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2268 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2271 scev
= scalar_evolution_in_region (region
, loop
, res
);
2273 if (tree_does_not_contain_chrecs (scev
))
2274 propagate_expr_outside_region (res
, scev
, region
);
2281 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2283 stmt
= gimple_build_assign (res
, zero_dim_array
);
2285 if (TREE_CODE (arg
) == SSA_NAME
)
2286 insert_out_of_ssa_copy (zero_dim_array
, arg
, SSA_NAME_DEF_STMT (arg
));
2288 insert_out_of_ssa_copy_on_edge (single_pred_edge (bb
),
2289 zero_dim_array
, arg
);
2292 remove_phi_node (psi
, false);
2293 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2294 SSA_NAME_DEF_STMT (res
) = stmt
;
2297 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2298 dimension array for it. */
2301 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2304 gimple phi
= gsi_stmt (*psi
);
2305 basic_block bb
= gimple_bb (phi
);
2306 tree res
= gimple_phi_result (phi
);
2307 tree var
= SSA_NAME_VAR (res
);
2308 tree zero_dim_array
= create_zero_dim_array (var
, "phi_out_of_ssa");
2309 gimple_stmt_iterator gsi
;
2313 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2315 tree arg
= gimple_phi_arg_def (phi
, i
);
2316 edge e
= gimple_phi_arg_edge (phi
, i
);
2318 /* Avoid the insertion of code in the loop latch to please the
2319 pattern matching of the vectorizer. */
2320 if (TREE_CODE (arg
) == SSA_NAME
2321 && e
->src
== bb
->loop_father
->latch
)
2322 insert_out_of_ssa_copy (zero_dim_array
, arg
, SSA_NAME_DEF_STMT (arg
));
2324 insert_out_of_ssa_copy_on_edge (e
, zero_dim_array
, arg
);
2327 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2330 stmts
= gimple_seq_alloc ();
2332 stmt
= gimple_build_assign (res
, var
);
2333 remove_phi_node (psi
, false);
2334 SSA_NAME_DEF_STMT (res
) = stmt
;
2336 gsi
= gsi_last (stmts
);
2337 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2339 gsi
= gsi_after_labels (bb
);
2340 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2343 /* Rewrite the degenerate phi node at position PSI from the degenerate
2344 form "x = phi (y, y, ..., y)" to "x = y". */
2347 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2351 gimple_stmt_iterator gsi
;
2352 gimple phi
= gsi_stmt (*psi
);
2353 tree res
= gimple_phi_result (phi
);
2356 bb
= gimple_bb (phi
);
2357 rhs
= degenerate_phi_result (phi
);
2360 stmt
= gimple_build_assign (res
, rhs
);
2361 remove_phi_node (psi
, false);
2362 SSA_NAME_DEF_STMT (res
) = stmt
;
2364 gsi
= gsi_after_labels (bb
);
2365 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2368 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2371 rewrite_reductions_out_of_ssa (scop_p scop
)
2374 gimple_stmt_iterator psi
;
2375 sese region
= SCOP_REGION (scop
);
2378 if (bb_in_sese_p (bb
, region
))
2379 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2381 gimple phi
= gsi_stmt (psi
);
2383 if (!is_gimple_reg (gimple_phi_result (phi
)))
2389 if (gimple_phi_num_args (phi
) > 1
2390 && degenerate_phi_result (phi
))
2391 rewrite_degenerate_phi (&psi
);
2393 else if (scalar_close_phi_node_p (phi
))
2394 rewrite_close_phi_out_of_ssa (&psi
, region
);
2396 else if (reduction_phi_p (region
, &psi
))
2397 rewrite_phi_out_of_ssa (&psi
);
2400 update_ssa (TODO_update_ssa
);
2401 #ifdef ENABLE_CHECKING
2402 verify_loop_closed_ssa (true);
2406 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2407 read from ZERO_DIM_ARRAY. */
2410 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2412 tree var
= SSA_NAME_VAR (def
);
2413 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2414 tree name
= make_ssa_name (var
, name_stmt
);
2416 use_operand_p use_p
;
2417 gimple_stmt_iterator gsi
;
2419 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2421 gimple_assign_set_lhs (name_stmt
, name
);
2423 gsi
= gsi_for_stmt (use_stmt
);
2424 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2426 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2427 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2428 replace_exp (use_p
, name
);
2430 update_stmt (use_stmt
);
2433 /* Rewrite the scalar dependences crossing the boundary of the BB
2434 containing STMT with an array. Return true when something has been
2438 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2440 gimple stmt
= gsi_stmt (*gsi
);
2441 imm_use_iterator imm_iter
;
2444 tree zero_dim_array
= NULL_TREE
;
2448 switch (gimple_code (stmt
))
2451 def
= gimple_assign_lhs (stmt
);
2455 def
= gimple_call_lhs (stmt
);
2463 || !is_gimple_reg (def
))
2466 if (scev_analyzable_p (def
, region
))
2468 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2469 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2471 if (tree_contains_chrecs (scev
, NULL
))
2474 propagate_expr_outside_region (def
, scev
, region
);
2478 def_bb
= gimple_bb (stmt
);
2480 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2481 if (gimple_code (use_stmt
) == GIMPLE_PHI
2484 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2486 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2487 rewrite_close_phi_out_of_ssa (&psi
, region
);
2489 rewrite_phi_out_of_ssa (&psi
);
2492 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2493 if (gimple_code (use_stmt
) != GIMPLE_PHI
2494 && def_bb
!= gimple_bb (use_stmt
)
2495 && !is_gimple_debug (use_stmt
)
2498 if (!zero_dim_array
)
2500 zero_dim_array
= create_zero_dim_array
2501 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2502 insert_out_of_ssa_copy (zero_dim_array
, def
,
2503 SSA_NAME_DEF_STMT (def
));
2507 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2513 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2516 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2519 gimple_stmt_iterator psi
;
2520 sese region
= SCOP_REGION (scop
);
2521 bool changed
= false;
2524 if (bb_in_sese_p (bb
, region
))
2525 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2526 changed
|= rewrite_cross_bb_scalar_deps (region
, &psi
);
2531 update_ssa (TODO_update_ssa
);
2532 #ifdef ENABLE_CHECKING
2533 verify_loop_closed_ssa (true);
2538 /* Returns the number of pbbs that are in loops contained in SCOP. */
2541 nb_pbbs_in_loops (scop_p scop
)
2547 FOR_EACH_VEC_ELT (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
)
2548 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2554 /* Return the number of data references in BB that write in
2558 nb_data_writes_in_bb (basic_block bb
)
2561 gimple_stmt_iterator gsi
;
2563 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2564 if (gimple_vdef (gsi_stmt (gsi
)))
2570 /* Splits STMT out of its current BB. */
2573 split_reduction_stmt (gimple stmt
)
2575 gimple_stmt_iterator gsi
;
2576 basic_block bb
= gimple_bb (stmt
);
2579 /* Do not split basic blocks with no writes to memory: the reduction
2580 will be the only write to memory. */
2581 if (nb_data_writes_in_bb (bb
) == 0)
2584 split_block (bb
, stmt
);
2586 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2589 gsi
= gsi_last_bb (bb
);
2591 e
= split_block (bb
, gsi_stmt (gsi
));
2596 /* Return true when stmt is a reduction operation. */
2599 is_reduction_operation_p (gimple stmt
)
2601 enum tree_code code
;
2603 gcc_assert (is_gimple_assign (stmt
));
2604 code
= gimple_assign_rhs_code (stmt
);
2606 return flag_associative_math
2607 && commutative_tree_code (code
)
2608 && associative_tree_code (code
);
2611 /* Returns true when PHI contains an argument ARG. */
2614 phi_contains_arg (gimple phi
, tree arg
)
2618 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2619 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2625 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2628 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2632 if (TREE_CODE (arg
) != SSA_NAME
)
2635 stmt
= SSA_NAME_DEF_STMT (arg
);
2637 if (gimple_code (stmt
) == GIMPLE_NOP
2638 || gimple_code (stmt
) == GIMPLE_CALL
)
2641 if (gimple_code (stmt
) == GIMPLE_PHI
)
2643 if (phi_contains_arg (stmt
, lhs
))
2648 if (!is_gimple_assign (stmt
))
2651 if (gimple_num_ops (stmt
) == 2)
2652 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2654 if (is_reduction_operation_p (stmt
))
2656 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2659 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2665 /* Detect commutative and associative scalar reductions starting at
2666 the STMT. Return the phi node of the reduction cycle, or NULL. */
2669 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2670 VEC (gimple
, heap
) **in
,
2671 VEC (gimple
, heap
) **out
)
2673 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2678 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2679 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2683 /* Detect commutative and associative scalar reductions starting at
2684 STMT. Return the phi node of the reduction cycle, or NULL. */
2687 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2688 VEC (gimple
, heap
) **out
)
2690 tree lhs
= gimple_assign_lhs (stmt
);
2692 if (gimple_num_ops (stmt
) == 2)
2693 return detect_commutative_reduction_arg (lhs
, stmt
,
2694 gimple_assign_rhs1 (stmt
),
2697 if (is_reduction_operation_p (stmt
))
2699 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2700 gimple_assign_rhs1 (stmt
),
2703 : detect_commutative_reduction_arg (lhs
, stmt
,
2704 gimple_assign_rhs2 (stmt
),
2711 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2714 follow_inital_value_to_phi (tree arg
, tree lhs
)
2718 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2721 stmt
= SSA_NAME_DEF_STMT (arg
);
2723 if (gimple_code (stmt
) == GIMPLE_PHI
2724 && phi_contains_arg (stmt
, lhs
))
2731 /* Return the argument of the loop PHI that is the inital value coming
2732 from outside the loop. */
2735 edge_initial_value_for_loop_phi (gimple phi
)
2739 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2741 edge e
= gimple_phi_arg_edge (phi
, i
);
2743 if (loop_depth (e
->src
->loop_father
)
2744 < loop_depth (e
->dest
->loop_father
))
2751 /* Return the argument of the loop PHI that is the inital value coming
2752 from outside the loop. */
2755 initial_value_for_loop_phi (gimple phi
)
2759 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2761 edge e
= gimple_phi_arg_edge (phi
, i
);
2763 if (loop_depth (e
->src
->loop_father
)
2764 < loop_depth (e
->dest
->loop_father
))
2765 return gimple_phi_arg_def (phi
, i
);
2771 /* Detect commutative and associative scalar reductions starting at
2772 the loop closed phi node STMT. Return the phi node of the
2773 reduction cycle, or NULL. */
2776 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2777 VEC (gimple
, heap
) **out
)
2779 if (scalar_close_phi_node_p (stmt
))
2781 tree arg
= gimple_phi_arg_def (stmt
, 0);
2782 gimple def
, loop_phi
;
2784 if (TREE_CODE (arg
) != SSA_NAME
)
2787 /* Note that loop close phi nodes should have a single argument
2788 because we translated the representation into a canonical form
2789 before Graphite: see canonicalize_loop_closed_ssa_form. */
2790 gcc_assert (gimple_phi_num_args (stmt
) == 1);
2792 def
= SSA_NAME_DEF_STMT (arg
);
2793 loop_phi
= detect_commutative_reduction (def
, in
, out
);
2797 tree lhs
= gimple_phi_result (stmt
);
2798 tree init
= initial_value_for_loop_phi (loop_phi
);
2799 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2801 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2802 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2809 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2810 return detect_commutative_reduction_assign (stmt
, in
, out
);
2815 /* Translate the scalar reduction statement STMT to an array RED
2816 knowing that its recursive phi node is LOOP_PHI. */
2819 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2822 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2823 tree res
= gimple_phi_result (loop_phi
);
2824 gimple assign
= gimple_build_assign (res
, red
);
2826 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2828 insert_gsi
= gsi_after_labels (gimple_bb (stmt
));
2829 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2830 insert_gsi
= gsi_for_stmt (stmt
);
2831 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2834 /* Removes the PHI node and resets all the debug stmts that are using
2838 remove_phi (gimple phi
)
2840 imm_use_iterator imm_iter
;
2842 use_operand_p use_p
;
2843 gimple_stmt_iterator gsi
;
2844 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2848 def
= PHI_RESULT (phi
);
2849 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2851 stmt
= USE_STMT (use_p
);
2853 if (is_gimple_debug (stmt
))
2855 gimple_debug_bind_reset_value (stmt
);
2856 VEC_safe_push (gimple
, heap
, update
, stmt
);
2860 FOR_EACH_VEC_ELT (gimple
, update
, i
, stmt
)
2863 VEC_free (gimple
, heap
, update
);
2865 gsi
= gsi_for_phi_node (phi
);
2866 remove_phi_node (&gsi
, false);
2869 /* Rewrite out of SSA the reduction described by the loop phi nodes
2870 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2873 IN: stmt, loop_n, ..., loop_0
2874 OUT: stmt, close_n, ..., close_0
2876 the first element is the reduction statement, and the next elements
2877 are the loop and close phi nodes of each of the outer loops. */
2880 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2881 VEC (gimple
, heap
) *out
,
2886 tree red
= NULL_TREE
;
2888 FOR_EACH_VEC_ELT (gimple
, in
, i
, loop_phi
)
2890 gimple close_phi
= VEC_index (gimple
, out
, i
);
2894 gimple stmt
= loop_phi
;
2895 basic_block bb
= split_reduction_stmt (stmt
);
2897 SET_BIT (reductions
, bb
->index
);
2898 gcc_assert (close_phi
== loop_phi
);
2900 red
= create_zero_dim_array
2901 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2902 translate_scalar_reduction_to_array_for_stmt
2903 (red
, stmt
, VEC_index (gimple
, in
, 1));
2907 if (i
== VEC_length (gimple
, in
) - 1)
2909 insert_out_of_ssa_copy (gimple_phi_result (close_phi
), red
,
2911 insert_out_of_ssa_copy_on_edge
2912 (edge_initial_value_for_loop_phi (loop_phi
),
2913 red
, initial_value_for_loop_phi (loop_phi
));
2916 remove_phi (loop_phi
);
2917 remove_phi (close_phi
);
2921 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
2922 true when something has been changed. */
2925 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2929 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2930 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2932 detect_commutative_reduction (close_phi
, &in
, &out
);
2933 res
= VEC_length (gimple
, in
) > 0;
2935 translate_scalar_reduction_to_array (in
, out
, reductions
);
2937 VEC_free (gimple
, heap
, in
);
2938 VEC_free (gimple
, heap
, out
);
2942 /* Rewrites all the commutative reductions from LOOP out of SSA.
2943 Returns true when something has been changed. */
2946 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2950 gimple_stmt_iterator gsi
;
2951 edge exit
= single_exit (loop
);
2953 bool changed
= false;
2958 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2959 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
2960 && is_gimple_reg (res
)
2961 && !scev_analyzable_p (res
, region
))
2962 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
2963 (gsi_stmt (gsi
), reductions
);
2968 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2971 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2975 bool changed
= false;
2977 if (!flag_associative_math
)
2980 FOR_EACH_LOOP (li
, loop
, 0)
2981 if (loop_in_sese_p (loop
, region
))
2982 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (loop
,
2989 gsi_commit_edge_inserts ();
2990 update_ssa (TODO_update_ssa
);
2991 #ifdef ENABLE_CHECKING
2992 verify_loop_closed_ssa (true);
2997 /* Java does not initialize long_long_integer_type_node. */
2998 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
3000 /* Can all ivs be represented by a signed integer?
3001 As CLooG might generate negative values in its expressions, signed loop ivs
3002 are required in the backend. */
3005 scop_ivs_can_be_represented (scop_p scop
)
3009 gimple_stmt_iterator psi
;
3011 FOR_EACH_LOOP (li
, loop
, 0)
3013 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3016 for (psi
= gsi_start_phis (loop
->header
);
3017 !gsi_end_p (psi
); gsi_next (&psi
))
3019 gimple phi
= gsi_stmt (psi
);
3020 tree res
= PHI_RESULT (phi
);
3021 tree type
= TREE_TYPE (res
);
3023 if (TYPE_UNSIGNED (type
)
3024 && TYPE_PRECISION (type
) >= TYPE_PRECISION (my_long_long
))
3034 /* Builds the polyhedral representation for a SESE region. */
3037 build_poly_scop (scop_p scop
)
3039 sese region
= SCOP_REGION (scop
);
3040 graphite_dim_t max_dim
;
3043 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3044 Once CLooG is fixed, remove this guard. Anyways, it makes no
3045 sense to optimize a scop containing only PBBs that do not belong
3047 if (nb_pbbs_in_loops (scop
) == 0)
3050 if (!scop_ivs_can_be_represented (scop
))
3053 build_sese_loop_nests (region
);
3054 build_sese_conditions (region
);
3055 find_scop_parameters (scop
);
3057 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3058 if (scop_nb_params (scop
) > max_dim
)
3061 build_scop_iteration_domain (scop
);
3062 build_scop_context (scop
);
3064 add_conditions_to_constraints (scop
);
3066 build_scop_scattering (scop
);
3067 build_scop_drs (scop
);
3069 /* This SCoP has been translated to the polyhedral
3071 POLY_SCOP_P (scop
) = true;