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-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "tree-ssanames.h"
43 #include "tree-ssa-loop-manip.h"
44 #include "tree-ssa-loop-niter.h"
45 #include "tree-ssa-loop.h"
46 #include "tree-into-ssa.h"
47 #include "tree-pass.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
54 #include "tree-ssa-propagate.h"
57 #include "graphite-poly.h"
58 #include "graphite-sese-to-poly.h"
61 /* Assigns to RES the value of the INTEGER_CST T. */
64 tree_int_to_gmp (tree t
, mpz_t res
)
66 double_int di
= tree_to_double_int (t
);
67 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
70 /* Returns the index of the PHI argument defined in the outermost
74 phi_arg_in_outermost_loop (gimple phi
)
76 loop_p loop
= gimple_bb (phi
)->loop_father
;
79 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
80 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
82 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
89 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
90 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
93 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
95 gimple phi
= gsi_stmt (*psi
);
96 tree res
= gimple_phi_result (phi
);
97 size_t entry
= phi_arg_in_outermost_loop (phi
);
98 tree init
= gimple_phi_arg_def (phi
, entry
);
99 gimple stmt
= gimple_build_assign (res
, init
);
100 edge e
= gimple_phi_arg_edge (phi
, entry
);
102 remove_phi_node (psi
, false);
103 gsi_insert_on_edge_immediate (e
, stmt
);
104 SSA_NAME_DEF_STMT (res
) = stmt
;
107 /* Removes an invariant phi node at position PSI by inserting on the
108 loop ENTRY edge the assignment RES = INIT. */
111 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
113 gimple phi
= gsi_stmt (*psi
);
114 loop_p loop
= loop_containing_stmt (phi
);
115 tree res
= gimple_phi_result (phi
);
116 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
117 size_t entry
= phi_arg_in_outermost_loop (phi
);
118 edge e
= gimple_phi_arg_edge (phi
, entry
);
121 gimple_seq stmts
= NULL
;
123 if (tree_contains_chrecs (scev
, NULL
))
124 scev
= gimple_phi_arg_def (phi
, entry
);
126 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
127 stmt
= gimple_build_assign (res
, var
);
128 remove_phi_node (psi
, false);
130 gimple_seq_add_stmt (&stmts
, stmt
);
131 gsi_insert_seq_on_edge (e
, stmts
);
132 gsi_commit_edge_inserts ();
133 SSA_NAME_DEF_STMT (res
) = stmt
;
136 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
139 simple_copy_phi_p (gimple phi
)
143 if (gimple_phi_num_args (phi
) != 2)
146 res
= gimple_phi_result (phi
);
147 return (res
== gimple_phi_arg_def (phi
, 0)
148 || res
== gimple_phi_arg_def (phi
, 1));
151 /* Returns true when the phi node at position PSI is a reduction phi
152 node in REGION. Otherwise moves the pointer PSI to the next phi to
156 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
159 gimple phi
= gsi_stmt (*psi
);
160 tree res
= gimple_phi_result (phi
);
162 loop
= loop_containing_stmt (phi
);
164 if (simple_copy_phi_p (phi
))
166 /* PRE introduces phi nodes like these, for an example,
167 see id-5.f in the fortran graphite testsuite:
169 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
171 remove_simple_copy_phi (psi
);
175 if (scev_analyzable_p (res
, region
))
177 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
179 if (evolution_function_is_invariant_p (scev
, loop
->num
))
180 remove_invariant_phi (region
, psi
);
187 /* All the other cases are considered reductions. */
191 /* Store the GRAPHITE representation of BB. */
194 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
196 struct gimple_bb
*gbb
;
198 gbb
= XNEW (struct gimple_bb
);
201 GBB_DATA_REFS (gbb
) = drs
;
202 GBB_CONDITIONS (gbb
).create (0);
203 GBB_CONDITION_CASES (gbb
).create (0);
209 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
212 struct data_reference
*dr
;
214 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
217 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
219 free (bap
->alias_set
);
228 free_gimple_bb (struct gimple_bb
*gbb
)
230 free_data_refs_aux (GBB_DATA_REFS (gbb
));
231 free_data_refs (GBB_DATA_REFS (gbb
));
233 GBB_CONDITIONS (gbb
).release ();
234 GBB_CONDITION_CASES (gbb
).release ();
235 GBB_BB (gbb
)->aux
= 0;
239 /* Deletes all gimple bbs in SCOP. */
242 remove_gbbs_in_scop (scop_p scop
)
247 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
248 free_gimple_bb (PBB_BLACK_BOX (pbb
));
251 /* Deletes all scops in SCOPS. */
254 free_scops (vec
<scop_p
> scops
)
259 FOR_EACH_VEC_ELT (scops
, i
, scop
)
261 remove_gbbs_in_scop (scop
);
262 free_sese (SCOP_REGION (scop
));
269 /* Same as outermost_loop_in_sese, returns the outermost loop
270 containing BB in REGION, but makes sure that the returned loop
271 belongs to the REGION, and so this returns the first loop in the
272 REGION when the loop containing BB does not belong to REGION. */
275 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
277 loop_p nest
= outermost_loop_in_sese (region
, bb
);
279 if (loop_in_sese_p (nest
, region
))
282 /* When the basic block BB does not belong to a loop in the region,
283 return the first loop in the region. */
286 if (loop_in_sese_p (nest
, region
))
295 /* Generates a polyhedral black box only if the bb contains interesting
299 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
301 vec
<data_reference_p
> drs
;
303 sese region
= SCOP_REGION (scop
);
304 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
305 gimple_stmt_iterator gsi
;
307 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
309 gimple stmt
= gsi_stmt (gsi
);
312 if (is_gimple_debug (stmt
))
315 loop
= loop_containing_stmt (stmt
);
316 if (!loop_in_sese_p (loop
, region
))
319 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
322 return new_gimple_bb (bb
, drs
);
325 /* Returns true if all predecessors of BB, that are not dominated by BB, are
326 marked in MAP. The predecessors dominated by BB are loop latches and will
327 be handled after BB. */
330 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
335 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
336 if (!bitmap_bit_p (map
, e
->src
->index
)
337 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
343 /* Compare the depth of two basic_block's P1 and P2. */
346 compare_bb_depths (const void *p1
, const void *p2
)
348 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
349 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
350 int d1
= loop_depth (bb1
->loop_father
);
351 int d2
= loop_depth (bb2
->loop_father
);
362 /* Sort the basic blocks from DOM such that the first are the ones at
363 a deepest loop level. */
366 graphite_sort_dominated_info (vec
<basic_block
> dom
)
368 dom
.qsort (compare_bb_depths
);
371 /* Recursive helper function for build_scops_bbs. */
374 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
376 sese region
= SCOP_REGION (scop
);
377 vec
<basic_block
> dom
;
380 if (bitmap_bit_p (visited
, bb
->index
)
381 || !bb_in_sese_p (bb
, region
))
384 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
385 SCOP_BBS (scop
).safe_push (pbb
);
386 bitmap_set_bit (visited
, bb
->index
);
388 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
393 graphite_sort_dominated_info (dom
);
395 while (!dom
.is_empty ())
400 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
401 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
403 build_scop_bbs_1 (scop
, visited
, dom_bb
);
404 dom
.unordered_remove (i
);
412 /* Gather the basic blocks belonging to the SCOP. */
415 build_scop_bbs (scop_p scop
)
417 sbitmap visited
= sbitmap_alloc (last_basic_block
);
418 sese region
= SCOP_REGION (scop
);
420 bitmap_clear (visited
);
421 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
422 sbitmap_free (visited
);
425 /* Return an ISL identifier for the polyhedral basic block PBB. */
428 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
431 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
432 return isl_id_alloc (s
->ctx
, name
, pbb
);
435 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
436 We generate SCATTERING_DIMENSIONS scattering dimensions.
438 CLooG 0.15.0 and previous versions require, that all
439 scattering functions of one CloogProgram have the same number of
440 scattering dimensions, therefore we allow to specify it. This
441 should be removed in future versions of CLooG.
443 The scattering polyhedron consists of these dimensions: scattering,
444 loop_iterators, parameters.
448 | scattering_dimensions = 5
449 | used_scattering_dimensions = 3
457 | Scattering polyhedron:
459 | scattering: {s1, s2, s3, s4, s5}
460 | loop_iterators: {i}
461 | parameters: {p1, p2}
463 | s1 s2 s3 s4 s5 i p1 p2 1
464 | 1 0 0 0 0 0 0 0 -4 = 0
465 | 0 1 0 0 0 -1 0 0 0 = 0
466 | 0 0 1 0 0 0 0 0 -5 = 0 */
469 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
470 poly_bb_p pbb
, int scattering_dimensions
)
473 int nb_iterators
= pbb_dim_iter_domain (pbb
);
474 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
478 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
482 dc
= isl_set_get_space (pbb
->domain
);
483 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
484 isl_dim_out
, scattering_dimensions
);
485 pbb
->schedule
= isl_map_universe (dm
);
487 for (i
= 0; i
< scattering_dimensions
; i
++)
489 /* Textual order inside this loop. */
492 isl_constraint
*c
= isl_equality_alloc
493 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
495 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
499 isl_int_neg (val
, val
);
500 c
= isl_constraint_set_constant (c
, val
);
501 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
502 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
505 /* Iterations of this loop. */
506 else /* if ((i % 2) == 1) */
508 int loop
= (i
- 1) / 2;
509 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
516 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
519 /* Build for BB the static schedule.
521 The static schedule is a Dewey numbering of the abstract syntax
522 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
524 The following example informally defines the static schedule:
543 Static schedules for A to F:
556 build_scop_scattering (scop_p scop
)
560 gimple_bb_p previous_gbb
= NULL
;
561 isl_space
*dc
= isl_set_get_space (scop
->context
);
562 isl_aff
*static_sched
;
564 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
565 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
567 /* We have to start schedules at 0 on the first component and
568 because we cannot compare_prefix_loops against a previous loop,
569 prefix will be equal to zero, and that index will be
570 incremented before copying. */
571 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
573 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
575 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
577 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
580 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
586 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
588 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
591 isl_aff_free (static_sched
);
594 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
596 /* Extract an affine expression from the chain of recurrence E. */
599 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
601 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
602 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
603 isl_local_space
*ls
= isl_local_space_from_space (space
);
604 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
605 isl_aff
*loop
= isl_aff_set_coefficient_si
606 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
607 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
609 /* Before multiplying, make sure that the result is affine. */
610 gcc_assert (isl_pw_aff_is_cst (rhs
)
611 || isl_pw_aff_is_cst (l
));
613 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
616 /* Extract an affine expression from the mult_expr E. */
619 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
621 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
622 isl_space_copy (space
));
623 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
625 if (!isl_pw_aff_is_cst (lhs
)
626 && !isl_pw_aff_is_cst (rhs
))
628 isl_pw_aff_free (lhs
);
629 isl_pw_aff_free (rhs
);
633 return isl_pw_aff_mul (lhs
, rhs
);
636 /* Return an ISL identifier from the name of the ssa_name E. */
639 isl_id_for_ssa_name (scop_p s
, tree e
)
641 const char *name
= get_name (e
);
645 id
= isl_id_alloc (s
->ctx
, name
, e
);
649 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
650 id
= isl_id_alloc (s
->ctx
, name1
, e
);
656 /* Return an ISL identifier for the data reference DR. */
659 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
661 /* Data references all get the same isl_id. They need to be comparable
662 and are distinguished through the first dimension, which contains the
664 return isl_id_alloc (s
->ctx
, "", 0);
667 /* Extract an affine expression from the ssa_name E. */
670 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
677 id
= isl_id_for_ssa_name (s
, e
);
678 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
680 dom
= isl_set_universe (isl_space_copy (space
));
681 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
682 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
683 return isl_pw_aff_alloc (dom
, aff
);
686 /* Extract an affine expression from the gmp constant G. */
689 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
691 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
692 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
693 isl_set
*dom
= isl_set_universe (space
);
697 isl_int_set_gmp (v
, g
);
698 aff
= isl_aff_add_constant (aff
, v
);
701 return isl_pw_aff_alloc (dom
, aff
);
704 /* Extract an affine expression from the integer_cst E. */
707 extract_affine_int (tree e
, __isl_take isl_space
*space
)
713 tree_int_to_gmp (e
, g
);
714 res
= extract_affine_gmp (g
, space
);
720 /* Compute pwaff mod 2^width. */
723 wrap (isl_pw_aff
*pwaff
, unsigned width
)
728 isl_int_set_si (mod
, 1);
729 isl_int_mul_2exp (mod
, mod
, width
);
731 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
738 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
739 Otherwise returns -1. */
742 parameter_index_in_region_1 (tree name
, sese region
)
747 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
749 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
756 /* When the parameter NAME is in REGION, returns its index in
757 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
758 and returns the index of NAME. */
761 parameter_index_in_region (tree name
, sese region
)
765 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
767 i
= parameter_index_in_region_1 (name
, region
);
771 gcc_assert (SESE_ADD_PARAMS (region
));
773 i
= SESE_PARAMS (region
).length ();
774 SESE_PARAMS (region
).safe_push (name
);
778 /* Extract an affine expression from the tree E in the scop S. */
781 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
783 isl_pw_aff
*lhs
, *rhs
, *res
;
786 if (e
== chrec_dont_know
) {
787 isl_space_free (space
);
791 switch (TREE_CODE (e
))
793 case POLYNOMIAL_CHREC
:
794 res
= extract_affine_chrec (s
, e
, space
);
798 res
= extract_affine_mul (s
, e
, space
);
802 case POINTER_PLUS_EXPR
:
803 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
804 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
805 res
= isl_pw_aff_add (lhs
, rhs
);
809 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
810 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
811 res
= isl_pw_aff_sub (lhs
, rhs
);
816 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
817 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
818 res
= isl_pw_aff_mul (lhs
, rhs
);
822 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
823 res
= extract_affine_name (s
, e
, space
);
827 res
= extract_affine_int (e
, space
);
828 /* No need to wrap a single integer. */
832 case NON_LVALUE_EXPR
:
833 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
841 type
= TREE_TYPE (e
);
842 if (TYPE_UNSIGNED (type
))
843 res
= wrap (res
, TYPE_PRECISION (type
));
848 /* In the context of sese S, scan the expression E and translate it to
849 a linear expression C. When parsing a symbolic multiplication, K
850 represents the constant multiplier of an expression containing
854 scan_tree_for_params (sese s
, tree e
)
856 if (e
== chrec_dont_know
)
859 switch (TREE_CODE (e
))
861 case POLYNOMIAL_CHREC
:
862 scan_tree_for_params (s
, CHREC_LEFT (e
));
866 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
867 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
869 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
873 case POINTER_PLUS_EXPR
:
875 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
876 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
882 case NON_LVALUE_EXPR
:
883 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
887 parameter_index_in_region (e
, s
);
900 /* Find parameters with respect to REGION in BB. We are looking in memory
901 access functions, conditions and loop bounds. */
904 find_params_in_bb (sese region
, gimple_bb_p gbb
)
910 loop_p loop
= GBB_BB (gbb
)->loop_father
;
912 /* Find parameters in the access functions of data references. */
913 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
914 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
915 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
917 /* Find parameters in conditional statements. */
918 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
920 tree lhs
= scalar_evolution_in_region (region
, loop
,
921 gimple_cond_lhs (stmt
));
922 tree rhs
= scalar_evolution_in_region (region
, loop
,
923 gimple_cond_rhs (stmt
));
925 scan_tree_for_params (region
, lhs
);
926 scan_tree_for_params (region
, rhs
);
930 /* Record the parameters used in the SCOP. A variable is a parameter
931 in a scop if it does not vary during the execution of that scop. */
934 find_scop_parameters (scop_p scop
)
938 sese region
= SCOP_REGION (scop
);
942 /* Find the parameters used in the loop bounds. */
943 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
945 tree nb_iters
= number_of_latch_executions (loop
);
947 if (!chrec_contains_symbols (nb_iters
))
950 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
951 scan_tree_for_params (region
, nb_iters
);
954 /* Find the parameters used in data accesses. */
955 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
956 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
958 nbp
= sese_nb_params (region
);
959 scop_set_nb_params (scop
, nbp
);
960 SESE_ADD_PARAMS (region
) = false;
964 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
966 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
967 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
968 isl_id_for_ssa_name (scop
, e
));
970 scop
->context
= isl_set_universe (space
);
974 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
975 the constraints for the surrounding loops. */
978 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
980 isl_set
*outer
, isl_set
**doms
)
982 tree nb_iters
= number_of_latch_executions (loop
);
983 sese region
= SCOP_REGION (scop
);
985 isl_set
*inner
= isl_set_copy (outer
);
988 int pos
= isl_set_dim (outer
, isl_dim_set
);
995 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
996 space
= isl_set_get_space (inner
);
999 c
= isl_inequality_alloc
1000 (isl_local_space_from_space (isl_space_copy (space
)));
1001 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1002 inner
= isl_set_add_constraint (inner
, c
);
1004 /* loop_i <= cst_nb_iters */
1005 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1007 c
= isl_inequality_alloc
1008 (isl_local_space_from_space (isl_space_copy (space
)));
1009 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1010 tree_int_to_gmp (nb_iters
, g
);
1011 isl_int_set_gmp (v
, g
);
1012 c
= isl_constraint_set_constant (c
, v
);
1013 inner
= isl_set_add_constraint (inner
, c
);
1016 /* loop_i <= expr_nb_iters */
1017 else if (!chrec_contains_undetermined (nb_iters
))
1022 isl_local_space
*ls
;
1026 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1028 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1029 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1030 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1031 isl_set_dim (valid
, isl_dim_set
));
1032 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1034 ls
= isl_local_space_from_space (isl_space_copy (space
));
1035 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1036 isl_dim_in
, pos
, 1);
1037 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1038 isl_pw_aff_copy (aff
));
1039 inner
= isl_set_intersect (inner
, le
);
1041 if (max_stmt_executions (loop
, &nit
))
1043 /* Insert in the context the constraints from the
1044 estimation of the number of iterations NIT and the
1045 symbolic number of iterations (involving parameter
1046 names) NB_ITERS. First, build the affine expression
1047 "NIT - NB_ITERS" and then say that it is positive,
1048 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1055 mpz_set_double_int (g
, nit
, false);
1056 mpz_sub_ui (g
, g
, 1);
1057 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1058 x
= isl_pw_aff_ge_set (approx
, aff
);
1059 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1060 isl_set_dim (x
, isl_dim_set
));
1061 scop
->context
= isl_set_intersect (scop
->context
, x
);
1063 c
= isl_inequality_alloc
1064 (isl_local_space_from_space (isl_space_copy (space
)));
1065 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1066 isl_int_set_gmp (v
, g
);
1068 c
= isl_constraint_set_constant (c
, v
);
1069 inner
= isl_set_add_constraint (inner
, c
);
1072 isl_pw_aff_free (aff
);
1077 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1078 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1079 isl_set_copy (inner
), doms
);
1083 && loop_in_sese_p (loop
->next
, region
))
1084 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1085 isl_set_copy (outer
), doms
);
1087 doms
[loop
->num
] = inner
;
1089 isl_set_free (outer
);
1090 isl_space_free (space
);
1095 /* Returns a linear expression for tree T evaluated in PBB. */
1098 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1100 scop_p scop
= PBB_SCOP (pbb
);
1102 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1103 gcc_assert (!automatically_generated_chrec_p (t
));
1105 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1108 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1109 operator. This allows us to invert the condition or to handle
1113 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1115 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1116 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1122 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1126 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1130 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1134 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1138 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1142 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1146 isl_pw_aff_free (lhs
);
1147 isl_pw_aff_free (rhs
);
1151 cond
= isl_set_coalesce (cond
);
1152 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1153 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1156 /* Add conditions to the domain of PBB. */
1159 add_conditions_to_domain (poly_bb_p pbb
)
1163 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1165 if (GBB_CONDITIONS (gbb
).is_empty ())
1168 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1169 switch (gimple_code (stmt
))
1173 enum tree_code code
= gimple_cond_code (stmt
);
1175 /* The conditions for ELSE-branches are inverted. */
1176 if (!GBB_CONDITION_CASES (gbb
)[i
])
1177 code
= invert_tree_comparison (code
, false);
1179 add_condition_to_pbb (pbb
, stmt
, code
);
1184 /* Switch statements are not supported right now - fall through. */
1192 /* Traverses all the GBBs of the SCOP and add their constraints to the
1193 iteration domains. */
1196 add_conditions_to_constraints (scop_p scop
)
1201 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1202 add_conditions_to_domain (pbb
);
1205 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1206 edge between BB and its predecessor is not a loop exit edge, and
1207 the last statement of the single predecessor is a COND_EXPR. */
1210 single_pred_cond_non_loop_exit (basic_block bb
)
1212 if (single_pred_p (bb
))
1214 edge e
= single_pred_edge (bb
);
1215 basic_block pred
= e
->src
;
1218 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1221 stmt
= last_stmt (pred
);
1223 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1230 class sese_dom_walker
: public dom_walker
1233 sese_dom_walker (cdi_direction
, sese
);
1235 virtual void before_dom_children (basic_block
);
1236 virtual void after_dom_children (basic_block
);
1239 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1243 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1244 : dom_walker (direction
), m_region (region
)
1248 /* Call-back for dom_walk executed before visiting the dominated
1252 sese_dom_walker::before_dom_children (basic_block bb
)
1257 if (!bb_in_sese_p (bb
, m_region
))
1260 stmt
= single_pred_cond_non_loop_exit (bb
);
1264 edge e
= single_pred_edge (bb
);
1266 m_conditions
.safe_push (stmt
);
1268 if (e
->flags
& EDGE_TRUE_VALUE
)
1269 m_cases
.safe_push (stmt
);
1271 m_cases
.safe_push (NULL
);
1274 gbb
= gbb_from_bb (bb
);
1278 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1279 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1283 /* Call-back for dom_walk executed after visiting the dominated
1287 sese_dom_walker::after_dom_children (basic_block bb
)
1289 if (!bb_in_sese_p (bb
, m_region
))
1292 if (single_pred_cond_non_loop_exit (bb
))
1294 m_conditions
.pop ();
1299 /* Add constraints on the possible values of parameter P from the type
1303 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1305 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1306 tree type
= TREE_TYPE (parameter
);
1307 tree lb
= NULL_TREE
;
1308 tree ub
= NULL_TREE
;
1310 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1311 lb
= lower_bound_in_type (type
, type
);
1313 lb
= TYPE_MIN_VALUE (type
);
1315 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1316 ub
= upper_bound_in_type (type
, type
);
1318 ub
= TYPE_MAX_VALUE (type
);
1322 isl_space
*space
= isl_set_get_space (scop
->context
);
1327 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1330 tree_int_to_gmp (lb
, g
);
1331 isl_int_set_gmp (v
, g
);
1334 c
= isl_constraint_set_constant (c
, v
);
1336 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1338 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1343 isl_space
*space
= isl_set_get_space (scop
->context
);
1348 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1352 tree_int_to_gmp (ub
, g
);
1353 isl_int_set_gmp (v
, g
);
1355 c
= isl_constraint_set_constant (c
, v
);
1357 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1359 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1363 /* Build the context of the SCOP. The context usually contains extra
1364 constraints that are added to the iteration domains that constrain
1368 build_scop_context (scop_p scop
)
1370 graphite_dim_t p
, n
= scop_nb_params (scop
);
1372 for (p
= 0; p
< n
; p
++)
1373 add_param_constraints (scop
, p
);
1376 /* Build the iteration domains: the loops belonging to the current
1377 SCOP, and that vary for the execution of the current basic block.
1378 Returns false if there is no loop in SCOP. */
1381 build_scop_iteration_domain (scop_p scop
)
1384 sese region
= SCOP_REGION (scop
);
1387 int nb_loops
= number_of_loops (cfun
);
1388 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1390 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1391 if (!loop_in_sese_p (loop_outer (loop
), region
))
1392 build_loop_iteration_domains (scop
, loop
, 0,
1393 isl_set_copy (scop
->context
), doms
);
1395 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1397 loop
= pbb_loop (pbb
);
1399 if (doms
[loop
->num
])
1400 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1402 pbb
->domain
= isl_set_copy (scop
->context
);
1404 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1405 isl_id_for_pbb (scop
, pbb
));
1408 for (i
= 0; i
< nb_loops
; i
++)
1410 isl_set_free (doms
[i
]);
1415 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1416 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1417 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1421 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1424 int alias_set_num
= 0;
1425 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1427 if (bap
&& bap
->alias_set
)
1428 alias_set_num
= *(bap
->alias_set
);
1430 c
= isl_equality_alloc
1431 (isl_local_space_from_space (isl_map_get_space (acc
)));
1432 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1433 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1435 return isl_map_add_constraint (acc
, c
);
1438 /* Assign the affine expression INDEX to the output dimension POS of
1439 MAP and return the result. */
1442 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1445 int len
= isl_map_dim (map
, isl_dim_out
);
1448 index_map
= isl_map_from_pw_aff (index
);
1449 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1450 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1452 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1453 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1454 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1455 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1457 return isl_map_intersect (map
, index_map
);
1460 /* Add to ACCESSES polyhedron equalities defining the access functions
1461 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1462 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1463 PBB is the poly_bb_p that contains the data reference DR. */
1466 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1468 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1469 scop_p scop
= PBB_SCOP (pbb
);
1471 for (i
= 0; i
< nb_subscripts
; i
++)
1474 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1476 aff
= extract_affine (scop
, afn
,
1477 isl_space_domain (isl_map_get_space (acc
)));
1478 acc
= set_index (acc
, i
+ 1, aff
);
1484 /* Add constrains representing the size of the accessed data to the
1485 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1486 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1490 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1492 tree ref
= DR_REF (dr
);
1493 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1495 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1499 if (TREE_CODE (ref
) != ARRAY_REF
)
1502 low
= array_ref_low_bound (ref
);
1503 high
= array_ref_up_bound (ref
);
1505 /* XXX The PPL code dealt separately with
1506 subscript - low >= 0 and high - subscript >= 0 in case one of
1507 the two bounds isn't known. Do the same here? */
1509 if (host_integerp (low
, 0)
1511 && host_integerp (high
, 0)
1512 /* 1-element arrays at end of structures may extend over
1513 their declared size. */
1514 && !(array_at_struct_end_p (ref
)
1515 && operand_equal_p (low
, high
, 0)))
1519 isl_set
*univ
, *lbs
, *ubs
;
1523 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1524 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1527 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1528 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1529 isl_set_dim (valid
, isl_dim_set
));
1530 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1532 space
= isl_set_get_space (extent
);
1533 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1534 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1535 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1536 index
= isl_pw_aff_alloc (univ
, aff
);
1538 id
= isl_set_get_tuple_id (extent
);
1539 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1540 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1542 /* low <= sub_i <= high */
1543 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1544 ubs
= isl_pw_aff_le_set (index
, ub
);
1545 extent
= isl_set_intersect (extent
, lbs
);
1546 extent
= isl_set_intersect (extent
, ubs
);
1553 /* Build data accesses for DR in PBB. */
1556 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1558 int dr_base_object_set
;
1561 scop_p scop
= PBB_SCOP (pbb
);
1564 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1565 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1566 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1567 isl_dim_out
, nb_out
);
1569 acc
= isl_map_universe (space
);
1570 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1573 acc
= pdr_add_alias_set (acc
, dr
);
1574 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1577 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1578 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1579 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1580 int alias_set_num
= 0;
1581 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1583 if (bap
&& bap
->alias_set
)
1584 alias_set_num
= *(bap
->alias_set
);
1586 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1587 extent
= isl_set_nat_universe (space
);
1588 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1589 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1592 gcc_assert (dr
->aux
);
1593 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1595 new_poly_dr (pbb
, dr_base_object_set
,
1596 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1597 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1600 /* Write to FILE the alias graph of data references in DIMACS format. */
1603 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1604 vec
<data_reference_p
> drs
)
1606 int num_vertex
= drs
.length ();
1608 data_reference_p dr1
, dr2
;
1611 if (num_vertex
== 0)
1614 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1615 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1616 if (dr_may_alias_p (dr1
, dr2
, true))
1619 fprintf (file
, "$\n");
1622 fprintf (file
, "c %s\n", comment
);
1624 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1626 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1627 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1628 if (dr_may_alias_p (dr1
, dr2
, true))
1629 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1634 /* Write to FILE the alias graph of data references in DOT format. */
1637 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1638 vec
<data_reference_p
> drs
)
1640 int num_vertex
= drs
.length ();
1641 data_reference_p dr1
, dr2
;
1644 if (num_vertex
== 0)
1647 fprintf (file
, "$\n");
1650 fprintf (file
, "c %s\n", comment
);
1652 /* First print all the vertices. */
1653 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1654 fprintf (file
, "n%d;\n", i
);
1656 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1657 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1658 if (dr_may_alias_p (dr1
, dr2
, true))
1659 fprintf (file
, "n%d n%d\n", i
, j
);
1664 /* Write to FILE the alias graph of data references in ECC format. */
1667 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1668 vec
<data_reference_p
> drs
)
1670 int num_vertex
= drs
.length ();
1671 data_reference_p dr1
, dr2
;
1674 if (num_vertex
== 0)
1677 fprintf (file
, "$\n");
1680 fprintf (file
, "c %s\n", comment
);
1682 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1683 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1684 if (dr_may_alias_p (dr1
, dr2
, true))
1685 fprintf (file
, "%d %d\n", i
, j
);
1690 /* Check if DR1 and DR2 are in the same object set. */
1693 dr_same_base_object_p (const struct data_reference
*dr1
,
1694 const struct data_reference
*dr2
)
1696 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1699 /* Uses DFS component number as representative of alias-sets. Also tests for
1700 optimality by verifying if every connected component is a clique. Returns
1701 true (1) if the above test is true, and false (0) otherwise. */
1704 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1706 int num_vertices
= drs
.length ();
1707 struct graph
*g
= new_graph (num_vertices
);
1708 data_reference_p dr1
, dr2
;
1710 int num_connected_components
;
1711 int v_indx1
, v_indx2
, num_vertices_in_component
;
1714 struct graph_edge
*e
;
1715 int this_component_is_clique
;
1716 int all_components_are_cliques
= 1;
1718 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1719 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1720 if (dr_may_alias_p (dr1
, dr2
, true))
1726 all_vertices
= XNEWVEC (int, num_vertices
);
1727 vertices
= XNEWVEC (int, num_vertices
);
1728 for (i
= 0; i
< num_vertices
; i
++)
1729 all_vertices
[i
] = i
;
1731 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1733 for (i
= 0; i
< g
->n_vertices
; i
++)
1735 data_reference_p dr
= drs
[i
];
1736 base_alias_pair
*bap
;
1738 gcc_assert (dr
->aux
);
1739 bap
= (base_alias_pair
*)(dr
->aux
);
1741 bap
->alias_set
= XNEW (int);
1742 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1745 /* Verify if the DFS numbering results in optimal solution. */
1746 for (i
= 0; i
< num_connected_components
; i
++)
1748 num_vertices_in_component
= 0;
1749 /* Get all vertices whose DFS component number is the same as i. */
1750 for (j
= 0; j
< num_vertices
; j
++)
1751 if (g
->vertices
[j
].component
== i
)
1752 vertices
[num_vertices_in_component
++] = j
;
1754 /* Now test if the vertices in 'vertices' form a clique, by testing
1755 for edges among each pair. */
1756 this_component_is_clique
= 1;
1757 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1759 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1761 /* Check if the two vertices are connected by iterating
1762 through all the edges which have one of these are source. */
1763 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1766 if (e
->src
== vertices
[v_indx1
])
1772 this_component_is_clique
= 0;
1776 if (!this_component_is_clique
)
1777 all_components_are_cliques
= 0;
1781 free (all_vertices
);
1784 return all_components_are_cliques
;
1787 /* Group each data reference in DRS with its base object set num. */
1790 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1792 int num_vertex
= drs
.length ();
1793 struct graph
*g
= new_graph (num_vertex
);
1794 data_reference_p dr1
, dr2
;
1798 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1799 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1800 if (dr_same_base_object_p (dr1
, dr2
))
1806 queue
= XNEWVEC (int, num_vertex
);
1807 for (i
= 0; i
< num_vertex
; i
++)
1810 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1812 for (i
= 0; i
< g
->n_vertices
; i
++)
1814 data_reference_p dr
= drs
[i
];
1815 base_alias_pair
*bap
;
1817 gcc_assert (dr
->aux
);
1818 bap
= (base_alias_pair
*)(dr
->aux
);
1820 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1827 /* Build the data references for PBB. */
1830 build_pbb_drs (poly_bb_p pbb
)
1833 data_reference_p dr
;
1834 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1836 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1837 build_poly_dr (dr
, pbb
);
1840 /* Dump to file the alias graphs for the data references in DRS. */
1843 dump_alias_graphs (vec
<data_reference_p
> drs
)
1846 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1848 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1851 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1852 current_function_name ());
1853 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1854 fclose (file_dimacs
);
1857 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1860 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1861 current_function_name ());
1862 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1866 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1869 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1870 current_function_name ());
1871 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1876 /* Build data references in SCOP. */
1879 build_scop_drs (scop_p scop
)
1883 data_reference_p dr
;
1884 stack_vec
<data_reference_p
, 3> drs
;
1886 /* Remove all the PBBs that do not have data references: these basic
1887 blocks are not handled in the polyhedral representation. */
1888 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1889 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1891 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1893 SCOP_BBS (scop
).ordered_remove (i
);
1897 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1898 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1901 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1902 dr
->aux
= XNEW (base_alias_pair
);
1904 if (!build_alias_set_optimal_p (drs
))
1906 /* TODO: Add support when building alias set is not optimal. */
1910 build_base_obj_set_for_drs (drs
);
1912 /* When debugging, enable the following code. This cannot be used
1913 in production compilers. */
1915 dump_alias_graphs (drs
);
1919 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1920 build_pbb_drs (pbb
);
1923 /* Return a gsi at the position of the phi node STMT. */
1925 static gimple_stmt_iterator
1926 gsi_for_phi_node (gimple stmt
)
1928 gimple_stmt_iterator psi
;
1929 basic_block bb
= gimple_bb (stmt
);
1931 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1932 if (stmt
== gsi_stmt (psi
))
1939 /* Analyze all the data references of STMTS and add them to the
1940 GBB_DATA_REFS vector of BB. */
1943 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1949 sese region
= SCOP_REGION (scop
);
1951 if (!bb_in_sese_p (bb
, region
))
1954 nest
= outermost_loop_in_sese_1 (region
, bb
);
1955 gbb
= gbb_from_bb (bb
);
1957 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1961 if (is_gimple_debug (stmt
))
1964 loop
= loop_containing_stmt (stmt
);
1965 if (!loop_in_sese_p (loop
, region
))
1968 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1969 &GBB_DATA_REFS (gbb
));
1973 /* Insert STMT at the end of the STMTS sequence and then insert the
1974 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1978 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1979 gimple_stmt_iterator insert_gsi
)
1981 gimple_stmt_iterator gsi
;
1982 stack_vec
<gimple
, 3> x
;
1984 gimple_seq_add_stmt (&stmts
, stmt
);
1985 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1986 x
.safe_push (gsi_stmt (gsi
));
1988 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1989 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1992 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1995 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
1998 gimple_stmt_iterator gsi
;
1999 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2000 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2001 stack_vec
<gimple
, 3> x
;
2003 gimple_seq_add_stmt (&stmts
, stmt
);
2004 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2005 x
.safe_push (gsi_stmt (gsi
));
2007 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2009 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2010 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2014 gsi
= gsi_for_stmt (after_stmt
);
2015 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2018 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2021 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2024 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2026 vec
<data_reference_p
> drs
;
2028 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2029 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2030 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2031 int index
, n
= SCOP_BBS (scop
).length ();
2033 /* The INDEX of PBB in SCOP_BBS. */
2034 for (index
= 0; index
< n
; index
++)
2035 if (SCOP_BBS (scop
)[index
] == pbb
)
2038 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2040 GBB_PBB (gbb1
) = pbb1
;
2041 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2042 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2043 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2046 /* Insert on edge E the assignment "RES := EXPR". */
2049 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2051 gimple_stmt_iterator gsi
;
2052 gimple_seq stmts
= NULL
;
2053 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2054 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2056 stack_vec
<gimple
, 3> x
;
2058 gimple_seq_add_stmt (&stmts
, stmt
);
2059 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2060 x
.safe_push (gsi_stmt (gsi
));
2062 gsi_insert_seq_on_edge (e
, stmts
);
2063 gsi_commit_edge_inserts ();
2064 bb
= gimple_bb (stmt
);
2066 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2069 if (!gbb_from_bb (bb
))
2070 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2072 analyze_drs_in_stmts (scop
, bb
, x
);
2075 /* Creates a zero dimension array of the same type as VAR. */
2078 create_zero_dim_array (tree var
, const char *base_name
)
2080 tree index_type
= build_index_type (integer_zero_node
);
2081 tree elt_type
= TREE_TYPE (var
);
2082 tree array_type
= build_array_type (elt_type
, index_type
);
2083 tree base
= create_tmp_var (array_type
, base_name
);
2085 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2089 /* Returns true when PHI is a loop close phi node. */
2092 scalar_close_phi_node_p (gimple phi
)
2094 if (gimple_code (phi
) != GIMPLE_PHI
2095 || virtual_operand_p (gimple_phi_result (phi
)))
2098 /* Note that loop close phi nodes should have a single argument
2099 because we translated the representation into a canonical form
2100 before Graphite: see canonicalize_loop_closed_ssa_form. */
2101 return (gimple_phi_num_args (phi
) == 1);
2104 /* For a definition DEF in REGION, propagates the expression EXPR in
2105 all the uses of DEF outside REGION. */
2108 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2110 imm_use_iterator imm_iter
;
2113 bool replaced_once
= false;
2115 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2117 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2120 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2121 if (!is_gimple_debug (use_stmt
)
2122 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2125 use_operand_p use_p
;
2127 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2128 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2129 && (replaced_once
= true))
2130 replace_exp (use_p
, expr
);
2132 update_stmt (use_stmt
);
2137 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2138 gsi_commit_edge_inserts ();
2142 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2143 dimension array for it. */
2146 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2148 sese region
= SCOP_REGION (scop
);
2149 gimple phi
= gsi_stmt (*psi
);
2150 tree res
= gimple_phi_result (phi
);
2151 basic_block bb
= gimple_bb (phi
);
2152 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2153 tree arg
= gimple_phi_arg_def (phi
, 0);
2156 /* Note that loop close phi nodes should have a single argument
2157 because we translated the representation into a canonical form
2158 before Graphite: see canonicalize_loop_closed_ssa_form. */
2159 gcc_assert (gimple_phi_num_args (phi
) == 1);
2161 /* The phi node can be a non close phi node, when its argument is
2162 invariant, or a default definition. */
2163 if (is_gimple_min_invariant (arg
)
2164 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2166 propagate_expr_outside_region (res
, arg
, region
);
2171 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2173 propagate_expr_outside_region (res
, arg
, region
);
2174 stmt
= gimple_build_assign (res
, arg
);
2175 remove_phi_node (psi
, false);
2176 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2177 SSA_NAME_DEF_STMT (res
) = stmt
;
2181 /* If res is scev analyzable and is not a scalar value, it is safe
2182 to ignore the close phi node: it will be code generated in the
2183 out of Graphite pass. */
2184 else if (scev_analyzable_p (res
, region
))
2186 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2189 if (!loop_in_sese_p (loop
, region
))
2191 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2192 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2193 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2196 scev
= scalar_evolution_in_region (region
, loop
, res
);
2198 if (tree_does_not_contain_chrecs (scev
))
2199 propagate_expr_outside_region (res
, scev
, region
);
2206 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2208 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2210 if (TREE_CODE (arg
) == SSA_NAME
)
2211 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2212 SSA_NAME_DEF_STMT (arg
));
2214 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2215 zero_dim_array
, arg
);
2218 remove_phi_node (psi
, false);
2219 SSA_NAME_DEF_STMT (res
) = stmt
;
2221 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2224 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2225 dimension array for it. */
2228 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2231 gimple phi
= gsi_stmt (*psi
);
2232 basic_block bb
= gimple_bb (phi
);
2233 tree res
= gimple_phi_result (phi
);
2234 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2237 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2239 tree arg
= gimple_phi_arg_def (phi
, i
);
2240 edge e
= gimple_phi_arg_edge (phi
, i
);
2242 /* Avoid the insertion of code in the loop latch to please the
2243 pattern matching of the vectorizer. */
2244 if (TREE_CODE (arg
) == SSA_NAME
2245 && e
->src
== bb
->loop_father
->latch
)
2246 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2247 SSA_NAME_DEF_STMT (arg
));
2249 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2252 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2253 remove_phi_node (psi
, false);
2254 SSA_NAME_DEF_STMT (res
) = stmt
;
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);
2277 SSA_NAME_DEF_STMT (res
) = stmt
;
2279 gsi
= gsi_after_labels (bb
);
2280 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2283 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2286 rewrite_reductions_out_of_ssa (scop_p scop
)
2289 gimple_stmt_iterator psi
;
2290 sese region
= SCOP_REGION (scop
);
2293 if (bb_in_sese_p (bb
, region
))
2294 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2296 gimple phi
= gsi_stmt (psi
);
2298 if (virtual_operand_p (gimple_phi_result (phi
)))
2304 if (gimple_phi_num_args (phi
) > 1
2305 && degenerate_phi_result (phi
))
2306 rewrite_degenerate_phi (&psi
);
2308 else if (scalar_close_phi_node_p (phi
))
2309 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2311 else if (reduction_phi_p (region
, &psi
))
2312 rewrite_phi_out_of_ssa (scop
, &psi
);
2315 update_ssa (TODO_update_ssa
);
2316 #ifdef ENABLE_CHECKING
2317 verify_loop_closed_ssa (true);
2321 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2322 read from ZERO_DIM_ARRAY. */
2325 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2326 tree def
, gimple use_stmt
)
2331 use_operand_p use_p
;
2333 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2335 name
= copy_ssa_name (def
, NULL
);
2336 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2338 gimple_assign_set_lhs (name_stmt
, name
);
2339 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2341 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2342 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2343 replace_exp (use_p
, name
);
2345 update_stmt (use_stmt
);
2348 /* For every definition DEF in the SCOP that is used outside the scop,
2349 insert a closing-scop definition in the basic block just after this
2353 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2355 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2356 tree new_name
= make_ssa_name (var
, stmt
);
2357 bool needs_copy
= false;
2358 use_operand_p use_p
;
2359 imm_use_iterator imm_iter
;
2361 sese region
= SCOP_REGION (scop
);
2363 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2365 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2367 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2369 SET_USE (use_p
, new_name
);
2371 update_stmt (use_stmt
);
2376 /* Insert in the empty BB just after the scop a use of DEF such
2377 that the rewrite of cross_bb_scalar_dependences won't insert
2378 arrays everywhere else. */
2381 gimple assign
= gimple_build_assign (new_name
, def
);
2382 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2384 SSA_NAME_DEF_STMT (new_name
) = assign
;
2385 update_stmt (assign
);
2386 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2390 /* Rewrite the scalar dependences crossing the boundary of the BB
2391 containing STMT with an array. Return true when something has been
2395 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2397 sese region
= SCOP_REGION (scop
);
2398 gimple stmt
= gsi_stmt (*gsi
);
2399 imm_use_iterator imm_iter
;
2402 tree zero_dim_array
= NULL_TREE
;
2406 switch (gimple_code (stmt
))
2409 def
= gimple_assign_lhs (stmt
);
2413 def
= gimple_call_lhs (stmt
);
2421 || !is_gimple_reg (def
))
2424 if (scev_analyzable_p (def
, region
))
2426 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2427 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2429 if (tree_contains_chrecs (scev
, NULL
))
2432 propagate_expr_outside_region (def
, scev
, region
);
2436 def_bb
= gimple_bb (stmt
);
2438 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2440 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2441 if (gimple_code (use_stmt
) == GIMPLE_PHI
2444 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2446 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2447 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2449 rewrite_phi_out_of_ssa (scop
, &psi
);
2452 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2453 if (gimple_code (use_stmt
) != GIMPLE_PHI
2454 && def_bb
!= gimple_bb (use_stmt
)
2455 && !is_gimple_debug (use_stmt
)
2458 if (!zero_dim_array
)
2460 zero_dim_array
= create_zero_dim_array
2461 (def
, "Cross_BB_scalar_dependence");
2462 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2463 SSA_NAME_DEF_STMT (def
));
2467 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2474 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2477 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2480 gimple_stmt_iterator psi
;
2481 sese region
= SCOP_REGION (scop
);
2482 bool changed
= false;
2484 /* Create an extra empty BB after the scop. */
2485 split_edge (SESE_EXIT (region
));
2488 if (bb_in_sese_p (bb
, region
))
2489 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2490 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2495 update_ssa (TODO_update_ssa
);
2496 #ifdef ENABLE_CHECKING
2497 verify_loop_closed_ssa (true);
2502 /* Returns the number of pbbs that are in loops contained in SCOP. */
2505 nb_pbbs_in_loops (scop_p scop
)
2511 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2512 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2518 /* Return the number of data references in BB that write in
2522 nb_data_writes_in_bb (basic_block bb
)
2525 gimple_stmt_iterator gsi
;
2527 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2528 if (gimple_vdef (gsi_stmt (gsi
)))
2534 /* Splits at STMT the basic block BB represented as PBB in the
2538 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2540 edge e1
= split_block (bb
, stmt
);
2541 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2545 /* Splits STMT out of its current BB. This is done for reduction
2546 statements for which we want to ignore data dependences. */
2549 split_reduction_stmt (scop_p scop
, gimple stmt
)
2551 basic_block bb
= gimple_bb (stmt
);
2552 poly_bb_p pbb
= pbb_from_bb (bb
);
2553 gimple_bb_p gbb
= gbb_from_bb (bb
);
2556 data_reference_p dr
;
2558 /* Do not split basic blocks with no writes to memory: the reduction
2559 will be the only write to memory. */
2560 if (nb_data_writes_in_bb (bb
) == 0
2561 /* Or if we have already marked BB as a reduction. */
2562 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2565 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2567 /* Split once more only when the reduction stmt is not the only one
2568 left in the original BB. */
2569 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2571 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2573 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2576 /* A part of the data references will end in a different basic block
2577 after the split: move the DRs from the original GBB to the newly
2579 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2581 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2585 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2586 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2587 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2595 /* Return true when stmt is a reduction operation. */
2598 is_reduction_operation_p (gimple stmt
)
2600 enum tree_code code
;
2602 gcc_assert (is_gimple_assign (stmt
));
2603 code
= gimple_assign_rhs_code (stmt
);
2605 return flag_associative_math
2606 && commutative_tree_code (code
)
2607 && associative_tree_code (code
);
2610 /* Returns true when PHI contains an argument ARG. */
2613 phi_contains_arg (gimple phi
, tree arg
)
2617 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2618 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2624 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2627 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2631 if (TREE_CODE (arg
) != SSA_NAME
)
2634 stmt
= SSA_NAME_DEF_STMT (arg
);
2636 if (gimple_code (stmt
) == GIMPLE_NOP
2637 || gimple_code (stmt
) == GIMPLE_CALL
)
2640 if (gimple_code (stmt
) == GIMPLE_PHI
)
2642 if (phi_contains_arg (stmt
, lhs
))
2647 if (!is_gimple_assign (stmt
))
2650 if (gimple_num_ops (stmt
) == 2)
2651 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2653 if (is_reduction_operation_p (stmt
))
2655 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2658 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2664 /* Detect commutative and associative scalar reductions starting at
2665 the STMT. Return the phi node of the reduction cycle, or NULL. */
2668 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2672 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2677 in
->safe_push (stmt
);
2678 out
->safe_push (stmt
);
2682 /* Detect commutative and associative scalar reductions starting at
2683 STMT. Return the phi node of the reduction cycle, or NULL. */
2686 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2689 tree lhs
= gimple_assign_lhs (stmt
);
2691 if (gimple_num_ops (stmt
) == 2)
2692 return detect_commutative_reduction_arg (lhs
, stmt
,
2693 gimple_assign_rhs1 (stmt
),
2696 if (is_reduction_operation_p (stmt
))
2698 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2699 gimple_assign_rhs1 (stmt
),
2702 : detect_commutative_reduction_arg (lhs
, stmt
,
2703 gimple_assign_rhs2 (stmt
),
2710 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2713 follow_inital_value_to_phi (tree arg
, tree lhs
)
2717 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2720 stmt
= SSA_NAME_DEF_STMT (arg
);
2722 if (gimple_code (stmt
) == GIMPLE_PHI
2723 && phi_contains_arg (stmt
, lhs
))
2730 /* Return the argument of the loop PHI that is the initial value coming
2731 from outside the loop. */
2734 edge_initial_value_for_loop_phi (gimple phi
)
2738 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2740 edge e
= gimple_phi_arg_edge (phi
, i
);
2742 if (loop_depth (e
->src
->loop_father
)
2743 < loop_depth (e
->dest
->loop_father
))
2750 /* Return the argument of the loop PHI that is the initial value coming
2751 from outside the loop. */
2754 initial_value_for_loop_phi (gimple phi
)
2758 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2760 edge e
= gimple_phi_arg_edge (phi
, i
);
2762 if (loop_depth (e
->src
->loop_father
)
2763 < loop_depth (e
->dest
->loop_father
))
2764 return gimple_phi_arg_def (phi
, i
);
2770 /* Returns true when DEF is used outside the reduction cycle of
2774 used_outside_reduction (tree def
, gimple loop_phi
)
2776 use_operand_p use_p
;
2777 imm_use_iterator imm_iter
;
2778 loop_p loop
= loop_containing_stmt (loop_phi
);
2780 /* In LOOP, DEF should be used only in LOOP_PHI. */
2781 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2783 gimple stmt
= USE_STMT (use_p
);
2785 if (stmt
!= loop_phi
2786 && !is_gimple_debug (stmt
)
2787 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2794 /* Detect commutative and associative scalar reductions belonging to
2795 the SCOP starting at the loop closed phi node STMT. Return the phi
2796 node of the reduction cycle, or NULL. */
2799 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2802 if (scalar_close_phi_node_p (stmt
))
2804 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2805 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2807 if (TREE_CODE (arg
) != SSA_NAME
)
2810 /* Note that loop close phi nodes should have a single argument
2811 because we translated the representation into a canonical form
2812 before Graphite: see canonicalize_loop_closed_ssa_form. */
2813 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2815 def
= SSA_NAME_DEF_STMT (arg
);
2816 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2817 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2820 lhs
= gimple_phi_result (close_phi
);
2821 init
= initial_value_for_loop_phi (loop_phi
);
2822 phi
= follow_inital_value_to_phi (init
, lhs
);
2824 if (phi
&& (used_outside_reduction (lhs
, phi
)
2825 || !has_single_use (gimple_phi_result (phi
))))
2828 in
->safe_push (loop_phi
);
2829 out
->safe_push (close_phi
);
2833 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2834 return detect_commutative_reduction_assign (stmt
, in
, out
);
2839 /* Translate the scalar reduction statement STMT to an array RED
2840 knowing that its recursive phi node is LOOP_PHI. */
2843 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2844 gimple stmt
, gimple loop_phi
)
2846 tree res
= gimple_phi_result (loop_phi
);
2847 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2848 gimple_stmt_iterator gsi
;
2850 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2852 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2853 gsi
= gsi_for_stmt (stmt
);
2855 insert_stmts (scop
, assign
, NULL
, gsi
);
2858 /* Removes the PHI node and resets all the debug stmts that are using
2862 remove_phi (gimple phi
)
2864 imm_use_iterator imm_iter
;
2866 use_operand_p use_p
;
2867 gimple_stmt_iterator gsi
;
2868 stack_vec
<gimple
, 3> update
;
2872 def
= PHI_RESULT (phi
);
2873 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2875 stmt
= USE_STMT (use_p
);
2877 if (is_gimple_debug (stmt
))
2879 gimple_debug_bind_reset_value (stmt
);
2880 update
.safe_push (stmt
);
2884 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2887 gsi
= gsi_for_phi_node (phi
);
2888 remove_phi_node (&gsi
, false);
2891 /* Helper function for for_each_index. For each INDEX of the data
2892 reference REF, returns true when its indices are valid in the loop
2893 nest LOOP passed in as DATA. */
2896 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2899 basic_block header
, def_bb
;
2902 if (TREE_CODE (*index
) != SSA_NAME
)
2905 loop
= *((loop_p
*) data
);
2906 header
= loop
->header
;
2907 stmt
= SSA_NAME_DEF_STMT (*index
);
2912 def_bb
= gimple_bb (stmt
);
2917 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2920 /* When the result of a CLOSE_PHI is written to a memory location,
2921 return a pointer to that memory reference, otherwise return
2925 close_phi_written_to_memory (gimple close_phi
)
2927 imm_use_iterator imm_iter
;
2928 use_operand_p use_p
;
2930 tree res
, def
= gimple_phi_result (close_phi
);
2932 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2933 if ((stmt
= USE_STMT (use_p
))
2934 && gimple_code (stmt
) == GIMPLE_ASSIGN
2935 && (res
= gimple_assign_lhs (stmt
)))
2937 switch (TREE_CODE (res
))
2947 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2948 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2950 /* FIXME: this restriction is for id-{24,25}.f and
2951 could be handled by duplicating the computation of
2952 array indices before the loop of the close_phi. */
2953 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2965 /* Rewrite out of SSA the reduction described by the loop phi nodes
2966 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2969 IN: stmt, loop_n, ..., loop_0
2970 OUT: stmt, close_n, ..., close_0
2972 the first element is the reduction statement, and the next elements
2973 are the loop and close phi nodes of each of the outer loops. */
2976 translate_scalar_reduction_to_array (scop_p scop
,
2981 unsigned int i
= out
.length () - 1;
2982 tree red
= close_phi_written_to_memory (out
[i
]);
2984 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2986 gimple close_phi
= out
[i
];
2990 gimple stmt
= loop_phi
;
2991 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2992 poly_bb_p pbb
= pbb_from_bb (bb
);
2993 PBB_IS_REDUCTION (pbb
) = true;
2994 gcc_assert (close_phi
== loop_phi
);
2997 red
= create_zero_dim_array
2998 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3000 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3004 if (i
== in
.length () - 1)
3006 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3007 unshare_expr (red
), close_phi
);
3008 insert_out_of_ssa_copy_on_edge
3009 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3010 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3013 remove_phi (loop_phi
);
3014 remove_phi (close_phi
);
3018 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3019 true when something has been changed. */
3022 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3026 stack_vec
<gimple
, 10> in
;
3027 stack_vec
<gimple
, 10> out
;
3029 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3030 res
= in
.length () > 1;
3032 translate_scalar_reduction_to_array (scop
, in
, out
);
3037 /* Rewrites all the commutative reductions from LOOP out of SSA.
3038 Returns true when something has been changed. */
3041 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3044 gimple_stmt_iterator gsi
;
3045 edge exit
= single_exit (loop
);
3047 bool changed
= false;
3052 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3053 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3054 && !virtual_operand_p (res
)
3055 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3056 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3057 (scop
, gsi_stmt (gsi
));
3062 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3065 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3069 bool changed
= false;
3070 sese region
= SCOP_REGION (scop
);
3072 FOR_EACH_LOOP (li
, 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
)
3096 gimple_stmt_iterator psi
;
3099 FOR_EACH_LOOP (li
, loop
, 0)
3101 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3104 for (psi
= gsi_start_phis (loop
->header
);
3105 !gsi_end_p (psi
); gsi_next (&psi
))
3107 gimple phi
= gsi_stmt (psi
);
3108 tree res
= PHI_RESULT (phi
);
3109 tree type
= TREE_TYPE (res
);
3111 if (TYPE_UNSIGNED (type
)
3112 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3119 FOR_EACH_LOOP_BREAK (li
);
3125 /* Builds the polyhedral representation for a SESE region. */
3128 build_poly_scop (scop_p scop
)
3130 sese region
= SCOP_REGION (scop
);
3131 graphite_dim_t max_dim
;
3133 build_scop_bbs (scop
);
3135 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3136 Once CLooG is fixed, remove this guard. Anyways, it makes no
3137 sense to optimize a scop containing only PBBs that do not belong
3139 if (nb_pbbs_in_loops (scop
) == 0)
3142 if (!scop_ivs_can_be_represented (scop
))
3145 if (flag_associative_math
)
3146 rewrite_commutative_reductions_out_of_ssa (scop
);
3148 build_sese_loop_nests (region
);
3149 /* Record all conditions in REGION. */
3150 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3151 find_scop_parameters (scop
);
3153 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3154 if (scop_nb_params (scop
) > max_dim
)
3157 build_scop_iteration_domain (scop
);
3158 build_scop_context (scop
);
3159 add_conditions_to_constraints (scop
);
3161 /* Rewrite out of SSA only after having translated the
3162 representation to the polyhedral representation to avoid scev
3163 analysis failures. That means that these functions will insert
3164 new data references that they create in the right place. */
3165 rewrite_reductions_out_of_ssa (scop
);
3166 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3168 build_scop_drs (scop
);
3170 build_scop_scattering (scop
);
3172 /* This SCoP has been translated to the polyhedral
3174 POLY_SCOP_P (scop
) = true;