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;
1049 /* Returns a gimple_bb from BB. */
1051 static inline gimple_bb_p
1052 gbb_from_bb (basic_block bb
)
1054 return (gimple_bb_p
) bb
->aux
;
1057 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1058 the constraints for the surrounding loops. */
1061 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1062 ppl_Polyhedron_t outer_ph
, int nb
)
1065 ppl_Polyhedron_t ph
;
1066 tree nb_iters
= number_of_latch_executions (loop
);
1067 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1068 sese region
= SCOP_REGION (scop
);
1071 ppl_const_Constraint_System_t pcs
;
1072 ppl_dimension_type
*map
1073 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1075 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1076 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1077 ppl_Polyhedron_add_constraints (ph
, pcs
);
1079 for (i
= 0; i
< (int) nb
; i
++)
1081 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1085 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1091 ppl_Constraint_t lb
;
1092 ppl_Linear_Expression_t lb_expr
;
1094 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1095 ppl_set_coef (lb_expr
, nb
, 1);
1096 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1097 ppl_delete_Linear_Expression (lb_expr
);
1098 ppl_Polyhedron_add_constraint (ph
, lb
);
1099 ppl_delete_Constraint (lb
);
1102 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1104 ppl_Constraint_t ub
;
1105 ppl_Linear_Expression_t ub_expr
;
1107 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1109 /* loop_i <= cst_nb_iters */
1110 ppl_set_coef (ub_expr
, nb
, -1);
1111 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1112 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1113 ppl_Polyhedron_add_constraint (ph
, ub
);
1114 ppl_delete_Linear_Expression (ub_expr
);
1115 ppl_delete_Constraint (ub
);
1117 else if (!chrec_contains_undetermined (nb_iters
))
1120 ppl_Constraint_t ub
;
1121 ppl_Linear_Expression_t ub_expr
;
1124 value_set_si (one
, 1);
1125 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1126 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1127 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1130 /* loop_i <= expr_nb_iters */
1131 ppl_set_coef (ub_expr
, nb
, -1);
1132 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1133 ppl_Polyhedron_add_constraint (ph
, ub
);
1134 ppl_delete_Linear_Expression (ub_expr
);
1135 ppl_delete_Constraint (ub
);
1140 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1141 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1145 && loop_in_sese_p (loop
->next
, region
))
1146 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1148 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1149 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1151 ppl_delete_Polyhedron (ph
);
1154 /* Returns a linear expression for tree T evaluated in PBB. */
1156 static ppl_Linear_Expression_t
1157 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1160 ppl_Linear_Expression_t res
;
1161 ppl_dimension_type dim
;
1162 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1163 loop_p loop
= pbb_loop (pbb
);
1165 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1166 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1168 t
= scalar_evolution_in_region (region
, loop
, t
);
1169 gcc_assert (!automatically_generated_chrec_p (t
));
1172 value_set_si (one
, 1);
1173 scan_tree_for_params (region
, t
, res
, one
);
1179 /* Returns the ppl constraint type from the gimple tree code CODE. */
1181 static enum ppl_enum_Constraint_Type
1182 ppl_constraint_type_from_tree_code (enum tree_code code
)
1186 /* We do not support LT and GT to be able to work with C_Polyhedron.
1187 As we work on integer polyhedron "a < b" can be expressed by
1194 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1197 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1200 return PPL_CONSTRAINT_TYPE_EQUAL
;
1207 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1208 CODE is used as the comparison operator. This allows us to invert the
1209 condition or to handle inequalities. */
1212 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1213 poly_bb_p pbb
, enum tree_code code
)
1216 ppl_Coefficient_t c
;
1217 ppl_Linear_Expression_t left
, right
;
1218 ppl_Constraint_t cstr
;
1219 enum ppl_enum_Constraint_Type type
;
1221 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1222 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1224 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1225 the left or the right side of the expression. */
1226 if (code
== LT_EXPR
)
1229 value_set_si (v
, 1);
1230 ppl_new_Coefficient (&c
);
1231 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1232 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1233 ppl_delete_Coefficient (c
);
1238 else if (code
== GT_EXPR
)
1241 value_set_si (v
, 1);
1242 ppl_new_Coefficient (&c
);
1243 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1244 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1245 ppl_delete_Coefficient (c
);
1251 type
= ppl_constraint_type_from_tree_code (code
);
1253 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1255 ppl_new_Constraint (&cstr
, left
, type
);
1256 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1258 ppl_delete_Constraint (cstr
);
1259 ppl_delete_Linear_Expression (left
);
1260 ppl_delete_Linear_Expression (right
);
1263 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1264 operator. This allows us to invert the condition or to handle
1268 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1270 if (code
== NE_EXPR
)
1272 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1273 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1274 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1276 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1277 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1278 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1280 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1283 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1286 /* Add conditions to the domain of PBB. */
1289 add_conditions_to_domain (poly_bb_p pbb
)
1293 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1294 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1296 if (VEC_empty (gimple
, conditions
))
1299 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1300 switch (gimple_code (stmt
))
1304 enum tree_code code
= gimple_cond_code (stmt
);
1306 /* The conditions for ELSE-branches are inverted. */
1307 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1308 code
= invert_tree_comparison (code
, false);
1310 add_condition_to_pbb (pbb
, stmt
, code
);
1315 /* Switch statements are not supported right now - fall throught. */
1323 /* Structure used to pass data to dom_walk. */
1327 VEC (gimple
, heap
) **conditions
, **cases
;
1331 /* Returns non NULL when BB has a single predecessor and the last
1332 statement of that predecessor is a COND_EXPR. */
1335 single_pred_cond (basic_block bb
)
1337 if (single_pred_p (bb
))
1339 edge e
= single_pred_edge (bb
);
1340 basic_block pred
= e
->src
;
1341 gimple stmt
= last_stmt (pred
);
1343 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1349 /* Call-back for dom_walk executed before visiting the dominated
1353 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1356 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1357 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1358 VEC (gimple
, heap
) **cases
= data
->cases
;
1359 gimple_bb_p gbb
= gbb_from_bb (bb
);
1360 gimple stmt
= single_pred_cond (bb
);
1362 if (!bb_in_sese_p (bb
, data
->region
))
1367 edge e
= single_pred_edge (bb
);
1369 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1371 if (e
->flags
& EDGE_TRUE_VALUE
)
1372 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1374 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1379 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1380 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1384 /* Call-back for dom_walk executed after visiting the dominated
1388 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1391 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1392 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1393 VEC (gimple
, heap
) **cases
= data
->cases
;
1395 if (!bb_in_sese_p (bb
, data
->region
))
1398 if (single_pred_cond (bb
))
1400 VEC_pop (gimple
, *conditions
);
1401 VEC_pop (gimple
, *cases
);
1405 /* Record all conditions in REGION. */
1408 build_sese_conditions (sese region
)
1410 struct dom_walk_data walk_data
;
1411 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1412 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1415 data
.conditions
= &conditions
;
1416 data
.cases
= &cases
;
1417 data
.region
= region
;
1419 walk_data
.dom_direction
= CDI_DOMINATORS
;
1420 walk_data
.initialize_block_local_data
= NULL
;
1421 walk_data
.before_dom_children
= build_sese_conditions_before
;
1422 walk_data
.after_dom_children
= build_sese_conditions_after
;
1423 walk_data
.global_data
= &data
;
1424 walk_data
.block_local_data_size
= 0;
1426 init_walk_dominator_tree (&walk_data
);
1427 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1428 fini_walk_dominator_tree (&walk_data
);
1430 VEC_free (gimple
, heap
, conditions
);
1431 VEC_free (gimple
, heap
, cases
);
1434 /* Traverses all the GBBs of the SCOP and add their constraints to the
1435 iteration domains. */
1438 add_conditions_to_constraints (scop_p scop
)
1443 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1444 add_conditions_to_domain (pbb
);
1447 /* Add constraints on the possible values of parameter P from the type
1451 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1453 ppl_Constraint_t cstr
;
1454 ppl_Linear_Expression_t le
;
1455 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1456 tree type
= TREE_TYPE (parameter
);
1459 /* Disabled until we fix CPU2006. */
1462 if (!INTEGRAL_TYPE_P (type
))
1465 lb
= TYPE_MIN_VALUE (type
);
1466 ub
= TYPE_MAX_VALUE (type
);
1470 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1471 ppl_set_coef (le
, p
, -1);
1472 ppl_set_inhomogeneous_tree (le
, lb
);
1473 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1474 ppl_Polyhedron_add_constraint (context
, cstr
);
1475 ppl_delete_Linear_Expression (le
);
1476 ppl_delete_Constraint (cstr
);
1481 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1482 ppl_set_coef (le
, p
, -1);
1483 ppl_set_inhomogeneous_tree (le
, ub
);
1484 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1485 ppl_Polyhedron_add_constraint (context
, cstr
);
1486 ppl_delete_Linear_Expression (le
);
1487 ppl_delete_Constraint (cstr
);
1491 /* Build the context of the SCOP. The context usually contains extra
1492 constraints that are added to the iteration domains that constrain
1496 build_scop_context (scop_p scop
)
1498 ppl_Polyhedron_t context
;
1499 graphite_dim_t p
, n
= scop_nb_params (scop
);
1501 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1503 for (p
= 0; p
< n
; p
++)
1504 add_param_constraints (scop
, context
, p
);
1506 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1507 (&SCOP_CONTEXT (scop
), context
);
1509 ppl_delete_Polyhedron (context
);
1512 /* Build the iteration domains: the loops belonging to the current
1513 SCOP, and that vary for the execution of the current basic block.
1514 Returns false if there is no loop in SCOP. */
1517 build_scop_iteration_domain (scop_p scop
)
1520 sese region
= SCOP_REGION (scop
);
1522 ppl_Polyhedron_t ph
;
1525 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1527 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1528 if (!loop_in_sese_p (loop_outer (loop
), region
))
1529 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1531 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1532 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1533 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1534 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1535 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1537 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1538 (&PBB_DOMAIN (pbb
), ph
);
1540 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1543 ppl_delete_Pointset_Powerset_C_Polyhedron
1544 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1548 ppl_delete_Polyhedron (ph
);
1551 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1552 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1553 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1557 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1558 ppl_dimension_type accessp_nb_dims
,
1559 ppl_dimension_type dom_nb_dims
)
1561 ppl_Linear_Expression_t alias
;
1562 ppl_Constraint_t cstr
;
1563 int alias_set_num
= 0;
1565 if (dr
->aux
!= NULL
)
1566 alias_set_num
= ((int *)(dr
->aux
))[ALIAS_SET_INDEX
];
1568 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1570 ppl_set_coef (alias
, dom_nb_dims
, 1);
1571 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1572 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1573 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1575 ppl_delete_Linear_Expression (alias
);
1576 ppl_delete_Constraint (cstr
);
1579 /* Add to ACCESSES polyhedron equalities defining the access functions
1580 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1581 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1582 PBB is the poly_bb_p that contains the data reference DR. */
1585 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1586 ppl_dimension_type accessp_nb_dims
,
1587 ppl_dimension_type dom_nb_dims
,
1590 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1592 scop_p scop
= PBB_SCOP (pbb
);
1593 sese region
= SCOP_REGION (scop
);
1597 for (i
= 0; i
< nb_subscripts
; i
++)
1599 ppl_Linear_Expression_t fn
, access
;
1600 ppl_Constraint_t cstr
;
1601 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1602 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1604 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1605 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1607 value_set_si (v
, 1);
1608 scan_tree_for_params (region
, afn
, fn
, v
);
1609 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1611 ppl_set_coef (access
, subscript
, -1);
1612 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1613 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1615 ppl_delete_Linear_Expression (fn
);
1616 ppl_delete_Linear_Expression (access
);
1617 ppl_delete_Constraint (cstr
);
1623 /* Add constrains representing the size of the accessed data to the
1624 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1625 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1629 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1630 ppl_dimension_type accessp_nb_dims
,
1631 ppl_dimension_type dom_nb_dims
)
1633 tree ref
= DR_REF (dr
);
1634 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1636 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1638 ppl_Linear_Expression_t expr
;
1639 ppl_Constraint_t cstr
;
1640 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1643 if (TREE_CODE (ref
) != ARRAY_REF
)
1646 low
= array_ref_low_bound (ref
);
1648 /* subscript - low >= 0 */
1649 if (host_integerp (low
, 0))
1651 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1652 ppl_set_coef (expr
, subscript
, 1);
1654 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1656 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1657 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1658 ppl_delete_Linear_Expression (expr
);
1659 ppl_delete_Constraint (cstr
);
1662 high
= array_ref_up_bound (ref
);
1664 /* high - subscript >= 0
1665 XXX: 1-element arrays at end of structures may extend over their
1667 if (high
&& host_integerp (high
, 0))
1669 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1670 ppl_set_coef (expr
, subscript
, -1);
1672 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1674 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1675 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1676 ppl_delete_Linear_Expression (expr
);
1677 ppl_delete_Constraint (cstr
);
1682 /* Build data accesses for DR in PBB. */
1685 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1687 ppl_Polyhedron_t accesses
;
1688 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1689 ppl_dimension_type dom_nb_dims
;
1690 ppl_dimension_type accessp_nb_dims
;
1691 int dr_base_object_set
;
1693 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1695 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1697 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1699 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1700 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1701 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1703 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1705 ppl_delete_Polyhedron (accesses
);
1707 dr_base_object_set
= ((int *)(dr
->aux
))[BASE_OBJECT_SET_INDEX
];
1709 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1710 dr
, DR_NUM_DIMENSIONS (dr
));
1713 /* Write to FILE the alias graph of data references with DIMACS format. */
1716 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1717 VEC (data_reference_p
, heap
) *drs
)
1719 int num_vertex
= VEC_length (data_reference_p
, drs
);
1721 data_reference_p dr1
, dr2
;
1724 if (num_vertex
== 0)
1727 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1728 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1729 if (dr_may_alias_p (dr1
, dr2
))
1732 fprintf (file
, "$\n");
1735 fprintf (file
, "c %s\n", comment
);
1737 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1739 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1740 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1741 if (dr_may_alias_p (dr1
, dr2
))
1742 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1748 partition_drs_to_sets (VEC (data_reference_p
, heap
) *drs
, int choice
,
1749 bool (* edge_exist_p
) (const struct data_reference
*,
1750 const struct data_reference
*))
1752 int num_vertex
= VEC_length (data_reference_p
, drs
);
1753 struct graph
*g
= new_graph (num_vertex
);
1754 data_reference_p dr1
, dr2
;
1759 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1760 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1761 if ((*edge_exist_p
) (dr1
, dr2
))
1767 queue
= XNEWVEC (int, num_vertex
);
1768 for (i
= 0; i
< num_vertex
; i
++)
1771 num_component
= graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1773 for (i
= 0; i
< g
->n_vertices
; i
++)
1775 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1777 dr
->aux
= XNEWVEC (int, 2);
1778 ((int *)(dr
->aux
))[choice
] = g
->vertices
[i
].component
+ 1;
1786 dr_same_base_object_p (const struct data_reference
*dr1
,
1787 const struct data_reference
*dr2
)
1789 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1792 /* Group each data reference in DRS with it's alias set num. */
1795 build_alias_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1797 partition_drs_to_sets (drs
, ALIAS_SET_INDEX
, dr_may_alias_p
);
1800 /* Group each data reference in DRS with it's base object set num. */
1803 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1805 partition_drs_to_sets (drs
, BASE_OBJECT_SET_INDEX
, dr_same_base_object_p
);
1808 /* Build the data references for PBB. */
1811 build_pbb_drs (poly_bb_p pbb
)
1814 data_reference_p dr
;
1815 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1817 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1818 build_poly_dr (dr
, pbb
);
1821 /* Build data references in SCOP. */
1824 build_scop_drs (scop_p scop
)
1828 data_reference_p dr
;
1829 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1831 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1832 for (j
= 0; VEC_iterate (data_reference_p
,
1833 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
1834 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1836 build_alias_set_for_drs (drs
);
1837 build_base_obj_set_for_drs (drs
);
1839 /* When debugging, enable the following code. This cannot be used
1840 in production compilers. */
1846 file
= fopen ("/tmp/dr_alias_graph", "ab");
1849 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1850 current_function_name ());
1851 write_alias_graph_to_ascii_dimacs (file
, comment
, drs
);
1857 VEC_free (data_reference_p
, heap
, drs
);
1859 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1860 build_pbb_drs (pbb
);
1863 /* Return a gsi at the position of the phi node STMT. */
1865 static gimple_stmt_iterator
1866 gsi_for_phi_node (gimple stmt
)
1868 gimple_stmt_iterator psi
;
1869 basic_block bb
= gimple_bb (stmt
);
1871 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1872 if (stmt
== gsi_stmt (psi
))
1879 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
1882 insert_out_of_ssa_copy (tree res
, tree var
)
1886 gimple_stmt_iterator si
;
1887 gimple_stmt_iterator gsi
;
1889 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
1890 stmt
= gimple_build_assign (res
, var
);
1892 stmts
= gimple_seq_alloc ();
1893 si
= gsi_last (stmts
);
1894 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
1896 stmt
= SSA_NAME_DEF_STMT (var
);
1897 if (gimple_code (stmt
) == GIMPLE_PHI
)
1899 gsi
= gsi_after_labels (gimple_bb (stmt
));
1900 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1904 gsi
= gsi_for_stmt (stmt
);
1905 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1909 /* Insert on edge E the assignment "RES := EXPR". */
1912 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
1914 gimple_stmt_iterator gsi
;
1916 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1917 gimple stmt
= gimple_build_assign (res
, var
);
1920 stmts
= gimple_seq_alloc ();
1922 gsi
= gsi_last (stmts
);
1923 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1924 gsi_insert_seq_on_edge (e
, stmts
);
1925 gsi_commit_edge_inserts ();
1928 /* Creates a zero dimension array of the same type as VAR. */
1931 create_zero_dim_array (tree var
)
1933 tree index_type
= build_index_type (integer_zero_node
);
1934 tree elt_type
= TREE_TYPE (var
);
1935 tree array_type
= build_array_type (elt_type
, index_type
);
1936 tree base
= create_tmp_var (array_type
, "Red");
1938 add_referenced_var (base
);
1940 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1944 /* Returns true when PHI is a loop close phi node. */
1947 scalar_close_phi_node_p (gimple phi
)
1949 if (gimple_code (phi
) != GIMPLE_PHI
1950 || !is_gimple_reg (gimple_phi_result (phi
)))
1953 return (gimple_phi_num_args (phi
) == 1);
1956 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1957 dimension array for it. */
1960 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1962 gimple phi
= gsi_stmt (*psi
);
1963 tree res
= gimple_phi_result (phi
);
1964 tree var
= SSA_NAME_VAR (res
);
1965 tree zero_dim_array
= create_zero_dim_array (var
);
1966 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
1967 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
1968 tree arg
= gimple_phi_arg_def (phi
, 0);
1970 insert_out_of_ssa_copy (zero_dim_array
, arg
);
1972 remove_phi_node (psi
, false);
1973 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1974 SSA_NAME_DEF_STMT (res
) = stmt
;
1977 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1978 dimension array for it. */
1981 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1984 gimple phi
= gsi_stmt (*psi
);
1985 basic_block bb
= gimple_bb (phi
);
1986 tree res
= gimple_phi_result (phi
);
1987 tree var
= SSA_NAME_VAR (res
);
1988 tree zero_dim_array
= create_zero_dim_array (var
);
1989 gimple_stmt_iterator gsi
;
1993 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1995 tree arg
= gimple_phi_arg_def (phi
, i
);
1997 /* Try to avoid the insertion on edges as much as possible: this
1998 would avoid the insertion of code on loop latch edges, making
1999 the pattern matching of the vectorizer happy, or it would
2000 avoid the insertion of useless basic blocks. Note that it is
2001 incorrect to insert out of SSA copies close by their
2002 definition when they are more than two loop levels apart:
2003 for example, starting from a double nested loop
2013 the following transform is incorrect
2025 whereas inserting the copy on the incomming edge is correct
2037 if (TREE_CODE (arg
) == SSA_NAME
2038 && is_gimple_reg (arg
)
2039 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2040 && (flow_bb_inside_loop_p (bb
->loop_father
,
2041 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2042 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2043 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2044 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2046 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2047 zero_dim_array
, arg
);
2050 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2053 stmts
= gimple_seq_alloc ();
2055 stmt
= gimple_build_assign (res
, var
);
2056 remove_phi_node (psi
, false);
2057 SSA_NAME_DEF_STMT (res
) = stmt
;
2059 gsi
= gsi_last (stmts
);
2060 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2062 gsi
= gsi_after_labels (bb
);
2063 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2066 /* Return true when DEF can be analyzed in REGION by the scalar
2067 evolution analyzer. */
2070 scev_analyzable_p (tree def
, sese region
)
2072 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2073 loop_p loop
= loop_containing_stmt (stmt
);
2074 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2076 return !chrec_contains_undetermined (scev
);
2079 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2080 read from ZERO_DIM_ARRAY. */
2083 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2085 tree var
= SSA_NAME_VAR (def
);
2086 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2087 tree name
= make_ssa_name (var
, name_stmt
);
2089 use_operand_p use_p
;
2090 gimple_stmt_iterator gsi
;
2092 gimple_assign_set_lhs (name_stmt
, name
);
2094 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2096 gimple phi
= use_stmt
;
2100 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2101 if (operand_equal_p (def
, gimple_phi_arg_def (phi
, i
), 0))
2103 entry
= gimple_phi_arg_edge (phi
, i
);
2107 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
2108 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2110 gsi
= gsi_last_bb (entry
->src
);
2111 gsi_insert_after (&gsi
, name_stmt
, GSI_NEW_STMT
);
2112 SET_USE (use_p
, name
);
2118 gsi
= gsi_for_stmt (use_stmt
);
2119 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2121 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2122 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2123 replace_exp (use_p
, name
);
2126 update_stmt (use_stmt
);
2129 /* Rewrite the scalar dependences crossing the boundary of the BB
2130 containing STMT with an array. */
2133 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2135 gimple stmt
= gsi_stmt (*gsi
);
2136 imm_use_iterator imm_iter
;
2139 tree zero_dim_array
= NULL_TREE
;
2142 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2145 def
= gimple_assign_lhs (stmt
);
2146 if (!is_gimple_reg (def
)
2147 || scev_analyzable_p (def
, region
))
2150 def_bb
= gimple_bb (stmt
);
2152 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2153 if (def_bb
!= gimple_bb (use_stmt
))
2155 if (!zero_dim_array
)
2157 zero_dim_array
= create_zero_dim_array (SSA_NAME_VAR (def
));
2158 insert_out_of_ssa_copy (zero_dim_array
, def
);
2162 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2166 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2169 rewrite_reductions_out_of_ssa (scop_p scop
)
2172 gimple_stmt_iterator psi
;
2173 sese region
= SCOP_REGION (scop
);
2176 if (bb_in_sese_p (bb
, region
))
2177 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2179 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2180 rewrite_close_phi_out_of_ssa (&psi
);
2181 else if (reduction_phi_p (region
, &psi
))
2182 rewrite_phi_out_of_ssa (&psi
);
2185 update_ssa (TODO_update_ssa
);
2186 #ifdef ENABLE_CHECKING
2188 verify_loop_closed_ssa ();
2192 if (bb_in_sese_p (bb
, region
))
2193 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2194 rewrite_cross_bb_scalar_deps (region
, &psi
);
2196 update_ssa (TODO_update_ssa
);
2197 #ifdef ENABLE_CHECKING
2199 verify_loop_closed_ssa ();
2203 /* Returns the number of pbbs that are in loops contained in SCOP. */
2206 nb_pbbs_in_loops (scop_p scop
)
2212 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2213 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2219 /* Return the number of data references in BB that write in
2223 nb_data_writes_in_bb (basic_block bb
)
2226 gimple_stmt_iterator gsi
;
2228 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2229 if (gimple_vdef (gsi_stmt (gsi
)))
2235 /* Splits STMT out of its current BB. */
2238 split_reduction_stmt (gimple stmt
)
2240 gimple_stmt_iterator gsi
;
2241 basic_block bb
= gimple_bb (stmt
);
2244 /* Do not split basic blocks with no writes to memory: the reduction
2245 will be the only write to memory. */
2246 if (nb_data_writes_in_bb (bb
) == 0)
2249 split_block (bb
, stmt
);
2251 gsi
= gsi_last_bb (bb
);
2253 e
= split_block (bb
, gsi_stmt (gsi
));
2258 /* Return true when stmt is a reduction operation. */
2261 is_reduction_operation_p (gimple stmt
)
2263 return flag_associative_math
2264 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2265 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2268 /* Returns true when PHI contains an argument ARG. */
2271 phi_contains_arg (gimple phi
, tree arg
)
2275 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2276 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2282 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2285 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2289 if (TREE_CODE (arg
) != SSA_NAME
)
2292 stmt
= SSA_NAME_DEF_STMT (arg
);
2294 if (gimple_code (stmt
) == GIMPLE_PHI
)
2296 if (phi_contains_arg (stmt
, lhs
))
2301 if (gimple_num_ops (stmt
) == 2)
2302 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2304 if (is_reduction_operation_p (stmt
))
2306 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2309 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2315 /* Detect commutative and associative scalar reductions starting at
2319 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2320 VEC (gimple
, heap
) **in
,
2321 VEC (gimple
, heap
) **out
)
2323 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2327 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2328 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2335 /* Detect commutative and associative scalar reductions starting at
2339 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2340 VEC (gimple
, heap
) **out
)
2342 tree lhs
= gimple_assign_lhs (stmt
);
2344 if (gimple_num_ops (stmt
) == 2)
2345 return detect_commutative_reduction_arg (lhs
, stmt
,
2346 gimple_assign_rhs1 (stmt
),
2349 if (is_reduction_operation_p (stmt
))
2351 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2352 gimple_assign_rhs1 (stmt
),
2355 : detect_commutative_reduction_arg (lhs
, stmt
,
2356 gimple_assign_rhs2 (stmt
),
2363 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2366 follow_inital_value_to_phi (tree arg
, tree lhs
)
2370 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2373 stmt
= SSA_NAME_DEF_STMT (arg
);
2375 if (gimple_code (stmt
) == GIMPLE_PHI
2376 && phi_contains_arg (stmt
, lhs
))
2383 /* Return the argument of the loop PHI that is the inital value coming
2384 from outside the loop. */
2387 edge_initial_value_for_loop_phi (gimple phi
)
2391 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2393 edge e
= gimple_phi_arg_edge (phi
, i
);
2395 if (loop_depth (e
->src
->loop_father
)
2396 < loop_depth (e
->dest
->loop_father
))
2403 /* Return the argument of the loop PHI that is the inital value coming
2404 from outside the loop. */
2407 initial_value_for_loop_phi (gimple phi
)
2411 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2413 edge e
= gimple_phi_arg_edge (phi
, i
);
2415 if (loop_depth (e
->src
->loop_father
)
2416 < loop_depth (e
->dest
->loop_father
))
2417 return gimple_phi_arg_def (phi
, i
);
2423 /* Detect commutative and associative scalar reductions starting at
2424 the loop closed phi node CLOSE_PHI. */
2427 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2428 VEC (gimple
, heap
) **out
)
2430 if (scalar_close_phi_node_p (stmt
))
2432 tree arg
= gimple_phi_arg_def (stmt
, 0);
2433 gimple def
= SSA_NAME_DEF_STMT (arg
);
2434 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2438 tree lhs
= gimple_phi_result (stmt
);
2439 tree init
= initial_value_for_loop_phi (loop_phi
);
2440 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2442 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2443 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2450 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2451 return detect_commutative_reduction_assign (stmt
, in
, out
);
2456 /* Translate the scalar reduction statement STMT to an array RED
2457 knowing that its recursive phi node is LOOP_PHI. */
2460 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2463 basic_block bb
= gimple_bb (stmt
);
2464 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2465 tree res
= gimple_phi_result (loop_phi
);
2466 gimple assign
= gimple_build_assign (res
, red
);
2468 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2470 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2471 insert_gsi
= gsi_for_stmt (stmt
);
2472 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2475 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2478 insert_copyout (tree red
, gimple close_phi
)
2480 tree res
= gimple_phi_result (close_phi
);
2481 basic_block bb
= gimple_bb (close_phi
);
2482 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2483 gimple assign
= gimple_build_assign (res
, red
);
2485 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2488 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2491 insert_copyin (tree red
, gimple loop_phi
)
2494 tree init
= initial_value_for_loop_phi (loop_phi
);
2495 edge e
= edge_initial_value_for_loop_phi (loop_phi
);
2496 basic_block bb
= e
->src
;
2497 gimple_stmt_iterator insert_gsi
= gsi_last_bb (bb
);
2498 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2500 force_gimple_operand (expr
, &stmts
, true, NULL
);
2501 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2504 /* Rewrite out of SSA the reduction described by the loop phi nodes
2505 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2508 IN: stmt, loop_n, ..., loop_0
2509 OUT: stmt, close_n, ..., close_0
2511 the first element is the reduction statement, and the next elements
2512 are the loop and close phi nodes of each of the outer loops. */
2515 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2516 VEC (gimple
, heap
) *out
,
2522 gimple_stmt_iterator gsi
;
2524 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2526 gimple close_phi
= VEC_index (gimple
, out
, i
);
2530 gimple stmt
= loop_phi
;
2531 basic_block bb
= split_reduction_stmt (stmt
);
2533 SET_BIT (reductions
, bb
->index
);
2534 gcc_assert (close_phi
== loop_phi
);
2536 red
= create_zero_dim_array (gimple_assign_lhs (stmt
));
2537 translate_scalar_reduction_to_array_for_stmt
2538 (red
, stmt
, VEC_index (gimple
, in
, 1));
2542 if (i
== VEC_length (gimple
, in
) - 1)
2544 insert_copyout (red
, close_phi
);
2545 insert_copyin (red
, loop_phi
);
2548 gsi
= gsi_for_phi_node (loop_phi
);
2549 remove_phi_node (&gsi
, false);
2551 gsi
= gsi_for_phi_node (close_phi
);
2552 remove_phi_node (&gsi
, false);
2556 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2559 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2562 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2563 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2565 detect_commutative_reduction (close_phi
, &in
, &out
);
2566 if (VEC_length (gimple
, in
) > 0)
2567 translate_scalar_reduction_to_array (in
, out
, reductions
);
2569 VEC_free (gimple
, heap
, in
);
2570 VEC_free (gimple
, heap
, out
);
2573 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2576 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2579 gimple_stmt_iterator gsi
;
2580 edge exit
= single_exit (loop
);
2585 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2586 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2590 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2593 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2598 FOR_EACH_LOOP (li
, loop
, 0)
2599 if (loop_in_sese_p (loop
, region
))
2600 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2603 /* Builds the polyhedral representation for a SESE region. */
2606 build_poly_scop (scop_p scop
)
2608 sese region
= SCOP_REGION (scop
);
2609 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2611 sbitmap_zero (reductions
);
2612 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2613 rewrite_reductions_out_of_ssa (scop
);
2614 build_scop_bbs (scop
, reductions
);
2615 sbitmap_free (reductions
);
2617 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2618 Once CLooG is fixed, remove this guard. Anyways, it makes no
2619 sense to optimize a scop containing only PBBs that do not belong
2621 if (nb_pbbs_in_loops (scop
) == 0)
2624 build_sese_loop_nests (region
);
2625 build_sese_conditions (region
);
2626 find_scop_parameters (scop
);
2628 build_scop_iteration_domain (scop
);
2629 build_scop_context (scop
);
2631 add_conditions_to_constraints (scop
);
2633 build_scop_scattering (scop
);
2634 build_scop_drs (scop
);
2639 /* Always return false. Exercise the scop_to_clast function. */
2642 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2644 #ifdef ENABLE_CHECKING
2645 cloog_prog_clast pc
= scop_to_clast (scop
);
2646 cloog_clast_free (pc
.stmt
);
2647 cloog_program_free (pc
.prog
);