1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2014 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>
30 /* For C++ linkage of C functions.
31 Missing from isl/val_gmp.h in isl 0.12 versions.
32 Appearing in isl/val_gmp.h in isl 0.13.
33 To be removed when passing to isl 0.13. */
34 #if defined(__cplusplus)
37 #include <isl/val_gmp.h>
38 #if defined(__cplusplus)
42 #include <cloog/cloog.h>
43 #include <cloog/cloog.h>
44 #include <cloog/isl/domain.h>
49 #include "coretypes.h"
57 #include "hard-reg-set.h"
60 #include "dominance.h"
62 #include "basic-block.h"
63 #include "tree-ssa-alias.h"
64 #include "internal-fn.h"
65 #include "gimple-expr.h"
68 #include "gimple-iterator.h"
70 #include "gimplify-me.h"
71 #include "gimple-ssa.h"
73 #include "tree-phinodes.h"
74 #include "ssa-iterators.h"
75 #include "stringpool.h"
76 #include "tree-ssanames.h"
77 #include "tree-ssa-loop-manip.h"
78 #include "tree-ssa-loop-niter.h"
79 #include "tree-ssa-loop.h"
80 #include "tree-into-ssa.h"
81 #include "tree-pass.h"
83 #include "tree-chrec.h"
84 #include "tree-data-ref.h"
85 #include "tree-scalar-evolution.h"
88 #include "tree-ssa-propagate.h"
92 #include "graphite-poly.h"
93 #include "graphite-sese-to-poly.h"
96 /* Assigns to RES the value of the INTEGER_CST T. */
99 tree_int_to_gmp (tree t
, mpz_t res
)
101 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
104 /* Returns the index of the PHI argument defined in the outermost
108 phi_arg_in_outermost_loop (gimple phi
)
110 loop_p loop
= gimple_bb (phi
)->loop_father
;
113 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
114 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
116 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
123 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
124 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
127 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
129 gimple phi
= gsi_stmt (*psi
);
130 tree res
= gimple_phi_result (phi
);
131 size_t entry
= phi_arg_in_outermost_loop (phi
);
132 tree init
= gimple_phi_arg_def (phi
, entry
);
133 gimple stmt
= gimple_build_assign (res
, init
);
134 edge e
= gimple_phi_arg_edge (phi
, entry
);
136 remove_phi_node (psi
, false);
137 gsi_insert_on_edge_immediate (e
, stmt
);
140 /* Removes an invariant phi node at position PSI by inserting on the
141 loop ENTRY edge the assignment RES = INIT. */
144 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
146 gimple phi
= gsi_stmt (*psi
);
147 loop_p loop
= loop_containing_stmt (phi
);
148 tree res
= gimple_phi_result (phi
);
149 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
150 size_t entry
= phi_arg_in_outermost_loop (phi
);
151 edge e
= gimple_phi_arg_edge (phi
, entry
);
154 gimple_seq stmts
= NULL
;
156 if (tree_contains_chrecs (scev
, NULL
))
157 scev
= gimple_phi_arg_def (phi
, entry
);
159 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
160 stmt
= gimple_build_assign (res
, var
);
161 remove_phi_node (psi
, false);
163 gimple_seq_add_stmt (&stmts
, stmt
);
164 gsi_insert_seq_on_edge (e
, stmts
);
165 gsi_commit_edge_inserts ();
166 SSA_NAME_DEF_STMT (res
) = stmt
;
169 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
172 simple_copy_phi_p (gimple phi
)
176 if (gimple_phi_num_args (phi
) != 2)
179 res
= gimple_phi_result (phi
);
180 return (res
== gimple_phi_arg_def (phi
, 0)
181 || res
== gimple_phi_arg_def (phi
, 1));
184 /* Returns true when the phi node at position PSI is a reduction phi
185 node in REGION. Otherwise moves the pointer PSI to the next phi to
189 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
192 gimple phi
= gsi_stmt (*psi
);
193 tree res
= gimple_phi_result (phi
);
195 loop
= loop_containing_stmt (phi
);
197 if (simple_copy_phi_p (phi
))
199 /* PRE introduces phi nodes like these, for an example,
200 see id-5.f in the fortran graphite testsuite:
202 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
204 remove_simple_copy_phi (psi
);
208 if (scev_analyzable_p (res
, region
))
210 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
212 if (evolution_function_is_invariant_p (scev
, loop
->num
))
213 remove_invariant_phi (region
, psi
);
220 /* All the other cases are considered reductions. */
224 /* Store the GRAPHITE representation of BB. */
227 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
229 struct gimple_bb
*gbb
;
231 gbb
= XNEW (struct gimple_bb
);
234 GBB_DATA_REFS (gbb
) = drs
;
235 GBB_CONDITIONS (gbb
).create (0);
236 GBB_CONDITION_CASES (gbb
).create (0);
242 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
245 struct data_reference
*dr
;
247 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
250 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
252 free (bap
->alias_set
);
261 free_gimple_bb (struct gimple_bb
*gbb
)
263 free_data_refs_aux (GBB_DATA_REFS (gbb
));
264 free_data_refs (GBB_DATA_REFS (gbb
));
266 GBB_CONDITIONS (gbb
).release ();
267 GBB_CONDITION_CASES (gbb
).release ();
268 GBB_BB (gbb
)->aux
= 0;
272 /* Deletes all gimple bbs in SCOP. */
275 remove_gbbs_in_scop (scop_p scop
)
280 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
281 free_gimple_bb (PBB_BLACK_BOX (pbb
));
284 /* Deletes all scops in SCOPS. */
287 free_scops (vec
<scop_p
> scops
)
292 FOR_EACH_VEC_ELT (scops
, i
, scop
)
294 remove_gbbs_in_scop (scop
);
295 free_sese (SCOP_REGION (scop
));
302 /* Same as outermost_loop_in_sese, returns the outermost loop
303 containing BB in REGION, but makes sure that the returned loop
304 belongs to the REGION, and so this returns the first loop in the
305 REGION when the loop containing BB does not belong to REGION. */
308 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
310 loop_p nest
= outermost_loop_in_sese (region
, bb
);
312 if (loop_in_sese_p (nest
, region
))
315 /* When the basic block BB does not belong to a loop in the region,
316 return the first loop in the region. */
319 if (loop_in_sese_p (nest
, region
))
328 /* Generates a polyhedral black box only if the bb contains interesting
332 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
334 vec
<data_reference_p
> drs
;
336 sese region
= SCOP_REGION (scop
);
337 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
338 gimple_stmt_iterator gsi
;
340 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
342 gimple stmt
= gsi_stmt (gsi
);
345 if (is_gimple_debug (stmt
))
348 loop
= loop_containing_stmt (stmt
);
349 if (!loop_in_sese_p (loop
, region
))
352 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
355 return new_gimple_bb (bb
, drs
);
358 /* Returns true if all predecessors of BB, that are not dominated by BB, are
359 marked in MAP. The predecessors dominated by BB are loop latches and will
360 be handled after BB. */
363 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
368 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
369 if (!bitmap_bit_p (map
, e
->src
->index
)
370 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
376 /* Compare the depth of two basic_block's P1 and P2. */
379 compare_bb_depths (const void *p1
, const void *p2
)
381 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
382 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
383 int d1
= loop_depth (bb1
->loop_father
);
384 int d2
= loop_depth (bb2
->loop_father
);
395 /* Sort the basic blocks from DOM such that the first are the ones at
396 a deepest loop level. */
399 graphite_sort_dominated_info (vec
<basic_block
> dom
)
401 dom
.qsort (compare_bb_depths
);
404 /* Recursive helper function for build_scops_bbs. */
407 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
409 sese region
= SCOP_REGION (scop
);
410 vec
<basic_block
> dom
;
413 if (bitmap_bit_p (visited
, bb
->index
)
414 || !bb_in_sese_p (bb
, region
))
417 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
418 SCOP_BBS (scop
).safe_push (pbb
);
419 bitmap_set_bit (visited
, bb
->index
);
421 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
426 graphite_sort_dominated_info (dom
);
428 while (!dom
.is_empty ())
433 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
434 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
436 build_scop_bbs_1 (scop
, visited
, dom_bb
);
437 dom
.unordered_remove (i
);
445 /* Gather the basic blocks belonging to the SCOP. */
448 build_scop_bbs (scop_p scop
)
450 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
451 sese region
= SCOP_REGION (scop
);
453 bitmap_clear (visited
);
454 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
455 sbitmap_free (visited
);
458 /* Return an ISL identifier for the polyhedral basic block PBB. */
461 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
464 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
465 return isl_id_alloc (s
->ctx
, name
, pbb
);
468 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
469 We generate SCATTERING_DIMENSIONS scattering dimensions.
471 CLooG 0.15.0 and previous versions require, that all
472 scattering functions of one CloogProgram have the same number of
473 scattering dimensions, therefore we allow to specify it. This
474 should be removed in future versions of CLooG.
476 The scattering polyhedron consists of these dimensions: scattering,
477 loop_iterators, parameters.
481 | scattering_dimensions = 5
482 | used_scattering_dimensions = 3
490 | Scattering polyhedron:
492 | scattering: {s1, s2, s3, s4, s5}
493 | loop_iterators: {i}
494 | parameters: {p1, p2}
496 | s1 s2 s3 s4 s5 i p1 p2 1
497 | 1 0 0 0 0 0 0 0 -4 = 0
498 | 0 1 0 0 0 -1 0 0 0 = 0
499 | 0 0 1 0 0 0 0 0 -5 = 0 */
502 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
503 poly_bb_p pbb
, int scattering_dimensions
)
506 int nb_iterators
= pbb_dim_iter_domain (pbb
);
507 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
511 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
513 dc
= isl_set_get_space (pbb
->domain
);
514 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
515 isl_dim_out
, scattering_dimensions
);
516 pbb
->schedule
= isl_map_universe (dm
);
518 for (i
= 0; i
< scattering_dimensions
; i
++)
520 /* Textual order inside this loop. */
523 isl_constraint
*c
= isl_equality_alloc
524 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
526 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
528 val
= isl_val_neg (val
);
529 c
= isl_constraint_set_constant_val (c
, val
);
530 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
531 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
534 /* Iterations of this loop. */
535 else /* if ((i % 2) == 1) */
537 int loop
= (i
- 1) / 2;
538 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
543 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
546 /* Build for BB the static schedule.
548 The static schedule is a Dewey numbering of the abstract syntax
549 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
551 The following example informally defines the static schedule:
570 Static schedules for A to F:
583 build_scop_scattering (scop_p scop
)
587 gimple_bb_p previous_gbb
= NULL
;
588 isl_space
*dc
= isl_set_get_space (scop
->context
);
589 isl_aff
*static_sched
;
591 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
592 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
594 /* We have to start schedules at 0 on the first component and
595 because we cannot compare_prefix_loops against a previous loop,
596 prefix will be equal to zero, and that index will be
597 incremented before copying. */
598 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
600 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
602 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
604 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
607 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
613 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
615 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
618 isl_aff_free (static_sched
);
621 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
623 /* Extract an affine expression from the chain of recurrence E. */
626 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
628 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
629 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
630 isl_local_space
*ls
= isl_local_space_from_space (space
);
631 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
632 isl_aff
*loop
= isl_aff_set_coefficient_si
633 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
634 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
636 /* Before multiplying, make sure that the result is affine. */
637 gcc_assert (isl_pw_aff_is_cst (rhs
)
638 || isl_pw_aff_is_cst (l
));
640 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
643 /* Extract an affine expression from the mult_expr E. */
646 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
648 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
649 isl_space_copy (space
));
650 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
652 if (!isl_pw_aff_is_cst (lhs
)
653 && !isl_pw_aff_is_cst (rhs
))
655 isl_pw_aff_free (lhs
);
656 isl_pw_aff_free (rhs
);
660 return isl_pw_aff_mul (lhs
, rhs
);
663 /* Return an ISL identifier from the name of the ssa_name E. */
666 isl_id_for_ssa_name (scop_p s
, tree e
)
668 const char *name
= get_name (e
);
672 id
= isl_id_alloc (s
->ctx
, name
, e
);
676 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
677 id
= isl_id_alloc (s
->ctx
, name1
, e
);
683 /* Return an ISL identifier for the data reference DR. */
686 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
688 /* Data references all get the same isl_id. They need to be comparable
689 and are distinguished through the first dimension, which contains the
691 return isl_id_alloc (s
->ctx
, "", 0);
694 /* Extract an affine expression from the ssa_name E. */
697 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
704 id
= isl_id_for_ssa_name (s
, e
);
705 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
707 dom
= isl_set_universe (isl_space_copy (space
));
708 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
709 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
710 return isl_pw_aff_alloc (dom
, aff
);
713 /* Extract an affine expression from the gmp constant G. */
716 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
718 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
719 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
720 isl_set
*dom
= isl_set_universe (space
);
724 ct
= isl_aff_get_ctx (aff
);
725 v
= isl_val_int_from_gmp (ct
, g
);
726 aff
= isl_aff_add_constant_val (aff
, v
);
728 return isl_pw_aff_alloc (dom
, aff
);
731 /* Extract an affine expression from the integer_cst E. */
734 extract_affine_int (tree e
, __isl_take isl_space
*space
)
740 tree_int_to_gmp (e
, g
);
741 res
= extract_affine_gmp (g
, space
);
747 /* Compute pwaff mod 2^width. */
749 extern isl_ctx
*the_isl_ctx
;
752 wrap (isl_pw_aff
*pwaff
, unsigned width
)
756 mod
= isl_val_int_from_ui(the_isl_ctx
, width
);
757 mod
= isl_val_2exp (mod
);
758 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
763 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
764 Otherwise returns -1. */
767 parameter_index_in_region_1 (tree name
, sese region
)
772 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
774 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
781 /* When the parameter NAME is in REGION, returns its index in
782 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
783 and returns the index of NAME. */
786 parameter_index_in_region (tree name
, sese region
)
790 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
792 i
= parameter_index_in_region_1 (name
, region
);
796 gcc_assert (SESE_ADD_PARAMS (region
));
798 i
= SESE_PARAMS (region
).length ();
799 SESE_PARAMS (region
).safe_push (name
);
803 /* Extract an affine expression from the tree E in the scop S. */
806 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
808 isl_pw_aff
*lhs
, *rhs
, *res
;
811 if (e
== chrec_dont_know
) {
812 isl_space_free (space
);
816 switch (TREE_CODE (e
))
818 case POLYNOMIAL_CHREC
:
819 res
= extract_affine_chrec (s
, e
, space
);
823 res
= extract_affine_mul (s
, e
, space
);
827 case POINTER_PLUS_EXPR
:
828 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
829 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
830 res
= isl_pw_aff_add (lhs
, rhs
);
834 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
835 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
836 res
= isl_pw_aff_sub (lhs
, rhs
);
841 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
842 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
843 res
= isl_pw_aff_mul (lhs
, rhs
);
847 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
848 res
= extract_affine_name (s
, e
, space
);
852 res
= extract_affine_int (e
, space
);
853 /* No need to wrap a single integer. */
857 case NON_LVALUE_EXPR
:
858 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
866 type
= TREE_TYPE (e
);
867 if (TYPE_UNSIGNED (type
))
868 res
= wrap (res
, TYPE_PRECISION (type
));
873 /* In the context of sese S, scan the expression E and translate it to
874 a linear expression C. When parsing a symbolic multiplication, K
875 represents the constant multiplier of an expression containing
879 scan_tree_for_params (sese s
, tree e
)
881 if (e
== chrec_dont_know
)
884 switch (TREE_CODE (e
))
886 case POLYNOMIAL_CHREC
:
887 scan_tree_for_params (s
, CHREC_LEFT (e
));
891 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
892 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
894 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
898 case POINTER_PLUS_EXPR
:
900 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
901 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
907 case NON_LVALUE_EXPR
:
908 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
912 parameter_index_in_region (e
, s
);
925 /* Find parameters with respect to REGION in BB. We are looking in memory
926 access functions, conditions and loop bounds. */
929 find_params_in_bb (sese region
, gimple_bb_p gbb
)
935 loop_p loop
= GBB_BB (gbb
)->loop_father
;
937 /* Find parameters in the access functions of data references. */
938 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
939 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
940 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
942 /* Find parameters in conditional statements. */
943 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
945 tree lhs
= scalar_evolution_in_region (region
, loop
,
946 gimple_cond_lhs (stmt
));
947 tree rhs
= scalar_evolution_in_region (region
, loop
,
948 gimple_cond_rhs (stmt
));
950 scan_tree_for_params (region
, lhs
);
951 scan_tree_for_params (region
, rhs
);
955 /* Record the parameters used in the SCOP. A variable is a parameter
956 in a scop if it does not vary during the execution of that scop. */
959 find_scop_parameters (scop_p scop
)
963 sese region
= SCOP_REGION (scop
);
967 /* Find the parameters used in the loop bounds. */
968 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
970 tree nb_iters
= number_of_latch_executions (loop
);
972 if (!chrec_contains_symbols (nb_iters
))
975 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
976 scan_tree_for_params (region
, nb_iters
);
979 /* Find the parameters used in data accesses. */
980 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
981 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
983 nbp
= sese_nb_params (region
);
984 scop_set_nb_params (scop
, nbp
);
985 SESE_ADD_PARAMS (region
) = false;
989 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
991 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
992 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
993 isl_id_for_ssa_name (scop
, e
));
995 scop
->context
= isl_set_universe (space
);
999 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1000 the constraints for the surrounding loops. */
1003 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1005 isl_set
*outer
, isl_set
**doms
)
1007 tree nb_iters
= number_of_latch_executions (loop
);
1008 sese region
= SCOP_REGION (scop
);
1010 isl_set
*inner
= isl_set_copy (outer
);
1013 int pos
= isl_set_dim (outer
, isl_dim_set
);
1019 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1020 space
= isl_set_get_space (inner
);
1023 c
= isl_inequality_alloc
1024 (isl_local_space_from_space (isl_space_copy (space
)));
1025 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1026 inner
= isl_set_add_constraint (inner
, c
);
1028 /* loop_i <= cst_nb_iters */
1029 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1031 c
= isl_inequality_alloc
1032 (isl_local_space_from_space (isl_space_copy (space
)));
1033 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1034 tree_int_to_gmp (nb_iters
, g
);
1035 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1036 c
= isl_constraint_set_constant_val (c
, v
);
1037 inner
= isl_set_add_constraint (inner
, c
);
1040 /* loop_i <= expr_nb_iters */
1041 else if (!chrec_contains_undetermined (nb_iters
))
1046 isl_local_space
*ls
;
1050 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1052 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1053 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1054 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1055 isl_set_dim (valid
, isl_dim_set
));
1056 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1058 ls
= isl_local_space_from_space (isl_space_copy (space
));
1059 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1060 isl_dim_in
, pos
, 1);
1061 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1062 isl_pw_aff_copy (aff
));
1063 inner
= isl_set_intersect (inner
, le
);
1065 if (max_stmt_executions (loop
, &nit
))
1067 /* Insert in the context the constraints from the
1068 estimation of the number of iterations NIT and the
1069 symbolic number of iterations (involving parameter
1070 names) NB_ITERS. First, build the affine expression
1071 "NIT - NB_ITERS" and then say that it is positive,
1072 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1079 wi::to_mpz (nit
, g
, SIGNED
);
1080 mpz_sub_ui (g
, g
, 1);
1081 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1082 x
= isl_pw_aff_ge_set (approx
, aff
);
1083 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1084 isl_set_dim (x
, isl_dim_set
));
1085 scop
->context
= isl_set_intersect (scop
->context
, x
);
1087 c
= isl_inequality_alloc
1088 (isl_local_space_from_space (isl_space_copy (space
)));
1089 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1090 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1092 c
= isl_constraint_set_constant_val (c
, v
);
1093 inner
= isl_set_add_constraint (inner
, c
);
1096 isl_pw_aff_free (aff
);
1101 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1102 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1103 isl_set_copy (inner
), doms
);
1107 && loop_in_sese_p (loop
->next
, region
))
1108 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1109 isl_set_copy (outer
), doms
);
1111 doms
[loop
->num
] = inner
;
1113 isl_set_free (outer
);
1114 isl_space_free (space
);
1118 /* Returns a linear expression for tree T evaluated in PBB. */
1121 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1123 scop_p scop
= PBB_SCOP (pbb
);
1125 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1126 gcc_assert (!automatically_generated_chrec_p (t
));
1128 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1131 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1132 operator. This allows us to invert the condition or to handle
1136 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1138 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1139 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1145 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1149 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1153 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1157 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1161 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1165 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1169 isl_pw_aff_free (lhs
);
1170 isl_pw_aff_free (rhs
);
1174 cond
= isl_set_coalesce (cond
);
1175 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1176 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1179 /* Add conditions to the domain of PBB. */
1182 add_conditions_to_domain (poly_bb_p pbb
)
1186 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1188 if (GBB_CONDITIONS (gbb
).is_empty ())
1191 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1192 switch (gimple_code (stmt
))
1196 enum tree_code code
= gimple_cond_code (stmt
);
1198 /* The conditions for ELSE-branches are inverted. */
1199 if (!GBB_CONDITION_CASES (gbb
)[i
])
1200 code
= invert_tree_comparison (code
, false);
1202 add_condition_to_pbb (pbb
, stmt
, code
);
1207 /* Switch statements are not supported right now - fall through. */
1215 /* Traverses all the GBBs of the SCOP and add their constraints to the
1216 iteration domains. */
1219 add_conditions_to_constraints (scop_p scop
)
1224 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1225 add_conditions_to_domain (pbb
);
1228 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1229 edge between BB and its predecessor is not a loop exit edge, and
1230 the last statement of the single predecessor is a COND_EXPR. */
1233 single_pred_cond_non_loop_exit (basic_block bb
)
1235 if (single_pred_p (bb
))
1237 edge e
= single_pred_edge (bb
);
1238 basic_block pred
= e
->src
;
1241 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1244 stmt
= last_stmt (pred
);
1246 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1253 class sese_dom_walker
: public dom_walker
1256 sese_dom_walker (cdi_direction
, sese
);
1258 virtual void before_dom_children (basic_block
);
1259 virtual void after_dom_children (basic_block
);
1262 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1266 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1267 : dom_walker (direction
), m_region (region
)
1271 /* Call-back for dom_walk executed before visiting the dominated
1275 sese_dom_walker::before_dom_children (basic_block bb
)
1280 if (!bb_in_sese_p (bb
, m_region
))
1283 stmt
= single_pred_cond_non_loop_exit (bb
);
1287 edge e
= single_pred_edge (bb
);
1289 m_conditions
.safe_push (stmt
);
1291 if (e
->flags
& EDGE_TRUE_VALUE
)
1292 m_cases
.safe_push (stmt
);
1294 m_cases
.safe_push (NULL
);
1297 gbb
= gbb_from_bb (bb
);
1301 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1302 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1306 /* Call-back for dom_walk executed after visiting the dominated
1310 sese_dom_walker::after_dom_children (basic_block bb
)
1312 if (!bb_in_sese_p (bb
, m_region
))
1315 if (single_pred_cond_non_loop_exit (bb
))
1317 m_conditions
.pop ();
1322 /* Add constraints on the possible values of parameter P from the type
1326 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1328 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1329 tree type
= TREE_TYPE (parameter
);
1330 tree lb
= NULL_TREE
;
1331 tree ub
= NULL_TREE
;
1333 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1334 lb
= lower_bound_in_type (type
, type
);
1336 lb
= TYPE_MIN_VALUE (type
);
1338 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1339 ub
= upper_bound_in_type (type
, type
);
1341 ub
= TYPE_MAX_VALUE (type
);
1345 isl_space
*space
= isl_set_get_space (scop
->context
);
1350 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1352 tree_int_to_gmp (lb
, g
);
1353 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1354 v
= isl_val_neg (v
);
1356 c
= isl_constraint_set_constant_val (c
, v
);
1357 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1359 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1364 isl_space
*space
= isl_set_get_space (scop
->context
);
1369 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1372 tree_int_to_gmp (ub
, g
);
1373 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1375 c
= isl_constraint_set_constant_val (c
, v
);
1376 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1378 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1382 /* Build the context of the SCOP. The context usually contains extra
1383 constraints that are added to the iteration domains that constrain
1387 build_scop_context (scop_p scop
)
1389 graphite_dim_t p
, n
= scop_nb_params (scop
);
1391 for (p
= 0; p
< n
; p
++)
1392 add_param_constraints (scop
, p
);
1395 /* Build the iteration domains: the loops belonging to the current
1396 SCOP, and that vary for the execution of the current basic block.
1397 Returns false if there is no loop in SCOP. */
1400 build_scop_iteration_domain (scop_p scop
)
1403 sese region
= SCOP_REGION (scop
);
1406 int nb_loops
= number_of_loops (cfun
);
1407 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1409 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1410 if (!loop_in_sese_p (loop_outer (loop
), region
))
1411 build_loop_iteration_domains (scop
, loop
, 0,
1412 isl_set_copy (scop
->context
), doms
);
1414 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1416 loop
= pbb_loop (pbb
);
1418 if (doms
[loop
->num
])
1419 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1421 pbb
->domain
= isl_set_copy (scop
->context
);
1423 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1424 isl_id_for_pbb (scop
, pbb
));
1427 for (i
= 0; i
< nb_loops
; i
++)
1429 isl_set_free (doms
[i
]);
1434 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1435 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1436 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1440 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1443 int alias_set_num
= 0;
1444 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1446 if (bap
&& bap
->alias_set
)
1447 alias_set_num
= *(bap
->alias_set
);
1449 c
= isl_equality_alloc
1450 (isl_local_space_from_space (isl_map_get_space (acc
)));
1451 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1452 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1454 return isl_map_add_constraint (acc
, c
);
1457 /* Assign the affine expression INDEX to the output dimension POS of
1458 MAP and return the result. */
1461 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1464 int len
= isl_map_dim (map
, isl_dim_out
);
1467 index_map
= isl_map_from_pw_aff (index
);
1468 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1469 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1471 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1472 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1473 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1474 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1476 return isl_map_intersect (map
, index_map
);
1479 /* Add to ACCESSES polyhedron equalities defining the access functions
1480 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1481 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1482 PBB is the poly_bb_p that contains the data reference DR. */
1485 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1487 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1488 scop_p scop
= PBB_SCOP (pbb
);
1490 for (i
= 0; i
< nb_subscripts
; i
++)
1493 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1495 aff
= extract_affine (scop
, afn
,
1496 isl_space_domain (isl_map_get_space (acc
)));
1497 acc
= set_index (acc
, i
+ 1, aff
);
1503 /* Add constrains representing the size of the accessed data to the
1504 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1505 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1509 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1511 tree ref
= DR_REF (dr
);
1512 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1514 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1518 if (TREE_CODE (ref
) != ARRAY_REF
)
1521 low
= array_ref_low_bound (ref
);
1522 high
= array_ref_up_bound (ref
);
1524 /* XXX The PPL code dealt separately with
1525 subscript - low >= 0 and high - subscript >= 0 in case one of
1526 the two bounds isn't known. Do the same here? */
1528 if (tree_fits_shwi_p (low
)
1530 && tree_fits_shwi_p (high
)
1531 /* 1-element arrays at end of structures may extend over
1532 their declared size. */
1533 && !(array_at_struct_end_p (ref
)
1534 && operand_equal_p (low
, high
, 0)))
1538 isl_set
*univ
, *lbs
, *ubs
;
1542 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1543 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1546 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1547 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1548 isl_set_dim (valid
, isl_dim_set
));
1549 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1551 space
= isl_set_get_space (extent
);
1552 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1553 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1554 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1555 index
= isl_pw_aff_alloc (univ
, aff
);
1557 id
= isl_set_get_tuple_id (extent
);
1558 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1559 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1561 /* low <= sub_i <= high */
1562 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1563 ubs
= isl_pw_aff_le_set (index
, ub
);
1564 extent
= isl_set_intersect (extent
, lbs
);
1565 extent
= isl_set_intersect (extent
, ubs
);
1572 /* Build data accesses for DR in PBB. */
1575 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1577 int dr_base_object_set
;
1580 scop_p scop
= PBB_SCOP (pbb
);
1583 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1584 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1585 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1586 isl_dim_out
, nb_out
);
1588 acc
= isl_map_universe (space
);
1589 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1592 acc
= pdr_add_alias_set (acc
, dr
);
1593 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1596 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1597 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1598 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1599 int alias_set_num
= 0;
1600 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1602 if (bap
&& bap
->alias_set
)
1603 alias_set_num
= *(bap
->alias_set
);
1605 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1606 extent
= isl_set_nat_universe (space
);
1607 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1608 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1611 gcc_assert (dr
->aux
);
1612 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1614 new_poly_dr (pbb
, dr_base_object_set
,
1615 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1616 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1619 /* Write to FILE the alias graph of data references in DIMACS format. */
1622 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1623 vec
<data_reference_p
> drs
)
1625 int num_vertex
= drs
.length ();
1627 data_reference_p dr1
, dr2
;
1630 if (num_vertex
== 0)
1633 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1634 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1635 if (dr_may_alias_p (dr1
, dr2
, true))
1638 fprintf (file
, "$\n");
1641 fprintf (file
, "c %s\n", comment
);
1643 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1645 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1646 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1647 if (dr_may_alias_p (dr1
, dr2
, true))
1648 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1653 /* Write to FILE the alias graph of data references in DOT format. */
1656 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1657 vec
<data_reference_p
> drs
)
1659 int num_vertex
= drs
.length ();
1660 data_reference_p dr1
, dr2
;
1663 if (num_vertex
== 0)
1666 fprintf (file
, "$\n");
1669 fprintf (file
, "c %s\n", comment
);
1671 /* First print all the vertices. */
1672 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1673 fprintf (file
, "n%d;\n", i
);
1675 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1676 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1677 if (dr_may_alias_p (dr1
, dr2
, true))
1678 fprintf (file
, "n%d n%d\n", i
, j
);
1683 /* Write to FILE the alias graph of data references in ECC format. */
1686 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1687 vec
<data_reference_p
> drs
)
1689 int num_vertex
= drs
.length ();
1690 data_reference_p dr1
, dr2
;
1693 if (num_vertex
== 0)
1696 fprintf (file
, "$\n");
1699 fprintf (file
, "c %s\n", comment
);
1701 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1702 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1703 if (dr_may_alias_p (dr1
, dr2
, true))
1704 fprintf (file
, "%d %d\n", i
, j
);
1709 /* Check if DR1 and DR2 are in the same object set. */
1712 dr_same_base_object_p (const struct data_reference
*dr1
,
1713 const struct data_reference
*dr2
)
1715 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1718 /* Uses DFS component number as representative of alias-sets. Also tests for
1719 optimality by verifying if every connected component is a clique. Returns
1720 true (1) if the above test is true, and false (0) otherwise. */
1723 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1725 int num_vertices
= drs
.length ();
1726 struct graph
*g
= new_graph (num_vertices
);
1727 data_reference_p dr1
, dr2
;
1729 int num_connected_components
;
1730 int v_indx1
, v_indx2
, num_vertices_in_component
;
1733 struct graph_edge
*e
;
1734 int this_component_is_clique
;
1735 int all_components_are_cliques
= 1;
1737 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1738 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1739 if (dr_may_alias_p (dr1
, dr2
, true))
1745 all_vertices
= XNEWVEC (int, num_vertices
);
1746 vertices
= XNEWVEC (int, num_vertices
);
1747 for (i
= 0; i
< num_vertices
; i
++)
1748 all_vertices
[i
] = i
;
1750 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1752 for (i
= 0; i
< g
->n_vertices
; i
++)
1754 data_reference_p dr
= drs
[i
];
1755 base_alias_pair
*bap
;
1757 gcc_assert (dr
->aux
);
1758 bap
= (base_alias_pair
*)(dr
->aux
);
1760 bap
->alias_set
= XNEW (int);
1761 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1764 /* Verify if the DFS numbering results in optimal solution. */
1765 for (i
= 0; i
< num_connected_components
; i
++)
1767 num_vertices_in_component
= 0;
1768 /* Get all vertices whose DFS component number is the same as i. */
1769 for (j
= 0; j
< num_vertices
; j
++)
1770 if (g
->vertices
[j
].component
== i
)
1771 vertices
[num_vertices_in_component
++] = j
;
1773 /* Now test if the vertices in 'vertices' form a clique, by testing
1774 for edges among each pair. */
1775 this_component_is_clique
= 1;
1776 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1778 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1780 /* Check if the two vertices are connected by iterating
1781 through all the edges which have one of these are source. */
1782 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1785 if (e
->src
== vertices
[v_indx1
])
1791 this_component_is_clique
= 0;
1795 if (!this_component_is_clique
)
1796 all_components_are_cliques
= 0;
1800 free (all_vertices
);
1803 return all_components_are_cliques
;
1806 /* Group each data reference in DRS with its base object set num. */
1809 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1811 int num_vertex
= drs
.length ();
1812 struct graph
*g
= new_graph (num_vertex
);
1813 data_reference_p dr1
, dr2
;
1817 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1818 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1819 if (dr_same_base_object_p (dr1
, dr2
))
1825 queue
= XNEWVEC (int, num_vertex
);
1826 for (i
= 0; i
< num_vertex
; i
++)
1829 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1831 for (i
= 0; i
< g
->n_vertices
; i
++)
1833 data_reference_p dr
= drs
[i
];
1834 base_alias_pair
*bap
;
1836 gcc_assert (dr
->aux
);
1837 bap
= (base_alias_pair
*)(dr
->aux
);
1839 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1846 /* Build the data references for PBB. */
1849 build_pbb_drs (poly_bb_p pbb
)
1852 data_reference_p dr
;
1853 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1855 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1856 build_poly_dr (dr
, pbb
);
1859 /* Dump to file the alias graphs for the data references in DRS. */
1862 dump_alias_graphs (vec
<data_reference_p
> drs
)
1865 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1867 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1870 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1871 current_function_name ());
1872 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1873 fclose (file_dimacs
);
1876 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1879 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1880 current_function_name ());
1881 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1885 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1888 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1889 current_function_name ());
1890 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1895 /* Build data references in SCOP. */
1898 build_scop_drs (scop_p scop
)
1902 data_reference_p dr
;
1903 auto_vec
<data_reference_p
, 3> drs
;
1905 /* Remove all the PBBs that do not have data references: these basic
1906 blocks are not handled in the polyhedral representation. */
1907 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1908 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1910 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1912 SCOP_BBS (scop
).ordered_remove (i
);
1916 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1917 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1920 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1921 dr
->aux
= XNEW (base_alias_pair
);
1923 if (!build_alias_set_optimal_p (drs
))
1925 /* TODO: Add support when building alias set is not optimal. */
1929 build_base_obj_set_for_drs (drs
);
1931 /* When debugging, enable the following code. This cannot be used
1932 in production compilers. */
1934 dump_alias_graphs (drs
);
1938 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1939 build_pbb_drs (pbb
);
1942 /* Return a gsi at the position of the phi node STMT. */
1944 static gimple_stmt_iterator
1945 gsi_for_phi_node (gimple stmt
)
1947 gimple_stmt_iterator psi
;
1948 basic_block bb
= gimple_bb (stmt
);
1950 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1951 if (stmt
== gsi_stmt (psi
))
1958 /* Analyze all the data references of STMTS and add them to the
1959 GBB_DATA_REFS vector of BB. */
1962 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1968 sese region
= SCOP_REGION (scop
);
1970 if (!bb_in_sese_p (bb
, region
))
1973 nest
= outermost_loop_in_sese_1 (region
, bb
);
1974 gbb
= gbb_from_bb (bb
);
1976 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1980 if (is_gimple_debug (stmt
))
1983 loop
= loop_containing_stmt (stmt
);
1984 if (!loop_in_sese_p (loop
, region
))
1987 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1988 &GBB_DATA_REFS (gbb
));
1992 /* Insert STMT at the end of the STMTS sequence and then insert the
1993 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1997 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1998 gimple_stmt_iterator insert_gsi
)
2000 gimple_stmt_iterator gsi
;
2001 auto_vec
<gimple
, 3> x
;
2003 gimple_seq_add_stmt (&stmts
, stmt
);
2004 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2005 x
.safe_push (gsi_stmt (gsi
));
2007 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2008 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2011 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2014 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2017 gimple_stmt_iterator gsi
;
2018 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2019 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2020 auto_vec
<gimple
, 3> x
;
2022 gimple_seq_add_stmt (&stmts
, stmt
);
2023 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2024 x
.safe_push (gsi_stmt (gsi
));
2026 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2028 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2029 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2033 gsi
= gsi_for_stmt (after_stmt
);
2034 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2037 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2040 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2043 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2045 vec
<data_reference_p
> drs
;
2047 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2048 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2049 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2050 int index
, n
= SCOP_BBS (scop
).length ();
2052 /* The INDEX of PBB in SCOP_BBS. */
2053 for (index
= 0; index
< n
; index
++)
2054 if (SCOP_BBS (scop
)[index
] == pbb
)
2057 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2058 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2059 isl_id_for_pbb (scop
, pbb1
));
2061 GBB_PBB (gbb1
) = pbb1
;
2062 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2063 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2064 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2067 /* Insert on edge E the assignment "RES := EXPR". */
2070 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2072 gimple_stmt_iterator gsi
;
2073 gimple_seq stmts
= NULL
;
2074 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2075 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2077 auto_vec
<gimple
, 3> x
;
2079 gimple_seq_add_stmt (&stmts
, stmt
);
2080 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2081 x
.safe_push (gsi_stmt (gsi
));
2083 gsi_insert_seq_on_edge (e
, stmts
);
2084 gsi_commit_edge_inserts ();
2085 bb
= gimple_bb (stmt
);
2087 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2090 if (!gbb_from_bb (bb
))
2091 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2093 analyze_drs_in_stmts (scop
, bb
, x
);
2096 /* Creates a zero dimension array of the same type as VAR. */
2099 create_zero_dim_array (tree var
, const char *base_name
)
2101 tree index_type
= build_index_type (integer_zero_node
);
2102 tree elt_type
= TREE_TYPE (var
);
2103 tree array_type
= build_array_type (elt_type
, index_type
);
2104 tree base
= create_tmp_var (array_type
, base_name
);
2106 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2110 /* Returns true when PHI is a loop close phi node. */
2113 scalar_close_phi_node_p (gimple phi
)
2115 if (gimple_code (phi
) != GIMPLE_PHI
2116 || virtual_operand_p (gimple_phi_result (phi
)))
2119 /* Note that loop close phi nodes should have a single argument
2120 because we translated the representation into a canonical form
2121 before Graphite: see canonicalize_loop_closed_ssa_form. */
2122 return (gimple_phi_num_args (phi
) == 1);
2125 /* For a definition DEF in REGION, propagates the expression EXPR in
2126 all the uses of DEF outside REGION. */
2129 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2131 imm_use_iterator imm_iter
;
2134 bool replaced_once
= false;
2136 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2138 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2141 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2142 if (!is_gimple_debug (use_stmt
)
2143 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2146 use_operand_p use_p
;
2148 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2149 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2150 && (replaced_once
= true))
2151 replace_exp (use_p
, expr
);
2153 update_stmt (use_stmt
);
2158 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2159 gsi_commit_edge_inserts ();
2163 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2164 dimension array for it. */
2167 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2169 sese region
= SCOP_REGION (scop
);
2170 gimple phi
= gsi_stmt (*psi
);
2171 tree res
= gimple_phi_result (phi
);
2172 basic_block bb
= gimple_bb (phi
);
2173 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2174 tree arg
= gimple_phi_arg_def (phi
, 0);
2177 /* Note that loop close phi nodes should have a single argument
2178 because we translated the representation into a canonical form
2179 before Graphite: see canonicalize_loop_closed_ssa_form. */
2180 gcc_assert (gimple_phi_num_args (phi
) == 1);
2182 /* The phi node can be a non close phi node, when its argument is
2183 invariant, or a default definition. */
2184 if (is_gimple_min_invariant (arg
)
2185 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2187 propagate_expr_outside_region (res
, arg
, region
);
2192 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2194 propagate_expr_outside_region (res
, arg
, region
);
2195 stmt
= gimple_build_assign (res
, arg
);
2196 remove_phi_node (psi
, false);
2197 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2201 /* If res is scev analyzable and is not a scalar value, it is safe
2202 to ignore the close phi node: it will be code generated in the
2203 out of Graphite pass. */
2204 else if (scev_analyzable_p (res
, region
))
2206 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2209 if (!loop_in_sese_p (loop
, region
))
2211 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2212 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2213 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2216 scev
= scalar_evolution_in_region (region
, loop
, res
);
2218 if (tree_does_not_contain_chrecs (scev
))
2219 propagate_expr_outside_region (res
, scev
, region
);
2226 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2228 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2230 if (TREE_CODE (arg
) == SSA_NAME
)
2231 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2232 SSA_NAME_DEF_STMT (arg
));
2234 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2235 zero_dim_array
, arg
);
2238 remove_phi_node (psi
, false);
2239 SSA_NAME_DEF_STMT (res
) = stmt
;
2241 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2244 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2245 dimension array for it. */
2248 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2251 gimple phi
= gsi_stmt (*psi
);
2252 basic_block bb
= gimple_bb (phi
);
2253 tree res
= gimple_phi_result (phi
);
2254 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2257 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2259 tree arg
= gimple_phi_arg_def (phi
, i
);
2260 edge e
= gimple_phi_arg_edge (phi
, i
);
2262 /* Avoid the insertion of code in the loop latch to please the
2263 pattern matching of the vectorizer. */
2264 if (TREE_CODE (arg
) == SSA_NAME
2265 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2266 && e
->src
== bb
->loop_father
->latch
)
2267 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2268 SSA_NAME_DEF_STMT (arg
));
2270 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2273 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2274 remove_phi_node (psi
, false);
2275 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2278 /* Rewrite the degenerate phi node at position PSI from the degenerate
2279 form "x = phi (y, y, ..., y)" to "x = y". */
2282 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2286 gimple_stmt_iterator gsi
;
2287 gimple phi
= gsi_stmt (*psi
);
2288 tree res
= gimple_phi_result (phi
);
2291 bb
= gimple_bb (phi
);
2292 rhs
= degenerate_phi_result (phi
);
2295 stmt
= gimple_build_assign (res
, rhs
);
2296 remove_phi_node (psi
, false);
2298 gsi
= gsi_after_labels (bb
);
2299 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2302 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2305 rewrite_reductions_out_of_ssa (scop_p scop
)
2308 gimple_stmt_iterator psi
;
2309 sese region
= SCOP_REGION (scop
);
2311 FOR_EACH_BB_FN (bb
, cfun
)
2312 if (bb_in_sese_p (bb
, region
))
2313 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2315 gimple phi
= gsi_stmt (psi
);
2317 if (virtual_operand_p (gimple_phi_result (phi
)))
2323 if (gimple_phi_num_args (phi
) > 1
2324 && degenerate_phi_result (phi
))
2325 rewrite_degenerate_phi (&psi
);
2327 else if (scalar_close_phi_node_p (phi
))
2328 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2330 else if (reduction_phi_p (region
, &psi
))
2331 rewrite_phi_out_of_ssa (scop
, &psi
);
2334 update_ssa (TODO_update_ssa
);
2335 #ifdef ENABLE_CHECKING
2336 verify_loop_closed_ssa (true);
2340 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2341 read from ZERO_DIM_ARRAY. */
2344 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2345 tree def
, gimple use_stmt
)
2350 use_operand_p use_p
;
2352 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2354 name
= copy_ssa_name (def
, NULL
);
2355 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2357 gimple_assign_set_lhs (name_stmt
, name
);
2358 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2360 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2361 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2362 replace_exp (use_p
, name
);
2364 update_stmt (use_stmt
);
2367 /* For every definition DEF in the SCOP that is used outside the scop,
2368 insert a closing-scop definition in the basic block just after this
2372 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2374 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2375 tree new_name
= make_ssa_name (var
, stmt
);
2376 bool needs_copy
= false;
2377 use_operand_p use_p
;
2378 imm_use_iterator imm_iter
;
2380 sese region
= SCOP_REGION (scop
);
2382 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2384 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2386 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2388 SET_USE (use_p
, new_name
);
2390 update_stmt (use_stmt
);
2395 /* Insert in the empty BB just after the scop a use of DEF such
2396 that the rewrite of cross_bb_scalar_dependences won't insert
2397 arrays everywhere else. */
2400 gimple assign
= gimple_build_assign (new_name
, def
);
2401 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2403 update_stmt (assign
);
2404 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2408 /* Rewrite the scalar dependences crossing the boundary of the BB
2409 containing STMT with an array. Return true when something has been
2413 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2415 sese region
= SCOP_REGION (scop
);
2416 gimple stmt
= gsi_stmt (*gsi
);
2417 imm_use_iterator imm_iter
;
2420 tree zero_dim_array
= NULL_TREE
;
2424 switch (gimple_code (stmt
))
2427 def
= gimple_assign_lhs (stmt
);
2431 def
= gimple_call_lhs (stmt
);
2439 || !is_gimple_reg (def
))
2442 if (scev_analyzable_p (def
, region
))
2444 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2445 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2447 if (tree_contains_chrecs (scev
, NULL
))
2450 propagate_expr_outside_region (def
, scev
, region
);
2454 def_bb
= gimple_bb (stmt
);
2456 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2458 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2459 if (gimple_code (use_stmt
) == GIMPLE_PHI
2462 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2464 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2465 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2467 rewrite_phi_out_of_ssa (scop
, &psi
);
2470 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2471 if (gimple_code (use_stmt
) != GIMPLE_PHI
2472 && def_bb
!= gimple_bb (use_stmt
)
2473 && !is_gimple_debug (use_stmt
)
2476 if (!zero_dim_array
)
2478 zero_dim_array
= create_zero_dim_array
2479 (def
, "Cross_BB_scalar_dependence");
2480 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2481 SSA_NAME_DEF_STMT (def
));
2485 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2492 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2495 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2498 gimple_stmt_iterator psi
;
2499 sese region
= SCOP_REGION (scop
);
2500 bool changed
= false;
2502 /* Create an extra empty BB after the scop. */
2503 split_edge (SESE_EXIT (region
));
2505 FOR_EACH_BB_FN (bb
, cfun
)
2506 if (bb_in_sese_p (bb
, region
))
2507 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2508 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2513 update_ssa (TODO_update_ssa
);
2514 #ifdef ENABLE_CHECKING
2515 verify_loop_closed_ssa (true);
2520 /* Returns the number of pbbs that are in loops contained in SCOP. */
2523 nb_pbbs_in_loops (scop_p scop
)
2529 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2530 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2536 /* Return the number of data references in BB that write in
2540 nb_data_writes_in_bb (basic_block bb
)
2543 gimple_stmt_iterator gsi
;
2545 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2546 if (gimple_vdef (gsi_stmt (gsi
)))
2552 /* Splits at STMT the basic block BB represented as PBB in the
2556 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2558 edge e1
= split_block (bb
, stmt
);
2559 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2563 /* Splits STMT out of its current BB. This is done for reduction
2564 statements for which we want to ignore data dependences. */
2567 split_reduction_stmt (scop_p scop
, gimple stmt
)
2569 basic_block bb
= gimple_bb (stmt
);
2570 poly_bb_p pbb
= pbb_from_bb (bb
);
2571 gimple_bb_p gbb
= gbb_from_bb (bb
);
2574 data_reference_p dr
;
2576 /* Do not split basic blocks with no writes to memory: the reduction
2577 will be the only write to memory. */
2578 if (nb_data_writes_in_bb (bb
) == 0
2579 /* Or if we have already marked BB as a reduction. */
2580 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2583 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2585 /* Split once more only when the reduction stmt is not the only one
2586 left in the original BB. */
2587 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2589 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2591 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2594 /* A part of the data references will end in a different basic block
2595 after the split: move the DRs from the original GBB to the newly
2597 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2599 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2603 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2604 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2605 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2613 /* Return true when stmt is a reduction operation. */
2616 is_reduction_operation_p (gimple stmt
)
2618 enum tree_code code
;
2620 gcc_assert (is_gimple_assign (stmt
));
2621 code
= gimple_assign_rhs_code (stmt
);
2623 return flag_associative_math
2624 && commutative_tree_code (code
)
2625 && associative_tree_code (code
);
2628 /* Returns true when PHI contains an argument ARG. */
2631 phi_contains_arg (gimple phi
, tree arg
)
2635 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2636 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2642 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2645 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2649 if (TREE_CODE (arg
) != SSA_NAME
)
2652 stmt
= SSA_NAME_DEF_STMT (arg
);
2654 if (gimple_code (stmt
) == GIMPLE_NOP
2655 || gimple_code (stmt
) == GIMPLE_CALL
)
2658 if (gimple_code (stmt
) == GIMPLE_PHI
)
2660 if (phi_contains_arg (stmt
, lhs
))
2665 if (!is_gimple_assign (stmt
))
2668 if (gimple_num_ops (stmt
) == 2)
2669 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2671 if (is_reduction_operation_p (stmt
))
2673 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2676 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2682 /* Detect commutative and associative scalar reductions starting at
2683 the STMT. Return the phi node of the reduction cycle, or NULL. */
2686 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2690 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2695 in
->safe_push (stmt
);
2696 out
->safe_push (stmt
);
2700 /* Detect commutative and associative scalar reductions starting at
2701 STMT. Return the phi node of the reduction cycle, or NULL. */
2704 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2707 tree lhs
= gimple_assign_lhs (stmt
);
2709 if (gimple_num_ops (stmt
) == 2)
2710 return detect_commutative_reduction_arg (lhs
, stmt
,
2711 gimple_assign_rhs1 (stmt
),
2714 if (is_reduction_operation_p (stmt
))
2716 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2717 gimple_assign_rhs1 (stmt
),
2720 : detect_commutative_reduction_arg (lhs
, stmt
,
2721 gimple_assign_rhs2 (stmt
),
2728 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2731 follow_inital_value_to_phi (tree arg
, tree lhs
)
2735 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2738 stmt
= SSA_NAME_DEF_STMT (arg
);
2740 if (gimple_code (stmt
) == GIMPLE_PHI
2741 && phi_contains_arg (stmt
, lhs
))
2748 /* Return the argument of the loop PHI that is the initial value coming
2749 from outside the loop. */
2752 edge_initial_value_for_loop_phi (gimple phi
)
2756 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2758 edge e
= gimple_phi_arg_edge (phi
, i
);
2760 if (loop_depth (e
->src
->loop_father
)
2761 < loop_depth (e
->dest
->loop_father
))
2768 /* Return the argument of the loop PHI that is the initial value coming
2769 from outside the loop. */
2772 initial_value_for_loop_phi (gimple phi
)
2776 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2778 edge e
= gimple_phi_arg_edge (phi
, i
);
2780 if (loop_depth (e
->src
->loop_father
)
2781 < loop_depth (e
->dest
->loop_father
))
2782 return gimple_phi_arg_def (phi
, i
);
2788 /* Returns true when DEF is used outside the reduction cycle of
2792 used_outside_reduction (tree def
, gimple loop_phi
)
2794 use_operand_p use_p
;
2795 imm_use_iterator imm_iter
;
2796 loop_p loop
= loop_containing_stmt (loop_phi
);
2798 /* In LOOP, DEF should be used only in LOOP_PHI. */
2799 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2801 gimple stmt
= USE_STMT (use_p
);
2803 if (stmt
!= loop_phi
2804 && !is_gimple_debug (stmt
)
2805 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2812 /* Detect commutative and associative scalar reductions belonging to
2813 the SCOP starting at the loop closed phi node STMT. Return the phi
2814 node of the reduction cycle, or NULL. */
2817 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2820 if (scalar_close_phi_node_p (stmt
))
2822 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2823 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2825 if (TREE_CODE (arg
) != SSA_NAME
)
2828 /* Note that loop close phi nodes should have a single argument
2829 because we translated the representation into a canonical form
2830 before Graphite: see canonicalize_loop_closed_ssa_form. */
2831 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2833 def
= SSA_NAME_DEF_STMT (arg
);
2834 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2835 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2838 lhs
= gimple_phi_result (close_phi
);
2839 init
= initial_value_for_loop_phi (loop_phi
);
2840 phi
= follow_inital_value_to_phi (init
, lhs
);
2842 if (phi
&& (used_outside_reduction (lhs
, phi
)
2843 || !has_single_use (gimple_phi_result (phi
))))
2846 in
->safe_push (loop_phi
);
2847 out
->safe_push (close_phi
);
2851 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2852 return detect_commutative_reduction_assign (stmt
, in
, out
);
2857 /* Translate the scalar reduction statement STMT to an array RED
2858 knowing that its recursive phi node is LOOP_PHI. */
2861 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2862 gimple stmt
, gimple loop_phi
)
2864 tree res
= gimple_phi_result (loop_phi
);
2865 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2866 gimple_stmt_iterator gsi
;
2868 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2870 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2871 gsi
= gsi_for_stmt (stmt
);
2873 insert_stmts (scop
, assign
, NULL
, gsi
);
2876 /* Removes the PHI node and resets all the debug stmts that are using
2880 remove_phi (gimple phi
)
2882 imm_use_iterator imm_iter
;
2884 use_operand_p use_p
;
2885 gimple_stmt_iterator gsi
;
2886 auto_vec
<gimple
, 3> update
;
2890 def
= PHI_RESULT (phi
);
2891 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2893 stmt
= USE_STMT (use_p
);
2895 if (is_gimple_debug (stmt
))
2897 gimple_debug_bind_reset_value (stmt
);
2898 update
.safe_push (stmt
);
2902 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2905 gsi
= gsi_for_phi_node (phi
);
2906 remove_phi_node (&gsi
, false);
2909 /* Helper function for for_each_index. For each INDEX of the data
2910 reference REF, returns true when its indices are valid in the loop
2911 nest LOOP passed in as DATA. */
2914 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2917 basic_block header
, def_bb
;
2920 if (TREE_CODE (*index
) != SSA_NAME
)
2923 loop
= *((loop_p
*) data
);
2924 header
= loop
->header
;
2925 stmt
= SSA_NAME_DEF_STMT (*index
);
2930 def_bb
= gimple_bb (stmt
);
2935 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2938 /* When the result of a CLOSE_PHI is written to a memory location,
2939 return a pointer to that memory reference, otherwise return
2943 close_phi_written_to_memory (gimple close_phi
)
2945 imm_use_iterator imm_iter
;
2946 use_operand_p use_p
;
2948 tree res
, def
= gimple_phi_result (close_phi
);
2950 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2951 if ((stmt
= USE_STMT (use_p
))
2952 && gimple_code (stmt
) == GIMPLE_ASSIGN
2953 && (res
= gimple_assign_lhs (stmt
)))
2955 switch (TREE_CODE (res
))
2965 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2966 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2968 /* FIXME: this restriction is for id-{24,25}.f and
2969 could be handled by duplicating the computation of
2970 array indices before the loop of the close_phi. */
2971 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2983 /* Rewrite out of SSA the reduction described by the loop phi nodes
2984 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2987 IN: stmt, loop_n, ..., loop_0
2988 OUT: stmt, close_n, ..., close_0
2990 the first element is the reduction statement, and the next elements
2991 are the loop and close phi nodes of each of the outer loops. */
2994 translate_scalar_reduction_to_array (scop_p scop
,
2999 unsigned int i
= out
.length () - 1;
3000 tree red
= close_phi_written_to_memory (out
[i
]);
3002 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
3004 gimple close_phi
= out
[i
];
3008 gimple stmt
= loop_phi
;
3009 basic_block bb
= split_reduction_stmt (scop
, stmt
);
3010 poly_bb_p pbb
= pbb_from_bb (bb
);
3011 PBB_IS_REDUCTION (pbb
) = true;
3012 gcc_assert (close_phi
== loop_phi
);
3015 red
= create_zero_dim_array
3016 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3018 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3022 if (i
== in
.length () - 1)
3024 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3025 unshare_expr (red
), close_phi
);
3026 insert_out_of_ssa_copy_on_edge
3027 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3028 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3031 remove_phi (loop_phi
);
3032 remove_phi (close_phi
);
3036 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3037 true when something has been changed. */
3040 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3044 auto_vec
<gimple
, 10> in
;
3045 auto_vec
<gimple
, 10> out
;
3047 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3048 res
= in
.length () > 1;
3050 translate_scalar_reduction_to_array (scop
, in
, out
);
3055 /* Rewrites all the commutative reductions from LOOP out of SSA.
3056 Returns true when something has been changed. */
3059 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3062 gimple_stmt_iterator gsi
;
3063 edge exit
= single_exit (loop
);
3065 bool changed
= false;
3070 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3071 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3072 && !virtual_operand_p (res
)
3073 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3074 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3075 (scop
, gsi_stmt (gsi
));
3080 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3083 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3086 bool changed
= false;
3087 sese region
= SCOP_REGION (scop
);
3089 FOR_EACH_LOOP (loop
, 0)
3090 if (loop_in_sese_p (loop
, region
))
3091 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3096 gsi_commit_edge_inserts ();
3097 update_ssa (TODO_update_ssa
);
3098 #ifdef ENABLE_CHECKING
3099 verify_loop_closed_ssa (true);
3104 /* Can all ivs be represented by a signed integer?
3105 As CLooG might generate negative values in its expressions, signed loop ivs
3106 are required in the backend. */
3109 scop_ivs_can_be_represented (scop_p scop
)
3112 gimple_stmt_iterator psi
;
3115 FOR_EACH_LOOP (loop
, 0)
3117 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3120 for (psi
= gsi_start_phis (loop
->header
);
3121 !gsi_end_p (psi
); gsi_next (&psi
))
3123 gimple phi
= gsi_stmt (psi
);
3124 tree res
= PHI_RESULT (phi
);
3125 tree type
= TREE_TYPE (res
);
3127 if (TYPE_UNSIGNED (type
)
3128 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3141 /* Builds the polyhedral representation for a SESE region. */
3144 build_poly_scop (scop_p scop
)
3146 sese region
= SCOP_REGION (scop
);
3147 graphite_dim_t max_dim
;
3149 build_scop_bbs (scop
);
3151 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3152 Once CLooG is fixed, remove this guard. Anyways, it makes no
3153 sense to optimize a scop containing only PBBs that do not belong
3155 if (nb_pbbs_in_loops (scop
) == 0)
3158 if (!scop_ivs_can_be_represented (scop
))
3161 if (flag_associative_math
)
3162 rewrite_commutative_reductions_out_of_ssa (scop
);
3164 build_sese_loop_nests (region
);
3165 /* Record all conditions in REGION. */
3166 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3167 find_scop_parameters (scop
);
3169 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3170 if (scop_nb_params (scop
) > max_dim
)
3173 build_scop_iteration_domain (scop
);
3174 build_scop_context (scop
);
3175 add_conditions_to_constraints (scop
);
3177 /* Rewrite out of SSA only after having translated the
3178 representation to the polyhedral representation to avoid scev
3179 analysis failures. That means that these functions will insert
3180 new data references that they create in the right place. */
3181 rewrite_reductions_out_of_ssa (scop
);
3182 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3184 build_scop_drs (scop
);
3186 build_scop_scattering (scop
);
3188 /* This SCoP has been translated to the polyhedral
3190 POLY_SCOP_P (scop
) = true;