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;
1901 int all_components_are_cliques = 1;
1903 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1904 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1905 if (dr_may_alias_p (dr1, dr2))
1911 all_vertices = XNEWVEC (int, num_vertices);
1912 vertices = XNEWVEC (int, num_vertices);
1913 for (i = 0; i < num_vertices; i++)
1914 all_vertices[i] = i;
1916 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1918 for (i = 0; i < g->n_vertices; i++)
1920 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1921 base_alias_pair *bap;
1922 if (dr->aux != NULL)
1923 bap = (base_alias_pair *)(dr->aux);
1924 bap->alias_set = XNEW (int);
1925 *(bap->alias_set) = g->vertices[i].component + 1;
1929 /* Verify if the DFS numbering results in optimal solution. */
1930 for (i = 0; i < num_connected_components; i++)
1932 num_vertices_in_component = 0;
1933 /* Get all vertices whose DFS component number is the same as i. */
1934 for (j = 0; j < num_vertices; j++)
1935 if (g->vertices[j].component == i)
1936 vertices[num_vertices_in_component++] = j;
1938 /* Now test if the vertices in 'vertices' form a clique, by testing
1939 for edges among each pair. */
1940 this_component_is_clique = 1;
1941 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1943 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1945 /* Check if the two vertices are connected by iterating
1946 through all the edges which have one of these are source. */
1947 e = g->vertices[vertices[v_indx2]].pred;
1950 if (e->src == vertices[v_indx1])
1956 this_component_is_clique = 0;
1960 if (!this_component_is_clique)
1961 all_components_are_cliques = 0;
1965 free (all_vertices);
1968 return all_components_are_cliques;
1971 /* Group each data reference in DRS with it's base object set num. */
1974 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1976 int num_vertex = VEC_length (data_reference_p, drs);
1977 struct graph *g = new_graph (num_vertex);
1978 data_reference_p dr1, dr2;
1983 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1984 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1985 if (dr_same_base_object_p (dr1, dr2))
1991 queue = XNEWVEC (int, num_vertex);
1992 for (i = 0; i < num_vertex; i++)
1995 num_component = graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1997 for (i = 0; i < g->n_vertices; i++)
1999 data_reference_p dr = VEC_index (data_reference_p, drs, i);
2000 base_alias_pair *bap;
2001 if (dr->aux != NULL)
2002 bap = (base_alias_pair *)(dr->aux);
2003 bap->base_obj_set = g->vertices[i].component + 1;
2010 /* Build the data references for PBB. */
2013 build_pbb_drs (poly_bb_p pbb)
2016 data_reference_p dr;
2017 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2019 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2020 build_poly_dr (dr, pbb);
2023 /* Build data references in SCOP. */
2026 build_scop_drs (scop_p scop)
2030 data_reference_p dr;
2031 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2033 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2034 for (j = 0; VEC_iterate (data_reference_p,
2035 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2036 VEC_safe_push (data_reference_p, heap, drs, dr);
2038 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2039 dr->aux = XNEW (base_alias_pair);
2041 if (!build_alias_set_optimal_p (drs))
2043 /* TODO: Add support when building alias set is not optimal. */
2047 build_base_obj_set_for_drs (drs);
2049 /* When debugging, enable the following code. This cannot be used
2050 in production compilers. */
2054 FILE *file_dimacs, *file_ecc, *file_dot;
2056 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2057 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2058 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2061 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2062 current_function_name ());
2063 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2064 fclose (file_dimacs);
2068 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2069 current_function_name ());
2070 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2075 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2076 current_function_name ());
2077 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2083 VEC_free (data_reference_p, heap, drs);
2085 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2086 build_pbb_drs (pbb);
2089 /* Return a gsi at the position of the phi node STMT. */
2091 static gimple_stmt_iterator
2092 gsi_for_phi_node (gimple stmt)
2094 gimple_stmt_iterator psi;
2095 basic_block bb = gimple_bb (stmt);
2097 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2098 if (stmt == gsi_stmt (psi))
2105 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
2108 insert_out_of_ssa_copy (tree res, tree var)
2112 gimple_stmt_iterator si;
2113 gimple_stmt_iterator gsi;
2115 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2116 stmt = gimple_build_assign (res, var);
2118 stmts = gimple_seq_alloc ();
2119 si = gsi_last (stmts);
2120 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2122 stmt = SSA_NAME_DEF_STMT (var);
2123 if (gimple_code (stmt) == GIMPLE_PHI)
2125 gsi = gsi_after_labels (gimple_bb (stmt));
2126 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2130 gsi = gsi_for_stmt (stmt);
2131 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2135 /* Insert on edge E the assignment "RES := EXPR". */
2138 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2140 gimple_stmt_iterator gsi;
2142 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2143 gimple stmt = gimple_build_assign (res, var);
2146 stmts = gimple_seq_alloc ();
2148 gsi = gsi_last (stmts);
2149 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2150 gsi_insert_seq_on_edge (e, stmts);
2151 gsi_commit_edge_inserts ();
2154 /* Creates a zero dimension array of the same type as VAR. */
2157 create_zero_dim_array (tree var)
2159 tree index_type = build_index_type (integer_zero_node);
2160 tree elt_type = TREE_TYPE (var);
2161 tree array_type = build_array_type (elt_type, index_type);
2162 tree base = create_tmp_var (array_type, "Red");
2164 add_referenced_var (base);
2166 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2170 /* Returns true when PHI is a loop close phi node. */
2173 scalar_close_phi_node_p (gimple phi)
2175 if (gimple_code (phi) != GIMPLE_PHI
2176 || !is_gimple_reg (gimple_phi_result (phi)))
2179 return (gimple_phi_num_args (phi) == 1);
2182 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2183 dimension array for it. */
2186 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2188 gimple phi = gsi_stmt (*psi);
2189 tree res = gimple_phi_result (phi);
2190 tree var = SSA_NAME_VAR (res);
2191 tree zero_dim_array = create_zero_dim_array (var);
2192 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2193 gimple stmt = gimple_build_assign (res, zero_dim_array);
2194 tree arg = gimple_phi_arg_def (phi, 0);
2196 insert_out_of_ssa_copy (zero_dim_array, arg);
2198 remove_phi_node (psi, false);
2199 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2200 SSA_NAME_DEF_STMT (res) = stmt;
2203 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2204 dimension array for it. */
2207 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2210 gimple phi = gsi_stmt (*psi);
2211 basic_block bb = gimple_bb (phi);
2212 tree res = gimple_phi_result (phi);
2213 tree var = SSA_NAME_VAR (res);
2214 tree zero_dim_array = create_zero_dim_array (var);
2215 gimple_stmt_iterator gsi;
2219 for (i = 0; i < gimple_phi_num_args (phi); i++)
2221 tree arg = gimple_phi_arg_def (phi, i);
2223 /* Try to avoid the insertion on edges as much as possible: this
2224 would avoid the insertion of code on loop latch edges, making
2225 the pattern matching of the vectorizer happy, or it would
2226 avoid the insertion of useless basic blocks. Note that it is
2227 incorrect to insert out of SSA copies close by their
2228 definition when they are more than two loop levels apart:
2229 for example, starting from a double nested loop
2239 the following transform is incorrect
2251 whereas inserting the copy on the incomming edge is correct
2263 if (TREE_CODE (arg) == SSA_NAME
2264 && is_gimple_reg (arg)
2265 && gimple_bb (SSA_NAME_DEF_STMT (arg))
2266 && (flow_bb_inside_loop_p (bb->loop_father,
2267 gimple_bb (SSA_NAME_DEF_STMT (arg)))
2268 || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2269 gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2270 insert_out_of_ssa_copy (zero_dim_array, arg);
2272 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2273 zero_dim_array, arg);
2276 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2279 stmts = gimple_seq_alloc ();
2281 stmt = gimple_build_assign (res, var);
2282 remove_phi_node (psi, false);
2283 SSA_NAME_DEF_STMT (res) = stmt;
2285 gsi = gsi_last (stmts);
2286 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2288 gsi = gsi_after_labels (bb);
2289 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2292 /* Return true when DEF can be analyzed in REGION by the scalar
2293 evolution analyzer. */
2296 scev_analyzable_p (tree def, sese region)
2298 gimple stmt = SSA_NAME_DEF_STMT (def);
2299 loop_p loop = loop_containing_stmt (stmt);
2300 tree scev = scalar_evolution_in_region (region, loop, def);
2302 return !chrec_contains_undetermined (scev);
2305 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2306 read from ZERO_DIM_ARRAY. */
2309 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2311 tree var = SSA_NAME_VAR (def);
2312 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2313 tree name = make_ssa_name (var, name_stmt);
2315 use_operand_p use_p;
2316 gimple_stmt_iterator gsi;
2318 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2320 gimple_assign_set_lhs (name_stmt, name);
2322 gsi = gsi_for_stmt (use_stmt);
2323 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2325 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2326 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2327 replace_exp (use_p, name);
2329 update_stmt (use_stmt);
2332 /* Rewrite the scalar dependences crossing the boundary of the BB
2333 containing STMT with an array. */
2336 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2338 gimple stmt = gsi_stmt (*gsi);
2339 imm_use_iterator imm_iter;
2342 tree zero_dim_array = NULL_TREE;
2345 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2348 def = gimple_assign_lhs (stmt);
2349 if (!is_gimple_reg (def)
2350 || scev_analyzable_p (def, region))
2353 def_bb = gimple_bb (stmt);
2355 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2356 if (def_bb != gimple_bb (use_stmt)
2357 && gimple_code (use_stmt) != GIMPLE_PHI)
2359 if (!zero_dim_array)
2361 zero_dim_array = create_zero_dim_array (SSA_NAME_VAR (def));
2362 insert_out_of_ssa_copy (zero_dim_array, def);
2366 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2370 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2373 rewrite_reductions_out_of_ssa (scop_p scop)
2376 gimple_stmt_iterator psi;
2377 sese region = SCOP_REGION (scop);
2380 if (bb_in_sese_p (bb, region))
2381 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2383 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2384 rewrite_close_phi_out_of_ssa (&psi);
2385 else if (reduction_phi_p (region, &psi))
2386 rewrite_phi_out_of_ssa (&psi);
2389 update_ssa (TODO_update_ssa);
2390 #ifdef ENABLE_CHECKING
2392 verify_loop_closed_ssa ();
2396 if (bb_in_sese_p (bb, region))
2397 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2398 rewrite_cross_bb_scalar_deps (region, &psi);
2400 update_ssa (TODO_update_ssa);
2401 #ifdef ENABLE_CHECKING
2403 verify_loop_closed_ssa ();
2407 /* Returns the number of pbbs that are in loops contained in SCOP. */
2410 nb_pbbs_in_loops (scop_p scop)
2416 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2417 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2423 /* Return the number of data references in BB that write in
2427 nb_data_writes_in_bb (basic_block bb)
2430 gimple_stmt_iterator gsi;
2432 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2433 if (gimple_vdef (gsi_stmt (gsi)))
2439 /* Splits STMT out of its current BB. */
2442 split_reduction_stmt (gimple stmt)
2444 gimple_stmt_iterator gsi;
2445 basic_block bb = gimple_bb (stmt);
2448 /* Do not split basic blocks with no writes to memory: the reduction
2449 will be the only write to memory. */
2450 if (nb_data_writes_in_bb (bb) == 0)
2453 split_block (bb, stmt);
2455 gsi = gsi_last_bb (bb);
2457 e = split_block (bb, gsi_stmt (gsi));
2462 /* Return true when stmt is a reduction operation. */
2465 is_reduction_operation_p (gimple stmt)
2467 return flag_associative_math
2468 && commutative_tree_code (gimple_assign_rhs_code (stmt))
2469 && associative_tree_code (gimple_assign_rhs_code (stmt));
2472 /* Returns true when PHI contains an argument ARG. */
2475 phi_contains_arg (gimple phi, tree arg)
2479 for (i = 0; i < gimple_phi_num_args (phi); i++)
2480 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2486 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2489 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2493 if (TREE_CODE (arg) != SSA_NAME)
2496 stmt = SSA_NAME_DEF_STMT (arg);
2498 if (gimple_code (stmt) == GIMPLE_PHI)
2500 if (phi_contains_arg (stmt, lhs))
2505 if (gimple_num_ops (stmt) == 2)
2506 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2508 if (is_reduction_operation_p (stmt))
2510 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2513 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2519 /* Detect commutative and associative scalar reductions starting at
2523 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2524 VEC (gimple, heap) **in,
2525 VEC (gimple, heap) **out)
2527 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2531 VEC_safe_push (gimple, heap, *in, stmt);
2532 VEC_safe_push (gimple, heap, *out, stmt);
2539 /* Detect commutative and associative scalar reductions starting at
2543 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2544 VEC (gimple, heap) **out)
2546 tree lhs = gimple_assign_lhs (stmt);
2548 if (gimple_num_ops (stmt) == 2)
2549 return detect_commutative_reduction_arg (lhs, stmt,
2550 gimple_assign_rhs1 (stmt),
2553 if (is_reduction_operation_p (stmt))
2555 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2556 gimple_assign_rhs1 (stmt),
2559 : detect_commutative_reduction_arg (lhs, stmt,
2560 gimple_assign_rhs2 (stmt),
2567 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2570 follow_inital_value_to_phi (tree arg, tree lhs)
2574 if (!arg || TREE_CODE (arg) != SSA_NAME)
2577 stmt = SSA_NAME_DEF_STMT (arg);
2579 if (gimple_code (stmt) == GIMPLE_PHI
2580 && phi_contains_arg (stmt, lhs))
2587 /* Return the argument of the loop PHI that is the inital value coming
2588 from outside the loop. */
2591 edge_initial_value_for_loop_phi (gimple phi)
2595 for (i = 0; i < gimple_phi_num_args (phi); i++)
2597 edge e = gimple_phi_arg_edge (phi, i);
2599 if (loop_depth (e->src->loop_father)
2600 < loop_depth (e->dest->loop_father))
2607 /* Return the argument of the loop PHI that is the inital value coming
2608 from outside the loop. */
2611 initial_value_for_loop_phi (gimple phi)
2615 for (i = 0; i < gimple_phi_num_args (phi); i++)
2617 edge e = gimple_phi_arg_edge (phi, i);
2619 if (loop_depth (e->src->loop_father)
2620 < loop_depth (e->dest->loop_father))
2621 return gimple_phi_arg_def (phi, i);
2627 /* Detect commutative and associative scalar reductions starting at
2628 the loop closed phi node CLOSE_PHI. */
2631 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2632 VEC (gimple, heap) **out)
2634 if (scalar_close_phi_node_p (stmt))
2636 tree arg = gimple_phi_arg_def (stmt, 0);
2637 gimple def = SSA_NAME_DEF_STMT (arg);
2638 gimple loop_phi = detect_commutative_reduction (def, in, out);
2642 tree lhs = gimple_phi_result (stmt);
2643 tree init = initial_value_for_loop_phi (loop_phi);
2644 gimple phi = follow_inital_value_to_phi (init, lhs);
2646 VEC_safe_push (gimple, heap, *in, loop_phi);
2647 VEC_safe_push (gimple, heap, *out, stmt);
2654 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2655 return detect_commutative_reduction_assign (stmt, in, out);
2660 /* Translate the scalar reduction statement STMT to an array RED
2661 knowing that its recursive phi node is LOOP_PHI. */
2664 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2667 basic_block bb = gimple_bb (stmt);
2668 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2669 tree res = gimple_phi_result (loop_phi);
2670 gimple assign = gimple_build_assign (res, red);
2672 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2674 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2675 insert_gsi = gsi_for_stmt (stmt);
2676 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2679 /* Insert the assignment "result (CLOSE_PHI) = RED". */
2682 insert_copyout (tree red, gimple close_phi)
2684 tree res = gimple_phi_result (close_phi);
2685 basic_block bb = gimple_bb (close_phi);
2686 gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2687 gimple assign = gimple_build_assign (res, red);
2689 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2692 /* Insert the assignment "RED = initial_value (LOOP_PHI)". */
2695 insert_copyin (tree red, gimple loop_phi)
2698 tree init = initial_value_for_loop_phi (loop_phi);
2699 tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2701 force_gimple_operand (expr, &stmts, true, NULL);
2702 gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2705 /* Rewrite out of SSA the reduction described by the loop phi nodes
2706 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2709 IN: stmt, loop_n, ..., loop_0
2710 OUT: stmt, close_n, ..., close_0
2712 the first element is the reduction statement, and the next elements
2713 are the loop and close phi nodes of each of the outer loops. */
2716 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2717 VEC (gimple, heap) *out,
2723 gimple_stmt_iterator gsi;
2725 for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2727 gimple close_phi = VEC_index (gimple, out, i);
2731 gimple stmt = loop_phi;
2732 basic_block bb = split_reduction_stmt (stmt);
2734 SET_BIT (reductions, bb->index);
2735 gcc_assert (close_phi == loop_phi);
2737 red = create_zero_dim_array (gimple_assign_lhs (stmt));
2738 translate_scalar_reduction_to_array_for_stmt
2739 (red, stmt, VEC_index (gimple, in, 1));
2743 if (i == VEC_length (gimple, in) - 1)
2745 insert_copyout (red, close_phi);
2746 insert_copyin (red, loop_phi);
2749 gsi = gsi_for_phi_node (loop_phi);
2750 remove_phi_node (&gsi, false);
2752 gsi = gsi_for_phi_node (close_phi);
2753 remove_phi_node (&gsi, false);
2757 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. */
2760 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2763 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2764 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2766 detect_commutative_reduction (close_phi, &in, &out);
2767 if (VEC_length (gimple, in) > 0)
2768 translate_scalar_reduction_to_array (in, out, reductions);
2770 VEC_free (gimple, heap, in);
2771 VEC_free (gimple, heap, out);
2774 /* Rewrites all the commutative reductions from LOOP out of SSA. */
2777 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2780 gimple_stmt_iterator gsi;
2781 edge exit = single_exit (loop);
2786 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2787 rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2791 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2794 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2799 FOR_EACH_LOOP (li, loop, 0)
2800 if (loop_in_sese_p (loop, region))
2801 rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2803 gsi_commit_edge_inserts ();
2804 update_ssa (TODO_update_ssa);
2805 #ifdef ENABLE_CHECKING
2807 verify_loop_closed_ssa ();
2811 /* Builds the polyhedral representation for a SESE region. */
2814 build_poly_scop (scop_p scop)
2816 sese region = SCOP_REGION (scop);
2817 sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2819 sbitmap_zero (reductions);
2820 rewrite_commutative_reductions_out_of_ssa (region, reductions);
2821 rewrite_reductions_out_of_ssa (scop);
2822 build_scop_bbs (scop, reductions);
2823 sbitmap_free (reductions);
2825 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2826 Once CLooG is fixed, remove this guard. Anyways, it makes no
2827 sense to optimize a scop containing only PBBs that do not belong
2829 if (nb_pbbs_in_loops (scop) == 0)
2832 build_sese_loop_nests (region);
2833 build_sese_conditions (region);
2834 find_scop_parameters (scop);
2836 build_scop_iteration_domain (scop);
2837 build_scop_context (scop);
2839 add_conditions_to_constraints (scop);
2841 build_scop_scattering (scop);
2842 build_scop_drs (scop);
2847 /* Always return false. Exercise the scop_to_clast function. */
2850 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2852 #ifdef ENABLE_CHECKING
2853 cloog_prog_clast pc = scop_to_clast (scop);
2854 cloog_clast_free (pc.stmt);
2855 cloog_program_free (pc.prog);