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"
47 #include "graphite-ppl.h"
49 #include "graphite-poly.h"
50 #include "graphite-scop-detection.h"
51 #include "graphite-sese-to-poly.h"
53 /* Check if VAR is used in a phi node, that is no loop header. */
56 var_used_in_not_loop_header_phi_node (tree var)
58 imm_use_iterator imm_iter;
62 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
64 basic_block bb = gimple_bb (stmt);
66 if (gimple_code (stmt) == GIMPLE_PHI
67 && bb->loop_father->header != bb)
74 /* Returns the index of the PHI argument defined in the outermost
78 phi_arg_in_outermost_loop (gimple phi)
80 loop_p loop = gimple_bb (phi)->loop_father;
83 for (i = 0; i < gimple_phi_num_args (phi); i++)
84 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
86 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
94 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
97 remove_simple_copy_phi (gimple_stmt_iterator *psi)
99 gimple phi = gsi_stmt (*psi);
100 tree res = gimple_phi_result (phi);
101 size_t entry = phi_arg_in_outermost_loop (phi);
102 tree init = gimple_phi_arg_def (phi, entry);
103 gimple stmt = gimple_build_assign (res, init);
104 edge e = gimple_phi_arg_edge (phi, entry);
106 remove_phi_node (psi, false);
107 gsi_insert_on_edge_immediate (e, stmt);
108 SSA_NAME_DEF_STMT (res) = stmt;
111 /* Removes an invariant phi node at position PSI by inserting on the
112 loop ENTRY edge the assignment RES = INIT. */
115 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
117 gimple phi = gsi_stmt (*psi);
118 loop_p loop = loop_containing_stmt (phi);
119 tree res = gimple_phi_result (phi);
120 tree scev = scalar_evolution_in_region (region, loop, res);
121 size_t entry = phi_arg_in_outermost_loop (phi);
122 edge e = gimple_phi_arg_edge (phi, entry);
126 gimple_stmt_iterator gsi;
128 if (tree_contains_chrecs (scev, NULL))
129 scev = gimple_phi_arg_def (phi, entry);
131 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
132 stmt = gimple_build_assign (res, var);
133 remove_phi_node (psi, false);
136 stmts = gimple_seq_alloc ();
138 gsi = gsi_last (stmts);
139 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
140 gsi_insert_seq_on_edge (e, stmts);
141 gsi_commit_edge_inserts ();
142 SSA_NAME_DEF_STMT (res) = stmt;
145 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
148 simple_copy_phi_p (gimple phi)
152 if (gimple_phi_num_args (phi) != 2)
155 res = gimple_phi_result (phi);
156 return (res == gimple_phi_arg_def (phi, 0)
157 || res == gimple_phi_arg_def (phi, 1));
160 /* Returns true when the phi node at position PSI is a reduction phi
161 node in REGION. Otherwise moves the pointer PSI to the next phi to
165 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
168 gimple phi = gsi_stmt (*psi);
169 tree res = gimple_phi_result (phi);
171 if (!is_gimple_reg (res))
177 loop = loop_containing_stmt (phi);
179 if (simple_copy_phi_p (phi))
181 /* PRE introduces phi nodes like these, for an example,
182 see id-5.f in the fortran graphite testsuite:
184 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
186 remove_simple_copy_phi (psi);
190 if (scev_analyzable_p (res, region))
192 tree scev = scalar_evolution_in_region (region, loop, res);
194 if (evolution_function_is_invariant_p (scev, loop->num))
195 remove_invariant_phi (region, psi);
202 /* All the other cases are considered reductions. */
206 /* Returns true when BB will be represented in graphite. Return false
207 for the basic blocks that contain code eliminated in the code
208 generation pass: i.e. induction variables and exit conditions. */
211 graphite_stmt_p (sese region, basic_block bb,
212 VEC (data_reference_p, heap) *drs)
214 gimple_stmt_iterator gsi;
215 loop_p loop = bb->loop_father;
217 if (VEC_length (data_reference_p, drs) > 0)
220 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
222 gimple stmt = gsi_stmt (gsi);
224 switch (gimple_code (stmt))
227 /* Control flow expressions can be ignored, as they are
228 represented in the iteration domains and will be
229 regenerated by graphite. */
237 tree var = gimple_assign_lhs (stmt);
239 /* We need these bbs to be able to construct the phi nodes. */
240 if (var_used_in_not_loop_header_phi_node (var))
243 var = scalar_evolution_in_region (region, loop, var);
244 if (chrec_contains_undetermined (var))
258 /* Store the GRAPHITE representation of BB. */
261 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
263 struct gimple_bb *gbb;
265 gbb = XNEW (struct gimple_bb);
268 GBB_DATA_REFS (gbb) = drs;
269 GBB_CONDITIONS (gbb) = NULL;
270 GBB_CONDITION_CASES (gbb) = NULL;
276 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
279 struct data_reference *dr;
281 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
284 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
287 free (bap->alias_set);
296 free_gimple_bb (struct gimple_bb *gbb)
298 free_data_refs_aux (GBB_DATA_REFS (gbb));
299 free_data_refs (GBB_DATA_REFS (gbb));
301 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
302 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
303 GBB_BB (gbb)->aux = 0;
307 /* Deletes all gimple bbs in SCOP. */
310 remove_gbbs_in_scop (scop_p scop)
315 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
316 free_gimple_bb (PBB_BLACK_BOX (pbb));
319 /* Deletes all scops in SCOPS. */
322 free_scops (VEC (scop_p, heap) *scops)
327 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
329 remove_gbbs_in_scop (scop);
330 free_sese (SCOP_REGION (scop));
334 VEC_free (scop_p, heap, scops);
337 /* Generates a polyhedral black box only if the bb contains interesting
341 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
343 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
344 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
345 gimple_stmt_iterator gsi;
347 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
349 gimple stmt = gsi_stmt (gsi);
350 if (!is_gimple_debug (stmt))
351 graphite_find_data_references_in_stmt (nest, stmt, &drs);
354 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
355 free_data_refs (drs);
357 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
361 /* Returns true if all predecessors of BB, that are not dominated by BB, are
362 marked in MAP. The predecessors dominated by BB are loop latches and will
363 be handled after BB. */
366 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
371 FOR_EACH_EDGE (e, ei, bb->preds)
372 if (!TEST_BIT (map, e->src->index)
373 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
379 /* Compare the depth of two basic_block's P1 and P2. */
382 compare_bb_depths (const void *p1, const void *p2)
384 const_basic_block const bb1 = *(const_basic_block const*)p1;
385 const_basic_block const bb2 = *(const_basic_block const*)p2;
386 int d1 = loop_depth (bb1->loop_father);
387 int d2 = loop_depth (bb2->loop_father);
398 /* Sort the basic blocks from DOM such that the first are the ones at
399 a deepest loop level. */
402 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
404 size_t len = VEC_length (basic_block, dom);
406 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
410 /* Recursive helper function for build_scops_bbs. */
413 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
415 sese region = SCOP_REGION (scop);
416 VEC (basic_block, heap) *dom;
418 if (TEST_BIT (visited, bb->index)
419 || !bb_in_sese_p (bb, region))
422 try_generate_gimple_bb (scop, bb, reductions);
423 SET_BIT (visited, bb->index);
425 dom = get_dominated_by (CDI_DOMINATORS, bb);
430 graphite_sort_dominated_info (dom);
432 while (!VEC_empty (basic_block, dom))
437 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
438 if (all_non_dominated_preds_marked_p (dom_bb, visited))
440 build_scop_bbs_1 (scop, visited, dom_bb, reductions);
441 VEC_unordered_remove (basic_block, dom, i);
446 VEC_free (basic_block, heap, dom);
449 /* Gather the basic blocks belonging to the SCOP. */
452 build_scop_bbs (scop_p scop, sbitmap reductions)
454 sbitmap visited = sbitmap_alloc (last_basic_block);
455 sese region = SCOP_REGION (scop);
457 sbitmap_zero (visited);
458 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
459 sbitmap_free (visited);
462 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
463 We generate SCATTERING_DIMENSIONS scattering dimensions.
465 CLooG 0.15.0 and previous versions require, that all
466 scattering functions of one CloogProgram have the same number of
467 scattering dimensions, therefore we allow to specify it. This
468 should be removed in future versions of CLooG.
470 The scattering polyhedron consists of these dimensions: scattering,
471 loop_iterators, parameters.
475 | scattering_dimensions = 5
476 | used_scattering_dimensions = 3
484 | Scattering polyhedron:
486 | scattering: {s1, s2, s3, s4, s5}
487 | loop_iterators: {i}
488 | parameters: {p1, p2}
490 | s1 s2 s3 s4 s5 i p1 p2 1
491 | 1 0 0 0 0 0 0 0 -4 = 0
492 | 0 1 0 0 0 -1 0 0 0 = 0
493 | 0 0 1 0 0 0 0 0 -5 = 0 */
496 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
497 poly_bb_p pbb, int scattering_dimensions)
500 scop_p scop = PBB_SCOP (pbb);
501 int nb_iterators = pbb_dim_iter_domain (pbb);
502 int used_scattering_dimensions = nb_iterators * 2 + 1;
503 int nb_params = scop_nb_params (scop);
505 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
508 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
511 ppl_new_Coefficient (&c);
512 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
513 ppl_new_C_Polyhedron_from_space_dimension
514 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
516 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
518 for (i = 0; i < scattering_dimensions; i++)
520 ppl_Constraint_t cstr;
521 ppl_Linear_Expression_t expr;
523 ppl_new_Linear_Expression_with_dimension (&expr, dim);
525 ppl_assign_Coefficient_from_mpz_t (c, v);
526 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
528 /* Textual order inside this loop. */
531 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
532 ppl_Coefficient_to_mpz_t (c, v);
534 ppl_assign_Coefficient_from_mpz_t (c, v);
535 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
538 /* Iterations of this loop. */
539 else /* if ((i % 2) == 1) */
541 int loop = (i - 1) / 2;
544 ppl_assign_Coefficient_from_mpz_t (c, v);
545 ppl_Linear_Expression_add_to_coefficient
546 (expr, scattering_dimensions + loop, c);
549 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
550 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
551 ppl_delete_Linear_Expression (expr);
552 ppl_delete_Constraint (cstr);
556 ppl_delete_Coefficient (c);
558 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
561 /* Build for BB the static schedule.
563 The static schedule is a Dewey numbering of the abstract syntax
564 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
566 The following example informally defines the static schedule:
585 Static schedules for A to F:
598 build_scop_scattering (scop_p scop)
602 gimple_bb_p previous_gbb = NULL;
603 ppl_Linear_Expression_t static_schedule;
608 ppl_new_Coefficient (&c);
609 ppl_new_Linear_Expression (&static_schedule);
611 /* We have to start schedules at 0 on the first component and
612 because we cannot compare_prefix_loops against a previous loop,
613 prefix will be equal to zero, and that index will be
614 incremented before copying. */
616 ppl_assign_Coefficient_from_mpz_t (c, v);
617 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
619 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
621 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
622 ppl_Linear_Expression_t common;
624 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
627 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
632 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
633 ppl_assign_Linear_Expression_from_Linear_Expression (common,
637 ppl_assign_Coefficient_from_mpz_t (c, v);
638 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
639 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
642 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
644 ppl_delete_Linear_Expression (common);
648 ppl_delete_Coefficient (c);
649 ppl_delete_Linear_Expression (static_schedule);
652 /* Add the value K to the dimension D of the linear expression EXPR. */
655 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
659 ppl_Coefficient_t coef;
661 ppl_new_Coefficient (&coef);
662 ppl_Linear_Expression_coefficient (expr, d, coef);
664 ppl_Coefficient_to_mpz_t (coef, val);
666 mpz_add (val, val, k);
668 ppl_assign_Coefficient_from_mpz_t (coef, val);
669 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
671 ppl_delete_Coefficient (coef);
674 /* In the context of scop S, scan E, the right hand side of a scalar
675 evolution function in loop VAR, and translate it to a linear
679 scan_tree_for_params_right_scev (sese s, tree e, int var,
680 ppl_Linear_Expression_t expr)
684 loop_p loop = get_loop (var);
685 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
688 /* Scalar evolutions should happen in the sese region. */
689 gcc_assert (sese_loop_depth (s, loop) > 0);
691 /* We can not deal with parametric strides like:
697 gcc_assert (TREE_CODE (e) == INTEGER_CST);
700 mpz_set_si (val, int_cst_value (e));
701 add_value_to_dim (l, expr, val);
706 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
707 linear expression EXPR. K is the multiplier of the constant. */
710 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
713 ppl_Coefficient_t coef;
714 int v = int_cst_value (cst);
719 /* Necessary to not get "-1 = 2^n - 1". */
721 mpz_sub_ui (val, val, -v);
723 mpz_add_ui (val, val, v);
725 mpz_mul (val, val, k);
726 ppl_new_Coefficient (&coef);
727 ppl_assign_Coefficient_from_mpz_t (coef, val);
728 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
730 ppl_delete_Coefficient (coef);
733 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
734 Otherwise returns -1. */
737 parameter_index_in_region_1 (tree name, sese region)
742 gcc_assert (TREE_CODE (name) == SSA_NAME);
744 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
751 /* When the parameter NAME is in REGION, returns its index in
752 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
753 and returns the index of NAME. */
756 parameter_index_in_region (tree name, sese region)
760 gcc_assert (TREE_CODE (name) == SSA_NAME);
762 i = parameter_index_in_region_1 (name, region);
766 gcc_assert (SESE_ADD_PARAMS (region));
768 i = VEC_length (tree, SESE_PARAMS (region));
769 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
773 /* In the context of sese S, scan the expression E and translate it to
774 a linear expression C. When parsing a symbolic multiplication, K
775 represents the constant multiplier of an expression containing
779 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
782 if (e == chrec_dont_know)
785 switch (TREE_CODE (e))
787 case POLYNOMIAL_CHREC:
788 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
789 CHREC_VARIABLE (e), c);
790 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
794 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
799 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
801 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
802 mpz_mul (val, val, k);
803 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
807 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
814 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
816 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
817 mpz_mul (val, val, k);
818 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
822 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
827 case POINTER_PLUS_EXPR:
828 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
829 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
834 ppl_Linear_Expression_t tmp_expr = NULL;
838 ppl_dimension_type dim;
839 ppl_Linear_Expression_space_dimension (c, &dim);
840 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
843 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
844 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
848 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
850 ppl_delete_Linear_Expression (tmp_expr);
858 ppl_Linear_Expression_t tmp_expr = NULL;
862 ppl_dimension_type dim;
863 ppl_Linear_Expression_space_dimension (c, &dim);
864 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
867 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
871 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
873 ppl_delete_Linear_Expression (tmp_expr);
881 ppl_Linear_Expression_t tmp_expr = NULL;
885 ppl_dimension_type dim;
886 ppl_Linear_Expression_space_dimension (c, &dim);
887 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
890 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
894 ppl_Coefficient_t coef;
897 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
899 ppl_delete_Linear_Expression (tmp_expr);
900 mpz_init (minus_one);
901 mpz_set_si (minus_one, -1);
902 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
903 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
904 mpz_clear (minus_one);
905 ppl_delete_Coefficient (coef);
913 ppl_dimension_type p = parameter_index_in_region (e, s);
917 ppl_dimension_type dim;
918 ppl_Linear_Expression_space_dimension (c, &dim);
919 p += dim - sese_nb_params (s);
920 add_value_to_dim (p, c, k);
927 scan_tree_for_params_int (e, c, k);
931 case NON_LVALUE_EXPR:
932 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
941 /* Find parameters with respect to REGION in BB. We are looking in memory
942 access functions, conditions and loop bounds. */
945 find_params_in_bb (sese region, gimple_bb_p gbb)
951 loop_p loop = GBB_BB (gbb)->loop_father;
957 /* Find parameters in the access functions of data references. */
958 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
959 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
960 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
962 /* Find parameters in conditional statements. */
963 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
965 tree lhs = scalar_evolution_in_region (region, loop,
966 gimple_cond_lhs (stmt));
967 tree rhs = scalar_evolution_in_region (region, loop,
968 gimple_cond_rhs (stmt));
970 scan_tree_for_params (region, lhs, NULL, one);
971 scan_tree_for_params (region, rhs, NULL, one);
977 /* Record the parameters used in the SCOP. A variable is a parameter
978 in a scop if it does not vary during the execution of that scop. */
981 find_scop_parameters (scop_p scop)
985 sese region = SCOP_REGION (scop);
992 /* Find the parameters used in the loop bounds. */
993 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
995 tree nb_iters = number_of_latch_executions (loop);
997 if (!chrec_contains_symbols (nb_iters))
1000 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1001 scan_tree_for_params (region, nb_iters, NULL, one);
1006 /* Find the parameters used in data accesses. */
1007 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1008 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1010 scop_set_nb_params (scop, sese_nb_params (region));
1011 SESE_ADD_PARAMS (region) = false;
1013 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1014 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1017 /* Returns a gimple_bb from BB. */
1019 static inline gimple_bb_p
1020 gbb_from_bb (basic_block bb)
1022 return (gimple_bb_p) bb->aux;
1025 /* Insert in the SCOP context constraints from the estimation of the
1026 number of iterations. UB_EXPR is a linear expression describing
1027 the number of iterations in a loop. This expression is bounded by
1028 the estimation NIT. */
1031 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
1032 ppl_dimension_type dim,
1033 ppl_Linear_Expression_t ub_expr)
1036 ppl_Linear_Expression_t nb_iters_le;
1037 ppl_Polyhedron_t pol;
1038 ppl_Coefficient_t coef;
1039 ppl_Constraint_t ub;
1041 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1042 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1043 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1046 /* Construct the negated number of last iteration in VAL. */
1048 mpz_set_double_int (val, nit, false);
1049 mpz_sub_ui (val, val, 1);
1052 /* NB_ITERS_LE holds the number of last iteration in
1053 parametrical form. Subtract estimated number of last
1054 iteration and assert that result is not positive. */
1055 ppl_new_Coefficient_from_mpz_t (&coef, val);
1056 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1057 ppl_delete_Coefficient (coef);
1058 ppl_new_Constraint (&ub, nb_iters_le,
1059 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1060 ppl_Polyhedron_add_constraint (pol, ub);
1062 /* Remove all but last GDIM dimensions from POL to obtain
1063 only the constraints on the parameters. */
1065 graphite_dim_t gdim = scop_nb_params (scop);
1066 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
1069 for (i = 0; i < dim - gdim; i++)
1072 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1076 /* Add the constraints on the parameters to the SCoP context. */
1078 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1080 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1081 (&constraints_ps, pol);
1082 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1083 (SCOP_CONTEXT (scop), constraints_ps);
1084 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1087 ppl_delete_Polyhedron (pol);
1088 ppl_delete_Linear_Expression (nb_iters_le);
1089 ppl_delete_Constraint (ub);
1093 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1094 the constraints for the surrounding loops. */
1097 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1098 ppl_Polyhedron_t outer_ph, int nb,
1099 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1102 ppl_Polyhedron_t ph;
1103 tree nb_iters = number_of_latch_executions (loop);
1104 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1105 sese region = SCOP_REGION (scop);
1108 ppl_const_Constraint_System_t pcs;
1109 ppl_dimension_type *map
1110 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1112 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1113 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1114 ppl_Polyhedron_add_constraints (ph, pcs);
1116 for (i = 0; i < (int) nb; i++)
1118 for (i = (int) nb; i < (int) dim - 1; i++)
1122 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1128 ppl_Constraint_t lb;
1129 ppl_Linear_Expression_t lb_expr;
1131 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1132 ppl_set_coef (lb_expr, nb, 1);
1133 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1134 ppl_delete_Linear_Expression (lb_expr);
1135 ppl_Polyhedron_add_constraint (ph, lb);
1136 ppl_delete_Constraint (lb);
1139 if (TREE_CODE (nb_iters) == INTEGER_CST)
1141 ppl_Constraint_t ub;
1142 ppl_Linear_Expression_t ub_expr;
1144 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1146 /* loop_i <= cst_nb_iters */
1147 ppl_set_coef (ub_expr, nb, -1);
1148 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1149 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1150 ppl_Polyhedron_add_constraint (ph, ub);
1151 ppl_delete_Linear_Expression (ub_expr);
1152 ppl_delete_Constraint (ub);
1154 else if (!chrec_contains_undetermined (nb_iters))
1157 ppl_Constraint_t ub;
1158 ppl_Linear_Expression_t ub_expr;
1162 mpz_set_si (one, 1);
1163 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1164 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1165 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1168 if (estimated_loop_iterations (loop, true, &nit))
1169 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1171 /* loop_i <= expr_nb_iters */
1172 ppl_set_coef (ub_expr, nb, -1);
1173 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1174 ppl_Polyhedron_add_constraint (ph, ub);
1175 ppl_delete_Linear_Expression (ub_expr);
1176 ppl_delete_Constraint (ub);
1181 if (loop->inner && loop_in_sese_p (loop->inner, region))
1182 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1186 && loop_in_sese_p (loop->next, region))
1187 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1189 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1190 (&domains[loop->num], ph);
1192 ppl_delete_Polyhedron (ph);
1195 /* Returns a linear expression for tree T evaluated in PBB. */
1197 static ppl_Linear_Expression_t
1198 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1201 ppl_Linear_Expression_t res;
1202 ppl_dimension_type dim;
1203 sese region = SCOP_REGION (PBB_SCOP (pbb));
1204 loop_p loop = pbb_loop (pbb);
1206 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1207 ppl_new_Linear_Expression_with_dimension (&res, dim);
1209 t = scalar_evolution_in_region (region, loop, t);
1210 gcc_assert (!automatically_generated_chrec_p (t));
1213 mpz_set_si (one, 1);
1214 scan_tree_for_params (region, t, res, one);
1220 /* Returns the ppl constraint type from the gimple tree code CODE. */
1222 static enum ppl_enum_Constraint_Type
1223 ppl_constraint_type_from_tree_code (enum tree_code code)
1227 /* We do not support LT and GT to be able to work with C_Polyhedron.
1228 As we work on integer polyhedron "a < b" can be expressed by
1235 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1238 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1241 return PPL_CONSTRAINT_TYPE_EQUAL;
1248 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1249 CODE is used as the comparison operator. This allows us to invert the
1250 condition or to handle inequalities. */
1253 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1254 poly_bb_p pbb, enum tree_code code)
1257 ppl_Coefficient_t c;
1258 ppl_Linear_Expression_t left, right;
1259 ppl_Constraint_t cstr;
1260 enum ppl_enum_Constraint_Type type;
1262 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1263 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1265 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1266 the left or the right side of the expression. */
1267 if (code == LT_EXPR)
1271 ppl_new_Coefficient (&c);
1272 ppl_assign_Coefficient_from_mpz_t (c, v);
1273 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1274 ppl_delete_Coefficient (c);
1279 else if (code == GT_EXPR)
1283 ppl_new_Coefficient (&c);
1284 ppl_assign_Coefficient_from_mpz_t (c, v);
1285 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1286 ppl_delete_Coefficient (c);
1292 type = ppl_constraint_type_from_tree_code (code);
1294 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1296 ppl_new_Constraint (&cstr, left, type);
1297 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1299 ppl_delete_Constraint (cstr);
1300 ppl_delete_Linear_Expression (left);
1301 ppl_delete_Linear_Expression (right);
1304 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1305 operator. This allows us to invert the condition or to handle
1309 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1311 if (code == NE_EXPR)
1313 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1314 ppl_Pointset_Powerset_C_Polyhedron_t right;
1315 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1317 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1318 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1319 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1320 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1323 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1326 /* Add conditions to the domain of PBB. */
1329 add_conditions_to_domain (poly_bb_p pbb)
1333 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1335 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1338 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
1339 switch (gimple_code (stmt))
1343 enum tree_code code = gimple_cond_code (stmt);
1345 /* The conditions for ELSE-branches are inverted. */
1346 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1347 code = invert_tree_comparison (code, false);
1349 add_condition_to_pbb (pbb, stmt, code);
1354 /* Switch statements are not supported right now - fall throught. */
1362 /* Structure used to pass data to dom_walk. */
1366 VEC (gimple, heap) **conditions, **cases;
1370 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1371 edge between BB and its predecessor is not a loop exit edge, and
1372 the last statement of the single predecessor is a COND_EXPR. */
1375 single_pred_cond_non_loop_exit (basic_block bb)
1377 if (single_pred_p (bb))
1379 edge e = single_pred_edge (bb);
1380 basic_block pred = e->src;
1383 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1386 stmt = last_stmt (pred);
1388 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1395 /* Call-back for dom_walk executed before visiting the dominated
1399 build_sese_conditions_before (struct dom_walk_data *dw_data,
1402 struct bsc *data = (struct bsc *) dw_data->global_data;
1403 VEC (gimple, heap) **conditions = data->conditions;
1404 VEC (gimple, heap) **cases = data->cases;
1408 if (!bb_in_sese_p (bb, data->region))
1411 stmt = single_pred_cond_non_loop_exit (bb);
1415 edge e = single_pred_edge (bb);
1417 VEC_safe_push (gimple, heap, *conditions, stmt);
1419 if (e->flags & EDGE_TRUE_VALUE)
1420 VEC_safe_push (gimple, heap, *cases, stmt);
1422 VEC_safe_push (gimple, heap, *cases, NULL);
1425 gbb = gbb_from_bb (bb);
1429 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1430 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1434 /* Call-back for dom_walk executed after visiting the dominated
1438 build_sese_conditions_after (struct dom_walk_data *dw_data,
1441 struct bsc *data = (struct bsc *) dw_data->global_data;
1442 VEC (gimple, heap) **conditions = data->conditions;
1443 VEC (gimple, heap) **cases = data->cases;
1445 if (!bb_in_sese_p (bb, data->region))
1448 if (single_pred_cond_non_loop_exit (bb))
1450 VEC_pop (gimple, *conditions);
1451 VEC_pop (gimple, *cases);
1455 /* Record all conditions in REGION. */
1458 build_sese_conditions (sese region)
1460 struct dom_walk_data walk_data;
1461 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1462 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1465 data.conditions = &conditions;
1466 data.cases = &cases;
1467 data.region = region;
1469 walk_data.dom_direction = CDI_DOMINATORS;
1470 walk_data.initialize_block_local_data = NULL;
1471 walk_data.before_dom_children = build_sese_conditions_before;
1472 walk_data.after_dom_children = build_sese_conditions_after;
1473 walk_data.global_data = &data;
1474 walk_data.block_local_data_size = 0;
1476 init_walk_dominator_tree (&walk_data);
1477 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1478 fini_walk_dominator_tree (&walk_data);
1480 VEC_free (gimple, heap, conditions);
1481 VEC_free (gimple, heap, cases);
1484 /* Traverses all the GBBs of the SCOP and add their constraints to the
1485 iteration domains. */
1488 add_conditions_to_constraints (scop_p scop)
1493 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1494 add_conditions_to_domain (pbb);
1497 /* Add constraints on the possible values of parameter P from the type
1501 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1503 ppl_Constraint_t cstr;
1504 ppl_Linear_Expression_t le;
1505 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1506 tree type = TREE_TYPE (parameter);
1507 tree lb = NULL_TREE;
1508 tree ub = NULL_TREE;
1510 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1511 lb = lower_bound_in_type (type, type);
1513 lb = TYPE_MIN_VALUE (type);
1515 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1516 ub = upper_bound_in_type (type, type);
1518 ub = TYPE_MAX_VALUE (type);
1522 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1523 ppl_set_coef (le, p, -1);
1524 ppl_set_inhomogeneous_tree (le, lb);
1525 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1526 ppl_Polyhedron_add_constraint (context, cstr);
1527 ppl_delete_Linear_Expression (le);
1528 ppl_delete_Constraint (cstr);
1533 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1534 ppl_set_coef (le, p, -1);
1535 ppl_set_inhomogeneous_tree (le, ub);
1536 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1537 ppl_Polyhedron_add_constraint (context, cstr);
1538 ppl_delete_Linear_Expression (le);
1539 ppl_delete_Constraint (cstr);
1543 /* Build the context of the SCOP. The context usually contains extra
1544 constraints that are added to the iteration domains that constrain
1548 build_scop_context (scop_p scop)
1550 ppl_Polyhedron_t context;
1551 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1552 graphite_dim_t p, n = scop_nb_params (scop);
1554 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1556 for (p = 0; p < n; p++)
1557 add_param_constraints (scop, context, p);
1559 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1561 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1562 (SCOP_CONTEXT (scop), ps);
1564 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1565 ppl_delete_Polyhedron (context);
1568 /* Build the iteration domains: the loops belonging to the current
1569 SCOP, and that vary for the execution of the current basic block.
1570 Returns false if there is no loop in SCOP. */
1573 build_scop_iteration_domain (scop_p scop)
1576 sese region = SCOP_REGION (scop);
1578 ppl_Polyhedron_t ph;
1580 int nb_loops = number_of_loops ();
1581 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1582 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1584 for (i = 0; i < nb_loops; i++)
1587 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1589 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1590 if (!loop_in_sese_p (loop_outer (loop), region))
1591 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1593 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1594 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1595 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1596 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1597 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1599 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1600 (&PBB_DOMAIN (pbb), ph);
1602 for (i = 0; i < nb_loops; i++)
1604 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1606 ppl_delete_Polyhedron (ph);
1610 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1611 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1612 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1616 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1617 ppl_dimension_type accessp_nb_dims,
1618 ppl_dimension_type dom_nb_dims)
1620 ppl_Linear_Expression_t alias;
1621 ppl_Constraint_t cstr;
1622 int alias_set_num = 0;
1623 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1625 if (bap && bap->alias_set)
1626 alias_set_num = *(bap->alias_set);
1628 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1630 ppl_set_coef (alias, dom_nb_dims, 1);
1631 ppl_set_inhomogeneous (alias, -alias_set_num);
1632 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1633 ppl_Polyhedron_add_constraint (accesses, cstr);
1635 ppl_delete_Linear_Expression (alias);
1636 ppl_delete_Constraint (cstr);
1639 /* Add to ACCESSES polyhedron equalities defining the access functions
1640 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1641 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1642 PBB is the poly_bb_p that contains the data reference DR. */
1645 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1646 ppl_dimension_type accessp_nb_dims,
1647 ppl_dimension_type dom_nb_dims,
1650 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1652 scop_p scop = PBB_SCOP (pbb);
1653 sese region = SCOP_REGION (scop);
1657 for (i = 0; i < nb_subscripts; i++)
1659 ppl_Linear_Expression_t fn, access;
1660 ppl_Constraint_t cstr;
1661 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1662 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1664 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1665 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1668 scan_tree_for_params (region, afn, fn, v);
1669 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1671 ppl_set_coef (access, subscript, -1);
1672 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1673 ppl_Polyhedron_add_constraint (accesses, cstr);
1675 ppl_delete_Linear_Expression (fn);
1676 ppl_delete_Linear_Expression (access);
1677 ppl_delete_Constraint (cstr);
1683 /* Add constrains representing the size of the accessed data to the
1684 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1685 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1689 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1690 ppl_dimension_type accessp_nb_dims,
1691 ppl_dimension_type dom_nb_dims)
1693 tree ref = DR_REF (dr);
1694 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1696 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1698 ppl_Linear_Expression_t expr;
1699 ppl_Constraint_t cstr;
1700 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1703 if (TREE_CODE (ref) != ARRAY_REF)
1706 low = array_ref_low_bound (ref);
1708 /* subscript - low >= 0 */
1709 if (host_integerp (low, 0))
1711 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1712 ppl_set_coef (expr, subscript, 1);
1714 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1716 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1717 ppl_Polyhedron_add_constraint (accesses, cstr);
1718 ppl_delete_Linear_Expression (expr);
1719 ppl_delete_Constraint (cstr);
1722 high = array_ref_up_bound (ref);
1724 /* high - subscript >= 0 */
1725 if (high && host_integerp (high, 0)
1726 /* 1-element arrays at end of structures may extend over
1727 their declared size. */
1728 && !(array_at_struct_end_p (ref)
1729 && operand_equal_p (low, high, 0)))
1731 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1732 ppl_set_coef (expr, subscript, -1);
1734 ppl_set_inhomogeneous (expr, int_cst_value (high));
1736 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1737 ppl_Polyhedron_add_constraint (accesses, cstr);
1738 ppl_delete_Linear_Expression (expr);
1739 ppl_delete_Constraint (cstr);
1744 /* Build data accesses for DR in PBB. */
1747 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1749 ppl_Polyhedron_t accesses;
1750 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1751 ppl_dimension_type dom_nb_dims;
1752 ppl_dimension_type accessp_nb_dims;
1753 int dr_base_object_set;
1755 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1757 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1759 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1761 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1762 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1763 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1765 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1767 ppl_delete_Polyhedron (accesses);
1769 gcc_assert (dr->aux);
1770 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1772 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1773 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1774 dr, DR_NUM_DIMENSIONS (dr));
1777 /* Write to FILE the alias graph of data references in DIMACS format. */
1780 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1781 VEC (data_reference_p, heap) *drs)
1783 int num_vertex = VEC_length (data_reference_p, drs);
1785 data_reference_p dr1, dr2;
1788 if (num_vertex == 0)
1791 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1792 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1793 if (dr_may_alias_p (dr1, dr2))
1796 fprintf (file, "$\n");
1799 fprintf (file, "c %s\n", comment);
1801 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1803 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1804 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1805 if (dr_may_alias_p (dr1, dr2))
1806 fprintf (file, "e %d %d\n", i + 1, j + 1);
1811 /* Write to FILE the alias graph of data references in DOT format. */
1814 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1815 VEC (data_reference_p, heap) *drs)
1817 int num_vertex = VEC_length (data_reference_p, drs);
1818 data_reference_p dr1, dr2;
1821 if (num_vertex == 0)
1824 fprintf (file, "$\n");
1827 fprintf (file, "c %s\n", comment);
1829 /* First print all the vertices. */
1830 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1831 fprintf (file, "n%d;\n", i);
1833 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1834 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1835 if (dr_may_alias_p (dr1, dr2))
1836 fprintf (file, "n%d n%d\n", i, j);
1841 /* Write to FILE the alias graph of data references in ECC format. */
1844 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1845 VEC (data_reference_p, heap) *drs)
1847 int num_vertex = VEC_length (data_reference_p, drs);
1848 data_reference_p dr1, dr2;
1851 if (num_vertex == 0)
1854 fprintf (file, "$\n");
1857 fprintf (file, "c %s\n", comment);
1859 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1860 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1861 if (dr_may_alias_p (dr1, dr2))
1862 fprintf (file, "%d %d\n", i, j);
1867 /* Check if DR1 and DR2 are in the same object set. */
1870 dr_same_base_object_p (const struct data_reference *dr1,
1871 const struct data_reference *dr2)
1873 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1876 /* Uses DFS component number as representative of alias-sets. Also tests for
1877 optimality by verifying if every connected component is a clique. Returns
1878 true (1) if the above test is true, and false (0) otherwise. */
1881 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1883 int num_vertices = VEC_length (data_reference_p, drs);
1884 struct graph *g = new_graph (num_vertices);
1885 data_reference_p dr1, dr2;
1887 int num_connected_components;
1888 int v_indx1, v_indx2, num_vertices_in_component;
1891 struct graph_edge *e;
1892 int this_component_is_clique;
1893 int all_components_are_cliques = 1;
1895 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1896 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1897 if (dr_may_alias_p (dr1, dr2))
1903 all_vertices = XNEWVEC (int, num_vertices);
1904 vertices = XNEWVEC (int, num_vertices);
1905 for (i = 0; i < num_vertices; i++)
1906 all_vertices[i] = i;
1908 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1910 for (i = 0; i < g->n_vertices; i++)
1912 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1913 base_alias_pair *bap;
1915 gcc_assert (dr->aux);
1916 bap = (base_alias_pair *)(dr->aux);
1918 bap->alias_set = XNEW (int);
1919 *(bap->alias_set) = g->vertices[i].component + 1;
1922 /* Verify if the DFS numbering results in optimal solution. */
1923 for (i = 0; i < num_connected_components; i++)
1925 num_vertices_in_component = 0;
1926 /* Get all vertices whose DFS component number is the same as i. */
1927 for (j = 0; j < num_vertices; j++)
1928 if (g->vertices[j].component == i)
1929 vertices[num_vertices_in_component++] = j;
1931 /* Now test if the vertices in 'vertices' form a clique, by testing
1932 for edges among each pair. */
1933 this_component_is_clique = 1;
1934 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1936 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1938 /* Check if the two vertices are connected by iterating
1939 through all the edges which have one of these are source. */
1940 e = g->vertices[vertices[v_indx2]].pred;
1943 if (e->src == vertices[v_indx1])
1949 this_component_is_clique = 0;
1953 if (!this_component_is_clique)
1954 all_components_are_cliques = 0;
1958 free (all_vertices);
1961 return all_components_are_cliques;
1964 /* Group each data reference in DRS with it's base object set num. */
1967 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1969 int num_vertex = VEC_length (data_reference_p, drs);
1970 struct graph *g = new_graph (num_vertex);
1971 data_reference_p dr1, dr2;
1975 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1976 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1977 if (dr_same_base_object_p (dr1, dr2))
1983 queue = XNEWVEC (int, num_vertex);
1984 for (i = 0; i < num_vertex; i++)
1987 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1989 for (i = 0; i < g->n_vertices; i++)
1991 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1992 base_alias_pair *bap;
1994 gcc_assert (dr->aux);
1995 bap = (base_alias_pair *)(dr->aux);
1997 bap->base_obj_set = g->vertices[i].component + 1;
2004 /* Build the data references for PBB. */
2007 build_pbb_drs (poly_bb_p pbb)
2010 data_reference_p dr;
2011 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2013 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2014 build_poly_dr (dr, pbb);
2017 /* Dump to file the alias graphs for the data references in DRS. */
2020 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2023 FILE *file_dimacs, *file_ecc, *file_dot;
2025 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2028 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2029 current_function_name ());
2030 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2031 fclose (file_dimacs);
2034 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2037 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2038 current_function_name ());
2039 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2043 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2046 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2047 current_function_name ());
2048 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2053 /* Build data references in SCOP. */
2056 build_scop_drs (scop_p scop)
2060 data_reference_p dr;
2061 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2063 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2064 for (j = 0; VEC_iterate (data_reference_p,
2065 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2066 VEC_safe_push (data_reference_p, heap, drs, dr);
2068 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2069 dr->aux = XNEW (base_alias_pair);
2071 if (!build_alias_set_optimal_p (drs))
2073 /* TODO: Add support when building alias set is not optimal. */
2077 build_base_obj_set_for_drs (drs);
2079 /* When debugging, enable the following code. This cannot be used
2080 in production compilers. */
2082 dump_alias_graphs (drs);
2084 VEC_free (data_reference_p, heap, drs);
2086 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2087 build_pbb_drs (pbb);
2090 /* Return a gsi at the position of the phi node STMT. */
2092 static gimple_stmt_iterator
2093 gsi_for_phi_node (gimple stmt)
2095 gimple_stmt_iterator psi;
2096 basic_block bb = gimple_bb (stmt);
2098 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2099 if (stmt == gsi_stmt (psi))
2106 /* Insert the assignment "RES := VAR" just after AFTER_STMT. */
2109 insert_out_of_ssa_copy (tree res, tree var, gimple after_stmt)
2113 gimple_stmt_iterator si;
2114 gimple_stmt_iterator gsi;
2116 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2117 stmt = gimple_build_assign (res, var);
2119 stmts = gimple_seq_alloc ();
2120 si = gsi_last (stmts);
2121 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2123 if (gimple_code (after_stmt) == GIMPLE_PHI)
2125 gsi = gsi_after_labels (gimple_bb (after_stmt));
2126 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2130 gsi = gsi_for_stmt (after_stmt);
2131 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2135 /* Insert on edge E the assignment "RES := EXPR". */
2138 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2140 gimple_stmt_iterator gsi;
2142 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2143 gimple stmt = gimple_build_assign (res, var);
2146 stmts = gimple_seq_alloc ();
2148 gsi = gsi_last (stmts);
2149 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2150 gsi_insert_seq_on_edge (e, stmts);
2151 gsi_commit_edge_inserts ();
2154 /* Creates a zero dimension array of the same type as VAR. */
2157 create_zero_dim_array (tree var, const char *base_name)
2159 tree index_type = build_index_type (integer_zero_node);
2160 tree elt_type = TREE_TYPE (var);
2161 tree array_type = build_array_type (elt_type, index_type);
2162 tree base = create_tmp_var (array_type, base_name);
2164 add_referenced_var (base);
2166 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2170 /* Returns true when PHI is a loop close phi node. */
2173 scalar_close_phi_node_p (gimple phi)
2175 if (gimple_code (phi) != GIMPLE_PHI
2176 || !is_gimple_reg (gimple_phi_result (phi)))
2179 /* Note that loop close phi nodes should have a single argument
2180 because we translated the representation into a canonical form
2181 before Graphite: see canonicalize_loop_closed_ssa_form. */
2182 return (gimple_phi_num_args (phi) == 1);
2185 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2186 dimension array for it. */
2189 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2191 gimple phi = gsi_stmt (*psi);
2192 tree res = gimple_phi_result (phi);
2193 tree var = SSA_NAME_VAR (res);
2194 basic_block bb = gimple_bb (phi);
2195 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2196 tree arg = gimple_phi_arg_def (phi, 0);
2199 /* Note that loop close phi nodes should have a single argument
2200 because we translated the representation into a canonical form
2201 before Graphite: see canonicalize_loop_closed_ssa_form. */
2202 gcc_assert (gimple_phi_num_args (phi) == 1);
2204 /* The phi node can be a non close phi node, when its argument is
2205 invariant, or when it is defined in the same loop as the phi node. */
2206 if (is_gimple_min_invariant (arg)
2207 || SSA_NAME_IS_DEFAULT_DEF (arg)
2208 || gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2209 stmt = gimple_build_assign (res, arg);
2212 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2214 stmt = gimple_build_assign (res, zero_dim_array);
2216 if (TREE_CODE (arg) == SSA_NAME)
2217 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2219 insert_out_of_ssa_copy_on_edge (single_pred_edge (bb),
2220 zero_dim_array, arg);
2223 remove_phi_node (psi, false);
2224 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2225 SSA_NAME_DEF_STMT (res) = stmt;
2228 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2229 dimension array for it. */
2232 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2235 gimple phi = gsi_stmt (*psi);
2236 basic_block bb = gimple_bb (phi);
2237 tree res = gimple_phi_result (phi);
2238 tree var = SSA_NAME_VAR (res);
2239 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2240 gimple_stmt_iterator gsi;
2244 for (i = 0; i < gimple_phi_num_args (phi); i++)
2246 tree arg = gimple_phi_arg_def (phi, i);
2247 edge e = gimple_phi_arg_edge (phi, i);
2249 /* Avoid the insertion of code in the loop latch to please the
2250 pattern matching of the vectorizer. */
2251 if (e->src == bb->loop_father->latch)
2252 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2254 insert_out_of_ssa_copy_on_edge (e, zero_dim_array, arg);
2257 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2260 stmts = gimple_seq_alloc ();
2262 stmt = gimple_build_assign (res, var);
2263 remove_phi_node (psi, false);
2264 SSA_NAME_DEF_STMT (res) = stmt;
2266 gsi = gsi_last (stmts);
2267 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2269 gsi = gsi_after_labels (bb);
2270 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2273 /* Rewrite the degenerate phi node at position PSI from the degenerate
2274 form "x = phi (y, y, ..., y)" to "x = y". */
2277 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2281 gimple_stmt_iterator gsi;
2282 gimple phi = gsi_stmt (*psi);
2283 tree res = gimple_phi_result (phi);
2286 if (!is_gimple_reg (res))
2292 bb = gimple_bb (phi);
2293 rhs = degenerate_phi_result (phi);
2296 stmt = gimple_build_assign (res, rhs);
2297 remove_phi_node (psi, false);
2298 SSA_NAME_DEF_STMT (res) = stmt;
2300 gsi = gsi_after_labels (bb);
2301 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2304 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2307 rewrite_reductions_out_of_ssa (scop_p scop)
2310 gimple_stmt_iterator psi;
2311 sese region = SCOP_REGION (scop);
2314 if (bb_in_sese_p (bb, region))
2315 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2317 gimple phi = gsi_stmt (psi);
2319 if (gimple_phi_num_args (phi) > 1
2320 && degenerate_phi_result (phi))
2321 rewrite_degenerate_phi (&psi);
2323 else if (scalar_close_phi_node_p (phi))
2324 rewrite_close_phi_out_of_ssa (&psi);
2326 else if (reduction_phi_p (region, &psi))
2327 rewrite_phi_out_of_ssa (&psi);
2330 update_ssa (TODO_update_ssa);
2331 #ifdef ENABLE_CHECKING
2332 verify_loop_closed_ssa (true);
2336 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2337 read from ZERO_DIM_ARRAY. */
2340 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2342 tree var = SSA_NAME_VAR (def);
2343 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2344 tree name = make_ssa_name (var, name_stmt);
2346 use_operand_p use_p;
2347 gimple_stmt_iterator gsi;
2349 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2351 gimple_assign_set_lhs (name_stmt, name);
2353 gsi = gsi_for_stmt (use_stmt);
2354 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2356 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2357 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2358 replace_exp (use_p, name);
2360 update_stmt (use_stmt);
2363 /* Rewrite the scalar dependences crossing the boundary of the BB
2364 containing STMT with an array. GSI points to a definition that is
2365 used in a PHI node. */
2368 rewrite_cross_bb_phi_deps (sese region, gimple_stmt_iterator gsi)
2370 gimple stmt = gsi_stmt (gsi);
2371 imm_use_iterator imm_iter;
2375 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2378 def = gimple_assign_lhs (stmt);
2379 if (!is_gimple_reg (def)
2380 || scev_analyzable_p (def, region))
2383 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2384 if (gimple_code (use_stmt) == GIMPLE_PHI)
2386 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2388 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2389 rewrite_close_phi_out_of_ssa (&psi);
2391 rewrite_phi_out_of_ssa (&psi);
2395 /* Rewrite the scalar dependences crossing the boundary of the BB
2396 containing STMT with an array. */
2399 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2401 gimple stmt = gsi_stmt (*gsi);
2402 imm_use_iterator imm_iter;
2405 tree zero_dim_array = NULL_TREE;
2408 switch (gimple_code (stmt))
2411 def = gimple_assign_lhs (stmt);
2415 def = gimple_call_lhs (stmt);
2422 if (!is_gimple_reg (def)
2423 || scev_analyzable_p (def, region))
2426 def_bb = gimple_bb (stmt);
2428 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2429 if (def_bb != gimple_bb (use_stmt)
2430 && !is_gimple_debug (use_stmt))
2432 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2434 if (!zero_dim_array)
2436 zero_dim_array = create_zero_dim_array
2437 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2438 insert_out_of_ssa_copy (zero_dim_array, def,
2439 SSA_NAME_DEF_STMT (def));
2443 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2447 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2450 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2453 gimple_stmt_iterator psi;
2454 sese region = SCOP_REGION (scop);
2457 if (bb_in_sese_p (bb, region))
2458 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2460 rewrite_cross_bb_phi_deps (region, psi);
2461 rewrite_cross_bb_scalar_deps (region, &psi);
2464 update_ssa (TODO_update_ssa);
2465 #ifdef ENABLE_CHECKING
2466 verify_loop_closed_ssa (true);
2470 /* Returns the number of pbbs that are in loops contained in SCOP. */
2473 nb_pbbs_in_loops (scop_p scop)
2479 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2480 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2486 /* Return the number of data references in BB that write in
2490 nb_data_writes_in_bb (basic_block bb)
2493 gimple_stmt_iterator gsi;
2495 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2496 if (gimple_vdef (gsi_stmt (gsi)))
2502 /* Splits STMT out of its current BB. */
2505 split_reduction_stmt (gimple stmt)
2507 gimple_stmt_iterator gsi;
2508 basic_block bb = gimple_bb (stmt);
2511 /* Do not split basic blocks with no writes to memory: the reduction
2512 will be the only write to memory. */
2513 if (nb_data_writes_in_bb (bb) == 0)
2516 split_block (bb, stmt);
2518 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2521 gsi = gsi_last_bb (bb);
2523 e = split_block (bb, gsi_stmt (gsi));
2528 /* Return true when stmt is a reduction operation. */
2531 is_reduction_operation_p (gimple stmt)
2533 enum tree_code code;
2535 gcc_assert (is_gimple_assign (stmt));
2536 code = gimple_assign_rhs_code (stmt);
2538 return flag_associative_math
2539 && commutative_tree_code (code)
2540 && associative_tree_code (code);
2543 /* Returns true when PHI contains an argument ARG. */
2546 phi_contains_arg (gimple phi, tree arg)
2550 for (i = 0; i < gimple_phi_num_args (phi); i++)
2551 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2557 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2560 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2564 if (TREE_CODE (arg) != SSA_NAME)
2567 stmt = SSA_NAME_DEF_STMT (arg);
2569 if (gimple_code (stmt) == GIMPLE_NOP
2570 || gimple_code (stmt) == GIMPLE_CALL)
2573 if (gimple_code (stmt) == GIMPLE_PHI)
2575 if (phi_contains_arg (stmt, lhs))
2580 if (!is_gimple_assign (stmt))
2583 if (gimple_num_ops (stmt) == 2)
2584 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2586 if (is_reduction_operation_p (stmt))
2588 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2591 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2597 /* Detect commutative and associative scalar reductions starting at
2598 the STMT. Return the phi node of the reduction cycle, or NULL. */
2601 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2602 VEC (gimple, heap) **in,
2603 VEC (gimple, heap) **out)
2605 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2610 VEC_safe_push (gimple, heap, *in, stmt);
2611 VEC_safe_push (gimple, heap, *out, stmt);
2615 /* Detect commutative and associative scalar reductions starting at
2616 STMT. Return the phi node of the reduction cycle, or NULL. */
2619 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2620 VEC (gimple, heap) **out)
2622 tree lhs = gimple_assign_lhs (stmt);
2624 if (gimple_num_ops (stmt) == 2)
2625 return detect_commutative_reduction_arg (lhs, stmt,
2626 gimple_assign_rhs1 (stmt),
2629 if (is_reduction_operation_p (stmt))
2631 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2632 gimple_assign_rhs1 (stmt),
2635 : detect_commutative_reduction_arg (lhs, stmt,
2636 gimple_assign_rhs2 (stmt),
2643 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2646 follow_inital_value_to_phi (tree arg, tree lhs)
2650 if (!arg || TREE_CODE (arg) != SSA_NAME)
2653 stmt = SSA_NAME_DEF_STMT (arg);
2655 if (gimple_code (stmt) == GIMPLE_PHI
2656 && phi_contains_arg (stmt, lhs))
2663 /* Return the argument of the loop PHI that is the inital value coming
2664 from outside the loop. */
2667 edge_initial_value_for_loop_phi (gimple phi)
2671 for (i = 0; i < gimple_phi_num_args (phi); i++)
2673 edge e = gimple_phi_arg_edge (phi, i);
2675 if (loop_depth (e->src->loop_father)
2676 < loop_depth (e->dest->loop_father))
2683 /* Return the argument of the loop PHI that is the inital value coming
2684 from outside the loop. */
2687 initial_value_for_loop_phi (gimple phi)
2691 for (i = 0; i < gimple_phi_num_args (phi); i++)
2693 edge e = gimple_phi_arg_edge (phi, i);
2695 if (loop_depth (e->src->loop_father)
2696 < loop_depth (e->dest->loop_father))
2697 return gimple_phi_arg_def (phi, i);
2703 /* Detect commutative and associative scalar reductions starting at
2704 the loop closed phi node STMT. Return the phi node of the
2705 reduction cycle, or NULL. */
2708 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2709 VEC (gimple, heap) **out)
2711 if (scalar_close_phi_node_p (stmt))
2713 tree arg = gimple_phi_arg_def (stmt, 0);
2714 gimple def, loop_phi;
2716 if (TREE_CODE (arg) != SSA_NAME)
2719 /* Note that loop close phi nodes should have a single argument
2720 because we translated the representation into a canonical form
2721 before Graphite: see canonicalize_loop_closed_ssa_form. */
2722 gcc_assert (gimple_phi_num_args (stmt) == 1);
2724 def = SSA_NAME_DEF_STMT (arg);
2725 loop_phi = detect_commutative_reduction (def, in, out);
2729 tree lhs = gimple_phi_result (stmt);
2730 tree init = initial_value_for_loop_phi (loop_phi);
2731 gimple phi = follow_inital_value_to_phi (init, lhs);
2733 VEC_safe_push (gimple, heap, *in, loop_phi);
2734 VEC_safe_push (gimple, heap, *out, stmt);
2741 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2742 return detect_commutative_reduction_assign (stmt, in, out);
2747 /* Translate the scalar reduction statement STMT to an array RED
2748 knowing that its recursive phi node is LOOP_PHI. */
2751 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2754 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2755 tree res = gimple_phi_result (loop_phi);
2756 gimple assign = gimple_build_assign (res, red);
2758 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2760 insert_gsi = gsi_after_labels (gimple_bb (stmt));
2761 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2762 insert_gsi = gsi_for_stmt (stmt);
2763 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2766 /* Removes the PHI node and resets all the debug stmts that are using
2770 remove_phi (gimple phi)
2772 imm_use_iterator imm_iter;
2774 use_operand_p use_p;
2775 gimple_stmt_iterator gsi;
2776 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2780 def = PHI_RESULT (phi);
2781 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2783 stmt = USE_STMT (use_p);
2785 if (is_gimple_debug (stmt))
2787 gimple_debug_bind_reset_value (stmt);
2788 VEC_safe_push (gimple, heap, update, stmt);
2792 for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2795 VEC_free (gimple, heap, update);
2797 gsi = gsi_for_phi_node (phi);
2798 remove_phi_node (&gsi, false);
2801 /* Rewrite out of SSA the reduction described by the loop phi nodes
2802 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2805 IN: stmt, loop_n, ..., loop_0
2806 OUT: stmt, close_n, ..., close_0
2808 the first element is the reduction statement, and the next elements
2809 are the loop and close phi nodes of each of the outer loops. */
2812 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2813 VEC (gimple, heap) *out,
2818 tree red = NULL_TREE;
2820 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2822 gimple close_phi = VEC_index (gimple, out, i);
2826 gimple stmt = loop_phi;
2827 basic_block bb = split_reduction_stmt (stmt);
2829 SET_BIT (reductions, bb->index);
2830 gcc_assert (close_phi == loop_phi);
2832 red = create_zero_dim_array
2833 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2834 translate_scalar_reduction_to_array_for_stmt
2835 (red, stmt, VEC_index (gimple, in, 1));
2839 if (i == VEC_length (gimple, in) - 1)
2841 insert_out_of_ssa_copy (gimple_phi_result (close_phi), red,
2843 insert_out_of_ssa_copy_on_edge
2844 (edge_initial_value_for_loop_phi (loop_phi),
2845 red, initial_value_for_loop_phi (loop_phi));
2848 remove_phi (loop_phi);
2849 remove_phi (close_phi);
2853 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2856 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2859 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2860 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2862 detect_commutative_reduction (close_phi, &in, &out);
2863 if (VEC_length (gimple, in) > 0)
2864 translate_scalar_reduction_to_array (in, out, reductions);
2866 VEC_free (gimple, heap, in);
2867 VEC_free (gimple, heap, out);
2870 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2873 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2876 gimple_stmt_iterator gsi;
2877 edge exit = single_exit (loop);
2882 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2883 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2887 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2890 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2895 if (!flag_associative_math)
2898 FOR_EACH_LOOP (li, loop, 0)
2899 if (loop_in_sese_p (loop, region))
2900 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2902 gsi_commit_edge_inserts ();
2903 update_ssa (TODO_update_ssa);
2904 #ifdef ENABLE_CHECKING
2905 verify_loop_closed_ssa (true);
2909 /* Java does not initialize long_long_integer_type_node. */
2910 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2912 /* Can all ivs be represented by a signed integer?
2913 As CLooG might generate negative values in its expressions, signed loop ivs
2914 are required in the backend. */
2917 scop_ivs_can_be_represented (scop_p scop)
2921 gimple_stmt_iterator psi;
2923 FOR_EACH_LOOP (li, loop, 0)
2925 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
2928 for (psi = gsi_start_phis (loop->header);
2929 !gsi_end_p (psi); gsi_next (&psi))
2931 gimple phi = gsi_stmt (psi);
2932 tree res = PHI_RESULT (phi);
2933 tree type = TREE_TYPE (res);
2935 if (TYPE_UNSIGNED (type)
2936 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
2946 /* Builds the polyhedral representation for a SESE region. */
2949 build_poly_scop (scop_p scop)
2951 sese region = SCOP_REGION (scop);
2952 graphite_dim_t max_dim;
2955 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2956 Once CLooG is fixed, remove this guard. Anyways, it makes no
2957 sense to optimize a scop containing only PBBs that do not belong
2959 if (nb_pbbs_in_loops (scop) == 0)
2962 if (!scop_ivs_can_be_represented (scop))
2965 build_sese_loop_nests (region);
2966 build_sese_conditions (region);
2967 find_scop_parameters (scop);
2969 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2970 if (scop_nb_params (scop) > max_dim)
2973 build_scop_iteration_domain (scop);
2974 build_scop_context (scop);
2976 add_conditions_to_constraints (scop);
2978 build_scop_scattering (scop);
2979 build_scop_drs (scop);
2981 /* This SCoP has been translated to the polyhedral
2983 POLY_SCOP_P (scop) = true;