1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009, 2010, 2011 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"
24 #include "tree-flow.h"
25 #include "tree-dump.h"
27 #include "tree-chrec.h"
28 #include "tree-data-ref.h"
29 #include "tree-scalar-evolution.h"
35 #include "graphite-ppl.h"
36 #include "graphite-poly.h"
37 #include "graphite-sese-to-poly.h"
39 /* Returns the index of the PHI argument defined in the outermost
43 phi_arg_in_outermost_loop (gimple phi)
45 loop_p loop = gimple_bb (phi)->loop_father;
48 for (i = 0; i < gimple_phi_num_args (phi); i++)
49 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
51 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
58 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
59 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
62 remove_simple_copy_phi (gimple_stmt_iterator *psi)
64 gimple phi = gsi_stmt (*psi);
65 tree res = gimple_phi_result (phi);
66 size_t entry = phi_arg_in_outermost_loop (phi);
67 tree init = gimple_phi_arg_def (phi, entry);
68 gimple stmt = gimple_build_assign (res, init);
69 edge e = gimple_phi_arg_edge (phi, entry);
71 remove_phi_node (psi, false);
72 gsi_insert_on_edge_immediate (e, stmt);
73 SSA_NAME_DEF_STMT (res) = stmt;
76 /* Removes an invariant phi node at position PSI by inserting on the
77 loop ENTRY edge the assignment RES = INIT. */
80 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
82 gimple phi = gsi_stmt (*psi);
83 loop_p loop = loop_containing_stmt (phi);
84 tree res = gimple_phi_result (phi);
85 tree scev = scalar_evolution_in_region (region, loop, res);
86 size_t entry = phi_arg_in_outermost_loop (phi);
87 edge e = gimple_phi_arg_edge (phi, entry);
91 gimple_stmt_iterator gsi;
93 if (tree_contains_chrecs (scev, NULL))
94 scev = gimple_phi_arg_def (phi, entry);
96 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
97 stmt = gimple_build_assign (res, var);
98 remove_phi_node (psi, false);
101 stmts = gimple_seq_alloc ();
103 gsi = gsi_last (stmts);
104 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
105 gsi_insert_seq_on_edge (e, stmts);
106 gsi_commit_edge_inserts ();
107 SSA_NAME_DEF_STMT (res) = stmt;
110 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
113 simple_copy_phi_p (gimple phi)
117 if (gimple_phi_num_args (phi) != 2)
120 res = gimple_phi_result (phi);
121 return (res == gimple_phi_arg_def (phi, 0)
122 || res == gimple_phi_arg_def (phi, 1));
125 /* Returns true when the phi node at position PSI is a reduction phi
126 node in REGION. Otherwise moves the pointer PSI to the next phi to
130 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
133 gimple phi = gsi_stmt (*psi);
134 tree res = gimple_phi_result (phi);
136 loop = loop_containing_stmt (phi);
138 if (simple_copy_phi_p (phi))
140 /* PRE introduces phi nodes like these, for an example,
141 see id-5.f in the fortran graphite testsuite:
143 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
145 remove_simple_copy_phi (psi);
149 if (scev_analyzable_p (res, region))
151 tree scev = scalar_evolution_in_region (region, loop, res);
153 if (evolution_function_is_invariant_p (scev, loop->num))
154 remove_invariant_phi (region, psi);
161 /* All the other cases are considered reductions. */
165 /* Store the GRAPHITE representation of BB. */
168 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
170 struct gimple_bb *gbb;
172 gbb = XNEW (struct gimple_bb);
175 GBB_DATA_REFS (gbb) = drs;
176 GBB_CONDITIONS (gbb) = NULL;
177 GBB_CONDITION_CASES (gbb) = NULL;
183 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
186 struct data_reference *dr;
188 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
191 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
194 free (bap->alias_set);
203 free_gimple_bb (struct gimple_bb *gbb)
205 free_data_refs_aux (GBB_DATA_REFS (gbb));
206 free_data_refs (GBB_DATA_REFS (gbb));
208 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
209 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
210 GBB_BB (gbb)->aux = 0;
214 /* Deletes all gimple bbs in SCOP. */
217 remove_gbbs_in_scop (scop_p scop)
222 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
223 free_gimple_bb (PBB_BLACK_BOX (pbb));
226 /* Deletes all scops in SCOPS. */
229 free_scops (VEC (scop_p, heap) *scops)
234 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
236 remove_gbbs_in_scop (scop);
237 free_sese (SCOP_REGION (scop));
241 VEC_free (scop_p, heap, scops);
244 /* Generates a polyhedral black box only if the bb contains interesting
248 try_generate_gimple_bb (scop_p scop, basic_block bb)
250 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
251 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
252 gimple_stmt_iterator gsi;
254 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
256 gimple stmt = gsi_stmt (gsi);
257 if (!is_gimple_debug (stmt))
258 graphite_find_data_references_in_stmt (nest, stmt, &drs);
261 return new_gimple_bb (bb, drs);
264 /* Returns true if all predecessors of BB, that are not dominated by BB, are
265 marked in MAP. The predecessors dominated by BB are loop latches and will
266 be handled after BB. */
269 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
274 FOR_EACH_EDGE (e, ei, bb->preds)
275 if (!TEST_BIT (map, e->src->index)
276 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
282 /* Compare the depth of two basic_block's P1 and P2. */
285 compare_bb_depths (const void *p1, const void *p2)
287 const_basic_block const bb1 = *(const_basic_block const*)p1;
288 const_basic_block const bb2 = *(const_basic_block const*)p2;
289 int d1 = loop_depth (bb1->loop_father);
290 int d2 = loop_depth (bb2->loop_father);
301 /* Sort the basic blocks from DOM such that the first are the ones at
302 a deepest loop level. */
305 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
307 VEC_qsort (basic_block, dom, compare_bb_depths);
310 /* Recursive helper function for build_scops_bbs. */
313 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
315 sese region = SCOP_REGION (scop);
316 VEC (basic_block, heap) *dom;
319 if (TEST_BIT (visited, bb->index)
320 || !bb_in_sese_p (bb, region))
323 pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb));
324 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
325 SET_BIT (visited, bb->index);
327 dom = get_dominated_by (CDI_DOMINATORS, bb);
332 graphite_sort_dominated_info (dom);
334 while (!VEC_empty (basic_block, dom))
339 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
340 if (all_non_dominated_preds_marked_p (dom_bb, visited))
342 build_scop_bbs_1 (scop, visited, dom_bb);
343 VEC_unordered_remove (basic_block, dom, i);
348 VEC_free (basic_block, heap, dom);
351 /* Gather the basic blocks belonging to the SCOP. */
354 build_scop_bbs (scop_p scop)
356 sbitmap visited = sbitmap_alloc (last_basic_block);
357 sese region = SCOP_REGION (scop);
359 sbitmap_zero (visited);
360 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
361 sbitmap_free (visited);
364 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
365 We generate SCATTERING_DIMENSIONS scattering dimensions.
367 CLooG 0.15.0 and previous versions require, that all
368 scattering functions of one CloogProgram have the same number of
369 scattering dimensions, therefore we allow to specify it. This
370 should be removed in future versions of CLooG.
372 The scattering polyhedron consists of these dimensions: scattering,
373 loop_iterators, parameters.
377 | scattering_dimensions = 5
378 | used_scattering_dimensions = 3
386 | Scattering polyhedron:
388 | scattering: {s1, s2, s3, s4, s5}
389 | loop_iterators: {i}
390 | parameters: {p1, p2}
392 | s1 s2 s3 s4 s5 i p1 p2 1
393 | 1 0 0 0 0 0 0 0 -4 = 0
394 | 0 1 0 0 0 -1 0 0 0 = 0
395 | 0 0 1 0 0 0 0 0 -5 = 0 */
398 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
399 poly_bb_p pbb, int scattering_dimensions)
402 scop_p scop = PBB_SCOP (pbb);
403 int nb_iterators = pbb_dim_iter_domain (pbb);
404 int used_scattering_dimensions = nb_iterators * 2 + 1;
405 int nb_params = scop_nb_params (scop);
407 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
410 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
413 ppl_new_Coefficient (&c);
414 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
415 ppl_new_C_Polyhedron_from_space_dimension
416 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
418 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
420 for (i = 0; i < scattering_dimensions; i++)
422 ppl_Constraint_t cstr;
423 ppl_Linear_Expression_t expr;
425 ppl_new_Linear_Expression_with_dimension (&expr, dim);
427 ppl_assign_Coefficient_from_mpz_t (c, v);
428 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
430 /* Textual order inside this loop. */
433 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
434 ppl_Coefficient_to_mpz_t (c, v);
436 ppl_assign_Coefficient_from_mpz_t (c, v);
437 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
440 /* Iterations of this loop. */
441 else /* if ((i % 2) == 1) */
443 int loop = (i - 1) / 2;
446 ppl_assign_Coefficient_from_mpz_t (c, v);
447 ppl_Linear_Expression_add_to_coefficient
448 (expr, scattering_dimensions + loop, c);
451 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
452 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
453 ppl_delete_Linear_Expression (expr);
454 ppl_delete_Constraint (cstr);
458 ppl_delete_Coefficient (c);
460 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
463 /* Build for BB the static schedule.
465 The static schedule is a Dewey numbering of the abstract syntax
466 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
468 The following example informally defines the static schedule:
487 Static schedules for A to F:
500 build_scop_scattering (scop_p scop)
504 gimple_bb_p previous_gbb = NULL;
505 ppl_Linear_Expression_t static_schedule;
510 ppl_new_Coefficient (&c);
511 ppl_new_Linear_Expression (&static_schedule);
513 /* We have to start schedules at 0 on the first component and
514 because we cannot compare_prefix_loops against a previous loop,
515 prefix will be equal to zero, and that index will be
516 incremented before copying. */
518 ppl_assign_Coefficient_from_mpz_t (c, v);
519 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
521 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
523 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
524 ppl_Linear_Expression_t common;
526 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
529 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
534 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
535 ppl_assign_Linear_Expression_from_Linear_Expression (common,
539 ppl_assign_Coefficient_from_mpz_t (c, v);
540 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
541 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
544 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
546 ppl_delete_Linear_Expression (common);
550 ppl_delete_Coefficient (c);
551 ppl_delete_Linear_Expression (static_schedule);
554 /* Add the value K to the dimension D of the linear expression EXPR. */
557 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
561 ppl_Coefficient_t coef;
563 ppl_new_Coefficient (&coef);
564 ppl_Linear_Expression_coefficient (expr, d, coef);
566 ppl_Coefficient_to_mpz_t (coef, val);
568 mpz_add (val, val, k);
570 ppl_assign_Coefficient_from_mpz_t (coef, val);
571 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
573 ppl_delete_Coefficient (coef);
576 /* In the context of scop S, scan E, the right hand side of a scalar
577 evolution function in loop VAR, and translate it to a linear
581 scan_tree_for_params_right_scev (sese s, tree e, int var,
582 ppl_Linear_Expression_t expr)
586 loop_p loop = get_loop (var);
587 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
590 /* Scalar evolutions should happen in the sese region. */
591 gcc_assert (sese_loop_depth (s, loop) > 0);
593 /* We can not deal with parametric strides like:
599 gcc_assert (TREE_CODE (e) == INTEGER_CST);
602 tree_int_to_gmp (e, val);
603 add_value_to_dim (l, expr, val);
608 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
609 linear expression EXPR. K is the multiplier of the constant. */
612 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
615 ppl_Coefficient_t coef;
616 tree type = TREE_TYPE (cst);
620 /* Necessary to not get "-1 = 2^n - 1". */
621 mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
622 TYPE_PRECISION (type)), false);
624 mpz_mul (val, val, k);
625 ppl_new_Coefficient (&coef);
626 ppl_assign_Coefficient_from_mpz_t (coef, val);
627 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
629 ppl_delete_Coefficient (coef);
632 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
633 Otherwise returns -1. */
636 parameter_index_in_region_1 (tree name, sese region)
641 gcc_assert (TREE_CODE (name) == SSA_NAME);
643 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
650 /* When the parameter NAME is in REGION, returns its index in
651 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
652 and returns the index of NAME. */
655 parameter_index_in_region (tree name, sese region)
659 gcc_assert (TREE_CODE (name) == SSA_NAME);
661 i = parameter_index_in_region_1 (name, region);
665 gcc_assert (SESE_ADD_PARAMS (region));
667 i = VEC_length (tree, SESE_PARAMS (region));
668 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
672 /* In the context of sese S, scan the expression E and translate it to
673 a linear expression C. When parsing a symbolic multiplication, K
674 represents the constant multiplier of an expression containing
678 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
681 if (e == chrec_dont_know)
684 switch (TREE_CODE (e))
686 case POLYNOMIAL_CHREC:
687 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
688 CHREC_VARIABLE (e), c);
689 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
693 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
698 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
700 tree_int_to_gmp (TREE_OPERAND (e, 1), val);
701 mpz_mul (val, val, k);
702 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
706 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
713 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
715 tree_int_to_gmp (TREE_OPERAND (e, 0), val);
716 mpz_mul (val, val, k);
717 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
721 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
726 case POINTER_PLUS_EXPR:
727 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
728 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
733 ppl_Linear_Expression_t tmp_expr = NULL;
737 ppl_dimension_type dim;
738 ppl_Linear_Expression_space_dimension (c, &dim);
739 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
742 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
743 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
747 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
749 ppl_delete_Linear_Expression (tmp_expr);
757 ppl_Linear_Expression_t tmp_expr = NULL;
761 ppl_dimension_type dim;
762 ppl_Linear_Expression_space_dimension (c, &dim);
763 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
766 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
770 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
772 ppl_delete_Linear_Expression (tmp_expr);
780 ppl_Linear_Expression_t tmp_expr = NULL;
784 ppl_dimension_type dim;
785 ppl_Linear_Expression_space_dimension (c, &dim);
786 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
789 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
793 ppl_Coefficient_t coef;
796 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
798 ppl_delete_Linear_Expression (tmp_expr);
799 mpz_init (minus_one);
800 mpz_set_si (minus_one, -1);
801 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
802 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
803 mpz_clear (minus_one);
804 ppl_delete_Coefficient (coef);
812 ppl_dimension_type p = parameter_index_in_region (e, s);
816 ppl_dimension_type dim;
817 ppl_Linear_Expression_space_dimension (c, &dim);
818 p += dim - sese_nb_params (s);
819 add_value_to_dim (p, c, k);
826 scan_tree_for_params_int (e, c, k);
830 case NON_LVALUE_EXPR:
831 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
843 /* Find parameters with respect to REGION in BB. We are looking in memory
844 access functions, conditions and loop bounds. */
847 find_params_in_bb (sese region, gimple_bb_p gbb)
853 loop_p loop = GBB_BB (gbb)->loop_father;
859 /* Find parameters in the access functions of data references. */
860 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
861 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
862 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
864 /* Find parameters in conditional statements. */
865 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
867 tree lhs = scalar_evolution_in_region (region, loop,
868 gimple_cond_lhs (stmt));
869 tree rhs = scalar_evolution_in_region (region, loop,
870 gimple_cond_rhs (stmt));
872 scan_tree_for_params (region, lhs, NULL, one);
873 scan_tree_for_params (region, rhs, NULL, one);
879 /* Record the parameters used in the SCOP. A variable is a parameter
880 in a scop if it does not vary during the execution of that scop. */
883 find_scop_parameters (scop_p scop)
887 sese region = SCOP_REGION (scop);
894 /* Find the parameters used in the loop bounds. */
895 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
897 tree nb_iters = number_of_latch_executions (loop);
899 if (!chrec_contains_symbols (nb_iters))
902 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
903 scan_tree_for_params (region, nb_iters, NULL, one);
908 /* Find the parameters used in data accesses. */
909 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
910 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
912 scop_set_nb_params (scop, sese_nb_params (region));
913 SESE_ADD_PARAMS (region) = false;
915 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
916 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
919 /* Insert in the SCOP context constraints from the estimation of the
920 number of iterations. UB_EXPR is a linear expression describing
921 the number of iterations in a loop. This expression is bounded by
922 the estimation NIT. */
925 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
926 ppl_dimension_type dim,
927 ppl_Linear_Expression_t ub_expr)
930 ppl_Linear_Expression_t nb_iters_le;
931 ppl_Polyhedron_t pol;
932 ppl_Coefficient_t coef;
935 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
936 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
939 /* Construct the negated number of last iteration in VAL. */
941 mpz_set_double_int (val, nit, false);
942 mpz_sub_ui (val, val, 1);
945 /* NB_ITERS_LE holds the number of last iteration in
946 parametrical form. Subtract estimated number of last
947 iteration and assert that result is not positive. */
948 ppl_new_Coefficient_from_mpz_t (&coef, val);
949 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
950 ppl_delete_Coefficient (coef);
951 ppl_new_Constraint (&ub, nb_iters_le,
952 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
953 ppl_Polyhedron_add_constraint (pol, ub);
955 /* Remove all but last GDIM dimensions from POL to obtain
956 only the constraints on the parameters. */
958 graphite_dim_t gdim = scop_nb_params (scop);
959 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
962 for (i = 0; i < dim - gdim; i++)
965 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
969 /* Add the constraints on the parameters to the SCoP context. */
971 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
973 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
974 (&constraints_ps, pol);
975 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
976 (SCOP_CONTEXT (scop), constraints_ps);
977 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
980 ppl_delete_Polyhedron (pol);
981 ppl_delete_Linear_Expression (nb_iters_le);
982 ppl_delete_Constraint (ub);
986 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
987 the constraints for the surrounding loops. */
990 build_loop_iteration_domains (scop_p scop, struct loop *loop,
991 ppl_Polyhedron_t outer_ph, int nb,
992 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
996 tree nb_iters = number_of_latch_executions (loop);
997 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
998 sese region = SCOP_REGION (scop);
1001 ppl_const_Constraint_System_t pcs;
1002 ppl_dimension_type *map
1003 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1005 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1006 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1007 ppl_Polyhedron_add_constraints (ph, pcs);
1009 for (i = 0; i < (int) nb; i++)
1011 for (i = (int) nb; i < (int) dim - 1; i++)
1015 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1021 ppl_Constraint_t lb;
1022 ppl_Linear_Expression_t lb_expr;
1024 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1025 ppl_set_coef (lb_expr, nb, 1);
1026 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1027 ppl_delete_Linear_Expression (lb_expr);
1028 ppl_Polyhedron_add_constraint (ph, lb);
1029 ppl_delete_Constraint (lb);
1032 if (TREE_CODE (nb_iters) == INTEGER_CST)
1034 ppl_Constraint_t ub;
1035 ppl_Linear_Expression_t ub_expr;
1037 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1039 /* loop_i <= cst_nb_iters */
1040 ppl_set_coef (ub_expr, nb, -1);
1041 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1042 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1043 ppl_Polyhedron_add_constraint (ph, ub);
1044 ppl_delete_Linear_Expression (ub_expr);
1045 ppl_delete_Constraint (ub);
1047 else if (!chrec_contains_undetermined (nb_iters))
1050 ppl_Constraint_t ub;
1051 ppl_Linear_Expression_t ub_expr;
1055 mpz_set_si (one, 1);
1056 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1057 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1058 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1061 if (estimated_loop_iterations (loop, true, &nit))
1062 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1064 /* loop_i <= expr_nb_iters */
1065 ppl_set_coef (ub_expr, nb, -1);
1066 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1067 ppl_Polyhedron_add_constraint (ph, ub);
1068 ppl_delete_Linear_Expression (ub_expr);
1069 ppl_delete_Constraint (ub);
1074 if (loop->inner && loop_in_sese_p (loop->inner, region))
1075 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1079 && loop_in_sese_p (loop->next, region))
1080 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1082 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1083 (&domains[loop->num], ph);
1085 ppl_delete_Polyhedron (ph);
1088 /* Returns a linear expression for tree T evaluated in PBB. */
1090 static ppl_Linear_Expression_t
1091 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1094 ppl_Linear_Expression_t res;
1095 ppl_dimension_type dim;
1096 sese region = SCOP_REGION (PBB_SCOP (pbb));
1097 loop_p loop = pbb_loop (pbb);
1099 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1100 ppl_new_Linear_Expression_with_dimension (&res, dim);
1102 t = scalar_evolution_in_region (region, loop, t);
1103 gcc_assert (!automatically_generated_chrec_p (t));
1106 mpz_set_si (one, 1);
1107 scan_tree_for_params (region, t, res, one);
1113 /* Returns the ppl constraint type from the gimple tree code CODE. */
1115 static enum ppl_enum_Constraint_Type
1116 ppl_constraint_type_from_tree_code (enum tree_code code)
1120 /* We do not support LT and GT to be able to work with C_Polyhedron.
1121 As we work on integer polyhedron "a < b" can be expressed by
1128 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1131 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1134 return PPL_CONSTRAINT_TYPE_EQUAL;
1141 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1142 CODE is used as the comparison operator. This allows us to invert the
1143 condition or to handle inequalities. */
1146 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1147 poly_bb_p pbb, enum tree_code code)
1150 ppl_Coefficient_t c;
1151 ppl_Linear_Expression_t left, right;
1152 ppl_Constraint_t cstr;
1153 enum ppl_enum_Constraint_Type type;
1155 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1156 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1158 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1159 the left or the right side of the expression. */
1160 if (code == LT_EXPR)
1164 ppl_new_Coefficient (&c);
1165 ppl_assign_Coefficient_from_mpz_t (c, v);
1166 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1167 ppl_delete_Coefficient (c);
1172 else if (code == GT_EXPR)
1176 ppl_new_Coefficient (&c);
1177 ppl_assign_Coefficient_from_mpz_t (c, v);
1178 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1179 ppl_delete_Coefficient (c);
1185 type = ppl_constraint_type_from_tree_code (code);
1187 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1189 ppl_new_Constraint (&cstr, left, type);
1190 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1192 ppl_delete_Constraint (cstr);
1193 ppl_delete_Linear_Expression (left);
1194 ppl_delete_Linear_Expression (right);
1197 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1198 operator. This allows us to invert the condition or to handle
1202 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1204 if (code == NE_EXPR)
1206 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1207 ppl_Pointset_Powerset_C_Polyhedron_t right;
1208 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1210 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1211 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1212 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1213 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1216 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1219 /* Add conditions to the domain of PBB. */
1222 add_conditions_to_domain (poly_bb_p pbb)
1226 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1228 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1231 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1232 switch (gimple_code (stmt))
1236 enum tree_code code = gimple_cond_code (stmt);
1238 /* The conditions for ELSE-branches are inverted. */
1239 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1240 code = invert_tree_comparison (code, false);
1242 add_condition_to_pbb (pbb, stmt, code);
1247 /* Switch statements are not supported right now - fall throught. */
1255 /* Traverses all the GBBs of the SCOP and add their constraints to the
1256 iteration domains. */
1259 add_conditions_to_constraints (scop_p scop)
1264 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1265 add_conditions_to_domain (pbb);
1268 /* Structure used to pass data to dom_walk. */
1272 VEC (gimple, heap) **conditions, **cases;
1276 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1277 edge between BB and its predecessor is not a loop exit edge, and
1278 the last statement of the single predecessor is a COND_EXPR. */
1281 single_pred_cond_non_loop_exit (basic_block bb)
1283 if (single_pred_p (bb))
1285 edge e = single_pred_edge (bb);
1286 basic_block pred = e->src;
1289 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1292 stmt = last_stmt (pred);
1294 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1301 /* Call-back for dom_walk executed before visiting the dominated
1305 build_sese_conditions_before (struct dom_walk_data *dw_data,
1308 struct bsc *data = (struct bsc *) dw_data->global_data;
1309 VEC (gimple, heap) **conditions = data->conditions;
1310 VEC (gimple, heap) **cases = data->cases;
1314 if (!bb_in_sese_p (bb, data->region))
1317 stmt = single_pred_cond_non_loop_exit (bb);
1321 edge e = single_pred_edge (bb);
1323 VEC_safe_push (gimple, heap, *conditions, stmt);
1325 if (e->flags & EDGE_TRUE_VALUE)
1326 VEC_safe_push (gimple, heap, *cases, stmt);
1328 VEC_safe_push (gimple, heap, *cases, NULL);
1331 gbb = gbb_from_bb (bb);
1335 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1336 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1340 /* Call-back for dom_walk executed after visiting the dominated
1344 build_sese_conditions_after (struct dom_walk_data *dw_data,
1347 struct bsc *data = (struct bsc *) dw_data->global_data;
1348 VEC (gimple, heap) **conditions = data->conditions;
1349 VEC (gimple, heap) **cases = data->cases;
1351 if (!bb_in_sese_p (bb, data->region))
1354 if (single_pred_cond_non_loop_exit (bb))
1356 VEC_pop (gimple, *conditions);
1357 VEC_pop (gimple, *cases);
1361 /* Record all conditions in REGION. */
1364 build_sese_conditions (sese region)
1366 struct dom_walk_data walk_data;
1367 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1368 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1371 data.conditions = &conditions;
1372 data.cases = &cases;
1373 data.region = region;
1375 walk_data.dom_direction = CDI_DOMINATORS;
1376 walk_data.initialize_block_local_data = NULL;
1377 walk_data.before_dom_children = build_sese_conditions_before;
1378 walk_data.after_dom_children = build_sese_conditions_after;
1379 walk_data.global_data = &data;
1380 walk_data.block_local_data_size = 0;
1382 init_walk_dominator_tree (&walk_data);
1383 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1384 fini_walk_dominator_tree (&walk_data);
1386 VEC_free (gimple, heap, conditions);
1387 VEC_free (gimple, heap, cases);
1390 /* Add constraints on the possible values of parameter P from the type
1394 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1396 ppl_Constraint_t cstr;
1397 ppl_Linear_Expression_t le;
1398 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1399 tree type = TREE_TYPE (parameter);
1400 tree lb = NULL_TREE;
1401 tree ub = NULL_TREE;
1403 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1404 lb = lower_bound_in_type (type, type);
1406 lb = TYPE_MIN_VALUE (type);
1408 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1409 ub = upper_bound_in_type (type, type);
1411 ub = TYPE_MAX_VALUE (type);
1415 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1416 ppl_set_coef (le, p, -1);
1417 ppl_set_inhomogeneous_tree (le, lb);
1418 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1419 ppl_Polyhedron_add_constraint (context, cstr);
1420 ppl_delete_Linear_Expression (le);
1421 ppl_delete_Constraint (cstr);
1426 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1427 ppl_set_coef (le, p, -1);
1428 ppl_set_inhomogeneous_tree (le, ub);
1429 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1430 ppl_Polyhedron_add_constraint (context, cstr);
1431 ppl_delete_Linear_Expression (le);
1432 ppl_delete_Constraint (cstr);
1436 /* Build the context of the SCOP. The context usually contains extra
1437 constraints that are added to the iteration domains that constrain
1441 build_scop_context (scop_p scop)
1443 ppl_Polyhedron_t context;
1444 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1445 graphite_dim_t p, n = scop_nb_params (scop);
1447 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1449 for (p = 0; p < n; p++)
1450 add_param_constraints (scop, context, p);
1452 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1454 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1455 (SCOP_CONTEXT (scop), ps);
1457 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1458 ppl_delete_Polyhedron (context);
1461 /* Build the iteration domains: the loops belonging to the current
1462 SCOP, and that vary for the execution of the current basic block.
1463 Returns false if there is no loop in SCOP. */
1466 build_scop_iteration_domain (scop_p scop)
1469 sese region = SCOP_REGION (scop);
1471 ppl_Polyhedron_t ph;
1473 int nb_loops = number_of_loops ();
1474 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1475 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1477 for (i = 0; i < nb_loops; i++)
1480 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1482 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1483 if (!loop_in_sese_p (loop_outer (loop), region))
1484 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1486 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1487 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1488 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1489 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1490 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1492 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1493 (&PBB_DOMAIN (pbb), ph);
1495 for (i = 0; i < nb_loops; i++)
1497 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1499 ppl_delete_Polyhedron (ph);
1503 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1504 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1505 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1509 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1510 ppl_dimension_type accessp_nb_dims,
1511 ppl_dimension_type dom_nb_dims)
1513 ppl_Linear_Expression_t alias;
1514 ppl_Constraint_t cstr;
1515 int alias_set_num = 0;
1516 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1518 if (bap && bap->alias_set)
1519 alias_set_num = *(bap->alias_set);
1521 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1523 ppl_set_coef (alias, dom_nb_dims, 1);
1524 ppl_set_inhomogeneous (alias, -alias_set_num);
1525 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1526 ppl_Polyhedron_add_constraint (accesses, cstr);
1528 ppl_delete_Linear_Expression (alias);
1529 ppl_delete_Constraint (cstr);
1532 /* Add to ACCESSES polyhedron equalities defining the access functions
1533 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1534 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1535 PBB is the poly_bb_p that contains the data reference DR. */
1538 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1539 ppl_dimension_type accessp_nb_dims,
1540 ppl_dimension_type dom_nb_dims,
1543 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1545 scop_p scop = PBB_SCOP (pbb);
1546 sese region = SCOP_REGION (scop);
1550 for (i = 0; i < nb_subscripts; i++)
1552 ppl_Linear_Expression_t fn, access;
1553 ppl_Constraint_t cstr;
1554 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1555 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1557 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1558 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1561 scan_tree_for_params (region, afn, fn, v);
1562 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1564 ppl_set_coef (access, subscript, -1);
1565 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1566 ppl_Polyhedron_add_constraint (accesses, cstr);
1568 ppl_delete_Linear_Expression (fn);
1569 ppl_delete_Linear_Expression (access);
1570 ppl_delete_Constraint (cstr);
1576 /* Add constrains representing the size of the accessed data to the
1577 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1578 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1582 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1583 ppl_dimension_type accessp_nb_dims,
1584 ppl_dimension_type dom_nb_dims)
1586 tree ref = DR_REF (dr);
1587 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1589 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1591 ppl_Linear_Expression_t expr;
1592 ppl_Constraint_t cstr;
1593 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1596 if (TREE_CODE (ref) != ARRAY_REF)
1599 low = array_ref_low_bound (ref);
1601 /* subscript - low >= 0 */
1602 if (host_integerp (low, 0))
1606 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1607 ppl_set_coef (expr, subscript, 1);
1609 minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low);
1610 ppl_set_inhomogeneous_tree (expr, minus_low);
1612 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1613 ppl_Polyhedron_add_constraint (accesses, cstr);
1614 ppl_delete_Linear_Expression (expr);
1615 ppl_delete_Constraint (cstr);
1618 high = array_ref_up_bound (ref);
1620 /* high - subscript >= 0 */
1621 if (high && host_integerp (high, 0)
1622 /* 1-element arrays at end of structures may extend over
1623 their declared size. */
1624 && !(array_at_struct_end_p (ref)
1625 && operand_equal_p (low, high, 0)))
1627 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1628 ppl_set_coef (expr, subscript, -1);
1630 ppl_set_inhomogeneous_tree (expr, high);
1632 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1633 ppl_Polyhedron_add_constraint (accesses, cstr);
1634 ppl_delete_Linear_Expression (expr);
1635 ppl_delete_Constraint (cstr);
1640 /* Build data accesses for DR in PBB. */
1643 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1645 ppl_Polyhedron_t accesses;
1646 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1647 ppl_dimension_type dom_nb_dims;
1648 ppl_dimension_type accessp_nb_dims;
1649 int dr_base_object_set;
1651 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1653 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1655 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1657 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1658 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1659 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1661 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1663 ppl_delete_Polyhedron (accesses);
1665 gcc_assert (dr->aux);
1666 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1668 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1669 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1670 dr, DR_NUM_DIMENSIONS (dr));
1673 /* Write to FILE the alias graph of data references in DIMACS format. */
1676 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1677 VEC (data_reference_p, heap) *drs)
1679 int num_vertex = VEC_length (data_reference_p, drs);
1681 data_reference_p dr1, dr2;
1684 if (num_vertex == 0)
1687 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1688 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1689 if (dr_may_alias_p (dr1, dr2))
1692 fprintf (file, "$\n");
1695 fprintf (file, "c %s\n", comment);
1697 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1699 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1700 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1701 if (dr_may_alias_p (dr1, dr2))
1702 fprintf (file, "e %d %d\n", i + 1, j + 1);
1707 /* Write to FILE the alias graph of data references in DOT format. */
1710 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1711 VEC (data_reference_p, heap) *drs)
1713 int num_vertex = VEC_length (data_reference_p, drs);
1714 data_reference_p dr1, dr2;
1717 if (num_vertex == 0)
1720 fprintf (file, "$\n");
1723 fprintf (file, "c %s\n", comment);
1725 /* First print all the vertices. */
1726 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1727 fprintf (file, "n%d;\n", i);
1729 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1730 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1731 if (dr_may_alias_p (dr1, dr2))
1732 fprintf (file, "n%d n%d\n", i, j);
1737 /* Write to FILE the alias graph of data references in ECC format. */
1740 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1741 VEC (data_reference_p, heap) *drs)
1743 int num_vertex = VEC_length (data_reference_p, drs);
1744 data_reference_p dr1, dr2;
1747 if (num_vertex == 0)
1750 fprintf (file, "$\n");
1753 fprintf (file, "c %s\n", comment);
1755 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1756 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1757 if (dr_may_alias_p (dr1, dr2))
1758 fprintf (file, "%d %d\n", i, j);
1763 /* Check if DR1 and DR2 are in the same object set. */
1766 dr_same_base_object_p (const struct data_reference *dr1,
1767 const struct data_reference *dr2)
1769 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1772 /* Uses DFS component number as representative of alias-sets. Also tests for
1773 optimality by verifying if every connected component is a clique. Returns
1774 true (1) if the above test is true, and false (0) otherwise. */
1777 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1779 int num_vertices = VEC_length (data_reference_p, drs);
1780 struct graph *g = new_graph (num_vertices);
1781 data_reference_p dr1, dr2;
1783 int num_connected_components;
1784 int v_indx1, v_indx2, num_vertices_in_component;
1787 struct graph_edge *e;
1788 int this_component_is_clique;
1789 int all_components_are_cliques = 1;
1791 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1792 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1793 if (dr_may_alias_p (dr1, dr2))
1799 all_vertices = XNEWVEC (int, num_vertices);
1800 vertices = XNEWVEC (int, num_vertices);
1801 for (i = 0; i < num_vertices; i++)
1802 all_vertices[i] = i;
1804 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1806 for (i = 0; i < g->n_vertices; i++)
1808 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1809 base_alias_pair *bap;
1811 gcc_assert (dr->aux);
1812 bap = (base_alias_pair *)(dr->aux);
1814 bap->alias_set = XNEW (int);
1815 *(bap->alias_set) = g->vertices[i].component + 1;
1818 /* Verify if the DFS numbering results in optimal solution. */
1819 for (i = 0; i < num_connected_components; i++)
1821 num_vertices_in_component = 0;
1822 /* Get all vertices whose DFS component number is the same as i. */
1823 for (j = 0; j < num_vertices; j++)
1824 if (g->vertices[j].component == i)
1825 vertices[num_vertices_in_component++] = j;
1827 /* Now test if the vertices in 'vertices' form a clique, by testing
1828 for edges among each pair. */
1829 this_component_is_clique = 1;
1830 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1832 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1834 /* Check if the two vertices are connected by iterating
1835 through all the edges which have one of these are source. */
1836 e = g->vertices[vertices[v_indx2]].pred;
1839 if (e->src == vertices[v_indx1])
1845 this_component_is_clique = 0;
1849 if (!this_component_is_clique)
1850 all_components_are_cliques = 0;
1854 free (all_vertices);
1857 return all_components_are_cliques;
1860 /* Group each data reference in DRS with its base object set num. */
1863 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1865 int num_vertex = VEC_length (data_reference_p, drs);
1866 struct graph *g = new_graph (num_vertex);
1867 data_reference_p dr1, dr2;
1871 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1872 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1873 if (dr_same_base_object_p (dr1, dr2))
1879 queue = XNEWVEC (int, num_vertex);
1880 for (i = 0; i < num_vertex; i++)
1883 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1885 for (i = 0; i < g->n_vertices; i++)
1887 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1888 base_alias_pair *bap;
1890 gcc_assert (dr->aux);
1891 bap = (base_alias_pair *)(dr->aux);
1893 bap->base_obj_set = g->vertices[i].component + 1;
1900 /* Build the data references for PBB. */
1903 build_pbb_drs (poly_bb_p pbb)
1906 data_reference_p dr;
1907 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1909 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
1910 build_poly_dr (dr, pbb);
1913 /* Dump to file the alias graphs for the data references in DRS. */
1916 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
1919 FILE *file_dimacs, *file_ecc, *file_dot;
1921 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1924 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1925 current_function_name ());
1926 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
1927 fclose (file_dimacs);
1930 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
1933 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1934 current_function_name ());
1935 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
1939 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
1942 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1943 current_function_name ());
1944 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
1949 /* Build data references in SCOP. */
1952 build_scop_drs (scop_p scop)
1956 data_reference_p dr;
1957 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1959 /* Remove all the PBBs that do not have data references: these basic
1960 blocks are not handled in the polyhedral representation. */
1961 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1962 if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb))))
1964 free_gimple_bb (PBB_BLACK_BOX (pbb));
1965 VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i);
1969 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1970 for (j = 0; VEC_iterate (data_reference_p,
1971 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
1972 VEC_safe_push (data_reference_p, heap, drs, dr);
1974 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
1975 dr->aux = XNEW (base_alias_pair);
1977 if (!build_alias_set_optimal_p (drs))
1979 /* TODO: Add support when building alias set is not optimal. */
1983 build_base_obj_set_for_drs (drs);
1985 /* When debugging, enable the following code. This cannot be used
1986 in production compilers. */
1988 dump_alias_graphs (drs);
1990 VEC_free (data_reference_p, heap, drs);
1992 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1993 build_pbb_drs (pbb);
1996 /* Return a gsi at the position of the phi node STMT. */
1998 static gimple_stmt_iterator
1999 gsi_for_phi_node (gimple stmt)
2001 gimple_stmt_iterator psi;
2002 basic_block bb = gimple_bb (stmt);
2004 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2005 if (stmt == gsi_stmt (psi))
2012 /* Analyze all the data references of STMTS and add them to the
2013 GBB_DATA_REFS vector of BB. */
2016 analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
2023 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2026 nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
2027 gbb = gbb_from_bb (bb);
2029 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
2030 if (!is_gimple_debug (stmt))
2031 graphite_find_data_references_in_stmt (nest, stmt,
2032 &GBB_DATA_REFS (gbb));
2035 /* Insert STMT at the end of the STMTS sequence and then insert the
2036 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2040 insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts,
2041 gimple_stmt_iterator insert_gsi)
2043 gimple_stmt_iterator gsi;
2044 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2047 stmts = gimple_seq_alloc ();
2049 gsi = gsi_last (stmts);
2050 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2051 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2052 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2054 gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2055 analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
2056 VEC_free (gimple, heap, x);
2059 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2062 insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt)
2065 gimple_stmt_iterator si;
2066 gimple_stmt_iterator gsi;
2067 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2068 gimple stmt = gimple_build_assign (res, var);
2069 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2072 stmts = gimple_seq_alloc ();
2073 si = gsi_last (stmts);
2074 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2075 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2076 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2078 if (gimple_code (after_stmt) == GIMPLE_PHI)
2080 gsi = gsi_after_labels (gimple_bb (after_stmt));
2081 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2085 gsi = gsi_for_stmt (after_stmt);
2086 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2089 analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
2090 VEC_free (gimple, heap, x);
2093 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2096 new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
2098 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2099 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
2100 gimple_bb_p gbb1 = new_gimple_bb (bb, drs);
2101 poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
2102 int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
2104 /* The INDEX of PBB in SCOP_BBS. */
2105 for (index = 0; index < n; index++)
2106 if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
2109 GBB_PBB (gbb1) = pbb1;
2110 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2111 (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
2112 GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
2113 GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
2114 VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
2117 /* Insert on edge E the assignment "RES := EXPR". */
2120 insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
2122 gimple_stmt_iterator gsi;
2124 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2125 gimple stmt = gimple_build_assign (res, var);
2127 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2130 stmts = gimple_seq_alloc ();
2132 gsi = gsi_last (stmts);
2133 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2134 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2135 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2137 gsi_insert_seq_on_edge (e, stmts);
2138 gsi_commit_edge_inserts ();
2139 bb = gimple_bb (stmt);
2141 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2144 if (!gbb_from_bb (bb))
2145 new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
2147 analyze_drs_in_stmts (scop, bb, x);
2148 VEC_free (gimple, heap, x);
2151 /* Creates a zero dimension array of the same type as VAR. */
2154 create_zero_dim_array (tree var, const char *base_name)
2156 tree index_type = build_index_type (integer_zero_node);
2157 tree elt_type = TREE_TYPE (var);
2158 tree array_type = build_array_type (elt_type, index_type);
2159 tree base = create_tmp_var (array_type, base_name);
2161 add_referenced_var (base);
2163 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2167 /* Returns true when PHI is a loop close phi node. */
2170 scalar_close_phi_node_p (gimple phi)
2172 if (gimple_code (phi) != GIMPLE_PHI
2173 || !is_gimple_reg (gimple_phi_result (phi)))
2176 /* Note that loop close phi nodes should have a single argument
2177 because we translated the representation into a canonical form
2178 before Graphite: see canonicalize_loop_closed_ssa_form. */
2179 return (gimple_phi_num_args (phi) == 1);
2182 /* For a definition DEF in REGION, propagates the expression EXPR in
2183 all the uses of DEF outside REGION. */
2186 propagate_expr_outside_region (tree def, tree expr, sese region)
2188 imm_use_iterator imm_iter;
2191 bool replaced_once = false;
2193 gcc_assert (TREE_CODE (def) == SSA_NAME);
2195 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2198 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2199 if (!is_gimple_debug (use_stmt)
2200 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2203 use_operand_p use_p;
2205 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2206 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2207 && (replaced_once = true))
2208 replace_exp (use_p, expr);
2210 update_stmt (use_stmt);
2215 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2216 gsi_commit_edge_inserts ();
2220 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2221 dimension array for it. */
2224 rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2226 sese region = SCOP_REGION (scop);
2227 gimple phi = gsi_stmt (*psi);
2228 tree res = gimple_phi_result (phi);
2229 tree var = SSA_NAME_VAR (res);
2230 basic_block bb = gimple_bb (phi);
2231 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2232 tree arg = gimple_phi_arg_def (phi, 0);
2235 /* Note that loop close phi nodes should have a single argument
2236 because we translated the representation into a canonical form
2237 before Graphite: see canonicalize_loop_closed_ssa_form. */
2238 gcc_assert (gimple_phi_num_args (phi) == 1);
2240 /* The phi node can be a non close phi node, when its argument is
2241 invariant, or a default definition. */
2242 if (is_gimple_min_invariant (arg)
2243 || SSA_NAME_IS_DEFAULT_DEF (arg))
2245 propagate_expr_outside_region (res, arg, region);
2250 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2252 propagate_expr_outside_region (res, arg, region);
2253 stmt = gimple_build_assign (res, arg);
2254 remove_phi_node (psi, false);
2255 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2256 SSA_NAME_DEF_STMT (res) = stmt;
2260 /* If res is scev analyzable and is not a scalar value, it is safe
2261 to ignore the close phi node: it will be code generated in the
2262 out of Graphite pass. */
2263 else if (scev_analyzable_p (res, region))
2265 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2268 if (!loop_in_sese_p (loop, region))
2270 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2271 scev = scalar_evolution_in_region (region, loop, arg);
2272 scev = compute_overall_effect_of_inner_loop (loop, scev);
2275 scev = scalar_evolution_in_region (region, loop, res);
2277 if (tree_does_not_contain_chrecs (scev))
2278 propagate_expr_outside_region (res, scev, region);
2285 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2287 stmt = gimple_build_assign (res, zero_dim_array);
2289 if (TREE_CODE (arg) == SSA_NAME)
2290 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2291 SSA_NAME_DEF_STMT (arg));
2293 insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
2294 zero_dim_array, arg);
2297 remove_phi_node (psi, false);
2298 SSA_NAME_DEF_STMT (res) = stmt;
2300 insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
2303 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2304 dimension array for it. */
2307 rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2310 gimple phi = gsi_stmt (*psi);
2311 basic_block bb = gimple_bb (phi);
2312 tree res = gimple_phi_result (phi);
2313 tree var = SSA_NAME_VAR (res);
2314 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2318 for (i = 0; i < gimple_phi_num_args (phi); i++)
2320 tree arg = gimple_phi_arg_def (phi, i);
2321 edge e = gimple_phi_arg_edge (phi, i);
2323 /* Avoid the insertion of code in the loop latch to please the
2324 pattern matching of the vectorizer. */
2325 if (TREE_CODE (arg) == SSA_NAME
2326 && e->src == bb->loop_father->latch)
2327 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2328 SSA_NAME_DEF_STMT (arg));
2330 insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
2333 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2335 stmt = gimple_build_assign (res, var);
2336 remove_phi_node (psi, false);
2337 SSA_NAME_DEF_STMT (res) = stmt;
2339 insert_stmts (scop, stmt, stmts, gsi_after_labels (bb));
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 (scop, &psi);
2395 else if (reduction_phi_p (region, &psi))
2396 rewrite_phi_out_of_ssa (scop, &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 (scop_p scop, tree zero_dim_array,
2410 tree def, gimple use_stmt)
2412 tree var = SSA_NAME_VAR (def);
2413 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2414 tree name = make_ssa_name (var, name_stmt);
2416 use_operand_p use_p;
2418 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2420 gimple_assign_set_lhs (name_stmt, name);
2421 insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
2423 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2424 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2425 replace_exp (use_p, name);
2427 update_stmt (use_stmt);
2430 /* For every definition DEF in the SCOP that is used outside the scop,
2431 insert a closing-scop definition in the basic block just after this
2435 handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt)
2437 tree var = create_tmp_reg (TREE_TYPE (def), NULL);
2438 tree new_name = make_ssa_name (var, stmt);
2439 bool needs_copy = false;
2440 use_operand_p use_p;
2441 imm_use_iterator imm_iter;
2443 sese region = SCOP_REGION (scop);
2445 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2447 if (!bb_in_sese_p (gimple_bb (use_stmt), region))
2449 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2451 SET_USE (use_p, new_name);
2453 update_stmt (use_stmt);
2458 /* Insert in the empty BB just after the scop a use of DEF such
2459 that the rewrite of cross_bb_scalar_dependences won't insert
2460 arrays everywhere else. */
2463 gimple assign = gimple_build_assign (new_name, def);
2464 gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest);
2466 add_referenced_var (var);
2467 SSA_NAME_DEF_STMT (new_name) = assign;
2468 update_stmt (assign);
2469 gsi_insert_before (&psi, assign, GSI_SAME_STMT);
2473 /* Rewrite the scalar dependences crossing the boundary of the BB
2474 containing STMT with an array. Return true when something has been
2478 rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
2480 sese region = SCOP_REGION (scop);
2481 gimple stmt = gsi_stmt (*gsi);
2482 imm_use_iterator imm_iter;
2485 tree zero_dim_array = NULL_TREE;
2489 switch (gimple_code (stmt))
2492 def = gimple_assign_lhs (stmt);
2496 def = gimple_call_lhs (stmt);
2504 || !is_gimple_reg (def))
2507 if (scev_analyzable_p (def, region))
2509 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2510 tree scev = scalar_evolution_in_region (region, loop, def);
2512 if (tree_contains_chrecs (scev, NULL))
2515 propagate_expr_outside_region (def, scev, region);
2519 def_bb = gimple_bb (stmt);
2521 handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
2523 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2524 if (gimple_code (use_stmt) == GIMPLE_PHI
2527 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2529 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2530 rewrite_close_phi_out_of_ssa (scop, &psi);
2532 rewrite_phi_out_of_ssa (scop, &psi);
2535 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2536 if (gimple_code (use_stmt) != GIMPLE_PHI
2537 && def_bb != gimple_bb (use_stmt)
2538 && !is_gimple_debug (use_stmt)
2541 if (!zero_dim_array)
2543 zero_dim_array = create_zero_dim_array
2544 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2545 insert_out_of_ssa_copy (scop, zero_dim_array, def,
2546 SSA_NAME_DEF_STMT (def));
2550 rewrite_cross_bb_scalar_dependence (scop, zero_dim_array,
2557 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2560 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2563 gimple_stmt_iterator psi;
2564 sese region = SCOP_REGION (scop);
2565 bool changed = false;
2567 /* Create an extra empty BB after the scop. */
2568 split_edge (SESE_EXIT (region));
2571 if (bb_in_sese_p (bb, region))
2572 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2573 changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
2578 update_ssa (TODO_update_ssa);
2579 #ifdef ENABLE_CHECKING
2580 verify_loop_closed_ssa (true);
2585 /* Returns the number of pbbs that are in loops contained in SCOP. */
2588 nb_pbbs_in_loops (scop_p scop)
2594 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2595 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2601 /* Return the number of data references in BB that write in
2605 nb_data_writes_in_bb (basic_block bb)
2608 gimple_stmt_iterator gsi;
2610 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2611 if (gimple_vdef (gsi_stmt (gsi)))
2617 /* Splits at STMT the basic block BB represented as PBB in the
2621 split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt)
2623 edge e1 = split_block (bb, stmt);
2624 new_pbb_from_pbb (scop, pbb, e1->dest);
2628 /* Splits STMT out of its current BB. This is done for reduction
2629 statements for which we want to ignore data dependences. */
2632 split_reduction_stmt (scop_p scop, gimple stmt)
2634 basic_block bb = gimple_bb (stmt);
2635 poly_bb_p pbb = pbb_from_bb (bb);
2636 gimple_bb_p gbb = gbb_from_bb (bb);
2639 data_reference_p dr;
2641 /* Do not split basic blocks with no writes to memory: the reduction
2642 will be the only write to memory. */
2643 if (nb_data_writes_in_bb (bb) == 0
2644 /* Or if we have already marked BB as a reduction. */
2645 || PBB_IS_REDUCTION (pbb_from_bb (bb)))
2648 e1 = split_pbb (scop, pbb, bb, stmt);
2650 /* Split once more only when the reduction stmt is not the only one
2651 left in the original BB. */
2652 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2654 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2656 e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi));
2659 /* A part of the data references will end in a different basic block
2660 after the split: move the DRs from the original GBB to the newly
2662 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
2664 basic_block bb1 = gimple_bb (DR_STMT (dr));
2668 gimple_bb_p gbb1 = gbb_from_bb (bb1);
2669 VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr);
2670 VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i);
2678 /* Return true when stmt is a reduction operation. */
2681 is_reduction_operation_p (gimple stmt)
2683 enum tree_code code;
2685 gcc_assert (is_gimple_assign (stmt));
2686 code = gimple_assign_rhs_code (stmt);
2688 return flag_associative_math
2689 && commutative_tree_code (code)
2690 && associative_tree_code (code);
2693 /* Returns true when PHI contains an argument ARG. */
2696 phi_contains_arg (gimple phi, tree arg)
2700 for (i = 0; i < gimple_phi_num_args (phi); i++)
2701 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2707 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2710 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2714 if (TREE_CODE (arg) != SSA_NAME)
2717 stmt = SSA_NAME_DEF_STMT (arg);
2719 if (gimple_code (stmt) == GIMPLE_NOP
2720 || gimple_code (stmt) == GIMPLE_CALL)
2723 if (gimple_code (stmt) == GIMPLE_PHI)
2725 if (phi_contains_arg (stmt, lhs))
2730 if (!is_gimple_assign (stmt))
2733 if (gimple_num_ops (stmt) == 2)
2734 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2736 if (is_reduction_operation_p (stmt))
2738 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2741 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2747 /* Detect commutative and associative scalar reductions starting at
2748 the STMT. Return the phi node of the reduction cycle, or NULL. */
2751 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2752 VEC (gimple, heap) **in,
2753 VEC (gimple, heap) **out)
2755 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2760 VEC_safe_push (gimple, heap, *in, stmt);
2761 VEC_safe_push (gimple, heap, *out, stmt);
2765 /* Detect commutative and associative scalar reductions starting at
2766 STMT. Return the phi node of the reduction cycle, or NULL. */
2769 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2770 VEC (gimple, heap) **out)
2772 tree lhs = gimple_assign_lhs (stmt);
2774 if (gimple_num_ops (stmt) == 2)
2775 return detect_commutative_reduction_arg (lhs, stmt,
2776 gimple_assign_rhs1 (stmt),
2779 if (is_reduction_operation_p (stmt))
2781 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2782 gimple_assign_rhs1 (stmt),
2785 : detect_commutative_reduction_arg (lhs, stmt,
2786 gimple_assign_rhs2 (stmt),
2793 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2796 follow_inital_value_to_phi (tree arg, tree lhs)
2800 if (!arg || TREE_CODE (arg) != SSA_NAME)
2803 stmt = SSA_NAME_DEF_STMT (arg);
2805 if (gimple_code (stmt) == GIMPLE_PHI
2806 && phi_contains_arg (stmt, lhs))
2813 /* Return the argument of the loop PHI that is the inital value coming
2814 from outside the loop. */
2817 edge_initial_value_for_loop_phi (gimple phi)
2821 for (i = 0; i < gimple_phi_num_args (phi); i++)
2823 edge e = gimple_phi_arg_edge (phi, i);
2825 if (loop_depth (e->src->loop_father)
2826 < loop_depth (e->dest->loop_father))
2833 /* Return the argument of the loop PHI that is the inital value coming
2834 from outside the loop. */
2837 initial_value_for_loop_phi (gimple phi)
2841 for (i = 0; i < gimple_phi_num_args (phi); i++)
2843 edge e = gimple_phi_arg_edge (phi, i);
2845 if (loop_depth (e->src->loop_father)
2846 < loop_depth (e->dest->loop_father))
2847 return gimple_phi_arg_def (phi, i);
2853 /* Detect commutative and associative scalar reductions belonging to
2854 the SCOP starting at the loop closed phi node STMT. Return the phi
2855 node of the reduction cycle, or NULL. */
2858 detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
2859 VEC (gimple, heap) **out)
2861 if (scalar_close_phi_node_p (stmt))
2863 tree arg = gimple_phi_arg_def (stmt, 0);
2864 gimple def, loop_phi;
2866 if (TREE_CODE (arg) != SSA_NAME)
2869 /* Note that loop close phi nodes should have a single argument
2870 because we translated the representation into a canonical form
2871 before Graphite: see canonicalize_loop_closed_ssa_form. */
2872 gcc_assert (gimple_phi_num_args (stmt) == 1);
2874 def = SSA_NAME_DEF_STMT (arg);
2875 if (!stmt_in_sese_p (def, SCOP_REGION (scop)))
2878 loop_phi = detect_commutative_reduction (scop, def, in, out);
2882 tree lhs = gimple_phi_result (stmt);
2883 tree init = initial_value_for_loop_phi (loop_phi);
2884 gimple phi = follow_inital_value_to_phi (init, lhs);
2886 VEC_safe_push (gimple, heap, *in, loop_phi);
2887 VEC_safe_push (gimple, heap, *out, stmt);
2894 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2895 return detect_commutative_reduction_assign (stmt, in, out);
2900 /* Translate the scalar reduction statement STMT to an array RED
2901 knowing that its recursive phi node is LOOP_PHI. */
2904 translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
2905 gimple stmt, gimple loop_phi)
2907 tree res = gimple_phi_result (loop_phi);
2908 gimple assign = gimple_build_assign (res, unshare_expr (red));
2909 gimple_stmt_iterator gsi;
2911 insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
2913 assign = gimple_build_assign (unshare_expr (red), gimple_assign_lhs (stmt));
2914 gsi = gsi_for_stmt (stmt);
2916 insert_stmts (scop, assign, NULL, gsi);
2919 /* Removes the PHI node and resets all the debug stmts that are using
2923 remove_phi (gimple phi)
2925 imm_use_iterator imm_iter;
2927 use_operand_p use_p;
2928 gimple_stmt_iterator gsi;
2929 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2933 def = PHI_RESULT (phi);
2934 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2936 stmt = USE_STMT (use_p);
2938 if (is_gimple_debug (stmt))
2940 gimple_debug_bind_reset_value (stmt);
2941 VEC_safe_push (gimple, heap, update, stmt);
2945 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
2948 VEC_free (gimple, heap, update);
2950 gsi = gsi_for_phi_node (phi);
2951 remove_phi_node (&gsi, false);
2954 /* When the result of a CLOSE_PHI is written to a memory location,
2955 return a pointer to that memory reference, otherwise return
2959 close_phi_written_to_memory (gimple close_phi)
2961 imm_use_iterator imm_iter;
2962 tree res, def = gimple_phi_result (close_phi);
2963 use_operand_p use_p;
2966 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2967 if ((stmt = USE_STMT (use_p))
2968 && gimple_code (stmt) == GIMPLE_ASSIGN
2969 && (res = gimple_assign_lhs (stmt))
2970 && (TREE_CODE (res) == ARRAY_REF
2971 || TREE_CODE (res) == MEM_REF
2972 || TREE_CODE (res) == VAR_DECL
2973 || TREE_CODE (res) == PARM_DECL
2974 || TREE_CODE (res) == RESULT_DECL))
2980 /* Rewrite out of SSA the reduction described by the loop phi nodes
2981 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2984 IN: stmt, loop_n, ..., loop_0
2985 OUT: stmt, close_n, ..., close_0
2987 the first element is the reduction statement, and the next elements
2988 are the loop and close phi nodes of each of the outer loops. */
2991 translate_scalar_reduction_to_array (scop_p scop,
2992 VEC (gimple, heap) *in,
2993 VEC (gimple, heap) *out)
2996 unsigned int i = VEC_length (gimple, out) - 1;
2997 tree red = close_phi_written_to_memory (VEC_index (gimple, out, i));
2999 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
3001 gimple close_phi = VEC_index (gimple, out, i);
3005 gimple stmt = loop_phi;
3006 basic_block bb = split_reduction_stmt (scop, stmt);
3007 poly_bb_p pbb = pbb_from_bb (bb);
3008 PBB_IS_REDUCTION (pbb) = true;
3009 gcc_assert (close_phi == loop_phi);
3012 red = create_zero_dim_array
3013 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
3015 translate_scalar_reduction_to_array_for_stmt
3016 (scop, red, stmt, VEC_index (gimple, in, 1));
3020 if (i == VEC_length (gimple, in) - 1)
3022 insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi),
3023 unshare_expr (red), close_phi);
3024 insert_out_of_ssa_copy_on_edge
3025 (scop, edge_initial_value_for_loop_phi (loop_phi),
3026 unshare_expr (red), initial_value_for_loop_phi (loop_phi));
3029 remove_phi (loop_phi);
3030 remove_phi (close_phi);
3034 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3035 true when something has been changed. */
3038 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
3042 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
3043 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
3045 detect_commutative_reduction (scop, close_phi, &in, &out);
3046 res = VEC_length (gimple, in) > 0;
3048 translate_scalar_reduction_to_array (scop, in, out);
3050 VEC_free (gimple, heap, in);
3051 VEC_free (gimple, heap, out);
3055 /* Rewrites all the commutative reductions from LOOP out of SSA.
3056 Returns true when something has been changed. */
3059 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop,
3062 gimple_stmt_iterator gsi;
3063 edge exit = single_exit (loop);
3065 bool changed = false;
3070 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3071 if ((res = gimple_phi_result (gsi_stmt (gsi)))
3072 && is_gimple_reg (res)
3073 && !scev_analyzable_p (res, SCOP_REGION (scop)))
3074 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
3075 (scop, gsi_stmt (gsi));
3080 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3083 rewrite_commutative_reductions_out_of_ssa (scop_p scop)
3087 bool changed = false;
3088 sese region = SCOP_REGION (scop);
3090 FOR_EACH_LOOP (li, loop, 0)
3091 if (loop_in_sese_p (loop, region))
3092 changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop);
3097 gsi_commit_edge_inserts ();
3098 update_ssa (TODO_update_ssa);
3099 #ifdef ENABLE_CHECKING
3100 verify_loop_closed_ssa (true);
3105 /* Java does not initialize long_long_integer_type_node. */
3106 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
3108 /* Can all ivs be represented by a signed integer?
3109 As CLooG might generate negative values in its expressions, signed loop ivs
3110 are required in the backend. */
3113 scop_ivs_can_be_represented (scop_p scop)
3117 gimple_stmt_iterator psi;
3119 FOR_EACH_LOOP (li, loop, 0)
3121 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3124 for (psi = gsi_start_phis (loop->header);
3125 !gsi_end_p (psi); gsi_next (&psi))
3127 gimple phi = gsi_stmt (psi);
3128 tree res = PHI_RESULT (phi);
3129 tree type = TREE_TYPE (res);
3131 if (TYPE_UNSIGNED (type)
3132 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
3142 /* Builds the polyhedral representation for a SESE region. */
3145 build_poly_scop (scop_p scop)
3147 sese region = SCOP_REGION (scop);
3148 graphite_dim_t max_dim;
3150 build_scop_bbs (scop);
3152 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3153 Once CLooG is fixed, remove this guard. Anyways, it makes no
3154 sense to optimize a scop containing only PBBs that do not belong
3156 if (nb_pbbs_in_loops (scop) == 0)
3159 if (!scop_ivs_can_be_represented (scop))
3162 build_sese_loop_nests (region);
3163 build_sese_conditions (region);
3164 find_scop_parameters (scop);
3166 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3167 if (scop_nb_params (scop) > max_dim)
3170 build_scop_iteration_domain (scop);
3171 build_scop_context (scop);
3172 add_conditions_to_constraints (scop);
3174 /* Rewrite out of SSA only after having translated the
3175 representation to the polyhedral representation to avoid scev
3176 analysis failures. That means that these functions will insert
3177 new data references that they create in the right place. */
3178 if (flag_associative_math)
3179 rewrite_commutative_reductions_out_of_ssa (scop);
3180 rewrite_reductions_out_of_ssa (scop);
3181 rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
3183 build_scop_drs (scop);
3185 build_scop_scattering (scop);
3187 /* This SCoP has been translated to the polyhedral
3189 POLY_SCOP_P (scop) = true;