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 mpz_set_si (val, int_cst_value (e));
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 int v = int_cst_value (cst);
634 /* Necessary to not get "-1 = 2^n - 1". */
636 mpz_sub_ui (val, val, -v);
638 mpz_add_ui (val, val, v);
640 mpz_mul (val, val, k);
641 ppl_new_Coefficient (&coef);
642 ppl_assign_Coefficient_from_mpz_t (coef, val);
643 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
645 ppl_delete_Coefficient (coef);
648 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
649 Otherwise returns -1. */
652 parameter_index_in_region_1 (tree name, sese region)
657 gcc_assert (TREE_CODE (name) == SSA_NAME);
659 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
666 /* When the parameter NAME is in REGION, returns its index in
667 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
668 and returns the index of NAME. */
671 parameter_index_in_region (tree name, sese region)
675 gcc_assert (TREE_CODE (name) == SSA_NAME);
677 i = parameter_index_in_region_1 (name, region);
681 gcc_assert (SESE_ADD_PARAMS (region));
683 i = VEC_length (tree, SESE_PARAMS (region));
684 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
688 /* In the context of sese S, scan the expression E and translate it to
689 a linear expression C. When parsing a symbolic multiplication, K
690 represents the constant multiplier of an expression containing
694 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
697 if (e == chrec_dont_know)
700 switch (TREE_CODE (e))
702 case POLYNOMIAL_CHREC:
703 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
704 CHREC_VARIABLE (e), c);
705 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
709 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
714 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
716 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
717 mpz_mul (val, val, k);
718 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
722 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
729 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
731 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
732 mpz_mul (val, val, k);
733 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
737 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
742 case POINTER_PLUS_EXPR:
743 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
744 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
749 ppl_Linear_Expression_t tmp_expr = NULL;
753 ppl_dimension_type dim;
754 ppl_Linear_Expression_space_dimension (c, &dim);
755 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
758 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
759 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
763 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
765 ppl_delete_Linear_Expression (tmp_expr);
773 ppl_Linear_Expression_t tmp_expr = NULL;
777 ppl_dimension_type dim;
778 ppl_Linear_Expression_space_dimension (c, &dim);
779 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
782 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
786 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
788 ppl_delete_Linear_Expression (tmp_expr);
796 ppl_Linear_Expression_t tmp_expr = NULL;
800 ppl_dimension_type dim;
801 ppl_Linear_Expression_space_dimension (c, &dim);
802 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
805 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
809 ppl_Coefficient_t coef;
812 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
814 ppl_delete_Linear_Expression (tmp_expr);
815 mpz_init (minus_one);
816 mpz_set_si (minus_one, -1);
817 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
818 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
819 mpz_clear (minus_one);
820 ppl_delete_Coefficient (coef);
828 ppl_dimension_type p = parameter_index_in_region (e, s);
832 ppl_dimension_type dim;
833 ppl_Linear_Expression_space_dimension (c, &dim);
834 p += dim - sese_nb_params (s);
835 add_value_to_dim (p, c, k);
842 scan_tree_for_params_int (e, c, k);
846 case NON_LVALUE_EXPR:
847 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
856 /* Find parameters with respect to REGION in BB. We are looking in memory
857 access functions, conditions and loop bounds. */
860 find_params_in_bb (sese region, gimple_bb_p gbb)
866 loop_p loop = GBB_BB (gbb)->loop_father;
872 /* Find parameters in the access functions of data references. */
873 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
874 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
875 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
877 /* Find parameters in conditional statements. */
878 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
880 tree lhs = scalar_evolution_in_region (region, loop,
881 gimple_cond_lhs (stmt));
882 tree rhs = scalar_evolution_in_region (region, loop,
883 gimple_cond_rhs (stmt));
885 scan_tree_for_params (region, lhs, NULL, one);
886 scan_tree_for_params (region, rhs, NULL, one);
892 /* Record the parameters used in the SCOP. A variable is a parameter
893 in a scop if it does not vary during the execution of that scop. */
896 find_scop_parameters (scop_p scop)
900 sese region = SCOP_REGION (scop);
907 /* Find the parameters used in the loop bounds. */
908 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
910 tree nb_iters = number_of_latch_executions (loop);
912 if (!chrec_contains_symbols (nb_iters))
915 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
916 scan_tree_for_params (region, nb_iters, NULL, one);
921 /* Find the parameters used in data accesses. */
922 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
923 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
925 scop_set_nb_params (scop, sese_nb_params (region));
926 SESE_ADD_PARAMS (region) = false;
928 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
929 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
932 /* Insert in the SCOP context constraints from the estimation of the
933 number of iterations. UB_EXPR is a linear expression describing
934 the number of iterations in a loop. This expression is bounded by
935 the estimation NIT. */
938 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
939 ppl_dimension_type dim,
940 ppl_Linear_Expression_t ub_expr)
943 ppl_Linear_Expression_t nb_iters_le;
944 ppl_Polyhedron_t pol;
945 ppl_Coefficient_t coef;
948 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
949 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
952 /* Construct the negated number of last iteration in VAL. */
954 mpz_set_double_int (val, nit, false);
955 mpz_sub_ui (val, val, 1);
958 /* NB_ITERS_LE holds the number of last iteration in
959 parametrical form. Subtract estimated number of last
960 iteration and assert that result is not positive. */
961 ppl_new_Coefficient_from_mpz_t (&coef, val);
962 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
963 ppl_delete_Coefficient (coef);
964 ppl_new_Constraint (&ub, nb_iters_le,
965 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
966 ppl_Polyhedron_add_constraint (pol, ub);
968 /* Remove all but last GDIM dimensions from POL to obtain
969 only the constraints on the parameters. */
971 graphite_dim_t gdim = scop_nb_params (scop);
972 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
975 for (i = 0; i < dim - gdim; i++)
978 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
982 /* Add the constraints on the parameters to the SCoP context. */
984 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
986 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
987 (&constraints_ps, pol);
988 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
989 (SCOP_CONTEXT (scop), constraints_ps);
990 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
993 ppl_delete_Polyhedron (pol);
994 ppl_delete_Linear_Expression (nb_iters_le);
995 ppl_delete_Constraint (ub);
999 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1000 the constraints for the surrounding loops. */
1003 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1004 ppl_Polyhedron_t outer_ph, int nb,
1005 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1008 ppl_Polyhedron_t ph;
1009 tree nb_iters = number_of_latch_executions (loop);
1010 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1011 sese region = SCOP_REGION (scop);
1014 ppl_const_Constraint_System_t pcs;
1015 ppl_dimension_type *map
1016 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1018 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1019 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1020 ppl_Polyhedron_add_constraints (ph, pcs);
1022 for (i = 0; i < (int) nb; i++)
1024 for (i = (int) nb; i < (int) dim - 1; i++)
1028 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1034 ppl_Constraint_t lb;
1035 ppl_Linear_Expression_t lb_expr;
1037 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1038 ppl_set_coef (lb_expr, nb, 1);
1039 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1040 ppl_delete_Linear_Expression (lb_expr);
1041 ppl_Polyhedron_add_constraint (ph, lb);
1042 ppl_delete_Constraint (lb);
1045 if (TREE_CODE (nb_iters) == INTEGER_CST)
1047 ppl_Constraint_t ub;
1048 ppl_Linear_Expression_t ub_expr;
1050 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1052 /* loop_i <= cst_nb_iters */
1053 ppl_set_coef (ub_expr, nb, -1);
1054 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1055 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1056 ppl_Polyhedron_add_constraint (ph, ub);
1057 ppl_delete_Linear_Expression (ub_expr);
1058 ppl_delete_Constraint (ub);
1060 else if (!chrec_contains_undetermined (nb_iters))
1063 ppl_Constraint_t ub;
1064 ppl_Linear_Expression_t ub_expr;
1068 mpz_set_si (one, 1);
1069 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1070 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1071 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1074 if (estimated_loop_iterations (loop, true, &nit))
1075 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1077 /* loop_i <= expr_nb_iters */
1078 ppl_set_coef (ub_expr, nb, -1);
1079 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1080 ppl_Polyhedron_add_constraint (ph, ub);
1081 ppl_delete_Linear_Expression (ub_expr);
1082 ppl_delete_Constraint (ub);
1087 if (loop->inner && loop_in_sese_p (loop->inner, region))
1088 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1092 && loop_in_sese_p (loop->next, region))
1093 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1095 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1096 (&domains[loop->num], ph);
1098 ppl_delete_Polyhedron (ph);
1101 /* Returns a linear expression for tree T evaluated in PBB. */
1103 static ppl_Linear_Expression_t
1104 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1107 ppl_Linear_Expression_t res;
1108 ppl_dimension_type dim;
1109 sese region = SCOP_REGION (PBB_SCOP (pbb));
1110 loop_p loop = pbb_loop (pbb);
1112 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1113 ppl_new_Linear_Expression_with_dimension (&res, dim);
1115 t = scalar_evolution_in_region (region, loop, t);
1116 gcc_assert (!automatically_generated_chrec_p (t));
1119 mpz_set_si (one, 1);
1120 scan_tree_for_params (region, t, res, one);
1126 /* Returns the ppl constraint type from the gimple tree code CODE. */
1128 static enum ppl_enum_Constraint_Type
1129 ppl_constraint_type_from_tree_code (enum tree_code code)
1133 /* We do not support LT and GT to be able to work with C_Polyhedron.
1134 As we work on integer polyhedron "a < b" can be expressed by
1141 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1144 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1147 return PPL_CONSTRAINT_TYPE_EQUAL;
1154 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1155 CODE is used as the comparison operator. This allows us to invert the
1156 condition or to handle inequalities. */
1159 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1160 poly_bb_p pbb, enum tree_code code)
1163 ppl_Coefficient_t c;
1164 ppl_Linear_Expression_t left, right;
1165 ppl_Constraint_t cstr;
1166 enum ppl_enum_Constraint_Type type;
1168 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1169 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1171 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1172 the left or the right side of the expression. */
1173 if (code == LT_EXPR)
1177 ppl_new_Coefficient (&c);
1178 ppl_assign_Coefficient_from_mpz_t (c, v);
1179 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1180 ppl_delete_Coefficient (c);
1185 else if (code == GT_EXPR)
1189 ppl_new_Coefficient (&c);
1190 ppl_assign_Coefficient_from_mpz_t (c, v);
1191 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1192 ppl_delete_Coefficient (c);
1198 type = ppl_constraint_type_from_tree_code (code);
1200 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1202 ppl_new_Constraint (&cstr, left, type);
1203 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1205 ppl_delete_Constraint (cstr);
1206 ppl_delete_Linear_Expression (left);
1207 ppl_delete_Linear_Expression (right);
1210 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1211 operator. This allows us to invert the condition or to handle
1215 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1217 if (code == NE_EXPR)
1219 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1220 ppl_Pointset_Powerset_C_Polyhedron_t right;
1221 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1223 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1224 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1225 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1226 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1229 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1232 /* Add conditions to the domain of PBB. */
1235 add_conditions_to_domain (poly_bb_p pbb)
1239 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1241 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1244 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1245 switch (gimple_code (stmt))
1249 enum tree_code code = gimple_cond_code (stmt);
1251 /* The conditions for ELSE-branches are inverted. */
1252 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1253 code = invert_tree_comparison (code, false);
1255 add_condition_to_pbb (pbb, stmt, code);
1260 /* Switch statements are not supported right now - fall throught. */
1268 /* Traverses all the GBBs of the SCOP and add their constraints to the
1269 iteration domains. */
1272 add_conditions_to_constraints (scop_p scop)
1277 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1278 add_conditions_to_domain (pbb);
1281 /* Structure used to pass data to dom_walk. */
1285 VEC (gimple, heap) **conditions, **cases;
1289 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1290 edge between BB and its predecessor is not a loop exit edge, and
1291 the last statement of the single predecessor is a COND_EXPR. */
1294 single_pred_cond_non_loop_exit (basic_block bb)
1296 if (single_pred_p (bb))
1298 edge e = single_pred_edge (bb);
1299 basic_block pred = e->src;
1302 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1305 stmt = last_stmt (pred);
1307 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1314 /* Call-back for dom_walk executed before visiting the dominated
1318 build_sese_conditions_before (struct dom_walk_data *dw_data,
1321 struct bsc *data = (struct bsc *) dw_data->global_data;
1322 VEC (gimple, heap) **conditions = data->conditions;
1323 VEC (gimple, heap) **cases = data->cases;
1327 if (!bb_in_sese_p (bb, data->region))
1330 stmt = single_pred_cond_non_loop_exit (bb);
1334 edge e = single_pred_edge (bb);
1336 VEC_safe_push (gimple, heap, *conditions, stmt);
1338 if (e->flags & EDGE_TRUE_VALUE)
1339 VEC_safe_push (gimple, heap, *cases, stmt);
1341 VEC_safe_push (gimple, heap, *cases, NULL);
1344 gbb = gbb_from_bb (bb);
1348 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1349 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1353 /* Call-back for dom_walk executed after visiting the dominated
1357 build_sese_conditions_after (struct dom_walk_data *dw_data,
1360 struct bsc *data = (struct bsc *) dw_data->global_data;
1361 VEC (gimple, heap) **conditions = data->conditions;
1362 VEC (gimple, heap) **cases = data->cases;
1364 if (!bb_in_sese_p (bb, data->region))
1367 if (single_pred_cond_non_loop_exit (bb))
1369 VEC_pop (gimple, *conditions);
1370 VEC_pop (gimple, *cases);
1374 /* Record all conditions in REGION. */
1377 build_sese_conditions (sese region)
1379 struct dom_walk_data walk_data;
1380 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1381 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1384 data.conditions = &conditions;
1385 data.cases = &cases;
1386 data.region = region;
1388 walk_data.dom_direction = CDI_DOMINATORS;
1389 walk_data.initialize_block_local_data = NULL;
1390 walk_data.before_dom_children = build_sese_conditions_before;
1391 walk_data.after_dom_children = build_sese_conditions_after;
1392 walk_data.global_data = &data;
1393 walk_data.block_local_data_size = 0;
1395 init_walk_dominator_tree (&walk_data);
1396 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1397 fini_walk_dominator_tree (&walk_data);
1399 VEC_free (gimple, heap, conditions);
1400 VEC_free (gimple, heap, cases);
1403 /* Add constraints on the possible values of parameter P from the type
1407 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1409 ppl_Constraint_t cstr;
1410 ppl_Linear_Expression_t le;
1411 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1412 tree type = TREE_TYPE (parameter);
1413 tree lb = NULL_TREE;
1414 tree ub = NULL_TREE;
1416 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1417 lb = lower_bound_in_type (type, type);
1419 lb = TYPE_MIN_VALUE (type);
1421 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1422 ub = upper_bound_in_type (type, type);
1424 ub = TYPE_MAX_VALUE (type);
1428 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1429 ppl_set_coef (le, p, -1);
1430 ppl_set_inhomogeneous_tree (le, lb);
1431 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1432 ppl_Polyhedron_add_constraint (context, cstr);
1433 ppl_delete_Linear_Expression (le);
1434 ppl_delete_Constraint (cstr);
1439 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1440 ppl_set_coef (le, p, -1);
1441 ppl_set_inhomogeneous_tree (le, ub);
1442 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1443 ppl_Polyhedron_add_constraint (context, cstr);
1444 ppl_delete_Linear_Expression (le);
1445 ppl_delete_Constraint (cstr);
1449 /* Build the context of the SCOP. The context usually contains extra
1450 constraints that are added to the iteration domains that constrain
1454 build_scop_context (scop_p scop)
1456 ppl_Polyhedron_t context;
1457 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1458 graphite_dim_t p, n = scop_nb_params (scop);
1460 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1462 for (p = 0; p < n; p++)
1463 add_param_constraints (scop, context, p);
1465 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1467 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1468 (SCOP_CONTEXT (scop), ps);
1470 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1471 ppl_delete_Polyhedron (context);
1474 /* Build the iteration domains: the loops belonging to the current
1475 SCOP, and that vary for the execution of the current basic block.
1476 Returns false if there is no loop in SCOP. */
1479 build_scop_iteration_domain (scop_p scop)
1482 sese region = SCOP_REGION (scop);
1484 ppl_Polyhedron_t ph;
1486 int nb_loops = number_of_loops ();
1487 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1488 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1490 for (i = 0; i < nb_loops; i++)
1493 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1495 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1496 if (!loop_in_sese_p (loop_outer (loop), region))
1497 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1499 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1500 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1501 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1502 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1503 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1505 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1506 (&PBB_DOMAIN (pbb), ph);
1508 for (i = 0; i < nb_loops; i++)
1510 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1512 ppl_delete_Polyhedron (ph);
1516 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1517 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1518 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1522 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1523 ppl_dimension_type accessp_nb_dims,
1524 ppl_dimension_type dom_nb_dims)
1526 ppl_Linear_Expression_t alias;
1527 ppl_Constraint_t cstr;
1528 int alias_set_num = 0;
1529 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1531 if (bap && bap->alias_set)
1532 alias_set_num = *(bap->alias_set);
1534 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1536 ppl_set_coef (alias, dom_nb_dims, 1);
1537 ppl_set_inhomogeneous (alias, -alias_set_num);
1538 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1539 ppl_Polyhedron_add_constraint (accesses, cstr);
1541 ppl_delete_Linear_Expression (alias);
1542 ppl_delete_Constraint (cstr);
1545 /* Add to ACCESSES polyhedron equalities defining the access functions
1546 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1547 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1548 PBB is the poly_bb_p that contains the data reference DR. */
1551 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1552 ppl_dimension_type accessp_nb_dims,
1553 ppl_dimension_type dom_nb_dims,
1556 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1558 scop_p scop = PBB_SCOP (pbb);
1559 sese region = SCOP_REGION (scop);
1563 for (i = 0; i < nb_subscripts; i++)
1565 ppl_Linear_Expression_t fn, access;
1566 ppl_Constraint_t cstr;
1567 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1568 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1570 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1571 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1574 scan_tree_for_params (region, afn, fn, v);
1575 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1577 ppl_set_coef (access, subscript, -1);
1578 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1579 ppl_Polyhedron_add_constraint (accesses, cstr);
1581 ppl_delete_Linear_Expression (fn);
1582 ppl_delete_Linear_Expression (access);
1583 ppl_delete_Constraint (cstr);
1589 /* Add constrains representing the size of the accessed data to the
1590 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1591 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1595 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1596 ppl_dimension_type accessp_nb_dims,
1597 ppl_dimension_type dom_nb_dims)
1599 tree ref = DR_REF (dr);
1600 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1602 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1604 ppl_Linear_Expression_t expr;
1605 ppl_Constraint_t cstr;
1606 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1609 if (TREE_CODE (ref) != ARRAY_REF)
1612 low = array_ref_low_bound (ref);
1614 /* subscript - low >= 0 */
1615 if (host_integerp (low, 0))
1617 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1618 ppl_set_coef (expr, subscript, 1);
1620 ppl_set_inhomogeneous (expr, -int_cst_value (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 (expr, int_cst_value (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 VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i);
1978 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1979 for (j = 0; VEC_iterate (data_reference_p,
1980 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
1981 VEC_safe_push (data_reference_p, heap, drs, dr);
1983 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
1984 dr->aux = XNEW (base_alias_pair);
1986 if (!build_alias_set_optimal_p (drs))
1988 /* TODO: Add support when building alias set is not optimal. */
1992 build_base_obj_set_for_drs (drs);
1994 /* When debugging, enable the following code. This cannot be used
1995 in production compilers. */
1997 dump_alias_graphs (drs);
1999 VEC_free (data_reference_p, heap, drs);
2001 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2002 build_pbb_drs (pbb);
2005 /* Return a gsi at the position of the phi node STMT. */
2007 static gimple_stmt_iterator
2008 gsi_for_phi_node (gimple stmt)
2010 gimple_stmt_iterator psi;
2011 basic_block bb = gimple_bb (stmt);
2013 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2014 if (stmt == gsi_stmt (psi))
2021 /* Analyze all the data references of STMTS and add them to the
2022 GBB_DATA_REFS vector of BB. */
2025 analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
2032 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2035 nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
2036 gbb = gbb_from_bb (bb);
2038 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
2039 if (!is_gimple_debug (stmt))
2040 graphite_find_data_references_in_stmt (nest, stmt,
2041 &GBB_DATA_REFS (gbb));
2044 /* Insert STMT at the end of the STMTS sequence and then insert the
2045 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2049 insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts,
2050 gimple_stmt_iterator insert_gsi)
2052 gimple_stmt_iterator gsi;
2053 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2056 stmts = gimple_seq_alloc ();
2058 gsi = gsi_last (stmts);
2059 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2060 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2061 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2063 gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2064 analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
2065 VEC_free (gimple, heap, x);
2068 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2071 insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt)
2074 gimple_stmt_iterator si;
2075 gimple_stmt_iterator gsi;
2076 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2077 gimple stmt = gimple_build_assign (res, var);
2078 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2081 stmts = gimple_seq_alloc ();
2082 si = gsi_last (stmts);
2083 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2084 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2085 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2087 if (gimple_code (after_stmt) == GIMPLE_PHI)
2089 gsi = gsi_after_labels (gimple_bb (after_stmt));
2090 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2094 gsi = gsi_for_stmt (after_stmt);
2095 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2098 analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
2099 VEC_free (gimple, heap, x);
2102 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2105 new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
2107 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2108 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
2109 gimple_bb_p gbb1 = new_gimple_bb (bb, drs);
2110 poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
2111 int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
2113 /* The INDEX of PBB in SCOP_BBS. */
2114 for (index = 0; index < n; index++)
2115 if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
2118 GBB_PBB (gbb1) = pbb1;
2119 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2120 (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
2121 GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
2122 GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
2123 VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
2126 /* Insert on edge E the assignment "RES := EXPR". */
2129 insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
2131 gimple_stmt_iterator gsi;
2133 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2134 gimple stmt = gimple_build_assign (res, var);
2136 VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2139 stmts = gimple_seq_alloc ();
2141 gsi = gsi_last (stmts);
2142 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2143 for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2144 VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2146 gsi_insert_seq_on_edge (e, stmts);
2147 gsi_commit_edge_inserts ();
2148 bb = gimple_bb (stmt);
2150 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2153 if (!gbb_from_bb (bb))
2154 new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
2156 analyze_drs_in_stmts (scop, bb, x);
2157 VEC_free (gimple, heap, x);
2160 /* Creates a zero dimension array of the same type as VAR. */
2163 create_zero_dim_array (tree var, const char *base_name)
2165 tree index_type = build_index_type (integer_zero_node);
2166 tree elt_type = TREE_TYPE (var);
2167 tree array_type = build_array_type (elt_type, index_type);
2168 tree base = create_tmp_var (array_type, base_name);
2170 add_referenced_var (base);
2172 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2176 /* Returns true when PHI is a loop close phi node. */
2179 scalar_close_phi_node_p (gimple phi)
2181 if (gimple_code (phi) != GIMPLE_PHI
2182 || !is_gimple_reg (gimple_phi_result (phi)))
2185 /* Note that loop close phi nodes should have a single argument
2186 because we translated the representation into a canonical form
2187 before Graphite: see canonicalize_loop_closed_ssa_form. */
2188 return (gimple_phi_num_args (phi) == 1);
2191 /* For a definition DEF in REGION, propagates the expression EXPR in
2192 all the uses of DEF outside REGION. */
2195 propagate_expr_outside_region (tree def, tree expr, sese region)
2197 imm_use_iterator imm_iter;
2200 bool replaced_once = false;
2202 gcc_assert (TREE_CODE (def) == SSA_NAME);
2204 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2207 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2208 if (!is_gimple_debug (use_stmt)
2209 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2212 use_operand_p use_p;
2214 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2215 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2216 && (replaced_once = true))
2217 replace_exp (use_p, expr);
2219 update_stmt (use_stmt);
2224 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2225 gsi_commit_edge_inserts ();
2229 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2230 dimension array for it. */
2233 rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2235 sese region = SCOP_REGION (scop);
2236 gimple phi = gsi_stmt (*psi);
2237 tree res = gimple_phi_result (phi);
2238 tree var = SSA_NAME_VAR (res);
2239 basic_block bb = gimple_bb (phi);
2240 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2241 tree arg = gimple_phi_arg_def (phi, 0);
2244 /* Note that loop close phi nodes should have a single argument
2245 because we translated the representation into a canonical form
2246 before Graphite: see canonicalize_loop_closed_ssa_form. */
2247 gcc_assert (gimple_phi_num_args (phi) == 1);
2249 /* The phi node can be a non close phi node, when its argument is
2250 invariant, or a default definition. */
2251 if (is_gimple_min_invariant (arg)
2252 || SSA_NAME_IS_DEFAULT_DEF (arg))
2254 propagate_expr_outside_region (res, arg, region);
2259 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2261 propagate_expr_outside_region (res, arg, region);
2262 stmt = gimple_build_assign (res, arg);
2263 remove_phi_node (psi, false);
2264 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2265 SSA_NAME_DEF_STMT (res) = stmt;
2269 /* If res is scev analyzable and is not a scalar value, it is safe
2270 to ignore the close phi node: it will be code generated in the
2271 out of Graphite pass. */
2272 else if (scev_analyzable_p (res, region))
2274 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2277 if (!loop_in_sese_p (loop, region))
2279 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2280 scev = scalar_evolution_in_region (region, loop, arg);
2281 scev = compute_overall_effect_of_inner_loop (loop, scev);
2284 scev = scalar_evolution_in_region (region, loop, res);
2286 if (tree_does_not_contain_chrecs (scev))
2287 propagate_expr_outside_region (res, scev, region);
2294 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2296 stmt = gimple_build_assign (res, zero_dim_array);
2298 if (TREE_CODE (arg) == SSA_NAME)
2299 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2300 SSA_NAME_DEF_STMT (arg));
2302 insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
2303 zero_dim_array, arg);
2306 remove_phi_node (psi, false);
2307 SSA_NAME_DEF_STMT (res) = stmt;
2309 insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
2312 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2313 dimension array for it. */
2316 rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2319 gimple phi = gsi_stmt (*psi);
2320 basic_block bb = gimple_bb (phi);
2321 tree res = gimple_phi_result (phi);
2322 tree var = SSA_NAME_VAR (res);
2323 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2327 for (i = 0; i < gimple_phi_num_args (phi); i++)
2329 tree arg = gimple_phi_arg_def (phi, i);
2330 edge e = gimple_phi_arg_edge (phi, i);
2332 /* Avoid the insertion of code in the loop latch to please the
2333 pattern matching of the vectorizer. */
2334 if (TREE_CODE (arg) == SSA_NAME
2335 && e->src == bb->loop_father->latch)
2336 insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2337 SSA_NAME_DEF_STMT (arg));
2339 insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
2342 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2344 stmt = gimple_build_assign (res, var);
2345 remove_phi_node (psi, false);
2346 SSA_NAME_DEF_STMT (res) = stmt;
2348 insert_stmts (scop, stmt, stmts, gsi_after_labels (bb));
2351 /* Rewrite the degenerate phi node at position PSI from the degenerate
2352 form "x = phi (y, y, ..., y)" to "x = y". */
2355 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2359 gimple_stmt_iterator gsi;
2360 gimple phi = gsi_stmt (*psi);
2361 tree res = gimple_phi_result (phi);
2364 bb = gimple_bb (phi);
2365 rhs = degenerate_phi_result (phi);
2368 stmt = gimple_build_assign (res, rhs);
2369 remove_phi_node (psi, false);
2370 SSA_NAME_DEF_STMT (res) = stmt;
2372 gsi = gsi_after_labels (bb);
2373 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2376 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2379 rewrite_reductions_out_of_ssa (scop_p scop)
2382 gimple_stmt_iterator psi;
2383 sese region = SCOP_REGION (scop);
2386 if (bb_in_sese_p (bb, region))
2387 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2389 gimple phi = gsi_stmt (psi);
2391 if (!is_gimple_reg (gimple_phi_result (phi)))
2397 if (gimple_phi_num_args (phi) > 1
2398 && degenerate_phi_result (phi))
2399 rewrite_degenerate_phi (&psi);
2401 else if (scalar_close_phi_node_p (phi))
2402 rewrite_close_phi_out_of_ssa (scop, &psi);
2404 else if (reduction_phi_p (region, &psi))
2405 rewrite_phi_out_of_ssa (scop, &psi);
2408 update_ssa (TODO_update_ssa);
2409 #ifdef ENABLE_CHECKING
2410 verify_loop_closed_ssa (true);
2414 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2415 read from ZERO_DIM_ARRAY. */
2418 rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array,
2419 tree def, gimple use_stmt)
2421 tree var = SSA_NAME_VAR (def);
2422 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2423 tree name = make_ssa_name (var, name_stmt);
2425 use_operand_p use_p;
2427 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2429 gimple_assign_set_lhs (name_stmt, name);
2430 insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
2432 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2433 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2434 replace_exp (use_p, name);
2436 update_stmt (use_stmt);
2439 /* For every definition DEF in the SCOP that is used outside the scop,
2440 insert a closing-scop definition in the basic block just after this
2444 handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt)
2446 tree var = create_tmp_reg (TREE_TYPE (def), NULL);
2447 tree new_name = make_ssa_name (var, stmt);
2448 bool needs_copy = false;
2449 use_operand_p use_p;
2450 imm_use_iterator imm_iter;
2452 sese region = SCOP_REGION (scop);
2454 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2456 if (!bb_in_sese_p (gimple_bb (use_stmt), region))
2458 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2460 SET_USE (use_p, new_name);
2462 update_stmt (use_stmt);
2467 /* Insert in the empty BB just after the scop a use of DEF such
2468 that the rewrite of cross_bb_scalar_dependences won't insert
2469 arrays everywhere else. */
2472 gimple assign = gimple_build_assign (new_name, def);
2473 gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest);
2475 add_referenced_var (var);
2476 SSA_NAME_DEF_STMT (new_name) = assign;
2477 update_stmt (assign);
2478 gsi_insert_before (&psi, assign, GSI_SAME_STMT);
2482 /* Rewrite the scalar dependences crossing the boundary of the BB
2483 containing STMT with an array. Return true when something has been
2487 rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
2489 sese region = SCOP_REGION (scop);
2490 gimple stmt = gsi_stmt (*gsi);
2491 imm_use_iterator imm_iter;
2494 tree zero_dim_array = NULL_TREE;
2498 switch (gimple_code (stmt))
2501 def = gimple_assign_lhs (stmt);
2505 def = gimple_call_lhs (stmt);
2513 || !is_gimple_reg (def))
2516 if (scev_analyzable_p (def, region))
2518 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2519 tree scev = scalar_evolution_in_region (region, loop, def);
2521 if (tree_contains_chrecs (scev, NULL))
2524 propagate_expr_outside_region (def, scev, region);
2528 def_bb = gimple_bb (stmt);
2530 handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
2532 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2533 if (gimple_code (use_stmt) == GIMPLE_PHI
2536 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2538 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2539 rewrite_close_phi_out_of_ssa (scop, &psi);
2541 rewrite_phi_out_of_ssa (scop, &psi);
2544 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2545 if (gimple_code (use_stmt) != GIMPLE_PHI
2546 && def_bb != gimple_bb (use_stmt)
2547 && !is_gimple_debug (use_stmt)
2550 if (!zero_dim_array)
2552 zero_dim_array = create_zero_dim_array
2553 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2554 insert_out_of_ssa_copy (scop, zero_dim_array, def,
2555 SSA_NAME_DEF_STMT (def));
2559 rewrite_cross_bb_scalar_dependence (scop, zero_dim_array,
2566 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2569 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2572 gimple_stmt_iterator psi;
2573 sese region = SCOP_REGION (scop);
2574 bool changed = false;
2576 /* Create an extra empty BB after the scop. */
2577 split_edge (SESE_EXIT (region));
2580 if (bb_in_sese_p (bb, region))
2581 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2582 changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
2587 update_ssa (TODO_update_ssa);
2588 #ifdef ENABLE_CHECKING
2589 verify_loop_closed_ssa (true);
2594 /* Returns the number of pbbs that are in loops contained in SCOP. */
2597 nb_pbbs_in_loops (scop_p scop)
2603 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2604 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2610 /* Return the number of data references in BB that write in
2614 nb_data_writes_in_bb (basic_block bb)
2617 gimple_stmt_iterator gsi;
2619 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2620 if (gimple_vdef (gsi_stmt (gsi)))
2626 /* Splits at STMT the basic block BB represented as PBB in the
2630 split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt)
2632 edge e1 = split_block (bb, stmt);
2633 new_pbb_from_pbb (scop, pbb, e1->dest);
2637 /* Splits STMT out of its current BB. This is done for reduction
2638 statements for which we want to ignore data dependences. */
2641 split_reduction_stmt (scop_p scop, gimple stmt)
2643 basic_block bb = gimple_bb (stmt);
2644 poly_bb_p pbb = pbb_from_bb (bb);
2645 gimple_bb_p gbb = gbb_from_bb (bb);
2648 data_reference_p dr;
2650 /* Do not split basic blocks with no writes to memory: the reduction
2651 will be the only write to memory. */
2652 if (nb_data_writes_in_bb (bb) == 0)
2655 e1 = split_pbb (scop, pbb, bb, stmt);
2657 /* Split once more only when the reduction stmt is not the only one
2658 left in the original BB. */
2659 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2661 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2663 e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi));
2666 /* A part of the data references will end in a different basic block
2667 after the split: move the DRs from the original GBB to the newly
2669 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
2671 basic_block bb1 = gimple_bb (DR_STMT (dr));
2675 gimple_bb_p gbb1 = gbb_from_bb (bb1);
2676 VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr);
2677 VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i);
2685 /* Return true when stmt is a reduction operation. */
2688 is_reduction_operation_p (gimple stmt)
2690 enum tree_code code;
2692 gcc_assert (is_gimple_assign (stmt));
2693 code = gimple_assign_rhs_code (stmt);
2695 return flag_associative_math
2696 && commutative_tree_code (code)
2697 && associative_tree_code (code);
2700 /* Returns true when PHI contains an argument ARG. */
2703 phi_contains_arg (gimple phi, tree arg)
2707 for (i = 0; i < gimple_phi_num_args (phi); i++)
2708 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2714 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2717 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2721 if (TREE_CODE (arg) != SSA_NAME)
2724 stmt = SSA_NAME_DEF_STMT (arg);
2726 if (gimple_code (stmt) == GIMPLE_NOP
2727 || gimple_code (stmt) == GIMPLE_CALL)
2730 if (gimple_code (stmt) == GIMPLE_PHI)
2732 if (phi_contains_arg (stmt, lhs))
2737 if (!is_gimple_assign (stmt))
2740 if (gimple_num_ops (stmt) == 2)
2741 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2743 if (is_reduction_operation_p (stmt))
2745 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2748 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2754 /* Detect commutative and associative scalar reductions starting at
2755 the STMT. Return the phi node of the reduction cycle, or NULL. */
2758 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2759 VEC (gimple, heap) **in,
2760 VEC (gimple, heap) **out)
2762 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2767 VEC_safe_push (gimple, heap, *in, stmt);
2768 VEC_safe_push (gimple, heap, *out, stmt);
2772 /* Detect commutative and associative scalar reductions starting at
2773 STMT. Return the phi node of the reduction cycle, or NULL. */
2776 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2777 VEC (gimple, heap) **out)
2779 tree lhs = gimple_assign_lhs (stmt);
2781 if (gimple_num_ops (stmt) == 2)
2782 return detect_commutative_reduction_arg (lhs, stmt,
2783 gimple_assign_rhs1 (stmt),
2786 if (is_reduction_operation_p (stmt))
2788 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2789 gimple_assign_rhs1 (stmt),
2792 : detect_commutative_reduction_arg (lhs, stmt,
2793 gimple_assign_rhs2 (stmt),
2800 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2803 follow_inital_value_to_phi (tree arg, tree lhs)
2807 if (!arg || TREE_CODE (arg) != SSA_NAME)
2810 stmt = SSA_NAME_DEF_STMT (arg);
2812 if (gimple_code (stmt) == GIMPLE_PHI
2813 && phi_contains_arg (stmt, lhs))
2820 /* Return the argument of the loop PHI that is the inital value coming
2821 from outside the loop. */
2824 edge_initial_value_for_loop_phi (gimple phi)
2828 for (i = 0; i < gimple_phi_num_args (phi); i++)
2830 edge e = gimple_phi_arg_edge (phi, i);
2832 if (loop_depth (e->src->loop_father)
2833 < loop_depth (e->dest->loop_father))
2840 /* Return the argument of the loop PHI that is the inital value coming
2841 from outside the loop. */
2844 initial_value_for_loop_phi (gimple phi)
2848 for (i = 0; i < gimple_phi_num_args (phi); i++)
2850 edge e = gimple_phi_arg_edge (phi, i);
2852 if (loop_depth (e->src->loop_father)
2853 < loop_depth (e->dest->loop_father))
2854 return gimple_phi_arg_def (phi, i);
2860 /* Detect commutative and associative scalar reductions starting at
2861 the loop closed phi node STMT. Return the phi node of the
2862 reduction cycle, or NULL. */
2865 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2866 VEC (gimple, heap) **out)
2868 if (scalar_close_phi_node_p (stmt))
2870 tree arg = gimple_phi_arg_def (stmt, 0);
2871 gimple def, loop_phi;
2873 if (TREE_CODE (arg) != SSA_NAME)
2876 /* Note that loop close phi nodes should have a single argument
2877 because we translated the representation into a canonical form
2878 before Graphite: see canonicalize_loop_closed_ssa_form. */
2879 gcc_assert (gimple_phi_num_args (stmt) == 1);
2881 def = SSA_NAME_DEF_STMT (arg);
2882 loop_phi = detect_commutative_reduction (def, in, out);
2886 tree lhs = gimple_phi_result (stmt);
2887 tree init = initial_value_for_loop_phi (loop_phi);
2888 gimple phi = follow_inital_value_to_phi (init, lhs);
2890 VEC_safe_push (gimple, heap, *in, loop_phi);
2891 VEC_safe_push (gimple, heap, *out, stmt);
2898 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2899 return detect_commutative_reduction_assign (stmt, in, out);
2904 /* Translate the scalar reduction statement STMT to an array RED
2905 knowing that its recursive phi node is LOOP_PHI. */
2908 translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
2909 gimple stmt, gimple loop_phi)
2911 tree res = gimple_phi_result (loop_phi);
2912 gimple assign = gimple_build_assign (res, red);
2913 gimple_stmt_iterator gsi;
2915 insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
2917 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2918 gsi = gsi_for_stmt (stmt);
2920 insert_stmts (scop, assign, NULL, gsi);
2923 /* Removes the PHI node and resets all the debug stmts that are using
2927 remove_phi (gimple phi)
2929 imm_use_iterator imm_iter;
2931 use_operand_p use_p;
2932 gimple_stmt_iterator gsi;
2933 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2937 def = PHI_RESULT (phi);
2938 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2940 stmt = USE_STMT (use_p);
2942 if (is_gimple_debug (stmt))
2944 gimple_debug_bind_reset_value (stmt);
2945 VEC_safe_push (gimple, heap, update, stmt);
2949 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
2952 VEC_free (gimple, heap, update);
2954 gsi = gsi_for_phi_node (phi);
2955 remove_phi_node (&gsi, false);
2958 /* Rewrite out of SSA the reduction described by the loop phi nodes
2959 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2962 IN: stmt, loop_n, ..., loop_0
2963 OUT: stmt, close_n, ..., close_0
2965 the first element is the reduction statement, and the next elements
2966 are the loop and close phi nodes of each of the outer loops. */
2969 translate_scalar_reduction_to_array (scop_p scop,
2970 VEC (gimple, heap) *in,
2971 VEC (gimple, heap) *out)
2975 tree red = NULL_TREE;
2977 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
2979 gimple close_phi = VEC_index (gimple, out, i);
2983 gimple stmt = loop_phi;
2984 basic_block bb = split_reduction_stmt (scop, stmt);
2985 poly_bb_p pbb = pbb_from_bb (bb);
2986 PBB_IS_REDUCTION (pbb) = true;
2987 gcc_assert (close_phi == loop_phi);
2989 red = create_zero_dim_array
2990 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2991 translate_scalar_reduction_to_array_for_stmt
2992 (scop, red, stmt, VEC_index (gimple, in, 1));
2996 if (i == VEC_length (gimple, in) - 1)
2998 insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi), red,
3000 insert_out_of_ssa_copy_on_edge
3001 (scop, edge_initial_value_for_loop_phi (loop_phi),
3002 red, initial_value_for_loop_phi (loop_phi));
3005 remove_phi (loop_phi);
3006 remove_phi (close_phi);
3010 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3011 true when something has been changed. */
3014 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
3018 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
3019 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
3021 detect_commutative_reduction (close_phi, &in, &out);
3022 res = VEC_length (gimple, in) > 0;
3024 translate_scalar_reduction_to_array (scop, in, out);
3026 VEC_free (gimple, heap, in);
3027 VEC_free (gimple, heap, out);
3031 /* Rewrites all the commutative reductions from LOOP out of SSA.
3032 Returns true when something has been changed. */
3035 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop,
3038 gimple_stmt_iterator gsi;
3039 edge exit = single_exit (loop);
3041 bool changed = false;
3046 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3047 if ((res = gimple_phi_result (gsi_stmt (gsi)))
3048 && is_gimple_reg (res)
3049 && !scev_analyzable_p (res, SCOP_REGION (scop)))
3050 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
3051 (scop, gsi_stmt (gsi));
3056 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3059 rewrite_commutative_reductions_out_of_ssa (scop_p scop)
3063 bool changed = false;
3064 sese region = SCOP_REGION (scop);
3066 FOR_EACH_LOOP (li, loop, 0)
3067 if (loop_in_sese_p (loop, region))
3068 changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop);
3073 gsi_commit_edge_inserts ();
3074 update_ssa (TODO_update_ssa);
3075 #ifdef ENABLE_CHECKING
3076 verify_loop_closed_ssa (true);
3081 /* Java does not initialize long_long_integer_type_node. */
3082 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
3084 /* Can all ivs be represented by a signed integer?
3085 As CLooG might generate negative values in its expressions, signed loop ivs
3086 are required in the backend. */
3089 scop_ivs_can_be_represented (scop_p scop)
3093 gimple_stmt_iterator psi;
3095 FOR_EACH_LOOP (li, loop, 0)
3097 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3100 for (psi = gsi_start_phis (loop->header);
3101 !gsi_end_p (psi); gsi_next (&psi))
3103 gimple phi = gsi_stmt (psi);
3104 tree res = PHI_RESULT (phi);
3105 tree type = TREE_TYPE (res);
3107 if (TYPE_UNSIGNED (type)
3108 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
3118 /* Builds the polyhedral representation for a SESE region. */
3121 build_poly_scop (scop_p scop)
3123 sese region = SCOP_REGION (scop);
3124 graphite_dim_t max_dim;
3126 build_scop_bbs (scop);
3128 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3129 Once CLooG is fixed, remove this guard. Anyways, it makes no
3130 sense to optimize a scop containing only PBBs that do not belong
3132 if (nb_pbbs_in_loops (scop) == 0)
3135 if (!scop_ivs_can_be_represented (scop))
3138 build_sese_loop_nests (region);
3139 build_sese_conditions (region);
3140 find_scop_parameters (scop);
3142 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3143 if (scop_nb_params (scop) > max_dim)
3146 build_scop_iteration_domain (scop);
3147 build_scop_context (scop);
3148 add_conditions_to_constraints (scop);
3150 /* Rewrite out of SSA only after having translated the
3151 representation to the polyhedral representation to avoid scev
3152 analysis failures. That means that these functions will insert
3153 new data references that they create in the right place. */
3154 if (flag_associative_math)
3155 rewrite_commutative_reductions_out_of_ssa (scop);
3156 rewrite_reductions_out_of_ssa (scop);
3157 rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
3159 build_scop_drs (scop);
3161 build_scop_scattering (scop);
3163 /* This SCoP has been translated to the polyhedral
3165 POLY_SCOP_P (scop) = true;