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-scalar-evolution.h"
37 #include "tree-data-ref.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
))
238 /* Control flow expressions can be ignored, as they are
239 represented in the iteration domains and will be
240 regenerated by graphite. */
248 tree var
= gimple_assign_lhs (stmt
);
250 /* We need these bbs to be able to construct the phi nodes. */
251 if (var_used_in_not_loop_header_phi_node (var
))
254 var
= scalar_evolution_in_region (region
, loop
, var
);
255 if (chrec_contains_undetermined (var
))
269 /* Store the GRAPHITE representation of BB. */
272 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
274 struct gimple_bb
*gbb
;
276 gbb
= XNEW (struct gimple_bb
);
279 GBB_DATA_REFS (gbb
) = drs
;
280 GBB_CONDITIONS (gbb
) = NULL
;
281 GBB_CONDITION_CASES (gbb
) = NULL
;
282 GBB_CLOOG_IV_TYPES (gbb
) = NULL
;
288 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
291 struct data_reference
*dr
;
293 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
296 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
299 free (bap
->alias_set
);
308 free_gimple_bb (struct gimple_bb
*gbb
)
310 if (GBB_CLOOG_IV_TYPES (gbb
))
311 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
313 free_data_refs_aux (GBB_DATA_REFS (gbb
));
314 free_data_refs (GBB_DATA_REFS (gbb
));
316 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
317 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
318 GBB_BB (gbb
)->aux
= 0;
322 /* Deletes all gimple bbs in SCOP. */
325 remove_gbbs_in_scop (scop_p scop
)
330 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
331 free_gimple_bb (PBB_BLACK_BOX (pbb
));
334 /* Deletes all scops in SCOPS. */
337 free_scops (VEC (scop_p
, heap
) *scops
)
342 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
344 remove_gbbs_in_scop (scop
);
345 free_sese (SCOP_REGION (scop
));
349 VEC_free (scop_p
, heap
, scops
);
352 /* Generates a polyhedral black box only if the bb contains interesting
356 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
358 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
359 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
360 gimple_stmt_iterator gsi
;
362 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
363 graphite_find_data_references_in_stmt (nest
, gsi_stmt (gsi
), &drs
);
365 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
366 free_data_refs (drs
);
368 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
372 /* Returns true if all predecessors of BB, that are not dominated by BB, are
373 marked in MAP. The predecessors dominated by BB are loop latches and will
374 be handled after BB. */
377 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
382 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
383 if (!TEST_BIT (map
, e
->src
->index
)
384 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
390 /* Compare the depth of two basic_block's P1 and P2. */
393 compare_bb_depths (const void *p1
, const void *p2
)
395 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
396 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
397 int d1
= loop_depth (bb1
->loop_father
);
398 int d2
= loop_depth (bb2
->loop_father
);
409 /* Sort the basic blocks from DOM such that the first are the ones at
410 a deepest loop level. */
413 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
415 size_t len
= VEC_length (basic_block
, dom
);
417 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
421 /* Recursive helper function for build_scops_bbs. */
424 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
426 sese region
= SCOP_REGION (scop
);
427 VEC (basic_block
, heap
) *dom
;
429 if (TEST_BIT (visited
, bb
->index
)
430 || !bb_in_sese_p (bb
, region
))
433 try_generate_gimple_bb (scop
, bb
, reductions
);
434 SET_BIT (visited
, bb
->index
);
436 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
441 graphite_sort_dominated_info (dom
);
443 while (!VEC_empty (basic_block
, dom
))
448 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
449 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
451 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
452 VEC_unordered_remove (basic_block
, dom
, i
);
457 VEC_free (basic_block
, heap
, dom
);
460 /* Gather the basic blocks belonging to the SCOP. */
463 build_scop_bbs (scop_p scop
, sbitmap reductions
)
465 sbitmap visited
= sbitmap_alloc (last_basic_block
);
466 sese region
= SCOP_REGION (scop
);
468 sbitmap_zero (visited
);
469 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
470 sbitmap_free (visited
);
473 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
474 We generate SCATTERING_DIMENSIONS scattering dimensions.
476 CLooG 0.15.0 and previous versions require, that all
477 scattering functions of one CloogProgram have the same number of
478 scattering dimensions, therefore we allow to specify it. This
479 should be removed in future versions of CLooG.
481 The scattering polyhedron consists of these dimensions: scattering,
482 loop_iterators, parameters.
486 | scattering_dimensions = 5
487 | used_scattering_dimensions = 3
495 | Scattering polyhedron:
497 | scattering: {s1, s2, s3, s4, s5}
498 | loop_iterators: {i}
499 | parameters: {p1, p2}
501 | s1 s2 s3 s4 s5 i p1 p2 1
502 | 1 0 0 0 0 0 0 0 -4 = 0
503 | 0 1 0 0 0 -1 0 0 0 = 0
504 | 0 0 1 0 0 0 0 0 -5 = 0 */
507 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
508 poly_bb_p pbb
, int scattering_dimensions
)
511 scop_p scop
= PBB_SCOP (pbb
);
512 int nb_iterators
= pbb_dim_iter_domain (pbb
);
513 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
514 int nb_params
= scop_nb_params (scop
);
516 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
519 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
522 ppl_new_Coefficient (&c
);
523 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
524 ppl_new_C_Polyhedron_from_space_dimension
525 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
527 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
529 for (i
= 0; i
< scattering_dimensions
; i
++)
531 ppl_Constraint_t cstr
;
532 ppl_Linear_Expression_t expr
;
534 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
536 ppl_assign_Coefficient_from_mpz_t (c
, v
);
537 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
539 /* Textual order inside this loop. */
542 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
543 ppl_Coefficient_to_mpz_t (c
, v
);
545 ppl_assign_Coefficient_from_mpz_t (c
, v
);
546 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
549 /* Iterations of this loop. */
550 else /* if ((i % 2) == 1) */
552 int loop
= (i
- 1) / 2;
554 value_set_si (v
, -1);
555 ppl_assign_Coefficient_from_mpz_t (c
, v
);
556 ppl_Linear_Expression_add_to_coefficient
557 (expr
, scattering_dimensions
+ loop
, c
);
560 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
561 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
562 ppl_delete_Linear_Expression (expr
);
563 ppl_delete_Constraint (cstr
);
567 ppl_delete_Coefficient (c
);
569 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
572 /* Build for BB the static schedule.
574 The static schedule is a Dewey numbering of the abstract syntax
575 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
577 The following example informally defines the static schedule:
596 Static schedules for A to F:
609 build_scop_scattering (scop_p scop
)
613 gimple_bb_p previous_gbb
= NULL
;
614 ppl_Linear_Expression_t static_schedule
;
619 ppl_new_Coefficient (&c
);
620 ppl_new_Linear_Expression (&static_schedule
);
622 /* We have to start schedules at 0 on the first component and
623 because we cannot compare_prefix_loops against a previous loop,
624 prefix will be equal to zero, and that index will be
625 incremented before copying. */
626 value_set_si (v
, -1);
627 ppl_assign_Coefficient_from_mpz_t (c
, v
);
628 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
630 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
632 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
633 ppl_Linear_Expression_t common
;
635 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
638 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
643 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
644 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
648 ppl_assign_Coefficient_from_mpz_t (c
, v
);
649 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
650 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
653 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
655 ppl_delete_Linear_Expression (common
);
659 ppl_delete_Coefficient (c
);
660 ppl_delete_Linear_Expression (static_schedule
);
663 /* Add the value K to the dimension D of the linear expression EXPR. */
666 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
670 ppl_Coefficient_t coef
;
672 ppl_new_Coefficient (&coef
);
673 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
675 ppl_Coefficient_to_mpz_t (coef
, val
);
677 value_addto (val
, val
, k
);
679 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
680 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
682 ppl_delete_Coefficient (coef
);
685 /* In the context of scop S, scan E, the right hand side of a scalar
686 evolution function in loop VAR, and translate it to a linear
690 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
691 ppl_Linear_Expression_t expr
)
695 loop_p loop
= get_loop (var
);
696 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
699 /* Scalar evolutions should happen in the sese region. */
700 gcc_assert (sese_loop_depth (s
, loop
) > 0);
702 /* We can not deal with parametric strides like:
708 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
711 value_set_si (val
, int_cst_value (e
));
712 add_value_to_dim (l
, expr
, val
);
717 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
718 linear expression EXPR. K is the multiplier of the constant. */
721 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
724 ppl_Coefficient_t coef
;
725 int v
= int_cst_value (cst
);
728 value_set_si (val
, 0);
730 /* Necessary to not get "-1 = 2^n - 1". */
732 value_sub_int (val
, val
, -v
);
734 value_add_int (val
, val
, v
);
736 value_multiply (val
, val
, k
);
737 ppl_new_Coefficient (&coef
);
738 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
739 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
741 ppl_delete_Coefficient (coef
);
744 /* Saves in NV at index I a new name for variable P. */
747 save_var_name (char **nv
, int i
, tree p
)
749 const char *name
= get_name (SSA_NAME_VAR (p
));
753 int len
= strlen (name
) + 16;
754 nv
[i
] = XNEWVEC (char, len
);
755 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
759 nv
[i
] = XNEWVEC (char, 16);
760 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
764 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
765 Otherwise returns -1. */
768 parameter_index_in_region_1 (tree name
, sese region
)
773 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
775 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
782 /* When the parameter NAME is in REGION, returns its index in
783 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
784 and returns the index of NAME. */
787 parameter_index_in_region (tree name
, sese region
)
791 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
793 i
= parameter_index_in_region_1 (name
, region
);
797 gcc_assert (SESE_ADD_PARAMS (region
));
799 i
= VEC_length (tree
, SESE_PARAMS (region
));
800 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
801 save_clast_name_index (SESE_PARAMS_INDEX (region
),
802 SESE_PARAMS_NAMES (region
)[i
], i
);
803 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
807 /* In the context of sese S, scan the expression E and translate it to
808 a linear expression C. When parsing a symbolic multiplication, K
809 represents the constant multiplier of an expression containing
813 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
816 if (e
== chrec_dont_know
)
819 switch (TREE_CODE (e
))
821 case POLYNOMIAL_CHREC
:
822 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
823 CHREC_VARIABLE (e
), c
);
824 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
828 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
833 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
835 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
836 value_multiply (val
, val
, k
);
837 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
841 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
848 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
850 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
851 value_multiply (val
, val
, k
);
852 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
856 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
861 case POINTER_PLUS_EXPR
:
862 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
863 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
868 ppl_Linear_Expression_t tmp_expr
= NULL
;
872 ppl_dimension_type dim
;
873 ppl_Linear_Expression_space_dimension (c
, &dim
);
874 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
878 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
882 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
884 ppl_delete_Linear_Expression (tmp_expr
);
892 ppl_Linear_Expression_t tmp_expr
= NULL
;
896 ppl_dimension_type dim
;
897 ppl_Linear_Expression_space_dimension (c
, &dim
);
898 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
901 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
905 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
907 ppl_delete_Linear_Expression (tmp_expr
);
915 ppl_Linear_Expression_t tmp_expr
= NULL
;
919 ppl_dimension_type dim
;
920 ppl_Linear_Expression_space_dimension (c
, &dim
);
921 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
924 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
928 ppl_Coefficient_t coef
;
931 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
933 ppl_delete_Linear_Expression (tmp_expr
);
934 value_init (minus_one
);
935 value_set_si (minus_one
, -1);
936 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
937 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
938 value_clear (minus_one
);
939 ppl_delete_Coefficient (coef
);
947 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
951 ppl_dimension_type dim
;
952 ppl_Linear_Expression_space_dimension (c
, &dim
);
953 p
+= dim
- sese_nb_params (s
);
954 add_value_to_dim (p
, c
, k
);
961 scan_tree_for_params_int (e
, c
, k
);
965 case NON_LVALUE_EXPR
:
966 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
975 /* Find parameters with respect to REGION in BB. We are looking in memory
976 access functions, conditions and loop bounds. */
979 find_params_in_bb (sese region
, gimple_bb_p gbb
)
985 loop_p loop
= GBB_BB (gbb
)->loop_father
;
989 value_set_si (one
, 1);
991 /* Find parameters in the access functions of data references. */
992 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
993 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
994 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
996 /* Find parameters in conditional statements. */
997 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
999 tree lhs
= scalar_evolution_in_region (region
, loop
,
1000 gimple_cond_lhs (stmt
));
1001 tree rhs
= scalar_evolution_in_region (region
, loop
,
1002 gimple_cond_rhs (stmt
));
1004 scan_tree_for_params (region
, lhs
, NULL
, one
);
1005 scan_tree_for_params (region
, rhs
, NULL
, one
);
1011 /* Record the parameters used in the SCOP. A variable is a parameter
1012 in a scop if it does not vary during the execution of that scop. */
1015 find_scop_parameters (scop_p scop
)
1019 sese region
= SCOP_REGION (scop
);
1024 value_set_si (one
, 1);
1026 /* Find the parameters used in the loop bounds. */
1027 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1029 tree nb_iters
= number_of_latch_executions (loop
);
1031 if (!chrec_contains_symbols (nb_iters
))
1034 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1035 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1040 /* Find the parameters used in data accesses. */
1041 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1042 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1044 scop_set_nb_params (scop
, sese_nb_params (region
));
1045 SESE_ADD_PARAMS (region
) = false;
1047 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1048 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
1051 /* Returns a gimple_bb from BB. */
1053 static inline gimple_bb_p
1054 gbb_from_bb (basic_block bb
)
1056 return (gimple_bb_p
) bb
->aux
;
1059 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1060 the constraints for the surrounding loops. */
1063 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1064 ppl_Polyhedron_t outer_ph
, int nb
)
1067 ppl_Polyhedron_t ph
;
1068 tree nb_iters
= number_of_latch_executions (loop
);
1069 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1070 sese region
= SCOP_REGION (scop
);
1073 ppl_const_Constraint_System_t pcs
;
1074 ppl_dimension_type
*map
1075 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1077 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1078 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1079 ppl_Polyhedron_add_constraints (ph
, pcs
);
1081 for (i
= 0; i
< (int) nb
; i
++)
1083 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1087 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1093 ppl_Constraint_t lb
;
1094 ppl_Linear_Expression_t lb_expr
;
1096 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1097 ppl_set_coef (lb_expr
, nb
, 1);
1098 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1099 ppl_delete_Linear_Expression (lb_expr
);
1100 ppl_Polyhedron_add_constraint (ph
, lb
);
1101 ppl_delete_Constraint (lb
);
1104 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1106 ppl_Constraint_t ub
;
1107 ppl_Linear_Expression_t ub_expr
;
1109 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1111 /* loop_i <= cst_nb_iters */
1112 ppl_set_coef (ub_expr
, nb
, -1);
1113 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1114 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1115 ppl_Polyhedron_add_constraint (ph
, ub
);
1116 ppl_delete_Linear_Expression (ub_expr
);
1117 ppl_delete_Constraint (ub
);
1119 else if (!chrec_contains_undetermined (nb_iters
))
1122 ppl_Constraint_t ub
;
1123 ppl_Linear_Expression_t ub_expr
;
1127 value_set_si (one
, 1);
1128 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1129 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1130 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1133 /* N <= estimated_nb_iters
1135 FIXME: This is a workaround that should go away once we will
1136 have the PIP algorithm. */
1137 if (estimated_loop_iterations (loop
, true, &nit
))
1140 ppl_Linear_Expression_t nb_iters_le
;
1141 ppl_Polyhedron_t pol
;
1142 graphite_dim_t n
= scop_nb_params (scop
);
1143 ppl_Coefficient_t coef
;
1145 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1146 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1149 /* Construct the negated number of last iteration in VAL. */
1151 mpz_set_double_int (val
, nit
, false);
1152 value_sub_int (val
, val
, 1);
1153 value_oppose (val
, val
);
1155 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1156 Subtract estimated number of last iteration and assert that result
1158 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1159 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1160 ppl_delete_Coefficient (coef
);
1161 ppl_new_Constraint (&ub
, nb_iters_le
,
1162 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1163 ppl_Polyhedron_add_constraint (pol
, ub
);
1165 /* Remove all but last N dimensions from POL to obtain constraints
1168 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- n
);
1170 for (i
= 0; i
< dim
- n
; i
++)
1172 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- n
);
1176 /* Add constraints on parameters to SCoP context. */
1178 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1179 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1180 (&constraints_ps
, pol
);
1181 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1182 (SCOP_CONTEXT (scop
), constraints_ps
);
1183 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1186 ppl_delete_Polyhedron (pol
);
1187 ppl_delete_Linear_Expression (nb_iters_le
);
1188 ppl_delete_Constraint (ub
);
1192 /* loop_i <= expr_nb_iters */
1193 ppl_set_coef (ub_expr
, nb
, -1);
1194 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1195 ppl_Polyhedron_add_constraint (ph
, ub
);
1196 ppl_delete_Linear_Expression (ub_expr
);
1197 ppl_delete_Constraint (ub
);
1202 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1203 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1207 && loop_in_sese_p (loop
->next
, region
))
1208 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1210 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1211 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1213 ppl_delete_Polyhedron (ph
);
1216 /* Returns a linear expression for tree T evaluated in PBB. */
1218 static ppl_Linear_Expression_t
1219 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1222 ppl_Linear_Expression_t res
;
1223 ppl_dimension_type dim
;
1224 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1225 loop_p loop
= pbb_loop (pbb
);
1227 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1228 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1230 t
= scalar_evolution_in_region (region
, loop
, t
);
1231 gcc_assert (!automatically_generated_chrec_p (t
));
1234 value_set_si (one
, 1);
1235 scan_tree_for_params (region
, t
, res
, one
);
1241 /* Returns the ppl constraint type from the gimple tree code CODE. */
1243 static enum ppl_enum_Constraint_Type
1244 ppl_constraint_type_from_tree_code (enum tree_code code
)
1248 /* We do not support LT and GT to be able to work with C_Polyhedron.
1249 As we work on integer polyhedron "a < b" can be expressed by
1256 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1259 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1262 return PPL_CONSTRAINT_TYPE_EQUAL
;
1269 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1270 CODE is used as the comparison operator. This allows us to invert the
1271 condition or to handle inequalities. */
1274 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1275 poly_bb_p pbb
, enum tree_code code
)
1278 ppl_Coefficient_t c
;
1279 ppl_Linear_Expression_t left
, right
;
1280 ppl_Constraint_t cstr
;
1281 enum ppl_enum_Constraint_Type type
;
1283 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1284 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1286 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1287 the left or the right side of the expression. */
1288 if (code
== LT_EXPR
)
1291 value_set_si (v
, 1);
1292 ppl_new_Coefficient (&c
);
1293 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1294 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1295 ppl_delete_Coefficient (c
);
1300 else if (code
== GT_EXPR
)
1303 value_set_si (v
, 1);
1304 ppl_new_Coefficient (&c
);
1305 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1306 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1307 ppl_delete_Coefficient (c
);
1313 type
= ppl_constraint_type_from_tree_code (code
);
1315 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1317 ppl_new_Constraint (&cstr
, left
, type
);
1318 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1320 ppl_delete_Constraint (cstr
);
1321 ppl_delete_Linear_Expression (left
);
1322 ppl_delete_Linear_Expression (right
);
1325 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1326 operator. This allows us to invert the condition or to handle
1330 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1332 if (code
== NE_EXPR
)
1334 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1335 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1336 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1338 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1339 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1340 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1342 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1345 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1348 /* Add conditions to the domain of PBB. */
1351 add_conditions_to_domain (poly_bb_p pbb
)
1355 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1356 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1358 if (VEC_empty (gimple
, conditions
))
1361 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1362 switch (gimple_code (stmt
))
1366 enum tree_code code
= gimple_cond_code (stmt
);
1368 /* The conditions for ELSE-branches are inverted. */
1369 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1370 code
= invert_tree_comparison (code
, false);
1372 add_condition_to_pbb (pbb
, stmt
, code
);
1377 /* Switch statements are not supported right now - fall throught. */
1385 /* Structure used to pass data to dom_walk. */
1389 VEC (gimple
, heap
) **conditions
, **cases
;
1393 /* Returns non NULL when BB has a single predecessor and the last
1394 statement of that predecessor is a COND_EXPR. */
1397 single_pred_cond (basic_block bb
)
1399 if (single_pred_p (bb
))
1401 edge e
= single_pred_edge (bb
);
1402 basic_block pred
= e
->src
;
1403 gimple stmt
= last_stmt (pred
);
1405 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1411 /* Call-back for dom_walk executed before visiting the dominated
1415 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1418 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1419 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1420 VEC (gimple
, heap
) **cases
= data
->cases
;
1421 gimple_bb_p gbb
= gbb_from_bb (bb
);
1422 gimple stmt
= single_pred_cond (bb
);
1424 if (!bb_in_sese_p (bb
, data
->region
))
1429 edge e
= single_pred_edge (bb
);
1431 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1433 if (e
->flags
& EDGE_TRUE_VALUE
)
1434 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1436 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1441 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1442 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1446 /* Call-back for dom_walk executed after visiting the dominated
1450 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1453 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1454 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1455 VEC (gimple
, heap
) **cases
= data
->cases
;
1457 if (!bb_in_sese_p (bb
, data
->region
))
1460 if (single_pred_cond (bb
))
1462 VEC_pop (gimple
, *conditions
);
1463 VEC_pop (gimple
, *cases
);
1467 /* Record all conditions in REGION. */
1470 build_sese_conditions (sese region
)
1472 struct dom_walk_data walk_data
;
1473 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1474 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1477 data
.conditions
= &conditions
;
1478 data
.cases
= &cases
;
1479 data
.region
= region
;
1481 walk_data
.dom_direction
= CDI_DOMINATORS
;
1482 walk_data
.initialize_block_local_data
= NULL
;
1483 walk_data
.before_dom_children
= build_sese_conditions_before
;
1484 walk_data
.after_dom_children
= build_sese_conditions_after
;
1485 walk_data
.global_data
= &data
;
1486 walk_data
.block_local_data_size
= 0;
1488 init_walk_dominator_tree (&walk_data
);
1489 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1490 fini_walk_dominator_tree (&walk_data
);
1492 VEC_free (gimple
, heap
, conditions
);
1493 VEC_free (gimple
, heap
, cases
);
1496 /* Traverses all the GBBs of the SCOP and add their constraints to the
1497 iteration domains. */
1500 add_conditions_to_constraints (scop_p scop
)
1505 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1506 add_conditions_to_domain (pbb
);
1509 /* Add constraints on the possible values of parameter P from the type
1513 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1515 ppl_Constraint_t cstr
;
1516 ppl_Linear_Expression_t le
;
1517 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1518 tree type
= TREE_TYPE (parameter
);
1521 /* Disabled until we fix CPU2006. */
1524 if (!INTEGRAL_TYPE_P (type
))
1527 lb
= TYPE_MIN_VALUE (type
);
1528 ub
= TYPE_MAX_VALUE (type
);
1532 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1533 ppl_set_coef (le
, p
, -1);
1534 ppl_set_inhomogeneous_tree (le
, lb
);
1535 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1536 ppl_Polyhedron_add_constraint (context
, cstr
);
1537 ppl_delete_Linear_Expression (le
);
1538 ppl_delete_Constraint (cstr
);
1543 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1544 ppl_set_coef (le
, p
, -1);
1545 ppl_set_inhomogeneous_tree (le
, ub
);
1546 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1547 ppl_Polyhedron_add_constraint (context
, cstr
);
1548 ppl_delete_Linear_Expression (le
);
1549 ppl_delete_Constraint (cstr
);
1553 /* Build the context of the SCOP. The context usually contains extra
1554 constraints that are added to the iteration domains that constrain
1558 build_scop_context (scop_p scop
)
1560 ppl_Polyhedron_t context
;
1561 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1562 graphite_dim_t p
, n
= scop_nb_params (scop
);
1564 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1566 for (p
= 0; p
< n
; p
++)
1567 add_param_constraints (scop
, context
, p
);
1569 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1571 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1572 (SCOP_CONTEXT (scop
), ps
);
1574 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1575 ppl_delete_Polyhedron (context
);
1578 /* Build the iteration domains: the loops belonging to the current
1579 SCOP, and that vary for the execution of the current basic block.
1580 Returns false if there is no loop in SCOP. */
1583 build_scop_iteration_domain (scop_p scop
)
1586 sese region
= SCOP_REGION (scop
);
1588 ppl_Polyhedron_t ph
;
1591 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1593 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1594 if (!loop_in_sese_p (loop_outer (loop
), region
))
1595 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1597 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1598 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1599 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1600 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1601 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1603 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1604 (&PBB_DOMAIN (pbb
), ph
);
1606 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1609 ppl_delete_Pointset_Powerset_C_Polyhedron
1610 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1614 ppl_delete_Polyhedron (ph
);
1617 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1618 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1619 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1623 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1624 ppl_dimension_type accessp_nb_dims
,
1625 ppl_dimension_type dom_nb_dims
)
1627 ppl_Linear_Expression_t alias
;
1628 ppl_Constraint_t cstr
;
1629 int alias_set_num
= 0;
1630 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1632 if (bap
&& bap
->alias_set
)
1633 alias_set_num
= *(bap
->alias_set
);
1635 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1637 ppl_set_coef (alias
, dom_nb_dims
, 1);
1638 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1639 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1640 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1642 ppl_delete_Linear_Expression (alias
);
1643 ppl_delete_Constraint (cstr
);
1646 /* Add to ACCESSES polyhedron equalities defining the access functions
1647 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1648 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1649 PBB is the poly_bb_p that contains the data reference DR. */
1652 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1653 ppl_dimension_type accessp_nb_dims
,
1654 ppl_dimension_type dom_nb_dims
,
1657 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1659 scop_p scop
= PBB_SCOP (pbb
);
1660 sese region
= SCOP_REGION (scop
);
1664 for (i
= 0; i
< nb_subscripts
; i
++)
1666 ppl_Linear_Expression_t fn
, access
;
1667 ppl_Constraint_t cstr
;
1668 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1669 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1671 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1672 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1674 value_set_si (v
, 1);
1675 scan_tree_for_params (region
, afn
, fn
, v
);
1676 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1678 ppl_set_coef (access
, subscript
, -1);
1679 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1680 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1682 ppl_delete_Linear_Expression (fn
);
1683 ppl_delete_Linear_Expression (access
);
1684 ppl_delete_Constraint (cstr
);
1690 /* Add constrains representing the size of the accessed data to the
1691 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1692 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1696 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1697 ppl_dimension_type accessp_nb_dims
,
1698 ppl_dimension_type dom_nb_dims
)
1700 tree ref
= DR_REF (dr
);
1701 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1703 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1705 ppl_Linear_Expression_t expr
;
1706 ppl_Constraint_t cstr
;
1707 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1710 if (TREE_CODE (ref
) != ARRAY_REF
)
1713 low
= array_ref_low_bound (ref
);
1715 /* subscript - low >= 0 */
1716 if (host_integerp (low
, 0))
1718 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1719 ppl_set_coef (expr
, subscript
, 1);
1721 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1723 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1724 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1725 ppl_delete_Linear_Expression (expr
);
1726 ppl_delete_Constraint (cstr
);
1729 high
= array_ref_up_bound (ref
);
1731 /* high - subscript >= 0 */
1732 if (high
&& host_integerp (high
, 0)
1733 /* 1-element arrays at end of structures may extend over
1734 their declared size. */
1735 && !(array_at_struct_end_p (ref
)
1736 && operand_equal_p (low
, high
, 0)))
1738 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1739 ppl_set_coef (expr
, subscript
, -1);
1741 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1743 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1744 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1745 ppl_delete_Linear_Expression (expr
);
1746 ppl_delete_Constraint (cstr
);
1751 /* Build data accesses for DR in PBB. */
1754 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1756 ppl_Polyhedron_t accesses
;
1757 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1758 ppl_dimension_type dom_nb_dims
;
1759 ppl_dimension_type accessp_nb_dims
;
1760 int dr_base_object_set
;
1762 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1764 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1766 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1768 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1769 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1770 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1772 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1774 ppl_delete_Polyhedron (accesses
);
1777 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1779 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1780 dr
, DR_NUM_DIMENSIONS (dr
));
1783 /* Write to FILE the alias graph of data references in DIMACS format. */
1786 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1787 VEC (data_reference_p
, heap
) *drs
)
1789 int num_vertex
= VEC_length (data_reference_p
, drs
);
1791 data_reference_p dr1
, dr2
;
1794 if (num_vertex
== 0)
1797 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1798 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1799 if (dr_may_alias_p (dr1
, dr2
))
1802 fprintf (file
, "$\n");
1805 fprintf (file
, "c %s\n", comment
);
1807 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1809 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1810 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1811 if (dr_may_alias_p (dr1
, dr2
))
1812 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1817 /* Write to FILE the alias graph of data references in DOT format. */
1820 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1821 VEC (data_reference_p
, heap
) *drs
)
1823 int num_vertex
= VEC_length (data_reference_p
, drs
);
1824 data_reference_p dr1
, dr2
;
1827 if (num_vertex
== 0)
1830 fprintf (file
, "$\n");
1833 fprintf (file
, "c %s\n", comment
);
1835 /* First print all the vertices. */
1836 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1837 fprintf (file
, "n%d;\n", i
);
1839 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1840 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1841 if (dr_may_alias_p (dr1
, dr2
))
1842 fprintf (file
, "n%d n%d\n", i
, j
);
1847 /* Write to FILE the alias graph of data references in ECC format. */
1850 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1851 VEC (data_reference_p
, heap
) *drs
)
1853 int num_vertex
= VEC_length (data_reference_p
, drs
);
1854 data_reference_p dr1
, dr2
;
1857 if (num_vertex
== 0)
1860 fprintf (file
, "$\n");
1863 fprintf (file
, "c %s\n", comment
);
1865 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1866 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1867 if (dr_may_alias_p (dr1
, dr2
))
1868 fprintf (file
, "%d %d\n", i
, j
);
1873 /* Check if DR1 and DR2 are in the same object set. */
1876 dr_same_base_object_p (const struct data_reference
*dr1
,
1877 const struct data_reference
*dr2
)
1879 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1882 /* Uses DFS component number as representative of alias-sets. Also tests for
1883 optimality by verifying if every connected component is a clique. Returns
1884 true (1) if the above test is true, and false (0) otherwise. */
1887 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1889 int num_vertices
= VEC_length (data_reference_p
, drs
);
1890 struct graph
*g
= new_graph (num_vertices
);
1891 data_reference_p dr1
, dr2
;
1893 int num_connected_components
;
1894 int v_indx1
, v_indx2
, num_vertices_in_component
;
1897 struct graph_edge
*e
;
1898 int this_component_is_clique
;
1899 int all_components_are_cliques
= 1;
1901 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1902 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1903 if (dr_may_alias_p (dr1
, dr2
))
1909 all_vertices
= XNEWVEC (int, num_vertices
);
1910 vertices
= XNEWVEC (int, num_vertices
);
1911 for (i
= 0; i
< num_vertices
; i
++)
1912 all_vertices
[i
] = i
;
1914 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1916 for (i
= 0; i
< g
->n_vertices
; i
++)
1918 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1919 base_alias_pair
*bap
;
1922 bap
= (base_alias_pair
*)(dr
->aux
);
1924 bap
->alias_set
= XNEW (int);
1925 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1928 /* Verify if the DFS numbering results in optimal solution. */
1929 for (i
= 0; i
< num_connected_components
; i
++)
1931 num_vertices_in_component
= 0;
1932 /* Get all vertices whose DFS component number is the same as i. */
1933 for (j
= 0; j
< num_vertices
; j
++)
1934 if (g
->vertices
[j
].component
== i
)
1935 vertices
[num_vertices_in_component
++] = j
;
1937 /* Now test if the vertices in 'vertices' form a clique, by testing
1938 for edges among each pair. */
1939 this_component_is_clique
= 1;
1940 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1942 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1944 /* Check if the two vertices are connected by iterating
1945 through all the edges which have one of these are source. */
1946 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1949 if (e
->src
== vertices
[v_indx1
])
1955 this_component_is_clique
= 0;
1959 if (!this_component_is_clique
)
1960 all_components_are_cliques
= 0;
1964 free (all_vertices
);
1967 return all_components_are_cliques
;
1970 /* Group each data reference in DRS with it's base object set num. */
1973 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1975 int num_vertex
= VEC_length (data_reference_p
, drs
);
1976 struct graph
*g
= new_graph (num_vertex
);
1977 data_reference_p dr1
, dr2
;
1981 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1982 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1983 if (dr_same_base_object_p (dr1
, dr2
))
1989 queue
= XNEWVEC (int, num_vertex
);
1990 for (i
= 0; i
< num_vertex
; i
++)
1993 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1995 for (i
= 0; i
< g
->n_vertices
; i
++)
1997 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1998 base_alias_pair
*bap
;
2001 bap
= (base_alias_pair
*)(dr
->aux
);
2003 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2010 /* Build the data references for PBB. */
2013 build_pbb_drs (poly_bb_p pbb
)
2016 data_reference_p dr
;
2017 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2019 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2020 build_poly_dr (dr
, pbb
);
2023 /* Dump to file the alias graphs for the data references in DRS. */
2026 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2029 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2031 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2034 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2035 current_function_name ());
2036 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2037 fclose (file_dimacs
);
2040 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2043 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2044 current_function_name ());
2045 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2049 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2052 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2053 current_function_name ());
2054 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2059 /* Build data references in SCOP. */
2062 build_scop_drs (scop_p scop
)
2066 data_reference_p dr
;
2067 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2069 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2070 for (j
= 0; VEC_iterate (data_reference_p
,
2071 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2072 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2074 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2075 dr
->aux
= XNEW (base_alias_pair
);
2077 if (!build_alias_set_optimal_p (drs
))
2079 /* TODO: Add support when building alias set is not optimal. */
2083 build_base_obj_set_for_drs (drs
);
2085 /* When debugging, enable the following code. This cannot be used
2086 in production compilers. */
2088 dump_alias_graphs (drs
);
2090 VEC_free (data_reference_p
, heap
, drs
);
2092 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2093 build_pbb_drs (pbb
);
2096 /* Return a gsi at the position of the phi node STMT. */
2098 static gimple_stmt_iterator
2099 gsi_for_phi_node (gimple stmt
)
2101 gimple_stmt_iterator psi
;
2102 basic_block bb
= gimple_bb (stmt
);
2104 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2105 if (stmt
== gsi_stmt (psi
))
2112 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2115 insert_out_of_ssa_copy (tree res
, tree var
)
2119 gimple_stmt_iterator si
;
2120 gimple_stmt_iterator gsi
;
2122 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2123 stmt
= gimple_build_assign (res
, var
);
2125 stmts
= gimple_seq_alloc ();
2126 si
= gsi_last (stmts
);
2127 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2129 stmt
= SSA_NAME_DEF_STMT (var
);
2130 if (gimple_code (stmt
) == GIMPLE_PHI
)
2132 gsi
= gsi_after_labels (gimple_bb (stmt
));
2133 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2137 gsi
= gsi_for_stmt (stmt
);
2138 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2142 /* Insert on edge E the assignment "RES := EXPR". */
2145 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2147 gimple_stmt_iterator gsi
;
2149 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2150 gimple stmt
= gimple_build_assign (res
, var
);
2153 stmts
= gimple_seq_alloc ();
2155 gsi
= gsi_last (stmts
);
2156 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2157 gsi_insert_seq_on_edge (e
, stmts
);
2158 gsi_commit_edge_inserts ();
2161 /* Creates a zero dimension array of the same type as VAR. */
2164 create_zero_dim_array (tree var
)
2166 tree index_type
= build_index_type (integer_zero_node
);
2167 tree elt_type
= TREE_TYPE (var
);
2168 tree array_type
= build_array_type (elt_type
, index_type
);
2169 tree base
= create_tmp_var (array_type
, "Red");
2171 add_referenced_var (base
);
2173 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2177 /* Returns true when PHI is a loop close phi node. */
2180 scalar_close_phi_node_p (gimple phi
)
2182 if (gimple_code (phi
) != GIMPLE_PHI
2183 || !is_gimple_reg (gimple_phi_result (phi
)))
2186 return (gimple_phi_num_args (phi
) == 1);
2189 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2190 dimension array for it. */
2193 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2195 gimple phi
= gsi_stmt (*psi
);
2196 tree res
= gimple_phi_result (phi
);
2197 tree var
= SSA_NAME_VAR (res
);
2198 tree zero_dim_array
= create_zero_dim_array (var
);
2199 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2200 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2201 tree arg
= gimple_phi_arg_def (phi
, 0);
2203 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2205 remove_phi_node (psi
, false);
2206 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2207 SSA_NAME_DEF_STMT (res
) = stmt
;
2210 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2211 dimension array for it. */
2214 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2217 gimple phi
= gsi_stmt (*psi
);
2218 basic_block bb
= gimple_bb (phi
);
2219 tree res
= gimple_phi_result (phi
);
2220 tree var
= SSA_NAME_VAR (res
);
2221 tree zero_dim_array
= create_zero_dim_array (var
);
2222 gimple_stmt_iterator gsi
;
2226 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2228 tree arg
= gimple_phi_arg_def (phi
, i
);
2230 /* Try to avoid the insertion on edges as much as possible: this
2231 would avoid the insertion of code on loop latch edges, making
2232 the pattern matching of the vectorizer happy, or it would
2233 avoid the insertion of useless basic blocks. Note that it is
2234 incorrect to insert out of SSA copies close by their
2235 definition when they are more than two loop levels apart:
2236 for example, starting from a double nested loop
2246 the following transform is incorrect
2258 whereas inserting the copy on the incomming edge is correct
2270 if (TREE_CODE (arg
) == SSA_NAME
2271 && is_gimple_reg (arg
)
2272 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2273 && (flow_bb_inside_loop_p (bb
->loop_father
,
2274 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2275 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2276 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2277 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2279 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2280 zero_dim_array
, arg
);
2283 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2286 stmts
= gimple_seq_alloc ();
2288 stmt
= gimple_build_assign (res
, var
);
2289 remove_phi_node (psi
, false);
2290 SSA_NAME_DEF_STMT (res
) = stmt
;
2292 gsi
= gsi_last (stmts
);
2293 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2295 gsi
= gsi_after_labels (bb
);
2296 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2299 /* Return true when DEF can be analyzed in REGION by the scalar
2300 evolution analyzer. */
2303 scev_analyzable_p (tree def
, sese region
)
2305 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2306 loop_p loop
= loop_containing_stmt (stmt
);
2307 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2309 return !chrec_contains_undetermined (scev
);
2312 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2313 read from ZERO_DIM_ARRAY. */
2316 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2318 tree var
= SSA_NAME_VAR (def
);
2319 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2320 tree name
= make_ssa_name (var
, name_stmt
);
2322 use_operand_p use_p
;
2323 gimple_stmt_iterator gsi
;
2325 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2327 gimple_assign_set_lhs (name_stmt
, name
);
2329 gsi
= gsi_for_stmt (use_stmt
);
2330 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2332 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2333 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2334 replace_exp (use_p
, name
);
2336 update_stmt (use_stmt
);
2339 /* Rewrite the scalar dependences crossing the boundary of the BB
2340 containing STMT with an array. */
2343 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2345 gimple stmt
= gsi_stmt (*gsi
);
2346 imm_use_iterator imm_iter
;
2349 tree zero_dim_array
= NULL_TREE
;
2352 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2355 def
= gimple_assign_lhs (stmt
);
2356 if (!is_gimple_reg (def
)
2357 || scev_analyzable_p (def
, region
))
2360 def_bb
= gimple_bb (stmt
);
2362 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2363 if (def_bb
!= gimple_bb (use_stmt
)
2364 && gimple_code (use_stmt
) != GIMPLE_PHI
)
2366 if (!zero_dim_array
)
2368 zero_dim_array
= create_zero_dim_array (SSA_NAME_VAR (def
));
2369 insert_out_of_ssa_copy (zero_dim_array
, def
);
2373 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2377 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2380 rewrite_reductions_out_of_ssa (scop_p scop
)
2383 gimple_stmt_iterator psi
;
2384 sese region
= SCOP_REGION (scop
);
2387 if (bb_in_sese_p (bb
, region
))
2388 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2390 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2391 rewrite_close_phi_out_of_ssa (&psi
);
2392 else if (reduction_phi_p (region
, &psi
))
2393 rewrite_phi_out_of_ssa (&psi
);
2396 update_ssa (TODO_update_ssa
);
2397 #ifdef ENABLE_CHECKING
2399 verify_loop_closed_ssa ();
2403 if (bb_in_sese_p (bb
, region
))
2404 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2405 rewrite_cross_bb_scalar_deps (region
, &psi
);
2407 update_ssa (TODO_update_ssa
);
2408 #ifdef ENABLE_CHECKING
2410 verify_loop_closed_ssa ();
2414 /* Returns the number of pbbs that are in loops contained in SCOP. */
2417 nb_pbbs_in_loops (scop_p scop
)
2423 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2424 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2430 /* Return the number of data references in BB that write in
2434 nb_data_writes_in_bb (basic_block bb
)
2437 gimple_stmt_iterator gsi
;
2439 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2440 if (gimple_vdef (gsi_stmt (gsi
)))
2446 /* Splits STMT out of its current BB. */
2449 split_reduction_stmt (gimple stmt
)
2451 gimple_stmt_iterator gsi
;
2452 basic_block bb
= gimple_bb (stmt
);
2455 /* Do not split basic blocks with no writes to memory: the reduction
2456 will be the only write to memory. */
2457 if (nb_data_writes_in_bb (bb
) == 0)
2460 split_block (bb
, stmt
);
2462 gsi
= gsi_last_bb (bb
);
2464 e
= split_block (bb
, gsi_stmt (gsi
));
2469 /* Return true when stmt is a reduction operation. */
2472 is_reduction_operation_p (gimple stmt
)
2474 return flag_associative_math
2475 && commutative_tree_code (gimple_assign_rhs_code (stmt
))
2476 && associative_tree_code (gimple_assign_rhs_code (stmt
));
2479 /* Returns true when PHI contains an argument ARG. */
2482 phi_contains_arg (gimple phi
, tree arg
)
2486 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2487 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2493 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2496 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2500 if (TREE_CODE (arg
) != SSA_NAME
)
2503 stmt
= SSA_NAME_DEF_STMT (arg
);
2505 if (gimple_code (stmt
) == GIMPLE_PHI
)
2507 if (phi_contains_arg (stmt
, lhs
))
2512 if (gimple_num_ops (stmt
) == 2)
2513 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2515 if (is_reduction_operation_p (stmt
))
2517 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2520 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2526 /* Detect commutative and associative scalar reductions starting at
2530 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2531 VEC (gimple
, heap
) **in
,
2532 VEC (gimple
, heap
) **out
)
2534 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2538 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2539 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2546 /* Detect commutative and associative scalar reductions starting at
2550 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2551 VEC (gimple
, heap
) **out
)
2553 tree lhs
= gimple_assign_lhs (stmt
);
2555 if (gimple_num_ops (stmt
) == 2)
2556 return detect_commutative_reduction_arg (lhs
, stmt
,
2557 gimple_assign_rhs1 (stmt
),
2560 if (is_reduction_operation_p (stmt
))
2562 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2563 gimple_assign_rhs1 (stmt
),
2566 : detect_commutative_reduction_arg (lhs
, stmt
,
2567 gimple_assign_rhs2 (stmt
),
2574 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2577 follow_inital_value_to_phi (tree arg
, tree lhs
)
2581 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2584 stmt
= SSA_NAME_DEF_STMT (arg
);
2586 if (gimple_code (stmt
) == GIMPLE_PHI
2587 && phi_contains_arg (stmt
, lhs
))
2594 /* Return the argument of the loop PHI that is the inital value coming
2595 from outside the loop. */
2598 edge_initial_value_for_loop_phi (gimple phi
)
2602 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2604 edge e
= gimple_phi_arg_edge (phi
, i
);
2606 if (loop_depth (e
->src
->loop_father
)
2607 < loop_depth (e
->dest
->loop_father
))
2614 /* Return the argument of the loop PHI that is the inital value coming
2615 from outside the loop. */
2618 initial_value_for_loop_phi (gimple phi
)
2622 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2624 edge e
= gimple_phi_arg_edge (phi
, i
);
2626 if (loop_depth (e
->src
->loop_father
)
2627 < loop_depth (e
->dest
->loop_father
))
2628 return gimple_phi_arg_def (phi
, i
);
2634 /* Detect commutative and associative scalar reductions starting at
2635 the loop closed phi node CLOSE_PHI. */
2638 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2639 VEC (gimple
, heap
) **out
)
2641 if (scalar_close_phi_node_p (stmt
))
2643 tree arg
= gimple_phi_arg_def (stmt
, 0);
2644 gimple def
= SSA_NAME_DEF_STMT (arg
);
2645 gimple loop_phi
= detect_commutative_reduction (def
, in
, out
);
2649 tree lhs
= gimple_phi_result (stmt
);
2650 tree init
= initial_value_for_loop_phi (loop_phi
);
2651 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2653 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2654 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2661 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2662 return detect_commutative_reduction_assign (stmt
, in
, out
);
2667 /* Translate the scalar reduction statement STMT to an array RED
2668 knowing that its recursive phi node is LOOP_PHI. */
2671 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2674 basic_block bb
= gimple_bb (stmt
);
2675 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2676 tree res
= gimple_phi_result (loop_phi
);
2677 gimple assign
= gimple_build_assign (res
, red
);
2679 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2681 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2682 insert_gsi
= gsi_for_stmt (stmt
);
2683 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2686 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2689 insert_copyout (tree red
, gimple close_phi
)
2691 tree res
= gimple_phi_result (close_phi
);
2692 basic_block bb
= gimple_bb (close_phi
);
2693 gimple_stmt_iterator insert_gsi
= gsi_after_labels (bb
);
2694 gimple assign
= gimple_build_assign (res
, red
);
2696 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2699 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2702 insert_copyin (tree red
, gimple loop_phi
)
2705 tree init
= initial_value_for_loop_phi (loop_phi
);
2706 tree expr
= build2 (MODIFY_EXPR
, TREE_TYPE (init
), red
, init
);
2708 force_gimple_operand (expr
, &stmts
, true, NULL
);
2709 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi
), stmts
);
2712 /* Rewrite out of SSA the reduction described by the loop phi nodes
2713 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2716 IN: stmt, loop_n, ..., loop_0
2717 OUT: stmt, close_n, ..., close_0
2719 the first element is the reduction statement, and the next elements
2720 are the loop and close phi nodes of each of the outer loops. */
2723 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2724 VEC (gimple
, heap
) *out
,
2730 gimple_stmt_iterator gsi
;
2732 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2734 gimple close_phi
= VEC_index (gimple
, out
, i
);
2738 gimple stmt
= loop_phi
;
2739 basic_block bb
= split_reduction_stmt (stmt
);
2741 SET_BIT (reductions
, bb
->index
);
2742 gcc_assert (close_phi
== loop_phi
);
2744 red
= create_zero_dim_array (gimple_assign_lhs (stmt
));
2745 translate_scalar_reduction_to_array_for_stmt
2746 (red
, stmt
, VEC_index (gimple
, in
, 1));
2750 if (i
== VEC_length (gimple
, in
) - 1)
2752 insert_copyout (red
, close_phi
);
2753 insert_copyin (red
, loop_phi
);
2756 gsi
= gsi_for_phi_node (loop_phi
);
2757 remove_phi_node (&gsi
, false);
2759 gsi
= gsi_for_phi_node (close_phi
);
2760 remove_phi_node (&gsi
, false);
2764 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2767 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2770 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2771 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2773 detect_commutative_reduction (close_phi
, &in
, &out
);
2774 if (VEC_length (gimple
, in
) > 0)
2775 translate_scalar_reduction_to_array (in
, out
, reductions
);
2777 VEC_free (gimple
, heap
, in
);
2778 VEC_free (gimple
, heap
, out
);
2781 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2784 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2787 gimple_stmt_iterator gsi
;
2788 edge exit
= single_exit (loop
);
2793 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2794 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2798 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2801 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2806 FOR_EACH_LOOP (li
, loop
, 0)
2807 if (loop_in_sese_p (loop
, region
))
2808 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2810 gsi_commit_edge_inserts ();
2811 update_ssa (TODO_update_ssa
);
2812 #ifdef ENABLE_CHECKING
2814 verify_loop_closed_ssa ();
2818 /* Builds the polyhedral representation for a SESE region. */
2821 build_poly_scop (scop_p scop
)
2823 sese region
= SCOP_REGION (scop
);
2824 sbitmap reductions
= sbitmap_alloc (last_basic_block
* 2);
2826 sbitmap_zero (reductions
);
2827 rewrite_commutative_reductions_out_of_ssa (region
, reductions
);
2828 rewrite_reductions_out_of_ssa (scop
);
2829 build_scop_bbs (scop
, reductions
);
2830 sbitmap_free (reductions
);
2832 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2833 Once CLooG is fixed, remove this guard. Anyways, it makes no
2834 sense to optimize a scop containing only PBBs that do not belong
2836 if (nb_pbbs_in_loops (scop
) == 0)
2839 build_sese_loop_nests (region
);
2840 build_sese_conditions (region
);
2841 find_scop_parameters (scop
);
2843 build_scop_iteration_domain (scop
);
2844 build_scop_context (scop
);
2846 add_conditions_to_constraints (scop
);
2848 build_scop_scattering (scop
);
2849 build_scop_drs (scop
);
2854 /* Always return false. Exercise the scop_to_clast function. */
2857 check_poly_representation (scop_p scop
)
2859 #ifdef ENABLE_CHECKING
2860 cloog_prog_clast pc
= scop_to_clast (scop
);
2861 cloog_clast_free (pc
.stmt
);
2862 cloog_program_free (pc
.prog
);