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 the degenerate phi node at position PSI from the degenerate
2276 form "x = phi (y, y, ..., y)" to "x = y". */
2279 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2283 gimple_stmt_iterator gsi;
2284 gimple phi = gsi_stmt (*psi);
2285 tree res = gimple_phi_result (phi);
2288 if (!is_gimple_reg (res))
2294 bb = gimple_bb (phi);
2295 rhs = degenerate_phi_result (phi);
2298 stmt = gimple_build_assign (res, rhs);
2299 remove_phi_node (psi, false);
2300 SSA_NAME_DEF_STMT (res) = stmt;
2302 gsi = gsi_after_labels (bb);
2303 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2306 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2309 rewrite_reductions_out_of_ssa (scop_p scop)
2312 gimple_stmt_iterator psi;
2313 sese region = SCOP_REGION (scop);
2316 if (bb_in_sese_p (bb, region))
2317 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2319 gimple phi = gsi_stmt (psi);
2321 if (gimple_phi_num_args (phi) > 1
2322 && degenerate_phi_result (phi))
2323 rewrite_degenerate_phi (&psi);
2325 else if (scalar_close_phi_node_p (phi))
2326 rewrite_close_phi_out_of_ssa (&psi);
2328 else if (reduction_phi_p (region, &psi))
2329 rewrite_phi_out_of_ssa (&psi);
2332 update_ssa (TODO_update_ssa);
2333 #ifdef ENABLE_CHECKING
2334 verify_loop_closed_ssa (true);
2338 /* Return true when DEF can be analyzed in REGION by the scalar
2339 evolution analyzer. */
2342 scev_analyzable_p (tree def, sese region)
2344 gimple stmt = SSA_NAME_DEF_STMT (def);
2345 loop_p loop = loop_containing_stmt (stmt);
2346 tree scev = scalar_evolution_in_region (region, loop, def);
2348 return !chrec_contains_undetermined (scev)
2349 && TREE_CODE (scev) != SSA_NAME;
2352 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2353 read from ZERO_DIM_ARRAY. */
2356 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2358 tree var = SSA_NAME_VAR (def);
2359 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2360 tree name = make_ssa_name (var, name_stmt);
2362 use_operand_p use_p;
2363 gimple_stmt_iterator gsi;
2365 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2367 gimple_assign_set_lhs (name_stmt, name);
2369 gsi = gsi_for_stmt (use_stmt);
2370 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2372 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2373 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2374 replace_exp (use_p, name);
2376 update_stmt (use_stmt);
2379 /* Rewrite the scalar dependences crossing the boundary of the BB
2380 containing STMT with an array. GSI points to a definition that is
2381 used in a PHI node. */
2384 rewrite_cross_bb_phi_deps (sese region, gimple_stmt_iterator gsi)
2386 gimple stmt = gsi_stmt (gsi);
2387 imm_use_iterator imm_iter;
2391 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2394 def = gimple_assign_lhs (stmt);
2395 if (!is_gimple_reg (def)
2396 || scev_analyzable_p (def, region))
2399 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2400 if (gimple_code (use_stmt) == GIMPLE_PHI)
2402 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2404 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2405 rewrite_close_phi_out_of_ssa (&psi);
2407 rewrite_phi_out_of_ssa (&psi);
2411 /* Rewrite the scalar dependences crossing the boundary of the BB
2412 containing STMT with an array. */
2415 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2417 gimple stmt = gsi_stmt (*gsi);
2418 imm_use_iterator imm_iter;
2421 tree zero_dim_array = NULL_TREE;
2424 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2427 def = gimple_assign_lhs (stmt);
2428 if (!is_gimple_reg (def)
2429 || scev_analyzable_p (def, region))
2432 def_bb = gimple_bb (stmt);
2434 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2435 if (def_bb != gimple_bb (use_stmt)
2436 && !is_gimple_debug (use_stmt))
2438 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2440 if (!zero_dim_array)
2442 zero_dim_array = create_zero_dim_array
2443 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2444 insert_out_of_ssa_copy (zero_dim_array, def,
2445 SSA_NAME_DEF_STMT (def));
2449 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2453 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2456 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2459 gimple_stmt_iterator psi;
2460 sese region = SCOP_REGION (scop);
2463 if (bb_in_sese_p (bb, region))
2464 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2466 rewrite_cross_bb_phi_deps (region, psi);
2467 rewrite_cross_bb_scalar_deps (region, &psi);
2470 update_ssa (TODO_update_ssa);
2471 #ifdef ENABLE_CHECKING
2472 verify_loop_closed_ssa (true);
2476 /* Returns the number of pbbs that are in loops contained in SCOP. */
2479 nb_pbbs_in_loops (scop_p scop)
2485 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2486 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2492 /* Return the number of data references in BB that write in
2496 nb_data_writes_in_bb (basic_block bb)
2499 gimple_stmt_iterator gsi;
2501 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2502 if (gimple_vdef (gsi_stmt (gsi)))
2508 /* Splits STMT out of its current BB. */
2511 split_reduction_stmt (gimple stmt)
2513 gimple_stmt_iterator gsi;
2514 basic_block bb = gimple_bb (stmt);
2517 /* Do not split basic blocks with no writes to memory: the reduction
2518 will be the only write to memory. */
2519 if (nb_data_writes_in_bb (bb) == 0)
2522 split_block (bb, stmt);
2524 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2527 gsi = gsi_last_bb (bb);
2529 e = split_block (bb, gsi_stmt (gsi));
2534 /* Return true when stmt is a reduction operation. */
2537 is_reduction_operation_p (gimple stmt)
2539 enum tree_code code;
2541 gcc_assert (is_gimple_assign (stmt));
2542 code = gimple_assign_rhs_code (stmt);
2544 return flag_associative_math
2545 && commutative_tree_code (code)
2546 && associative_tree_code (code);
2549 /* Returns true when PHI contains an argument ARG. */
2552 phi_contains_arg (gimple phi, tree arg)
2556 for (i = 0; i < gimple_phi_num_args (phi); i++)
2557 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2563 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2566 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2570 if (TREE_CODE (arg) != SSA_NAME)
2573 stmt = SSA_NAME_DEF_STMT (arg);
2575 if (gimple_code (stmt) == GIMPLE_NOP
2576 || gimple_code (stmt) == GIMPLE_CALL)
2579 if (gimple_code (stmt) == GIMPLE_PHI)
2581 if (phi_contains_arg (stmt, lhs))
2586 if (!is_gimple_assign (stmt))
2589 if (gimple_num_ops (stmt) == 2)
2590 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2592 if (is_reduction_operation_p (stmt))
2594 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2597 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2603 /* Detect commutative and associative scalar reductions starting at
2604 the STMT. Return the phi node of the reduction cycle, or NULL. */
2607 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2608 VEC (gimple, heap) **in,
2609 VEC (gimple, heap) **out)
2611 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2616 VEC_safe_push (gimple, heap, *in, stmt);
2617 VEC_safe_push (gimple, heap, *out, stmt);
2621 /* Detect commutative and associative scalar reductions starting at
2622 STMT. Return the phi node of the reduction cycle, or NULL. */
2625 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2626 VEC (gimple, heap) **out)
2628 tree lhs = gimple_assign_lhs (stmt);
2630 if (gimple_num_ops (stmt) == 2)
2631 return detect_commutative_reduction_arg (lhs, stmt,
2632 gimple_assign_rhs1 (stmt),
2635 if (is_reduction_operation_p (stmt))
2637 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2638 gimple_assign_rhs1 (stmt),
2641 : detect_commutative_reduction_arg (lhs, stmt,
2642 gimple_assign_rhs2 (stmt),
2649 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2652 follow_inital_value_to_phi (tree arg, tree lhs)
2656 if (!arg || TREE_CODE (arg) != SSA_NAME)
2659 stmt = SSA_NAME_DEF_STMT (arg);
2661 if (gimple_code (stmt) == GIMPLE_PHI
2662 && phi_contains_arg (stmt, lhs))
2669 /* Return the argument of the loop PHI that is the inital value coming
2670 from outside the loop. */
2673 edge_initial_value_for_loop_phi (gimple phi)
2677 for (i = 0; i < gimple_phi_num_args (phi); i++)
2679 edge e = gimple_phi_arg_edge (phi, i);
2681 if (loop_depth (e->src->loop_father)
2682 < loop_depth (e->dest->loop_father))
2689 /* Return the argument of the loop PHI that is the inital value coming
2690 from outside the loop. */
2693 initial_value_for_loop_phi (gimple phi)
2697 for (i = 0; i < gimple_phi_num_args (phi); i++)
2699 edge e = gimple_phi_arg_edge (phi, i);
2701 if (loop_depth (e->src->loop_father)
2702 < loop_depth (e->dest->loop_father))
2703 return gimple_phi_arg_def (phi, i);
2709 /* Detect commutative and associative scalar reductions starting at
2710 the loop closed phi node STMT. Return the phi node of the
2711 reduction cycle, or NULL. */
2714 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2715 VEC (gimple, heap) **out)
2717 if (scalar_close_phi_node_p (stmt))
2719 tree arg = gimple_phi_arg_def (stmt, 0);
2720 gimple def, loop_phi;
2722 if (TREE_CODE (arg) != SSA_NAME)
2725 /* Note that loop close phi nodes should have a single argument
2726 because we translated the representation into a canonical form
2727 before Graphite: see canonicalize_loop_closed_ssa_form. */
2728 gcc_assert (gimple_phi_num_args (stmt) == 1);
2730 def = SSA_NAME_DEF_STMT (arg);
2731 loop_phi = detect_commutative_reduction (def, in, out);
2735 tree lhs = gimple_phi_result (stmt);
2736 tree init = initial_value_for_loop_phi (loop_phi);
2737 gimple phi = follow_inital_value_to_phi (init, lhs);
2739 VEC_safe_push (gimple, heap, *in, loop_phi);
2740 VEC_safe_push (gimple, heap, *out, stmt);
2747 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2748 return detect_commutative_reduction_assign (stmt, in, out);
2753 /* Translate the scalar reduction statement STMT to an array RED
2754 knowing that its recursive phi node is LOOP_PHI. */
2757 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2760 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2761 tree res = gimple_phi_result (loop_phi);
2762 gimple assign = gimple_build_assign (res, red);
2764 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2766 insert_gsi = gsi_after_labels (gimple_bb (stmt));
2767 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2768 insert_gsi = gsi_for_stmt (stmt);
2769 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2772 /* Removes the PHI node and resets all the debug stmts that are using
2776 remove_phi (gimple phi)
2778 imm_use_iterator imm_iter;
2780 use_operand_p use_p;
2781 gimple_stmt_iterator gsi;
2782 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2786 def = PHI_RESULT (phi);
2787 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2789 stmt = USE_STMT (use_p);
2791 if (is_gimple_debug (stmt))
2793 gimple_debug_bind_reset_value (stmt);
2794 VEC_safe_push (gimple, heap, update, stmt);
2798 for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2801 VEC_free (gimple, heap, update);
2803 gsi = gsi_for_phi_node (phi);
2804 remove_phi_node (&gsi, false);
2807 /* Rewrite out of SSA the reduction described by the loop phi nodes
2808 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2811 IN: stmt, loop_n, ..., loop_0
2812 OUT: stmt, close_n, ..., close_0
2814 the first element is the reduction statement, and the next elements
2815 are the loop and close phi nodes of each of the outer loops. */
2818 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2819 VEC (gimple, heap) *out,
2824 tree red = NULL_TREE;
2826 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2828 gimple close_phi = VEC_index (gimple, out, i);
2832 gimple stmt = loop_phi;
2833 basic_block bb = split_reduction_stmt (stmt);
2835 SET_BIT (reductions, bb->index);
2836 gcc_assert (close_phi == loop_phi);
2838 red = create_zero_dim_array
2839 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2840 translate_scalar_reduction_to_array_for_stmt
2841 (red, stmt, VEC_index (gimple, in, 1));
2845 if (i == VEC_length (gimple, in) - 1)
2847 insert_out_of_ssa_copy (gimple_phi_result (close_phi), red,
2849 insert_out_of_ssa_copy_on_edge
2850 (edge_initial_value_for_loop_phi (loop_phi),
2851 red, initial_value_for_loop_phi (loop_phi));
2854 remove_phi (loop_phi);
2855 remove_phi (close_phi);
2859 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2862 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2865 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2866 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2868 detect_commutative_reduction (close_phi, &in, &out);
2869 if (VEC_length (gimple, in) > 0)
2870 translate_scalar_reduction_to_array (in, out, reductions);
2872 VEC_free (gimple, heap, in);
2873 VEC_free (gimple, heap, out);
2876 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2879 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2882 gimple_stmt_iterator gsi;
2883 edge exit = single_exit (loop);
2888 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2889 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2893 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2896 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2901 if (!flag_associative_math)
2904 FOR_EACH_LOOP (li, loop, 0)
2905 if (loop_in_sese_p (loop, region))
2906 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2908 gsi_commit_edge_inserts ();
2909 update_ssa (TODO_update_ssa);
2910 #ifdef ENABLE_CHECKING
2911 verify_loop_closed_ssa (true);
2915 /* A LOOP is in normal form for Graphite when it contains only one
2916 scalar phi node that defines the main induction variable of the
2917 loop, only one increment of the IV, and only one exit condition. */
2920 graphite_loop_normal_form (loop_p loop)
2922 struct tree_niter_desc niter;
2925 edge exit = single_dom_exit (loop);
2927 bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2929 /* At this point we should know the number of iterations. */
2930 gcc_assert (known_niter);
2932 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2935 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2937 loop->single_iv = canonicalize_loop_ivs (loop, &nit, false);
2940 /* Rewrite all the loops of SCOP in normal form: one induction
2941 variable per loop. */
2944 scop_canonicalize_loops (scop_p scop)
2949 FOR_EACH_LOOP (li, loop, 0)
2950 if (loop_in_sese_p (loop, SCOP_REGION (scop)))
2951 graphite_loop_normal_form (loop);
2954 /* Java does not initialize long_long_integer_type_node. */
2955 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2957 /* Can all ivs be represented by a signed integer?
2958 As CLooG might generate negative values in its expressions, signed loop ivs
2959 are required in the backend. */
2962 scop_ivs_can_be_represented (scop_p scop)
2967 FOR_EACH_LOOP (li, loop, 0)
2972 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
2975 if (!loop->single_iv)
2978 type = TREE_TYPE (loop->single_iv);
2979 precision = TYPE_PRECISION (type);
2981 if (TYPE_UNSIGNED (type)
2982 && precision >= TYPE_PRECISION (my_long_long))
2991 /* Builds the polyhedral representation for a SESE region. */
2994 build_poly_scop (scop_p scop)
2996 sese region = SCOP_REGION (scop);
2997 graphite_dim_t max_dim;
3000 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3001 Once CLooG is fixed, remove this guard. Anyways, it makes no
3002 sense to optimize a scop containing only PBBs that do not belong
3004 if (nb_pbbs_in_loops (scop) == 0)
3007 scop_canonicalize_loops (scop);
3008 if (!scop_ivs_can_be_represented (scop))
3011 build_sese_loop_nests (region);
3012 build_sese_conditions (region);
3013 find_scop_parameters (scop);
3015 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3016 if (scop_nb_params (scop) > max_dim)
3019 build_scop_iteration_domain (scop);
3020 build_scop_context (scop);
3022 add_conditions_to_constraints (scop);
3024 build_scop_scattering (scop);
3025 build_scop_drs (scop);
3027 /* This SCoP has been translated to the polyhedral
3029 POLY_SCOP_P (scop) = true;
3032 /* Always return false. Exercise the scop_to_clast function. */
3035 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
3037 #ifdef ENABLE_CHECKING
3038 cloog_prog_clast pc = scop_to_clast (scop);
3039 cloog_clast_free (pc.stmt);
3040 cloog_program_free (pc.prog);