1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2013 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/>. */
26 #include <isl/union_map.h>
27 #include <isl/constraint.h>
29 #include <cloog/cloog.h>
30 #include <cloog/cloog.h>
31 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
45 #include "gimplify-me.h"
46 #include "gimple-ssa.h"
48 #include "tree-phinodes.h"
49 #include "ssa-iterators.h"
50 #include "stringpool.h"
51 #include "tree-ssanames.h"
52 #include "tree-ssa-loop-manip.h"
53 #include "tree-ssa-loop-niter.h"
54 #include "tree-ssa-loop.h"
55 #include "tree-into-ssa.h"
56 #include "tree-pass.h"
58 #include "tree-chrec.h"
59 #include "tree-data-ref.h"
60 #include "tree-scalar-evolution.h"
63 #include "tree-ssa-propagate.h"
68 #include "graphite-poly.h"
69 #include "graphite-sese-to-poly.h"
72 /* Assigns to RES the value of the INTEGER_CST T. */
75 tree_int_to_gmp (tree t
, mpz_t res
)
77 double_int di
= tree_to_double_int (t
);
78 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
81 /* Returns the index of the PHI argument defined in the outermost
85 phi_arg_in_outermost_loop (gimple phi
)
87 loop_p loop
= gimple_bb (phi
)->loop_father
;
90 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
91 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
93 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
100 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
101 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
104 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
106 gimple phi
= gsi_stmt (*psi
);
107 tree res
= gimple_phi_result (phi
);
108 size_t entry
= phi_arg_in_outermost_loop (phi
);
109 tree init
= gimple_phi_arg_def (phi
, entry
);
110 gimple stmt
= gimple_build_assign (res
, init
);
111 edge e
= gimple_phi_arg_edge (phi
, entry
);
113 remove_phi_node (psi
, false);
114 gsi_insert_on_edge_immediate (e
, stmt
);
117 /* Removes an invariant phi node at position PSI by inserting on the
118 loop ENTRY edge the assignment RES = INIT. */
121 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
123 gimple phi
= gsi_stmt (*psi
);
124 loop_p loop
= loop_containing_stmt (phi
);
125 tree res
= gimple_phi_result (phi
);
126 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
127 size_t entry
= phi_arg_in_outermost_loop (phi
);
128 edge e
= gimple_phi_arg_edge (phi
, entry
);
131 gimple_seq stmts
= NULL
;
133 if (tree_contains_chrecs (scev
, NULL
))
134 scev
= gimple_phi_arg_def (phi
, entry
);
136 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
137 stmt
= gimple_build_assign (res
, var
);
138 remove_phi_node (psi
, false);
140 gimple_seq_add_stmt (&stmts
, 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
)
169 gimple phi
= gsi_stmt (*psi
);
170 tree res
= gimple_phi_result (phi
);
172 loop
= loop_containing_stmt (phi
);
174 if (simple_copy_phi_p (phi
))
176 /* PRE introduces phi nodes like these, for an example,
177 see id-5.f in the fortran graphite testsuite:
179 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
181 remove_simple_copy_phi (psi
);
185 if (scev_analyzable_p (res
, region
))
187 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
189 if (evolution_function_is_invariant_p (scev
, loop
->num
))
190 remove_invariant_phi (region
, psi
);
197 /* All the other cases are considered reductions. */
201 /* Store the GRAPHITE representation of BB. */
204 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
206 struct gimple_bb
*gbb
;
208 gbb
= XNEW (struct gimple_bb
);
211 GBB_DATA_REFS (gbb
) = drs
;
212 GBB_CONDITIONS (gbb
).create (0);
213 GBB_CONDITION_CASES (gbb
).create (0);
219 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
222 struct data_reference
*dr
;
224 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
227 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
229 free (bap
->alias_set
);
238 free_gimple_bb (struct gimple_bb
*gbb
)
240 free_data_refs_aux (GBB_DATA_REFS (gbb
));
241 free_data_refs (GBB_DATA_REFS (gbb
));
243 GBB_CONDITIONS (gbb
).release ();
244 GBB_CONDITION_CASES (gbb
).release ();
245 GBB_BB (gbb
)->aux
= 0;
249 /* Deletes all gimple bbs in SCOP. */
252 remove_gbbs_in_scop (scop_p scop
)
257 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
258 free_gimple_bb (PBB_BLACK_BOX (pbb
));
261 /* Deletes all scops in SCOPS. */
264 free_scops (vec
<scop_p
> scops
)
269 FOR_EACH_VEC_ELT (scops
, i
, scop
)
271 remove_gbbs_in_scop (scop
);
272 free_sese (SCOP_REGION (scop
));
279 /* Same as outermost_loop_in_sese, returns the outermost loop
280 containing BB in REGION, but makes sure that the returned loop
281 belongs to the REGION, and so this returns the first loop in the
282 REGION when the loop containing BB does not belong to REGION. */
285 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
287 loop_p nest
= outermost_loop_in_sese (region
, bb
);
289 if (loop_in_sese_p (nest
, region
))
292 /* When the basic block BB does not belong to a loop in the region,
293 return the first loop in the region. */
296 if (loop_in_sese_p (nest
, region
))
305 /* Generates a polyhedral black box only if the bb contains interesting
309 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
311 vec
<data_reference_p
> drs
;
313 sese region
= SCOP_REGION (scop
);
314 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
315 gimple_stmt_iterator gsi
;
317 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
319 gimple stmt
= gsi_stmt (gsi
);
322 if (is_gimple_debug (stmt
))
325 loop
= loop_containing_stmt (stmt
);
326 if (!loop_in_sese_p (loop
, region
))
329 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
332 return new_gimple_bb (bb
, drs
);
335 /* Returns true if all predecessors of BB, that are not dominated by BB, are
336 marked in MAP. The predecessors dominated by BB are loop latches and will
337 be handled after BB. */
340 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
345 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
346 if (!bitmap_bit_p (map
, e
->src
->index
)
347 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
353 /* Compare the depth of two basic_block's P1 and P2. */
356 compare_bb_depths (const void *p1
, const void *p2
)
358 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
359 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
360 int d1
= loop_depth (bb1
->loop_father
);
361 int d2
= loop_depth (bb2
->loop_father
);
372 /* Sort the basic blocks from DOM such that the first are the ones at
373 a deepest loop level. */
376 graphite_sort_dominated_info (vec
<basic_block
> dom
)
378 dom
.qsort (compare_bb_depths
);
381 /* Recursive helper function for build_scops_bbs. */
384 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
386 sese region
= SCOP_REGION (scop
);
387 vec
<basic_block
> dom
;
390 if (bitmap_bit_p (visited
, bb
->index
)
391 || !bb_in_sese_p (bb
, region
))
394 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
395 SCOP_BBS (scop
).safe_push (pbb
);
396 bitmap_set_bit (visited
, bb
->index
);
398 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
403 graphite_sort_dominated_info (dom
);
405 while (!dom
.is_empty ())
410 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
411 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
413 build_scop_bbs_1 (scop
, visited
, dom_bb
);
414 dom
.unordered_remove (i
);
422 /* Gather the basic blocks belonging to the SCOP. */
425 build_scop_bbs (scop_p scop
)
427 sbitmap visited
= sbitmap_alloc (last_basic_block
);
428 sese region
= SCOP_REGION (scop
);
430 bitmap_clear (visited
);
431 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
432 sbitmap_free (visited
);
435 /* Return an ISL identifier for the polyhedral basic block PBB. */
438 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
441 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
442 return isl_id_alloc (s
->ctx
, name
, pbb
);
445 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
446 We generate SCATTERING_DIMENSIONS scattering dimensions.
448 CLooG 0.15.0 and previous versions require, that all
449 scattering functions of one CloogProgram have the same number of
450 scattering dimensions, therefore we allow to specify it. This
451 should be removed in future versions of CLooG.
453 The scattering polyhedron consists of these dimensions: scattering,
454 loop_iterators, parameters.
458 | scattering_dimensions = 5
459 | used_scattering_dimensions = 3
467 | Scattering polyhedron:
469 | scattering: {s1, s2, s3, s4, s5}
470 | loop_iterators: {i}
471 | parameters: {p1, p2}
473 | s1 s2 s3 s4 s5 i p1 p2 1
474 | 1 0 0 0 0 0 0 0 -4 = 0
475 | 0 1 0 0 0 -1 0 0 0 = 0
476 | 0 0 1 0 0 0 0 0 -5 = 0 */
479 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
480 poly_bb_p pbb
, int scattering_dimensions
)
483 int nb_iterators
= pbb_dim_iter_domain (pbb
);
484 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
488 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
492 dc
= isl_set_get_space (pbb
->domain
);
493 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
494 isl_dim_out
, scattering_dimensions
);
495 pbb
->schedule
= isl_map_universe (dm
);
497 for (i
= 0; i
< scattering_dimensions
; i
++)
499 /* Textual order inside this loop. */
502 isl_constraint
*c
= isl_equality_alloc
503 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
505 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
509 isl_int_neg (val
, val
);
510 c
= isl_constraint_set_constant (c
, val
);
511 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
512 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
515 /* Iterations of this loop. */
516 else /* if ((i % 2) == 1) */
518 int loop
= (i
- 1) / 2;
519 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
526 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
529 /* Build for BB the static schedule.
531 The static schedule is a Dewey numbering of the abstract syntax
532 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
534 The following example informally defines the static schedule:
553 Static schedules for A to F:
566 build_scop_scattering (scop_p scop
)
570 gimple_bb_p previous_gbb
= NULL
;
571 isl_space
*dc
= isl_set_get_space (scop
->context
);
572 isl_aff
*static_sched
;
574 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
575 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
577 /* We have to start schedules at 0 on the first component and
578 because we cannot compare_prefix_loops against a previous loop,
579 prefix will be equal to zero, and that index will be
580 incremented before copying. */
581 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
583 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
585 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
587 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
590 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
596 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
598 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
601 isl_aff_free (static_sched
);
604 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
606 /* Extract an affine expression from the chain of recurrence E. */
609 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
611 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
612 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
613 isl_local_space
*ls
= isl_local_space_from_space (space
);
614 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
615 isl_aff
*loop
= isl_aff_set_coefficient_si
616 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
617 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
619 /* Before multiplying, make sure that the result is affine. */
620 gcc_assert (isl_pw_aff_is_cst (rhs
)
621 || isl_pw_aff_is_cst (l
));
623 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
626 /* Extract an affine expression from the mult_expr E. */
629 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
631 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
632 isl_space_copy (space
));
633 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
635 if (!isl_pw_aff_is_cst (lhs
)
636 && !isl_pw_aff_is_cst (rhs
))
638 isl_pw_aff_free (lhs
);
639 isl_pw_aff_free (rhs
);
643 return isl_pw_aff_mul (lhs
, rhs
);
646 /* Return an ISL identifier from the name of the ssa_name E. */
649 isl_id_for_ssa_name (scop_p s
, tree e
)
651 const char *name
= get_name (e
);
655 id
= isl_id_alloc (s
->ctx
, name
, e
);
659 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
660 id
= isl_id_alloc (s
->ctx
, name1
, e
);
666 /* Return an ISL identifier for the data reference DR. */
669 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
671 /* Data references all get the same isl_id. They need to be comparable
672 and are distinguished through the first dimension, which contains the
674 return isl_id_alloc (s
->ctx
, "", 0);
677 /* Extract an affine expression from the ssa_name E. */
680 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
687 id
= isl_id_for_ssa_name (s
, e
);
688 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
690 dom
= isl_set_universe (isl_space_copy (space
));
691 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
692 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
693 return isl_pw_aff_alloc (dom
, aff
);
696 /* Extract an affine expression from the gmp constant G. */
699 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
701 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
702 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
703 isl_set
*dom
= isl_set_universe (space
);
707 isl_int_set_gmp (v
, g
);
708 aff
= isl_aff_add_constant (aff
, v
);
711 return isl_pw_aff_alloc (dom
, aff
);
714 /* Extract an affine expression from the integer_cst E. */
717 extract_affine_int (tree e
, __isl_take isl_space
*space
)
723 tree_int_to_gmp (e
, g
);
724 res
= extract_affine_gmp (g
, space
);
730 /* Compute pwaff mod 2^width. */
733 wrap (isl_pw_aff
*pwaff
, unsigned width
)
738 isl_int_set_si (mod
, 1);
739 isl_int_mul_2exp (mod
, mod
, width
);
741 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
748 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
749 Otherwise returns -1. */
752 parameter_index_in_region_1 (tree name
, sese region
)
757 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
759 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
766 /* When the parameter NAME is in REGION, returns its index in
767 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
768 and returns the index of NAME. */
771 parameter_index_in_region (tree name
, sese region
)
775 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
777 i
= parameter_index_in_region_1 (name
, region
);
781 gcc_assert (SESE_ADD_PARAMS (region
));
783 i
= SESE_PARAMS (region
).length ();
784 SESE_PARAMS (region
).safe_push (name
);
788 /* Extract an affine expression from the tree E in the scop S. */
791 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
793 isl_pw_aff
*lhs
, *rhs
, *res
;
796 if (e
== chrec_dont_know
) {
797 isl_space_free (space
);
801 switch (TREE_CODE (e
))
803 case POLYNOMIAL_CHREC
:
804 res
= extract_affine_chrec (s
, e
, space
);
808 res
= extract_affine_mul (s
, e
, space
);
812 case POINTER_PLUS_EXPR
:
813 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
814 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
815 res
= isl_pw_aff_add (lhs
, rhs
);
819 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
820 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
821 res
= isl_pw_aff_sub (lhs
, rhs
);
826 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
827 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
828 res
= isl_pw_aff_mul (lhs
, rhs
);
832 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
833 res
= extract_affine_name (s
, e
, space
);
837 res
= extract_affine_int (e
, space
);
838 /* No need to wrap a single integer. */
842 case NON_LVALUE_EXPR
:
843 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
851 type
= TREE_TYPE (e
);
852 if (TYPE_UNSIGNED (type
))
853 res
= wrap (res
, TYPE_PRECISION (type
));
858 /* In the context of sese S, scan the expression E and translate it to
859 a linear expression C. When parsing a symbolic multiplication, K
860 represents the constant multiplier of an expression containing
864 scan_tree_for_params (sese s
, tree e
)
866 if (e
== chrec_dont_know
)
869 switch (TREE_CODE (e
))
871 case POLYNOMIAL_CHREC
:
872 scan_tree_for_params (s
, CHREC_LEFT (e
));
876 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
879 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
883 case POINTER_PLUS_EXPR
:
885 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
886 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
892 case NON_LVALUE_EXPR
:
893 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
897 parameter_index_in_region (e
, s
);
910 /* Find parameters with respect to REGION in BB. We are looking in memory
911 access functions, conditions and loop bounds. */
914 find_params_in_bb (sese region
, gimple_bb_p gbb
)
920 loop_p loop
= GBB_BB (gbb
)->loop_father
;
922 /* Find parameters in the access functions of data references. */
923 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
924 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
925 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
927 /* Find parameters in conditional statements. */
928 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
930 tree lhs
= scalar_evolution_in_region (region
, loop
,
931 gimple_cond_lhs (stmt
));
932 tree rhs
= scalar_evolution_in_region (region
, loop
,
933 gimple_cond_rhs (stmt
));
935 scan_tree_for_params (region
, lhs
);
936 scan_tree_for_params (region
, rhs
);
940 /* Record the parameters used in the SCOP. A variable is a parameter
941 in a scop if it does not vary during the execution of that scop. */
944 find_scop_parameters (scop_p scop
)
948 sese region
= SCOP_REGION (scop
);
952 /* Find the parameters used in the loop bounds. */
953 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
955 tree nb_iters
= number_of_latch_executions (loop
);
957 if (!chrec_contains_symbols (nb_iters
))
960 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
961 scan_tree_for_params (region
, nb_iters
);
964 /* Find the parameters used in data accesses. */
965 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
966 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
968 nbp
= sese_nb_params (region
);
969 scop_set_nb_params (scop
, nbp
);
970 SESE_ADD_PARAMS (region
) = false;
974 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
976 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
977 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
978 isl_id_for_ssa_name (scop
, e
));
980 scop
->context
= isl_set_universe (space
);
984 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
985 the constraints for the surrounding loops. */
988 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
990 isl_set
*outer
, isl_set
**doms
)
992 tree nb_iters
= number_of_latch_executions (loop
);
993 sese region
= SCOP_REGION (scop
);
995 isl_set
*inner
= isl_set_copy (outer
);
998 int pos
= isl_set_dim (outer
, isl_dim_set
);
1005 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1006 space
= isl_set_get_space (inner
);
1009 c
= isl_inequality_alloc
1010 (isl_local_space_from_space (isl_space_copy (space
)));
1011 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1012 inner
= isl_set_add_constraint (inner
, c
);
1014 /* loop_i <= cst_nb_iters */
1015 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1017 c
= isl_inequality_alloc
1018 (isl_local_space_from_space (isl_space_copy (space
)));
1019 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1020 tree_int_to_gmp (nb_iters
, g
);
1021 isl_int_set_gmp (v
, g
);
1022 c
= isl_constraint_set_constant (c
, v
);
1023 inner
= isl_set_add_constraint (inner
, c
);
1026 /* loop_i <= expr_nb_iters */
1027 else if (!chrec_contains_undetermined (nb_iters
))
1032 isl_local_space
*ls
;
1036 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1038 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1039 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1040 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1041 isl_set_dim (valid
, isl_dim_set
));
1042 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1044 ls
= isl_local_space_from_space (isl_space_copy (space
));
1045 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1046 isl_dim_in
, pos
, 1);
1047 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1048 isl_pw_aff_copy (aff
));
1049 inner
= isl_set_intersect (inner
, le
);
1051 if (max_stmt_executions (loop
, &nit
))
1053 /* Insert in the context the constraints from the
1054 estimation of the number of iterations NIT and the
1055 symbolic number of iterations (involving parameter
1056 names) NB_ITERS. First, build the affine expression
1057 "NIT - NB_ITERS" and then say that it is positive,
1058 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1065 mpz_set_double_int (g
, nit
, false);
1066 mpz_sub_ui (g
, g
, 1);
1067 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1068 x
= isl_pw_aff_ge_set (approx
, aff
);
1069 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1070 isl_set_dim (x
, isl_dim_set
));
1071 scop
->context
= isl_set_intersect (scop
->context
, x
);
1073 c
= isl_inequality_alloc
1074 (isl_local_space_from_space (isl_space_copy (space
)));
1075 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1076 isl_int_set_gmp (v
, g
);
1078 c
= isl_constraint_set_constant (c
, v
);
1079 inner
= isl_set_add_constraint (inner
, c
);
1082 isl_pw_aff_free (aff
);
1087 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1088 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1089 isl_set_copy (inner
), doms
);
1093 && loop_in_sese_p (loop
->next
, region
))
1094 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1095 isl_set_copy (outer
), doms
);
1097 doms
[loop
->num
] = inner
;
1099 isl_set_free (outer
);
1100 isl_space_free (space
);
1105 /* Returns a linear expression for tree T evaluated in PBB. */
1108 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1110 scop_p scop
= PBB_SCOP (pbb
);
1112 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1113 gcc_assert (!automatically_generated_chrec_p (t
));
1115 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1118 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1119 operator. This allows us to invert the condition or to handle
1123 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1125 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1126 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1132 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1136 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1140 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1144 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1148 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1152 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1156 isl_pw_aff_free (lhs
);
1157 isl_pw_aff_free (rhs
);
1161 cond
= isl_set_coalesce (cond
);
1162 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1163 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1166 /* Add conditions to the domain of PBB. */
1169 add_conditions_to_domain (poly_bb_p pbb
)
1173 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1175 if (GBB_CONDITIONS (gbb
).is_empty ())
1178 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1179 switch (gimple_code (stmt
))
1183 enum tree_code code
= gimple_cond_code (stmt
);
1185 /* The conditions for ELSE-branches are inverted. */
1186 if (!GBB_CONDITION_CASES (gbb
)[i
])
1187 code
= invert_tree_comparison (code
, false);
1189 add_condition_to_pbb (pbb
, stmt
, code
);
1194 /* Switch statements are not supported right now - fall through. */
1202 /* Traverses all the GBBs of the SCOP and add their constraints to the
1203 iteration domains. */
1206 add_conditions_to_constraints (scop_p scop
)
1211 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1212 add_conditions_to_domain (pbb
);
1215 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1216 edge between BB and its predecessor is not a loop exit edge, and
1217 the last statement of the single predecessor is a COND_EXPR. */
1220 single_pred_cond_non_loop_exit (basic_block bb
)
1222 if (single_pred_p (bb
))
1224 edge e
= single_pred_edge (bb
);
1225 basic_block pred
= e
->src
;
1228 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1231 stmt
= last_stmt (pred
);
1233 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1240 class sese_dom_walker
: public dom_walker
1243 sese_dom_walker (cdi_direction
, sese
);
1245 virtual void before_dom_children (basic_block
);
1246 virtual void after_dom_children (basic_block
);
1249 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1253 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1254 : dom_walker (direction
), m_region (region
)
1258 /* Call-back for dom_walk executed before visiting the dominated
1262 sese_dom_walker::before_dom_children (basic_block bb
)
1267 if (!bb_in_sese_p (bb
, m_region
))
1270 stmt
= single_pred_cond_non_loop_exit (bb
);
1274 edge e
= single_pred_edge (bb
);
1276 m_conditions
.safe_push (stmt
);
1278 if (e
->flags
& EDGE_TRUE_VALUE
)
1279 m_cases
.safe_push (stmt
);
1281 m_cases
.safe_push (NULL
);
1284 gbb
= gbb_from_bb (bb
);
1288 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1289 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1293 /* Call-back for dom_walk executed after visiting the dominated
1297 sese_dom_walker::after_dom_children (basic_block bb
)
1299 if (!bb_in_sese_p (bb
, m_region
))
1302 if (single_pred_cond_non_loop_exit (bb
))
1304 m_conditions
.pop ();
1309 /* Add constraints on the possible values of parameter P from the type
1313 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1315 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1316 tree type
= TREE_TYPE (parameter
);
1317 tree lb
= NULL_TREE
;
1318 tree ub
= NULL_TREE
;
1320 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1321 lb
= lower_bound_in_type (type
, type
);
1323 lb
= TYPE_MIN_VALUE (type
);
1325 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1326 ub
= upper_bound_in_type (type
, type
);
1328 ub
= TYPE_MAX_VALUE (type
);
1332 isl_space
*space
= isl_set_get_space (scop
->context
);
1337 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1340 tree_int_to_gmp (lb
, g
);
1341 isl_int_set_gmp (v
, g
);
1344 c
= isl_constraint_set_constant (c
, v
);
1346 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1348 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1353 isl_space
*space
= isl_set_get_space (scop
->context
);
1358 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1362 tree_int_to_gmp (ub
, g
);
1363 isl_int_set_gmp (v
, g
);
1365 c
= isl_constraint_set_constant (c
, v
);
1367 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1369 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1373 /* Build the context of the SCOP. The context usually contains extra
1374 constraints that are added to the iteration domains that constrain
1378 build_scop_context (scop_p scop
)
1380 graphite_dim_t p
, n
= scop_nb_params (scop
);
1382 for (p
= 0; p
< n
; p
++)
1383 add_param_constraints (scop
, p
);
1386 /* Build the iteration domains: the loops belonging to the current
1387 SCOP, and that vary for the execution of the current basic block.
1388 Returns false if there is no loop in SCOP. */
1391 build_scop_iteration_domain (scop_p scop
)
1394 sese region
= SCOP_REGION (scop
);
1397 int nb_loops
= number_of_loops (cfun
);
1398 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1400 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1401 if (!loop_in_sese_p (loop_outer (loop
), region
))
1402 build_loop_iteration_domains (scop
, loop
, 0,
1403 isl_set_copy (scop
->context
), doms
);
1405 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1407 loop
= pbb_loop (pbb
);
1409 if (doms
[loop
->num
])
1410 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1412 pbb
->domain
= isl_set_copy (scop
->context
);
1414 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1415 isl_id_for_pbb (scop
, pbb
));
1418 for (i
= 0; i
< nb_loops
; i
++)
1420 isl_set_free (doms
[i
]);
1425 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1426 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1427 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1431 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1434 int alias_set_num
= 0;
1435 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1437 if (bap
&& bap
->alias_set
)
1438 alias_set_num
= *(bap
->alias_set
);
1440 c
= isl_equality_alloc
1441 (isl_local_space_from_space (isl_map_get_space (acc
)));
1442 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1443 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1445 return isl_map_add_constraint (acc
, c
);
1448 /* Assign the affine expression INDEX to the output dimension POS of
1449 MAP and return the result. */
1452 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1455 int len
= isl_map_dim (map
, isl_dim_out
);
1458 index_map
= isl_map_from_pw_aff (index
);
1459 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1460 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1462 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1463 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1464 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1465 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1467 return isl_map_intersect (map
, index_map
);
1470 /* Add to ACCESSES polyhedron equalities defining the access functions
1471 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1472 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1473 PBB is the poly_bb_p that contains the data reference DR. */
1476 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1478 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1479 scop_p scop
= PBB_SCOP (pbb
);
1481 for (i
= 0; i
< nb_subscripts
; i
++)
1484 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1486 aff
= extract_affine (scop
, afn
,
1487 isl_space_domain (isl_map_get_space (acc
)));
1488 acc
= set_index (acc
, i
+ 1, aff
);
1494 /* Add constrains representing the size of the accessed data to the
1495 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1496 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1500 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1502 tree ref
= DR_REF (dr
);
1503 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1505 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1509 if (TREE_CODE (ref
) != ARRAY_REF
)
1512 low
= array_ref_low_bound (ref
);
1513 high
= array_ref_up_bound (ref
);
1515 /* XXX The PPL code dealt separately with
1516 subscript - low >= 0 and high - subscript >= 0 in case one of
1517 the two bounds isn't known. Do the same here? */
1519 if (tree_fits_shwi_p (low
)
1521 && tree_fits_shwi_p (high
)
1522 /* 1-element arrays at end of structures may extend over
1523 their declared size. */
1524 && !(array_at_struct_end_p (ref
)
1525 && operand_equal_p (low
, high
, 0)))
1529 isl_set
*univ
, *lbs
, *ubs
;
1533 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1534 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1537 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1538 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1539 isl_set_dim (valid
, isl_dim_set
));
1540 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1542 space
= isl_set_get_space (extent
);
1543 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1544 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1545 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1546 index
= isl_pw_aff_alloc (univ
, aff
);
1548 id
= isl_set_get_tuple_id (extent
);
1549 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1550 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1552 /* low <= sub_i <= high */
1553 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1554 ubs
= isl_pw_aff_le_set (index
, ub
);
1555 extent
= isl_set_intersect (extent
, lbs
);
1556 extent
= isl_set_intersect (extent
, ubs
);
1563 /* Build data accesses for DR in PBB. */
1566 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1568 int dr_base_object_set
;
1571 scop_p scop
= PBB_SCOP (pbb
);
1574 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1575 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1576 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1577 isl_dim_out
, nb_out
);
1579 acc
= isl_map_universe (space
);
1580 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1583 acc
= pdr_add_alias_set (acc
, dr
);
1584 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1587 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1588 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1589 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1590 int alias_set_num
= 0;
1591 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1593 if (bap
&& bap
->alias_set
)
1594 alias_set_num
= *(bap
->alias_set
);
1596 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1597 extent
= isl_set_nat_universe (space
);
1598 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1599 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1602 gcc_assert (dr
->aux
);
1603 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1605 new_poly_dr (pbb
, dr_base_object_set
,
1606 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1607 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1610 /* Write to FILE the alias graph of data references in DIMACS format. */
1613 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1614 vec
<data_reference_p
> drs
)
1616 int num_vertex
= drs
.length ();
1618 data_reference_p dr1
, dr2
;
1621 if (num_vertex
== 0)
1624 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1625 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1626 if (dr_may_alias_p (dr1
, dr2
, true))
1629 fprintf (file
, "$\n");
1632 fprintf (file
, "c %s\n", comment
);
1634 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1636 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1637 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1638 if (dr_may_alias_p (dr1
, dr2
, true))
1639 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1644 /* Write to FILE the alias graph of data references in DOT format. */
1647 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1648 vec
<data_reference_p
> drs
)
1650 int num_vertex
= drs
.length ();
1651 data_reference_p dr1
, dr2
;
1654 if (num_vertex
== 0)
1657 fprintf (file
, "$\n");
1660 fprintf (file
, "c %s\n", comment
);
1662 /* First print all the vertices. */
1663 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1664 fprintf (file
, "n%d;\n", i
);
1666 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1667 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1668 if (dr_may_alias_p (dr1
, dr2
, true))
1669 fprintf (file
, "n%d n%d\n", i
, j
);
1674 /* Write to FILE the alias graph of data references in ECC format. */
1677 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1678 vec
<data_reference_p
> drs
)
1680 int num_vertex
= drs
.length ();
1681 data_reference_p dr1
, dr2
;
1684 if (num_vertex
== 0)
1687 fprintf (file
, "$\n");
1690 fprintf (file
, "c %s\n", comment
);
1692 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1693 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1694 if (dr_may_alias_p (dr1
, dr2
, true))
1695 fprintf (file
, "%d %d\n", i
, j
);
1700 /* Check if DR1 and DR2 are in the same object set. */
1703 dr_same_base_object_p (const struct data_reference
*dr1
,
1704 const struct data_reference
*dr2
)
1706 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1709 /* Uses DFS component number as representative of alias-sets. Also tests for
1710 optimality by verifying if every connected component is a clique. Returns
1711 true (1) if the above test is true, and false (0) otherwise. */
1714 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1716 int num_vertices
= drs
.length ();
1717 struct graph
*g
= new_graph (num_vertices
);
1718 data_reference_p dr1
, dr2
;
1720 int num_connected_components
;
1721 int v_indx1
, v_indx2
, num_vertices_in_component
;
1724 struct graph_edge
*e
;
1725 int this_component_is_clique
;
1726 int all_components_are_cliques
= 1;
1728 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1729 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1730 if (dr_may_alias_p (dr1
, dr2
, true))
1736 all_vertices
= XNEWVEC (int, num_vertices
);
1737 vertices
= XNEWVEC (int, num_vertices
);
1738 for (i
= 0; i
< num_vertices
; i
++)
1739 all_vertices
[i
] = i
;
1741 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1743 for (i
= 0; i
< g
->n_vertices
; i
++)
1745 data_reference_p dr
= drs
[i
];
1746 base_alias_pair
*bap
;
1748 gcc_assert (dr
->aux
);
1749 bap
= (base_alias_pair
*)(dr
->aux
);
1751 bap
->alias_set
= XNEW (int);
1752 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1755 /* Verify if the DFS numbering results in optimal solution. */
1756 for (i
= 0; i
< num_connected_components
; i
++)
1758 num_vertices_in_component
= 0;
1759 /* Get all vertices whose DFS component number is the same as i. */
1760 for (j
= 0; j
< num_vertices
; j
++)
1761 if (g
->vertices
[j
].component
== i
)
1762 vertices
[num_vertices_in_component
++] = j
;
1764 /* Now test if the vertices in 'vertices' form a clique, by testing
1765 for edges among each pair. */
1766 this_component_is_clique
= 1;
1767 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1769 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1771 /* Check if the two vertices are connected by iterating
1772 through all the edges which have one of these are source. */
1773 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1776 if (e
->src
== vertices
[v_indx1
])
1782 this_component_is_clique
= 0;
1786 if (!this_component_is_clique
)
1787 all_components_are_cliques
= 0;
1791 free (all_vertices
);
1794 return all_components_are_cliques
;
1797 /* Group each data reference in DRS with its base object set num. */
1800 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1802 int num_vertex
= drs
.length ();
1803 struct graph
*g
= new_graph (num_vertex
);
1804 data_reference_p dr1
, dr2
;
1808 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1809 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1810 if (dr_same_base_object_p (dr1
, dr2
))
1816 queue
= XNEWVEC (int, num_vertex
);
1817 for (i
= 0; i
< num_vertex
; i
++)
1820 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1822 for (i
= 0; i
< g
->n_vertices
; i
++)
1824 data_reference_p dr
= drs
[i
];
1825 base_alias_pair
*bap
;
1827 gcc_assert (dr
->aux
);
1828 bap
= (base_alias_pair
*)(dr
->aux
);
1830 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1837 /* Build the data references for PBB. */
1840 build_pbb_drs (poly_bb_p pbb
)
1843 data_reference_p dr
;
1844 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1846 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1847 build_poly_dr (dr
, pbb
);
1850 /* Dump to file the alias graphs for the data references in DRS. */
1853 dump_alias_graphs (vec
<data_reference_p
> drs
)
1856 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1858 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1861 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1862 current_function_name ());
1863 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1864 fclose (file_dimacs
);
1867 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1870 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1871 current_function_name ());
1872 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1876 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1879 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1880 current_function_name ());
1881 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1886 /* Build data references in SCOP. */
1889 build_scop_drs (scop_p scop
)
1893 data_reference_p dr
;
1894 stack_vec
<data_reference_p
, 3> drs
;
1896 /* Remove all the PBBs that do not have data references: these basic
1897 blocks are not handled in the polyhedral representation. */
1898 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1899 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1901 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1903 SCOP_BBS (scop
).ordered_remove (i
);
1907 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1908 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1911 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1912 dr
->aux
= XNEW (base_alias_pair
);
1914 if (!build_alias_set_optimal_p (drs
))
1916 /* TODO: Add support when building alias set is not optimal. */
1920 build_base_obj_set_for_drs (drs
);
1922 /* When debugging, enable the following code. This cannot be used
1923 in production compilers. */
1925 dump_alias_graphs (drs
);
1929 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1930 build_pbb_drs (pbb
);
1933 /* Return a gsi at the position of the phi node STMT. */
1935 static gimple_stmt_iterator
1936 gsi_for_phi_node (gimple stmt
)
1938 gimple_stmt_iterator psi
;
1939 basic_block bb
= gimple_bb (stmt
);
1941 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1942 if (stmt
== gsi_stmt (psi
))
1949 /* Analyze all the data references of STMTS and add them to the
1950 GBB_DATA_REFS vector of BB. */
1953 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1959 sese region
= SCOP_REGION (scop
);
1961 if (!bb_in_sese_p (bb
, region
))
1964 nest
= outermost_loop_in_sese_1 (region
, bb
);
1965 gbb
= gbb_from_bb (bb
);
1967 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1971 if (is_gimple_debug (stmt
))
1974 loop
= loop_containing_stmt (stmt
);
1975 if (!loop_in_sese_p (loop
, region
))
1978 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1979 &GBB_DATA_REFS (gbb
));
1983 /* Insert STMT at the end of the STMTS sequence and then insert the
1984 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1988 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1989 gimple_stmt_iterator insert_gsi
)
1991 gimple_stmt_iterator gsi
;
1992 stack_vec
<gimple
, 3> x
;
1994 gimple_seq_add_stmt (&stmts
, stmt
);
1995 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1996 x
.safe_push (gsi_stmt (gsi
));
1998 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1999 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2002 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2005 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2008 gimple_stmt_iterator gsi
;
2009 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2010 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2011 stack_vec
<gimple
, 3> x
;
2013 gimple_seq_add_stmt (&stmts
, stmt
);
2014 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2015 x
.safe_push (gsi_stmt (gsi
));
2017 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2019 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2020 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2024 gsi
= gsi_for_stmt (after_stmt
);
2025 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2028 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2031 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2034 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2036 vec
<data_reference_p
> drs
;
2038 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2039 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2040 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2041 int index
, n
= SCOP_BBS (scop
).length ();
2043 /* The INDEX of PBB in SCOP_BBS. */
2044 for (index
= 0; index
< n
; index
++)
2045 if (SCOP_BBS (scop
)[index
] == pbb
)
2048 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2050 GBB_PBB (gbb1
) = pbb1
;
2051 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2052 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2053 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2056 /* Insert on edge E the assignment "RES := EXPR". */
2059 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2061 gimple_stmt_iterator gsi
;
2062 gimple_seq stmts
= NULL
;
2063 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2064 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2066 stack_vec
<gimple
, 3> x
;
2068 gimple_seq_add_stmt (&stmts
, stmt
);
2069 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2070 x
.safe_push (gsi_stmt (gsi
));
2072 gsi_insert_seq_on_edge (e
, stmts
);
2073 gsi_commit_edge_inserts ();
2074 bb
= gimple_bb (stmt
);
2076 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2079 if (!gbb_from_bb (bb
))
2080 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2082 analyze_drs_in_stmts (scop
, bb
, x
);
2085 /* Creates a zero dimension array of the same type as VAR. */
2088 create_zero_dim_array (tree var
, const char *base_name
)
2090 tree index_type
= build_index_type (integer_zero_node
);
2091 tree elt_type
= TREE_TYPE (var
);
2092 tree array_type
= build_array_type (elt_type
, index_type
);
2093 tree base
= create_tmp_var (array_type
, base_name
);
2095 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2099 /* Returns true when PHI is a loop close phi node. */
2102 scalar_close_phi_node_p (gimple phi
)
2104 if (gimple_code (phi
) != GIMPLE_PHI
2105 || virtual_operand_p (gimple_phi_result (phi
)))
2108 /* Note that loop close phi nodes should have a single argument
2109 because we translated the representation into a canonical form
2110 before Graphite: see canonicalize_loop_closed_ssa_form. */
2111 return (gimple_phi_num_args (phi
) == 1);
2114 /* For a definition DEF in REGION, propagates the expression EXPR in
2115 all the uses of DEF outside REGION. */
2118 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2120 imm_use_iterator imm_iter
;
2123 bool replaced_once
= false;
2125 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2127 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2130 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2131 if (!is_gimple_debug (use_stmt
)
2132 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2135 use_operand_p use_p
;
2137 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2138 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2139 && (replaced_once
= true))
2140 replace_exp (use_p
, expr
);
2142 update_stmt (use_stmt
);
2147 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2148 gsi_commit_edge_inserts ();
2152 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2153 dimension array for it. */
2156 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2158 sese region
= SCOP_REGION (scop
);
2159 gimple phi
= gsi_stmt (*psi
);
2160 tree res
= gimple_phi_result (phi
);
2161 basic_block bb
= gimple_bb (phi
);
2162 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2163 tree arg
= gimple_phi_arg_def (phi
, 0);
2166 /* Note that loop close phi nodes should have a single argument
2167 because we translated the representation into a canonical form
2168 before Graphite: see canonicalize_loop_closed_ssa_form. */
2169 gcc_assert (gimple_phi_num_args (phi
) == 1);
2171 /* The phi node can be a non close phi node, when its argument is
2172 invariant, or a default definition. */
2173 if (is_gimple_min_invariant (arg
)
2174 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2176 propagate_expr_outside_region (res
, arg
, region
);
2181 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2183 propagate_expr_outside_region (res
, arg
, region
);
2184 stmt
= gimple_build_assign (res
, arg
);
2185 remove_phi_node (psi
, false);
2186 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2190 /* If res is scev analyzable and is not a scalar value, it is safe
2191 to ignore the close phi node: it will be code generated in the
2192 out of Graphite pass. */
2193 else if (scev_analyzable_p (res
, region
))
2195 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2198 if (!loop_in_sese_p (loop
, region
))
2200 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2201 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2202 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2205 scev
= scalar_evolution_in_region (region
, loop
, res
);
2207 if (tree_does_not_contain_chrecs (scev
))
2208 propagate_expr_outside_region (res
, scev
, region
);
2215 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2217 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2219 if (TREE_CODE (arg
) == SSA_NAME
)
2220 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2221 SSA_NAME_DEF_STMT (arg
));
2223 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2224 zero_dim_array
, arg
);
2227 remove_phi_node (psi
, false);
2228 SSA_NAME_DEF_STMT (res
) = stmt
;
2230 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2233 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2234 dimension array for it. */
2237 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2240 gimple phi
= gsi_stmt (*psi
);
2241 basic_block bb
= gimple_bb (phi
);
2242 tree res
= gimple_phi_result (phi
);
2243 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2246 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2248 tree arg
= gimple_phi_arg_def (phi
, i
);
2249 edge e
= gimple_phi_arg_edge (phi
, i
);
2251 /* Avoid the insertion of code in the loop latch to please the
2252 pattern matching of the vectorizer. */
2253 if (TREE_CODE (arg
) == SSA_NAME
2254 && e
->src
== bb
->loop_father
->latch
)
2255 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2256 SSA_NAME_DEF_STMT (arg
));
2258 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2261 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2262 remove_phi_node (psi
, false);
2263 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2266 /* Rewrite the degenerate phi node at position PSI from the degenerate
2267 form "x = phi (y, y, ..., y)" to "x = y". */
2270 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2274 gimple_stmt_iterator gsi
;
2275 gimple phi
= gsi_stmt (*psi
);
2276 tree res
= gimple_phi_result (phi
);
2279 bb
= gimple_bb (phi
);
2280 rhs
= degenerate_phi_result (phi
);
2283 stmt
= gimple_build_assign (res
, rhs
);
2284 remove_phi_node (psi
, false);
2286 gsi
= gsi_after_labels (bb
);
2287 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2290 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2293 rewrite_reductions_out_of_ssa (scop_p scop
)
2296 gimple_stmt_iterator psi
;
2297 sese region
= SCOP_REGION (scop
);
2300 if (bb_in_sese_p (bb
, region
))
2301 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2303 gimple phi
= gsi_stmt (psi
);
2305 if (virtual_operand_p (gimple_phi_result (phi
)))
2311 if (gimple_phi_num_args (phi
) > 1
2312 && degenerate_phi_result (phi
))
2313 rewrite_degenerate_phi (&psi
);
2315 else if (scalar_close_phi_node_p (phi
))
2316 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2318 else if (reduction_phi_p (region
, &psi
))
2319 rewrite_phi_out_of_ssa (scop
, &psi
);
2322 update_ssa (TODO_update_ssa
);
2323 #ifdef ENABLE_CHECKING
2324 verify_loop_closed_ssa (true);
2328 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2329 read from ZERO_DIM_ARRAY. */
2332 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2333 tree def
, gimple use_stmt
)
2338 use_operand_p use_p
;
2340 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2342 name
= copy_ssa_name (def
, NULL
);
2343 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2345 gimple_assign_set_lhs (name_stmt
, name
);
2346 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2348 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2349 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2350 replace_exp (use_p
, name
);
2352 update_stmt (use_stmt
);
2355 /* For every definition DEF in the SCOP that is used outside the scop,
2356 insert a closing-scop definition in the basic block just after this
2360 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2362 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2363 tree new_name
= make_ssa_name (var
, stmt
);
2364 bool needs_copy
= false;
2365 use_operand_p use_p
;
2366 imm_use_iterator imm_iter
;
2368 sese region
= SCOP_REGION (scop
);
2370 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2372 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2374 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2376 SET_USE (use_p
, new_name
);
2378 update_stmt (use_stmt
);
2383 /* Insert in the empty BB just after the scop a use of DEF such
2384 that the rewrite of cross_bb_scalar_dependences won't insert
2385 arrays everywhere else. */
2388 gimple assign
= gimple_build_assign (new_name
, def
);
2389 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2391 update_stmt (assign
);
2392 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2396 /* Rewrite the scalar dependences crossing the boundary of the BB
2397 containing STMT with an array. Return true when something has been
2401 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2403 sese region
= SCOP_REGION (scop
);
2404 gimple stmt
= gsi_stmt (*gsi
);
2405 imm_use_iterator imm_iter
;
2408 tree zero_dim_array
= NULL_TREE
;
2412 switch (gimple_code (stmt
))
2415 def
= gimple_assign_lhs (stmt
);
2419 def
= gimple_call_lhs (stmt
);
2427 || !is_gimple_reg (def
))
2430 if (scev_analyzable_p (def
, region
))
2432 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2433 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2435 if (tree_contains_chrecs (scev
, NULL
))
2438 propagate_expr_outside_region (def
, scev
, region
);
2442 def_bb
= gimple_bb (stmt
);
2444 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2446 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2447 if (gimple_code (use_stmt
) == GIMPLE_PHI
2450 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2452 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2453 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2455 rewrite_phi_out_of_ssa (scop
, &psi
);
2458 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2459 if (gimple_code (use_stmt
) != GIMPLE_PHI
2460 && def_bb
!= gimple_bb (use_stmt
)
2461 && !is_gimple_debug (use_stmt
)
2464 if (!zero_dim_array
)
2466 zero_dim_array
= create_zero_dim_array
2467 (def
, "Cross_BB_scalar_dependence");
2468 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2469 SSA_NAME_DEF_STMT (def
));
2473 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2480 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2483 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2486 gimple_stmt_iterator psi
;
2487 sese region
= SCOP_REGION (scop
);
2488 bool changed
= false;
2490 /* Create an extra empty BB after the scop. */
2491 split_edge (SESE_EXIT (region
));
2494 if (bb_in_sese_p (bb
, region
))
2495 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2496 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2501 update_ssa (TODO_update_ssa
);
2502 #ifdef ENABLE_CHECKING
2503 verify_loop_closed_ssa (true);
2508 /* Returns the number of pbbs that are in loops contained in SCOP. */
2511 nb_pbbs_in_loops (scop_p scop
)
2517 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2518 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2524 /* Return the number of data references in BB that write in
2528 nb_data_writes_in_bb (basic_block bb
)
2531 gimple_stmt_iterator gsi
;
2533 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2534 if (gimple_vdef (gsi_stmt (gsi
)))
2540 /* Splits at STMT the basic block BB represented as PBB in the
2544 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2546 edge e1
= split_block (bb
, stmt
);
2547 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2551 /* Splits STMT out of its current BB. This is done for reduction
2552 statements for which we want to ignore data dependences. */
2555 split_reduction_stmt (scop_p scop
, gimple stmt
)
2557 basic_block bb
= gimple_bb (stmt
);
2558 poly_bb_p pbb
= pbb_from_bb (bb
);
2559 gimple_bb_p gbb
= gbb_from_bb (bb
);
2562 data_reference_p dr
;
2564 /* Do not split basic blocks with no writes to memory: the reduction
2565 will be the only write to memory. */
2566 if (nb_data_writes_in_bb (bb
) == 0
2567 /* Or if we have already marked BB as a reduction. */
2568 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2571 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2573 /* Split once more only when the reduction stmt is not the only one
2574 left in the original BB. */
2575 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2577 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2579 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2582 /* A part of the data references will end in a different basic block
2583 after the split: move the DRs from the original GBB to the newly
2585 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2587 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2591 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2592 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2593 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2601 /* Return true when stmt is a reduction operation. */
2604 is_reduction_operation_p (gimple stmt
)
2606 enum tree_code code
;
2608 gcc_assert (is_gimple_assign (stmt
));
2609 code
= gimple_assign_rhs_code (stmt
);
2611 return flag_associative_math
2612 && commutative_tree_code (code
)
2613 && associative_tree_code (code
);
2616 /* Returns true when PHI contains an argument ARG. */
2619 phi_contains_arg (gimple phi
, tree arg
)
2623 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2624 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2630 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2633 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2637 if (TREE_CODE (arg
) != SSA_NAME
)
2640 stmt
= SSA_NAME_DEF_STMT (arg
);
2642 if (gimple_code (stmt
) == GIMPLE_NOP
2643 || gimple_code (stmt
) == GIMPLE_CALL
)
2646 if (gimple_code (stmt
) == GIMPLE_PHI
)
2648 if (phi_contains_arg (stmt
, lhs
))
2653 if (!is_gimple_assign (stmt
))
2656 if (gimple_num_ops (stmt
) == 2)
2657 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2659 if (is_reduction_operation_p (stmt
))
2661 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2664 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2670 /* Detect commutative and associative scalar reductions starting at
2671 the STMT. Return the phi node of the reduction cycle, or NULL. */
2674 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2678 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2683 in
->safe_push (stmt
);
2684 out
->safe_push (stmt
);
2688 /* Detect commutative and associative scalar reductions starting at
2689 STMT. Return the phi node of the reduction cycle, or NULL. */
2692 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2695 tree lhs
= gimple_assign_lhs (stmt
);
2697 if (gimple_num_ops (stmt
) == 2)
2698 return detect_commutative_reduction_arg (lhs
, stmt
,
2699 gimple_assign_rhs1 (stmt
),
2702 if (is_reduction_operation_p (stmt
))
2704 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2705 gimple_assign_rhs1 (stmt
),
2708 : detect_commutative_reduction_arg (lhs
, stmt
,
2709 gimple_assign_rhs2 (stmt
),
2716 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2719 follow_inital_value_to_phi (tree arg
, tree lhs
)
2723 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2726 stmt
= SSA_NAME_DEF_STMT (arg
);
2728 if (gimple_code (stmt
) == GIMPLE_PHI
2729 && phi_contains_arg (stmt
, lhs
))
2736 /* Return the argument of the loop PHI that is the initial value coming
2737 from outside the loop. */
2740 edge_initial_value_for_loop_phi (gimple phi
)
2744 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2746 edge e
= gimple_phi_arg_edge (phi
, i
);
2748 if (loop_depth (e
->src
->loop_father
)
2749 < loop_depth (e
->dest
->loop_father
))
2756 /* Return the argument of the loop PHI that is the initial value coming
2757 from outside the loop. */
2760 initial_value_for_loop_phi (gimple phi
)
2764 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2766 edge e
= gimple_phi_arg_edge (phi
, i
);
2768 if (loop_depth (e
->src
->loop_father
)
2769 < loop_depth (e
->dest
->loop_father
))
2770 return gimple_phi_arg_def (phi
, i
);
2776 /* Returns true when DEF is used outside the reduction cycle of
2780 used_outside_reduction (tree def
, gimple loop_phi
)
2782 use_operand_p use_p
;
2783 imm_use_iterator imm_iter
;
2784 loop_p loop
= loop_containing_stmt (loop_phi
);
2786 /* In LOOP, DEF should be used only in LOOP_PHI. */
2787 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2789 gimple stmt
= USE_STMT (use_p
);
2791 if (stmt
!= loop_phi
2792 && !is_gimple_debug (stmt
)
2793 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2800 /* Detect commutative and associative scalar reductions belonging to
2801 the SCOP starting at the loop closed phi node STMT. Return the phi
2802 node of the reduction cycle, or NULL. */
2805 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2808 if (scalar_close_phi_node_p (stmt
))
2810 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2811 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2813 if (TREE_CODE (arg
) != SSA_NAME
)
2816 /* Note that loop close phi nodes should have a single argument
2817 because we translated the representation into a canonical form
2818 before Graphite: see canonicalize_loop_closed_ssa_form. */
2819 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2821 def
= SSA_NAME_DEF_STMT (arg
);
2822 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2823 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2826 lhs
= gimple_phi_result (close_phi
);
2827 init
= initial_value_for_loop_phi (loop_phi
);
2828 phi
= follow_inital_value_to_phi (init
, lhs
);
2830 if (phi
&& (used_outside_reduction (lhs
, phi
)
2831 || !has_single_use (gimple_phi_result (phi
))))
2834 in
->safe_push (loop_phi
);
2835 out
->safe_push (close_phi
);
2839 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2840 return detect_commutative_reduction_assign (stmt
, in
, out
);
2845 /* Translate the scalar reduction statement STMT to an array RED
2846 knowing that its recursive phi node is LOOP_PHI. */
2849 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2850 gimple stmt
, gimple loop_phi
)
2852 tree res
= gimple_phi_result (loop_phi
);
2853 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2854 gimple_stmt_iterator gsi
;
2856 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2858 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2859 gsi
= gsi_for_stmt (stmt
);
2861 insert_stmts (scop
, assign
, NULL
, gsi
);
2864 /* Removes the PHI node and resets all the debug stmts that are using
2868 remove_phi (gimple phi
)
2870 imm_use_iterator imm_iter
;
2872 use_operand_p use_p
;
2873 gimple_stmt_iterator gsi
;
2874 stack_vec
<gimple
, 3> update
;
2878 def
= PHI_RESULT (phi
);
2879 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2881 stmt
= USE_STMT (use_p
);
2883 if (is_gimple_debug (stmt
))
2885 gimple_debug_bind_reset_value (stmt
);
2886 update
.safe_push (stmt
);
2890 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2893 gsi
= gsi_for_phi_node (phi
);
2894 remove_phi_node (&gsi
, false);
2897 /* Helper function for for_each_index. For each INDEX of the data
2898 reference REF, returns true when its indices are valid in the loop
2899 nest LOOP passed in as DATA. */
2902 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2905 basic_block header
, def_bb
;
2908 if (TREE_CODE (*index
) != SSA_NAME
)
2911 loop
= *((loop_p
*) data
);
2912 header
= loop
->header
;
2913 stmt
= SSA_NAME_DEF_STMT (*index
);
2918 def_bb
= gimple_bb (stmt
);
2923 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2926 /* When the result of a CLOSE_PHI is written to a memory location,
2927 return a pointer to that memory reference, otherwise return
2931 close_phi_written_to_memory (gimple close_phi
)
2933 imm_use_iterator imm_iter
;
2934 use_operand_p use_p
;
2936 tree res
, def
= gimple_phi_result (close_phi
);
2938 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2939 if ((stmt
= USE_STMT (use_p
))
2940 && gimple_code (stmt
) == GIMPLE_ASSIGN
2941 && (res
= gimple_assign_lhs (stmt
)))
2943 switch (TREE_CODE (res
))
2953 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2954 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2956 /* FIXME: this restriction is for id-{24,25}.f and
2957 could be handled by duplicating the computation of
2958 array indices before the loop of the close_phi. */
2959 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2971 /* Rewrite out of SSA the reduction described by the loop phi nodes
2972 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2975 IN: stmt, loop_n, ..., loop_0
2976 OUT: stmt, close_n, ..., close_0
2978 the first element is the reduction statement, and the next elements
2979 are the loop and close phi nodes of each of the outer loops. */
2982 translate_scalar_reduction_to_array (scop_p scop
,
2987 unsigned int i
= out
.length () - 1;
2988 tree red
= close_phi_written_to_memory (out
[i
]);
2990 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2992 gimple close_phi
= out
[i
];
2996 gimple stmt
= loop_phi
;
2997 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2998 poly_bb_p pbb
= pbb_from_bb (bb
);
2999 PBB_IS_REDUCTION (pbb
) = true;
3000 gcc_assert (close_phi
== loop_phi
);
3003 red
= create_zero_dim_array
3004 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3006 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3010 if (i
== in
.length () - 1)
3012 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3013 unshare_expr (red
), close_phi
);
3014 insert_out_of_ssa_copy_on_edge
3015 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3016 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3019 remove_phi (loop_phi
);
3020 remove_phi (close_phi
);
3024 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3025 true when something has been changed. */
3028 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3032 stack_vec
<gimple
, 10> in
;
3033 stack_vec
<gimple
, 10> out
;
3035 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3036 res
= in
.length () > 1;
3038 translate_scalar_reduction_to_array (scop
, in
, out
);
3043 /* Rewrites all the commutative reductions from LOOP out of SSA.
3044 Returns true when something has been changed. */
3047 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3050 gimple_stmt_iterator gsi
;
3051 edge exit
= single_exit (loop
);
3053 bool changed
= false;
3058 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3059 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3060 && !virtual_operand_p (res
)
3061 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3062 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3063 (scop
, gsi_stmt (gsi
));
3068 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3071 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3074 bool changed
= false;
3075 sese region
= SCOP_REGION (scop
);
3077 FOR_EACH_LOOP (loop
, 0)
3078 if (loop_in_sese_p (loop
, region
))
3079 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3084 gsi_commit_edge_inserts ();
3085 update_ssa (TODO_update_ssa
);
3086 #ifdef ENABLE_CHECKING
3087 verify_loop_closed_ssa (true);
3092 /* Can all ivs be represented by a signed integer?
3093 As CLooG might generate negative values in its expressions, signed loop ivs
3094 are required in the backend. */
3097 scop_ivs_can_be_represented (scop_p scop
)
3100 gimple_stmt_iterator psi
;
3103 FOR_EACH_LOOP (loop
, 0)
3105 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3108 for (psi
= gsi_start_phis (loop
->header
);
3109 !gsi_end_p (psi
); gsi_next (&psi
))
3111 gimple phi
= gsi_stmt (psi
);
3112 tree res
= PHI_RESULT (phi
);
3113 tree type
= TREE_TYPE (res
);
3115 if (TYPE_UNSIGNED (type
)
3116 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3129 /* Builds the polyhedral representation for a SESE region. */
3132 build_poly_scop (scop_p scop
)
3134 sese region
= SCOP_REGION (scop
);
3135 graphite_dim_t max_dim
;
3137 build_scop_bbs (scop
);
3139 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3140 Once CLooG is fixed, remove this guard. Anyways, it makes no
3141 sense to optimize a scop containing only PBBs that do not belong
3143 if (nb_pbbs_in_loops (scop
) == 0)
3146 if (!scop_ivs_can_be_represented (scop
))
3149 if (flag_associative_math
)
3150 rewrite_commutative_reductions_out_of_ssa (scop
);
3152 build_sese_loop_nests (region
);
3153 /* Record all conditions in REGION. */
3154 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3155 find_scop_parameters (scop
);
3157 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3158 if (scop_nb_params (scop
) > max_dim
)
3161 build_scop_iteration_domain (scop
);
3162 build_scop_context (scop
);
3163 add_conditions_to_constraints (scop
);
3165 /* Rewrite out of SSA only after having translated the
3166 representation to the polyhedral representation to avoid scev
3167 analysis failures. That means that these functions will insert
3168 new data references that they create in the right place. */
3169 rewrite_reductions_out_of_ssa (scop
);
3170 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3172 build_scop_drs (scop
);
3174 build_scop_scattering (scop
);
3176 /* This SCoP has been translated to the polyhedral
3178 POLY_SCOP_P (scop
) = true;