1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
47 #include "graphite-ppl.h"
49 #include "graphite-poly.h"
50 #include "graphite-scop-detection.h"
51 #include "graphite-sese-to-poly.h"
53 /* Check if VAR is used in a phi node, that is no loop header. */
56 var_used_in_not_loop_header_phi_node (tree var)
58 imm_use_iterator imm_iter;
62 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
64 basic_block bb = gimple_bb (stmt);
66 if (gimple_code (stmt) == GIMPLE_PHI
67 && bb->loop_father->header != bb)
74 /* Returns the index of the PHI argument defined in the outermost
78 phi_arg_in_outermost_loop (gimple phi)
80 loop_p loop = gimple_bb (phi)->loop_father;
83 for (i = 0; i < gimple_phi_num_args (phi); i++)
84 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
86 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
94 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
97 remove_simple_copy_phi (gimple_stmt_iterator *psi)
99 gimple phi = gsi_stmt (*psi);
100 tree res = gimple_phi_result (phi);
101 size_t entry = phi_arg_in_outermost_loop (phi);
102 tree init = gimple_phi_arg_def (phi, entry);
103 gimple stmt = gimple_build_assign (res, init);
104 edge e = gimple_phi_arg_edge (phi, entry);
106 remove_phi_node (psi, false);
107 gsi_insert_on_edge_immediate (e, stmt);
108 SSA_NAME_DEF_STMT (res) = stmt;
111 /* Removes an invariant phi node at position PSI by inserting on the
112 loop ENTRY edge the assignment RES = INIT. */
115 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
117 gimple phi = gsi_stmt (*psi);
118 loop_p loop = loop_containing_stmt (phi);
119 tree res = gimple_phi_result (phi);
120 tree scev = scalar_evolution_in_region (region, loop, res);
121 size_t entry = phi_arg_in_outermost_loop (phi);
122 edge e = gimple_phi_arg_edge (phi, entry);
126 gimple_stmt_iterator gsi;
128 if (tree_contains_chrecs (scev, NULL))
129 scev = gimple_phi_arg_def (phi, entry);
131 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
132 stmt = gimple_build_assign (res, var);
133 remove_phi_node (psi, false);
136 stmts = gimple_seq_alloc ();
138 gsi = gsi_last (stmts);
139 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
140 gsi_insert_seq_on_edge (e, stmts);
141 gsi_commit_edge_inserts ();
142 SSA_NAME_DEF_STMT (res) = stmt;
145 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
148 simple_copy_phi_p (gimple phi)
152 if (gimple_phi_num_args (phi) != 2)
155 res = gimple_phi_result (phi);
156 return (res == gimple_phi_arg_def (phi, 0)
157 || res == gimple_phi_arg_def (phi, 1));
160 /* Returns true when the phi node at position PSI is a reduction phi
161 node in REGION. Otherwise moves the pointer PSI to the next phi to
165 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
168 gimple phi = gsi_stmt (*psi);
169 tree res = gimple_phi_result (phi);
171 loop = loop_containing_stmt (phi);
173 if (simple_copy_phi_p (phi))
175 /* PRE introduces phi nodes like these, for an example,
176 see id-5.f in the fortran graphite testsuite:
178 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
180 remove_simple_copy_phi (psi);
184 if (scev_analyzable_p (res, region))
186 tree scev = scalar_evolution_in_region (region, loop, res);
188 if (evolution_function_is_invariant_p (scev, loop->num))
189 remove_invariant_phi (region, psi);
196 /* All the other cases are considered reductions. */
200 /* Returns true when BB will be represented in graphite. Return false
201 for the basic blocks that contain code eliminated in the code
202 generation pass: i.e. induction variables and exit conditions. */
205 graphite_stmt_p (sese region, basic_block bb,
206 VEC (data_reference_p, heap) *drs)
208 gimple_stmt_iterator gsi;
209 loop_p loop = bb->loop_father;
211 if (VEC_length (data_reference_p, drs) > 0)
214 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
216 gimple stmt = gsi_stmt (gsi);
218 switch (gimple_code (stmt))
221 /* Control flow expressions can be ignored, as they are
222 represented in the iteration domains and will be
223 regenerated by graphite. */
231 tree var = gimple_assign_lhs (stmt);
233 /* We need these bbs to be able to construct the phi nodes. */
234 if (var_used_in_not_loop_header_phi_node (var))
237 var = scalar_evolution_in_region (region, loop, var);
238 if (chrec_contains_undetermined (var))
252 /* Store the GRAPHITE representation of BB. */
255 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
257 struct gimple_bb *gbb;
259 gbb = XNEW (struct gimple_bb);
262 GBB_DATA_REFS (gbb) = drs;
263 GBB_CONDITIONS (gbb) = NULL;
264 GBB_CONDITION_CASES (gbb) = NULL;
270 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
273 struct data_reference *dr;
275 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
278 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
281 free (bap->alias_set);
290 free_gimple_bb (struct gimple_bb *gbb)
292 free_data_refs_aux (GBB_DATA_REFS (gbb));
293 free_data_refs (GBB_DATA_REFS (gbb));
295 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
296 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
297 GBB_BB (gbb)->aux = 0;
301 /* Deletes all gimple bbs in SCOP. */
304 remove_gbbs_in_scop (scop_p scop)
309 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
310 free_gimple_bb (PBB_BLACK_BOX (pbb));
313 /* Deletes all scops in SCOPS. */
316 free_scops (VEC (scop_p, heap) *scops)
321 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
323 remove_gbbs_in_scop (scop);
324 free_sese (SCOP_REGION (scop));
328 VEC_free (scop_p, heap, scops);
331 /* Generates a polyhedral black box only if the bb contains interesting
335 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
337 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
338 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
339 gimple_stmt_iterator gsi;
341 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
343 gimple stmt = gsi_stmt (gsi);
344 if (!is_gimple_debug (stmt))
345 graphite_find_data_references_in_stmt (nest, stmt, &drs);
348 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
349 free_data_refs (drs);
351 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
355 /* Returns true if all predecessors of BB, that are not dominated by BB, are
356 marked in MAP. The predecessors dominated by BB are loop latches and will
357 be handled after BB. */
360 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
365 FOR_EACH_EDGE (e, ei, bb->preds)
366 if (!TEST_BIT (map, e->src->index)
367 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
373 /* Compare the depth of two basic_block's P1 and P2. */
376 compare_bb_depths (const void *p1, const void *p2)
378 const_basic_block const bb1 = *(const_basic_block const*)p1;
379 const_basic_block const bb2 = *(const_basic_block const*)p2;
380 int d1 = loop_depth (bb1->loop_father);
381 int d2 = loop_depth (bb2->loop_father);
392 /* Sort the basic blocks from DOM such that the first are the ones at
393 a deepest loop level. */
396 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
398 size_t len = VEC_length (basic_block, dom);
400 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
404 /* Recursive helper function for build_scops_bbs. */
407 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
409 sese region = SCOP_REGION (scop);
410 VEC (basic_block, heap) *dom;
412 if (TEST_BIT (visited, bb->index)
413 || !bb_in_sese_p (bb, region))
416 try_generate_gimple_bb (scop, bb, reductions);
417 SET_BIT (visited, bb->index);
419 dom = get_dominated_by (CDI_DOMINATORS, bb);
424 graphite_sort_dominated_info (dom);
426 while (!VEC_empty (basic_block, dom))
431 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
432 if (all_non_dominated_preds_marked_p (dom_bb, visited))
434 build_scop_bbs_1 (scop, visited, dom_bb, reductions);
435 VEC_unordered_remove (basic_block, dom, i);
440 VEC_free (basic_block, heap, dom);
443 /* Gather the basic blocks belonging to the SCOP. */
446 build_scop_bbs (scop_p scop, sbitmap reductions)
448 sbitmap visited = sbitmap_alloc (last_basic_block);
449 sese region = SCOP_REGION (scop);
451 sbitmap_zero (visited);
452 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
453 sbitmap_free (visited);
456 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
457 We generate SCATTERING_DIMENSIONS scattering dimensions.
459 CLooG 0.15.0 and previous versions require, that all
460 scattering functions of one CloogProgram have the same number of
461 scattering dimensions, therefore we allow to specify it. This
462 should be removed in future versions of CLooG.
464 The scattering polyhedron consists of these dimensions: scattering,
465 loop_iterators, parameters.
469 | scattering_dimensions = 5
470 | used_scattering_dimensions = 3
478 | Scattering polyhedron:
480 | scattering: {s1, s2, s3, s4, s5}
481 | loop_iterators: {i}
482 | parameters: {p1, p2}
484 | s1 s2 s3 s4 s5 i p1 p2 1
485 | 1 0 0 0 0 0 0 0 -4 = 0
486 | 0 1 0 0 0 -1 0 0 0 = 0
487 | 0 0 1 0 0 0 0 0 -5 = 0 */
490 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
491 poly_bb_p pbb, int scattering_dimensions)
494 scop_p scop = PBB_SCOP (pbb);
495 int nb_iterators = pbb_dim_iter_domain (pbb);
496 int used_scattering_dimensions = nb_iterators * 2 + 1;
497 int nb_params = scop_nb_params (scop);
499 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
502 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
505 ppl_new_Coefficient (&c);
506 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
507 ppl_new_C_Polyhedron_from_space_dimension
508 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
510 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
512 for (i = 0; i < scattering_dimensions; i++)
514 ppl_Constraint_t cstr;
515 ppl_Linear_Expression_t expr;
517 ppl_new_Linear_Expression_with_dimension (&expr, dim);
519 ppl_assign_Coefficient_from_mpz_t (c, v);
520 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
522 /* Textual order inside this loop. */
525 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
526 ppl_Coefficient_to_mpz_t (c, v);
528 ppl_assign_Coefficient_from_mpz_t (c, v);
529 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
532 /* Iterations of this loop. */
533 else /* if ((i % 2) == 1) */
535 int loop = (i - 1) / 2;
538 ppl_assign_Coefficient_from_mpz_t (c, v);
539 ppl_Linear_Expression_add_to_coefficient
540 (expr, scattering_dimensions + loop, c);
543 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
544 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
545 ppl_delete_Linear_Expression (expr);
546 ppl_delete_Constraint (cstr);
550 ppl_delete_Coefficient (c);
552 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
555 /* Build for BB the static schedule.
557 The static schedule is a Dewey numbering of the abstract syntax
558 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
560 The following example informally defines the static schedule:
579 Static schedules for A to F:
592 build_scop_scattering (scop_p scop)
596 gimple_bb_p previous_gbb = NULL;
597 ppl_Linear_Expression_t static_schedule;
602 ppl_new_Coefficient (&c);
603 ppl_new_Linear_Expression (&static_schedule);
605 /* We have to start schedules at 0 on the first component and
606 because we cannot compare_prefix_loops against a previous loop,
607 prefix will be equal to zero, and that index will be
608 incremented before copying. */
610 ppl_assign_Coefficient_from_mpz_t (c, v);
611 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
613 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
615 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
616 ppl_Linear_Expression_t common;
618 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
621 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
626 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
627 ppl_assign_Linear_Expression_from_Linear_Expression (common,
631 ppl_assign_Coefficient_from_mpz_t (c, v);
632 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
633 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
636 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
638 ppl_delete_Linear_Expression (common);
642 ppl_delete_Coefficient (c);
643 ppl_delete_Linear_Expression (static_schedule);
646 /* Add the value K to the dimension D of the linear expression EXPR. */
649 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
653 ppl_Coefficient_t coef;
655 ppl_new_Coefficient (&coef);
656 ppl_Linear_Expression_coefficient (expr, d, coef);
658 ppl_Coefficient_to_mpz_t (coef, val);
660 mpz_add (val, val, k);
662 ppl_assign_Coefficient_from_mpz_t (coef, val);
663 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
665 ppl_delete_Coefficient (coef);
668 /* In the context of scop S, scan E, the right hand side of a scalar
669 evolution function in loop VAR, and translate it to a linear
673 scan_tree_for_params_right_scev (sese s, tree e, int var,
674 ppl_Linear_Expression_t expr)
678 loop_p loop = get_loop (var);
679 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
682 /* Scalar evolutions should happen in the sese region. */
683 gcc_assert (sese_loop_depth (s, loop) > 0);
685 /* We can not deal with parametric strides like:
691 gcc_assert (TREE_CODE (e) == INTEGER_CST);
694 mpz_set_si (val, int_cst_value (e));
695 add_value_to_dim (l, expr, val);
700 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
701 linear expression EXPR. K is the multiplier of the constant. */
704 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
707 ppl_Coefficient_t coef;
708 int v = int_cst_value (cst);
713 /* Necessary to not get "-1 = 2^n - 1". */
715 mpz_sub_ui (val, val, -v);
717 mpz_add_ui (val, val, v);
719 mpz_mul (val, val, k);
720 ppl_new_Coefficient (&coef);
721 ppl_assign_Coefficient_from_mpz_t (coef, val);
722 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
724 ppl_delete_Coefficient (coef);
727 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
728 Otherwise returns -1. */
731 parameter_index_in_region_1 (tree name, sese region)
736 gcc_assert (TREE_CODE (name) == SSA_NAME);
738 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
745 /* When the parameter NAME is in REGION, returns its index in
746 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
747 and returns the index of NAME. */
750 parameter_index_in_region (tree name, sese region)
754 gcc_assert (TREE_CODE (name) == SSA_NAME);
756 i = parameter_index_in_region_1 (name, region);
760 gcc_assert (SESE_ADD_PARAMS (region));
762 i = VEC_length (tree, SESE_PARAMS (region));
763 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
767 /* In the context of sese S, scan the expression E and translate it to
768 a linear expression C. When parsing a symbolic multiplication, K
769 represents the constant multiplier of an expression containing
773 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
776 if (e == chrec_dont_know)
779 switch (TREE_CODE (e))
781 case POLYNOMIAL_CHREC:
782 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
783 CHREC_VARIABLE (e), c);
784 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
788 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
793 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
795 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
796 mpz_mul (val, val, k);
797 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
801 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
808 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
810 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
811 mpz_mul (val, val, k);
812 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
816 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
821 case POINTER_PLUS_EXPR:
822 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
823 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
828 ppl_Linear_Expression_t tmp_expr = NULL;
832 ppl_dimension_type dim;
833 ppl_Linear_Expression_space_dimension (c, &dim);
834 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
837 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
838 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
842 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
844 ppl_delete_Linear_Expression (tmp_expr);
852 ppl_Linear_Expression_t tmp_expr = NULL;
856 ppl_dimension_type dim;
857 ppl_Linear_Expression_space_dimension (c, &dim);
858 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
861 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
865 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
867 ppl_delete_Linear_Expression (tmp_expr);
875 ppl_Linear_Expression_t tmp_expr = NULL;
879 ppl_dimension_type dim;
880 ppl_Linear_Expression_space_dimension (c, &dim);
881 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
884 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
888 ppl_Coefficient_t coef;
891 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
893 ppl_delete_Linear_Expression (tmp_expr);
894 mpz_init (minus_one);
895 mpz_set_si (minus_one, -1);
896 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
897 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
898 mpz_clear (minus_one);
899 ppl_delete_Coefficient (coef);
907 ppl_dimension_type p = parameter_index_in_region (e, s);
911 ppl_dimension_type dim;
912 ppl_Linear_Expression_space_dimension (c, &dim);
913 p += dim - sese_nb_params (s);
914 add_value_to_dim (p, c, k);
921 scan_tree_for_params_int (e, c, k);
925 case NON_LVALUE_EXPR:
926 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
935 /* Find parameters with respect to REGION in BB. We are looking in memory
936 access functions, conditions and loop bounds. */
939 find_params_in_bb (sese region, gimple_bb_p gbb)
945 loop_p loop = GBB_BB (gbb)->loop_father;
951 /* Find parameters in the access functions of data references. */
952 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
953 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
954 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
956 /* Find parameters in conditional statements. */
957 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
959 tree lhs = scalar_evolution_in_region (region, loop,
960 gimple_cond_lhs (stmt));
961 tree rhs = scalar_evolution_in_region (region, loop,
962 gimple_cond_rhs (stmt));
964 scan_tree_for_params (region, lhs, NULL, one);
965 scan_tree_for_params (region, rhs, NULL, one);
971 /* Record the parameters used in the SCOP. A variable is a parameter
972 in a scop if it does not vary during the execution of that scop. */
975 find_scop_parameters (scop_p scop)
979 sese region = SCOP_REGION (scop);
986 /* Find the parameters used in the loop bounds. */
987 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
989 tree nb_iters = number_of_latch_executions (loop);
991 if (!chrec_contains_symbols (nb_iters))
994 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
995 scan_tree_for_params (region, nb_iters, NULL, one);
1000 /* Find the parameters used in data accesses. */
1001 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1002 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1004 scop_set_nb_params (scop, sese_nb_params (region));
1005 SESE_ADD_PARAMS (region) = false;
1007 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1008 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1011 /* Returns a gimple_bb from BB. */
1013 static inline gimple_bb_p
1014 gbb_from_bb (basic_block bb)
1016 return (gimple_bb_p) bb->aux;
1019 /* Insert in the SCOP context constraints from the estimation of the
1020 number of iterations. UB_EXPR is a linear expression describing
1021 the number of iterations in a loop. This expression is bounded by
1022 the estimation NIT. */
1025 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
1026 ppl_dimension_type dim,
1027 ppl_Linear_Expression_t ub_expr)
1030 ppl_Linear_Expression_t nb_iters_le;
1031 ppl_Polyhedron_t pol;
1032 ppl_Coefficient_t coef;
1033 ppl_Constraint_t ub;
1035 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1036 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1039 /* Construct the negated number of last iteration in VAL. */
1041 mpz_set_double_int (val, nit, false);
1042 mpz_sub_ui (val, val, 1);
1045 /* NB_ITERS_LE holds the number of last iteration in
1046 parametrical form. Subtract estimated number of last
1047 iteration and assert that result is not positive. */
1048 ppl_new_Coefficient_from_mpz_t (&coef, val);
1049 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1050 ppl_delete_Coefficient (coef);
1051 ppl_new_Constraint (&ub, nb_iters_le,
1052 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1053 ppl_Polyhedron_add_constraint (pol, ub);
1055 /* Remove all but last GDIM dimensions from POL to obtain
1056 only the constraints on the parameters. */
1058 graphite_dim_t gdim = scop_nb_params (scop);
1059 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
1062 for (i = 0; i < dim - gdim; i++)
1065 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1069 /* Add the constraints on the parameters to the SCoP context. */
1071 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1073 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1074 (&constraints_ps, pol);
1075 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1076 (SCOP_CONTEXT (scop), constraints_ps);
1077 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1080 ppl_delete_Polyhedron (pol);
1081 ppl_delete_Linear_Expression (nb_iters_le);
1082 ppl_delete_Constraint (ub);
1086 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1087 the constraints for the surrounding loops. */
1090 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1091 ppl_Polyhedron_t outer_ph, int nb,
1092 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1095 ppl_Polyhedron_t ph;
1096 tree nb_iters = number_of_latch_executions (loop);
1097 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1098 sese region = SCOP_REGION (scop);
1101 ppl_const_Constraint_System_t pcs;
1102 ppl_dimension_type *map
1103 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1105 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1106 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1107 ppl_Polyhedron_add_constraints (ph, pcs);
1109 for (i = 0; i < (int) nb; i++)
1111 for (i = (int) nb; i < (int) dim - 1; i++)
1115 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1121 ppl_Constraint_t lb;
1122 ppl_Linear_Expression_t lb_expr;
1124 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1125 ppl_set_coef (lb_expr, nb, 1);
1126 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1127 ppl_delete_Linear_Expression (lb_expr);
1128 ppl_Polyhedron_add_constraint (ph, lb);
1129 ppl_delete_Constraint (lb);
1132 if (TREE_CODE (nb_iters) == INTEGER_CST)
1134 ppl_Constraint_t ub;
1135 ppl_Linear_Expression_t ub_expr;
1137 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1139 /* loop_i <= cst_nb_iters */
1140 ppl_set_coef (ub_expr, nb, -1);
1141 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1142 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1143 ppl_Polyhedron_add_constraint (ph, ub);
1144 ppl_delete_Linear_Expression (ub_expr);
1145 ppl_delete_Constraint (ub);
1147 else if (!chrec_contains_undetermined (nb_iters))
1150 ppl_Constraint_t ub;
1151 ppl_Linear_Expression_t ub_expr;
1155 mpz_set_si (one, 1);
1156 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1157 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1158 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1161 if (estimated_loop_iterations (loop, true, &nit))
1162 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1164 /* loop_i <= expr_nb_iters */
1165 ppl_set_coef (ub_expr, nb, -1);
1166 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1167 ppl_Polyhedron_add_constraint (ph, ub);
1168 ppl_delete_Linear_Expression (ub_expr);
1169 ppl_delete_Constraint (ub);
1174 if (loop->inner && loop_in_sese_p (loop->inner, region))
1175 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1179 && loop_in_sese_p (loop->next, region))
1180 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1182 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1183 (&domains[loop->num], ph);
1185 ppl_delete_Polyhedron (ph);
1188 /* Returns a linear expression for tree T evaluated in PBB. */
1190 static ppl_Linear_Expression_t
1191 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1194 ppl_Linear_Expression_t res;
1195 ppl_dimension_type dim;
1196 sese region = SCOP_REGION (PBB_SCOP (pbb));
1197 loop_p loop = pbb_loop (pbb);
1199 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1200 ppl_new_Linear_Expression_with_dimension (&res, dim);
1202 t = scalar_evolution_in_region (region, loop, t);
1203 gcc_assert (!automatically_generated_chrec_p (t));
1206 mpz_set_si (one, 1);
1207 scan_tree_for_params (region, t, res, one);
1213 /* Returns the ppl constraint type from the gimple tree code CODE. */
1215 static enum ppl_enum_Constraint_Type
1216 ppl_constraint_type_from_tree_code (enum tree_code code)
1220 /* We do not support LT and GT to be able to work with C_Polyhedron.
1221 As we work on integer polyhedron "a < b" can be expressed by
1228 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1231 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1234 return PPL_CONSTRAINT_TYPE_EQUAL;
1241 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1242 CODE is used as the comparison operator. This allows us to invert the
1243 condition or to handle inequalities. */
1246 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1247 poly_bb_p pbb, enum tree_code code)
1250 ppl_Coefficient_t c;
1251 ppl_Linear_Expression_t left, right;
1252 ppl_Constraint_t cstr;
1253 enum ppl_enum_Constraint_Type type;
1255 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1256 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1258 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1259 the left or the right side of the expression. */
1260 if (code == LT_EXPR)
1264 ppl_new_Coefficient (&c);
1265 ppl_assign_Coefficient_from_mpz_t (c, v);
1266 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1267 ppl_delete_Coefficient (c);
1272 else if (code == GT_EXPR)
1276 ppl_new_Coefficient (&c);
1277 ppl_assign_Coefficient_from_mpz_t (c, v);
1278 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1279 ppl_delete_Coefficient (c);
1285 type = ppl_constraint_type_from_tree_code (code);
1287 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1289 ppl_new_Constraint (&cstr, left, type);
1290 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1292 ppl_delete_Constraint (cstr);
1293 ppl_delete_Linear_Expression (left);
1294 ppl_delete_Linear_Expression (right);
1297 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1298 operator. This allows us to invert the condition or to handle
1302 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1304 if (code == NE_EXPR)
1306 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1307 ppl_Pointset_Powerset_C_Polyhedron_t right;
1308 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1310 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1311 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1312 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1313 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1316 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1319 /* Add conditions to the domain of PBB. */
1322 add_conditions_to_domain (poly_bb_p pbb)
1326 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1328 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1331 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1332 switch (gimple_code (stmt))
1336 enum tree_code code = gimple_cond_code (stmt);
1338 /* The conditions for ELSE-branches are inverted. */
1339 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1340 code = invert_tree_comparison (code, false);
1342 add_condition_to_pbb (pbb, stmt, code);
1347 /* Switch statements are not supported right now - fall throught. */
1355 /* Structure used to pass data to dom_walk. */
1359 VEC (gimple, heap) **conditions, **cases;
1363 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1364 edge between BB and its predecessor is not a loop exit edge, and
1365 the last statement of the single predecessor is a COND_EXPR. */
1368 single_pred_cond_non_loop_exit (basic_block bb)
1370 if (single_pred_p (bb))
1372 edge e = single_pred_edge (bb);
1373 basic_block pred = e->src;
1376 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1379 stmt = last_stmt (pred);
1381 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1388 /* Call-back for dom_walk executed before visiting the dominated
1392 build_sese_conditions_before (struct dom_walk_data *dw_data,
1395 struct bsc *data = (struct bsc *) dw_data->global_data;
1396 VEC (gimple, heap) **conditions = data->conditions;
1397 VEC (gimple, heap) **cases = data->cases;
1401 if (!bb_in_sese_p (bb, data->region))
1404 stmt = single_pred_cond_non_loop_exit (bb);
1408 edge e = single_pred_edge (bb);
1410 VEC_safe_push (gimple, heap, *conditions, stmt);
1412 if (e->flags & EDGE_TRUE_VALUE)
1413 VEC_safe_push (gimple, heap, *cases, stmt);
1415 VEC_safe_push (gimple, heap, *cases, NULL);
1418 gbb = gbb_from_bb (bb);
1422 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1423 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1427 /* Call-back for dom_walk executed after visiting the dominated
1431 build_sese_conditions_after (struct dom_walk_data *dw_data,
1434 struct bsc *data = (struct bsc *) dw_data->global_data;
1435 VEC (gimple, heap) **conditions = data->conditions;
1436 VEC (gimple, heap) **cases = data->cases;
1438 if (!bb_in_sese_p (bb, data->region))
1441 if (single_pred_cond_non_loop_exit (bb))
1443 VEC_pop (gimple, *conditions);
1444 VEC_pop (gimple, *cases);
1448 /* Record all conditions in REGION. */
1451 build_sese_conditions (sese region)
1453 struct dom_walk_data walk_data;
1454 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1455 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1458 data.conditions = &conditions;
1459 data.cases = &cases;
1460 data.region = region;
1462 walk_data.dom_direction = CDI_DOMINATORS;
1463 walk_data.initialize_block_local_data = NULL;
1464 walk_data.before_dom_children = build_sese_conditions_before;
1465 walk_data.after_dom_children = build_sese_conditions_after;
1466 walk_data.global_data = &data;
1467 walk_data.block_local_data_size = 0;
1469 init_walk_dominator_tree (&walk_data);
1470 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1471 fini_walk_dominator_tree (&walk_data);
1473 VEC_free (gimple, heap, conditions);
1474 VEC_free (gimple, heap, cases);
1477 /* Traverses all the GBBs of the SCOP and add their constraints to the
1478 iteration domains. */
1481 add_conditions_to_constraints (scop_p scop)
1486 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1487 add_conditions_to_domain (pbb);
1490 /* Add constraints on the possible values of parameter P from the type
1494 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1496 ppl_Constraint_t cstr;
1497 ppl_Linear_Expression_t le;
1498 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1499 tree type = TREE_TYPE (parameter);
1500 tree lb = NULL_TREE;
1501 tree ub = NULL_TREE;
1503 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1504 lb = lower_bound_in_type (type, type);
1506 lb = TYPE_MIN_VALUE (type);
1508 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1509 ub = upper_bound_in_type (type, type);
1511 ub = TYPE_MAX_VALUE (type);
1515 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1516 ppl_set_coef (le, p, -1);
1517 ppl_set_inhomogeneous_tree (le, lb);
1518 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1519 ppl_Polyhedron_add_constraint (context, cstr);
1520 ppl_delete_Linear_Expression (le);
1521 ppl_delete_Constraint (cstr);
1526 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1527 ppl_set_coef (le, p, -1);
1528 ppl_set_inhomogeneous_tree (le, ub);
1529 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1530 ppl_Polyhedron_add_constraint (context, cstr);
1531 ppl_delete_Linear_Expression (le);
1532 ppl_delete_Constraint (cstr);
1536 /* Build the context of the SCOP. The context usually contains extra
1537 constraints that are added to the iteration domains that constrain
1541 build_scop_context (scop_p scop)
1543 ppl_Polyhedron_t context;
1544 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1545 graphite_dim_t p, n = scop_nb_params (scop);
1547 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1549 for (p = 0; p < n; p++)
1550 add_param_constraints (scop, context, p);
1552 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1554 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1555 (SCOP_CONTEXT (scop), ps);
1557 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1558 ppl_delete_Polyhedron (context);
1561 /* Build the iteration domains: the loops belonging to the current
1562 SCOP, and that vary for the execution of the current basic block.
1563 Returns false if there is no loop in SCOP. */
1566 build_scop_iteration_domain (scop_p scop)
1569 sese region = SCOP_REGION (scop);
1571 ppl_Polyhedron_t ph;
1573 int nb_loops = number_of_loops ();
1574 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1575 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1577 for (i = 0; i < nb_loops; i++)
1580 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1582 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1583 if (!loop_in_sese_p (loop_outer (loop), region))
1584 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1586 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1587 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1588 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1589 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1590 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1592 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1593 (&PBB_DOMAIN (pbb), ph);
1595 for (i = 0; i < nb_loops; i++)
1597 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1599 ppl_delete_Polyhedron (ph);
1603 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1604 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1605 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1609 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1610 ppl_dimension_type accessp_nb_dims,
1611 ppl_dimension_type dom_nb_dims)
1613 ppl_Linear_Expression_t alias;
1614 ppl_Constraint_t cstr;
1615 int alias_set_num = 0;
1616 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1618 if (bap && bap->alias_set)
1619 alias_set_num = *(bap->alias_set);
1621 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1623 ppl_set_coef (alias, dom_nb_dims, 1);
1624 ppl_set_inhomogeneous (alias, -alias_set_num);
1625 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1626 ppl_Polyhedron_add_constraint (accesses, cstr);
1628 ppl_delete_Linear_Expression (alias);
1629 ppl_delete_Constraint (cstr);
1632 /* Add to ACCESSES polyhedron equalities defining the access functions
1633 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1634 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1635 PBB is the poly_bb_p that contains the data reference DR. */
1638 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1639 ppl_dimension_type accessp_nb_dims,
1640 ppl_dimension_type dom_nb_dims,
1643 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1645 scop_p scop = PBB_SCOP (pbb);
1646 sese region = SCOP_REGION (scop);
1650 for (i = 0; i < nb_subscripts; i++)
1652 ppl_Linear_Expression_t fn, access;
1653 ppl_Constraint_t cstr;
1654 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1655 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1657 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1658 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1661 scan_tree_for_params (region, afn, fn, v);
1662 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1664 ppl_set_coef (access, subscript, -1);
1665 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1666 ppl_Polyhedron_add_constraint (accesses, cstr);
1668 ppl_delete_Linear_Expression (fn);
1669 ppl_delete_Linear_Expression (access);
1670 ppl_delete_Constraint (cstr);
1676 /* Add constrains representing the size of the accessed data to the
1677 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1678 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1682 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1683 ppl_dimension_type accessp_nb_dims,
1684 ppl_dimension_type dom_nb_dims)
1686 tree ref = DR_REF (dr);
1687 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1689 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1691 ppl_Linear_Expression_t expr;
1692 ppl_Constraint_t cstr;
1693 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1696 if (TREE_CODE (ref) != ARRAY_REF)
1699 low = array_ref_low_bound (ref);
1701 /* subscript - low >= 0 */
1702 if (host_integerp (low, 0))
1704 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1705 ppl_set_coef (expr, subscript, 1);
1707 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1709 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1710 ppl_Polyhedron_add_constraint (accesses, cstr);
1711 ppl_delete_Linear_Expression (expr);
1712 ppl_delete_Constraint (cstr);
1715 high = array_ref_up_bound (ref);
1717 /* high - subscript >= 0 */
1718 if (high && host_integerp (high, 0)
1719 /* 1-element arrays at end of structures may extend over
1720 their declared size. */
1721 && !(array_at_struct_end_p (ref)
1722 && operand_equal_p (low, high, 0)))
1724 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1725 ppl_set_coef (expr, subscript, -1);
1727 ppl_set_inhomogeneous (expr, int_cst_value (high));
1729 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1730 ppl_Polyhedron_add_constraint (accesses, cstr);
1731 ppl_delete_Linear_Expression (expr);
1732 ppl_delete_Constraint (cstr);
1737 /* Build data accesses for DR in PBB. */
1740 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1742 ppl_Polyhedron_t accesses;
1743 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1744 ppl_dimension_type dom_nb_dims;
1745 ppl_dimension_type accessp_nb_dims;
1746 int dr_base_object_set;
1748 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1750 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1752 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1754 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1755 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1756 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1758 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1760 ppl_delete_Polyhedron (accesses);
1762 gcc_assert (dr->aux);
1763 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1765 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1766 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1767 dr, DR_NUM_DIMENSIONS (dr));
1770 /* Write to FILE the alias graph of data references in DIMACS format. */
1773 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1774 VEC (data_reference_p, heap) *drs)
1776 int num_vertex = VEC_length (data_reference_p, drs);
1778 data_reference_p dr1, dr2;
1781 if (num_vertex == 0)
1784 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1785 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1786 if (dr_may_alias_p (dr1, dr2))
1789 fprintf (file, "$\n");
1792 fprintf (file, "c %s\n", comment);
1794 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1796 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1797 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1798 if (dr_may_alias_p (dr1, dr2))
1799 fprintf (file, "e %d %d\n", i + 1, j + 1);
1804 /* Write to FILE the alias graph of data references in DOT format. */
1807 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1808 VEC (data_reference_p, heap) *drs)
1810 int num_vertex = VEC_length (data_reference_p, drs);
1811 data_reference_p dr1, dr2;
1814 if (num_vertex == 0)
1817 fprintf (file, "$\n");
1820 fprintf (file, "c %s\n", comment);
1822 /* First print all the vertices. */
1823 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1824 fprintf (file, "n%d;\n", i);
1826 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1827 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1828 if (dr_may_alias_p (dr1, dr2))
1829 fprintf (file, "n%d n%d\n", i, j);
1834 /* Write to FILE the alias graph of data references in ECC format. */
1837 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1838 VEC (data_reference_p, heap) *drs)
1840 int num_vertex = VEC_length (data_reference_p, drs);
1841 data_reference_p dr1, dr2;
1844 if (num_vertex == 0)
1847 fprintf (file, "$\n");
1850 fprintf (file, "c %s\n", comment);
1852 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1853 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1854 if (dr_may_alias_p (dr1, dr2))
1855 fprintf (file, "%d %d\n", i, j);
1860 /* Check if DR1 and DR2 are in the same object set. */
1863 dr_same_base_object_p (const struct data_reference *dr1,
1864 const struct data_reference *dr2)
1866 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1869 /* Uses DFS component number as representative of alias-sets. Also tests for
1870 optimality by verifying if every connected component is a clique. Returns
1871 true (1) if the above test is true, and false (0) otherwise. */
1874 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1876 int num_vertices = VEC_length (data_reference_p, drs);
1877 struct graph *g = new_graph (num_vertices);
1878 data_reference_p dr1, dr2;
1880 int num_connected_components;
1881 int v_indx1, v_indx2, num_vertices_in_component;
1884 struct graph_edge *e;
1885 int this_component_is_clique;
1886 int all_components_are_cliques = 1;
1888 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1889 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1890 if (dr_may_alias_p (dr1, dr2))
1896 all_vertices = XNEWVEC (int, num_vertices);
1897 vertices = XNEWVEC (int, num_vertices);
1898 for (i = 0; i < num_vertices; i++)
1899 all_vertices[i] = i;
1901 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1903 for (i = 0; i < g->n_vertices; i++)
1905 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1906 base_alias_pair *bap;
1908 gcc_assert (dr->aux);
1909 bap = (base_alias_pair *)(dr->aux);
1911 bap->alias_set = XNEW (int);
1912 *(bap->alias_set) = g->vertices[i].component + 1;
1915 /* Verify if the DFS numbering results in optimal solution. */
1916 for (i = 0; i < num_connected_components; i++)
1918 num_vertices_in_component = 0;
1919 /* Get all vertices whose DFS component number is the same as i. */
1920 for (j = 0; j < num_vertices; j++)
1921 if (g->vertices[j].component == i)
1922 vertices[num_vertices_in_component++] = j;
1924 /* Now test if the vertices in 'vertices' form a clique, by testing
1925 for edges among each pair. */
1926 this_component_is_clique = 1;
1927 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1929 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1931 /* Check if the two vertices are connected by iterating
1932 through all the edges which have one of these are source. */
1933 e = g->vertices[vertices[v_indx2]].pred;
1936 if (e->src == vertices[v_indx1])
1942 this_component_is_clique = 0;
1946 if (!this_component_is_clique)
1947 all_components_are_cliques = 0;
1951 free (all_vertices);
1954 return all_components_are_cliques;
1957 /* Group each data reference in DRS with it's base object set num. */
1960 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1962 int num_vertex = VEC_length (data_reference_p, drs);
1963 struct graph *g = new_graph (num_vertex);
1964 data_reference_p dr1, dr2;
1968 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1969 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1970 if (dr_same_base_object_p (dr1, dr2))
1976 queue = XNEWVEC (int, num_vertex);
1977 for (i = 0; i < num_vertex; i++)
1980 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1982 for (i = 0; i < g->n_vertices; i++)
1984 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1985 base_alias_pair *bap;
1987 gcc_assert (dr->aux);
1988 bap = (base_alias_pair *)(dr->aux);
1990 bap->base_obj_set = g->vertices[i].component + 1;
1997 /* Build the data references for PBB. */
2000 build_pbb_drs (poly_bb_p pbb)
2003 data_reference_p dr;
2004 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2006 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
2007 build_poly_dr (dr, pbb);
2010 /* Dump to file the alias graphs for the data references in DRS. */
2013 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2016 FILE *file_dimacs, *file_ecc, *file_dot;
2018 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2021 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2022 current_function_name ());
2023 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2024 fclose (file_dimacs);
2027 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2030 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2031 current_function_name ());
2032 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2036 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2039 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2040 current_function_name ());
2041 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2046 /* Build data references in SCOP. */
2049 build_scop_drs (scop_p scop)
2053 data_reference_p dr;
2054 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2056 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2057 for (j = 0; VEC_iterate (data_reference_p,
2058 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2059 VEC_safe_push (data_reference_p, heap, drs, dr);
2061 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
2062 dr->aux = XNEW (base_alias_pair);
2064 if (!build_alias_set_optimal_p (drs))
2066 /* TODO: Add support when building alias set is not optimal. */
2070 build_base_obj_set_for_drs (drs);
2072 /* When debugging, enable the following code. This cannot be used
2073 in production compilers. */
2075 dump_alias_graphs (drs);
2077 VEC_free (data_reference_p, heap, drs);
2079 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2080 build_pbb_drs (pbb);
2083 /* Return a gsi at the position of the phi node STMT. */
2085 static gimple_stmt_iterator
2086 gsi_for_phi_node (gimple stmt)
2088 gimple_stmt_iterator psi;
2089 basic_block bb = gimple_bb (stmt);
2091 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2092 if (stmt == gsi_stmt (psi))
2099 /* Insert the assignment "RES := VAR" just after AFTER_STMT. */
2102 insert_out_of_ssa_copy (tree res, tree var, gimple after_stmt)
2106 gimple_stmt_iterator si;
2107 gimple_stmt_iterator gsi;
2109 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2110 stmt = gimple_build_assign (res, var);
2112 stmts = gimple_seq_alloc ();
2113 si = gsi_last (stmts);
2114 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2116 if (gimple_code (after_stmt) == GIMPLE_PHI)
2118 gsi = gsi_after_labels (gimple_bb (after_stmt));
2119 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2123 gsi = gsi_for_stmt (after_stmt);
2124 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2128 /* Insert on edge E the assignment "RES := EXPR". */
2131 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2133 gimple_stmt_iterator gsi;
2135 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2136 gimple stmt = gimple_build_assign (res, var);
2139 stmts = gimple_seq_alloc ();
2141 gsi = gsi_last (stmts);
2142 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2143 gsi_insert_seq_on_edge (e, stmts);
2144 gsi_commit_edge_inserts ();
2147 /* Creates a zero dimension array of the same type as VAR. */
2150 create_zero_dim_array (tree var, const char *base_name)
2152 tree index_type = build_index_type (integer_zero_node);
2153 tree elt_type = TREE_TYPE (var);
2154 tree array_type = build_array_type (elt_type, index_type);
2155 tree base = create_tmp_var (array_type, base_name);
2157 add_referenced_var (base);
2159 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2163 /* Returns true when PHI is a loop close phi node. */
2166 scalar_close_phi_node_p (gimple phi)
2168 if (gimple_code (phi) != GIMPLE_PHI
2169 || !is_gimple_reg (gimple_phi_result (phi)))
2172 /* Note that loop close phi nodes should have a single argument
2173 because we translated the representation into a canonical form
2174 before Graphite: see canonicalize_loop_closed_ssa_form. */
2175 return (gimple_phi_num_args (phi) == 1);
2178 /* For a definition DEF in REGION, propagates the expression EXPR in
2179 all the uses of DEF outside REGION. */
2182 propagate_expr_outside_region (tree def, tree expr, sese region)
2184 imm_use_iterator imm_iter;
2187 bool replaced_once = false;
2189 gcc_assert (TREE_CODE (def) == SSA_NAME);
2191 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2194 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2195 if (!is_gimple_debug (use_stmt)
2196 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2199 use_operand_p use_p;
2201 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2202 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2203 && (replaced_once = true))
2204 replace_exp (use_p, expr);
2206 update_stmt (use_stmt);
2211 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2212 gsi_commit_edge_inserts ();
2216 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2217 dimension array for it. */
2220 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region)
2222 gimple phi = gsi_stmt (*psi);
2223 tree res = gimple_phi_result (phi);
2224 tree var = SSA_NAME_VAR (res);
2225 basic_block bb = gimple_bb (phi);
2226 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2227 tree arg = gimple_phi_arg_def (phi, 0);
2230 /* Note that loop close phi nodes should have a single argument
2231 because we translated the representation into a canonical form
2232 before Graphite: see canonicalize_loop_closed_ssa_form. */
2233 gcc_assert (gimple_phi_num_args (phi) == 1);
2235 /* The phi node can be a non close phi node, when its argument is
2236 invariant, or a default definition. */
2237 if (is_gimple_min_invariant (arg)
2238 || SSA_NAME_IS_DEFAULT_DEF (arg))
2240 propagate_expr_outside_region (res, arg, region);
2245 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2247 propagate_expr_outside_region (res, arg, region);
2248 stmt = gimple_build_assign (res, arg);
2249 remove_phi_node (psi, false);
2250 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2251 SSA_NAME_DEF_STMT (res) = stmt;
2255 /* If res is scev analyzable and is not a scalar value, it is safe
2256 to ignore the close phi node: it will be code generated in the
2257 out of Graphite pass. */
2258 else if (scev_analyzable_p (res, region))
2260 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2263 if (!loop_in_sese_p (loop, region))
2265 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2266 scev = scalar_evolution_in_region (region, loop, arg);
2267 scev = compute_overall_effect_of_inner_loop (loop, scev);
2270 scev = scalar_evolution_in_region (region, loop, res);
2272 if (tree_does_not_contain_chrecs (scev))
2273 propagate_expr_outside_region (res, scev, region);
2280 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2282 stmt = gimple_build_assign (res, zero_dim_array);
2284 if (TREE_CODE (arg) == SSA_NAME)
2285 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2287 insert_out_of_ssa_copy_on_edge (single_pred_edge (bb),
2288 zero_dim_array, arg);
2291 remove_phi_node (psi, false);
2292 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2293 SSA_NAME_DEF_STMT (res) = stmt;
2296 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2297 dimension array for it. */
2300 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2303 gimple phi = gsi_stmt (*psi);
2304 basic_block bb = gimple_bb (phi);
2305 tree res = gimple_phi_result (phi);
2306 tree var = SSA_NAME_VAR (res);
2307 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2308 gimple_stmt_iterator gsi;
2312 for (i = 0; i < gimple_phi_num_args (phi); i++)
2314 tree arg = gimple_phi_arg_def (phi, i);
2315 edge e = gimple_phi_arg_edge (phi, i);
2317 /* Avoid the insertion of code in the loop latch to please the
2318 pattern matching of the vectorizer. */
2319 if (TREE_CODE (arg) == SSA_NAME
2320 && e->src == bb->loop_father->latch)
2321 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2323 insert_out_of_ssa_copy_on_edge (e, zero_dim_array, arg);
2326 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2329 stmts = gimple_seq_alloc ();
2331 stmt = gimple_build_assign (res, var);
2332 remove_phi_node (psi, false);
2333 SSA_NAME_DEF_STMT (res) = stmt;
2335 gsi = gsi_last (stmts);
2336 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2338 gsi = gsi_after_labels (bb);
2339 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2342 /* Rewrite the degenerate phi node at position PSI from the degenerate
2343 form "x = phi (y, y, ..., y)" to "x = y". */
2346 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2350 gimple_stmt_iterator gsi;
2351 gimple phi = gsi_stmt (*psi);
2352 tree res = gimple_phi_result (phi);
2355 bb = gimple_bb (phi);
2356 rhs = degenerate_phi_result (phi);
2359 stmt = gimple_build_assign (res, rhs);
2360 remove_phi_node (psi, false);
2361 SSA_NAME_DEF_STMT (res) = stmt;
2363 gsi = gsi_after_labels (bb);
2364 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2367 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2370 rewrite_reductions_out_of_ssa (scop_p scop)
2373 gimple_stmt_iterator psi;
2374 sese region = SCOP_REGION (scop);
2377 if (bb_in_sese_p (bb, region))
2378 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2380 gimple phi = gsi_stmt (psi);
2382 if (!is_gimple_reg (gimple_phi_result (phi)))
2388 if (gimple_phi_num_args (phi) > 1
2389 && degenerate_phi_result (phi))
2390 rewrite_degenerate_phi (&psi);
2392 else if (scalar_close_phi_node_p (phi))
2393 rewrite_close_phi_out_of_ssa (&psi, region);
2395 else if (reduction_phi_p (region, &psi))
2396 rewrite_phi_out_of_ssa (&psi);
2399 update_ssa (TODO_update_ssa);
2400 #ifdef ENABLE_CHECKING
2401 verify_loop_closed_ssa (true);
2405 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2406 read from ZERO_DIM_ARRAY. */
2409 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2411 tree var = SSA_NAME_VAR (def);
2412 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2413 tree name = make_ssa_name (var, name_stmt);
2415 use_operand_p use_p;
2416 gimple_stmt_iterator gsi;
2418 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2420 gimple_assign_set_lhs (name_stmt, name);
2422 gsi = gsi_for_stmt (use_stmt);
2423 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2425 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2426 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2427 replace_exp (use_p, name);
2429 update_stmt (use_stmt);
2432 /* Rewrite the scalar dependences crossing the boundary of the BB
2433 containing STMT with an array. Return true when something has been
2437 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2439 gimple stmt = gsi_stmt (*gsi);
2440 imm_use_iterator imm_iter;
2443 tree zero_dim_array = NULL_TREE;
2447 switch (gimple_code (stmt))
2450 def = gimple_assign_lhs (stmt);
2454 def = gimple_call_lhs (stmt);
2462 || !is_gimple_reg (def))
2465 if (scev_analyzable_p (def, region))
2467 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2468 tree scev = scalar_evolution_in_region (region, loop, def);
2470 if (tree_contains_chrecs (scev, NULL))
2473 propagate_expr_outside_region (def, scev, region);
2477 def_bb = gimple_bb (stmt);
2479 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2480 if (gimple_code (use_stmt) == GIMPLE_PHI
2483 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2485 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2486 rewrite_close_phi_out_of_ssa (&psi, region);
2488 rewrite_phi_out_of_ssa (&psi);
2491 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2492 if (gimple_code (use_stmt) != GIMPLE_PHI
2493 && def_bb != gimple_bb (use_stmt)
2494 && !is_gimple_debug (use_stmt)
2497 if (!zero_dim_array)
2499 zero_dim_array = create_zero_dim_array
2500 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2501 insert_out_of_ssa_copy (zero_dim_array, def,
2502 SSA_NAME_DEF_STMT (def));
2506 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2512 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2515 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2518 gimple_stmt_iterator psi;
2519 sese region = SCOP_REGION (scop);
2520 bool changed = false;
2523 if (bb_in_sese_p (bb, region))
2524 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2525 changed |= rewrite_cross_bb_scalar_deps (region, &psi);
2530 update_ssa (TODO_update_ssa);
2531 #ifdef ENABLE_CHECKING
2532 verify_loop_closed_ssa (true);
2537 /* Returns the number of pbbs that are in loops contained in SCOP. */
2540 nb_pbbs_in_loops (scop_p scop)
2546 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2547 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2553 /* Return the number of data references in BB that write in
2557 nb_data_writes_in_bb (basic_block bb)
2560 gimple_stmt_iterator gsi;
2562 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2563 if (gimple_vdef (gsi_stmt (gsi)))
2569 /* Splits STMT out of its current BB. */
2572 split_reduction_stmt (gimple stmt)
2574 gimple_stmt_iterator gsi;
2575 basic_block bb = gimple_bb (stmt);
2578 /* Do not split basic blocks with no writes to memory: the reduction
2579 will be the only write to memory. */
2580 if (nb_data_writes_in_bb (bb) == 0)
2583 split_block (bb, stmt);
2585 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2588 gsi = gsi_last_bb (bb);
2590 e = split_block (bb, gsi_stmt (gsi));
2595 /* Return true when stmt is a reduction operation. */
2598 is_reduction_operation_p (gimple stmt)
2600 enum tree_code code;
2602 gcc_assert (is_gimple_assign (stmt));
2603 code = gimple_assign_rhs_code (stmt);
2605 return flag_associative_math
2606 && commutative_tree_code (code)
2607 && associative_tree_code (code);
2610 /* Returns true when PHI contains an argument ARG. */
2613 phi_contains_arg (gimple phi, tree arg)
2617 for (i = 0; i < gimple_phi_num_args (phi); i++)
2618 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2624 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2627 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2631 if (TREE_CODE (arg) != SSA_NAME)
2634 stmt = SSA_NAME_DEF_STMT (arg);
2636 if (gimple_code (stmt) == GIMPLE_NOP
2637 || gimple_code (stmt) == GIMPLE_CALL)
2640 if (gimple_code (stmt) == GIMPLE_PHI)
2642 if (phi_contains_arg (stmt, lhs))
2647 if (!is_gimple_assign (stmt))
2650 if (gimple_num_ops (stmt) == 2)
2651 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2653 if (is_reduction_operation_p (stmt))
2655 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2658 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2664 /* Detect commutative and associative scalar reductions starting at
2665 the STMT. Return the phi node of the reduction cycle, or NULL. */
2668 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2669 VEC (gimple, heap) **in,
2670 VEC (gimple, heap) **out)
2672 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2677 VEC_safe_push (gimple, heap, *in, stmt);
2678 VEC_safe_push (gimple, heap, *out, stmt);
2682 /* Detect commutative and associative scalar reductions starting at
2683 STMT. Return the phi node of the reduction cycle, or NULL. */
2686 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2687 VEC (gimple, heap) **out)
2689 tree lhs = gimple_assign_lhs (stmt);
2691 if (gimple_num_ops (stmt) == 2)
2692 return detect_commutative_reduction_arg (lhs, stmt,
2693 gimple_assign_rhs1 (stmt),
2696 if (is_reduction_operation_p (stmt))
2698 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2699 gimple_assign_rhs1 (stmt),
2702 : detect_commutative_reduction_arg (lhs, stmt,
2703 gimple_assign_rhs2 (stmt),
2710 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2713 follow_inital_value_to_phi (tree arg, tree lhs)
2717 if (!arg || TREE_CODE (arg) != SSA_NAME)
2720 stmt = SSA_NAME_DEF_STMT (arg);
2722 if (gimple_code (stmt) == GIMPLE_PHI
2723 && phi_contains_arg (stmt, lhs))
2730 /* Return the argument of the loop PHI that is the inital value coming
2731 from outside the loop. */
2734 edge_initial_value_for_loop_phi (gimple phi)
2738 for (i = 0; i < gimple_phi_num_args (phi); i++)
2740 edge e = gimple_phi_arg_edge (phi, i);
2742 if (loop_depth (e->src->loop_father)
2743 < loop_depth (e->dest->loop_father))
2750 /* Return the argument of the loop PHI that is the inital value coming
2751 from outside the loop. */
2754 initial_value_for_loop_phi (gimple phi)
2758 for (i = 0; i < gimple_phi_num_args (phi); i++)
2760 edge e = gimple_phi_arg_edge (phi, i);
2762 if (loop_depth (e->src->loop_father)
2763 < loop_depth (e->dest->loop_father))
2764 return gimple_phi_arg_def (phi, i);
2770 /* Detect commutative and associative scalar reductions starting at
2771 the loop closed phi node STMT. Return the phi node of the
2772 reduction cycle, or NULL. */
2775 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2776 VEC (gimple, heap) **out)
2778 if (scalar_close_phi_node_p (stmt))
2780 tree arg = gimple_phi_arg_def (stmt, 0);
2781 gimple def, loop_phi;
2783 if (TREE_CODE (arg) != SSA_NAME)
2786 /* Note that loop close phi nodes should have a single argument
2787 because we translated the representation into a canonical form
2788 before Graphite: see canonicalize_loop_closed_ssa_form. */
2789 gcc_assert (gimple_phi_num_args (stmt) == 1);
2791 def = SSA_NAME_DEF_STMT (arg);
2792 loop_phi = detect_commutative_reduction (def, in, out);
2796 tree lhs = gimple_phi_result (stmt);
2797 tree init = initial_value_for_loop_phi (loop_phi);
2798 gimple phi = follow_inital_value_to_phi (init, lhs);
2800 VEC_safe_push (gimple, heap, *in, loop_phi);
2801 VEC_safe_push (gimple, heap, *out, stmt);
2808 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2809 return detect_commutative_reduction_assign (stmt, in, out);
2814 /* Translate the scalar reduction statement STMT to an array RED
2815 knowing that its recursive phi node is LOOP_PHI. */
2818 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2821 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2822 tree res = gimple_phi_result (loop_phi);
2823 gimple assign = gimple_build_assign (res, red);
2825 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2827 insert_gsi = gsi_after_labels (gimple_bb (stmt));
2828 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2829 insert_gsi = gsi_for_stmt (stmt);
2830 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2833 /* Removes the PHI node and resets all the debug stmts that are using
2837 remove_phi (gimple phi)
2839 imm_use_iterator imm_iter;
2841 use_operand_p use_p;
2842 gimple_stmt_iterator gsi;
2843 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2847 def = PHI_RESULT (phi);
2848 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2850 stmt = USE_STMT (use_p);
2852 if (is_gimple_debug (stmt))
2854 gimple_debug_bind_reset_value (stmt);
2855 VEC_safe_push (gimple, heap, update, stmt);
2859 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
2862 VEC_free (gimple, heap, update);
2864 gsi = gsi_for_phi_node (phi);
2865 remove_phi_node (&gsi, false);
2868 /* Rewrite out of SSA the reduction described by the loop phi nodes
2869 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2872 IN: stmt, loop_n, ..., loop_0
2873 OUT: stmt, close_n, ..., close_0
2875 the first element is the reduction statement, and the next elements
2876 are the loop and close phi nodes of each of the outer loops. */
2879 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2880 VEC (gimple, heap) *out,
2885 tree red = NULL_TREE;
2887 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
2889 gimple close_phi = VEC_index (gimple, out, i);
2893 gimple stmt = loop_phi;
2894 basic_block bb = split_reduction_stmt (stmt);
2896 SET_BIT (reductions, bb->index);
2897 gcc_assert (close_phi == loop_phi);
2899 red = create_zero_dim_array
2900 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2901 translate_scalar_reduction_to_array_for_stmt
2902 (red, stmt, VEC_index (gimple, in, 1));
2906 if (i == VEC_length (gimple, in) - 1)
2908 insert_out_of_ssa_copy (gimple_phi_result (close_phi), red,
2910 insert_out_of_ssa_copy_on_edge
2911 (edge_initial_value_for_loop_phi (loop_phi),
2912 red, initial_value_for_loop_phi (loop_phi));
2915 remove_phi (loop_phi);
2916 remove_phi (close_phi);
2920 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
2921 true when something has been changed. */
2924 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2928 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2929 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2931 detect_commutative_reduction (close_phi, &in, &out);
2932 res = VEC_length (gimple, in) > 0;
2934 translate_scalar_reduction_to_array (in, out, reductions);
2936 VEC_free (gimple, heap, in);
2937 VEC_free (gimple, heap, out);
2941 /* Rewrites all the commutative reductions from LOOP out of SSA.
2942 Returns true when something has been changed. */
2945 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2949 gimple_stmt_iterator gsi;
2950 edge exit = single_exit (loop);
2952 bool changed = false;
2957 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2958 if ((res = gimple_phi_result (gsi_stmt (gsi)))
2959 && is_gimple_reg (res)
2960 && !scev_analyzable_p (res, region))
2961 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
2962 (gsi_stmt (gsi), reductions);
2967 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2970 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2974 bool changed = false;
2976 if (!flag_associative_math)
2979 FOR_EACH_LOOP (li, loop, 0)
2980 if (loop_in_sese_p (loop, region))
2981 changed |= rewrite_commutative_reductions_out_of_ssa_loop (loop,
2988 gsi_commit_edge_inserts ();
2989 update_ssa (TODO_update_ssa);
2990 #ifdef ENABLE_CHECKING
2991 verify_loop_closed_ssa (true);
2996 /* Java does not initialize long_long_integer_type_node. */
2997 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2999 /* Can all ivs be represented by a signed integer?
3000 As CLooG might generate negative values in its expressions, signed loop ivs
3001 are required in the backend. */
3004 scop_ivs_can_be_represented (scop_p scop)
3008 gimple_stmt_iterator psi;
3010 FOR_EACH_LOOP (li, loop, 0)
3012 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3015 for (psi = gsi_start_phis (loop->header);
3016 !gsi_end_p (psi); gsi_next (&psi))
3018 gimple phi = gsi_stmt (psi);
3019 tree res = PHI_RESULT (phi);
3020 tree type = TREE_TYPE (res);
3022 if (TYPE_UNSIGNED (type)
3023 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
3033 /* Builds the polyhedral representation for a SESE region. */
3036 build_poly_scop (scop_p scop)
3038 sese region = SCOP_REGION (scop);
3039 graphite_dim_t max_dim;
3042 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3043 Once CLooG is fixed, remove this guard. Anyways, it makes no
3044 sense to optimize a scop containing only PBBs that do not belong
3046 if (nb_pbbs_in_loops (scop) == 0)
3049 if (!scop_ivs_can_be_represented (scop))
3052 build_sese_loop_nests (region);
3053 build_sese_conditions (region);
3054 find_scop_parameters (scop);
3056 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3057 if (scop_nb_params (scop) > max_dim)
3060 build_scop_iteration_domain (scop);
3061 build_scop_context (scop);
3063 add_conditions_to_constraints (scop);
3065 build_scop_scattering (scop);
3066 build_scop_drs (scop);
3068 /* This SCoP has been translated to the polyhedral
3070 POLY_SCOP_P (scop) = true;