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"
31 #include "tree-dump.h"
34 #include "tree-chrec.h"
35 #include "tree-data-ref.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-pass.h"
39 #include "value-prof.h"
40 #include "pointer-set.h"
46 #include "graphite-ppl.h"
48 #include "graphite-poly.h"
49 #include "graphite-scop-detection.h"
50 #include "graphite-sese-to-poly.h"
52 /* Returns the index of the PHI argument defined in the outermost
56 phi_arg_in_outermost_loop (gimple phi)
58 loop_p loop = gimple_bb (phi)->loop_father;
61 for (i = 0; i < gimple_phi_num_args (phi); i++)
62 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
64 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
71 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
72 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
75 remove_simple_copy_phi (gimple_stmt_iterator *psi)
77 gimple phi = gsi_stmt (*psi);
78 tree res = gimple_phi_result (phi);
79 size_t entry = phi_arg_in_outermost_loop (phi);
80 tree init = gimple_phi_arg_def (phi, entry);
81 gimple stmt = gimple_build_assign (res, init);
82 edge e = gimple_phi_arg_edge (phi, entry);
84 remove_phi_node (psi, false);
85 gsi_insert_on_edge_immediate (e, stmt);
86 SSA_NAME_DEF_STMT (res) = stmt;
89 /* Removes an invariant phi node at position PSI by inserting on the
90 loop ENTRY edge the assignment RES = INIT. */
93 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
95 gimple phi = gsi_stmt (*psi);
96 loop_p loop = loop_containing_stmt (phi);
97 tree res = gimple_phi_result (phi);
98 tree scev = scalar_evolution_in_region (region, loop, res);
99 size_t entry = phi_arg_in_outermost_loop (phi);
100 edge e = gimple_phi_arg_edge (phi, entry);
104 gimple_stmt_iterator gsi;
106 if (tree_contains_chrecs (scev, NULL))
107 scev = gimple_phi_arg_def (phi, entry);
109 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
110 stmt = gimple_build_assign (res, var);
111 remove_phi_node (psi, false);
114 stmts = gimple_seq_alloc ();
116 gsi = gsi_last (stmts);
117 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
118 gsi_insert_seq_on_edge (e, stmts);
119 gsi_commit_edge_inserts ();
120 SSA_NAME_DEF_STMT (res) = stmt;
123 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
126 simple_copy_phi_p (gimple phi)
130 if (gimple_phi_num_args (phi) != 2)
133 res = gimple_phi_result (phi);
134 return (res == gimple_phi_arg_def (phi, 0)
135 || res == gimple_phi_arg_def (phi, 1));
138 /* Returns true when the phi node at position PSI is a reduction phi
139 node in REGION. Otherwise moves the pointer PSI to the next phi to
143 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
146 gimple phi = gsi_stmt (*psi);
147 tree res = gimple_phi_result (phi);
149 loop = loop_containing_stmt (phi);
151 if (simple_copy_phi_p (phi))
153 /* PRE introduces phi nodes like these, for an example,
154 see id-5.f in the fortran graphite testsuite:
156 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
158 remove_simple_copy_phi (psi);
162 if (scev_analyzable_p (res, region))
164 tree scev = scalar_evolution_in_region (region, loop, res);
166 if (evolution_function_is_invariant_p (scev, loop->num))
167 remove_invariant_phi (region, psi);
174 /* All the other cases are considered reductions. */
178 /* Store the GRAPHITE representation of BB. */
181 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
183 struct gimple_bb *gbb;
185 gbb = XNEW (struct gimple_bb);
188 GBB_DATA_REFS (gbb) = drs;
189 GBB_CONDITIONS (gbb) = NULL;
190 GBB_CONDITION_CASES (gbb) = NULL;
196 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
199 struct data_reference *dr;
201 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
204 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
207 free (bap->alias_set);
216 free_gimple_bb (struct gimple_bb *gbb)
218 free_data_refs_aux (GBB_DATA_REFS (gbb));
219 free_data_refs (GBB_DATA_REFS (gbb));
221 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
222 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
223 GBB_BB (gbb)->aux = 0;
227 /* Deletes all gimple bbs in SCOP. */
230 remove_gbbs_in_scop (scop_p scop)
235 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
236 free_gimple_bb (PBB_BLACK_BOX (pbb));
239 /* Deletes all scops in SCOPS. */
242 free_scops (VEC (scop_p, heap) *scops)
247 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
249 remove_gbbs_in_scop (scop);
250 free_sese (SCOP_REGION (scop));
254 VEC_free (scop_p, heap, scops);
257 /* Generates a polyhedral black box only if the bb contains interesting
261 try_generate_gimple_bb (scop_p scop, basic_block bb)
263 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
264 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
265 gimple_stmt_iterator gsi;
267 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
269 gimple stmt = gsi_stmt (gsi);
270 if (!is_gimple_debug (stmt))
271 graphite_find_data_references_in_stmt (nest, stmt, &drs);
274 return new_gimple_bb (bb, drs);
277 /* Returns true if all predecessors of BB, that are not dominated by BB, are
278 marked in MAP. The predecessors dominated by BB are loop latches and will
279 be handled after BB. */
282 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
287 FOR_EACH_EDGE (e, ei, bb->preds)
288 if (!TEST_BIT (map, e->src->index)
289 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
295 /* Compare the depth of two basic_block's P1 and P2. */
298 compare_bb_depths (const void *p1, const void *p2)
300 const_basic_block const bb1 = *(const_basic_block const*)p1;
301 const_basic_block const bb2 = *(const_basic_block const*)p2;
302 int d1 = loop_depth (bb1->loop_father);
303 int d2 = loop_depth (bb2->loop_father);
314 /* Sort the basic blocks from DOM such that the first are the ones at
315 a deepest loop level. */
318 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
320 VEC_qsort (basic_block, dom, compare_bb_depths);
323 /* Recursive helper function for build_scops_bbs. */
326 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
328 sese region = SCOP_REGION (scop);
329 VEC (basic_block, heap) *dom;
332 if (TEST_BIT (visited, bb->index)
333 || !bb_in_sese_p (bb, region))
336 pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb));
337 VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
338 SET_BIT (visited, bb->index);
340 dom = get_dominated_by (CDI_DOMINATORS, bb);
345 graphite_sort_dominated_info (dom);
347 while (!VEC_empty (basic_block, dom))
352 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
353 if (all_non_dominated_preds_marked_p (dom_bb, visited))
355 build_scop_bbs_1 (scop, visited, dom_bb);
356 VEC_unordered_remove (basic_block, dom, i);
361 VEC_free (basic_block, heap, dom);
364 /* Gather the basic blocks belonging to the SCOP. */
367 build_scop_bbs (scop_p scop)
369 sbitmap visited = sbitmap_alloc (last_basic_block);
370 sese region = SCOP_REGION (scop);
372 sbitmap_zero (visited);
373 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
374 sbitmap_free (visited);
377 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
378 We generate SCATTERING_DIMENSIONS scattering dimensions.
380 CLooG 0.15.0 and previous versions require, that all
381 scattering functions of one CloogProgram have the same number of
382 scattering dimensions, therefore we allow to specify it. This
383 should be removed in future versions of CLooG.
385 The scattering polyhedron consists of these dimensions: scattering,
386 loop_iterators, parameters.
390 | scattering_dimensions = 5
391 | used_scattering_dimensions = 3
399 | Scattering polyhedron:
401 | scattering: {s1, s2, s3, s4, s5}
402 | loop_iterators: {i}
403 | parameters: {p1, p2}
405 | s1 s2 s3 s4 s5 i p1 p2 1
406 | 1 0 0 0 0 0 0 0 -4 = 0
407 | 0 1 0 0 0 -1 0 0 0 = 0
408 | 0 0 1 0 0 0 0 0 -5 = 0 */
411 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
412 poly_bb_p pbb, int scattering_dimensions)
415 scop_p scop = PBB_SCOP (pbb);
416 int nb_iterators = pbb_dim_iter_domain (pbb);
417 int used_scattering_dimensions = nb_iterators * 2 + 1;
418 int nb_params = scop_nb_params (scop);
420 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
423 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
426 ppl_new_Coefficient (&c);
427 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
428 ppl_new_C_Polyhedron_from_space_dimension
429 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
431 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
433 for (i = 0; i < scattering_dimensions; i++)
435 ppl_Constraint_t cstr;
436 ppl_Linear_Expression_t expr;
438 ppl_new_Linear_Expression_with_dimension (&expr, dim);
440 ppl_assign_Coefficient_from_mpz_t (c, v);
441 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
443 /* Textual order inside this loop. */
446 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
447 ppl_Coefficient_to_mpz_t (c, v);
449 ppl_assign_Coefficient_from_mpz_t (c, v);
450 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
453 /* Iterations of this loop. */
454 else /* if ((i % 2) == 1) */
456 int loop = (i - 1) / 2;
459 ppl_assign_Coefficient_from_mpz_t (c, v);
460 ppl_Linear_Expression_add_to_coefficient
461 (expr, scattering_dimensions + loop, c);
464 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
465 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
466 ppl_delete_Linear_Expression (expr);
467 ppl_delete_Constraint (cstr);
471 ppl_delete_Coefficient (c);
473 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
476 /* Build for BB the static schedule.
478 The static schedule is a Dewey numbering of the abstract syntax
479 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
481 The following example informally defines the static schedule:
500 Static schedules for A to F:
513 build_scop_scattering (scop_p scop)
517 gimple_bb_p previous_gbb = NULL;
518 ppl_Linear_Expression_t static_schedule;
523 ppl_new_Coefficient (&c);
524 ppl_new_Linear_Expression (&static_schedule);
526 /* We have to start schedules at 0 on the first component and
527 because we cannot compare_prefix_loops against a previous loop,
528 prefix will be equal to zero, and that index will be
529 incremented before copying. */
531 ppl_assign_Coefficient_from_mpz_t (c, v);
532 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
534 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
536 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
537 ppl_Linear_Expression_t common;
539 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
542 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
547 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
548 ppl_assign_Linear_Expression_from_Linear_Expression (common,
552 ppl_assign_Coefficient_from_mpz_t (c, v);
553 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
554 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
557 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
559 ppl_delete_Linear_Expression (common);
563 ppl_delete_Coefficient (c);
564 ppl_delete_Linear_Expression (static_schedule);
567 /* Add the value K to the dimension D of the linear expression EXPR. */
570 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
574 ppl_Coefficient_t coef;
576 ppl_new_Coefficient (&coef);
577 ppl_Linear_Expression_coefficient (expr, d, coef);
579 ppl_Coefficient_to_mpz_t (coef, val);
581 mpz_add (val, val, k);
583 ppl_assign_Coefficient_from_mpz_t (coef, val);
584 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
586 ppl_delete_Coefficient (coef);
589 /* In the context of scop S, scan E, the right hand side of a scalar
590 evolution function in loop VAR, and translate it to a linear
594 scan_tree_for_params_right_scev (sese s, tree e, int var,
595 ppl_Linear_Expression_t expr)
599 loop_p loop = get_loop (var);
600 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
603 /* Scalar evolutions should happen in the sese region. */
604 gcc_assert (sese_loop_depth (s, loop) > 0);
606 /* We can not deal with parametric strides like:
612 gcc_assert (TREE_CODE (e) == INTEGER_CST);
615 tree_int_to_gmp (e, val);
616 add_value_to_dim (l, expr, val);
621 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
622 linear expression EXPR. K is the multiplier of the constant. */
625 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
628 ppl_Coefficient_t coef;
629 tree type = TREE_TYPE (cst);
633 /* Necessary to not get "-1 = 2^n - 1". */
634 mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
635 TYPE_PRECISION (type)), false);
637 mpz_mul (val, val, k);
638 ppl_new_Coefficient (&coef);
639 ppl_assign_Coefficient_from_mpz_t (coef, val);
640 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
642 ppl_delete_Coefficient (coef);
645 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
646 Otherwise returns -1. */
649 parameter_index_in_region_1 (tree name, sese region)
654 gcc_assert (TREE_CODE (name) == SSA_NAME);
656 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
663 /* When the parameter NAME is in REGION, returns its index in
664 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
665 and returns the index of NAME. */
668 parameter_index_in_region (tree name, sese region)
672 gcc_assert (TREE_CODE (name) == SSA_NAME);
674 i = parameter_index_in_region_1 (name, region);
678 gcc_assert (SESE_ADD_PARAMS (region));
680 i = VEC_length (tree, SESE_PARAMS (region));
681 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
685 /* In the context of sese S, scan the expression E and translate it to
686 a linear expression C. When parsing a symbolic multiplication, K
687 represents the constant multiplier of an expression containing
691 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
694 if (e == chrec_dont_know)
697 switch (TREE_CODE (e))
699 case POLYNOMIAL_CHREC:
700 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
701 CHREC_VARIABLE (e), c);
702 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
706 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
711 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
713 tree_int_to_gmp (TREE_OPERAND (e, 1), val);
714 mpz_mul (val, val, k);
715 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
719 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
726 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
728 tree_int_to_gmp (TREE_OPERAND (e, 0), val);
729 mpz_mul (val, val, k);
730 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
734 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
739 case POINTER_PLUS_EXPR:
740 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
741 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
746 ppl_Linear_Expression_t tmp_expr = NULL;
750 ppl_dimension_type dim;
751 ppl_Linear_Expression_space_dimension (c, &dim);
752 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
755 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
756 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
760 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
762 ppl_delete_Linear_Expression (tmp_expr);
770 ppl_Linear_Expression_t tmp_expr = NULL;
774 ppl_dimension_type dim;
775 ppl_Linear_Expression_space_dimension (c, &dim);
776 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
779 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
783 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
785 ppl_delete_Linear_Expression (tmp_expr);
793 ppl_Linear_Expression_t tmp_expr = NULL;
797 ppl_dimension_type dim;
798 ppl_Linear_Expression_space_dimension (c, &dim);
799 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
802 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
806 ppl_Coefficient_t coef;
809 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
811 ppl_delete_Linear_Expression (tmp_expr);
812 mpz_init (minus_one);
813 mpz_set_si (minus_one, -1);
814 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
815 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
816 mpz_clear (minus_one);
817 ppl_delete_Coefficient (coef);
825 ppl_dimension_type p = parameter_index_in_region (e, s);
829 ppl_dimension_type dim;
830 ppl_Linear_Expression_space_dimension (c, &dim);
831 p += dim - sese_nb_params (s);
832 add_value_to_dim (p, c, k);
839 scan_tree_for_params_int (e, c, k);
843 case NON_LVALUE_EXPR:
844 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
853 /* Find parameters with respect to REGION in BB. We are looking in memory
854 access functions, conditions and loop bounds. */
857 find_params_in_bb (sese region, gimple_bb_p gbb)
863 loop_p loop = GBB_BB (gbb)->loop_father;
869 /* Find parameters in the access functions of data references. */
870 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
871 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
872 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
874 /* Find parameters in conditional statements. */
875 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
877 tree lhs = scalar_evolution_in_region (region, loop,
878 gimple_cond_lhs (stmt));
879 tree rhs = scalar_evolution_in_region (region, loop,
880 gimple_cond_rhs (stmt));
882 scan_tree_for_params (region, lhs, NULL, one);
883 scan_tree_for_params (region, rhs, NULL, one);
889 /* Record the parameters used in the SCOP. A variable is a parameter
890 in a scop if it does not vary during the execution of that scop. */
893 find_scop_parameters (scop_p scop)
897 sese region = SCOP_REGION (scop);
904 /* Find the parameters used in the loop bounds. */
905 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
907 tree nb_iters = number_of_latch_executions (loop);
909 if (!chrec_contains_symbols (nb_iters))
912 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
913 scan_tree_for_params (region, nb_iters, NULL, one);
918 /* Find the parameters used in data accesses. */
919 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
920 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
922 scop_set_nb_params (scop, sese_nb_params (region));
923 SESE_ADD_PARAMS (region) = false;
925 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
926 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
929 /* Insert in the SCOP context constraints from the estimation of the
930 number of iterations. UB_EXPR is a linear expression describing
931 the number of iterations in a loop. This expression is bounded by
932 the estimation NIT. */
935 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
936 ppl_dimension_type dim,
937 ppl_Linear_Expression_t ub_expr)
940 ppl_Linear_Expression_t nb_iters_le;
941 ppl_Polyhedron_t pol;
942 ppl_Coefficient_t coef;
945 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
946 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
949 /* Construct the negated number of last iteration in VAL. */
951 mpz_set_double_int (val, nit, false);
952 mpz_sub_ui (val, val, 1);
955 /* NB_ITERS_LE holds the number of last iteration in
956 parametrical form. Subtract estimated number of last
957 iteration and assert that result is not positive. */
958 ppl_new_Coefficient_from_mpz_t (&coef, val);
959 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
960 ppl_delete_Coefficient (coef);
961 ppl_new_Constraint (&ub, nb_iters_le,
962 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
963 ppl_Polyhedron_add_constraint (pol, ub);
965 /* Remove all but last GDIM dimensions from POL to obtain
966 only the constraints on the parameters. */
968 graphite_dim_t gdim = scop_nb_params (scop);
969 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
972 for (i = 0; i < dim - gdim; i++)
975 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
979 /* Add the constraints on the parameters to the SCoP context. */
981 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
983 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
984 (&constraints_ps, pol);
985 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
986 (SCOP_CONTEXT (scop), constraints_ps);
987 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
990 ppl_delete_Polyhedron (pol);
991 ppl_delete_Linear_Expression (nb_iters_le);
992 ppl_delete_Constraint (ub);
996 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
997 the constraints for the surrounding loops. */
1000 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1001 ppl_Polyhedron_t outer_ph, int nb,
1002 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1005 ppl_Polyhedron_t ph;
1006 tree nb_iters = number_of_latch_executions (loop);
1007 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1008 sese region = SCOP_REGION (scop);
1011 ppl_const_Constraint_System_t pcs;
1012 ppl_dimension_type *map
1013 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1015 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1016 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1017 ppl_Polyhedron_add_constraints (ph, pcs);
1019 for (i = 0; i < (int) nb; i++)
1021 for (i = (int) nb; i < (int) dim - 1; i++)
1025 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1031 ppl_Constraint_t lb;
1032 ppl_Linear_Expression_t lb_expr;
1034 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1035 ppl_set_coef (lb_expr, nb, 1);
1036 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1037 ppl_delete_Linear_Expression (lb_expr);
1038 ppl_Polyhedron_add_constraint (ph, lb);
1039 ppl_delete_Constraint (lb);
1042 if (TREE_CODE (nb_iters) == INTEGER_CST)
1044 ppl_Constraint_t ub;
1045 ppl_Linear_Expression_t ub_expr;
1047 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1049 /* loop_i <= cst_nb_iters */
1050 ppl_set_coef (ub_expr, nb, -1);
1051 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1052 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1053 ppl_Polyhedron_add_constraint (ph, ub);
1054 ppl_delete_Linear_Expression (ub_expr);
1055 ppl_delete_Constraint (ub);
1057 else if (!chrec_contains_undetermined (nb_iters))
1060 ppl_Constraint_t ub;
1061 ppl_Linear_Expression_t ub_expr;
1065 mpz_set_si (one, 1);
1066 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1067 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1068 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1071 if (estimated_loop_iterations (loop, true, &nit))
1072 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1074 /* loop_i <= expr_nb_iters */
1075 ppl_set_coef (ub_expr, nb, -1);
1076 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1077 ppl_Polyhedron_add_constraint (ph, ub);
1078 ppl_delete_Linear_Expression (ub_expr);
1079 ppl_delete_Constraint (ub);
1084 if (loop->inner && loop_in_sese_p (loop->inner, region))
1085 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1089 && loop_in_sese_p (loop->next, region))
1090 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1092 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1093 (&domains[loop->num], ph);
1095 ppl_delete_Polyhedron (ph);
1098 /* Returns a linear expression for tree T evaluated in PBB. */
1100 static ppl_Linear_Expression_t
1101 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1104 ppl_Linear_Expression_t res;
1105 ppl_dimension_type dim;
1106 sese region = SCOP_REGION (PBB_SCOP (pbb));
1107 loop_p loop = pbb_loop (pbb);
1109 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1110 ppl_new_Linear_Expression_with_dimension (&res, dim);
1112 t = scalar_evolution_in_region (region, loop, t);
1113 gcc_assert (!automatically_generated_chrec_p (t));
1116 mpz_set_si (one, 1);
1117 scan_tree_for_params (region, t, res, one);
1123 /* Returns the ppl constraint type from the gimple tree code CODE. */
1125 static enum ppl_enum_Constraint_Type
1126 ppl_constraint_type_from_tree_code (enum tree_code code)
1130 /* We do not support LT and GT to be able to work with C_Polyhedron.
1131 As we work on integer polyhedron "a < b" can be expressed by
1138 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1141 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1144 return PPL_CONSTRAINT_TYPE_EQUAL;
1151 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1152 CODE is used as the comparison operator. This allows us to invert the
1153 condition or to handle inequalities. */
1156 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1157 poly_bb_p pbb, enum tree_code code)
1160 ppl_Coefficient_t c;
1161 ppl_Linear_Expression_t left, right;
1162 ppl_Constraint_t cstr;
1163 enum ppl_enum_Constraint_Type type;
1165 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1166 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1168 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1169 the left or the right side of the expression. */
1170 if (code == LT_EXPR)
1174 ppl_new_Coefficient (&c);
1175 ppl_assign_Coefficient_from_mpz_t (c, v);
1176 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1177 ppl_delete_Coefficient (c);
1182 else if (code == GT_EXPR)
1186 ppl_new_Coefficient (&c);
1187 ppl_assign_Coefficient_from_mpz_t (c, v);
1188 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1189 ppl_delete_Coefficient (c);
1195 type = ppl_constraint_type_from_tree_code (code);
1197 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1199 ppl_new_Constraint (&cstr, left, type);
1200 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1202 ppl_delete_Constraint (cstr);
1203 ppl_delete_Linear_Expression (left);
1204 ppl_delete_Linear_Expression (right);
1207 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1208 operator. This allows us to invert the condition or to handle
1212 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1214 if (code == NE_EXPR)
1216 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1217 ppl_Pointset_Powerset_C_Polyhedron_t right;
1218 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1220 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1221 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1222 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1223 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1226 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1229 /* Add conditions to the domain of PBB. */
1232 add_conditions_to_domain (poly_bb_p pbb)
1236 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1238 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1241 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1242 switch (gimple_code (stmt))
1246 enum tree_code code = gimple_cond_code (stmt);
1248 /* The conditions for ELSE-branches are inverted. */
1249 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1250 code = invert_tree_comparison (code, false);
1252 add_condition_to_pbb (pbb, stmt, code);
1257 /* Switch statements are not supported right now - fall throught. */
1265 /* Traverses all the GBBs of the SCOP and add their constraints to the
1266 iteration domains. */
1269 add_conditions_to_constraints (scop_p scop)
1274 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1275 add_conditions_to_domain (pbb);
1278 /* Structure used to pass data to dom_walk. */
1282 VEC (gimple, heap) **conditions, **cases;
1286 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1287 edge between BB and its predecessor is not a loop exit edge, and
1288 the last statement of the single predecessor is a COND_EXPR. */
1291 single_pred_cond_non_loop_exit (basic_block bb)
1293 if (single_pred_p (bb))
1295 edge e = single_pred_edge (bb);
1296 basic_block pred = e->src;
1299 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1302 stmt = last_stmt (pred);
1304 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1311 /* Call-back for dom_walk executed before visiting the dominated
1315 build_sese_conditions_before (struct dom_walk_data *dw_data,
1318 struct bsc *data = (struct bsc *) dw_data->global_data;
1319 VEC (gimple, heap) **conditions = data->conditions;
1320 VEC (gimple, heap) **cases = data->cases;
1324 if (!bb_in_sese_p (bb, data->region))
1327 stmt = single_pred_cond_non_loop_exit (bb);
1331 edge e = single_pred_edge (bb);
1333 VEC_safe_push (gimple, heap, *conditions, stmt);
1335 if (e->flags & EDGE_TRUE_VALUE)
1336 VEC_safe_push (gimple, heap, *cases, stmt);
1338 VEC_safe_push (gimple, heap, *cases, NULL);
1341 gbb = gbb_from_bb (bb);
1345 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1346 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1350 /* Call-back for dom_walk executed after visiting the dominated
1354 build_sese_conditions_after (struct dom_walk_data *dw_data,
1357 struct bsc *data = (struct bsc *) dw_data->global_data;
1358 VEC (gimple, heap) **conditions = data->conditions;
1359 VEC (gimple, heap) **cases = data->cases;
1361 if (!bb_in_sese_p (bb, data->region))
1364 if (single_pred_cond_non_loop_exit (bb))
1366 VEC_pop (gimple, *conditions);
1367 VEC_pop (gimple, *cases);
1371 /* Record all conditions in REGION. */
1374 build_sese_conditions (sese region)
1376 struct dom_walk_data walk_data;
1377 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1378 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1381 data.conditions = &conditions;
1382 data.cases = &cases;
1383 data.region = region;
1385 walk_data.dom_direction = CDI_DOMINATORS;
1386 walk_data.initialize_block_local_data = NULL;
1387 walk_data.before_dom_children = build_sese_conditions_before;
1388 walk_data.after_dom_children = build_sese_conditions_after;
1389 walk_data.global_data = &data;
1390 walk_data.block_local_data_size = 0;
1392 init_walk_dominator_tree (&walk_data);
1393 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1394 fini_walk_dominator_tree (&walk_data);
1396 VEC_free (gimple, heap, conditions);
1397 VEC_free (gimple, heap, cases);
1400 /* Add constraints on the possible values of parameter P from the type
1404 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1406 ppl_Constraint_t cstr;
1407 ppl_Linear_Expression_t le;
1408 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1409 tree type = TREE_TYPE (parameter);
1410 tree lb = NULL_TREE;
1411 tree ub = NULL_TREE;
1413 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1414 lb = lower_bound_in_type (type, type);
1416 lb = TYPE_MIN_VALUE (type);
1418 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1419 ub = upper_bound_in_type (type, type);
1421 ub = TYPE_MAX_VALUE (type);
1425 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1426 ppl_set_coef (le, p, -1);
1427 ppl_set_inhomogeneous_tree (le, lb);
1428 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1429 ppl_Polyhedron_add_constraint (context, cstr);
1430 ppl_delete_Linear_Expression (le);
1431 ppl_delete_Constraint (cstr);
1436 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1437 ppl_set_coef (le, p, -1);
1438 ppl_set_inhomogeneous_tree (le, ub);
1439 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1440 ppl_Polyhedron_add_constraint (context, cstr);
1441 ppl_delete_Linear_Expression (le);
1442 ppl_delete_Constraint (cstr);
1446 /* Build the context of the SCOP. The context usually contains extra
1447 constraints that are added to the iteration domains that constrain
1451 build_scop_context (scop_p scop)
1453 ppl_Polyhedron_t context;
1454 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1455 graphite_dim_t p, n = scop_nb_params (scop);
1457 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1459 for (p = 0; p < n; p++)
1460 add_param_constraints (scop, context, p);
1462 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1464 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1465 (SCOP_CONTEXT (scop), ps);
1467 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1468 ppl_delete_Polyhedron (context);
1471 /* Build the iteration domains: the loops belonging to the current
1472 SCOP, and that vary for the execution of the current basic block.
1473 Returns false if there is no loop in SCOP. */
1476 build_scop_iteration_domain (scop_p scop)
1479 sese region = SCOP_REGION (scop);
1481 ppl_Polyhedron_t ph;
1483 int nb_loops = number_of_loops ();
1484 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1485 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1487 for (i = 0; i < nb_loops; i++)
1490 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1492 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1493 if (!loop_in_sese_p (loop_outer (loop), region))
1494 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1496 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1497 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1498 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1499 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1500 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1502 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1503 (&PBB_DOMAIN (pbb), ph);
1505 for (i = 0; i < nb_loops; i++)
1507 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1509 ppl_delete_Polyhedron (ph);
1513 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1514 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1515 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1519 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1520 ppl_dimension_type accessp_nb_dims,
1521 ppl_dimension_type dom_nb_dims)
1523 ppl_Linear_Expression_t alias;
1524 ppl_Constraint_t cstr;
1525 int alias_set_num = 0;
1526 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1528 if (bap && bap->alias_set)
1529 alias_set_num = *(bap->alias_set);
1531 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1533 ppl_set_coef (alias, dom_nb_dims, 1);
1534 ppl_set_inhomogeneous (alias, -alias_set_num);
1535 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1536 ppl_Polyhedron_add_constraint (accesses, cstr);
1538 ppl_delete_Linear_Expression (alias);
1539 ppl_delete_Constraint (cstr);
1542 /* Add to ACCESSES polyhedron equalities defining the access functions
1543 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1544 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1545 PBB is the poly_bb_p that contains the data reference DR. */
1548 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1549 ppl_dimension_type accessp_nb_dims,
1550 ppl_dimension_type dom_nb_dims,
1553 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1555 scop_p scop = PBB_SCOP (pbb);
1556 sese region = SCOP_REGION (scop);
1560 for (i = 0; i < nb_subscripts; i++)
1562 ppl_Linear_Expression_t fn, access;
1563 ppl_Constraint_t cstr;
1564 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1565 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1567 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1568 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1571 scan_tree_for_params (region, afn, fn, v);
1572 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1574 ppl_set_coef (access, subscript, -1);
1575 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1576 ppl_Polyhedron_add_constraint (accesses, cstr);
1578 ppl_delete_Linear_Expression (fn);
1579 ppl_delete_Linear_Expression (access);
1580 ppl_delete_Constraint (cstr);
1586 /* Add constrains representing the size of the accessed data to the
1587 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1588 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1592 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1593 ppl_dimension_type accessp_nb_dims,
1594 ppl_dimension_type dom_nb_dims)
1596 tree ref = DR_REF (dr);
1597 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1599 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1601 ppl_Linear_Expression_t expr;
1602 ppl_Constraint_t cstr;
1603 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1606 if (TREE_CODE (ref) != ARRAY_REF)
1609 low = array_ref_low_bound (ref);
1611 /* subscript - low >= 0 */
1612 if (host_integerp (low, 0))
1616 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1617 ppl_set_coef (expr, subscript, 1);
1619 minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low);
1620 ppl_set_inhomogeneous_tree (expr, minus_low);
1622 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1623 ppl_Polyhedron_add_constraint (accesses, cstr);
1624 ppl_delete_Linear_Expression (expr);
1625 ppl_delete_Constraint (cstr);
1628 high = array_ref_up_bound (ref);
1630 /* high - subscript >= 0 */
1631 if (high && host_integerp (high, 0)
1632 /* 1-element arrays at end of structures may extend over
1633 their declared size. */
1634 && !(array_at_struct_end_p (ref)
1635 && operand_equal_p (low, high, 0)))
1637 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1638 ppl_set_coef (expr, subscript, -1);
1640 ppl_set_inhomogeneous_tree (expr, high);
1642 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1643 ppl_Polyhedron_add_constraint (accesses, cstr);
1644 ppl_delete_Linear_Expression (expr);
1645 ppl_delete_Constraint (cstr);
1650 /* Build data accesses for DR in PBB. */
1653 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1655 ppl_Polyhedron_t accesses;
1656 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1657 ppl_dimension_type dom_nb_dims;
1658 ppl_dimension_type accessp_nb_dims;
1659 int dr_base_object_set;
1661 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1663 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1665 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1667 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1668 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1669 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1671 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1673 ppl_delete_Polyhedron (accesses);
1675 gcc_assert (dr->aux);
1676 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1678 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1679 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1680 dr, DR_NUM_DIMENSIONS (dr));
1683 /* Write to FILE the alias graph of data references in DIMACS format. */
1686 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1687 VEC (data_reference_p, heap) *drs)
1689 int num_vertex = VEC_length (data_reference_p, drs);
1691 data_reference_p dr1, dr2;
1694 if (num_vertex == 0)
1697 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1698 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1699 if (dr_may_alias_p (dr1, dr2))
1702 fprintf (file, "$\n");
1705 fprintf (file, "c %s\n", comment);
1707 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1709 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1710 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1711 if (dr_may_alias_p (dr1, dr2))
1712 fprintf (file, "e %d %d\n", i + 1, j + 1);
1717 /* Write to FILE the alias graph of data references in DOT format. */
1720 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1721 VEC (data_reference_p, heap) *drs)
1723 int num_vertex = VEC_length (data_reference_p, drs);
1724 data_reference_p dr1, dr2;
1727 if (num_vertex == 0)
1730 fprintf (file, "$\n");
1733 fprintf (file, "c %s\n", comment);
1735 /* First print all the vertices. */
1736 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1737 fprintf (file, "n%d;\n", i);
1739 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1740 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1741 if (dr_may_alias_p (dr1, dr2))
1742 fprintf (file, "n%d n%d\n", i, j);
1747 /* Write to FILE the alias graph of data references in ECC format. */
1750 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1751 VEC (data_reference_p, heap) *drs)
1753 int num_vertex = VEC_length (data_reference_p, drs);
1754 data_reference_p dr1, dr2;
1757 if (num_vertex == 0)
1760 fprintf (file, "$\n");
1763 fprintf (file, "c %s\n", comment);
1765 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1766 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1767 if (dr_may_alias_p (dr1, dr2))
1768 fprintf (file, "%d %d\n", i, j);
1773 /* Check if DR1 and DR2 are in the same object set. */
1776 dr_same_base_object_p (const struct data_reference *dr1,
1777 const struct data_reference *dr2)
1779 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1782 /* Uses DFS component number as representative of alias-sets. Also tests for
1783 optimality by verifying if every connected component is a clique. Returns
1784 true (1) if the above test is true, and false (0) otherwise. */
1787 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1789 int num_vertices = VEC_length (data_reference_p, drs);
1790 struct graph *g = new_graph (num_vertices);
1791 data_reference_p dr1, dr2;
1793 int num_connected_components;
1794 int v_indx1, v_indx2, num_vertices_in_component;
1797 struct graph_edge *e;
1798 int this_component_is_clique;
1799 int all_components_are_cliques = 1;
1801 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1802 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1803 if (dr_may_alias_p (dr1, dr2))
1809 all_vertices = XNEWVEC (int, num_vertices);
1810 vertices = XNEWVEC (int, num_vertices);
1811 for (i = 0; i < num_vertices; i++)
1812 all_vertices[i] = i;
1814 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1816 for (i = 0; i < g->n_vertices; i++)
1818 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1819 base_alias_pair *bap;
1821 gcc_assert (dr->aux);
1822 bap = (base_alias_pair *)(dr->aux);
1824 bap->alias_set = XNEW (int);
1825 *(bap->alias_set) = g->vertices[i].component + 1;
1828 /* Verify if the DFS numbering results in optimal solution. */
1829 for (i = 0; i < num_connected_components; i++)
1831 num_vertices_in_component = 0;
1832 /* Get all vertices whose DFS component number is the same as i. */
1833 for (j = 0; j < num_vertices; j++)
1834 if (g->vertices[j].component == i)
1835 vertices[num_vertices_in_component++] = j;
1837 /* Now test if the vertices in 'vertices' form a clique, by testing
1838 for edges among each pair. */
1839 this_component_is_clique = 1;
1840 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1842 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1844 /* Check if the two vertices are connected by iterating
1845 through all the edges which have one of these are source. */
1846 e = g->vertices[vertices[v_indx2]].pred;
1849 if (e->src == vertices[v_indx1])
1855 this_component_is_clique = 0;
1859 if (!this_component_is_clique)
1860 all_components_are_cliques = 0;
1864 free (all_vertices);
1867 return all_components_are_cliques;
1870 /* Group each data reference in DRS with its base object set num. */
1873 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1875 int num_vertex = VEC_length (data_reference_p, drs);
1876 struct graph *g = new_graph (num_vertex);
1877 data_reference_p dr1, dr2;
1881 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1882 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1883 if (dr_same_base_object_p (dr1, dr2))
1889 queue = XNEWVEC (int, num_vertex);
1890 for (i = 0; i < num_vertex; i++)
1893 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1895 for (i = 0; i < g->n_vertices; i++)
1897 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1898 base_alias_pair *bap;
1900 gcc_assert (dr->aux);
1901 bap = (base_alias_pair *)(dr->aux);
1903 bap->base_obj_set = g->vertices[i].component + 1;
1910 /* Build the data references for PBB. */
1913 build_pbb_drs (poly_bb_p pbb)
1916 data_reference_p dr;
1917 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1919 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
1920 build_poly_dr (dr, pbb);
1923 /* Dump to file the alias graphs for the data references in DRS. */
1926 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
1929 FILE *file_dimacs, *file_ecc, *file_dot;
1931 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1934 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1935 current_function_name ());
1936 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
1937 fclose (file_dimacs);
1940 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
1943 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1944 current_function_name ());
1945 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
1949 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
1952 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1953 current_function_name ());
1954 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
1959 /* Build data references in SCOP. */
1962 build_scop_drs (scop_p scop)
1966 data_reference_p dr;
1967 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1969 /* Remove all the PBBs that do not have data references: these basic
1970 blocks are not handled in the polyhedral representation. */
1971 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1972 if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb))))
1974 free_gimple_bb (PBB_BLACK_BOX (pbb));
1975 VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i);
1979 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1980 for (j = 0; VEC_iterate (data_reference_p,
1981 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
1982 VEC_safe_push (data_reference_p, heap, drs, dr);
1984 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
1985 dr->aux = XNEW (base_alias_pair);
1987 if (!build_alias_set_optimal_p (drs))
1989 /* TODO: Add support when building alias set is not optimal. */
1993 build_base_obj_set_for_drs (drs);
1995 /* When debugging, enable the following code. This cannot be used
1996 in production compilers. */
1998 dump_alias_graphs (drs);
2000 VEC_free (data_reference_p, heap, drs);
2002 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2003 build_pbb_drs (pbb);
2006 /* Return a gsi at the position of the phi node STMT. */
2008 static gimple_stmt_iterator
2009 gsi_for_phi_node (gimple stmt)
2011 gimple_stmt_iterator psi;
2012 basic_block bb = gimple_bb (stmt);
2014 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2015 if (stmt == gsi_stmt (psi))
2022 /* Analyze all the data references of STMTS and add them to the
2023 GBB_DATA_REFS vector of BB. */
2026 analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
2033 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2036 nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
2037 gbb = gbb_from_bb (bb);
2039 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
2040 if (!is_gimple_debug (stmt))
2041 graphite_find_data_references_in_stmt (nest, stmt,
2042 &GBB_DATA_REFS (gbb));
2045 /* Insert STMT at the end of the STMTS sequence and then insert the
2046 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2050 insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts,
2051 gimple_stmt_iterator insert_gsi)
2053 gimple_stmt_iterator gsi;
2054 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2057 stmts = gimple_seq_alloc ();
2059 gsi = gsi_last (stmts);
2060 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2061 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2062 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2064 gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2065 analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
2066 VEC_free (gimple, heap, x);
2069 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2072 insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt)
2075 gimple_stmt_iterator si;
2076 gimple_stmt_iterator gsi;
2077 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2078 gimple stmt = gimple_build_assign (res, var);
2079 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2082 stmts = gimple_seq_alloc ();
2083 si = gsi_last (stmts);
2084 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2085 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2086 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2088 if (gimple_code (after_stmt) == GIMPLE_PHI)
2090 gsi = gsi_after_labels (gimple_bb (after_stmt));
2091 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2095 gsi = gsi_for_stmt (after_stmt);
2096 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2099 analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
2100 VEC_free (gimple, heap, x);
2103 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2106 new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
2108 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2109 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
2110 gimple_bb_p gbb1 = new_gimple_bb (bb, drs);
2111 poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
2112 int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
2114 /* The INDEX of PBB in SCOP_BBS. */
2115 for (index = 0; index < n; index++)
2116 if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
2119 GBB_PBB (gbb1) = pbb1;
2120 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2121 (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
2122 GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
2123 GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
2124 VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
2127 /* Insert on edge E the assignment "RES := EXPR". */
2130 insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
2132 gimple_stmt_iterator gsi;
2134 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2135 gimple stmt = gimple_build_assign (res, var);
2137 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2140 stmts = gimple_seq_alloc ();
2142 gsi = gsi_last (stmts);
2143 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2144 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2145 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2147 gsi_insert_seq_on_edge (e, stmts);
2148 gsi_commit_edge_inserts ();
2149 bb = gimple_bb (stmt);
2151 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2154 if (!gbb_from_bb (bb))
2155 new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
2157 analyze_drs_in_stmts (scop, bb, x);
2158 VEC_free (gimple, heap, x);
2161 /* Creates a zero dimension array of the same type as VAR. */
2164 create_zero_dim_array (tree var, const char *base_name)
2166 tree index_type = build_index_type (integer_zero_node);
2167 tree elt_type = TREE_TYPE (var);
2168 tree array_type = build_array_type (elt_type, index_type);
2169 tree base = create_tmp_var (array_type, base_name);
2171 add_referenced_var (base);
2173 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2177 /* Returns true when PHI is a loop close phi node. */
2180 scalar_close_phi_node_p (gimple phi)
2182 if (gimple_code (phi) != GIMPLE_PHI
2183 || !is_gimple_reg (gimple_phi_result (phi)))
2186 /* Note that loop close phi nodes should have a single argument
2187 because we translated the representation into a canonical form
2188 before Graphite: see canonicalize_loop_closed_ssa_form. */
2189 return (gimple_phi_num_args (phi) == 1);
2192 /* For a definition DEF in REGION, propagates the expression EXPR in
2193 all the uses of DEF outside REGION. */
2196 propagate_expr_outside_region (tree def, tree expr, sese region)
2198 imm_use_iterator imm_iter;
2201 bool replaced_once = false;
2203 gcc_assert (TREE_CODE (def) == SSA_NAME);
2205 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2208 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2209 if (!is_gimple_debug (use_stmt)
2210 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2213 use_operand_p use_p;
2215 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2216 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2217 && (replaced_once = true))
2218 replace_exp (use_p, expr);
2220 update_stmt (use_stmt);
2225 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2226 gsi_commit_edge_inserts ();
2230 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2231 dimension array for it. */
2234 rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2236 sese region = SCOP_REGION (scop);
2237 gimple phi = gsi_stmt (*psi);
2238 tree res = gimple_phi_result (phi);
2239 tree var = SSA_NAME_VAR (res);
2240 basic_block bb = gimple_bb (phi);
2241 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2242 tree arg = gimple_phi_arg_def (phi, 0);
2245 /* Note that loop close phi nodes should have a single argument
2246 because we translated the representation into a canonical form
2247 before Graphite: see canonicalize_loop_closed_ssa_form. */
2248 gcc_assert (gimple_phi_num_args (phi) == 1);
2250 /* The phi node can be a non close phi node, when its argument is
2251 invariant, or a default definition. */
2252 if (is_gimple_min_invariant (arg)
2253 || SSA_NAME_IS_DEFAULT_DEF (arg))
2255 propagate_expr_outside_region (res, arg, region);
2260 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2262 propagate_expr_outside_region (res, arg, region);
2263 stmt = gimple_build_assign (res, arg);
2264 remove_phi_node (psi, false);
2265 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2266 SSA_NAME_DEF_STMT (res) = stmt;
2270 /* If res is scev analyzable and is not a scalar value, it is safe
2271 to ignore the close phi node: it will be code generated in the
2272 out of Graphite pass. */
2273 else if (scev_analyzable_p (res, region))
2275 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2278 if (!loop_in_sese_p (loop, region))
2280 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2281 scev = scalar_evolution_in_region (region, loop, arg);
2282 scev = compute_overall_effect_of_inner_loop (loop, scev);
2285 scev = scalar_evolution_in_region (region, loop, res);
2287 if (tree_does_not_contain_chrecs (scev))
2288 propagate_expr_outside_region (res, scev, region);
2295 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2297 stmt = gimple_build_assign (res, zero_dim_array);
2299 if (TREE_CODE (arg) == SSA_NAME)
2300 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2301 SSA_NAME_DEF_STMT (arg));
2303 insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
2304 zero_dim_array, arg);
2307 remove_phi_node (psi, false);
2308 SSA_NAME_DEF_STMT (res) = stmt;
2310 insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
2313 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2314 dimension array for it. */
2317 rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2320 gimple phi = gsi_stmt (*psi);
2321 basic_block bb = gimple_bb (phi);
2322 tree res = gimple_phi_result (phi);
2323 tree var = SSA_NAME_VAR (res);
2324 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2328 for (i = 0; i < gimple_phi_num_args (phi); i++)
2330 tree arg = gimple_phi_arg_def (phi, i);
2331 edge e = gimple_phi_arg_edge (phi, i);
2333 /* Avoid the insertion of code in the loop latch to please the
2334 pattern matching of the vectorizer. */
2335 if (TREE_CODE (arg) == SSA_NAME
2336 && e->src == bb->loop_father->latch)
2337 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2338 SSA_NAME_DEF_STMT (arg));
2340 insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
2343 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2345 stmt = gimple_build_assign (res, var);
2346 remove_phi_node (psi, false);
2347 SSA_NAME_DEF_STMT (res) = stmt;
2349 insert_stmts (scop, stmt, stmts, gsi_after_labels (bb));
2352 /* Rewrite the degenerate phi node at position PSI from the degenerate
2353 form "x = phi (y, y, ..., y)" to "x = y". */
2356 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2360 gimple_stmt_iterator gsi;
2361 gimple phi = gsi_stmt (*psi);
2362 tree res = gimple_phi_result (phi);
2365 bb = gimple_bb (phi);
2366 rhs = degenerate_phi_result (phi);
2369 stmt = gimple_build_assign (res, rhs);
2370 remove_phi_node (psi, false);
2371 SSA_NAME_DEF_STMT (res) = stmt;
2373 gsi = gsi_after_labels (bb);
2374 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2377 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2380 rewrite_reductions_out_of_ssa (scop_p scop)
2383 gimple_stmt_iterator psi;
2384 sese region = SCOP_REGION (scop);
2387 if (bb_in_sese_p (bb, region))
2388 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2390 gimple phi = gsi_stmt (psi);
2392 if (!is_gimple_reg (gimple_phi_result (phi)))
2398 if (gimple_phi_num_args (phi) > 1
2399 && degenerate_phi_result (phi))
2400 rewrite_degenerate_phi (&psi);
2402 else if (scalar_close_phi_node_p (phi))
2403 rewrite_close_phi_out_of_ssa (scop, &psi);
2405 else if (reduction_phi_p (region, &psi))
2406 rewrite_phi_out_of_ssa (scop, &psi);
2409 update_ssa (TODO_update_ssa);
2410 #ifdef ENABLE_CHECKING
2411 verify_loop_closed_ssa (true);
2415 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2416 read from ZERO_DIM_ARRAY. */
2419 rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array,
2420 tree def, gimple use_stmt)
2422 tree var = SSA_NAME_VAR (def);
2423 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2424 tree name = make_ssa_name (var, name_stmt);
2426 use_operand_p use_p;
2428 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2430 gimple_assign_set_lhs (name_stmt, name);
2431 insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
2433 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2434 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2435 replace_exp (use_p, name);
2437 update_stmt (use_stmt);
2440 /* For every definition DEF in the SCOP that is used outside the scop,
2441 insert a closing-scop definition in the basic block just after this
2445 handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt)
2447 tree var = create_tmp_reg (TREE_TYPE (def), NULL);
2448 tree new_name = make_ssa_name (var, stmt);
2449 bool needs_copy = false;
2450 use_operand_p use_p;
2451 imm_use_iterator imm_iter;
2453 sese region = SCOP_REGION (scop);
2455 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2457 if (!bb_in_sese_p (gimple_bb (use_stmt), region))
2459 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2461 SET_USE (use_p, new_name);
2463 update_stmt (use_stmt);
2468 /* Insert in the empty BB just after the scop a use of DEF such
2469 that the rewrite of cross_bb_scalar_dependences won't insert
2470 arrays everywhere else. */
2473 gimple assign = gimple_build_assign (new_name, def);
2474 gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest);
2476 add_referenced_var (var);
2477 SSA_NAME_DEF_STMT (new_name) = assign;
2478 update_stmt (assign);
2479 gsi_insert_before (&psi, assign, GSI_SAME_STMT);
2483 /* Rewrite the scalar dependences crossing the boundary of the BB
2484 containing STMT with an array. Return true when something has been
2488 rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
2490 sese region = SCOP_REGION (scop);
2491 gimple stmt = gsi_stmt (*gsi);
2492 imm_use_iterator imm_iter;
2495 tree zero_dim_array = NULL_TREE;
2499 switch (gimple_code (stmt))
2502 def = gimple_assign_lhs (stmt);
2506 def = gimple_call_lhs (stmt);
2514 || !is_gimple_reg (def))
2517 if (scev_analyzable_p (def, region))
2519 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2520 tree scev = scalar_evolution_in_region (region, loop, def);
2522 if (tree_contains_chrecs (scev, NULL))
2525 propagate_expr_outside_region (def, scev, region);
2529 def_bb = gimple_bb (stmt);
2531 handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
2533 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2534 if (gimple_code (use_stmt) == GIMPLE_PHI
2537 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2539 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2540 rewrite_close_phi_out_of_ssa (scop, &psi);
2542 rewrite_phi_out_of_ssa (scop, &psi);
2545 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2546 if (gimple_code (use_stmt) != GIMPLE_PHI
2547 && def_bb != gimple_bb (use_stmt)
2548 && !is_gimple_debug (use_stmt)
2551 if (!zero_dim_array)
2553 zero_dim_array = create_zero_dim_array
2554 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2555 insert_out_of_ssa_copy (scop, zero_dim_array, def,
2556 SSA_NAME_DEF_STMT (def));
2560 rewrite_cross_bb_scalar_dependence (scop, zero_dim_array,
2567 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2570 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2573 gimple_stmt_iterator psi;
2574 sese region = SCOP_REGION (scop);
2575 bool changed = false;
2577 /* Create an extra empty BB after the scop. */
2578 split_edge (SESE_EXIT (region));
2581 if (bb_in_sese_p (bb, region))
2582 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2583 changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
2588 update_ssa (TODO_update_ssa);
2589 #ifdef ENABLE_CHECKING
2590 verify_loop_closed_ssa (true);
2595 /* Returns the number of pbbs that are in loops contained in SCOP. */
2598 nb_pbbs_in_loops (scop_p scop)
2604 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2605 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2611 /* Return the number of data references in BB that write in
2615 nb_data_writes_in_bb (basic_block bb)
2618 gimple_stmt_iterator gsi;
2620 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2621 if (gimple_vdef (gsi_stmt (gsi)))
2627 /* Splits at STMT the basic block BB represented as PBB in the
2631 split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt)
2633 edge e1 = split_block (bb, stmt);
2634 new_pbb_from_pbb (scop, pbb, e1->dest);
2638 /* Splits STMT out of its current BB. This is done for reduction
2639 statements for which we want to ignore data dependences. */
2642 split_reduction_stmt (scop_p scop, gimple stmt)
2644 basic_block bb = gimple_bb (stmt);
2645 poly_bb_p pbb = pbb_from_bb (bb);
2646 gimple_bb_p gbb = gbb_from_bb (bb);
2649 data_reference_p dr;
2651 /* Do not split basic blocks with no writes to memory: the reduction
2652 will be the only write to memory. */
2653 if (nb_data_writes_in_bb (bb) == 0)
2656 e1 = split_pbb (scop, pbb, bb, stmt);
2658 /* Split once more only when the reduction stmt is not the only one
2659 left in the original BB. */
2660 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2662 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2664 e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi));
2667 /* A part of the data references will end in a different basic block
2668 after the split: move the DRs from the original GBB to the newly
2670 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
2672 basic_block bb1 = gimple_bb (DR_STMT (dr));
2676 gimple_bb_p gbb1 = gbb_from_bb (bb1);
2677 VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr);
2678 VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i);
2686 /* Return true when stmt is a reduction operation. */
2689 is_reduction_operation_p (gimple stmt)
2691 enum tree_code code;
2693 gcc_assert (is_gimple_assign (stmt));
2694 code = gimple_assign_rhs_code (stmt);
2696 return flag_associative_math
2697 && commutative_tree_code (code)
2698 && associative_tree_code (code);
2701 /* Returns true when PHI contains an argument ARG. */
2704 phi_contains_arg (gimple phi, tree arg)
2708 for (i = 0; i < gimple_phi_num_args (phi); i++)
2709 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2715 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2718 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2722 if (TREE_CODE (arg) != SSA_NAME)
2725 stmt = SSA_NAME_DEF_STMT (arg);
2727 if (gimple_code (stmt) == GIMPLE_NOP
2728 || gimple_code (stmt) == GIMPLE_CALL)
2731 if (gimple_code (stmt) == GIMPLE_PHI)
2733 if (phi_contains_arg (stmt, lhs))
2738 if (!is_gimple_assign (stmt))
2741 if (gimple_num_ops (stmt) == 2)
2742 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2744 if (is_reduction_operation_p (stmt))
2746 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2749 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2755 /* Detect commutative and associative scalar reductions starting at
2756 the STMT. Return the phi node of the reduction cycle, or NULL. */
2759 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2760 VEC (gimple, heap) **in,
2761 VEC (gimple, heap) **out)
2763 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2768 VEC_safe_push (gimple, heap, *in, stmt);
2769 VEC_safe_push (gimple, heap, *out, stmt);
2773 /* Detect commutative and associative scalar reductions starting at
2774 STMT. Return the phi node of the reduction cycle, or NULL. */
2777 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2778 VEC (gimple, heap) **out)
2780 tree lhs = gimple_assign_lhs (stmt);
2782 if (gimple_num_ops (stmt) == 2)
2783 return detect_commutative_reduction_arg (lhs, stmt,
2784 gimple_assign_rhs1 (stmt),
2787 if (is_reduction_operation_p (stmt))
2789 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2790 gimple_assign_rhs1 (stmt),
2793 : detect_commutative_reduction_arg (lhs, stmt,
2794 gimple_assign_rhs2 (stmt),
2801 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2804 follow_inital_value_to_phi (tree arg, tree lhs)
2808 if (!arg || TREE_CODE (arg) != SSA_NAME)
2811 stmt = SSA_NAME_DEF_STMT (arg);
2813 if (gimple_code (stmt) == GIMPLE_PHI
2814 && phi_contains_arg (stmt, lhs))
2821 /* Return the argument of the loop PHI that is the inital value coming
2822 from outside the loop. */
2825 edge_initial_value_for_loop_phi (gimple phi)
2829 for (i = 0; i < gimple_phi_num_args (phi); i++)
2831 edge e = gimple_phi_arg_edge (phi, i);
2833 if (loop_depth (e->src->loop_father)
2834 < loop_depth (e->dest->loop_father))
2841 /* Return the argument of the loop PHI that is the inital value coming
2842 from outside the loop. */
2845 initial_value_for_loop_phi (gimple phi)
2849 for (i = 0; i < gimple_phi_num_args (phi); i++)
2851 edge e = gimple_phi_arg_edge (phi, i);
2853 if (loop_depth (e->src->loop_father)
2854 < loop_depth (e->dest->loop_father))
2855 return gimple_phi_arg_def (phi, i);
2861 /* Detect commutative and associative scalar reductions belonging to
2862 the SCOP starting at the loop closed phi node STMT. Return the phi
2863 node of the reduction cycle, or NULL. */
2866 detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
2867 VEC (gimple, heap) **out)
2869 if (scalar_close_phi_node_p (stmt))
2871 tree arg = gimple_phi_arg_def (stmt, 0);
2872 gimple def, loop_phi;
2874 if (TREE_CODE (arg) != SSA_NAME)
2877 /* Note that loop close phi nodes should have a single argument
2878 because we translated the representation into a canonical form
2879 before Graphite: see canonicalize_loop_closed_ssa_form. */
2880 gcc_assert (gimple_phi_num_args (stmt) == 1);
2882 def = SSA_NAME_DEF_STMT (arg);
2883 if (!stmt_in_sese_p (def, SCOP_REGION (scop)))
2886 loop_phi = detect_commutative_reduction (scop, def, in, out);
2890 tree lhs = gimple_phi_result (stmt);
2891 tree init = initial_value_for_loop_phi (loop_phi);
2892 gimple phi = follow_inital_value_to_phi (init, lhs);
2894 VEC_safe_push (gimple, heap, *in, loop_phi);
2895 VEC_safe_push (gimple, heap, *out, stmt);
2902 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2903 return detect_commutative_reduction_assign (stmt, in, out);
2908 /* Translate the scalar reduction statement STMT to an array RED
2909 knowing that its recursive phi node is LOOP_PHI. */
2912 translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
2913 gimple stmt, gimple loop_phi)
2915 tree res = gimple_phi_result (loop_phi);
2916 gimple assign = gimple_build_assign (res, red);
2917 gimple_stmt_iterator gsi;
2919 insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
2921 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2922 gsi = gsi_for_stmt (stmt);
2924 insert_stmts (scop, assign, NULL, gsi);
2927 /* Removes the PHI node and resets all the debug stmts that are using
2931 remove_phi (gimple phi)
2933 imm_use_iterator imm_iter;
2935 use_operand_p use_p;
2936 gimple_stmt_iterator gsi;
2937 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2941 def = PHI_RESULT (phi);
2942 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2944 stmt = USE_STMT (use_p);
2946 if (is_gimple_debug (stmt))
2948 gimple_debug_bind_reset_value (stmt);
2949 VEC_safe_push (gimple, heap, update, stmt);
2953 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
2956 VEC_free (gimple, heap, update);
2958 gsi = gsi_for_phi_node (phi);
2959 remove_phi_node (&gsi, false);
2962 /* Rewrite out of SSA the reduction described by the loop phi nodes
2963 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2966 IN: stmt, loop_n, ..., loop_0
2967 OUT: stmt, close_n, ..., close_0
2969 the first element is the reduction statement, and the next elements
2970 are the loop and close phi nodes of each of the outer loops. */
2973 translate_scalar_reduction_to_array (scop_p scop,
2974 VEC (gimple, heap) *in,
2975 VEC (gimple, heap) *out)
2979 tree red = NULL_TREE;
2981 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
2983 gimple close_phi = VEC_index (gimple, out, i);
2987 gimple stmt = loop_phi;
2988 basic_block bb = split_reduction_stmt (scop, stmt);
2989 poly_bb_p pbb = pbb_from_bb (bb);
2990 PBB_IS_REDUCTION (pbb) = true;
2991 gcc_assert (close_phi == loop_phi);
2993 red = create_zero_dim_array
2994 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2995 translate_scalar_reduction_to_array_for_stmt
2996 (scop, red, stmt, VEC_index (gimple, in, 1));
3000 if (i == VEC_length (gimple, in) - 1)
3002 insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi), red,
3004 insert_out_of_ssa_copy_on_edge
3005 (scop, edge_initial_value_for_loop_phi (loop_phi),
3006 red, initial_value_for_loop_phi (loop_phi));
3009 remove_phi (loop_phi);
3010 remove_phi (close_phi);
3014 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3015 true when something has been changed. */
3018 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
3022 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
3023 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
3025 detect_commutative_reduction (scop, close_phi, &in, &out);
3026 res = VEC_length (gimple, in) > 0;
3028 translate_scalar_reduction_to_array (scop, in, out);
3030 VEC_free (gimple, heap, in);
3031 VEC_free (gimple, heap, out);
3035 /* Rewrites all the commutative reductions from LOOP out of SSA.
3036 Returns true when something has been changed. */
3039 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop,
3042 gimple_stmt_iterator gsi;
3043 edge exit = single_exit (loop);
3045 bool changed = false;
3050 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3051 if ((res = gimple_phi_result (gsi_stmt (gsi)))
3052 && is_gimple_reg (res)
3053 && !scev_analyzable_p (res, SCOP_REGION (scop)))
3054 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
3055 (scop, gsi_stmt (gsi));
3060 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3063 rewrite_commutative_reductions_out_of_ssa (scop_p scop)
3067 bool changed = false;
3068 sese region = SCOP_REGION (scop);
3070 FOR_EACH_LOOP (li, loop, 0)
3071 if (loop_in_sese_p (loop, region))
3072 changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop);
3077 gsi_commit_edge_inserts ();
3078 update_ssa (TODO_update_ssa);
3079 #ifdef ENABLE_CHECKING
3080 verify_loop_closed_ssa (true);
3085 /* Java does not initialize long_long_integer_type_node. */
3086 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
3088 /* Can all ivs be represented by a signed integer?
3089 As CLooG might generate negative values in its expressions, signed loop ivs
3090 are required in the backend. */
3093 scop_ivs_can_be_represented (scop_p scop)
3097 gimple_stmt_iterator psi;
3099 FOR_EACH_LOOP (li, loop, 0)
3101 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3104 for (psi = gsi_start_phis (loop->header);
3105 !gsi_end_p (psi); gsi_next (&psi))
3107 gimple phi = gsi_stmt (psi);
3108 tree res = PHI_RESULT (phi);
3109 tree type = TREE_TYPE (res);
3111 if (TYPE_UNSIGNED (type)
3112 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
3122 /* Builds the polyhedral representation for a SESE region. */
3125 build_poly_scop (scop_p scop)
3127 sese region = SCOP_REGION (scop);
3128 graphite_dim_t max_dim;
3130 build_scop_bbs (scop);
3132 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3133 Once CLooG is fixed, remove this guard. Anyways, it makes no
3134 sense to optimize a scop containing only PBBs that do not belong
3136 if (nb_pbbs_in_loops (scop) == 0)
3139 if (!scop_ivs_can_be_represented (scop))
3142 build_sese_loop_nests (region);
3143 build_sese_conditions (region);
3144 find_scop_parameters (scop);
3146 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3147 if (scop_nb_params (scop) > max_dim)
3150 build_scop_iteration_domain (scop);
3151 build_scop_context (scop);
3152 add_conditions_to_constraints (scop);
3154 /* Rewrite out of SSA only after having translated the
3155 representation to the polyhedral representation to avoid scev
3156 analysis failures. That means that these functions will insert
3157 new data references that they create in the right place. */
3158 if (flag_associative_math)
3159 rewrite_commutative_reductions_out_of_ssa (scop);
3160 rewrite_reductions_out_of_ssa (scop);
3161 rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
3163 build_scop_drs (scop);
3165 build_scop_scattering (scop);
3167 /* This SCoP has been translated to the polyhedral
3169 POLY_SCOP_P (scop) = true;