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 /* Check if VAR is used in a phi node, that is no loop header. */
55 var_used_in_not_loop_header_phi_node (tree var)
57 imm_use_iterator imm_iter;
61 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
63 basic_block bb = gimple_bb (stmt);
65 if (gimple_code (stmt) == GIMPLE_PHI
66 && bb->loop_father->header != bb)
73 /* Returns the index of the PHI argument defined in the outermost
77 phi_arg_in_outermost_loop (gimple phi)
79 loop_p loop = gimple_bb (phi)->loop_father;
82 for (i = 0; i < gimple_phi_num_args (phi); i++)
83 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
85 loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
92 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
93 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
96 remove_simple_copy_phi (gimple_stmt_iterator *psi)
98 gimple phi = gsi_stmt (*psi);
99 tree res = gimple_phi_result (phi);
100 size_t entry = phi_arg_in_outermost_loop (phi);
101 tree init = gimple_phi_arg_def (phi, entry);
102 gimple stmt = gimple_build_assign (res, init);
103 edge e = gimple_phi_arg_edge (phi, entry);
105 remove_phi_node (psi, false);
106 gsi_insert_on_edge_immediate (e, stmt);
107 SSA_NAME_DEF_STMT (res) = stmt;
110 /* Removes an invariant phi node at position PSI by inserting on the
111 loop ENTRY edge the assignment RES = INIT. */
114 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
116 gimple phi = gsi_stmt (*psi);
117 loop_p loop = loop_containing_stmt (phi);
118 tree res = gimple_phi_result (phi);
119 tree scev = scalar_evolution_in_region (region, loop, res);
120 size_t entry = phi_arg_in_outermost_loop (phi);
121 edge e = gimple_phi_arg_edge (phi, entry);
125 gimple_stmt_iterator gsi;
127 if (tree_contains_chrecs (scev, NULL))
128 scev = gimple_phi_arg_def (phi, entry);
130 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
131 stmt = gimple_build_assign (res, var);
132 remove_phi_node (psi, false);
135 stmts = gimple_seq_alloc ();
137 gsi = gsi_last (stmts);
138 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
139 gsi_insert_seq_on_edge (e, stmts);
140 gsi_commit_edge_inserts ();
141 SSA_NAME_DEF_STMT (res) = stmt;
144 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
147 simple_copy_phi_p (gimple phi)
151 if (gimple_phi_num_args (phi) != 2)
154 res = gimple_phi_result (phi);
155 return (res == gimple_phi_arg_def (phi, 0)
156 || res == gimple_phi_arg_def (phi, 1));
159 /* Returns true when the phi node at position PSI is a reduction phi
160 node in REGION. Otherwise moves the pointer PSI to the next phi to
164 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
167 gimple phi = gsi_stmt (*psi);
168 tree res = gimple_phi_result (phi);
170 loop = loop_containing_stmt (phi);
172 if (simple_copy_phi_p (phi))
174 /* PRE introduces phi nodes like these, for an example,
175 see id-5.f in the fortran graphite testsuite:
177 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
179 remove_simple_copy_phi (psi);
183 if (scev_analyzable_p (res, region))
185 tree scev = scalar_evolution_in_region (region, loop, res);
187 if (evolution_function_is_invariant_p (scev, loop->num))
188 remove_invariant_phi (region, psi);
195 /* All the other cases are considered reductions. */
199 /* Returns true when BB will be represented in graphite. Return false
200 for the basic blocks that contain code eliminated in the code
201 generation pass: i.e. induction variables and exit conditions. */
204 graphite_stmt_p (sese region, basic_block bb,
205 VEC (data_reference_p, heap) *drs)
207 gimple_stmt_iterator gsi;
208 loop_p loop = bb->loop_father;
210 if (VEC_length (data_reference_p, drs) > 0)
213 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
215 gimple stmt = gsi_stmt (gsi);
217 switch (gimple_code (stmt))
220 /* Control flow expressions can be ignored, as they are
221 represented in the iteration domains and will be
222 regenerated by graphite. */
230 tree var = gimple_assign_lhs (stmt);
232 /* We need these bbs to be able to construct the phi nodes. */
233 if (var_used_in_not_loop_header_phi_node (var))
236 var = scalar_evolution_in_region (region, loop, var);
237 if (chrec_contains_undetermined (var))
251 /* Store the GRAPHITE representation of BB. */
254 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
256 struct gimple_bb *gbb;
258 gbb = XNEW (struct gimple_bb);
261 GBB_DATA_REFS (gbb) = drs;
262 GBB_CONDITIONS (gbb) = NULL;
263 GBB_CONDITION_CASES (gbb) = NULL;
269 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
272 struct data_reference *dr;
274 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
277 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
280 free (bap->alias_set);
289 free_gimple_bb (struct gimple_bb *gbb)
291 free_data_refs_aux (GBB_DATA_REFS (gbb));
292 free_data_refs (GBB_DATA_REFS (gbb));
294 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
295 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
296 GBB_BB (gbb)->aux = 0;
300 /* Deletes all gimple bbs in SCOP. */
303 remove_gbbs_in_scop (scop_p scop)
308 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
309 free_gimple_bb (PBB_BLACK_BOX (pbb));
312 /* Deletes all scops in SCOPS. */
315 free_scops (VEC (scop_p, heap) *scops)
320 FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
322 remove_gbbs_in_scop (scop);
323 free_sese (SCOP_REGION (scop));
327 VEC_free (scop_p, heap, scops);
330 /* Generates a polyhedral black box only if the bb contains interesting
334 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
336 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
337 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
338 gimple_stmt_iterator gsi;
340 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
342 gimple stmt = gsi_stmt (gsi);
343 if (!is_gimple_debug (stmt))
344 graphite_find_data_references_in_stmt (nest, stmt, &drs);
347 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
348 free_data_refs (drs);
350 new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
354 /* Returns true if all predecessors of BB, that are not dominated by BB, are
355 marked in MAP. The predecessors dominated by BB are loop latches and will
356 be handled after BB. */
359 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
364 FOR_EACH_EDGE (e, ei, bb->preds)
365 if (!TEST_BIT (map, e->src->index)
366 && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
372 /* Compare the depth of two basic_block's P1 and P2. */
375 compare_bb_depths (const void *p1, const void *p2)
377 const_basic_block const bb1 = *(const_basic_block const*)p1;
378 const_basic_block const bb2 = *(const_basic_block const*)p2;
379 int d1 = loop_depth (bb1->loop_father);
380 int d2 = loop_depth (bb2->loop_father);
391 /* Sort the basic blocks from DOM such that the first are the ones at
392 a deepest loop level. */
395 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
397 VEC_qsort (basic_block, dom, compare_bb_depths);
400 /* Recursive helper function for build_scops_bbs. */
403 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
405 sese region = SCOP_REGION (scop);
406 VEC (basic_block, heap) *dom;
408 if (TEST_BIT (visited, bb->index)
409 || !bb_in_sese_p (bb, region))
412 try_generate_gimple_bb (scop, bb, reductions);
413 SET_BIT (visited, bb->index);
415 dom = get_dominated_by (CDI_DOMINATORS, bb);
420 graphite_sort_dominated_info (dom);
422 while (!VEC_empty (basic_block, dom))
427 FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
428 if (all_non_dominated_preds_marked_p (dom_bb, visited))
430 build_scop_bbs_1 (scop, visited, dom_bb, reductions);
431 VEC_unordered_remove (basic_block, dom, i);
436 VEC_free (basic_block, heap, dom);
439 /* Gather the basic blocks belonging to the SCOP. */
442 build_scop_bbs (scop_p scop, sbitmap reductions)
444 sbitmap visited = sbitmap_alloc (last_basic_block);
445 sese region = SCOP_REGION (scop);
447 sbitmap_zero (visited);
448 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
449 sbitmap_free (visited);
452 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
453 We generate SCATTERING_DIMENSIONS scattering dimensions.
455 CLooG 0.15.0 and previous versions require, that all
456 scattering functions of one CloogProgram have the same number of
457 scattering dimensions, therefore we allow to specify it. This
458 should be removed in future versions of CLooG.
460 The scattering polyhedron consists of these dimensions: scattering,
461 loop_iterators, parameters.
465 | scattering_dimensions = 5
466 | used_scattering_dimensions = 3
474 | Scattering polyhedron:
476 | scattering: {s1, s2, s3, s4, s5}
477 | loop_iterators: {i}
478 | parameters: {p1, p2}
480 | s1 s2 s3 s4 s5 i p1 p2 1
481 | 1 0 0 0 0 0 0 0 -4 = 0
482 | 0 1 0 0 0 -1 0 0 0 = 0
483 | 0 0 1 0 0 0 0 0 -5 = 0 */
486 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
487 poly_bb_p pbb, int scattering_dimensions)
490 scop_p scop = PBB_SCOP (pbb);
491 int nb_iterators = pbb_dim_iter_domain (pbb);
492 int used_scattering_dimensions = nb_iterators * 2 + 1;
493 int nb_params = scop_nb_params (scop);
495 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
498 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
501 ppl_new_Coefficient (&c);
502 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
503 ppl_new_C_Polyhedron_from_space_dimension
504 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
506 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
508 for (i = 0; i < scattering_dimensions; i++)
510 ppl_Constraint_t cstr;
511 ppl_Linear_Expression_t expr;
513 ppl_new_Linear_Expression_with_dimension (&expr, dim);
515 ppl_assign_Coefficient_from_mpz_t (c, v);
516 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
518 /* Textual order inside this loop. */
521 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
522 ppl_Coefficient_to_mpz_t (c, v);
524 ppl_assign_Coefficient_from_mpz_t (c, v);
525 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
528 /* Iterations of this loop. */
529 else /* if ((i % 2) == 1) */
531 int loop = (i - 1) / 2;
534 ppl_assign_Coefficient_from_mpz_t (c, v);
535 ppl_Linear_Expression_add_to_coefficient
536 (expr, scattering_dimensions + loop, c);
539 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
540 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
541 ppl_delete_Linear_Expression (expr);
542 ppl_delete_Constraint (cstr);
546 ppl_delete_Coefficient (c);
548 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
551 /* Build for BB the static schedule.
553 The static schedule is a Dewey numbering of the abstract syntax
554 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
556 The following example informally defines the static schedule:
575 Static schedules for A to F:
588 build_scop_scattering (scop_p scop)
592 gimple_bb_p previous_gbb = NULL;
593 ppl_Linear_Expression_t static_schedule;
598 ppl_new_Coefficient (&c);
599 ppl_new_Linear_Expression (&static_schedule);
601 /* We have to start schedules at 0 on the first component and
602 because we cannot compare_prefix_loops against a previous loop,
603 prefix will be equal to zero, and that index will be
604 incremented before copying. */
606 ppl_assign_Coefficient_from_mpz_t (c, v);
607 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
609 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
611 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
612 ppl_Linear_Expression_t common;
614 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
617 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
622 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
623 ppl_assign_Linear_Expression_from_Linear_Expression (common,
627 ppl_assign_Coefficient_from_mpz_t (c, v);
628 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
629 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
632 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
634 ppl_delete_Linear_Expression (common);
638 ppl_delete_Coefficient (c);
639 ppl_delete_Linear_Expression (static_schedule);
642 /* Add the value K to the dimension D of the linear expression EXPR. */
645 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
649 ppl_Coefficient_t coef;
651 ppl_new_Coefficient (&coef);
652 ppl_Linear_Expression_coefficient (expr, d, coef);
654 ppl_Coefficient_to_mpz_t (coef, val);
656 mpz_add (val, val, k);
658 ppl_assign_Coefficient_from_mpz_t (coef, val);
659 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
661 ppl_delete_Coefficient (coef);
664 /* In the context of scop S, scan E, the right hand side of a scalar
665 evolution function in loop VAR, and translate it to a linear
669 scan_tree_for_params_right_scev (sese s, tree e, int var,
670 ppl_Linear_Expression_t expr)
674 loop_p loop = get_loop (var);
675 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
678 /* Scalar evolutions should happen in the sese region. */
679 gcc_assert (sese_loop_depth (s, loop) > 0);
681 /* We can not deal with parametric strides like:
687 gcc_assert (TREE_CODE (e) == INTEGER_CST);
690 mpz_set_si (val, int_cst_value (e));
691 add_value_to_dim (l, expr, val);
696 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
697 linear expression EXPR. K is the multiplier of the constant. */
700 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
703 ppl_Coefficient_t coef;
704 int v = int_cst_value (cst);
709 /* Necessary to not get "-1 = 2^n - 1". */
711 mpz_sub_ui (val, val, -v);
713 mpz_add_ui (val, val, v);
715 mpz_mul (val, val, k);
716 ppl_new_Coefficient (&coef);
717 ppl_assign_Coefficient_from_mpz_t (coef, val);
718 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
720 ppl_delete_Coefficient (coef);
723 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
724 Otherwise returns -1. */
727 parameter_index_in_region_1 (tree name, sese region)
732 gcc_assert (TREE_CODE (name) == SSA_NAME);
734 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
741 /* When the parameter NAME is in REGION, returns its index in
742 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
743 and returns the index of NAME. */
746 parameter_index_in_region (tree name, sese region)
750 gcc_assert (TREE_CODE (name) == SSA_NAME);
752 i = parameter_index_in_region_1 (name, region);
756 gcc_assert (SESE_ADD_PARAMS (region));
758 i = VEC_length (tree, SESE_PARAMS (region));
759 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
763 /* In the context of sese S, scan the expression E and translate it to
764 a linear expression C. When parsing a symbolic multiplication, K
765 represents the constant multiplier of an expression containing
769 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
772 if (e == chrec_dont_know)
775 switch (TREE_CODE (e))
777 case POLYNOMIAL_CHREC:
778 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
779 CHREC_VARIABLE (e), c);
780 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
784 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
789 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
791 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
792 mpz_mul (val, val, k);
793 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
797 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
804 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
806 mpz_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
807 mpz_mul (val, val, k);
808 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
812 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
817 case POINTER_PLUS_EXPR:
818 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
819 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
824 ppl_Linear_Expression_t tmp_expr = NULL;
828 ppl_dimension_type dim;
829 ppl_Linear_Expression_space_dimension (c, &dim);
830 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
833 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
834 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
838 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
840 ppl_delete_Linear_Expression (tmp_expr);
848 ppl_Linear_Expression_t tmp_expr = NULL;
852 ppl_dimension_type dim;
853 ppl_Linear_Expression_space_dimension (c, &dim);
854 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
857 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
861 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
863 ppl_delete_Linear_Expression (tmp_expr);
871 ppl_Linear_Expression_t tmp_expr = NULL;
875 ppl_dimension_type dim;
876 ppl_Linear_Expression_space_dimension (c, &dim);
877 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
880 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
884 ppl_Coefficient_t coef;
887 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
889 ppl_delete_Linear_Expression (tmp_expr);
890 mpz_init (minus_one);
891 mpz_set_si (minus_one, -1);
892 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
893 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
894 mpz_clear (minus_one);
895 ppl_delete_Coefficient (coef);
903 ppl_dimension_type p = parameter_index_in_region (e, s);
907 ppl_dimension_type dim;
908 ppl_Linear_Expression_space_dimension (c, &dim);
909 p += dim - sese_nb_params (s);
910 add_value_to_dim (p, c, k);
917 scan_tree_for_params_int (e, c, k);
921 case NON_LVALUE_EXPR:
922 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
931 /* Find parameters with respect to REGION in BB. We are looking in memory
932 access functions, conditions and loop bounds. */
935 find_params_in_bb (sese region, gimple_bb_p gbb)
941 loop_p loop = GBB_BB (gbb)->loop_father;
947 /* Find parameters in the access functions of data references. */
948 FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
949 for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
950 scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
952 /* Find parameters in conditional statements. */
953 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
955 tree lhs = scalar_evolution_in_region (region, loop,
956 gimple_cond_lhs (stmt));
957 tree rhs = scalar_evolution_in_region (region, loop,
958 gimple_cond_rhs (stmt));
960 scan_tree_for_params (region, lhs, NULL, one);
961 scan_tree_for_params (region, rhs, NULL, one);
967 /* Record the parameters used in the SCOP. A variable is a parameter
968 in a scop if it does not vary during the execution of that scop. */
971 find_scop_parameters (scop_p scop)
975 sese region = SCOP_REGION (scop);
982 /* Find the parameters used in the loop bounds. */
983 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
985 tree nb_iters = number_of_latch_executions (loop);
987 if (!chrec_contains_symbols (nb_iters))
990 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
991 scan_tree_for_params (region, nb_iters, NULL, one);
996 /* Find the parameters used in data accesses. */
997 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
998 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1000 scop_set_nb_params (scop, sese_nb_params (region));
1001 SESE_ADD_PARAMS (region) = false;
1003 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1004 (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1007 /* Returns a gimple_bb from BB. */
1009 static inline gimple_bb_p
1010 gbb_from_bb (basic_block bb)
1012 return (gimple_bb_p) bb->aux;
1015 /* Insert in the SCOP context constraints from the estimation of the
1016 number of iterations. UB_EXPR is a linear expression describing
1017 the number of iterations in a loop. This expression is bounded by
1018 the estimation NIT. */
1021 add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
1022 ppl_dimension_type dim,
1023 ppl_Linear_Expression_t ub_expr)
1026 ppl_Linear_Expression_t nb_iters_le;
1027 ppl_Polyhedron_t pol;
1028 ppl_Coefficient_t coef;
1029 ppl_Constraint_t ub;
1031 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1032 ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1035 /* Construct the negated number of last iteration in VAL. */
1037 mpz_set_double_int (val, nit, false);
1038 mpz_sub_ui (val, val, 1);
1041 /* NB_ITERS_LE holds the number of last iteration in
1042 parametrical form. Subtract estimated number of last
1043 iteration and assert that result is not positive. */
1044 ppl_new_Coefficient_from_mpz_t (&coef, val);
1045 ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1046 ppl_delete_Coefficient (coef);
1047 ppl_new_Constraint (&ub, nb_iters_le,
1048 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1049 ppl_Polyhedron_add_constraint (pol, ub);
1051 /* Remove all but last GDIM dimensions from POL to obtain
1052 only the constraints on the parameters. */
1054 graphite_dim_t gdim = scop_nb_params (scop);
1055 ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
1058 for (i = 0; i < dim - gdim; i++)
1061 ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1065 /* Add the constraints on the parameters to the SCoP context. */
1067 ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1069 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1070 (&constraints_ps, pol);
1071 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1072 (SCOP_CONTEXT (scop), constraints_ps);
1073 ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1076 ppl_delete_Polyhedron (pol);
1077 ppl_delete_Linear_Expression (nb_iters_le);
1078 ppl_delete_Constraint (ub);
1082 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1083 the constraints for the surrounding loops. */
1086 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1087 ppl_Polyhedron_t outer_ph, int nb,
1088 ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1091 ppl_Polyhedron_t ph;
1092 tree nb_iters = number_of_latch_executions (loop);
1093 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1094 sese region = SCOP_REGION (scop);
1097 ppl_const_Constraint_System_t pcs;
1098 ppl_dimension_type *map
1099 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1101 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1102 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1103 ppl_Polyhedron_add_constraints (ph, pcs);
1105 for (i = 0; i < (int) nb; i++)
1107 for (i = (int) nb; i < (int) dim - 1; i++)
1111 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1117 ppl_Constraint_t lb;
1118 ppl_Linear_Expression_t lb_expr;
1120 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1121 ppl_set_coef (lb_expr, nb, 1);
1122 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1123 ppl_delete_Linear_Expression (lb_expr);
1124 ppl_Polyhedron_add_constraint (ph, lb);
1125 ppl_delete_Constraint (lb);
1128 if (TREE_CODE (nb_iters) == INTEGER_CST)
1130 ppl_Constraint_t ub;
1131 ppl_Linear_Expression_t ub_expr;
1133 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1135 /* loop_i <= cst_nb_iters */
1136 ppl_set_coef (ub_expr, nb, -1);
1137 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1138 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1139 ppl_Polyhedron_add_constraint (ph, ub);
1140 ppl_delete_Linear_Expression (ub_expr);
1141 ppl_delete_Constraint (ub);
1143 else if (!chrec_contains_undetermined (nb_iters))
1146 ppl_Constraint_t ub;
1147 ppl_Linear_Expression_t ub_expr;
1151 mpz_set_si (one, 1);
1152 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1153 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1154 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1157 if (estimated_loop_iterations (loop, true, &nit))
1158 add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1160 /* loop_i <= expr_nb_iters */
1161 ppl_set_coef (ub_expr, nb, -1);
1162 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1163 ppl_Polyhedron_add_constraint (ph, ub);
1164 ppl_delete_Linear_Expression (ub_expr);
1165 ppl_delete_Constraint (ub);
1170 if (loop->inner && loop_in_sese_p (loop->inner, region))
1171 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1175 && loop_in_sese_p (loop->next, region))
1176 build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1178 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1179 (&domains[loop->num], ph);
1181 ppl_delete_Polyhedron (ph);
1184 /* Returns a linear expression for tree T evaluated in PBB. */
1186 static ppl_Linear_Expression_t
1187 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1190 ppl_Linear_Expression_t res;
1191 ppl_dimension_type dim;
1192 sese region = SCOP_REGION (PBB_SCOP (pbb));
1193 loop_p loop = pbb_loop (pbb);
1195 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1196 ppl_new_Linear_Expression_with_dimension (&res, dim);
1198 t = scalar_evolution_in_region (region, loop, t);
1199 gcc_assert (!automatically_generated_chrec_p (t));
1202 mpz_set_si (one, 1);
1203 scan_tree_for_params (region, t, res, one);
1209 /* Returns the ppl constraint type from the gimple tree code CODE. */
1211 static enum ppl_enum_Constraint_Type
1212 ppl_constraint_type_from_tree_code (enum tree_code code)
1216 /* We do not support LT and GT to be able to work with C_Polyhedron.
1217 As we work on integer polyhedron "a < b" can be expressed by
1224 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1227 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1230 return PPL_CONSTRAINT_TYPE_EQUAL;
1237 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1238 CODE is used as the comparison operator. This allows us to invert the
1239 condition or to handle inequalities. */
1242 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1243 poly_bb_p pbb, enum tree_code code)
1246 ppl_Coefficient_t c;
1247 ppl_Linear_Expression_t left, right;
1248 ppl_Constraint_t cstr;
1249 enum ppl_enum_Constraint_Type type;
1251 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1252 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1254 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1255 the left or the right side of the expression. */
1256 if (code == LT_EXPR)
1260 ppl_new_Coefficient (&c);
1261 ppl_assign_Coefficient_from_mpz_t (c, v);
1262 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1263 ppl_delete_Coefficient (c);
1268 else if (code == GT_EXPR)
1272 ppl_new_Coefficient (&c);
1273 ppl_assign_Coefficient_from_mpz_t (c, v);
1274 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1275 ppl_delete_Coefficient (c);
1281 type = ppl_constraint_type_from_tree_code (code);
1283 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1285 ppl_new_Constraint (&cstr, left, type);
1286 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1288 ppl_delete_Constraint (cstr);
1289 ppl_delete_Linear_Expression (left);
1290 ppl_delete_Linear_Expression (right);
1293 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1294 operator. This allows us to invert the condition or to handle
1298 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1300 if (code == NE_EXPR)
1302 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1303 ppl_Pointset_Powerset_C_Polyhedron_t right;
1304 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1306 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1307 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1308 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1309 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1312 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1315 /* Add conditions to the domain of PBB. */
1318 add_conditions_to_domain (poly_bb_p pbb)
1322 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1324 if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1327 FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1328 switch (gimple_code (stmt))
1332 enum tree_code code = gimple_cond_code (stmt);
1334 /* The conditions for ELSE-branches are inverted. */
1335 if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1336 code = invert_tree_comparison (code, false);
1338 add_condition_to_pbb (pbb, stmt, code);
1343 /* Switch statements are not supported right now - fall throught. */
1351 /* Structure used to pass data to dom_walk. */
1355 VEC (gimple, heap) **conditions, **cases;
1359 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1360 edge between BB and its predecessor is not a loop exit edge, and
1361 the last statement of the single predecessor is a COND_EXPR. */
1364 single_pred_cond_non_loop_exit (basic_block bb)
1366 if (single_pred_p (bb))
1368 edge e = single_pred_edge (bb);
1369 basic_block pred = e->src;
1372 if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1375 stmt = last_stmt (pred);
1377 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1384 /* Call-back for dom_walk executed before visiting the dominated
1388 build_sese_conditions_before (struct dom_walk_data *dw_data,
1391 struct bsc *data = (struct bsc *) dw_data->global_data;
1392 VEC (gimple, heap) **conditions = data->conditions;
1393 VEC (gimple, heap) **cases = data->cases;
1397 if (!bb_in_sese_p (bb, data->region))
1400 stmt = single_pred_cond_non_loop_exit (bb);
1404 edge e = single_pred_edge (bb);
1406 VEC_safe_push (gimple, heap, *conditions, stmt);
1408 if (e->flags & EDGE_TRUE_VALUE)
1409 VEC_safe_push (gimple, heap, *cases, stmt);
1411 VEC_safe_push (gimple, heap, *cases, NULL);
1414 gbb = gbb_from_bb (bb);
1418 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1419 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1423 /* Call-back for dom_walk executed after visiting the dominated
1427 build_sese_conditions_after (struct dom_walk_data *dw_data,
1430 struct bsc *data = (struct bsc *) dw_data->global_data;
1431 VEC (gimple, heap) **conditions = data->conditions;
1432 VEC (gimple, heap) **cases = data->cases;
1434 if (!bb_in_sese_p (bb, data->region))
1437 if (single_pred_cond_non_loop_exit (bb))
1439 VEC_pop (gimple, *conditions);
1440 VEC_pop (gimple, *cases);
1444 /* Record all conditions in REGION. */
1447 build_sese_conditions (sese region)
1449 struct dom_walk_data walk_data;
1450 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1451 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1454 data.conditions = &conditions;
1455 data.cases = &cases;
1456 data.region = region;
1458 walk_data.dom_direction = CDI_DOMINATORS;
1459 walk_data.initialize_block_local_data = NULL;
1460 walk_data.before_dom_children = build_sese_conditions_before;
1461 walk_data.after_dom_children = build_sese_conditions_after;
1462 walk_data.global_data = &data;
1463 walk_data.block_local_data_size = 0;
1465 init_walk_dominator_tree (&walk_data);
1466 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1467 fini_walk_dominator_tree (&walk_data);
1469 VEC_free (gimple, heap, conditions);
1470 VEC_free (gimple, heap, cases);
1473 /* Traverses all the GBBs of the SCOP and add their constraints to the
1474 iteration domains. */
1477 add_conditions_to_constraints (scop_p scop)
1482 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1483 add_conditions_to_domain (pbb);
1486 /* Add constraints on the possible values of parameter P from the type
1490 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1492 ppl_Constraint_t cstr;
1493 ppl_Linear_Expression_t le;
1494 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1495 tree type = TREE_TYPE (parameter);
1496 tree lb = NULL_TREE;
1497 tree ub = NULL_TREE;
1499 if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1500 lb = lower_bound_in_type (type, type);
1502 lb = TYPE_MIN_VALUE (type);
1504 if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1505 ub = upper_bound_in_type (type, type);
1507 ub = TYPE_MAX_VALUE (type);
1511 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1512 ppl_set_coef (le, p, -1);
1513 ppl_set_inhomogeneous_tree (le, lb);
1514 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1515 ppl_Polyhedron_add_constraint (context, cstr);
1516 ppl_delete_Linear_Expression (le);
1517 ppl_delete_Constraint (cstr);
1522 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1523 ppl_set_coef (le, p, -1);
1524 ppl_set_inhomogeneous_tree (le, ub);
1525 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1526 ppl_Polyhedron_add_constraint (context, cstr);
1527 ppl_delete_Linear_Expression (le);
1528 ppl_delete_Constraint (cstr);
1532 /* Build the context of the SCOP. The context usually contains extra
1533 constraints that are added to the iteration domains that constrain
1537 build_scop_context (scop_p scop)
1539 ppl_Polyhedron_t context;
1540 ppl_Pointset_Powerset_C_Polyhedron_t ps;
1541 graphite_dim_t p, n = scop_nb_params (scop);
1543 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1545 for (p = 0; p < n; p++)
1546 add_param_constraints (scop, context, p);
1548 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1550 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1551 (SCOP_CONTEXT (scop), ps);
1553 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1554 ppl_delete_Polyhedron (context);
1557 /* Build the iteration domains: the loops belonging to the current
1558 SCOP, and that vary for the execution of the current basic block.
1559 Returns false if there is no loop in SCOP. */
1562 build_scop_iteration_domain (scop_p scop)
1565 sese region = SCOP_REGION (scop);
1567 ppl_Polyhedron_t ph;
1569 int nb_loops = number_of_loops ();
1570 ppl_Pointset_Powerset_C_Polyhedron_t *domains
1571 = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1573 for (i = 0; i < nb_loops; i++)
1576 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1578 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1579 if (!loop_in_sese_p (loop_outer (loop), region))
1580 build_loop_iteration_domains (scop, loop, ph, 0, domains);
1582 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1583 if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1584 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1585 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1586 domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1588 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1589 (&PBB_DOMAIN (pbb), ph);
1591 for (i = 0; i < nb_loops; i++)
1593 ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1595 ppl_delete_Polyhedron (ph);
1599 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1600 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1601 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1605 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1606 ppl_dimension_type accessp_nb_dims,
1607 ppl_dimension_type dom_nb_dims)
1609 ppl_Linear_Expression_t alias;
1610 ppl_Constraint_t cstr;
1611 int alias_set_num = 0;
1612 base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1614 if (bap && bap->alias_set)
1615 alias_set_num = *(bap->alias_set);
1617 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1619 ppl_set_coef (alias, dom_nb_dims, 1);
1620 ppl_set_inhomogeneous (alias, -alias_set_num);
1621 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1622 ppl_Polyhedron_add_constraint (accesses, cstr);
1624 ppl_delete_Linear_Expression (alias);
1625 ppl_delete_Constraint (cstr);
1628 /* Add to ACCESSES polyhedron equalities defining the access functions
1629 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1630 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1631 PBB is the poly_bb_p that contains the data reference DR. */
1634 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1635 ppl_dimension_type accessp_nb_dims,
1636 ppl_dimension_type dom_nb_dims,
1639 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1641 scop_p scop = PBB_SCOP (pbb);
1642 sese region = SCOP_REGION (scop);
1646 for (i = 0; i < nb_subscripts; i++)
1648 ppl_Linear_Expression_t fn, access;
1649 ppl_Constraint_t cstr;
1650 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1651 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1653 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1654 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1657 scan_tree_for_params (region, afn, fn, v);
1658 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1660 ppl_set_coef (access, subscript, -1);
1661 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1662 ppl_Polyhedron_add_constraint (accesses, cstr);
1664 ppl_delete_Linear_Expression (fn);
1665 ppl_delete_Linear_Expression (access);
1666 ppl_delete_Constraint (cstr);
1672 /* Add constrains representing the size of the accessed data to the
1673 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1674 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1678 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1679 ppl_dimension_type accessp_nb_dims,
1680 ppl_dimension_type dom_nb_dims)
1682 tree ref = DR_REF (dr);
1683 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1685 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1687 ppl_Linear_Expression_t expr;
1688 ppl_Constraint_t cstr;
1689 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1692 if (TREE_CODE (ref) != ARRAY_REF)
1695 low = array_ref_low_bound (ref);
1697 /* subscript - low >= 0 */
1698 if (host_integerp (low, 0))
1700 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1701 ppl_set_coef (expr, subscript, 1);
1703 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1705 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1706 ppl_Polyhedron_add_constraint (accesses, cstr);
1707 ppl_delete_Linear_Expression (expr);
1708 ppl_delete_Constraint (cstr);
1711 high = array_ref_up_bound (ref);
1713 /* high - subscript >= 0 */
1714 if (high && host_integerp (high, 0)
1715 /* 1-element arrays at end of structures may extend over
1716 their declared size. */
1717 && !(array_at_struct_end_p (ref)
1718 && operand_equal_p (low, high, 0)))
1720 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1721 ppl_set_coef (expr, subscript, -1);
1723 ppl_set_inhomogeneous (expr, int_cst_value (high));
1725 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1726 ppl_Polyhedron_add_constraint (accesses, cstr);
1727 ppl_delete_Linear_Expression (expr);
1728 ppl_delete_Constraint (cstr);
1733 /* Build data accesses for DR in PBB. */
1736 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1738 ppl_Polyhedron_t accesses;
1739 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1740 ppl_dimension_type dom_nb_dims;
1741 ppl_dimension_type accessp_nb_dims;
1742 int dr_base_object_set;
1744 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1746 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1748 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1750 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1751 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1752 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1754 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1756 ppl_delete_Polyhedron (accesses);
1758 gcc_assert (dr->aux);
1759 dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1761 new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1762 DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1763 dr, DR_NUM_DIMENSIONS (dr));
1766 /* Write to FILE the alias graph of data references in DIMACS format. */
1769 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1770 VEC (data_reference_p, heap) *drs)
1772 int num_vertex = VEC_length (data_reference_p, drs);
1774 data_reference_p dr1, dr2;
1777 if (num_vertex == 0)
1780 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1781 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1782 if (dr_may_alias_p (dr1, dr2))
1785 fprintf (file, "$\n");
1788 fprintf (file, "c %s\n", comment);
1790 fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1792 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1793 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1794 if (dr_may_alias_p (dr1, dr2))
1795 fprintf (file, "e %d %d\n", i + 1, j + 1);
1800 /* Write to FILE the alias graph of data references in DOT format. */
1803 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1804 VEC (data_reference_p, heap) *drs)
1806 int num_vertex = VEC_length (data_reference_p, drs);
1807 data_reference_p dr1, dr2;
1810 if (num_vertex == 0)
1813 fprintf (file, "$\n");
1816 fprintf (file, "c %s\n", comment);
1818 /* First print all the vertices. */
1819 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1820 fprintf (file, "n%d;\n", i);
1822 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1823 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1824 if (dr_may_alias_p (dr1, dr2))
1825 fprintf (file, "n%d n%d\n", i, j);
1830 /* Write to FILE the alias graph of data references in ECC format. */
1833 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1834 VEC (data_reference_p, heap) *drs)
1836 int num_vertex = VEC_length (data_reference_p, drs);
1837 data_reference_p dr1, dr2;
1840 if (num_vertex == 0)
1843 fprintf (file, "$\n");
1846 fprintf (file, "c %s\n", comment);
1848 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1849 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1850 if (dr_may_alias_p (dr1, dr2))
1851 fprintf (file, "%d %d\n", i, j);
1856 /* Check if DR1 and DR2 are in the same object set. */
1859 dr_same_base_object_p (const struct data_reference *dr1,
1860 const struct data_reference *dr2)
1862 return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1865 /* Uses DFS component number as representative of alias-sets. Also tests for
1866 optimality by verifying if every connected component is a clique. Returns
1867 true (1) if the above test is true, and false (0) otherwise. */
1870 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1872 int num_vertices = VEC_length (data_reference_p, drs);
1873 struct graph *g = new_graph (num_vertices);
1874 data_reference_p dr1, dr2;
1876 int num_connected_components;
1877 int v_indx1, v_indx2, num_vertices_in_component;
1880 struct graph_edge *e;
1881 int this_component_is_clique;
1882 int all_components_are_cliques = 1;
1884 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1885 for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1886 if (dr_may_alias_p (dr1, dr2))
1892 all_vertices = XNEWVEC (int, num_vertices);
1893 vertices = XNEWVEC (int, num_vertices);
1894 for (i = 0; i < num_vertices; i++)
1895 all_vertices[i] = i;
1897 num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1899 for (i = 0; i < g->n_vertices; i++)
1901 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1902 base_alias_pair *bap;
1904 gcc_assert (dr->aux);
1905 bap = (base_alias_pair *)(dr->aux);
1907 bap->alias_set = XNEW (int);
1908 *(bap->alias_set) = g->vertices[i].component + 1;
1911 /* Verify if the DFS numbering results in optimal solution. */
1912 for (i = 0; i < num_connected_components; i++)
1914 num_vertices_in_component = 0;
1915 /* Get all vertices whose DFS component number is the same as i. */
1916 for (j = 0; j < num_vertices; j++)
1917 if (g->vertices[j].component == i)
1918 vertices[num_vertices_in_component++] = j;
1920 /* Now test if the vertices in 'vertices' form a clique, by testing
1921 for edges among each pair. */
1922 this_component_is_clique = 1;
1923 for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1925 for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1927 /* Check if the two vertices are connected by iterating
1928 through all the edges which have one of these are source. */
1929 e = g->vertices[vertices[v_indx2]].pred;
1932 if (e->src == vertices[v_indx1])
1938 this_component_is_clique = 0;
1942 if (!this_component_is_clique)
1943 all_components_are_cliques = 0;
1947 free (all_vertices);
1950 return all_components_are_cliques;
1953 /* Group each data reference in DRS with it's base object set num. */
1956 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1958 int num_vertex = VEC_length (data_reference_p, drs);
1959 struct graph *g = new_graph (num_vertex);
1960 data_reference_p dr1, dr2;
1964 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1965 for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1966 if (dr_same_base_object_p (dr1, dr2))
1972 queue = XNEWVEC (int, num_vertex);
1973 for (i = 0; i < num_vertex; i++)
1976 graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1978 for (i = 0; i < g->n_vertices; i++)
1980 data_reference_p dr = VEC_index (data_reference_p, drs, i);
1981 base_alias_pair *bap;
1983 gcc_assert (dr->aux);
1984 bap = (base_alias_pair *)(dr->aux);
1986 bap->base_obj_set = g->vertices[i].component + 1;
1993 /* Build the data references for PBB. */
1996 build_pbb_drs (poly_bb_p pbb)
1999 data_reference_p dr;
2000 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2002 FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
2003 build_poly_dr (dr, pbb);
2006 /* Dump to file the alias graphs for the data references in DRS. */
2009 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2012 FILE *file_dimacs, *file_ecc, *file_dot;
2014 file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2017 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2018 current_function_name ());
2019 write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2020 fclose (file_dimacs);
2023 file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2026 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2027 current_function_name ());
2028 write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2032 file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2035 snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2036 current_function_name ());
2037 write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2042 /* Build data references in SCOP. */
2045 build_scop_drs (scop_p scop)
2049 data_reference_p dr;
2050 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2052 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2053 for (j = 0; VEC_iterate (data_reference_p,
2054 GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2055 VEC_safe_push (data_reference_p, heap, drs, dr);
2057 FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
2058 dr->aux = XNEW (base_alias_pair);
2060 if (!build_alias_set_optimal_p (drs))
2062 /* TODO: Add support when building alias set is not optimal. */
2066 build_base_obj_set_for_drs (drs);
2068 /* When debugging, enable the following code. This cannot be used
2069 in production compilers. */
2071 dump_alias_graphs (drs);
2073 VEC_free (data_reference_p, heap, drs);
2075 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2076 build_pbb_drs (pbb);
2079 /* Return a gsi at the position of the phi node STMT. */
2081 static gimple_stmt_iterator
2082 gsi_for_phi_node (gimple stmt)
2084 gimple_stmt_iterator psi;
2085 basic_block bb = gimple_bb (stmt);
2087 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2088 if (stmt == gsi_stmt (psi))
2095 /* Insert the assignment "RES := VAR" just after AFTER_STMT. */
2098 insert_out_of_ssa_copy (tree res, tree var, gimple after_stmt)
2102 gimple_stmt_iterator si;
2103 gimple_stmt_iterator gsi;
2105 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2106 stmt = gimple_build_assign (res, var);
2108 stmts = gimple_seq_alloc ();
2109 si = gsi_last (stmts);
2110 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2112 if (gimple_code (after_stmt) == GIMPLE_PHI)
2114 gsi = gsi_after_labels (gimple_bb (after_stmt));
2115 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2119 gsi = gsi_for_stmt (after_stmt);
2120 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2124 /* Insert on edge E the assignment "RES := EXPR". */
2127 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2129 gimple_stmt_iterator gsi;
2131 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2132 gimple stmt = gimple_build_assign (res, var);
2135 stmts = gimple_seq_alloc ();
2137 gsi = gsi_last (stmts);
2138 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2139 gsi_insert_seq_on_edge (e, stmts);
2140 gsi_commit_edge_inserts ();
2143 /* Creates a zero dimension array of the same type as VAR. */
2146 create_zero_dim_array (tree var, const char *base_name)
2148 tree index_type = build_index_type (integer_zero_node);
2149 tree elt_type = TREE_TYPE (var);
2150 tree array_type = build_array_type (elt_type, index_type);
2151 tree base = create_tmp_var (array_type, base_name);
2153 add_referenced_var (base);
2155 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2159 /* Returns true when PHI is a loop close phi node. */
2162 scalar_close_phi_node_p (gimple phi)
2164 if (gimple_code (phi) != GIMPLE_PHI
2165 || !is_gimple_reg (gimple_phi_result (phi)))
2168 /* Note that loop close phi nodes should have a single argument
2169 because we translated the representation into a canonical form
2170 before Graphite: see canonicalize_loop_closed_ssa_form. */
2171 return (gimple_phi_num_args (phi) == 1);
2174 /* For a definition DEF in REGION, propagates the expression EXPR in
2175 all the uses of DEF outside REGION. */
2178 propagate_expr_outside_region (tree def, tree expr, sese region)
2180 imm_use_iterator imm_iter;
2183 bool replaced_once = false;
2185 gcc_assert (TREE_CODE (def) == SSA_NAME);
2187 expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2190 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2191 if (!is_gimple_debug (use_stmt)
2192 && !bb_in_sese_p (gimple_bb (use_stmt), region))
2195 use_operand_p use_p;
2197 FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2198 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2199 && (replaced_once = true))
2200 replace_exp (use_p, expr);
2202 update_stmt (use_stmt);
2207 gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2208 gsi_commit_edge_inserts ();
2212 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2213 dimension array for it. */
2216 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi, sese region)
2218 gimple phi = gsi_stmt (*psi);
2219 tree res = gimple_phi_result (phi);
2220 tree var = SSA_NAME_VAR (res);
2221 basic_block bb = gimple_bb (phi);
2222 gimple_stmt_iterator gsi = gsi_after_labels (bb);
2223 tree arg = gimple_phi_arg_def (phi, 0);
2226 /* Note that loop close phi nodes should have a single argument
2227 because we translated the representation into a canonical form
2228 before Graphite: see canonicalize_loop_closed_ssa_form. */
2229 gcc_assert (gimple_phi_num_args (phi) == 1);
2231 /* The phi node can be a non close phi node, when its argument is
2232 invariant, or a default definition. */
2233 if (is_gimple_min_invariant (arg)
2234 || SSA_NAME_IS_DEFAULT_DEF (arg))
2236 propagate_expr_outside_region (res, arg, region);
2241 else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2243 propagate_expr_outside_region (res, arg, region);
2244 stmt = gimple_build_assign (res, arg);
2245 remove_phi_node (psi, false);
2246 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2247 SSA_NAME_DEF_STMT (res) = stmt;
2251 /* If res is scev analyzable and is not a scalar value, it is safe
2252 to ignore the close phi node: it will be code generated in the
2253 out of Graphite pass. */
2254 else if (scev_analyzable_p (res, region))
2256 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2259 if (!loop_in_sese_p (loop, region))
2261 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2262 scev = scalar_evolution_in_region (region, loop, arg);
2263 scev = compute_overall_effect_of_inner_loop (loop, scev);
2266 scev = scalar_evolution_in_region (region, loop, res);
2268 if (tree_does_not_contain_chrecs (scev))
2269 propagate_expr_outside_region (res, scev, region);
2276 tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2278 stmt = gimple_build_assign (res, zero_dim_array);
2280 if (TREE_CODE (arg) == SSA_NAME)
2281 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2283 insert_out_of_ssa_copy_on_edge (single_pred_edge (bb),
2284 zero_dim_array, arg);
2287 remove_phi_node (psi, false);
2288 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2289 SSA_NAME_DEF_STMT (res) = stmt;
2292 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2293 dimension array for it. */
2296 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2299 gimple phi = gsi_stmt (*psi);
2300 basic_block bb = gimple_bb (phi);
2301 tree res = gimple_phi_result (phi);
2302 tree var = SSA_NAME_VAR (res);
2303 tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2304 gimple_stmt_iterator gsi;
2308 for (i = 0; i < gimple_phi_num_args (phi); i++)
2310 tree arg = gimple_phi_arg_def (phi, i);
2311 edge e = gimple_phi_arg_edge (phi, i);
2313 /* Avoid the insertion of code in the loop latch to please the
2314 pattern matching of the vectorizer. */
2315 if (TREE_CODE (arg) == SSA_NAME
2316 && e->src == bb->loop_father->latch)
2317 insert_out_of_ssa_copy (zero_dim_array, arg, SSA_NAME_DEF_STMT (arg));
2319 insert_out_of_ssa_copy_on_edge (e, zero_dim_array, arg);
2322 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2325 stmts = gimple_seq_alloc ();
2327 stmt = gimple_build_assign (res, var);
2328 remove_phi_node (psi, false);
2329 SSA_NAME_DEF_STMT (res) = stmt;
2331 gsi = gsi_last (stmts);
2332 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2334 gsi = gsi_after_labels (bb);
2335 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2338 /* Rewrite the degenerate phi node at position PSI from the degenerate
2339 form "x = phi (y, y, ..., y)" to "x = y". */
2342 rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2346 gimple_stmt_iterator gsi;
2347 gimple phi = gsi_stmt (*psi);
2348 tree res = gimple_phi_result (phi);
2351 bb = gimple_bb (phi);
2352 rhs = degenerate_phi_result (phi);
2355 stmt = gimple_build_assign (res, rhs);
2356 remove_phi_node (psi, false);
2357 SSA_NAME_DEF_STMT (res) = stmt;
2359 gsi = gsi_after_labels (bb);
2360 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2363 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2366 rewrite_reductions_out_of_ssa (scop_p scop)
2369 gimple_stmt_iterator psi;
2370 sese region = SCOP_REGION (scop);
2373 if (bb_in_sese_p (bb, region))
2374 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2376 gimple phi = gsi_stmt (psi);
2378 if (!is_gimple_reg (gimple_phi_result (phi)))
2384 if (gimple_phi_num_args (phi) > 1
2385 && degenerate_phi_result (phi))
2386 rewrite_degenerate_phi (&psi);
2388 else if (scalar_close_phi_node_p (phi))
2389 rewrite_close_phi_out_of_ssa (&psi, region);
2391 else if (reduction_phi_p (region, &psi))
2392 rewrite_phi_out_of_ssa (&psi);
2395 update_ssa (TODO_update_ssa);
2396 #ifdef ENABLE_CHECKING
2397 verify_loop_closed_ssa (true);
2401 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2402 read from ZERO_DIM_ARRAY. */
2405 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2407 tree var = SSA_NAME_VAR (def);
2408 gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2409 tree name = make_ssa_name (var, name_stmt);
2411 use_operand_p use_p;
2412 gimple_stmt_iterator gsi;
2414 gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2416 gimple_assign_set_lhs (name_stmt, name);
2418 gsi = gsi_for_stmt (use_stmt);
2419 gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2421 FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2422 if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2423 replace_exp (use_p, name);
2425 update_stmt (use_stmt);
2428 /* Rewrite the scalar dependences crossing the boundary of the BB
2429 containing STMT with an array. Return true when something has been
2433 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2435 gimple stmt = gsi_stmt (*gsi);
2436 imm_use_iterator imm_iter;
2439 tree zero_dim_array = NULL_TREE;
2443 switch (gimple_code (stmt))
2446 def = gimple_assign_lhs (stmt);
2450 def = gimple_call_lhs (stmt);
2458 || !is_gimple_reg (def))
2461 if (scev_analyzable_p (def, region))
2463 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2464 tree scev = scalar_evolution_in_region (region, loop, def);
2466 if (tree_contains_chrecs (scev, NULL))
2469 propagate_expr_outside_region (def, scev, region);
2473 def_bb = gimple_bb (stmt);
2475 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2476 if (gimple_code (use_stmt) == GIMPLE_PHI
2479 gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2481 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2482 rewrite_close_phi_out_of_ssa (&psi, region);
2484 rewrite_phi_out_of_ssa (&psi);
2487 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2488 if (gimple_code (use_stmt) != GIMPLE_PHI
2489 && def_bb != gimple_bb (use_stmt)
2490 && !is_gimple_debug (use_stmt)
2493 if (!zero_dim_array)
2495 zero_dim_array = create_zero_dim_array
2496 (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2497 insert_out_of_ssa_copy (zero_dim_array, def,
2498 SSA_NAME_DEF_STMT (def));
2502 rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2508 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2511 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2514 gimple_stmt_iterator psi;
2515 sese region = SCOP_REGION (scop);
2516 bool changed = false;
2519 if (bb_in_sese_p (bb, region))
2520 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2521 changed |= rewrite_cross_bb_scalar_deps (region, &psi);
2526 update_ssa (TODO_update_ssa);
2527 #ifdef ENABLE_CHECKING
2528 verify_loop_closed_ssa (true);
2533 /* Returns the number of pbbs that are in loops contained in SCOP. */
2536 nb_pbbs_in_loops (scop_p scop)
2542 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2543 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2549 /* Return the number of data references in BB that write in
2553 nb_data_writes_in_bb (basic_block bb)
2556 gimple_stmt_iterator gsi;
2558 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2559 if (gimple_vdef (gsi_stmt (gsi)))
2565 /* Splits STMT out of its current BB. */
2568 split_reduction_stmt (gimple stmt)
2570 gimple_stmt_iterator gsi;
2571 basic_block bb = gimple_bb (stmt);
2574 /* Do not split basic blocks with no writes to memory: the reduction
2575 will be the only write to memory. */
2576 if (nb_data_writes_in_bb (bb) == 0)
2579 split_block (bb, stmt);
2581 if (gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2584 gsi = gsi_last_bb (bb);
2586 e = split_block (bb, gsi_stmt (gsi));
2591 /* Return true when stmt is a reduction operation. */
2594 is_reduction_operation_p (gimple stmt)
2596 enum tree_code code;
2598 gcc_assert (is_gimple_assign (stmt));
2599 code = gimple_assign_rhs_code (stmt);
2601 return flag_associative_math
2602 && commutative_tree_code (code)
2603 && associative_tree_code (code);
2606 /* Returns true when PHI contains an argument ARG. */
2609 phi_contains_arg (gimple phi, tree arg)
2613 for (i = 0; i < gimple_phi_num_args (phi); i++)
2614 if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2620 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2623 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2627 if (TREE_CODE (arg) != SSA_NAME)
2630 stmt = SSA_NAME_DEF_STMT (arg);
2632 if (gimple_code (stmt) == GIMPLE_NOP
2633 || gimple_code (stmt) == GIMPLE_CALL)
2636 if (gimple_code (stmt) == GIMPLE_PHI)
2638 if (phi_contains_arg (stmt, lhs))
2643 if (!is_gimple_assign (stmt))
2646 if (gimple_num_ops (stmt) == 2)
2647 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2649 if (is_reduction_operation_p (stmt))
2651 gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2654 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2660 /* Detect commutative and associative scalar reductions starting at
2661 the STMT. Return the phi node of the reduction cycle, or NULL. */
2664 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2665 VEC (gimple, heap) **in,
2666 VEC (gimple, heap) **out)
2668 gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2673 VEC_safe_push (gimple, heap, *in, stmt);
2674 VEC_safe_push (gimple, heap, *out, stmt);
2678 /* Detect commutative and associative scalar reductions starting at
2679 STMT. Return the phi node of the reduction cycle, or NULL. */
2682 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2683 VEC (gimple, heap) **out)
2685 tree lhs = gimple_assign_lhs (stmt);
2687 if (gimple_num_ops (stmt) == 2)
2688 return detect_commutative_reduction_arg (lhs, stmt,
2689 gimple_assign_rhs1 (stmt),
2692 if (is_reduction_operation_p (stmt))
2694 gimple res = detect_commutative_reduction_arg (lhs, stmt,
2695 gimple_assign_rhs1 (stmt),
2698 : detect_commutative_reduction_arg (lhs, stmt,
2699 gimple_assign_rhs2 (stmt),
2706 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2709 follow_inital_value_to_phi (tree arg, tree lhs)
2713 if (!arg || TREE_CODE (arg) != SSA_NAME)
2716 stmt = SSA_NAME_DEF_STMT (arg);
2718 if (gimple_code (stmt) == GIMPLE_PHI
2719 && phi_contains_arg (stmt, lhs))
2726 /* Return the argument of the loop PHI that is the inital value coming
2727 from outside the loop. */
2730 edge_initial_value_for_loop_phi (gimple phi)
2734 for (i = 0; i < gimple_phi_num_args (phi); i++)
2736 edge e = gimple_phi_arg_edge (phi, i);
2738 if (loop_depth (e->src->loop_father)
2739 < loop_depth (e->dest->loop_father))
2746 /* Return the argument of the loop PHI that is the inital value coming
2747 from outside the loop. */
2750 initial_value_for_loop_phi (gimple phi)
2754 for (i = 0; i < gimple_phi_num_args (phi); i++)
2756 edge e = gimple_phi_arg_edge (phi, i);
2758 if (loop_depth (e->src->loop_father)
2759 < loop_depth (e->dest->loop_father))
2760 return gimple_phi_arg_def (phi, i);
2766 /* Detect commutative and associative scalar reductions starting at
2767 the loop closed phi node STMT. Return the phi node of the
2768 reduction cycle, or NULL. */
2771 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2772 VEC (gimple, heap) **out)
2774 if (scalar_close_phi_node_p (stmt))
2776 tree arg = gimple_phi_arg_def (stmt, 0);
2777 gimple def, loop_phi;
2779 if (TREE_CODE (arg) != SSA_NAME)
2782 /* Note that loop close phi nodes should have a single argument
2783 because we translated the representation into a canonical form
2784 before Graphite: see canonicalize_loop_closed_ssa_form. */
2785 gcc_assert (gimple_phi_num_args (stmt) == 1);
2787 def = SSA_NAME_DEF_STMT (arg);
2788 loop_phi = detect_commutative_reduction (def, in, out);
2792 tree lhs = gimple_phi_result (stmt);
2793 tree init = initial_value_for_loop_phi (loop_phi);
2794 gimple phi = follow_inital_value_to_phi (init, lhs);
2796 VEC_safe_push (gimple, heap, *in, loop_phi);
2797 VEC_safe_push (gimple, heap, *out, stmt);
2804 if (gimple_code (stmt) == GIMPLE_ASSIGN)
2805 return detect_commutative_reduction_assign (stmt, in, out);
2810 /* Translate the scalar reduction statement STMT to an array RED
2811 knowing that its recursive phi node is LOOP_PHI. */
2814 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2817 gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2818 tree res = gimple_phi_result (loop_phi);
2819 gimple assign = gimple_build_assign (res, red);
2821 gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2823 insert_gsi = gsi_after_labels (gimple_bb (stmt));
2824 assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2825 insert_gsi = gsi_for_stmt (stmt);
2826 gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2829 /* Removes the PHI node and resets all the debug stmts that are using
2833 remove_phi (gimple phi)
2835 imm_use_iterator imm_iter;
2837 use_operand_p use_p;
2838 gimple_stmt_iterator gsi;
2839 VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2843 def = PHI_RESULT (phi);
2844 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2846 stmt = USE_STMT (use_p);
2848 if (is_gimple_debug (stmt))
2850 gimple_debug_bind_reset_value (stmt);
2851 VEC_safe_push (gimple, heap, update, stmt);
2855 FOR_EACH_VEC_ELT (gimple, update, i, stmt)
2858 VEC_free (gimple, heap, update);
2860 gsi = gsi_for_phi_node (phi);
2861 remove_phi_node (&gsi, false);
2864 /* Rewrite out of SSA the reduction described by the loop phi nodes
2865 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2868 IN: stmt, loop_n, ..., loop_0
2869 OUT: stmt, close_n, ..., close_0
2871 the first element is the reduction statement, and the next elements
2872 are the loop and close phi nodes of each of the outer loops. */
2875 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2876 VEC (gimple, heap) *out,
2881 tree red = NULL_TREE;
2883 FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
2885 gimple close_phi = VEC_index (gimple, out, i);
2889 gimple stmt = loop_phi;
2890 basic_block bb = split_reduction_stmt (stmt);
2892 SET_BIT (reductions, bb->index);
2893 gcc_assert (close_phi == loop_phi);
2895 red = create_zero_dim_array
2896 (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2897 translate_scalar_reduction_to_array_for_stmt
2898 (red, stmt, VEC_index (gimple, in, 1));
2902 if (i == VEC_length (gimple, in) - 1)
2904 insert_out_of_ssa_copy (gimple_phi_result (close_phi), red,
2906 insert_out_of_ssa_copy_on_edge
2907 (edge_initial_value_for_loop_phi (loop_phi),
2908 red, initial_value_for_loop_phi (loop_phi));
2911 remove_phi (loop_phi);
2912 remove_phi (close_phi);
2916 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
2917 true when something has been changed. */
2920 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2924 VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2925 VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2927 detect_commutative_reduction (close_phi, &in, &out);
2928 res = VEC_length (gimple, in) > 0;
2930 translate_scalar_reduction_to_array (in, out, reductions);
2932 VEC_free (gimple, heap, in);
2933 VEC_free (gimple, heap, out);
2937 /* Rewrites all the commutative reductions from LOOP out of SSA.
2938 Returns true when something has been changed. */
2941 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2945 gimple_stmt_iterator gsi;
2946 edge exit = single_exit (loop);
2948 bool changed = false;
2953 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2954 if ((res = gimple_phi_result (gsi_stmt (gsi)))
2955 && is_gimple_reg (res)
2956 && !scev_analyzable_p (res, region))
2957 changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
2958 (gsi_stmt (gsi), reductions);
2963 /* Rewrites all the commutative reductions from SCOP out of SSA. */
2966 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2970 bool changed = false;
2972 if (!flag_associative_math)
2975 FOR_EACH_LOOP (li, loop, 0)
2976 if (loop_in_sese_p (loop, region))
2977 changed |= rewrite_commutative_reductions_out_of_ssa_loop (loop,
2984 gsi_commit_edge_inserts ();
2985 update_ssa (TODO_update_ssa);
2986 #ifdef ENABLE_CHECKING
2987 verify_loop_closed_ssa (true);
2992 /* Java does not initialize long_long_integer_type_node. */
2993 #define my_long_long (long_long_integer_type_node ? long_long_integer_type_node : ssizetype)
2995 /* Can all ivs be represented by a signed integer?
2996 As CLooG might generate negative values in its expressions, signed loop ivs
2997 are required in the backend. */
3000 scop_ivs_can_be_represented (scop_p scop)
3004 gimple_stmt_iterator psi;
3006 FOR_EACH_LOOP (li, loop, 0)
3008 if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3011 for (psi = gsi_start_phis (loop->header);
3012 !gsi_end_p (psi); gsi_next (&psi))
3014 gimple phi = gsi_stmt (psi);
3015 tree res = PHI_RESULT (phi);
3016 tree type = TREE_TYPE (res);
3018 if (TYPE_UNSIGNED (type)
3019 && TYPE_PRECISION (type) >= TYPE_PRECISION (my_long_long))
3029 /* Builds the polyhedral representation for a SESE region. */
3032 build_poly_scop (scop_p scop)
3034 sese region = SCOP_REGION (scop);
3035 graphite_dim_t max_dim;
3038 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3039 Once CLooG is fixed, remove this guard. Anyways, it makes no
3040 sense to optimize a scop containing only PBBs that do not belong
3042 if (nb_pbbs_in_loops (scop) == 0)
3045 if (!scop_ivs_can_be_represented (scop))
3048 build_sese_loop_nests (region);
3049 build_sese_conditions (region);
3050 find_scop_parameters (scop);
3052 max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3053 if (scop_nb_params (scop) > max_dim)
3056 build_scop_iteration_domain (scop);
3057 build_scop_context (scop);
3059 add_conditions_to_constraints (scop);
3061 build_scop_scattering (scop);
3062 build_scop_drs (scop);
3064 /* This SCoP has been translated to the polyhedral
3066 POLY_SCOP_P (scop) = true;