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 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
750 Otherwise returns -1. */
753 parameter_index_in_region_1 (tree name
, sese region
)
758 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
760 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
767 /* When the parameter NAME is in REGION, returns its index in
768 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
769 and returns the index of NAME. */
772 parameter_index_in_region (tree name
, sese region
)
776 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
778 i
= parameter_index_in_region_1 (name
, region
);
782 gcc_assert (SESE_ADD_PARAMS (region
));
784 i
= VEC_length (tree
, SESE_PARAMS (region
));
785 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
789 /* In the context of sese S, scan the expression E and translate it to
790 a linear expression C. When parsing a symbolic multiplication, K
791 represents the constant multiplier of an expression containing
795 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
798 if (e
== chrec_dont_know
)
801 switch (TREE_CODE (e
))
803 case POLYNOMIAL_CHREC
:
804 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
805 CHREC_VARIABLE (e
), c
);
806 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
810 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
815 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
817 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
818 value_multiply (val
, val
, k
);
819 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
823 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
830 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
832 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
833 value_multiply (val
, val
, k
);
834 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
838 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
843 case POINTER_PLUS_EXPR
:
844 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
845 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
850 ppl_Linear_Expression_t tmp_expr
= NULL
;
854 ppl_dimension_type dim
;
855 ppl_Linear_Expression_space_dimension (c
, &dim
);
856 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
859 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
860 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
864 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
866 ppl_delete_Linear_Expression (tmp_expr
);
874 ppl_Linear_Expression_t tmp_expr
= NULL
;
878 ppl_dimension_type dim
;
879 ppl_Linear_Expression_space_dimension (c
, &dim
);
880 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
883 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), 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_Coefficient_t coef
;
913 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
915 ppl_delete_Linear_Expression (tmp_expr
);
916 value_init (minus_one
);
917 value_set_si (minus_one
, -1);
918 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
919 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
920 value_clear (minus_one
);
921 ppl_delete_Coefficient (coef
);
929 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
933 ppl_dimension_type dim
;
934 ppl_Linear_Expression_space_dimension (c
, &dim
);
935 p
+= dim
- sese_nb_params (s
);
936 add_value_to_dim (p
, c
, k
);
943 scan_tree_for_params_int (e
, c
, k
);
947 case NON_LVALUE_EXPR
:
948 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
957 /* Find parameters with respect to REGION in BB. We are looking in memory
958 access functions, conditions and loop bounds. */
961 find_params_in_bb (sese region
, gimple_bb_p gbb
)
967 loop_p loop
= GBB_BB (gbb
)->loop_father
;
971 value_set_si (one
, 1);
973 /* Find parameters in the access functions of data references. */
974 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
975 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
976 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
978 /* Find parameters in conditional statements. */
979 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
981 tree lhs
= scalar_evolution_in_region (region
, loop
,
982 gimple_cond_lhs (stmt
));
983 tree rhs
= scalar_evolution_in_region (region
, loop
,
984 gimple_cond_rhs (stmt
));
986 scan_tree_for_params (region
, lhs
, NULL
, one
);
987 scan_tree_for_params (region
, rhs
, NULL
, one
);
993 /* Record the parameters used in the SCOP. A variable is a parameter
994 in a scop if it does not vary during the execution of that scop. */
997 find_scop_parameters (scop_p scop
)
1001 sese region
= SCOP_REGION (scop
);
1006 value_set_si (one
, 1);
1008 /* Find the parameters used in the loop bounds. */
1009 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1011 tree nb_iters
= number_of_latch_executions (loop
);
1013 if (!chrec_contains_symbols (nb_iters
))
1016 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1017 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1022 /* Find the parameters used in data accesses. */
1023 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1024 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1026 scop_set_nb_params (scop
, sese_nb_params (region
));
1027 SESE_ADD_PARAMS (region
) = false;
1029 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1030 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1033 /* Returns a gimple_bb from BB. */
1035 static inline gimple_bb_p
1036 gbb_from_bb (basic_block bb
)
1038 return (gimple_bb_p
) bb
->aux
;
1041 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1042 the constraints for the surrounding loops. */
1045 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1046 ppl_Polyhedron_t outer_ph
, int nb
,
1047 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1050 ppl_Polyhedron_t ph
;
1051 tree nb_iters
= number_of_latch_executions (loop
);
1052 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1053 sese region
= SCOP_REGION (scop
);
1056 ppl_const_Constraint_System_t pcs
;
1057 ppl_dimension_type
*map
1058 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1060 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1061 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1062 ppl_Polyhedron_add_constraints (ph
, pcs
);
1064 for (i
= 0; i
< (int) nb
; i
++)
1066 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1070 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1076 ppl_Constraint_t lb
;
1077 ppl_Linear_Expression_t lb_expr
;
1079 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1080 ppl_set_coef (lb_expr
, nb
, 1);
1081 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1082 ppl_delete_Linear_Expression (lb_expr
);
1083 ppl_Polyhedron_add_constraint (ph
, lb
);
1084 ppl_delete_Constraint (lb
);
1087 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1089 ppl_Constraint_t ub
;
1090 ppl_Linear_Expression_t ub_expr
;
1092 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1094 /* loop_i <= cst_nb_iters */
1095 ppl_set_coef (ub_expr
, nb
, -1);
1096 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1097 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1098 ppl_Polyhedron_add_constraint (ph
, ub
);
1099 ppl_delete_Linear_Expression (ub_expr
);
1100 ppl_delete_Constraint (ub
);
1102 else if (!chrec_contains_undetermined (nb_iters
))
1105 ppl_Constraint_t ub
;
1106 ppl_Linear_Expression_t ub_expr
;
1110 value_set_si (one
, 1);
1111 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1112 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1113 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1116 /* N <= estimated_nb_iters
1118 FIXME: This is a workaround that should go away once we will
1119 have the PIP algorithm. */
1120 if (estimated_loop_iterations (loop
, true, &nit
))
1123 ppl_Linear_Expression_t nb_iters_le
;
1124 ppl_Polyhedron_t pol
;
1125 graphite_dim_t n
= scop_nb_params (scop
);
1126 ppl_Coefficient_t coef
;
1128 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1129 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1132 /* Construct the negated number of last iteration in VAL. */
1134 mpz_set_double_int (val
, nit
, false);
1135 value_sub_int (val
, val
, 1);
1136 value_oppose (val
, val
);
1138 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1139 Subtract estimated number of last iteration and assert that result
1141 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1142 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1143 ppl_delete_Coefficient (coef
);
1144 ppl_new_Constraint (&ub
, nb_iters_le
,
1145 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1146 ppl_Polyhedron_add_constraint (pol
, ub
);
1148 /* Remove all but last N dimensions from POL to obtain constraints
1151 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- n
);
1153 for (i
= 0; i
< dim
- n
; i
++)
1155 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- n
);
1159 /* Add constraints on parameters to SCoP context. */
1161 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1162 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1163 (&constraints_ps
, pol
);
1164 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1165 (SCOP_CONTEXT (scop
), constraints_ps
);
1166 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1169 ppl_delete_Polyhedron (pol
);
1170 ppl_delete_Linear_Expression (nb_iters_le
);
1171 ppl_delete_Constraint (ub
);
1175 /* loop_i <= expr_nb_iters */
1176 ppl_set_coef (ub_expr
, nb
, -1);
1177 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1178 ppl_Polyhedron_add_constraint (ph
, ub
);
1179 ppl_delete_Linear_Expression (ub_expr
);
1180 ppl_delete_Constraint (ub
);
1185 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1186 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1190 && loop_in_sese_p (loop
->next
, region
))
1191 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1193 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1194 (&domains
[loop
->num
], ph
);
1196 ppl_delete_Polyhedron (ph
);
1199 /* Returns a linear expression for tree T evaluated in PBB. */
1201 static ppl_Linear_Expression_t
1202 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1205 ppl_Linear_Expression_t res
;
1206 ppl_dimension_type dim
;
1207 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1208 loop_p loop
= pbb_loop (pbb
);
1210 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1211 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1213 t
= scalar_evolution_in_region (region
, loop
, t
);
1214 gcc_assert (!automatically_generated_chrec_p (t
));
1217 value_set_si (one
, 1);
1218 scan_tree_for_params (region
, t
, res
, one
);
1224 /* Returns the ppl constraint type from the gimple tree code CODE. */
1226 static enum ppl_enum_Constraint_Type
1227 ppl_constraint_type_from_tree_code (enum tree_code code
)
1231 /* We do not support LT and GT to be able to work with C_Polyhedron.
1232 As we work on integer polyhedron "a < b" can be expressed by
1239 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1242 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1245 return PPL_CONSTRAINT_TYPE_EQUAL
;
1252 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1253 CODE is used as the comparison operator. This allows us to invert the
1254 condition or to handle inequalities. */
1257 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1258 poly_bb_p pbb
, enum tree_code code
)
1261 ppl_Coefficient_t c
;
1262 ppl_Linear_Expression_t left
, right
;
1263 ppl_Constraint_t cstr
;
1264 enum ppl_enum_Constraint_Type type
;
1266 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1267 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1269 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1270 the left or the right side of the expression. */
1271 if (code
== LT_EXPR
)
1274 value_set_si (v
, 1);
1275 ppl_new_Coefficient (&c
);
1276 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1277 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1278 ppl_delete_Coefficient (c
);
1283 else if (code
== GT_EXPR
)
1286 value_set_si (v
, 1);
1287 ppl_new_Coefficient (&c
);
1288 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1289 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1290 ppl_delete_Coefficient (c
);
1296 type
= ppl_constraint_type_from_tree_code (code
);
1298 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1300 ppl_new_Constraint (&cstr
, left
, type
);
1301 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1303 ppl_delete_Constraint (cstr
);
1304 ppl_delete_Linear_Expression (left
);
1305 ppl_delete_Linear_Expression (right
);
1308 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1309 operator. This allows us to invert the condition or to handle
1313 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1315 if (code
== NE_EXPR
)
1317 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1318 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1319 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1321 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1322 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1323 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1325 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1328 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1331 /* Add conditions to the domain of PBB. */
1334 add_conditions_to_domain (poly_bb_p pbb
)
1338 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1339 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1341 if (VEC_empty (gimple
, conditions
))
1344 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1345 switch (gimple_code (stmt
))
1349 enum tree_code code
= gimple_cond_code (stmt
);
1351 /* The conditions for ELSE-branches are inverted. */
1352 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1353 code
= invert_tree_comparison (code
, false);
1355 add_condition_to_pbb (pbb
, stmt
, code
);
1360 /* Switch statements are not supported right now - fall throught. */
1368 /* Structure used to pass data to dom_walk. */
1372 VEC (gimple
, heap
) **conditions
, **cases
;
1376 /* Returns non NULL when BB has a single predecessor and the last
1377 statement of that predecessor is a COND_EXPR. */
1380 single_pred_cond (basic_block bb
)
1382 if (single_pred_p (bb
))
1384 edge e
= single_pred_edge (bb
);
1385 basic_block pred
= e
->src
;
1386 gimple stmt
= last_stmt (pred
);
1388 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1394 /* Call-back for dom_walk executed before visiting the dominated
1398 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1401 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1402 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1403 VEC (gimple
, heap
) **cases
= data
->cases
;
1404 gimple_bb_p gbb
= gbb_from_bb (bb
);
1405 gimple stmt
= single_pred_cond (bb
);
1407 if (!bb_in_sese_p (bb
, data
->region
))
1412 edge e
= single_pred_edge (bb
);
1414 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1416 if (e
->flags
& EDGE_TRUE_VALUE
)
1417 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1419 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1424 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1425 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1429 /* Call-back for dom_walk executed after visiting the dominated
1433 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1436 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1437 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1438 VEC (gimple
, heap
) **cases
= data
->cases
;
1440 if (!bb_in_sese_p (bb
, data
->region
))
1443 if (single_pred_cond (bb
))
1445 VEC_pop (gimple
, *conditions
);
1446 VEC_pop (gimple
, *cases
);
1450 /* Record all conditions in REGION. */
1453 build_sese_conditions (sese region
)
1455 struct dom_walk_data walk_data
;
1456 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1457 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1460 data
.conditions
= &conditions
;
1461 data
.cases
= &cases
;
1462 data
.region
= region
;
1464 walk_data
.dom_direction
= CDI_DOMINATORS
;
1465 walk_data
.initialize_block_local_data
= NULL
;
1466 walk_data
.before_dom_children
= build_sese_conditions_before
;
1467 walk_data
.after_dom_children
= build_sese_conditions_after
;
1468 walk_data
.global_data
= &data
;
1469 walk_data
.block_local_data_size
= 0;
1471 init_walk_dominator_tree (&walk_data
);
1472 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1473 fini_walk_dominator_tree (&walk_data
);
1475 VEC_free (gimple
, heap
, conditions
);
1476 VEC_free (gimple
, heap
, cases
);
1479 /* Traverses all the GBBs of the SCOP and add their constraints to the
1480 iteration domains. */
1483 add_conditions_to_constraints (scop_p scop
)
1488 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1489 add_conditions_to_domain (pbb
);
1492 /* Add constraints on the possible values of parameter P from the type
1496 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1498 ppl_Constraint_t cstr
;
1499 ppl_Linear_Expression_t le
;
1500 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1501 tree type
= TREE_TYPE (parameter
);
1504 /* Disabled until we fix CPU2006. */
1507 if (!INTEGRAL_TYPE_P (type
))
1510 lb
= TYPE_MIN_VALUE (type
);
1511 ub
= TYPE_MAX_VALUE (type
);
1515 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1516 ppl_set_coef (le
, p
, -1);
1517 ppl_set_inhomogeneous_tree (le
, lb
);
1518 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1519 ppl_Polyhedron_add_constraint (context
, cstr
);
1520 ppl_delete_Linear_Expression (le
);
1521 ppl_delete_Constraint (cstr
);
1526 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1527 ppl_set_coef (le
, p
, -1);
1528 ppl_set_inhomogeneous_tree (le
, ub
);
1529 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1530 ppl_Polyhedron_add_constraint (context
, cstr
);
1531 ppl_delete_Linear_Expression (le
);
1532 ppl_delete_Constraint (cstr
);
1536 /* Build the context of the SCOP. The context usually contains extra
1537 constraints that are added to the iteration domains that constrain
1541 build_scop_context (scop_p scop
)
1543 ppl_Polyhedron_t context
;
1544 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1545 graphite_dim_t p
, n
= scop_nb_params (scop
);
1547 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1549 for (p
= 0; p
< n
; p
++)
1550 add_param_constraints (scop
, context
, p
);
1552 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1554 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1555 (SCOP_CONTEXT (scop
), ps
);
1557 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1558 ppl_delete_Polyhedron (context
);
1561 /* Build the iteration domains: the loops belonging to the current
1562 SCOP, and that vary for the execution of the current basic block.
1563 Returns false if there is no loop in SCOP. */
1566 build_scop_iteration_domain (scop_p scop
)
1569 sese region
= SCOP_REGION (scop
);
1571 ppl_Polyhedron_t ph
;
1573 int nb_loops
= number_of_loops ();
1574 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1575 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1577 for (i
= 0; i
< nb_loops
; i
++)
1580 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1582 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1583 if (!loop_in_sese_p (loop_outer (loop
), region
))
1584 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1586 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1587 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1588 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1589 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1590 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1592 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1593 (&PBB_DOMAIN (pbb
), ph
);
1595 for (i
= 0; i
< nb_loops
; i
++)
1597 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1599 ppl_delete_Polyhedron (ph
);
1603 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1604 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1605 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1609 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1610 ppl_dimension_type accessp_nb_dims
,
1611 ppl_dimension_type dom_nb_dims
)
1613 ppl_Linear_Expression_t alias
;
1614 ppl_Constraint_t cstr
;
1615 int alias_set_num
= 0;
1616 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1618 if (bap
&& bap
->alias_set
)
1619 alias_set_num
= *(bap
->alias_set
);
1621 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1623 ppl_set_coef (alias
, dom_nb_dims
, 1);
1624 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1625 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1626 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1628 ppl_delete_Linear_Expression (alias
);
1629 ppl_delete_Constraint (cstr
);
1632 /* Add to ACCESSES polyhedron equalities defining the access functions
1633 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1634 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1635 PBB is the poly_bb_p that contains the data reference DR. */
1638 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1639 ppl_dimension_type accessp_nb_dims
,
1640 ppl_dimension_type dom_nb_dims
,
1643 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1645 scop_p scop
= PBB_SCOP (pbb
);
1646 sese region
= SCOP_REGION (scop
);
1650 for (i
= 0; i
< nb_subscripts
; i
++)
1652 ppl_Linear_Expression_t fn
, access
;
1653 ppl_Constraint_t cstr
;
1654 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1655 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1657 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1658 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1660 value_set_si (v
, 1);
1661 scan_tree_for_params (region
, afn
, fn
, v
);
1662 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1664 ppl_set_coef (access
, subscript
, -1);
1665 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1666 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1668 ppl_delete_Linear_Expression (fn
);
1669 ppl_delete_Linear_Expression (access
);
1670 ppl_delete_Constraint (cstr
);
1676 /* Add constrains representing the size of the accessed data to the
1677 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1678 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1682 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1683 ppl_dimension_type accessp_nb_dims
,
1684 ppl_dimension_type dom_nb_dims
)
1686 tree ref
= DR_REF (dr
);
1687 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1689 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1691 ppl_Linear_Expression_t expr
;
1692 ppl_Constraint_t cstr
;
1693 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1696 if (TREE_CODE (ref
) != ARRAY_REF
)
1699 low
= array_ref_low_bound (ref
);
1701 /* subscript - low >= 0 */
1702 if (host_integerp (low
, 0))
1704 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1705 ppl_set_coef (expr
, subscript
, 1);
1707 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1709 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1710 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1711 ppl_delete_Linear_Expression (expr
);
1712 ppl_delete_Constraint (cstr
);
1715 high
= array_ref_up_bound (ref
);
1717 /* high - subscript >= 0 */
1718 if (high
&& host_integerp (high
, 0)
1719 /* 1-element arrays at end of structures may extend over
1720 their declared size. */
1721 && !(array_at_struct_end_p (ref
)
1722 && operand_equal_p (low
, high
, 0)))
1724 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1725 ppl_set_coef (expr
, subscript
, -1);
1727 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1729 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1730 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1731 ppl_delete_Linear_Expression (expr
);
1732 ppl_delete_Constraint (cstr
);
1737 /* Build data accesses for DR in PBB. */
1740 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1742 ppl_Polyhedron_t accesses
;
1743 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1744 ppl_dimension_type dom_nb_dims
;
1745 ppl_dimension_type accessp_nb_dims
;
1746 int dr_base_object_set
;
1748 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1750 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1752 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1754 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1755 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1756 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1758 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1760 ppl_delete_Polyhedron (accesses
);
1763 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1765 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1766 dr
, DR_NUM_DIMENSIONS (dr
));
1769 /* Write to FILE the alias graph of data references in DIMACS format. */
1772 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1773 VEC (data_reference_p
, heap
) *drs
)
1775 int num_vertex
= VEC_length (data_reference_p
, drs
);
1777 data_reference_p dr1
, dr2
;
1780 if (num_vertex
== 0)
1783 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1784 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1785 if (dr_may_alias_p (dr1
, dr2
))
1788 fprintf (file
, "$\n");
1791 fprintf (file
, "c %s\n", comment
);
1793 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1795 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1796 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1797 if (dr_may_alias_p (dr1
, dr2
))
1798 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1803 /* Write to FILE the alias graph of data references in DOT format. */
1806 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1807 VEC (data_reference_p
, heap
) *drs
)
1809 int num_vertex
= VEC_length (data_reference_p
, drs
);
1810 data_reference_p dr1
, dr2
;
1813 if (num_vertex
== 0)
1816 fprintf (file
, "$\n");
1819 fprintf (file
, "c %s\n", comment
);
1821 /* First print all the vertices. */
1822 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1823 fprintf (file
, "n%d;\n", i
);
1825 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1826 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1827 if (dr_may_alias_p (dr1
, dr2
))
1828 fprintf (file
, "n%d n%d\n", i
, j
);
1833 /* Write to FILE the alias graph of data references in ECC format. */
1836 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1837 VEC (data_reference_p
, heap
) *drs
)
1839 int num_vertex
= VEC_length (data_reference_p
, drs
);
1840 data_reference_p dr1
, dr2
;
1843 if (num_vertex
== 0)
1846 fprintf (file
, "$\n");
1849 fprintf (file
, "c %s\n", comment
);
1851 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1852 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1853 if (dr_may_alias_p (dr1
, dr2
))
1854 fprintf (file
, "%d %d\n", i
, j
);
1859 /* Check if DR1 and DR2 are in the same object set. */
1862 dr_same_base_object_p (const struct data_reference
*dr1
,
1863 const struct data_reference
*dr2
)
1865 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1868 /* Uses DFS component number as representative of alias-sets. Also tests for
1869 optimality by verifying if every connected component is a clique. Returns
1870 true (1) if the above test is true, and false (0) otherwise. */
1873 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1875 int num_vertices
= VEC_length (data_reference_p
, drs
);
1876 struct graph
*g
= new_graph (num_vertices
);
1877 data_reference_p dr1
, dr2
;
1879 int num_connected_components
;
1880 int v_indx1
, v_indx2
, num_vertices_in_component
;
1883 struct graph_edge
*e
;
1884 int this_component_is_clique
;
1885 int all_components_are_cliques
= 1;
1887 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1888 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1889 if (dr_may_alias_p (dr1
, dr2
))
1895 all_vertices
= XNEWVEC (int, num_vertices
);
1896 vertices
= XNEWVEC (int, num_vertices
);
1897 for (i
= 0; i
< num_vertices
; i
++)
1898 all_vertices
[i
] = i
;
1900 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1902 for (i
= 0; i
< g
->n_vertices
; i
++)
1904 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1905 base_alias_pair
*bap
;
1908 bap
= (base_alias_pair
*)(dr
->aux
);
1910 bap
->alias_set
= XNEW (int);
1911 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1914 /* Verify if the DFS numbering results in optimal solution. */
1915 for (i
= 0; i
< num_connected_components
; i
++)
1917 num_vertices_in_component
= 0;
1918 /* Get all vertices whose DFS component number is the same as i. */
1919 for (j
= 0; j
< num_vertices
; j
++)
1920 if (g
->vertices
[j
].component
== i
)
1921 vertices
[num_vertices_in_component
++] = j
;
1923 /* Now test if the vertices in 'vertices' form a clique, by testing
1924 for edges among each pair. */
1925 this_component_is_clique
= 1;
1926 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1928 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1930 /* Check if the two vertices are connected by iterating
1931 through all the edges which have one of these are source. */
1932 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1935 if (e
->src
== vertices
[v_indx1
])
1941 this_component_is_clique
= 0;
1945 if (!this_component_is_clique
)
1946 all_components_are_cliques
= 0;
1950 free (all_vertices
);
1953 return all_components_are_cliques
;
1956 /* Group each data reference in DRS with it's base object set num. */
1959 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1961 int num_vertex
= VEC_length (data_reference_p
, drs
);
1962 struct graph
*g
= new_graph (num_vertex
);
1963 data_reference_p dr1
, dr2
;
1967 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1968 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1969 if (dr_same_base_object_p (dr1
, dr2
))
1975 queue
= XNEWVEC (int, num_vertex
);
1976 for (i
= 0; i
< num_vertex
; i
++)
1979 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1981 for (i
= 0; i
< g
->n_vertices
; i
++)
1983 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1984 base_alias_pair
*bap
;
1987 bap
= (base_alias_pair
*)(dr
->aux
);
1989 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1996 /* Build the data references for PBB. */
1999 build_pbb_drs (poly_bb_p pbb
)
2002 data_reference_p dr
;
2003 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2005 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2006 build_poly_dr (dr
, pbb
);
2009 /* Dump to file the alias graphs for the data references in DRS. */
2012 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2015 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2017 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2020 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2021 current_function_name ());
2022 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2023 fclose (file_dimacs
);
2026 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2029 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2030 current_function_name ());
2031 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2035 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2038 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2039 current_function_name ());
2040 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2045 /* Build data references in SCOP. */
2048 build_scop_drs (scop_p scop
)
2052 data_reference_p dr
;
2053 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2055 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2056 for (j
= 0; VEC_iterate (data_reference_p
,
2057 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2058 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2060 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2061 dr
->aux
= XNEW (base_alias_pair
);
2063 if (!build_alias_set_optimal_p (drs
))
2065 /* TODO: Add support when building alias set is not optimal. */
2069 build_base_obj_set_for_drs (drs
);
2071 /* When debugging, enable the following code. This cannot be used
2072 in production compilers. */
2074 dump_alias_graphs (drs
);
2076 VEC_free (data_reference_p
, heap
, drs
);
2078 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2079 build_pbb_drs (pbb
);
2082 /* Return a gsi at the position of the phi node STMT. */
2084 static gimple_stmt_iterator
2085 gsi_for_phi_node (gimple stmt
)
2087 gimple_stmt_iterator psi
;
2088 basic_block bb
= gimple_bb (stmt
);
2090 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2091 if (stmt
== gsi_stmt (psi
))
2098 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2101 insert_out_of_ssa_copy (tree res
, tree var
)
2105 gimple_stmt_iterator si
;
2106 gimple_stmt_iterator gsi
;
2108 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2109 stmt
= gimple_build_assign (res
, var
);
2111 stmts
= gimple_seq_alloc ();
2112 si
= gsi_last (stmts
);
2113 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2115 stmt
= SSA_NAME_DEF_STMT (var
);
2116 if (gimple_code (stmt
) == GIMPLE_PHI
)
2118 gsi
= gsi_after_labels (gimple_bb (stmt
));
2119 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2123 gsi
= gsi_for_stmt (stmt
);
2124 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2128 /* Insert on edge E the assignment "RES := EXPR". */
2131 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2133 gimple_stmt_iterator gsi
;
2135 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2136 gimple stmt
= gimple_build_assign (res
, var
);
2139 stmts
= gimple_seq_alloc ();
2141 gsi
= gsi_last (stmts
);
2142 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2143 gsi_insert_seq_on_edge (e
, stmts
);
2144 gsi_commit_edge_inserts ();
2147 /* Creates a zero dimension array of the same type as VAR. */
2150 create_zero_dim_array (tree var
, const char *base_name
)
2152 tree index_type
= build_index_type (integer_zero_node
);
2153 tree elt_type
= TREE_TYPE (var
);
2154 tree array_type
= build_array_type (elt_type
, index_type
);
2155 tree base
= create_tmp_var (array_type
, base_name
);
2157 add_referenced_var (base
);
2159 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2163 /* Returns true when PHI is a loop close phi node. */
2166 scalar_close_phi_node_p (gimple phi
)
2168 if (gimple_code (phi
) != GIMPLE_PHI
2169 || !is_gimple_reg (gimple_phi_result (phi
)))
2172 return (gimple_phi_num_args (phi
) == 1);
2175 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2176 dimension array for it. */
2179 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2181 gimple phi
= gsi_stmt (*psi
);
2182 tree res
= gimple_phi_result (phi
);
2183 tree var
= SSA_NAME_VAR (res
);
2184 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2185 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2186 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2187 tree arg
= gimple_phi_arg_def (phi
, 0);
2189 if (TREE_CODE (arg
) == SSA_NAME
)
2190 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2192 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi
)),
2193 zero_dim_array
, arg
);
2195 remove_phi_node (psi
, false);
2196 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2197 SSA_NAME_DEF_STMT (res
) = stmt
;
2200 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2201 dimension array for it. */
2204 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2207 gimple phi
= gsi_stmt (*psi
);
2208 basic_block bb
= gimple_bb (phi
);
2209 tree res
= gimple_phi_result (phi
);
2210 tree var
= SSA_NAME_VAR (res
);
2211 tree zero_dim_array
= create_zero_dim_array (var
, "General_Reduction");
2212 gimple_stmt_iterator gsi
;
2216 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2218 tree arg
= gimple_phi_arg_def (phi
, i
);
2220 /* Try to avoid the insertion on edges as much as possible: this
2221 would avoid the insertion of code on loop latch edges, making
2222 the pattern matching of the vectorizer happy, or it would
2223 avoid the insertion of useless basic blocks. Note that it is
2224 incorrect to insert out of SSA copies close by their
2225 definition when they are more than two loop levels apart:
2226 for example, starting from a double nested loop
2236 the following transform is incorrect
2248 whereas inserting the copy on the incoming edge is correct
2260 if (TREE_CODE (arg
) == SSA_NAME
2261 && is_gimple_reg (arg
)
2262 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2263 && (flow_bb_inside_loop_p (bb
->loop_father
,
2264 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2265 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2266 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2267 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2269 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2270 zero_dim_array
, arg
);
2273 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2276 stmts
= gimple_seq_alloc ();
2278 stmt
= gimple_build_assign (res
, var
);
2279 remove_phi_node (psi
, false);
2280 SSA_NAME_DEF_STMT (res
) = stmt
;
2282 gsi
= gsi_last (stmts
);
2283 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2285 gsi
= gsi_after_labels (bb
);
2286 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2289 /* Return true when DEF can be analyzed in REGION by the scalar
2290 evolution analyzer. */
2293 scev_analyzable_p (tree def
, sese region
)
2295 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2296 loop_p loop
= loop_containing_stmt (stmt
);
2297 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2299 return !chrec_contains_undetermined (scev
);
2302 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2303 read from ZERO_DIM_ARRAY. */
2306 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2308 tree var
= SSA_NAME_VAR (def
);
2309 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2310 tree name
= make_ssa_name (var
, name_stmt
);
2312 use_operand_p use_p
;
2313 gimple_stmt_iterator gsi
;
2315 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2317 gimple_assign_set_lhs (name_stmt
, name
);
2319 gsi
= gsi_for_stmt (use_stmt
);
2320 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2322 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2323 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2324 replace_exp (use_p
, name
);
2326 update_stmt (use_stmt
);
2329 /* Rewrite the scalar dependences crossing the boundary of the BB
2330 containing STMT with an array. */
2333 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2335 gimple stmt
= gsi_stmt (*gsi
);
2336 imm_use_iterator imm_iter
;
2339 tree zero_dim_array
= NULL_TREE
;
2342 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2345 def
= gimple_assign_lhs (stmt
);
2346 if (!is_gimple_reg (def
)
2347 || scev_analyzable_p (def
, region
))
2350 def_bb
= gimple_bb (stmt
);
2352 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2353 if (def_bb
!= gimple_bb (use_stmt
)
2354 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2356 if (!zero_dim_array
)
2358 zero_dim_array
= create_zero_dim_array
2359 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2360 insert_out_of_ssa_copy (zero_dim_array
, def
);
2364 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2368 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2371 rewrite_reductions_out_of_ssa (scop_p scop
)
2374 gimple_stmt_iterator psi
;
2375 sese region
= SCOP_REGION (scop
);
2378 if (bb_in_sese_p (bb
, region
))
2379 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2381 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2382 rewrite_close_phi_out_of_ssa (&psi
);
2383 else if (reduction_phi_p (region
, &psi
))
2384 rewrite_phi_out_of_ssa (&psi
);
2387 update_ssa (TODO_update_ssa
);
2388 #ifdef ENABLE_CHECKING
2390 verify_loop_closed_ssa ();
2394 if (bb_in_sese_p (bb
, region
))
2395 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2396 rewrite_cross_bb_scalar_deps (region
, &psi
);
2398 update_ssa (TODO_update_ssa
);
2399 #ifdef ENABLE_CHECKING
2401 verify_loop_closed_ssa ();
2405 /* Returns the number of pbbs that are in loops contained in SCOP. */
2408 nb_pbbs_in_loops (scop_p scop
)
2414 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2415 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2421 /* Return the number of data references in BB that write in
2425 nb_data_writes_in_bb (basic_block bb
)
2428 gimple_stmt_iterator gsi
;
2430 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2431 if (gimple_vdef (gsi_stmt (gsi
)))
2437 /* Splits STMT out of its current BB. */
2440 split_reduction_stmt (gimple stmt
)
2442 gimple_stmt_iterator gsi
;
2443 basic_block bb
= gimple_bb (stmt
);
2446 /* Do not split basic blocks with no writes to memory: the reduction
2447 will be the only write to memory. */
2448 if (nb_data_writes_in_bb (bb
) == 0)
2451 split_block (bb
, stmt
);
2453 if (gsi_one_before_end_p (gsi_start_bb (bb
)))
2456 gsi
= gsi_last_bb (bb
);
2458 e
= split_block (bb
, gsi_stmt (gsi
));
2463 /* Return true when stmt is a reduction operation. */
2466 is_reduction_operation_p (gimple stmt
)
2468 enum tree_code code
;
2470 gcc_assert (is_gimple_assign (stmt
));
2471 code
= gimple_assign_rhs_code (stmt
);
2473 return flag_associative_math
2474 && commutative_tree_code (code
)
2475 && associative_tree_code (code
);
2478 /* Returns true when PHI contains an argument ARG. */
2481 phi_contains_arg (gimple phi
, tree arg
)
2485 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2486 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2492 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2495 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2499 if (TREE_CODE (arg
) != SSA_NAME
)
2502 stmt
= SSA_NAME_DEF_STMT (arg
);
2504 if (gimple_code (stmt
) == GIMPLE_NOP
2505 || gimple_code (stmt
) == GIMPLE_CALL
)
2508 if (gimple_code (stmt
) == GIMPLE_PHI
)
2510 if (phi_contains_arg (stmt
, lhs
))
2515 if (!is_gimple_assign (stmt
))
2518 if (gimple_num_ops (stmt
) == 2)
2519 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2521 if (is_reduction_operation_p (stmt
))
2523 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2526 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2532 /* Detect commutative and associative scalar reductions starting at
2533 the STMT. Return the phi node of the reduction cycle, or NULL. */
2536 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2537 VEC (gimple
, heap
) **in
,
2538 VEC (gimple
, heap
) **out
)
2540 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2545 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2546 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2550 /* Detect commutative and associative scalar reductions starting at
2551 the STMT. Return the phi node of the reduction cycle, or NULL. */
2554 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2555 VEC (gimple
, heap
) **out
)
2557 tree lhs
= gimple_assign_lhs (stmt
);
2559 if (gimple_num_ops (stmt
) == 2)
2560 return detect_commutative_reduction_arg (lhs
, stmt
,
2561 gimple_assign_rhs1 (stmt
),
2564 if (is_reduction_operation_p (stmt
))
2566 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2567 gimple_assign_rhs1 (stmt
),
2570 : detect_commutative_reduction_arg (lhs
, stmt
,
2571 gimple_assign_rhs2 (stmt
),
2578 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2581 follow_inital_value_to_phi (tree arg
, tree lhs
)
2585 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2588 stmt
= SSA_NAME_DEF_STMT (arg
);
2590 if (gimple_code (stmt
) == GIMPLE_PHI
2591 && phi_contains_arg (stmt
, lhs
))
2598 /* Return the argument of the loop PHI that is the inital value coming
2599 from outside the loop. */
2602 edge_initial_value_for_loop_phi (gimple phi
)
2606 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2608 edge e
= gimple_phi_arg_edge (phi
, i
);
2610 if (loop_depth (e
->src
->loop_father
)
2611 < loop_depth (e
->dest
->loop_father
))
2618 /* Return the argument of the loop PHI that is the inital value coming
2619 from outside the loop. */
2622 initial_value_for_loop_phi (gimple phi
)
2626 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2628 edge e
= gimple_phi_arg_edge (phi
, i
);
2630 if (loop_depth (e
->src
->loop_father
)
2631 < loop_depth (e
->dest
->loop_father
))
2632 return gimple_phi_arg_def (phi
, i
);
2638 /* Detect commutative and associative scalar reductions starting at
2639 the loop closed phi node CLOSE_PHI. Return the phi node of the
2640 reduction cycle, or NULL. */
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
, loop_phi
;
2651 if (TREE_CODE (arg
) != SSA_NAME
)
2654 def
= SSA_NAME_DEF_STMT (arg
);
2655 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 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2685 tree res
= gimple_phi_result (loop_phi
);
2686 gimple assign
= gimple_build_assign (res
, red
);
2688 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2690 insert_gsi
= gsi_after_labels (gimple_bb (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 /* Removes the PHI node and resets all the debug stmts that are using
2726 remove_phi (gimple phi
)
2728 imm_use_iterator imm_iter
;
2730 use_operand_p use_p
;
2731 gimple_stmt_iterator gsi
;
2732 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2736 def
= PHI_RESULT (phi
);
2737 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2739 stmt
= USE_STMT (use_p
);
2741 if (is_gimple_debug (stmt
))
2743 gimple_debug_bind_reset_value (stmt
);
2744 VEC_safe_push (gimple
, heap
, update
, stmt
);
2748 for (i
= 0; VEC_iterate (gimple
, update
, i
, stmt
); i
++)
2751 VEC_free (gimple
, heap
, update
);
2753 gsi
= gsi_for_phi_node (phi
);
2754 remove_phi_node (&gsi
, false);
2757 /* Rewrite out of SSA the reduction described by the loop phi nodes
2758 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2761 IN: stmt, loop_n, ..., loop_0
2762 OUT: stmt, close_n, ..., close_0
2764 the first element is the reduction statement, and the next elements
2765 are the loop and close phi nodes of each of the outer loops. */
2768 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2769 VEC (gimple
, heap
) *out
,
2776 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2778 gimple close_phi
= VEC_index (gimple
, out
, i
);
2782 gimple stmt
= loop_phi
;
2783 basic_block bb
= split_reduction_stmt (stmt
);
2785 SET_BIT (reductions
, bb
->index
);
2786 gcc_assert (close_phi
== loop_phi
);
2788 red
= create_zero_dim_array
2789 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2790 translate_scalar_reduction_to_array_for_stmt
2791 (red
, stmt
, VEC_index (gimple
, in
, 1));
2795 if (i
== VEC_length (gimple
, in
) - 1)
2797 insert_copyout (red
, close_phi
);
2798 insert_copyin (red
, loop_phi
);
2801 remove_phi (loop_phi
);
2802 remove_phi (close_phi
);
2806 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2809 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2812 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2813 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2815 detect_commutative_reduction (close_phi
, &in
, &out
);
2816 if (VEC_length (gimple
, in
) > 0)
2817 translate_scalar_reduction_to_array (in
, out
, reductions
);
2819 VEC_free (gimple
, heap
, in
);
2820 VEC_free (gimple
, heap
, out
);
2823 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2826 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2829 gimple_stmt_iterator gsi
;
2830 edge exit
= single_exit (loop
);
2835 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2836 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2840 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2843 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2848 FOR_EACH_LOOP (li
, loop
, 0)
2849 if (loop_in_sese_p (loop
, region
))
2850 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2852 gsi_commit_edge_inserts ();
2853 update_ssa (TODO_update_ssa
);
2854 #ifdef ENABLE_CHECKING
2856 verify_loop_closed_ssa ();
2860 /* A LOOP is in normal form for Graphite when it contains only one
2861 scalar phi node that defines the main induction variable of the
2862 loop, only one increment of the IV, and only one exit condition. */
2865 graphite_loop_normal_form (loop_p loop
)
2867 struct tree_niter_desc niter
;
2870 edge exit
= single_dom_exit (loop
);
2872 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2874 /* At this point we should know the number of iterations, */
2875 gcc_assert (known_niter
);
2877 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2880 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2882 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
);
2885 /* Rewrite all the loops of SCOP in normal form: one induction
2886 variable per loop. */
2889 scop_canonicalize_loops (scop_p scop
)
2894 FOR_EACH_LOOP (li
, loop
, 0)
2895 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2896 graphite_loop_normal_form (loop
);
2899 /* Builds the polyhedral representation for a SESE region. */
2902 build_poly_scop (scop_p scop
)
2904 sese region
= SCOP_REGION (scop
);
2905 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2907 sbitmap_zero (reductions
);
2908 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2909 rewrite_reductions_out_of_ssa (scop
);
2910 build_scop_bbs (scop
, reductions
);
2911 sbitmap_free (reductions
);
2913 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2914 Once CLooG is fixed, remove this guard. Anyways, it makes no
2915 sense to optimize a scop containing only PBBs that do not belong
2917 if (nb_pbbs_in_loops (scop
) == 0)
2920 scop_canonicalize_loops (scop
);
2921 build_sese_loop_nests (region
);
2922 build_sese_conditions (region
);
2923 find_scop_parameters (scop
);
2925 build_scop_iteration_domain (scop
);
2926 build_scop_context (scop
);
2928 add_conditions_to_constraints (scop
);
2930 build_scop_scattering (scop
);
2931 build_scop_drs (scop
);
2932 POLY_SCOP_P (scop
) = true;
2937 /* Always return false. Exercise the scop_to_clast function. */
2940 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2942 #ifdef ENABLE_CHECKING
2943 cloog_prog_clast pc
= scop_to_clast (scop
);
2944 cloog_clast_free (pc
.stmt
);
2945 cloog_program_free (pc
.prog
);