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
;
288 free_gimple_bb (struct gimple_bb
*gbb
)
290 if (GBB_CLOOG_IV_TYPES (gbb
))
291 htab_delete (GBB_CLOOG_IV_TYPES (gbb
));
293 free_data_refs (GBB_DATA_REFS (gbb
));
295 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
296 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
297 GBB_BB (gbb
)->aux
= 0;
301 /* Deletes all gimple bbs in SCOP. */
304 remove_gbbs_in_scop (scop_p scop
)
309 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
310 free_gimple_bb (PBB_BLACK_BOX (pbb
));
313 /* Deletes all scops in SCOPS. */
316 free_scops (VEC (scop_p
, heap
) *scops
)
321 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
323 remove_gbbs_in_scop (scop
);
324 free_sese (SCOP_REGION (scop
));
328 VEC_free (scop_p
, heap
, scops
);
331 /* Generates a polyhedral black box only if the bb contains interesting
335 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
337 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
338 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
339 gimple_stmt_iterator gsi
;
341 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
343 gimple stmt
= gsi_stmt (gsi
);
344 if (!is_gimple_debug (stmt
))
345 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
348 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
349 free_data_refs (drs
);
351 new_poly_bb (scop
, new_gimple_bb (bb
, drs
));
354 /* Returns true if all predecessors of BB, that are not dominated by BB, are
355 marked in MAP. The predecessors dominated by BB are loop latches and will
356 be handled after BB. */
359 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
364 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
365 if (!TEST_BIT (map
, e
->src
->index
)
366 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
372 /* Compare the depth of two basic_block's P1 and P2. */
375 compare_bb_depths (const void *p1
, const void *p2
)
377 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
378 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
379 int d1
= loop_depth (bb1
->loop_father
);
380 int d2
= loop_depth (bb2
->loop_father
);
391 /* Sort the basic blocks from DOM such that the first are the ones at
392 a deepest loop level. */
395 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
397 size_t len
= VEC_length (basic_block
, dom
);
399 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
403 /* Recursive helper function for build_scops_bbs. */
406 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
408 sese region
= SCOP_REGION (scop
);
409 VEC (basic_block
, heap
) *dom
;
411 if (TEST_BIT (visited
, bb
->index
)
412 || !bb_in_sese_p (bb
, region
))
415 try_generate_gimple_bb (scop
, bb
);
416 SET_BIT (visited
, bb
->index
);
418 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
423 graphite_sort_dominated_info (dom
);
425 while (!VEC_empty (basic_block
, dom
))
430 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
431 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
433 build_scop_bbs_1 (scop
, visited
, dom_bb
);
434 VEC_unordered_remove (basic_block
, dom
, i
);
439 VEC_free (basic_block
, heap
, dom
);
442 /* Gather the basic blocks belonging to the SCOP. */
445 build_scop_bbs (scop_p scop
)
447 sbitmap visited
= sbitmap_alloc (last_basic_block
);
448 sese region
= SCOP_REGION (scop
);
450 sbitmap_zero (visited
);
451 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
453 sbitmap_free (visited
);
456 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
457 We generate SCATTERING_DIMENSIONS scattering dimensions.
459 CLooG 0.15.0 and previous versions require, that all
460 scattering functions of one CloogProgram have the same number of
461 scattering dimensions, therefore we allow to specify it. This
462 should be removed in future versions of CLooG.
464 The scattering polyhedron consists of these dimensions: scattering,
465 loop_iterators, parameters.
469 | scattering_dimensions = 5
470 | used_scattering_dimensions = 3
478 | Scattering polyhedron:
480 | scattering: {s1, s2, s3, s4, s5}
481 | loop_iterators: {i}
482 | parameters: {p1, p2}
484 | s1 s2 s3 s4 s5 i p1 p2 1
485 | 1 0 0 0 0 0 0 0 -4 = 0
486 | 0 1 0 0 0 -1 0 0 0 = 0
487 | 0 0 1 0 0 0 0 0 -5 = 0 */
490 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
491 poly_bb_p pbb
, int scattering_dimensions
)
494 scop_p scop
= PBB_SCOP (pbb
);
495 int nb_iterators
= pbb_dim_iter_domain (pbb
);
496 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
497 int nb_params
= scop_nb_params (scop
);
499 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
502 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
505 ppl_new_Coefficient (&c
);
506 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
507 ppl_new_C_Polyhedron_from_space_dimension
508 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
510 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
512 for (i
= 0; i
< scattering_dimensions
; i
++)
514 ppl_Constraint_t cstr
;
515 ppl_Linear_Expression_t expr
;
517 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
519 ppl_assign_Coefficient_from_mpz_t (c
, v
);
520 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
522 /* Textual order inside this loop. */
525 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
526 ppl_Coefficient_to_mpz_t (c
, v
);
528 ppl_assign_Coefficient_from_mpz_t (c
, v
);
529 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
532 /* Iterations of this loop. */
533 else /* if ((i % 2) == 1) */
535 int loop
= (i
- 1) / 2;
537 value_set_si (v
, -1);
538 ppl_assign_Coefficient_from_mpz_t (c
, v
);
539 ppl_Linear_Expression_add_to_coefficient
540 (expr
, scattering_dimensions
+ loop
, c
);
543 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
544 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
545 ppl_delete_Linear_Expression (expr
);
546 ppl_delete_Constraint (cstr
);
550 ppl_delete_Coefficient (c
);
552 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
555 /* Build for BB the static schedule.
557 The static schedule is a Dewey numbering of the abstract syntax
558 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
560 The following example informally defines the static schedule:
579 Static schedules for A to F:
592 build_scop_scattering (scop_p scop
)
596 gimple_bb_p previous_gbb
= NULL
;
597 ppl_Linear_Expression_t static_schedule
;
602 ppl_new_Coefficient (&c
);
603 ppl_new_Linear_Expression (&static_schedule
);
605 /* We have to start schedules at 0 on the first component and
606 because we cannot compare_prefix_loops against a previous loop,
607 prefix will be equal to zero, and that index will be
608 incremented before copying. */
609 value_set_si (v
, -1);
610 ppl_assign_Coefficient_from_mpz_t (c
, v
);
611 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
613 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
615 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
616 ppl_Linear_Expression_t common
;
618 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
621 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
626 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
627 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
631 ppl_assign_Coefficient_from_mpz_t (c
, v
);
632 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
633 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
636 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
638 ppl_delete_Linear_Expression (common
);
642 ppl_delete_Coefficient (c
);
643 ppl_delete_Linear_Expression (static_schedule
);
646 /* Add the value K to the dimension D of the linear expression EXPR. */
649 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
653 ppl_Coefficient_t coef
;
655 ppl_new_Coefficient (&coef
);
656 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
658 ppl_Coefficient_to_mpz_t (coef
, val
);
660 value_addto (val
, val
, k
);
662 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
663 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
665 ppl_delete_Coefficient (coef
);
668 /* In the context of scop S, scan E, the right hand side of a scalar
669 evolution function in loop VAR, and translate it to a linear
673 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
674 ppl_Linear_Expression_t expr
)
678 loop_p loop
= get_loop (var
);
679 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
682 /* Scalar evolutions should happen in the sese region. */
683 gcc_assert (sese_loop_depth (s
, loop
) > 0);
685 /* We can not deal with parametric strides like:
691 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
694 value_set_si (val
, int_cst_value (e
));
695 add_value_to_dim (l
, expr
, val
);
700 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
701 linear expression EXPR. K is the multiplier of the constant. */
704 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, Value k
)
707 ppl_Coefficient_t coef
;
708 int v
= int_cst_value (cst
);
711 value_set_si (val
, 0);
713 /* Necessary to not get "-1 = 2^n - 1". */
715 value_sub_int (val
, val
, -v
);
717 value_add_int (val
, val
, v
);
719 value_multiply (val
, val
, k
);
720 ppl_new_Coefficient (&coef
);
721 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
722 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
724 ppl_delete_Coefficient (coef
);
727 /* Saves in NV at index I a new name for variable P. */
730 save_var_name (char **nv
, int i
, tree p
)
732 const char *name
= get_name (SSA_NAME_VAR (p
));
736 int len
= strlen (name
) + 16;
737 nv
[i
] = XNEWVEC (char, len
);
738 snprintf (nv
[i
], len
, "%s_%d", name
, SSA_NAME_VERSION (p
));
742 nv
[i
] = XNEWVEC (char, 16);
743 snprintf (nv
[i
], 2 + 16, "T_%d", SSA_NAME_VERSION (p
));
747 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
748 Otherwise returns -1. */
751 parameter_index_in_region_1 (tree name
, sese region
)
756 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
758 for (i
= 0; VEC_iterate (tree
, SESE_PARAMS (region
), i
, p
); i
++)
765 /* When the parameter NAME is in REGION, returns its index in
766 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
767 and returns the index of NAME. */
770 parameter_index_in_region (tree name
, sese region
)
774 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
776 i
= parameter_index_in_region_1 (name
, region
);
780 gcc_assert (SESE_ADD_PARAMS (region
));
782 i
= VEC_length (tree
, SESE_PARAMS (region
));
783 save_var_name (SESE_PARAMS_NAMES (region
), i
, name
);
784 save_clast_name_index (SESE_PARAMS_INDEX (region
),
785 SESE_PARAMS_NAMES (region
)[i
], i
);
786 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
790 /* In the context of sese S, scan the expression E and translate it to
791 a linear expression C. When parsing a symbolic multiplication, K
792 represents the constant multiplier of an expression containing
796 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
799 if (e
== chrec_dont_know
)
802 switch (TREE_CODE (e
))
804 case POLYNOMIAL_CHREC
:
805 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
806 CHREC_VARIABLE (e
), c
);
807 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
811 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
816 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
818 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
819 value_multiply (val
, val
, k
);
820 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
824 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
831 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
833 value_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
834 value_multiply (val
, val
, k
);
835 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
839 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
844 case POINTER_PLUS_EXPR
:
845 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
846 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
851 ppl_Linear_Expression_t tmp_expr
= NULL
;
855 ppl_dimension_type dim
;
856 ppl_Linear_Expression_space_dimension (c
, &dim
);
857 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
860 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
861 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
865 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
867 ppl_delete_Linear_Expression (tmp_expr
);
875 ppl_Linear_Expression_t tmp_expr
= NULL
;
879 ppl_dimension_type dim
;
880 ppl_Linear_Expression_space_dimension (c
, &dim
);
881 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
884 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
888 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
890 ppl_delete_Linear_Expression (tmp_expr
);
898 ppl_Linear_Expression_t tmp_expr
= NULL
;
902 ppl_dimension_type dim
;
903 ppl_Linear_Expression_space_dimension (c
, &dim
);
904 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
907 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
911 ppl_Coefficient_t coef
;
914 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
916 ppl_delete_Linear_Expression (tmp_expr
);
917 value_init (minus_one
);
918 value_set_si (minus_one
, -1);
919 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
920 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
921 value_clear (minus_one
);
922 ppl_delete_Coefficient (coef
);
930 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
934 ppl_dimension_type dim
;
935 ppl_Linear_Expression_space_dimension (c
, &dim
);
936 p
+= dim
- sese_nb_params (s
);
937 add_value_to_dim (p
, c
, k
);
944 scan_tree_for_params_int (e
, c
, k
);
948 case NON_LVALUE_EXPR
:
949 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
958 /* Find parameters with respect to REGION in BB. We are looking in memory
959 access functions, conditions and loop bounds. */
962 find_params_in_bb (sese region
, gimple_bb_p gbb
)
968 loop_p loop
= GBB_BB (gbb
)->loop_father
;
972 value_set_si (one
, 1);
974 /* Find parameters in the access functions of data references. */
975 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
976 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
977 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
979 /* Find parameters in conditional statements. */
980 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
982 tree lhs
= scalar_evolution_in_region (region
, loop
,
983 gimple_cond_lhs (stmt
));
984 tree rhs
= scalar_evolution_in_region (region
, loop
,
985 gimple_cond_rhs (stmt
));
987 scan_tree_for_params (region
, lhs
, NULL
, one
);
988 scan_tree_for_params (region
, rhs
, NULL
, one
);
994 /* Record the parameters used in the SCOP. A variable is a parameter
995 in a scop if it does not vary during the execution of that scop. */
998 find_scop_parameters (scop_p scop
)
1002 sese region
= SCOP_REGION (scop
);
1007 value_set_si (one
, 1);
1009 /* Find the parameters used in the loop bounds. */
1010 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1012 tree nb_iters
= number_of_latch_executions (loop
);
1014 if (!chrec_contains_symbols (nb_iters
))
1017 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1018 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1023 /* Find the parameters used in data accesses. */
1024 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1025 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1027 scop_set_nb_params (scop
, sese_nb_params (region
));
1028 SESE_ADD_PARAMS (region
) = false;
1031 /* Returns a gimple_bb from BB. */
1033 static inline gimple_bb_p
1034 gbb_from_bb (basic_block bb
)
1036 return (gimple_bb_p
) bb
->aux
;
1039 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1040 the constraints for the surrounding loops. */
1043 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1044 ppl_Polyhedron_t outer_ph
, int nb
)
1048 ppl_Polyhedron_t ph
;
1049 tree nb_iters
= number_of_latch_executions (loop
);
1050 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1051 sese region
= SCOP_REGION (scop
);
1054 ppl_const_Constraint_System_t pcs
;
1055 ppl_dimension_type
*map
1056 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1058 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1059 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1060 ppl_Polyhedron_add_constraints (ph
, pcs
);
1062 for (i
= 0; i
< (int) nb
; i
++)
1064 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1068 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1074 ppl_Constraint_t lb
;
1075 ppl_Linear_Expression_t lb_expr
;
1077 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1078 ppl_set_coef (lb_expr
, nb
, 1);
1079 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1080 ppl_delete_Linear_Expression (lb_expr
);
1081 ppl_Polyhedron_add_constraint (ph
, lb
);
1082 ppl_delete_Constraint (lb
);
1085 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1087 ppl_Constraint_t ub
;
1088 ppl_Linear_Expression_t ub_expr
;
1090 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1092 /* loop_i <= cst_nb_iters */
1093 ppl_set_coef (ub_expr
, nb
, -1);
1094 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1095 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1096 ppl_Polyhedron_add_constraint (ph
, ub
);
1097 ppl_delete_Linear_Expression (ub_expr
);
1098 ppl_delete_Constraint (ub
);
1100 else if (!chrec_contains_undetermined (nb_iters
))
1103 ppl_Constraint_t ub
;
1104 ppl_Linear_Expression_t ub_expr
;
1107 value_set_si (one
, 1);
1108 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1109 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1110 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1113 /* loop_i <= expr_nb_iters */
1114 ppl_set_coef (ub_expr
, nb
, -1);
1115 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1116 ppl_Polyhedron_add_constraint (ph
, ub
);
1117 ppl_delete_Linear_Expression (ub_expr
);
1118 ppl_delete_Constraint (ub
);
1123 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1124 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1);
1128 && loop_in_sese_p (loop
->next
, region
))
1129 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
);
1131 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1132 ((ppl_Pointset_Powerset_C_Polyhedron_t
*) &loop
->aux
, ph
);
1134 ppl_delete_Polyhedron (ph
);
1137 /* Returns a linear expression for tree T evaluated in PBB. */
1139 static ppl_Linear_Expression_t
1140 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1143 ppl_Linear_Expression_t res
;
1144 ppl_dimension_type dim
;
1145 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1146 loop_p loop
= GBB_BB (PBB_BLACK_BOX (pbb
))->loop_father
;
1148 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1149 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1151 t
= scalar_evolution_in_region (region
, loop
, t
);
1152 gcc_assert (!automatically_generated_chrec_p (t
));
1155 value_set_si (one
, 1);
1156 scan_tree_for_params (region
, t
, res
, one
);
1162 /* Returns the ppl constraint type from the gimple tree code CODE. */
1164 static enum ppl_enum_Constraint_Type
1165 ppl_constraint_type_from_tree_code (enum tree_code code
)
1169 /* We do not support LT and GT to be able to work with C_Polyhedron.
1170 As we work on integer polyhedron "a < b" can be expressed by
1177 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1180 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1183 return PPL_CONSTRAINT_TYPE_EQUAL
;
1190 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1191 CODE is used as the comparison operator. This allows us to invert the
1192 condition or to handle inequalities. */
1195 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1196 poly_bb_p pbb
, enum tree_code code
)
1199 ppl_Coefficient_t c
;
1200 ppl_Linear_Expression_t left
, right
;
1201 ppl_Constraint_t cstr
;
1202 enum ppl_enum_Constraint_Type type
;
1204 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1205 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1207 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1208 the left or the right side of the expression. */
1209 if (code
== LT_EXPR
)
1212 value_set_si (v
, 1);
1213 ppl_new_Coefficient (&c
);
1214 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1215 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1216 ppl_delete_Coefficient (c
);
1221 else if (code
== GT_EXPR
)
1224 value_set_si (v
, 1);
1225 ppl_new_Coefficient (&c
);
1226 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1227 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1228 ppl_delete_Coefficient (c
);
1234 type
= ppl_constraint_type_from_tree_code (code
);
1236 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1238 ppl_new_Constraint (&cstr
, left
, type
);
1239 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1241 ppl_delete_Constraint (cstr
);
1242 ppl_delete_Linear_Expression (left
);
1243 ppl_delete_Linear_Expression (right
);
1246 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1247 operator. This allows us to invert the condition or to handle
1251 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1253 if (code
== NE_EXPR
)
1255 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1256 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1257 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1259 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1260 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1261 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
,
1263 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1266 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1269 /* Add conditions to the domain of PBB. */
1272 add_conditions_to_domain (poly_bb_p pbb
)
1276 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1277 VEC (gimple
, heap
) *conditions
= GBB_CONDITIONS (gbb
);
1279 if (VEC_empty (gimple
, conditions
))
1282 for (i
= 0; VEC_iterate (gimple
, conditions
, i
, stmt
); i
++)
1283 switch (gimple_code (stmt
))
1287 enum tree_code code
= gimple_cond_code (stmt
);
1289 /* The conditions for ELSE-branches are inverted. */
1290 if (VEC_index (gimple
, gbb
->condition_cases
, i
) == NULL
)
1291 code
= invert_tree_comparison (code
, false);
1293 add_condition_to_pbb (pbb
, stmt
, code
);
1298 /* Switch statements are not supported right now - fall throught. */
1306 /* Structure used to pass data to dom_walk. */
1310 VEC (gimple
, heap
) **conditions
, **cases
;
1314 /* Returns non NULL when BB has a single predecessor and the last
1315 statement of that predecessor is a COND_EXPR. */
1318 single_pred_cond (basic_block bb
)
1320 if (single_pred_p (bb
))
1322 edge e
= single_pred_edge (bb
);
1323 basic_block pred
= e
->src
;
1324 gimple stmt
= last_stmt (pred
);
1326 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1332 /* Call-back for dom_walk executed before visiting the dominated
1336 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1339 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1340 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1341 VEC (gimple
, heap
) **cases
= data
->cases
;
1342 gimple_bb_p gbb
= gbb_from_bb (bb
);
1343 gimple stmt
= single_pred_cond (bb
);
1345 if (!bb_in_sese_p (bb
, data
->region
))
1350 edge e
= single_pred_edge (bb
);
1352 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1354 if (e
->flags
& EDGE_TRUE_VALUE
)
1355 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1357 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1362 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1363 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1367 /* Call-back for dom_walk executed after visiting the dominated
1371 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1374 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1375 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1376 VEC (gimple
, heap
) **cases
= data
->cases
;
1378 if (!bb_in_sese_p (bb
, data
->region
))
1381 if (single_pred_cond (bb
))
1383 VEC_pop (gimple
, *conditions
);
1384 VEC_pop (gimple
, *cases
);
1388 /* Record all conditions in REGION. */
1391 build_sese_conditions (sese region
)
1393 struct dom_walk_data walk_data
;
1394 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1395 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1398 data
.conditions
= &conditions
;
1399 data
.cases
= &cases
;
1400 data
.region
= region
;
1402 walk_data
.dom_direction
= CDI_DOMINATORS
;
1403 walk_data
.initialize_block_local_data
= NULL
;
1404 walk_data
.before_dom_children
= build_sese_conditions_before
;
1405 walk_data
.after_dom_children
= build_sese_conditions_after
;
1406 walk_data
.global_data
= &data
;
1407 walk_data
.block_local_data_size
= 0;
1409 init_walk_dominator_tree (&walk_data
);
1410 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1411 fini_walk_dominator_tree (&walk_data
);
1413 VEC_free (gimple
, heap
, conditions
);
1414 VEC_free (gimple
, heap
, cases
);
1417 /* Traverses all the GBBs of the SCOP and add their constraints to the
1418 iteration domains. */
1421 add_conditions_to_constraints (scop_p scop
)
1426 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1427 add_conditions_to_domain (pbb
);
1430 /* Add constraints on the possible values of parameter P from the type
1434 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1436 ppl_Constraint_t cstr
;
1437 ppl_Linear_Expression_t le
;
1438 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1439 tree type
= TREE_TYPE (parameter
);
1442 /* Disabled until we fix CPU2006. */
1445 if (!INTEGRAL_TYPE_P (type
))
1448 lb
= TYPE_MIN_VALUE (type
);
1449 ub
= TYPE_MAX_VALUE (type
);
1453 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1454 ppl_set_coef (le
, p
, -1);
1455 ppl_set_inhomogeneous_tree (le
, lb
);
1456 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1457 ppl_Polyhedron_add_constraint (context
, cstr
);
1458 ppl_delete_Linear_Expression (le
);
1459 ppl_delete_Constraint (cstr
);
1464 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1465 ppl_set_coef (le
, p
, -1);
1466 ppl_set_inhomogeneous_tree (le
, ub
);
1467 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1468 ppl_Polyhedron_add_constraint (context
, cstr
);
1469 ppl_delete_Linear_Expression (le
);
1470 ppl_delete_Constraint (cstr
);
1474 /* Build the context of the SCOP. The context usually contains extra
1475 constraints that are added to the iteration domains that constrain
1479 build_scop_context (scop_p scop
)
1481 ppl_Polyhedron_t context
;
1482 graphite_dim_t p
, n
= scop_nb_params (scop
);
1484 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1486 for (p
= 0; p
< n
; p
++)
1487 add_param_constraints (scop
, context
, p
);
1489 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1490 (&SCOP_CONTEXT (scop
), context
);
1492 ppl_delete_Polyhedron (context
);
1495 /* Build the iteration domains: the loops belonging to the current
1496 SCOP, and that vary for the execution of the current basic block.
1497 Returns false if there is no loop in SCOP. */
1500 build_scop_iteration_domain (scop_p scop
)
1503 sese region
= SCOP_REGION (scop
);
1505 ppl_Polyhedron_t ph
;
1508 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1510 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1511 if (!loop_in_sese_p (loop_outer (loop
), region
))
1512 build_loop_iteration_domains (scop
, loop
, ph
, 0);
1514 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1515 if (gbb_loop (PBB_BLACK_BOX (pbb
))->aux
)
1516 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1517 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1518 gbb_loop (PBB_BLACK_BOX (pbb
))->aux
);
1520 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1521 (&PBB_DOMAIN (pbb
), ph
);
1523 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1526 ppl_delete_Pointset_Powerset_C_Polyhedron
1527 ((ppl_Pointset_Powerset_C_Polyhedron_t
) loop
->aux
);
1531 ppl_delete_Polyhedron (ph
);
1534 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1535 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1536 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1540 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1541 ppl_dimension_type accessp_nb_dims
,
1542 ppl_dimension_type dom_nb_dims
)
1544 ppl_Linear_Expression_t alias
;
1545 ppl_Constraint_t cstr
;
1546 int alias_set_num
= 0;
1548 if (dr
->aux
!= NULL
)
1550 alias_set_num
= *((int *)(dr
->aux
));
1555 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1557 ppl_set_coef (alias
, dom_nb_dims
, 1);
1558 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1559 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1560 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1562 ppl_delete_Linear_Expression (alias
);
1563 ppl_delete_Constraint (cstr
);
1566 /* Add to ACCESSES polyhedron equalities defining the access functions
1567 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1568 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1569 PBB is the poly_bb_p that contains the data reference DR. */
1572 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1573 ppl_dimension_type accessp_nb_dims
,
1574 ppl_dimension_type dom_nb_dims
,
1577 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1579 scop_p scop
= PBB_SCOP (pbb
);
1580 sese region
= SCOP_REGION (scop
);
1584 for (i
= 0; i
< nb_subscripts
; i
++)
1586 ppl_Linear_Expression_t fn
, access
;
1587 ppl_Constraint_t cstr
;
1588 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1589 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1591 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1592 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1594 value_set_si (v
, 1);
1595 scan_tree_for_params (region
, afn
, fn
, v
);
1596 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1598 ppl_set_coef (access
, subscript
, -1);
1599 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1600 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1602 ppl_delete_Linear_Expression (fn
);
1603 ppl_delete_Linear_Expression (access
);
1604 ppl_delete_Constraint (cstr
);
1610 /* Add constrains representing the size of the accessed data to the
1611 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1612 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1616 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1617 ppl_dimension_type accessp_nb_dims
,
1618 ppl_dimension_type dom_nb_dims
)
1620 tree ref
= DR_REF (dr
);
1621 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1623 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1625 ppl_Linear_Expression_t expr
;
1626 ppl_Constraint_t cstr
;
1627 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1630 if (TREE_CODE (ref
) != ARRAY_REF
)
1633 low
= array_ref_low_bound (ref
);
1635 /* subscript - low >= 0 */
1636 if (host_integerp (low
, 0))
1638 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1639 ppl_set_coef (expr
, subscript
, 1);
1641 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1643 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1644 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1645 ppl_delete_Linear_Expression (expr
);
1646 ppl_delete_Constraint (cstr
);
1649 high
= array_ref_up_bound (ref
);
1651 /* high - subscript >= 0
1652 XXX: 1-element arrays at end of structures may extend over their
1654 if (high
&& host_integerp (high
, 0))
1656 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1657 ppl_set_coef (expr
, subscript
, -1);
1659 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1661 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1662 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1663 ppl_delete_Linear_Expression (expr
);
1664 ppl_delete_Constraint (cstr
);
1669 /* Build data accesses for DR in PBB. */
1672 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1674 ppl_Polyhedron_t accesses
;
1675 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1676 ppl_dimension_type dom_nb_dims
;
1677 ppl_dimension_type accessp_nb_dims
;
1679 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1681 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1683 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1685 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1686 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1687 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1689 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1691 ppl_delete_Polyhedron (accesses
);
1692 new_poly_dr (pbb
, accesses_ps
, DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
, dr
,
1693 DR_NUM_DIMENSIONS (dr
));
1696 /* Group each data reference in DRS with it's alias set num. */
1699 build_alias_set_for_drs (VEC (data_reference_p
, heap
) **drs
)
1701 int num_vertex
= VEC_length (data_reference_p
, *drs
);
1702 struct graph
*g
= new_graph (num_vertex
);
1703 data_reference_p dr1
, dr2
;
1708 for (i
= 0; VEC_iterate (data_reference_p
, *drs
, i
, dr1
); i
++)
1709 for (j
= i
+1; VEC_iterate (data_reference_p
, *drs
, j
, dr2
); j
++)
1710 if (dr_may_alias_p (dr1
, dr2
))
1716 queue
= XNEWVEC (int, num_vertex
);
1717 for (i
= 0; i
< num_vertex
; i
++)
1720 num_component
= graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1722 for (i
= 0; i
< g
->n_vertices
; i
++)
1724 data_reference_p dr
= VEC_index (data_reference_p
, *drs
, i
);
1725 dr
->aux
= XNEW (int);
1726 *((int *)(dr
->aux
)) = g
->vertices
[i
].component
+ 1;
1733 /* Build the data references for PBB. */
1736 build_pbb_drs (poly_bb_p pbb
)
1739 data_reference_p dr
;
1740 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1742 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1743 build_poly_dr (dr
, pbb
);
1746 /* Build data references in SCOP. */
1749 build_scop_drs (scop_p scop
)
1753 data_reference_p dr
;
1754 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
1756 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1758 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1759 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
1760 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
1763 build_alias_set_for_drs (&drs
);
1764 VEC_free (data_reference_p
, heap
, drs
);
1766 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1767 build_pbb_drs (pbb
);
1770 /* Return a gsi at the position of the VAR definition. */
1772 static gimple_stmt_iterator
1773 gsi_for_ssa_name_def (tree var
)
1777 gimple_stmt_iterator gsi
;
1778 gimple_stmt_iterator psi
;
1780 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
1782 stmt
= SSA_NAME_DEF_STMT (var
);
1783 bb
= gimple_bb (stmt
);
1785 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1786 if (stmt
== gsi_stmt (psi
))
1787 return gsi_after_labels (bb
);
1789 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1790 if (stmt
== gsi_stmt (gsi
))
1800 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
1803 insert_out_of_ssa_copy (tree res
, tree var
)
1805 gimple_stmt_iterator gsi
= gsi_for_ssa_name_def (var
);
1808 gimple_stmt_iterator si
;
1810 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
1811 stmt
= gimple_build_assign (res
, var
);
1813 stmts
= gimple_seq_alloc ();
1814 si
= gsi_last (stmts
);
1815 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
1816 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1819 /* Insert on edge E the assignment "RES := EXPR". */
1822 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
1824 gimple_stmt_iterator gsi
;
1826 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1827 gimple stmt
= gimple_build_assign (res
, var
);
1830 stmts
= gimple_seq_alloc ();
1832 gsi
= gsi_last (stmts
);
1833 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1834 gsi_insert_seq_on_edge (e
, stmts
);
1835 gsi_commit_edge_inserts ();
1838 /* Creates a zero dimension array of the same type as VAR. */
1841 create_zero_dim_array (tree var
)
1843 tree index_type
= build_index_type (integer_zero_node
);
1844 tree elt_type
= TREE_TYPE (var
);
1845 tree array_type
= build_array_type (elt_type
, index_type
);
1846 tree base
= create_tmp_var (array_type
, "Red");
1848 add_referenced_var (base
);
1850 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
1854 /* Returns true when PHI is a loop close phi node. */
1857 scalar_close_phi_node_p (gimple phi
)
1859 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
1861 if (!is_gimple_reg (gimple_phi_result (phi
)))
1864 return (gimple_phi_num_args (phi
) == 1);
1867 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1868 dimension array for it. */
1871 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1873 gimple phi
= gsi_stmt (*psi
);
1874 tree res
= gimple_phi_result (phi
);
1875 tree var
= SSA_NAME_VAR (res
);
1876 tree zero_dim_array
= create_zero_dim_array (var
);
1877 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
1878 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
1879 tree arg
= gimple_phi_arg_def (phi
, 0);
1881 insert_out_of_ssa_copy (zero_dim_array
, arg
);
1883 remove_phi_node (psi
, false);
1884 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1885 SSA_NAME_DEF_STMT (res
) = stmt
;
1888 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1889 dimension array for it. */
1892 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
1895 gimple phi
= gsi_stmt (*psi
);
1896 basic_block bb
= gimple_bb (phi
);
1897 tree res
= gimple_phi_result (phi
);
1898 tree var
= SSA_NAME_VAR (res
);
1899 tree zero_dim_array
= create_zero_dim_array (var
);
1900 gimple_stmt_iterator gsi
;
1904 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1906 tree arg
= gimple_phi_arg_def (phi
, i
);
1908 /* Try to avoid the insertion on edges as much as possible: this
1909 would avoid the insertion of code on loop latch edges, making
1910 the pattern matching of the vectorizer happy, or it would
1911 avoid the insertion of useless basic blocks. Note that it is
1912 incorrect to insert out of SSA copies close by their
1913 definition when they are more than two loop levels apart:
1914 for example, starting from a double nested loop
1924 the following transform is incorrect
1936 whereas inserting the copy on the incomming edge is correct
1948 if (TREE_CODE (arg
) == SSA_NAME
1949 && is_gimple_reg (arg
)
1950 && gimple_bb (SSA_NAME_DEF_STMT (arg
))
1951 && (flow_bb_inside_loop_p (bb
->loop_father
,
1952 gimple_bb (SSA_NAME_DEF_STMT (arg
)))
1953 || flow_bb_inside_loop_p (loop_outer (bb
->loop_father
),
1954 gimple_bb (SSA_NAME_DEF_STMT (arg
)))))
1955 insert_out_of_ssa_copy (zero_dim_array
, arg
);
1957 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi
, i
),
1958 zero_dim_array
, arg
);
1961 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
1964 stmts
= gimple_seq_alloc ();
1966 stmt
= gimple_build_assign (res
, var
);
1967 remove_phi_node (psi
, false);
1968 SSA_NAME_DEF_STMT (res
) = stmt
;
1970 gsi
= gsi_last (stmts
);
1971 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1973 gsi
= gsi_after_labels (bb
);
1974 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1977 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
1980 rewrite_reductions_out_of_ssa (scop_p scop
)
1983 gimple_stmt_iterator psi
;
1984 sese region
= SCOP_REGION (scop
);
1987 if (bb_in_region (bb
, SESE_ENTRY_BB (region
), SESE_EXIT_BB (region
)))
1988 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
1990 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
1991 rewrite_close_phi_out_of_ssa (&psi
);
1992 else if (reduction_phi_p (region
, &psi
))
1993 rewrite_phi_out_of_ssa (&psi
);
1996 update_ssa (TODO_update_ssa
);
1997 #ifdef ENABLE_CHECKING
1999 verify_loop_closed_ssa ();
2003 /* Returns the number of pbbs that are in loops contained in SCOP. */
2006 nb_pbbs_in_loops (scop_p scop
)
2012 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2013 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2019 /* Builds the polyhedral representation for a SESE region. */
2022 build_poly_scop (scop_p scop
)
2024 sese region
= SCOP_REGION (scop
);
2025 rewrite_reductions_out_of_ssa (scop
);
2026 build_scop_bbs (scop
);
2028 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2029 Once CLooG is fixed, remove this guard. Anyways, it makes no
2030 sense to optimize a scop containing only PBBs that do not belong
2032 if (nb_pbbs_in_loops (scop
) == 0)
2035 build_sese_loop_nests (region
);
2036 build_sese_conditions (region
);
2037 find_scop_parameters (scop
);
2039 build_scop_iteration_domain (scop
);
2040 build_scop_context (scop
);
2042 add_conditions_to_constraints (scop
);
2043 build_scop_scattering (scop
);
2044 build_scop_drs (scop
);
2049 /* Always return false. Exercise the scop_to_clast function. */
2052 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2054 #ifdef ENABLE_CHECKING
2055 cloog_prog_clast pc
= scop_to_clast (scop
);
2056 cloog_clast_free (pc
.stmt
);
2057 cloog_program_free (pc
.prog
);