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
++)
305 free_gimple_bb (struct gimple_bb
*gbb
)
307 if (GBB_CLOOG_IV_TYPES (gbb
))
308 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
310 free_data_refs_aux (GBB_DATA_REFS (gbb
));
311 free_data_refs (GBB_DATA_REFS (gbb
));
313 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
314 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
315 GBB_BB (gbb
)->aux
= 0;
319 /* Deletes all gimple bbs in SCOP. */
322 remove_gbbs_in_scop (scop_p scop
)
327 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
328 free_gimple_bb (PBB_BLACK_BOX (pbb
));
331 /* Deletes all scops in SCOPS. */
334 free_scops (VEC (scop_p
, heap
) *scops
)
339 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
341 remove_gbbs_in_scop (scop
);
342 free_sese (SCOP_REGION (scop
));
346 VEC_free (scop_p
, heap
, scops
);
349 /* Generates a polyhedral black box only if the bb contains interesting
353 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
355 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
356 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
357 gimple_stmt_iterator gsi
;
359 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
361 gimple stmt
= gsi_stmt (gsi
);
362 if (!is_gimple_debug (stmt
))
363 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
366 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
367 free_data_refs (drs
);
369 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
373 /* Returns true if all predecessors of BB, that are not dominated by BB, are
374 marked in MAP. The predecessors dominated by BB are loop latches and will
375 be handled after BB. */
378 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
383 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
384 if (!TEST_BIT (map
, e
->src
->index
)
385 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
391 /* Compare the depth of two basic_block's P1 and P2. */
394 compare_bb_depths (const void *p1
, const void *p2
)
396 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
397 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
398 int d1
= loop_depth (bb1
->loop_father
);
399 int d2
= loop_depth (bb2
->loop_father
);
410 /* Sort the basic blocks from DOM such that the first are the ones at
411 a deepest loop level. */
414 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
416 size_t len
= VEC_length (basic_block
, dom
);
418 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
422 /* Recursive helper function for build_scops_bbs. */
425 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
427 sese region
= SCOP_REGION (scop
);
428 VEC (basic_block
, heap
) *dom
;
430 if (TEST_BIT (visited
, bb
->index
)
431 || !bb_in_sese_p (bb
, region
))
434 try_generate_gimple_bb (scop
, bb
, reductions
);
435 SET_BIT (visited
, bb
->index
);
437 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
442 graphite_sort_dominated_info (dom
);
444 while (!VEC_empty (basic_block
, dom
))
449 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
450 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
452 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
453 VEC_unordered_remove (basic_block
, dom
, i
);
458 VEC_free (basic_block
, heap
, dom
);
461 /* Gather the basic blocks belonging to the SCOP. */
464 build_scop_bbs (scop_p scop
, sbitmap reductions
)
466 sbitmap visited
= sbitmap_alloc (last_basic_block
);
467 sese region
= SCOP_REGION (scop
);
469 sbitmap_zero (visited
);
470 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
471 sbitmap_free (visited
);
474 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
475 We generate SCATTERING_DIMENSIONS scattering dimensions.
477 CLooG 0.15.0 and previous versions require, that all
478 scattering functions of one CloogProgram have the same number of
479 scattering dimensions, therefore we allow to specify it. This
480 should be removed in future versions of CLooG.
482 The scattering polyhedron consists of these dimensions: scattering,
483 loop_iterators, parameters.
487 | scattering_dimensions = 5
488 | used_scattering_dimensions = 3
496 | Scattering polyhedron:
498 | scattering: {s1, s2, s3, s4, s5}
499 | loop_iterators: {i}
500 | parameters: {p1, p2}
502 | s1 s2 s3 s4 s5 i p1 p2 1
503 | 1 0 0 0 0 0 0 0 -4 = 0
504 | 0 1 0 0 0 -1 0 0 0 = 0
505 | 0 0 1 0 0 0 0 0 -5 = 0 */
508 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
509 poly_bb_p pbb
, int scattering_dimensions
)
512 scop_p scop
= PBB_SCOP (pbb
);
513 int nb_iterators
= pbb_dim_iter_domain (pbb
);
514 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
515 int nb_params
= scop_nb_params (scop
);
517 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
520 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
523 ppl_new_Coefficient (&c
);
524 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
525 ppl_new_C_Polyhedron_from_space_dimension
526 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
528 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
530 for (i
= 0; i
< scattering_dimensions
; i
++)
532 ppl_Constraint_t cstr
;
533 ppl_Linear_Expression_t expr
;
535 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
537 ppl_assign_Coefficient_from_mpz_t (c
, v
);
538 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
540 /* Textual order inside this loop. */
543 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
544 ppl_Coefficient_to_mpz_t (c
, v
);
546 ppl_assign_Coefficient_from_mpz_t (c
, v
);
547 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
550 /* Iterations of this loop. */
551 else /* if ((i % 2) == 1) */
553 int loop
= (i
- 1) / 2;
555 value_set_si (v
, -1);
556 ppl_assign_Coefficient_from_mpz_t (c
, v
);
557 ppl_Linear_Expression_add_to_coefficient
558 (expr
, scattering_dimensions
+ loop
, c
);
561 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
562 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
563 ppl_delete_Linear_Expression (expr
);
564 ppl_delete_Constraint (cstr
);
568 ppl_delete_Coefficient (c
);
570 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
573 /* Build for BB the static schedule.
575 The static schedule is a Dewey numbering of the abstract syntax
576 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
578 The following example informally defines the static schedule:
597 Static schedules for A to F:
610 build_scop_scattering (scop_p scop
)
614 gimple_bb_p previous_gbb
= NULL
;
615 ppl_Linear_Expression_t static_schedule
;
620 ppl_new_Coefficient (&c
);
621 ppl_new_Linear_Expression (&static_schedule
);
623 /* We have to start schedules at 0 on the first component and
624 because we cannot compare_prefix_loops against a previous loop,
625 prefix will be equal to zero, and that index will be
626 incremented before copying. */
627 value_set_si (v
, -1);
628 ppl_assign_Coefficient_from_mpz_t (c
, v
);
629 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
631 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
633 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
634 ppl_Linear_Expression_t common
;
636 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
639 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
644 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
645 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
649 ppl_assign_Coefficient_from_mpz_t (c
, v
);
650 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
651 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
654 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
656 ppl_delete_Linear_Expression (common
);
660 ppl_delete_Coefficient (c
);
661 ppl_delete_Linear_Expression (static_schedule
);
664 /* Add the value K to the dimension D of the linear expression EXPR. */
667 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
671 ppl_Coefficient_t coef
;
673 ppl_new_Coefficient (&coef
);
674 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
676 ppl_Coefficient_to_mpz_t (coef
, val
);
678 value_addto (val
, val
, k
);
680 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
681 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
683 ppl_delete_Coefficient (coef
);
686 /* In the context of scop S, scan E, the right hand side of a scalar
687 evolution function in loop VAR, and translate it to a linear
691 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
692 ppl_Linear_Expression_t expr
)
696 loop_p loop
= get_loop (var
);
697 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
700 /* Scalar evolutions should happen in the sese region. */
701 gcc_assert (sese_loop_depth (s
, loop
) > 0);
703 /* We can not deal with parametric strides like:
709 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
712 value_set_si (val
, int_cst_value (e
));
713 add_value_to_dim (l
, expr
, val
);
718 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
719 linear expression EXPR. K is the multiplier of the constant. */
722 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
725 ppl_Coefficient_t coef
;
726 int v
= int_cst_value (cst
);
729 value_set_si (val
, 0);
731 /* Necessary to not get "-1 = 2^n - 1". */
733 value_sub_int (val
, val
, -v
);
735 value_add_int (val
, val
, v
);
737 value_multiply (val
, val
, k
);
738 ppl_new_Coefficient (&coef
);
739 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
740 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
742 ppl_delete_Coefficient (coef
);
745 /* Saves in NV at index I a new name for variable P. */
748 save_var_name (char **nv
, int i
, tree p
)
750 const char *name
= get_name (SSA_NAME_VAR (p
));
754 int len
= strlen (name
) + 16;
755 nv
[i
] = XNEWVEC (char, len
);
756 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
760 nv
[i
] = XNEWVEC (char, 16);
761 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
765 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
766 Otherwise returns -1. */
769 parameter_index_in_region_1 (tree name
, sese region
)
774 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
776 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
783 /* When the parameter NAME is in REGION, returns its index in
784 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
785 and returns the index of NAME. */
788 parameter_index_in_region (tree name
, sese region
)
792 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
794 i
= parameter_index_in_region_1 (name
, region
);
798 gcc_assert (SESE_ADD_PARAMS (region
));
800 i
= VEC_length (tree
, SESE_PARAMS (region
));
801 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
802 save_clast_name_index (SESE_PARAMS_INDEX (region
),
803 SESE_PARAMS_NAMES (region
)[i
], i
);
804 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
808 /* In the context of sese S, scan the expression E and translate it to
809 a linear expression C. When parsing a symbolic multiplication, K
810 represents the constant multiplier of an expression containing
814 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
817 if (e
== chrec_dont_know
)
820 switch (TREE_CODE (e
))
822 case POLYNOMIAL_CHREC
:
823 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
824 CHREC_VARIABLE (e
), c
);
825 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
829 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
834 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
836 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
837 value_multiply (val
, val
, k
);
838 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
842 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
849 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
851 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
852 value_multiply (val
, val
, k
);
853 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
857 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
862 case POINTER_PLUS_EXPR
:
863 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
864 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
869 ppl_Linear_Expression_t tmp_expr
= NULL
;
873 ppl_dimension_type dim
;
874 ppl_Linear_Expression_space_dimension (c
, &dim
);
875 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
878 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
879 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
883 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
885 ppl_delete_Linear_Expression (tmp_expr
);
893 ppl_Linear_Expression_t tmp_expr
= NULL
;
897 ppl_dimension_type dim
;
898 ppl_Linear_Expression_space_dimension (c
, &dim
);
899 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
902 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
906 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
908 ppl_delete_Linear_Expression (tmp_expr
);
916 ppl_Linear_Expression_t tmp_expr
= NULL
;
920 ppl_dimension_type dim
;
921 ppl_Linear_Expression_space_dimension (c
, &dim
);
922 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
925 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
929 ppl_Coefficient_t coef
;
932 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
934 ppl_delete_Linear_Expression (tmp_expr
);
935 value_init (minus_one
);
936 value_set_si (minus_one
, -1);
937 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
938 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
939 value_clear (minus_one
);
940 ppl_delete_Coefficient (coef
);
948 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
952 ppl_dimension_type dim
;
953 ppl_Linear_Expression_space_dimension (c
, &dim
);
954 p
+= dim
- sese_nb_params (s
);
955 add_value_to_dim (p
, c
, k
);
962 scan_tree_for_params_int (e
, c
, k
);
966 case NON_LVALUE_EXPR
:
967 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
976 /* Find parameters with respect to REGION in BB. We are looking in memory
977 access functions, conditions and loop bounds. */
980 find_params_in_bb (sese region
, gimple_bb_p gbb
)
986 loop_p loop
= GBB_BB (gbb
)->loop_father
;
990 value_set_si (one
, 1);
992 /* Find parameters in the access functions of data references. */
993 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
994 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
995 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
997 /* Find parameters in conditional statements. */
998 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
1000 tree lhs
= scalar_evolution_in_region (region
, loop
,
1001 gimple_cond_lhs (stmt
));
1002 tree rhs
= scalar_evolution_in_region (region
, loop
,
1003 gimple_cond_rhs (stmt
));
1005 scan_tree_for_params (region
, lhs
, NULL
, one
);
1006 scan_tree_for_params (region
, rhs
, NULL
, one
);
1012 /* Record the parameters used in the SCOP. A variable is a parameter
1013 in a scop if it does not vary during the execution of that scop. */
1016 find_scop_parameters (scop_p scop
)
1020 sese region
= SCOP_REGION (scop
);
1025 value_set_si (one
, 1);
1027 /* Find the parameters used in the loop bounds. */
1028 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1030 tree nb_iters
= number_of_latch_executions (loop
);
1032 if (!chrec_contains_symbols (nb_iters
))
1035 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1036 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1041 /* Find the parameters used in data accesses. */
1042 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1043 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1045 scop_set_nb_params (scop
, sese_nb_params (region
));
1046 SESE_ADD_PARAMS (region
) = false;
1048 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1049 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1052 /* Returns a gimple_bb from BB. */
1054 static inline gimple_bb_p
1055 gbb_from_bb (basic_block bb
)
1057 return (gimple_bb_p
) bb
->aux
;
1060 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1061 the constraints for the surrounding loops. */
1064 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1065 ppl_Polyhedron_t outer_ph
, int nb
)
1068 ppl_Polyhedron_t ph
;
1069 tree nb_iters
= number_of_latch_executions (loop
);
1070 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1071 sese region
= SCOP_REGION (scop
);
1074 ppl_const_Constraint_System_t pcs
;
1075 ppl_dimension_type
*map
1076 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1078 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1079 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1080 ppl_Polyhedron_add_constraints (ph
, pcs
);
1082 for (i
= 0; i
< (int) nb
; i
++)
1084 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1088 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1094 ppl_Constraint_t lb
;
1095 ppl_Linear_Expression_t lb_expr
;
1097 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1098 ppl_set_coef (lb_expr
, nb
, 1);
1099 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1100 ppl_delete_Linear_Expression (lb_expr
);
1101 ppl_Polyhedron_add_constraint (ph
, lb
);
1102 ppl_delete_Constraint (lb
);
1105 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1107 ppl_Constraint_t ub
;
1108 ppl_Linear_Expression_t ub_expr
;
1110 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1112 /* loop_i <= cst_nb_iters */
1113 ppl_set_coef (ub_expr
, nb
, -1);
1114 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1115 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1116 ppl_Polyhedron_add_constraint (ph
, ub
);
1117 ppl_delete_Linear_Expression (ub_expr
);
1118 ppl_delete_Constraint (ub
);
1120 else if (!chrec_contains_undetermined (nb_iters
))
1123 ppl_Constraint_t ub
;
1124 ppl_Linear_Expression_t ub_expr
;
1128 value_set_si (one
, 1);
1129 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1130 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1131 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1134 /* N <= estimated_nb_iters
1136 FIXME: This is a workaround that should go away once we will
1137 have the PIP algorithm. */
1138 if (estimated_loop_iterations (loop
, true, &nit
))
1141 ppl_Linear_Expression_t nb_iters_le
;
1142 ppl_Polyhedron_t pol
;
1143 graphite_dim_t n
= scop_nb_params (scop
);
1144 ppl_Coefficient_t coef
;
1146 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1147 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1150 /* Construct the negated number of last iteration in VAL. */
1152 mpz_set_double_int (val
, nit
, false);
1153 value_sub_int (val
, val
, 1);
1154 value_oppose (val
, val
);
1156 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1157 Subtract estimated number of last iteration and assert that result
1159 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1160 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1161 ppl_delete_Coefficient (coef
);
1162 ppl_new_Constraint (&ub
, nb_iters_le
,
1163 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1164 ppl_Polyhedron_add_constraint (pol
, ub
);
1166 /* Remove all but last N dimensions from POL to obtain constraints
1169 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- n
);
1171 for (i
= 0; i
< dim
- n
; i
++)
1173 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- n
);
1177 /* Add constraints on parameters to SCoP context. */
1179 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1180 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1181 (&constraints_ps
, pol
);
1182 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1183 (SCOP_CONTEXT (scop
), constraints_ps
);
1184 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1187 ppl_delete_Polyhedron (pol
);
1188 ppl_delete_Linear_Expression (nb_iters_le
);
1189 ppl_delete_Constraint (ub
);
1193 /* loop_i <= expr_nb_iters */
1194 ppl_set_coef (ub_expr
, nb
, -1);
1195 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1196 ppl_Polyhedron_add_constraint (ph
, ub
);
1197 ppl_delete_Linear_Expression (ub_expr
);
1198 ppl_delete_Constraint (ub
);
1203 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1204 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1208 && loop_in_sese_p (loop
->next
, region
))
1209 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1211 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1212 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1214 ppl_delete_Polyhedron (ph
);
1217 /* Returns a linear expression for tree T evaluated in PBB. */
1219 static ppl_Linear_Expression_t
1220 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1223 ppl_Linear_Expression_t res
;
1224 ppl_dimension_type dim
;
1225 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1226 loop_p loop
= pbb_loop (pbb
);
1228 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1229 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1231 t
= scalar_evolution_in_region (region
, loop
, t
);
1232 gcc_assert (!automatically_generated_chrec_p (t
));
1235 value_set_si (one
, 1);
1236 scan_tree_for_params (region
, t
, res
, one
);
1242 /* Returns the ppl constraint type from the gimple tree code CODE. */
1244 static enum ppl_enum_Constraint_Type
1245 ppl_constraint_type_from_tree_code (enum tree_code code
)
1249 /* We do not support LT and GT to be able to work with C_Polyhedron.
1250 As we work on integer polyhedron "a < b" can be expressed by
1257 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1260 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1263 return PPL_CONSTRAINT_TYPE_EQUAL
;
1270 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1271 CODE is used as the comparison operator. This allows us to invert the
1272 condition or to handle inequalities. */
1275 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1276 poly_bb_p pbb
, enum tree_code code
)
1279 ppl_Coefficient_t c
;
1280 ppl_Linear_Expression_t left
, right
;
1281 ppl_Constraint_t cstr
;
1282 enum ppl_enum_Constraint_Type type
;
1284 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1285 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1287 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1288 the left or the right side of the expression. */
1289 if (code
== LT_EXPR
)
1292 value_set_si (v
, 1);
1293 ppl_new_Coefficient (&c
);
1294 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1295 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1296 ppl_delete_Coefficient (c
);
1301 else if (code
== GT_EXPR
)
1304 value_set_si (v
, 1);
1305 ppl_new_Coefficient (&c
);
1306 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1307 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1308 ppl_delete_Coefficient (c
);
1314 type
= ppl_constraint_type_from_tree_code (code
);
1316 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1318 ppl_new_Constraint (&cstr
, left
, type
);
1319 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1321 ppl_delete_Constraint (cstr
);
1322 ppl_delete_Linear_Expression (left
);
1323 ppl_delete_Linear_Expression (right
);
1326 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1327 operator. This allows us to invert the condition or to handle
1331 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1333 if (code
== NE_EXPR
)
1335 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1336 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1337 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1339 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1340 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1341 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1343 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1346 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1349 /* Add conditions to the domain of PBB. */
1352 add_conditions_to_domain (poly_bb_p pbb
)
1356 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1357 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1359 if (VEC_empty (gimple
, conditions
))
1362 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1363 switch (gimple_code (stmt
))
1367 enum tree_code code
= gimple_cond_code (stmt
);
1369 /* The conditions for ELSE-branches are inverted. */
1370 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1371 code
= invert_tree_comparison (code
, false);
1373 add_condition_to_pbb (pbb
, stmt
, code
);
1378 /* Switch statements are not supported right now - fall throught. */
1386 /* Structure used to pass data to dom_walk. */
1390 VEC (gimple
, heap
) **conditions
, **cases
;
1394 /* Returns non NULL when BB has a single predecessor and the last
1395 statement of that predecessor is a COND_EXPR. */
1398 single_pred_cond (basic_block bb
)
1400 if (single_pred_p (bb
))
1402 edge e
= single_pred_edge (bb
);
1403 basic_block pred
= e
->src
;
1404 gimple stmt
= last_stmt (pred
);
1406 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1412 /* Call-back for dom_walk executed before visiting the dominated
1416 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1419 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1420 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1421 VEC (gimple
, heap
) **cases
= data
->cases
;
1422 gimple_bb_p gbb
= gbb_from_bb (bb
);
1423 gimple stmt
= single_pred_cond (bb
);
1425 if (!bb_in_sese_p (bb
, data
->region
))
1430 edge e
= single_pred_edge (bb
);
1432 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1434 if (e
->flags
& EDGE_TRUE_VALUE
)
1435 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1437 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1442 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1443 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1447 /* Call-back for dom_walk executed after visiting the dominated
1451 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1454 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1455 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1456 VEC (gimple
, heap
) **cases
= data
->cases
;
1458 if (!bb_in_sese_p (bb
, data
->region
))
1461 if (single_pred_cond (bb
))
1463 VEC_pop (gimple
, *conditions
);
1464 VEC_pop (gimple
, *cases
);
1468 /* Record all conditions in REGION. */
1471 build_sese_conditions (sese region
)
1473 struct dom_walk_data walk_data
;
1474 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1475 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1478 data
.conditions
= &conditions
;
1479 data
.cases
= &cases
;
1480 data
.region
= region
;
1482 walk_data
.dom_direction
= CDI_DOMINATORS
;
1483 walk_data
.initialize_block_local_data
= NULL
;
1484 walk_data
.before_dom_children
= build_sese_conditions_before
;
1485 walk_data
.after_dom_children
= build_sese_conditions_after
;
1486 walk_data
.global_data
= &data
;
1487 walk_data
.block_local_data_size
= 0;
1489 init_walk_dominator_tree (&walk_data
);
1490 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1491 fini_walk_dominator_tree (&walk_data
);
1493 VEC_free (gimple
, heap
, conditions
);
1494 VEC_free (gimple
, heap
, cases
);
1497 /* Traverses all the GBBs of the SCOP and add their constraints to the
1498 iteration domains. */
1501 add_conditions_to_constraints (scop_p scop
)
1506 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1507 add_conditions_to_domain (pbb
);
1510 /* Add constraints on the possible values of parameter P from the type
1514 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1516 ppl_Constraint_t cstr
;
1517 ppl_Linear_Expression_t le
;
1518 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1519 tree type
= TREE_TYPE (parameter
);
1522 /* Disabled until we fix CPU2006. */
1525 if (!INTEGRAL_TYPE_P (type
))
1528 lb
= TYPE_MIN_VALUE (type
);
1529 ub
= TYPE_MAX_VALUE (type
);
1533 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1534 ppl_set_coef (le
, p
, -1);
1535 ppl_set_inhomogeneous_tree (le
, lb
);
1536 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1537 ppl_Polyhedron_add_constraint (context
, cstr
);
1538 ppl_delete_Linear_Expression (le
);
1539 ppl_delete_Constraint (cstr
);
1544 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1545 ppl_set_coef (le
, p
, -1);
1546 ppl_set_inhomogeneous_tree (le
, ub
);
1547 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1548 ppl_Polyhedron_add_constraint (context
, cstr
);
1549 ppl_delete_Linear_Expression (le
);
1550 ppl_delete_Constraint (cstr
);
1554 /* Build the context of the SCOP. The context usually contains extra
1555 constraints that are added to the iteration domains that constrain
1559 build_scop_context (scop_p scop
)
1561 ppl_Polyhedron_t context
;
1562 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1563 graphite_dim_t p
, n
= scop_nb_params (scop
);
1565 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1567 for (p
= 0; p
< n
; p
++)
1568 add_param_constraints (scop
, context
, p
);
1570 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1572 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1573 (SCOP_CONTEXT (scop
), ps
);
1575 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1576 ppl_delete_Polyhedron (context
);
1579 /* Build the iteration domains: the loops belonging to the current
1580 SCOP, and that vary for the execution of the current basic block.
1581 Returns false if there is no loop in SCOP. */
1584 build_scop_iteration_domain (scop_p scop
)
1587 sese region
= SCOP_REGION (scop
);
1589 ppl_Polyhedron_t ph
;
1592 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1594 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1595 if (!loop_in_sese_p (loop_outer (loop
), region
))
1596 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1598 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1599 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1600 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1601 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1602 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1604 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1605 (&PBB_DOMAIN (pbb
), ph
);
1607 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1610 ppl_delete_Pointset_Powerset_C_Polyhedron
1611 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1615 ppl_delete_Polyhedron (ph
);
1618 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1619 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1620 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1624 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1625 ppl_dimension_type accessp_nb_dims
,
1626 ppl_dimension_type dom_nb_dims
)
1628 ppl_Linear_Expression_t alias
;
1629 ppl_Constraint_t cstr
;
1630 int alias_set_num
= 0;
1632 if (dr
->aux
!= NULL
)
1633 alias_set_num
= ((int *)(dr
->aux
))[ALIAS_SET_INDEX
];
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
);
1776 dr_base_object_set
= ((int *)(dr
->aux
))[BASE_OBJECT_SET_INDEX
];
1778 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1779 dr
, DR_NUM_DIMENSIONS (dr
));
1782 /* Write to FILE the alias graph of data references in DIMACS format. */
1785 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1786 VEC (data_reference_p
, heap
) *drs
)
1788 int num_vertex
= VEC_length (data_reference_p
, drs
);
1790 data_reference_p dr1
, dr2
;
1793 if (num_vertex
== 0)
1796 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1797 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1798 if (dr_may_alias_p (dr1
, dr2
))
1801 fprintf (file
, "$\n");
1804 fprintf (file
, "c %s\n", comment
);
1806 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1808 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1809 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1810 if (dr_may_alias_p (dr1
, dr2
))
1811 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1816 /* Write to FILE the alias graph of data references in DOT format. */
1819 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1820 VEC (data_reference_p
, heap
) *drs
)
1822 int num_vertex
= VEC_length (data_reference_p
, drs
);
1823 data_reference_p dr1
, dr2
;
1826 if (num_vertex
== 0)
1829 fprintf (file
, "$\n");
1832 fprintf (file
, "c %s\n", comment
);
1834 /* First print all the vertices. */
1835 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1836 fprintf (file
, "n%d;\n", i
);
1838 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1839 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1840 if (dr_may_alias_p (dr1
, dr2
))
1841 fprintf (file
, "n%d n%d\n", i
, j
);
1846 /* Write to FILE the alias graph of data references in ECC format. */
1849 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1850 VEC (data_reference_p
, heap
) *drs
)
1852 int num_vertex
= VEC_length (data_reference_p
, drs
);
1853 data_reference_p dr1
, dr2
;
1856 if (num_vertex
== 0)
1859 fprintf (file
, "$\n");
1862 fprintf (file
, "c %s\n", comment
);
1864 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1865 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1866 if (dr_may_alias_p (dr1
, dr2
))
1867 fprintf (file
, "%d %d\n", i
, j
);
1873 /* Uses DFS component number as representative of alias-sets. Also tests for
1874 optimality by verifying if every connected component is a clique. Returns
1875 true (1) if the above test is true, and false (0) otherwise. */
1878 partition_drs_to_sets (VEC (data_reference_p
, heap
) *drs
, int choice
,
1879 bool (* edge_exist_p
) (const struct data_reference
*,
1880 const struct data_reference
*))
1883 int num_vertices
= VEC_length (data_reference_p
, drs
);
1884 struct graph
*g
= new_graph (num_vertices
);
1885 data_reference_p dr1
, dr2
;
1887 int num_connected_components
;
1888 int v_indx1
, v_indx2
, num_vertices_in_component
;
1891 struct graph_edge
*e
;
1892 int this_component_is_clique
, all_components_are_cliques
;
1894 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1895 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1896 if (edge_exist_p (dr1
, dr2
))
1902 all_vertices
= XNEWVEC (int, num_vertices
);
1903 vertices
= XNEWVEC (int, num_vertices
);
1904 for (i
= 0; i
< num_vertices
; i
++)
1905 all_vertices
[i
] = i
;
1907 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
, NULL
, true, NULL
);
1909 /* Verify if the DFS numbering results in optimal solution. */
1910 for (i
= 0; i
< num_connected_components
; i
++)
1912 num_vertices_in_component
= 0;
1913 /* Get all vertices whose DFS component number is the same as i. */
1914 for (j
= 0; j
< num_vertices
; j
++)
1915 if (g
->vertices
[j
].component
== i
)
1916 vertices
[num_vertices_in_component
++] = j
;
1918 /* Now test if the vertices in 'vertices' form a clique, by testing
1919 for edges among each pair. */
1920 this_component_is_clique
= 1;
1921 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1923 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1925 /* Check if the two vertices are connected by iterating
1926 through all the edges which have one of these are source. */
1927 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1930 if (e
->src
== vertices
[v_indx1
])
1936 this_component_is_clique
= 0;
1940 if (!this_component_is_clique
)
1941 all_components_are_cliques
= 0;
1945 for (i
= 0; i
< g
->n_vertices
; i
++)
1947 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1949 dr
->aux
= XNEWVEC (int, 2);
1950 ((int *)(dr
->aux
))[choice
] = g
->vertices
[i
].component
+ 1;
1953 free (all_vertices
);
1956 return all_components_are_cliques
;
1960 dr_same_base_object_p (const struct data_reference
*dr1
,
1961 const struct data_reference
*dr2
)
1963 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1966 /* Group each data reference in DRS with it's alias set num. */
1969 build_alias_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1971 partition_drs_to_sets (drs
, ALIAS_SET_INDEX
, dr_may_alias_p
);
1974 /* Group each data reference in DRS with it's base object set num. */
1977 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1979 partition_drs_to_sets (drs
, BASE_OBJECT_SET_INDEX
, dr_same_base_object_p
);
1982 /* Build the data references for PBB. */
1985 build_pbb_drs (poly_bb_p pbb
)
1988 data_reference_p dr
;
1989 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1991 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1992 build_poly_dr (dr
, pbb
);
1995 /* Build data references in SCOP. */
1998 build_scop_drs (scop_p scop
)
2002 data_reference_p dr
;
2003 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2005 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2006 for (j
= 0; VEC_iterate (data_reference_p
,
2007 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2008 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2010 build_alias_set_for_drs (drs
);
2011 build_base_obj_set_for_drs (drs
);
2013 /* When debugging, enable the following code. This cannot be used
2014 in production compilers. */
2018 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2020 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2021 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2022 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2025 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2026 current_function_name ());
2027 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2028 fclose (file_dimacs
);
2032 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2033 current_function_name ());
2034 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2039 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2040 current_function_name ());
2041 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2047 VEC_free (data_reference_p
, heap
, drs
);
2049 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2050 build_pbb_drs (pbb
);
2053 /* Return a gsi at the position of the phi node STMT. */
2055 static gimple_stmt_iterator
2056 gsi_for_phi_node (gimple stmt
)
2058 gimple_stmt_iterator psi
;
2059 basic_block bb
= gimple_bb (stmt
);
2061 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2062 if (stmt
== gsi_stmt (psi
))
2069 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2072 insert_out_of_ssa_copy (tree res
, tree var
)
2076 gimple_stmt_iterator si
;
2077 gimple_stmt_iterator gsi
;
2079 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2080 stmt
= gimple_build_assign (res
, var
);
2082 stmts
= gimple_seq_alloc ();
2083 si
= gsi_last (stmts
);
2084 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2086 stmt
= SSA_NAME_DEF_STMT (var
);
2087 if (gimple_code (stmt
) == GIMPLE_PHI
)
2089 gsi
= gsi_after_labels (gimple_bb (stmt
));
2090 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2094 gsi
= gsi_for_stmt (stmt
);
2095 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2099 /* Insert on edge E the assignment "RES := EXPR". */
2102 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2104 gimple_stmt_iterator gsi
;
2106 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2107 gimple stmt
= gimple_build_assign (res
, var
);
2110 stmts
= gimple_seq_alloc ();
2112 gsi
= gsi_last (stmts
);
2113 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2114 gsi_insert_seq_on_edge (e
, stmts
);
2115 gsi_commit_edge_inserts ();
2118 /* Creates a zero dimension array of the same type as VAR. */
2121 create_zero_dim_array (tree var
)
2123 tree index_type
= build_index_type (integer_zero_node
);
2124 tree elt_type
= TREE_TYPE (var
);
2125 tree array_type
= build_array_type (elt_type
, index_type
);
2126 tree base
= create_tmp_var (array_type
, "Red");
2128 add_referenced_var (base
);
2130 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2134 /* Returns true when PHI is a loop close phi node. */
2137 scalar_close_phi_node_p (gimple phi
)
2139 if (gimple_code (phi
) != GIMPLE_PHI
2140 || !is_gimple_reg (gimple_phi_result (phi
)))
2143 return (gimple_phi_num_args (phi
) == 1);
2146 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2147 dimension array for it. */
2150 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2152 gimple phi
= gsi_stmt (*psi
);
2153 tree res
= gimple_phi_result (phi
);
2154 tree var
= SSA_NAME_VAR (res
);
2155 tree zero_dim_array
= create_zero_dim_array (var
);
2156 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2157 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2158 tree arg
= gimple_phi_arg_def (phi
, 0);
2160 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2162 remove_phi_node (psi
, false);
2163 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2164 SSA_NAME_DEF_STMT (res
) = stmt
;
2167 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2168 dimension array for it. */
2171 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2174 gimple phi
= gsi_stmt (*psi
);
2175 basic_block bb
= gimple_bb (phi
);
2176 tree res
= gimple_phi_result (phi
);
2177 tree var
= SSA_NAME_VAR (res
);
2178 tree zero_dim_array
= create_zero_dim_array (var
);
2179 gimple_stmt_iterator gsi
;
2183 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2185 tree arg
= gimple_phi_arg_def (phi
, i
);
2187 /* Try to avoid the insertion on edges as much as possible: this
2188 would avoid the insertion of code on loop latch edges, making
2189 the pattern matching of the vectorizer happy, or it would
2190 avoid the insertion of useless basic blocks. Note that it is
2191 incorrect to insert out of SSA copies close by their
2192 definition when they are more than two loop levels apart:
2193 for example, starting from a double nested loop
2203 the following transform is incorrect
2215 whereas inserting the copy on the incomming edge is correct
2227 if (TREE_CODE (arg
) == SSA_NAME
2228 && is_gimple_reg (arg
)
2229 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2230 && (flow_bb_inside_loop_p (bb
->loop_father
,
2231 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2232 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2233 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2234 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2236 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2237 zero_dim_array
, arg
);
2240 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2243 stmts
= gimple_seq_alloc ();
2245 stmt
= gimple_build_assign (res
, var
);
2246 remove_phi_node (psi
, false);
2247 SSA_NAME_DEF_STMT (res
) = stmt
;
2249 gsi
= gsi_last (stmts
);
2250 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2252 gsi
= gsi_after_labels (bb
);
2253 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2256 /* Return true when DEF can be analyzed in REGION by the scalar
2257 evolution analyzer. */
2260 scev_analyzable_p (tree def
, sese region
)
2262 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2263 loop_p loop
= loop_containing_stmt (stmt
);
2264 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2266 return !chrec_contains_undetermined (scev
);
2269 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2270 read from ZERO_DIM_ARRAY. */
2273 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2275 tree var
= SSA_NAME_VAR (def
);
2276 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2277 tree name
= make_ssa_name (var
, name_stmt
);
2279 use_operand_p use_p
;
2280 gimple_stmt_iterator gsi
;
2282 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2284 gimple_assign_set_lhs (name_stmt
, name
);
2286 gsi
= gsi_for_stmt (use_stmt
);
2287 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2289 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2290 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2291 replace_exp (use_p
, name
);
2293 update_stmt (use_stmt
);
2296 /* Rewrite the scalar dependences crossing the boundary of the BB
2297 containing STMT with an array. */
2300 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2302 gimple stmt
= gsi_stmt (*gsi
);
2303 imm_use_iterator imm_iter
;
2306 tree zero_dim_array
= NULL_TREE
;
2309 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2312 def
= gimple_assign_lhs (stmt
);
2313 if (!is_gimple_reg (def
)
2314 || scev_analyzable_p (def
, region
))
2317 def_bb
= gimple_bb (stmt
);
2319 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2320 if (def_bb
!= gimple_bb (use_stmt
)
2321 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2323 if (!zero_dim_array
)
2325 zero_dim_array
= create_zero_dim_array (SSA_NAME_VAR (def
));
2326 insert_out_of_ssa_copy (zero_dim_array
, def
);
2330 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2334 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2337 rewrite_reductions_out_of_ssa (scop_p scop
)
2340 gimple_stmt_iterator psi
;
2341 sese region
= SCOP_REGION (scop
);
2344 if (bb_in_sese_p (bb
, region
))
2345 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2347 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2348 rewrite_close_phi_out_of_ssa (&psi
);
2349 else if (reduction_phi_p (region
, &psi
))
2350 rewrite_phi_out_of_ssa (&psi
);
2353 update_ssa (TODO_update_ssa
);
2354 #ifdef ENABLE_CHECKING
2356 verify_loop_closed_ssa ();
2360 if (bb_in_sese_p (bb
, region
))
2361 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2362 rewrite_cross_bb_scalar_deps (region
, &psi
);
2364 update_ssa (TODO_update_ssa
);
2365 #ifdef ENABLE_CHECKING
2367 verify_loop_closed_ssa ();
2371 /* Returns the number of pbbs that are in loops contained in SCOP. */
2374 nb_pbbs_in_loops (scop_p scop
)
2380 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2381 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2387 /* Return the number of data references in BB that write in
2391 nb_data_writes_in_bb (basic_block bb
)
2394 gimple_stmt_iterator gsi
;
2396 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2397 if (gimple_vdef (gsi_stmt (gsi
)))
2403 /* Splits STMT out of its current BB. */
2406 split_reduction_stmt (gimple stmt
)
2408 gimple_stmt_iterator gsi
;
2409 basic_block bb
= gimple_bb (stmt
);
2412 /* Do not split basic blocks with no writes to memory: the reduction
2413 will be the only write to memory. */
2414 if (nb_data_writes_in_bb (bb
) == 0)
2417 split_block (bb
, stmt
);
2419 gsi
= gsi_last_bb (bb
);
2421 e
= split_block (bb
, gsi_stmt (gsi
));
2426 /* Return true when stmt is a reduction operation. */
2429 is_reduction_operation_p (gimple stmt
)
2431 return flag_associative_math
2432 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2433 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2436 /* Returns true when PHI contains an argument ARG. */
2439 phi_contains_arg (gimple phi
, tree arg
)
2443 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2444 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2450 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2453 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2457 if (TREE_CODE (arg
) != SSA_NAME
)
2460 stmt
= SSA_NAME_DEF_STMT (arg
);
2462 if (gimple_code (stmt
) == GIMPLE_PHI
)
2464 if (phi_contains_arg (stmt
, lhs
))
2469 if (gimple_num_ops (stmt
) == 2)
2470 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2472 if (is_reduction_operation_p (stmt
))
2474 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2477 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2483 /* Detect commutative and associative scalar reductions starting at
2487 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2488 VEC (gimple
, heap
) **in
,
2489 VEC (gimple
, heap
) **out
)
2491 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2495 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2496 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2503 /* Detect commutative and associative scalar reductions starting at
2507 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2508 VEC (gimple
, heap
) **out
)
2510 tree lhs
= gimple_assign_lhs (stmt
);
2512 if (gimple_num_ops (stmt
) == 2)
2513 return detect_commutative_reduction_arg (lhs
, stmt
,
2514 gimple_assign_rhs1 (stmt
),
2517 if (is_reduction_operation_p (stmt
))
2519 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2520 gimple_assign_rhs1 (stmt
),
2523 : detect_commutative_reduction_arg (lhs
, stmt
,
2524 gimple_assign_rhs2 (stmt
),
2531 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2534 follow_inital_value_to_phi (tree arg
, tree lhs
)
2538 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2541 stmt
= SSA_NAME_DEF_STMT (arg
);
2543 if (gimple_code (stmt
) == GIMPLE_PHI
2544 && phi_contains_arg (stmt
, lhs
))
2551 /* Return the argument of the loop PHI that is the inital value coming
2552 from outside the loop. */
2555 edge_initial_value_for_loop_phi (gimple phi
)
2559 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2561 edge e
= gimple_phi_arg_edge (phi
, i
);
2563 if (loop_depth (e
->src
->loop_father
)
2564 < loop_depth (e
->dest
->loop_father
))
2571 /* Return the argument of the loop PHI that is the inital value coming
2572 from outside the loop. */
2575 initial_value_for_loop_phi (gimple phi
)
2579 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2581 edge e
= gimple_phi_arg_edge (phi
, i
);
2583 if (loop_depth (e
->src
->loop_father
)
2584 < loop_depth (e
->dest
->loop_father
))
2585 return gimple_phi_arg_def (phi
, i
);
2591 /* Detect commutative and associative scalar reductions starting at
2592 the loop closed phi node CLOSE_PHI. */
2595 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2596 VEC (gimple
, heap
) **out
)
2598 if (scalar_close_phi_node_p (stmt
))
2600 tree arg
= gimple_phi_arg_def (stmt
, 0);
2601 gimple def
= SSA_NAME_DEF_STMT (arg
);
2602 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2606 tree lhs
= gimple_phi_result (stmt
);
2607 tree init
= initial_value_for_loop_phi (loop_phi
);
2608 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2610 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2611 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2618 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2619 return detect_commutative_reduction_assign (stmt
, in
, out
);
2624 /* Translate the scalar reduction statement STMT to an array RED
2625 knowing that its recursive phi node is LOOP_PHI. */
2628 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2631 basic_block bb
= gimple_bb (stmt
);
2632 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2633 tree res
= gimple_phi_result (loop_phi
);
2634 gimple assign
= gimple_build_assign (res
, red
);
2636 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2638 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2639 insert_gsi
= gsi_for_stmt (stmt
);
2640 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2643 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2646 insert_copyout (tree red
, gimple close_phi
)
2648 tree res
= gimple_phi_result (close_phi
);
2649 basic_block bb
= gimple_bb (close_phi
);
2650 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2651 gimple assign
= gimple_build_assign (res
, red
);
2653 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2656 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2659 insert_copyin (tree red
, gimple loop_phi
)
2662 tree init
= initial_value_for_loop_phi (loop_phi
);
2663 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2665 force_gimple_operand (expr
, &stmts
, true, NULL
);
2666 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2669 /* Rewrite out of SSA the reduction described by the loop phi nodes
2670 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2673 IN: stmt, loop_n, ..., loop_0
2674 OUT: stmt, close_n, ..., close_0
2676 the first element is the reduction statement, and the next elements
2677 are the loop and close phi nodes of each of the outer loops. */
2680 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2681 VEC (gimple
, heap
) *out
,
2687 gimple_stmt_iterator gsi
;
2689 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2691 gimple close_phi
= VEC_index (gimple
, out
, i
);
2695 gimple stmt
= loop_phi
;
2696 basic_block bb
= split_reduction_stmt (stmt
);
2698 SET_BIT (reductions
, bb
->index
);
2699 gcc_assert (close_phi
== loop_phi
);
2701 red
= create_zero_dim_array (gimple_assign_lhs (stmt
));
2702 translate_scalar_reduction_to_array_for_stmt
2703 (red
, stmt
, VEC_index (gimple
, in
, 1));
2707 if (i
== VEC_length (gimple
, in
) - 1)
2709 insert_copyout (red
, close_phi
);
2710 insert_copyin (red
, loop_phi
);
2713 gsi
= gsi_for_phi_node (loop_phi
);
2714 remove_phi_node (&gsi
, false);
2716 gsi
= gsi_for_phi_node (close_phi
);
2717 remove_phi_node (&gsi
, false);
2721 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2724 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2727 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2728 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2730 detect_commutative_reduction (close_phi
, &in
, &out
);
2731 if (VEC_length (gimple
, in
) > 0)
2732 translate_scalar_reduction_to_array (in
, out
, reductions
);
2734 VEC_free (gimple
, heap
, in
);
2735 VEC_free (gimple
, heap
, out
);
2738 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2741 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2744 gimple_stmt_iterator gsi
;
2745 edge exit
= single_exit (loop
);
2750 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2751 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2755 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2758 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2763 FOR_EACH_LOOP (li
, loop
, 0)
2764 if (loop_in_sese_p (loop
, region
))
2765 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2767 gsi_commit_edge_inserts ();
2768 update_ssa (TODO_update_ssa
);
2769 #ifdef ENABLE_CHECKING
2771 verify_loop_closed_ssa ();
2775 /* Builds the polyhedral representation for a SESE region. */
2778 build_poly_scop (scop_p scop
)
2780 sese region
= SCOP_REGION (scop
);
2781 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2783 sbitmap_zero (reductions
);
2784 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2785 rewrite_reductions_out_of_ssa (scop
);
2786 build_scop_bbs (scop
, reductions
);
2787 sbitmap_free (reductions
);
2789 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2790 Once CLooG is fixed, remove this guard. Anyways, it makes no
2791 sense to optimize a scop containing only PBBs that do not belong
2793 if (nb_pbbs_in_loops (scop
) == 0)
2796 build_sese_loop_nests (region
);
2797 build_sese_conditions (region
);
2798 find_scop_parameters (scop
);
2800 build_scop_iteration_domain (scop
);
2801 build_scop_context (scop
);
2803 add_conditions_to_constraints (scop
);
2805 build_scop_scattering (scop
);
2806 build_scop_drs (scop
);
2811 /* Always return false. Exercise the scop_to_clast function. */
2814 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2816 #ifdef ENABLE_CHECKING
2817 cloog_prog_clast pc
= scop_to_clast (scop
);
2818 cloog_clast_free (pc
.stmt
);
2819 cloog_program_free (pc
.prog
);