1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-sese-to-poly.h"
55 /* Check if VAR is used in a phi node, that is no loop header. */
58 var_used_in_not_loop_header_phi_node (tree var)
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 corresponding to the initial
80 loop_entry_phi_arg (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))
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 = loop_entry_phi_arg (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 = loop_entry_phi_arg (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)
170 gimple phi = gsi_stmt (*psi);
171 tree res = gimple_phi_result (phi);
173 if (!is_gimple_reg (res))
179 loop = loop_containing_stmt (phi);
181 if (simple_copy_phi_p (phi))
183 /* FIXME: PRE introduces phi nodes like these, for an example,
184 see id-5.f in the fortran graphite testsuite:
186 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
188 remove_simple_copy_phi (psi);
192 /* Main induction variables with constant strides in LOOP are not
194 if (simple_iv (loop, loop, res, &iv, true))
196 if (integer_zerop (iv.step))
197 remove_invariant_phi (region, psi);
204 scev = scalar_evolution_in_region (region, loop, res);
205 if (chrec_contains_undetermined (scev))
208 if (evolution_function_is_invariant_p (scev, loop->num))
210 remove_invariant_phi (region, psi);
214 /* All the other cases are considered reductions. */
218 /* Returns true when BB will be represented in graphite. Return false
219 for the basic blocks that contain code eliminated in the code
220 generation pass: i.e. induction variables and exit conditions. */
223 graphite_stmt_p (sese region, basic_block bb,
224 VEC (data_reference_p, heap) *drs)
226 gimple_stmt_iterator gsi;
227 loop_p loop = bb->loop_father;
229 if (VEC_length (data_reference_p, drs) > 0)
232 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
234 gimple stmt = gsi_stmt (gsi);
236 switch (gimple_code (stmt))
239 /* Control flow expressions can be ignored, as they are
240 represented in the iteration domains and will be
241 regenerated by graphite. */
249 tree var = gimple_assign_lhs (stmt);
251 /* We need these bbs to be able to construct the phi nodes. */
252 if (var_used_in_not_loop_header_phi_node (var))
255 var = scalar_evolution_in_region (region, loop, var);
256 if (chrec_contains_undetermined (var))
270 /* Store the GRAPHITE representation of BB. */
273 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
275 struct gimple_bb *gbb;
277 gbb = XNEW (struct gimple_bb);
280 GBB_DATA_REFS (gbb) = drs;
281 GBB_CONDITIONS (gbb) = NULL;
282 GBB_CONDITION_CASES (gbb) = NULL;
283 GBB_CLOOG_IV_TYPES (gbb) = NULL;
289 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
292 struct data_reference *dr;
294 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
297 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
300 free (bap->alias_set);
309 free_gimple_bb (struct gimple_bb *gbb)
311 if (GBB_CLOOG_IV_TYPES (gbb))
312 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
314 free_data_refs_aux (GBB_DATA_REFS (gbb));
315 free_data_refs (GBB_DATA_REFS (gbb));
317 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
318 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
319 GBB_BB (gbb)->aux = 0;
323 /* Deletes all gimple bbs in SCOP. */
326 remove_gbbs_in_scop (scop_p scop)
331 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
332 free_gimple_bb (PBB_BLACK_BOX (pbb));
335 /* Deletes all scops in SCOPS. */
338 free_scops (VEC (scop_p, heap) *scops)
343 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
345 remove_gbbs_in_scop (scop);
346 free_sese (SCOP_REGION (scop));
350 VEC_free (scop_p, heap, scops);
353 /* Generates a polyhedral black box only if the bb contains interesting
357 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
359 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
360 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
361 gimple_stmt_iterator gsi;
363 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
365 gimple stmt = gsi_stmt (gsi);
366 if (!is_gimple_debug (stmt))
367 graphite_find_data_references_in_stmt (nest, stmt, &drs);
370 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
371 free_data_refs (drs);
373 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
377 /* Returns true if all predecessors of BB, that are not dominated by BB, are
378 marked in MAP. The predecessors dominated by BB are loop latches and will
379 be handled after BB. */
382 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
387 FOR_EACH_EDGE (e, ei, bb->preds)
388 if (!TEST_BIT (map, e->src->index)
389 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
395 /* Compare the depth of two basic_block's P1 and P2. */
398 compare_bb_depths (const void *p1, const void *p2)
400 const_basic_block const bb1 = *(const_basic_block const*)p1;
401 const_basic_block const bb2 = *(const_basic_block const*)p2;
402 int d1 = loop_depth (bb1->loop_father);
403 int d2 = loop_depth (bb2->loop_father);
414 /* Sort the basic blocks from DOM such that the first are the ones at
415 a deepest loop level. */
418 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
420 size_t len = VEC_length (basic_block, dom);
422 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
426 /* Recursive helper function for build_scops_bbs. */
429 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
431 sese region = SCOP_REGION (scop);
432 VEC (basic_block, heap) *dom;
434 if (TEST_BIT (visited, bb->index)
435 || !bb_in_sese_p (bb, region))
438 try_generate_gimple_bb (scop, bb, reductions);
439 SET_BIT (visited, bb->index);
441 dom = get_dominated_by (CDI_DOMINATORS, bb);
446 graphite_sort_dominated_info (dom);
448 while (!VEC_empty (basic_block, dom))
453 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
454 if (all_non_dominated_preds_marked_p (dom_bb, visited))
456 build_scop_bbs_1 (scop, visited, dom_bb, reductions);
457 VEC_unordered_remove (basic_block, dom, i);
462 VEC_free (basic_block, heap, dom);
465 /* Gather the basic blocks belonging to the SCOP. */
468 build_scop_bbs (scop_p scop, sbitmap reductions)
470 sbitmap visited = sbitmap_alloc (last_basic_block);
471 sese region = SCOP_REGION (scop);
473 sbitmap_zero (visited);
474 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
475 sbitmap_free (visited);
478 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
479 We generate SCATTERING_DIMENSIONS scattering dimensions.
481 CLooG 0.15.0 and previous versions require, that all
482 scattering functions of one CloogProgram have the same number of
483 scattering dimensions, therefore we allow to specify it. This
484 should be removed in future versions of CLooG.
486 The scattering polyhedron consists of these dimensions: scattering,
487 loop_iterators, parameters.
491 | scattering_dimensions = 5
492 | used_scattering_dimensions = 3
500 | Scattering polyhedron:
502 | scattering: {s1, s2, s3, s4, s5}
503 | loop_iterators: {i}
504 | parameters: {p1, p2}
506 | s1 s2 s3 s4 s5 i p1 p2 1
507 | 1 0 0 0 0 0 0 0 -4 = 0
508 | 0 1 0 0 0 -1 0 0 0 = 0
509 | 0 0 1 0 0 0 0 0 -5 = 0 */
512 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
513 poly_bb_p pbb, int scattering_dimensions)
516 scop_p scop = PBB_SCOP (pbb);
517 int nb_iterators = pbb_dim_iter_domain (pbb);
518 int used_scattering_dimensions = nb_iterators * 2 + 1;
519 int nb_params = scop_nb_params (scop);
521 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
524 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
527 ppl_new_Coefficient (&c);
528 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
529 ppl_new_C_Polyhedron_from_space_dimension
530 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
532 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
534 for (i = 0; i < scattering_dimensions; i++)
536 ppl_Constraint_t cstr;
537 ppl_Linear_Expression_t expr;
539 ppl_new_Linear_Expression_with_dimension (&expr, dim);
541 ppl_assign_Coefficient_from_mpz_t (c, v);
542 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
544 /* Textual order inside this loop. */
547 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
548 ppl_Coefficient_to_mpz_t (c, v);
550 ppl_assign_Coefficient_from_mpz_t (c, v);
551 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
554 /* Iterations of this loop. */
555 else /* if ((i % 2) == 1) */
557 int loop = (i - 1) / 2;
559 value_set_si (v, -1);
560 ppl_assign_Coefficient_from_mpz_t (c, v);
561 ppl_Linear_Expression_add_to_coefficient
562 (expr, scattering_dimensions + loop, c);
565 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
566 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
567 ppl_delete_Linear_Expression (expr);
568 ppl_delete_Constraint (cstr);
572 ppl_delete_Coefficient (c);
574 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
577 /* Build for BB the static schedule.
579 The static schedule is a Dewey numbering of the abstract syntax
580 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
582 The following example informally defines the static schedule:
601 Static schedules for A to F:
614 build_scop_scattering (scop_p scop)
618 gimple_bb_p previous_gbb = NULL;
619 ppl_Linear_Expression_t static_schedule;
624 ppl_new_Coefficient (&c);
625 ppl_new_Linear_Expression (&static_schedule);
627 /* We have to start schedules at 0 on the first component and
628 because we cannot compare_prefix_loops against a previous loop,
629 prefix will be equal to zero, and that index will be
630 incremented before copying. */
631 value_set_si (v, -1);
632 ppl_assign_Coefficient_from_mpz_t (c, v);
633 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
635 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
637 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
638 ppl_Linear_Expression_t common;
640 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
643 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
648 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
649 ppl_assign_Linear_Expression_from_Linear_Expression (common,
653 ppl_assign_Coefficient_from_mpz_t (c, v);
654 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
655 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
658 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
660 ppl_delete_Linear_Expression (common);
664 ppl_delete_Coefficient (c);
665 ppl_delete_Linear_Expression (static_schedule);
668 /* Add the value K to the dimension D of the linear expression EXPR. */
671 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
675 ppl_Coefficient_t coef;
677 ppl_new_Coefficient (&coef);
678 ppl_Linear_Expression_coefficient (expr, d, coef);
680 ppl_Coefficient_to_mpz_t (coef, val);
682 value_addto (val, val, k);
684 ppl_assign_Coefficient_from_mpz_t (coef, val);
685 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
687 ppl_delete_Coefficient (coef);
690 /* In the context of scop S, scan E, the right hand side of a scalar
691 evolution function in loop VAR, and translate it to a linear
695 scan_tree_for_params_right_scev (sese s, tree e, int var,
696 ppl_Linear_Expression_t expr)
700 loop_p loop = get_loop (var);
701 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
704 /* Scalar evolutions should happen in the sese region. */
705 gcc_assert (sese_loop_depth (s, loop) > 0);
707 /* We can not deal with parametric strides like:
713 gcc_assert (TREE_CODE (e) == INTEGER_CST);
716 value_set_si (val, int_cst_value (e));
717 add_value_to_dim (l, expr, val);
722 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
723 linear expression EXPR. K is the multiplier of the constant. */
726 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
729 ppl_Coefficient_t coef;
730 int v = int_cst_value (cst);
733 value_set_si (val, 0);
735 /* Necessary to not get "-1 = 2^n - 1". */
737 value_sub_int (val, val, -v);
739 value_add_int (val, val, v);
741 value_multiply (val, val, k);
742 ppl_new_Coefficient (&coef);
743 ppl_assign_Coefficient_from_mpz_t (coef, val);
744 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
746 ppl_delete_Coefficient (coef);
749 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
750 Otherwise returns -1. */
753 parameter_index_in_region_1 (tree name, sese region)
758 gcc_assert (TREE_CODE (name) == SSA_NAME);
760 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
767 /* When the parameter NAME is in REGION, returns its index in
768 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
769 and returns the index of NAME. */
772 parameter_index_in_region (tree name, sese region)
776 gcc_assert (TREE_CODE (name) == SSA_NAME);
778 i = parameter_index_in_region_1 (name, region);
782 gcc_assert (SESE_ADD_PARAMS (region));
784 i = VEC_length (tree, SESE_PARAMS (region));
785 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
789 /* In the context of sese S, scan the expression E and translate it to
790 a linear expression C. When parsing a symbolic multiplication, K
791 represents the constant multiplier of an expression containing
795 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
798 if (e == chrec_dont_know)
801 switch (TREE_CODE (e))
803 case POLYNOMIAL_CHREC:
804 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
805 CHREC_VARIABLE (e), c);
806 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
810 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
815 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
817 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
818 value_multiply (val, val, k);
819 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
823 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
830 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
832 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
833 value_multiply (val, val, k);
834 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
838 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
843 case POINTER_PLUS_EXPR:
844 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
845 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
850 ppl_Linear_Expression_t tmp_expr = NULL;
854 ppl_dimension_type dim;
855 ppl_Linear_Expression_space_dimension (c, &dim);
856 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
859 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
860 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
864 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
866 ppl_delete_Linear_Expression (tmp_expr);
874 ppl_Linear_Expression_t tmp_expr = NULL;
878 ppl_dimension_type dim;
879 ppl_Linear_Expression_space_dimension (c, &dim);
880 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
883 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
887 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
889 ppl_delete_Linear_Expression (tmp_expr);
897 ppl_Linear_Expression_t tmp_expr = NULL;
901 ppl_dimension_type dim;
902 ppl_Linear_Expression_space_dimension (c, &dim);
903 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
906 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
910 ppl_Coefficient_t coef;
913 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
915 ppl_delete_Linear_Expression (tmp_expr);
916 value_init (minus_one);
917 value_set_si (minus_one, -1);
918 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
919 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
920 value_clear (minus_one);
921 ppl_delete_Coefficient (coef);
929 ppl_dimension_type p = parameter_index_in_region (e, s);
933 ppl_dimension_type dim;
934 ppl_Linear_Expression_space_dimension (c, &dim);
935 p += dim - sese_nb_params (s);
936 add_value_to_dim (p, c, k);
943 scan_tree_for_params_int (e, c, k);
947 case NON_LVALUE_EXPR:
948 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
957 /* Find parameters with respect to REGION in BB. We are looking in memory
958 access functions, conditions and loop bounds. */
961 find_params_in_bb (sese region, gimple_bb_p gbb)
967 loop_p loop = GBB_BB (gbb)->loop_father;
971 value_set_si (one, 1);
973 /* Find parameters in the access functions of data references. */
974 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
975 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
976 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
978 /* Find parameters in conditional statements. */
979 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
981 tree lhs = scalar_evolution_in_region (region, loop,
982 gimple_cond_lhs (stmt));
983 tree rhs = scalar_evolution_in_region (region, loop,
984 gimple_cond_rhs (stmt));
986 scan_tree_for_params (region, lhs, NULL, one);
987 scan_tree_for_params (region, rhs, NULL, one);
993 /* Record the parameters used in the SCOP. A variable is a parameter
994 in a scop if it does not vary during the execution of that scop. */
997 find_scop_parameters (scop_p scop)
1001 sese region = SCOP_REGION (scop);
1006 value_set_si (one, 1);
1008 /* Find the parameters used in the loop bounds. */
1009 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1011 tree nb_iters = number_of_latch_executions (loop);
1013 if (!chrec_contains_symbols (nb_iters))
1016 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1017 scan_tree_for_params (region, nb_iters, NULL, one);
1022 /* Find the parameters used in data accesses. */
1023 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1024 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1026 scop_set_nb_params (scop, sese_nb_params (region));
1027 SESE_ADD_PARAMS (region) = false;
1029 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1030 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1033 /* Returns a gimple_bb from BB. */
1035 static inline gimple_bb_p
1036 gbb_from_bb (basic_block bb)
1038 return (gimple_bb_p) bb->aux;
1041 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1042 the constraints for the surrounding loops. */
1045 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1046 ppl_Polyhedron_t outer_ph, int nb,
1047 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1050 ppl_Polyhedron_t ph;
1051 tree nb_iters = number_of_latch_executions (loop);
1052 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1053 sese region = SCOP_REGION (scop);
1056 ppl_const_Constraint_System_t pcs;
1057 ppl_dimension_type *map
1058 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1060 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1061 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1062 ppl_Polyhedron_add_constraints (ph, pcs);
1064 for (i = 0; i < (int) nb; i++)
1066 for (i = (int) nb; i < (int) dim - 1; i++)
1070 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1076 ppl_Constraint_t lb;
1077 ppl_Linear_Expression_t lb_expr;
1079 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1080 ppl_set_coef (lb_expr, nb, 1);
1081 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1082 ppl_delete_Linear_Expression (lb_expr);
1083 ppl_Polyhedron_add_constraint (ph, lb);
1084 ppl_delete_Constraint (lb);
1087 if (TREE_CODE (nb_iters) == INTEGER_CST)
1089 ppl_Constraint_t ub;
1090 ppl_Linear_Expression_t ub_expr;
1092 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1094 /* loop_i <= cst_nb_iters */
1095 ppl_set_coef (ub_expr, nb, -1);
1096 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1097 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1098 ppl_Polyhedron_add_constraint (ph, ub);
1099 ppl_delete_Linear_Expression (ub_expr);
1100 ppl_delete_Constraint (ub);
1102 else if (!chrec_contains_undetermined (nb_iters))
1105 ppl_Constraint_t ub;
1106 ppl_Linear_Expression_t ub_expr;
1110 value_set_si (one, 1);
1111 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1112 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1113 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1116 /* N <= estimated_nb_iters
1118 FIXME: This is a workaround that should go away once we will
1119 have the PIP algorithm. */
1120 if (estimated_loop_iterations (loop, true, &nit))
1123 ppl_Linear_Expression_t nb_iters_le;
1124 ppl_Polyhedron_t pol;
1125 graphite_dim_t n = scop_nb_params (scop);
1126 ppl_Coefficient_t coef;
1128 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1129 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1132 /* Construct the negated number of last iteration in VAL. */
1134 mpz_set_double_int (val, nit, false);
1135 value_sub_int (val, val, 1);
1136 value_oppose (val, val);
1138 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1139 Subtract estimated number of last iteration and assert that result
1141 ppl_new_Coefficient_from_mpz_t (&coef, val);
1142 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1143 ppl_delete_Coefficient (coef);
1144 ppl_new_Constraint (&ub, nb_iters_le,
1145 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1146 ppl_Polyhedron_add_constraint (pol, ub);
1148 /* Remove all but last N dimensions from POL to obtain constraints
1151 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - n);
1153 for (i = 0; i < dim - n; i++)
1155 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - n);
1159 /* Add constraints on parameters to SCoP context. */
1161 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1162 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1163 (&constraints_ps, pol);
1164 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1165 (SCOP_CONTEXT (scop), constraints_ps);
1166 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1169 ppl_delete_Polyhedron (pol);
1170 ppl_delete_Linear_Expression (nb_iters_le);
1171 ppl_delete_Constraint (ub);
1175 /* loop_i <= expr_nb_iters */
1176 ppl_set_coef (ub_expr, nb, -1);
1177 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1178 ppl_Polyhedron_add_constraint (ph, ub);
1179 ppl_delete_Linear_Expression (ub_expr);
1180 ppl_delete_Constraint (ub);
1185 if (loop->inner && loop_in_sese_p (loop->inner, region))
1186 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1190 && loop_in_sese_p (loop->next, region))
1191 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1193 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1194 (&domains[loop->num], ph);
1196 ppl_delete_Polyhedron (ph);
1199 /* Returns a linear expression for tree T evaluated in PBB. */
1201 static ppl_Linear_Expression_t
1202 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1205 ppl_Linear_Expression_t res;
1206 ppl_dimension_type dim;
1207 sese region = SCOP_REGION (PBB_SCOP (pbb));
1208 loop_p loop = pbb_loop (pbb);
1210 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1211 ppl_new_Linear_Expression_with_dimension (&res, dim);
1213 t = scalar_evolution_in_region (region, loop, t);
1214 gcc_assert (!automatically_generated_chrec_p (t));
1217 value_set_si (one, 1);
1218 scan_tree_for_params (region, t, res, one);
1224 /* Returns the ppl constraint type from the gimple tree code CODE. */
1226 static enum ppl_enum_Constraint_Type
1227 ppl_constraint_type_from_tree_code (enum tree_code code)
1231 /* We do not support LT and GT to be able to work with C_Polyhedron.
1232 As we work on integer polyhedron "a < b" can be expressed by
1239 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1242 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1245 return PPL_CONSTRAINT_TYPE_EQUAL;
1252 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1253 CODE is used as the comparison operator. This allows us to invert the
1254 condition or to handle inequalities. */
1257 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1258 poly_bb_p pbb, enum tree_code code)
1261 ppl_Coefficient_t c;
1262 ppl_Linear_Expression_t left, right;
1263 ppl_Constraint_t cstr;
1264 enum ppl_enum_Constraint_Type type;
1266 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1267 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1269 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1270 the left or the right side of the expression. */
1271 if (code == LT_EXPR)
1274 value_set_si (v, 1);
1275 ppl_new_Coefficient (&c);
1276 ppl_assign_Coefficient_from_mpz_t (c, v);
1277 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1278 ppl_delete_Coefficient (c);
1283 else if (code == GT_EXPR)
1286 value_set_si (v, 1);
1287 ppl_new_Coefficient (&c);
1288 ppl_assign_Coefficient_from_mpz_t (c, v);
1289 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1290 ppl_delete_Coefficient (c);
1296 type = ppl_constraint_type_from_tree_code (code);
1298 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1300 ppl_new_Constraint (&cstr, left, type);
1301 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1303 ppl_delete_Constraint (cstr);
1304 ppl_delete_Linear_Expression (left);
1305 ppl_delete_Linear_Expression (right);
1308 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1309 operator. This allows us to invert the condition or to handle
1313 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1315 if (code == NE_EXPR)
1317 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1318 ppl_Pointset_Powerset_C_Polyhedron_t right;
1319 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1321 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1322 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1323 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1325 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1328 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1331 /* Add conditions to the domain of PBB. */
1334 add_conditions_to_domain (poly_bb_p pbb)
1338 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1339 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1341 if (VEC_empty (gimple, conditions))
1344 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1345 switch (gimple_code (stmt))
1349 enum tree_code code = gimple_cond_code (stmt);
1351 /* The conditions for ELSE-branches are inverted. */
1352 if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1353 code = invert_tree_comparison (code, false);
1355 add_condition_to_pbb (pbb, stmt, code);
1360 /* Switch statements are not supported right now - fall throught. */
1368 /* Structure used to pass data to dom_walk. */
1372 VEC (gimple, heap) **conditions, **cases;
1376 /* Returns non NULL when BB has a single predecessor and the last
1377 statement of that predecessor is a COND_EXPR. */
1380 single_pred_cond (basic_block bb)
1382 if (single_pred_p (bb))
1384 edge e = single_pred_edge (bb);
1385 basic_block pred = e->src;
1386 gimple stmt = last_stmt (pred);
1388 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1394 /* Call-back for dom_walk executed before visiting the dominated
1398 build_sese_conditions_before (struct dom_walk_data *dw_data,
1401 struct bsc *data = (struct bsc *) dw_data->global_data;
1402 VEC (gimple, heap) **conditions = data->conditions;
1403 VEC (gimple, heap) **cases = data->cases;
1404 gimple_bb_p gbb = gbb_from_bb (bb);
1405 gimple stmt = single_pred_cond (bb);
1407 if (!bb_in_sese_p (bb, data->region))
1412 edge e = single_pred_edge (bb);
1414 VEC_safe_push (gimple, heap, *conditions, stmt);
1416 if (e->flags & EDGE_TRUE_VALUE)
1417 VEC_safe_push (gimple, heap, *cases, stmt);
1419 VEC_safe_push (gimple, heap, *cases, NULL);
1424 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1425 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1429 /* Call-back for dom_walk executed after visiting the dominated
1433 build_sese_conditions_after (struct dom_walk_data *dw_data,
1436 struct bsc *data = (struct bsc *) dw_data->global_data;
1437 VEC (gimple, heap) **conditions = data->conditions;
1438 VEC (gimple, heap) **cases = data->cases;
1440 if (!bb_in_sese_p (bb, data->region))
1443 if (single_pred_cond (bb))
1445 VEC_pop (gimple, *conditions);
1446 VEC_pop (gimple, *cases);
1450 /* Record all conditions in REGION. */
1453 build_sese_conditions (sese region)
1455 struct dom_walk_data walk_data;
1456 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1457 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1460 data.conditions = &conditions;
1461 data.cases = &cases;
1462 data.region = region;
1464 walk_data.dom_direction = CDI_DOMINATORS;
1465 walk_data.initialize_block_local_data = NULL;
1466 walk_data.before_dom_children = build_sese_conditions_before;
1467 walk_data.after_dom_children = build_sese_conditions_after;
1468 walk_data.global_data = &data;
1469 walk_data.block_local_data_size = 0;
1471 init_walk_dominator_tree (&walk_data);
1472 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1473 fini_walk_dominator_tree (&walk_data);
1475 VEC_free (gimple, heap, conditions);
1476 VEC_free (gimple, heap, cases);
1479 /* Traverses all the GBBs of the SCOP and add their constraints to the
1480 iteration domains. */
1483 add_conditions_to_constraints (scop_p scop)
1488 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1489 add_conditions_to_domain (pbb);
1492 /* Add constraints on the possible values of parameter P from the type
1496 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1498 ppl_Constraint_t cstr;
1499 ppl_Linear_Expression_t le;
1500 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1501 tree type = TREE_TYPE (parameter);
1504 if (!INTEGRAL_TYPE_P (type))
1507 lb = TYPE_MIN_VALUE (type);
1508 ub = TYPE_MAX_VALUE (type);
1512 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1513 ppl_set_coef (le, p, -1);
1514 ppl_set_inhomogeneous_tree (le, lb);
1515 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1516 ppl_Polyhedron_add_constraint (context, cstr);
1517 ppl_delete_Linear_Expression (le);
1518 ppl_delete_Constraint (cstr);
1523 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1524 ppl_set_coef (le, p, -1);
1525 ppl_set_inhomogeneous_tree (le, ub);
1526 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1527 ppl_Polyhedron_add_constraint (context, cstr);
1528 ppl_delete_Linear_Expression (le);
1529 ppl_delete_Constraint (cstr);
1533 /* Build the context of the SCOP. The context usually contains extra
1534 constraints that are added to the iteration domains that constrain
1538 build_scop_context (scop_p scop)
1540 ppl_Polyhedron_t context;
1541 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1542 graphite_dim_t p, n = scop_nb_params (scop);
1544 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1546 for (p = 0; p < n; p++)
1547 add_param_constraints (scop, context, p);
1549 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1551 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1552 (SCOP_CONTEXT (scop), ps);
1554 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1555 ppl_delete_Polyhedron (context);
1558 /* Build the iteration domains: the loops belonging to the current
1559 SCOP, and that vary for the execution of the current basic block.
1560 Returns false if there is no loop in SCOP. */
1563 build_scop_iteration_domain (scop_p scop)
1566 sese region = SCOP_REGION (scop);
1568 ppl_Polyhedron_t ph;
1570 int nb_loops = number_of_loops ();
1571 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1572 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1574 for (i = 0; i < nb_loops; i++)
1577 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1579 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1580 if (!loop_in_sese_p (loop_outer (loop), region))
1581 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1583 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1584 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1585 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1586 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1587 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1589 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1590 (&PBB_DOMAIN (pbb), ph);
1592 for (i = 0; i < nb_loops; i++)
1594 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1596 ppl_delete_Polyhedron (ph);
1600 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1601 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1602 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1606 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1607 ppl_dimension_type accessp_nb_dims,
1608 ppl_dimension_type dom_nb_dims)
1610 ppl_Linear_Expression_t alias;
1611 ppl_Constraint_t cstr;
1612 int alias_set_num = 0;
1613 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1615 if (bap && bap->alias_set)
1616 alias_set_num = *(bap->alias_set);
1618 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1620 ppl_set_coef (alias, dom_nb_dims, 1);
1621 ppl_set_inhomogeneous (alias, -alias_set_num);
1622 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1623 ppl_Polyhedron_add_constraint (accesses, cstr);
1625 ppl_delete_Linear_Expression (alias);
1626 ppl_delete_Constraint (cstr);
1629 /* Add to ACCESSES polyhedron equalities defining the access functions
1630 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1631 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1632 PBB is the poly_bb_p that contains the data reference DR. */
1635 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1636 ppl_dimension_type accessp_nb_dims,
1637 ppl_dimension_type dom_nb_dims,
1640 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1642 scop_p scop = PBB_SCOP (pbb);
1643 sese region = SCOP_REGION (scop);
1647 for (i = 0; i < nb_subscripts; i++)
1649 ppl_Linear_Expression_t fn, access;
1650 ppl_Constraint_t cstr;
1651 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1652 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1654 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1655 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1657 value_set_si (v, 1);
1658 scan_tree_for_params (region, afn, fn, v);
1659 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1661 ppl_set_coef (access, subscript, -1);
1662 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1663 ppl_Polyhedron_add_constraint (accesses, cstr);
1665 ppl_delete_Linear_Expression (fn);
1666 ppl_delete_Linear_Expression (access);
1667 ppl_delete_Constraint (cstr);
1673 /* Add constrains representing the size of the accessed data to the
1674 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1675 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1679 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1680 ppl_dimension_type accessp_nb_dims,
1681 ppl_dimension_type dom_nb_dims)
1683 tree ref = DR_REF (dr);
1684 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1686 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1688 ppl_Linear_Expression_t expr;
1689 ppl_Constraint_t cstr;
1690 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1693 if (TREE_CODE (ref) != ARRAY_REF)
1696 low = array_ref_low_bound (ref);
1698 /* subscript - low >= 0 */
1699 if (host_integerp (low, 0))
1701 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1702 ppl_set_coef (expr, subscript, 1);
1704 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1706 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1707 ppl_Polyhedron_add_constraint (accesses, cstr);
1708 ppl_delete_Linear_Expression (expr);
1709 ppl_delete_Constraint (cstr);
1712 high = array_ref_up_bound (ref);
1714 /* high - subscript >= 0 */
1715 if (high && host_integerp (high, 0)
1716 /* 1-element arrays at end of structures may extend over
1717 their declared size. */
1718 && !(array_at_struct_end_p (ref)
1719 && operand_equal_p (low, high, 0)))
1721 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1722 ppl_set_coef (expr, subscript, -1);
1724 ppl_set_inhomogeneous (expr, int_cst_value (high));
1726 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1727 ppl_Polyhedron_add_constraint (accesses, cstr);
1728 ppl_delete_Linear_Expression (expr);
1729 ppl_delete_Constraint (cstr);
1734 /* Build data accesses for DR in PBB. */
1737 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1739 ppl_Polyhedron_t accesses;
1740 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1741 ppl_dimension_type dom_nb_dims;
1742 ppl_dimension_type accessp_nb_dims;
1743 int dr_base_object_set;
1745 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1747 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1749 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1751 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1752 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1753 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1755 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1757 ppl_delete_Polyhedron (accesses);
1760 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1762 new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1763 dr, DR_NUM_DIMENSIONS (dr));
1766 /* Write to FILE the alias graph of data references in DIMACS format. */
1769 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1770 VEC (data_reference_p, heap) *drs)
1772 int num_vertex = VEC_length (data_reference_p, drs);
1774 data_reference_p dr1, dr2;
1777 if (num_vertex == 0)
1780 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1781 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1782 if (dr_may_alias_p (dr1, dr2))
1785 fprintf (file, "$\n");
1788 fprintf (file, "c %s\n", comment);
1790 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1792 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1793 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1794 if (dr_may_alias_p (dr1, dr2))
1795 fprintf (file, "e %d %d\n", i + 1, j + 1);
1800 /* Write to FILE the alias graph of data references in DOT format. */
1803 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1804 VEC (data_reference_p, heap) *drs)
1806 int num_vertex = VEC_length (data_reference_p, drs);
1807 data_reference_p dr1, dr2;
1810 if (num_vertex == 0)
1813 fprintf (file, "$\n");
1816 fprintf (file, "c %s\n", comment);
1818 /* First print all the vertices. */
1819 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1820 fprintf (file, "n%d;\n", i);
1822 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1823 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1824 if (dr_may_alias_p (dr1, dr2))
1825 fprintf (file, "n%d n%d\n", i, j);
1830 /* Write to FILE the alias graph of data references in ECC format. */
1833 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1834 VEC (data_reference_p, heap) *drs)
1836 int num_vertex = VEC_length (data_reference_p, drs);
1837 data_reference_p dr1, dr2;
1840 if (num_vertex == 0)
1843 fprintf (file, "$\n");
1846 fprintf (file, "c %s\n", comment);
1848 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1849 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1850 if (dr_may_alias_p (dr1, dr2))
1851 fprintf (file, "%d %d\n", i, j);
1856 /* Check if DR1 and DR2 are in the same object set. */
1859 dr_same_base_object_p (const struct data_reference *dr1,
1860 const struct data_reference *dr2)
1862 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1865 /* Uses DFS component number as representative of alias-sets. Also tests for
1866 optimality by verifying if every connected component is a clique. Returns
1867 true (1) if the above test is true, and false (0) otherwise. */
1870 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1872 int num_vertices = VEC_length (data_reference_p, drs);
1873 struct graph *g = new_graph (num_vertices);
1874 data_reference_p dr1, dr2;
1876 int num_connected_components;
1877 int v_indx1, v_indx2, num_vertices_in_component;
1880 struct graph_edge *e;
1881 int this_component_is_clique;
1882 int all_components_are_cliques = 1;
1884 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1885 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1886 if (dr_may_alias_p (dr1, dr2))
1892 all_vertices = XNEWVEC (int, num_vertices);
1893 vertices = XNEWVEC (int, num_vertices);
1894 for (i = 0; i < num_vertices; i++)
1895 all_vertices[i] = i;
1897 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1899 for (i = 0; i < g->n_vertices; i++)
1901 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1902 base_alias_pair *bap;
1905 bap = (base_alias_pair *)(dr->aux);
1907 bap->alias_set = XNEW (int);
1908 *(bap->alias_set) = g->vertices[i].component + 1;
1911 /* Verify if the DFS numbering results in optimal solution. */
1912 for (i = 0; i < num_connected_components; i++)
1914 num_vertices_in_component = 0;
1915 /* Get all vertices whose DFS component number is the same as i. */
1916 for (j = 0; j < num_vertices; j++)
1917 if (g->vertices[j].component == i)
1918 vertices[num_vertices_in_component++] = j;
1920 /* Now test if the vertices in 'vertices' form a clique, by testing
1921 for edges among each pair. */
1922 this_component_is_clique = 1;
1923 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1925 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1927 /* Check if the two vertices are connected by iterating
1928 through all the edges which have one of these are source. */
1929 e = g->vertices[vertices[v_indx2]].pred;
1932 if (e->src == vertices[v_indx1])
1938 this_component_is_clique = 0;
1942 if (!this_component_is_clique)
1943 all_components_are_cliques = 0;
1947 free (all_vertices);
1950 return all_components_are_cliques;
1953 /* Group each data reference in DRS with it's base object set num. */
1956 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1958 int num_vertex = VEC_length (data_reference_p, drs);
1959 struct graph *g = new_graph (num_vertex);
1960 data_reference_p dr1, dr2;
1964 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1965 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1966 if (dr_same_base_object_p (dr1, dr2))
1972 queue = XNEWVEC (int, num_vertex);
1973 for (i = 0; i < num_vertex; i++)
1976 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1978 for (i = 0; i < g->n_vertices; i++)
1980 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1981 base_alias_pair *bap;
1984 bap = (base_alias_pair *)(dr->aux);
1986 bap->base_obj_set = g->vertices[i].component + 1;
1993 /* Build the data references for PBB. */
1996 build_pbb_drs (poly_bb_p pbb)
1999 data_reference_p dr;
2000 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2002 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2003 build_poly_dr (dr, pbb);
2006 /* Dump to file the alias graphs for the data references in DRS. */
2009 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2012 FILE *file_dimacs, *file_ecc, *file_dot;
2014 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2017 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2018 current_function_name ());
2019 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2020 fclose (file_dimacs);
2023 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2026 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2027 current_function_name ());
2028 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2032 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2035 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2036 current_function_name ());
2037 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2042 /* Build data references in SCOP. */
2045 build_scop_drs (scop_p scop)
2049 data_reference_p dr;
2050 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2052 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2053 for (j = 0; VEC_iterate (data_reference_p,
2054 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2055 VEC_safe_push (data_reference_p, heap, drs, dr);
2057 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2058 dr->aux = XNEW (base_alias_pair);
2060 if (!build_alias_set_optimal_p (drs))
2062 /* TODO: Add support when building alias set is not optimal. */
2066 build_base_obj_set_for_drs (drs);
2068 /* When debugging, enable the following code. This cannot be used
2069 in production compilers. */
2071 dump_alias_graphs (drs);
2073 VEC_free (data_reference_p, heap, drs);
2075 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2076 build_pbb_drs (pbb);
2079 /* Return a gsi at the position of the phi node STMT. */
2081 static gimple_stmt_iterator
2082 gsi_for_phi_node (gimple stmt)
2084 gimple_stmt_iterator psi;
2085 basic_block bb = gimple_bb (stmt);
2087 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2088 if (stmt == gsi_stmt (psi))
2095 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2098 insert_out_of_ssa_copy (tree res, tree var)
2102 gimple_stmt_iterator si;
2103 gimple_stmt_iterator gsi;
2105 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2106 stmt = gimple_build_assign (res, var);
2108 stmts = gimple_seq_alloc ();
2109 si = gsi_last (stmts);
2110 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2112 stmt = SSA_NAME_DEF_STMT (var);
2113 if (gimple_code (stmt) == GIMPLE_PHI)
2115 gsi = gsi_after_labels (gimple_bb (stmt));
2116 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2120 gsi = gsi_for_stmt (stmt);
2121 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2125 /* Insert on edge E the assignment "RES := EXPR". */
2128 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2130 gimple_stmt_iterator gsi;
2132 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2133 gimple stmt = gimple_build_assign (res, var);
2136 stmts = gimple_seq_alloc ();
2138 gsi = gsi_last (stmts);
2139 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2140 gsi_insert_seq_on_edge (e, stmts);
2141 gsi_commit_edge_inserts ();
2144 /* Creates a zero dimension array of the same type as VAR. */
2147 create_zero_dim_array (tree var, const char *base_name)
2149 tree index_type = build_index_type (integer_zero_node);
2150 tree elt_type = TREE_TYPE (var);
2151 tree array_type = build_array_type (elt_type, index_type);
2152 tree base = create_tmp_var (array_type, base_name);
2154 add_referenced_var (base);
2156 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2160 /* Returns true when PHI is a loop close phi node. */
2163 scalar_close_phi_node_p (gimple phi)
2165 if (gimple_code (phi) != GIMPLE_PHI
2166 || !is_gimple_reg (gimple_phi_result (phi)))
2169 return (gimple_phi_num_args (phi) == 1);
2172 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2173 dimension array for it. */
2176 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2178 gimple phi = gsi_stmt (*psi);
2179 tree res = gimple_phi_result (phi);
2180 tree var = SSA_NAME_VAR (res);
2181 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2182 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2183 gimple stmt = gimple_build_assign (res, zero_dim_array);
2184 tree arg = gimple_phi_arg_def (phi, 0);
2186 if (TREE_CODE (arg) == SSA_NAME)
2187 insert_out_of_ssa_copy (zero_dim_array, arg);
2189 insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)),
2190 zero_dim_array, arg);
2192 remove_phi_node (psi, false);
2193 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2194 SSA_NAME_DEF_STMT (res) = stmt;
2197 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2198 dimension array for it. */
2201 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2204 gimple phi = gsi_stmt (*psi);
2205 basic_block bb = gimple_bb (phi);
2206 tree res = gimple_phi_result (phi);
2207 tree var = SSA_NAME_VAR (res);
2208 tree zero_dim_array = create_zero_dim_array (var, "General_Reduction");
2209 gimple_stmt_iterator gsi;
2213 for (i = 0; i < gimple_phi_num_args (phi); i++)
2215 tree arg = gimple_phi_arg_def (phi, i);
2217 /* Try to avoid the insertion on edges as much as possible: this
2218 would avoid the insertion of code on loop latch edges, making
2219 the pattern matching of the vectorizer happy, or it would
2220 avoid the insertion of useless basic blocks. Note that it is
2221 incorrect to insert out of SSA copies close by their
2222 definition when they are more than two loop levels apart:
2223 for example, starting from a double nested loop
2233 the following transform is incorrect
2245 whereas inserting the copy on the incoming edge is correct
2257 if (TREE_CODE (arg) == SSA_NAME
2258 && is_gimple_reg (arg)
2259 && gimple_bb (SSA_NAME_DEF_STMT (arg))
2260 && (flow_bb_inside_loop_p (bb->loop_father,
2261 gimple_bb (SSA_NAME_DEF_STMT (arg)))
2262 || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2263 gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2264 insert_out_of_ssa_copy (zero_dim_array, arg);
2266 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2267 zero_dim_array, arg);
2270 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2273 stmts = gimple_seq_alloc ();
2275 stmt = gimple_build_assign (res, var);
2276 remove_phi_node (psi, false);
2277 SSA_NAME_DEF_STMT (res) = stmt;
2279 gsi = gsi_last (stmts);
2280 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2282 gsi = gsi_after_labels (bb);
2283 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2286 /* Return true when DEF can be analyzed in REGION by the scalar
2287 evolution analyzer. */
2290 scev_analyzable_p (tree def, sese region)
2292 gimple stmt = SSA_NAME_DEF_STMT (def);
2293 loop_p loop = loop_containing_stmt (stmt);
2294 tree scev = scalar_evolution_in_region (region, loop, def);
2296 return !chrec_contains_undetermined (scev);
2299 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2300 read from ZERO_DIM_ARRAY. */
2303 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2305 tree var = SSA_NAME_VAR (def);
2306 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2307 tree name = make_ssa_name (var, name_stmt);
2309 use_operand_p use_p;
2310 gimple_stmt_iterator gsi;
2312 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2314 gimple_assign_set_lhs (name_stmt, name);
2316 gsi = gsi_for_stmt (use_stmt);
2317 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2319 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2320 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2321 replace_exp (use_p, name);
2323 update_stmt (use_stmt);
2326 /* Rewrite the scalar dependences crossing the boundary of the BB
2327 containing STMT with an array. */
2330 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2332 gimple stmt = gsi_stmt (*gsi);
2333 imm_use_iterator imm_iter;
2336 tree zero_dim_array = NULL_TREE;
2339 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2342 def = gimple_assign_lhs (stmt);
2343 if (!is_gimple_reg (def)
2344 || scev_analyzable_p (def, region))
2347 def_bb = gimple_bb (stmt);
2349 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2350 if (def_bb != gimple_bb (use_stmt)
2351 && gimple_code (use_stmt) != GIMPLE_PHI)
2353 if (!zero_dim_array)
2355 zero_dim_array = create_zero_dim_array
2356 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2357 insert_out_of_ssa_copy (zero_dim_array, def);
2361 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2365 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2368 rewrite_reductions_out_of_ssa (scop_p scop)
2371 gimple_stmt_iterator psi;
2372 sese region = SCOP_REGION (scop);
2375 if (bb_in_sese_p (bb, region))
2376 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2378 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2379 rewrite_close_phi_out_of_ssa (&psi);
2380 else if (reduction_phi_p (region, &psi))
2381 rewrite_phi_out_of_ssa (&psi);
2384 update_ssa (TODO_update_ssa);
2385 #ifdef ENABLE_CHECKING
2387 verify_loop_closed_ssa ();
2391 if (bb_in_sese_p (bb, region))
2392 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2393 rewrite_cross_bb_scalar_deps (region, &psi);
2395 update_ssa (TODO_update_ssa);
2396 #ifdef ENABLE_CHECKING
2398 verify_loop_closed_ssa ();
2402 /* Returns the number of pbbs that are in loops contained in SCOP. */
2405 nb_pbbs_in_loops (scop_p scop)
2411 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2412 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2418 /* Return the number of data references in BB that write in
2422 nb_data_writes_in_bb (basic_block bb)
2425 gimple_stmt_iterator gsi;
2427 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2428 if (gimple_vdef (gsi_stmt (gsi)))
2434 /* Splits STMT out of its current BB. */
2437 split_reduction_stmt (gimple stmt)
2439 gimple_stmt_iterator gsi;
2440 basic_block bb = gimple_bb (stmt);
2443 /* Do not split basic blocks with no writes to memory: the reduction
2444 will be the only write to memory. */
2445 if (nb_data_writes_in_bb (bb) == 0)
2448 split_block (bb, stmt);
2450 if (gsi_one_before_end_p (gsi_start_bb (bb)))
2453 gsi = gsi_last_bb (bb);
2455 e = split_block (bb, gsi_stmt (gsi));
2460 /* Return true when stmt is a reduction operation. */
2463 is_reduction_operation_p (gimple stmt)
2465 enum tree_code code;
2467 gcc_assert (is_gimple_assign (stmt));
2468 code = gimple_assign_rhs_code (stmt);
2470 return flag_associative_math
2471 && commutative_tree_code (code)
2472 && associative_tree_code (code);
2475 /* Returns true when PHI contains an argument ARG. */
2478 phi_contains_arg (gimple phi, tree arg)
2482 for (i = 0; i < gimple_phi_num_args (phi); i++)
2483 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2489 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2492 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2496 if (TREE_CODE (arg) != SSA_NAME)
2499 stmt = SSA_NAME_DEF_STMT (arg);
2501 if (gimple_code (stmt) == GIMPLE_NOP
2502 || gimple_code (stmt) == GIMPLE_CALL)
2505 if (gimple_code (stmt) == GIMPLE_PHI)
2507 if (phi_contains_arg (stmt, lhs))
2512 if (!is_gimple_assign (stmt))
2515 if (gimple_num_ops (stmt) == 2)
2516 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2518 if (is_reduction_operation_p (stmt))
2520 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2523 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2529 /* Detect commutative and associative scalar reductions starting at
2530 the STMT. Return the phi node of the reduction cycle, or NULL. */
2533 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2534 VEC (gimple, heap) **in,
2535 VEC (gimple, heap) **out)
2537 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2542 VEC_safe_push (gimple, heap, *in, stmt);
2543 VEC_safe_push (gimple, heap, *out, stmt);
2547 /* Detect commutative and associative scalar reductions starting at
2548 the STMT. Return the phi node of the reduction cycle, or NULL. */
2551 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2552 VEC (gimple, heap) **out)
2554 tree lhs = gimple_assign_lhs (stmt);
2556 if (gimple_num_ops (stmt) == 2)
2557 return detect_commutative_reduction_arg (lhs, stmt,
2558 gimple_assign_rhs1 (stmt),
2561 if (is_reduction_operation_p (stmt))
2563 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2564 gimple_assign_rhs1 (stmt),
2567 : detect_commutative_reduction_arg (lhs, stmt,
2568 gimple_assign_rhs2 (stmt),
2575 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2578 follow_inital_value_to_phi (tree arg, tree lhs)
2582 if (!arg || TREE_CODE (arg) != SSA_NAME)
2585 stmt = SSA_NAME_DEF_STMT (arg);
2587 if (gimple_code (stmt) == GIMPLE_PHI
2588 && phi_contains_arg (stmt, lhs))
2595 /* Return the argument of the loop PHI that is the inital value coming
2596 from outside the loop. */
2599 edge_initial_value_for_loop_phi (gimple phi)
2603 for (i = 0; i < gimple_phi_num_args (phi); i++)
2605 edge e = gimple_phi_arg_edge (phi, i);
2607 if (loop_depth (e->src->loop_father)
2608 < loop_depth (e->dest->loop_father))
2615 /* Return the argument of the loop PHI that is the inital value coming
2616 from outside the loop. */
2619 initial_value_for_loop_phi (gimple phi)
2623 for (i = 0; i < gimple_phi_num_args (phi); i++)
2625 edge e = gimple_phi_arg_edge (phi, i);
2627 if (loop_depth (e->src->loop_father)
2628 < loop_depth (e->dest->loop_father))
2629 return gimple_phi_arg_def (phi, i);
2635 /* Detect commutative and associative scalar reductions starting at
2636 the loop closed phi node CLOSE_PHI. Return the phi node of the
2637 reduction cycle, or NULL. */
2640 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2641 VEC (gimple, heap) **out)
2643 if (scalar_close_phi_node_p (stmt))
2645 tree arg = gimple_phi_arg_def (stmt, 0);
2646 gimple def, loop_phi;
2648 if (TREE_CODE (arg) != SSA_NAME)
2651 def = SSA_NAME_DEF_STMT (arg);
2652 loop_phi = detect_commutative_reduction (def, in, out);
2656 tree lhs = gimple_phi_result (stmt);
2657 tree init = initial_value_for_loop_phi (loop_phi);
2658 gimple phi = follow_inital_value_to_phi (init, lhs);
2660 VEC_safe_push (gimple, heap, *in, loop_phi);
2661 VEC_safe_push (gimple, heap, *out, stmt);
2668 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2669 return detect_commutative_reduction_assign (stmt, in, out);
2674 /* Translate the scalar reduction statement STMT to an array RED
2675 knowing that its recursive phi node is LOOP_PHI. */
2678 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2681 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2682 tree res = gimple_phi_result (loop_phi);
2683 gimple assign = gimple_build_assign (res, red);
2685 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2687 insert_gsi = gsi_after_labels (gimple_bb (stmt));
2688 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2689 insert_gsi = gsi_for_stmt (stmt);
2690 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2693 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2696 insert_copyout (tree red, gimple close_phi)
2698 tree res = gimple_phi_result (close_phi);
2699 basic_block bb = gimple_bb (close_phi);
2700 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2701 gimple assign = gimple_build_assign (res, red);
2703 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2706 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2709 insert_copyin (tree red, gimple loop_phi)
2712 tree init = initial_value_for_loop_phi (loop_phi);
2713 tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2715 force_gimple_operand (expr, &stmts, true, NULL);
2716 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2719 /* Removes the PHI node and resets all the debug stmts that are using
2723 remove_phi (gimple phi)
2725 imm_use_iterator imm_iter;
2727 use_operand_p use_p;
2728 gimple_stmt_iterator gsi;
2729 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2733 def = PHI_RESULT (phi);
2734 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2736 stmt = USE_STMT (use_p);
2738 if (is_gimple_debug (stmt))
2740 gimple_debug_bind_reset_value (stmt);
2741 VEC_safe_push (gimple, heap, update, stmt);
2745 for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2748 VEC_free (gimple, heap, update);
2750 gsi = gsi_for_phi_node (phi);
2751 remove_phi_node (&gsi, false);
2754 /* Rewrite out of SSA the reduction described by the loop phi nodes
2755 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2758 IN: stmt, loop_n, ..., loop_0
2759 OUT: stmt, close_n, ..., close_0
2761 the first element is the reduction statement, and the next elements
2762 are the loop and close phi nodes of each of the outer loops. */
2765 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2766 VEC (gimple, heap) *out,
2773 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2775 gimple close_phi = VEC_index (gimple, out, i);
2779 gimple stmt = loop_phi;
2780 basic_block bb = split_reduction_stmt (stmt);
2782 SET_BIT (reductions, bb->index);
2783 gcc_assert (close_phi == loop_phi);
2785 red = create_zero_dim_array
2786 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2787 translate_scalar_reduction_to_array_for_stmt
2788 (red, stmt, VEC_index (gimple, in, 1));
2792 if (i == VEC_length (gimple, in) - 1)
2794 insert_copyout (red, close_phi);
2795 insert_copyin (red, loop_phi);
2798 remove_phi (loop_phi);
2799 remove_phi (close_phi);
2803 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2806 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2809 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2810 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2812 detect_commutative_reduction (close_phi, &in, &out);
2813 if (VEC_length (gimple, in) > 0)
2814 translate_scalar_reduction_to_array (in, out, reductions);
2816 VEC_free (gimple, heap, in);
2817 VEC_free (gimple, heap, out);
2820 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2823 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2826 gimple_stmt_iterator gsi;
2827 edge exit = single_exit (loop);
2832 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2833 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2837 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2840 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2845 FOR_EACH_LOOP (li, loop, 0)
2846 if (loop_in_sese_p (loop, region))
2847 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2849 gsi_commit_edge_inserts ();
2850 update_ssa (TODO_update_ssa);
2851 #ifdef ENABLE_CHECKING
2853 verify_loop_closed_ssa ();
2857 /* A LOOP is in normal form for Graphite when it contains only one
2858 scalar phi node that defines the main induction variable of the
2859 loop, only one increment of the IV, and only one exit condition. */
2862 graphite_loop_normal_form (loop_p loop)
2864 struct tree_niter_desc niter;
2867 edge exit = single_dom_exit (loop);
2869 bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2871 /* At this point we should know the number of iterations, */
2872 gcc_assert (known_niter);
2874 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2877 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2879 loop->single_iv = canonicalize_loop_ivs (loop, &nit);
2882 /* Rewrite all the loops of SCOP in normal form: one induction
2883 variable per loop. */
2886 scop_canonicalize_loops (scop_p scop)
2891 FOR_EACH_LOOP (li, loop, 0)
2892 if (loop_in_sese_p (loop, SCOP_REGION (scop)))
2893 graphite_loop_normal_form (loop);
2896 /* Builds the polyhedral representation for a SESE region. */
2899 build_poly_scop (scop_p scop)
2901 sese region = SCOP_REGION (scop);
2902 sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2904 sbitmap_zero (reductions);
2905 rewrite_commutative_reductions_out_of_ssa (region, reductions);
2906 rewrite_reductions_out_of_ssa (scop);
2907 build_scop_bbs (scop, reductions);
2908 sbitmap_free (reductions);
2910 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2911 Once CLooG is fixed, remove this guard. Anyways, it makes no
2912 sense to optimize a scop containing only PBBs that do not belong
2914 if (nb_pbbs_in_loops (scop) == 0)
2917 scop_canonicalize_loops (scop);
2918 build_sese_loop_nests (region);
2919 build_sese_conditions (region);
2920 find_scop_parameters (scop);
2922 build_scop_iteration_domain (scop);
2923 build_scop_context (scop);
2925 add_conditions_to_constraints (scop);
2927 build_scop_scattering (scop);
2928 build_scop_drs (scop);
2929 POLY_SCOP_P (scop) = true;
2934 /* Always return false. Exercise the scop_to_clast function. */
2937 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2939 #ifdef ENABLE_CHECKING
2940 cloog_prog_clast pc = scop_to_clast (scop);
2941 cloog_clast_free (pc.stmt);
2942 cloog_program_free (pc.prog);