1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-sese-to-poly.h"
55 /* Check if VAR is used in a phi node, that is no loop header. */
58 var_used_in_not_loop_header_phi_node (tree var
)
60 imm_use_iterator imm_iter
;
64 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, var
)
66 basic_block bb
= gimple_bb (stmt
);
68 if (gimple_code (stmt
) == GIMPLE_PHI
69 && bb
->loop_father
->header
!= bb
)
76 /* Returns the index of the PHI argument defined in the outermost
80 phi_arg_in_outermost_loop (gimple phi
)
82 loop_p loop
= gimple_bb (phi
)->loop_father
;
85 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
86 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
88 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
95 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
96 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
99 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
101 gimple phi
= gsi_stmt (*psi
);
102 tree res
= gimple_phi_result (phi
);
103 size_t entry
= phi_arg_in_outermost_loop (phi
);
104 tree init
= gimple_phi_arg_def (phi
, entry
);
105 gimple stmt
= gimple_build_assign (res
, init
);
106 edge e
= gimple_phi_arg_edge (phi
, entry
);
108 remove_phi_node (psi
, false);
109 gsi_insert_on_edge_immediate (e
, stmt
);
110 SSA_NAME_DEF_STMT (res
) = stmt
;
113 /* Removes an invariant phi node at position PSI by inserting on the
114 loop ENTRY edge the assignment RES = INIT. */
117 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
119 gimple phi
= gsi_stmt (*psi
);
120 loop_p loop
= loop_containing_stmt (phi
);
121 tree res
= gimple_phi_result (phi
);
122 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
123 size_t entry
= phi_arg_in_outermost_loop (phi
);
124 edge e
= gimple_phi_arg_edge (phi
, entry
);
128 gimple_stmt_iterator gsi
;
130 if (tree_contains_chrecs (scev
, NULL
))
131 scev
= gimple_phi_arg_def (phi
, entry
);
133 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
134 stmt
= gimple_build_assign (res
, var
);
135 remove_phi_node (psi
, false);
138 stmts
= gimple_seq_alloc ();
140 gsi
= gsi_last (stmts
);
141 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
142 gsi_insert_seq_on_edge (e
, stmts
);
143 gsi_commit_edge_inserts ();
144 SSA_NAME_DEF_STMT (res
) = stmt
;
147 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
150 simple_copy_phi_p (gimple phi
)
154 if (gimple_phi_num_args (phi
) != 2)
157 res
= gimple_phi_result (phi
);
158 return (res
== gimple_phi_arg_def (phi
, 0)
159 || res
== gimple_phi_arg_def (phi
, 1));
162 /* Returns true when the phi node at position PSI is a reduction phi
163 node in REGION. Otherwise moves the pointer PSI to the next phi to
167 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
172 gimple phi
= gsi_stmt (*psi
);
173 tree res
= gimple_phi_result (phi
);
175 if (!is_gimple_reg (res
))
181 loop
= loop_containing_stmt (phi
);
183 if (simple_copy_phi_p (phi
))
185 /* PRE introduces phi nodes like these, for an example,
186 see id-5.f in the fortran graphite testsuite:
188 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
190 remove_simple_copy_phi (psi
);
194 /* Main induction variables with constant strides in LOOP are not
196 if (simple_iv (loop
, loop
, res
, &iv
, true))
198 if (integer_zerop (iv
.step
))
199 remove_invariant_phi (region
, psi
);
206 scev
= scalar_evolution_in_region (region
, loop
, res
);
207 if (chrec_contains_undetermined (scev
))
210 if (evolution_function_is_invariant_p (scev
, loop
->num
))
212 remove_invariant_phi (region
, psi
);
216 /* All the other cases are considered reductions. */
220 /* Returns true when BB will be represented in graphite. Return false
221 for the basic blocks that contain code eliminated in the code
222 generation pass: i.e. induction variables and exit conditions. */
225 graphite_stmt_p (sese region
, basic_block bb
,
226 VEC (data_reference_p
, heap
) *drs
)
228 gimple_stmt_iterator gsi
;
229 loop_p loop
= bb
->loop_father
;
231 if (VEC_length (data_reference_p
, drs
) > 0)
234 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
236 gimple stmt
= gsi_stmt (gsi
);
238 switch (gimple_code (stmt
))
241 /* Control flow expressions can be ignored, as they are
242 represented in the iteration domains and will be
243 regenerated by graphite. */
251 tree var
= gimple_assign_lhs (stmt
);
253 /* We need these bbs to be able to construct the phi nodes. */
254 if (var_used_in_not_loop_header_phi_node (var
))
257 var
= scalar_evolution_in_region (region
, loop
, var
);
258 if (chrec_contains_undetermined (var
))
272 /* Store the GRAPHITE representation of BB. */
275 new_gimple_bb (basic_block bb
, VEC (data_reference_p
, heap
) *drs
)
277 struct gimple_bb
*gbb
;
279 gbb
= XNEW (struct gimple_bb
);
282 GBB_DATA_REFS (gbb
) = drs
;
283 GBB_CONDITIONS (gbb
) = NULL
;
284 GBB_CONDITION_CASES (gbb
) = NULL
;
290 free_data_refs_aux (VEC (data_reference_p
, heap
) *datarefs
)
293 struct data_reference
*dr
;
295 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
298 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
301 free (bap
->alias_set
);
310 free_gimple_bb (struct gimple_bb
*gbb
)
312 free_data_refs_aux (GBB_DATA_REFS (gbb
));
313 free_data_refs (GBB_DATA_REFS (gbb
));
315 VEC_free (gimple
, heap
, GBB_CONDITIONS (gbb
));
316 VEC_free (gimple
, heap
, GBB_CONDITION_CASES (gbb
));
317 GBB_BB (gbb
)->aux
= 0;
321 /* Deletes all gimple bbs in SCOP. */
324 remove_gbbs_in_scop (scop_p scop
)
329 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
330 free_gimple_bb (PBB_BLACK_BOX (pbb
));
333 /* Deletes all scops in SCOPS. */
336 free_scops (VEC (scop_p
, heap
) *scops
)
341 for (i
= 0; VEC_iterate (scop_p
, scops
, i
, scop
); i
++)
343 remove_gbbs_in_scop (scop
);
344 free_sese (SCOP_REGION (scop
));
348 VEC_free (scop_p
, heap
, scops
);
351 /* Generates a polyhedral black box only if the bb contains interesting
355 try_generate_gimple_bb (scop_p scop
, basic_block bb
, sbitmap reductions
)
357 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 5);
358 loop_p nest
= outermost_loop_in_sese (SCOP_REGION (scop
), bb
);
359 gimple_stmt_iterator gsi
;
361 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
363 gimple stmt
= gsi_stmt (gsi
);
364 if (!is_gimple_debug (stmt
))
365 graphite_find_data_references_in_stmt (nest
, stmt
, &drs
);
368 if (!graphite_stmt_p (SCOP_REGION (scop
), bb
, drs
))
369 free_data_refs (drs
);
371 new_poly_bb (scop
, new_gimple_bb (bb
, drs
), TEST_BIT (reductions
,
375 /* Returns true if all predecessors of BB, that are not dominated by BB, are
376 marked in MAP. The predecessors dominated by BB are loop latches and will
377 be handled after BB. */
380 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
385 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
386 if (!TEST_BIT (map
, e
->src
->index
)
387 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
393 /* Compare the depth of two basic_block's P1 and P2. */
396 compare_bb_depths (const void *p1
, const void *p2
)
398 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
399 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
400 int d1
= loop_depth (bb1
->loop_father
);
401 int d2
= loop_depth (bb2
->loop_father
);
412 /* Sort the basic blocks from DOM such that the first are the ones at
413 a deepest loop level. */
416 graphite_sort_dominated_info (VEC (basic_block
, heap
) *dom
)
418 size_t len
= VEC_length (basic_block
, dom
);
420 qsort (VEC_address (basic_block
, dom
), len
, sizeof (basic_block
),
424 /* Recursive helper function for build_scops_bbs. */
427 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
, sbitmap reductions
)
429 sese region
= SCOP_REGION (scop
);
430 VEC (basic_block
, heap
) *dom
;
432 if (TEST_BIT (visited
, bb
->index
)
433 || !bb_in_sese_p (bb
, region
))
436 try_generate_gimple_bb (scop
, bb
, reductions
);
437 SET_BIT (visited
, bb
->index
);
439 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
444 graphite_sort_dominated_info (dom
);
446 while (!VEC_empty (basic_block
, dom
))
451 for (i
= 0; VEC_iterate (basic_block
, dom
, i
, dom_bb
); i
++)
452 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
454 build_scop_bbs_1 (scop
, visited
, dom_bb
, reductions
);
455 VEC_unordered_remove (basic_block
, dom
, i
);
460 VEC_free (basic_block
, heap
, dom
);
463 /* Gather the basic blocks belonging to the SCOP. */
466 build_scop_bbs (scop_p scop
, sbitmap reductions
)
468 sbitmap visited
= sbitmap_alloc (last_basic_block
);
469 sese region
= SCOP_REGION (scop
);
471 sbitmap_zero (visited
);
472 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
), reductions
);
473 sbitmap_free (visited
);
476 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
477 We generate SCATTERING_DIMENSIONS scattering dimensions.
479 CLooG 0.15.0 and previous versions require, that all
480 scattering functions of one CloogProgram have the same number of
481 scattering dimensions, therefore we allow to specify it. This
482 should be removed in future versions of CLooG.
484 The scattering polyhedron consists of these dimensions: scattering,
485 loop_iterators, parameters.
489 | scattering_dimensions = 5
490 | used_scattering_dimensions = 3
498 | Scattering polyhedron:
500 | scattering: {s1, s2, s3, s4, s5}
501 | loop_iterators: {i}
502 | parameters: {p1, p2}
504 | s1 s2 s3 s4 s5 i p1 p2 1
505 | 1 0 0 0 0 0 0 0 -4 = 0
506 | 0 1 0 0 0 -1 0 0 0 = 0
507 | 0 0 1 0 0 0 0 0 -5 = 0 */
510 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule
,
511 poly_bb_p pbb
, int scattering_dimensions
)
514 scop_p scop
= PBB_SCOP (pbb
);
515 int nb_iterators
= pbb_dim_iter_domain (pbb
);
516 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
517 int nb_params
= scop_nb_params (scop
);
519 ppl_dimension_type dim
= scattering_dimensions
+ nb_iterators
+ nb_params
;
522 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
525 ppl_new_Coefficient (&c
);
526 PBB_TRANSFORMED (pbb
) = poly_scattering_new ();
527 ppl_new_C_Polyhedron_from_space_dimension
528 (&PBB_TRANSFORMED_SCATTERING (pbb
), dim
, 0);
530 PBB_NB_SCATTERING_TRANSFORM (pbb
) = scattering_dimensions
;
532 for (i
= 0; i
< scattering_dimensions
; i
++)
534 ppl_Constraint_t cstr
;
535 ppl_Linear_Expression_t expr
;
537 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
539 ppl_assign_Coefficient_from_mpz_t (c
, v
);
540 ppl_Linear_Expression_add_to_coefficient (expr
, i
, c
);
542 /* Textual order inside this loop. */
545 ppl_Linear_Expression_coefficient (static_schedule
, i
/ 2, c
);
546 ppl_Coefficient_to_mpz_t (c
, v
);
548 ppl_assign_Coefficient_from_mpz_t (c
, v
);
549 ppl_Linear_Expression_add_to_inhomogeneous (expr
, c
);
552 /* Iterations of this loop. */
553 else /* if ((i % 2) == 1) */
555 int loop
= (i
- 1) / 2;
558 ppl_assign_Coefficient_from_mpz_t (c
, v
);
559 ppl_Linear_Expression_add_to_coefficient
560 (expr
, scattering_dimensions
+ loop
, c
);
563 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
564 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb
), cstr
);
565 ppl_delete_Linear_Expression (expr
);
566 ppl_delete_Constraint (cstr
);
570 ppl_delete_Coefficient (c
);
572 PBB_ORIGINAL (pbb
) = poly_scattering_copy (PBB_TRANSFORMED (pbb
));
575 /* Build for BB the static schedule.
577 The static schedule is a Dewey numbering of the abstract syntax
578 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
580 The following example informally defines the static schedule:
599 Static schedules for A to F:
612 build_scop_scattering (scop_p scop
)
616 gimple_bb_p previous_gbb
= NULL
;
617 ppl_Linear_Expression_t static_schedule
;
622 ppl_new_Coefficient (&c
);
623 ppl_new_Linear_Expression (&static_schedule
);
625 /* We have to start schedules at 0 on the first component and
626 because we cannot compare_prefix_loops against a previous loop,
627 prefix will be equal to zero, and that index will be
628 incremented before copying. */
630 ppl_assign_Coefficient_from_mpz_t (c
, v
);
631 ppl_Linear_Expression_add_to_coefficient (static_schedule
, 0, c
);
633 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
635 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
636 ppl_Linear_Expression_t common
;
638 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
641 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
646 ppl_new_Linear_Expression_with_dimension (&common
, prefix
+ 1);
647 ppl_assign_Linear_Expression_from_Linear_Expression (common
,
651 ppl_assign_Coefficient_from_mpz_t (c
, v
);
652 ppl_Linear_Expression_add_to_coefficient (common
, prefix
, c
);
653 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule
,
656 build_pbb_scattering_polyhedrons (common
, pbb
, nb_scat_dims
);
658 ppl_delete_Linear_Expression (common
);
662 ppl_delete_Coefficient (c
);
663 ppl_delete_Linear_Expression (static_schedule
);
666 /* Add the value K to the dimension D of the linear expression EXPR. */
669 add_value_to_dim (ppl_dimension_type d
, ppl_Linear_Expression_t expr
,
673 ppl_Coefficient_t coef
;
675 ppl_new_Coefficient (&coef
);
676 ppl_Linear_Expression_coefficient (expr
, d
, coef
);
678 ppl_Coefficient_to_mpz_t (coef
, val
);
680 mpz_add (val
, val
, k
);
682 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
683 ppl_Linear_Expression_add_to_coefficient (expr
, d
, coef
);
685 ppl_delete_Coefficient (coef
);
688 /* In the context of scop S, scan E, the right hand side of a scalar
689 evolution function in loop VAR, and translate it to a linear
693 scan_tree_for_params_right_scev (sese s
, tree e
, int var
,
694 ppl_Linear_Expression_t expr
)
698 loop_p loop
= get_loop (var
);
699 ppl_dimension_type l
= sese_loop_depth (s
, loop
) - 1;
702 /* Scalar evolutions should happen in the sese region. */
703 gcc_assert (sese_loop_depth (s
, loop
) > 0);
705 /* We can not deal with parametric strides like:
711 gcc_assert (TREE_CODE (e
) == INTEGER_CST
);
714 mpz_set_si (val
, int_cst_value (e
));
715 add_value_to_dim (l
, expr
, val
);
720 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
721 linear expression EXPR. K is the multiplier of the constant. */
724 scan_tree_for_params_int (tree cst
, ppl_Linear_Expression_t expr
, mpz_t k
)
727 ppl_Coefficient_t coef
;
728 int v
= int_cst_value (cst
);
733 /* Necessary to not get "-1 = 2^n - 1". */
735 mpz_sub_ui (val
, val
, -v
);
737 mpz_add_ui (val
, val
, v
);
739 mpz_mul (val
, val
, k
);
740 ppl_new_Coefficient (&coef
);
741 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
742 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
744 ppl_delete_Coefficient (coef
);
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 VEC_safe_push (tree
, heap
, SESE_PARAMS (region
), name
);
787 /* In the context of sese S, scan the expression E and translate it to
788 a linear expression C. When parsing a symbolic multiplication, K
789 represents the constant multiplier of an expression containing
793 scan_tree_for_params (sese s
, tree e
, ppl_Linear_Expression_t c
,
796 if (e
== chrec_dont_know
)
799 switch (TREE_CODE (e
))
801 case POLYNOMIAL_CHREC
:
802 scan_tree_for_params_right_scev (s
, CHREC_RIGHT (e
),
803 CHREC_VARIABLE (e
), c
);
804 scan_tree_for_params (s
, CHREC_LEFT (e
), c
, k
);
808 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
813 gcc_assert (host_integerp (TREE_OPERAND (e
, 1), 0));
815 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 1)));
816 mpz_mul (val
, val
, k
);
817 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, val
);
821 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
828 gcc_assert (host_integerp (TREE_OPERAND (e
, 0), 0));
830 mpz_set_si (val
, int_cst_value (TREE_OPERAND (e
, 0)));
831 mpz_mul (val
, val
, k
);
832 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, val
);
836 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
841 case POINTER_PLUS_EXPR
:
842 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
843 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), c
, k
);
848 ppl_Linear_Expression_t tmp_expr
= NULL
;
852 ppl_dimension_type dim
;
853 ppl_Linear_Expression_space_dimension (c
, &dim
);
854 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
857 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
858 scan_tree_for_params (s
, TREE_OPERAND (e
, 1), tmp_expr
, k
);
862 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
864 ppl_delete_Linear_Expression (tmp_expr
);
872 ppl_Linear_Expression_t tmp_expr
= NULL
;
876 ppl_dimension_type dim
;
877 ppl_Linear_Expression_space_dimension (c
, &dim
);
878 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
881 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
885 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
887 ppl_delete_Linear_Expression (tmp_expr
);
895 ppl_Linear_Expression_t tmp_expr
= NULL
;
899 ppl_dimension_type dim
;
900 ppl_Linear_Expression_space_dimension (c
, &dim
);
901 ppl_new_Linear_Expression_with_dimension (&tmp_expr
, dim
);
904 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), tmp_expr
, k
);
908 ppl_Coefficient_t coef
;
911 ppl_subtract_Linear_Expression_from_Linear_Expression (c
,
913 ppl_delete_Linear_Expression (tmp_expr
);
914 mpz_init (minus_one
);
915 mpz_set_si (minus_one
, -1);
916 ppl_new_Coefficient_from_mpz_t (&coef
, minus_one
);
917 ppl_Linear_Expression_add_to_inhomogeneous (c
, coef
);
918 mpz_clear (minus_one
);
919 ppl_delete_Coefficient (coef
);
927 ppl_dimension_type p
= parameter_index_in_region (e
, s
);
931 ppl_dimension_type dim
;
932 ppl_Linear_Expression_space_dimension (c
, &dim
);
933 p
+= dim
- sese_nb_params (s
);
934 add_value_to_dim (p
, c
, k
);
941 scan_tree_for_params_int (e
, c
, k
);
945 case NON_LVALUE_EXPR
:
946 scan_tree_for_params (s
, TREE_OPERAND (e
, 0), c
, k
);
955 /* Find parameters with respect to REGION in BB. We are looking in memory
956 access functions, conditions and loop bounds. */
959 find_params_in_bb (sese region
, gimple_bb_p gbb
)
965 loop_p loop
= GBB_BB (gbb
)->loop_father
;
971 /* Find parameters in the access functions of data references. */
972 for (i
= 0; VEC_iterate (data_reference_p
, GBB_DATA_REFS (gbb
), i
, dr
); i
++)
973 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
974 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
), NULL
, one
);
976 /* Find parameters in conditional statements. */
977 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
979 tree lhs
= scalar_evolution_in_region (region
, loop
,
980 gimple_cond_lhs (stmt
));
981 tree rhs
= scalar_evolution_in_region (region
, loop
,
982 gimple_cond_rhs (stmt
));
984 scan_tree_for_params (region
, lhs
, NULL
, one
);
985 scan_tree_for_params (region
, rhs
, NULL
, one
);
991 /* Record the parameters used in the SCOP. A variable is a parameter
992 in a scop if it does not vary during the execution of that scop. */
995 find_scop_parameters (scop_p scop
)
999 sese region
= SCOP_REGION (scop
);
1004 mpz_set_si (one
, 1);
1006 /* Find the parameters used in the loop bounds. */
1007 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1009 tree nb_iters
= number_of_latch_executions (loop
);
1011 if (!chrec_contains_symbols (nb_iters
))
1014 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1015 scan_tree_for_params (region
, nb_iters
, NULL
, one
);
1020 /* Find the parameters used in data accesses. */
1021 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1022 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
1024 scop_set_nb_params (scop
, sese_nb_params (region
));
1025 SESE_ADD_PARAMS (region
) = false;
1027 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1028 (&SCOP_CONTEXT (scop
), scop_nb_params (scop
), 0);
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 /* Insert in the SCOP context constraints from the estimation of the
1040 number of iterations. UB_EXPR is a linear expression describing
1041 the number of iterations in a loop. This expression is bounded by
1042 the estimation NIT. */
1045 add_upper_bounds_from_estimated_nit (scop_p scop
, double_int nit
,
1046 ppl_dimension_type dim
,
1047 ppl_Linear_Expression_t ub_expr
)
1050 ppl_Linear_Expression_t nb_iters_le
;
1051 ppl_Polyhedron_t pol
;
1052 ppl_Coefficient_t coef
;
1053 ppl_Constraint_t ub
;
1055 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1056 ppl_new_C_Polyhedron_from_space_dimension (&pol
, dim
, 0);
1057 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le
,
1060 /* Construct the negated number of last iteration in VAL. */
1062 mpz_set_double_int (val
, nit
, false);
1063 mpz_sub_ui (val
, val
, 1);
1066 /* NB_ITERS_LE holds the number of last iteration in
1067 parametrical form. Subtract estimated number of last
1068 iteration and assert that result is not positive. */
1069 ppl_new_Coefficient_from_mpz_t (&coef
, val
);
1070 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le
, coef
);
1071 ppl_delete_Coefficient (coef
);
1072 ppl_new_Constraint (&ub
, nb_iters_le
,
1073 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1074 ppl_Polyhedron_add_constraint (pol
, ub
);
1076 /* Remove all but last GDIM dimensions from POL to obtain
1077 only the constraints on the parameters. */
1079 graphite_dim_t gdim
= scop_nb_params (scop
);
1080 ppl_dimension_type
*dims
= XNEWVEC (ppl_dimension_type
, dim
- gdim
);
1083 for (i
= 0; i
< dim
- gdim
; i
++)
1086 ppl_Polyhedron_remove_space_dimensions (pol
, dims
, dim
- gdim
);
1090 /* Add the constraints on the parameters to the SCoP context. */
1092 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps
;
1094 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1095 (&constraints_ps
, pol
);
1096 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1097 (SCOP_CONTEXT (scop
), constraints_ps
);
1098 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps
);
1101 ppl_delete_Polyhedron (pol
);
1102 ppl_delete_Linear_Expression (nb_iters_le
);
1103 ppl_delete_Constraint (ub
);
1107 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1108 the constraints for the surrounding loops. */
1111 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1112 ppl_Polyhedron_t outer_ph
, int nb
,
1113 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
)
1116 ppl_Polyhedron_t ph
;
1117 tree nb_iters
= number_of_latch_executions (loop
);
1118 ppl_dimension_type dim
= nb
+ 1 + scop_nb_params (scop
);
1119 sese region
= SCOP_REGION (scop
);
1122 ppl_const_Constraint_System_t pcs
;
1123 ppl_dimension_type
*map
1124 = (ppl_dimension_type
*) XNEWVEC (ppl_dimension_type
, dim
);
1126 ppl_new_C_Polyhedron_from_space_dimension (&ph
, dim
, 0);
1127 ppl_Polyhedron_get_constraints (outer_ph
, &pcs
);
1128 ppl_Polyhedron_add_constraints (ph
, pcs
);
1130 for (i
= 0; i
< (int) nb
; i
++)
1132 for (i
= (int) nb
; i
< (int) dim
- 1; i
++)
1136 ppl_Polyhedron_map_space_dimensions (ph
, map
, dim
);
1142 ppl_Constraint_t lb
;
1143 ppl_Linear_Expression_t lb_expr
;
1145 ppl_new_Linear_Expression_with_dimension (&lb_expr
, dim
);
1146 ppl_set_coef (lb_expr
, nb
, 1);
1147 ppl_new_Constraint (&lb
, lb_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1148 ppl_delete_Linear_Expression (lb_expr
);
1149 ppl_Polyhedron_add_constraint (ph
, lb
);
1150 ppl_delete_Constraint (lb
);
1153 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1155 ppl_Constraint_t ub
;
1156 ppl_Linear_Expression_t ub_expr
;
1158 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1160 /* loop_i <= cst_nb_iters */
1161 ppl_set_coef (ub_expr
, nb
, -1);
1162 ppl_set_inhomogeneous_tree (ub_expr
, nb_iters
);
1163 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1164 ppl_Polyhedron_add_constraint (ph
, ub
);
1165 ppl_delete_Linear_Expression (ub_expr
);
1166 ppl_delete_Constraint (ub
);
1168 else if (!chrec_contains_undetermined (nb_iters
))
1171 ppl_Constraint_t ub
;
1172 ppl_Linear_Expression_t ub_expr
;
1176 mpz_set_si (one
, 1);
1177 ppl_new_Linear_Expression_with_dimension (&ub_expr
, dim
);
1178 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1179 scan_tree_for_params (SCOP_REGION (scop
), nb_iters
, ub_expr
, one
);
1182 if (estimated_loop_iterations (loop
, true, &nit
))
1183 add_upper_bounds_from_estimated_nit (scop
, nit
, dim
, ub_expr
);
1185 /* loop_i <= expr_nb_iters */
1186 ppl_set_coef (ub_expr
, nb
, -1);
1187 ppl_new_Constraint (&ub
, ub_expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1188 ppl_Polyhedron_add_constraint (ph
, ub
);
1189 ppl_delete_Linear_Expression (ub_expr
);
1190 ppl_delete_Constraint (ub
);
1195 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1196 build_loop_iteration_domains (scop
, loop
->inner
, ph
, nb
+ 1, domains
);
1200 && loop_in_sese_p (loop
->next
, region
))
1201 build_loop_iteration_domains (scop
, loop
->next
, outer_ph
, nb
, domains
);
1203 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1204 (&domains
[loop
->num
], ph
);
1206 ppl_delete_Polyhedron (ph
);
1209 /* Returns a linear expression for tree T evaluated in PBB. */
1211 static ppl_Linear_Expression_t
1212 create_linear_expr_from_tree (poly_bb_p pbb
, tree t
)
1215 ppl_Linear_Expression_t res
;
1216 ppl_dimension_type dim
;
1217 sese region
= SCOP_REGION (PBB_SCOP (pbb
));
1218 loop_p loop
= pbb_loop (pbb
);
1220 dim
= pbb_dim_iter_domain (pbb
) + pbb_nb_params (pbb
);
1221 ppl_new_Linear_Expression_with_dimension (&res
, dim
);
1223 t
= scalar_evolution_in_region (region
, loop
, t
);
1224 gcc_assert (!automatically_generated_chrec_p (t
));
1227 mpz_set_si (one
, 1);
1228 scan_tree_for_params (region
, t
, res
, one
);
1234 /* Returns the ppl constraint type from the gimple tree code CODE. */
1236 static enum ppl_enum_Constraint_Type
1237 ppl_constraint_type_from_tree_code (enum tree_code code
)
1241 /* We do not support LT and GT to be able to work with C_Polyhedron.
1242 As we work on integer polyhedron "a < b" can be expressed by
1249 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
;
1252 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
;
1255 return PPL_CONSTRAINT_TYPE_EQUAL
;
1262 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1263 CODE is used as the comparison operator. This allows us to invert the
1264 condition or to handle inequalities. */
1267 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps
, gimple stmt
,
1268 poly_bb_p pbb
, enum tree_code code
)
1271 ppl_Coefficient_t c
;
1272 ppl_Linear_Expression_t left
, right
;
1273 ppl_Constraint_t cstr
;
1274 enum ppl_enum_Constraint_Type type
;
1276 left
= create_linear_expr_from_tree (pbb
, gimple_cond_lhs (stmt
));
1277 right
= create_linear_expr_from_tree (pbb
, gimple_cond_rhs (stmt
));
1279 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1280 the left or the right side of the expression. */
1281 if (code
== LT_EXPR
)
1285 ppl_new_Coefficient (&c
);
1286 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1287 ppl_Linear_Expression_add_to_inhomogeneous (left
, c
);
1288 ppl_delete_Coefficient (c
);
1293 else if (code
== GT_EXPR
)
1297 ppl_new_Coefficient (&c
);
1298 ppl_assign_Coefficient_from_mpz_t (c
, v
);
1299 ppl_Linear_Expression_add_to_inhomogeneous (right
, c
);
1300 ppl_delete_Coefficient (c
);
1306 type
= ppl_constraint_type_from_tree_code (code
);
1308 ppl_subtract_Linear_Expression_from_Linear_Expression (left
, right
);
1310 ppl_new_Constraint (&cstr
, left
, type
);
1311 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps
, cstr
);
1313 ppl_delete_Constraint (cstr
);
1314 ppl_delete_Linear_Expression (left
);
1315 ppl_delete_Linear_Expression (right
);
1318 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1319 operator. This allows us to invert the condition or to handle
1323 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1325 if (code
== NE_EXPR
)
1327 ppl_Pointset_Powerset_C_Polyhedron_t left
= PBB_DOMAIN (pbb
);
1328 ppl_Pointset_Powerset_C_Polyhedron_t right
;
1329 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1331 add_condition_to_domain (left
, stmt
, pbb
, LT_EXPR
);
1332 add_condition_to_domain (right
, stmt
, pbb
, GT_EXPR
);
1333 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left
, right
);
1334 ppl_delete_Pointset_Powerset_C_Polyhedron (right
);
1337 add_condition_to_domain (PBB_DOMAIN (pbb
), stmt
, pbb
, code
);
1340 /* Add conditions to the domain of PBB. */
1343 add_conditions_to_domain (poly_bb_p pbb
)
1347 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1349 if (VEC_empty (gimple
, GBB_CONDITIONS (gbb
)))
1352 for (i
= 0; VEC_iterate (gimple
, GBB_CONDITIONS (gbb
), i
, stmt
); i
++)
1353 switch (gimple_code (stmt
))
1357 enum tree_code code
= gimple_cond_code (stmt
);
1359 /* The conditions for ELSE-branches are inverted. */
1360 if (!VEC_index (gimple
, GBB_CONDITION_CASES (gbb
), i
))
1361 code
= invert_tree_comparison (code
, false);
1363 add_condition_to_pbb (pbb
, stmt
, code
);
1368 /* Switch statements are not supported right now - fall throught. */
1376 /* Structure used to pass data to dom_walk. */
1380 VEC (gimple
, heap
) **conditions
, **cases
;
1384 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1385 edge between BB and its predecessor is not a loop exit edge, and
1386 the last statement of the single predecessor is a COND_EXPR. */
1389 single_pred_cond_non_loop_exit (basic_block bb
)
1391 if (single_pred_p (bb
))
1393 edge e
= single_pred_edge (bb
);
1394 basic_block pred
= e
->src
;
1397 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1400 stmt
= last_stmt (pred
);
1402 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1409 /* Call-back for dom_walk executed before visiting the dominated
1413 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1416 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1417 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1418 VEC (gimple
, heap
) **cases
= data
->cases
;
1422 if (!bb_in_sese_p (bb
, data
->region
))
1425 stmt
= single_pred_cond_non_loop_exit (bb
);
1429 edge e
= single_pred_edge (bb
);
1431 VEC_safe_push (gimple
, heap
, *conditions
, stmt
);
1433 if (e
->flags
& EDGE_TRUE_VALUE
)
1434 VEC_safe_push (gimple
, heap
, *cases
, stmt
);
1436 VEC_safe_push (gimple
, heap
, *cases
, NULL
);
1439 gbb
= gbb_from_bb (bb
);
1443 GBB_CONDITIONS (gbb
) = VEC_copy (gimple
, heap
, *conditions
);
1444 GBB_CONDITION_CASES (gbb
) = VEC_copy (gimple
, heap
, *cases
);
1448 /* Call-back for dom_walk executed after visiting the dominated
1452 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1455 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1456 VEC (gimple
, heap
) **conditions
= data
->conditions
;
1457 VEC (gimple
, heap
) **cases
= data
->cases
;
1459 if (!bb_in_sese_p (bb
, data
->region
))
1462 if (single_pred_cond_non_loop_exit (bb
))
1464 VEC_pop (gimple
, *conditions
);
1465 VEC_pop (gimple
, *cases
);
1469 /* Record all conditions in REGION. */
1472 build_sese_conditions (sese region
)
1474 struct dom_walk_data walk_data
;
1475 VEC (gimple
, heap
) *conditions
= VEC_alloc (gimple
, heap
, 3);
1476 VEC (gimple
, heap
) *cases
= VEC_alloc (gimple
, heap
, 3);
1479 data
.conditions
= &conditions
;
1480 data
.cases
= &cases
;
1481 data
.region
= region
;
1483 walk_data
.dom_direction
= CDI_DOMINATORS
;
1484 walk_data
.initialize_block_local_data
= NULL
;
1485 walk_data
.before_dom_children
= build_sese_conditions_before
;
1486 walk_data
.after_dom_children
= build_sese_conditions_after
;
1487 walk_data
.global_data
= &data
;
1488 walk_data
.block_local_data_size
= 0;
1490 init_walk_dominator_tree (&walk_data
);
1491 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1492 fini_walk_dominator_tree (&walk_data
);
1494 VEC_free (gimple
, heap
, conditions
);
1495 VEC_free (gimple
, heap
, cases
);
1498 /* Traverses all the GBBs of the SCOP and add their constraints to the
1499 iteration domains. */
1502 add_conditions_to_constraints (scop_p scop
)
1507 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1508 add_conditions_to_domain (pbb
);
1511 /* Add constraints on the possible values of parameter P from the type
1515 add_param_constraints (scop_p scop
, ppl_Polyhedron_t context
, graphite_dim_t p
)
1517 ppl_Constraint_t cstr
;
1518 ppl_Linear_Expression_t le
;
1519 tree parameter
= VEC_index (tree
, SESE_PARAMS (SCOP_REGION (scop
)), p
);
1520 tree type
= TREE_TYPE (parameter
);
1521 tree lb
= NULL_TREE
;
1522 tree ub
= NULL_TREE
;
1524 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1525 lb
= lower_bound_in_type (type
, type
);
1527 lb
= TYPE_MIN_VALUE (type
);
1529 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1530 ub
= upper_bound_in_type (type
, type
);
1532 ub
= TYPE_MAX_VALUE (type
);
1536 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1537 ppl_set_coef (le
, p
, -1);
1538 ppl_set_inhomogeneous_tree (le
, lb
);
1539 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
);
1540 ppl_Polyhedron_add_constraint (context
, cstr
);
1541 ppl_delete_Linear_Expression (le
);
1542 ppl_delete_Constraint (cstr
);
1547 ppl_new_Linear_Expression_with_dimension (&le
, scop_nb_params (scop
));
1548 ppl_set_coef (le
, p
, -1);
1549 ppl_set_inhomogeneous_tree (le
, ub
);
1550 ppl_new_Constraint (&cstr
, le
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1551 ppl_Polyhedron_add_constraint (context
, cstr
);
1552 ppl_delete_Linear_Expression (le
);
1553 ppl_delete_Constraint (cstr
);
1557 /* Build the context of the SCOP. The context usually contains extra
1558 constraints that are added to the iteration domains that constrain
1562 build_scop_context (scop_p scop
)
1564 ppl_Polyhedron_t context
;
1565 ppl_Pointset_Powerset_C_Polyhedron_t ps
;
1566 graphite_dim_t p
, n
= scop_nb_params (scop
);
1568 ppl_new_C_Polyhedron_from_space_dimension (&context
, n
, 0);
1570 for (p
= 0; p
< n
; p
++)
1571 add_param_constraints (scop
, context
, p
);
1573 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1575 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1576 (SCOP_CONTEXT (scop
), ps
);
1578 ppl_delete_Pointset_Powerset_C_Polyhedron (ps
);
1579 ppl_delete_Polyhedron (context
);
1582 /* Build the iteration domains: the loops belonging to the current
1583 SCOP, and that vary for the execution of the current basic block.
1584 Returns false if there is no loop in SCOP. */
1587 build_scop_iteration_domain (scop_p scop
)
1590 sese region
= SCOP_REGION (scop
);
1592 ppl_Polyhedron_t ph
;
1594 int nb_loops
= number_of_loops ();
1595 ppl_Pointset_Powerset_C_Polyhedron_t
*domains
1596 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t
, nb_loops
);
1598 for (i
= 0; i
< nb_loops
; i
++)
1601 ppl_new_C_Polyhedron_from_space_dimension (&ph
, scop_nb_params (scop
), 0);
1603 for (i
= 0; VEC_iterate (loop_p
, SESE_LOOP_NEST (region
), i
, loop
); i
++)
1604 if (!loop_in_sese_p (loop_outer (loop
), region
))
1605 build_loop_iteration_domains (scop
, loop
, ph
, 0, domains
);
1607 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
1608 if (domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
])
1609 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1610 (&PBB_DOMAIN (pbb
), (ppl_const_Pointset_Powerset_C_Polyhedron_t
)
1611 domains
[gbb_loop (PBB_BLACK_BOX (pbb
))->num
]);
1613 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1614 (&PBB_DOMAIN (pbb
), ph
);
1616 for (i
= 0; i
< nb_loops
; i
++)
1618 ppl_delete_Pointset_Powerset_C_Polyhedron (domains
[i
]);
1620 ppl_delete_Polyhedron (ph
);
1624 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1625 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1626 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1630 pdr_add_alias_set (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1631 ppl_dimension_type accessp_nb_dims
,
1632 ppl_dimension_type dom_nb_dims
)
1634 ppl_Linear_Expression_t alias
;
1635 ppl_Constraint_t cstr
;
1636 int alias_set_num
= 0;
1637 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1639 if (bap
&& bap
->alias_set
)
1640 alias_set_num
= *(bap
->alias_set
);
1642 ppl_new_Linear_Expression_with_dimension (&alias
, accessp_nb_dims
);
1644 ppl_set_coef (alias
, dom_nb_dims
, 1);
1645 ppl_set_inhomogeneous (alias
, -alias_set_num
);
1646 ppl_new_Constraint (&cstr
, alias
, PPL_CONSTRAINT_TYPE_EQUAL
);
1647 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1649 ppl_delete_Linear_Expression (alias
);
1650 ppl_delete_Constraint (cstr
);
1653 /* Add to ACCESSES polyhedron equalities defining the access functions
1654 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1655 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1656 PBB is the poly_bb_p that contains the data reference DR. */
1659 pdr_add_memory_accesses (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1660 ppl_dimension_type accessp_nb_dims
,
1661 ppl_dimension_type dom_nb_dims
,
1664 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1666 scop_p scop
= PBB_SCOP (pbb
);
1667 sese region
= SCOP_REGION (scop
);
1671 for (i
= 0; i
< nb_subscripts
; i
++)
1673 ppl_Linear_Expression_t fn
, access
;
1674 ppl_Constraint_t cstr
;
1675 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1676 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1678 ppl_new_Linear_Expression_with_dimension (&fn
, dom_nb_dims
);
1679 ppl_new_Linear_Expression_with_dimension (&access
, accessp_nb_dims
);
1682 scan_tree_for_params (region
, afn
, fn
, v
);
1683 ppl_assign_Linear_Expression_from_Linear_Expression (access
, fn
);
1685 ppl_set_coef (access
, subscript
, -1);
1686 ppl_new_Constraint (&cstr
, access
, PPL_CONSTRAINT_TYPE_EQUAL
);
1687 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1689 ppl_delete_Linear_Expression (fn
);
1690 ppl_delete_Linear_Expression (access
);
1691 ppl_delete_Constraint (cstr
);
1697 /* Add constrains representing the size of the accessed data to the
1698 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1699 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1703 pdr_add_data_dimensions (ppl_Polyhedron_t accesses
, data_reference_p dr
,
1704 ppl_dimension_type accessp_nb_dims
,
1705 ppl_dimension_type dom_nb_dims
)
1707 tree ref
= DR_REF (dr
);
1708 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1710 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1712 ppl_Linear_Expression_t expr
;
1713 ppl_Constraint_t cstr
;
1714 ppl_dimension_type subscript
= dom_nb_dims
+ 1 + i
;
1717 if (TREE_CODE (ref
) != ARRAY_REF
)
1720 low
= array_ref_low_bound (ref
);
1722 /* subscript - low >= 0 */
1723 if (host_integerp (low
, 0))
1725 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1726 ppl_set_coef (expr
, subscript
, 1);
1728 ppl_set_inhomogeneous (expr
, -int_cst_value (low
));
1730 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1731 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1732 ppl_delete_Linear_Expression (expr
);
1733 ppl_delete_Constraint (cstr
);
1736 high
= array_ref_up_bound (ref
);
1738 /* high - subscript >= 0 */
1739 if (high
&& host_integerp (high
, 0)
1740 /* 1-element arrays at end of structures may extend over
1741 their declared size. */
1742 && !(array_at_struct_end_p (ref
)
1743 && operand_equal_p (low
, high
, 0)))
1745 ppl_new_Linear_Expression_with_dimension (&expr
, accessp_nb_dims
);
1746 ppl_set_coef (expr
, subscript
, -1);
1748 ppl_set_inhomogeneous (expr
, int_cst_value (high
));
1750 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
1751 ppl_Polyhedron_add_constraint (accesses
, cstr
);
1752 ppl_delete_Linear_Expression (expr
);
1753 ppl_delete_Constraint (cstr
);
1758 /* Build data accesses for DR in PBB. */
1761 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1763 ppl_Polyhedron_t accesses
;
1764 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps
;
1765 ppl_dimension_type dom_nb_dims
;
1766 ppl_dimension_type accessp_nb_dims
;
1767 int dr_base_object_set
;
1769 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb
),
1771 accessp_nb_dims
= dom_nb_dims
+ 1 + DR_NUM_DIMENSIONS (dr
);
1773 ppl_new_C_Polyhedron_from_space_dimension (&accesses
, accessp_nb_dims
, 0);
1775 pdr_add_alias_set (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1776 pdr_add_memory_accesses (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
, pbb
);
1777 pdr_add_data_dimensions (accesses
, dr
, accessp_nb_dims
, dom_nb_dims
);
1779 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps
,
1781 ppl_delete_Polyhedron (accesses
);
1783 gcc_assert (dr
->aux
);
1784 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1786 new_poly_dr (pbb
, dr_base_object_set
, accesses_ps
,
1787 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1788 dr
, DR_NUM_DIMENSIONS (dr
));
1791 /* Write to FILE the alias graph of data references in DIMACS format. */
1794 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1795 VEC (data_reference_p
, heap
) *drs
)
1797 int num_vertex
= VEC_length (data_reference_p
, drs
);
1799 data_reference_p dr1
, dr2
;
1802 if (num_vertex
== 0)
1805 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1806 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1807 if (dr_may_alias_p (dr1
, dr2
))
1810 fprintf (file
, "$\n");
1813 fprintf (file
, "c %s\n", comment
);
1815 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1817 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1818 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1819 if (dr_may_alias_p (dr1
, dr2
))
1820 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1825 /* Write to FILE the alias graph of data references in DOT format. */
1828 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1829 VEC (data_reference_p
, heap
) *drs
)
1831 int num_vertex
= VEC_length (data_reference_p
, drs
);
1832 data_reference_p dr1
, dr2
;
1835 if (num_vertex
== 0)
1838 fprintf (file
, "$\n");
1841 fprintf (file
, "c %s\n", comment
);
1843 /* First print all the vertices. */
1844 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1845 fprintf (file
, "n%d;\n", i
);
1847 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1848 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1849 if (dr_may_alias_p (dr1
, dr2
))
1850 fprintf (file
, "n%d n%d\n", i
, j
);
1855 /* Write to FILE the alias graph of data references in ECC format. */
1858 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1859 VEC (data_reference_p
, heap
) *drs
)
1861 int num_vertex
= VEC_length (data_reference_p
, drs
);
1862 data_reference_p dr1
, dr2
;
1865 if (num_vertex
== 0)
1868 fprintf (file
, "$\n");
1871 fprintf (file
, "c %s\n", comment
);
1873 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1874 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1875 if (dr_may_alias_p (dr1
, dr2
))
1876 fprintf (file
, "%d %d\n", i
, j
);
1881 /* Check if DR1 and DR2 are in the same object set. */
1884 dr_same_base_object_p (const struct data_reference
*dr1
,
1885 const struct data_reference
*dr2
)
1887 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1890 /* Uses DFS component number as representative of alias-sets. Also tests for
1891 optimality by verifying if every connected component is a clique. Returns
1892 true (1) if the above test is true, and false (0) otherwise. */
1895 build_alias_set_optimal_p (VEC (data_reference_p
, heap
) *drs
)
1897 int num_vertices
= VEC_length (data_reference_p
, drs
);
1898 struct graph
*g
= new_graph (num_vertices
);
1899 data_reference_p dr1
, dr2
;
1901 int num_connected_components
;
1902 int v_indx1
, v_indx2
, num_vertices_in_component
;
1905 struct graph_edge
*e
;
1906 int this_component_is_clique
;
1907 int all_components_are_cliques
= 1;
1909 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1910 for (j
= i
+1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1911 if (dr_may_alias_p (dr1
, dr2
))
1917 all_vertices
= XNEWVEC (int, num_vertices
);
1918 vertices
= XNEWVEC (int, num_vertices
);
1919 for (i
= 0; i
< num_vertices
; i
++)
1920 all_vertices
[i
] = i
;
1922 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1924 for (i
= 0; i
< g
->n_vertices
; i
++)
1926 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
1927 base_alias_pair
*bap
;
1929 gcc_assert (dr
->aux
);
1930 bap
= (base_alias_pair
*)(dr
->aux
);
1932 bap
->alias_set
= XNEW (int);
1933 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1936 /* Verify if the DFS numbering results in optimal solution. */
1937 for (i
= 0; i
< num_connected_components
; i
++)
1939 num_vertices_in_component
= 0;
1940 /* Get all vertices whose DFS component number is the same as i. */
1941 for (j
= 0; j
< num_vertices
; j
++)
1942 if (g
->vertices
[j
].component
== i
)
1943 vertices
[num_vertices_in_component
++] = j
;
1945 /* Now test if the vertices in 'vertices' form a clique, by testing
1946 for edges among each pair. */
1947 this_component_is_clique
= 1;
1948 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1950 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1952 /* Check if the two vertices are connected by iterating
1953 through all the edges which have one of these are source. */
1954 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1957 if (e
->src
== vertices
[v_indx1
])
1963 this_component_is_clique
= 0;
1967 if (!this_component_is_clique
)
1968 all_components_are_cliques
= 0;
1972 free (all_vertices
);
1975 return all_components_are_cliques
;
1978 /* Group each data reference in DRS with it's base object set num. */
1981 build_base_obj_set_for_drs (VEC (data_reference_p
, heap
) *drs
)
1983 int num_vertex
= VEC_length (data_reference_p
, drs
);
1984 struct graph
*g
= new_graph (num_vertex
);
1985 data_reference_p dr1
, dr2
;
1989 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr1
); i
++)
1990 for (j
= i
+ 1; VEC_iterate (data_reference_p
, drs
, j
, dr2
); j
++)
1991 if (dr_same_base_object_p (dr1
, dr2
))
1997 queue
= XNEWVEC (int, num_vertex
);
1998 for (i
= 0; i
< num_vertex
; i
++)
2001 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
2003 for (i
= 0; i
< g
->n_vertices
; i
++)
2005 data_reference_p dr
= VEC_index (data_reference_p
, drs
, i
);
2006 base_alias_pair
*bap
;
2008 gcc_assert (dr
->aux
);
2009 bap
= (base_alias_pair
*)(dr
->aux
);
2011 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
2018 /* Build the data references for PBB. */
2021 build_pbb_drs (poly_bb_p pbb
)
2024 data_reference_p dr
;
2025 VEC (data_reference_p
, heap
) *gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
2027 for (j
= 0; VEC_iterate (data_reference_p
, gbb_drs
, j
, dr
); j
++)
2028 build_poly_dr (dr
, pbb
);
2031 /* Dump to file the alias graphs for the data references in DRS. */
2034 dump_alias_graphs (VEC (data_reference_p
, heap
) *drs
)
2037 FILE *file_dimacs
, *file_ecc
, *file_dot
;
2039 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2042 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2043 current_function_name ());
2044 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
2045 fclose (file_dimacs
);
2048 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
2051 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2052 current_function_name ());
2053 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
2057 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
2060 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
2061 current_function_name ());
2062 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
2067 /* Build data references in SCOP. */
2070 build_scop_drs (scop_p scop
)
2074 data_reference_p dr
;
2075 VEC (data_reference_p
, heap
) *drs
= VEC_alloc (data_reference_p
, heap
, 3);
2077 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2078 for (j
= 0; VEC_iterate (data_reference_p
,
2079 GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)), j
, dr
); j
++)
2080 VEC_safe_push (data_reference_p
, heap
, drs
, dr
);
2082 for (i
= 0; VEC_iterate (data_reference_p
, drs
, i
, dr
); i
++)
2083 dr
->aux
= XNEW (base_alias_pair
);
2085 if (!build_alias_set_optimal_p (drs
))
2087 /* TODO: Add support when building alias set is not optimal. */
2091 build_base_obj_set_for_drs (drs
);
2093 /* When debugging, enable the following code. This cannot be used
2094 in production compilers. */
2096 dump_alias_graphs (drs
);
2098 VEC_free (data_reference_p
, heap
, drs
);
2100 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2101 build_pbb_drs (pbb
);
2104 /* Return a gsi at the position of the phi node STMT. */
2106 static gimple_stmt_iterator
2107 gsi_for_phi_node (gimple stmt
)
2109 gimple_stmt_iterator psi
;
2110 basic_block bb
= gimple_bb (stmt
);
2112 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2113 if (stmt
== gsi_stmt (psi
))
2120 /* Insert the assignment "RES := VAR" just after AFTER_STMT. */
2123 insert_out_of_ssa_copy (tree res
, tree var
, gimple after_stmt
)
2127 gimple_stmt_iterator si
;
2128 gimple_stmt_iterator gsi
;
2130 var
= force_gimple_operand (var
, &stmts
, true, NULL_TREE
);
2131 stmt
= gimple_build_assign (res
, var
);
2133 stmts
= gimple_seq_alloc ();
2134 si
= gsi_last (stmts
);
2135 gsi_insert_after (&si
, stmt
, GSI_NEW_STMT
);
2137 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2139 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2140 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2144 gsi
= gsi_for_stmt (after_stmt
);
2145 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2149 /* Insert on edge E the assignment "RES := EXPR". */
2152 insert_out_of_ssa_copy_on_edge (edge e
, tree res
, tree expr
)
2154 gimple_stmt_iterator gsi
;
2156 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2157 gimple stmt
= gimple_build_assign (res
, var
);
2160 stmts
= gimple_seq_alloc ();
2162 gsi
= gsi_last (stmts
);
2163 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2164 gsi_insert_seq_on_edge (e
, stmts
);
2165 gsi_commit_edge_inserts ();
2168 /* Creates a zero dimension array of the same type as VAR. */
2171 create_zero_dim_array (tree var
, const char *base_name
)
2173 tree index_type
= build_index_type (integer_zero_node
);
2174 tree elt_type
= TREE_TYPE (var
);
2175 tree array_type
= build_array_type (elt_type
, index_type
);
2176 tree base
= create_tmp_var (array_type
, base_name
);
2178 add_referenced_var (base
);
2180 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2184 /* Returns true when PHI is a loop close phi node. */
2187 scalar_close_phi_node_p (gimple phi
)
2189 if (gimple_code (phi
) != GIMPLE_PHI
2190 || !is_gimple_reg (gimple_phi_result (phi
)))
2193 /* Note that loop close phi nodes should have a single argument
2194 because we translated the representation into a canonical form
2195 before Graphite: see canonicalize_loop_closed_ssa_form. */
2196 return (gimple_phi_num_args (phi
) == 1);
2199 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2200 dimension array for it. */
2203 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2205 gimple phi
= gsi_stmt (*psi
);
2206 tree res
= gimple_phi_result (phi
);
2207 tree var
= SSA_NAME_VAR (res
);
2208 tree zero_dim_array
= create_zero_dim_array (var
, "Close_Phi");
2209 gimple_stmt_iterator gsi
= gsi_after_labels (gimple_bb (phi
));
2210 gimple stmt
= gimple_build_assign (res
, zero_dim_array
);
2211 tree arg
= gimple_phi_arg_def (phi
, 0);
2213 /* Note that loop close phi nodes should have a single argument
2214 because we translated the representation into a canonical form
2215 before Graphite: see canonicalize_loop_closed_ssa_form. */
2216 gcc_assert (gimple_phi_num_args (phi
) == 1);
2218 if (TREE_CODE (arg
) == SSA_NAME
2219 && !SSA_NAME_IS_DEFAULT_DEF (arg
))
2220 insert_out_of_ssa_copy (zero_dim_array
, arg
, SSA_NAME_DEF_STMT (arg
));
2222 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi
)),
2223 zero_dim_array
, arg
);
2225 remove_phi_node (psi
, false);
2226 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2227 SSA_NAME_DEF_STMT (res
) = stmt
;
2230 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2231 dimension array for it. */
2234 rewrite_phi_out_of_ssa (gimple_stmt_iterator
*psi
)
2237 gimple phi
= gsi_stmt (*psi
);
2238 basic_block bb
= gimple_bb (phi
);
2239 tree res
= gimple_phi_result (phi
);
2240 tree var
= SSA_NAME_VAR (res
);
2241 tree zero_dim_array
= create_zero_dim_array (var
, "phi_out_of_ssa");
2242 gimple_stmt_iterator gsi
;
2246 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2248 tree arg
= gimple_phi_arg_def (phi
, i
);
2249 edge e
= gimple_phi_arg_edge (phi
, i
);
2251 /* Avoid the insertion of code in the loop latch to please the
2252 pattern matching of the vectorizer. */
2253 if (e
->src
== bb
->loop_father
->latch
)
2254 insert_out_of_ssa_copy (zero_dim_array
, arg
, SSA_NAME_DEF_STMT (arg
));
2256 insert_out_of_ssa_copy_on_edge (e
, zero_dim_array
, arg
);
2259 var
= force_gimple_operand (zero_dim_array
, &stmts
, true, NULL_TREE
);
2262 stmts
= gimple_seq_alloc ();
2264 stmt
= gimple_build_assign (res
, var
);
2265 remove_phi_node (psi
, false);
2266 SSA_NAME_DEF_STMT (res
) = stmt
;
2268 gsi
= gsi_last (stmts
);
2269 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
2271 gsi
= gsi_after_labels (bb
);
2272 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2275 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2278 rewrite_reductions_out_of_ssa (scop_p scop
)
2281 gimple_stmt_iterator psi
;
2282 sese region
= SCOP_REGION (scop
);
2285 if (bb_in_sese_p (bb
, region
))
2286 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2288 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2289 rewrite_close_phi_out_of_ssa (&psi
);
2290 else if (reduction_phi_p (region
, &psi
))
2291 rewrite_phi_out_of_ssa (&psi
);
2294 update_ssa (TODO_update_ssa
);
2295 #ifdef ENABLE_CHECKING
2296 verify_loop_closed_ssa (true);
2300 /* Return true when DEF can be analyzed in REGION by the scalar
2301 evolution analyzer. */
2304 scev_analyzable_p (tree def
, sese region
)
2306 gimple stmt
= SSA_NAME_DEF_STMT (def
);
2307 loop_p loop
= loop_containing_stmt (stmt
);
2308 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2310 return !chrec_contains_undetermined (scev
)
2311 && TREE_CODE (scev
) != SSA_NAME
;
2314 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2315 read from ZERO_DIM_ARRAY. */
2318 rewrite_cross_bb_scalar_dependence (tree zero_dim_array
, tree def
, gimple use_stmt
)
2320 tree var
= SSA_NAME_VAR (def
);
2321 gimple name_stmt
= gimple_build_assign (var
, zero_dim_array
);
2322 tree name
= make_ssa_name (var
, name_stmt
);
2324 use_operand_p use_p
;
2325 gimple_stmt_iterator gsi
;
2327 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2329 gimple_assign_set_lhs (name_stmt
, name
);
2331 gsi
= gsi_for_stmt (use_stmt
);
2332 gsi_insert_before (&gsi
, name_stmt
, GSI_NEW_STMT
);
2334 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2335 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2336 replace_exp (use_p
, name
);
2338 update_stmt (use_stmt
);
2341 /* Rewrite the scalar dependences crossing the boundary of the BB
2342 containing STMT with an array. GSI points to a definition that is
2343 used in a PHI node. */
2346 rewrite_cross_bb_phi_deps (sese region
, gimple_stmt_iterator gsi
)
2348 gimple stmt
= gsi_stmt (gsi
);
2349 imm_use_iterator imm_iter
;
2354 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2357 def
= gimple_assign_lhs (stmt
);
2358 if (!is_gimple_reg (def
)
2359 || scev_analyzable_p (def
, region
))
2362 def_bb
= gimple_bb (stmt
);
2364 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2365 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2367 gimple_stmt_iterator si
= gsi_for_stmt (use_stmt
);
2368 rewrite_phi_out_of_ssa (&si
);
2372 /* Rewrite the scalar dependences crossing the boundary of the BB
2373 containing STMT with an array. */
2376 rewrite_cross_bb_scalar_deps (sese region
, gimple_stmt_iterator
*gsi
)
2378 gimple stmt
= gsi_stmt (*gsi
);
2379 imm_use_iterator imm_iter
;
2382 tree zero_dim_array
= NULL_TREE
;
2385 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2388 def
= gimple_assign_lhs (stmt
);
2389 if (!is_gimple_reg (def
)
2390 || scev_analyzable_p (def
, region
))
2393 def_bb
= gimple_bb (stmt
);
2395 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2396 if (def_bb
!= gimple_bb (use_stmt
)
2397 && !is_gimple_debug (use_stmt
))
2399 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2401 if (!zero_dim_array
)
2403 zero_dim_array
= create_zero_dim_array
2404 (SSA_NAME_VAR (def
), "Cross_BB_scalar_dependence");
2405 insert_out_of_ssa_copy (zero_dim_array
, def
,
2406 SSA_NAME_DEF_STMT (def
));
2410 rewrite_cross_bb_scalar_dependence (zero_dim_array
, def
, use_stmt
);
2414 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2417 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2420 gimple_stmt_iterator psi
;
2421 sese region
= SCOP_REGION (scop
);
2424 if (bb_in_sese_p (bb
, region
))
2425 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2427 rewrite_cross_bb_phi_deps (region
, psi
);
2428 rewrite_cross_bb_scalar_deps (region
, &psi
);
2431 update_ssa (TODO_update_ssa
);
2432 #ifdef ENABLE_CHECKING
2433 verify_loop_closed_ssa (true);
2437 /* Returns the number of pbbs that are in loops contained in SCOP. */
2440 nb_pbbs_in_loops (scop_p scop
)
2446 for (i
= 0; VEC_iterate (poly_bb_p
, SCOP_BBS (scop
), i
, pbb
); i
++)
2447 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2453 /* Return the number of data references in BB that write in
2457 nb_data_writes_in_bb (basic_block bb
)
2460 gimple_stmt_iterator gsi
;
2462 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2463 if (gimple_vdef (gsi_stmt (gsi
)))
2469 /* Splits STMT out of its current BB. */
2472 split_reduction_stmt (gimple stmt
)
2474 gimple_stmt_iterator gsi
;
2475 basic_block bb
= gimple_bb (stmt
);
2478 /* Do not split basic blocks with no writes to memory: the reduction
2479 will be the only write to memory. */
2480 if (nb_data_writes_in_bb (bb
) == 0)
2483 split_block (bb
, stmt
);
2485 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2488 gsi
= gsi_last_bb (bb
);
2490 e
= split_block (bb
, gsi_stmt (gsi
));
2495 /* Return true when stmt is a reduction operation. */
2498 is_reduction_operation_p (gimple stmt
)
2500 enum tree_code code
;
2502 gcc_assert (is_gimple_assign (stmt
));
2503 code
= gimple_assign_rhs_code (stmt
);
2505 return flag_associative_math
2506 && commutative_tree_code (code
)
2507 && associative_tree_code (code
);
2510 /* Returns true when PHI contains an argument ARG. */
2513 phi_contains_arg (gimple phi
, tree arg
)
2517 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2518 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2524 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2527 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2531 if (TREE_CODE (arg
) != SSA_NAME
)
2534 stmt
= SSA_NAME_DEF_STMT (arg
);
2536 if (gimple_code (stmt
) == GIMPLE_NOP
2537 || gimple_code (stmt
) == GIMPLE_CALL
)
2540 if (gimple_code (stmt
) == GIMPLE_PHI
)
2542 if (phi_contains_arg (stmt
, lhs
))
2547 if (!is_gimple_assign (stmt
))
2550 if (gimple_num_ops (stmt
) == 2)
2551 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2553 if (is_reduction_operation_p (stmt
))
2555 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2558 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2564 /* Detect commutative and associative scalar reductions starting at
2565 the STMT. Return the phi node of the reduction cycle, or NULL. */
2568 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2569 VEC (gimple
, heap
) **in
,
2570 VEC (gimple
, heap
) **out
)
2572 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2577 VEC_safe_push (gimple
, heap
, *in
, stmt
);
2578 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2582 /* Detect commutative and associative scalar reductions starting at
2583 STMT. Return the phi node of the reduction cycle, or NULL. */
2586 detect_commutative_reduction_assign (gimple stmt
, VEC (gimple
, heap
) **in
,
2587 VEC (gimple
, heap
) **out
)
2589 tree lhs
= gimple_assign_lhs (stmt
);
2591 if (gimple_num_ops (stmt
) == 2)
2592 return detect_commutative_reduction_arg (lhs
, stmt
,
2593 gimple_assign_rhs1 (stmt
),
2596 if (is_reduction_operation_p (stmt
))
2598 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2599 gimple_assign_rhs1 (stmt
),
2602 : detect_commutative_reduction_arg (lhs
, stmt
,
2603 gimple_assign_rhs2 (stmt
),
2610 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2613 follow_inital_value_to_phi (tree arg
, tree lhs
)
2617 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2620 stmt
= SSA_NAME_DEF_STMT (arg
);
2622 if (gimple_code (stmt
) == GIMPLE_PHI
2623 && phi_contains_arg (stmt
, lhs
))
2630 /* Return the argument of the loop PHI that is the inital value coming
2631 from outside the loop. */
2634 edge_initial_value_for_loop_phi (gimple phi
)
2638 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2640 edge e
= gimple_phi_arg_edge (phi
, i
);
2642 if (loop_depth (e
->src
->loop_father
)
2643 < loop_depth (e
->dest
->loop_father
))
2650 /* Return the argument of the loop PHI that is the inital value coming
2651 from outside the loop. */
2654 initial_value_for_loop_phi (gimple phi
)
2658 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2660 edge e
= gimple_phi_arg_edge (phi
, i
);
2662 if (loop_depth (e
->src
->loop_father
)
2663 < loop_depth (e
->dest
->loop_father
))
2664 return gimple_phi_arg_def (phi
, i
);
2670 /* Detect commutative and associative scalar reductions starting at
2671 the loop closed phi node STMT. Return the phi node of the
2672 reduction cycle, or NULL. */
2675 detect_commutative_reduction (gimple stmt
, VEC (gimple
, heap
) **in
,
2676 VEC (gimple
, heap
) **out
)
2678 if (scalar_close_phi_node_p (stmt
))
2680 tree arg
= gimple_phi_arg_def (stmt
, 0);
2681 gimple def
, loop_phi
;
2683 if (TREE_CODE (arg
) != SSA_NAME
)
2686 /* Note that loop close phi nodes should have a single argument
2687 because we translated the representation into a canonical form
2688 before Graphite: see canonicalize_loop_closed_ssa_form. */
2689 gcc_assert (gimple_phi_num_args (stmt
) == 1);
2691 def
= SSA_NAME_DEF_STMT (arg
);
2692 loop_phi
= detect_commutative_reduction (def
, in
, out
);
2696 tree lhs
= gimple_phi_result (stmt
);
2697 tree init
= initial_value_for_loop_phi (loop_phi
);
2698 gimple phi
= follow_inital_value_to_phi (init
, lhs
);
2700 VEC_safe_push (gimple
, heap
, *in
, loop_phi
);
2701 VEC_safe_push (gimple
, heap
, *out
, stmt
);
2708 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2709 return detect_commutative_reduction_assign (stmt
, in
, out
);
2714 /* Translate the scalar reduction statement STMT to an array RED
2715 knowing that its recursive phi node is LOOP_PHI. */
2718 translate_scalar_reduction_to_array_for_stmt (tree red
, gimple stmt
,
2721 gimple_stmt_iterator insert_gsi
= gsi_after_labels (gimple_bb (loop_phi
));
2722 tree res
= gimple_phi_result (loop_phi
);
2723 gimple assign
= gimple_build_assign (res
, red
);
2725 gsi_insert_before (&insert_gsi
, assign
, GSI_SAME_STMT
);
2727 insert_gsi
= gsi_after_labels (gimple_bb (stmt
));
2728 assign
= gimple_build_assign (red
, gimple_assign_lhs (stmt
));
2729 insert_gsi
= gsi_for_stmt (stmt
);
2730 gsi_insert_after (&insert_gsi
, assign
, GSI_SAME_STMT
);
2733 /* Removes the PHI node and resets all the debug stmts that are using
2737 remove_phi (gimple phi
)
2739 imm_use_iterator imm_iter
;
2741 use_operand_p use_p
;
2742 gimple_stmt_iterator gsi
;
2743 VEC (gimple
, heap
) *update
= VEC_alloc (gimple
, heap
, 3);
2747 def
= PHI_RESULT (phi
);
2748 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2750 stmt
= USE_STMT (use_p
);
2752 if (is_gimple_debug (stmt
))
2754 gimple_debug_bind_reset_value (stmt
);
2755 VEC_safe_push (gimple
, heap
, update
, stmt
);
2759 for (i
= 0; VEC_iterate (gimple
, update
, i
, stmt
); i
++)
2762 VEC_free (gimple
, heap
, update
);
2764 gsi
= gsi_for_phi_node (phi
);
2765 remove_phi_node (&gsi
, false);
2768 /* Rewrite out of SSA the reduction described by the loop phi nodes
2769 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2772 IN: stmt, loop_n, ..., loop_0
2773 OUT: stmt, close_n, ..., close_0
2775 the first element is the reduction statement, and the next elements
2776 are the loop and close phi nodes of each of the outer loops. */
2779 translate_scalar_reduction_to_array (VEC (gimple
, heap
) *in
,
2780 VEC (gimple
, heap
) *out
,
2785 tree red
= NULL_TREE
;
2787 for (i
= 0; VEC_iterate (gimple
, in
, i
, loop_phi
); i
++)
2789 gimple close_phi
= VEC_index (gimple
, out
, i
);
2793 gimple stmt
= loop_phi
;
2794 basic_block bb
= split_reduction_stmt (stmt
);
2796 SET_BIT (reductions
, bb
->index
);
2797 gcc_assert (close_phi
== loop_phi
);
2799 red
= create_zero_dim_array
2800 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2801 translate_scalar_reduction_to_array_for_stmt
2802 (red
, stmt
, VEC_index (gimple
, in
, 1));
2806 if (i
== VEC_length (gimple
, in
) - 1)
2808 insert_out_of_ssa_copy (gimple_phi_result (close_phi
), red
,
2810 insert_out_of_ssa_copy_on_edge
2811 (edge_initial_value_for_loop_phi (loop_phi
),
2812 red
, initial_value_for_loop_phi (loop_phi
));
2815 remove_phi (loop_phi
);
2816 remove_phi (close_phi
);
2820 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2823 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi
,
2826 VEC (gimple
, heap
) *in
= VEC_alloc (gimple
, heap
, 10);
2827 VEC (gimple
, heap
) *out
= VEC_alloc (gimple
, heap
, 10);
2829 detect_commutative_reduction (close_phi
, &in
, &out
);
2830 if (VEC_length (gimple
, in
) > 0)
2831 translate_scalar_reduction_to_array (in
, out
, reductions
);
2833 VEC_free (gimple
, heap
, in
);
2834 VEC_free (gimple
, heap
, out
);
2837 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2840 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop
,
2843 gimple_stmt_iterator gsi
;
2844 edge exit
= single_exit (loop
);
2849 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2850 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi
),
2854 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2857 rewrite_commutative_reductions_out_of_ssa (sese region
, sbitmap reductions
)
2862 if (!flag_associative_math
)
2865 FOR_EACH_LOOP (li
, loop
, 0)
2866 if (loop_in_sese_p (loop
, region
))
2867 rewrite_commutative_reductions_out_of_ssa_loop (loop
, reductions
);
2869 gsi_commit_edge_inserts ();
2870 update_ssa (TODO_update_ssa
);
2871 #ifdef ENABLE_CHECKING
2872 verify_loop_closed_ssa (true);
2876 /* A LOOP is in normal form for Graphite when it contains only one
2877 scalar phi node that defines the main induction variable of the
2878 loop, only one increment of the IV, and only one exit condition. */
2881 graphite_loop_normal_form (loop_p loop
)
2883 struct tree_niter_desc niter
;
2886 edge exit
= single_dom_exit (loop
);
2888 bool known_niter
= number_of_iterations_exit (loop
, exit
, &niter
, false);
2890 /* At this point we should know the number of iterations. */
2891 gcc_assert (known_niter
);
2893 nit
= force_gimple_operand (unshare_expr (niter
.niter
), &stmts
, true,
2896 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2898 loop
->single_iv
= canonicalize_loop_ivs (loop
, &nit
, false);
2901 /* Rewrite all the loops of SCOP in normal form: one induction
2902 variable per loop. */
2905 scop_canonicalize_loops (scop_p scop
)
2910 FOR_EACH_LOOP (li
, loop
, 0)
2911 if (loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2912 graphite_loop_normal_form (loop
);
2915 /* Java does not initialize long_long_integer_type_node. */
2916 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2918 /* Can all ivs be represented by a signed integer?
2919 As CLooG might generate negative values in its expressions, signed loop ivs
2920 are required in the backend. */
2923 scop_ivs_can_be_represented (scop_p scop
)
2928 FOR_EACH_LOOP (li
, loop
, 0)
2933 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
2936 if (!loop
->single_iv
)
2939 type
= TREE_TYPE (loop
->single_iv
);
2940 precision
= TYPE_PRECISION (type
);
2942 if (TYPE_UNSIGNED (type
)
2943 && precision
>= TYPE_PRECISION (my_long_long
))
2952 /* Builds the polyhedral representation for a SESE region. */
2955 build_poly_scop (scop_p scop
)
2957 sese region
= SCOP_REGION (scop
);
2958 graphite_dim_t max_dim
;
2961 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2962 Once CLooG is fixed, remove this guard. Anyways, it makes no
2963 sense to optimize a scop containing only PBBs that do not belong
2965 if (nb_pbbs_in_loops (scop
) == 0)
2968 scop_canonicalize_loops (scop
);
2969 if (!scop_ivs_can_be_represented (scop
))
2972 build_sese_loop_nests (region
);
2973 build_sese_conditions (region
);
2974 find_scop_parameters (scop
);
2976 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2977 if (scop_nb_params (scop
) > max_dim
)
2980 build_scop_iteration_domain (scop
);
2981 build_scop_context (scop
);
2983 add_conditions_to_constraints (scop
);
2985 build_scop_scattering (scop
);
2986 build_scop_drs (scop
);
2988 /* This SCoP has been translated to the polyhedral
2990 POLY_SCOP_P (scop
) = true;
2993 /* Always return false. Exercise the scop_to_clast function. */
2996 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED
)
2998 #ifdef ENABLE_CHECKING
2999 cloog_prog_clast pc
= scop_to_clast (scop
);
3000 cloog_clast_free (pc
.stmt
);
3001 cloog_program_free (pc
.prog
);