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
)
61 imm_use_iterator imm_iter
;
65 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
67 basic_block bb
= gimple_bb (stmt
);
69 if (gimple_code (stmt
) == GIMPLE_PHI
70 && bb
->loop_father
->header
!= bb
)
77 /* Returns the index of the phi argument corresponding to the initial
81 loop_entry_phi_arg (gimple phi
)
83 loop_p loop
= gimple_bb (phi
)->loop_father
;
86 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
87 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
94 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
95 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
98 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
100 gimple phi
= gsi_stmt (*psi
);
101 tree res
= gimple_phi_result (phi
);
102 size_t entry
= loop_entry_phi_arg (phi
);
103 tree init
= gimple_phi_arg_def (phi
, entry
);
104 gimple stmt
= gimple_build_assign (res
, init
);
105 edge e
= gimple_phi_arg_edge (phi
, entry
);
107 remove_phi_node (psi
, false);
108 gsi_insert_on_edge_immediate (e
, stmt
);
109 SSA_NAME_DEF_STMT (res
) = stmt
;
112 /* Removes an invariant phi node at position PSI by inserting on the
113 loop ENTRY edge the assignment RES = INIT. */
116 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
118 gimple phi
= gsi_stmt (*psi
);
119 loop_p loop
= loop_containing_stmt (phi
);
120 tree res
= gimple_phi_result (phi
);
121 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
122 size_t entry
= loop_entry_phi_arg (phi
);
123 edge e
= gimple_phi_arg_edge (phi
, entry
);
127 gimple_stmt_iterator gsi
;
129 if (tree_contains_chrecs (scev
, NULL
))
130 scev
= gimple_phi_arg_def (phi
, entry
);
132 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
133 stmt
= gimple_build_assign (res
, var
);
134 remove_phi_node (psi
, false);
137 stmts
= gimple_seq_alloc ();
139 gsi
= gsi_last (stmts
);
140 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
141 gsi_insert_seq_on_edge (e
, stmts
);
142 gsi_commit_edge_inserts ();
143 SSA_NAME_DEF_STMT (res
) = stmt
;
146 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
149 simple_copy_phi_p (gimple phi
)
153 if (gimple_phi_num_args (phi
) != 2)
156 res
= gimple_phi_result (phi
);
157 return (res
== gimple_phi_arg_def (phi
, 0)
158 || res
== gimple_phi_arg_def (phi
, 1));
161 /* Returns true when the phi node at position PSI is a reduction phi
162 node in REGION. Otherwise moves the pointer PSI to the next phi to
166 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
171 gimple phi
= gsi_stmt (*psi
);
172 tree res
= gimple_phi_result (phi
);
174 if (!is_gimple_reg (res
))
180 loop
= loop_containing_stmt (phi
);
182 if (simple_copy_phi_p (phi
))
184 /* FIXME: PRE introduces phi nodes like these, for an example,
185 see id-5.f in the fortran graphite testsuite:
187 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
189 remove_simple_copy_phi (psi
);
193 /* Main induction variables with constant strides in LOOP are not
195 if (simple_iv (loop
, loop
, res
, &iv
, true))
201 scev
= scalar_evolution_in_region (region
, loop
, res
);
202 if (chrec_contains_undetermined (scev
))
205 if (evolution_function_is_invariant_p (scev
, loop
->num
))
207 remove_invariant_phi (region
, psi
);
211 /* All the other cases are considered reductions. */
215 /* Returns true when BB will be represented in graphite. Return false
216 for the basic blocks that contain code eliminated in the code
217 generation pass: i.e. induction variables and exit conditions. */
220 graphite_stmt_p (sese region
, basic_block bb
,
221 VEC (data_reference_p
, heap
) *drs
)
223 gimple_stmt_iterator gsi
;
224 loop_p loop
= bb
->loop_father
;
226 if (VEC_length (data_reference_p
, drs
) > 0)
229 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
231 gimple stmt
= gsi_stmt (gsi
);
233 switch (gimple_code (stmt
))
236 /* Control flow expressions can be ignored, as they are
237 represented in the iteration domains and will be
238 regenerated by graphite. */
246 tree var
= gimple_assign_lhs (stmt
);
248 /* We need these bbs to be able to construct the phi nodes. */
249 if (var_used_in_not_loop_header_phi_node (var
))
252 var
= scalar_evolution_in_region (region
, loop
, var
);
253 if (chrec_contains_undetermined (var
))
267 /* Store the GRAPHITE representation of BB. */
270 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
272 struct gimple_bb
*gbb
;
274 gbb
= XNEW (struct gimple_bb
);
277 GBB_DATA_REFS (gbb
) = drs
;
278 GBB_CONDITIONS (gbb
) = NULL
;
279 GBB_CONDITION_CASES (gbb
) = NULL
;
280 GBB_CLOOG_IV_TYPES (gbb
) = NULL
;
286 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
289 struct data_reference
*dr
;
291 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
302 free_gimple_bb (struct gimple_bb
*gbb
)
304 if (GBB_CLOOG_IV_TYPES (gbb
))
305 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
307 free_data_refs_aux (GBB_DATA_REFS (gbb
));
308 free_data_refs (GBB_DATA_REFS (gbb
));
310 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
311 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
312 GBB_BB (gbb
)->aux
= 0;
316 /* Deletes all gimple bbs in SCOP. */
319 remove_gbbs_in_scop (scop_p scop
)
324 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
325 free_gimple_bb (PBB_BLACK_BOX (pbb
));
328 /* Deletes all scops in SCOPS. */
331 free_scops (VEC (scop_p
, heap
) *scops
)
336 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
338 remove_gbbs_in_scop (scop
);
339 free_sese (SCOP_REGION (scop
));
343 VEC_free (scop_p
, heap
, scops
);
346 /* Generates a polyhedral black box only if the bb contains interesting
350 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
352 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
353 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
354 gimple_stmt_iterator gsi
;
356 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
358 gimple stmt
= gsi_stmt (gsi
);
359 if (!is_gimple_debug (stmt
))
360 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
363 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
364 free_data_refs (drs
);
366 new_poly_bb (scop
, new_gimple_bb (bb
, drs
));
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
)
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
);
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
);
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
)
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
));
468 sbitmap_free (visited
);
471 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
472 We generate SCATTERING_DIMENSIONS scattering dimensions.
474 CLooG 0.15.0 and previous versions require, that all
475 scattering functions of one CloogProgram have the same number of
476 scattering dimensions, therefore we allow to specify it. This
477 should be removed in future versions of CLooG.
479 The scattering polyhedron consists of these dimensions: scattering,
480 loop_iterators, parameters.
484 | scattering_dimensions = 5
485 | used_scattering_dimensions = 3
493 | Scattering polyhedron:
495 | scattering: {s1, s2, s3, s4, s5}
496 | loop_iterators: {i}
497 | parameters: {p1, p2}
499 | s1 s2 s3 s4 s5 i p1 p2 1
500 | 1 0 0 0 0 0 0 0 -4 = 0
501 | 0 1 0 0 0 -1 0 0 0 = 0
502 | 0 0 1 0 0 0 0 0 -5 = 0 */
505 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
506 poly_bb_p pbb
, int scattering_dimensions
)
509 scop_p scop
= PBB_SCOP (pbb
);
510 int nb_iterators
= pbb_dim_iter_domain (pbb
);
511 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
512 int nb_params
= scop_nb_params (scop
);
514 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
517 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
520 ppl_new_Coefficient (&c
);
521 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
522 ppl_new_C_Polyhedron_from_space_dimension
523 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
525 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
527 for (i
= 0; i
< scattering_dimensions
; i
++)
529 ppl_Constraint_t cstr
;
530 ppl_Linear_Expression_t expr
;
532 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
534 ppl_assign_Coefficient_from_mpz_t (c
, v
);
535 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
537 /* Textual order inside this loop. */
540 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
541 ppl_Coefficient_to_mpz_t (c
, v
);
543 ppl_assign_Coefficient_from_mpz_t (c
, v
);
544 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
547 /* Iterations of this loop. */
548 else /* if ((i % 2) == 1) */
550 int loop
= (i
- 1) / 2;
552 value_set_si (v
, -1);
553 ppl_assign_Coefficient_from_mpz_t (c
, v
);
554 ppl_Linear_Expression_add_to_coefficient
555 (expr
, scattering_dimensions
+ loop
, c
);
558 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
559 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
560 ppl_delete_Linear_Expression (expr
);
561 ppl_delete_Constraint (cstr
);
565 ppl_delete_Coefficient (c
);
567 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
570 /* Build for BB the static schedule.
572 The static schedule is a Dewey numbering of the abstract syntax
573 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
575 The following example informally defines the static schedule:
594 Static schedules for A to F:
607 build_scop_scattering (scop_p scop
)
611 gimple_bb_p previous_gbb
= NULL
;
612 ppl_Linear_Expression_t static_schedule
;
617 ppl_new_Coefficient (&c
);
618 ppl_new_Linear_Expression (&static_schedule
);
620 /* We have to start schedules at 0 on the first component and
621 because we cannot compare_prefix_loops against a previous loop,
622 prefix will be equal to zero, and that index will be
623 incremented before copying. */
624 value_set_si (v
, -1);
625 ppl_assign_Coefficient_from_mpz_t (c
, v
);
626 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
628 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
630 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
631 ppl_Linear_Expression_t common
;
633 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
636 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
641 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
642 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
646 ppl_assign_Coefficient_from_mpz_t (c
, v
);
647 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
648 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
651 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
653 ppl_delete_Linear_Expression (common
);
657 ppl_delete_Coefficient (c
);
658 ppl_delete_Linear_Expression (static_schedule
);
661 /* Add the value K to the dimension D of the linear expression EXPR. */
664 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
668 ppl_Coefficient_t coef
;
670 ppl_new_Coefficient (&coef
);
671 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
673 ppl_Coefficient_to_mpz_t (coef
, val
);
675 value_addto (val
, val
, k
);
677 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
678 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
680 ppl_delete_Coefficient (coef
);
683 /* In the context of scop S, scan E, the right hand side of a scalar
684 evolution function in loop VAR, and translate it to a linear
688 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
689 ppl_Linear_Expression_t expr
)
693 loop_p loop
= get_loop (var
);
694 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
697 /* Scalar evolutions should happen in the sese region. */
698 gcc_assert (sese_loop_depth (s
, loop
) > 0);
700 /* We can not deal with parametric strides like:
706 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
709 value_set_si (val
, int_cst_value (e
));
710 add_value_to_dim (l
, expr
, val
);
715 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
716 linear expression EXPR. K is the multiplier of the constant. */
719 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
722 ppl_Coefficient_t coef
;
723 int v
= int_cst_value (cst
);
726 value_set_si (val
, 0);
728 /* Necessary to not get "-1 = 2^n - 1". */
730 value_sub_int (val
, val
, -v
);
732 value_add_int (val
, val
, v
);
734 value_multiply (val
, val
, k
);
735 ppl_new_Coefficient (&coef
);
736 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
737 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
739 ppl_delete_Coefficient (coef
);
742 /* Saves in NV at index I a new name for variable P. */
745 save_var_name (char **nv
, int i
, tree p
)
747 const char *name
= get_name (SSA_NAME_VAR (p
));
751 int len
= strlen (name
) + 16;
752 nv
[i
] = XNEWVEC (char, len
);
753 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
757 nv
[i
] = XNEWVEC (char, 16);
758 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
762 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
763 Otherwise returns -1. */
766 parameter_index_in_region_1 (tree name
, sese region
)
771 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
773 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
780 /* When the parameter NAME is in REGION, returns its index in
781 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
782 and returns the index of NAME. */
785 parameter_index_in_region (tree name
, sese region
)
789 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
791 i
= parameter_index_in_region_1 (name
, region
);
795 gcc_assert (SESE_ADD_PARAMS (region
));
797 i
= VEC_length (tree
, SESE_PARAMS (region
));
798 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
799 save_clast_name_index (SESE_PARAMS_INDEX (region
),
800 SESE_PARAMS_NAMES (region
)[i
], i
);
801 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
805 /* In the context of sese S, scan the expression E and translate it to
806 a linear expression C. When parsing a symbolic multiplication, K
807 represents the constant multiplier of an expression containing
811 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
814 if (e
== chrec_dont_know
)
817 switch (TREE_CODE (e
))
819 case POLYNOMIAL_CHREC
:
820 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
821 CHREC_VARIABLE (e
), c
);
822 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
826 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
831 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
833 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
834 value_multiply (val
, val
, k
);
835 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
839 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
846 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
848 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
849 value_multiply (val
, val
, k
);
850 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
854 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
859 case POINTER_PLUS_EXPR
:
860 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
861 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
866 ppl_Linear_Expression_t tmp_expr
= NULL
;
870 ppl_dimension_type dim
;
871 ppl_Linear_Expression_space_dimension (c
, &dim
);
872 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
875 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
876 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
880 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
882 ppl_delete_Linear_Expression (tmp_expr
);
890 ppl_Linear_Expression_t tmp_expr
= NULL
;
894 ppl_dimension_type dim
;
895 ppl_Linear_Expression_space_dimension (c
, &dim
);
896 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
899 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
903 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
905 ppl_delete_Linear_Expression (tmp_expr
);
913 ppl_Linear_Expression_t tmp_expr
= NULL
;
917 ppl_dimension_type dim
;
918 ppl_Linear_Expression_space_dimension (c
, &dim
);
919 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
922 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
926 ppl_Coefficient_t coef
;
929 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
931 ppl_delete_Linear_Expression (tmp_expr
);
932 value_init (minus_one
);
933 value_set_si (minus_one
, -1);
934 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
935 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
936 value_clear (minus_one
);
937 ppl_delete_Coefficient (coef
);
945 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
949 ppl_dimension_type dim
;
950 ppl_Linear_Expression_space_dimension (c
, &dim
);
951 p
+= dim
- sese_nb_params (s
);
952 add_value_to_dim (p
, c
, k
);
959 scan_tree_for_params_int (e
, c
, k
);
963 case NON_LVALUE_EXPR
:
964 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
973 /* Find parameters with respect to REGION in BB. We are looking in memory
974 access functions, conditions and loop bounds. */
977 find_params_in_bb (sese region
, gimple_bb_p gbb
)
983 loop_p loop
= GBB_BB (gbb
)->loop_father
;
987 value_set_si (one
, 1);
989 /* Find parameters in the access functions of data references. */
990 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
991 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
992 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
994 /* Find parameters in conditional statements. */
995 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
997 tree lhs
= scalar_evolution_in_region (region
, loop
,
998 gimple_cond_lhs (stmt
));
999 tree rhs
= scalar_evolution_in_region (region
, loop
,
1000 gimple_cond_rhs (stmt
));
1002 scan_tree_for_params (region
, lhs
, NULL
, one
);
1003 scan_tree_for_params (region
, rhs
, NULL
, one
);
1009 /* Record the parameters used in the SCOP. A variable is a parameter
1010 in a scop if it does not vary during the execution of that scop. */
1013 find_scop_parameters (scop_p scop
)
1017 sese region
= SCOP_REGION (scop
);
1022 value_set_si (one
, 1);
1024 /* Find the parameters used in the loop bounds. */
1025 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1027 tree nb_iters
= number_of_latch_executions (loop
);
1029 if (!chrec_contains_symbols (nb_iters
))
1032 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1033 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1038 /* Find the parameters used in data accesses. */
1039 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1040 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1042 scop_set_nb_params (scop
, sese_nb_params (region
));
1043 SESE_ADD_PARAMS (region
) = false;
1046 /* Returns a gimple_bb from BB. */
1048 static inline gimple_bb_p
1049 gbb_from_bb (basic_block bb
)
1051 return (gimple_bb_p
) bb
->aux
;
1054 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1055 the constraints for the surrounding loops. */
1058 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1059 ppl_Polyhedron_t outer_ph
, int nb
)
1063 ppl_Polyhedron_t ph
;
1064 tree nb_iters
= number_of_latch_executions (loop
);
1065 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1066 sese region
= SCOP_REGION (scop
);
1069 ppl_const_Constraint_System_t pcs
;
1070 ppl_dimension_type
*map
1071 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1073 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1074 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1075 ppl_Polyhedron_add_constraints (ph
, pcs
);
1077 for (i
= 0; i
< (int) nb
; i
++)
1079 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1083 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1089 ppl_Constraint_t lb
;
1090 ppl_Linear_Expression_t lb_expr
;
1092 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1093 ppl_set_coef (lb_expr
, nb
, 1);
1094 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1095 ppl_delete_Linear_Expression (lb_expr
);
1096 ppl_Polyhedron_add_constraint (ph
, lb
);
1097 ppl_delete_Constraint (lb
);
1100 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1102 ppl_Constraint_t ub
;
1103 ppl_Linear_Expression_t ub_expr
;
1105 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1107 /* loop_i <= cst_nb_iters */
1108 ppl_set_coef (ub_expr
, nb
, -1);
1109 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1110 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1111 ppl_Polyhedron_add_constraint (ph
, ub
);
1112 ppl_delete_Linear_Expression (ub_expr
);
1113 ppl_delete_Constraint (ub
);
1115 else if (!chrec_contains_undetermined (nb_iters
))
1118 ppl_Constraint_t ub
;
1119 ppl_Linear_Expression_t ub_expr
;
1122 value_set_si (one
, 1);
1123 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1124 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1125 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1128 /* loop_i <= expr_nb_iters */
1129 ppl_set_coef (ub_expr
, nb
, -1);
1130 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1131 ppl_Polyhedron_add_constraint (ph
, ub
);
1132 ppl_delete_Linear_Expression (ub_expr
);
1133 ppl_delete_Constraint (ub
);
1138 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1139 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1143 && loop_in_sese_p (loop
->next
, region
))
1144 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1146 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1147 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1149 ppl_delete_Polyhedron (ph
);
1152 /* Returns a linear expression for tree T evaluated in PBB. */
1154 static ppl_Linear_Expression_t
1155 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1158 ppl_Linear_Expression_t res
;
1159 ppl_dimension_type dim
;
1160 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1161 loop_p loop
= GBB_BB (PBB_BLACK_BOX (pbb
))->loop_father
;
1163 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1164 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1166 t
= scalar_evolution_in_region (region
, loop
, t
);
1167 gcc_assert (!automatically_generated_chrec_p (t
));
1170 value_set_si (one
, 1);
1171 scan_tree_for_params (region
, t
, res
, one
);
1177 /* Returns the ppl constraint type from the gimple tree code CODE. */
1179 static enum ppl_enum_Constraint_Type
1180 ppl_constraint_type_from_tree_code (enum tree_code code
)
1184 /* We do not support LT and GT to be able to work with C_Polyhedron.
1185 As we work on integer polyhedron "a < b" can be expressed by
1192 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1195 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1198 return PPL_CONSTRAINT_TYPE_EQUAL
;
1205 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1206 CODE is used as the comparison operator. This allows us to invert the
1207 condition or to handle inequalities. */
1210 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1211 poly_bb_p pbb
, enum tree_code code
)
1214 ppl_Coefficient_t c
;
1215 ppl_Linear_Expression_t left
, right
;
1216 ppl_Constraint_t cstr
;
1217 enum ppl_enum_Constraint_Type type
;
1219 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1220 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1222 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1223 the left or the right side of the expression. */
1224 if (code
== LT_EXPR
)
1227 value_set_si (v
, 1);
1228 ppl_new_Coefficient (&c
);
1229 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1230 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1231 ppl_delete_Coefficient (c
);
1236 else if (code
== GT_EXPR
)
1239 value_set_si (v
, 1);
1240 ppl_new_Coefficient (&c
);
1241 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1242 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1243 ppl_delete_Coefficient (c
);
1249 type
= ppl_constraint_type_from_tree_code (code
);
1251 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1253 ppl_new_Constraint (&cstr
, left
, type
);
1254 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1256 ppl_delete_Constraint (cstr
);
1257 ppl_delete_Linear_Expression (left
);
1258 ppl_delete_Linear_Expression (right
);
1261 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1262 operator. This allows us to invert the condition or to handle
1266 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1268 if (code
== NE_EXPR
)
1270 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1271 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1272 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1274 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1275 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1276 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1278 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1281 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1284 /* Add conditions to the domain of PBB. */
1287 add_conditions_to_domain (poly_bb_p pbb
)
1291 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1292 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1294 if (VEC_empty (gimple
, conditions
))
1297 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1298 switch (gimple_code (stmt
))
1302 enum tree_code code
= gimple_cond_code (stmt
);
1304 /* The conditions for ELSE-branches are inverted. */
1305 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1306 code
= invert_tree_comparison (code
, false);
1308 add_condition_to_pbb (pbb
, stmt
, code
);
1313 /* Switch statements are not supported right now - fall throught. */
1321 /* Structure used to pass data to dom_walk. */
1325 VEC (gimple
, heap
) **conditions
, **cases
;
1329 /* Returns non NULL when BB has a single predecessor and the last
1330 statement of that predecessor is a COND_EXPR. */
1333 single_pred_cond (basic_block bb
)
1335 if (single_pred_p (bb
))
1337 edge e
= single_pred_edge (bb
);
1338 basic_block pred
= e
->src
;
1339 gimple stmt
= last_stmt (pred
);
1341 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1347 /* Call-back for dom_walk executed before visiting the dominated
1351 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1354 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1355 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1356 VEC (gimple
, heap
) **cases
= data
->cases
;
1357 gimple_bb_p gbb
= gbb_from_bb (bb
);
1358 gimple stmt
= single_pred_cond (bb
);
1360 if (!bb_in_sese_p (bb
, data
->region
))
1365 edge e
= single_pred_edge (bb
);
1367 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1369 if (e
->flags
& EDGE_TRUE_VALUE
)
1370 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1372 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1377 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1378 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1382 /* Call-back for dom_walk executed after visiting the dominated
1386 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1389 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1390 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1391 VEC (gimple
, heap
) **cases
= data
->cases
;
1393 if (!bb_in_sese_p (bb
, data
->region
))
1396 if (single_pred_cond (bb
))
1398 VEC_pop (gimple
, *conditions
);
1399 VEC_pop (gimple
, *cases
);
1403 /* Record all conditions in REGION. */
1406 build_sese_conditions (sese region
)
1408 struct dom_walk_data walk_data
;
1409 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1410 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1413 data
.conditions
= &conditions
;
1414 data
.cases
= &cases
;
1415 data
.region
= region
;
1417 walk_data
.dom_direction
= CDI_DOMINATORS
;
1418 walk_data
.initialize_block_local_data
= NULL
;
1419 walk_data
.before_dom_children
= build_sese_conditions_before
;
1420 walk_data
.after_dom_children
= build_sese_conditions_after
;
1421 walk_data
.global_data
= &data
;
1422 walk_data
.block_local_data_size
= 0;
1424 init_walk_dominator_tree (&walk_data
);
1425 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1426 fini_walk_dominator_tree (&walk_data
);
1428 VEC_free (gimple
, heap
, conditions
);
1429 VEC_free (gimple
, heap
, cases
);
1432 /* Traverses all the GBBs of the SCOP and add their constraints to the
1433 iteration domains. */
1436 add_conditions_to_constraints (scop_p scop
)
1441 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1442 add_conditions_to_domain (pbb
);
1445 /* Add constraints on the possible values of parameter P from the type
1449 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1451 ppl_Constraint_t cstr
;
1452 ppl_Linear_Expression_t le
;
1453 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1454 tree type
= TREE_TYPE (parameter
);
1457 /* Disabled until we fix CPU2006. */
1460 if (!INTEGRAL_TYPE_P (type
))
1463 lb
= TYPE_MIN_VALUE (type
);
1464 ub
= TYPE_MAX_VALUE (type
);
1468 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1469 ppl_set_coef (le
, p
, -1);
1470 ppl_set_inhomogeneous_tree (le
, lb
);
1471 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1472 ppl_Polyhedron_add_constraint (context
, cstr
);
1473 ppl_delete_Linear_Expression (le
);
1474 ppl_delete_Constraint (cstr
);
1479 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1480 ppl_set_coef (le
, p
, -1);
1481 ppl_set_inhomogeneous_tree (le
, ub
);
1482 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1483 ppl_Polyhedron_add_constraint (context
, cstr
);
1484 ppl_delete_Linear_Expression (le
);
1485 ppl_delete_Constraint (cstr
);
1489 /* Build the context of the SCOP. The context usually contains extra
1490 constraints that are added to the iteration domains that constrain
1494 build_scop_context (scop_p scop
)
1496 ppl_Polyhedron_t context
;
1497 graphite_dim_t p
, n
= scop_nb_params (scop
);
1499 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1501 for (p
= 0; p
< n
; p
++)
1502 add_param_constraints (scop
, context
, p
);
1504 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1505 (&SCOP_CONTEXT (scop
), context
);
1507 ppl_delete_Polyhedron (context
);
1510 /* Build the iteration domains: the loops belonging to the current
1511 SCOP, and that vary for the execution of the current basic block.
1512 Returns false if there is no loop in SCOP. */
1515 build_scop_iteration_domain (scop_p scop
)
1518 sese region
= SCOP_REGION (scop
);
1520 ppl_Polyhedron_t ph
;
1523 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1525 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1526 if (!loop_in_sese_p (loop_outer (loop
), region
))
1527 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1529 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1530 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1531 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1532 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1533 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1535 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1536 (&PBB_DOMAIN (pbb
), ph
);
1538 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1541 ppl_delete_Pointset_Powerset_C_Polyhedron
1542 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1546 ppl_delete_Polyhedron (ph
);
1549 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1550 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1551 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1555 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1556 ppl_dimension_type accessp_nb_dims
,
1557 ppl_dimension_type dom_nb_dims
)
1559 ppl_Linear_Expression_t alias
;
1560 ppl_Constraint_t cstr
;
1561 int alias_set_num
= 0;
1563 if (dr
->aux
!= NULL
)
1564 alias_set_num
= ((int *)(dr
->aux
))[ALIAS_SET_INDEX
];
1566 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1568 ppl_set_coef (alias
, dom_nb_dims
, 1);
1569 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1570 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1571 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1573 ppl_delete_Linear_Expression (alias
);
1574 ppl_delete_Constraint (cstr
);
1577 /* Add to ACCESSES polyhedron equalities defining the access functions
1578 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1579 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1580 PBB is the poly_bb_p that contains the data reference DR. */
1583 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1584 ppl_dimension_type accessp_nb_dims
,
1585 ppl_dimension_type dom_nb_dims
,
1588 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1590 scop_p scop
= PBB_SCOP (pbb
);
1591 sese region
= SCOP_REGION (scop
);
1595 for (i
= 0; i
< nb_subscripts
; i
++)
1597 ppl_Linear_Expression_t fn
, access
;
1598 ppl_Constraint_t cstr
;
1599 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1600 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1602 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1603 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1605 value_set_si (v
, 1);
1606 scan_tree_for_params (region
, afn
, fn
, v
);
1607 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1609 ppl_set_coef (access
, subscript
, -1);
1610 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1611 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1613 ppl_delete_Linear_Expression (fn
);
1614 ppl_delete_Linear_Expression (access
);
1615 ppl_delete_Constraint (cstr
);
1621 /* Add constrains representing the size of the accessed data to the
1622 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1623 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1627 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1628 ppl_dimension_type accessp_nb_dims
,
1629 ppl_dimension_type dom_nb_dims
)
1631 tree ref
= DR_REF (dr
);
1632 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1634 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1636 ppl_Linear_Expression_t expr
;
1637 ppl_Constraint_t cstr
;
1638 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1641 if (TREE_CODE (ref
) != ARRAY_REF
)
1644 low
= array_ref_low_bound (ref
);
1646 /* subscript - low >= 0 */
1647 if (host_integerp (low
, 0))
1649 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1650 ppl_set_coef (expr
, subscript
, 1);
1652 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1654 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1655 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1656 ppl_delete_Linear_Expression (expr
);
1657 ppl_delete_Constraint (cstr
);
1660 high
= array_ref_up_bound (ref
);
1662 /* high - subscript >= 0
1663 XXX: 1-element arrays at end of structures may extend over their
1665 if (high
&& host_integerp (high
, 0))
1667 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1668 ppl_set_coef (expr
, subscript
, -1);
1670 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1672 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1673 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1674 ppl_delete_Linear_Expression (expr
);
1675 ppl_delete_Constraint (cstr
);
1680 /* Build data accesses for DR in PBB. */
1683 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1685 ppl_Polyhedron_t accesses
;
1686 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1687 ppl_dimension_type dom_nb_dims
;
1688 ppl_dimension_type accessp_nb_dims
;
1689 int dr_base_object_set
;
1691 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1693 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1695 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1697 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1698 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1699 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1701 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1703 ppl_delete_Polyhedron (accesses
);
1705 dr_base_object_set
= ((int *)(dr
->aux
))[BASE_OBJECT_SET_INDEX
];
1707 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1708 dr
, DR_NUM_DIMENSIONS (dr
));
1711 /* Write to FILE the alias graph of data references with DIMACS format. */
1714 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1715 VEC (data_reference_p
, heap
) *drs
)
1717 int num_vertex
= VEC_length (data_reference_p
, drs
);
1719 data_reference_p dr1
, dr2
;
1722 if (num_vertex
== 0)
1725 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1726 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1727 if (dr_may_alias_p (dr1
, dr2
))
1730 fprintf (file
, "$\n");
1733 fprintf (file
, "c %s\n", comment
);
1735 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1737 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1738 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1739 if (dr_may_alias_p (dr1
, dr2
))
1740 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1746 partition_drs_to_sets (VEC (data_reference_p
, heap
) **drs
, int choice
,
1747 bool (* edge_exist_p
) (const struct data_reference
*,
1748 const struct data_reference
*))
1750 int num_vertex
= VEC_length (data_reference_p
, *drs
);
1751 struct graph
*g
= new_graph (num_vertex
);
1752 data_reference_p dr1
, dr2
;
1757 for (i
= 0; VEC_iterate (data_reference_p
, *drs
, i
, dr1
); i
++)
1758 for (j
= i
+1; VEC_iterate (data_reference_p
, *drs
, j
, dr2
); j
++)
1759 if ((*edge_exist_p
) (dr1
, dr2
))
1765 queue
= XNEWVEC (int, num_vertex
);
1766 for (i
= 0; i
< num_vertex
; i
++)
1769 num_component
= graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1771 for (i
= 0; i
< g
->n_vertices
; i
++)
1773 data_reference_p dr
= VEC_index (data_reference_p
, *drs
, i
);
1775 dr
->aux
= XNEWVEC (int, 2);
1776 ((int *)(dr
->aux
))[choice
] = g
->vertices
[i
].component
+ 1;
1784 dr_same_base_object_p (const struct data_reference
*dr1
,
1785 const struct data_reference
*dr2
)
1787 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1790 /* Group each data reference in DRS with it's alias set num. */
1793 build_alias_set_for_drs (VEC (data_reference_p
, heap
) **drs
)
1795 partition_drs_to_sets (drs
, ALIAS_SET_INDEX
, dr_may_alias_p
);
1798 /* Group each data reference in DRS with it's base object set num. */
1801 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) **drs
)
1803 partition_drs_to_sets (drs
, BASE_OBJECT_SET_INDEX
, dr_same_base_object_p
);
1806 /* Build the data references for PBB. */
1809 build_pbb_drs (poly_bb_p pbb
)
1812 data_reference_p dr
;
1813 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1815 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1816 build_poly_dr (dr
, pbb
);
1819 /* Build data references in SCOP. */
1822 build_scop_drs (scop_p scop
)
1826 data_reference_p dr
;
1827 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1829 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1831 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1832 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1833 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1836 build_alias_set_for_drs (&drs
);
1837 build_base_obj_set_for_drs (&drs
);
1839 /* When debugging, enable the following code. This cannot be used
1840 in production compilers. */
1846 file
= fopen ("/tmp/dr_alias_graph", "ab");
1849 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1850 current_function_name ());
1851 write_alias_graph_to_ascii_dimacs (file
, comment
, drs
);
1857 VEC_free (data_reference_p
, heap
, drs
);
1859 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1860 build_pbb_drs (pbb
);
1863 /* Return a gsi at the position of the VAR definition. */
1865 static gimple_stmt_iterator
1866 gsi_for_ssa_name_def (tree var
)
1870 gimple_stmt_iterator gsi
;
1871 gimple_stmt_iterator psi
;
1873 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1875 stmt
= SSA_NAME_DEF_STMT (var
);
1876 bb
= gimple_bb (stmt
);
1878 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1879 if (stmt
== gsi_stmt (psi
))
1880 return gsi_after_labels (bb
);
1882 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1883 if (stmt
== gsi_stmt (gsi
))
1893 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
1896 insert_out_of_ssa_copy (tree res
, tree var
)
1898 gimple_stmt_iterator gsi
= gsi_for_ssa_name_def (var
);
1901 gimple_stmt_iterator si
;
1903 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
1904 stmt
= gimple_build_assign (res
, var
);
1906 stmts
= gimple_seq_alloc ();
1907 si
= gsi_last (stmts
);
1908 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
1909 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1912 /* Insert on edge E the assignment "RES := EXPR". */
1915 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
1917 gimple_stmt_iterator gsi
;
1919 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1920 gimple stmt
= gimple_build_assign (res
, var
);
1923 stmts
= gimple_seq_alloc ();
1925 gsi
= gsi_last (stmts
);
1926 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1927 gsi_insert_seq_on_edge (e
, stmts
);
1928 gsi_commit_edge_inserts ();
1931 /* Creates a zero dimension array of the same type as VAR. */
1934 create_zero_dim_array (tree var
)
1936 tree index_type
= build_index_type (integer_zero_node
);
1937 tree elt_type
= TREE_TYPE (var
);
1938 tree array_type
= build_array_type (elt_type
, index_type
);
1939 tree base
= create_tmp_var (array_type
, "Red");
1941 add_referenced_var (base
);
1943 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1947 /* Returns true when PHI is a loop close phi node. */
1950 scalar_close_phi_node_p (gimple phi
)
1952 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
1954 if (!is_gimple_reg (gimple_phi_result (phi
)))
1957 return (gimple_phi_num_args (phi
) == 1);
1960 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1961 dimension array for it. */
1964 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1966 gimple phi
= gsi_stmt (*psi
);
1967 tree res
= gimple_phi_result (phi
);
1968 tree var
= SSA_NAME_VAR (res
);
1969 tree zero_dim_array
= create_zero_dim_array (var
);
1970 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
1971 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
1972 tree arg
= gimple_phi_arg_def (phi
, 0);
1974 insert_out_of_ssa_copy (zero_dim_array
, arg
);
1976 remove_phi_node (psi
, false);
1977 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1978 SSA_NAME_DEF_STMT (res
) = stmt
;
1981 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1982 dimension array for it. */
1985 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1988 gimple phi
= gsi_stmt (*psi
);
1989 basic_block bb
= gimple_bb (phi
);
1990 tree res
= gimple_phi_result (phi
);
1991 tree var
= SSA_NAME_VAR (res
);
1992 tree zero_dim_array
= create_zero_dim_array (var
);
1993 gimple_stmt_iterator gsi
;
1997 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1999 tree arg
= gimple_phi_arg_def (phi
, i
);
2001 /* Try to avoid the insertion on edges as much as possible: this
2002 would avoid the insertion of code on loop latch edges, making
2003 the pattern matching of the vectorizer happy, or it would
2004 avoid the insertion of useless basic blocks. Note that it is
2005 incorrect to insert out of SSA copies close by their
2006 definition when they are more than two loop levels apart:
2007 for example, starting from a double nested loop
2017 the following transform is incorrect
2029 whereas inserting the copy on the incomming edge is correct
2041 if (TREE_CODE (arg
) == SSA_NAME
2042 && is_gimple_reg (arg
)
2043 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
2044 && (flow_bb_inside_loop_p (bb
->loop_father
,
2045 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
2046 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
2047 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
2048 insert_out_of_ssa_copy (zero_dim_array
, arg
);
2050 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
2051 zero_dim_array
, arg
);
2054 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2057 stmts
= gimple_seq_alloc ();
2059 stmt
= gimple_build_assign (res
, var
);
2060 remove_phi_node (psi
, false);
2061 SSA_NAME_DEF_STMT (res
) = stmt
;
2063 gsi
= gsi_last (stmts
);
2064 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2066 gsi
= gsi_after_labels (bb
);
2067 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2070 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2073 rewrite_reductions_out_of_ssa (scop_p scop
)
2076 gimple_stmt_iterator psi
;
2077 sese region
= SCOP_REGION (scop
);
2080 if (bb_in_region (bb
, SESE_ENTRY_BB (region
), SESE_EXIT_BB (region
)))
2081 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2083 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2084 rewrite_close_phi_out_of_ssa (&psi
);
2085 else if (reduction_phi_p (region
, &psi
))
2086 rewrite_phi_out_of_ssa (&psi
);
2089 update_ssa (TODO_update_ssa
);
2090 #ifdef ENABLE_CHECKING
2092 verify_loop_closed_ssa ();
2096 /* Returns the number of pbbs that are in loops contained in SCOP. */
2099 nb_pbbs_in_loops (scop_p scop
)
2105 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2106 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2112 /* Builds the polyhedral representation for a SESE region. */
2115 build_poly_scop (scop_p scop
)
2117 sese region
= SCOP_REGION (scop
);
2118 rewrite_reductions_out_of_ssa (scop
);
2119 build_scop_bbs (scop
);
2121 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2122 Once CLooG is fixed, remove this guard. Anyways, it makes no
2123 sense to optimize a scop containing only PBBs that do not belong
2125 if (nb_pbbs_in_loops (scop
) == 0)
2128 build_sese_loop_nests (region
);
2129 build_sese_conditions (region
);
2130 find_scop_parameters (scop
);
2132 build_scop_iteration_domain (scop
);
2133 build_scop_context (scop
);
2135 add_conditions_to_constraints (scop
);
2136 build_scop_scattering (scop
);
2137 build_scop_drs (scop
);
2142 /* Always return false. Exercise the scop_to_clast function. */
2145 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2147 #ifdef ENABLE_CHECKING
2148 cloog_prog_clast pc
= scop_to_clast (scop
);
2149 cloog_clast_free (pc
.stmt
);
2150 cloog_program_free (pc
.prog
);