1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
35 #include "tree-chrec.h"
36 #include "tree-data-ref.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-pass.h"
40 #include "value-prof.h"
41 #include "pointer-set.h"
46 #include "cloog/cloog.h"
48 #include "graphite-ppl.h"
50 #include "graphite-poly.h"
51 #include "graphite-scop-detection.h"
52 #include "graphite-clast-to-gimple.h"
53 #include "graphite-sese-to-poly.h"
55 /* Check if VAR is used in a phi node, that is no loop header. */
58 var_used_in_not_loop_header_phi_node (tree var)
61 imm_use_iterator imm_iter;
65 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
67 basic_block bb = gimple_bb (stmt);
69 if (gimple_code (stmt) == GIMPLE_PHI
70 && bb->loop_father->header != bb)
77 /* Returns the index of the phi argument corresponding to the initial
81 loop_entry_phi_arg (gimple phi)
83 loop_p loop = gimple_bb (phi)->loop_father;
86 for (i = 0; i < gimple_phi_num_args (phi); i++)
87 if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
94 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
95 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
98 remove_simple_copy_phi (gimple_stmt_iterator *psi)
100 gimple phi = gsi_stmt (*psi);
101 tree res = gimple_phi_result (phi);
102 size_t entry = loop_entry_phi_arg (phi);
103 tree init = gimple_phi_arg_def (phi, entry);
104 gimple stmt = gimple_build_assign (res, init);
105 edge e = gimple_phi_arg_edge (phi, entry);
107 remove_phi_node (psi, false);
108 gsi_insert_on_edge_immediate (e, stmt);
109 SSA_NAME_DEF_STMT (res) = stmt;
112 /* Removes an invariant phi node at position PSI by inserting on the
113 loop ENTRY edge the assignment RES = INIT. */
116 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
118 gimple phi = gsi_stmt (*psi);
119 loop_p loop = loop_containing_stmt (phi);
120 tree res = gimple_phi_result (phi);
121 tree scev = scalar_evolution_in_region (region, loop, res);
122 size_t entry = loop_entry_phi_arg (phi);
123 edge e = gimple_phi_arg_edge (phi, entry);
127 gimple_stmt_iterator gsi;
129 if (tree_contains_chrecs (scev, NULL))
130 scev = gimple_phi_arg_def (phi, entry);
132 var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
133 stmt = gimple_build_assign (res, var);
134 remove_phi_node (psi, false);
137 stmts = gimple_seq_alloc ();
139 gsi = gsi_last (stmts);
140 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
141 gsi_insert_seq_on_edge (e, stmts);
142 gsi_commit_edge_inserts ();
143 SSA_NAME_DEF_STMT (res) = stmt;
146 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
149 simple_copy_phi_p (gimple phi)
153 if (gimple_phi_num_args (phi) != 2)
156 res = gimple_phi_result (phi);
157 return (res == gimple_phi_arg_def (phi, 0)
158 || res == gimple_phi_arg_def (phi, 1));
161 /* Returns true when the phi node at position PSI is a reduction phi
162 node in REGION. Otherwise moves the pointer PSI to the next phi to
166 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
171 gimple phi = gsi_stmt (*psi);
172 tree res = gimple_phi_result (phi);
174 if (!is_gimple_reg (res))
180 loop = loop_containing_stmt (phi);
182 if (simple_copy_phi_p (phi))
184 /* FIXME: PRE introduces phi nodes like these, for an example,
185 see id-5.f in the fortran graphite testsuite:
187 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
189 remove_simple_copy_phi (psi);
193 /* Main induction variables with constant strides in LOOP are not
195 if (simple_iv (loop, loop, res, &iv, true))
201 scev = scalar_evolution_in_region (region, loop, res);
202 if (chrec_contains_undetermined (scev))
205 if (evolution_function_is_invariant_p (scev, loop->num))
207 remove_invariant_phi (region, psi);
211 /* All the other cases are considered reductions. */
215 /* Returns true when BB will be represented in graphite. Return false
216 for the basic blocks that contain code eliminated in the code
217 generation pass: i.e. induction variables and exit conditions. */
220 graphite_stmt_p (sese region, basic_block bb,
221 VEC (data_reference_p, heap) *drs)
223 gimple_stmt_iterator gsi;
224 loop_p loop = bb->loop_father;
226 if (VEC_length (data_reference_p, drs) > 0)
229 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
231 gimple stmt = gsi_stmt (gsi);
233 switch (gimple_code (stmt))
236 /* Control flow expressions can be ignored, as they are
237 represented in the iteration domains and will be
238 regenerated by graphite. */
246 tree var = gimple_assign_lhs (stmt);
248 /* We need these bbs to be able to construct the phi nodes. */
249 if (var_used_in_not_loop_header_phi_node (var))
252 var = scalar_evolution_in_region (region, loop, var);
253 if (chrec_contains_undetermined (var))
267 /* Store the GRAPHITE representation of BB. */
270 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
272 struct gimple_bb *gbb;
274 gbb = XNEW (struct gimple_bb);
277 GBB_DATA_REFS (gbb) = drs;
278 GBB_CONDITIONS (gbb) = NULL;
279 GBB_CONDITION_CASES (gbb) = NULL;
280 GBB_CLOOG_IV_TYPES (gbb) = NULL;
288 free_gimple_bb (struct gimple_bb *gbb)
290 if (GBB_CLOOG_IV_TYPES (gbb))
291 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
293 free_data_refs (GBB_DATA_REFS (gbb));
295 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
296 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
297 GBB_BB (gbb)->aux = 0;
301 /* Deletes all gimple bbs in SCOP. */
304 remove_gbbs_in_scop (scop_p scop)
309 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
310 free_gimple_bb (PBB_BLACK_BOX (pbb));
313 /* Deletes all scops in SCOPS. */
316 free_scops (VEC (scop_p, heap) *scops)
321 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
323 remove_gbbs_in_scop (scop);
324 free_sese (SCOP_REGION (scop));
328 VEC_free (scop_p, heap, scops);
331 /* Generates a polyhedral black box only if the bb contains interesting
335 try_generate_gimple_bb (scop_p scop, basic_block bb)
337 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
338 loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
339 gimple_stmt_iterator gsi;
341 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
343 gimple stmt = gsi_stmt (gsi);
344 if (!is_gimple_debug (stmt))
345 graphite_find_data_references_in_stmt (nest, stmt, &drs);
348 if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
349 free_data_refs (drs);
351 new_poly_bb (scop, new_gimple_bb (bb, drs));
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 size_t len = VEC_length (basic_block, dom);
399 qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
403 /* Recursive helper function for build_scops_bbs. */
406 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
408 sese region = SCOP_REGION (scop);
409 VEC (basic_block, heap) *dom;
411 if (TEST_BIT (visited, bb->index)
412 || !bb_in_sese_p (bb, region))
415 try_generate_gimple_bb (scop, bb);
416 SET_BIT (visited, bb->index);
418 dom = get_dominated_by (CDI_DOMINATORS, bb);
423 graphite_sort_dominated_info (dom);
425 while (!VEC_empty (basic_block, dom))
430 for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
431 if (all_non_dominated_preds_marked_p (dom_bb, visited))
433 build_scop_bbs_1 (scop, visited, dom_bb);
434 VEC_unordered_remove (basic_block, dom, i);
439 VEC_free (basic_block, heap, dom);
442 /* Gather the basic blocks belonging to the SCOP. */
445 build_scop_bbs (scop_p scop)
447 sbitmap visited = sbitmap_alloc (last_basic_block);
448 sese region = SCOP_REGION (scop);
450 sbitmap_zero (visited);
451 build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
453 sbitmap_free (visited);
456 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
457 We generate SCATTERING_DIMENSIONS scattering dimensions.
459 CLooG 0.15.0 and previous versions require, that all
460 scattering functions of one CloogProgram have the same number of
461 scattering dimensions, therefore we allow to specify it. This
462 should be removed in future versions of CLooG.
464 The scattering polyhedron consists of these dimensions: scattering,
465 loop_iterators, parameters.
469 | scattering_dimensions = 5
470 | used_scattering_dimensions = 3
478 | Scattering polyhedron:
480 | scattering: {s1, s2, s3, s4, s5}
481 | loop_iterators: {i}
482 | parameters: {p1, p2}
484 | s1 s2 s3 s4 s5 i p1 p2 1
485 | 1 0 0 0 0 0 0 0 -4 = 0
486 | 0 1 0 0 0 -1 0 0 0 = 0
487 | 0 0 1 0 0 0 0 0 -5 = 0 */
490 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
491 poly_bb_p pbb, int scattering_dimensions)
494 scop_p scop = PBB_SCOP (pbb);
495 int nb_iterators = pbb_dim_iter_domain (pbb);
496 int used_scattering_dimensions = nb_iterators * 2 + 1;
497 int nb_params = scop_nb_params (scop);
499 ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
502 gcc_assert (scattering_dimensions >= used_scattering_dimensions);
505 ppl_new_Coefficient (&c);
506 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
507 ppl_new_C_Polyhedron_from_space_dimension
508 (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
510 PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
512 for (i = 0; i < scattering_dimensions; i++)
514 ppl_Constraint_t cstr;
515 ppl_Linear_Expression_t expr;
517 ppl_new_Linear_Expression_with_dimension (&expr, dim);
519 ppl_assign_Coefficient_from_mpz_t (c, v);
520 ppl_Linear_Expression_add_to_coefficient (expr, i, c);
522 /* Textual order inside this loop. */
525 ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
526 ppl_Coefficient_to_mpz_t (c, v);
528 ppl_assign_Coefficient_from_mpz_t (c, v);
529 ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
532 /* Iterations of this loop. */
533 else /* if ((i % 2) == 1) */
535 int loop = (i - 1) / 2;
537 value_set_si (v, -1);
538 ppl_assign_Coefficient_from_mpz_t (c, v);
539 ppl_Linear_Expression_add_to_coefficient
540 (expr, scattering_dimensions + loop, c);
543 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
544 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
545 ppl_delete_Linear_Expression (expr);
546 ppl_delete_Constraint (cstr);
550 ppl_delete_Coefficient (c);
552 PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
555 /* Build for BB the static schedule.
557 The static schedule is a Dewey numbering of the abstract syntax
558 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
560 The following example informally defines the static schedule:
579 Static schedules for A to F:
592 build_scop_scattering (scop_p scop)
596 gimple_bb_p previous_gbb = NULL;
597 ppl_Linear_Expression_t static_schedule;
602 ppl_new_Coefficient (&c);
603 ppl_new_Linear_Expression (&static_schedule);
605 /* We have to start schedules at 0 on the first component and
606 because we cannot compare_prefix_loops against a previous loop,
607 prefix will be equal to zero, and that index will be
608 incremented before copying. */
609 value_set_si (v, -1);
610 ppl_assign_Coefficient_from_mpz_t (c, v);
611 ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
613 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
615 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
616 ppl_Linear_Expression_t common;
618 int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
621 prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
626 ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
627 ppl_assign_Linear_Expression_from_Linear_Expression (common,
631 ppl_assign_Coefficient_from_mpz_t (c, v);
632 ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
633 ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
636 build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
638 ppl_delete_Linear_Expression (common);
642 ppl_delete_Coefficient (c);
643 ppl_delete_Linear_Expression (static_schedule);
646 /* Add the value K to the dimension D of the linear expression EXPR. */
649 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
653 ppl_Coefficient_t coef;
655 ppl_new_Coefficient (&coef);
656 ppl_Linear_Expression_coefficient (expr, d, coef);
658 ppl_Coefficient_to_mpz_t (coef, val);
660 value_addto (val, val, k);
662 ppl_assign_Coefficient_from_mpz_t (coef, val);
663 ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
665 ppl_delete_Coefficient (coef);
668 /* In the context of scop S, scan E, the right hand side of a scalar
669 evolution function in loop VAR, and translate it to a linear
673 scan_tree_for_params_right_scev (sese s, tree e, int var,
674 ppl_Linear_Expression_t expr)
678 loop_p loop = get_loop (var);
679 ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
682 /* Scalar evolutions should happen in the sese region. */
683 gcc_assert (sese_loop_depth (s, loop) > 0);
685 /* We can not deal with parametric strides like:
691 gcc_assert (TREE_CODE (e) == INTEGER_CST);
694 value_set_si (val, int_cst_value (e));
695 add_value_to_dim (l, expr, val);
700 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
701 linear expression EXPR. K is the multiplier of the constant. */
704 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
707 ppl_Coefficient_t coef;
708 int v = int_cst_value (cst);
711 value_set_si (val, 0);
713 /* Necessary to not get "-1 = 2^n - 1". */
715 value_sub_int (val, val, -v);
717 value_add_int (val, val, v);
719 value_multiply (val, val, k);
720 ppl_new_Coefficient (&coef);
721 ppl_assign_Coefficient_from_mpz_t (coef, val);
722 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
724 ppl_delete_Coefficient (coef);
727 /* Saves in NV at index I a new name for variable P. */
730 save_var_name (char **nv, int i, tree p)
732 const char *name = get_name (SSA_NAME_VAR (p));
736 int len = strlen (name) + 16;
737 nv[i] = XNEWVEC (char, len);
738 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p));
742 nv[i] = XNEWVEC (char, 16);
743 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p));
747 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
748 Otherwise returns -1. */
751 parameter_index_in_region_1 (tree name, sese region)
756 gcc_assert (TREE_CODE (name) == SSA_NAME);
758 for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
765 /* When the parameter NAME is in REGION, returns its index in
766 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
767 and returns the index of NAME. */
770 parameter_index_in_region (tree name, sese region)
774 gcc_assert (TREE_CODE (name) == SSA_NAME);
776 i = parameter_index_in_region_1 (name, region);
780 gcc_assert (SESE_ADD_PARAMS (region));
782 i = VEC_length (tree, SESE_PARAMS (region));
783 save_var_name (SESE_PARAMS_NAMES (region), i, name);
784 save_clast_name_index (SESE_PARAMS_INDEX (region),
785 SESE_PARAMS_NAMES (region)[i], i);
786 VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
790 /* In the context of sese S, scan the expression E and translate it to
791 a linear expression C. When parsing a symbolic multiplication, K
792 represents the constant multiplier of an expression containing
796 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
799 if (e == chrec_dont_know)
802 switch (TREE_CODE (e))
804 case POLYNOMIAL_CHREC:
805 scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
806 CHREC_VARIABLE (e), c);
807 scan_tree_for_params (s, CHREC_LEFT (e), c, k);
811 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
816 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
818 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
819 value_multiply (val, val, k);
820 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
824 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
831 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
833 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
834 value_multiply (val, val, k);
835 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
839 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
844 case POINTER_PLUS_EXPR:
845 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
846 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
851 ppl_Linear_Expression_t tmp_expr = NULL;
855 ppl_dimension_type dim;
856 ppl_Linear_Expression_space_dimension (c, &dim);
857 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
860 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
861 scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
865 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
867 ppl_delete_Linear_Expression (tmp_expr);
875 ppl_Linear_Expression_t tmp_expr = NULL;
879 ppl_dimension_type dim;
880 ppl_Linear_Expression_space_dimension (c, &dim);
881 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
884 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
888 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
890 ppl_delete_Linear_Expression (tmp_expr);
898 ppl_Linear_Expression_t tmp_expr = NULL;
902 ppl_dimension_type dim;
903 ppl_Linear_Expression_space_dimension (c, &dim);
904 ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
907 scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
911 ppl_Coefficient_t coef;
914 ppl_subtract_Linear_Expression_from_Linear_Expression (c,
916 ppl_delete_Linear_Expression (tmp_expr);
917 value_init (minus_one);
918 value_set_si (minus_one, -1);
919 ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
920 ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
921 value_clear (minus_one);
922 ppl_delete_Coefficient (coef);
930 ppl_dimension_type p = parameter_index_in_region (e, s);
934 ppl_dimension_type dim;
935 ppl_Linear_Expression_space_dimension (c, &dim);
936 p += dim - sese_nb_params (s);
937 add_value_to_dim (p, c, k);
944 scan_tree_for_params_int (e, c, k);
948 case NON_LVALUE_EXPR:
949 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
958 /* Data structure for idx_record_params. */
966 /* For a data reference with an ARRAY_REF as its BASE, record the
967 parameters occurring in IDX. DTA is passed in as complementary
968 information, and is used by the automatic walker function. This
969 function is a callback for for_each_index. */
972 idx_record_params (tree base, tree *idx, void *dta)
974 struct irp_data *data = (struct irp_data *) dta;
976 if (TREE_CODE (base) != ARRAY_REF)
979 if (TREE_CODE (*idx) == SSA_NAME)
982 sese region = data->region;
983 struct loop *loop = data->loop;
986 scev = scalar_evolution_in_region (region, loop, *idx);
989 value_set_si (one, 1);
990 scan_tree_for_params (region, scev, NULL, one);
997 /* Find parameters with respect to REGION in BB. We are looking in memory
998 access functions, conditions and loop bounds. */
1001 find_params_in_bb (sese region, gimple_bb_p gbb)
1004 data_reference_p dr;
1006 loop_p loop = GBB_BB (gbb)->loop_father;
1008 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
1010 struct irp_data irp;
1013 irp.region = region;
1014 for_each_index (&dr->ref, idx_record_params, &irp);
1017 /* Find parameters in conditional statements. */
1018 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
1021 tree lhs = scalar_evolution_in_region (region, loop,
1022 gimple_cond_lhs (stmt));
1023 tree rhs = scalar_evolution_in_region (region, loop,
1024 gimple_cond_rhs (stmt));
1027 value_set_si (one, 1);
1028 scan_tree_for_params (region, lhs, NULL, one);
1029 scan_tree_for_params (region, rhs, NULL, one);
1034 /* Record the parameters used in the SCOP. A variable is a parameter
1035 in a scop if it does not vary during the execution of that scop. */
1038 find_scop_parameters (scop_p scop)
1042 sese region = SCOP_REGION (scop);
1047 value_set_si (one, 1);
1049 /* Find the parameters used in the loop bounds. */
1050 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1052 tree nb_iters = number_of_latch_executions (loop);
1054 if (!chrec_contains_symbols (nb_iters))
1057 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1058 scan_tree_for_params (region, nb_iters, NULL, one);
1063 /* Find the parameters used in data accesses. */
1064 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1065 find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1067 scop_set_nb_params (scop, sese_nb_params (region));
1068 SESE_ADD_PARAMS (region) = false;
1071 /* Returns a gimple_bb from BB. */
1073 static inline gimple_bb_p
1074 gbb_from_bb (basic_block bb)
1076 return (gimple_bb_p) bb->aux;
1079 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1080 the constraints for the surrounding loops. */
1083 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1084 ppl_Polyhedron_t outer_ph, int nb)
1088 ppl_Polyhedron_t ph;
1089 tree nb_iters = number_of_latch_executions (loop);
1090 ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1091 sese region = SCOP_REGION (scop);
1094 ppl_const_Constraint_System_t pcs;
1095 ppl_dimension_type *map
1096 = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1098 ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1099 ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1100 ppl_Polyhedron_add_constraints (ph, pcs);
1102 for (i = 0; i < (int) nb; i++)
1104 for (i = (int) nb; i < (int) dim - 1; i++)
1108 ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1114 ppl_Constraint_t lb;
1115 ppl_Linear_Expression_t lb_expr;
1117 ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1118 ppl_set_coef (lb_expr, nb, 1);
1119 ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1120 ppl_delete_Linear_Expression (lb_expr);
1121 ppl_Polyhedron_add_constraint (ph, lb);
1122 ppl_delete_Constraint (lb);
1125 if (TREE_CODE (nb_iters) == INTEGER_CST)
1127 ppl_Constraint_t ub;
1128 ppl_Linear_Expression_t ub_expr;
1130 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1132 /* loop_i <= cst_nb_iters */
1133 ppl_set_coef (ub_expr, nb, -1);
1134 ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1135 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1136 ppl_Polyhedron_add_constraint (ph, ub);
1137 ppl_delete_Linear_Expression (ub_expr);
1138 ppl_delete_Constraint (ub);
1140 else if (!chrec_contains_undetermined (nb_iters))
1143 ppl_Constraint_t ub;
1144 ppl_Linear_Expression_t ub_expr;
1147 value_set_si (one, 1);
1148 ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1149 nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1150 scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1153 /* loop_i <= expr_nb_iters */
1154 ppl_set_coef (ub_expr, nb, -1);
1155 ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1156 ppl_Polyhedron_add_constraint (ph, ub);
1157 ppl_delete_Linear_Expression (ub_expr);
1158 ppl_delete_Constraint (ub);
1163 if (loop->inner && loop_in_sese_p (loop->inner, region))
1164 build_loop_iteration_domains (scop, loop->inner, ph, nb + 1);
1168 && loop_in_sese_p (loop->next, region))
1169 build_loop_iteration_domains (scop, loop->next, outer_ph, nb);
1171 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1172 ((ppl_Pointset_Powerset_C_Polyhedron_t *) &loop->aux, ph);
1174 ppl_delete_Polyhedron (ph);
1177 /* Returns a linear expression for tree T evaluated in PBB. */
1179 static ppl_Linear_Expression_t
1180 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1183 ppl_Linear_Expression_t res;
1184 ppl_dimension_type dim;
1185 sese region = SCOP_REGION (PBB_SCOP (pbb));
1186 loop_p loop = GBB_BB (PBB_BLACK_BOX (pbb))->loop_father;
1188 dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1189 ppl_new_Linear_Expression_with_dimension (&res, dim);
1191 t = scalar_evolution_in_region (region, loop, t);
1192 gcc_assert (!automatically_generated_chrec_p (t));
1195 value_set_si (one, 1);
1196 scan_tree_for_params (region, t, res, one);
1202 /* Returns the ppl constraint type from the gimple tree code CODE. */
1204 static enum ppl_enum_Constraint_Type
1205 ppl_constraint_type_from_tree_code (enum tree_code code)
1209 /* We do not support LT and GT to be able to work with C_Polyhedron.
1210 As we work on integer polyhedron "a < b" can be expressed by
1217 return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1220 return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1223 return PPL_CONSTRAINT_TYPE_EQUAL;
1230 /* Add conditional statement STMT to PS. It is evaluated in PBB and
1231 CODE is used as the comparison operator. This allows us to invert the
1232 condition or to handle inequalities. */
1235 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1236 poly_bb_p pbb, enum tree_code code)
1239 ppl_Coefficient_t c;
1240 ppl_Linear_Expression_t left, right;
1241 ppl_Constraint_t cstr;
1242 enum ppl_enum_Constraint_Type type;
1244 left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1245 right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1247 /* If we have < or > expressions convert them to <= or >= by adding 1 to
1248 the left or the right side of the expression. */
1249 if (code == LT_EXPR)
1252 value_set_si (v, 1);
1253 ppl_new_Coefficient (&c);
1254 ppl_assign_Coefficient_from_mpz_t (c, v);
1255 ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1256 ppl_delete_Coefficient (c);
1261 else if (code == GT_EXPR)
1264 value_set_si (v, 1);
1265 ppl_new_Coefficient (&c);
1266 ppl_assign_Coefficient_from_mpz_t (c, v);
1267 ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1268 ppl_delete_Coefficient (c);
1274 type = ppl_constraint_type_from_tree_code (code);
1276 ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1278 ppl_new_Constraint (&cstr, left, type);
1279 ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1281 ppl_delete_Constraint (cstr);
1282 ppl_delete_Linear_Expression (left);
1283 ppl_delete_Linear_Expression (right);
1286 /* Add conditional statement STMT to pbb. CODE is used as the comparision
1287 operator. This allows us to invert the condition or to handle
1291 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1293 if (code == NE_EXPR)
1295 ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1296 ppl_Pointset_Powerset_C_Polyhedron_t right;
1297 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1299 add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1300 add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1301 ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1303 ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1306 add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1309 /* Add conditions to the domain of PBB. */
1312 add_conditions_to_domain (poly_bb_p pbb)
1316 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1317 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1319 if (VEC_empty (gimple, conditions))
1322 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1323 switch (gimple_code (stmt))
1327 enum tree_code code = gimple_cond_code (stmt);
1329 /* The conditions for ELSE-branches are inverted. */
1330 if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1331 code = invert_tree_comparison (code, false);
1333 add_condition_to_pbb (pbb, stmt, code);
1338 /* Switch statements are not supported right now - fall throught. */
1346 /* Structure used to pass data to dom_walk. */
1350 VEC (gimple, heap) **conditions, **cases;
1354 /* Returns non NULL when BB has a single predecessor and the last
1355 statement of that predecessor is a COND_EXPR. */
1358 single_pred_cond (basic_block bb)
1360 if (single_pred_p (bb))
1362 edge e = single_pred_edge (bb);
1363 basic_block pred = e->src;
1364 gimple stmt = last_stmt (pred);
1366 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1372 /* Call-back for dom_walk executed before visiting the dominated
1376 build_sese_conditions_before (struct dom_walk_data *dw_data,
1379 struct bsc *data = (struct bsc *) dw_data->global_data;
1380 VEC (gimple, heap) **conditions = data->conditions;
1381 VEC (gimple, heap) **cases = data->cases;
1382 gimple_bb_p gbb = gbb_from_bb (bb);
1383 gimple stmt = single_pred_cond (bb);
1385 if (!bb_in_sese_p (bb, data->region))
1390 edge e = single_pred_edge (bb);
1392 VEC_safe_push (gimple, heap, *conditions, stmt);
1394 if (e->flags & EDGE_TRUE_VALUE)
1395 VEC_safe_push (gimple, heap, *cases, stmt);
1397 VEC_safe_push (gimple, heap, *cases, NULL);
1402 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1403 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1407 /* Call-back for dom_walk executed after visiting the dominated
1411 build_sese_conditions_after (struct dom_walk_data *dw_data,
1414 struct bsc *data = (struct bsc *) dw_data->global_data;
1415 VEC (gimple, heap) **conditions = data->conditions;
1416 VEC (gimple, heap) **cases = data->cases;
1418 if (!bb_in_sese_p (bb, data->region))
1421 if (single_pred_cond (bb))
1423 VEC_pop (gimple, *conditions);
1424 VEC_pop (gimple, *cases);
1428 /* Record all conditions in REGION. */
1431 build_sese_conditions (sese region)
1433 struct dom_walk_data walk_data;
1434 VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1435 VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1438 data.conditions = &conditions;
1439 data.cases = &cases;
1440 data.region = region;
1442 walk_data.dom_direction = CDI_DOMINATORS;
1443 walk_data.initialize_block_local_data = NULL;
1444 walk_data.before_dom_children = build_sese_conditions_before;
1445 walk_data.after_dom_children = build_sese_conditions_after;
1446 walk_data.global_data = &data;
1447 walk_data.block_local_data_size = 0;
1449 init_walk_dominator_tree (&walk_data);
1450 walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1451 fini_walk_dominator_tree (&walk_data);
1453 VEC_free (gimple, heap, conditions);
1454 VEC_free (gimple, heap, cases);
1457 /* Traverses all the GBBs of the SCOP and add their constraints to the
1458 iteration domains. */
1461 add_conditions_to_constraints (scop_p scop)
1466 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1467 add_conditions_to_domain (pbb);
1470 /* Add constraints on the possible values of parameter P from the type
1474 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1476 ppl_Constraint_t cstr;
1477 ppl_Linear_Expression_t le;
1478 tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1479 tree type = TREE_TYPE (parameter);
1482 /* Disabled until we fix CPU2006. */
1485 if (!INTEGRAL_TYPE_P (type))
1488 lb = TYPE_MIN_VALUE (type);
1489 ub = TYPE_MAX_VALUE (type);
1493 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1494 ppl_set_coef (le, p, -1);
1495 ppl_set_inhomogeneous_tree (le, lb);
1496 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1497 ppl_Polyhedron_add_constraint (context, cstr);
1498 ppl_delete_Linear_Expression (le);
1499 ppl_delete_Constraint (cstr);
1504 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1505 ppl_set_coef (le, p, -1);
1506 ppl_set_inhomogeneous_tree (le, ub);
1507 ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1508 ppl_Polyhedron_add_constraint (context, cstr);
1509 ppl_delete_Linear_Expression (le);
1510 ppl_delete_Constraint (cstr);
1514 /* Build the context of the SCOP. The context usually contains extra
1515 constraints that are added to the iteration domains that constrain
1519 build_scop_context (scop_p scop)
1521 ppl_Polyhedron_t context;
1522 graphite_dim_t p, n = scop_nb_params (scop);
1524 ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1526 for (p = 0; p < n; p++)
1527 add_param_constraints (scop, context, p);
1529 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1530 (&SCOP_CONTEXT (scop), context);
1532 ppl_delete_Polyhedron (context);
1535 /* Build the iteration domains: the loops belonging to the current
1536 SCOP, and that vary for the execution of the current basic block.
1537 Returns false if there is no loop in SCOP. */
1540 build_scop_iteration_domain (scop_p scop)
1543 sese region = SCOP_REGION (scop);
1545 ppl_Polyhedron_t ph;
1548 ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1550 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1551 if (!loop_in_sese_p (loop_outer (loop), region))
1552 build_loop_iteration_domains (scop, loop, ph, 0);
1554 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1555 if (gbb_loop (PBB_BLACK_BOX (pbb))->aux)
1556 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1557 (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1558 gbb_loop (PBB_BLACK_BOX (pbb))->aux);
1560 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1561 (&PBB_DOMAIN (pbb), ph);
1563 for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1566 ppl_delete_Pointset_Powerset_C_Polyhedron
1567 ((ppl_Pointset_Powerset_C_Polyhedron_t) loop->aux);
1571 ppl_delete_Polyhedron (ph);
1574 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1575 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1576 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1580 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1581 ppl_dimension_type accessp_nb_dims,
1582 ppl_dimension_type dom_nb_dims)
1584 ppl_Linear_Expression_t alias;
1585 ppl_Constraint_t cstr;
1586 int alias_set_num = 0;
1588 if (dr->aux != NULL)
1590 alias_set_num = *((int *)(dr->aux));
1595 ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1597 ppl_set_coef (alias, dom_nb_dims, 1);
1598 ppl_set_inhomogeneous (alias, -alias_set_num);
1599 ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1600 ppl_Polyhedron_add_constraint (accesses, cstr);
1602 ppl_delete_Linear_Expression (alias);
1603 ppl_delete_Constraint (cstr);
1606 /* Add to ACCESSES polyhedron equalities defining the access functions
1607 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1608 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1609 PBB is the poly_bb_p that contains the data reference DR. */
1612 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1613 ppl_dimension_type accessp_nb_dims,
1614 ppl_dimension_type dom_nb_dims,
1617 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1619 scop_p scop = PBB_SCOP (pbb);
1620 sese region = SCOP_REGION (scop);
1624 for (i = 0; i < nb_subscripts; i++)
1626 ppl_Linear_Expression_t fn, access;
1627 ppl_Constraint_t cstr;
1628 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1629 tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1631 ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1632 ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1634 value_set_si (v, 1);
1635 scan_tree_for_params (region, afn, fn, v);
1636 ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1638 ppl_set_coef (access, subscript, -1);
1639 ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1640 ppl_Polyhedron_add_constraint (accesses, cstr);
1642 ppl_delete_Linear_Expression (fn);
1643 ppl_delete_Linear_Expression (access);
1644 ppl_delete_Constraint (cstr);
1650 /* Add constrains representing the size of the accessed data to the
1651 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1652 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1656 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1657 ppl_dimension_type accessp_nb_dims,
1658 ppl_dimension_type dom_nb_dims)
1660 tree ref = DR_REF (dr);
1661 int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1663 for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1665 ppl_Linear_Expression_t expr;
1666 ppl_Constraint_t cstr;
1667 ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1670 if (TREE_CODE (ref) != ARRAY_REF)
1673 low = array_ref_low_bound (ref);
1675 /* subscript - low >= 0 */
1676 if (host_integerp (low, 0))
1678 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1679 ppl_set_coef (expr, subscript, 1);
1681 ppl_set_inhomogeneous (expr, -int_cst_value (low));
1683 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1684 ppl_Polyhedron_add_constraint (accesses, cstr);
1685 ppl_delete_Linear_Expression (expr);
1686 ppl_delete_Constraint (cstr);
1689 high = array_ref_up_bound (ref);
1691 /* high - subscript >= 0
1692 XXX: 1-element arrays at end of structures may extend over their
1694 if (high && host_integerp (high, 0))
1696 ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1697 ppl_set_coef (expr, subscript, -1);
1699 ppl_set_inhomogeneous (expr, int_cst_value (high));
1701 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1702 ppl_Polyhedron_add_constraint (accesses, cstr);
1703 ppl_delete_Linear_Expression (expr);
1704 ppl_delete_Constraint (cstr);
1709 /* Build data accesses for DR in PBB. */
1712 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1714 ppl_Polyhedron_t accesses;
1715 ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1716 ppl_dimension_type dom_nb_dims;
1717 ppl_dimension_type accessp_nb_dims;
1719 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1721 accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1723 ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1725 pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1726 pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1727 pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1729 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1731 ppl_delete_Polyhedron (accesses);
1732 new_poly_dr (pbb, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, dr,
1733 DR_NUM_DIMENSIONS (dr));
1736 /* Group each data reference in DRS with it's alias set num. */
1739 build_alias_set_for_drs (VEC (data_reference_p, heap) **drs)
1741 int num_vertex = VEC_length (data_reference_p, *drs);
1742 struct graph *g = new_graph (num_vertex);
1743 data_reference_p dr1, dr2;
1748 for (i = 0; VEC_iterate (data_reference_p, *drs, i, dr1); i++)
1749 for (j = i+1; VEC_iterate (data_reference_p, *drs, j, dr2); j++)
1750 if (dr_may_alias_p (dr1, dr2))
1756 queue = XNEWVEC (int, num_vertex);
1757 for (i = 0; i < num_vertex; i++)
1760 num_component = graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1762 for (i = 0; i < g->n_vertices; i++)
1764 data_reference_p dr = VEC_index (data_reference_p, *drs, i);
1765 dr->aux = XNEW (int);
1766 *((int *)(dr->aux)) = g->vertices[i].component + 1;
1773 /* Build the data references for PBB. */
1776 build_pbb_drs (poly_bb_p pbb)
1779 data_reference_p dr;
1780 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1782 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
1783 build_poly_dr (dr, pbb);
1786 /* Build data references in SCOP. */
1789 build_scop_drs (scop_p scop)
1793 data_reference_p dr;
1794 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1796 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1798 VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1799 for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
1800 VEC_safe_push (data_reference_p, heap, drs, dr);
1803 build_alias_set_for_drs (&drs);
1804 VEC_free (data_reference_p, heap, drs);
1806 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1807 build_pbb_drs (pbb);
1810 /* Return a gsi at the position of the VAR definition. */
1812 static gimple_stmt_iterator
1813 gsi_for_ssa_name_def (tree var)
1817 gimple_stmt_iterator gsi;
1818 gimple_stmt_iterator psi;
1820 gcc_assert (TREE_CODE (var) == SSA_NAME);
1822 stmt = SSA_NAME_DEF_STMT (var);
1823 bb = gimple_bb (stmt);
1825 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1826 if (stmt == gsi_stmt (psi))
1827 return gsi_after_labels (bb);
1829 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1830 if (stmt == gsi_stmt (gsi))
1840 /* Insert the assignment "RES := VAR" just after the definition of VAR. */
1843 insert_out_of_ssa_copy (tree res, tree var)
1845 gimple_stmt_iterator gsi = gsi_for_ssa_name_def (var);
1848 gimple_stmt_iterator si;
1850 var = force_gimple_operand (var, &stmts, true, NULL_TREE);
1851 stmt = gimple_build_assign (res, var);
1853 stmts = gimple_seq_alloc ();
1854 si = gsi_last (stmts);
1855 gsi_insert_after (&si, stmt, GSI_NEW_STMT);
1856 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
1859 /* Insert on edge E the assignment "RES := EXPR". */
1862 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
1864 gimple_stmt_iterator gsi;
1866 tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
1867 gimple stmt = gimple_build_assign (res, var);
1870 stmts = gimple_seq_alloc ();
1872 gsi = gsi_last (stmts);
1873 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1874 gsi_insert_seq_on_edge (e, stmts);
1875 gsi_commit_edge_inserts ();
1878 /* Creates a zero dimension array of the same type as VAR. */
1881 create_zero_dim_array (tree var)
1883 tree index_type = build_index_type (integer_zero_node);
1884 tree elt_type = TREE_TYPE (var);
1885 tree array_type = build_array_type (elt_type, index_type);
1886 tree base = create_tmp_var (array_type, "Red");
1888 add_referenced_var (base);
1890 return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
1894 /* Returns true when PHI is a loop close phi node. */
1897 scalar_close_phi_node_p (gimple phi)
1899 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
1901 if (!is_gimple_reg (gimple_phi_result (phi)))
1904 return (gimple_phi_num_args (phi) == 1);
1907 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1908 dimension array for it. */
1911 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
1913 gimple phi = gsi_stmt (*psi);
1914 tree res = gimple_phi_result (phi);
1915 tree var = SSA_NAME_VAR (res);
1916 tree zero_dim_array = create_zero_dim_array (var);
1917 gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
1918 gimple stmt = gimple_build_assign (res, zero_dim_array);
1919 tree arg = gimple_phi_arg_def (phi, 0);
1921 insert_out_of_ssa_copy (zero_dim_array, arg);
1923 remove_phi_node (psi, false);
1924 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1925 SSA_NAME_DEF_STMT (res) = stmt;
1928 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
1929 dimension array for it. */
1932 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
1935 gimple phi = gsi_stmt (*psi);
1936 basic_block bb = gimple_bb (phi);
1937 tree res = gimple_phi_result (phi);
1938 tree var = SSA_NAME_VAR (res);
1939 tree zero_dim_array = create_zero_dim_array (var);
1940 gimple_stmt_iterator gsi;
1944 for (i = 0; i < gimple_phi_num_args (phi); i++)
1946 tree arg = gimple_phi_arg_def (phi, i);
1948 /* Try to avoid the insertion on edges as much as possible: this
1949 would avoid the insertion of code on loop latch edges, making
1950 the pattern matching of the vectorizer happy, or it would
1951 avoid the insertion of useless basic blocks. Note that it is
1952 incorrect to insert out of SSA copies close by their
1953 definition when they are more than two loop levels apart:
1954 for example, starting from a double nested loop
1964 the following transform is incorrect
1976 whereas inserting the copy on the incomming edge is correct
1988 if (TREE_CODE (arg) == SSA_NAME
1989 && is_gimple_reg (arg)
1990 && gimple_bb (SSA_NAME_DEF_STMT (arg))
1991 && (flow_bb_inside_loop_p (bb->loop_father,
1992 gimple_bb (SSA_NAME_DEF_STMT (arg)))
1993 || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
1994 gimple_bb (SSA_NAME_DEF_STMT (arg)))))
1995 insert_out_of_ssa_copy (zero_dim_array, arg);
1997 insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
1998 zero_dim_array, arg);
2001 var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2004 stmts = gimple_seq_alloc ();
2006 stmt = gimple_build_assign (res, var);
2007 remove_phi_node (psi, false);
2008 SSA_NAME_DEF_STMT (res) = stmt;
2010 gsi = gsi_last (stmts);
2011 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2013 gsi = gsi_after_labels (bb);
2014 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2017 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2020 rewrite_reductions_out_of_ssa (scop_p scop)
2023 gimple_stmt_iterator psi;
2024 sese region = SCOP_REGION (scop);
2027 if (bb_in_region (bb, SESE_ENTRY_BB (region), SESE_EXIT_BB (region)))
2028 for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2030 if (scalar_close_phi_node_p (gsi_stmt (psi)))
2031 rewrite_close_phi_out_of_ssa (&psi);
2032 else if (reduction_phi_p (region, &psi))
2033 rewrite_phi_out_of_ssa (&psi);
2036 update_ssa (TODO_update_ssa);
2037 #ifdef ENABLE_CHECKING
2039 verify_loop_closed_ssa ();
2043 /* Returns the number of pbbs that are in loops contained in SCOP. */
2046 nb_pbbs_in_loops (scop_p scop)
2052 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2053 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2059 /* Builds the polyhedral representation for a SESE region. */
2062 build_poly_scop (scop_p scop)
2064 sese region = SCOP_REGION (scop);
2065 rewrite_reductions_out_of_ssa (scop);
2066 build_scop_bbs (scop);
2068 /* FIXME: This restriction is needed to avoid a problem in CLooG.
2069 Once CLooG is fixed, remove this guard. Anyways, it makes no
2070 sense to optimize a scop containing only PBBs that do not belong
2072 if (nb_pbbs_in_loops (scop) == 0)
2075 build_sese_loop_nests (region);
2076 build_sese_conditions (region);
2077 find_scop_parameters (scop);
2079 build_scop_iteration_domain (scop);
2080 build_scop_context (scop);
2082 add_conditions_to_constraints (scop);
2083 build_scop_scattering (scop);
2084 build_scop_drs (scop);
2089 /* Always return false. Exercise the scop_to_clast function. */
2092 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2094 #ifdef ENABLE_CHECKING
2095 cloog_prog_clast pc = scop_to_clast (scop);
2096 cloog_clast_free (pc.stmt);
2097 cloog_program_free (pc.prog);