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"
38 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "stringpool.h"
46 #include "tree-ssanames.h"
47 #include "tree-ssa-loop-manip.h"
48 #include "tree-ssa-loop-niter.h"
49 #include "tree-ssa-loop.h"
50 #include "tree-into-ssa.h"
51 #include "tree-pass.h"
53 #include "tree-chrec.h"
54 #include "tree-data-ref.h"
55 #include "tree-scalar-evolution.h"
58 #include "tree-ssa-propagate.h"
63 #include "graphite-poly.h"
64 #include "graphite-sese-to-poly.h"
67 /* Assigns to RES the value of the INTEGER_CST T. */
70 tree_int_to_gmp (tree t
, mpz_t res
)
72 double_int di
= tree_to_double_int (t
);
73 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
76 /* Returns the index of the PHI argument defined in the outermost
80 phi_arg_in_outermost_loop (gimple phi
)
82 loop_p loop
= gimple_bb (phi
)->loop_father
;
85 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
86 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
88 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
95 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
96 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
99 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
101 gimple phi
= gsi_stmt (*psi
);
102 tree res
= gimple_phi_result (phi
);
103 size_t entry
= phi_arg_in_outermost_loop (phi
);
104 tree init
= gimple_phi_arg_def (phi
, entry
);
105 gimple stmt
= gimple_build_assign (res
, init
);
106 edge e
= gimple_phi_arg_edge (phi
, entry
);
108 remove_phi_node (psi
, false);
109 gsi_insert_on_edge_immediate (e
, stmt
);
112 /* Removes an invariant phi node at position PSI by inserting on the
113 loop ENTRY edge the assignment RES = INIT. */
116 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
118 gimple phi
= gsi_stmt (*psi
);
119 loop_p loop
= loop_containing_stmt (phi
);
120 tree res
= gimple_phi_result (phi
);
121 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
122 size_t entry
= phi_arg_in_outermost_loop (phi
);
123 edge e
= gimple_phi_arg_edge (phi
, entry
);
126 gimple_seq stmts
= NULL
;
128 if (tree_contains_chrecs (scev
, NULL
))
129 scev
= gimple_phi_arg_def (phi
, entry
);
131 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
132 stmt
= gimple_build_assign (res
, var
);
133 remove_phi_node (psi
, false);
135 gimple_seq_add_stmt (&stmts
, stmt
);
136 gsi_insert_seq_on_edge (e
, stmts
);
137 gsi_commit_edge_inserts ();
138 SSA_NAME_DEF_STMT (res
) = stmt
;
141 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
144 simple_copy_phi_p (gimple phi
)
148 if (gimple_phi_num_args (phi
) != 2)
151 res
= gimple_phi_result (phi
);
152 return (res
== gimple_phi_arg_def (phi
, 0)
153 || res
== gimple_phi_arg_def (phi
, 1));
156 /* Returns true when the phi node at position PSI is a reduction phi
157 node in REGION. Otherwise moves the pointer PSI to the next phi to
161 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
164 gimple phi
= gsi_stmt (*psi
);
165 tree res
= gimple_phi_result (phi
);
167 loop
= loop_containing_stmt (phi
);
169 if (simple_copy_phi_p (phi
))
171 /* PRE introduces phi nodes like these, for an example,
172 see id-5.f in the fortran graphite testsuite:
174 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
176 remove_simple_copy_phi (psi
);
180 if (scev_analyzable_p (res
, region
))
182 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
184 if (evolution_function_is_invariant_p (scev
, loop
->num
))
185 remove_invariant_phi (region
, psi
);
192 /* All the other cases are considered reductions. */
196 /* Store the GRAPHITE representation of BB. */
199 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
201 struct gimple_bb
*gbb
;
203 gbb
= XNEW (struct gimple_bb
);
206 GBB_DATA_REFS (gbb
) = drs
;
207 GBB_CONDITIONS (gbb
).create (0);
208 GBB_CONDITION_CASES (gbb
).create (0);
214 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
217 struct data_reference
*dr
;
219 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
222 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
224 free (bap
->alias_set
);
233 free_gimple_bb (struct gimple_bb
*gbb
)
235 free_data_refs_aux (GBB_DATA_REFS (gbb
));
236 free_data_refs (GBB_DATA_REFS (gbb
));
238 GBB_CONDITIONS (gbb
).release ();
239 GBB_CONDITION_CASES (gbb
).release ();
240 GBB_BB (gbb
)->aux
= 0;
244 /* Deletes all gimple bbs in SCOP. */
247 remove_gbbs_in_scop (scop_p scop
)
252 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
253 free_gimple_bb (PBB_BLACK_BOX (pbb
));
256 /* Deletes all scops in SCOPS. */
259 free_scops (vec
<scop_p
> scops
)
264 FOR_EACH_VEC_ELT (scops
, i
, scop
)
266 remove_gbbs_in_scop (scop
);
267 free_sese (SCOP_REGION (scop
));
274 /* Same as outermost_loop_in_sese, returns the outermost loop
275 containing BB in REGION, but makes sure that the returned loop
276 belongs to the REGION, and so this returns the first loop in the
277 REGION when the loop containing BB does not belong to REGION. */
280 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
282 loop_p nest
= outermost_loop_in_sese (region
, bb
);
284 if (loop_in_sese_p (nest
, region
))
287 /* When the basic block BB does not belong to a loop in the region,
288 return the first loop in the region. */
291 if (loop_in_sese_p (nest
, region
))
300 /* Generates a polyhedral black box only if the bb contains interesting
304 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
306 vec
<data_reference_p
> drs
;
308 sese region
= SCOP_REGION (scop
);
309 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
310 gimple_stmt_iterator gsi
;
312 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
314 gimple stmt
= gsi_stmt (gsi
);
317 if (is_gimple_debug (stmt
))
320 loop
= loop_containing_stmt (stmt
);
321 if (!loop_in_sese_p (loop
, region
))
324 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
327 return new_gimple_bb (bb
, drs
);
330 /* Returns true if all predecessors of BB, that are not dominated by BB, are
331 marked in MAP. The predecessors dominated by BB are loop latches and will
332 be handled after BB. */
335 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
340 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
341 if (!bitmap_bit_p (map
, e
->src
->index
)
342 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
348 /* Compare the depth of two basic_block's P1 and P2. */
351 compare_bb_depths (const void *p1
, const void *p2
)
353 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
354 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
355 int d1
= loop_depth (bb1
->loop_father
);
356 int d2
= loop_depth (bb2
->loop_father
);
367 /* Sort the basic blocks from DOM such that the first are the ones at
368 a deepest loop level. */
371 graphite_sort_dominated_info (vec
<basic_block
> dom
)
373 dom
.qsort (compare_bb_depths
);
376 /* Recursive helper function for build_scops_bbs. */
379 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
381 sese region
= SCOP_REGION (scop
);
382 vec
<basic_block
> dom
;
385 if (bitmap_bit_p (visited
, bb
->index
)
386 || !bb_in_sese_p (bb
, region
))
389 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
390 SCOP_BBS (scop
).safe_push (pbb
);
391 bitmap_set_bit (visited
, bb
->index
);
393 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
398 graphite_sort_dominated_info (dom
);
400 while (!dom
.is_empty ())
405 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
406 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
408 build_scop_bbs_1 (scop
, visited
, dom_bb
);
409 dom
.unordered_remove (i
);
417 /* Gather the basic blocks belonging to the SCOP. */
420 build_scop_bbs (scop_p scop
)
422 sbitmap visited
= sbitmap_alloc (last_basic_block
);
423 sese region
= SCOP_REGION (scop
);
425 bitmap_clear (visited
);
426 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
427 sbitmap_free (visited
);
430 /* Return an ISL identifier for the polyhedral basic block PBB. */
433 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
436 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
437 return isl_id_alloc (s
->ctx
, name
, pbb
);
440 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
441 We generate SCATTERING_DIMENSIONS scattering dimensions.
443 CLooG 0.15.0 and previous versions require, that all
444 scattering functions of one CloogProgram have the same number of
445 scattering dimensions, therefore we allow to specify it. This
446 should be removed in future versions of CLooG.
448 The scattering polyhedron consists of these dimensions: scattering,
449 loop_iterators, parameters.
453 | scattering_dimensions = 5
454 | used_scattering_dimensions = 3
462 | Scattering polyhedron:
464 | scattering: {s1, s2, s3, s4, s5}
465 | loop_iterators: {i}
466 | parameters: {p1, p2}
468 | s1 s2 s3 s4 s5 i p1 p2 1
469 | 1 0 0 0 0 0 0 0 -4 = 0
470 | 0 1 0 0 0 -1 0 0 0 = 0
471 | 0 0 1 0 0 0 0 0 -5 = 0 */
474 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
475 poly_bb_p pbb
, int scattering_dimensions
)
478 int nb_iterators
= pbb_dim_iter_domain (pbb
);
479 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
483 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
487 dc
= isl_set_get_space (pbb
->domain
);
488 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
489 isl_dim_out
, scattering_dimensions
);
490 pbb
->schedule
= isl_map_universe (dm
);
492 for (i
= 0; i
< scattering_dimensions
; i
++)
494 /* Textual order inside this loop. */
497 isl_constraint
*c
= isl_equality_alloc
498 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
500 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
504 isl_int_neg (val
, val
);
505 c
= isl_constraint_set_constant (c
, val
);
506 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
507 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
510 /* Iterations of this loop. */
511 else /* if ((i % 2) == 1) */
513 int loop
= (i
- 1) / 2;
514 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
521 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
524 /* Build for BB the static schedule.
526 The static schedule is a Dewey numbering of the abstract syntax
527 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
529 The following example informally defines the static schedule:
548 Static schedules for A to F:
561 build_scop_scattering (scop_p scop
)
565 gimple_bb_p previous_gbb
= NULL
;
566 isl_space
*dc
= isl_set_get_space (scop
->context
);
567 isl_aff
*static_sched
;
569 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
570 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
572 /* We have to start schedules at 0 on the first component and
573 because we cannot compare_prefix_loops against a previous loop,
574 prefix will be equal to zero, and that index will be
575 incremented before copying. */
576 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
578 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
580 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
582 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
585 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
591 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
593 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
596 isl_aff_free (static_sched
);
599 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
601 /* Extract an affine expression from the chain of recurrence E. */
604 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
606 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
607 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
608 isl_local_space
*ls
= isl_local_space_from_space (space
);
609 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
610 isl_aff
*loop
= isl_aff_set_coefficient_si
611 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
612 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
614 /* Before multiplying, make sure that the result is affine. */
615 gcc_assert (isl_pw_aff_is_cst (rhs
)
616 || isl_pw_aff_is_cst (l
));
618 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
621 /* Extract an affine expression from the mult_expr E. */
624 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
626 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
627 isl_space_copy (space
));
628 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
630 if (!isl_pw_aff_is_cst (lhs
)
631 && !isl_pw_aff_is_cst (rhs
))
633 isl_pw_aff_free (lhs
);
634 isl_pw_aff_free (rhs
);
638 return isl_pw_aff_mul (lhs
, rhs
);
641 /* Return an ISL identifier from the name of the ssa_name E. */
644 isl_id_for_ssa_name (scop_p s
, tree e
)
646 const char *name
= get_name (e
);
650 id
= isl_id_alloc (s
->ctx
, name
, e
);
654 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
655 id
= isl_id_alloc (s
->ctx
, name1
, e
);
661 /* Return an ISL identifier for the data reference DR. */
664 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
666 /* Data references all get the same isl_id. They need to be comparable
667 and are distinguished through the first dimension, which contains the
669 return isl_id_alloc (s
->ctx
, "", 0);
672 /* Extract an affine expression from the ssa_name E. */
675 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
682 id
= isl_id_for_ssa_name (s
, e
);
683 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
685 dom
= isl_set_universe (isl_space_copy (space
));
686 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
687 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
688 return isl_pw_aff_alloc (dom
, aff
);
691 /* Extract an affine expression from the gmp constant G. */
694 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
696 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
697 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
698 isl_set
*dom
= isl_set_universe (space
);
702 isl_int_set_gmp (v
, g
);
703 aff
= isl_aff_add_constant (aff
, v
);
706 return isl_pw_aff_alloc (dom
, aff
);
709 /* Extract an affine expression from the integer_cst E. */
712 extract_affine_int (tree e
, __isl_take isl_space
*space
)
718 tree_int_to_gmp (e
, g
);
719 res
= extract_affine_gmp (g
, space
);
725 /* Compute pwaff mod 2^width. */
728 wrap (isl_pw_aff
*pwaff
, unsigned width
)
733 isl_int_set_si (mod
, 1);
734 isl_int_mul_2exp (mod
, mod
, width
);
736 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
743 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
744 Otherwise returns -1. */
747 parameter_index_in_region_1 (tree name
, sese region
)
752 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
754 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
761 /* When the parameter NAME is in REGION, returns its index in
762 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
763 and returns the index of NAME. */
766 parameter_index_in_region (tree name
, sese region
)
770 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
772 i
= parameter_index_in_region_1 (name
, region
);
776 gcc_assert (SESE_ADD_PARAMS (region
));
778 i
= SESE_PARAMS (region
).length ();
779 SESE_PARAMS (region
).safe_push (name
);
783 /* Extract an affine expression from the tree E in the scop S. */
786 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
788 isl_pw_aff
*lhs
, *rhs
, *res
;
791 if (e
== chrec_dont_know
) {
792 isl_space_free (space
);
796 switch (TREE_CODE (e
))
798 case POLYNOMIAL_CHREC
:
799 res
= extract_affine_chrec (s
, e
, space
);
803 res
= extract_affine_mul (s
, e
, space
);
807 case POINTER_PLUS_EXPR
:
808 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
809 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
810 res
= isl_pw_aff_add (lhs
, rhs
);
814 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
815 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
816 res
= isl_pw_aff_sub (lhs
, rhs
);
821 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
822 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
823 res
= isl_pw_aff_mul (lhs
, rhs
);
827 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
828 res
= extract_affine_name (s
, e
, space
);
832 res
= extract_affine_int (e
, space
);
833 /* No need to wrap a single integer. */
837 case NON_LVALUE_EXPR
:
838 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
846 type
= TREE_TYPE (e
);
847 if (TYPE_UNSIGNED (type
))
848 res
= wrap (res
, TYPE_PRECISION (type
));
853 /* In the context of sese S, scan the expression E and translate it to
854 a linear expression C. When parsing a symbolic multiplication, K
855 represents the constant multiplier of an expression containing
859 scan_tree_for_params (sese s
, tree e
)
861 if (e
== chrec_dont_know
)
864 switch (TREE_CODE (e
))
866 case POLYNOMIAL_CHREC
:
867 scan_tree_for_params (s
, CHREC_LEFT (e
));
871 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
872 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
874 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
878 case POINTER_PLUS_EXPR
:
880 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
881 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
887 case NON_LVALUE_EXPR
:
888 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
892 parameter_index_in_region (e
, s
);
905 /* Find parameters with respect to REGION in BB. We are looking in memory
906 access functions, conditions and loop bounds. */
909 find_params_in_bb (sese region
, gimple_bb_p gbb
)
915 loop_p loop
= GBB_BB (gbb
)->loop_father
;
917 /* Find parameters in the access functions of data references. */
918 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
919 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
920 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
922 /* Find parameters in conditional statements. */
923 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
925 tree lhs
= scalar_evolution_in_region (region
, loop
,
926 gimple_cond_lhs (stmt
));
927 tree rhs
= scalar_evolution_in_region (region
, loop
,
928 gimple_cond_rhs (stmt
));
930 scan_tree_for_params (region
, lhs
);
931 scan_tree_for_params (region
, rhs
);
935 /* Record the parameters used in the SCOP. A variable is a parameter
936 in a scop if it does not vary during the execution of that scop. */
939 find_scop_parameters (scop_p scop
)
943 sese region
= SCOP_REGION (scop
);
947 /* Find the parameters used in the loop bounds. */
948 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
950 tree nb_iters
= number_of_latch_executions (loop
);
952 if (!chrec_contains_symbols (nb_iters
))
955 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
956 scan_tree_for_params (region
, nb_iters
);
959 /* Find the parameters used in data accesses. */
960 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
961 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
963 nbp
= sese_nb_params (region
);
964 scop_set_nb_params (scop
, nbp
);
965 SESE_ADD_PARAMS (region
) = false;
969 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
971 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
972 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
973 isl_id_for_ssa_name (scop
, e
));
975 scop
->context
= isl_set_universe (space
);
979 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
980 the constraints for the surrounding loops. */
983 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
985 isl_set
*outer
, isl_set
**doms
)
987 tree nb_iters
= number_of_latch_executions (loop
);
988 sese region
= SCOP_REGION (scop
);
990 isl_set
*inner
= isl_set_copy (outer
);
993 int pos
= isl_set_dim (outer
, isl_dim_set
);
1000 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1001 space
= isl_set_get_space (inner
);
1004 c
= isl_inequality_alloc
1005 (isl_local_space_from_space (isl_space_copy (space
)));
1006 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1007 inner
= isl_set_add_constraint (inner
, c
);
1009 /* loop_i <= cst_nb_iters */
1010 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1012 c
= isl_inequality_alloc
1013 (isl_local_space_from_space (isl_space_copy (space
)));
1014 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1015 tree_int_to_gmp (nb_iters
, g
);
1016 isl_int_set_gmp (v
, g
);
1017 c
= isl_constraint_set_constant (c
, v
);
1018 inner
= isl_set_add_constraint (inner
, c
);
1021 /* loop_i <= expr_nb_iters */
1022 else if (!chrec_contains_undetermined (nb_iters
))
1027 isl_local_space
*ls
;
1031 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1033 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1034 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1035 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1036 isl_set_dim (valid
, isl_dim_set
));
1037 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1039 ls
= isl_local_space_from_space (isl_space_copy (space
));
1040 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1041 isl_dim_in
, pos
, 1);
1042 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1043 isl_pw_aff_copy (aff
));
1044 inner
= isl_set_intersect (inner
, le
);
1046 if (max_stmt_executions (loop
, &nit
))
1048 /* Insert in the context the constraints from the
1049 estimation of the number of iterations NIT and the
1050 symbolic number of iterations (involving parameter
1051 names) NB_ITERS. First, build the affine expression
1052 "NIT - NB_ITERS" and then say that it is positive,
1053 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1060 mpz_set_double_int (g
, nit
, false);
1061 mpz_sub_ui (g
, g
, 1);
1062 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1063 x
= isl_pw_aff_ge_set (approx
, aff
);
1064 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1065 isl_set_dim (x
, isl_dim_set
));
1066 scop
->context
= isl_set_intersect (scop
->context
, x
);
1068 c
= isl_inequality_alloc
1069 (isl_local_space_from_space (isl_space_copy (space
)));
1070 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1071 isl_int_set_gmp (v
, g
);
1073 c
= isl_constraint_set_constant (c
, v
);
1074 inner
= isl_set_add_constraint (inner
, c
);
1077 isl_pw_aff_free (aff
);
1082 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1083 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1084 isl_set_copy (inner
), doms
);
1088 && loop_in_sese_p (loop
->next
, region
))
1089 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1090 isl_set_copy (outer
), doms
);
1092 doms
[loop
->num
] = inner
;
1094 isl_set_free (outer
);
1095 isl_space_free (space
);
1100 /* Returns a linear expression for tree T evaluated in PBB. */
1103 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1105 scop_p scop
= PBB_SCOP (pbb
);
1107 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1108 gcc_assert (!automatically_generated_chrec_p (t
));
1110 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1113 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1114 operator. This allows us to invert the condition or to handle
1118 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1120 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1121 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1127 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1131 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1135 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1139 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1143 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1147 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1151 isl_pw_aff_free (lhs
);
1152 isl_pw_aff_free (rhs
);
1156 cond
= isl_set_coalesce (cond
);
1157 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1158 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1161 /* Add conditions to the domain of PBB. */
1164 add_conditions_to_domain (poly_bb_p pbb
)
1168 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1170 if (GBB_CONDITIONS (gbb
).is_empty ())
1173 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1174 switch (gimple_code (stmt
))
1178 enum tree_code code
= gimple_cond_code (stmt
);
1180 /* The conditions for ELSE-branches are inverted. */
1181 if (!GBB_CONDITION_CASES (gbb
)[i
])
1182 code
= invert_tree_comparison (code
, false);
1184 add_condition_to_pbb (pbb
, stmt
, code
);
1189 /* Switch statements are not supported right now - fall through. */
1197 /* Traverses all the GBBs of the SCOP and add their constraints to the
1198 iteration domains. */
1201 add_conditions_to_constraints (scop_p scop
)
1206 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1207 add_conditions_to_domain (pbb
);
1210 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1211 edge between BB and its predecessor is not a loop exit edge, and
1212 the last statement of the single predecessor is a COND_EXPR. */
1215 single_pred_cond_non_loop_exit (basic_block bb
)
1217 if (single_pred_p (bb
))
1219 edge e
= single_pred_edge (bb
);
1220 basic_block pred
= e
->src
;
1223 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1226 stmt
= last_stmt (pred
);
1228 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1235 class sese_dom_walker
: public dom_walker
1238 sese_dom_walker (cdi_direction
, sese
);
1240 virtual void before_dom_children (basic_block
);
1241 virtual void after_dom_children (basic_block
);
1244 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1248 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1249 : dom_walker (direction
), m_region (region
)
1253 /* Call-back for dom_walk executed before visiting the dominated
1257 sese_dom_walker::before_dom_children (basic_block bb
)
1262 if (!bb_in_sese_p (bb
, m_region
))
1265 stmt
= single_pred_cond_non_loop_exit (bb
);
1269 edge e
= single_pred_edge (bb
);
1271 m_conditions
.safe_push (stmt
);
1273 if (e
->flags
& EDGE_TRUE_VALUE
)
1274 m_cases
.safe_push (stmt
);
1276 m_cases
.safe_push (NULL
);
1279 gbb
= gbb_from_bb (bb
);
1283 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1284 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1288 /* Call-back for dom_walk executed after visiting the dominated
1292 sese_dom_walker::after_dom_children (basic_block bb
)
1294 if (!bb_in_sese_p (bb
, m_region
))
1297 if (single_pred_cond_non_loop_exit (bb
))
1299 m_conditions
.pop ();
1304 /* Add constraints on the possible values of parameter P from the type
1308 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1310 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1311 tree type
= TREE_TYPE (parameter
);
1312 tree lb
= NULL_TREE
;
1313 tree ub
= NULL_TREE
;
1315 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1316 lb
= lower_bound_in_type (type
, type
);
1318 lb
= TYPE_MIN_VALUE (type
);
1320 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1321 ub
= upper_bound_in_type (type
, type
);
1323 ub
= TYPE_MAX_VALUE (type
);
1327 isl_space
*space
= isl_set_get_space (scop
->context
);
1332 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1335 tree_int_to_gmp (lb
, g
);
1336 isl_int_set_gmp (v
, g
);
1339 c
= isl_constraint_set_constant (c
, v
);
1341 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1343 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1348 isl_space
*space
= isl_set_get_space (scop
->context
);
1353 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1357 tree_int_to_gmp (ub
, g
);
1358 isl_int_set_gmp (v
, g
);
1360 c
= isl_constraint_set_constant (c
, v
);
1362 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1364 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1368 /* Build the context of the SCOP. The context usually contains extra
1369 constraints that are added to the iteration domains that constrain
1373 build_scop_context (scop_p scop
)
1375 graphite_dim_t p
, n
= scop_nb_params (scop
);
1377 for (p
= 0; p
< n
; p
++)
1378 add_param_constraints (scop
, p
);
1381 /* Build the iteration domains: the loops belonging to the current
1382 SCOP, and that vary for the execution of the current basic block.
1383 Returns false if there is no loop in SCOP. */
1386 build_scop_iteration_domain (scop_p scop
)
1389 sese region
= SCOP_REGION (scop
);
1392 int nb_loops
= number_of_loops (cfun
);
1393 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1395 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1396 if (!loop_in_sese_p (loop_outer (loop
), region
))
1397 build_loop_iteration_domains (scop
, loop
, 0,
1398 isl_set_copy (scop
->context
), doms
);
1400 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1402 loop
= pbb_loop (pbb
);
1404 if (doms
[loop
->num
])
1405 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1407 pbb
->domain
= isl_set_copy (scop
->context
);
1409 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1410 isl_id_for_pbb (scop
, pbb
));
1413 for (i
= 0; i
< nb_loops
; i
++)
1415 isl_set_free (doms
[i
]);
1420 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1421 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1422 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1426 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1429 int alias_set_num
= 0;
1430 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1432 if (bap
&& bap
->alias_set
)
1433 alias_set_num
= *(bap
->alias_set
);
1435 c
= isl_equality_alloc
1436 (isl_local_space_from_space (isl_map_get_space (acc
)));
1437 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1438 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1440 return isl_map_add_constraint (acc
, c
);
1443 /* Assign the affine expression INDEX to the output dimension POS of
1444 MAP and return the result. */
1447 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1450 int len
= isl_map_dim (map
, isl_dim_out
);
1453 index_map
= isl_map_from_pw_aff (index
);
1454 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1455 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1457 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1458 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1459 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1460 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1462 return isl_map_intersect (map
, index_map
);
1465 /* Add to ACCESSES polyhedron equalities defining the access functions
1466 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1467 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1468 PBB is the poly_bb_p that contains the data reference DR. */
1471 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1473 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1474 scop_p scop
= PBB_SCOP (pbb
);
1476 for (i
= 0; i
< nb_subscripts
; i
++)
1479 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1481 aff
= extract_affine (scop
, afn
,
1482 isl_space_domain (isl_map_get_space (acc
)));
1483 acc
= set_index (acc
, i
+ 1, aff
);
1489 /* Add constrains representing the size of the accessed data to the
1490 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1491 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1495 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1497 tree ref
= DR_REF (dr
);
1498 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1500 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1504 if (TREE_CODE (ref
) != ARRAY_REF
)
1507 low
= array_ref_low_bound (ref
);
1508 high
= array_ref_up_bound (ref
);
1510 /* XXX The PPL code dealt separately with
1511 subscript - low >= 0 and high - subscript >= 0 in case one of
1512 the two bounds isn't known. Do the same here? */
1514 if (tree_fits_shwi_p (low
)
1516 && tree_fits_shwi_p (high
)
1517 /* 1-element arrays at end of structures may extend over
1518 their declared size. */
1519 && !(array_at_struct_end_p (ref
)
1520 && operand_equal_p (low
, high
, 0)))
1524 isl_set
*univ
, *lbs
, *ubs
;
1528 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1529 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1532 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1533 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1534 isl_set_dim (valid
, isl_dim_set
));
1535 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1537 space
= isl_set_get_space (extent
);
1538 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1539 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1540 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1541 index
= isl_pw_aff_alloc (univ
, aff
);
1543 id
= isl_set_get_tuple_id (extent
);
1544 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1545 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1547 /* low <= sub_i <= high */
1548 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1549 ubs
= isl_pw_aff_le_set (index
, ub
);
1550 extent
= isl_set_intersect (extent
, lbs
);
1551 extent
= isl_set_intersect (extent
, ubs
);
1558 /* Build data accesses for DR in PBB. */
1561 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1563 int dr_base_object_set
;
1566 scop_p scop
= PBB_SCOP (pbb
);
1569 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1570 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1571 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1572 isl_dim_out
, nb_out
);
1574 acc
= isl_map_universe (space
);
1575 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1578 acc
= pdr_add_alias_set (acc
, dr
);
1579 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1582 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1583 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1584 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1585 int alias_set_num
= 0;
1586 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1588 if (bap
&& bap
->alias_set
)
1589 alias_set_num
= *(bap
->alias_set
);
1591 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1592 extent
= isl_set_nat_universe (space
);
1593 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1594 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1597 gcc_assert (dr
->aux
);
1598 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1600 new_poly_dr (pbb
, dr_base_object_set
,
1601 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1602 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1605 /* Write to FILE the alias graph of data references in DIMACS format. */
1608 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1609 vec
<data_reference_p
> drs
)
1611 int num_vertex
= drs
.length ();
1613 data_reference_p dr1
, dr2
;
1616 if (num_vertex
== 0)
1619 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1620 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1621 if (dr_may_alias_p (dr1
, dr2
, true))
1624 fprintf (file
, "$\n");
1627 fprintf (file
, "c %s\n", comment
);
1629 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1631 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1632 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1633 if (dr_may_alias_p (dr1
, dr2
, true))
1634 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1639 /* Write to FILE the alias graph of data references in DOT format. */
1642 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1643 vec
<data_reference_p
> drs
)
1645 int num_vertex
= drs
.length ();
1646 data_reference_p dr1
, dr2
;
1649 if (num_vertex
== 0)
1652 fprintf (file
, "$\n");
1655 fprintf (file
, "c %s\n", comment
);
1657 /* First print all the vertices. */
1658 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1659 fprintf (file
, "n%d;\n", i
);
1661 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1662 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1663 if (dr_may_alias_p (dr1
, dr2
, true))
1664 fprintf (file
, "n%d n%d\n", i
, j
);
1669 /* Write to FILE the alias graph of data references in ECC format. */
1672 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1673 vec
<data_reference_p
> drs
)
1675 int num_vertex
= drs
.length ();
1676 data_reference_p dr1
, dr2
;
1679 if (num_vertex
== 0)
1682 fprintf (file
, "$\n");
1685 fprintf (file
, "c %s\n", comment
);
1687 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1688 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1689 if (dr_may_alias_p (dr1
, dr2
, true))
1690 fprintf (file
, "%d %d\n", i
, j
);
1695 /* Check if DR1 and DR2 are in the same object set. */
1698 dr_same_base_object_p (const struct data_reference
*dr1
,
1699 const struct data_reference
*dr2
)
1701 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1704 /* Uses DFS component number as representative of alias-sets. Also tests for
1705 optimality by verifying if every connected component is a clique. Returns
1706 true (1) if the above test is true, and false (0) otherwise. */
1709 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1711 int num_vertices
= drs
.length ();
1712 struct graph
*g
= new_graph (num_vertices
);
1713 data_reference_p dr1
, dr2
;
1715 int num_connected_components
;
1716 int v_indx1
, v_indx2
, num_vertices_in_component
;
1719 struct graph_edge
*e
;
1720 int this_component_is_clique
;
1721 int all_components_are_cliques
= 1;
1723 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1724 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1725 if (dr_may_alias_p (dr1
, dr2
, true))
1731 all_vertices
= XNEWVEC (int, num_vertices
);
1732 vertices
= XNEWVEC (int, num_vertices
);
1733 for (i
= 0; i
< num_vertices
; i
++)
1734 all_vertices
[i
] = i
;
1736 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1738 for (i
= 0; i
< g
->n_vertices
; i
++)
1740 data_reference_p dr
= drs
[i
];
1741 base_alias_pair
*bap
;
1743 gcc_assert (dr
->aux
);
1744 bap
= (base_alias_pair
*)(dr
->aux
);
1746 bap
->alias_set
= XNEW (int);
1747 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1750 /* Verify if the DFS numbering results in optimal solution. */
1751 for (i
= 0; i
< num_connected_components
; i
++)
1753 num_vertices_in_component
= 0;
1754 /* Get all vertices whose DFS component number is the same as i. */
1755 for (j
= 0; j
< num_vertices
; j
++)
1756 if (g
->vertices
[j
].component
== i
)
1757 vertices
[num_vertices_in_component
++] = j
;
1759 /* Now test if the vertices in 'vertices' form a clique, by testing
1760 for edges among each pair. */
1761 this_component_is_clique
= 1;
1762 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1764 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1766 /* Check if the two vertices are connected by iterating
1767 through all the edges which have one of these are source. */
1768 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1771 if (e
->src
== vertices
[v_indx1
])
1777 this_component_is_clique
= 0;
1781 if (!this_component_is_clique
)
1782 all_components_are_cliques
= 0;
1786 free (all_vertices
);
1789 return all_components_are_cliques
;
1792 /* Group each data reference in DRS with its base object set num. */
1795 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1797 int num_vertex
= drs
.length ();
1798 struct graph
*g
= new_graph (num_vertex
);
1799 data_reference_p dr1
, dr2
;
1803 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1804 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1805 if (dr_same_base_object_p (dr1
, dr2
))
1811 queue
= XNEWVEC (int, num_vertex
);
1812 for (i
= 0; i
< num_vertex
; i
++)
1815 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1817 for (i
= 0; i
< g
->n_vertices
; i
++)
1819 data_reference_p dr
= drs
[i
];
1820 base_alias_pair
*bap
;
1822 gcc_assert (dr
->aux
);
1823 bap
= (base_alias_pair
*)(dr
->aux
);
1825 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1832 /* Build the data references for PBB. */
1835 build_pbb_drs (poly_bb_p pbb
)
1838 data_reference_p dr
;
1839 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1841 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1842 build_poly_dr (dr
, pbb
);
1845 /* Dump to file the alias graphs for the data references in DRS. */
1848 dump_alias_graphs (vec
<data_reference_p
> drs
)
1851 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1853 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1856 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1857 current_function_name ());
1858 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1859 fclose (file_dimacs
);
1862 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1865 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1866 current_function_name ());
1867 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1871 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1874 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1875 current_function_name ());
1876 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1881 /* Build data references in SCOP. */
1884 build_scop_drs (scop_p scop
)
1888 data_reference_p dr
;
1889 stack_vec
<data_reference_p
, 3> drs
;
1891 /* Remove all the PBBs that do not have data references: these basic
1892 blocks are not handled in the polyhedral representation. */
1893 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1894 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1896 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1898 SCOP_BBS (scop
).ordered_remove (i
);
1902 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1903 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1906 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1907 dr
->aux
= XNEW (base_alias_pair
);
1909 if (!build_alias_set_optimal_p (drs
))
1911 /* TODO: Add support when building alias set is not optimal. */
1915 build_base_obj_set_for_drs (drs
);
1917 /* When debugging, enable the following code. This cannot be used
1918 in production compilers. */
1920 dump_alias_graphs (drs
);
1924 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1925 build_pbb_drs (pbb
);
1928 /* Return a gsi at the position of the phi node STMT. */
1930 static gimple_stmt_iterator
1931 gsi_for_phi_node (gimple stmt
)
1933 gimple_stmt_iterator psi
;
1934 basic_block bb
= gimple_bb (stmt
);
1936 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1937 if (stmt
== gsi_stmt (psi
))
1944 /* Analyze all the data references of STMTS and add them to the
1945 GBB_DATA_REFS vector of BB. */
1948 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1954 sese region
= SCOP_REGION (scop
);
1956 if (!bb_in_sese_p (bb
, region
))
1959 nest
= outermost_loop_in_sese_1 (region
, bb
);
1960 gbb
= gbb_from_bb (bb
);
1962 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1966 if (is_gimple_debug (stmt
))
1969 loop
= loop_containing_stmt (stmt
);
1970 if (!loop_in_sese_p (loop
, region
))
1973 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1974 &GBB_DATA_REFS (gbb
));
1978 /* Insert STMT at the end of the STMTS sequence and then insert the
1979 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1983 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1984 gimple_stmt_iterator insert_gsi
)
1986 gimple_stmt_iterator gsi
;
1987 stack_vec
<gimple
, 3> x
;
1989 gimple_seq_add_stmt (&stmts
, stmt
);
1990 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1991 x
.safe_push (gsi_stmt (gsi
));
1993 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1994 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1997 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2000 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2003 gimple_stmt_iterator gsi
;
2004 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2005 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2006 stack_vec
<gimple
, 3> x
;
2008 gimple_seq_add_stmt (&stmts
, stmt
);
2009 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2010 x
.safe_push (gsi_stmt (gsi
));
2012 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2014 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2015 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2019 gsi
= gsi_for_stmt (after_stmt
);
2020 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2023 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2026 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2029 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2031 vec
<data_reference_p
> drs
;
2033 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2034 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2035 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2036 int index
, n
= SCOP_BBS (scop
).length ();
2038 /* The INDEX of PBB in SCOP_BBS. */
2039 for (index
= 0; index
< n
; index
++)
2040 if (SCOP_BBS (scop
)[index
] == pbb
)
2043 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2045 GBB_PBB (gbb1
) = pbb1
;
2046 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2047 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2048 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2051 /* Insert on edge E the assignment "RES := EXPR". */
2054 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2056 gimple_stmt_iterator gsi
;
2057 gimple_seq stmts
= NULL
;
2058 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2059 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2061 stack_vec
<gimple
, 3> x
;
2063 gimple_seq_add_stmt (&stmts
, stmt
);
2064 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2065 x
.safe_push (gsi_stmt (gsi
));
2067 gsi_insert_seq_on_edge (e
, stmts
);
2068 gsi_commit_edge_inserts ();
2069 bb
= gimple_bb (stmt
);
2071 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2074 if (!gbb_from_bb (bb
))
2075 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2077 analyze_drs_in_stmts (scop
, bb
, x
);
2080 /* Creates a zero dimension array of the same type as VAR. */
2083 create_zero_dim_array (tree var
, const char *base_name
)
2085 tree index_type
= build_index_type (integer_zero_node
);
2086 tree elt_type
= TREE_TYPE (var
);
2087 tree array_type
= build_array_type (elt_type
, index_type
);
2088 tree base
= create_tmp_var (array_type
, base_name
);
2090 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2094 /* Returns true when PHI is a loop close phi node. */
2097 scalar_close_phi_node_p (gimple phi
)
2099 if (gimple_code (phi
) != GIMPLE_PHI
2100 || virtual_operand_p (gimple_phi_result (phi
)))
2103 /* Note that loop close phi nodes should have a single argument
2104 because we translated the representation into a canonical form
2105 before Graphite: see canonicalize_loop_closed_ssa_form. */
2106 return (gimple_phi_num_args (phi
) == 1);
2109 /* For a definition DEF in REGION, propagates the expression EXPR in
2110 all the uses of DEF outside REGION. */
2113 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2115 imm_use_iterator imm_iter
;
2118 bool replaced_once
= false;
2120 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2122 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2125 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2126 if (!is_gimple_debug (use_stmt
)
2127 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2130 use_operand_p use_p
;
2132 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2133 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2134 && (replaced_once
= true))
2135 replace_exp (use_p
, expr
);
2137 update_stmt (use_stmt
);
2142 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2143 gsi_commit_edge_inserts ();
2147 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2148 dimension array for it. */
2151 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2153 sese region
= SCOP_REGION (scop
);
2154 gimple phi
= gsi_stmt (*psi
);
2155 tree res
= gimple_phi_result (phi
);
2156 basic_block bb
= gimple_bb (phi
);
2157 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2158 tree arg
= gimple_phi_arg_def (phi
, 0);
2161 /* Note that loop close phi nodes should have a single argument
2162 because we translated the representation into a canonical form
2163 before Graphite: see canonicalize_loop_closed_ssa_form. */
2164 gcc_assert (gimple_phi_num_args (phi
) == 1);
2166 /* The phi node can be a non close phi node, when its argument is
2167 invariant, or a default definition. */
2168 if (is_gimple_min_invariant (arg
)
2169 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2171 propagate_expr_outside_region (res
, arg
, region
);
2176 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2178 propagate_expr_outside_region (res
, arg
, region
);
2179 stmt
= gimple_build_assign (res
, arg
);
2180 remove_phi_node (psi
, false);
2181 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2185 /* If res is scev analyzable and is not a scalar value, it is safe
2186 to ignore the close phi node: it will be code generated in the
2187 out of Graphite pass. */
2188 else if (scev_analyzable_p (res
, region
))
2190 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2193 if (!loop_in_sese_p (loop
, region
))
2195 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2196 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2197 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2200 scev
= scalar_evolution_in_region (region
, loop
, res
);
2202 if (tree_does_not_contain_chrecs (scev
))
2203 propagate_expr_outside_region (res
, scev
, region
);
2210 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2212 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2214 if (TREE_CODE (arg
) == SSA_NAME
)
2215 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2216 SSA_NAME_DEF_STMT (arg
));
2218 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2219 zero_dim_array
, arg
);
2222 remove_phi_node (psi
, false);
2223 SSA_NAME_DEF_STMT (res
) = stmt
;
2225 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2228 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2229 dimension array for it. */
2232 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2235 gimple phi
= gsi_stmt (*psi
);
2236 basic_block bb
= gimple_bb (phi
);
2237 tree res
= gimple_phi_result (phi
);
2238 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2241 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2243 tree arg
= gimple_phi_arg_def (phi
, i
);
2244 edge e
= gimple_phi_arg_edge (phi
, i
);
2246 /* Avoid the insertion of code in the loop latch to please the
2247 pattern matching of the vectorizer. */
2248 if (TREE_CODE (arg
) == SSA_NAME
2249 && e
->src
== bb
->loop_father
->latch
)
2250 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2251 SSA_NAME_DEF_STMT (arg
));
2253 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2256 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2257 remove_phi_node (psi
, false);
2258 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2261 /* Rewrite the degenerate phi node at position PSI from the degenerate
2262 form "x = phi (y, y, ..., y)" to "x = y". */
2265 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2269 gimple_stmt_iterator gsi
;
2270 gimple phi
= gsi_stmt (*psi
);
2271 tree res
= gimple_phi_result (phi
);
2274 bb
= gimple_bb (phi
);
2275 rhs
= degenerate_phi_result (phi
);
2278 stmt
= gimple_build_assign (res
, rhs
);
2279 remove_phi_node (psi
, false);
2281 gsi
= gsi_after_labels (bb
);
2282 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2285 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2288 rewrite_reductions_out_of_ssa (scop_p scop
)
2291 gimple_stmt_iterator psi
;
2292 sese region
= SCOP_REGION (scop
);
2295 if (bb_in_sese_p (bb
, region
))
2296 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2298 gimple phi
= gsi_stmt (psi
);
2300 if (virtual_operand_p (gimple_phi_result (phi
)))
2306 if (gimple_phi_num_args (phi
) > 1
2307 && degenerate_phi_result (phi
))
2308 rewrite_degenerate_phi (&psi
);
2310 else if (scalar_close_phi_node_p (phi
))
2311 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2313 else if (reduction_phi_p (region
, &psi
))
2314 rewrite_phi_out_of_ssa (scop
, &psi
);
2317 update_ssa (TODO_update_ssa
);
2318 #ifdef ENABLE_CHECKING
2319 verify_loop_closed_ssa (true);
2323 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2324 read from ZERO_DIM_ARRAY. */
2327 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2328 tree def
, gimple use_stmt
)
2333 use_operand_p use_p
;
2335 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2337 name
= copy_ssa_name (def
, NULL
);
2338 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2340 gimple_assign_set_lhs (name_stmt
, name
);
2341 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2343 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2344 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2345 replace_exp (use_p
, name
);
2347 update_stmt (use_stmt
);
2350 /* For every definition DEF in the SCOP that is used outside the scop,
2351 insert a closing-scop definition in the basic block just after this
2355 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2357 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2358 tree new_name
= make_ssa_name (var
, stmt
);
2359 bool needs_copy
= false;
2360 use_operand_p use_p
;
2361 imm_use_iterator imm_iter
;
2363 sese region
= SCOP_REGION (scop
);
2365 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2367 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2369 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2371 SET_USE (use_p
, new_name
);
2373 update_stmt (use_stmt
);
2378 /* Insert in the empty BB just after the scop a use of DEF such
2379 that the rewrite of cross_bb_scalar_dependences won't insert
2380 arrays everywhere else. */
2383 gimple assign
= gimple_build_assign (new_name
, def
);
2384 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2386 update_stmt (assign
);
2387 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2391 /* Rewrite the scalar dependences crossing the boundary of the BB
2392 containing STMT with an array. Return true when something has been
2396 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2398 sese region
= SCOP_REGION (scop
);
2399 gimple stmt
= gsi_stmt (*gsi
);
2400 imm_use_iterator imm_iter
;
2403 tree zero_dim_array
= NULL_TREE
;
2407 switch (gimple_code (stmt
))
2410 def
= gimple_assign_lhs (stmt
);
2414 def
= gimple_call_lhs (stmt
);
2422 || !is_gimple_reg (def
))
2425 if (scev_analyzable_p (def
, region
))
2427 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2428 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2430 if (tree_contains_chrecs (scev
, NULL
))
2433 propagate_expr_outside_region (def
, scev
, region
);
2437 def_bb
= gimple_bb (stmt
);
2439 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2441 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2442 if (gimple_code (use_stmt
) == GIMPLE_PHI
2445 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2447 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2448 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2450 rewrite_phi_out_of_ssa (scop
, &psi
);
2453 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2454 if (gimple_code (use_stmt
) != GIMPLE_PHI
2455 && def_bb
!= gimple_bb (use_stmt
)
2456 && !is_gimple_debug (use_stmt
)
2459 if (!zero_dim_array
)
2461 zero_dim_array
= create_zero_dim_array
2462 (def
, "Cross_BB_scalar_dependence");
2463 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2464 SSA_NAME_DEF_STMT (def
));
2468 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2475 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2478 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2481 gimple_stmt_iterator psi
;
2482 sese region
= SCOP_REGION (scop
);
2483 bool changed
= false;
2485 /* Create an extra empty BB after the scop. */
2486 split_edge (SESE_EXIT (region
));
2489 if (bb_in_sese_p (bb
, region
))
2490 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2491 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2496 update_ssa (TODO_update_ssa
);
2497 #ifdef ENABLE_CHECKING
2498 verify_loop_closed_ssa (true);
2503 /* Returns the number of pbbs that are in loops contained in SCOP. */
2506 nb_pbbs_in_loops (scop_p scop
)
2512 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2513 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2519 /* Return the number of data references in BB that write in
2523 nb_data_writes_in_bb (basic_block bb
)
2526 gimple_stmt_iterator gsi
;
2528 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2529 if (gimple_vdef (gsi_stmt (gsi
)))
2535 /* Splits at STMT the basic block BB represented as PBB in the
2539 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2541 edge e1
= split_block (bb
, stmt
);
2542 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2546 /* Splits STMT out of its current BB. This is done for reduction
2547 statements for which we want to ignore data dependences. */
2550 split_reduction_stmt (scop_p scop
, gimple stmt
)
2552 basic_block bb
= gimple_bb (stmt
);
2553 poly_bb_p pbb
= pbb_from_bb (bb
);
2554 gimple_bb_p gbb
= gbb_from_bb (bb
);
2557 data_reference_p dr
;
2559 /* Do not split basic blocks with no writes to memory: the reduction
2560 will be the only write to memory. */
2561 if (nb_data_writes_in_bb (bb
) == 0
2562 /* Or if we have already marked BB as a reduction. */
2563 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2566 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2568 /* Split once more only when the reduction stmt is not the only one
2569 left in the original BB. */
2570 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2572 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2574 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2577 /* A part of the data references will end in a different basic block
2578 after the split: move the DRs from the original GBB to the newly
2580 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2582 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2586 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2587 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2588 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2596 /* Return true when stmt is a reduction operation. */
2599 is_reduction_operation_p (gimple stmt
)
2601 enum tree_code code
;
2603 gcc_assert (is_gimple_assign (stmt
));
2604 code
= gimple_assign_rhs_code (stmt
);
2606 return flag_associative_math
2607 && commutative_tree_code (code
)
2608 && associative_tree_code (code
);
2611 /* Returns true when PHI contains an argument ARG. */
2614 phi_contains_arg (gimple phi
, tree arg
)
2618 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2619 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2625 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2628 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2632 if (TREE_CODE (arg
) != SSA_NAME
)
2635 stmt
= SSA_NAME_DEF_STMT (arg
);
2637 if (gimple_code (stmt
) == GIMPLE_NOP
2638 || gimple_code (stmt
) == GIMPLE_CALL
)
2641 if (gimple_code (stmt
) == GIMPLE_PHI
)
2643 if (phi_contains_arg (stmt
, lhs
))
2648 if (!is_gimple_assign (stmt
))
2651 if (gimple_num_ops (stmt
) == 2)
2652 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2654 if (is_reduction_operation_p (stmt
))
2656 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2659 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2665 /* Detect commutative and associative scalar reductions starting at
2666 the STMT. Return the phi node of the reduction cycle, or NULL. */
2669 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2673 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2678 in
->safe_push (stmt
);
2679 out
->safe_push (stmt
);
2683 /* Detect commutative and associative scalar reductions starting at
2684 STMT. Return the phi node of the reduction cycle, or NULL. */
2687 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2690 tree lhs
= gimple_assign_lhs (stmt
);
2692 if (gimple_num_ops (stmt
) == 2)
2693 return detect_commutative_reduction_arg (lhs
, stmt
,
2694 gimple_assign_rhs1 (stmt
),
2697 if (is_reduction_operation_p (stmt
))
2699 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2700 gimple_assign_rhs1 (stmt
),
2703 : detect_commutative_reduction_arg (lhs
, stmt
,
2704 gimple_assign_rhs2 (stmt
),
2711 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2714 follow_inital_value_to_phi (tree arg
, tree lhs
)
2718 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2721 stmt
= SSA_NAME_DEF_STMT (arg
);
2723 if (gimple_code (stmt
) == GIMPLE_PHI
2724 && phi_contains_arg (stmt
, lhs
))
2731 /* Return the argument of the loop PHI that is the initial value coming
2732 from outside the loop. */
2735 edge_initial_value_for_loop_phi (gimple phi
)
2739 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2741 edge e
= gimple_phi_arg_edge (phi
, i
);
2743 if (loop_depth (e
->src
->loop_father
)
2744 < loop_depth (e
->dest
->loop_father
))
2751 /* Return the argument of the loop PHI that is the initial value coming
2752 from outside the loop. */
2755 initial_value_for_loop_phi (gimple phi
)
2759 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2761 edge e
= gimple_phi_arg_edge (phi
, i
);
2763 if (loop_depth (e
->src
->loop_father
)
2764 < loop_depth (e
->dest
->loop_father
))
2765 return gimple_phi_arg_def (phi
, i
);
2771 /* Returns true when DEF is used outside the reduction cycle of
2775 used_outside_reduction (tree def
, gimple loop_phi
)
2777 use_operand_p use_p
;
2778 imm_use_iterator imm_iter
;
2779 loop_p loop
= loop_containing_stmt (loop_phi
);
2781 /* In LOOP, DEF should be used only in LOOP_PHI. */
2782 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2784 gimple stmt
= USE_STMT (use_p
);
2786 if (stmt
!= loop_phi
2787 && !is_gimple_debug (stmt
)
2788 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2795 /* Detect commutative and associative scalar reductions belonging to
2796 the SCOP starting at the loop closed phi node STMT. Return the phi
2797 node of the reduction cycle, or NULL. */
2800 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2803 if (scalar_close_phi_node_p (stmt
))
2805 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2806 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2808 if (TREE_CODE (arg
) != SSA_NAME
)
2811 /* Note that loop close phi nodes should have a single argument
2812 because we translated the representation into a canonical form
2813 before Graphite: see canonicalize_loop_closed_ssa_form. */
2814 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2816 def
= SSA_NAME_DEF_STMT (arg
);
2817 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2818 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2821 lhs
= gimple_phi_result (close_phi
);
2822 init
= initial_value_for_loop_phi (loop_phi
);
2823 phi
= follow_inital_value_to_phi (init
, lhs
);
2825 if (phi
&& (used_outside_reduction (lhs
, phi
)
2826 || !has_single_use (gimple_phi_result (phi
))))
2829 in
->safe_push (loop_phi
);
2830 out
->safe_push (close_phi
);
2834 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2835 return detect_commutative_reduction_assign (stmt
, in
, out
);
2840 /* Translate the scalar reduction statement STMT to an array RED
2841 knowing that its recursive phi node is LOOP_PHI. */
2844 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2845 gimple stmt
, gimple loop_phi
)
2847 tree res
= gimple_phi_result (loop_phi
);
2848 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2849 gimple_stmt_iterator gsi
;
2851 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2853 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2854 gsi
= gsi_for_stmt (stmt
);
2856 insert_stmts (scop
, assign
, NULL
, gsi
);
2859 /* Removes the PHI node and resets all the debug stmts that are using
2863 remove_phi (gimple phi
)
2865 imm_use_iterator imm_iter
;
2867 use_operand_p use_p
;
2868 gimple_stmt_iterator gsi
;
2869 stack_vec
<gimple
, 3> update
;
2873 def
= PHI_RESULT (phi
);
2874 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2876 stmt
= USE_STMT (use_p
);
2878 if (is_gimple_debug (stmt
))
2880 gimple_debug_bind_reset_value (stmt
);
2881 update
.safe_push (stmt
);
2885 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2888 gsi
= gsi_for_phi_node (phi
);
2889 remove_phi_node (&gsi
, false);
2892 /* Helper function for for_each_index. For each INDEX of the data
2893 reference REF, returns true when its indices are valid in the loop
2894 nest LOOP passed in as DATA. */
2897 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2900 basic_block header
, def_bb
;
2903 if (TREE_CODE (*index
) != SSA_NAME
)
2906 loop
= *((loop_p
*) data
);
2907 header
= loop
->header
;
2908 stmt
= SSA_NAME_DEF_STMT (*index
);
2913 def_bb
= gimple_bb (stmt
);
2918 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2921 /* When the result of a CLOSE_PHI is written to a memory location,
2922 return a pointer to that memory reference, otherwise return
2926 close_phi_written_to_memory (gimple close_phi
)
2928 imm_use_iterator imm_iter
;
2929 use_operand_p use_p
;
2931 tree res
, def
= gimple_phi_result (close_phi
);
2933 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2934 if ((stmt
= USE_STMT (use_p
))
2935 && gimple_code (stmt
) == GIMPLE_ASSIGN
2936 && (res
= gimple_assign_lhs (stmt
)))
2938 switch (TREE_CODE (res
))
2948 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2949 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2951 /* FIXME: this restriction is for id-{24,25}.f and
2952 could be handled by duplicating the computation of
2953 array indices before the loop of the close_phi. */
2954 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2966 /* Rewrite out of SSA the reduction described by the loop phi nodes
2967 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2970 IN: stmt, loop_n, ..., loop_0
2971 OUT: stmt, close_n, ..., close_0
2973 the first element is the reduction statement, and the next elements
2974 are the loop and close phi nodes of each of the outer loops. */
2977 translate_scalar_reduction_to_array (scop_p scop
,
2982 unsigned int i
= out
.length () - 1;
2983 tree red
= close_phi_written_to_memory (out
[i
]);
2985 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2987 gimple close_phi
= out
[i
];
2991 gimple stmt
= loop_phi
;
2992 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2993 poly_bb_p pbb
= pbb_from_bb (bb
);
2994 PBB_IS_REDUCTION (pbb
) = true;
2995 gcc_assert (close_phi
== loop_phi
);
2998 red
= create_zero_dim_array
2999 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3001 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3005 if (i
== in
.length () - 1)
3007 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3008 unshare_expr (red
), close_phi
);
3009 insert_out_of_ssa_copy_on_edge
3010 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3011 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3014 remove_phi (loop_phi
);
3015 remove_phi (close_phi
);
3019 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3020 true when something has been changed. */
3023 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3027 stack_vec
<gimple
, 10> in
;
3028 stack_vec
<gimple
, 10> out
;
3030 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3031 res
= in
.length () > 1;
3033 translate_scalar_reduction_to_array (scop
, in
, out
);
3038 /* Rewrites all the commutative reductions from LOOP out of SSA.
3039 Returns true when something has been changed. */
3042 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3045 gimple_stmt_iterator gsi
;
3046 edge exit
= single_exit (loop
);
3048 bool changed
= false;
3053 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3054 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3055 && !virtual_operand_p (res
)
3056 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3057 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3058 (scop
, gsi_stmt (gsi
));
3063 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3066 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3069 bool changed
= false;
3070 sese region
= SCOP_REGION (scop
);
3072 FOR_EACH_LOOP (loop
, 0)
3073 if (loop_in_sese_p (loop
, region
))
3074 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3079 gsi_commit_edge_inserts ();
3080 update_ssa (TODO_update_ssa
);
3081 #ifdef ENABLE_CHECKING
3082 verify_loop_closed_ssa (true);
3087 /* Can all ivs be represented by a signed integer?
3088 As CLooG might generate negative values in its expressions, signed loop ivs
3089 are required in the backend. */
3092 scop_ivs_can_be_represented (scop_p scop
)
3095 gimple_stmt_iterator psi
;
3098 FOR_EACH_LOOP (loop
, 0)
3100 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3103 for (psi
= gsi_start_phis (loop
->header
);
3104 !gsi_end_p (psi
); gsi_next (&psi
))
3106 gimple phi
= gsi_stmt (psi
);
3107 tree res
= PHI_RESULT (phi
);
3108 tree type
= TREE_TYPE (res
);
3110 if (TYPE_UNSIGNED (type
)
3111 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3124 /* Builds the polyhedral representation for a SESE region. */
3127 build_poly_scop (scop_p scop
)
3129 sese region
= SCOP_REGION (scop
);
3130 graphite_dim_t max_dim
;
3132 build_scop_bbs (scop
);
3134 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3135 Once CLooG is fixed, remove this guard. Anyways, it makes no
3136 sense to optimize a scop containing only PBBs that do not belong
3138 if (nb_pbbs_in_loops (scop
) == 0)
3141 if (!scop_ivs_can_be_represented (scop
))
3144 if (flag_associative_math
)
3145 rewrite_commutative_reductions_out_of_ssa (scop
);
3147 build_sese_loop_nests (region
);
3148 /* Record all conditions in REGION. */
3149 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3150 find_scop_parameters (scop
);
3152 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3153 if (scop_nb_params (scop
) > max_dim
)
3156 build_scop_iteration_domain (scop
);
3157 build_scop_context (scop
);
3158 add_conditions_to_constraints (scop
);
3160 /* Rewrite out of SSA only after having translated the
3161 representation to the polyhedral representation to avoid scev
3162 analysis failures. That means that these functions will insert
3163 new data references that they create in the right place. */
3164 rewrite_reductions_out_of_ssa (scop
);
3165 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3167 build_scop_drs (scop
);
3169 build_scop_scattering (scop
);
3171 /* This SCoP has been translated to the polyhedral
3173 POLY_SCOP_P (scop
) = true;