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
);
1502 tree lb
= NULL_TREE
;
1503 tree ub
= NULL_TREE
;
1505 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1506 lb
= lower_bound_in_type (type
, type
);
1508 lb
= TYPE_MIN_VALUE (type
);
1510 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1511 ub
= upper_bound_in_type (type
, type
);
1513 ub
= TYPE_MAX_VALUE (type
);
1517 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1518 ppl_set_coef (le
, p
, -1);
1519 ppl_set_inhomogeneous_tree (le
, lb
);
1520 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1521 ppl_Polyhedron_add_constraint (context
, cstr
);
1522 ppl_delete_Linear_Expression (le
);
1523 ppl_delete_Constraint (cstr
);
1528 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1529 ppl_set_coef (le
, p
, -1);
1530 ppl_set_inhomogeneous_tree (le
, ub
);
1531 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1532 ppl_Polyhedron_add_constraint (context
, cstr
);
1533 ppl_delete_Linear_Expression (le
);
1534 ppl_delete_Constraint (cstr
);
1538 /* Build the context of the SCOP. The context usually contains extra
1539 constraints that are added to the iteration domains that constrain
1543 build_scop_context (scop_p scop
)
1545 ppl_Polyhedron_t context
;
1546 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1547 graphite_dim_t p
, n
= scop_nb_params (scop
);
1549 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1551 for (p
= 0; p
< n
; p
++)
1552 add_param_constraints (scop
, context
, p
);
1554 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1556 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1557 (SCOP_CONTEXT (scop
), ps
);
1559 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1560 ppl_delete_Polyhedron (context
);
1563 /* Build the iteration domains: the loops belonging to the current
1564 SCOP, and that vary for the execution of the current basic block.
1565 Returns false if there is no loop in SCOP. */
1568 build_scop_iteration_domain (scop_p scop
)
1571 sese region
= SCOP_REGION (scop
);
1573 ppl_Polyhedron_t ph
;
1575 int nb_loops
= number_of_loops ();
1576 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1577 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1579 for (i
= 0; i
< nb_loops
; i
++)
1582 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1584 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1585 if (!loop_in_sese_p (loop_outer (loop
), region
))
1586 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1588 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1589 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1590 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1591 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1592 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1594 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1595 (&PBB_DOMAIN (pbb
), ph
);
1597 for (i
= 0; i
< nb_loops
; i
++)
1599 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1601 ppl_delete_Polyhedron (ph
);
1605 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1606 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1607 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1611 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1612 ppl_dimension_type accessp_nb_dims
,
1613 ppl_dimension_type dom_nb_dims
)
1615 ppl_Linear_Expression_t alias
;
1616 ppl_Constraint_t cstr
;
1617 int alias_set_num
= 0;
1618 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1620 if (bap
&& bap
->alias_set
)
1621 alias_set_num
= *(bap
->alias_set
);
1623 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1625 ppl_set_coef (alias
, dom_nb_dims
, 1);
1626 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1627 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1628 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1630 ppl_delete_Linear_Expression (alias
);
1631 ppl_delete_Constraint (cstr
);
1634 /* Add to ACCESSES polyhedron equalities defining the access functions
1635 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1636 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1637 PBB is the poly_bb_p that contains the data reference DR. */
1640 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1641 ppl_dimension_type accessp_nb_dims
,
1642 ppl_dimension_type dom_nb_dims
,
1645 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1647 scop_p scop
= PBB_SCOP (pbb
);
1648 sese region
= SCOP_REGION (scop
);
1652 for (i
= 0; i
< nb_subscripts
; i
++)
1654 ppl_Linear_Expression_t fn
, access
;
1655 ppl_Constraint_t cstr
;
1656 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1657 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1659 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1660 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1662 value_set_si (v
, 1);
1663 scan_tree_for_params (region
, afn
, fn
, v
);
1664 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1666 ppl_set_coef (access
, subscript
, -1);
1667 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1668 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1670 ppl_delete_Linear_Expression (fn
);
1671 ppl_delete_Linear_Expression (access
);
1672 ppl_delete_Constraint (cstr
);
1678 /* Add constrains representing the size of the accessed data to the
1679 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1680 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1684 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1685 ppl_dimension_type accessp_nb_dims
,
1686 ppl_dimension_type dom_nb_dims
)
1688 tree ref
= DR_REF (dr
);
1689 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1691 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1693 ppl_Linear_Expression_t expr
;
1694 ppl_Constraint_t cstr
;
1695 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1698 if (TREE_CODE (ref
) != ARRAY_REF
)
1701 low
= array_ref_low_bound (ref
);
1703 /* subscript - low >= 0 */
1704 if (host_integerp (low
, 0))
1706 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1707 ppl_set_coef (expr
, subscript
, 1);
1709 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1711 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1712 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1713 ppl_delete_Linear_Expression (expr
);
1714 ppl_delete_Constraint (cstr
);
1717 high
= array_ref_up_bound (ref
);
1719 /* high - subscript >= 0 */
1720 if (high
&& host_integerp (high
, 0)
1721 /* 1-element arrays at end of structures may extend over
1722 their declared size. */
1723 && !(array_at_struct_end_p (ref
)
1724 && operand_equal_p (low
, high
, 0)))
1726 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1727 ppl_set_coef (expr
, subscript
, -1);
1729 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1731 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1732 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1733 ppl_delete_Linear_Expression (expr
);
1734 ppl_delete_Constraint (cstr
);
1739 /* Build data accesses for DR in PBB. */
1742 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1744 ppl_Polyhedron_t accesses
;
1745 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1746 ppl_dimension_type dom_nb_dims
;
1747 ppl_dimension_type accessp_nb_dims
;
1748 int dr_base_object_set
;
1750 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1752 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1754 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1756 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1757 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1758 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1760 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1762 ppl_delete_Polyhedron (accesses
);
1765 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1767 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1768 dr
, DR_NUM_DIMENSIONS (dr
));
1771 /* Write to FILE the alias graph of data references in DIMACS format. */
1774 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1775 VEC (data_reference_p
, heap
) *drs
)
1777 int num_vertex
= VEC_length (data_reference_p
, drs
);
1779 data_reference_p dr1
, dr2
;
1782 if (num_vertex
== 0)
1785 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1786 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1787 if (dr_may_alias_p (dr1
, dr2
))
1790 fprintf (file
, "$\n");
1793 fprintf (file
, "c %s\n", comment
);
1795 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1797 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1798 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1799 if (dr_may_alias_p (dr1
, dr2
))
1800 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1805 /* Write to FILE the alias graph of data references in DOT format. */
1808 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1809 VEC (data_reference_p
, heap
) *drs
)
1811 int num_vertex
= VEC_length (data_reference_p
, drs
);
1812 data_reference_p dr1
, dr2
;
1815 if (num_vertex
== 0)
1818 fprintf (file
, "$\n");
1821 fprintf (file
, "c %s\n", comment
);
1823 /* First print all the vertices. */
1824 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1825 fprintf (file
, "n%d;\n", i
);
1827 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1828 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1829 if (dr_may_alias_p (dr1
, dr2
))
1830 fprintf (file
, "n%d n%d\n", i
, j
);
1835 /* Write to FILE the alias graph of data references in ECC format. */
1838 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1839 VEC (data_reference_p
, heap
) *drs
)
1841 int num_vertex
= VEC_length (data_reference_p
, drs
);
1842 data_reference_p dr1
, dr2
;
1845 if (num_vertex
== 0)
1848 fprintf (file
, "$\n");
1851 fprintf (file
, "c %s\n", comment
);
1853 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1854 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1855 if (dr_may_alias_p (dr1
, dr2
))
1856 fprintf (file
, "%d %d\n", i
, j
);
1861 /* Check if DR1 and DR2 are in the same object set. */
1864 dr_same_base_object_p (const struct data_reference
*dr1
,
1865 const struct data_reference
*dr2
)
1867 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1870 /* Uses DFS component number as representative of alias-sets. Also tests for
1871 optimality by verifying if every connected component is a clique. Returns
1872 true (1) if the above test is true, and false (0) otherwise. */
1875 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1877 int num_vertices
= VEC_length (data_reference_p
, drs
);
1878 struct graph
*g
= new_graph (num_vertices
);
1879 data_reference_p dr1
, dr2
;
1881 int num_connected_components
;
1882 int v_indx1
, v_indx2
, num_vertices_in_component
;
1885 struct graph_edge
*e
;
1886 int this_component_is_clique
;
1887 int all_components_are_cliques
= 1;
1889 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1890 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1891 if (dr_may_alias_p (dr1
, dr2
))
1897 all_vertices
= XNEWVEC (int, num_vertices
);
1898 vertices
= XNEWVEC (int, num_vertices
);
1899 for (i
= 0; i
< num_vertices
; i
++)
1900 all_vertices
[i
] = i
;
1902 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1904 for (i
= 0; i
< g
->n_vertices
; i
++)
1906 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1907 base_alias_pair
*bap
;
1910 bap
= (base_alias_pair
*)(dr
->aux
);
1912 bap
->alias_set
= XNEW (int);
1913 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1916 /* Verify if the DFS numbering results in optimal solution. */
1917 for (i
= 0; i
< num_connected_components
; i
++)
1919 num_vertices_in_component
= 0;
1920 /* Get all vertices whose DFS component number is the same as i. */
1921 for (j
= 0; j
< num_vertices
; j
++)
1922 if (g
->vertices
[j
].component
== i
)
1923 vertices
[num_vertices_in_component
++] = j
;
1925 /* Now test if the vertices in 'vertices' form a clique, by testing
1926 for edges among each pair. */
1927 this_component_is_clique
= 1;
1928 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1930 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1932 /* Check if the two vertices are connected by iterating
1933 through all the edges which have one of these are source. */
1934 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1937 if (e
->src
== vertices
[v_indx1
])
1943 this_component_is_clique
= 0;
1947 if (!this_component_is_clique
)
1948 all_components_are_cliques
= 0;
1952 free (all_vertices
);
1955 return all_components_are_cliques
;
1958 /* Group each data reference in DRS with it's base object set num. */
1961 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1963 int num_vertex
= VEC_length (data_reference_p
, drs
);
1964 struct graph
*g
= new_graph (num_vertex
);
1965 data_reference_p dr1
, dr2
;
1969 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1970 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1971 if (dr_same_base_object_p (dr1
, dr2
))
1977 queue
= XNEWVEC (int, num_vertex
);
1978 for (i
= 0; i
< num_vertex
; i
++)
1981 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1983 for (i
= 0; i
< g
->n_vertices
; i
++)
1985 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1986 base_alias_pair
*bap
;
1989 bap
= (base_alias_pair
*)(dr
->aux
);
1991 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1998 /* Build the data references for PBB. */
2001 build_pbb_drs (poly_bb_p pbb
)
2004 data_reference_p dr
;
2005 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2007 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2008 build_poly_dr (dr
, pbb
);
2011 /* Dump to file the alias graphs for the data references in DRS. */
2014 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2017 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2019 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2022 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2023 current_function_name ());
2024 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2025 fclose (file_dimacs
);
2028 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2031 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2032 current_function_name ());
2033 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2037 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2040 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2041 current_function_name ());
2042 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2047 /* Build data references in SCOP. */
2050 build_scop_drs (scop_p scop
)
2054 data_reference_p dr
;
2055 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2057 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2058 for (j
= 0; VEC_iterate (data_reference_p
,
2059 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2060 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2062 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2063 dr
->aux
= XNEW (base_alias_pair
);
2065 if (!build_alias_set_optimal_p (drs
))
2067 /* TODO: Add support when building alias set is not optimal. */
2071 build_base_obj_set_for_drs (drs
);
2073 /* When debugging, enable the following code. This cannot be used
2074 in production compilers. */
2076 dump_alias_graphs (drs
);
2078 VEC_free (data_reference_p
, heap
, drs
);
2080 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2081 build_pbb_drs (pbb
);
2084 /* Return a gsi at the position of the phi node STMT. */
2086 static gimple_stmt_iterator
2087 gsi_for_phi_node (gimple stmt
)
2089 gimple_stmt_iterator psi
;
2090 basic_block bb
= gimple_bb (stmt
);
2092 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2093 if (stmt
== gsi_stmt (psi
))
2100 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2103 insert_out_of_ssa_copy (tree res
, tree var
)
2107 gimple_stmt_iterator si
;
2108 gimple_stmt_iterator gsi
;
2110 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2111 stmt
= gimple_build_assign (res
, var
);
2113 stmts
= gimple_seq_alloc ();
2114 si
= gsi_last (stmts
);
2115 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2117 stmt
= SSA_NAME_DEF_STMT (var
);
2118 if (gimple_code (stmt
) == GIMPLE_PHI
)
2120 gsi
= gsi_after_labels (gimple_bb (stmt
));
2121 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2125 gsi
= gsi_for_stmt (stmt
);
2126 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2130 /* Insert on edge E the assignment "RES := EXPR". */
2133 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2135 gimple_stmt_iterator gsi
;
2137 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2138 gimple stmt
= gimple_build_assign (res
, var
);
2141 stmts
= gimple_seq_alloc ();
2143 gsi
= gsi_last (stmts
);
2144 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2145 gsi_insert_seq_on_edge (e
, stmts
);
2146 gsi_commit_edge_inserts ();
2149 /* Creates a zero dimension array of the same type as VAR. */
2152 create_zero_dim_array (tree var
, const char *base_name
)
2154 tree index_type
= build_index_type (integer_zero_node
);
2155 tree elt_type
= TREE_TYPE (var
);
2156 tree array_type
= build_array_type (elt_type
, index_type
);
2157 tree base
= create_tmp_var (array_type
, base_name
);
2159 add_referenced_var (base
);
2161 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2165 /* Returns true when PHI is a loop close phi node. */
2168 scalar_close_phi_node_p (gimple phi
)
2170 if (gimple_code (phi
) != GIMPLE_PHI
2171 || !is_gimple_reg (gimple_phi_result (phi
)))
2174 return (gimple_phi_num_args (phi
) == 1);
2177 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2178 dimension array for it. */
2181 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2183 gimple phi
= gsi_stmt (*psi
);
2184 tree res
= gimple_phi_result (phi
);
2185 tree var
= SSA_NAME_VAR (res
);
2186 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2187 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2188 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2189 tree arg
= gimple_phi_arg_def (phi
, 0);
2191 if (TREE_CODE (arg
) == SSA_NAME
)
2192 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2194 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi
)),
2195 zero_dim_array
, arg
);
2197 remove_phi_node (psi
, false);
2198 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2199 SSA_NAME_DEF_STMT (res
) = stmt
;
2202 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2203 dimension array for it. */
2206 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2209 gimple phi
= gsi_stmt (*psi
);
2210 basic_block bb
= gimple_bb (phi
);
2211 tree res
= gimple_phi_result (phi
);
2212 tree var
= SSA_NAME_VAR (res
);
2213 tree zero_dim_array
= create_zero_dim_array (var
, "General_Reduction");
2214 gimple_stmt_iterator gsi
;
2218 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2220 tree arg
= gimple_phi_arg_def (phi
, i
);
2222 /* Try to avoid the insertion on edges as much as possible: this
2223 would avoid the insertion of code on loop latch edges, making
2224 the pattern matching of the vectorizer happy, or it would
2225 avoid the insertion of useless basic blocks. Note that it is
2226 incorrect to insert out of SSA copies close by their
2227 definition when they are more than two loop levels apart:
2228 for example, starting from a double nested loop
2238 the following transform is incorrect
2250 whereas inserting the copy on the incoming edge is correct
2262 if (TREE_CODE (arg
) == SSA_NAME
2263 && is_gimple_reg (arg
)
2264 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2265 && (flow_bb_inside_loop_p (bb
->loop_father
,
2266 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2267 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2268 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2269 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2271 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2272 zero_dim_array
, arg
);
2275 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2278 stmts
= gimple_seq_alloc ();
2280 stmt
= gimple_build_assign (res
, var
);
2281 remove_phi_node (psi
, false);
2282 SSA_NAME_DEF_STMT (res
) = stmt
;
2284 gsi
= gsi_last (stmts
);
2285 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2287 gsi
= gsi_after_labels (bb
);
2288 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2291 /* Return true when DEF can be analyzed in REGION by the scalar
2292 evolution analyzer. */
2295 scev_analyzable_p (tree def
, sese region
)
2297 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2298 loop_p loop
= loop_containing_stmt (stmt
);
2299 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2301 return !chrec_contains_undetermined (scev
);
2304 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2305 read from ZERO_DIM_ARRAY. */
2308 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2310 tree var
= SSA_NAME_VAR (def
);
2311 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2312 tree name
= make_ssa_name (var
, name_stmt
);
2314 use_operand_p use_p
;
2315 gimple_stmt_iterator gsi
;
2317 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2319 gimple_assign_set_lhs (name_stmt
, name
);
2321 gsi
= gsi_for_stmt (use_stmt
);
2322 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2324 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2325 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2326 replace_exp (use_p
, name
);
2328 update_stmt (use_stmt
);
2331 /* Rewrite the scalar dependences crossing the boundary of the BB
2332 containing STMT with an array. */
2335 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2337 gimple stmt
= gsi_stmt (*gsi
);
2338 imm_use_iterator imm_iter
;
2341 tree zero_dim_array
= NULL_TREE
;
2344 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2347 def
= gimple_assign_lhs (stmt
);
2348 if (!is_gimple_reg (def
)
2349 || scev_analyzable_p (def
, region
))
2352 def_bb
= gimple_bb (stmt
);
2354 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2355 if (def_bb
!= gimple_bb (use_stmt
)
2356 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2358 if (!zero_dim_array
)
2360 zero_dim_array
= create_zero_dim_array
2361 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2362 insert_out_of_ssa_copy (zero_dim_array
, def
);
2366 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2370 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2373 rewrite_reductions_out_of_ssa (scop_p scop
)
2376 gimple_stmt_iterator psi
;
2377 sese region
= SCOP_REGION (scop
);
2380 if (bb_in_sese_p (bb
, region
))
2381 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2383 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2384 rewrite_close_phi_out_of_ssa (&psi
);
2385 else if (reduction_phi_p (region
, &psi
))
2386 rewrite_phi_out_of_ssa (&psi
);
2389 update_ssa (TODO_update_ssa
);
2390 #ifdef ENABLE_CHECKING
2392 verify_loop_closed_ssa ();
2396 if (bb_in_sese_p (bb
, region
))
2397 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2398 rewrite_cross_bb_scalar_deps (region
, &psi
);
2400 update_ssa (TODO_update_ssa
);
2401 #ifdef ENABLE_CHECKING
2403 verify_loop_closed_ssa ();
2407 /* Returns the number of pbbs that are in loops contained in SCOP. */
2410 nb_pbbs_in_loops (scop_p scop
)
2416 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2417 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2423 /* Return the number of data references in BB that write in
2427 nb_data_writes_in_bb (basic_block bb
)
2430 gimple_stmt_iterator gsi
;
2432 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2433 if (gimple_vdef (gsi_stmt (gsi
)))
2439 /* Splits STMT out of its current BB. */
2442 split_reduction_stmt (gimple stmt
)
2444 gimple_stmt_iterator gsi
;
2445 basic_block bb
= gimple_bb (stmt
);
2448 /* Do not split basic blocks with no writes to memory: the reduction
2449 will be the only write to memory. */
2450 if (nb_data_writes_in_bb (bb
) == 0)
2453 split_block (bb
, stmt
);
2455 if (gsi_one_before_end_p (gsi_start_bb (bb
)))
2458 gsi
= gsi_last_bb (bb
);
2460 e
= split_block (bb
, gsi_stmt (gsi
));
2465 /* Return true when stmt is a reduction operation. */
2468 is_reduction_operation_p (gimple stmt
)
2470 enum tree_code code
;
2472 gcc_assert (is_gimple_assign (stmt
));
2473 code
= gimple_assign_rhs_code (stmt
);
2475 return flag_associative_math
2476 && commutative_tree_code (code
)
2477 && associative_tree_code (code
);
2480 /* Returns true when PHI contains an argument ARG. */
2483 phi_contains_arg (gimple phi
, tree arg
)
2487 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2488 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2494 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2497 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2501 if (TREE_CODE (arg
) != SSA_NAME
)
2504 stmt
= SSA_NAME_DEF_STMT (arg
);
2506 if (gimple_code (stmt
) == GIMPLE_NOP
2507 || gimple_code (stmt
) == GIMPLE_CALL
)
2510 if (gimple_code (stmt
) == GIMPLE_PHI
)
2512 if (phi_contains_arg (stmt
, lhs
))
2517 if (!is_gimple_assign (stmt
))
2520 if (gimple_num_ops (stmt
) == 2)
2521 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2523 if (is_reduction_operation_p (stmt
))
2525 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2528 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2534 /* Detect commutative and associative scalar reductions starting at
2535 the STMT. Return the phi node of the reduction cycle, or NULL. */
2538 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2539 VEC (gimple
, heap
) **in
,
2540 VEC (gimple
, heap
) **out
)
2542 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2547 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2548 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2552 /* Detect commutative and associative scalar reductions starting at
2553 the STMT. Return the phi node of the reduction cycle, or NULL. */
2556 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2557 VEC (gimple
, heap
) **out
)
2559 tree lhs
= gimple_assign_lhs (stmt
);
2561 if (gimple_num_ops (stmt
) == 2)
2562 return detect_commutative_reduction_arg (lhs
, stmt
,
2563 gimple_assign_rhs1 (stmt
),
2566 if (is_reduction_operation_p (stmt
))
2568 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2569 gimple_assign_rhs1 (stmt
),
2572 : detect_commutative_reduction_arg (lhs
, stmt
,
2573 gimple_assign_rhs2 (stmt
),
2580 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2583 follow_inital_value_to_phi (tree arg
, tree lhs
)
2587 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2590 stmt
= SSA_NAME_DEF_STMT (arg
);
2592 if (gimple_code (stmt
) == GIMPLE_PHI
2593 && phi_contains_arg (stmt
, lhs
))
2600 /* Return the argument of the loop PHI that is the inital value coming
2601 from outside the loop. */
2604 edge_initial_value_for_loop_phi (gimple phi
)
2608 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2610 edge e
= gimple_phi_arg_edge (phi
, i
);
2612 if (loop_depth (e
->src
->loop_father
)
2613 < loop_depth (e
->dest
->loop_father
))
2620 /* Return the argument of the loop PHI that is the inital value coming
2621 from outside the loop. */
2624 initial_value_for_loop_phi (gimple phi
)
2628 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2630 edge e
= gimple_phi_arg_edge (phi
, i
);
2632 if (loop_depth (e
->src
->loop_father
)
2633 < loop_depth (e
->dest
->loop_father
))
2634 return gimple_phi_arg_def (phi
, i
);
2640 /* Detect commutative and associative scalar reductions starting at
2641 the loop closed phi node CLOSE_PHI. Return the phi node of the
2642 reduction cycle, or NULL. */
2645 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2646 VEC (gimple
, heap
) **out
)
2648 if (scalar_close_phi_node_p (stmt
))
2650 tree arg
= gimple_phi_arg_def (stmt
, 0);
2651 gimple def
, loop_phi
;
2653 if (TREE_CODE (arg
) != SSA_NAME
)
2656 def
= SSA_NAME_DEF_STMT (arg
);
2657 loop_phi
= detect_commutative_reduction (def
, in
, out
);
2661 tree lhs
= gimple_phi_result (stmt
);
2662 tree init
= initial_value_for_loop_phi (loop_phi
);
2663 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2665 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2666 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2673 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2674 return detect_commutative_reduction_assign (stmt
, in
, out
);
2679 /* Translate the scalar reduction statement STMT to an array RED
2680 knowing that its recursive phi node is LOOP_PHI. */
2683 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2686 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2687 tree res
= gimple_phi_result (loop_phi
);
2688 gimple assign
= gimple_build_assign (res
, red
);
2690 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2692 insert_gsi
= gsi_after_labels (gimple_bb (stmt
));
2693 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2694 insert_gsi
= gsi_for_stmt (stmt
);
2695 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2698 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2701 insert_copyout (tree red
, gimple close_phi
)
2703 tree res
= gimple_phi_result (close_phi
);
2704 basic_block bb
= gimple_bb (close_phi
);
2705 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2706 gimple assign
= gimple_build_assign (res
, red
);
2708 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2711 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2714 insert_copyin (tree red
, gimple loop_phi
)
2717 tree init
= initial_value_for_loop_phi (loop_phi
);
2718 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2720 force_gimple_operand (expr
, &stmts
, true, NULL
);
2721 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2724 /* Removes the PHI node and resets all the debug stmts that are using
2728 remove_phi (gimple phi
)
2730 imm_use_iterator imm_iter
;
2732 use_operand_p use_p
;
2733 gimple_stmt_iterator gsi
;
2734 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2738 def
= PHI_RESULT (phi
);
2739 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2741 stmt
= USE_STMT (use_p
);
2743 if (is_gimple_debug (stmt
))
2745 gimple_debug_bind_reset_value (stmt
);
2746 VEC_safe_push (gimple
, heap
, update
, stmt
);
2750 for (i
= 0; VEC_iterate (gimple
, update
, i
, stmt
); i
++)
2753 VEC_free (gimple
, heap
, update
);
2755 gsi
= gsi_for_phi_node (phi
);
2756 remove_phi_node (&gsi
, false);
2759 /* Rewrite out of SSA the reduction described by the loop phi nodes
2760 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2763 IN: stmt, loop_n, ..., loop_0
2764 OUT: stmt, close_n, ..., close_0
2766 the first element is the reduction statement, and the next elements
2767 are the loop and close phi nodes of each of the outer loops. */
2770 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2771 VEC (gimple
, heap
) *out
,
2778 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2780 gimple close_phi
= VEC_index (gimple
, out
, i
);
2784 gimple stmt
= loop_phi
;
2785 basic_block bb
= split_reduction_stmt (stmt
);
2787 SET_BIT (reductions
, bb
->index
);
2788 gcc_assert (close_phi
== loop_phi
);
2790 red
= create_zero_dim_array
2791 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2792 translate_scalar_reduction_to_array_for_stmt
2793 (red
, stmt
, VEC_index (gimple
, in
, 1));
2797 if (i
== VEC_length (gimple
, in
) - 1)
2799 insert_copyout (red
, close_phi
);
2800 insert_copyin (red
, loop_phi
);
2803 remove_phi (loop_phi
);
2804 remove_phi (close_phi
);
2808 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2811 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2814 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2815 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2817 detect_commutative_reduction (close_phi
, &in
, &out
);
2818 if (VEC_length (gimple
, in
) > 0)
2819 translate_scalar_reduction_to_array (in
, out
, reductions
);
2821 VEC_free (gimple
, heap
, in
);
2822 VEC_free (gimple
, heap
, out
);
2825 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2828 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2831 gimple_stmt_iterator gsi
;
2832 edge exit
= single_exit (loop
);
2837 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2838 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2842 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2845 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2850 FOR_EACH_LOOP (li
, loop
, 0)
2851 if (loop_in_sese_p (loop
, region
))
2852 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2854 gsi_commit_edge_inserts ();
2855 update_ssa (TODO_update_ssa
);
2856 #ifdef ENABLE_CHECKING
2858 verify_loop_closed_ssa ();
2862 /* A LOOP is in normal form for Graphite when it contains only one
2863 scalar phi node that defines the main induction variable of the
2864 loop, only one increment of the IV, and only one exit condition. */
2867 graphite_loop_normal_form (loop_p loop
)
2869 struct tree_niter_desc niter
;
2872 edge exit
= single_dom_exit (loop
);
2874 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2876 /* At this point we should know the number of iterations, */
2877 gcc_assert (known_niter
);
2879 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2882 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2884 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
);
2887 /* Rewrite all the loops of SCOP in normal form: one induction
2888 variable per loop. */
2891 scop_canonicalize_loops (scop_p scop
)
2896 FOR_EACH_LOOP (li
, loop
, 0)
2897 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2898 graphite_loop_normal_form (loop
);
2901 /* Can all ivs be represented by a signed integer?
2902 As CLooG might generate negative values in its expressions, signed loop ivs
2903 are required in the backend. */
2905 scop_ivs_can_be_represented (scop_p scop
)
2910 FOR_EACH_LOOP (li
, loop
, 0)
2915 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2918 if (!loop
->single_iv
)
2921 type
= TREE_TYPE(loop
->single_iv
);
2922 precision
= TYPE_PRECISION (type
);
2924 if (TYPE_UNSIGNED (type
)
2925 && precision
>= TYPE_PRECISION (long_long_integer_type_node
))
2933 /* Builds the polyhedral representation for a SESE region. */
2936 build_poly_scop (scop_p scop
)
2938 sese region
= SCOP_REGION (scop
);
2939 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2941 sbitmap_zero (reductions
);
2942 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2943 rewrite_reductions_out_of_ssa (scop
);
2944 build_scop_bbs (scop
, reductions
);
2945 sbitmap_free (reductions
);
2947 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2948 Once CLooG is fixed, remove this guard. Anyways, it makes no
2949 sense to optimize a scop containing only PBBs that do not belong
2951 if (nb_pbbs_in_loops (scop
) == 0)
2954 scop_canonicalize_loops (scop
);
2956 if (!scop_ivs_can_be_represented (scop
))
2959 build_sese_loop_nests (region
);
2960 build_sese_conditions (region
);
2961 find_scop_parameters (scop
);
2963 build_scop_iteration_domain (scop
);
2964 build_scop_context (scop
);
2966 add_conditions_to_constraints (scop
);
2968 build_scop_scattering (scop
);
2969 build_scop_drs (scop
);
2970 POLY_SCOP_P (scop
) = true;
2975 /* Always return false. Exercise the scop_to_clast function. */
2978 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2980 #ifdef ENABLE_CHECKING
2981 cloog_prog_clast pc
= scop_to_clast (scop
);
2982 cloog_clast_free (pc
.stmt
);
2983 cloog_program_free (pc
.prog
);