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))
200 scev
= scalar_evolution_in_region (region
, loop
, res
);
201 if (chrec_contains_undetermined (scev
))
204 if (evolution_function_is_invariant_p (scev
, loop
->num
))
206 remove_invariant_phi (region
, psi
);
210 /* All the other cases are considered reductions. */
214 /* Returns true when BB will be represented in graphite. Return false
215 for the basic blocks that contain code eliminated in the code
216 generation pass: i.e. induction variables and exit conditions. */
219 graphite_stmt_p (sese region
, basic_block bb
,
220 VEC (data_reference_p
, heap
) *drs
)
222 gimple_stmt_iterator gsi
;
223 loop_p loop
= bb
->loop_father
;
225 if (VEC_length (data_reference_p
, drs
) > 0)
228 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
230 gimple stmt
= gsi_stmt (gsi
);
232 switch (gimple_code (stmt
))
235 /* Control flow expressions can be ignored, as they are
236 represented in the iteration domains and will be
237 regenerated by graphite. */
245 tree var
= gimple_assign_lhs (stmt
);
247 /* We need these bbs to be able to construct the phi nodes. */
248 if (var_used_in_not_loop_header_phi_node (var
))
251 var
= scalar_evolution_in_region (region
, loop
, var
);
252 if (chrec_contains_undetermined (var
))
266 /* Store the GRAPHITE representation of BB. */
269 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
271 struct gimple_bb
*gbb
;
273 gbb
= XNEW (struct gimple_bb
);
276 GBB_DATA_REFS (gbb
) = drs
;
277 GBB_CONDITIONS (gbb
) = NULL
;
278 GBB_CONDITION_CASES (gbb
) = NULL
;
279 GBB_CLOOG_IV_TYPES (gbb
) = NULL
;
285 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
288 struct data_reference
*dr
;
290 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
301 free_gimple_bb (struct gimple_bb
*gbb
)
303 if (GBB_CLOOG_IV_TYPES (gbb
))
304 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
306 free_data_refs_aux (GBB_DATA_REFS (gbb
));
307 free_data_refs (GBB_DATA_REFS (gbb
));
309 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
310 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
311 GBB_BB (gbb
)->aux
= 0;
315 /* Deletes all gimple bbs in SCOP. */
318 remove_gbbs_in_scop (scop_p scop
)
323 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
324 free_gimple_bb (PBB_BLACK_BOX (pbb
));
327 /* Deletes all scops in SCOPS. */
330 free_scops (VEC (scop_p
, heap
) *scops
)
335 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
337 remove_gbbs_in_scop (scop
);
338 free_sese (SCOP_REGION (scop
));
342 VEC_free (scop_p
, heap
, scops
);
345 /* Generates a polyhedral black box only if the bb contains interesting
349 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
351 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
352 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
353 gimple_stmt_iterator gsi
;
355 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
357 gimple stmt
= gsi_stmt (gsi
);
358 if (!is_gimple_debug (stmt
))
359 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
362 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
363 free_data_refs (drs
);
365 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
369 /* Returns true if all predecessors of BB, that are not dominated by BB, are
370 marked in MAP. The predecessors dominated by BB are loop latches and will
371 be handled after BB. */
374 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
379 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
380 if (!TEST_BIT (map
, e
->src
->index
)
381 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
387 /* Compare the depth of two basic_block's P1 and P2. */
390 compare_bb_depths (const void *p1
, const void *p2
)
392 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
393 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
394 int d1
= loop_depth (bb1
->loop_father
);
395 int d2
= loop_depth (bb2
->loop_father
);
406 /* Sort the basic blocks from DOM such that the first are the ones at
407 a deepest loop level. */
410 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
412 size_t len
= VEC_length (basic_block
, dom
);
414 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
418 /* Recursive helper function for build_scops_bbs. */
421 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
423 sese region
= SCOP_REGION (scop
);
424 VEC (basic_block
, heap
) *dom
;
426 if (TEST_BIT (visited
, bb
->index
)
427 || !bb_in_sese_p (bb
, region
))
430 try_generate_gimple_bb (scop
, bb
, reductions
);
431 SET_BIT (visited
, bb
->index
);
433 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
438 graphite_sort_dominated_info (dom
);
440 while (!VEC_empty (basic_block
, dom
))
445 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
446 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
448 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
449 VEC_unordered_remove (basic_block
, dom
, i
);
454 VEC_free (basic_block
, heap
, dom
);
457 /* Gather the basic blocks belonging to the SCOP. */
460 build_scop_bbs (scop_p scop
, sbitmap reductions
)
462 sbitmap visited
= sbitmap_alloc (last_basic_block
);
463 sese region
= SCOP_REGION (scop
);
465 sbitmap_zero (visited
);
466 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
467 sbitmap_free (visited
);
470 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
471 We generate SCATTERING_DIMENSIONS scattering dimensions.
473 CLooG 0.15.0 and previous versions require, that all
474 scattering functions of one CloogProgram have the same number of
475 scattering dimensions, therefore we allow to specify it. This
476 should be removed in future versions of CLooG.
478 The scattering polyhedron consists of these dimensions: scattering,
479 loop_iterators, parameters.
483 | scattering_dimensions = 5
484 | used_scattering_dimensions = 3
492 | Scattering polyhedron:
494 | scattering: {s1, s2, s3, s4, s5}
495 | loop_iterators: {i}
496 | parameters: {p1, p2}
498 | s1 s2 s3 s4 s5 i p1 p2 1
499 | 1 0 0 0 0 0 0 0 -4 = 0
500 | 0 1 0 0 0 -1 0 0 0 = 0
501 | 0 0 1 0 0 0 0 0 -5 = 0 */
504 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
505 poly_bb_p pbb
, int scattering_dimensions
)
508 scop_p scop
= PBB_SCOP (pbb
);
509 int nb_iterators
= pbb_dim_iter_domain (pbb
);
510 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
511 int nb_params
= scop_nb_params (scop
);
513 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
516 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
519 ppl_new_Coefficient (&c
);
520 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
521 ppl_new_C_Polyhedron_from_space_dimension
522 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
524 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
526 for (i
= 0; i
< scattering_dimensions
; i
++)
528 ppl_Constraint_t cstr
;
529 ppl_Linear_Expression_t expr
;
531 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
533 ppl_assign_Coefficient_from_mpz_t (c
, v
);
534 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
536 /* Textual order inside this loop. */
539 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
540 ppl_Coefficient_to_mpz_t (c
, v
);
542 ppl_assign_Coefficient_from_mpz_t (c
, v
);
543 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
546 /* Iterations of this loop. */
547 else /* if ((i % 2) == 1) */
549 int loop
= (i
- 1) / 2;
551 value_set_si (v
, -1);
552 ppl_assign_Coefficient_from_mpz_t (c
, v
);
553 ppl_Linear_Expression_add_to_coefficient
554 (expr
, scattering_dimensions
+ loop
, c
);
557 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
558 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
559 ppl_delete_Linear_Expression (expr
);
560 ppl_delete_Constraint (cstr
);
564 ppl_delete_Coefficient (c
);
566 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
569 /* Build for BB the static schedule.
571 The static schedule is a Dewey numbering of the abstract syntax
572 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
574 The following example informally defines the static schedule:
593 Static schedules for A to F:
606 build_scop_scattering (scop_p scop
)
610 gimple_bb_p previous_gbb
= NULL
;
611 ppl_Linear_Expression_t static_schedule
;
616 ppl_new_Coefficient (&c
);
617 ppl_new_Linear_Expression (&static_schedule
);
619 /* We have to start schedules at 0 on the first component and
620 because we cannot compare_prefix_loops against a previous loop,
621 prefix will be equal to zero, and that index will be
622 incremented before copying. */
623 value_set_si (v
, -1);
624 ppl_assign_Coefficient_from_mpz_t (c
, v
);
625 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
627 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
629 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
630 ppl_Linear_Expression_t common
;
632 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
635 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
640 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
641 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
645 ppl_assign_Coefficient_from_mpz_t (c
, v
);
646 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
647 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
650 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
652 ppl_delete_Linear_Expression (common
);
656 ppl_delete_Coefficient (c
);
657 ppl_delete_Linear_Expression (static_schedule
);
660 /* Add the value K to the dimension D of the linear expression EXPR. */
663 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
667 ppl_Coefficient_t coef
;
669 ppl_new_Coefficient (&coef
);
670 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
672 ppl_Coefficient_to_mpz_t (coef
, val
);
674 value_addto (val
, val
, k
);
676 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
677 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
679 ppl_delete_Coefficient (coef
);
682 /* In the context of scop S, scan E, the right hand side of a scalar
683 evolution function in loop VAR, and translate it to a linear
687 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
688 ppl_Linear_Expression_t expr
)
692 loop_p loop
= get_loop (var
);
693 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
696 /* Scalar evolutions should happen in the sese region. */
697 gcc_assert (sese_loop_depth (s
, loop
) > 0);
699 /* We can not deal with parametric strides like:
705 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
708 value_set_si (val
, int_cst_value (e
));
709 add_value_to_dim (l
, expr
, val
);
714 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
715 linear expression EXPR. K is the multiplier of the constant. */
718 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
721 ppl_Coefficient_t coef
;
722 int v
= int_cst_value (cst
);
725 value_set_si (val
, 0);
727 /* Necessary to not get "-1 = 2^n - 1". */
729 value_sub_int (val
, val
, -v
);
731 value_add_int (val
, val
, v
);
733 value_multiply (val
, val
, k
);
734 ppl_new_Coefficient (&coef
);
735 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
736 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
738 ppl_delete_Coefficient (coef
);
741 /* Saves in NV at index I a new name for variable P. */
744 save_var_name (char **nv
, int i
, tree p
)
746 const char *name
= get_name (SSA_NAME_VAR (p
));
750 int len
= strlen (name
) + 16;
751 nv
[i
] = XNEWVEC (char, len
);
752 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
756 nv
[i
] = XNEWVEC (char, 16);
757 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
761 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
762 Otherwise returns -1. */
765 parameter_index_in_region_1 (tree name
, sese region
)
770 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
772 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
779 /* When the parameter NAME is in REGION, returns its index in
780 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
781 and returns the index of NAME. */
784 parameter_index_in_region (tree name
, sese region
)
788 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
790 i
= parameter_index_in_region_1 (name
, region
);
794 gcc_assert (SESE_ADD_PARAMS (region
));
796 i
= VEC_length (tree
, SESE_PARAMS (region
));
797 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
798 save_clast_name_index (SESE_PARAMS_INDEX (region
),
799 SESE_PARAMS_NAMES (region
)[i
], i
);
800 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
804 /* In the context of sese S, scan the expression E and translate it to
805 a linear expression C. When parsing a symbolic multiplication, K
806 represents the constant multiplier of an expression containing
810 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
813 if (e
== chrec_dont_know
)
816 switch (TREE_CODE (e
))
818 case POLYNOMIAL_CHREC
:
819 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
820 CHREC_VARIABLE (e
), c
);
821 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
825 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
830 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
832 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
833 value_multiply (val
, val
, k
);
834 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
838 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
845 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
847 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
848 value_multiply (val
, val
, k
);
849 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
853 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
858 case POINTER_PLUS_EXPR
:
859 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
860 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
865 ppl_Linear_Expression_t tmp_expr
= NULL
;
869 ppl_dimension_type dim
;
870 ppl_Linear_Expression_space_dimension (c
, &dim
);
871 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
874 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
875 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
879 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
881 ppl_delete_Linear_Expression (tmp_expr
);
889 ppl_Linear_Expression_t tmp_expr
= NULL
;
893 ppl_dimension_type dim
;
894 ppl_Linear_Expression_space_dimension (c
, &dim
);
895 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
898 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
902 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
904 ppl_delete_Linear_Expression (tmp_expr
);
912 ppl_Linear_Expression_t tmp_expr
= NULL
;
916 ppl_dimension_type dim
;
917 ppl_Linear_Expression_space_dimension (c
, &dim
);
918 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
921 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
925 ppl_Coefficient_t coef
;
928 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
930 ppl_delete_Linear_Expression (tmp_expr
);
931 value_init (minus_one
);
932 value_set_si (minus_one
, -1);
933 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
934 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
935 value_clear (minus_one
);
936 ppl_delete_Coefficient (coef
);
944 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
948 ppl_dimension_type dim
;
949 ppl_Linear_Expression_space_dimension (c
, &dim
);
950 p
+= dim
- sese_nb_params (s
);
951 add_value_to_dim (p
, c
, k
);
958 scan_tree_for_params_int (e
, c
, k
);
962 case NON_LVALUE_EXPR
:
963 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
972 /* Find parameters with respect to REGION in BB. We are looking in memory
973 access functions, conditions and loop bounds. */
976 find_params_in_bb (sese region
, gimple_bb_p gbb
)
982 loop_p loop
= GBB_BB (gbb
)->loop_father
;
986 value_set_si (one
, 1);
988 /* Find parameters in the access functions of data references. */
989 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
990 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
991 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
993 /* Find parameters in conditional statements. */
994 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
996 tree lhs
= scalar_evolution_in_region (region
, loop
,
997 gimple_cond_lhs (stmt
));
998 tree rhs
= scalar_evolution_in_region (region
, loop
,
999 gimple_cond_rhs (stmt
));
1001 scan_tree_for_params (region
, lhs
, NULL
, one
);
1002 scan_tree_for_params (region
, rhs
, NULL
, one
);
1008 /* Record the parameters used in the SCOP. A variable is a parameter
1009 in a scop if it does not vary during the execution of that scop. */
1012 find_scop_parameters (scop_p scop
)
1016 sese region
= SCOP_REGION (scop
);
1021 value_set_si (one
, 1);
1023 /* Find the parameters used in the loop bounds. */
1024 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1026 tree nb_iters
= number_of_latch_executions (loop
);
1028 if (!chrec_contains_symbols (nb_iters
))
1031 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1032 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1037 /* Find the parameters used in data accesses. */
1038 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1039 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1041 scop_set_nb_params (scop
, sese_nb_params (region
));
1042 SESE_ADD_PARAMS (region
) = false;
1045 /* Returns a gimple_bb from BB. */
1047 static inline gimple_bb_p
1048 gbb_from_bb (basic_block bb
)
1050 return (gimple_bb_p
) bb
->aux
;
1053 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1054 the constraints for the surrounding loops. */
1057 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1058 ppl_Polyhedron_t outer_ph
, int nb
)
1062 ppl_Polyhedron_t ph
;
1063 tree nb_iters
= number_of_latch_executions (loop
);
1064 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1065 sese region
= SCOP_REGION (scop
);
1068 ppl_const_Constraint_System_t pcs
;
1069 ppl_dimension_type
*map
1070 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1072 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1073 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1074 ppl_Polyhedron_add_constraints (ph
, pcs
);
1076 for (i
= 0; i
< (int) nb
; i
++)
1078 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1082 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1088 ppl_Constraint_t lb
;
1089 ppl_Linear_Expression_t lb_expr
;
1091 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1092 ppl_set_coef (lb_expr
, nb
, 1);
1093 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1094 ppl_delete_Linear_Expression (lb_expr
);
1095 ppl_Polyhedron_add_constraint (ph
, lb
);
1096 ppl_delete_Constraint (lb
);
1099 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1101 ppl_Constraint_t ub
;
1102 ppl_Linear_Expression_t ub_expr
;
1104 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1106 /* loop_i <= cst_nb_iters */
1107 ppl_set_coef (ub_expr
, nb
, -1);
1108 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1109 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1110 ppl_Polyhedron_add_constraint (ph
, ub
);
1111 ppl_delete_Linear_Expression (ub_expr
);
1112 ppl_delete_Constraint (ub
);
1114 else if (!chrec_contains_undetermined (nb_iters
))
1117 ppl_Constraint_t ub
;
1118 ppl_Linear_Expression_t ub_expr
;
1121 value_set_si (one
, 1);
1122 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1123 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1124 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1127 /* loop_i <= expr_nb_iters */
1128 ppl_set_coef (ub_expr
, nb
, -1);
1129 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1130 ppl_Polyhedron_add_constraint (ph
, ub
);
1131 ppl_delete_Linear_Expression (ub_expr
);
1132 ppl_delete_Constraint (ub
);
1137 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1138 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1142 && loop_in_sese_p (loop
->next
, region
))
1143 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1145 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1146 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1148 ppl_delete_Polyhedron (ph
);
1151 /* Returns a linear expression for tree T evaluated in PBB. */
1153 static ppl_Linear_Expression_t
1154 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1157 ppl_Linear_Expression_t res
;
1158 ppl_dimension_type dim
;
1159 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1160 loop_p loop
= pbb_loop (pbb
);
1162 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1163 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1165 t
= scalar_evolution_in_region (region
, loop
, t
);
1166 gcc_assert (!automatically_generated_chrec_p (t
));
1169 value_set_si (one
, 1);
1170 scan_tree_for_params (region
, t
, res
, one
);
1176 /* Returns the ppl constraint type from the gimple tree code CODE. */
1178 static enum ppl_enum_Constraint_Type
1179 ppl_constraint_type_from_tree_code (enum tree_code code
)
1183 /* We do not support LT and GT to be able to work with C_Polyhedron.
1184 As we work on integer polyhedron "a < b" can be expressed by
1191 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1194 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1197 return PPL_CONSTRAINT_TYPE_EQUAL
;
1204 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1205 CODE is used as the comparison operator. This allows us to invert the
1206 condition or to handle inequalities. */
1209 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1210 poly_bb_p pbb
, enum tree_code code
)
1213 ppl_Coefficient_t c
;
1214 ppl_Linear_Expression_t left
, right
;
1215 ppl_Constraint_t cstr
;
1216 enum ppl_enum_Constraint_Type type
;
1218 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1219 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1221 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1222 the left or the right side of the expression. */
1223 if (code
== LT_EXPR
)
1226 value_set_si (v
, 1);
1227 ppl_new_Coefficient (&c
);
1228 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1229 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1230 ppl_delete_Coefficient (c
);
1235 else if (code
== GT_EXPR
)
1238 value_set_si (v
, 1);
1239 ppl_new_Coefficient (&c
);
1240 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1241 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1242 ppl_delete_Coefficient (c
);
1248 type
= ppl_constraint_type_from_tree_code (code
);
1250 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1252 ppl_new_Constraint (&cstr
, left
, type
);
1253 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1255 ppl_delete_Constraint (cstr
);
1256 ppl_delete_Linear_Expression (left
);
1257 ppl_delete_Linear_Expression (right
);
1260 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1261 operator. This allows us to invert the condition or to handle
1265 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1267 if (code
== NE_EXPR
)
1269 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1270 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1271 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1273 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1274 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1275 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1277 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1280 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1283 /* Add conditions to the domain of PBB. */
1286 add_conditions_to_domain (poly_bb_p pbb
)
1290 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1291 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1293 if (VEC_empty (gimple
, conditions
))
1296 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1297 switch (gimple_code (stmt
))
1301 enum tree_code code
= gimple_cond_code (stmt
);
1303 /* The conditions for ELSE-branches are inverted. */
1304 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1305 code
= invert_tree_comparison (code
, false);
1307 add_condition_to_pbb (pbb
, stmt
, code
);
1312 /* Switch statements are not supported right now - fall throught. */
1320 /* Structure used to pass data to dom_walk. */
1324 VEC (gimple
, heap
) **conditions
, **cases
;
1328 /* Returns non NULL when BB has a single predecessor and the last
1329 statement of that predecessor is a COND_EXPR. */
1332 single_pred_cond (basic_block bb
)
1334 if (single_pred_p (bb
))
1336 edge e
= single_pred_edge (bb
);
1337 basic_block pred
= e
->src
;
1338 gimple stmt
= last_stmt (pred
);
1340 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1346 /* Call-back for dom_walk executed before visiting the dominated
1350 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1353 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1354 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1355 VEC (gimple
, heap
) **cases
= data
->cases
;
1356 gimple_bb_p gbb
= gbb_from_bb (bb
);
1357 gimple stmt
= single_pred_cond (bb
);
1359 if (!bb_in_sese_p (bb
, data
->region
))
1364 edge e
= single_pred_edge (bb
);
1366 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1368 if (e
->flags
& EDGE_TRUE_VALUE
)
1369 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1371 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1376 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1377 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1381 /* Call-back for dom_walk executed after visiting the dominated
1385 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1388 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1389 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1390 VEC (gimple
, heap
) **cases
= data
->cases
;
1392 if (!bb_in_sese_p (bb
, data
->region
))
1395 if (single_pred_cond (bb
))
1397 VEC_pop (gimple
, *conditions
);
1398 VEC_pop (gimple
, *cases
);
1402 /* Record all conditions in REGION. */
1405 build_sese_conditions (sese region
)
1407 struct dom_walk_data walk_data
;
1408 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1409 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1412 data
.conditions
= &conditions
;
1413 data
.cases
= &cases
;
1414 data
.region
= region
;
1416 walk_data
.dom_direction
= CDI_DOMINATORS
;
1417 walk_data
.initialize_block_local_data
= NULL
;
1418 walk_data
.before_dom_children
= build_sese_conditions_before
;
1419 walk_data
.after_dom_children
= build_sese_conditions_after
;
1420 walk_data
.global_data
= &data
;
1421 walk_data
.block_local_data_size
= 0;
1423 init_walk_dominator_tree (&walk_data
);
1424 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1425 fini_walk_dominator_tree (&walk_data
);
1427 VEC_free (gimple
, heap
, conditions
);
1428 VEC_free (gimple
, heap
, cases
);
1431 /* Traverses all the GBBs of the SCOP and add their constraints to the
1432 iteration domains. */
1435 add_conditions_to_constraints (scop_p scop
)
1440 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1441 add_conditions_to_domain (pbb
);
1444 /* Add constraints on the possible values of parameter P from the type
1448 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1450 ppl_Constraint_t cstr
;
1451 ppl_Linear_Expression_t le
;
1452 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1453 tree type
= TREE_TYPE (parameter
);
1456 /* Disabled until we fix CPU2006. */
1459 if (!INTEGRAL_TYPE_P (type
))
1462 lb
= TYPE_MIN_VALUE (type
);
1463 ub
= TYPE_MAX_VALUE (type
);
1467 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1468 ppl_set_coef (le
, p
, -1);
1469 ppl_set_inhomogeneous_tree (le
, lb
);
1470 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1471 ppl_Polyhedron_add_constraint (context
, cstr
);
1472 ppl_delete_Linear_Expression (le
);
1473 ppl_delete_Constraint (cstr
);
1478 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1479 ppl_set_coef (le
, p
, -1);
1480 ppl_set_inhomogeneous_tree (le
, ub
);
1481 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1482 ppl_Polyhedron_add_constraint (context
, cstr
);
1483 ppl_delete_Linear_Expression (le
);
1484 ppl_delete_Constraint (cstr
);
1488 /* Build the context of the SCOP. The context usually contains extra
1489 constraints that are added to the iteration domains that constrain
1493 build_scop_context (scop_p scop
)
1495 ppl_Polyhedron_t context
;
1496 graphite_dim_t p
, n
= scop_nb_params (scop
);
1498 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1500 for (p
= 0; p
< n
; p
++)
1501 add_param_constraints (scop
, context
, p
);
1503 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1504 (&SCOP_CONTEXT (scop
), context
);
1506 ppl_delete_Polyhedron (context
);
1509 /* Build the iteration domains: the loops belonging to the current
1510 SCOP, and that vary for the execution of the current basic block.
1511 Returns false if there is no loop in SCOP. */
1514 build_scop_iteration_domain (scop_p scop
)
1517 sese region
= SCOP_REGION (scop
);
1519 ppl_Polyhedron_t ph
;
1522 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1524 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1525 if (!loop_in_sese_p (loop_outer (loop
), region
))
1526 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1528 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1529 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1530 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1531 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1532 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1534 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1535 (&PBB_DOMAIN (pbb
), ph
);
1537 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1540 ppl_delete_Pointset_Powerset_C_Polyhedron
1541 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1545 ppl_delete_Polyhedron (ph
);
1548 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1549 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1550 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1554 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1555 ppl_dimension_type accessp_nb_dims
,
1556 ppl_dimension_type dom_nb_dims
)
1558 ppl_Linear_Expression_t alias
;
1559 ppl_Constraint_t cstr
;
1560 int alias_set_num
= 0;
1562 if (dr
->aux
!= NULL
)
1563 alias_set_num
= ((int *)(dr
->aux
))[ALIAS_SET_INDEX
];
1565 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1567 ppl_set_coef (alias
, dom_nb_dims
, 1);
1568 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1569 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1570 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1572 ppl_delete_Linear_Expression (alias
);
1573 ppl_delete_Constraint (cstr
);
1576 /* Add to ACCESSES polyhedron equalities defining the access functions
1577 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1578 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1579 PBB is the poly_bb_p that contains the data reference DR. */
1582 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1583 ppl_dimension_type accessp_nb_dims
,
1584 ppl_dimension_type dom_nb_dims
,
1587 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1589 scop_p scop
= PBB_SCOP (pbb
);
1590 sese region
= SCOP_REGION (scop
);
1594 for (i
= 0; i
< nb_subscripts
; i
++)
1596 ppl_Linear_Expression_t fn
, access
;
1597 ppl_Constraint_t cstr
;
1598 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1599 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1601 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1602 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1604 value_set_si (v
, 1);
1605 scan_tree_for_params (region
, afn
, fn
, v
);
1606 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1608 ppl_set_coef (access
, subscript
, -1);
1609 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1610 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1612 ppl_delete_Linear_Expression (fn
);
1613 ppl_delete_Linear_Expression (access
);
1614 ppl_delete_Constraint (cstr
);
1620 /* Add constrains representing the size of the accessed data to the
1621 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1622 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1626 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1627 ppl_dimension_type accessp_nb_dims
,
1628 ppl_dimension_type dom_nb_dims
)
1630 tree ref
= DR_REF (dr
);
1631 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1633 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1635 ppl_Linear_Expression_t expr
;
1636 ppl_Constraint_t cstr
;
1637 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1640 if (TREE_CODE (ref
) != ARRAY_REF
)
1643 low
= array_ref_low_bound (ref
);
1645 /* subscript - low >= 0 */
1646 if (host_integerp (low
, 0))
1648 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1649 ppl_set_coef (expr
, subscript
, 1);
1651 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1653 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1654 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1655 ppl_delete_Linear_Expression (expr
);
1656 ppl_delete_Constraint (cstr
);
1659 high
= array_ref_up_bound (ref
);
1661 /* high - subscript >= 0
1662 XXX: 1-element arrays at end of structures may extend over their
1664 if (high
&& host_integerp (high
, 0))
1666 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1667 ppl_set_coef (expr
, subscript
, -1);
1669 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1671 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1672 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1673 ppl_delete_Linear_Expression (expr
);
1674 ppl_delete_Constraint (cstr
);
1679 /* Build data accesses for DR in PBB. */
1682 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1684 ppl_Polyhedron_t accesses
;
1685 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1686 ppl_dimension_type dom_nb_dims
;
1687 ppl_dimension_type accessp_nb_dims
;
1688 int dr_base_object_set
;
1690 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1692 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1694 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1696 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1697 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1698 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1700 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1702 ppl_delete_Polyhedron (accesses
);
1704 dr_base_object_set
= ((int *)(dr
->aux
))[BASE_OBJECT_SET_INDEX
];
1706 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1707 dr
, DR_NUM_DIMENSIONS (dr
));
1710 /* Write to FILE the alias graph of data references with DIMACS format. */
1713 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1714 VEC (data_reference_p
, heap
) *drs
)
1716 int num_vertex
= VEC_length (data_reference_p
, drs
);
1718 data_reference_p dr1
, dr2
;
1721 if (num_vertex
== 0)
1724 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1725 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1726 if (dr_may_alias_p (dr1
, dr2
))
1729 fprintf (file
, "$\n");
1732 fprintf (file
, "c %s\n", comment
);
1734 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1736 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1737 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1738 if (dr_may_alias_p (dr1
, dr2
))
1739 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1745 partition_drs_to_sets (VEC (data_reference_p
, heap
) *drs
, int choice
,
1746 bool (* edge_exist_p
) (const struct data_reference
*,
1747 const struct data_reference
*))
1749 int num_vertex
= VEC_length (data_reference_p
, drs
);
1750 struct graph
*g
= new_graph (num_vertex
);
1751 data_reference_p dr1
, dr2
;
1756 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1757 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1758 if ((*edge_exist_p
) (dr1
, dr2
))
1764 queue
= XNEWVEC (int, num_vertex
);
1765 for (i
= 0; i
< num_vertex
; i
++)
1768 num_component
= graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1770 for (i
= 0; i
< g
->n_vertices
; i
++)
1772 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1774 dr
->aux
= XNEWVEC (int, 2);
1775 ((int *)(dr
->aux
))[choice
] = g
->vertices
[i
].component
+ 1;
1783 dr_same_base_object_p (const struct data_reference
*dr1
,
1784 const struct data_reference
*dr2
)
1786 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1789 /* Group each data reference in DRS with it's alias set num. */
1792 build_alias_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1794 partition_drs_to_sets (drs
, ALIAS_SET_INDEX
, dr_may_alias_p
);
1797 /* Group each data reference in DRS with it's base object set num. */
1800 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1802 partition_drs_to_sets (drs
, BASE_OBJECT_SET_INDEX
, dr_same_base_object_p
);
1805 /* Build the data references for PBB. */
1808 build_pbb_drs (poly_bb_p pbb
)
1811 data_reference_p dr
;
1812 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1814 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1815 build_poly_dr (dr
, pbb
);
1818 /* Build data references in SCOP. */
1821 build_scop_drs (scop_p scop
)
1825 data_reference_p dr
;
1826 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1828 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1829 for (j
= 0; VEC_iterate (data_reference_p
,
1830 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
1831 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1833 build_alias_set_for_drs (drs
);
1834 build_base_obj_set_for_drs (drs
);
1836 /* When debugging, enable the following code. This cannot be used
1837 in production compilers. */
1843 file
= fopen ("/tmp/dr_alias_graph", "ab");
1846 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1847 current_function_name ());
1848 write_alias_graph_to_ascii_dimacs (file
, comment
, drs
);
1854 VEC_free (data_reference_p
, heap
, drs
);
1856 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1857 build_pbb_drs (pbb
);
1860 /* Return a gsi at the position of the phi node STMT. */
1862 static gimple_stmt_iterator
1863 gsi_for_phi_node (gimple stmt
)
1865 gimple_stmt_iterator psi
;
1866 basic_block bb
= gimple_bb (stmt
);
1868 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1869 if (stmt
== gsi_stmt (psi
))
1876 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
1879 insert_out_of_ssa_copy (tree res
, tree var
)
1883 gimple_stmt_iterator si
;
1884 gimple_stmt_iterator gsi
;
1886 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
1887 stmt
= gimple_build_assign (res
, var
);
1889 stmts
= gimple_seq_alloc ();
1890 si
= gsi_last (stmts
);
1891 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
1893 stmt
= SSA_NAME_DEF_STMT (var
);
1894 if (gimple_code (stmt
) == GIMPLE_PHI
)
1896 gsi
= gsi_after_labels (gimple_bb (stmt
));
1897 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1901 gsi
= gsi_for_stmt (stmt
);
1902 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1906 /* Insert on edge E the assignment "RES := EXPR". */
1909 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
1911 gimple_stmt_iterator gsi
;
1913 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1914 gimple stmt
= gimple_build_assign (res
, var
);
1917 stmts
= gimple_seq_alloc ();
1919 gsi
= gsi_last (stmts
);
1920 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1921 gsi_insert_seq_on_edge (e
, stmts
);
1922 gsi_commit_edge_inserts ();
1925 /* Creates a zero dimension array of the same type as VAR. */
1928 create_zero_dim_array (tree var
)
1930 tree index_type
= build_index_type (integer_zero_node
);
1931 tree elt_type
= TREE_TYPE (var
);
1932 tree array_type
= build_array_type (elt_type
, index_type
);
1933 tree base
= create_tmp_var (array_type
, "Red");
1935 add_referenced_var (base
);
1937 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1941 /* Returns true when PHI is a loop close phi node. */
1944 scalar_close_phi_node_p (gimple phi
)
1946 if (gimple_code (phi
) != GIMPLE_PHI
1947 || !is_gimple_reg (gimple_phi_result (phi
)))
1950 return (gimple_phi_num_args (phi
) == 1);
1953 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1954 dimension array for it. */
1957 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1959 gimple phi
= gsi_stmt (*psi
);
1960 tree res
= gimple_phi_result (phi
);
1961 tree var
= SSA_NAME_VAR (res
);
1962 tree zero_dim_array
= create_zero_dim_array (var
);
1963 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
1964 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
1965 tree arg
= gimple_phi_arg_def (phi
, 0);
1967 insert_out_of_ssa_copy (zero_dim_array
, arg
);
1969 remove_phi_node (psi
, false);
1970 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1971 SSA_NAME_DEF_STMT (res
) = stmt
;
1974 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1975 dimension array for it. */
1978 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1981 gimple phi
= gsi_stmt (*psi
);
1982 basic_block bb
= gimple_bb (phi
);
1983 tree res
= gimple_phi_result (phi
);
1984 tree var
= SSA_NAME_VAR (res
);
1985 tree zero_dim_array
= create_zero_dim_array (var
);
1986 gimple_stmt_iterator gsi
;
1990 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1992 tree arg
= gimple_phi_arg_def (phi
, i
);
1994 /* Try to avoid the insertion on edges as much as possible: this
1995 would avoid the insertion of code on loop latch edges, making
1996 the pattern matching of the vectorizer happy, or it would
1997 avoid the insertion of useless basic blocks. Note that it is
1998 incorrect to insert out of SSA copies close by their
1999 definition when they are more than two loop levels apart:
2000 for example, starting from a double nested loop
2010 the following transform is incorrect
2022 whereas inserting the copy on the incomming edge is correct
2034 if (TREE_CODE (arg
) == SSA_NAME
2035 && is_gimple_reg (arg
)
2036 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2037 && (flow_bb_inside_loop_p (bb
->loop_father
,
2038 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2039 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2040 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2041 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2043 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2044 zero_dim_array
, arg
);
2047 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2050 stmts
= gimple_seq_alloc ();
2052 stmt
= gimple_build_assign (res
, var
);
2053 remove_phi_node (psi
, false);
2054 SSA_NAME_DEF_STMT (res
) = stmt
;
2056 gsi
= gsi_last (stmts
);
2057 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2059 gsi
= gsi_after_labels (bb
);
2060 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2063 /* Return true when DEF can be analyzed in REGION by the scalar
2064 evolution analyzer. */
2067 scev_analyzable_p (tree def
, sese region
)
2069 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2070 loop_p loop
= loop_containing_stmt (stmt
);
2071 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2073 return !chrec_contains_undetermined (scev
);
2076 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2077 read from ZERO_DIM_ARRAY. */
2080 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2082 tree var
= SSA_NAME_VAR (def
);
2083 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2084 tree name
= make_ssa_name (var
, name_stmt
);
2086 use_operand_p use_p
;
2087 gimple_stmt_iterator gsi
;
2089 gimple_assign_set_lhs (name_stmt
, name
);
2091 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2093 gimple phi
= use_stmt
;
2097 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2098 if (operand_equal_p (def
, gimple_phi_arg_def (phi
, i
), 0))
2100 entry
= gimple_phi_arg_edge (phi
, i
);
2104 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
2105 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2107 gsi
= gsi_last_bb (entry
->src
);
2108 gsi_insert_after (&gsi
, name_stmt
, GSI_NEW_STMT
);
2109 SET_USE (use_p
, name
);
2115 gsi
= gsi_for_stmt (use_stmt
);
2116 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2118 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2119 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2120 replace_exp (use_p
, name
);
2123 update_stmt (use_stmt
);
2126 /* Rewrite the scalar dependences crossing the boundary of the BB
2127 containing STMT with an array. */
2130 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2132 gimple stmt
= gsi_stmt (*gsi
);
2133 imm_use_iterator imm_iter
;
2136 tree zero_dim_array
= NULL_TREE
;
2139 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2142 def
= gimple_assign_lhs (stmt
);
2143 if (!is_gimple_reg (def
)
2144 || scev_analyzable_p (def
, region
))
2147 def_bb
= gimple_bb (stmt
);
2149 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2150 if (def_bb
!= gimple_bb (use_stmt
))
2152 if (!zero_dim_array
)
2154 zero_dim_array
= create_zero_dim_array (SSA_NAME_VAR (def
));
2155 insert_out_of_ssa_copy (zero_dim_array
, def
);
2159 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2163 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2166 rewrite_reductions_out_of_ssa (scop_p scop
)
2169 gimple_stmt_iterator psi
;
2170 sese region
= SCOP_REGION (scop
);
2173 if (bb_in_sese_p (bb
, region
))
2174 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2176 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2177 rewrite_close_phi_out_of_ssa (&psi
);
2178 else if (reduction_phi_p (region
, &psi
))
2179 rewrite_phi_out_of_ssa (&psi
);
2182 update_ssa (TODO_update_ssa
);
2183 #ifdef ENABLE_CHECKING
2185 verify_loop_closed_ssa ();
2189 if (bb_in_sese_p (bb
, region
))
2190 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2191 rewrite_cross_bb_scalar_deps (region
, &psi
);
2193 update_ssa (TODO_update_ssa
);
2194 #ifdef ENABLE_CHECKING
2196 verify_loop_closed_ssa ();
2200 /* Returns the number of pbbs that are in loops contained in SCOP. */
2203 nb_pbbs_in_loops (scop_p scop
)
2209 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2210 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2216 /* Splits STMT out of its current BB. */
2219 split_reduction_stmt (gimple stmt
)
2221 gimple_stmt_iterator gsi
;
2222 basic_block bb
= gimple_bb (stmt
);
2225 split_block (bb
, stmt
);
2227 gsi
= gsi_last_bb (bb
);
2229 e
= split_block (bb
, gsi_stmt (gsi
));
2234 /* Return true when stmt is a reduction operation. */
2237 is_reduction_operation_p (gimple stmt
)
2239 return flag_associative_math
2240 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2241 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2244 /* Returns true when PHI contains an argument ARG. */
2247 phi_contains_arg (gimple phi
, tree arg
)
2251 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2252 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2258 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2261 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2265 if (TREE_CODE (arg
) != SSA_NAME
)
2268 stmt
= SSA_NAME_DEF_STMT (arg
);
2270 if (gimple_code (stmt
) == GIMPLE_PHI
)
2272 if (phi_contains_arg (stmt
, lhs
))
2277 if (gimple_num_ops (stmt
) == 2)
2278 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2280 if (is_reduction_operation_p (stmt
))
2282 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2285 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2291 /* Detect commutative and associative scalar reductions starting at
2295 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2296 VEC (gimple
, heap
) **in
,
2297 VEC (gimple
, heap
) **out
)
2299 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2303 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2304 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2311 /* Detect commutative and associative scalar reductions starting at
2315 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2316 VEC (gimple
, heap
) **out
)
2318 tree lhs
= gimple_assign_lhs (stmt
);
2320 if (gimple_num_ops (stmt
) == 2)
2321 return detect_commutative_reduction_arg (lhs
, stmt
,
2322 gimple_assign_rhs1 (stmt
),
2325 if (is_reduction_operation_p (stmt
))
2327 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2328 gimple_assign_rhs1 (stmt
),
2331 : detect_commutative_reduction_arg (lhs
, stmt
,
2332 gimple_assign_rhs2 (stmt
),
2339 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2342 follow_inital_value_to_phi (tree arg
, tree lhs
)
2346 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2349 stmt
= SSA_NAME_DEF_STMT (arg
);
2351 if (gimple_code (stmt
) == GIMPLE_PHI
2352 && phi_contains_arg (stmt
, lhs
))
2359 /* Return the argument of the loop PHI that is the inital value coming
2360 from outside the loop. */
2363 edge_initial_value_for_loop_phi (gimple phi
)
2367 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2369 edge e
= gimple_phi_arg_edge (phi
, i
);
2371 if (loop_depth (e
->src
->loop_father
)
2372 < loop_depth (e
->dest
->loop_father
))
2379 /* Return the argument of the loop PHI that is the inital value coming
2380 from outside the loop. */
2383 initial_value_for_loop_phi (gimple phi
)
2387 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2389 edge e
= gimple_phi_arg_edge (phi
, i
);
2391 if (loop_depth (e
->src
->loop_father
)
2392 < loop_depth (e
->dest
->loop_father
))
2393 return gimple_phi_arg_def (phi
, i
);
2399 /* Detect commutative and associative scalar reductions starting at
2400 the loop closed phi node CLOSE_PHI. */
2403 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2404 VEC (gimple
, heap
) **out
)
2406 if (scalar_close_phi_node_p (stmt
))
2408 tree arg
= gimple_phi_arg_def (stmt
, 0);
2409 gimple def
= SSA_NAME_DEF_STMT (arg
);
2410 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2414 tree lhs
= gimple_phi_result (stmt
);
2415 tree init
= initial_value_for_loop_phi (loop_phi
);
2416 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2418 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2419 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2426 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2427 return detect_commutative_reduction_assign (stmt
, in
, out
);
2432 /* Translate the scalar reduction statement STMT to an array RED
2433 knowing that its recursive phi node is LOOP_PHI. */
2436 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2439 basic_block bb
= gimple_bb (stmt
);
2440 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2441 tree res
= gimple_phi_result (loop_phi
);
2442 gimple assign
= gimple_build_assign (res
, red
);
2444 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2446 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2447 insert_gsi
= gsi_last_bb (bb
);
2448 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2451 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2454 insert_copyout (tree red
, gimple close_phi
)
2456 tree res
= gimple_phi_result (close_phi
);
2457 basic_block bb
= gimple_bb (close_phi
);
2458 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2459 gimple assign
= gimple_build_assign (res
, red
);
2461 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2464 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2467 insert_copyin (tree red
, gimple loop_phi
)
2470 tree init
= initial_value_for_loop_phi (loop_phi
);
2471 edge e
= edge_initial_value_for_loop_phi (loop_phi
);
2472 basic_block bb
= e
->src
;
2473 gimple_stmt_iterator insert_gsi
= gsi_last_bb (bb
);
2474 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2476 force_gimple_operand (expr
, &stmts
, true, NULL
);
2477 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2480 /* Rewrite out of SSA the reduction described by the loop phi nodes
2481 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2484 IN: stmt, loop_n, ..., loop_0
2485 OUT: stmt, close_n, ..., close_0
2487 the first element is the reduction statement, and the next elements
2488 are the loop and close phi nodes of each of the outer loops. */
2491 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2492 VEC (gimple
, heap
) *out
,
2498 gimple_stmt_iterator gsi
;
2500 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2502 gimple close_phi
= VEC_index (gimple
, out
, i
);
2506 gimple stmt
= loop_phi
;
2507 basic_block bb
= split_reduction_stmt (stmt
);
2509 SET_BIT (reductions
, bb
->index
);
2510 gcc_assert (close_phi
== loop_phi
);
2512 red
= create_zero_dim_array (gimple_assign_lhs (stmt
));
2513 translate_scalar_reduction_to_array_for_stmt
2514 (red
, stmt
, VEC_index (gimple
, in
, 1));
2518 if (i
== VEC_length (gimple
, in
) - 1)
2520 insert_copyout (red
, close_phi
);
2521 insert_copyin (red
, loop_phi
);
2524 gsi
= gsi_for_phi_node (loop_phi
);
2525 remove_phi_node (&gsi
, false);
2527 gsi
= gsi_for_phi_node (close_phi
);
2528 remove_phi_node (&gsi
, false);
2532 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2535 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2538 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2539 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2541 detect_commutative_reduction (close_phi
, &in
, &out
);
2542 if (VEC_length (gimple
, in
) > 0)
2543 translate_scalar_reduction_to_array (in
, out
, reductions
);
2545 VEC_free (gimple
, heap
, in
);
2546 VEC_free (gimple
, heap
, out
);
2549 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2552 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2555 gimple_stmt_iterator gsi
;
2556 edge exit
= single_exit (loop
);
2561 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2562 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2566 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2569 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2574 FOR_EACH_LOOP (li
, loop
, 0)
2575 if (loop_in_sese_p (loop
, region
))
2576 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2579 /* Builds the polyhedral representation for a SESE region. */
2582 build_poly_scop (scop_p scop
)
2584 sese region
= SCOP_REGION (scop
);
2585 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2587 sbitmap_zero (reductions
);
2588 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2589 rewrite_reductions_out_of_ssa (scop
);
2590 build_scop_bbs (scop
, reductions
);
2591 sbitmap_free (reductions
);
2593 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2594 Once CLooG is fixed, remove this guard. Anyways, it makes no
2595 sense to optimize a scop containing only PBBs that do not belong
2597 if (nb_pbbs_in_loops (scop
) == 0)
2600 build_sese_loop_nests (region
);
2601 build_sese_conditions (region
);
2602 find_scop_parameters (scop
);
2604 build_scop_iteration_domain (scop
);
2605 build_scop_context (scop
);
2607 add_conditions_to_constraints (scop
);
2608 build_scop_scattering (scop
);
2609 build_scop_drs (scop
);
2614 /* Always return false. Exercise the scop_to_clast function. */
2617 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2619 #ifdef ENABLE_CHECKING
2620 cloog_prog_clast pc
= scop_to_clast (scop
);
2621 cloog_clast_free (pc
.stmt
);
2622 cloog_program_free (pc
.prog
);