1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009 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 /* FIXME: 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
;
283 GBB_CLOOG_IV_TYPES (gbb
) = NULL
;
289 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
292 struct data_reference
*dr
;
294 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
297 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
300 free (bap
->alias_set
);
309 free_gimple_bb (struct gimple_bb
*gbb
)
311 if (GBB_CLOOG_IV_TYPES (gbb
))
312 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
314 free_data_refs_aux (GBB_DATA_REFS (gbb
));
315 free_data_refs (GBB_DATA_REFS (gbb
));
317 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
318 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
319 GBB_BB (gbb
)->aux
= 0;
323 /* Deletes all gimple bbs in SCOP. */
326 remove_gbbs_in_scop (scop_p scop
)
331 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
332 free_gimple_bb (PBB_BLACK_BOX (pbb
));
335 /* Deletes all scops in SCOPS. */
338 free_scops (VEC (scop_p
, heap
) *scops
)
343 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
345 remove_gbbs_in_scop (scop
);
346 free_sese (SCOP_REGION (scop
));
350 VEC_free (scop_p
, heap
, scops
);
353 /* Generates a polyhedral black box only if the bb contains interesting
357 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
359 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
360 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
361 gimple_stmt_iterator gsi
;
363 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
365 gimple stmt
= gsi_stmt (gsi
);
366 if (!is_gimple_debug (stmt
))
367 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
370 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
371 free_data_refs (drs
);
373 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
377 /* Returns true if all predecessors of BB, that are not dominated by BB, are
378 marked in MAP. The predecessors dominated by BB are loop latches and will
379 be handled after BB. */
382 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
387 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
388 if (!TEST_BIT (map
, e
->src
->index
)
389 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
395 /* Compare the depth of two basic_block's P1 and P2. */
398 compare_bb_depths (const void *p1
, const void *p2
)
400 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
401 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
402 int d1
= loop_depth (bb1
->loop_father
);
403 int d2
= loop_depth (bb2
->loop_father
);
414 /* Sort the basic blocks from DOM such that the first are the ones at
415 a deepest loop level. */
418 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
420 size_t len
= VEC_length (basic_block
, dom
);
422 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
426 /* Recursive helper function for build_scops_bbs. */
429 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
431 sese region
= SCOP_REGION (scop
);
432 VEC (basic_block
, heap
) *dom
;
434 if (TEST_BIT (visited
, bb
->index
)
435 || !bb_in_sese_p (bb
, region
))
438 try_generate_gimple_bb (scop
, bb
, reductions
);
439 SET_BIT (visited
, bb
->index
);
441 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
446 graphite_sort_dominated_info (dom
);
448 while (!VEC_empty (basic_block
, dom
))
453 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
454 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
456 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
457 VEC_unordered_remove (basic_block
, dom
, i
);
462 VEC_free (basic_block
, heap
, dom
);
465 /* Gather the basic blocks belonging to the SCOP. */
468 build_scop_bbs (scop_p scop
, sbitmap reductions
)
470 sbitmap visited
= sbitmap_alloc (last_basic_block
);
471 sese region
= SCOP_REGION (scop
);
473 sbitmap_zero (visited
);
474 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
475 sbitmap_free (visited
);
478 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
479 We generate SCATTERING_DIMENSIONS scattering dimensions.
481 CLooG 0.15.0 and previous versions require, that all
482 scattering functions of one CloogProgram have the same number of
483 scattering dimensions, therefore we allow to specify it. This
484 should be removed in future versions of CLooG.
486 The scattering polyhedron consists of these dimensions: scattering,
487 loop_iterators, parameters.
491 | scattering_dimensions = 5
492 | used_scattering_dimensions = 3
500 | Scattering polyhedron:
502 | scattering: {s1, s2, s3, s4, s5}
503 | loop_iterators: {i}
504 | parameters: {p1, p2}
506 | s1 s2 s3 s4 s5 i p1 p2 1
507 | 1 0 0 0 0 0 0 0 -4 = 0
508 | 0 1 0 0 0 -1 0 0 0 = 0
509 | 0 0 1 0 0 0 0 0 -5 = 0 */
512 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
513 poly_bb_p pbb
, int scattering_dimensions
)
516 scop_p scop
= PBB_SCOP (pbb
);
517 int nb_iterators
= pbb_dim_iter_domain (pbb
);
518 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
519 int nb_params
= scop_nb_params (scop
);
521 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
524 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
527 ppl_new_Coefficient (&c
);
528 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
529 ppl_new_C_Polyhedron_from_space_dimension
530 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
532 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
534 for (i
= 0; i
< scattering_dimensions
; i
++)
536 ppl_Constraint_t cstr
;
537 ppl_Linear_Expression_t expr
;
539 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
541 ppl_assign_Coefficient_from_mpz_t (c
, v
);
542 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
544 /* Textual order inside this loop. */
547 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
548 ppl_Coefficient_to_mpz_t (c
, v
);
550 ppl_assign_Coefficient_from_mpz_t (c
, v
);
551 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
554 /* Iterations of this loop. */
555 else /* if ((i % 2) == 1) */
557 int loop
= (i
- 1) / 2;
559 value_set_si (v
, -1);
560 ppl_assign_Coefficient_from_mpz_t (c
, v
);
561 ppl_Linear_Expression_add_to_coefficient
562 (expr
, scattering_dimensions
+ loop
, c
);
565 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
566 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
567 ppl_delete_Linear_Expression (expr
);
568 ppl_delete_Constraint (cstr
);
572 ppl_delete_Coefficient (c
);
574 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
577 /* Build for BB the static schedule.
579 The static schedule is a Dewey numbering of the abstract syntax
580 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
582 The following example informally defines the static schedule:
601 Static schedules for A to F:
614 build_scop_scattering (scop_p scop
)
618 gimple_bb_p previous_gbb
= NULL
;
619 ppl_Linear_Expression_t static_schedule
;
624 ppl_new_Coefficient (&c
);
625 ppl_new_Linear_Expression (&static_schedule
);
627 /* We have to start schedules at 0 on the first component and
628 because we cannot compare_prefix_loops against a previous loop,
629 prefix will be equal to zero, and that index will be
630 incremented before copying. */
631 value_set_si (v
, -1);
632 ppl_assign_Coefficient_from_mpz_t (c
, v
);
633 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
635 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
637 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
638 ppl_Linear_Expression_t common
;
640 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
643 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
648 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
649 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
653 ppl_assign_Coefficient_from_mpz_t (c
, v
);
654 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
655 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
658 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
660 ppl_delete_Linear_Expression (common
);
664 ppl_delete_Coefficient (c
);
665 ppl_delete_Linear_Expression (static_schedule
);
668 /* Add the value K to the dimension D of the linear expression EXPR. */
671 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
675 ppl_Coefficient_t coef
;
677 ppl_new_Coefficient (&coef
);
678 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
680 ppl_Coefficient_to_mpz_t (coef
, val
);
682 value_addto (val
, val
, k
);
684 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
685 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
687 ppl_delete_Coefficient (coef
);
690 /* In the context of scop S, scan E, the right hand side of a scalar
691 evolution function in loop VAR, and translate it to a linear
695 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
696 ppl_Linear_Expression_t expr
)
700 loop_p loop
= get_loop (var
);
701 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
704 /* Scalar evolutions should happen in the sese region. */
705 gcc_assert (sese_loop_depth (s
, loop
) > 0);
707 /* We can not deal with parametric strides like:
713 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
716 value_set_si (val
, int_cst_value (e
));
717 add_value_to_dim (l
, expr
, val
);
722 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
723 linear expression EXPR. K is the multiplier of the constant. */
726 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
729 ppl_Coefficient_t coef
;
730 int v
= int_cst_value (cst
);
733 value_set_si (val
, 0);
735 /* Necessary to not get "-1 = 2^n - 1". */
737 value_sub_int (val
, val
, -v
);
739 value_add_int (val
, val
, v
);
741 value_multiply (val
, val
, k
);
742 ppl_new_Coefficient (&coef
);
743 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
744 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
746 ppl_delete_Coefficient (coef
);
749 /* Saves in NV at index I a new name for variable P. */
752 save_var_name (char **nv
, int i
, tree p
)
754 const char *name
= get_name (SSA_NAME_VAR (p
));
758 int len
= strlen (name
) + 16;
759 nv
[i
] = XNEWVEC (char, len
);
760 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
764 nv
[i
] = XNEWVEC (char, 16);
765 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
769 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
770 Otherwise returns -1. */
773 parameter_index_in_region_1 (tree name
, sese region
)
778 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
780 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
787 /* When the parameter NAME is in REGION, returns its index in
788 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
789 and returns the index of NAME. */
792 parameter_index_in_region (tree name
, sese region
)
796 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
798 i
= parameter_index_in_region_1 (name
, region
);
802 gcc_assert (SESE_ADD_PARAMS (region
));
804 i
= VEC_length (tree
, SESE_PARAMS (region
));
805 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
806 save_clast_name_index (SESE_PARAMS_INDEX (region
),
807 SESE_PARAMS_NAMES (region
)[i
], i
);
808 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
812 /* In the context of sese S, scan the expression E and translate it to
813 a linear expression C. When parsing a symbolic multiplication, K
814 represents the constant multiplier of an expression containing
818 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
821 if (e
== chrec_dont_know
)
824 switch (TREE_CODE (e
))
826 case POLYNOMIAL_CHREC
:
827 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
828 CHREC_VARIABLE (e
), c
);
829 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
833 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
838 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
840 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
841 value_multiply (val
, val
, k
);
842 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
846 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
853 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
855 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
856 value_multiply (val
, val
, k
);
857 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
861 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
866 case POINTER_PLUS_EXPR
:
867 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
868 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
873 ppl_Linear_Expression_t tmp_expr
= NULL
;
877 ppl_dimension_type dim
;
878 ppl_Linear_Expression_space_dimension (c
, &dim
);
879 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
882 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
883 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
887 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
889 ppl_delete_Linear_Expression (tmp_expr
);
897 ppl_Linear_Expression_t tmp_expr
= NULL
;
901 ppl_dimension_type dim
;
902 ppl_Linear_Expression_space_dimension (c
, &dim
);
903 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
906 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
910 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
912 ppl_delete_Linear_Expression (tmp_expr
);
920 ppl_Linear_Expression_t tmp_expr
= NULL
;
924 ppl_dimension_type dim
;
925 ppl_Linear_Expression_space_dimension (c
, &dim
);
926 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
929 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
933 ppl_Coefficient_t coef
;
936 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
938 ppl_delete_Linear_Expression (tmp_expr
);
939 value_init (minus_one
);
940 value_set_si (minus_one
, -1);
941 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
942 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
943 value_clear (minus_one
);
944 ppl_delete_Coefficient (coef
);
952 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
956 ppl_dimension_type dim
;
957 ppl_Linear_Expression_space_dimension (c
, &dim
);
958 p
+= dim
- sese_nb_params (s
);
959 add_value_to_dim (p
, c
, k
);
966 scan_tree_for_params_int (e
, c
, k
);
970 case NON_LVALUE_EXPR
:
971 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
980 /* Find parameters with respect to REGION in BB. We are looking in memory
981 access functions, conditions and loop bounds. */
984 find_params_in_bb (sese region
, gimple_bb_p gbb
)
990 loop_p loop
= GBB_BB (gbb
)->loop_father
;
994 value_set_si (one
, 1);
996 /* Find parameters in the access functions of data references. */
997 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
998 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
999 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
1001 /* Find parameters in conditional statements. */
1002 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
1004 tree lhs
= scalar_evolution_in_region (region
, loop
,
1005 gimple_cond_lhs (stmt
));
1006 tree rhs
= scalar_evolution_in_region (region
, loop
,
1007 gimple_cond_rhs (stmt
));
1009 scan_tree_for_params (region
, lhs
, NULL
, one
);
1010 scan_tree_for_params (region
, rhs
, NULL
, one
);
1016 /* Record the parameters used in the SCOP. A variable is a parameter
1017 in a scop if it does not vary during the execution of that scop. */
1020 find_scop_parameters (scop_p scop
)
1024 sese region
= SCOP_REGION (scop
);
1029 value_set_si (one
, 1);
1031 /* Find the parameters used in the loop bounds. */
1032 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1034 tree nb_iters
= number_of_latch_executions (loop
);
1036 if (!chrec_contains_symbols (nb_iters
))
1039 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1040 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1045 /* Find the parameters used in data accesses. */
1046 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1047 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1049 scop_set_nb_params (scop
, sese_nb_params (region
));
1050 SESE_ADD_PARAMS (region
) = false;
1052 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1053 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1056 /* Returns a gimple_bb from BB. */
1058 static inline gimple_bb_p
1059 gbb_from_bb (basic_block bb
)
1061 return (gimple_bb_p
) bb
->aux
;
1064 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1065 the constraints for the surrounding loops. */
1068 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1069 ppl_Polyhedron_t outer_ph
, int nb
)
1072 ppl_Polyhedron_t ph
;
1073 tree nb_iters
= number_of_latch_executions (loop
);
1074 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1075 sese region
= SCOP_REGION (scop
);
1078 ppl_const_Constraint_System_t pcs
;
1079 ppl_dimension_type
*map
1080 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1082 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1083 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1084 ppl_Polyhedron_add_constraints (ph
, pcs
);
1086 for (i
= 0; i
< (int) nb
; i
++)
1088 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1092 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1098 ppl_Constraint_t lb
;
1099 ppl_Linear_Expression_t lb_expr
;
1101 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1102 ppl_set_coef (lb_expr
, nb
, 1);
1103 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1104 ppl_delete_Linear_Expression (lb_expr
);
1105 ppl_Polyhedron_add_constraint (ph
, lb
);
1106 ppl_delete_Constraint (lb
);
1109 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1111 ppl_Constraint_t ub
;
1112 ppl_Linear_Expression_t ub_expr
;
1114 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1116 /* loop_i <= cst_nb_iters */
1117 ppl_set_coef (ub_expr
, nb
, -1);
1118 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1119 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1120 ppl_Polyhedron_add_constraint (ph
, ub
);
1121 ppl_delete_Linear_Expression (ub_expr
);
1122 ppl_delete_Constraint (ub
);
1124 else if (!chrec_contains_undetermined (nb_iters
))
1127 ppl_Constraint_t ub
;
1128 ppl_Linear_Expression_t ub_expr
;
1132 value_set_si (one
, 1);
1133 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1134 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1135 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1138 /* N <= estimated_nb_iters
1140 FIXME: This is a workaround that should go away once we will
1141 have the PIP algorithm. */
1142 if (estimated_loop_iterations (loop
, true, &nit
))
1145 ppl_Linear_Expression_t nb_iters_le
;
1146 ppl_Polyhedron_t pol
;
1147 graphite_dim_t n
= scop_nb_params (scop
);
1148 ppl_Coefficient_t coef
;
1150 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1151 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1154 /* Construct the negated number of last iteration in VAL. */
1156 mpz_set_double_int (val
, nit
, false);
1157 value_sub_int (val
, val
, 1);
1158 value_oppose (val
, val
);
1160 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1161 Subtract estimated number of last iteration and assert that result
1163 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1164 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1165 ppl_delete_Coefficient (coef
);
1166 ppl_new_Constraint (&ub
, nb_iters_le
,
1167 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1168 ppl_Polyhedron_add_constraint (pol
, ub
);
1170 /* Remove all but last N dimensions from POL to obtain constraints
1173 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- n
);
1175 for (i
= 0; i
< dim
- n
; i
++)
1177 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- n
);
1181 /* Add constraints on parameters to SCoP context. */
1183 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1184 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1185 (&constraints_ps
, pol
);
1186 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1187 (SCOP_CONTEXT (scop
), constraints_ps
);
1188 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1191 ppl_delete_Polyhedron (pol
);
1192 ppl_delete_Linear_Expression (nb_iters_le
);
1193 ppl_delete_Constraint (ub
);
1197 /* loop_i <= expr_nb_iters */
1198 ppl_set_coef (ub_expr
, nb
, -1);
1199 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1200 ppl_Polyhedron_add_constraint (ph
, ub
);
1201 ppl_delete_Linear_Expression (ub_expr
);
1202 ppl_delete_Constraint (ub
);
1207 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1208 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1212 && loop_in_sese_p (loop
->next
, region
))
1213 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1215 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1216 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1218 ppl_delete_Polyhedron (ph
);
1221 /* Returns a linear expression for tree T evaluated in PBB. */
1223 static ppl_Linear_Expression_t
1224 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1227 ppl_Linear_Expression_t res
;
1228 ppl_dimension_type dim
;
1229 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1230 loop_p loop
= pbb_loop (pbb
);
1232 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1233 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1235 t
= scalar_evolution_in_region (region
, loop
, t
);
1236 gcc_assert (!automatically_generated_chrec_p (t
));
1239 value_set_si (one
, 1);
1240 scan_tree_for_params (region
, t
, res
, one
);
1246 /* Returns the ppl constraint type from the gimple tree code CODE. */
1248 static enum ppl_enum_Constraint_Type
1249 ppl_constraint_type_from_tree_code (enum tree_code code
)
1253 /* We do not support LT and GT to be able to work with C_Polyhedron.
1254 As we work on integer polyhedron "a < b" can be expressed by
1261 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1264 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1267 return PPL_CONSTRAINT_TYPE_EQUAL
;
1274 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1275 CODE is used as the comparison operator. This allows us to invert the
1276 condition or to handle inequalities. */
1279 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1280 poly_bb_p pbb
, enum tree_code code
)
1283 ppl_Coefficient_t c
;
1284 ppl_Linear_Expression_t left
, right
;
1285 ppl_Constraint_t cstr
;
1286 enum ppl_enum_Constraint_Type type
;
1288 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1289 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1291 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1292 the left or the right side of the expression. */
1293 if (code
== LT_EXPR
)
1296 value_set_si (v
, 1);
1297 ppl_new_Coefficient (&c
);
1298 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1299 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1300 ppl_delete_Coefficient (c
);
1305 else if (code
== GT_EXPR
)
1308 value_set_si (v
, 1);
1309 ppl_new_Coefficient (&c
);
1310 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1311 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1312 ppl_delete_Coefficient (c
);
1318 type
= ppl_constraint_type_from_tree_code (code
);
1320 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1322 ppl_new_Constraint (&cstr
, left
, type
);
1323 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1325 ppl_delete_Constraint (cstr
);
1326 ppl_delete_Linear_Expression (left
);
1327 ppl_delete_Linear_Expression (right
);
1330 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1331 operator. This allows us to invert the condition or to handle
1335 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1337 if (code
== NE_EXPR
)
1339 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1340 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1341 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1343 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1344 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1345 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1347 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1350 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1353 /* Add conditions to the domain of PBB. */
1356 add_conditions_to_domain (poly_bb_p pbb
)
1360 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1361 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1363 if (VEC_empty (gimple
, conditions
))
1366 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1367 switch (gimple_code (stmt
))
1371 enum tree_code code
= gimple_cond_code (stmt
);
1373 /* The conditions for ELSE-branches are inverted. */
1374 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1375 code
= invert_tree_comparison (code
, false);
1377 add_condition_to_pbb (pbb
, stmt
, code
);
1382 /* Switch statements are not supported right now - fall throught. */
1390 /* Structure used to pass data to dom_walk. */
1394 VEC (gimple
, heap
) **conditions
, **cases
;
1398 /* Returns non NULL when BB has a single predecessor and the last
1399 statement of that predecessor is a COND_EXPR. */
1402 single_pred_cond (basic_block bb
)
1404 if (single_pred_p (bb
))
1406 edge e
= single_pred_edge (bb
);
1407 basic_block pred
= e
->src
;
1408 gimple stmt
= last_stmt (pred
);
1410 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1416 /* Call-back for dom_walk executed before visiting the dominated
1420 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1423 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1424 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1425 VEC (gimple
, heap
) **cases
= data
->cases
;
1426 gimple_bb_p gbb
= gbb_from_bb (bb
);
1427 gimple stmt
= single_pred_cond (bb
);
1429 if (!bb_in_sese_p (bb
, data
->region
))
1434 edge e
= single_pred_edge (bb
);
1436 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1438 if (e
->flags
& EDGE_TRUE_VALUE
)
1439 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1441 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1446 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1447 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1451 /* Call-back for dom_walk executed after visiting the dominated
1455 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1458 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1459 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1460 VEC (gimple
, heap
) **cases
= data
->cases
;
1462 if (!bb_in_sese_p (bb
, data
->region
))
1465 if (single_pred_cond (bb
))
1467 VEC_pop (gimple
, *conditions
);
1468 VEC_pop (gimple
, *cases
);
1472 /* Record all conditions in REGION. */
1475 build_sese_conditions (sese region
)
1477 struct dom_walk_data walk_data
;
1478 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1479 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1482 data
.conditions
= &conditions
;
1483 data
.cases
= &cases
;
1484 data
.region
= region
;
1486 walk_data
.dom_direction
= CDI_DOMINATORS
;
1487 walk_data
.initialize_block_local_data
= NULL
;
1488 walk_data
.before_dom_children
= build_sese_conditions_before
;
1489 walk_data
.after_dom_children
= build_sese_conditions_after
;
1490 walk_data
.global_data
= &data
;
1491 walk_data
.block_local_data_size
= 0;
1493 init_walk_dominator_tree (&walk_data
);
1494 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1495 fini_walk_dominator_tree (&walk_data
);
1497 VEC_free (gimple
, heap
, conditions
);
1498 VEC_free (gimple
, heap
, cases
);
1501 /* Traverses all the GBBs of the SCOP and add their constraints to the
1502 iteration domains. */
1505 add_conditions_to_constraints (scop_p scop
)
1510 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1511 add_conditions_to_domain (pbb
);
1514 /* Add constraints on the possible values of parameter P from the type
1518 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1520 ppl_Constraint_t cstr
;
1521 ppl_Linear_Expression_t le
;
1522 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1523 tree type
= TREE_TYPE (parameter
);
1526 /* Disabled until we fix CPU2006. */
1529 if (!INTEGRAL_TYPE_P (type
))
1532 lb
= TYPE_MIN_VALUE (type
);
1533 ub
= TYPE_MAX_VALUE (type
);
1537 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1538 ppl_set_coef (le
, p
, -1);
1539 ppl_set_inhomogeneous_tree (le
, lb
);
1540 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1541 ppl_Polyhedron_add_constraint (context
, cstr
);
1542 ppl_delete_Linear_Expression (le
);
1543 ppl_delete_Constraint (cstr
);
1548 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1549 ppl_set_coef (le
, p
, -1);
1550 ppl_set_inhomogeneous_tree (le
, ub
);
1551 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1552 ppl_Polyhedron_add_constraint (context
, cstr
);
1553 ppl_delete_Linear_Expression (le
);
1554 ppl_delete_Constraint (cstr
);
1558 /* Build the context of the SCOP. The context usually contains extra
1559 constraints that are added to the iteration domains that constrain
1563 build_scop_context (scop_p scop
)
1565 ppl_Polyhedron_t context
;
1566 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1567 graphite_dim_t p
, n
= scop_nb_params (scop
);
1569 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1571 for (p
= 0; p
< n
; p
++)
1572 add_param_constraints (scop
, context
, p
);
1574 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1576 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1577 (SCOP_CONTEXT (scop
), ps
);
1579 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1580 ppl_delete_Polyhedron (context
);
1583 /* Build the iteration domains: the loops belonging to the current
1584 SCOP, and that vary for the execution of the current basic block.
1585 Returns false if there is no loop in SCOP. */
1588 build_scop_iteration_domain (scop_p scop
)
1591 sese region
= SCOP_REGION (scop
);
1593 ppl_Polyhedron_t ph
;
1596 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1598 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1599 if (!loop_in_sese_p (loop_outer (loop
), region
))
1600 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1602 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1603 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1604 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1605 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1606 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1608 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1609 (&PBB_DOMAIN (pbb
), ph
);
1611 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1614 ppl_delete_Pointset_Powerset_C_Polyhedron
1615 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1619 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
);
1679 value_set_si (v
, 1);
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
);
1782 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1784 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1785 dr
, DR_NUM_DIMENSIONS (dr
));
1788 /* Write to FILE the alias graph of data references in DIMACS format. */
1791 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1792 VEC (data_reference_p
, heap
) *drs
)
1794 int num_vertex
= VEC_length (data_reference_p
, drs
);
1796 data_reference_p dr1
, dr2
;
1799 if (num_vertex
== 0)
1802 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1803 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1804 if (dr_may_alias_p (dr1
, dr2
))
1807 fprintf (file
, "$\n");
1810 fprintf (file
, "c %s\n", comment
);
1812 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1814 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1815 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1816 if (dr_may_alias_p (dr1
, dr2
))
1817 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1822 /* Write to FILE the alias graph of data references in DOT format. */
1825 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1826 VEC (data_reference_p
, heap
) *drs
)
1828 int num_vertex
= VEC_length (data_reference_p
, drs
);
1829 data_reference_p dr1
, dr2
;
1832 if (num_vertex
== 0)
1835 fprintf (file
, "$\n");
1838 fprintf (file
, "c %s\n", comment
);
1840 /* First print all the vertices. */
1841 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1842 fprintf (file
, "n%d;\n", i
);
1844 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1845 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1846 if (dr_may_alias_p (dr1
, dr2
))
1847 fprintf (file
, "n%d n%d\n", i
, j
);
1852 /* Write to FILE the alias graph of data references in ECC format. */
1855 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1856 VEC (data_reference_p
, heap
) *drs
)
1858 int num_vertex
= VEC_length (data_reference_p
, drs
);
1859 data_reference_p dr1
, dr2
;
1862 if (num_vertex
== 0)
1865 fprintf (file
, "$\n");
1868 fprintf (file
, "c %s\n", comment
);
1870 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1871 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1872 if (dr_may_alias_p (dr1
, dr2
))
1873 fprintf (file
, "%d %d\n", i
, j
);
1878 /* Check if DR1 and DR2 are in the same object set. */
1881 dr_same_base_object_p (const struct data_reference
*dr1
,
1882 const struct data_reference
*dr2
)
1884 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1887 /* Uses DFS component number as representative of alias-sets. Also tests for
1888 optimality by verifying if every connected component is a clique. Returns
1889 true (1) if the above test is true, and false (0) otherwise. */
1892 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1894 int num_vertices
= VEC_length (data_reference_p
, drs
);
1895 struct graph
*g
= new_graph (num_vertices
);
1896 data_reference_p dr1
, dr2
;
1898 int num_connected_components
;
1899 int v_indx1
, v_indx2
, num_vertices_in_component
;
1902 struct graph_edge
*e
;
1903 int this_component_is_clique
;
1904 int all_components_are_cliques
= 1;
1906 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1907 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1908 if (dr_may_alias_p (dr1
, dr2
))
1914 all_vertices
= XNEWVEC (int, num_vertices
);
1915 vertices
= XNEWVEC (int, num_vertices
);
1916 for (i
= 0; i
< num_vertices
; i
++)
1917 all_vertices
[i
] = i
;
1919 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1921 for (i
= 0; i
< g
->n_vertices
; i
++)
1923 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1924 base_alias_pair
*bap
;
1927 bap
= (base_alias_pair
*)(dr
->aux
);
1929 bap
->alias_set
= XNEW (int);
1930 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1933 /* Verify if the DFS numbering results in optimal solution. */
1934 for (i
= 0; i
< num_connected_components
; i
++)
1936 num_vertices_in_component
= 0;
1937 /* Get all vertices whose DFS component number is the same as i. */
1938 for (j
= 0; j
< num_vertices
; j
++)
1939 if (g
->vertices
[j
].component
== i
)
1940 vertices
[num_vertices_in_component
++] = j
;
1942 /* Now test if the vertices in 'vertices' form a clique, by testing
1943 for edges among each pair. */
1944 this_component_is_clique
= 1;
1945 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1947 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1949 /* Check if the two vertices are connected by iterating
1950 through all the edges which have one of these are source. */
1951 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1954 if (e
->src
== vertices
[v_indx1
])
1960 this_component_is_clique
= 0;
1964 if (!this_component_is_clique
)
1965 all_components_are_cliques
= 0;
1969 free (all_vertices
);
1972 return all_components_are_cliques
;
1975 /* Group each data reference in DRS with it's base object set num. */
1978 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1980 int num_vertex
= VEC_length (data_reference_p
, drs
);
1981 struct graph
*g
= new_graph (num_vertex
);
1982 data_reference_p dr1
, dr2
;
1986 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1987 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1988 if (dr_same_base_object_p (dr1
, dr2
))
1994 queue
= XNEWVEC (int, num_vertex
);
1995 for (i
= 0; i
< num_vertex
; i
++)
1998 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
2000 for (i
= 0; i
< g
->n_vertices
; i
++)
2002 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
2003 base_alias_pair
*bap
;
2006 bap
= (base_alias_pair
*)(dr
->aux
);
2008 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2015 /* Build the data references for PBB. */
2018 build_pbb_drs (poly_bb_p pbb
)
2021 data_reference_p dr
;
2022 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2024 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2025 build_poly_dr (dr
, pbb
);
2028 /* Dump to file the alias graphs for the data references in DRS. */
2031 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2034 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2036 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2039 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2040 current_function_name ());
2041 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2042 fclose (file_dimacs
);
2045 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2048 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2049 current_function_name ());
2050 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2054 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2057 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2058 current_function_name ());
2059 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2064 /* Build data references in SCOP. */
2067 build_scop_drs (scop_p scop
)
2071 data_reference_p dr
;
2072 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2074 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2075 for (j
= 0; VEC_iterate (data_reference_p
,
2076 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2077 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2079 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2080 dr
->aux
= XNEW (base_alias_pair
);
2082 if (!build_alias_set_optimal_p (drs
))
2084 /* TODO: Add support when building alias set is not optimal. */
2088 build_base_obj_set_for_drs (drs
);
2090 /* When debugging, enable the following code. This cannot be used
2091 in production compilers. */
2093 dump_alias_graphs (drs
);
2095 VEC_free (data_reference_p
, heap
, drs
);
2097 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2098 build_pbb_drs (pbb
);
2101 /* Return a gsi at the position of the phi node STMT. */
2103 static gimple_stmt_iterator
2104 gsi_for_phi_node (gimple stmt
)
2106 gimple_stmt_iterator psi
;
2107 basic_block bb
= gimple_bb (stmt
);
2109 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2110 if (stmt
== gsi_stmt (psi
))
2117 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2120 insert_out_of_ssa_copy (tree res
, tree var
)
2124 gimple_stmt_iterator si
;
2125 gimple_stmt_iterator gsi
;
2127 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2128 stmt
= gimple_build_assign (res
, var
);
2130 stmts
= gimple_seq_alloc ();
2131 si
= gsi_last (stmts
);
2132 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2134 stmt
= SSA_NAME_DEF_STMT (var
);
2135 if (gimple_code (stmt
) == GIMPLE_PHI
)
2137 gsi
= gsi_after_labels (gimple_bb (stmt
));
2138 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2142 gsi
= gsi_for_stmt (stmt
);
2143 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2147 /* Insert on edge E the assignment "RES := EXPR". */
2150 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2152 gimple_stmt_iterator gsi
;
2154 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2155 gimple stmt
= gimple_build_assign (res
, var
);
2158 stmts
= gimple_seq_alloc ();
2160 gsi
= gsi_last (stmts
);
2161 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2162 gsi_insert_seq_on_edge (e
, stmts
);
2163 gsi_commit_edge_inserts ();
2166 /* Creates a zero dimension array of the same type as VAR. */
2169 create_zero_dim_array (tree var
)
2171 tree index_type
= build_index_type (integer_zero_node
);
2172 tree elt_type
= TREE_TYPE (var
);
2173 tree array_type
= build_array_type (elt_type
, index_type
);
2174 tree base
= create_tmp_var (array_type
, "Red");
2176 add_referenced_var (base
);
2178 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2182 /* Returns true when PHI is a loop close phi node. */
2185 scalar_close_phi_node_p (gimple phi
)
2187 if (gimple_code (phi
) != GIMPLE_PHI
2188 || !is_gimple_reg (gimple_phi_result (phi
)))
2191 return (gimple_phi_num_args (phi
) == 1);
2194 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2195 dimension array for it. */
2198 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2200 gimple phi
= gsi_stmt (*psi
);
2201 tree res
= gimple_phi_result (phi
);
2202 tree var
= SSA_NAME_VAR (res
);
2203 tree zero_dim_array
= create_zero_dim_array (var
);
2204 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2205 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2206 tree arg
= gimple_phi_arg_def (phi
, 0);
2208 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2210 remove_phi_node (psi
, false);
2211 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2212 SSA_NAME_DEF_STMT (res
) = stmt
;
2215 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2216 dimension array for it. */
2219 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2222 gimple phi
= gsi_stmt (*psi
);
2223 basic_block bb
= gimple_bb (phi
);
2224 tree res
= gimple_phi_result (phi
);
2225 tree var
= SSA_NAME_VAR (res
);
2226 tree zero_dim_array
= create_zero_dim_array (var
);
2227 gimple_stmt_iterator gsi
;
2231 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2233 tree arg
= gimple_phi_arg_def (phi
, i
);
2235 /* Try to avoid the insertion on edges as much as possible: this
2236 would avoid the insertion of code on loop latch edges, making
2237 the pattern matching of the vectorizer happy, or it would
2238 avoid the insertion of useless basic blocks. Note that it is
2239 incorrect to insert out of SSA copies close by their
2240 definition when they are more than two loop levels apart:
2241 for example, starting from a double nested loop
2251 the following transform is incorrect
2263 whereas inserting the copy on the incomming edge is correct
2275 if (TREE_CODE (arg
) == SSA_NAME
2276 && is_gimple_reg (arg
)
2277 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2278 && (flow_bb_inside_loop_p (bb
->loop_father
,
2279 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2280 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2281 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2282 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2284 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2285 zero_dim_array
, arg
);
2288 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2291 stmts
= gimple_seq_alloc ();
2293 stmt
= gimple_build_assign (res
, var
);
2294 remove_phi_node (psi
, false);
2295 SSA_NAME_DEF_STMT (res
) = stmt
;
2297 gsi
= gsi_last (stmts
);
2298 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2300 gsi
= gsi_after_labels (bb
);
2301 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2304 /* Return true when DEF can be analyzed in REGION by the scalar
2305 evolution analyzer. */
2308 scev_analyzable_p (tree def
, sese region
)
2310 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2311 loop_p loop
= loop_containing_stmt (stmt
);
2312 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2314 return !chrec_contains_undetermined (scev
);
2317 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2318 read from ZERO_DIM_ARRAY. */
2321 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2323 tree var
= SSA_NAME_VAR (def
);
2324 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2325 tree name
= make_ssa_name (var
, name_stmt
);
2327 use_operand_p use_p
;
2328 gimple_stmt_iterator gsi
;
2330 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2332 gimple_assign_set_lhs (name_stmt
, name
);
2334 gsi
= gsi_for_stmt (use_stmt
);
2335 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2337 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2338 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2339 replace_exp (use_p
, name
);
2341 update_stmt (use_stmt
);
2344 /* Rewrite the scalar dependences crossing the boundary of the BB
2345 containing STMT with an array. */
2348 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2350 gimple stmt
= gsi_stmt (*gsi
);
2351 imm_use_iterator imm_iter
;
2354 tree zero_dim_array
= NULL_TREE
;
2357 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2360 def
= gimple_assign_lhs (stmt
);
2361 if (!is_gimple_reg (def
)
2362 || scev_analyzable_p (def
, region
))
2365 def_bb
= gimple_bb (stmt
);
2367 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2368 if (def_bb
!= gimple_bb (use_stmt
)
2369 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2371 if (!zero_dim_array
)
2373 zero_dim_array
= create_zero_dim_array (SSA_NAME_VAR (def
));
2374 insert_out_of_ssa_copy (zero_dim_array
, def
);
2378 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2382 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2385 rewrite_reductions_out_of_ssa (scop_p scop
)
2388 gimple_stmt_iterator psi
;
2389 sese region
= SCOP_REGION (scop
);
2392 if (bb_in_sese_p (bb
, region
))
2393 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2395 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2396 rewrite_close_phi_out_of_ssa (&psi
);
2397 else if (reduction_phi_p (region
, &psi
))
2398 rewrite_phi_out_of_ssa (&psi
);
2401 update_ssa (TODO_update_ssa
);
2402 #ifdef ENABLE_CHECKING
2404 verify_loop_closed_ssa ();
2408 if (bb_in_sese_p (bb
, region
))
2409 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2410 rewrite_cross_bb_scalar_deps (region
, &psi
);
2412 update_ssa (TODO_update_ssa
);
2413 #ifdef ENABLE_CHECKING
2415 verify_loop_closed_ssa ();
2419 /* Returns the number of pbbs that are in loops contained in SCOP. */
2422 nb_pbbs_in_loops (scop_p scop
)
2428 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2429 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2435 /* Return the number of data references in BB that write in
2439 nb_data_writes_in_bb (basic_block bb
)
2442 gimple_stmt_iterator gsi
;
2444 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2445 if (gimple_vdef (gsi_stmt (gsi
)))
2451 /* Splits STMT out of its current BB. */
2454 split_reduction_stmt (gimple stmt
)
2456 gimple_stmt_iterator gsi
;
2457 basic_block bb
= gimple_bb (stmt
);
2460 /* Do not split basic blocks with no writes to memory: the reduction
2461 will be the only write to memory. */
2462 if (nb_data_writes_in_bb (bb
) == 0)
2465 split_block (bb
, stmt
);
2467 gsi
= gsi_last_bb (bb
);
2469 e
= split_block (bb
, gsi_stmt (gsi
));
2474 /* Return true when stmt is a reduction operation. */
2477 is_reduction_operation_p (gimple stmt
)
2479 return flag_associative_math
2480 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2481 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2484 /* Returns true when PHI contains an argument ARG. */
2487 phi_contains_arg (gimple phi
, tree arg
)
2491 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2492 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2498 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2501 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2505 if (TREE_CODE (arg
) != SSA_NAME
)
2508 stmt
= SSA_NAME_DEF_STMT (arg
);
2510 if (gimple_code (stmt
) == GIMPLE_PHI
)
2512 if (phi_contains_arg (stmt
, lhs
))
2517 if (gimple_num_ops (stmt
) == 2)
2518 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2520 if (is_reduction_operation_p (stmt
))
2522 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2525 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2531 /* Detect commutative and associative scalar reductions starting at
2535 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2536 VEC (gimple
, heap
) **in
,
2537 VEC (gimple
, heap
) **out
)
2539 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2543 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2544 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2551 /* Detect commutative and associative scalar reductions starting at
2555 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2556 VEC (gimple
, heap
) **out
)
2558 tree lhs
= gimple_assign_lhs (stmt
);
2560 if (gimple_num_ops (stmt
) == 2)
2561 return detect_commutative_reduction_arg (lhs
, stmt
,
2562 gimple_assign_rhs1 (stmt
),
2565 if (is_reduction_operation_p (stmt
))
2567 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2568 gimple_assign_rhs1 (stmt
),
2571 : detect_commutative_reduction_arg (lhs
, stmt
,
2572 gimple_assign_rhs2 (stmt
),
2579 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2582 follow_inital_value_to_phi (tree arg
, tree lhs
)
2586 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2589 stmt
= SSA_NAME_DEF_STMT (arg
);
2591 if (gimple_code (stmt
) == GIMPLE_PHI
2592 && phi_contains_arg (stmt
, lhs
))
2599 /* Return the argument of the loop PHI that is the inital value coming
2600 from outside the loop. */
2603 edge_initial_value_for_loop_phi (gimple phi
)
2607 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2609 edge e
= gimple_phi_arg_edge (phi
, i
);
2611 if (loop_depth (e
->src
->loop_father
)
2612 < loop_depth (e
->dest
->loop_father
))
2619 /* Return the argument of the loop PHI that is the inital value coming
2620 from outside the loop. */
2623 initial_value_for_loop_phi (gimple phi
)
2627 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2629 edge e
= gimple_phi_arg_edge (phi
, i
);
2631 if (loop_depth (e
->src
->loop_father
)
2632 < loop_depth (e
->dest
->loop_father
))
2633 return gimple_phi_arg_def (phi
, i
);
2639 /* Detect commutative and associative scalar reductions starting at
2640 the loop closed phi node CLOSE_PHI. */
2643 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2644 VEC (gimple
, heap
) **out
)
2646 if (scalar_close_phi_node_p (stmt
))
2648 tree arg
= gimple_phi_arg_def (stmt
, 0);
2649 gimple def
= SSA_NAME_DEF_STMT (arg
);
2650 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2654 tree lhs
= gimple_phi_result (stmt
);
2655 tree init
= initial_value_for_loop_phi (loop_phi
);
2656 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2658 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2659 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2666 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2667 return detect_commutative_reduction_assign (stmt
, in
, out
);
2672 /* Translate the scalar reduction statement STMT to an array RED
2673 knowing that its recursive phi node is LOOP_PHI. */
2676 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2679 basic_block bb
= gimple_bb (stmt
);
2680 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2681 tree res
= gimple_phi_result (loop_phi
);
2682 gimple assign
= gimple_build_assign (res
, red
);
2684 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2686 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2687 insert_gsi
= gsi_for_stmt (stmt
);
2688 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2691 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2694 insert_copyout (tree red
, gimple close_phi
)
2696 tree res
= gimple_phi_result (close_phi
);
2697 basic_block bb
= gimple_bb (close_phi
);
2698 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2699 gimple assign
= gimple_build_assign (res
, red
);
2701 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2704 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2707 insert_copyin (tree red
, gimple loop_phi
)
2710 tree init
= initial_value_for_loop_phi (loop_phi
);
2711 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2713 force_gimple_operand (expr
, &stmts
, true, NULL
);
2714 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2717 /* Rewrite out of SSA the reduction described by the loop phi nodes
2718 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2721 IN: stmt, loop_n, ..., loop_0
2722 OUT: stmt, close_n, ..., close_0
2724 the first element is the reduction statement, and the next elements
2725 are the loop and close phi nodes of each of the outer loops. */
2728 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2729 VEC (gimple
, heap
) *out
,
2735 gimple_stmt_iterator gsi
;
2737 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2739 gimple close_phi
= VEC_index (gimple
, out
, i
);
2743 gimple stmt
= loop_phi
;
2744 basic_block bb
= split_reduction_stmt (stmt
);
2746 SET_BIT (reductions
, bb
->index
);
2747 gcc_assert (close_phi
== loop_phi
);
2749 red
= create_zero_dim_array (gimple_assign_lhs (stmt
));
2750 translate_scalar_reduction_to_array_for_stmt
2751 (red
, stmt
, VEC_index (gimple
, in
, 1));
2755 if (i
== VEC_length (gimple
, in
) - 1)
2757 insert_copyout (red
, close_phi
);
2758 insert_copyin (red
, loop_phi
);
2761 gsi
= gsi_for_phi_node (loop_phi
);
2762 remove_phi_node (&gsi
, false);
2764 gsi
= gsi_for_phi_node (close_phi
);
2765 remove_phi_node (&gsi
, false);
2769 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2772 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2775 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2776 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2778 detect_commutative_reduction (close_phi
, &in
, &out
);
2779 if (VEC_length (gimple
, in
) > 0)
2780 translate_scalar_reduction_to_array (in
, out
, reductions
);
2782 VEC_free (gimple
, heap
, in
);
2783 VEC_free (gimple
, heap
, out
);
2786 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2789 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2792 gimple_stmt_iterator gsi
;
2793 edge exit
= single_exit (loop
);
2798 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2799 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2803 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2806 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2811 FOR_EACH_LOOP (li
, loop
, 0)
2812 if (loop_in_sese_p (loop
, region
))
2813 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2815 gsi_commit_edge_inserts ();
2816 update_ssa (TODO_update_ssa
);
2817 #ifdef ENABLE_CHECKING
2819 verify_loop_closed_ssa ();
2823 /* Builds the polyhedral representation for a SESE region. */
2826 build_poly_scop (scop_p scop
)
2828 sese region
= SCOP_REGION (scop
);
2829 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2831 sbitmap_zero (reductions
);
2832 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2833 rewrite_reductions_out_of_ssa (scop
);
2834 build_scop_bbs (scop
, reductions
);
2835 sbitmap_free (reductions
);
2837 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2838 Once CLooG is fixed, remove this guard. Anyways, it makes no
2839 sense to optimize a scop containing only PBBs that do not belong
2841 if (nb_pbbs_in_loops (scop
) == 0)
2844 build_sese_loop_nests (region
);
2845 build_sese_conditions (region
);
2846 find_scop_parameters (scop
);
2848 build_scop_iteration_domain (scop
);
2849 build_scop_context (scop
);
2851 add_conditions_to_constraints (scop
);
2853 build_scop_scattering (scop
);
2854 build_scop_drs (scop
);
2859 /* Always return false. Exercise the scop_to_clast function. */
2862 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2864 #ifdef ENABLE_CHECKING
2865 cloog_prog_clast pc
= scop_to_clast (scop
);
2866 cloog_clast_free (pc
.stmt
);
2867 cloog_program_free (pc
.prog
);