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"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-sese-to-poly.h"
55 /* Check if VAR is used in a phi node, that is no loop header. */
58 var_used_in_not_loop_header_phi_node (tree var
)
60 imm_use_iterator imm_iter
;
64 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
66 basic_block bb
= gimple_bb (stmt
);
68 if (gimple_code (stmt
) == GIMPLE_PHI
69 && bb
->loop_father
->header
!= bb
)
76 /* Returns the index of the phi argument corresponding to the initial
80 loop_entry_phi_arg (gimple phi
)
82 loop_p loop
= gimple_bb (phi
)->loop_father
;
85 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
86 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
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
= loop_entry_phi_arg (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
= loop_entry_phi_arg (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
)
170 gimple phi
= gsi_stmt (*psi
);
171 tree res
= gimple_phi_result (phi
);
173 if (!is_gimple_reg (res
))
179 loop
= loop_containing_stmt (phi
);
181 if (simple_copy_phi_p (phi
))
183 /* PRE introduces phi nodes like these, for an example,
184 see id-5.f in the fortran graphite testsuite:
186 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
188 remove_simple_copy_phi (psi
);
192 /* Main induction variables with constant strides in LOOP are not
194 if (simple_iv (loop
, loop
, res
, &iv
, true))
196 if (integer_zerop (iv
.step
))
197 remove_invariant_phi (region
, psi
);
204 scev
= scalar_evolution_in_region (region
, loop
, res
);
205 if (chrec_contains_undetermined (scev
))
208 if (evolution_function_is_invariant_p (scev
, loop
->num
))
210 remove_invariant_phi (region
, psi
);
214 /* All the other cases are considered reductions. */
218 /* Returns true when BB will be represented in graphite. Return false
219 for the basic blocks that contain code eliminated in the code
220 generation pass: i.e. induction variables and exit conditions. */
223 graphite_stmt_p (sese region
, basic_block bb
,
224 VEC (data_reference_p
, heap
) *drs
)
226 gimple_stmt_iterator gsi
;
227 loop_p loop
= bb
->loop_father
;
229 if (VEC_length (data_reference_p
, drs
) > 0)
232 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
234 gimple stmt
= gsi_stmt (gsi
);
236 switch (gimple_code (stmt
))
239 /* Control flow expressions can be ignored, as they are
240 represented in the iteration domains and will be
241 regenerated by graphite. */
249 tree var
= gimple_assign_lhs (stmt
);
251 /* We need these bbs to be able to construct the phi nodes. */
252 if (var_used_in_not_loop_header_phi_node (var
))
255 var
= scalar_evolution_in_region (region
, loop
, var
);
256 if (chrec_contains_undetermined (var
))
270 /* Store the GRAPHITE representation of BB. */
273 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
275 struct gimple_bb
*gbb
;
277 gbb
= XNEW (struct gimple_bb
);
280 GBB_DATA_REFS (gbb
) = drs
;
281 GBB_CONDITIONS (gbb
) = NULL
;
282 GBB_CONDITION_CASES (gbb
) = NULL
;
288 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
291 struct data_reference
*dr
;
293 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
296 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
299 free (bap
->alias_set
);
308 free_gimple_bb (struct gimple_bb
*gbb
)
310 free_data_refs_aux (GBB_DATA_REFS (gbb
));
311 free_data_refs (GBB_DATA_REFS (gbb
));
313 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
314 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
315 GBB_BB (gbb
)->aux
= 0;
319 /* Deletes all gimple bbs in SCOP. */
322 remove_gbbs_in_scop (scop_p scop
)
327 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
328 free_gimple_bb (PBB_BLACK_BOX (pbb
));
331 /* Deletes all scops in SCOPS. */
334 free_scops (VEC (scop_p
, heap
) *scops
)
339 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
341 remove_gbbs_in_scop (scop
);
342 free_sese (SCOP_REGION (scop
));
346 VEC_free (scop_p
, heap
, scops
);
349 /* Generates a polyhedral black box only if the bb contains interesting
353 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
355 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
356 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
357 gimple_stmt_iterator gsi
;
359 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
361 gimple stmt
= gsi_stmt (gsi
);
362 if (!is_gimple_debug (stmt
))
363 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
366 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
367 free_data_refs (drs
);
369 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
373 /* Returns true if all predecessors of BB, that are not dominated by BB, are
374 marked in MAP. The predecessors dominated by BB are loop latches and will
375 be handled after BB. */
378 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
383 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
384 if (!TEST_BIT (map
, e
->src
->index
)
385 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
391 /* Compare the depth of two basic_block's P1 and P2. */
394 compare_bb_depths (const void *p1
, const void *p2
)
396 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
397 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
398 int d1
= loop_depth (bb1
->loop_father
);
399 int d2
= loop_depth (bb2
->loop_father
);
410 /* Sort the basic blocks from DOM such that the first are the ones at
411 a deepest loop level. */
414 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
416 size_t len
= VEC_length (basic_block
, dom
);
418 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
422 /* Recursive helper function for build_scops_bbs. */
425 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
427 sese region
= SCOP_REGION (scop
);
428 VEC (basic_block
, heap
) *dom
;
430 if (TEST_BIT (visited
, bb
->index
)
431 || !bb_in_sese_p (bb
, region
))
434 try_generate_gimple_bb (scop
, bb
, reductions
);
435 SET_BIT (visited
, bb
->index
);
437 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
442 graphite_sort_dominated_info (dom
);
444 while (!VEC_empty (basic_block
, dom
))
449 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
450 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
452 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
453 VEC_unordered_remove (basic_block
, dom
, i
);
458 VEC_free (basic_block
, heap
, dom
);
461 /* Gather the basic blocks belonging to the SCOP. */
464 build_scop_bbs (scop_p scop
, sbitmap reductions
)
466 sbitmap visited
= sbitmap_alloc (last_basic_block
);
467 sese region
= SCOP_REGION (scop
);
469 sbitmap_zero (visited
);
470 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
471 sbitmap_free (visited
);
474 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
475 We generate SCATTERING_DIMENSIONS scattering dimensions.
477 CLooG 0.15.0 and previous versions require, that all
478 scattering functions of one CloogProgram have the same number of
479 scattering dimensions, therefore we allow to specify it. This
480 should be removed in future versions of CLooG.
482 The scattering polyhedron consists of these dimensions: scattering,
483 loop_iterators, parameters.
487 | scattering_dimensions = 5
488 | used_scattering_dimensions = 3
496 | Scattering polyhedron:
498 | scattering: {s1, s2, s3, s4, s5}
499 | loop_iterators: {i}
500 | parameters: {p1, p2}
502 | s1 s2 s3 s4 s5 i p1 p2 1
503 | 1 0 0 0 0 0 0 0 -4 = 0
504 | 0 1 0 0 0 -1 0 0 0 = 0
505 | 0 0 1 0 0 0 0 0 -5 = 0 */
508 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
509 poly_bb_p pbb
, int scattering_dimensions
)
512 scop_p scop
= PBB_SCOP (pbb
);
513 int nb_iterators
= pbb_dim_iter_domain (pbb
);
514 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
515 int nb_params
= scop_nb_params (scop
);
517 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
520 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
523 ppl_new_Coefficient (&c
);
524 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
525 ppl_new_C_Polyhedron_from_space_dimension
526 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
528 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
530 for (i
= 0; i
< scattering_dimensions
; i
++)
532 ppl_Constraint_t cstr
;
533 ppl_Linear_Expression_t expr
;
535 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
537 ppl_assign_Coefficient_from_mpz_t (c
, v
);
538 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
540 /* Textual order inside this loop. */
543 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
544 ppl_Coefficient_to_mpz_t (c
, v
);
546 ppl_assign_Coefficient_from_mpz_t (c
, v
);
547 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
550 /* Iterations of this loop. */
551 else /* if ((i % 2) == 1) */
553 int loop
= (i
- 1) / 2;
556 ppl_assign_Coefficient_from_mpz_t (c
, v
);
557 ppl_Linear_Expression_add_to_coefficient
558 (expr
, scattering_dimensions
+ loop
, c
);
561 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
562 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
563 ppl_delete_Linear_Expression (expr
);
564 ppl_delete_Constraint (cstr
);
568 ppl_delete_Coefficient (c
);
570 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
573 /* Build for BB the static schedule.
575 The static schedule is a Dewey numbering of the abstract syntax
576 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
578 The following example informally defines the static schedule:
597 Static schedules for A to F:
610 build_scop_scattering (scop_p scop
)
614 gimple_bb_p previous_gbb
= NULL
;
615 ppl_Linear_Expression_t static_schedule
;
620 ppl_new_Coefficient (&c
);
621 ppl_new_Linear_Expression (&static_schedule
);
623 /* We have to start schedules at 0 on the first component and
624 because we cannot compare_prefix_loops against a previous loop,
625 prefix will be equal to zero, and that index will be
626 incremented before copying. */
628 ppl_assign_Coefficient_from_mpz_t (c
, v
);
629 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
631 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
633 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
634 ppl_Linear_Expression_t common
;
636 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
639 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
644 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
645 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
649 ppl_assign_Coefficient_from_mpz_t (c
, v
);
650 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
651 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
654 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
656 ppl_delete_Linear_Expression (common
);
660 ppl_delete_Coefficient (c
);
661 ppl_delete_Linear_Expression (static_schedule
);
664 /* Add the value K to the dimension D of the linear expression EXPR. */
667 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
671 ppl_Coefficient_t coef
;
673 ppl_new_Coefficient (&coef
);
674 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
676 ppl_Coefficient_to_mpz_t (coef
, val
);
678 mpz_add (val
, val
, k
);
680 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
681 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
683 ppl_delete_Coefficient (coef
);
686 /* In the context of scop S, scan E, the right hand side of a scalar
687 evolution function in loop VAR, and translate it to a linear
691 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
692 ppl_Linear_Expression_t expr
)
696 loop_p loop
= get_loop (var
);
697 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
700 /* Scalar evolutions should happen in the sese region. */
701 gcc_assert (sese_loop_depth (s
, loop
) > 0);
703 /* We can not deal with parametric strides like:
709 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
712 mpz_set_si (val
, int_cst_value (e
));
713 add_value_to_dim (l
, expr
, val
);
718 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
719 linear expression EXPR. K is the multiplier of the constant. */
722 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, mpz_t k
)
725 ppl_Coefficient_t coef
;
726 int v
= int_cst_value (cst
);
731 /* Necessary to not get "-1 = 2^n - 1". */
733 mpz_sub_ui (val
, val
, -v
);
735 mpz_add_ui (val
, val
, v
);
737 mpz_mul (val
, val
, k
);
738 ppl_new_Coefficient (&coef
);
739 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
740 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
742 ppl_delete_Coefficient (coef
);
745 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
746 Otherwise returns -1. */
749 parameter_index_in_region_1 (tree name
, sese region
)
754 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
756 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
763 /* When the parameter NAME is in REGION, returns its index in
764 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
765 and returns the index of NAME. */
768 parameter_index_in_region (tree name
, sese region
)
772 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
774 i
= parameter_index_in_region_1 (name
, region
);
778 gcc_assert (SESE_ADD_PARAMS (region
));
780 i
= VEC_length (tree
, SESE_PARAMS (region
));
781 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
785 /* In the context of sese S, scan the expression E and translate it to
786 a linear expression C. When parsing a symbolic multiplication, K
787 represents the constant multiplier of an expression containing
791 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
794 if (e
== chrec_dont_know
)
797 switch (TREE_CODE (e
))
799 case POLYNOMIAL_CHREC
:
800 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
801 CHREC_VARIABLE (e
), c
);
802 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
806 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
811 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
813 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
814 mpz_mul (val
, val
, k
);
815 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
819 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
826 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
828 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
829 mpz_mul (val
, val
, k
);
830 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
834 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
839 case POINTER_PLUS_EXPR
:
840 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
841 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
846 ppl_Linear_Expression_t tmp_expr
= NULL
;
850 ppl_dimension_type dim
;
851 ppl_Linear_Expression_space_dimension (c
, &dim
);
852 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
855 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
856 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
860 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
862 ppl_delete_Linear_Expression (tmp_expr
);
870 ppl_Linear_Expression_t tmp_expr
= NULL
;
874 ppl_dimension_type dim
;
875 ppl_Linear_Expression_space_dimension (c
, &dim
);
876 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
879 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
883 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
885 ppl_delete_Linear_Expression (tmp_expr
);
893 ppl_Linear_Expression_t tmp_expr
= NULL
;
897 ppl_dimension_type dim
;
898 ppl_Linear_Expression_space_dimension (c
, &dim
);
899 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
902 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
906 ppl_Coefficient_t coef
;
909 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
911 ppl_delete_Linear_Expression (tmp_expr
);
912 mpz_init (minus_one
);
913 mpz_set_si (minus_one
, -1);
914 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
915 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
916 mpz_clear (minus_one
);
917 ppl_delete_Coefficient (coef
);
925 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
929 ppl_dimension_type dim
;
930 ppl_Linear_Expression_space_dimension (c
, &dim
);
931 p
+= dim
- sese_nb_params (s
);
932 add_value_to_dim (p
, c
, k
);
939 scan_tree_for_params_int (e
, c
, k
);
943 case NON_LVALUE_EXPR
:
944 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
953 /* Find parameters with respect to REGION in BB. We are looking in memory
954 access functions, conditions and loop bounds. */
957 find_params_in_bb (sese region
, gimple_bb_p gbb
)
963 loop_p loop
= GBB_BB (gbb
)->loop_father
;
969 /* Find parameters in the access functions of data references. */
970 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
971 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
972 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
974 /* Find parameters in conditional statements. */
975 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
977 tree lhs
= scalar_evolution_in_region (region
, loop
,
978 gimple_cond_lhs (stmt
));
979 tree rhs
= scalar_evolution_in_region (region
, loop
,
980 gimple_cond_rhs (stmt
));
982 scan_tree_for_params (region
, lhs
, NULL
, one
);
983 scan_tree_for_params (region
, rhs
, NULL
, one
);
989 /* Record the parameters used in the SCOP. A variable is a parameter
990 in a scop if it does not vary during the execution of that scop. */
993 find_scop_parameters (scop_p scop
)
997 sese region
= SCOP_REGION (scop
);
1002 mpz_set_si (one
, 1);
1004 /* Find the parameters used in the loop bounds. */
1005 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1007 tree nb_iters
= number_of_latch_executions (loop
);
1009 if (!chrec_contains_symbols (nb_iters
))
1012 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1013 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1018 /* Find the parameters used in data accesses. */
1019 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1020 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1022 scop_set_nb_params (scop
, sese_nb_params (region
));
1023 SESE_ADD_PARAMS (region
) = false;
1025 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1026 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1029 /* Returns a gimple_bb from BB. */
1031 static inline gimple_bb_p
1032 gbb_from_bb (basic_block bb
)
1034 return (gimple_bb_p
) bb
->aux
;
1037 /* Insert in the SCOP context constraints from the estimation of the
1038 number of iterations. UB_EXPR is a linear expression describing
1039 the number of iterations in a loop. This expression is bounded by
1040 the estimation NIT. */
1043 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
1044 ppl_dimension_type dim
,
1045 ppl_Linear_Expression_t ub_expr
)
1048 ppl_Linear_Expression_t nb_iters_le
;
1049 ppl_Polyhedron_t pol
;
1050 ppl_Coefficient_t coef
;
1051 ppl_Constraint_t ub
;
1053 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1054 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1055 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1058 /* Construct the negated number of last iteration in VAL. */
1060 mpz_set_double_int (val
, nit
, false);
1061 mpz_sub_ui (val
, val
, 1);
1064 /* NB_ITERS_LE holds the number of last iteration in
1065 parametrical form. Subtract estimated number of last
1066 iteration and assert that result is not positive. */
1067 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1068 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1069 ppl_delete_Coefficient (coef
);
1070 ppl_new_Constraint (&ub
, nb_iters_le
,
1071 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1072 ppl_Polyhedron_add_constraint (pol
, ub
);
1074 /* Remove all but last GDIM dimensions from POL to obtain
1075 only the constraints on the parameters. */
1077 graphite_dim_t gdim
= scop_nb_params (scop
);
1078 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
1081 for (i
= 0; i
< dim
- gdim
; i
++)
1084 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
1088 /* Add the constraints on the parameters to the SCoP context. */
1090 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1092 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1093 (&constraints_ps
, pol
);
1094 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1095 (SCOP_CONTEXT (scop
), constraints_ps
);
1096 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1099 ppl_delete_Polyhedron (pol
);
1100 ppl_delete_Linear_Expression (nb_iters_le
);
1101 ppl_delete_Constraint (ub
);
1105 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1106 the constraints for the surrounding loops. */
1109 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1110 ppl_Polyhedron_t outer_ph
, int nb
,
1111 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1114 ppl_Polyhedron_t ph
;
1115 tree nb_iters
= number_of_latch_executions (loop
);
1116 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1117 sese region
= SCOP_REGION (scop
);
1120 ppl_const_Constraint_System_t pcs
;
1121 ppl_dimension_type
*map
1122 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1124 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1125 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1126 ppl_Polyhedron_add_constraints (ph
, pcs
);
1128 for (i
= 0; i
< (int) nb
; i
++)
1130 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1134 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1140 ppl_Constraint_t lb
;
1141 ppl_Linear_Expression_t lb_expr
;
1143 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1144 ppl_set_coef (lb_expr
, nb
, 1);
1145 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1146 ppl_delete_Linear_Expression (lb_expr
);
1147 ppl_Polyhedron_add_constraint (ph
, lb
);
1148 ppl_delete_Constraint (lb
);
1151 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1153 ppl_Constraint_t ub
;
1154 ppl_Linear_Expression_t ub_expr
;
1156 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1158 /* loop_i <= cst_nb_iters */
1159 ppl_set_coef (ub_expr
, nb
, -1);
1160 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1161 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1162 ppl_Polyhedron_add_constraint (ph
, ub
);
1163 ppl_delete_Linear_Expression (ub_expr
);
1164 ppl_delete_Constraint (ub
);
1166 else if (!chrec_contains_undetermined (nb_iters
))
1169 ppl_Constraint_t ub
;
1170 ppl_Linear_Expression_t ub_expr
;
1174 mpz_set_si (one
, 1);
1175 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1176 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1177 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1180 if (estimated_loop_iterations (loop
, true, &nit
))
1181 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1183 /* loop_i <= expr_nb_iters */
1184 ppl_set_coef (ub_expr
, nb
, -1);
1185 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1186 ppl_Polyhedron_add_constraint (ph
, ub
);
1187 ppl_delete_Linear_Expression (ub_expr
);
1188 ppl_delete_Constraint (ub
);
1193 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1194 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1198 && loop_in_sese_p (loop
->next
, region
))
1199 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1201 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1202 (&domains
[loop
->num
], ph
);
1204 ppl_delete_Polyhedron (ph
);
1207 /* Returns a linear expression for tree T evaluated in PBB. */
1209 static ppl_Linear_Expression_t
1210 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1213 ppl_Linear_Expression_t res
;
1214 ppl_dimension_type dim
;
1215 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1216 loop_p loop
= pbb_loop (pbb
);
1218 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1219 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1221 t
= scalar_evolution_in_region (region
, loop
, t
);
1222 gcc_assert (!automatically_generated_chrec_p (t
));
1225 mpz_set_si (one
, 1);
1226 scan_tree_for_params (region
, t
, res
, one
);
1232 /* Returns the ppl constraint type from the gimple tree code CODE. */
1234 static enum ppl_enum_Constraint_Type
1235 ppl_constraint_type_from_tree_code (enum tree_code code
)
1239 /* We do not support LT and GT to be able to work with C_Polyhedron.
1240 As we work on integer polyhedron "a < b" can be expressed by
1247 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1250 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1253 return PPL_CONSTRAINT_TYPE_EQUAL
;
1260 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1261 CODE is used as the comparison operator. This allows us to invert the
1262 condition or to handle inequalities. */
1265 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1266 poly_bb_p pbb
, enum tree_code code
)
1269 ppl_Coefficient_t c
;
1270 ppl_Linear_Expression_t left
, right
;
1271 ppl_Constraint_t cstr
;
1272 enum ppl_enum_Constraint_Type type
;
1274 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1275 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1277 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1278 the left or the right side of the expression. */
1279 if (code
== LT_EXPR
)
1283 ppl_new_Coefficient (&c
);
1284 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1285 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1286 ppl_delete_Coefficient (c
);
1291 else if (code
== GT_EXPR
)
1295 ppl_new_Coefficient (&c
);
1296 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1297 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1298 ppl_delete_Coefficient (c
);
1304 type
= ppl_constraint_type_from_tree_code (code
);
1306 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1308 ppl_new_Constraint (&cstr
, left
, type
);
1309 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1311 ppl_delete_Constraint (cstr
);
1312 ppl_delete_Linear_Expression (left
);
1313 ppl_delete_Linear_Expression (right
);
1316 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1317 operator. This allows us to invert the condition or to handle
1321 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1323 if (code
== NE_EXPR
)
1325 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1326 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1327 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1329 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1330 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1331 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
, right
);
1332 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1335 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1338 /* Add conditions to the domain of PBB. */
1341 add_conditions_to_domain (poly_bb_p pbb
)
1345 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1347 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1350 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
1351 switch (gimple_code (stmt
))
1355 enum tree_code code
= gimple_cond_code (stmt
);
1357 /* The conditions for ELSE-branches are inverted. */
1358 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1359 code
= invert_tree_comparison (code
, false);
1361 add_condition_to_pbb (pbb
, stmt
, code
);
1366 /* Switch statements are not supported right now - fall throught. */
1374 /* Structure used to pass data to dom_walk. */
1378 VEC (gimple
, heap
) **conditions
, **cases
;
1382 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1383 edge between BB and its predecessor is not a loop exit edge, and
1384 the last statement of the single predecessor is a COND_EXPR. */
1387 single_pred_cond_non_loop_exit (basic_block bb
)
1389 if (single_pred_p (bb
))
1391 edge e
= single_pred_edge (bb
);
1392 basic_block pred
= e
->src
;
1395 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1398 stmt
= last_stmt (pred
);
1400 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1407 /* Call-back for dom_walk executed before visiting the dominated
1411 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1414 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1415 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1416 VEC (gimple
, heap
) **cases
= data
->cases
;
1420 if (!bb_in_sese_p (bb
, data
->region
))
1423 stmt
= single_pred_cond_non_loop_exit (bb
);
1427 edge e
= single_pred_edge (bb
);
1429 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1431 if (e
->flags
& EDGE_TRUE_VALUE
)
1432 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1434 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1437 gbb
= gbb_from_bb (bb
);
1441 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1442 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1446 /* Call-back for dom_walk executed after visiting the dominated
1450 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1453 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1454 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1455 VEC (gimple
, heap
) **cases
= data
->cases
;
1457 if (!bb_in_sese_p (bb
, data
->region
))
1460 if (single_pred_cond_non_loop_exit (bb
))
1462 VEC_pop (gimple
, *conditions
);
1463 VEC_pop (gimple
, *cases
);
1467 /* Record all conditions in REGION. */
1470 build_sese_conditions (sese region
)
1472 struct dom_walk_data walk_data
;
1473 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1474 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1477 data
.conditions
= &conditions
;
1478 data
.cases
= &cases
;
1479 data
.region
= region
;
1481 walk_data
.dom_direction
= CDI_DOMINATORS
;
1482 walk_data
.initialize_block_local_data
= NULL
;
1483 walk_data
.before_dom_children
= build_sese_conditions_before
;
1484 walk_data
.after_dom_children
= build_sese_conditions_after
;
1485 walk_data
.global_data
= &data
;
1486 walk_data
.block_local_data_size
= 0;
1488 init_walk_dominator_tree (&walk_data
);
1489 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1490 fini_walk_dominator_tree (&walk_data
);
1492 VEC_free (gimple
, heap
, conditions
);
1493 VEC_free (gimple
, heap
, cases
);
1496 /* Traverses all the GBBs of the SCOP and add their constraints to the
1497 iteration domains. */
1500 add_conditions_to_constraints (scop_p scop
)
1505 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1506 add_conditions_to_domain (pbb
);
1509 /* Add constraints on the possible values of parameter P from the type
1513 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1515 ppl_Constraint_t cstr
;
1516 ppl_Linear_Expression_t le
;
1517 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1518 tree type
= TREE_TYPE (parameter
);
1519 tree lb
= NULL_TREE
;
1520 tree ub
= NULL_TREE
;
1522 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1523 lb
= lower_bound_in_type (type
, type
);
1525 lb
= TYPE_MIN_VALUE (type
);
1527 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1528 ub
= upper_bound_in_type (type
, type
);
1530 ub
= TYPE_MAX_VALUE (type
);
1534 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1535 ppl_set_coef (le
, p
, -1);
1536 ppl_set_inhomogeneous_tree (le
, lb
);
1537 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1538 ppl_Polyhedron_add_constraint (context
, cstr
);
1539 ppl_delete_Linear_Expression (le
);
1540 ppl_delete_Constraint (cstr
);
1545 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1546 ppl_set_coef (le
, p
, -1);
1547 ppl_set_inhomogeneous_tree (le
, ub
);
1548 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1549 ppl_Polyhedron_add_constraint (context
, cstr
);
1550 ppl_delete_Linear_Expression (le
);
1551 ppl_delete_Constraint (cstr
);
1555 /* Build the context of the SCOP. The context usually contains extra
1556 constraints that are added to the iteration domains that constrain
1560 build_scop_context (scop_p scop
)
1562 ppl_Polyhedron_t context
;
1563 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1564 graphite_dim_t p
, n
= scop_nb_params (scop
);
1566 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1568 for (p
= 0; p
< n
; p
++)
1569 add_param_constraints (scop
, context
, p
);
1571 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1573 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1574 (SCOP_CONTEXT (scop
), ps
);
1576 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1577 ppl_delete_Polyhedron (context
);
1580 /* Build the iteration domains: the loops belonging to the current
1581 SCOP, and that vary for the execution of the current basic block.
1582 Returns false if there is no loop in SCOP. */
1585 build_scop_iteration_domain (scop_p scop
)
1588 sese region
= SCOP_REGION (scop
);
1590 ppl_Polyhedron_t ph
;
1592 int nb_loops
= number_of_loops ();
1593 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1594 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1596 for (i
= 0; i
< nb_loops
; i
++)
1599 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1601 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1602 if (!loop_in_sese_p (loop_outer (loop
), region
))
1603 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1605 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1606 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1607 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1608 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1609 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1611 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1612 (&PBB_DOMAIN (pbb
), ph
);
1614 for (i
= 0; i
< nb_loops
; i
++)
1616 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1618 ppl_delete_Polyhedron (ph
);
1622 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1623 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1624 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1628 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1629 ppl_dimension_type accessp_nb_dims
,
1630 ppl_dimension_type dom_nb_dims
)
1632 ppl_Linear_Expression_t alias
;
1633 ppl_Constraint_t cstr
;
1634 int alias_set_num
= 0;
1635 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1637 if (bap
&& bap
->alias_set
)
1638 alias_set_num
= *(bap
->alias_set
);
1640 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1642 ppl_set_coef (alias
, dom_nb_dims
, 1);
1643 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1644 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1645 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1647 ppl_delete_Linear_Expression (alias
);
1648 ppl_delete_Constraint (cstr
);
1651 /* Add to ACCESSES polyhedron equalities defining the access functions
1652 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1653 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1654 PBB is the poly_bb_p that contains the data reference DR. */
1657 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1658 ppl_dimension_type accessp_nb_dims
,
1659 ppl_dimension_type dom_nb_dims
,
1662 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1664 scop_p scop
= PBB_SCOP (pbb
);
1665 sese region
= SCOP_REGION (scop
);
1669 for (i
= 0; i
< nb_subscripts
; i
++)
1671 ppl_Linear_Expression_t fn
, access
;
1672 ppl_Constraint_t cstr
;
1673 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1674 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1676 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1677 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1680 scan_tree_for_params (region
, afn
, fn
, v
);
1681 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1683 ppl_set_coef (access
, subscript
, -1);
1684 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1685 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1687 ppl_delete_Linear_Expression (fn
);
1688 ppl_delete_Linear_Expression (access
);
1689 ppl_delete_Constraint (cstr
);
1695 /* Add constrains representing the size of the accessed data to the
1696 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1697 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1701 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1702 ppl_dimension_type accessp_nb_dims
,
1703 ppl_dimension_type dom_nb_dims
)
1705 tree ref
= DR_REF (dr
);
1706 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1708 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1710 ppl_Linear_Expression_t expr
;
1711 ppl_Constraint_t cstr
;
1712 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1715 if (TREE_CODE (ref
) != ARRAY_REF
)
1718 low
= array_ref_low_bound (ref
);
1720 /* subscript - low >= 0 */
1721 if (host_integerp (low
, 0))
1723 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1724 ppl_set_coef (expr
, subscript
, 1);
1726 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1728 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1729 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1730 ppl_delete_Linear_Expression (expr
);
1731 ppl_delete_Constraint (cstr
);
1734 high
= array_ref_up_bound (ref
);
1736 /* high - subscript >= 0 */
1737 if (high
&& host_integerp (high
, 0)
1738 /* 1-element arrays at end of structures may extend over
1739 their declared size. */
1740 && !(array_at_struct_end_p (ref
)
1741 && operand_equal_p (low
, high
, 0)))
1743 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1744 ppl_set_coef (expr
, subscript
, -1);
1746 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1748 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1749 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1750 ppl_delete_Linear_Expression (expr
);
1751 ppl_delete_Constraint (cstr
);
1756 /* Build data accesses for DR in PBB. */
1759 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1761 ppl_Polyhedron_t accesses
;
1762 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1763 ppl_dimension_type dom_nb_dims
;
1764 ppl_dimension_type accessp_nb_dims
;
1765 int dr_base_object_set
;
1767 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1769 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1771 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1773 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1774 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1775 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1777 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1779 ppl_delete_Polyhedron (accesses
);
1781 gcc_assert (dr
->aux
);
1782 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1784 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
,
1785 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1786 dr
, DR_NUM_DIMENSIONS (dr
));
1789 /* Write to FILE the alias graph of data references in DIMACS format. */
1792 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1793 VEC (data_reference_p
, heap
) *drs
)
1795 int num_vertex
= VEC_length (data_reference_p
, drs
);
1797 data_reference_p dr1
, dr2
;
1800 if (num_vertex
== 0)
1803 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1804 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1805 if (dr_may_alias_p (dr1
, dr2
))
1808 fprintf (file
, "$\n");
1811 fprintf (file
, "c %s\n", comment
);
1813 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1815 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1816 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1817 if (dr_may_alias_p (dr1
, dr2
))
1818 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1823 /* Write to FILE the alias graph of data references in DOT format. */
1826 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1827 VEC (data_reference_p
, heap
) *drs
)
1829 int num_vertex
= VEC_length (data_reference_p
, drs
);
1830 data_reference_p dr1
, dr2
;
1833 if (num_vertex
== 0)
1836 fprintf (file
, "$\n");
1839 fprintf (file
, "c %s\n", comment
);
1841 /* First print all the vertices. */
1842 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1843 fprintf (file
, "n%d;\n", i
);
1845 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1846 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1847 if (dr_may_alias_p (dr1
, dr2
))
1848 fprintf (file
, "n%d n%d\n", i
, j
);
1853 /* Write to FILE the alias graph of data references in ECC format. */
1856 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1857 VEC (data_reference_p
, heap
) *drs
)
1859 int num_vertex
= VEC_length (data_reference_p
, drs
);
1860 data_reference_p dr1
, dr2
;
1863 if (num_vertex
== 0)
1866 fprintf (file
, "$\n");
1869 fprintf (file
, "c %s\n", comment
);
1871 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1872 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1873 if (dr_may_alias_p (dr1
, dr2
))
1874 fprintf (file
, "%d %d\n", i
, j
);
1879 /* Check if DR1 and DR2 are in the same object set. */
1882 dr_same_base_object_p (const struct data_reference
*dr1
,
1883 const struct data_reference
*dr2
)
1885 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1888 /* Uses DFS component number as representative of alias-sets. Also tests for
1889 optimality by verifying if every connected component is a clique. Returns
1890 true (1) if the above test is true, and false (0) otherwise. */
1893 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1895 int num_vertices
= VEC_length (data_reference_p
, drs
);
1896 struct graph
*g
= new_graph (num_vertices
);
1897 data_reference_p dr1
, dr2
;
1899 int num_connected_components
;
1900 int v_indx1
, v_indx2
, num_vertices_in_component
;
1903 struct graph_edge
*e
;
1904 int this_component_is_clique
;
1905 int all_components_are_cliques
= 1;
1907 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1908 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1909 if (dr_may_alias_p (dr1
, dr2
))
1915 all_vertices
= XNEWVEC (int, num_vertices
);
1916 vertices
= XNEWVEC (int, num_vertices
);
1917 for (i
= 0; i
< num_vertices
; i
++)
1918 all_vertices
[i
] = i
;
1920 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1922 for (i
= 0; i
< g
->n_vertices
; i
++)
1924 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1925 base_alias_pair
*bap
;
1927 gcc_assert (dr
->aux
);
1928 bap
= (base_alias_pair
*)(dr
->aux
);
1930 bap
->alias_set
= XNEW (int);
1931 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1934 /* Verify if the DFS numbering results in optimal solution. */
1935 for (i
= 0; i
< num_connected_components
; i
++)
1937 num_vertices_in_component
= 0;
1938 /* Get all vertices whose DFS component number is the same as i. */
1939 for (j
= 0; j
< num_vertices
; j
++)
1940 if (g
->vertices
[j
].component
== i
)
1941 vertices
[num_vertices_in_component
++] = j
;
1943 /* Now test if the vertices in 'vertices' form a clique, by testing
1944 for edges among each pair. */
1945 this_component_is_clique
= 1;
1946 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1948 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1950 /* Check if the two vertices are connected by iterating
1951 through all the edges which have one of these are source. */
1952 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1955 if (e
->src
== vertices
[v_indx1
])
1961 this_component_is_clique
= 0;
1965 if (!this_component_is_clique
)
1966 all_components_are_cliques
= 0;
1970 free (all_vertices
);
1973 return all_components_are_cliques
;
1976 /* Group each data reference in DRS with it's base object set num. */
1979 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1981 int num_vertex
= VEC_length (data_reference_p
, drs
);
1982 struct graph
*g
= new_graph (num_vertex
);
1983 data_reference_p dr1
, dr2
;
1987 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1988 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1989 if (dr_same_base_object_p (dr1
, dr2
))
1995 queue
= XNEWVEC (int, num_vertex
);
1996 for (i
= 0; i
< num_vertex
; i
++)
1999 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
2001 for (i
= 0; i
< g
->n_vertices
; i
++)
2003 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
2004 base_alias_pair
*bap
;
2006 gcc_assert (dr
->aux
);
2007 bap
= (base_alias_pair
*)(dr
->aux
);
2009 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2016 /* Build the data references for PBB. */
2019 build_pbb_drs (poly_bb_p pbb
)
2022 data_reference_p dr
;
2023 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2025 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2026 build_poly_dr (dr
, pbb
);
2029 /* Dump to file the alias graphs for the data references in DRS. */
2032 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2035 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2037 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2040 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2041 current_function_name ());
2042 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2043 fclose (file_dimacs
);
2046 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2049 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2050 current_function_name ());
2051 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2055 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2058 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2059 current_function_name ());
2060 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2065 /* Build data references in SCOP. */
2068 build_scop_drs (scop_p scop
)
2072 data_reference_p dr
;
2073 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2075 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2076 for (j
= 0; VEC_iterate (data_reference_p
,
2077 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2078 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2080 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2081 dr
->aux
= XNEW (base_alias_pair
);
2083 if (!build_alias_set_optimal_p (drs
))
2085 /* TODO: Add support when building alias set is not optimal. */
2089 build_base_obj_set_for_drs (drs
);
2091 /* When debugging, enable the following code. This cannot be used
2092 in production compilers. */
2094 dump_alias_graphs (drs
);
2096 VEC_free (data_reference_p
, heap
, drs
);
2098 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2099 build_pbb_drs (pbb
);
2102 /* Return a gsi at the position of the phi node STMT. */
2104 static gimple_stmt_iterator
2105 gsi_for_phi_node (gimple stmt
)
2107 gimple_stmt_iterator psi
;
2108 basic_block bb
= gimple_bb (stmt
);
2110 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2111 if (stmt
== gsi_stmt (psi
))
2118 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2121 insert_out_of_ssa_copy (tree res
, tree var
)
2125 gimple_stmt_iterator si
;
2126 gimple_stmt_iterator gsi
;
2128 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2129 stmt
= gimple_build_assign (res
, var
);
2131 stmts
= gimple_seq_alloc ();
2132 si
= gsi_last (stmts
);
2133 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2135 stmt
= SSA_NAME_DEF_STMT (var
);
2136 if (gimple_code (stmt
) == GIMPLE_PHI
)
2138 gsi
= gsi_after_labels (gimple_bb (stmt
));
2139 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2143 gsi
= gsi_for_stmt (stmt
);
2144 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2148 /* Insert on edge E the assignment "RES := EXPR". */
2151 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2153 gimple_stmt_iterator gsi
;
2155 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2156 gimple stmt
= gimple_build_assign (res
, var
);
2159 stmts
= gimple_seq_alloc ();
2161 gsi
= gsi_last (stmts
);
2162 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2163 gsi_insert_seq_on_edge (e
, stmts
);
2164 gsi_commit_edge_inserts ();
2167 /* Creates a zero dimension array of the same type as VAR. */
2170 create_zero_dim_array (tree var
, const char *base_name
)
2172 tree index_type
= build_index_type (integer_zero_node
);
2173 tree elt_type
= TREE_TYPE (var
);
2174 tree array_type
= build_array_type (elt_type
, index_type
);
2175 tree base
= create_tmp_var (array_type
, base_name
);
2177 add_referenced_var (base
);
2179 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2183 /* Returns true when PHI is a loop close phi node. */
2186 scalar_close_phi_node_p (gimple phi
)
2188 if (gimple_code (phi
) != GIMPLE_PHI
2189 || !is_gimple_reg (gimple_phi_result (phi
)))
2192 /* Note that loop close phi nodes should have a single argument
2193 because we translated the representation into a canonical form
2194 before Graphite: see canonicalize_loop_closed_ssa_form. */
2195 return (gimple_phi_num_args (phi
) == 1);
2198 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2199 dimension array for it. */
2202 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2204 gimple phi
= gsi_stmt (*psi
);
2205 tree res
= gimple_phi_result (phi
);
2206 tree var
= SSA_NAME_VAR (res
);
2207 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2208 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2209 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2210 tree arg
= gimple_phi_arg_def (phi
, 0);
2212 /* Note that loop close phi nodes should have a single argument
2213 because we translated the representation into a canonical form
2214 before Graphite: see canonicalize_loop_closed_ssa_form. */
2215 gcc_assert (gimple_phi_num_args (phi
) == 1);
2217 if (TREE_CODE (arg
) == SSA_NAME
2218 && !SSA_NAME_IS_DEFAULT_DEF (arg
))
2219 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2221 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi
)),
2222 zero_dim_array
, arg
);
2224 remove_phi_node (psi
, false);
2225 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2226 SSA_NAME_DEF_STMT (res
) = stmt
;
2229 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2230 dimension array for it. */
2233 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2236 gimple phi
= gsi_stmt (*psi
);
2237 basic_block bb
= gimple_bb (phi
);
2238 tree res
= gimple_phi_result (phi
);
2239 tree var
= SSA_NAME_VAR (res
);
2240 tree zero_dim_array
= create_zero_dim_array (var
, "General_Reduction");
2241 gimple_stmt_iterator gsi
;
2245 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2247 tree arg
= gimple_phi_arg_def (phi
, i
);
2249 /* Try to avoid the insertion on edges as much as possible: this
2250 would avoid the insertion of code on loop latch edges, making
2251 the pattern matching of the vectorizer happy, or it would
2252 avoid the insertion of useless basic blocks. Note that it is
2253 incorrect to insert out of SSA copies close by their
2254 definition when they are more than two loop levels apart:
2255 for example, starting from a double nested loop
2265 the following transform is incorrect
2277 whereas inserting the copy on the incoming edge is correct
2289 if (TREE_CODE (arg
) == SSA_NAME
2290 && is_gimple_reg (arg
)
2291 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2292 && (flow_bb_inside_loop_p (bb
->loop_father
,
2293 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2294 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2295 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2296 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2298 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2299 zero_dim_array
, arg
);
2302 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2305 stmts
= gimple_seq_alloc ();
2307 stmt
= gimple_build_assign (res
, var
);
2308 remove_phi_node (psi
, false);
2309 SSA_NAME_DEF_STMT (res
) = stmt
;
2311 gsi
= gsi_last (stmts
);
2312 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2314 gsi
= gsi_after_labels (bb
);
2315 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2318 /* Return true when DEF can be analyzed in REGION by the scalar
2319 evolution analyzer. */
2322 scev_analyzable_p (tree def
, sese region
)
2324 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2325 loop_p loop
= loop_containing_stmt (stmt
);
2326 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2328 return !chrec_contains_undetermined (scev
);
2331 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2332 read from ZERO_DIM_ARRAY. */
2335 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2337 tree var
= SSA_NAME_VAR (def
);
2338 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2339 tree name
= make_ssa_name (var
, name_stmt
);
2341 use_operand_p use_p
;
2342 gimple_stmt_iterator gsi
;
2344 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2346 gimple_assign_set_lhs (name_stmt
, name
);
2348 gsi
= gsi_for_stmt (use_stmt
);
2349 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2351 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2352 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2353 replace_exp (use_p
, name
);
2355 update_stmt (use_stmt
);
2358 /* Rewrite the scalar dependences crossing the boundary of the BB
2359 containing STMT with an array. */
2362 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2364 gimple stmt
= gsi_stmt (*gsi
);
2365 imm_use_iterator imm_iter
;
2368 tree zero_dim_array
= NULL_TREE
;
2371 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2374 def
= gimple_assign_lhs (stmt
);
2375 if (!is_gimple_reg (def
)
2376 || scev_analyzable_p (def
, region
))
2379 def_bb
= gimple_bb (stmt
);
2381 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2382 if (def_bb
!= gimple_bb (use_stmt
)
2383 && gimple_code (use_stmt
) != GIMPLE_PHI
2384 && !is_gimple_debug (use_stmt
))
2386 if (!zero_dim_array
)
2388 zero_dim_array
= create_zero_dim_array
2389 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2390 insert_out_of_ssa_copy (zero_dim_array
, def
);
2394 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2398 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2401 rewrite_reductions_out_of_ssa (scop_p scop
)
2404 gimple_stmt_iterator psi
;
2405 sese region
= SCOP_REGION (scop
);
2408 if (bb_in_sese_p (bb
, region
))
2409 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2411 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2412 rewrite_close_phi_out_of_ssa (&psi
);
2413 else if (reduction_phi_p (region
, &psi
))
2414 rewrite_phi_out_of_ssa (&psi
);
2417 update_ssa (TODO_update_ssa
);
2418 #ifdef ENABLE_CHECKING
2419 verify_loop_closed_ssa (true);
2423 if (bb_in_sese_p (bb
, region
))
2424 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2425 rewrite_cross_bb_scalar_deps (region
, &psi
);
2427 update_ssa (TODO_update_ssa
);
2428 #ifdef ENABLE_CHECKING
2429 verify_loop_closed_ssa (true);
2433 /* Returns the number of pbbs that are in loops contained in SCOP. */
2436 nb_pbbs_in_loops (scop_p scop
)
2442 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2443 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2449 /* Return the number of data references in BB that write in
2453 nb_data_writes_in_bb (basic_block bb
)
2456 gimple_stmt_iterator gsi
;
2458 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2459 if (gimple_vdef (gsi_stmt (gsi
)))
2465 /* Splits STMT out of its current BB. */
2468 split_reduction_stmt (gimple stmt
)
2470 gimple_stmt_iterator gsi
;
2471 basic_block bb
= gimple_bb (stmt
);
2474 /* Do not split basic blocks with no writes to memory: the reduction
2475 will be the only write to memory. */
2476 if (nb_data_writes_in_bb (bb
) == 0)
2479 split_block (bb
, stmt
);
2481 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2484 gsi
= gsi_last_bb (bb
);
2486 e
= split_block (bb
, gsi_stmt (gsi
));
2491 /* Return true when stmt is a reduction operation. */
2494 is_reduction_operation_p (gimple stmt
)
2496 enum tree_code code
;
2498 gcc_assert (is_gimple_assign (stmt
));
2499 code
= gimple_assign_rhs_code (stmt
);
2501 return flag_associative_math
2502 && commutative_tree_code (code
)
2503 && associative_tree_code (code
);
2506 /* Returns true when PHI contains an argument ARG. */
2509 phi_contains_arg (gimple phi
, tree arg
)
2513 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2514 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2520 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2523 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2527 if (TREE_CODE (arg
) != SSA_NAME
)
2530 stmt
= SSA_NAME_DEF_STMT (arg
);
2532 if (gimple_code (stmt
) == GIMPLE_NOP
2533 || gimple_code (stmt
) == GIMPLE_CALL
)
2536 if (gimple_code (stmt
) == GIMPLE_PHI
)
2538 if (phi_contains_arg (stmt
, lhs
))
2543 if (!is_gimple_assign (stmt
))
2546 if (gimple_num_ops (stmt
) == 2)
2547 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2549 if (is_reduction_operation_p (stmt
))
2551 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2554 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2560 /* Detect commutative and associative scalar reductions starting at
2561 the STMT. Return the phi node of the reduction cycle, or NULL. */
2564 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2565 VEC (gimple
, heap
) **in
,
2566 VEC (gimple
, heap
) **out
)
2568 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2573 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2574 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2578 /* Detect commutative and associative scalar reductions starting at
2579 the STMT. Return the phi node of the reduction cycle, or NULL. */
2582 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2583 VEC (gimple
, heap
) **out
)
2585 tree lhs
= gimple_assign_lhs (stmt
);
2587 if (gimple_num_ops (stmt
) == 2)
2588 return detect_commutative_reduction_arg (lhs
, stmt
,
2589 gimple_assign_rhs1 (stmt
),
2592 if (is_reduction_operation_p (stmt
))
2594 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2595 gimple_assign_rhs1 (stmt
),
2598 : detect_commutative_reduction_arg (lhs
, stmt
,
2599 gimple_assign_rhs2 (stmt
),
2606 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2609 follow_inital_value_to_phi (tree arg
, tree lhs
)
2613 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2616 stmt
= SSA_NAME_DEF_STMT (arg
);
2618 if (gimple_code (stmt
) == GIMPLE_PHI
2619 && phi_contains_arg (stmt
, lhs
))
2626 /* Return the argument of the loop PHI that is the inital value coming
2627 from outside the loop. */
2630 edge_initial_value_for_loop_phi (gimple phi
)
2634 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2636 edge e
= gimple_phi_arg_edge (phi
, i
);
2638 if (loop_depth (e
->src
->loop_father
)
2639 < loop_depth (e
->dest
->loop_father
))
2646 /* Return the argument of the loop PHI that is the inital value coming
2647 from outside the loop. */
2650 initial_value_for_loop_phi (gimple phi
)
2654 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2656 edge e
= gimple_phi_arg_edge (phi
, i
);
2658 if (loop_depth (e
->src
->loop_father
)
2659 < loop_depth (e
->dest
->loop_father
))
2660 return gimple_phi_arg_def (phi
, i
);
2666 /* Detect commutative and associative scalar reductions starting at
2667 the loop closed phi node CLOSE_PHI. Return the phi node of the
2668 reduction cycle, or NULL. */
2671 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2672 VEC (gimple
, heap
) **out
)
2674 if (scalar_close_phi_node_p (stmt
))
2676 tree arg
= gimple_phi_arg_def (stmt
, 0);
2677 gimple def
, loop_phi
;
2679 if (TREE_CODE (arg
) != SSA_NAME
)
2682 /* Note that loop close phi nodes should have a single argument
2683 because we translated the representation into a canonical form
2684 before Graphite: see canonicalize_loop_closed_ssa_form. */
2685 gcc_assert (gimple_phi_num_args (stmt
) == 1);
2687 def
= SSA_NAME_DEF_STMT (arg
);
2688 loop_phi
= detect_commutative_reduction (def
, in
, out
);
2692 tree lhs
= gimple_phi_result (stmt
);
2693 tree init
= initial_value_for_loop_phi (loop_phi
);
2694 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2696 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2697 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2704 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2705 return detect_commutative_reduction_assign (stmt
, in
, out
);
2710 /* Translate the scalar reduction statement STMT to an array RED
2711 knowing that its recursive phi node is LOOP_PHI. */
2714 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2717 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2718 tree res
= gimple_phi_result (loop_phi
);
2719 gimple assign
= gimple_build_assign (res
, red
);
2721 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2723 insert_gsi
= gsi_after_labels (gimple_bb (stmt
));
2724 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2725 insert_gsi
= gsi_for_stmt (stmt
);
2726 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2729 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2732 insert_copyout (tree red
, gimple close_phi
)
2734 tree res
= gimple_phi_result (close_phi
);
2735 basic_block bb
= gimple_bb (close_phi
);
2736 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2737 gimple assign
= gimple_build_assign (res
, red
);
2739 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2742 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2745 insert_copyin (tree red
, gimple loop_phi
)
2748 tree init
= initial_value_for_loop_phi (loop_phi
);
2749 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2751 force_gimple_operand (expr
, &stmts
, true, NULL
);
2752 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2755 /* Removes the PHI node and resets all the debug stmts that are using
2759 remove_phi (gimple phi
)
2761 imm_use_iterator imm_iter
;
2763 use_operand_p use_p
;
2764 gimple_stmt_iterator gsi
;
2765 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2769 def
= PHI_RESULT (phi
);
2770 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2772 stmt
= USE_STMT (use_p
);
2774 if (is_gimple_debug (stmt
))
2776 gimple_debug_bind_reset_value (stmt
);
2777 VEC_safe_push (gimple
, heap
, update
, stmt
);
2781 for (i
= 0; VEC_iterate (gimple
, update
, i
, stmt
); i
++)
2784 VEC_free (gimple
, heap
, update
);
2786 gsi
= gsi_for_phi_node (phi
);
2787 remove_phi_node (&gsi
, false);
2790 /* Rewrite out of SSA the reduction described by the loop phi nodes
2791 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2794 IN: stmt, loop_n, ..., loop_0
2795 OUT: stmt, close_n, ..., close_0
2797 the first element is the reduction statement, and the next elements
2798 are the loop and close phi nodes of each of the outer loops. */
2801 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2802 VEC (gimple
, heap
) *out
,
2807 tree red
= NULL_TREE
;
2809 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2811 gimple close_phi
= VEC_index (gimple
, out
, i
);
2815 gimple stmt
= loop_phi
;
2816 basic_block bb
= split_reduction_stmt (stmt
);
2818 SET_BIT (reductions
, bb
->index
);
2819 gcc_assert (close_phi
== loop_phi
);
2821 red
= create_zero_dim_array
2822 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2823 translate_scalar_reduction_to_array_for_stmt
2824 (red
, stmt
, VEC_index (gimple
, in
, 1));
2828 if (i
== VEC_length (gimple
, in
) - 1)
2830 insert_copyout (red
, close_phi
);
2831 insert_copyin (red
, loop_phi
);
2834 remove_phi (loop_phi
);
2835 remove_phi (close_phi
);
2839 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2842 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2845 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2846 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2848 detect_commutative_reduction (close_phi
, &in
, &out
);
2849 if (VEC_length (gimple
, in
) > 0)
2850 translate_scalar_reduction_to_array (in
, out
, reductions
);
2852 VEC_free (gimple
, heap
, in
);
2853 VEC_free (gimple
, heap
, out
);
2856 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2859 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2862 gimple_stmt_iterator gsi
;
2863 edge exit
= single_exit (loop
);
2868 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2869 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2873 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2876 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2881 FOR_EACH_LOOP (li
, loop
, 0)
2882 if (loop_in_sese_p (loop
, region
))
2883 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2885 gsi_commit_edge_inserts ();
2886 update_ssa (TODO_update_ssa
);
2887 #ifdef ENABLE_CHECKING
2888 verify_loop_closed_ssa (true);
2892 /* A LOOP is in normal form for Graphite when it contains only one
2893 scalar phi node that defines the main induction variable of the
2894 loop, only one increment of the IV, and only one exit condition. */
2897 graphite_loop_normal_form (loop_p loop
)
2899 struct tree_niter_desc niter
;
2902 edge exit
= single_dom_exit (loop
);
2904 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2906 /* At this point we should know the number of iterations. */
2907 gcc_assert (known_niter
);
2909 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2912 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2914 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
, false);
2917 /* Rewrite all the loops of SCOP in normal form: one induction
2918 variable per loop. */
2921 scop_canonicalize_loops (scop_p scop
)
2926 FOR_EACH_LOOP (li
, loop
, 0)
2927 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2928 graphite_loop_normal_form (loop
);
2931 /* Java does not initialize long_long_integer_type_node. */
2932 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2934 /* Can all ivs be represented by a signed integer?
2935 As CLooG might generate negative values in its expressions, signed loop ivs
2936 are required in the backend. */
2939 scop_ivs_can_be_represented (scop_p scop
)
2944 FOR_EACH_LOOP (li
, loop
, 0)
2949 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2952 if (!loop
->single_iv
)
2955 type
= TREE_TYPE (loop
->single_iv
);
2956 precision
= TYPE_PRECISION (type
);
2958 if (TYPE_UNSIGNED (type
)
2959 && precision
>= TYPE_PRECISION (my_long_long
))
2968 /* Builds the polyhedral representation for a SESE region. */
2971 build_poly_scop (scop_p scop
)
2973 sese region
= SCOP_REGION (scop
);
2974 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2975 graphite_dim_t max_dim
;
2977 sbitmap_zero (reductions
);
2978 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2979 rewrite_reductions_out_of_ssa (scop
);
2980 build_scop_bbs (scop
, reductions
);
2981 sbitmap_free (reductions
);
2983 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2984 Once CLooG is fixed, remove this guard. Anyways, it makes no
2985 sense to optimize a scop containing only PBBs that do not belong
2987 if (nb_pbbs_in_loops (scop
) == 0)
2990 scop_canonicalize_loops (scop
);
2991 if (!scop_ivs_can_be_represented (scop
))
2994 build_sese_loop_nests (region
);
2995 build_sese_conditions (region
);
2996 find_scop_parameters (scop
);
2998 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2999 if (scop_nb_params (scop
) > max_dim
)
3002 build_scop_iteration_domain (scop
);
3003 build_scop_context (scop
);
3005 add_conditions_to_constraints (scop
);
3007 build_scop_scattering (scop
);
3008 build_scop_drs (scop
);
3010 /* This SCoP has been translated to the polyhedral
3012 POLY_SCOP_P (scop
) = true;
3015 /* Always return false. Exercise the scop_to_clast function. */
3018 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
3020 #ifdef ENABLE_CHECKING
3021 cloog_prog_clast pc
= scop_to_clast (scop
);
3022 cloog_clast_free (pc
.stmt
);
3023 cloog_program_free (pc
.prog
);