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;
293 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
296 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
297 if (bap->alias_set != NULL)
298 free (bap->alias_set);
306 free_gimple_bb (struct gimple_bb *gbb)
308 if (GBB_CLOOG_IV_TYPES (gbb))
309 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
311 free_data_refs_aux (GBB_DATA_REFS (gbb));
312 free_data_refs (GBB_DATA_REFS (gbb));
314 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
315 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
316 GBB_BB (gbb)->aux = 0;
320 /* Deletes all gimple bbs in SCOP. */
323 remove_gbbs_in_scop (scop_p scop)
328 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
329 free_gimple_bb (PBB_BLACK_BOX (pbb));
332 /* Deletes all scops in SCOPS. */
335 free_scops (VEC (scop_p, heap) *scops)
340 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
342 remove_gbbs_in_scop (scop);
343 free_sese (SCOP_REGION (scop));
347 VEC_free (scop_p, heap, scops);
350 /* Generates a polyhedral black box only if the bb contains interesting
354 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
356 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
357 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
358 gimple_stmt_iterator gsi;
360 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
362 gimple stmt = gsi_stmt (gsi);
363 if (!is_gimple_debug (stmt))
364 graphite_find_data_references_in_stmt (nest, stmt, &drs);
367 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
368 free_data_refs (drs);
370 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
374 /* Returns true if all predecessors of BB, that are not dominated by BB, are
375 marked in MAP. The predecessors dominated by BB are loop latches and will
376 be handled after BB. */
379 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
384 FOR_EACH_EDGE (e, ei, bb->preds)
385 if (!TEST_BIT (map, e->src->index)
386 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
392 /* Compare the depth of two basic_block's P1 and P2. */
395 compare_bb_depths (const void *p1, const void *p2)
397 const_basic_block const bb1 = *(const_basic_block const*)p1;
398 const_basic_block const bb2 = *(const_basic_block const*)p2;
399 int d1 = loop_depth (bb1->loop_father);
400 int d2 = loop_depth (bb2->loop_father);
411 /* Sort the basic blocks from DOM such that the first are the ones at
412 a deepest loop level. */
415 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
417 size_t len = VEC_length (basic_block, dom);
419 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
423 /* Recursive helper function for build_scops_bbs. */
426 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
428 sese region = SCOP_REGION (scop);
429 VEC (basic_block, heap) *dom;
431 if (TEST_BIT (visited, bb->index)
432 || !bb_in_sese_p (bb, region))
435 try_generate_gimple_bb (scop, bb, reductions);
436 SET_BIT (visited, bb->index);
438 dom = get_dominated_by (CDI_DOMINATORS, bb);
443 graphite_sort_dominated_info (dom);
445 while (!VEC_empty (basic_block, dom))
450 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
451 if (all_non_dominated_preds_marked_p (dom_bb, visited))
453 build_scop_bbs_1 (scop, visited, dom_bb, reductions);
454 VEC_unordered_remove (basic_block, dom, i);
459 VEC_free (basic_block, heap, dom);
462 /* Gather the basic blocks belonging to the SCOP. */
465 build_scop_bbs (scop_p scop, sbitmap reductions)
467 sbitmap visited = sbitmap_alloc (last_basic_block);
468 sese region = SCOP_REGION (scop);
470 sbitmap_zero (visited);
471 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
472 sbitmap_free (visited);
475 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
476 We generate SCATTERING_DIMENSIONS scattering dimensions.
478 CLooG 0.15.0 and previous versions require, that all
479 scattering functions of one CloogProgram have the same number of
480 scattering dimensions, therefore we allow to specify it. This
481 should be removed in future versions of CLooG.
483 The scattering polyhedron consists of these dimensions: scattering,
484 loop_iterators, parameters.
488 | scattering_dimensions = 5
489 | used_scattering_dimensions = 3
497 | Scattering polyhedron:
499 | scattering: {s1, s2, s3, s4, s5}
500 | loop_iterators: {i}
501 | parameters: {p1, p2}
503 | s1 s2 s3 s4 s5 i p1 p2 1
504 | 1 0 0 0 0 0 0 0 -4 = 0
505 | 0 1 0 0 0 -1 0 0 0 = 0
506 | 0 0 1 0 0 0 0 0 -5 = 0 */
509 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
510 poly_bb_p pbb, int scattering_dimensions)
513 scop_p scop = PBB_SCOP (pbb);
514 int nb_iterators = pbb_dim_iter_domain (pbb);
515 int used_scattering_dimensions = nb_iterators * 2 + 1;
516 int nb_params = scop_nb_params (scop);
518 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
521 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
524 ppl_new_Coefficient (&c);
525 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
526 ppl_new_C_Polyhedron_from_space_dimension
527 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
529 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
531 for (i = 0; i < scattering_dimensions; i++)
533 ppl_Constraint_t cstr;
534 ppl_Linear_Expression_t expr;
536 ppl_new_Linear_Expression_with_dimension (&expr, dim);
538 ppl_assign_Coefficient_from_mpz_t (c, v);
539 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
541 /* Textual order inside this loop. */
544 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
545 ppl_Coefficient_to_mpz_t (c, v);
547 ppl_assign_Coefficient_from_mpz_t (c, v);
548 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
551 /* Iterations of this loop. */
552 else /* if ((i % 2) == 1) */
554 int loop = (i - 1) / 2;
556 value_set_si (v, -1);
557 ppl_assign_Coefficient_from_mpz_t (c, v);
558 ppl_Linear_Expression_add_to_coefficient
559 (expr, scattering_dimensions + loop, c);
562 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
563 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
564 ppl_delete_Linear_Expression (expr);
565 ppl_delete_Constraint (cstr);
569 ppl_delete_Coefficient (c);
571 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
574 /* Build for BB the static schedule.
576 The static schedule is a Dewey numbering of the abstract syntax
577 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
579 The following example informally defines the static schedule:
598 Static schedules for A to F:
611 build_scop_scattering (scop_p scop)
615 gimple_bb_p previous_gbb = NULL;
616 ppl_Linear_Expression_t static_schedule;
621 ppl_new_Coefficient (&c);
622 ppl_new_Linear_Expression (&static_schedule);
624 /* We have to start schedules at 0 on the first component and
625 because we cannot compare_prefix_loops against a previous loop,
626 prefix will be equal to zero, and that index will be
627 incremented before copying. */
628 value_set_si (v, -1);
629 ppl_assign_Coefficient_from_mpz_t (c, v);
630 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
632 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
634 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
635 ppl_Linear_Expression_t common;
637 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
640 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
645 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
646 ppl_assign_Linear_Expression_from_Linear_Expression (common,
650 ppl_assign_Coefficient_from_mpz_t (c, v);
651 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
652 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
655 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
657 ppl_delete_Linear_Expression (common);
661 ppl_delete_Coefficient (c);
662 ppl_delete_Linear_Expression (static_schedule);
665 /* Add the value K to the dimension D of the linear expression EXPR. */
668 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
672 ppl_Coefficient_t coef;
674 ppl_new_Coefficient (&coef);
675 ppl_Linear_Expression_coefficient (expr, d, coef);
677 ppl_Coefficient_to_mpz_t (coef, val);
679 value_addto (val, val, k);
681 ppl_assign_Coefficient_from_mpz_t (coef, val);
682 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
684 ppl_delete_Coefficient (coef);
687 /* In the context of scop S, scan E, the right hand side of a scalar
688 evolution function in loop VAR, and translate it to a linear
692 scan_tree_for_params_right_scev (sese s, tree e, int var,
693 ppl_Linear_Expression_t expr)
697 loop_p loop = get_loop (var);
698 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
701 /* Scalar evolutions should happen in the sese region. */
702 gcc_assert (sese_loop_depth (s, loop) > 0);
704 /* We can not deal with parametric strides like:
710 gcc_assert (TREE_CODE (e) == INTEGER_CST);
713 value_set_si (val, int_cst_value (e));
714 add_value_to_dim (l, expr, val);
719 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
720 linear expression EXPR. K is the multiplier of the constant. */
723 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
726 ppl_Coefficient_t coef;
727 int v = int_cst_value (cst);
730 value_set_si (val, 0);
732 /* Necessary to not get "-1 = 2^n - 1". */
734 value_sub_int (val, val, -v);
736 value_add_int (val, val, v);
738 value_multiply (val, val, k);
739 ppl_new_Coefficient (&coef);
740 ppl_assign_Coefficient_from_mpz_t (coef, val);
741 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
743 ppl_delete_Coefficient (coef);
746 /* Saves in NV at index I a new name for variable P. */
749 save_var_name (char **nv, int i, tree p)
751 const char *name = get_name (SSA_NAME_VAR (p));
755 int len = strlen (name) + 16;
756 nv[i] = XNEWVEC (char, len);
757 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p));
761 nv[i] = XNEWVEC (char, 16);
762 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p));
766 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
767 Otherwise returns -1. */
770 parameter_index_in_region_1 (tree name, sese region)
775 gcc_assert (TREE_CODE (name) == SSA_NAME);
777 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
784 /* When the parameter NAME is in REGION, returns its index in
785 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
786 and returns the index of NAME. */
789 parameter_index_in_region (tree name, sese region)
793 gcc_assert (TREE_CODE (name) == SSA_NAME);
795 i = parameter_index_in_region_1 (name, region);
799 gcc_assert (SESE_ADD_PARAMS (region));
801 i = VEC_length (tree, SESE_PARAMS (region));
802 save_var_name (SESE_PARAMS_NAMES (region), i, name);
803 save_clast_name_index (SESE_PARAMS_INDEX (region),
804 SESE_PARAMS_NAMES (region)[i], i);
805 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
809 /* In the context of sese S, scan the expression E and translate it to
810 a linear expression C. When parsing a symbolic multiplication, K
811 represents the constant multiplier of an expression containing
815 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
818 if (e == chrec_dont_know)
821 switch (TREE_CODE (e))
823 case POLYNOMIAL_CHREC:
824 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
825 CHREC_VARIABLE (e), c);
826 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
830 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
835 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
837 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
838 value_multiply (val, val, k);
839 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
843 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
850 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
852 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
853 value_multiply (val, val, k);
854 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
858 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
863 case POINTER_PLUS_EXPR:
864 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
865 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
870 ppl_Linear_Expression_t tmp_expr = NULL;
874 ppl_dimension_type dim;
875 ppl_Linear_Expression_space_dimension (c, &dim);
876 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
879 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
880 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
884 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
886 ppl_delete_Linear_Expression (tmp_expr);
894 ppl_Linear_Expression_t tmp_expr = NULL;
898 ppl_dimension_type dim;
899 ppl_Linear_Expression_space_dimension (c, &dim);
900 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
903 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
907 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
909 ppl_delete_Linear_Expression (tmp_expr);
917 ppl_Linear_Expression_t tmp_expr = NULL;
921 ppl_dimension_type dim;
922 ppl_Linear_Expression_space_dimension (c, &dim);
923 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
926 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
930 ppl_Coefficient_t coef;
933 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
935 ppl_delete_Linear_Expression (tmp_expr);
936 value_init (minus_one);
937 value_set_si (minus_one, -1);
938 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
939 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
940 value_clear (minus_one);
941 ppl_delete_Coefficient (coef);
949 ppl_dimension_type p = parameter_index_in_region (e, s);
953 ppl_dimension_type dim;
954 ppl_Linear_Expression_space_dimension (c, &dim);
955 p += dim - sese_nb_params (s);
956 add_value_to_dim (p, c, k);
963 scan_tree_for_params_int (e, c, k);
967 case NON_LVALUE_EXPR:
968 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
977 /* Find parameters with respect to REGION in BB. We are looking in memory
978 access functions, conditions and loop bounds. */
981 find_params_in_bb (sese region, gimple_bb_p gbb)
987 loop_p loop = GBB_BB (gbb)->loop_father;
991 value_set_si (one, 1);
993 /* Find parameters in the access functions of data references. */
994 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
995 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
996 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
998 /* Find parameters in conditional statements. */
999 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
1001 tree lhs = scalar_evolution_in_region (region, loop,
1002 gimple_cond_lhs (stmt));
1003 tree rhs = scalar_evolution_in_region (region, loop,
1004 gimple_cond_rhs (stmt));
1006 scan_tree_for_params (region, lhs, NULL, one);
1007 scan_tree_for_params (region, rhs, NULL, one);
1013 /* Record the parameters used in the SCOP. A variable is a parameter
1014 in a scop if it does not vary during the execution of that scop. */
1017 find_scop_parameters (scop_p scop)
1021 sese region = SCOP_REGION (scop);
1026 value_set_si (one, 1);
1028 /* Find the parameters used in the loop bounds. */
1029 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1031 tree nb_iters = number_of_latch_executions (loop);
1033 if (!chrec_contains_symbols (nb_iters))
1036 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1037 scan_tree_for_params (region, nb_iters, NULL, one);
1042 /* Find the parameters used in data accesses. */
1043 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1044 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1046 scop_set_nb_params (scop, sese_nb_params (region));
1047 SESE_ADD_PARAMS (region) = false;
1049 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1050 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1053 /* Returns a gimple_bb from BB. */
1055 static inline gimple_bb_p
1056 gbb_from_bb (basic_block bb)
1058 return (gimple_bb_p) bb->aux;
1061 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1062 the constraints for the surrounding loops. */
1065 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1066 ppl_Polyhedron_t outer_ph, int nb)
1069 ppl_Polyhedron_t ph;
1070 tree nb_iters = number_of_latch_executions (loop);
1071 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1072 sese region = SCOP_REGION (scop);
1075 ppl_const_Constraint_System_t pcs;
1076 ppl_dimension_type *map
1077 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1079 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1080 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1081 ppl_Polyhedron_add_constraints (ph, pcs);
1083 for (i = 0; i < (int) nb; i++)
1085 for (i = (int) nb; i < (int) dim - 1; i++)
1089 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1095 ppl_Constraint_t lb;
1096 ppl_Linear_Expression_t lb_expr;
1098 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1099 ppl_set_coef (lb_expr, nb, 1);
1100 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1101 ppl_delete_Linear_Expression (lb_expr);
1102 ppl_Polyhedron_add_constraint (ph, lb);
1103 ppl_delete_Constraint (lb);
1106 if (TREE_CODE (nb_iters) == INTEGER_CST)
1108 ppl_Constraint_t ub;
1109 ppl_Linear_Expression_t ub_expr;
1111 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1113 /* loop_i <= cst_nb_iters */
1114 ppl_set_coef (ub_expr, nb, -1);
1115 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1116 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1117 ppl_Polyhedron_add_constraint (ph, ub);
1118 ppl_delete_Linear_Expression (ub_expr);
1119 ppl_delete_Constraint (ub);
1121 else if (!chrec_contains_undetermined (nb_iters))
1124 ppl_Constraint_t ub;
1125 ppl_Linear_Expression_t ub_expr;
1129 value_set_si (one, 1);
1130 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1131 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1132 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1135 /* N <= estimated_nb_iters
1137 FIXME: This is a workaround that should go away once we will
1138 have the PIP algorithm. */
1139 if (estimated_loop_iterations (loop, true, &nit))
1142 ppl_Linear_Expression_t nb_iters_le;
1143 ppl_Polyhedron_t pol;
1144 graphite_dim_t n = scop_nb_params (scop);
1145 ppl_Coefficient_t coef;
1147 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1148 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1151 /* Construct the negated number of last iteration in VAL. */
1153 mpz_set_double_int (val, nit, false);
1154 value_sub_int (val, val, 1);
1155 value_oppose (val, val);
1157 /* NB_ITERS_LE holds number of last iteration in parametrical form.
1158 Subtract estimated number of last iteration and assert that result
1160 ppl_new_Coefficient_from_mpz_t (&coef, val);
1161 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1162 ppl_delete_Coefficient (coef);
1163 ppl_new_Constraint (&ub, nb_iters_le,
1164 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1165 ppl_Polyhedron_add_constraint (pol, ub);
1167 /* Remove all but last N dimensions from POL to obtain constraints
1170 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - n);
1172 for (i = 0; i < dim - n; i++)
1174 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - n);
1178 /* Add constraints on parameters to SCoP context. */
1180 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1181 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1182 (&constraints_ps, pol);
1183 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1184 (SCOP_CONTEXT (scop), constraints_ps);
1185 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1188 ppl_delete_Polyhedron (pol);
1189 ppl_delete_Linear_Expression (nb_iters_le);
1190 ppl_delete_Constraint (ub);
1194 /* loop_i <= expr_nb_iters */
1195 ppl_set_coef (ub_expr, nb, -1);
1196 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1197 ppl_Polyhedron_add_constraint (ph, ub);
1198 ppl_delete_Linear_Expression (ub_expr);
1199 ppl_delete_Constraint (ub);
1204 if (loop->inner && loop_in_sese_p (loop->inner, region))
1205 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1);
1209 && loop_in_sese_p (loop->next, region))
1210 build_loop_iteration_domains (scop, loop->next, outer_ph, nb);
1212 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1213 ((ppl_Pointset_Powerset_C_Polyhedron_t *) &loop->aux, ph);
1215 ppl_delete_Polyhedron (ph);
1218 /* Returns a linear expression for tree T evaluated in PBB. */
1220 static ppl_Linear_Expression_t
1221 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1224 ppl_Linear_Expression_t res;
1225 ppl_dimension_type dim;
1226 sese region = SCOP_REGION (PBB_SCOP (pbb));
1227 loop_p loop = pbb_loop (pbb);
1229 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1230 ppl_new_Linear_Expression_with_dimension (&res, dim);
1232 t = scalar_evolution_in_region (region, loop, t);
1233 gcc_assert (!automatically_generated_chrec_p (t));
1236 value_set_si (one, 1);
1237 scan_tree_for_params (region, t, res, one);
1243 /* Returns the ppl constraint type from the gimple tree code CODE. */
1245 static enum ppl_enum_Constraint_Type
1246 ppl_constraint_type_from_tree_code (enum tree_code code)
1250 /* We do not support LT and GT to be able to work with C_Polyhedron.
1251 As we work on integer polyhedron "a < b" can be expressed by
1258 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1261 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1264 return PPL_CONSTRAINT_TYPE_EQUAL;
1271 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1272 CODE is used as the comparison operator. This allows us to invert the
1273 condition or to handle inequalities. */
1276 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1277 poly_bb_p pbb, enum tree_code code)
1280 ppl_Coefficient_t c;
1281 ppl_Linear_Expression_t left, right;
1282 ppl_Constraint_t cstr;
1283 enum ppl_enum_Constraint_Type type;
1285 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1286 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1288 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1289 the left or the right side of the expression. */
1290 if (code == LT_EXPR)
1293 value_set_si (v, 1);
1294 ppl_new_Coefficient (&c);
1295 ppl_assign_Coefficient_from_mpz_t (c, v);
1296 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1297 ppl_delete_Coefficient (c);
1302 else if (code == GT_EXPR)
1305 value_set_si (v, 1);
1306 ppl_new_Coefficient (&c);
1307 ppl_assign_Coefficient_from_mpz_t (c, v);
1308 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1309 ppl_delete_Coefficient (c);
1315 type = ppl_constraint_type_from_tree_code (code);
1317 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1319 ppl_new_Constraint (&cstr, left, type);
1320 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1322 ppl_delete_Constraint (cstr);
1323 ppl_delete_Linear_Expression (left);
1324 ppl_delete_Linear_Expression (right);
1327 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1328 operator. This allows us to invert the condition or to handle
1332 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1334 if (code == NE_EXPR)
1336 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1337 ppl_Pointset_Powerset_C_Polyhedron_t right;
1338 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1340 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1341 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1342 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1344 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1347 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1350 /* Add conditions to the domain of PBB. */
1353 add_conditions_to_domain (poly_bb_p pbb)
1357 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1358 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1360 if (VEC_empty (gimple, conditions))
1363 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1364 switch (gimple_code (stmt))
1368 enum tree_code code = gimple_cond_code (stmt);
1370 /* The conditions for ELSE-branches are inverted. */
1371 if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1372 code = invert_tree_comparison (code, false);
1374 add_condition_to_pbb (pbb, stmt, code);
1379 /* Switch statements are not supported right now - fall throught. */
1387 /* Structure used to pass data to dom_walk. */
1391 VEC (gimple, heap) **conditions, **cases;
1395 /* Returns non NULL when BB has a single predecessor and the last
1396 statement of that predecessor is a COND_EXPR. */
1399 single_pred_cond (basic_block bb)
1401 if (single_pred_p (bb))
1403 edge e = single_pred_edge (bb);
1404 basic_block pred = e->src;
1405 gimple stmt = last_stmt (pred);
1407 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1413 /* Call-back for dom_walk executed before visiting the dominated
1417 build_sese_conditions_before (struct dom_walk_data *dw_data,
1420 struct bsc *data = (struct bsc *) dw_data->global_data;
1421 VEC (gimple, heap) **conditions = data->conditions;
1422 VEC (gimple, heap) **cases = data->cases;
1423 gimple_bb_p gbb = gbb_from_bb (bb);
1424 gimple stmt = single_pred_cond (bb);
1426 if (!bb_in_sese_p (bb, data->region))
1431 edge e = single_pred_edge (bb);
1433 VEC_safe_push (gimple, heap, *conditions, stmt);
1435 if (e->flags & EDGE_TRUE_VALUE)
1436 VEC_safe_push (gimple, heap, *cases, stmt);
1438 VEC_safe_push (gimple, heap, *cases, NULL);
1443 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1444 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1448 /* Call-back for dom_walk executed after visiting the dominated
1452 build_sese_conditions_after (struct dom_walk_data *dw_data,
1455 struct bsc *data = (struct bsc *) dw_data->global_data;
1456 VEC (gimple, heap) **conditions = data->conditions;
1457 VEC (gimple, heap) **cases = data->cases;
1459 if (!bb_in_sese_p (bb, data->region))
1462 if (single_pred_cond (bb))
1464 VEC_pop (gimple, *conditions);
1465 VEC_pop (gimple, *cases);
1469 /* Record all conditions in REGION. */
1472 build_sese_conditions (sese region)
1474 struct dom_walk_data walk_data;
1475 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1476 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1479 data.conditions = &conditions;
1480 data.cases = &cases;
1481 data.region = region;
1483 walk_data.dom_direction = CDI_DOMINATORS;
1484 walk_data.initialize_block_local_data = NULL;
1485 walk_data.before_dom_children = build_sese_conditions_before;
1486 walk_data.after_dom_children = build_sese_conditions_after;
1487 walk_data.global_data = &data;
1488 walk_data.block_local_data_size = 0;
1490 init_walk_dominator_tree (&walk_data);
1491 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1492 fini_walk_dominator_tree (&walk_data);
1494 VEC_free (gimple, heap, conditions);
1495 VEC_free (gimple, heap, cases);
1498 /* Traverses all the GBBs of the SCOP and add their constraints to the
1499 iteration domains. */
1502 add_conditions_to_constraints (scop_p scop)
1507 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1508 add_conditions_to_domain (pbb);
1511 /* Add constraints on the possible values of parameter P from the type
1515 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1517 ppl_Constraint_t cstr;
1518 ppl_Linear_Expression_t le;
1519 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1520 tree type = TREE_TYPE (parameter);
1523 /* Disabled until we fix CPU2006. */
1526 if (!INTEGRAL_TYPE_P (type))
1529 lb = TYPE_MIN_VALUE (type);
1530 ub = TYPE_MAX_VALUE (type);
1534 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1535 ppl_set_coef (le, p, -1);
1536 ppl_set_inhomogeneous_tree (le, lb);
1537 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1538 ppl_Polyhedron_add_constraint (context, cstr);
1539 ppl_delete_Linear_Expression (le);
1540 ppl_delete_Constraint (cstr);
1545 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1546 ppl_set_coef (le, p, -1);
1547 ppl_set_inhomogeneous_tree (le, ub);
1548 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1549 ppl_Polyhedron_add_constraint (context, cstr);
1550 ppl_delete_Linear_Expression (le);
1551 ppl_delete_Constraint (cstr);
1555 /* Build the context of the SCOP. The context usually contains extra
1556 constraints that are added to the iteration domains that constrain
1560 build_scop_context (scop_p scop)
1562 ppl_Polyhedron_t context;
1563 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1564 graphite_dim_t p, n = scop_nb_params (scop);
1566 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1568 for (p = 0; p < n; p++)
1569 add_param_constraints (scop, context, p);
1571 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1573 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1574 (SCOP_CONTEXT (scop), ps);
1576 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1577 ppl_delete_Polyhedron (context);
1580 /* Build the iteration domains: the loops belonging to the current
1581 SCOP, and that vary for the execution of the current basic block.
1582 Returns false if there is no loop in SCOP. */
1585 build_scop_iteration_domain (scop_p scop)
1588 sese region = SCOP_REGION (scop);
1590 ppl_Polyhedron_t ph;
1593 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1595 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1596 if (!loop_in_sese_p (loop_outer (loop), region))
1597 build_loop_iteration_domains (scop, loop, ph, 0);
1599 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1600 if (gbb_loop (PBB_BLACK_BOX (pbb))->aux)
1601 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1602 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1603 gbb_loop (PBB_BLACK_BOX (pbb))->aux);
1605 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1606 (&PBB_DOMAIN (pbb), ph);
1608 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1611 ppl_delete_Pointset_Powerset_C_Polyhedron
1612 ((ppl_Pointset_Powerset_C_Polyhedron_t) loop->aux);
1616 ppl_delete_Polyhedron (ph);
1619 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1620 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1621 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1625 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1626 ppl_dimension_type accessp_nb_dims,
1627 ppl_dimension_type dom_nb_dims)
1629 ppl_Linear_Expression_t alias;
1630 ppl_Constraint_t cstr;
1631 int alias_set_num = 0;
1632 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1634 if (bap != NULL && bap->alias_set != NULL)
1635 alias_set_num = *(bap->alias_set);
1637 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1639 ppl_set_coef (alias, dom_nb_dims, 1);
1640 ppl_set_inhomogeneous (alias, -alias_set_num);
1641 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1642 ppl_Polyhedron_add_constraint (accesses, cstr);
1644 ppl_delete_Linear_Expression (alias);
1645 ppl_delete_Constraint (cstr);
1648 /* Add to ACCESSES polyhedron equalities defining the access functions
1649 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1650 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1651 PBB is the poly_bb_p that contains the data reference DR. */
1654 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1655 ppl_dimension_type accessp_nb_dims,
1656 ppl_dimension_type dom_nb_dims,
1659 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1661 scop_p scop = PBB_SCOP (pbb);
1662 sese region = SCOP_REGION (scop);
1666 for (i = 0; i < nb_subscripts; i++)
1668 ppl_Linear_Expression_t fn, access;
1669 ppl_Constraint_t cstr;
1670 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1671 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1673 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1674 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1676 value_set_si (v, 1);
1677 scan_tree_for_params (region, afn, fn, v);
1678 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1680 ppl_set_coef (access, subscript, -1);
1681 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1682 ppl_Polyhedron_add_constraint (accesses, cstr);
1684 ppl_delete_Linear_Expression (fn);
1685 ppl_delete_Linear_Expression (access);
1686 ppl_delete_Constraint (cstr);
1692 /* Add constrains representing the size of the accessed data to the
1693 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1694 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1698 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1699 ppl_dimension_type accessp_nb_dims,
1700 ppl_dimension_type dom_nb_dims)
1702 tree ref = DR_REF (dr);
1703 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1705 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1707 ppl_Linear_Expression_t expr;
1708 ppl_Constraint_t cstr;
1709 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1712 if (TREE_CODE (ref) != ARRAY_REF)
1715 low = array_ref_low_bound (ref);
1717 /* subscript - low >= 0 */
1718 if (host_integerp (low, 0))
1720 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1721 ppl_set_coef (expr, subscript, 1);
1723 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1725 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1726 ppl_Polyhedron_add_constraint (accesses, cstr);
1727 ppl_delete_Linear_Expression (expr);
1728 ppl_delete_Constraint (cstr);
1731 high = array_ref_up_bound (ref);
1733 /* high - subscript >= 0 */
1734 if (high && host_integerp (high, 0)
1735 /* 1-element arrays at end of structures may extend over
1736 their declared size. */
1737 && !(array_at_struct_end_p (ref)
1738 && operand_equal_p (low, high, 0)))
1740 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1741 ppl_set_coef (expr, subscript, -1);
1743 ppl_set_inhomogeneous (expr, int_cst_value (high));
1745 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1746 ppl_Polyhedron_add_constraint (accesses, cstr);
1747 ppl_delete_Linear_Expression (expr);
1748 ppl_delete_Constraint (cstr);
1753 /* Build data accesses for DR in PBB. */
1756 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1758 ppl_Polyhedron_t accesses;
1759 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1760 ppl_dimension_type dom_nb_dims;
1761 ppl_dimension_type accessp_nb_dims;
1762 int dr_base_object_set;
1764 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1766 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1768 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1770 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1771 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1772 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1774 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1776 ppl_delete_Polyhedron (accesses);
1778 if (dr->aux != NULL)
1779 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1781 new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1782 dr, DR_NUM_DIMENSIONS (dr));
1785 /* Write to FILE the alias graph of data references in DIMACS format. */
1788 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1789 VEC (data_reference_p, heap) *drs)
1791 int num_vertex = VEC_length (data_reference_p, drs);
1793 data_reference_p dr1, dr2;
1796 if (num_vertex == 0)
1799 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1800 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1801 if (dr_may_alias_p (dr1, dr2))
1804 fprintf (file, "$\n");
1807 fprintf (file, "c %s\n", comment);
1809 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1811 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1812 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1813 if (dr_may_alias_p (dr1, dr2))
1814 fprintf (file, "e %d %d\n", i + 1, j + 1);
1819 /* Write to FILE the alias graph of data references in DOT format. */
1822 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1823 VEC (data_reference_p, heap) *drs)
1825 int num_vertex = VEC_length (data_reference_p, drs);
1826 data_reference_p dr1, dr2;
1829 if (num_vertex == 0)
1832 fprintf (file, "$\n");
1835 fprintf (file, "c %s\n", comment);
1837 /* First print all the vertices. */
1838 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1839 fprintf (file, "n%d;\n", i);
1841 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1842 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1843 if (dr_may_alias_p (dr1, dr2))
1844 fprintf (file, "n%d n%d\n", i, j);
1849 /* Write to FILE the alias graph of data references in ECC format. */
1852 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1853 VEC (data_reference_p, heap) *drs)
1855 int num_vertex = VEC_length (data_reference_p, drs);
1856 data_reference_p dr1, dr2;
1859 if (num_vertex == 0)
1862 fprintf (file, "$\n");
1865 fprintf (file, "c %s\n", comment);
1867 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1868 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1869 if (dr_may_alias_p (dr1, dr2))
1870 fprintf (file, "%d %d\n", i, j);
1875 /* Check if DR1 and DR2 are in the same object set. */
1878 dr_same_base_object_p (const struct data_reference *dr1,
1879 const struct data_reference *dr2)
1881 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1884 /* Uses DFS component number as representative of alias-sets. Also tests for
1885 optimality by verifying if every connected component is a clique. Returns
1886 true (1) if the above test is true, and false (0) otherwise. */
1889 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1891 int num_vertices = VEC_length (data_reference_p, drs);
1892 struct graph *g = new_graph (num_vertices);
1893 data_reference_p dr1, dr2;
1895 int num_connected_components;
1896 int v_indx1, v_indx2, num_vertices_in_component;
1899 struct graph_edge *e;
1900 int this_component_is_clique, all_components_are_cliques;
1902 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1903 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1904 if (dr_may_alias_p (dr1, dr2))
1910 all_vertices = XNEWVEC (int, num_vertices);
1911 vertices = XNEWVEC (int, num_vertices);
1912 for (i = 0; i < num_vertices; i++)
1913 all_vertices[i] = i;
1915 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1917 for (i = 0; i < g->n_vertices; i++)
1919 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1920 base_alias_pair *bap;
1921 if (dr->aux != NULL)
1922 bap = (base_alias_pair *)(dr->aux);
1923 bap->alias_set = XNEW (int);
1924 *(bap->alias_set) = g->vertices[i].component + 1;
1928 /* Verify if the DFS numbering results in optimal solution. */
1929 for (i = 0; i < num_connected_components; i++)
1931 num_vertices_in_component = 0;
1932 /* Get all vertices whose DFS component number is the same as i. */
1933 for (j = 0; j < num_vertices; j++)
1934 if (g->vertices[j].component == i)
1935 vertices[num_vertices_in_component++] = j;
1937 /* Now test if the vertices in 'vertices' form a clique, by testing
1938 for edges among each pair. */
1939 this_component_is_clique = 1;
1940 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1942 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1944 /* Check if the two vertices are connected by iterating
1945 through all the edges which have one of these are source. */
1946 e = g->vertices[vertices[v_indx2]].pred;
1949 if (e->src == vertices[v_indx1])
1955 this_component_is_clique = 0;
1959 if (!this_component_is_clique)
1960 all_components_are_cliques = 0;
1964 free (all_vertices);
1967 return all_components_are_cliques;
1970 /* Group each data reference in DRS with it's base object set num. */
1973 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1975 int num_vertex = VEC_length (data_reference_p, drs);
1976 struct graph *g = new_graph (num_vertex);
1977 data_reference_p dr1, dr2;
1982 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1983 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1984 if (dr_same_base_object_p (dr1, dr2))
1990 queue = XNEWVEC (int, num_vertex);
1991 for (i = 0; i < num_vertex; i++)
1994 num_component = graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1996 for (i = 0; i < g->n_vertices; i++)
1998 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1999 base_alias_pair *bap;
2000 if (dr->aux != NULL)
2001 bap = (base_alias_pair *)(dr->aux);
2002 bap->base_obj_set = g->vertices[i].component + 1;
2009 /* Build the data references for PBB. */
2012 build_pbb_drs (poly_bb_p pbb)
2015 data_reference_p dr;
2016 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2018 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2019 build_poly_dr (dr, pbb);
2022 /* Build data references in SCOP. */
2025 build_scop_drs (scop_p scop)
2029 data_reference_p dr;
2030 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2032 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2033 for (j = 0; VEC_iterate (data_reference_p,
2034 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2035 VEC_safe_push (data_reference_p, heap, drs, dr);
2037 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2038 dr->aux = XNEW (base_alias_pair);
2040 if (!build_alias_set_optimal_p (drs))
2042 /* TODO: Add support when building alias set is not optimal. */
2046 build_base_obj_set_for_drs (drs);
2048 /* When debugging, enable the following code. This cannot be used
2049 in production compilers. */
2053 FILE *file_dimacs, *file_ecc, *file_dot;
2055 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2056 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2057 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2060 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2061 current_function_name ());
2062 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2063 fclose (file_dimacs);
2067 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2068 current_function_name ());
2069 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2074 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2075 current_function_name ());
2076 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2082 VEC_free (data_reference_p, heap, drs);
2084 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2085 build_pbb_drs (pbb);
2088 /* Return a gsi at the position of the phi node STMT. */
2090 static gimple_stmt_iterator
2091 gsi_for_phi_node (gimple stmt)
2093 gimple_stmt_iterator psi;
2094 basic_block bb = gimple_bb (stmt);
2096 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2097 if (stmt == gsi_stmt (psi))
2104 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2107 insert_out_of_ssa_copy (tree res, tree var)
2111 gimple_stmt_iterator si;
2112 gimple_stmt_iterator gsi;
2114 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2115 stmt = gimple_build_assign (res, var);
2117 stmts = gimple_seq_alloc ();
2118 si = gsi_last (stmts);
2119 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2121 stmt = SSA_NAME_DEF_STMT (var);
2122 if (gimple_code (stmt) == GIMPLE_PHI)
2124 gsi = gsi_after_labels (gimple_bb (stmt));
2125 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2129 gsi = gsi_for_stmt (stmt);
2130 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2134 /* Insert on edge E the assignment "RES := EXPR". */
2137 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2139 gimple_stmt_iterator gsi;
2141 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2142 gimple stmt = gimple_build_assign (res, var);
2145 stmts = gimple_seq_alloc ();
2147 gsi = gsi_last (stmts);
2148 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2149 gsi_insert_seq_on_edge (e, stmts);
2150 gsi_commit_edge_inserts ();
2153 /* Creates a zero dimension array of the same type as VAR. */
2156 create_zero_dim_array (tree var)
2158 tree index_type = build_index_type (integer_zero_node);
2159 tree elt_type = TREE_TYPE (var);
2160 tree array_type = build_array_type (elt_type, index_type);
2161 tree base = create_tmp_var (array_type, "Red");
2163 add_referenced_var (base);
2165 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2169 /* Returns true when PHI is a loop close phi node. */
2172 scalar_close_phi_node_p (gimple phi)
2174 if (gimple_code (phi) != GIMPLE_PHI
2175 || !is_gimple_reg (gimple_phi_result (phi)))
2178 return (gimple_phi_num_args (phi) == 1);
2181 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2182 dimension array for it. */
2185 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2187 gimple phi = gsi_stmt (*psi);
2188 tree res = gimple_phi_result (phi);
2189 tree var = SSA_NAME_VAR (res);
2190 tree zero_dim_array = create_zero_dim_array (var);
2191 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2192 gimple stmt = gimple_build_assign (res, zero_dim_array);
2193 tree arg = gimple_phi_arg_def (phi, 0);
2195 insert_out_of_ssa_copy (zero_dim_array, arg);
2197 remove_phi_node (psi, false);
2198 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2199 SSA_NAME_DEF_STMT (res) = stmt;
2202 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2203 dimension array for it. */
2206 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2209 gimple phi = gsi_stmt (*psi);
2210 basic_block bb = gimple_bb (phi);
2211 tree res = gimple_phi_result (phi);
2212 tree var = SSA_NAME_VAR (res);
2213 tree zero_dim_array = create_zero_dim_array (var);
2214 gimple_stmt_iterator gsi;
2218 for (i = 0; i < gimple_phi_num_args (phi); i++)
2220 tree arg = gimple_phi_arg_def (phi, i);
2222 /* Try to avoid the insertion on edges as much as possible: this
2223 would avoid the insertion of code on loop latch edges, making
2224 the pattern matching of the vectorizer happy, or it would
2225 avoid the insertion of useless basic blocks. Note that it is
2226 incorrect to insert out of SSA copies close by their
2227 definition when they are more than two loop levels apart:
2228 for example, starting from a double nested loop
2238 the following transform is incorrect
2250 whereas inserting the copy on the incomming edge is correct
2262 if (TREE_CODE (arg) == SSA_NAME
2263 && is_gimple_reg (arg)
2264 && gimple_bb (SSA_NAME_DEF_STMT (arg))
2265 && (flow_bb_inside_loop_p (bb->loop_father,
2266 gimple_bb (SSA_NAME_DEF_STMT (arg)))
2267 || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2268 gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2269 insert_out_of_ssa_copy (zero_dim_array, arg);
2271 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2272 zero_dim_array, arg);
2275 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2278 stmts = gimple_seq_alloc ();
2280 stmt = gimple_build_assign (res, var);
2281 remove_phi_node (psi, false);
2282 SSA_NAME_DEF_STMT (res) = stmt;
2284 gsi = gsi_last (stmts);
2285 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2287 gsi = gsi_after_labels (bb);
2288 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2291 /* Return true when DEF can be analyzed in REGION by the scalar
2292 evolution analyzer. */
2295 scev_analyzable_p (tree def, sese region)
2297 gimple stmt = SSA_NAME_DEF_STMT (def);
2298 loop_p loop = loop_containing_stmt (stmt);
2299 tree scev = scalar_evolution_in_region (region, loop, def);
2301 return !chrec_contains_undetermined (scev);
2304 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2305 read from ZERO_DIM_ARRAY. */
2308 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2310 tree var = SSA_NAME_VAR (def);
2311 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2312 tree name = make_ssa_name (var, name_stmt);
2314 use_operand_p use_p;
2315 gimple_stmt_iterator gsi;
2317 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2319 gimple_assign_set_lhs (name_stmt, name);
2321 gsi = gsi_for_stmt (use_stmt);
2322 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2324 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2325 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2326 replace_exp (use_p, name);
2328 update_stmt (use_stmt);
2331 /* Rewrite the scalar dependences crossing the boundary of the BB
2332 containing STMT with an array. */
2335 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2337 gimple stmt = gsi_stmt (*gsi);
2338 imm_use_iterator imm_iter;
2341 tree zero_dim_array = NULL_TREE;
2344 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2347 def = gimple_assign_lhs (stmt);
2348 if (!is_gimple_reg (def)
2349 || scev_analyzable_p (def, region))
2352 def_bb = gimple_bb (stmt);
2354 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2355 if (def_bb != gimple_bb (use_stmt)
2356 && gimple_code (use_stmt) != GIMPLE_PHI)
2358 if (!zero_dim_array)
2360 zero_dim_array = create_zero_dim_array (SSA_NAME_VAR (def));
2361 insert_out_of_ssa_copy (zero_dim_array, def);
2365 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2369 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2372 rewrite_reductions_out_of_ssa (scop_p scop)
2375 gimple_stmt_iterator psi;
2376 sese region = SCOP_REGION (scop);
2379 if (bb_in_sese_p (bb, region))
2380 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2382 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2383 rewrite_close_phi_out_of_ssa (&psi);
2384 else if (reduction_phi_p (region, &psi))
2385 rewrite_phi_out_of_ssa (&psi);
2388 update_ssa (TODO_update_ssa);
2389 #ifdef ENABLE_CHECKING
2391 verify_loop_closed_ssa ();
2395 if (bb_in_sese_p (bb, region))
2396 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2397 rewrite_cross_bb_scalar_deps (region, &psi);
2399 update_ssa (TODO_update_ssa);
2400 #ifdef ENABLE_CHECKING
2402 verify_loop_closed_ssa ();
2406 /* Returns the number of pbbs that are in loops contained in SCOP. */
2409 nb_pbbs_in_loops (scop_p scop)
2415 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2416 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2422 /* Return the number of data references in BB that write in
2426 nb_data_writes_in_bb (basic_block bb)
2429 gimple_stmt_iterator gsi;
2431 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2432 if (gimple_vdef (gsi_stmt (gsi)))
2438 /* Splits STMT out of its current BB. */
2441 split_reduction_stmt (gimple stmt)
2443 gimple_stmt_iterator gsi;
2444 basic_block bb = gimple_bb (stmt);
2447 /* Do not split basic blocks with no writes to memory: the reduction
2448 will be the only write to memory. */
2449 if (nb_data_writes_in_bb (bb) == 0)
2452 split_block (bb, stmt);
2454 gsi = gsi_last_bb (bb);
2456 e = split_block (bb, gsi_stmt (gsi));
2461 /* Return true when stmt is a reduction operation. */
2464 is_reduction_operation_p (gimple stmt)
2466 return flag_associative_math
2467 && commutative_tree_code (gimple_assign_rhs_code (stmt))
2468 && associative_tree_code (gimple_assign_rhs_code (stmt));
2471 /* Returns true when PHI contains an argument ARG. */
2474 phi_contains_arg (gimple phi, tree arg)
2478 for (i = 0; i < gimple_phi_num_args (phi); i++)
2479 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2485 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2488 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2492 if (TREE_CODE (arg) != SSA_NAME)
2495 stmt = SSA_NAME_DEF_STMT (arg);
2497 if (gimple_code (stmt) == GIMPLE_PHI)
2499 if (phi_contains_arg (stmt, lhs))
2504 if (gimple_num_ops (stmt) == 2)
2505 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2507 if (is_reduction_operation_p (stmt))
2509 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2512 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2518 /* Detect commutative and associative scalar reductions starting at
2522 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2523 VEC (gimple, heap) **in,
2524 VEC (gimple, heap) **out)
2526 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2530 VEC_safe_push (gimple, heap, *in, stmt);
2531 VEC_safe_push (gimple, heap, *out, stmt);
2538 /* Detect commutative and associative scalar reductions starting at
2542 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2543 VEC (gimple, heap) **out)
2545 tree lhs = gimple_assign_lhs (stmt);
2547 if (gimple_num_ops (stmt) == 2)
2548 return detect_commutative_reduction_arg (lhs, stmt,
2549 gimple_assign_rhs1 (stmt),
2552 if (is_reduction_operation_p (stmt))
2554 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2555 gimple_assign_rhs1 (stmt),
2558 : detect_commutative_reduction_arg (lhs, stmt,
2559 gimple_assign_rhs2 (stmt),
2566 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2569 follow_inital_value_to_phi (tree arg, tree lhs)
2573 if (!arg || TREE_CODE (arg) != SSA_NAME)
2576 stmt = SSA_NAME_DEF_STMT (arg);
2578 if (gimple_code (stmt) == GIMPLE_PHI
2579 && phi_contains_arg (stmt, lhs))
2586 /* Return the argument of the loop PHI that is the inital value coming
2587 from outside the loop. */
2590 edge_initial_value_for_loop_phi (gimple phi)
2594 for (i = 0; i < gimple_phi_num_args (phi); i++)
2596 edge e = gimple_phi_arg_edge (phi, i);
2598 if (loop_depth (e->src->loop_father)
2599 < loop_depth (e->dest->loop_father))
2606 /* Return the argument of the loop PHI that is the inital value coming
2607 from outside the loop. */
2610 initial_value_for_loop_phi (gimple phi)
2614 for (i = 0; i < gimple_phi_num_args (phi); i++)
2616 edge e = gimple_phi_arg_edge (phi, i);
2618 if (loop_depth (e->src->loop_father)
2619 < loop_depth (e->dest->loop_father))
2620 return gimple_phi_arg_def (phi, i);
2626 /* Detect commutative and associative scalar reductions starting at
2627 the loop closed phi node CLOSE_PHI. */
2630 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2631 VEC (gimple, heap) **out)
2633 if (scalar_close_phi_node_p (stmt))
2635 tree arg = gimple_phi_arg_def (stmt, 0);
2636 gimple def = SSA_NAME_DEF_STMT (arg);
2637 gimple loop_phi = detect_commutative_reduction (def, in, out);
2641 tree lhs = gimple_phi_result (stmt);
2642 tree init = initial_value_for_loop_phi (loop_phi);
2643 gimple phi = follow_inital_value_to_phi (init, lhs);
2645 VEC_safe_push (gimple, heap, *in, loop_phi);
2646 VEC_safe_push (gimple, heap, *out, stmt);
2653 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2654 return detect_commutative_reduction_assign (stmt, in, out);
2659 /* Translate the scalar reduction statement STMT to an array RED
2660 knowing that its recursive phi node is LOOP_PHI. */
2663 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2666 basic_block bb = gimple_bb (stmt);
2667 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2668 tree res = gimple_phi_result (loop_phi);
2669 gimple assign = gimple_build_assign (res, red);
2671 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2673 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2674 insert_gsi = gsi_for_stmt (stmt);
2675 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2678 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2681 insert_copyout (tree red, gimple close_phi)
2683 tree res = gimple_phi_result (close_phi);
2684 basic_block bb = gimple_bb (close_phi);
2685 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2686 gimple assign = gimple_build_assign (res, red);
2688 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2691 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2694 insert_copyin (tree red, gimple loop_phi)
2697 tree init = initial_value_for_loop_phi (loop_phi);
2698 tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2700 force_gimple_operand (expr, &stmts, true, NULL);
2701 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2704 /* Rewrite out of SSA the reduction described by the loop phi nodes
2705 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2708 IN: stmt, loop_n, ..., loop_0
2709 OUT: stmt, close_n, ..., close_0
2711 the first element is the reduction statement, and the next elements
2712 are the loop and close phi nodes of each of the outer loops. */
2715 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2716 VEC (gimple, heap) *out,
2722 gimple_stmt_iterator gsi;
2724 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2726 gimple close_phi = VEC_index (gimple, out, i);
2730 gimple stmt = loop_phi;
2731 basic_block bb = split_reduction_stmt (stmt);
2733 SET_BIT (reductions, bb->index);
2734 gcc_assert (close_phi == loop_phi);
2736 red = create_zero_dim_array (gimple_assign_lhs (stmt));
2737 translate_scalar_reduction_to_array_for_stmt
2738 (red, stmt, VEC_index (gimple, in, 1));
2742 if (i == VEC_length (gimple, in) - 1)
2744 insert_copyout (red, close_phi);
2745 insert_copyin (red, loop_phi);
2748 gsi = gsi_for_phi_node (loop_phi);
2749 remove_phi_node (&gsi, false);
2751 gsi = gsi_for_phi_node (close_phi);
2752 remove_phi_node (&gsi, false);
2756 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2759 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2762 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2763 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2765 detect_commutative_reduction (close_phi, &in, &out);
2766 if (VEC_length (gimple, in) > 0)
2767 translate_scalar_reduction_to_array (in, out, reductions);
2769 VEC_free (gimple, heap, in);
2770 VEC_free (gimple, heap, out);
2773 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2776 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2779 gimple_stmt_iterator gsi;
2780 edge exit = single_exit (loop);
2785 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2786 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2790 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2793 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2798 FOR_EACH_LOOP (li, loop, 0)
2799 if (loop_in_sese_p (loop, region))
2800 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2802 gsi_commit_edge_inserts ();
2803 update_ssa (TODO_update_ssa);
2804 #ifdef ENABLE_CHECKING
2806 verify_loop_closed_ssa ();
2810 /* Builds the polyhedral representation for a SESE region. */
2813 build_poly_scop (scop_p scop)
2815 sese region = SCOP_REGION (scop);
2816 sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2818 sbitmap_zero (reductions);
2819 rewrite_commutative_reductions_out_of_ssa (region, reductions);
2820 rewrite_reductions_out_of_ssa (scop);
2821 build_scop_bbs (scop, reductions);
2822 sbitmap_free (reductions);
2824 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2825 Once CLooG is fixed, remove this guard. Anyways, it makes no
2826 sense to optimize a scop containing only PBBs that do not belong
2828 if (nb_pbbs_in_loops (scop) == 0)
2831 build_sese_loop_nests (region);
2832 build_sese_conditions (region);
2833 find_scop_parameters (scop);
2835 build_scop_iteration_domain (scop);
2836 build_scop_context (scop);
2838 add_conditions_to_constraints (scop);
2840 build_scop_scattering (scop);
2841 build_scop_drs (scop);
2846 /* Always return false. Exercise the scop_to_clast function. */
2849 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2851 #ifdef ENABLE_CHECKING
2852 cloog_prog_clast pc = scop_to_clast (scop);
2853 cloog_clast_free (pc.stmt);
2854 cloog_program_free (pc.prog);