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 /* 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 /* Insert in the SCOP context constraints from the estimation of the
1042 number of iterations. UB_EXPR is a linear expression describing
1043 the number of iterations in a loop. This expression is bounded by
1044 the estimation NIT. */
1047 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
1048 ppl_dimension_type dim
,
1049 ppl_Linear_Expression_t ub_expr
)
1052 ppl_Linear_Expression_t nb_iters_le
;
1053 ppl_Polyhedron_t pol
;
1054 ppl_Coefficient_t coef
;
1055 ppl_Constraint_t ub
;
1057 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1058 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1059 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1062 /* Construct the negated number of last iteration in VAL. */
1064 mpz_set_double_int (val
, nit
, false);
1065 value_sub_int (val
, val
, 1);
1066 value_oppose (val
, val
);
1068 /* NB_ITERS_LE holds the number of last iteration in
1069 parametrical form. Subtract estimated number of last
1070 iteration and assert that result is not positive. */
1071 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1072 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1073 ppl_delete_Coefficient (coef
);
1074 ppl_new_Constraint (&ub
, nb_iters_le
,
1075 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1076 ppl_Polyhedron_add_constraint (pol
, ub
);
1078 /* Remove all but last GDIM dimensions from POL to obtain
1079 only the constraints on the parameters. */
1081 graphite_dim_t gdim
= scop_nb_params (scop
);
1082 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
1085 for (i
= 0; i
< dim
- gdim
; i
++)
1088 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
1092 /* Add the constraints on the parameters to the SCoP context. */
1094 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1096 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1097 (&constraints_ps
, pol
);
1098 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1099 (SCOP_CONTEXT (scop
), constraints_ps
);
1100 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1103 ppl_delete_Polyhedron (pol
);
1104 ppl_delete_Linear_Expression (nb_iters_le
);
1105 ppl_delete_Constraint (ub
);
1109 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1110 the constraints for the surrounding loops. */
1113 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1114 ppl_Polyhedron_t outer_ph
, int nb
,
1115 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1118 ppl_Polyhedron_t ph
;
1119 tree nb_iters
= number_of_latch_executions (loop
);
1120 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1121 sese region
= SCOP_REGION (scop
);
1124 ppl_const_Constraint_System_t pcs
;
1125 ppl_dimension_type
*map
1126 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1128 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1129 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1130 ppl_Polyhedron_add_constraints (ph
, pcs
);
1132 for (i
= 0; i
< (int) nb
; i
++)
1134 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1138 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1144 ppl_Constraint_t lb
;
1145 ppl_Linear_Expression_t lb_expr
;
1147 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1148 ppl_set_coef (lb_expr
, nb
, 1);
1149 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1150 ppl_delete_Linear_Expression (lb_expr
);
1151 ppl_Polyhedron_add_constraint (ph
, lb
);
1152 ppl_delete_Constraint (lb
);
1155 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1157 ppl_Constraint_t ub
;
1158 ppl_Linear_Expression_t ub_expr
;
1160 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1162 /* loop_i <= cst_nb_iters */
1163 ppl_set_coef (ub_expr
, nb
, -1);
1164 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1165 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1166 ppl_Polyhedron_add_constraint (ph
, ub
);
1167 ppl_delete_Linear_Expression (ub_expr
);
1168 ppl_delete_Constraint (ub
);
1170 else if (!chrec_contains_undetermined (nb_iters
))
1173 ppl_Constraint_t ub
;
1174 ppl_Linear_Expression_t ub_expr
;
1178 value_set_si (one
, 1);
1179 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1180 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1181 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1184 if (estimated_loop_iterations (loop
, true, &nit
))
1185 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1187 /* loop_i <= expr_nb_iters */
1188 ppl_set_coef (ub_expr
, nb
, -1);
1189 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1190 ppl_Polyhedron_add_constraint (ph
, ub
);
1191 ppl_delete_Linear_Expression (ub_expr
);
1192 ppl_delete_Constraint (ub
);
1197 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1198 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1202 && loop_in_sese_p (loop
->next
, region
))
1203 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1205 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1206 (&domains
[loop
->num
], ph
);
1208 ppl_delete_Polyhedron (ph
);
1211 /* Returns a linear expression for tree T evaluated in PBB. */
1213 static ppl_Linear_Expression_t
1214 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1217 ppl_Linear_Expression_t res
;
1218 ppl_dimension_type dim
;
1219 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1220 loop_p loop
= pbb_loop (pbb
);
1222 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1223 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1225 t
= scalar_evolution_in_region (region
, loop
, t
);
1226 gcc_assert (!automatically_generated_chrec_p (t
));
1229 value_set_si (one
, 1);
1230 scan_tree_for_params (region
, t
, res
, one
);
1236 /* Returns the ppl constraint type from the gimple tree code CODE. */
1238 static enum ppl_enum_Constraint_Type
1239 ppl_constraint_type_from_tree_code (enum tree_code code
)
1243 /* We do not support LT and GT to be able to work with C_Polyhedron.
1244 As we work on integer polyhedron "a < b" can be expressed by
1251 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1254 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1257 return PPL_CONSTRAINT_TYPE_EQUAL
;
1264 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1265 CODE is used as the comparison operator. This allows us to invert the
1266 condition or to handle inequalities. */
1269 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1270 poly_bb_p pbb
, enum tree_code code
)
1273 ppl_Coefficient_t c
;
1274 ppl_Linear_Expression_t left
, right
;
1275 ppl_Constraint_t cstr
;
1276 enum ppl_enum_Constraint_Type type
;
1278 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1279 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1281 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1282 the left or the right side of the expression. */
1283 if (code
== LT_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 (left
, c
);
1290 ppl_delete_Coefficient (c
);
1295 else if (code
== GT_EXPR
)
1298 value_set_si (v
, 1);
1299 ppl_new_Coefficient (&c
);
1300 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1301 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1302 ppl_delete_Coefficient (c
);
1308 type
= ppl_constraint_type_from_tree_code (code
);
1310 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1312 ppl_new_Constraint (&cstr
, left
, type
);
1313 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1315 ppl_delete_Constraint (cstr
);
1316 ppl_delete_Linear_Expression (left
);
1317 ppl_delete_Linear_Expression (right
);
1320 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1321 operator. This allows us to invert the condition or to handle
1325 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1327 if (code
== NE_EXPR
)
1329 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1330 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1331 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1333 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1334 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1335 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1337 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1340 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1343 /* Add conditions to the domain of PBB. */
1346 add_conditions_to_domain (poly_bb_p pbb
)
1350 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1351 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1353 if (VEC_empty (gimple
, conditions
))
1356 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1357 switch (gimple_code (stmt
))
1361 enum tree_code code
= gimple_cond_code (stmt
);
1363 /* The conditions for ELSE-branches are inverted. */
1364 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1365 code
= invert_tree_comparison (code
, false);
1367 add_condition_to_pbb (pbb
, stmt
, code
);
1372 /* Switch statements are not supported right now - fall throught. */
1380 /* Structure used to pass data to dom_walk. */
1384 VEC (gimple
, heap
) **conditions
, **cases
;
1388 /* Returns non NULL when BB has a single predecessor and the last
1389 statement of that predecessor is a COND_EXPR. */
1392 single_pred_cond (basic_block bb
)
1394 if (single_pred_p (bb
))
1396 edge e
= single_pred_edge (bb
);
1397 basic_block pred
= e
->src
;
1398 gimple stmt
= last_stmt (pred
);
1400 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1406 /* Call-back for dom_walk executed before visiting the dominated
1410 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1413 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1414 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1415 VEC (gimple
, heap
) **cases
= data
->cases
;
1416 gimple_bb_p gbb
= gbb_from_bb (bb
);
1417 gimple stmt
= single_pred_cond (bb
);
1419 if (!bb_in_sese_p (bb
, data
->region
))
1424 edge e
= single_pred_edge (bb
);
1426 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1428 if (e
->flags
& EDGE_TRUE_VALUE
)
1429 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1431 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1436 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1437 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1441 /* Call-back for dom_walk executed after visiting the dominated
1445 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1448 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1449 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1450 VEC (gimple
, heap
) **cases
= data
->cases
;
1452 if (!bb_in_sese_p (bb
, data
->region
))
1455 if (single_pred_cond (bb
))
1457 VEC_pop (gimple
, *conditions
);
1458 VEC_pop (gimple
, *cases
);
1462 /* Record all conditions in REGION. */
1465 build_sese_conditions (sese region
)
1467 struct dom_walk_data walk_data
;
1468 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1469 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1472 data
.conditions
= &conditions
;
1473 data
.cases
= &cases
;
1474 data
.region
= region
;
1476 walk_data
.dom_direction
= CDI_DOMINATORS
;
1477 walk_data
.initialize_block_local_data
= NULL
;
1478 walk_data
.before_dom_children
= build_sese_conditions_before
;
1479 walk_data
.after_dom_children
= build_sese_conditions_after
;
1480 walk_data
.global_data
= &data
;
1481 walk_data
.block_local_data_size
= 0;
1483 init_walk_dominator_tree (&walk_data
);
1484 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1485 fini_walk_dominator_tree (&walk_data
);
1487 VEC_free (gimple
, heap
, conditions
);
1488 VEC_free (gimple
, heap
, cases
);
1491 /* Traverses all the GBBs of the SCOP and add their constraints to the
1492 iteration domains. */
1495 add_conditions_to_constraints (scop_p scop
)
1500 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1501 add_conditions_to_domain (pbb
);
1504 /* Add constraints on the possible values of parameter P from the type
1508 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1510 ppl_Constraint_t cstr
;
1511 ppl_Linear_Expression_t le
;
1512 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1513 tree type
= TREE_TYPE (parameter
);
1514 tree lb
= NULL_TREE
;
1515 tree ub
= NULL_TREE
;
1517 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1518 lb
= lower_bound_in_type (type
, type
);
1520 lb
= TYPE_MIN_VALUE (type
);
1522 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1523 ub
= upper_bound_in_type (type
, type
);
1525 ub
= TYPE_MAX_VALUE (type
);
1529 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1530 ppl_set_coef (le
, p
, -1);
1531 ppl_set_inhomogeneous_tree (le
, lb
);
1532 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1533 ppl_Polyhedron_add_constraint (context
, cstr
);
1534 ppl_delete_Linear_Expression (le
);
1535 ppl_delete_Constraint (cstr
);
1540 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1541 ppl_set_coef (le
, p
, -1);
1542 ppl_set_inhomogeneous_tree (le
, ub
);
1543 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1544 ppl_Polyhedron_add_constraint (context
, cstr
);
1545 ppl_delete_Linear_Expression (le
);
1546 ppl_delete_Constraint (cstr
);
1550 /* Build the context of the SCOP. The context usually contains extra
1551 constraints that are added to the iteration domains that constrain
1555 build_scop_context (scop_p scop
)
1557 ppl_Polyhedron_t context
;
1558 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1559 graphite_dim_t p
, n
= scop_nb_params (scop
);
1561 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1563 for (p
= 0; p
< n
; p
++)
1564 add_param_constraints (scop
, context
, p
);
1566 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1568 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1569 (SCOP_CONTEXT (scop
), ps
);
1571 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1572 ppl_delete_Polyhedron (context
);
1575 /* Build the iteration domains: the loops belonging to the current
1576 SCOP, and that vary for the execution of the current basic block.
1577 Returns false if there is no loop in SCOP. */
1580 build_scop_iteration_domain (scop_p scop
)
1583 sese region
= SCOP_REGION (scop
);
1585 ppl_Polyhedron_t ph
;
1587 int nb_loops
= number_of_loops ();
1588 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1589 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1591 for (i
= 0; i
< nb_loops
; i
++)
1594 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1596 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1597 if (!loop_in_sese_p (loop_outer (loop
), region
))
1598 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1600 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1601 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1602 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1603 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1604 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1606 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1607 (&PBB_DOMAIN (pbb
), ph
);
1609 for (i
= 0; i
< nb_loops
; i
++)
1611 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1613 ppl_delete_Polyhedron (ph
);
1617 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1618 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1619 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1623 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1624 ppl_dimension_type accessp_nb_dims
,
1625 ppl_dimension_type dom_nb_dims
)
1627 ppl_Linear_Expression_t alias
;
1628 ppl_Constraint_t cstr
;
1629 int alias_set_num
= 0;
1630 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1632 if (bap
&& bap
->alias_set
)
1633 alias_set_num
= *(bap
->alias_set
);
1635 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1637 ppl_set_coef (alias
, dom_nb_dims
, 1);
1638 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1639 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1640 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1642 ppl_delete_Linear_Expression (alias
);
1643 ppl_delete_Constraint (cstr
);
1646 /* Add to ACCESSES polyhedron equalities defining the access functions
1647 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1648 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1649 PBB is the poly_bb_p that contains the data reference DR. */
1652 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1653 ppl_dimension_type accessp_nb_dims
,
1654 ppl_dimension_type dom_nb_dims
,
1657 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1659 scop_p scop
= PBB_SCOP (pbb
);
1660 sese region
= SCOP_REGION (scop
);
1664 for (i
= 0; i
< nb_subscripts
; i
++)
1666 ppl_Linear_Expression_t fn
, access
;
1667 ppl_Constraint_t cstr
;
1668 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1669 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1671 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1672 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1674 value_set_si (v
, 1);
1675 scan_tree_for_params (region
, afn
, fn
, v
);
1676 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1678 ppl_set_coef (access
, subscript
, -1);
1679 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1680 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1682 ppl_delete_Linear_Expression (fn
);
1683 ppl_delete_Linear_Expression (access
);
1684 ppl_delete_Constraint (cstr
);
1690 /* Add constrains representing the size of the accessed data to the
1691 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1692 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1696 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1697 ppl_dimension_type accessp_nb_dims
,
1698 ppl_dimension_type dom_nb_dims
)
1700 tree ref
= DR_REF (dr
);
1701 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1703 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1705 ppl_Linear_Expression_t expr
;
1706 ppl_Constraint_t cstr
;
1707 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1710 if (TREE_CODE (ref
) != ARRAY_REF
)
1713 low
= array_ref_low_bound (ref
);
1715 /* subscript - low >= 0 */
1716 if (host_integerp (low
, 0))
1718 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1719 ppl_set_coef (expr
, subscript
, 1);
1721 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1723 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1724 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1725 ppl_delete_Linear_Expression (expr
);
1726 ppl_delete_Constraint (cstr
);
1729 high
= array_ref_up_bound (ref
);
1731 /* high - subscript >= 0 */
1732 if (high
&& host_integerp (high
, 0)
1733 /* 1-element arrays at end of structures may extend over
1734 their declared size. */
1735 && !(array_at_struct_end_p (ref
)
1736 && operand_equal_p (low
, high
, 0)))
1738 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1739 ppl_set_coef (expr
, subscript
, -1);
1741 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1743 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1744 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1745 ppl_delete_Linear_Expression (expr
);
1746 ppl_delete_Constraint (cstr
);
1751 /* Build data accesses for DR in PBB. */
1754 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1756 ppl_Polyhedron_t accesses
;
1757 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1758 ppl_dimension_type dom_nb_dims
;
1759 ppl_dimension_type accessp_nb_dims
;
1760 int dr_base_object_set
;
1762 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1764 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1766 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1768 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1769 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1770 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1772 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1774 ppl_delete_Polyhedron (accesses
);
1777 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1779 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1780 dr
, DR_NUM_DIMENSIONS (dr
));
1783 /* Write to FILE the alias graph of data references in DIMACS format. */
1786 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1787 VEC (data_reference_p
, heap
) *drs
)
1789 int num_vertex
= VEC_length (data_reference_p
, drs
);
1791 data_reference_p dr1
, dr2
;
1794 if (num_vertex
== 0)
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
))
1802 fprintf (file
, "$\n");
1805 fprintf (file
, "c %s\n", comment
);
1807 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1809 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1810 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1811 if (dr_may_alias_p (dr1
, dr2
))
1812 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1817 /* Write to FILE the alias graph of data references in DOT format. */
1820 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1821 VEC (data_reference_p
, heap
) *drs
)
1823 int num_vertex
= VEC_length (data_reference_p
, drs
);
1824 data_reference_p dr1
, dr2
;
1827 if (num_vertex
== 0)
1830 fprintf (file
, "$\n");
1833 fprintf (file
, "c %s\n", comment
);
1835 /* First print all the vertices. */
1836 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1837 fprintf (file
, "n%d;\n", i
);
1839 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1840 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1841 if (dr_may_alias_p (dr1
, dr2
))
1842 fprintf (file
, "n%d n%d\n", i
, j
);
1847 /* Write to FILE the alias graph of data references in ECC format. */
1850 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1851 VEC (data_reference_p
, heap
) *drs
)
1853 int num_vertex
= VEC_length (data_reference_p
, drs
);
1854 data_reference_p dr1
, dr2
;
1857 if (num_vertex
== 0)
1860 fprintf (file
, "$\n");
1863 fprintf (file
, "c %s\n", comment
);
1865 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1866 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1867 if (dr_may_alias_p (dr1
, dr2
))
1868 fprintf (file
, "%d %d\n", i
, j
);
1873 /* Check if DR1 and DR2 are in the same object set. */
1876 dr_same_base_object_p (const struct data_reference
*dr1
,
1877 const struct data_reference
*dr2
)
1879 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1882 /* Uses DFS component number as representative of alias-sets. Also tests for
1883 optimality by verifying if every connected component is a clique. Returns
1884 true (1) if the above test is true, and false (0) otherwise. */
1887 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1889 int num_vertices
= VEC_length (data_reference_p
, drs
);
1890 struct graph
*g
= new_graph (num_vertices
);
1891 data_reference_p dr1
, dr2
;
1893 int num_connected_components
;
1894 int v_indx1
, v_indx2
, num_vertices_in_component
;
1897 struct graph_edge
*e
;
1898 int this_component_is_clique
;
1899 int all_components_are_cliques
= 1;
1901 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1902 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1903 if (dr_may_alias_p (dr1
, dr2
))
1909 all_vertices
= XNEWVEC (int, num_vertices
);
1910 vertices
= XNEWVEC (int, num_vertices
);
1911 for (i
= 0; i
< num_vertices
; i
++)
1912 all_vertices
[i
] = i
;
1914 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1916 for (i
= 0; i
< g
->n_vertices
; i
++)
1918 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1919 base_alias_pair
*bap
;
1922 bap
= (base_alias_pair
*)(dr
->aux
);
1924 bap
->alias_set
= XNEW (int);
1925 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1928 /* Verify if the DFS numbering results in optimal solution. */
1929 for (i
= 0; i
< num_connected_components
; i
++)
1931 num_vertices_in_component
= 0;
1932 /* Get all vertices whose DFS component number is the same as i. */
1933 for (j
= 0; j
< num_vertices
; j
++)
1934 if (g
->vertices
[j
].component
== i
)
1935 vertices
[num_vertices_in_component
++] = j
;
1937 /* Now test if the vertices in 'vertices' form a clique, by testing
1938 for edges among each pair. */
1939 this_component_is_clique
= 1;
1940 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1942 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1944 /* Check if the two vertices are connected by iterating
1945 through all the edges which have one of these are source. */
1946 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1949 if (e
->src
== vertices
[v_indx1
])
1955 this_component_is_clique
= 0;
1959 if (!this_component_is_clique
)
1960 all_components_are_cliques
= 0;
1964 free (all_vertices
);
1967 return all_components_are_cliques
;
1970 /* Group each data reference in DRS with it's base object set num. */
1973 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1975 int num_vertex
= VEC_length (data_reference_p
, drs
);
1976 struct graph
*g
= new_graph (num_vertex
);
1977 data_reference_p dr1
, dr2
;
1981 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1982 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1983 if (dr_same_base_object_p (dr1
, dr2
))
1989 queue
= XNEWVEC (int, num_vertex
);
1990 for (i
= 0; i
< num_vertex
; i
++)
1993 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1995 for (i
= 0; i
< g
->n_vertices
; i
++)
1997 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1998 base_alias_pair
*bap
;
2001 bap
= (base_alias_pair
*)(dr
->aux
);
2003 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2010 /* Build the data references for PBB. */
2013 build_pbb_drs (poly_bb_p pbb
)
2016 data_reference_p dr
;
2017 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2019 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2020 build_poly_dr (dr
, pbb
);
2023 /* Dump to file the alias graphs for the data references in DRS. */
2026 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2029 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2031 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2034 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2035 current_function_name ());
2036 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2037 fclose (file_dimacs
);
2040 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2043 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2044 current_function_name ());
2045 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2049 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2052 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2053 current_function_name ());
2054 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2059 /* Build data references in SCOP. */
2062 build_scop_drs (scop_p scop
)
2066 data_reference_p dr
;
2067 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2069 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2070 for (j
= 0; VEC_iterate (data_reference_p
,
2071 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2072 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2074 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2075 dr
->aux
= XNEW (base_alias_pair
);
2077 if (!build_alias_set_optimal_p (drs
))
2079 /* TODO: Add support when building alias set is not optimal. */
2083 build_base_obj_set_for_drs (drs
);
2085 /* When debugging, enable the following code. This cannot be used
2086 in production compilers. */
2088 dump_alias_graphs (drs
);
2090 VEC_free (data_reference_p
, heap
, drs
);
2092 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2093 build_pbb_drs (pbb
);
2096 /* Return a gsi at the position of the phi node STMT. */
2098 static gimple_stmt_iterator
2099 gsi_for_phi_node (gimple stmt
)
2101 gimple_stmt_iterator psi
;
2102 basic_block bb
= gimple_bb (stmt
);
2104 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2105 if (stmt
== gsi_stmt (psi
))
2112 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2115 insert_out_of_ssa_copy (tree res
, tree var
)
2119 gimple_stmt_iterator si
;
2120 gimple_stmt_iterator gsi
;
2122 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2123 stmt
= gimple_build_assign (res
, var
);
2125 stmts
= gimple_seq_alloc ();
2126 si
= gsi_last (stmts
);
2127 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2129 stmt
= SSA_NAME_DEF_STMT (var
);
2130 if (gimple_code (stmt
) == GIMPLE_PHI
)
2132 gsi
= gsi_after_labels (gimple_bb (stmt
));
2133 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2137 gsi
= gsi_for_stmt (stmt
);
2138 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2142 /* Insert on edge E the assignment "RES := EXPR". */
2145 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2147 gimple_stmt_iterator gsi
;
2149 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2150 gimple stmt
= gimple_build_assign (res
, var
);
2153 stmts
= gimple_seq_alloc ();
2155 gsi
= gsi_last (stmts
);
2156 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2157 gsi_insert_seq_on_edge (e
, stmts
);
2158 gsi_commit_edge_inserts ();
2161 /* Creates a zero dimension array of the same type as VAR. */
2164 create_zero_dim_array (tree var
, const char *base_name
)
2166 tree index_type
= build_index_type (integer_zero_node
);
2167 tree elt_type
= TREE_TYPE (var
);
2168 tree array_type
= build_array_type (elt_type
, index_type
);
2169 tree base
= create_tmp_var (array_type
, base_name
);
2171 add_referenced_var (base
);
2173 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2177 /* Returns true when PHI is a loop close phi node. */
2180 scalar_close_phi_node_p (gimple phi
)
2182 if (gimple_code (phi
) != GIMPLE_PHI
2183 || !is_gimple_reg (gimple_phi_result (phi
)))
2186 return (gimple_phi_num_args (phi
) == 1);
2189 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2190 dimension array for it. */
2193 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2195 gimple phi
= gsi_stmt (*psi
);
2196 tree res
= gimple_phi_result (phi
);
2197 tree var
= SSA_NAME_VAR (res
);
2198 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2199 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2200 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2201 tree arg
= gimple_phi_arg_def (phi
, 0);
2203 if (TREE_CODE (arg
) == SSA_NAME
)
2204 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2206 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi
)),
2207 zero_dim_array
, arg
);
2209 remove_phi_node (psi
, false);
2210 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2211 SSA_NAME_DEF_STMT (res
) = stmt
;
2214 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2215 dimension array for it. */
2218 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2221 gimple phi
= gsi_stmt (*psi
);
2222 basic_block bb
= gimple_bb (phi
);
2223 tree res
= gimple_phi_result (phi
);
2224 tree var
= SSA_NAME_VAR (res
);
2225 tree zero_dim_array
= create_zero_dim_array (var
, "General_Reduction");
2226 gimple_stmt_iterator gsi
;
2230 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2232 tree arg
= gimple_phi_arg_def (phi
, i
);
2234 /* Try to avoid the insertion on edges as much as possible: this
2235 would avoid the insertion of code on loop latch edges, making
2236 the pattern matching of the vectorizer happy, or it would
2237 avoid the insertion of useless basic blocks. Note that it is
2238 incorrect to insert out of SSA copies close by their
2239 definition when they are more than two loop levels apart:
2240 for example, starting from a double nested loop
2250 the following transform is incorrect
2262 whereas inserting the copy on the incoming edge is correct
2274 if (TREE_CODE (arg
) == SSA_NAME
2275 && is_gimple_reg (arg
)
2276 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2277 && (flow_bb_inside_loop_p (bb
->loop_father
,
2278 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2279 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2280 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2281 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2283 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2284 zero_dim_array
, arg
);
2287 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2290 stmts
= gimple_seq_alloc ();
2292 stmt
= gimple_build_assign (res
, var
);
2293 remove_phi_node (psi
, false);
2294 SSA_NAME_DEF_STMT (res
) = stmt
;
2296 gsi
= gsi_last (stmts
);
2297 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2299 gsi
= gsi_after_labels (bb
);
2300 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2303 /* Return true when DEF can be analyzed in REGION by the scalar
2304 evolution analyzer. */
2307 scev_analyzable_p (tree def
, sese region
)
2309 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2310 loop_p loop
= loop_containing_stmt (stmt
);
2311 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2313 return !chrec_contains_undetermined (scev
);
2316 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2317 read from ZERO_DIM_ARRAY. */
2320 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2322 tree var
= SSA_NAME_VAR (def
);
2323 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2324 tree name
= make_ssa_name (var
, name_stmt
);
2326 use_operand_p use_p
;
2327 gimple_stmt_iterator gsi
;
2329 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2331 gimple_assign_set_lhs (name_stmt
, name
);
2333 gsi
= gsi_for_stmt (use_stmt
);
2334 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2336 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2337 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2338 replace_exp (use_p
, name
);
2340 update_stmt (use_stmt
);
2343 /* Rewrite the scalar dependences crossing the boundary of the BB
2344 containing STMT with an array. */
2347 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2349 gimple stmt
= gsi_stmt (*gsi
);
2350 imm_use_iterator imm_iter
;
2353 tree zero_dim_array
= NULL_TREE
;
2356 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2359 def
= gimple_assign_lhs (stmt
);
2360 if (!is_gimple_reg (def
)
2361 || scev_analyzable_p (def
, region
))
2364 def_bb
= gimple_bb (stmt
);
2366 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2367 if (def_bb
!= gimple_bb (use_stmt
)
2368 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2370 if (!zero_dim_array
)
2372 zero_dim_array
= create_zero_dim_array
2373 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2374 insert_out_of_ssa_copy (zero_dim_array
, def
);
2378 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2382 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2385 rewrite_reductions_out_of_ssa (scop_p scop
)
2388 gimple_stmt_iterator psi
;
2389 sese region
= SCOP_REGION (scop
);
2392 if (bb_in_sese_p (bb
, region
))
2393 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2395 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2396 rewrite_close_phi_out_of_ssa (&psi
);
2397 else if (reduction_phi_p (region
, &psi
))
2398 rewrite_phi_out_of_ssa (&psi
);
2401 update_ssa (TODO_update_ssa
);
2402 #ifdef ENABLE_CHECKING
2404 verify_loop_closed_ssa ();
2408 if (bb_in_sese_p (bb
, region
))
2409 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2410 rewrite_cross_bb_scalar_deps (region
, &psi
);
2412 update_ssa (TODO_update_ssa
);
2413 #ifdef ENABLE_CHECKING
2415 verify_loop_closed_ssa ();
2419 /* Returns the number of pbbs that are in loops contained in SCOP. */
2422 nb_pbbs_in_loops (scop_p scop
)
2428 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2429 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2435 /* Return the number of data references in BB that write in
2439 nb_data_writes_in_bb (basic_block bb
)
2442 gimple_stmt_iterator gsi
;
2444 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2445 if (gimple_vdef (gsi_stmt (gsi
)))
2451 /* Splits STMT out of its current BB. */
2454 split_reduction_stmt (gimple stmt
)
2456 gimple_stmt_iterator gsi
;
2457 basic_block bb
= gimple_bb (stmt
);
2460 /* Do not split basic blocks with no writes to memory: the reduction
2461 will be the only write to memory. */
2462 if (nb_data_writes_in_bb (bb
) == 0)
2465 split_block (bb
, stmt
);
2467 if (gsi_one_before_end_p (gsi_start_bb (bb
)))
2470 gsi
= gsi_last_bb (bb
);
2472 e
= split_block (bb
, gsi_stmt (gsi
));
2477 /* Return true when stmt is a reduction operation. */
2480 is_reduction_operation_p (gimple stmt
)
2482 enum tree_code code
;
2484 gcc_assert (is_gimple_assign (stmt
));
2485 code
= gimple_assign_rhs_code (stmt
);
2487 return flag_associative_math
2488 && commutative_tree_code (code
)
2489 && associative_tree_code (code
);
2492 /* Returns true when PHI contains an argument ARG. */
2495 phi_contains_arg (gimple phi
, tree arg
)
2499 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2500 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2506 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2509 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2513 if (TREE_CODE (arg
) != SSA_NAME
)
2516 stmt
= SSA_NAME_DEF_STMT (arg
);
2518 if (gimple_code (stmt
) == GIMPLE_NOP
2519 || gimple_code (stmt
) == GIMPLE_CALL
)
2522 if (gimple_code (stmt
) == GIMPLE_PHI
)
2524 if (phi_contains_arg (stmt
, lhs
))
2529 if (!is_gimple_assign (stmt
))
2532 if (gimple_num_ops (stmt
) == 2)
2533 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2535 if (is_reduction_operation_p (stmt
))
2537 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2540 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2546 /* Detect commutative and associative scalar reductions starting at
2547 the STMT. Return the phi node of the reduction cycle, or NULL. */
2550 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2551 VEC (gimple
, heap
) **in
,
2552 VEC (gimple
, heap
) **out
)
2554 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2559 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2560 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2564 /* Detect commutative and associative scalar reductions starting at
2565 the STMT. Return the phi node of the reduction cycle, or NULL. */
2568 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2569 VEC (gimple
, heap
) **out
)
2571 tree lhs
= gimple_assign_lhs (stmt
);
2573 if (gimple_num_ops (stmt
) == 2)
2574 return detect_commutative_reduction_arg (lhs
, stmt
,
2575 gimple_assign_rhs1 (stmt
),
2578 if (is_reduction_operation_p (stmt
))
2580 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2581 gimple_assign_rhs1 (stmt
),
2584 : detect_commutative_reduction_arg (lhs
, stmt
,
2585 gimple_assign_rhs2 (stmt
),
2592 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2595 follow_inital_value_to_phi (tree arg
, tree lhs
)
2599 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2602 stmt
= SSA_NAME_DEF_STMT (arg
);
2604 if (gimple_code (stmt
) == GIMPLE_PHI
2605 && phi_contains_arg (stmt
, lhs
))
2612 /* Return the argument of the loop PHI that is the inital value coming
2613 from outside the loop. */
2616 edge_initial_value_for_loop_phi (gimple phi
)
2620 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2622 edge e
= gimple_phi_arg_edge (phi
, i
);
2624 if (loop_depth (e
->src
->loop_father
)
2625 < loop_depth (e
->dest
->loop_father
))
2632 /* Return the argument of the loop PHI that is the inital value coming
2633 from outside the loop. */
2636 initial_value_for_loop_phi (gimple phi
)
2640 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2642 edge e
= gimple_phi_arg_edge (phi
, i
);
2644 if (loop_depth (e
->src
->loop_father
)
2645 < loop_depth (e
->dest
->loop_father
))
2646 return gimple_phi_arg_def (phi
, i
);
2652 /* Detect commutative and associative scalar reductions starting at
2653 the loop closed phi node CLOSE_PHI. Return the phi node of the
2654 reduction cycle, or NULL. */
2657 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2658 VEC (gimple
, heap
) **out
)
2660 if (scalar_close_phi_node_p (stmt
))
2662 tree arg
= gimple_phi_arg_def (stmt
, 0);
2663 gimple def
, loop_phi
;
2665 if (TREE_CODE (arg
) != SSA_NAME
)
2668 def
= SSA_NAME_DEF_STMT (arg
);
2669 loop_phi
= detect_commutative_reduction (def
, in
, out
);
2673 tree lhs
= gimple_phi_result (stmt
);
2674 tree init
= initial_value_for_loop_phi (loop_phi
);
2675 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2677 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2678 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2685 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2686 return detect_commutative_reduction_assign (stmt
, in
, out
);
2691 /* Translate the scalar reduction statement STMT to an array RED
2692 knowing that its recursive phi node is LOOP_PHI. */
2695 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2698 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2699 tree res
= gimple_phi_result (loop_phi
);
2700 gimple assign
= gimple_build_assign (res
, red
);
2702 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2704 insert_gsi
= gsi_after_labels (gimple_bb (stmt
));
2705 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2706 insert_gsi
= gsi_for_stmt (stmt
);
2707 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2710 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2713 insert_copyout (tree red
, gimple close_phi
)
2715 tree res
= gimple_phi_result (close_phi
);
2716 basic_block bb
= gimple_bb (close_phi
);
2717 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2718 gimple assign
= gimple_build_assign (res
, red
);
2720 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2723 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2726 insert_copyin (tree red
, gimple loop_phi
)
2729 tree init
= initial_value_for_loop_phi (loop_phi
);
2730 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2732 force_gimple_operand (expr
, &stmts
, true, NULL
);
2733 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2736 /* Removes the PHI node and resets all the debug stmts that are using
2740 remove_phi (gimple phi
)
2742 imm_use_iterator imm_iter
;
2744 use_operand_p use_p
;
2745 gimple_stmt_iterator gsi
;
2746 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2750 def
= PHI_RESULT (phi
);
2751 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2753 stmt
= USE_STMT (use_p
);
2755 if (is_gimple_debug (stmt
))
2757 gimple_debug_bind_reset_value (stmt
);
2758 VEC_safe_push (gimple
, heap
, update
, stmt
);
2762 for (i
= 0; VEC_iterate (gimple
, update
, i
, stmt
); i
++)
2765 VEC_free (gimple
, heap
, update
);
2767 gsi
= gsi_for_phi_node (phi
);
2768 remove_phi_node (&gsi
, false);
2771 /* Rewrite out of SSA the reduction described by the loop phi nodes
2772 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2775 IN: stmt, loop_n, ..., loop_0
2776 OUT: stmt, close_n, ..., close_0
2778 the first element is the reduction statement, and the next elements
2779 are the loop and close phi nodes of each of the outer loops. */
2782 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2783 VEC (gimple
, heap
) *out
,
2790 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2792 gimple close_phi
= VEC_index (gimple
, out
, i
);
2796 gimple stmt
= loop_phi
;
2797 basic_block bb
= split_reduction_stmt (stmt
);
2799 SET_BIT (reductions
, bb
->index
);
2800 gcc_assert (close_phi
== loop_phi
);
2802 red
= create_zero_dim_array
2803 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2804 translate_scalar_reduction_to_array_for_stmt
2805 (red
, stmt
, VEC_index (gimple
, in
, 1));
2809 if (i
== VEC_length (gimple
, in
) - 1)
2811 insert_copyout (red
, close_phi
);
2812 insert_copyin (red
, loop_phi
);
2815 remove_phi (loop_phi
);
2816 remove_phi (close_phi
);
2820 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2823 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2826 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2827 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2829 detect_commutative_reduction (close_phi
, &in
, &out
);
2830 if (VEC_length (gimple
, in
) > 0)
2831 translate_scalar_reduction_to_array (in
, out
, reductions
);
2833 VEC_free (gimple
, heap
, in
);
2834 VEC_free (gimple
, heap
, out
);
2837 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2840 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2843 gimple_stmt_iterator gsi
;
2844 edge exit
= single_exit (loop
);
2849 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2850 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2854 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2857 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2862 FOR_EACH_LOOP (li
, loop
, 0)
2863 if (loop_in_sese_p (loop
, region
))
2864 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2866 gsi_commit_edge_inserts ();
2867 update_ssa (TODO_update_ssa
);
2868 #ifdef ENABLE_CHECKING
2870 verify_loop_closed_ssa ();
2874 /* A LOOP is in normal form for Graphite when it contains only one
2875 scalar phi node that defines the main induction variable of the
2876 loop, only one increment of the IV, and only one exit condition. */
2879 graphite_loop_normal_form (loop_p loop
)
2881 struct tree_niter_desc niter
;
2884 edge exit
= single_dom_exit (loop
);
2886 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2888 /* At this point we should know the number of iterations, */
2889 gcc_assert (known_niter
);
2891 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2894 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2896 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
);
2899 /* Rewrite all the loops of SCOP in normal form: one induction
2900 variable per loop. */
2903 scop_canonicalize_loops (scop_p scop
)
2908 FOR_EACH_LOOP (li
, loop
, 0)
2909 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2910 graphite_loop_normal_form (loop
);
2913 /* Can all ivs be represented by a signed integer?
2914 As CLooG might generate negative values in its expressions, signed loop ivs
2915 are required in the backend. */
2917 scop_ivs_can_be_represented (scop_p scop
)
2922 FOR_EACH_LOOP (li
, loop
, 0)
2927 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2930 if (!loop
->single_iv
)
2933 type
= TREE_TYPE(loop
->single_iv
);
2934 precision
= TYPE_PRECISION (type
);
2936 if (TYPE_UNSIGNED (type
)
2937 && precision
>= TYPE_PRECISION (long_long_integer_type_node
))
2945 /* Builds the polyhedral representation for a SESE region. */
2948 build_poly_scop (scop_p scop
)
2950 sese region
= SCOP_REGION (scop
);
2951 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2952 graphite_dim_t max_dim
;
2954 sbitmap_zero (reductions
);
2955 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2956 rewrite_reductions_out_of_ssa (scop
);
2957 build_scop_bbs (scop
, reductions
);
2958 sbitmap_free (reductions
);
2960 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2961 Once CLooG is fixed, remove this guard. Anyways, it makes no
2962 sense to optimize a scop containing only PBBs that do not belong
2964 if (nb_pbbs_in_loops (scop
) == 0)
2967 scop_canonicalize_loops (scop
);
2968 if (!scop_ivs_can_be_represented (scop
))
2971 build_sese_loop_nests (region
);
2972 build_sese_conditions (region
);
2973 find_scop_parameters (scop
);
2975 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2976 if (scop_nb_params (scop
) > max_dim
)
2979 build_scop_iteration_domain (scop
);
2980 build_scop_context (scop
);
2982 add_conditions_to_constraints (scop
);
2984 build_scop_scattering (scop
);
2985 build_scop_drs (scop
);
2987 /* This SCoP has been translated to the polyhedral
2989 POLY_SCOP_P (scop
) = true;
2992 /* Always return false. Exercise the scop_to_clast function. */
2995 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2997 #ifdef ENABLE_CHECKING
2998 cloog_prog_clast pc
= scop_to_clast (scop
);
2999 cloog_clast_free (pc
.stmt
);
3000 cloog_program_free (pc
.prog
);