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
,
1070 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1073 ppl_Polyhedron_t ph
;
1074 tree nb_iters
= number_of_latch_executions (loop
);
1075 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1076 sese region
= SCOP_REGION (scop
);
1079 ppl_const_Constraint_System_t pcs
;
1080 ppl_dimension_type
*map
1081 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1083 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1084 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1085 ppl_Polyhedron_add_constraints (ph
, pcs
);
1087 for (i
= 0; i
< (int) nb
; i
++)
1089 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1093 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1099 ppl_Constraint_t lb
;
1100 ppl_Linear_Expression_t lb_expr
;
1102 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1103 ppl_set_coef (lb_expr
, nb
, 1);
1104 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1105 ppl_delete_Linear_Expression (lb_expr
);
1106 ppl_Polyhedron_add_constraint (ph
, lb
);
1107 ppl_delete_Constraint (lb
);
1110 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1112 ppl_Constraint_t ub
;
1113 ppl_Linear_Expression_t ub_expr
;
1115 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1117 /* loop_i <= cst_nb_iters */
1118 ppl_set_coef (ub_expr
, nb
, -1);
1119 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1120 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1121 ppl_Polyhedron_add_constraint (ph
, ub
);
1122 ppl_delete_Linear_Expression (ub_expr
);
1123 ppl_delete_Constraint (ub
);
1125 else if (!chrec_contains_undetermined (nb_iters
))
1128 ppl_Constraint_t ub
;
1129 ppl_Linear_Expression_t ub_expr
;
1133 value_set_si (one
, 1);
1134 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1135 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1136 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1139 /* N <= estimated_nb_iters
1141 FIXME: This is a workaround that should go away once we will
1142 have the PIP algorithm. */
1143 if (estimated_loop_iterations (loop
, true, &nit
))
1146 ppl_Linear_Expression_t nb_iters_le
;
1147 ppl_Polyhedron_t pol
;
1148 graphite_dim_t n
= scop_nb_params (scop
);
1149 ppl_Coefficient_t coef
;
1151 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1152 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1155 /* Construct the negated number of last iteration in VAL. */
1157 mpz_set_double_int (val
, nit
, false);
1158 value_sub_int (val
, val
, 1);
1159 value_oppose (val
, val
);
1161 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1162 Subtract estimated number of last iteration and assert that result
1164 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1165 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1166 ppl_delete_Coefficient (coef
);
1167 ppl_new_Constraint (&ub
, nb_iters_le
,
1168 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1169 ppl_Polyhedron_add_constraint (pol
, ub
);
1171 /* Remove all but last N dimensions from POL to obtain constraints
1174 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- n
);
1176 for (i
= 0; i
< dim
- n
; i
++)
1178 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- n
);
1182 /* Add constraints on parameters to SCoP context. */
1184 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1185 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1186 (&constraints_ps
, pol
);
1187 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1188 (SCOP_CONTEXT (scop
), constraints_ps
);
1189 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1192 ppl_delete_Polyhedron (pol
);
1193 ppl_delete_Linear_Expression (nb_iters_le
);
1194 ppl_delete_Constraint (ub
);
1198 /* loop_i <= expr_nb_iters */
1199 ppl_set_coef (ub_expr
, nb
, -1);
1200 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1201 ppl_Polyhedron_add_constraint (ph
, ub
);
1202 ppl_delete_Linear_Expression (ub_expr
);
1203 ppl_delete_Constraint (ub
);
1208 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1209 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1213 && loop_in_sese_p (loop
->next
, region
))
1214 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1216 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1217 (&domains
[loop
->num
], ph
);
1219 ppl_delete_Polyhedron (ph
);
1222 /* Returns a linear expression for tree T evaluated in PBB. */
1224 static ppl_Linear_Expression_t
1225 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1228 ppl_Linear_Expression_t res
;
1229 ppl_dimension_type dim
;
1230 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1231 loop_p loop
= pbb_loop (pbb
);
1233 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1234 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1236 t
= scalar_evolution_in_region (region
, loop
, t
);
1237 gcc_assert (!automatically_generated_chrec_p (t
));
1240 value_set_si (one
, 1);
1241 scan_tree_for_params (region
, t
, res
, one
);
1247 /* Returns the ppl constraint type from the gimple tree code CODE. */
1249 static enum ppl_enum_Constraint_Type
1250 ppl_constraint_type_from_tree_code (enum tree_code code
)
1254 /* We do not support LT and GT to be able to work with C_Polyhedron.
1255 As we work on integer polyhedron "a < b" can be expressed by
1262 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1265 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1268 return PPL_CONSTRAINT_TYPE_EQUAL
;
1275 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1276 CODE is used as the comparison operator. This allows us to invert the
1277 condition or to handle inequalities. */
1280 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1281 poly_bb_p pbb
, enum tree_code code
)
1284 ppl_Coefficient_t c
;
1285 ppl_Linear_Expression_t left
, right
;
1286 ppl_Constraint_t cstr
;
1287 enum ppl_enum_Constraint_Type type
;
1289 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1290 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1292 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1293 the left or the right side of the expression. */
1294 if (code
== LT_EXPR
)
1297 value_set_si (v
, 1);
1298 ppl_new_Coefficient (&c
);
1299 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1300 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1301 ppl_delete_Coefficient (c
);
1306 else if (code
== GT_EXPR
)
1309 value_set_si (v
, 1);
1310 ppl_new_Coefficient (&c
);
1311 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1312 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1313 ppl_delete_Coefficient (c
);
1319 type
= ppl_constraint_type_from_tree_code (code
);
1321 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1323 ppl_new_Constraint (&cstr
, left
, type
);
1324 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1326 ppl_delete_Constraint (cstr
);
1327 ppl_delete_Linear_Expression (left
);
1328 ppl_delete_Linear_Expression (right
);
1331 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1332 operator. This allows us to invert the condition or to handle
1336 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1338 if (code
== NE_EXPR
)
1340 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1341 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1342 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1344 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1345 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1346 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1348 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1351 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1354 /* Add conditions to the domain of PBB. */
1357 add_conditions_to_domain (poly_bb_p pbb
)
1361 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1362 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1364 if (VEC_empty (gimple
, conditions
))
1367 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1368 switch (gimple_code (stmt
))
1372 enum tree_code code
= gimple_cond_code (stmt
);
1374 /* The conditions for ELSE-branches are inverted. */
1375 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1376 code
= invert_tree_comparison (code
, false);
1378 add_condition_to_pbb (pbb
, stmt
, code
);
1383 /* Switch statements are not supported right now - fall throught. */
1391 /* Structure used to pass data to dom_walk. */
1395 VEC (gimple
, heap
) **conditions
, **cases
;
1399 /* Returns non NULL when BB has a single predecessor and the last
1400 statement of that predecessor is a COND_EXPR. */
1403 single_pred_cond (basic_block bb
)
1405 if (single_pred_p (bb
))
1407 edge e
= single_pred_edge (bb
);
1408 basic_block pred
= e
->src
;
1409 gimple stmt
= last_stmt (pred
);
1411 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1417 /* Call-back for dom_walk executed before visiting the dominated
1421 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1424 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1425 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1426 VEC (gimple
, heap
) **cases
= data
->cases
;
1427 gimple_bb_p gbb
= gbb_from_bb (bb
);
1428 gimple stmt
= single_pred_cond (bb
);
1430 if (!bb_in_sese_p (bb
, data
->region
))
1435 edge e
= single_pred_edge (bb
);
1437 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1439 if (e
->flags
& EDGE_TRUE_VALUE
)
1440 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1442 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1447 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1448 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1452 /* Call-back for dom_walk executed after visiting the dominated
1456 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1459 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1460 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1461 VEC (gimple
, heap
) **cases
= data
->cases
;
1463 if (!bb_in_sese_p (bb
, data
->region
))
1466 if (single_pred_cond (bb
))
1468 VEC_pop (gimple
, *conditions
);
1469 VEC_pop (gimple
, *cases
);
1473 /* Record all conditions in REGION. */
1476 build_sese_conditions (sese region
)
1478 struct dom_walk_data walk_data
;
1479 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1480 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1483 data
.conditions
= &conditions
;
1484 data
.cases
= &cases
;
1485 data
.region
= region
;
1487 walk_data
.dom_direction
= CDI_DOMINATORS
;
1488 walk_data
.initialize_block_local_data
= NULL
;
1489 walk_data
.before_dom_children
= build_sese_conditions_before
;
1490 walk_data
.after_dom_children
= build_sese_conditions_after
;
1491 walk_data
.global_data
= &data
;
1492 walk_data
.block_local_data_size
= 0;
1494 init_walk_dominator_tree (&walk_data
);
1495 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1496 fini_walk_dominator_tree (&walk_data
);
1498 VEC_free (gimple
, heap
, conditions
);
1499 VEC_free (gimple
, heap
, cases
);
1502 /* Traverses all the GBBs of the SCOP and add their constraints to the
1503 iteration domains. */
1506 add_conditions_to_constraints (scop_p scop
)
1511 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1512 add_conditions_to_domain (pbb
);
1515 /* Add constraints on the possible values of parameter P from the type
1519 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1521 ppl_Constraint_t cstr
;
1522 ppl_Linear_Expression_t le
;
1523 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1524 tree type
= TREE_TYPE (parameter
);
1527 /* Disabled until we fix CPU2006. */
1530 if (!INTEGRAL_TYPE_P (type
))
1533 lb
= TYPE_MIN_VALUE (type
);
1534 ub
= TYPE_MAX_VALUE (type
);
1538 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1539 ppl_set_coef (le
, p
, -1);
1540 ppl_set_inhomogeneous_tree (le
, lb
);
1541 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1542 ppl_Polyhedron_add_constraint (context
, cstr
);
1543 ppl_delete_Linear_Expression (le
);
1544 ppl_delete_Constraint (cstr
);
1549 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1550 ppl_set_coef (le
, p
, -1);
1551 ppl_set_inhomogeneous_tree (le
, ub
);
1552 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1553 ppl_Polyhedron_add_constraint (context
, cstr
);
1554 ppl_delete_Linear_Expression (le
);
1555 ppl_delete_Constraint (cstr
);
1559 /* Build the context of the SCOP. The context usually contains extra
1560 constraints that are added to the iteration domains that constrain
1564 build_scop_context (scop_p scop
)
1566 ppl_Polyhedron_t context
;
1567 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1568 graphite_dim_t p
, n
= scop_nb_params (scop
);
1570 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1572 for (p
= 0; p
< n
; p
++)
1573 add_param_constraints (scop
, context
, p
);
1575 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1577 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1578 (SCOP_CONTEXT (scop
), ps
);
1580 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1581 ppl_delete_Polyhedron (context
);
1584 /* Build the iteration domains: the loops belonging to the current
1585 SCOP, and that vary for the execution of the current basic block.
1586 Returns false if there is no loop in SCOP. */
1589 build_scop_iteration_domain (scop_p scop
)
1592 sese region
= SCOP_REGION (scop
);
1594 ppl_Polyhedron_t ph
;
1596 int nb_loops
= number_of_loops ();
1597 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1598 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1600 for (i
= 0; i
< nb_loops
; i
++)
1603 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1605 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1606 if (!loop_in_sese_p (loop_outer (loop
), region
))
1607 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1609 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1610 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1611 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1612 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1613 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1615 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1616 (&PBB_DOMAIN (pbb
), ph
);
1618 for (i
= 0; i
< nb_loops
; i
++)
1620 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1622 ppl_delete_Polyhedron (ph
);
1626 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1627 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1628 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1632 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1633 ppl_dimension_type accessp_nb_dims
,
1634 ppl_dimension_type dom_nb_dims
)
1636 ppl_Linear_Expression_t alias
;
1637 ppl_Constraint_t cstr
;
1638 int alias_set_num
= 0;
1639 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1641 if (bap
&& bap
->alias_set
)
1642 alias_set_num
= *(bap
->alias_set
);
1644 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1646 ppl_set_coef (alias
, dom_nb_dims
, 1);
1647 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1648 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1649 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1651 ppl_delete_Linear_Expression (alias
);
1652 ppl_delete_Constraint (cstr
);
1655 /* Add to ACCESSES polyhedron equalities defining the access functions
1656 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1657 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1658 PBB is the poly_bb_p that contains the data reference DR. */
1661 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1662 ppl_dimension_type accessp_nb_dims
,
1663 ppl_dimension_type dom_nb_dims
,
1666 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1668 scop_p scop
= PBB_SCOP (pbb
);
1669 sese region
= SCOP_REGION (scop
);
1673 for (i
= 0; i
< nb_subscripts
; i
++)
1675 ppl_Linear_Expression_t fn
, access
;
1676 ppl_Constraint_t cstr
;
1677 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1678 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1680 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1681 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1683 value_set_si (v
, 1);
1684 scan_tree_for_params (region
, afn
, fn
, v
);
1685 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1687 ppl_set_coef (access
, subscript
, -1);
1688 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1689 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1691 ppl_delete_Linear_Expression (fn
);
1692 ppl_delete_Linear_Expression (access
);
1693 ppl_delete_Constraint (cstr
);
1699 /* Add constrains representing the size of the accessed data to the
1700 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1701 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1705 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1706 ppl_dimension_type accessp_nb_dims
,
1707 ppl_dimension_type dom_nb_dims
)
1709 tree ref
= DR_REF (dr
);
1710 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1712 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1714 ppl_Linear_Expression_t expr
;
1715 ppl_Constraint_t cstr
;
1716 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1719 if (TREE_CODE (ref
) != ARRAY_REF
)
1722 low
= array_ref_low_bound (ref
);
1724 /* subscript - low >= 0 */
1725 if (host_integerp (low
, 0))
1727 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1728 ppl_set_coef (expr
, subscript
, 1);
1730 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1732 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1733 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1734 ppl_delete_Linear_Expression (expr
);
1735 ppl_delete_Constraint (cstr
);
1738 high
= array_ref_up_bound (ref
);
1740 /* high - subscript >= 0 */
1741 if (high
&& host_integerp (high
, 0)
1742 /* 1-element arrays at end of structures may extend over
1743 their declared size. */
1744 && !(array_at_struct_end_p (ref
)
1745 && operand_equal_p (low
, high
, 0)))
1747 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1748 ppl_set_coef (expr
, subscript
, -1);
1750 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1752 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1753 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1754 ppl_delete_Linear_Expression (expr
);
1755 ppl_delete_Constraint (cstr
);
1760 /* Build data accesses for DR in PBB. */
1763 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1765 ppl_Polyhedron_t accesses
;
1766 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1767 ppl_dimension_type dom_nb_dims
;
1768 ppl_dimension_type accessp_nb_dims
;
1769 int dr_base_object_set
;
1771 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1773 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1775 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1777 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1778 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1779 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1781 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1783 ppl_delete_Polyhedron (accesses
);
1786 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1788 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1789 dr
, DR_NUM_DIMENSIONS (dr
));
1792 /* Write to FILE the alias graph of data references in DIMACS format. */
1795 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1796 VEC (data_reference_p
, heap
) *drs
)
1798 int num_vertex
= VEC_length (data_reference_p
, drs
);
1800 data_reference_p dr1
, dr2
;
1803 if (num_vertex
== 0)
1806 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1807 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1808 if (dr_may_alias_p (dr1
, dr2
))
1811 fprintf (file
, "$\n");
1814 fprintf (file
, "c %s\n", comment
);
1816 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1818 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1819 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1820 if (dr_may_alias_p (dr1
, dr2
))
1821 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1826 /* Write to FILE the alias graph of data references in DOT format. */
1829 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1830 VEC (data_reference_p
, heap
) *drs
)
1832 int num_vertex
= VEC_length (data_reference_p
, drs
);
1833 data_reference_p dr1
, dr2
;
1836 if (num_vertex
== 0)
1839 fprintf (file
, "$\n");
1842 fprintf (file
, "c %s\n", comment
);
1844 /* First print all the vertices. */
1845 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1846 fprintf (file
, "n%d;\n", i
);
1848 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1849 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1850 if (dr_may_alias_p (dr1
, dr2
))
1851 fprintf (file
, "n%d n%d\n", i
, j
);
1856 /* Write to FILE the alias graph of data references in ECC format. */
1859 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1860 VEC (data_reference_p
, heap
) *drs
)
1862 int num_vertex
= VEC_length (data_reference_p
, drs
);
1863 data_reference_p dr1
, dr2
;
1866 if (num_vertex
== 0)
1869 fprintf (file
, "$\n");
1872 fprintf (file
, "c %s\n", comment
);
1874 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1875 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1876 if (dr_may_alias_p (dr1
, dr2
))
1877 fprintf (file
, "%d %d\n", i
, j
);
1882 /* Check if DR1 and DR2 are in the same object set. */
1885 dr_same_base_object_p (const struct data_reference
*dr1
,
1886 const struct data_reference
*dr2
)
1888 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1891 /* Uses DFS component number as representative of alias-sets. Also tests for
1892 optimality by verifying if every connected component is a clique. Returns
1893 true (1) if the above test is true, and false (0) otherwise. */
1896 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1898 int num_vertices
= VEC_length (data_reference_p
, drs
);
1899 struct graph
*g
= new_graph (num_vertices
);
1900 data_reference_p dr1
, dr2
;
1902 int num_connected_components
;
1903 int v_indx1
, v_indx2
, num_vertices_in_component
;
1906 struct graph_edge
*e
;
1907 int this_component_is_clique
;
1908 int all_components_are_cliques
= 1;
1910 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1911 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1912 if (dr_may_alias_p (dr1
, dr2
))
1918 all_vertices
= XNEWVEC (int, num_vertices
);
1919 vertices
= XNEWVEC (int, num_vertices
);
1920 for (i
= 0; i
< num_vertices
; i
++)
1921 all_vertices
[i
] = i
;
1923 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1925 for (i
= 0; i
< g
->n_vertices
; i
++)
1927 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1928 base_alias_pair
*bap
;
1931 bap
= (base_alias_pair
*)(dr
->aux
);
1933 bap
->alias_set
= XNEW (int);
1934 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1937 /* Verify if the DFS numbering results in optimal solution. */
1938 for (i
= 0; i
< num_connected_components
; i
++)
1940 num_vertices_in_component
= 0;
1941 /* Get all vertices whose DFS component number is the same as i. */
1942 for (j
= 0; j
< num_vertices
; j
++)
1943 if (g
->vertices
[j
].component
== i
)
1944 vertices
[num_vertices_in_component
++] = j
;
1946 /* Now test if the vertices in 'vertices' form a clique, by testing
1947 for edges among each pair. */
1948 this_component_is_clique
= 1;
1949 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1951 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1953 /* Check if the two vertices are connected by iterating
1954 through all the edges which have one of these are source. */
1955 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1958 if (e
->src
== vertices
[v_indx1
])
1964 this_component_is_clique
= 0;
1968 if (!this_component_is_clique
)
1969 all_components_are_cliques
= 0;
1973 free (all_vertices
);
1976 return all_components_are_cliques
;
1979 /* Group each data reference in DRS with it's base object set num. */
1982 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1984 int num_vertex
= VEC_length (data_reference_p
, drs
);
1985 struct graph
*g
= new_graph (num_vertex
);
1986 data_reference_p dr1
, dr2
;
1990 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1991 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1992 if (dr_same_base_object_p (dr1
, dr2
))
1998 queue
= XNEWVEC (int, num_vertex
);
1999 for (i
= 0; i
< num_vertex
; i
++)
2002 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
2004 for (i
= 0; i
< g
->n_vertices
; i
++)
2006 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
2007 base_alias_pair
*bap
;
2010 bap
= (base_alias_pair
*)(dr
->aux
);
2012 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2019 /* Build the data references for PBB. */
2022 build_pbb_drs (poly_bb_p pbb
)
2025 data_reference_p dr
;
2026 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2028 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2029 build_poly_dr (dr
, pbb
);
2032 /* Dump to file the alias graphs for the data references in DRS. */
2035 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2038 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2040 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2043 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2044 current_function_name ());
2045 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2046 fclose (file_dimacs
);
2049 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2052 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2053 current_function_name ());
2054 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2058 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2061 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2062 current_function_name ());
2063 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2068 /* Build data references in SCOP. */
2071 build_scop_drs (scop_p scop
)
2075 data_reference_p dr
;
2076 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2078 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2079 for (j
= 0; VEC_iterate (data_reference_p
,
2080 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2081 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2083 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2084 dr
->aux
= XNEW (base_alias_pair
);
2086 if (!build_alias_set_optimal_p (drs
))
2088 /* TODO: Add support when building alias set is not optimal. */
2092 build_base_obj_set_for_drs (drs
);
2094 /* When debugging, enable the following code. This cannot be used
2095 in production compilers. */
2097 dump_alias_graphs (drs
);
2099 VEC_free (data_reference_p
, heap
, drs
);
2101 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2102 build_pbb_drs (pbb
);
2105 /* Return a gsi at the position of the phi node STMT. */
2107 static gimple_stmt_iterator
2108 gsi_for_phi_node (gimple stmt
)
2110 gimple_stmt_iterator psi
;
2111 basic_block bb
= gimple_bb (stmt
);
2113 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2114 if (stmt
== gsi_stmt (psi
))
2121 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2124 insert_out_of_ssa_copy (tree res
, tree var
)
2128 gimple_stmt_iterator si
;
2129 gimple_stmt_iterator gsi
;
2131 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2132 stmt
= gimple_build_assign (res
, var
);
2134 stmts
= gimple_seq_alloc ();
2135 si
= gsi_last (stmts
);
2136 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2138 stmt
= SSA_NAME_DEF_STMT (var
);
2139 if (gimple_code (stmt
) == GIMPLE_PHI
)
2141 gsi
= gsi_after_labels (gimple_bb (stmt
));
2142 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2146 gsi
= gsi_for_stmt (stmt
);
2147 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2151 /* Insert on edge E the assignment "RES := EXPR". */
2154 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2156 gimple_stmt_iterator gsi
;
2158 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2159 gimple stmt
= gimple_build_assign (res
, var
);
2162 stmts
= gimple_seq_alloc ();
2164 gsi
= gsi_last (stmts
);
2165 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2166 gsi_insert_seq_on_edge (e
, stmts
);
2167 gsi_commit_edge_inserts ();
2170 /* Creates a zero dimension array of the same type as VAR. */
2173 create_zero_dim_array (tree var
, const char *base_name
)
2175 tree index_type
= build_index_type (integer_zero_node
);
2176 tree elt_type
= TREE_TYPE (var
);
2177 tree array_type
= build_array_type (elt_type
, index_type
);
2178 tree base
= create_tmp_var (array_type
, base_name
);
2180 add_referenced_var (base
);
2182 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2186 /* Returns true when PHI is a loop close phi node. */
2189 scalar_close_phi_node_p (gimple phi
)
2191 if (gimple_code (phi
) != GIMPLE_PHI
2192 || !is_gimple_reg (gimple_phi_result (phi
)))
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 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2214 remove_phi_node (psi
, false);
2215 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2216 SSA_NAME_DEF_STMT (res
) = stmt
;
2219 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2220 dimension array for it. */
2223 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2226 gimple phi
= gsi_stmt (*psi
);
2227 basic_block bb
= gimple_bb (phi
);
2228 tree res
= gimple_phi_result (phi
);
2229 tree var
= SSA_NAME_VAR (res
);
2230 tree zero_dim_array
= create_zero_dim_array (var
, "General_Reduction");
2231 gimple_stmt_iterator gsi
;
2235 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2237 tree arg
= gimple_phi_arg_def (phi
, i
);
2239 /* Try to avoid the insertion on edges as much as possible: this
2240 would avoid the insertion of code on loop latch edges, making
2241 the pattern matching of the vectorizer happy, or it would
2242 avoid the insertion of useless basic blocks. Note that it is
2243 incorrect to insert out of SSA copies close by their
2244 definition when they are more than two loop levels apart:
2245 for example, starting from a double nested loop
2255 the following transform is incorrect
2267 whereas inserting the copy on the incomming edge is correct
2279 if (TREE_CODE (arg
) == SSA_NAME
2280 && is_gimple_reg (arg
)
2281 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2282 && (flow_bb_inside_loop_p (bb
->loop_father
,
2283 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2284 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2285 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2286 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2288 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2289 zero_dim_array
, arg
);
2292 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2295 stmts
= gimple_seq_alloc ();
2297 stmt
= gimple_build_assign (res
, var
);
2298 remove_phi_node (psi
, false);
2299 SSA_NAME_DEF_STMT (res
) = stmt
;
2301 gsi
= gsi_last (stmts
);
2302 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2304 gsi
= gsi_after_labels (bb
);
2305 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2308 /* Return true when DEF can be analyzed in REGION by the scalar
2309 evolution analyzer. */
2312 scev_analyzable_p (tree def
, sese region
)
2314 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2315 loop_p loop
= loop_containing_stmt (stmt
);
2316 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2318 return !chrec_contains_undetermined (scev
);
2321 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2322 read from ZERO_DIM_ARRAY. */
2325 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2327 tree var
= SSA_NAME_VAR (def
);
2328 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2329 tree name
= make_ssa_name (var
, name_stmt
);
2331 use_operand_p use_p
;
2332 gimple_stmt_iterator gsi
;
2334 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2336 gimple_assign_set_lhs (name_stmt
, name
);
2338 gsi
= gsi_for_stmt (use_stmt
);
2339 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2341 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2342 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2343 replace_exp (use_p
, name
);
2345 update_stmt (use_stmt
);
2348 /* Rewrite the scalar dependences crossing the boundary of the BB
2349 containing STMT with an array. */
2352 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2354 gimple stmt
= gsi_stmt (*gsi
);
2355 imm_use_iterator imm_iter
;
2358 tree zero_dim_array
= NULL_TREE
;
2361 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2364 def
= gimple_assign_lhs (stmt
);
2365 if (!is_gimple_reg (def
)
2366 || scev_analyzable_p (def
, region
))
2369 def_bb
= gimple_bb (stmt
);
2371 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2372 if (def_bb
!= gimple_bb (use_stmt
)
2373 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2375 if (!zero_dim_array
)
2377 zero_dim_array
= create_zero_dim_array
2378 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2379 insert_out_of_ssa_copy (zero_dim_array
, def
);
2383 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2387 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2390 rewrite_reductions_out_of_ssa (scop_p scop
)
2393 gimple_stmt_iterator psi
;
2394 sese region
= SCOP_REGION (scop
);
2397 if (bb_in_sese_p (bb
, region
))
2398 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2400 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2401 rewrite_close_phi_out_of_ssa (&psi
);
2402 else if (reduction_phi_p (region
, &psi
))
2403 rewrite_phi_out_of_ssa (&psi
);
2406 update_ssa (TODO_update_ssa
);
2407 #ifdef ENABLE_CHECKING
2409 verify_loop_closed_ssa ();
2413 if (bb_in_sese_p (bb
, region
))
2414 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2415 rewrite_cross_bb_scalar_deps (region
, &psi
);
2417 update_ssa (TODO_update_ssa
);
2418 #ifdef ENABLE_CHECKING
2420 verify_loop_closed_ssa ();
2424 /* Returns the number of pbbs that are in loops contained in SCOP. */
2427 nb_pbbs_in_loops (scop_p scop
)
2433 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2434 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2440 /* Return the number of data references in BB that write in
2444 nb_data_writes_in_bb (basic_block bb
)
2447 gimple_stmt_iterator gsi
;
2449 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2450 if (gimple_vdef (gsi_stmt (gsi
)))
2456 /* Splits STMT out of its current BB. */
2459 split_reduction_stmt (gimple stmt
)
2461 gimple_stmt_iterator gsi
;
2462 basic_block bb
= gimple_bb (stmt
);
2465 /* Do not split basic blocks with no writes to memory: the reduction
2466 will be the only write to memory. */
2467 if (nb_data_writes_in_bb (bb
) == 0)
2470 split_block (bb
, stmt
);
2472 gsi
= gsi_last_bb (bb
);
2474 e
= split_block (bb
, gsi_stmt (gsi
));
2479 /* Return true when stmt is a reduction operation. */
2482 is_reduction_operation_p (gimple stmt
)
2484 return flag_associative_math
2485 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2486 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2489 /* Returns true when PHI contains an argument ARG. */
2492 phi_contains_arg (gimple phi
, tree arg
)
2496 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2497 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2503 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2506 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2510 if (TREE_CODE (arg
) != SSA_NAME
)
2513 stmt
= SSA_NAME_DEF_STMT (arg
);
2515 if (gimple_code (stmt
) == GIMPLE_PHI
)
2517 if (phi_contains_arg (stmt
, lhs
))
2522 if (gimple_num_ops (stmt
) == 2)
2523 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2525 if (is_reduction_operation_p (stmt
))
2527 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2530 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2536 /* Detect commutative and associative scalar reductions starting at
2540 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2541 VEC (gimple
, heap
) **in
,
2542 VEC (gimple
, heap
) **out
)
2544 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2548 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2549 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2556 /* Detect commutative and associative scalar reductions starting at
2560 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2561 VEC (gimple
, heap
) **out
)
2563 tree lhs
= gimple_assign_lhs (stmt
);
2565 if (gimple_num_ops (stmt
) == 2)
2566 return detect_commutative_reduction_arg (lhs
, stmt
,
2567 gimple_assign_rhs1 (stmt
),
2570 if (is_reduction_operation_p (stmt
))
2572 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2573 gimple_assign_rhs1 (stmt
),
2576 : detect_commutative_reduction_arg (lhs
, stmt
,
2577 gimple_assign_rhs2 (stmt
),
2584 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2587 follow_inital_value_to_phi (tree arg
, tree lhs
)
2591 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2594 stmt
= SSA_NAME_DEF_STMT (arg
);
2596 if (gimple_code (stmt
) == GIMPLE_PHI
2597 && phi_contains_arg (stmt
, lhs
))
2604 /* Return the argument of the loop PHI that is the inital value coming
2605 from outside the loop. */
2608 edge_initial_value_for_loop_phi (gimple phi
)
2612 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2614 edge e
= gimple_phi_arg_edge (phi
, i
);
2616 if (loop_depth (e
->src
->loop_father
)
2617 < loop_depth (e
->dest
->loop_father
))
2624 /* Return the argument of the loop PHI that is the inital value coming
2625 from outside the loop. */
2628 initial_value_for_loop_phi (gimple phi
)
2632 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2634 edge e
= gimple_phi_arg_edge (phi
, i
);
2636 if (loop_depth (e
->src
->loop_father
)
2637 < loop_depth (e
->dest
->loop_father
))
2638 return gimple_phi_arg_def (phi
, i
);
2644 /* Detect commutative and associative scalar reductions starting at
2645 the loop closed phi node CLOSE_PHI. */
2648 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2649 VEC (gimple
, heap
) **out
)
2651 if (scalar_close_phi_node_p (stmt
))
2653 tree arg
= gimple_phi_arg_def (stmt
, 0);
2654 gimple def
= SSA_NAME_DEF_STMT (arg
);
2655 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2659 tree lhs
= gimple_phi_result (stmt
);
2660 tree init
= initial_value_for_loop_phi (loop_phi
);
2661 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2663 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2664 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2671 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2672 return detect_commutative_reduction_assign (stmt
, in
, out
);
2677 /* Translate the scalar reduction statement STMT to an array RED
2678 knowing that its recursive phi node is LOOP_PHI. */
2681 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2684 basic_block bb
= gimple_bb (stmt
);
2685 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2686 tree res
= gimple_phi_result (loop_phi
);
2687 gimple assign
= gimple_build_assign (res
, red
);
2689 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2691 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2692 insert_gsi
= gsi_for_stmt (stmt
);
2693 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2696 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2699 insert_copyout (tree red
, gimple close_phi
)
2701 tree res
= gimple_phi_result (close_phi
);
2702 basic_block bb
= gimple_bb (close_phi
);
2703 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2704 gimple assign
= gimple_build_assign (res
, red
);
2706 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2709 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2712 insert_copyin (tree red
, gimple loop_phi
)
2715 tree init
= initial_value_for_loop_phi (loop_phi
);
2716 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2718 force_gimple_operand (expr
, &stmts
, true, NULL
);
2719 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2722 /* Rewrite out of SSA the reduction described by the loop phi nodes
2723 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2726 IN: stmt, loop_n, ..., loop_0
2727 OUT: stmt, close_n, ..., close_0
2729 the first element is the reduction statement, and the next elements
2730 are the loop and close phi nodes of each of the outer loops. */
2733 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2734 VEC (gimple
, heap
) *out
,
2740 gimple_stmt_iterator gsi
;
2742 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2744 gimple close_phi
= VEC_index (gimple
, out
, i
);
2748 gimple stmt
= loop_phi
;
2749 basic_block bb
= split_reduction_stmt (stmt
);
2751 SET_BIT (reductions
, bb
->index
);
2752 gcc_assert (close_phi
== loop_phi
);
2754 red
= create_zero_dim_array
2755 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2756 translate_scalar_reduction_to_array_for_stmt
2757 (red
, stmt
, VEC_index (gimple
, in
, 1));
2761 if (i
== VEC_length (gimple
, in
) - 1)
2763 insert_copyout (red
, close_phi
);
2764 insert_copyin (red
, loop_phi
);
2767 gsi
= gsi_for_phi_node (loop_phi
);
2768 remove_phi_node (&gsi
, false);
2770 gsi
= gsi_for_phi_node (close_phi
);
2771 remove_phi_node (&gsi
, false);
2775 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2778 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2781 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2782 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2784 detect_commutative_reduction (close_phi
, &in
, &out
);
2785 if (VEC_length (gimple
, in
) > 0)
2786 translate_scalar_reduction_to_array (in
, out
, reductions
);
2788 VEC_free (gimple
, heap
, in
);
2789 VEC_free (gimple
, heap
, out
);
2792 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2795 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2798 gimple_stmt_iterator gsi
;
2799 edge exit
= single_exit (loop
);
2804 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2805 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2809 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2812 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2817 FOR_EACH_LOOP (li
, loop
, 0)
2818 if (loop_in_sese_p (loop
, region
))
2819 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2821 gsi_commit_edge_inserts ();
2822 update_ssa (TODO_update_ssa
);
2823 #ifdef ENABLE_CHECKING
2825 verify_loop_closed_ssa ();
2829 /* A LOOP is in normal form for Graphite when it contains only one
2830 scalar phi node that defines the main induction variable of the
2831 loop, only one increment of the IV, and only one exit condition. */
2834 graphite_loop_normal_form (loop_p loop
)
2836 struct tree_niter_desc niter
;
2839 edge exit
= single_dom_exit (loop
);
2841 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2843 /* At this point we should know the number of iterations, */
2844 gcc_assert (known_niter
);
2846 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2849 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2851 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
);
2854 /* Rewrite all the loops of SCOP in normal form: one induction
2855 variable per loop. */
2858 scop_canonicalize_loops (scop_p scop
)
2863 FOR_EACH_LOOP (li
, loop
, 0)
2864 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2865 graphite_loop_normal_form (loop
);
2868 /* Builds the polyhedral representation for a SESE region. */
2871 build_poly_scop (scop_p scop
)
2873 sese region
= SCOP_REGION (scop
);
2874 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2876 sbitmap_zero (reductions
);
2877 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2878 rewrite_reductions_out_of_ssa (scop
);
2879 build_scop_bbs (scop
, reductions
);
2880 sbitmap_free (reductions
);
2882 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2883 Once CLooG is fixed, remove this guard. Anyways, it makes no
2884 sense to optimize a scop containing only PBBs that do not belong
2886 if (nb_pbbs_in_loops (scop
) == 0)
2889 scop_canonicalize_loops (scop
);
2890 build_sese_loop_nests (region
);
2891 build_sese_conditions (region
);
2892 find_scop_parameters (scop
);
2894 build_scop_iteration_domain (scop
);
2895 build_scop_context (scop
);
2897 add_conditions_to_constraints (scop
);
2899 build_scop_scattering (scop
);
2900 build_scop_drs (scop
);
2905 /* Always return false. Exercise the scop_to_clast function. */
2908 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2910 #ifdef ENABLE_CHECKING
2911 cloog_prog_clast pc
= scop_to_clast (scop
);
2912 cloog_clast_free (pc
.stmt
);
2913 cloog_program_free (pc
.prog
);