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 "tree-ssanames.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-ssa-loop-niter.h"
48 #include "tree-ssa-loop.h"
49 #include "tree-into-ssa.h"
50 #include "tree-pass.h"
52 #include "tree-chrec.h"
53 #include "tree-data-ref.h"
54 #include "tree-scalar-evolution.h"
57 #include "tree-ssa-propagate.h"
60 #include "graphite-poly.h"
61 #include "graphite-sese-to-poly.h"
64 /* Assigns to RES the value of the INTEGER_CST T. */
67 tree_int_to_gmp (tree t
, mpz_t res
)
69 double_int di
= tree_to_double_int (t
);
70 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
73 /* Returns the index of the PHI argument defined in the outermost
77 phi_arg_in_outermost_loop (gimple phi
)
79 loop_p loop
= gimple_bb (phi
)->loop_father
;
82 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
83 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
85 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
92 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
93 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
96 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
98 gimple phi
= gsi_stmt (*psi
);
99 tree res
= gimple_phi_result (phi
);
100 size_t entry
= phi_arg_in_outermost_loop (phi
);
101 tree init
= gimple_phi_arg_def (phi
, entry
);
102 gimple stmt
= gimple_build_assign (res
, init
);
103 edge e
= gimple_phi_arg_edge (phi
, entry
);
105 remove_phi_node (psi
, false);
106 gsi_insert_on_edge_immediate (e
, stmt
);
109 /* Removes an invariant phi node at position PSI by inserting on the
110 loop ENTRY edge the assignment RES = INIT. */
113 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
115 gimple phi
= gsi_stmt (*psi
);
116 loop_p loop
= loop_containing_stmt (phi
);
117 tree res
= gimple_phi_result (phi
);
118 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
119 size_t entry
= phi_arg_in_outermost_loop (phi
);
120 edge e
= gimple_phi_arg_edge (phi
, entry
);
123 gimple_seq stmts
= NULL
;
125 if (tree_contains_chrecs (scev
, NULL
))
126 scev
= gimple_phi_arg_def (phi
, entry
);
128 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
129 stmt
= gimple_build_assign (res
, var
);
130 remove_phi_node (psi
, false);
132 gimple_seq_add_stmt (&stmts
, stmt
);
133 gsi_insert_seq_on_edge (e
, stmts
);
134 gsi_commit_edge_inserts ();
135 SSA_NAME_DEF_STMT (res
) = stmt
;
138 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
141 simple_copy_phi_p (gimple phi
)
145 if (gimple_phi_num_args (phi
) != 2)
148 res
= gimple_phi_result (phi
);
149 return (res
== gimple_phi_arg_def (phi
, 0)
150 || res
== gimple_phi_arg_def (phi
, 1));
153 /* Returns true when the phi node at position PSI is a reduction phi
154 node in REGION. Otherwise moves the pointer PSI to the next phi to
158 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
161 gimple phi
= gsi_stmt (*psi
);
162 tree res
= gimple_phi_result (phi
);
164 loop
= loop_containing_stmt (phi
);
166 if (simple_copy_phi_p (phi
))
168 /* PRE introduces phi nodes like these, for an example,
169 see id-5.f in the fortran graphite testsuite:
171 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
173 remove_simple_copy_phi (psi
);
177 if (scev_analyzable_p (res
, region
))
179 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
181 if (evolution_function_is_invariant_p (scev
, loop
->num
))
182 remove_invariant_phi (region
, psi
);
189 /* All the other cases are considered reductions. */
193 /* Store the GRAPHITE representation of BB. */
196 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
198 struct gimple_bb
*gbb
;
200 gbb
= XNEW (struct gimple_bb
);
203 GBB_DATA_REFS (gbb
) = drs
;
204 GBB_CONDITIONS (gbb
).create (0);
205 GBB_CONDITION_CASES (gbb
).create (0);
211 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
214 struct data_reference
*dr
;
216 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
219 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
221 free (bap
->alias_set
);
230 free_gimple_bb (struct gimple_bb
*gbb
)
232 free_data_refs_aux (GBB_DATA_REFS (gbb
));
233 free_data_refs (GBB_DATA_REFS (gbb
));
235 GBB_CONDITIONS (gbb
).release ();
236 GBB_CONDITION_CASES (gbb
).release ();
237 GBB_BB (gbb
)->aux
= 0;
241 /* Deletes all gimple bbs in SCOP. */
244 remove_gbbs_in_scop (scop_p scop
)
249 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
250 free_gimple_bb (PBB_BLACK_BOX (pbb
));
253 /* Deletes all scops in SCOPS. */
256 free_scops (vec
<scop_p
> scops
)
261 FOR_EACH_VEC_ELT (scops
, i
, scop
)
263 remove_gbbs_in_scop (scop
);
264 free_sese (SCOP_REGION (scop
));
271 /* Same as outermost_loop_in_sese, returns the outermost loop
272 containing BB in REGION, but makes sure that the returned loop
273 belongs to the REGION, and so this returns the first loop in the
274 REGION when the loop containing BB does not belong to REGION. */
277 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
279 loop_p nest
= outermost_loop_in_sese (region
, bb
);
281 if (loop_in_sese_p (nest
, region
))
284 /* When the basic block BB does not belong to a loop in the region,
285 return the first loop in the region. */
288 if (loop_in_sese_p (nest
, region
))
297 /* Generates a polyhedral black box only if the bb contains interesting
301 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
303 vec
<data_reference_p
> drs
;
305 sese region
= SCOP_REGION (scop
);
306 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
307 gimple_stmt_iterator gsi
;
309 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
311 gimple stmt
= gsi_stmt (gsi
);
314 if (is_gimple_debug (stmt
))
317 loop
= loop_containing_stmt (stmt
);
318 if (!loop_in_sese_p (loop
, region
))
321 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
324 return new_gimple_bb (bb
, drs
);
327 /* Returns true if all predecessors of BB, that are not dominated by BB, are
328 marked in MAP. The predecessors dominated by BB are loop latches and will
329 be handled after BB. */
332 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
337 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
338 if (!bitmap_bit_p (map
, e
->src
->index
)
339 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
345 /* Compare the depth of two basic_block's P1 and P2. */
348 compare_bb_depths (const void *p1
, const void *p2
)
350 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
351 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
352 int d1
= loop_depth (bb1
->loop_father
);
353 int d2
= loop_depth (bb2
->loop_father
);
364 /* Sort the basic blocks from DOM such that the first are the ones at
365 a deepest loop level. */
368 graphite_sort_dominated_info (vec
<basic_block
> dom
)
370 dom
.qsort (compare_bb_depths
);
373 /* Recursive helper function for build_scops_bbs. */
376 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
378 sese region
= SCOP_REGION (scop
);
379 vec
<basic_block
> dom
;
382 if (bitmap_bit_p (visited
, bb
->index
)
383 || !bb_in_sese_p (bb
, region
))
386 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
387 SCOP_BBS (scop
).safe_push (pbb
);
388 bitmap_set_bit (visited
, bb
->index
);
390 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
395 graphite_sort_dominated_info (dom
);
397 while (!dom
.is_empty ())
402 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
403 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
405 build_scop_bbs_1 (scop
, visited
, dom_bb
);
406 dom
.unordered_remove (i
);
414 /* Gather the basic blocks belonging to the SCOP. */
417 build_scop_bbs (scop_p scop
)
419 sbitmap visited
= sbitmap_alloc (last_basic_block
);
420 sese region
= SCOP_REGION (scop
);
422 bitmap_clear (visited
);
423 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
424 sbitmap_free (visited
);
427 /* Return an ISL identifier for the polyhedral basic block PBB. */
430 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
433 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
434 return isl_id_alloc (s
->ctx
, name
, pbb
);
437 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
438 We generate SCATTERING_DIMENSIONS scattering dimensions.
440 CLooG 0.15.0 and previous versions require, that all
441 scattering functions of one CloogProgram have the same number of
442 scattering dimensions, therefore we allow to specify it. This
443 should be removed in future versions of CLooG.
445 The scattering polyhedron consists of these dimensions: scattering,
446 loop_iterators, parameters.
450 | scattering_dimensions = 5
451 | used_scattering_dimensions = 3
459 | Scattering polyhedron:
461 | scattering: {s1, s2, s3, s4, s5}
462 | loop_iterators: {i}
463 | parameters: {p1, p2}
465 | s1 s2 s3 s4 s5 i p1 p2 1
466 | 1 0 0 0 0 0 0 0 -4 = 0
467 | 0 1 0 0 0 -1 0 0 0 = 0
468 | 0 0 1 0 0 0 0 0 -5 = 0 */
471 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
472 poly_bb_p pbb
, int scattering_dimensions
)
475 int nb_iterators
= pbb_dim_iter_domain (pbb
);
476 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
480 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
484 dc
= isl_set_get_space (pbb
->domain
);
485 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
486 isl_dim_out
, scattering_dimensions
);
487 pbb
->schedule
= isl_map_universe (dm
);
489 for (i
= 0; i
< scattering_dimensions
; i
++)
491 /* Textual order inside this loop. */
494 isl_constraint
*c
= isl_equality_alloc
495 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
497 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
501 isl_int_neg (val
, val
);
502 c
= isl_constraint_set_constant (c
, val
);
503 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
504 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
507 /* Iterations of this loop. */
508 else /* if ((i % 2) == 1) */
510 int loop
= (i
- 1) / 2;
511 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
518 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
521 /* Build for BB the static schedule.
523 The static schedule is a Dewey numbering of the abstract syntax
524 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
526 The following example informally defines the static schedule:
545 Static schedules for A to F:
558 build_scop_scattering (scop_p scop
)
562 gimple_bb_p previous_gbb
= NULL
;
563 isl_space
*dc
= isl_set_get_space (scop
->context
);
564 isl_aff
*static_sched
;
566 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
567 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
569 /* We have to start schedules at 0 on the first component and
570 because we cannot compare_prefix_loops against a previous loop,
571 prefix will be equal to zero, and that index will be
572 incremented before copying. */
573 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
575 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
577 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
579 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
582 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
588 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
590 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
593 isl_aff_free (static_sched
);
596 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
598 /* Extract an affine expression from the chain of recurrence E. */
601 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
603 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
604 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
605 isl_local_space
*ls
= isl_local_space_from_space (space
);
606 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
607 isl_aff
*loop
= isl_aff_set_coefficient_si
608 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
609 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
611 /* Before multiplying, make sure that the result is affine. */
612 gcc_assert (isl_pw_aff_is_cst (rhs
)
613 || isl_pw_aff_is_cst (l
));
615 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
618 /* Extract an affine expression from the mult_expr E. */
621 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
623 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
624 isl_space_copy (space
));
625 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
627 if (!isl_pw_aff_is_cst (lhs
)
628 && !isl_pw_aff_is_cst (rhs
))
630 isl_pw_aff_free (lhs
);
631 isl_pw_aff_free (rhs
);
635 return isl_pw_aff_mul (lhs
, rhs
);
638 /* Return an ISL identifier from the name of the ssa_name E. */
641 isl_id_for_ssa_name (scop_p s
, tree e
)
643 const char *name
= get_name (e
);
647 id
= isl_id_alloc (s
->ctx
, name
, e
);
651 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
652 id
= isl_id_alloc (s
->ctx
, name1
, e
);
658 /* Return an ISL identifier for the data reference DR. */
661 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
663 /* Data references all get the same isl_id. They need to be comparable
664 and are distinguished through the first dimension, which contains the
666 return isl_id_alloc (s
->ctx
, "", 0);
669 /* Extract an affine expression from the ssa_name E. */
672 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
679 id
= isl_id_for_ssa_name (s
, e
);
680 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
682 dom
= isl_set_universe (isl_space_copy (space
));
683 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
684 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
685 return isl_pw_aff_alloc (dom
, aff
);
688 /* Extract an affine expression from the gmp constant G. */
691 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
693 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
694 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
695 isl_set
*dom
= isl_set_universe (space
);
699 isl_int_set_gmp (v
, g
);
700 aff
= isl_aff_add_constant (aff
, v
);
703 return isl_pw_aff_alloc (dom
, aff
);
706 /* Extract an affine expression from the integer_cst E. */
709 extract_affine_int (tree e
, __isl_take isl_space
*space
)
715 tree_int_to_gmp (e
, g
);
716 res
= extract_affine_gmp (g
, space
);
722 /* Compute pwaff mod 2^width. */
725 wrap (isl_pw_aff
*pwaff
, unsigned width
)
730 isl_int_set_si (mod
, 1);
731 isl_int_mul_2exp (mod
, mod
, width
);
733 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
740 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
741 Otherwise returns -1. */
744 parameter_index_in_region_1 (tree name
, sese region
)
749 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
751 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
758 /* When the parameter NAME is in REGION, returns its index in
759 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
760 and returns the index of NAME. */
763 parameter_index_in_region (tree name
, sese region
)
767 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
769 i
= parameter_index_in_region_1 (name
, region
);
773 gcc_assert (SESE_ADD_PARAMS (region
));
775 i
= SESE_PARAMS (region
).length ();
776 SESE_PARAMS (region
).safe_push (name
);
780 /* Extract an affine expression from the tree E in the scop S. */
783 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
785 isl_pw_aff
*lhs
, *rhs
, *res
;
788 if (e
== chrec_dont_know
) {
789 isl_space_free (space
);
793 switch (TREE_CODE (e
))
795 case POLYNOMIAL_CHREC
:
796 res
= extract_affine_chrec (s
, e
, space
);
800 res
= extract_affine_mul (s
, e
, space
);
804 case POINTER_PLUS_EXPR
:
805 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
806 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
807 res
= isl_pw_aff_add (lhs
, rhs
);
811 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
812 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
813 res
= isl_pw_aff_sub (lhs
, rhs
);
818 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
819 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
820 res
= isl_pw_aff_mul (lhs
, rhs
);
824 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
825 res
= extract_affine_name (s
, e
, space
);
829 res
= extract_affine_int (e
, space
);
830 /* No need to wrap a single integer. */
834 case NON_LVALUE_EXPR
:
835 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
843 type
= TREE_TYPE (e
);
844 if (TYPE_UNSIGNED (type
))
845 res
= wrap (res
, TYPE_PRECISION (type
));
850 /* In the context of sese S, scan the expression E and translate it to
851 a linear expression C. When parsing a symbolic multiplication, K
852 represents the constant multiplier of an expression containing
856 scan_tree_for_params (sese s
, tree e
)
858 if (e
== chrec_dont_know
)
861 switch (TREE_CODE (e
))
863 case POLYNOMIAL_CHREC
:
864 scan_tree_for_params (s
, CHREC_LEFT (e
));
868 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
869 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
871 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
875 case POINTER_PLUS_EXPR
:
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
878 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
884 case NON_LVALUE_EXPR
:
885 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
889 parameter_index_in_region (e
, s
);
902 /* Find parameters with respect to REGION in BB. We are looking in memory
903 access functions, conditions and loop bounds. */
906 find_params_in_bb (sese region
, gimple_bb_p gbb
)
912 loop_p loop
= GBB_BB (gbb
)->loop_father
;
914 /* Find parameters in the access functions of data references. */
915 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
916 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
917 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
919 /* Find parameters in conditional statements. */
920 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
922 tree lhs
= scalar_evolution_in_region (region
, loop
,
923 gimple_cond_lhs (stmt
));
924 tree rhs
= scalar_evolution_in_region (region
, loop
,
925 gimple_cond_rhs (stmt
));
927 scan_tree_for_params (region
, lhs
);
928 scan_tree_for_params (region
, rhs
);
932 /* Record the parameters used in the SCOP. A variable is a parameter
933 in a scop if it does not vary during the execution of that scop. */
936 find_scop_parameters (scop_p scop
)
940 sese region
= SCOP_REGION (scop
);
944 /* Find the parameters used in the loop bounds. */
945 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
947 tree nb_iters
= number_of_latch_executions (loop
);
949 if (!chrec_contains_symbols (nb_iters
))
952 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
953 scan_tree_for_params (region
, nb_iters
);
956 /* Find the parameters used in data accesses. */
957 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
958 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
960 nbp
= sese_nb_params (region
);
961 scop_set_nb_params (scop
, nbp
);
962 SESE_ADD_PARAMS (region
) = false;
966 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
968 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
969 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
970 isl_id_for_ssa_name (scop
, e
));
972 scop
->context
= isl_set_universe (space
);
976 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
977 the constraints for the surrounding loops. */
980 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
982 isl_set
*outer
, isl_set
**doms
)
984 tree nb_iters
= number_of_latch_executions (loop
);
985 sese region
= SCOP_REGION (scop
);
987 isl_set
*inner
= isl_set_copy (outer
);
990 int pos
= isl_set_dim (outer
, isl_dim_set
);
997 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
998 space
= isl_set_get_space (inner
);
1001 c
= isl_inequality_alloc
1002 (isl_local_space_from_space (isl_space_copy (space
)));
1003 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1004 inner
= isl_set_add_constraint (inner
, c
);
1006 /* loop_i <= cst_nb_iters */
1007 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1009 c
= isl_inequality_alloc
1010 (isl_local_space_from_space (isl_space_copy (space
)));
1011 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1012 tree_int_to_gmp (nb_iters
, g
);
1013 isl_int_set_gmp (v
, g
);
1014 c
= isl_constraint_set_constant (c
, v
);
1015 inner
= isl_set_add_constraint (inner
, c
);
1018 /* loop_i <= expr_nb_iters */
1019 else if (!chrec_contains_undetermined (nb_iters
))
1024 isl_local_space
*ls
;
1028 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1030 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1031 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1032 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1033 isl_set_dim (valid
, isl_dim_set
));
1034 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1036 ls
= isl_local_space_from_space (isl_space_copy (space
));
1037 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1038 isl_dim_in
, pos
, 1);
1039 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1040 isl_pw_aff_copy (aff
));
1041 inner
= isl_set_intersect (inner
, le
);
1043 if (max_stmt_executions (loop
, &nit
))
1045 /* Insert in the context the constraints from the
1046 estimation of the number of iterations NIT and the
1047 symbolic number of iterations (involving parameter
1048 names) NB_ITERS. First, build the affine expression
1049 "NIT - NB_ITERS" and then say that it is positive,
1050 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1057 mpz_set_double_int (g
, nit
, false);
1058 mpz_sub_ui (g
, g
, 1);
1059 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1060 x
= isl_pw_aff_ge_set (approx
, aff
);
1061 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1062 isl_set_dim (x
, isl_dim_set
));
1063 scop
->context
= isl_set_intersect (scop
->context
, x
);
1065 c
= isl_inequality_alloc
1066 (isl_local_space_from_space (isl_space_copy (space
)));
1067 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1068 isl_int_set_gmp (v
, g
);
1070 c
= isl_constraint_set_constant (c
, v
);
1071 inner
= isl_set_add_constraint (inner
, c
);
1074 isl_pw_aff_free (aff
);
1079 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1080 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1081 isl_set_copy (inner
), doms
);
1085 && loop_in_sese_p (loop
->next
, region
))
1086 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1087 isl_set_copy (outer
), doms
);
1089 doms
[loop
->num
] = inner
;
1091 isl_set_free (outer
);
1092 isl_space_free (space
);
1097 /* Returns a linear expression for tree T evaluated in PBB. */
1100 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1102 scop_p scop
= PBB_SCOP (pbb
);
1104 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1105 gcc_assert (!automatically_generated_chrec_p (t
));
1107 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1110 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1111 operator. This allows us to invert the condition or to handle
1115 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1117 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1118 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1124 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1128 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1132 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1136 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1140 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1144 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1148 isl_pw_aff_free (lhs
);
1149 isl_pw_aff_free (rhs
);
1153 cond
= isl_set_coalesce (cond
);
1154 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1155 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1158 /* Add conditions to the domain of PBB. */
1161 add_conditions_to_domain (poly_bb_p pbb
)
1165 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1167 if (GBB_CONDITIONS (gbb
).is_empty ())
1170 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1171 switch (gimple_code (stmt
))
1175 enum tree_code code
= gimple_cond_code (stmt
);
1177 /* The conditions for ELSE-branches are inverted. */
1178 if (!GBB_CONDITION_CASES (gbb
)[i
])
1179 code
= invert_tree_comparison (code
, false);
1181 add_condition_to_pbb (pbb
, stmt
, code
);
1186 /* Switch statements are not supported right now - fall through. */
1194 /* Traverses all the GBBs of the SCOP and add their constraints to the
1195 iteration domains. */
1198 add_conditions_to_constraints (scop_p scop
)
1203 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1204 add_conditions_to_domain (pbb
);
1207 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1208 edge between BB and its predecessor is not a loop exit edge, and
1209 the last statement of the single predecessor is a COND_EXPR. */
1212 single_pred_cond_non_loop_exit (basic_block bb
)
1214 if (single_pred_p (bb
))
1216 edge e
= single_pred_edge (bb
);
1217 basic_block pred
= e
->src
;
1220 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1223 stmt
= last_stmt (pred
);
1225 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1232 class sese_dom_walker
: public dom_walker
1235 sese_dom_walker (cdi_direction
, sese
);
1237 virtual void before_dom_children (basic_block
);
1238 virtual void after_dom_children (basic_block
);
1241 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1245 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1246 : dom_walker (direction
), m_region (region
)
1250 /* Call-back for dom_walk executed before visiting the dominated
1254 sese_dom_walker::before_dom_children (basic_block bb
)
1259 if (!bb_in_sese_p (bb
, m_region
))
1262 stmt
= single_pred_cond_non_loop_exit (bb
);
1266 edge e
= single_pred_edge (bb
);
1268 m_conditions
.safe_push (stmt
);
1270 if (e
->flags
& EDGE_TRUE_VALUE
)
1271 m_cases
.safe_push (stmt
);
1273 m_cases
.safe_push (NULL
);
1276 gbb
= gbb_from_bb (bb
);
1280 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1281 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1285 /* Call-back for dom_walk executed after visiting the dominated
1289 sese_dom_walker::after_dom_children (basic_block bb
)
1291 if (!bb_in_sese_p (bb
, m_region
))
1294 if (single_pred_cond_non_loop_exit (bb
))
1296 m_conditions
.pop ();
1301 /* Add constraints on the possible values of parameter P from the type
1305 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1307 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1308 tree type
= TREE_TYPE (parameter
);
1309 tree lb
= NULL_TREE
;
1310 tree ub
= NULL_TREE
;
1312 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1313 lb
= lower_bound_in_type (type
, type
);
1315 lb
= TYPE_MIN_VALUE (type
);
1317 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1318 ub
= upper_bound_in_type (type
, type
);
1320 ub
= TYPE_MAX_VALUE (type
);
1324 isl_space
*space
= isl_set_get_space (scop
->context
);
1329 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1332 tree_int_to_gmp (lb
, g
);
1333 isl_int_set_gmp (v
, g
);
1336 c
= isl_constraint_set_constant (c
, v
);
1338 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1340 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1345 isl_space
*space
= isl_set_get_space (scop
->context
);
1350 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1354 tree_int_to_gmp (ub
, g
);
1355 isl_int_set_gmp (v
, g
);
1357 c
= isl_constraint_set_constant (c
, v
);
1359 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1361 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1365 /* Build the context of the SCOP. The context usually contains extra
1366 constraints that are added to the iteration domains that constrain
1370 build_scop_context (scop_p scop
)
1372 graphite_dim_t p
, n
= scop_nb_params (scop
);
1374 for (p
= 0; p
< n
; p
++)
1375 add_param_constraints (scop
, p
);
1378 /* Build the iteration domains: the loops belonging to the current
1379 SCOP, and that vary for the execution of the current basic block.
1380 Returns false if there is no loop in SCOP. */
1383 build_scop_iteration_domain (scop_p scop
)
1386 sese region
= SCOP_REGION (scop
);
1389 int nb_loops
= number_of_loops (cfun
);
1390 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1392 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1393 if (!loop_in_sese_p (loop_outer (loop
), region
))
1394 build_loop_iteration_domains (scop
, loop
, 0,
1395 isl_set_copy (scop
->context
), doms
);
1397 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1399 loop
= pbb_loop (pbb
);
1401 if (doms
[loop
->num
])
1402 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1404 pbb
->domain
= isl_set_copy (scop
->context
);
1406 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1407 isl_id_for_pbb (scop
, pbb
));
1410 for (i
= 0; i
< nb_loops
; i
++)
1412 isl_set_free (doms
[i
]);
1417 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1418 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1419 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1423 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1426 int alias_set_num
= 0;
1427 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1429 if (bap
&& bap
->alias_set
)
1430 alias_set_num
= *(bap
->alias_set
);
1432 c
= isl_equality_alloc
1433 (isl_local_space_from_space (isl_map_get_space (acc
)));
1434 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1435 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1437 return isl_map_add_constraint (acc
, c
);
1440 /* Assign the affine expression INDEX to the output dimension POS of
1441 MAP and return the result. */
1444 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1447 int len
= isl_map_dim (map
, isl_dim_out
);
1450 index_map
= isl_map_from_pw_aff (index
);
1451 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1452 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1454 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1455 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1456 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1457 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1459 return isl_map_intersect (map
, index_map
);
1462 /* Add to ACCESSES polyhedron equalities defining the access functions
1463 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1464 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1465 PBB is the poly_bb_p that contains the data reference DR. */
1468 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1470 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1471 scop_p scop
= PBB_SCOP (pbb
);
1473 for (i
= 0; i
< nb_subscripts
; i
++)
1476 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1478 aff
= extract_affine (scop
, afn
,
1479 isl_space_domain (isl_map_get_space (acc
)));
1480 acc
= set_index (acc
, i
+ 1, aff
);
1486 /* Add constrains representing the size of the accessed data to the
1487 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1488 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1492 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1494 tree ref
= DR_REF (dr
);
1495 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1497 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1501 if (TREE_CODE (ref
) != ARRAY_REF
)
1504 low
= array_ref_low_bound (ref
);
1505 high
= array_ref_up_bound (ref
);
1507 /* XXX The PPL code dealt separately with
1508 subscript - low >= 0 and high - subscript >= 0 in case one of
1509 the two bounds isn't known. Do the same here? */
1511 if (tree_fits_shwi_p (low
)
1513 && tree_fits_shwi_p (high
)
1514 /* 1-element arrays at end of structures may extend over
1515 their declared size. */
1516 && !(array_at_struct_end_p (ref
)
1517 && operand_equal_p (low
, high
, 0)))
1521 isl_set
*univ
, *lbs
, *ubs
;
1525 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1526 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1529 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1530 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1531 isl_set_dim (valid
, isl_dim_set
));
1532 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1534 space
= isl_set_get_space (extent
);
1535 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1536 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1537 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1538 index
= isl_pw_aff_alloc (univ
, aff
);
1540 id
= isl_set_get_tuple_id (extent
);
1541 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1542 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1544 /* low <= sub_i <= high */
1545 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1546 ubs
= isl_pw_aff_le_set (index
, ub
);
1547 extent
= isl_set_intersect (extent
, lbs
);
1548 extent
= isl_set_intersect (extent
, ubs
);
1555 /* Build data accesses for DR in PBB. */
1558 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1560 int dr_base_object_set
;
1563 scop_p scop
= PBB_SCOP (pbb
);
1566 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1567 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1568 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1569 isl_dim_out
, nb_out
);
1571 acc
= isl_map_universe (space
);
1572 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1575 acc
= pdr_add_alias_set (acc
, dr
);
1576 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1579 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1580 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1581 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1582 int alias_set_num
= 0;
1583 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1585 if (bap
&& bap
->alias_set
)
1586 alias_set_num
= *(bap
->alias_set
);
1588 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1589 extent
= isl_set_nat_universe (space
);
1590 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1591 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1594 gcc_assert (dr
->aux
);
1595 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1597 new_poly_dr (pbb
, dr_base_object_set
,
1598 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1599 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1602 /* Write to FILE the alias graph of data references in DIMACS format. */
1605 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1606 vec
<data_reference_p
> drs
)
1608 int num_vertex
= drs
.length ();
1610 data_reference_p dr1
, dr2
;
1613 if (num_vertex
== 0)
1616 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1617 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1618 if (dr_may_alias_p (dr1
, dr2
, true))
1621 fprintf (file
, "$\n");
1624 fprintf (file
, "c %s\n", comment
);
1626 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1628 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1629 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1630 if (dr_may_alias_p (dr1
, dr2
, true))
1631 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1636 /* Write to FILE the alias graph of data references in DOT format. */
1639 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1640 vec
<data_reference_p
> drs
)
1642 int num_vertex
= drs
.length ();
1643 data_reference_p dr1
, dr2
;
1646 if (num_vertex
== 0)
1649 fprintf (file
, "$\n");
1652 fprintf (file
, "c %s\n", comment
);
1654 /* First print all the vertices. */
1655 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1656 fprintf (file
, "n%d;\n", i
);
1658 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1659 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1660 if (dr_may_alias_p (dr1
, dr2
, true))
1661 fprintf (file
, "n%d n%d\n", i
, j
);
1666 /* Write to FILE the alias graph of data references in ECC format. */
1669 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1670 vec
<data_reference_p
> drs
)
1672 int num_vertex
= drs
.length ();
1673 data_reference_p dr1
, dr2
;
1676 if (num_vertex
== 0)
1679 fprintf (file
, "$\n");
1682 fprintf (file
, "c %s\n", comment
);
1684 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1685 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1686 if (dr_may_alias_p (dr1
, dr2
, true))
1687 fprintf (file
, "%d %d\n", i
, j
);
1692 /* Check if DR1 and DR2 are in the same object set. */
1695 dr_same_base_object_p (const struct data_reference
*dr1
,
1696 const struct data_reference
*dr2
)
1698 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1701 /* Uses DFS component number as representative of alias-sets. Also tests for
1702 optimality by verifying if every connected component is a clique. Returns
1703 true (1) if the above test is true, and false (0) otherwise. */
1706 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1708 int num_vertices
= drs
.length ();
1709 struct graph
*g
= new_graph (num_vertices
);
1710 data_reference_p dr1
, dr2
;
1712 int num_connected_components
;
1713 int v_indx1
, v_indx2
, num_vertices_in_component
;
1716 struct graph_edge
*e
;
1717 int this_component_is_clique
;
1718 int all_components_are_cliques
= 1;
1720 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1721 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1722 if (dr_may_alias_p (dr1
, dr2
, true))
1728 all_vertices
= XNEWVEC (int, num_vertices
);
1729 vertices
= XNEWVEC (int, num_vertices
);
1730 for (i
= 0; i
< num_vertices
; i
++)
1731 all_vertices
[i
] = i
;
1733 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1735 for (i
= 0; i
< g
->n_vertices
; i
++)
1737 data_reference_p dr
= drs
[i
];
1738 base_alias_pair
*bap
;
1740 gcc_assert (dr
->aux
);
1741 bap
= (base_alias_pair
*)(dr
->aux
);
1743 bap
->alias_set
= XNEW (int);
1744 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1747 /* Verify if the DFS numbering results in optimal solution. */
1748 for (i
= 0; i
< num_connected_components
; i
++)
1750 num_vertices_in_component
= 0;
1751 /* Get all vertices whose DFS component number is the same as i. */
1752 for (j
= 0; j
< num_vertices
; j
++)
1753 if (g
->vertices
[j
].component
== i
)
1754 vertices
[num_vertices_in_component
++] = j
;
1756 /* Now test if the vertices in 'vertices' form a clique, by testing
1757 for edges among each pair. */
1758 this_component_is_clique
= 1;
1759 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1761 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1763 /* Check if the two vertices are connected by iterating
1764 through all the edges which have one of these are source. */
1765 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1768 if (e
->src
== vertices
[v_indx1
])
1774 this_component_is_clique
= 0;
1778 if (!this_component_is_clique
)
1779 all_components_are_cliques
= 0;
1783 free (all_vertices
);
1786 return all_components_are_cliques
;
1789 /* Group each data reference in DRS with its base object set num. */
1792 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1794 int num_vertex
= drs
.length ();
1795 struct graph
*g
= new_graph (num_vertex
);
1796 data_reference_p dr1
, dr2
;
1800 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1801 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1802 if (dr_same_base_object_p (dr1
, dr2
))
1808 queue
= XNEWVEC (int, num_vertex
);
1809 for (i
= 0; i
< num_vertex
; i
++)
1812 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1814 for (i
= 0; i
< g
->n_vertices
; i
++)
1816 data_reference_p dr
= drs
[i
];
1817 base_alias_pair
*bap
;
1819 gcc_assert (dr
->aux
);
1820 bap
= (base_alias_pair
*)(dr
->aux
);
1822 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1829 /* Build the data references for PBB. */
1832 build_pbb_drs (poly_bb_p pbb
)
1835 data_reference_p dr
;
1836 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1838 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1839 build_poly_dr (dr
, pbb
);
1842 /* Dump to file the alias graphs for the data references in DRS. */
1845 dump_alias_graphs (vec
<data_reference_p
> drs
)
1848 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1850 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1853 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1854 current_function_name ());
1855 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1856 fclose (file_dimacs
);
1859 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1862 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1863 current_function_name ());
1864 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1868 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1871 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1872 current_function_name ());
1873 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1878 /* Build data references in SCOP. */
1881 build_scop_drs (scop_p scop
)
1885 data_reference_p dr
;
1886 stack_vec
<data_reference_p
, 3> drs
;
1888 /* Remove all the PBBs that do not have data references: these basic
1889 blocks are not handled in the polyhedral representation. */
1890 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1891 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1893 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1895 SCOP_BBS (scop
).ordered_remove (i
);
1899 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1900 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1903 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1904 dr
->aux
= XNEW (base_alias_pair
);
1906 if (!build_alias_set_optimal_p (drs
))
1908 /* TODO: Add support when building alias set is not optimal. */
1912 build_base_obj_set_for_drs (drs
);
1914 /* When debugging, enable the following code. This cannot be used
1915 in production compilers. */
1917 dump_alias_graphs (drs
);
1921 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1922 build_pbb_drs (pbb
);
1925 /* Return a gsi at the position of the phi node STMT. */
1927 static gimple_stmt_iterator
1928 gsi_for_phi_node (gimple stmt
)
1930 gimple_stmt_iterator psi
;
1931 basic_block bb
= gimple_bb (stmt
);
1933 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1934 if (stmt
== gsi_stmt (psi
))
1941 /* Analyze all the data references of STMTS and add them to the
1942 GBB_DATA_REFS vector of BB. */
1945 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1951 sese region
= SCOP_REGION (scop
);
1953 if (!bb_in_sese_p (bb
, region
))
1956 nest
= outermost_loop_in_sese_1 (region
, bb
);
1957 gbb
= gbb_from_bb (bb
);
1959 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1963 if (is_gimple_debug (stmt
))
1966 loop
= loop_containing_stmt (stmt
);
1967 if (!loop_in_sese_p (loop
, region
))
1970 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1971 &GBB_DATA_REFS (gbb
));
1975 /* Insert STMT at the end of the STMTS sequence and then insert the
1976 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1980 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1981 gimple_stmt_iterator insert_gsi
)
1983 gimple_stmt_iterator gsi
;
1984 stack_vec
<gimple
, 3> x
;
1986 gimple_seq_add_stmt (&stmts
, stmt
);
1987 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1988 x
.safe_push (gsi_stmt (gsi
));
1990 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1991 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1994 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1997 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2000 gimple_stmt_iterator gsi
;
2001 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2002 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2003 stack_vec
<gimple
, 3> x
;
2005 gimple_seq_add_stmt (&stmts
, stmt
);
2006 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2007 x
.safe_push (gsi_stmt (gsi
));
2009 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2011 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2012 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2016 gsi
= gsi_for_stmt (after_stmt
);
2017 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2020 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2023 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2026 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2028 vec
<data_reference_p
> drs
;
2030 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2031 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2032 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2033 int index
, n
= SCOP_BBS (scop
).length ();
2035 /* The INDEX of PBB in SCOP_BBS. */
2036 for (index
= 0; index
< n
; index
++)
2037 if (SCOP_BBS (scop
)[index
] == pbb
)
2040 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2042 GBB_PBB (gbb1
) = pbb1
;
2043 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2044 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2045 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2048 /* Insert on edge E the assignment "RES := EXPR". */
2051 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2053 gimple_stmt_iterator gsi
;
2054 gimple_seq stmts
= NULL
;
2055 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2056 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2058 stack_vec
<gimple
, 3> x
;
2060 gimple_seq_add_stmt (&stmts
, stmt
);
2061 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2062 x
.safe_push (gsi_stmt (gsi
));
2064 gsi_insert_seq_on_edge (e
, stmts
);
2065 gsi_commit_edge_inserts ();
2066 bb
= gimple_bb (stmt
);
2068 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2071 if (!gbb_from_bb (bb
))
2072 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2074 analyze_drs_in_stmts (scop
, bb
, x
);
2077 /* Creates a zero dimension array of the same type as VAR. */
2080 create_zero_dim_array (tree var
, const char *base_name
)
2082 tree index_type
= build_index_type (integer_zero_node
);
2083 tree elt_type
= TREE_TYPE (var
);
2084 tree array_type
= build_array_type (elt_type
, index_type
);
2085 tree base
= create_tmp_var (array_type
, base_name
);
2087 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2091 /* Returns true when PHI is a loop close phi node. */
2094 scalar_close_phi_node_p (gimple phi
)
2096 if (gimple_code (phi
) != GIMPLE_PHI
2097 || virtual_operand_p (gimple_phi_result (phi
)))
2100 /* Note that loop close phi nodes should have a single argument
2101 because we translated the representation into a canonical form
2102 before Graphite: see canonicalize_loop_closed_ssa_form. */
2103 return (gimple_phi_num_args (phi
) == 1);
2106 /* For a definition DEF in REGION, propagates the expression EXPR in
2107 all the uses of DEF outside REGION. */
2110 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2112 imm_use_iterator imm_iter
;
2115 bool replaced_once
= false;
2117 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2119 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2122 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2123 if (!is_gimple_debug (use_stmt
)
2124 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2127 use_operand_p use_p
;
2129 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2130 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2131 && (replaced_once
= true))
2132 replace_exp (use_p
, expr
);
2134 update_stmt (use_stmt
);
2139 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2140 gsi_commit_edge_inserts ();
2144 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2145 dimension array for it. */
2148 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2150 sese region
= SCOP_REGION (scop
);
2151 gimple phi
= gsi_stmt (*psi
);
2152 tree res
= gimple_phi_result (phi
);
2153 basic_block bb
= gimple_bb (phi
);
2154 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2155 tree arg
= gimple_phi_arg_def (phi
, 0);
2158 /* Note that loop close phi nodes should have a single argument
2159 because we translated the representation into a canonical form
2160 before Graphite: see canonicalize_loop_closed_ssa_form. */
2161 gcc_assert (gimple_phi_num_args (phi
) == 1);
2163 /* The phi node can be a non close phi node, when its argument is
2164 invariant, or a default definition. */
2165 if (is_gimple_min_invariant (arg
)
2166 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2168 propagate_expr_outside_region (res
, arg
, region
);
2173 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2175 propagate_expr_outside_region (res
, arg
, region
);
2176 stmt
= gimple_build_assign (res
, arg
);
2177 remove_phi_node (psi
, false);
2178 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2182 /* If res is scev analyzable and is not a scalar value, it is safe
2183 to ignore the close phi node: it will be code generated in the
2184 out of Graphite pass. */
2185 else if (scev_analyzable_p (res
, region
))
2187 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2190 if (!loop_in_sese_p (loop
, region
))
2192 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2193 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2194 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2197 scev
= scalar_evolution_in_region (region
, loop
, res
);
2199 if (tree_does_not_contain_chrecs (scev
))
2200 propagate_expr_outside_region (res
, scev
, region
);
2207 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2209 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2211 if (TREE_CODE (arg
) == SSA_NAME
)
2212 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2213 SSA_NAME_DEF_STMT (arg
));
2215 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2216 zero_dim_array
, arg
);
2219 remove_phi_node (psi
, false);
2220 SSA_NAME_DEF_STMT (res
) = stmt
;
2222 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2225 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2226 dimension array for it. */
2229 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2232 gimple phi
= gsi_stmt (*psi
);
2233 basic_block bb
= gimple_bb (phi
);
2234 tree res
= gimple_phi_result (phi
);
2235 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2238 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2240 tree arg
= gimple_phi_arg_def (phi
, i
);
2241 edge e
= gimple_phi_arg_edge (phi
, i
);
2243 /* Avoid the insertion of code in the loop latch to please the
2244 pattern matching of the vectorizer. */
2245 if (TREE_CODE (arg
) == SSA_NAME
2246 && e
->src
== bb
->loop_father
->latch
)
2247 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2248 SSA_NAME_DEF_STMT (arg
));
2250 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2253 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2254 remove_phi_node (psi
, false);
2255 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2258 /* Rewrite the degenerate phi node at position PSI from the degenerate
2259 form "x = phi (y, y, ..., y)" to "x = y". */
2262 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2266 gimple_stmt_iterator gsi
;
2267 gimple phi
= gsi_stmt (*psi
);
2268 tree res
= gimple_phi_result (phi
);
2271 bb
= gimple_bb (phi
);
2272 rhs
= degenerate_phi_result (phi
);
2275 stmt
= gimple_build_assign (res
, rhs
);
2276 remove_phi_node (psi
, false);
2278 gsi
= gsi_after_labels (bb
);
2279 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2282 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2285 rewrite_reductions_out_of_ssa (scop_p scop
)
2288 gimple_stmt_iterator psi
;
2289 sese region
= SCOP_REGION (scop
);
2292 if (bb_in_sese_p (bb
, region
))
2293 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2295 gimple phi
= gsi_stmt (psi
);
2297 if (virtual_operand_p (gimple_phi_result (phi
)))
2303 if (gimple_phi_num_args (phi
) > 1
2304 && degenerate_phi_result (phi
))
2305 rewrite_degenerate_phi (&psi
);
2307 else if (scalar_close_phi_node_p (phi
))
2308 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2310 else if (reduction_phi_p (region
, &psi
))
2311 rewrite_phi_out_of_ssa (scop
, &psi
);
2314 update_ssa (TODO_update_ssa
);
2315 #ifdef ENABLE_CHECKING
2316 verify_loop_closed_ssa (true);
2320 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2321 read from ZERO_DIM_ARRAY. */
2324 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2325 tree def
, gimple use_stmt
)
2330 use_operand_p use_p
;
2332 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2334 name
= copy_ssa_name (def
, NULL
);
2335 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2337 gimple_assign_set_lhs (name_stmt
, name
);
2338 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2340 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2341 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2342 replace_exp (use_p
, name
);
2344 update_stmt (use_stmt
);
2347 /* For every definition DEF in the SCOP that is used outside the scop,
2348 insert a closing-scop definition in the basic block just after this
2352 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2354 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2355 tree new_name
= make_ssa_name (var
, stmt
);
2356 bool needs_copy
= false;
2357 use_operand_p use_p
;
2358 imm_use_iterator imm_iter
;
2360 sese region
= SCOP_REGION (scop
);
2362 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2364 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2366 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2368 SET_USE (use_p
, new_name
);
2370 update_stmt (use_stmt
);
2375 /* Insert in the empty BB just after the scop a use of DEF such
2376 that the rewrite of cross_bb_scalar_dependences won't insert
2377 arrays everywhere else. */
2380 gimple assign
= gimple_build_assign (new_name
, def
);
2381 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2383 update_stmt (assign
);
2384 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2388 /* Rewrite the scalar dependences crossing the boundary of the BB
2389 containing STMT with an array. Return true when something has been
2393 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2395 sese region
= SCOP_REGION (scop
);
2396 gimple stmt
= gsi_stmt (*gsi
);
2397 imm_use_iterator imm_iter
;
2400 tree zero_dim_array
= NULL_TREE
;
2404 switch (gimple_code (stmt
))
2407 def
= gimple_assign_lhs (stmt
);
2411 def
= gimple_call_lhs (stmt
);
2419 || !is_gimple_reg (def
))
2422 if (scev_analyzable_p (def
, region
))
2424 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2425 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2427 if (tree_contains_chrecs (scev
, NULL
))
2430 propagate_expr_outside_region (def
, scev
, region
);
2434 def_bb
= gimple_bb (stmt
);
2436 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2438 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2439 if (gimple_code (use_stmt
) == GIMPLE_PHI
2442 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2444 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2445 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2447 rewrite_phi_out_of_ssa (scop
, &psi
);
2450 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2451 if (gimple_code (use_stmt
) != GIMPLE_PHI
2452 && def_bb
!= gimple_bb (use_stmt
)
2453 && !is_gimple_debug (use_stmt
)
2456 if (!zero_dim_array
)
2458 zero_dim_array
= create_zero_dim_array
2459 (def
, "Cross_BB_scalar_dependence");
2460 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2461 SSA_NAME_DEF_STMT (def
));
2465 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2472 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2475 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2478 gimple_stmt_iterator psi
;
2479 sese region
= SCOP_REGION (scop
);
2480 bool changed
= false;
2482 /* Create an extra empty BB after the scop. */
2483 split_edge (SESE_EXIT (region
));
2486 if (bb_in_sese_p (bb
, region
))
2487 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2488 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2493 update_ssa (TODO_update_ssa
);
2494 #ifdef ENABLE_CHECKING
2495 verify_loop_closed_ssa (true);
2500 /* Returns the number of pbbs that are in loops contained in SCOP. */
2503 nb_pbbs_in_loops (scop_p scop
)
2509 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2510 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2516 /* Return the number of data references in BB that write in
2520 nb_data_writes_in_bb (basic_block bb
)
2523 gimple_stmt_iterator gsi
;
2525 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2526 if (gimple_vdef (gsi_stmt (gsi
)))
2532 /* Splits at STMT the basic block BB represented as PBB in the
2536 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2538 edge e1
= split_block (bb
, stmt
);
2539 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2543 /* Splits STMT out of its current BB. This is done for reduction
2544 statements for which we want to ignore data dependences. */
2547 split_reduction_stmt (scop_p scop
, gimple stmt
)
2549 basic_block bb
= gimple_bb (stmt
);
2550 poly_bb_p pbb
= pbb_from_bb (bb
);
2551 gimple_bb_p gbb
= gbb_from_bb (bb
);
2554 data_reference_p dr
;
2556 /* Do not split basic blocks with no writes to memory: the reduction
2557 will be the only write to memory. */
2558 if (nb_data_writes_in_bb (bb
) == 0
2559 /* Or if we have already marked BB as a reduction. */
2560 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2563 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2565 /* Split once more only when the reduction stmt is not the only one
2566 left in the original BB. */
2567 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2569 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2571 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2574 /* A part of the data references will end in a different basic block
2575 after the split: move the DRs from the original GBB to the newly
2577 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2579 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2583 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2584 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2585 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2593 /* Return true when stmt is a reduction operation. */
2596 is_reduction_operation_p (gimple stmt
)
2598 enum tree_code code
;
2600 gcc_assert (is_gimple_assign (stmt
));
2601 code
= gimple_assign_rhs_code (stmt
);
2603 return flag_associative_math
2604 && commutative_tree_code (code
)
2605 && associative_tree_code (code
);
2608 /* Returns true when PHI contains an argument ARG. */
2611 phi_contains_arg (gimple phi
, tree arg
)
2615 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2616 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2622 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2625 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2629 if (TREE_CODE (arg
) != SSA_NAME
)
2632 stmt
= SSA_NAME_DEF_STMT (arg
);
2634 if (gimple_code (stmt
) == GIMPLE_NOP
2635 || gimple_code (stmt
) == GIMPLE_CALL
)
2638 if (gimple_code (stmt
) == GIMPLE_PHI
)
2640 if (phi_contains_arg (stmt
, lhs
))
2645 if (!is_gimple_assign (stmt
))
2648 if (gimple_num_ops (stmt
) == 2)
2649 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2651 if (is_reduction_operation_p (stmt
))
2653 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2656 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2662 /* Detect commutative and associative scalar reductions starting at
2663 the STMT. Return the phi node of the reduction cycle, or NULL. */
2666 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2670 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2675 in
->safe_push (stmt
);
2676 out
->safe_push (stmt
);
2680 /* Detect commutative and associative scalar reductions starting at
2681 STMT. Return the phi node of the reduction cycle, or NULL. */
2684 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2687 tree lhs
= gimple_assign_lhs (stmt
);
2689 if (gimple_num_ops (stmt
) == 2)
2690 return detect_commutative_reduction_arg (lhs
, stmt
,
2691 gimple_assign_rhs1 (stmt
),
2694 if (is_reduction_operation_p (stmt
))
2696 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2697 gimple_assign_rhs1 (stmt
),
2700 : detect_commutative_reduction_arg (lhs
, stmt
,
2701 gimple_assign_rhs2 (stmt
),
2708 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2711 follow_inital_value_to_phi (tree arg
, tree lhs
)
2715 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2718 stmt
= SSA_NAME_DEF_STMT (arg
);
2720 if (gimple_code (stmt
) == GIMPLE_PHI
2721 && phi_contains_arg (stmt
, lhs
))
2728 /* Return the argument of the loop PHI that is the initial value coming
2729 from outside the loop. */
2732 edge_initial_value_for_loop_phi (gimple phi
)
2736 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2738 edge e
= gimple_phi_arg_edge (phi
, i
);
2740 if (loop_depth (e
->src
->loop_father
)
2741 < loop_depth (e
->dest
->loop_father
))
2748 /* Return the argument of the loop PHI that is the initial value coming
2749 from outside the loop. */
2752 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
))
2762 return gimple_phi_arg_def (phi
, i
);
2768 /* Returns true when DEF is used outside the reduction cycle of
2772 used_outside_reduction (tree def
, gimple loop_phi
)
2774 use_operand_p use_p
;
2775 imm_use_iterator imm_iter
;
2776 loop_p loop
= loop_containing_stmt (loop_phi
);
2778 /* In LOOP, DEF should be used only in LOOP_PHI. */
2779 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2781 gimple stmt
= USE_STMT (use_p
);
2783 if (stmt
!= loop_phi
2784 && !is_gimple_debug (stmt
)
2785 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2792 /* Detect commutative and associative scalar reductions belonging to
2793 the SCOP starting at the loop closed phi node STMT. Return the phi
2794 node of the reduction cycle, or NULL. */
2797 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2800 if (scalar_close_phi_node_p (stmt
))
2802 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2803 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2805 if (TREE_CODE (arg
) != SSA_NAME
)
2808 /* Note that loop close phi nodes should have a single argument
2809 because we translated the representation into a canonical form
2810 before Graphite: see canonicalize_loop_closed_ssa_form. */
2811 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2813 def
= SSA_NAME_DEF_STMT (arg
);
2814 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2815 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2818 lhs
= gimple_phi_result (close_phi
);
2819 init
= initial_value_for_loop_phi (loop_phi
);
2820 phi
= follow_inital_value_to_phi (init
, lhs
);
2822 if (phi
&& (used_outside_reduction (lhs
, phi
)
2823 || !has_single_use (gimple_phi_result (phi
))))
2826 in
->safe_push (loop_phi
);
2827 out
->safe_push (close_phi
);
2831 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2832 return detect_commutative_reduction_assign (stmt
, in
, out
);
2837 /* Translate the scalar reduction statement STMT to an array RED
2838 knowing that its recursive phi node is LOOP_PHI. */
2841 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2842 gimple stmt
, gimple loop_phi
)
2844 tree res
= gimple_phi_result (loop_phi
);
2845 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2846 gimple_stmt_iterator gsi
;
2848 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2850 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2851 gsi
= gsi_for_stmt (stmt
);
2853 insert_stmts (scop
, assign
, NULL
, gsi
);
2856 /* Removes the PHI node and resets all the debug stmts that are using
2860 remove_phi (gimple phi
)
2862 imm_use_iterator imm_iter
;
2864 use_operand_p use_p
;
2865 gimple_stmt_iterator gsi
;
2866 stack_vec
<gimple
, 3> update
;
2870 def
= PHI_RESULT (phi
);
2871 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2873 stmt
= USE_STMT (use_p
);
2875 if (is_gimple_debug (stmt
))
2877 gimple_debug_bind_reset_value (stmt
);
2878 update
.safe_push (stmt
);
2882 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2885 gsi
= gsi_for_phi_node (phi
);
2886 remove_phi_node (&gsi
, false);
2889 /* Helper function for for_each_index. For each INDEX of the data
2890 reference REF, returns true when its indices are valid in the loop
2891 nest LOOP passed in as DATA. */
2894 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2897 basic_block header
, def_bb
;
2900 if (TREE_CODE (*index
) != SSA_NAME
)
2903 loop
= *((loop_p
*) data
);
2904 header
= loop
->header
;
2905 stmt
= SSA_NAME_DEF_STMT (*index
);
2910 def_bb
= gimple_bb (stmt
);
2915 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2918 /* When the result of a CLOSE_PHI is written to a memory location,
2919 return a pointer to that memory reference, otherwise return
2923 close_phi_written_to_memory (gimple close_phi
)
2925 imm_use_iterator imm_iter
;
2926 use_operand_p use_p
;
2928 tree res
, def
= gimple_phi_result (close_phi
);
2930 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2931 if ((stmt
= USE_STMT (use_p
))
2932 && gimple_code (stmt
) == GIMPLE_ASSIGN
2933 && (res
= gimple_assign_lhs (stmt
)))
2935 switch (TREE_CODE (res
))
2945 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2946 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2948 /* FIXME: this restriction is for id-{24,25}.f and
2949 could be handled by duplicating the computation of
2950 array indices before the loop of the close_phi. */
2951 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2963 /* Rewrite out of SSA the reduction described by the loop phi nodes
2964 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2967 IN: stmt, loop_n, ..., loop_0
2968 OUT: stmt, close_n, ..., close_0
2970 the first element is the reduction statement, and the next elements
2971 are the loop and close phi nodes of each of the outer loops. */
2974 translate_scalar_reduction_to_array (scop_p scop
,
2979 unsigned int i
= out
.length () - 1;
2980 tree red
= close_phi_written_to_memory (out
[i
]);
2982 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2984 gimple close_phi
= out
[i
];
2988 gimple stmt
= loop_phi
;
2989 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2990 poly_bb_p pbb
= pbb_from_bb (bb
);
2991 PBB_IS_REDUCTION (pbb
) = true;
2992 gcc_assert (close_phi
== loop_phi
);
2995 red
= create_zero_dim_array
2996 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2998 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3002 if (i
== in
.length () - 1)
3004 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3005 unshare_expr (red
), close_phi
);
3006 insert_out_of_ssa_copy_on_edge
3007 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3008 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3011 remove_phi (loop_phi
);
3012 remove_phi (close_phi
);
3016 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3017 true when something has been changed. */
3020 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3024 stack_vec
<gimple
, 10> in
;
3025 stack_vec
<gimple
, 10> out
;
3027 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3028 res
= in
.length () > 1;
3030 translate_scalar_reduction_to_array (scop
, in
, out
);
3035 /* Rewrites all the commutative reductions from LOOP out of SSA.
3036 Returns true when something has been changed. */
3039 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3042 gimple_stmt_iterator gsi
;
3043 edge exit
= single_exit (loop
);
3045 bool changed
= false;
3050 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3051 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3052 && !virtual_operand_p (res
)
3053 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3054 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3055 (scop
, gsi_stmt (gsi
));
3060 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3063 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3067 bool changed
= false;
3068 sese region
= SCOP_REGION (scop
);
3070 FOR_EACH_LOOP (li
, loop
, 0)
3071 if (loop_in_sese_p (loop
, region
))
3072 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3077 gsi_commit_edge_inserts ();
3078 update_ssa (TODO_update_ssa
);
3079 #ifdef ENABLE_CHECKING
3080 verify_loop_closed_ssa (true);
3085 /* Can all ivs be represented by a signed integer?
3086 As CLooG might generate negative values in its expressions, signed loop ivs
3087 are required in the backend. */
3090 scop_ivs_can_be_represented (scop_p scop
)
3094 gimple_stmt_iterator psi
;
3097 FOR_EACH_LOOP (li
, loop
, 0)
3099 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3102 for (psi
= gsi_start_phis (loop
->header
);
3103 !gsi_end_p (psi
); gsi_next (&psi
))
3105 gimple phi
= gsi_stmt (psi
);
3106 tree res
= PHI_RESULT (phi
);
3107 tree type
= TREE_TYPE (res
);
3109 if (TYPE_UNSIGNED (type
)
3110 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3117 FOR_EACH_LOOP_BREAK (li
);
3123 /* Builds the polyhedral representation for a SESE region. */
3126 build_poly_scop (scop_p scop
)
3128 sese region
= SCOP_REGION (scop
);
3129 graphite_dim_t max_dim
;
3131 build_scop_bbs (scop
);
3133 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3134 Once CLooG is fixed, remove this guard. Anyways, it makes no
3135 sense to optimize a scop containing only PBBs that do not belong
3137 if (nb_pbbs_in_loops (scop
) == 0)
3140 if (!scop_ivs_can_be_represented (scop
))
3143 if (flag_associative_math
)
3144 rewrite_commutative_reductions_out_of_ssa (scop
);
3146 build_sese_loop_nests (region
);
3147 /* Record all conditions in REGION. */
3148 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3149 find_scop_parameters (scop
);
3151 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3152 if (scop_nb_params (scop
) > max_dim
)
3155 build_scop_iteration_domain (scop
);
3156 build_scop_context (scop
);
3157 add_conditions_to_constraints (scop
);
3159 /* Rewrite out of SSA only after having translated the
3160 representation to the polyhedral representation to avoid scev
3161 analysis failures. That means that these functions will insert
3162 new data references that they create in the right place. */
3163 rewrite_reductions_out_of_ssa (scop
);
3164 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3166 build_scop_drs (scop
);
3168 build_scop_scattering (scop
);
3170 /* This SCoP has been translated to the polyhedral
3172 POLY_SCOP_P (scop
) = true;