1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
26 #include <isl/union_map.h>
27 #include <isl/constraint.h>
29 #include <cloog/cloog.h>
30 #include <cloog/cloog.h>
31 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
38 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
41 #include "gimple-ssa.h"
43 #include "tree-phinodes.h"
44 #include "ssa-iterators.h"
45 #include "stringpool.h"
46 #include "tree-ssanames.h"
47 #include "tree-ssa-loop-manip.h"
48 #include "tree-ssa-loop-niter.h"
49 #include "tree-ssa-loop.h"
50 #include "tree-into-ssa.h"
51 #include "tree-pass.h"
53 #include "tree-chrec.h"
54 #include "tree-data-ref.h"
55 #include "tree-scalar-evolution.h"
58 #include "tree-ssa-propagate.h"
62 #include "graphite-poly.h"
63 #include "graphite-sese-to-poly.h"
66 /* Assigns to RES the value of the INTEGER_CST T. */
69 tree_int_to_gmp (tree t
, mpz_t res
)
71 double_int di
= tree_to_double_int (t
);
72 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
75 /* Returns the index of the PHI argument defined in the outermost
79 phi_arg_in_outermost_loop (gimple phi
)
81 loop_p loop
= gimple_bb (phi
)->loop_father
;
84 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
85 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
87 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
94 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
95 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
98 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
100 gimple phi
= gsi_stmt (*psi
);
101 tree res
= gimple_phi_result (phi
);
102 size_t entry
= phi_arg_in_outermost_loop (phi
);
103 tree init
= gimple_phi_arg_def (phi
, entry
);
104 gimple stmt
= gimple_build_assign (res
, init
);
105 edge e
= gimple_phi_arg_edge (phi
, entry
);
107 remove_phi_node (psi
, false);
108 gsi_insert_on_edge_immediate (e
, stmt
);
111 /* Removes an invariant phi node at position PSI by inserting on the
112 loop ENTRY edge the assignment RES = INIT. */
115 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
117 gimple phi
= gsi_stmt (*psi
);
118 loop_p loop
= loop_containing_stmt (phi
);
119 tree res
= gimple_phi_result (phi
);
120 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
121 size_t entry
= phi_arg_in_outermost_loop (phi
);
122 edge e
= gimple_phi_arg_edge (phi
, entry
);
125 gimple_seq stmts
= NULL
;
127 if (tree_contains_chrecs (scev
, NULL
))
128 scev
= gimple_phi_arg_def (phi
, entry
);
130 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
131 stmt
= gimple_build_assign (res
, var
);
132 remove_phi_node (psi
, false);
134 gimple_seq_add_stmt (&stmts
, stmt
);
135 gsi_insert_seq_on_edge (e
, stmts
);
136 gsi_commit_edge_inserts ();
137 SSA_NAME_DEF_STMT (res
) = stmt
;
140 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
143 simple_copy_phi_p (gimple phi
)
147 if (gimple_phi_num_args (phi
) != 2)
150 res
= gimple_phi_result (phi
);
151 return (res
== gimple_phi_arg_def (phi
, 0)
152 || res
== gimple_phi_arg_def (phi
, 1));
155 /* Returns true when the phi node at position PSI is a reduction phi
156 node in REGION. Otherwise moves the pointer PSI to the next phi to
160 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
163 gimple phi
= gsi_stmt (*psi
);
164 tree res
= gimple_phi_result (phi
);
166 loop
= loop_containing_stmt (phi
);
168 if (simple_copy_phi_p (phi
))
170 /* PRE introduces phi nodes like these, for an example,
171 see id-5.f in the fortran graphite testsuite:
173 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
175 remove_simple_copy_phi (psi
);
179 if (scev_analyzable_p (res
, region
))
181 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
183 if (evolution_function_is_invariant_p (scev
, loop
->num
))
184 remove_invariant_phi (region
, psi
);
191 /* All the other cases are considered reductions. */
195 /* Store the GRAPHITE representation of BB. */
198 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
200 struct gimple_bb
*gbb
;
202 gbb
= XNEW (struct gimple_bb
);
205 GBB_DATA_REFS (gbb
) = drs
;
206 GBB_CONDITIONS (gbb
).create (0);
207 GBB_CONDITION_CASES (gbb
).create (0);
213 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
216 struct data_reference
*dr
;
218 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
221 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
223 free (bap
->alias_set
);
232 free_gimple_bb (struct gimple_bb
*gbb
)
234 free_data_refs_aux (GBB_DATA_REFS (gbb
));
235 free_data_refs (GBB_DATA_REFS (gbb
));
237 GBB_CONDITIONS (gbb
).release ();
238 GBB_CONDITION_CASES (gbb
).release ();
239 GBB_BB (gbb
)->aux
= 0;
243 /* Deletes all gimple bbs in SCOP. */
246 remove_gbbs_in_scop (scop_p scop
)
251 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
252 free_gimple_bb (PBB_BLACK_BOX (pbb
));
255 /* Deletes all scops in SCOPS. */
258 free_scops (vec
<scop_p
> scops
)
263 FOR_EACH_VEC_ELT (scops
, i
, scop
)
265 remove_gbbs_in_scop (scop
);
266 free_sese (SCOP_REGION (scop
));
273 /* Same as outermost_loop_in_sese, returns the outermost loop
274 containing BB in REGION, but makes sure that the returned loop
275 belongs to the REGION, and so this returns the first loop in the
276 REGION when the loop containing BB does not belong to REGION. */
279 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
281 loop_p nest
= outermost_loop_in_sese (region
, bb
);
283 if (loop_in_sese_p (nest
, region
))
286 /* When the basic block BB does not belong to a loop in the region,
287 return the first loop in the region. */
290 if (loop_in_sese_p (nest
, region
))
299 /* Generates a polyhedral black box only if the bb contains interesting
303 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
305 vec
<data_reference_p
> drs
;
307 sese region
= SCOP_REGION (scop
);
308 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
309 gimple_stmt_iterator gsi
;
311 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
313 gimple stmt
= gsi_stmt (gsi
);
316 if (is_gimple_debug (stmt
))
319 loop
= loop_containing_stmt (stmt
);
320 if (!loop_in_sese_p (loop
, region
))
323 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
326 return new_gimple_bb (bb
, drs
);
329 /* Returns true if all predecessors of BB, that are not dominated by BB, are
330 marked in MAP. The predecessors dominated by BB are loop latches and will
331 be handled after BB. */
334 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
339 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
340 if (!bitmap_bit_p (map
, e
->src
->index
)
341 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
347 /* Compare the depth of two basic_block's P1 and P2. */
350 compare_bb_depths (const void *p1
, const void *p2
)
352 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
353 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
354 int d1
= loop_depth (bb1
->loop_father
);
355 int d2
= loop_depth (bb2
->loop_father
);
366 /* Sort the basic blocks from DOM such that the first are the ones at
367 a deepest loop level. */
370 graphite_sort_dominated_info (vec
<basic_block
> dom
)
372 dom
.qsort (compare_bb_depths
);
375 /* Recursive helper function for build_scops_bbs. */
378 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
380 sese region
= SCOP_REGION (scop
);
381 vec
<basic_block
> dom
;
384 if (bitmap_bit_p (visited
, bb
->index
)
385 || !bb_in_sese_p (bb
, region
))
388 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
389 SCOP_BBS (scop
).safe_push (pbb
);
390 bitmap_set_bit (visited
, bb
->index
);
392 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
397 graphite_sort_dominated_info (dom
);
399 while (!dom
.is_empty ())
404 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
405 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
407 build_scop_bbs_1 (scop
, visited
, dom_bb
);
408 dom
.unordered_remove (i
);
416 /* Gather the basic blocks belonging to the SCOP. */
419 build_scop_bbs (scop_p scop
)
421 sbitmap visited
= sbitmap_alloc (last_basic_block
);
422 sese region
= SCOP_REGION (scop
);
424 bitmap_clear (visited
);
425 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
426 sbitmap_free (visited
);
429 /* Return an ISL identifier for the polyhedral basic block PBB. */
432 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
435 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
436 return isl_id_alloc (s
->ctx
, name
, pbb
);
439 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
440 We generate SCATTERING_DIMENSIONS scattering dimensions.
442 CLooG 0.15.0 and previous versions require, that all
443 scattering functions of one CloogProgram have the same number of
444 scattering dimensions, therefore we allow to specify it. This
445 should be removed in future versions of CLooG.
447 The scattering polyhedron consists of these dimensions: scattering,
448 loop_iterators, parameters.
452 | scattering_dimensions = 5
453 | used_scattering_dimensions = 3
461 | Scattering polyhedron:
463 | scattering: {s1, s2, s3, s4, s5}
464 | loop_iterators: {i}
465 | parameters: {p1, p2}
467 | s1 s2 s3 s4 s5 i p1 p2 1
468 | 1 0 0 0 0 0 0 0 -4 = 0
469 | 0 1 0 0 0 -1 0 0 0 = 0
470 | 0 0 1 0 0 0 0 0 -5 = 0 */
473 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
474 poly_bb_p pbb
, int scattering_dimensions
)
477 int nb_iterators
= pbb_dim_iter_domain (pbb
);
478 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
482 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
486 dc
= isl_set_get_space (pbb
->domain
);
487 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
488 isl_dim_out
, scattering_dimensions
);
489 pbb
->schedule
= isl_map_universe (dm
);
491 for (i
= 0; i
< scattering_dimensions
; i
++)
493 /* Textual order inside this loop. */
496 isl_constraint
*c
= isl_equality_alloc
497 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
499 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
503 isl_int_neg (val
, val
);
504 c
= isl_constraint_set_constant (c
, val
);
505 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
506 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
509 /* Iterations of this loop. */
510 else /* if ((i % 2) == 1) */
512 int loop
= (i
- 1) / 2;
513 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
520 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
523 /* Build for BB the static schedule.
525 The static schedule is a Dewey numbering of the abstract syntax
526 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
528 The following example informally defines the static schedule:
547 Static schedules for A to F:
560 build_scop_scattering (scop_p scop
)
564 gimple_bb_p previous_gbb
= NULL
;
565 isl_space
*dc
= isl_set_get_space (scop
->context
);
566 isl_aff
*static_sched
;
568 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
569 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
571 /* We have to start schedules at 0 on the first component and
572 because we cannot compare_prefix_loops against a previous loop,
573 prefix will be equal to zero, and that index will be
574 incremented before copying. */
575 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
577 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
579 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
581 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
584 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
590 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
592 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
595 isl_aff_free (static_sched
);
598 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
600 /* Extract an affine expression from the chain of recurrence E. */
603 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
605 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
606 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
607 isl_local_space
*ls
= isl_local_space_from_space (space
);
608 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
609 isl_aff
*loop
= isl_aff_set_coefficient_si
610 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
611 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
613 /* Before multiplying, make sure that the result is affine. */
614 gcc_assert (isl_pw_aff_is_cst (rhs
)
615 || isl_pw_aff_is_cst (l
));
617 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
620 /* Extract an affine expression from the mult_expr E. */
623 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
625 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
626 isl_space_copy (space
));
627 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
629 if (!isl_pw_aff_is_cst (lhs
)
630 && !isl_pw_aff_is_cst (rhs
))
632 isl_pw_aff_free (lhs
);
633 isl_pw_aff_free (rhs
);
637 return isl_pw_aff_mul (lhs
, rhs
);
640 /* Return an ISL identifier from the name of the ssa_name E. */
643 isl_id_for_ssa_name (scop_p s
, tree e
)
645 const char *name
= get_name (e
);
649 id
= isl_id_alloc (s
->ctx
, name
, e
);
653 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
654 id
= isl_id_alloc (s
->ctx
, name1
, e
);
660 /* Return an ISL identifier for the data reference DR. */
663 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
665 /* Data references all get the same isl_id. They need to be comparable
666 and are distinguished through the first dimension, which contains the
668 return isl_id_alloc (s
->ctx
, "", 0);
671 /* Extract an affine expression from the ssa_name E. */
674 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
681 id
= isl_id_for_ssa_name (s
, e
);
682 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
684 dom
= isl_set_universe (isl_space_copy (space
));
685 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
686 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
687 return isl_pw_aff_alloc (dom
, aff
);
690 /* Extract an affine expression from the gmp constant G. */
693 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
695 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
696 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
697 isl_set
*dom
= isl_set_universe (space
);
701 isl_int_set_gmp (v
, g
);
702 aff
= isl_aff_add_constant (aff
, v
);
705 return isl_pw_aff_alloc (dom
, aff
);
708 /* Extract an affine expression from the integer_cst E. */
711 extract_affine_int (tree e
, __isl_take isl_space
*space
)
717 tree_int_to_gmp (e
, g
);
718 res
= extract_affine_gmp (g
, space
);
724 /* Compute pwaff mod 2^width. */
727 wrap (isl_pw_aff
*pwaff
, unsigned width
)
732 isl_int_set_si (mod
, 1);
733 isl_int_mul_2exp (mod
, mod
, width
);
735 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
742 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
743 Otherwise returns -1. */
746 parameter_index_in_region_1 (tree name
, sese region
)
751 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
753 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
760 /* When the parameter NAME is in REGION, returns its index in
761 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
762 and returns the index of NAME. */
765 parameter_index_in_region (tree name
, sese region
)
769 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
771 i
= parameter_index_in_region_1 (name
, region
);
775 gcc_assert (SESE_ADD_PARAMS (region
));
777 i
= SESE_PARAMS (region
).length ();
778 SESE_PARAMS (region
).safe_push (name
);
782 /* Extract an affine expression from the tree E in the scop S. */
785 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
787 isl_pw_aff
*lhs
, *rhs
, *res
;
790 if (e
== chrec_dont_know
) {
791 isl_space_free (space
);
795 switch (TREE_CODE (e
))
797 case POLYNOMIAL_CHREC
:
798 res
= extract_affine_chrec (s
, e
, space
);
802 res
= extract_affine_mul (s
, e
, space
);
806 case POINTER_PLUS_EXPR
:
807 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
808 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
809 res
= isl_pw_aff_add (lhs
, rhs
);
813 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
814 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
815 res
= isl_pw_aff_sub (lhs
, rhs
);
820 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
821 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
822 res
= isl_pw_aff_mul (lhs
, rhs
);
826 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
827 res
= extract_affine_name (s
, e
, space
);
831 res
= extract_affine_int (e
, space
);
832 /* No need to wrap a single integer. */
836 case NON_LVALUE_EXPR
:
837 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
845 type
= TREE_TYPE (e
);
846 if (TYPE_UNSIGNED (type
))
847 res
= wrap (res
, TYPE_PRECISION (type
));
852 /* In the context of sese S, scan the expression E and translate it to
853 a linear expression C. When parsing a symbolic multiplication, K
854 represents the constant multiplier of an expression containing
858 scan_tree_for_params (sese s
, tree e
)
860 if (e
== chrec_dont_know
)
863 switch (TREE_CODE (e
))
865 case POLYNOMIAL_CHREC
:
866 scan_tree_for_params (s
, CHREC_LEFT (e
));
870 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
871 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
873 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
877 case POINTER_PLUS_EXPR
:
879 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
880 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
886 case NON_LVALUE_EXPR
:
887 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
891 parameter_index_in_region (e
, s
);
904 /* Find parameters with respect to REGION in BB. We are looking in memory
905 access functions, conditions and loop bounds. */
908 find_params_in_bb (sese region
, gimple_bb_p gbb
)
914 loop_p loop
= GBB_BB (gbb
)->loop_father
;
916 /* Find parameters in the access functions of data references. */
917 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
918 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
919 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
921 /* Find parameters in conditional statements. */
922 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
924 tree lhs
= scalar_evolution_in_region (region
, loop
,
925 gimple_cond_lhs (stmt
));
926 tree rhs
= scalar_evolution_in_region (region
, loop
,
927 gimple_cond_rhs (stmt
));
929 scan_tree_for_params (region
, lhs
);
930 scan_tree_for_params (region
, rhs
);
934 /* Record the parameters used in the SCOP. A variable is a parameter
935 in a scop if it does not vary during the execution of that scop. */
938 find_scop_parameters (scop_p scop
)
942 sese region
= SCOP_REGION (scop
);
946 /* Find the parameters used in the loop bounds. */
947 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
949 tree nb_iters
= number_of_latch_executions (loop
);
951 if (!chrec_contains_symbols (nb_iters
))
954 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
955 scan_tree_for_params (region
, nb_iters
);
958 /* Find the parameters used in data accesses. */
959 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
960 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
962 nbp
= sese_nb_params (region
);
963 scop_set_nb_params (scop
, nbp
);
964 SESE_ADD_PARAMS (region
) = false;
968 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
970 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
971 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
972 isl_id_for_ssa_name (scop
, e
));
974 scop
->context
= isl_set_universe (space
);
978 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
979 the constraints for the surrounding loops. */
982 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
984 isl_set
*outer
, isl_set
**doms
)
986 tree nb_iters
= number_of_latch_executions (loop
);
987 sese region
= SCOP_REGION (scop
);
989 isl_set
*inner
= isl_set_copy (outer
);
992 int pos
= isl_set_dim (outer
, isl_dim_set
);
999 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1000 space
= isl_set_get_space (inner
);
1003 c
= isl_inequality_alloc
1004 (isl_local_space_from_space (isl_space_copy (space
)));
1005 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1006 inner
= isl_set_add_constraint (inner
, c
);
1008 /* loop_i <= cst_nb_iters */
1009 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1011 c
= isl_inequality_alloc
1012 (isl_local_space_from_space (isl_space_copy (space
)));
1013 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1014 tree_int_to_gmp (nb_iters
, g
);
1015 isl_int_set_gmp (v
, g
);
1016 c
= isl_constraint_set_constant (c
, v
);
1017 inner
= isl_set_add_constraint (inner
, c
);
1020 /* loop_i <= expr_nb_iters */
1021 else if (!chrec_contains_undetermined (nb_iters
))
1026 isl_local_space
*ls
;
1030 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1032 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1033 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1034 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1035 isl_set_dim (valid
, isl_dim_set
));
1036 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1038 ls
= isl_local_space_from_space (isl_space_copy (space
));
1039 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1040 isl_dim_in
, pos
, 1);
1041 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1042 isl_pw_aff_copy (aff
));
1043 inner
= isl_set_intersect (inner
, le
);
1045 if (max_stmt_executions (loop
, &nit
))
1047 /* Insert in the context the constraints from the
1048 estimation of the number of iterations NIT and the
1049 symbolic number of iterations (involving parameter
1050 names) NB_ITERS. First, build the affine expression
1051 "NIT - NB_ITERS" and then say that it is positive,
1052 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1059 mpz_set_double_int (g
, nit
, false);
1060 mpz_sub_ui (g
, g
, 1);
1061 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1062 x
= isl_pw_aff_ge_set (approx
, aff
);
1063 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1064 isl_set_dim (x
, isl_dim_set
));
1065 scop
->context
= isl_set_intersect (scop
->context
, x
);
1067 c
= isl_inequality_alloc
1068 (isl_local_space_from_space (isl_space_copy (space
)));
1069 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1070 isl_int_set_gmp (v
, g
);
1072 c
= isl_constraint_set_constant (c
, v
);
1073 inner
= isl_set_add_constraint (inner
, c
);
1076 isl_pw_aff_free (aff
);
1081 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1082 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1083 isl_set_copy (inner
), doms
);
1087 && loop_in_sese_p (loop
->next
, region
))
1088 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1089 isl_set_copy (outer
), doms
);
1091 doms
[loop
->num
] = inner
;
1093 isl_set_free (outer
);
1094 isl_space_free (space
);
1099 /* Returns a linear expression for tree T evaluated in PBB. */
1102 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1104 scop_p scop
= PBB_SCOP (pbb
);
1106 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1107 gcc_assert (!automatically_generated_chrec_p (t
));
1109 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1112 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1113 operator. This allows us to invert the condition or to handle
1117 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1119 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1120 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1126 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1130 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1134 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1138 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1142 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1146 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1150 isl_pw_aff_free (lhs
);
1151 isl_pw_aff_free (rhs
);
1155 cond
= isl_set_coalesce (cond
);
1156 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1157 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1160 /* Add conditions to the domain of PBB. */
1163 add_conditions_to_domain (poly_bb_p pbb
)
1167 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1169 if (GBB_CONDITIONS (gbb
).is_empty ())
1172 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1173 switch (gimple_code (stmt
))
1177 enum tree_code code
= gimple_cond_code (stmt
);
1179 /* The conditions for ELSE-branches are inverted. */
1180 if (!GBB_CONDITION_CASES (gbb
)[i
])
1181 code
= invert_tree_comparison (code
, false);
1183 add_condition_to_pbb (pbb
, stmt
, code
);
1188 /* Switch statements are not supported right now - fall through. */
1196 /* Traverses all the GBBs of the SCOP and add their constraints to the
1197 iteration domains. */
1200 add_conditions_to_constraints (scop_p scop
)
1205 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1206 add_conditions_to_domain (pbb
);
1209 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1210 edge between BB and its predecessor is not a loop exit edge, and
1211 the last statement of the single predecessor is a COND_EXPR. */
1214 single_pred_cond_non_loop_exit (basic_block bb
)
1216 if (single_pred_p (bb
))
1218 edge e
= single_pred_edge (bb
);
1219 basic_block pred
= e
->src
;
1222 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1225 stmt
= last_stmt (pred
);
1227 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1234 class sese_dom_walker
: public dom_walker
1237 sese_dom_walker (cdi_direction
, sese
);
1239 virtual void before_dom_children (basic_block
);
1240 virtual void after_dom_children (basic_block
);
1243 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1247 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1248 : dom_walker (direction
), m_region (region
)
1252 /* Call-back for dom_walk executed before visiting the dominated
1256 sese_dom_walker::before_dom_children (basic_block bb
)
1261 if (!bb_in_sese_p (bb
, m_region
))
1264 stmt
= single_pred_cond_non_loop_exit (bb
);
1268 edge e
= single_pred_edge (bb
);
1270 m_conditions
.safe_push (stmt
);
1272 if (e
->flags
& EDGE_TRUE_VALUE
)
1273 m_cases
.safe_push (stmt
);
1275 m_cases
.safe_push (NULL
);
1278 gbb
= gbb_from_bb (bb
);
1282 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1283 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1287 /* Call-back for dom_walk executed after visiting the dominated
1291 sese_dom_walker::after_dom_children (basic_block bb
)
1293 if (!bb_in_sese_p (bb
, m_region
))
1296 if (single_pred_cond_non_loop_exit (bb
))
1298 m_conditions
.pop ();
1303 /* Add constraints on the possible values of parameter P from the type
1307 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1309 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1310 tree type
= TREE_TYPE (parameter
);
1311 tree lb
= NULL_TREE
;
1312 tree ub
= NULL_TREE
;
1314 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1315 lb
= lower_bound_in_type (type
, type
);
1317 lb
= TYPE_MIN_VALUE (type
);
1319 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1320 ub
= upper_bound_in_type (type
, type
);
1322 ub
= TYPE_MAX_VALUE (type
);
1326 isl_space
*space
= isl_set_get_space (scop
->context
);
1331 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1334 tree_int_to_gmp (lb
, g
);
1335 isl_int_set_gmp (v
, g
);
1338 c
= isl_constraint_set_constant (c
, v
);
1340 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1342 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1347 isl_space
*space
= isl_set_get_space (scop
->context
);
1352 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1356 tree_int_to_gmp (ub
, g
);
1357 isl_int_set_gmp (v
, g
);
1359 c
= isl_constraint_set_constant (c
, v
);
1361 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1363 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1367 /* Build the context of the SCOP. The context usually contains extra
1368 constraints that are added to the iteration domains that constrain
1372 build_scop_context (scop_p scop
)
1374 graphite_dim_t p
, n
= scop_nb_params (scop
);
1376 for (p
= 0; p
< n
; p
++)
1377 add_param_constraints (scop
, p
);
1380 /* Build the iteration domains: the loops belonging to the current
1381 SCOP, and that vary for the execution of the current basic block.
1382 Returns false if there is no loop in SCOP. */
1385 build_scop_iteration_domain (scop_p scop
)
1388 sese region
= SCOP_REGION (scop
);
1391 int nb_loops
= number_of_loops (cfun
);
1392 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1394 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1395 if (!loop_in_sese_p (loop_outer (loop
), region
))
1396 build_loop_iteration_domains (scop
, loop
, 0,
1397 isl_set_copy (scop
->context
), doms
);
1399 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1401 loop
= pbb_loop (pbb
);
1403 if (doms
[loop
->num
])
1404 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1406 pbb
->domain
= isl_set_copy (scop
->context
);
1408 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1409 isl_id_for_pbb (scop
, pbb
));
1412 for (i
= 0; i
< nb_loops
; i
++)
1414 isl_set_free (doms
[i
]);
1419 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1420 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1421 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1425 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1428 int alias_set_num
= 0;
1429 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1431 if (bap
&& bap
->alias_set
)
1432 alias_set_num
= *(bap
->alias_set
);
1434 c
= isl_equality_alloc
1435 (isl_local_space_from_space (isl_map_get_space (acc
)));
1436 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1437 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1439 return isl_map_add_constraint (acc
, c
);
1442 /* Assign the affine expression INDEX to the output dimension POS of
1443 MAP and return the result. */
1446 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1449 int len
= isl_map_dim (map
, isl_dim_out
);
1452 index_map
= isl_map_from_pw_aff (index
);
1453 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1454 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1456 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1457 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1458 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1459 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1461 return isl_map_intersect (map
, index_map
);
1464 /* Add to ACCESSES polyhedron equalities defining the access functions
1465 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1466 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1467 PBB is the poly_bb_p that contains the data reference DR. */
1470 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1472 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1473 scop_p scop
= PBB_SCOP (pbb
);
1475 for (i
= 0; i
< nb_subscripts
; i
++)
1478 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1480 aff
= extract_affine (scop
, afn
,
1481 isl_space_domain (isl_map_get_space (acc
)));
1482 acc
= set_index (acc
, i
+ 1, aff
);
1488 /* Add constrains representing the size of the accessed data to the
1489 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1490 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1494 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1496 tree ref
= DR_REF (dr
);
1497 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1499 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1503 if (TREE_CODE (ref
) != ARRAY_REF
)
1506 low
= array_ref_low_bound (ref
);
1507 high
= array_ref_up_bound (ref
);
1509 /* XXX The PPL code dealt separately with
1510 subscript - low >= 0 and high - subscript >= 0 in case one of
1511 the two bounds isn't known. Do the same here? */
1513 if (tree_fits_shwi_p (low
)
1515 && tree_fits_shwi_p (high
)
1516 /* 1-element arrays at end of structures may extend over
1517 their declared size. */
1518 && !(array_at_struct_end_p (ref
)
1519 && operand_equal_p (low
, high
, 0)))
1523 isl_set
*univ
, *lbs
, *ubs
;
1527 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1528 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1531 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1532 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1533 isl_set_dim (valid
, isl_dim_set
));
1534 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1536 space
= isl_set_get_space (extent
);
1537 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1538 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1539 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1540 index
= isl_pw_aff_alloc (univ
, aff
);
1542 id
= isl_set_get_tuple_id (extent
);
1543 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1544 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1546 /* low <= sub_i <= high */
1547 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1548 ubs
= isl_pw_aff_le_set (index
, ub
);
1549 extent
= isl_set_intersect (extent
, lbs
);
1550 extent
= isl_set_intersect (extent
, ubs
);
1557 /* Build data accesses for DR in PBB. */
1560 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1562 int dr_base_object_set
;
1565 scop_p scop
= PBB_SCOP (pbb
);
1568 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1569 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1570 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1571 isl_dim_out
, nb_out
);
1573 acc
= isl_map_universe (space
);
1574 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1577 acc
= pdr_add_alias_set (acc
, dr
);
1578 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1581 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1582 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1583 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1584 int alias_set_num
= 0;
1585 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1587 if (bap
&& bap
->alias_set
)
1588 alias_set_num
= *(bap
->alias_set
);
1590 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1591 extent
= isl_set_nat_universe (space
);
1592 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1593 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1596 gcc_assert (dr
->aux
);
1597 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1599 new_poly_dr (pbb
, dr_base_object_set
,
1600 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1601 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1604 /* Write to FILE the alias graph of data references in DIMACS format. */
1607 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1608 vec
<data_reference_p
> drs
)
1610 int num_vertex
= drs
.length ();
1612 data_reference_p dr1
, dr2
;
1615 if (num_vertex
== 0)
1618 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1619 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1620 if (dr_may_alias_p (dr1
, dr2
, true))
1623 fprintf (file
, "$\n");
1626 fprintf (file
, "c %s\n", comment
);
1628 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1630 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1631 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1632 if (dr_may_alias_p (dr1
, dr2
, true))
1633 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1638 /* Write to FILE the alias graph of data references in DOT format. */
1641 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1642 vec
<data_reference_p
> drs
)
1644 int num_vertex
= drs
.length ();
1645 data_reference_p dr1
, dr2
;
1648 if (num_vertex
== 0)
1651 fprintf (file
, "$\n");
1654 fprintf (file
, "c %s\n", comment
);
1656 /* First print all the vertices. */
1657 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1658 fprintf (file
, "n%d;\n", i
);
1660 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1661 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1662 if (dr_may_alias_p (dr1
, dr2
, true))
1663 fprintf (file
, "n%d n%d\n", i
, j
);
1668 /* Write to FILE the alias graph of data references in ECC format. */
1671 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1672 vec
<data_reference_p
> drs
)
1674 int num_vertex
= drs
.length ();
1675 data_reference_p dr1
, dr2
;
1678 if (num_vertex
== 0)
1681 fprintf (file
, "$\n");
1684 fprintf (file
, "c %s\n", comment
);
1686 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1687 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1688 if (dr_may_alias_p (dr1
, dr2
, true))
1689 fprintf (file
, "%d %d\n", i
, j
);
1694 /* Check if DR1 and DR2 are in the same object set. */
1697 dr_same_base_object_p (const struct data_reference
*dr1
,
1698 const struct data_reference
*dr2
)
1700 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1703 /* Uses DFS component number as representative of alias-sets. Also tests for
1704 optimality by verifying if every connected component is a clique. Returns
1705 true (1) if the above test is true, and false (0) otherwise. */
1708 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1710 int num_vertices
= drs
.length ();
1711 struct graph
*g
= new_graph (num_vertices
);
1712 data_reference_p dr1
, dr2
;
1714 int num_connected_components
;
1715 int v_indx1
, v_indx2
, num_vertices_in_component
;
1718 struct graph_edge
*e
;
1719 int this_component_is_clique
;
1720 int all_components_are_cliques
= 1;
1722 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1723 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1724 if (dr_may_alias_p (dr1
, dr2
, true))
1730 all_vertices
= XNEWVEC (int, num_vertices
);
1731 vertices
= XNEWVEC (int, num_vertices
);
1732 for (i
= 0; i
< num_vertices
; i
++)
1733 all_vertices
[i
] = i
;
1735 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1737 for (i
= 0; i
< g
->n_vertices
; i
++)
1739 data_reference_p dr
= drs
[i
];
1740 base_alias_pair
*bap
;
1742 gcc_assert (dr
->aux
);
1743 bap
= (base_alias_pair
*)(dr
->aux
);
1745 bap
->alias_set
= XNEW (int);
1746 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1749 /* Verify if the DFS numbering results in optimal solution. */
1750 for (i
= 0; i
< num_connected_components
; i
++)
1752 num_vertices_in_component
= 0;
1753 /* Get all vertices whose DFS component number is the same as i. */
1754 for (j
= 0; j
< num_vertices
; j
++)
1755 if (g
->vertices
[j
].component
== i
)
1756 vertices
[num_vertices_in_component
++] = j
;
1758 /* Now test if the vertices in 'vertices' form a clique, by testing
1759 for edges among each pair. */
1760 this_component_is_clique
= 1;
1761 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1763 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1765 /* Check if the two vertices are connected by iterating
1766 through all the edges which have one of these are source. */
1767 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1770 if (e
->src
== vertices
[v_indx1
])
1776 this_component_is_clique
= 0;
1780 if (!this_component_is_clique
)
1781 all_components_are_cliques
= 0;
1785 free (all_vertices
);
1788 return all_components_are_cliques
;
1791 /* Group each data reference in DRS with its base object set num. */
1794 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1796 int num_vertex
= drs
.length ();
1797 struct graph
*g
= new_graph (num_vertex
);
1798 data_reference_p dr1
, dr2
;
1802 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1803 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1804 if (dr_same_base_object_p (dr1
, dr2
))
1810 queue
= XNEWVEC (int, num_vertex
);
1811 for (i
= 0; i
< num_vertex
; i
++)
1814 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1816 for (i
= 0; i
< g
->n_vertices
; i
++)
1818 data_reference_p dr
= drs
[i
];
1819 base_alias_pair
*bap
;
1821 gcc_assert (dr
->aux
);
1822 bap
= (base_alias_pair
*)(dr
->aux
);
1824 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1831 /* Build the data references for PBB. */
1834 build_pbb_drs (poly_bb_p pbb
)
1837 data_reference_p dr
;
1838 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1840 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1841 build_poly_dr (dr
, pbb
);
1844 /* Dump to file the alias graphs for the data references in DRS. */
1847 dump_alias_graphs (vec
<data_reference_p
> drs
)
1850 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1852 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1855 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1856 current_function_name ());
1857 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1858 fclose (file_dimacs
);
1861 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1864 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1865 current_function_name ());
1866 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1870 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1873 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1874 current_function_name ());
1875 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1880 /* Build data references in SCOP. */
1883 build_scop_drs (scop_p scop
)
1887 data_reference_p dr
;
1888 stack_vec
<data_reference_p
, 3> drs
;
1890 /* Remove all the PBBs that do not have data references: these basic
1891 blocks are not handled in the polyhedral representation. */
1892 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1893 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1895 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1897 SCOP_BBS (scop
).ordered_remove (i
);
1901 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1902 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1905 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1906 dr
->aux
= XNEW (base_alias_pair
);
1908 if (!build_alias_set_optimal_p (drs
))
1910 /* TODO: Add support when building alias set is not optimal. */
1914 build_base_obj_set_for_drs (drs
);
1916 /* When debugging, enable the following code. This cannot be used
1917 in production compilers. */
1919 dump_alias_graphs (drs
);
1923 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1924 build_pbb_drs (pbb
);
1927 /* Return a gsi at the position of the phi node STMT. */
1929 static gimple_stmt_iterator
1930 gsi_for_phi_node (gimple stmt
)
1932 gimple_stmt_iterator psi
;
1933 basic_block bb
= gimple_bb (stmt
);
1935 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1936 if (stmt
== gsi_stmt (psi
))
1943 /* Analyze all the data references of STMTS and add them to the
1944 GBB_DATA_REFS vector of BB. */
1947 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1953 sese region
= SCOP_REGION (scop
);
1955 if (!bb_in_sese_p (bb
, region
))
1958 nest
= outermost_loop_in_sese_1 (region
, bb
);
1959 gbb
= gbb_from_bb (bb
);
1961 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1965 if (is_gimple_debug (stmt
))
1968 loop
= loop_containing_stmt (stmt
);
1969 if (!loop_in_sese_p (loop
, region
))
1972 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1973 &GBB_DATA_REFS (gbb
));
1977 /* Insert STMT at the end of the STMTS sequence and then insert the
1978 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1982 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1983 gimple_stmt_iterator insert_gsi
)
1985 gimple_stmt_iterator gsi
;
1986 stack_vec
<gimple
, 3> x
;
1988 gimple_seq_add_stmt (&stmts
, stmt
);
1989 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1990 x
.safe_push (gsi_stmt (gsi
));
1992 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1993 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1996 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1999 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2002 gimple_stmt_iterator gsi
;
2003 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2004 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2005 stack_vec
<gimple
, 3> x
;
2007 gimple_seq_add_stmt (&stmts
, stmt
);
2008 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2009 x
.safe_push (gsi_stmt (gsi
));
2011 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2013 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2014 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2018 gsi
= gsi_for_stmt (after_stmt
);
2019 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2022 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2025 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2028 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2030 vec
<data_reference_p
> drs
;
2032 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2033 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2034 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2035 int index
, n
= SCOP_BBS (scop
).length ();
2037 /* The INDEX of PBB in SCOP_BBS. */
2038 for (index
= 0; index
< n
; index
++)
2039 if (SCOP_BBS (scop
)[index
] == pbb
)
2042 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2044 GBB_PBB (gbb1
) = pbb1
;
2045 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2046 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2047 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2050 /* Insert on edge E the assignment "RES := EXPR". */
2053 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2055 gimple_stmt_iterator gsi
;
2056 gimple_seq stmts
= NULL
;
2057 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2058 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2060 stack_vec
<gimple
, 3> x
;
2062 gimple_seq_add_stmt (&stmts
, stmt
);
2063 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2064 x
.safe_push (gsi_stmt (gsi
));
2066 gsi_insert_seq_on_edge (e
, stmts
);
2067 gsi_commit_edge_inserts ();
2068 bb
= gimple_bb (stmt
);
2070 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2073 if (!gbb_from_bb (bb
))
2074 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2076 analyze_drs_in_stmts (scop
, bb
, x
);
2079 /* Creates a zero dimension array of the same type as VAR. */
2082 create_zero_dim_array (tree var
, const char *base_name
)
2084 tree index_type
= build_index_type (integer_zero_node
);
2085 tree elt_type
= TREE_TYPE (var
);
2086 tree array_type
= build_array_type (elt_type
, index_type
);
2087 tree base
= create_tmp_var (array_type
, base_name
);
2089 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2093 /* Returns true when PHI is a loop close phi node. */
2096 scalar_close_phi_node_p (gimple phi
)
2098 if (gimple_code (phi
) != GIMPLE_PHI
2099 || virtual_operand_p (gimple_phi_result (phi
)))
2102 /* Note that loop close phi nodes should have a single argument
2103 because we translated the representation into a canonical form
2104 before Graphite: see canonicalize_loop_closed_ssa_form. */
2105 return (gimple_phi_num_args (phi
) == 1);
2108 /* For a definition DEF in REGION, propagates the expression EXPR in
2109 all the uses of DEF outside REGION. */
2112 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2114 imm_use_iterator imm_iter
;
2117 bool replaced_once
= false;
2119 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2121 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2124 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2125 if (!is_gimple_debug (use_stmt
)
2126 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2129 use_operand_p use_p
;
2131 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2132 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2133 && (replaced_once
= true))
2134 replace_exp (use_p
, expr
);
2136 update_stmt (use_stmt
);
2141 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2142 gsi_commit_edge_inserts ();
2146 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2147 dimension array for it. */
2150 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2152 sese region
= SCOP_REGION (scop
);
2153 gimple phi
= gsi_stmt (*psi
);
2154 tree res
= gimple_phi_result (phi
);
2155 basic_block bb
= gimple_bb (phi
);
2156 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2157 tree arg
= gimple_phi_arg_def (phi
, 0);
2160 /* Note that loop close phi nodes should have a single argument
2161 because we translated the representation into a canonical form
2162 before Graphite: see canonicalize_loop_closed_ssa_form. */
2163 gcc_assert (gimple_phi_num_args (phi
) == 1);
2165 /* The phi node can be a non close phi node, when its argument is
2166 invariant, or a default definition. */
2167 if (is_gimple_min_invariant (arg
)
2168 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2170 propagate_expr_outside_region (res
, arg
, region
);
2175 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2177 propagate_expr_outside_region (res
, arg
, region
);
2178 stmt
= gimple_build_assign (res
, arg
);
2179 remove_phi_node (psi
, false);
2180 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2184 /* If res is scev analyzable and is not a scalar value, it is safe
2185 to ignore the close phi node: it will be code generated in the
2186 out of Graphite pass. */
2187 else if (scev_analyzable_p (res
, region
))
2189 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2192 if (!loop_in_sese_p (loop
, region
))
2194 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2195 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2196 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2199 scev
= scalar_evolution_in_region (region
, loop
, res
);
2201 if (tree_does_not_contain_chrecs (scev
))
2202 propagate_expr_outside_region (res
, scev
, region
);
2209 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2211 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2213 if (TREE_CODE (arg
) == SSA_NAME
)
2214 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2215 SSA_NAME_DEF_STMT (arg
));
2217 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2218 zero_dim_array
, arg
);
2221 remove_phi_node (psi
, false);
2222 SSA_NAME_DEF_STMT (res
) = stmt
;
2224 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2227 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2228 dimension array for it. */
2231 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2234 gimple phi
= gsi_stmt (*psi
);
2235 basic_block bb
= gimple_bb (phi
);
2236 tree res
= gimple_phi_result (phi
);
2237 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2240 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2242 tree arg
= gimple_phi_arg_def (phi
, i
);
2243 edge e
= gimple_phi_arg_edge (phi
, i
);
2245 /* Avoid the insertion of code in the loop latch to please the
2246 pattern matching of the vectorizer. */
2247 if (TREE_CODE (arg
) == SSA_NAME
2248 && e
->src
== bb
->loop_father
->latch
)
2249 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2250 SSA_NAME_DEF_STMT (arg
));
2252 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2255 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2256 remove_phi_node (psi
, false);
2257 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2260 /* Rewrite the degenerate phi node at position PSI from the degenerate
2261 form "x = phi (y, y, ..., y)" to "x = y". */
2264 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2268 gimple_stmt_iterator gsi
;
2269 gimple phi
= gsi_stmt (*psi
);
2270 tree res
= gimple_phi_result (phi
);
2273 bb
= gimple_bb (phi
);
2274 rhs
= degenerate_phi_result (phi
);
2277 stmt
= gimple_build_assign (res
, rhs
);
2278 remove_phi_node (psi
, false);
2280 gsi
= gsi_after_labels (bb
);
2281 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2284 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2287 rewrite_reductions_out_of_ssa (scop_p scop
)
2290 gimple_stmt_iterator psi
;
2291 sese region
= SCOP_REGION (scop
);
2294 if (bb_in_sese_p (bb
, region
))
2295 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2297 gimple phi
= gsi_stmt (psi
);
2299 if (virtual_operand_p (gimple_phi_result (phi
)))
2305 if (gimple_phi_num_args (phi
) > 1
2306 && degenerate_phi_result (phi
))
2307 rewrite_degenerate_phi (&psi
);
2309 else if (scalar_close_phi_node_p (phi
))
2310 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2312 else if (reduction_phi_p (region
, &psi
))
2313 rewrite_phi_out_of_ssa (scop
, &psi
);
2316 update_ssa (TODO_update_ssa
);
2317 #ifdef ENABLE_CHECKING
2318 verify_loop_closed_ssa (true);
2322 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2323 read from ZERO_DIM_ARRAY. */
2326 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2327 tree def
, gimple use_stmt
)
2332 use_operand_p use_p
;
2334 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2336 name
= copy_ssa_name (def
, NULL
);
2337 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2339 gimple_assign_set_lhs (name_stmt
, name
);
2340 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2342 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2343 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2344 replace_exp (use_p
, name
);
2346 update_stmt (use_stmt
);
2349 /* For every definition DEF in the SCOP that is used outside the scop,
2350 insert a closing-scop definition in the basic block just after this
2354 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2356 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2357 tree new_name
= make_ssa_name (var
, stmt
);
2358 bool needs_copy
= false;
2359 use_operand_p use_p
;
2360 imm_use_iterator imm_iter
;
2362 sese region
= SCOP_REGION (scop
);
2364 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2366 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2368 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2370 SET_USE (use_p
, new_name
);
2372 update_stmt (use_stmt
);
2377 /* Insert in the empty BB just after the scop a use of DEF such
2378 that the rewrite of cross_bb_scalar_dependences won't insert
2379 arrays everywhere else. */
2382 gimple assign
= gimple_build_assign (new_name
, def
);
2383 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
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;