1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2014 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
26 #include <isl/union_map.h>
27 #include <isl/constraint.h>
29 #include <cloog/cloog.h>
30 #include <cloog/cloog.h>
31 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
37 #include "basic-block.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
45 #include "gimplify-me.h"
46 #include "gimple-ssa.h"
48 #include "tree-phinodes.h"
49 #include "ssa-iterators.h"
50 #include "stringpool.h"
51 #include "tree-ssanames.h"
52 #include "tree-ssa-loop-manip.h"
53 #include "tree-ssa-loop-niter.h"
54 #include "tree-ssa-loop.h"
55 #include "tree-into-ssa.h"
56 #include "tree-pass.h"
58 #include "tree-chrec.h"
59 #include "tree-data-ref.h"
60 #include "tree-scalar-evolution.h"
63 #include "tree-ssa-propagate.h"
67 #include "graphite-poly.h"
68 #include "graphite-sese-to-poly.h"
71 /* Assigns to RES the value of the INTEGER_CST T. */
74 tree_int_to_gmp (tree t
, mpz_t res
)
76 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
79 /* Returns the index of the PHI argument defined in the outermost
83 phi_arg_in_outermost_loop (gimple phi
)
85 loop_p loop
= gimple_bb (phi
)->loop_father
;
88 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
89 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
91 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
98 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
99 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
102 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
104 gimple phi
= gsi_stmt (*psi
);
105 tree res
= gimple_phi_result (phi
);
106 size_t entry
= phi_arg_in_outermost_loop (phi
);
107 tree init
= gimple_phi_arg_def (phi
, entry
);
108 gimple stmt
= gimple_build_assign (res
, init
);
109 edge e
= gimple_phi_arg_edge (phi
, entry
);
111 remove_phi_node (psi
, false);
112 gsi_insert_on_edge_immediate (e
, stmt
);
115 /* Removes an invariant phi node at position PSI by inserting on the
116 loop ENTRY edge the assignment RES = INIT. */
119 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
121 gimple phi
= gsi_stmt (*psi
);
122 loop_p loop
= loop_containing_stmt (phi
);
123 tree res
= gimple_phi_result (phi
);
124 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
125 size_t entry
= phi_arg_in_outermost_loop (phi
);
126 edge e
= gimple_phi_arg_edge (phi
, entry
);
129 gimple_seq stmts
= NULL
;
131 if (tree_contains_chrecs (scev
, NULL
))
132 scev
= gimple_phi_arg_def (phi
, entry
);
134 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
135 stmt
= gimple_build_assign (res
, var
);
136 remove_phi_node (psi
, false);
138 gimple_seq_add_stmt (&stmts
, stmt
);
139 gsi_insert_seq_on_edge (e
, stmts
);
140 gsi_commit_edge_inserts ();
141 SSA_NAME_DEF_STMT (res
) = stmt
;
144 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
147 simple_copy_phi_p (gimple phi
)
151 if (gimple_phi_num_args (phi
) != 2)
154 res
= gimple_phi_result (phi
);
155 return (res
== gimple_phi_arg_def (phi
, 0)
156 || res
== gimple_phi_arg_def (phi
, 1));
159 /* Returns true when the phi node at position PSI is a reduction phi
160 node in REGION. Otherwise moves the pointer PSI to the next phi to
164 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
167 gimple phi
= gsi_stmt (*psi
);
168 tree res
= gimple_phi_result (phi
);
170 loop
= loop_containing_stmt (phi
);
172 if (simple_copy_phi_p (phi
))
174 /* PRE introduces phi nodes like these, for an example,
175 see id-5.f in the fortran graphite testsuite:
177 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
179 remove_simple_copy_phi (psi
);
183 if (scev_analyzable_p (res
, region
))
185 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
187 if (evolution_function_is_invariant_p (scev
, loop
->num
))
188 remove_invariant_phi (region
, psi
);
195 /* All the other cases are considered reductions. */
199 /* Store the GRAPHITE representation of BB. */
202 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
204 struct gimple_bb
*gbb
;
206 gbb
= XNEW (struct gimple_bb
);
209 GBB_DATA_REFS (gbb
) = drs
;
210 GBB_CONDITIONS (gbb
).create (0);
211 GBB_CONDITION_CASES (gbb
).create (0);
217 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
220 struct data_reference
*dr
;
222 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
225 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
227 free (bap
->alias_set
);
236 free_gimple_bb (struct gimple_bb
*gbb
)
238 free_data_refs_aux (GBB_DATA_REFS (gbb
));
239 free_data_refs (GBB_DATA_REFS (gbb
));
241 GBB_CONDITIONS (gbb
).release ();
242 GBB_CONDITION_CASES (gbb
).release ();
243 GBB_BB (gbb
)->aux
= 0;
247 /* Deletes all gimple bbs in SCOP. */
250 remove_gbbs_in_scop (scop_p scop
)
255 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
256 free_gimple_bb (PBB_BLACK_BOX (pbb
));
259 /* Deletes all scops in SCOPS. */
262 free_scops (vec
<scop_p
> scops
)
267 FOR_EACH_VEC_ELT (scops
, i
, scop
)
269 remove_gbbs_in_scop (scop
);
270 free_sese (SCOP_REGION (scop
));
277 /* Same as outermost_loop_in_sese, returns the outermost loop
278 containing BB in REGION, but makes sure that the returned loop
279 belongs to the REGION, and so this returns the first loop in the
280 REGION when the loop containing BB does not belong to REGION. */
283 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
285 loop_p nest
= outermost_loop_in_sese (region
, bb
);
287 if (loop_in_sese_p (nest
, region
))
290 /* When the basic block BB does not belong to a loop in the region,
291 return the first loop in the region. */
294 if (loop_in_sese_p (nest
, region
))
303 /* Generates a polyhedral black box only if the bb contains interesting
307 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
309 vec
<data_reference_p
> drs
;
311 sese region
= SCOP_REGION (scop
);
312 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
313 gimple_stmt_iterator gsi
;
315 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
317 gimple stmt
= gsi_stmt (gsi
);
320 if (is_gimple_debug (stmt
))
323 loop
= loop_containing_stmt (stmt
);
324 if (!loop_in_sese_p (loop
, region
))
327 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
330 return new_gimple_bb (bb
, drs
);
333 /* Returns true if all predecessors of BB, that are not dominated by BB, are
334 marked in MAP. The predecessors dominated by BB are loop latches and will
335 be handled after BB. */
338 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
343 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
344 if (!bitmap_bit_p (map
, e
->src
->index
)
345 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
351 /* Compare the depth of two basic_block's P1 and P2. */
354 compare_bb_depths (const void *p1
, const void *p2
)
356 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
357 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
358 int d1
= loop_depth (bb1
->loop_father
);
359 int d2
= loop_depth (bb2
->loop_father
);
370 /* Sort the basic blocks from DOM such that the first are the ones at
371 a deepest loop level. */
374 graphite_sort_dominated_info (vec
<basic_block
> dom
)
376 dom
.qsort (compare_bb_depths
);
379 /* Recursive helper function for build_scops_bbs. */
382 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
384 sese region
= SCOP_REGION (scop
);
385 vec
<basic_block
> dom
;
388 if (bitmap_bit_p (visited
, bb
->index
)
389 || !bb_in_sese_p (bb
, region
))
392 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
393 SCOP_BBS (scop
).safe_push (pbb
);
394 bitmap_set_bit (visited
, bb
->index
);
396 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
401 graphite_sort_dominated_info (dom
);
403 while (!dom
.is_empty ())
408 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
409 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
411 build_scop_bbs_1 (scop
, visited
, dom_bb
);
412 dom
.unordered_remove (i
);
420 /* Gather the basic blocks belonging to the SCOP. */
423 build_scop_bbs (scop_p scop
)
425 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
426 sese region
= SCOP_REGION (scop
);
428 bitmap_clear (visited
);
429 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
430 sbitmap_free (visited
);
433 /* Return an ISL identifier for the polyhedral basic block PBB. */
436 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
439 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
440 return isl_id_alloc (s
->ctx
, name
, pbb
);
443 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
444 We generate SCATTERING_DIMENSIONS scattering dimensions.
446 CLooG 0.15.0 and previous versions require, that all
447 scattering functions of one CloogProgram have the same number of
448 scattering dimensions, therefore we allow to specify it. This
449 should be removed in future versions of CLooG.
451 The scattering polyhedron consists of these dimensions: scattering,
452 loop_iterators, parameters.
456 | scattering_dimensions = 5
457 | used_scattering_dimensions = 3
465 | Scattering polyhedron:
467 | scattering: {s1, s2, s3, s4, s5}
468 | loop_iterators: {i}
469 | parameters: {p1, p2}
471 | s1 s2 s3 s4 s5 i p1 p2 1
472 | 1 0 0 0 0 0 0 0 -4 = 0
473 | 0 1 0 0 0 -1 0 0 0 = 0
474 | 0 0 1 0 0 0 0 0 -5 = 0 */
477 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
478 poly_bb_p pbb
, int scattering_dimensions
)
481 int nb_iterators
= pbb_dim_iter_domain (pbb
);
482 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
486 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
490 dc
= isl_set_get_space (pbb
->domain
);
491 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
492 isl_dim_out
, scattering_dimensions
);
493 pbb
->schedule
= isl_map_universe (dm
);
495 for (i
= 0; i
< scattering_dimensions
; i
++)
497 /* Textual order inside this loop. */
500 isl_constraint
*c
= isl_equality_alloc
501 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
503 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
507 isl_int_neg (val
, val
);
508 c
= isl_constraint_set_constant (c
, val
);
509 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
510 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
513 /* Iterations of this loop. */
514 else /* if ((i % 2) == 1) */
516 int loop
= (i
- 1) / 2;
517 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
524 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
527 /* Build for BB the static schedule.
529 The static schedule is a Dewey numbering of the abstract syntax
530 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
532 The following example informally defines the static schedule:
551 Static schedules for A to F:
564 build_scop_scattering (scop_p scop
)
568 gimple_bb_p previous_gbb
= NULL
;
569 isl_space
*dc
= isl_set_get_space (scop
->context
);
570 isl_aff
*static_sched
;
572 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
573 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
575 /* We have to start schedules at 0 on the first component and
576 because we cannot compare_prefix_loops against a previous loop,
577 prefix will be equal to zero, and that index will be
578 incremented before copying. */
579 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
581 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
583 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
585 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
588 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
594 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
596 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
599 isl_aff_free (static_sched
);
602 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
604 /* Extract an affine expression from the chain of recurrence E. */
607 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
609 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
610 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
611 isl_local_space
*ls
= isl_local_space_from_space (space
);
612 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
613 isl_aff
*loop
= isl_aff_set_coefficient_si
614 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
615 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
617 /* Before multiplying, make sure that the result is affine. */
618 gcc_assert (isl_pw_aff_is_cst (rhs
)
619 || isl_pw_aff_is_cst (l
));
621 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
624 /* Extract an affine expression from the mult_expr E. */
627 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
629 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
630 isl_space_copy (space
));
631 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
633 if (!isl_pw_aff_is_cst (lhs
)
634 && !isl_pw_aff_is_cst (rhs
))
636 isl_pw_aff_free (lhs
);
637 isl_pw_aff_free (rhs
);
641 return isl_pw_aff_mul (lhs
, rhs
);
644 /* Return an ISL identifier from the name of the ssa_name E. */
647 isl_id_for_ssa_name (scop_p s
, tree e
)
649 const char *name
= get_name (e
);
653 id
= isl_id_alloc (s
->ctx
, name
, e
);
657 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
658 id
= isl_id_alloc (s
->ctx
, name1
, e
);
664 /* Return an ISL identifier for the data reference DR. */
667 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
669 /* Data references all get the same isl_id. They need to be comparable
670 and are distinguished through the first dimension, which contains the
672 return isl_id_alloc (s
->ctx
, "", 0);
675 /* Extract an affine expression from the ssa_name E. */
678 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
685 id
= isl_id_for_ssa_name (s
, e
);
686 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
688 dom
= isl_set_universe (isl_space_copy (space
));
689 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
690 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
691 return isl_pw_aff_alloc (dom
, aff
);
694 /* Extract an affine expression from the gmp constant G. */
697 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
699 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
700 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
701 isl_set
*dom
= isl_set_universe (space
);
705 isl_int_set_gmp (v
, g
);
706 aff
= isl_aff_add_constant (aff
, v
);
709 return isl_pw_aff_alloc (dom
, aff
);
712 /* Extract an affine expression from the integer_cst E. */
715 extract_affine_int (tree e
, __isl_take isl_space
*space
)
721 tree_int_to_gmp (e
, g
);
722 res
= extract_affine_gmp (g
, space
);
728 /* Compute pwaff mod 2^width. */
731 wrap (isl_pw_aff
*pwaff
, unsigned width
)
736 isl_int_set_si (mod
, 1);
737 isl_int_mul_2exp (mod
, mod
, width
);
739 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
746 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
747 Otherwise returns -1. */
750 parameter_index_in_region_1 (tree name
, sese region
)
755 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
757 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
764 /* When the parameter NAME is in REGION, returns its index in
765 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
766 and returns the index of NAME. */
769 parameter_index_in_region (tree name
, sese region
)
773 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
775 i
= parameter_index_in_region_1 (name
, region
);
779 gcc_assert (SESE_ADD_PARAMS (region
));
781 i
= SESE_PARAMS (region
).length ();
782 SESE_PARAMS (region
).safe_push (name
);
786 /* Extract an affine expression from the tree E in the scop S. */
789 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
791 isl_pw_aff
*lhs
, *rhs
, *res
;
794 if (e
== chrec_dont_know
) {
795 isl_space_free (space
);
799 switch (TREE_CODE (e
))
801 case POLYNOMIAL_CHREC
:
802 res
= extract_affine_chrec (s
, e
, space
);
806 res
= extract_affine_mul (s
, e
, space
);
810 case POINTER_PLUS_EXPR
:
811 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
812 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
813 res
= isl_pw_aff_add (lhs
, rhs
);
817 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
818 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
819 res
= isl_pw_aff_sub (lhs
, rhs
);
824 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
825 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
826 res
= isl_pw_aff_mul (lhs
, rhs
);
830 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
831 res
= extract_affine_name (s
, e
, space
);
835 res
= extract_affine_int (e
, space
);
836 /* No need to wrap a single integer. */
840 case NON_LVALUE_EXPR
:
841 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
849 type
= TREE_TYPE (e
);
850 if (TYPE_UNSIGNED (type
))
851 res
= wrap (res
, TYPE_PRECISION (type
));
856 /* In the context of sese S, scan the expression E and translate it to
857 a linear expression C. When parsing a symbolic multiplication, K
858 represents the constant multiplier of an expression containing
862 scan_tree_for_params (sese s
, tree e
)
864 if (e
== chrec_dont_know
)
867 switch (TREE_CODE (e
))
869 case POLYNOMIAL_CHREC
:
870 scan_tree_for_params (s
, CHREC_LEFT (e
));
874 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
875 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
881 case POINTER_PLUS_EXPR
:
883 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
884 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
890 case NON_LVALUE_EXPR
:
891 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
895 parameter_index_in_region (e
, s
);
908 /* Find parameters with respect to REGION in BB. We are looking in memory
909 access functions, conditions and loop bounds. */
912 find_params_in_bb (sese region
, gimple_bb_p gbb
)
918 loop_p loop
= GBB_BB (gbb
)->loop_father
;
920 /* Find parameters in the access functions of data references. */
921 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
922 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
923 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
925 /* Find parameters in conditional statements. */
926 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
928 tree lhs
= scalar_evolution_in_region (region
, loop
,
929 gimple_cond_lhs (stmt
));
930 tree rhs
= scalar_evolution_in_region (region
, loop
,
931 gimple_cond_rhs (stmt
));
933 scan_tree_for_params (region
, lhs
);
934 scan_tree_for_params (region
, rhs
);
938 /* Record the parameters used in the SCOP. A variable is a parameter
939 in a scop if it does not vary during the execution of that scop. */
942 find_scop_parameters (scop_p scop
)
946 sese region
= SCOP_REGION (scop
);
950 /* Find the parameters used in the loop bounds. */
951 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
953 tree nb_iters
= number_of_latch_executions (loop
);
955 if (!chrec_contains_symbols (nb_iters
))
958 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
959 scan_tree_for_params (region
, nb_iters
);
962 /* Find the parameters used in data accesses. */
963 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
964 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
966 nbp
= sese_nb_params (region
);
967 scop_set_nb_params (scop
, nbp
);
968 SESE_ADD_PARAMS (region
) = false;
972 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
974 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
975 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
976 isl_id_for_ssa_name (scop
, e
));
978 scop
->context
= isl_set_universe (space
);
982 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
983 the constraints for the surrounding loops. */
986 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
988 isl_set
*outer
, isl_set
**doms
)
990 tree nb_iters
= number_of_latch_executions (loop
);
991 sese region
= SCOP_REGION (scop
);
993 isl_set
*inner
= isl_set_copy (outer
);
996 int pos
= isl_set_dim (outer
, isl_dim_set
);
1003 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1004 space
= isl_set_get_space (inner
);
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 inner
= isl_set_add_constraint (inner
, c
);
1012 /* loop_i <= cst_nb_iters */
1013 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1015 c
= isl_inequality_alloc
1016 (isl_local_space_from_space (isl_space_copy (space
)));
1017 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1018 tree_int_to_gmp (nb_iters
, g
);
1019 isl_int_set_gmp (v
, g
);
1020 c
= isl_constraint_set_constant (c
, v
);
1021 inner
= isl_set_add_constraint (inner
, c
);
1024 /* loop_i <= expr_nb_iters */
1025 else if (!chrec_contains_undetermined (nb_iters
))
1030 isl_local_space
*ls
;
1034 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1036 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1037 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1038 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1039 isl_set_dim (valid
, isl_dim_set
));
1040 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1042 ls
= isl_local_space_from_space (isl_space_copy (space
));
1043 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1044 isl_dim_in
, pos
, 1);
1045 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1046 isl_pw_aff_copy (aff
));
1047 inner
= isl_set_intersect (inner
, le
);
1049 if (max_stmt_executions (loop
, &nit
))
1051 /* Insert in the context the constraints from the
1052 estimation of the number of iterations NIT and the
1053 symbolic number of iterations (involving parameter
1054 names) NB_ITERS. First, build the affine expression
1055 "NIT - NB_ITERS" and then say that it is positive,
1056 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1063 wi::to_mpz (nit
, g
, SIGNED
);
1064 mpz_sub_ui (g
, g
, 1);
1065 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1066 x
= isl_pw_aff_ge_set (approx
, aff
);
1067 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1068 isl_set_dim (x
, isl_dim_set
));
1069 scop
->context
= isl_set_intersect (scop
->context
, x
);
1071 c
= isl_inequality_alloc
1072 (isl_local_space_from_space (isl_space_copy (space
)));
1073 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1074 isl_int_set_gmp (v
, g
);
1076 c
= isl_constraint_set_constant (c
, v
);
1077 inner
= isl_set_add_constraint (inner
, c
);
1080 isl_pw_aff_free (aff
);
1085 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1086 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1087 isl_set_copy (inner
), doms
);
1091 && loop_in_sese_p (loop
->next
, region
))
1092 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1093 isl_set_copy (outer
), doms
);
1095 doms
[loop
->num
] = inner
;
1097 isl_set_free (outer
);
1098 isl_space_free (space
);
1103 /* Returns a linear expression for tree T evaluated in PBB. */
1106 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1108 scop_p scop
= PBB_SCOP (pbb
);
1110 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1111 gcc_assert (!automatically_generated_chrec_p (t
));
1113 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1116 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1117 operator. This allows us to invert the condition or to handle
1121 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1123 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1124 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1130 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1134 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1138 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1142 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1146 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1150 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1154 isl_pw_aff_free (lhs
);
1155 isl_pw_aff_free (rhs
);
1159 cond
= isl_set_coalesce (cond
);
1160 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1161 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1164 /* Add conditions to the domain of PBB. */
1167 add_conditions_to_domain (poly_bb_p pbb
)
1171 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1173 if (GBB_CONDITIONS (gbb
).is_empty ())
1176 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1177 switch (gimple_code (stmt
))
1181 enum tree_code code
= gimple_cond_code (stmt
);
1183 /* The conditions for ELSE-branches are inverted. */
1184 if (!GBB_CONDITION_CASES (gbb
)[i
])
1185 code
= invert_tree_comparison (code
, false);
1187 add_condition_to_pbb (pbb
, stmt
, code
);
1192 /* Switch statements are not supported right now - fall through. */
1200 /* Traverses all the GBBs of the SCOP and add their constraints to the
1201 iteration domains. */
1204 add_conditions_to_constraints (scop_p scop
)
1209 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1210 add_conditions_to_domain (pbb
);
1213 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1214 edge between BB and its predecessor is not a loop exit edge, and
1215 the last statement of the single predecessor is a COND_EXPR. */
1218 single_pred_cond_non_loop_exit (basic_block bb
)
1220 if (single_pred_p (bb
))
1222 edge e
= single_pred_edge (bb
);
1223 basic_block pred
= e
->src
;
1226 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1229 stmt
= last_stmt (pred
);
1231 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1238 class sese_dom_walker
: public dom_walker
1241 sese_dom_walker (cdi_direction
, sese
);
1243 virtual void before_dom_children (basic_block
);
1244 virtual void after_dom_children (basic_block
);
1247 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1251 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1252 : dom_walker (direction
), m_region (region
)
1256 /* Call-back for dom_walk executed before visiting the dominated
1260 sese_dom_walker::before_dom_children (basic_block bb
)
1265 if (!bb_in_sese_p (bb
, m_region
))
1268 stmt
= single_pred_cond_non_loop_exit (bb
);
1272 edge e
= single_pred_edge (bb
);
1274 m_conditions
.safe_push (stmt
);
1276 if (e
->flags
& EDGE_TRUE_VALUE
)
1277 m_cases
.safe_push (stmt
);
1279 m_cases
.safe_push (NULL
);
1282 gbb
= gbb_from_bb (bb
);
1286 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1287 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1291 /* Call-back for dom_walk executed after visiting the dominated
1295 sese_dom_walker::after_dom_children (basic_block bb
)
1297 if (!bb_in_sese_p (bb
, m_region
))
1300 if (single_pred_cond_non_loop_exit (bb
))
1302 m_conditions
.pop ();
1307 /* Add constraints on the possible values of parameter P from the type
1311 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1313 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1314 tree type
= TREE_TYPE (parameter
);
1315 tree lb
= NULL_TREE
;
1316 tree ub
= NULL_TREE
;
1318 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1319 lb
= lower_bound_in_type (type
, type
);
1321 lb
= TYPE_MIN_VALUE (type
);
1323 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1324 ub
= upper_bound_in_type (type
, type
);
1326 ub
= TYPE_MAX_VALUE (type
);
1330 isl_space
*space
= isl_set_get_space (scop
->context
);
1335 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1338 tree_int_to_gmp (lb
, g
);
1339 isl_int_set_gmp (v
, g
);
1342 c
= isl_constraint_set_constant (c
, v
);
1344 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1346 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1351 isl_space
*space
= isl_set_get_space (scop
->context
);
1356 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1360 tree_int_to_gmp (ub
, g
);
1361 isl_int_set_gmp (v
, g
);
1363 c
= isl_constraint_set_constant (c
, v
);
1365 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1367 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1371 /* Build the context of the SCOP. The context usually contains extra
1372 constraints that are added to the iteration domains that constrain
1376 build_scop_context (scop_p scop
)
1378 graphite_dim_t p
, n
= scop_nb_params (scop
);
1380 for (p
= 0; p
< n
; p
++)
1381 add_param_constraints (scop
, p
);
1384 /* Build the iteration domains: the loops belonging to the current
1385 SCOP, and that vary for the execution of the current basic block.
1386 Returns false if there is no loop in SCOP. */
1389 build_scop_iteration_domain (scop_p scop
)
1392 sese region
= SCOP_REGION (scop
);
1395 int nb_loops
= number_of_loops (cfun
);
1396 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1398 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1399 if (!loop_in_sese_p (loop_outer (loop
), region
))
1400 build_loop_iteration_domains (scop
, loop
, 0,
1401 isl_set_copy (scop
->context
), doms
);
1403 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1405 loop
= pbb_loop (pbb
);
1407 if (doms
[loop
->num
])
1408 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1410 pbb
->domain
= isl_set_copy (scop
->context
);
1412 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1413 isl_id_for_pbb (scop
, pbb
));
1416 for (i
= 0; i
< nb_loops
; i
++)
1418 isl_set_free (doms
[i
]);
1423 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1424 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1425 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1429 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1432 int alias_set_num
= 0;
1433 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1435 if (bap
&& bap
->alias_set
)
1436 alias_set_num
= *(bap
->alias_set
);
1438 c
= isl_equality_alloc
1439 (isl_local_space_from_space (isl_map_get_space (acc
)));
1440 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1441 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1443 return isl_map_add_constraint (acc
, c
);
1446 /* Assign the affine expression INDEX to the output dimension POS of
1447 MAP and return the result. */
1450 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1453 int len
= isl_map_dim (map
, isl_dim_out
);
1456 index_map
= isl_map_from_pw_aff (index
);
1457 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1458 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1460 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1461 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1462 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1463 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1465 return isl_map_intersect (map
, index_map
);
1468 /* Add to ACCESSES polyhedron equalities defining the access functions
1469 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1470 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1471 PBB is the poly_bb_p that contains the data reference DR. */
1474 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1476 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1477 scop_p scop
= PBB_SCOP (pbb
);
1479 for (i
= 0; i
< nb_subscripts
; i
++)
1482 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1484 aff
= extract_affine (scop
, afn
,
1485 isl_space_domain (isl_map_get_space (acc
)));
1486 acc
= set_index (acc
, i
+ 1, aff
);
1492 /* Add constrains representing the size of the accessed data to the
1493 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1494 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1498 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1500 tree ref
= DR_REF (dr
);
1501 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1503 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1507 if (TREE_CODE (ref
) != ARRAY_REF
)
1510 low
= array_ref_low_bound (ref
);
1511 high
= array_ref_up_bound (ref
);
1513 /* XXX The PPL code dealt separately with
1514 subscript - low >= 0 and high - subscript >= 0 in case one of
1515 the two bounds isn't known. Do the same here? */
1517 if (tree_fits_shwi_p (low
)
1519 && tree_fits_shwi_p (high
)
1520 /* 1-element arrays at end of structures may extend over
1521 their declared size. */
1522 && !(array_at_struct_end_p (ref
)
1523 && operand_equal_p (low
, high
, 0)))
1527 isl_set
*univ
, *lbs
, *ubs
;
1531 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1532 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1535 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1536 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1537 isl_set_dim (valid
, isl_dim_set
));
1538 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1540 space
= isl_set_get_space (extent
);
1541 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1542 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1543 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1544 index
= isl_pw_aff_alloc (univ
, aff
);
1546 id
= isl_set_get_tuple_id (extent
);
1547 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1548 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1550 /* low <= sub_i <= high */
1551 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1552 ubs
= isl_pw_aff_le_set (index
, ub
);
1553 extent
= isl_set_intersect (extent
, lbs
);
1554 extent
= isl_set_intersect (extent
, ubs
);
1561 /* Build data accesses for DR in PBB. */
1564 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1566 int dr_base_object_set
;
1569 scop_p scop
= PBB_SCOP (pbb
);
1572 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1573 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1574 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1575 isl_dim_out
, nb_out
);
1577 acc
= isl_map_universe (space
);
1578 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1581 acc
= pdr_add_alias_set (acc
, dr
);
1582 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1585 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1586 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1587 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1588 int alias_set_num
= 0;
1589 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1591 if (bap
&& bap
->alias_set
)
1592 alias_set_num
= *(bap
->alias_set
);
1594 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1595 extent
= isl_set_nat_universe (space
);
1596 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1597 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1600 gcc_assert (dr
->aux
);
1601 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1603 new_poly_dr (pbb
, dr_base_object_set
,
1604 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1605 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1608 /* Write to FILE the alias graph of data references in DIMACS format. */
1611 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1612 vec
<data_reference_p
> drs
)
1614 int num_vertex
= drs
.length ();
1616 data_reference_p dr1
, dr2
;
1619 if (num_vertex
== 0)
1622 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1623 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1624 if (dr_may_alias_p (dr1
, dr2
, true))
1627 fprintf (file
, "$\n");
1630 fprintf (file
, "c %s\n", comment
);
1632 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1634 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1635 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1636 if (dr_may_alias_p (dr1
, dr2
, true))
1637 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1642 /* Write to FILE the alias graph of data references in DOT format. */
1645 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1646 vec
<data_reference_p
> drs
)
1648 int num_vertex
= drs
.length ();
1649 data_reference_p dr1
, dr2
;
1652 if (num_vertex
== 0)
1655 fprintf (file
, "$\n");
1658 fprintf (file
, "c %s\n", comment
);
1660 /* First print all the vertices. */
1661 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1662 fprintf (file
, "n%d;\n", i
);
1664 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1665 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1666 if (dr_may_alias_p (dr1
, dr2
, true))
1667 fprintf (file
, "n%d n%d\n", i
, j
);
1672 /* Write to FILE the alias graph of data references in ECC format. */
1675 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1676 vec
<data_reference_p
> drs
)
1678 int num_vertex
= drs
.length ();
1679 data_reference_p dr1
, dr2
;
1682 if (num_vertex
== 0)
1685 fprintf (file
, "$\n");
1688 fprintf (file
, "c %s\n", comment
);
1690 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1691 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1692 if (dr_may_alias_p (dr1
, dr2
, true))
1693 fprintf (file
, "%d %d\n", i
, j
);
1698 /* Check if DR1 and DR2 are in the same object set. */
1701 dr_same_base_object_p (const struct data_reference
*dr1
,
1702 const struct data_reference
*dr2
)
1704 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1707 /* Uses DFS component number as representative of alias-sets. Also tests for
1708 optimality by verifying if every connected component is a clique. Returns
1709 true (1) if the above test is true, and false (0) otherwise. */
1712 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1714 int num_vertices
= drs
.length ();
1715 struct graph
*g
= new_graph (num_vertices
);
1716 data_reference_p dr1
, dr2
;
1718 int num_connected_components
;
1719 int v_indx1
, v_indx2
, num_vertices_in_component
;
1722 struct graph_edge
*e
;
1723 int this_component_is_clique
;
1724 int all_components_are_cliques
= 1;
1726 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1727 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1728 if (dr_may_alias_p (dr1
, dr2
, true))
1734 all_vertices
= XNEWVEC (int, num_vertices
);
1735 vertices
= XNEWVEC (int, num_vertices
);
1736 for (i
= 0; i
< num_vertices
; i
++)
1737 all_vertices
[i
] = i
;
1739 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1741 for (i
= 0; i
< g
->n_vertices
; i
++)
1743 data_reference_p dr
= drs
[i
];
1744 base_alias_pair
*bap
;
1746 gcc_assert (dr
->aux
);
1747 bap
= (base_alias_pair
*)(dr
->aux
);
1749 bap
->alias_set
= XNEW (int);
1750 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1753 /* Verify if the DFS numbering results in optimal solution. */
1754 for (i
= 0; i
< num_connected_components
; i
++)
1756 num_vertices_in_component
= 0;
1757 /* Get all vertices whose DFS component number is the same as i. */
1758 for (j
= 0; j
< num_vertices
; j
++)
1759 if (g
->vertices
[j
].component
== i
)
1760 vertices
[num_vertices_in_component
++] = j
;
1762 /* Now test if the vertices in 'vertices' form a clique, by testing
1763 for edges among each pair. */
1764 this_component_is_clique
= 1;
1765 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1767 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1769 /* Check if the two vertices are connected by iterating
1770 through all the edges which have one of these are source. */
1771 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1774 if (e
->src
== vertices
[v_indx1
])
1780 this_component_is_clique
= 0;
1784 if (!this_component_is_clique
)
1785 all_components_are_cliques
= 0;
1789 free (all_vertices
);
1792 return all_components_are_cliques
;
1795 /* Group each data reference in DRS with its base object set num. */
1798 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1800 int num_vertex
= drs
.length ();
1801 struct graph
*g
= new_graph (num_vertex
);
1802 data_reference_p dr1
, dr2
;
1806 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1807 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1808 if (dr_same_base_object_p (dr1
, dr2
))
1814 queue
= XNEWVEC (int, num_vertex
);
1815 for (i
= 0; i
< num_vertex
; i
++)
1818 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1820 for (i
= 0; i
< g
->n_vertices
; i
++)
1822 data_reference_p dr
= drs
[i
];
1823 base_alias_pair
*bap
;
1825 gcc_assert (dr
->aux
);
1826 bap
= (base_alias_pair
*)(dr
->aux
);
1828 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1835 /* Build the data references for PBB. */
1838 build_pbb_drs (poly_bb_p pbb
)
1841 data_reference_p dr
;
1842 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1844 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1845 build_poly_dr (dr
, pbb
);
1848 /* Dump to file the alias graphs for the data references in DRS. */
1851 dump_alias_graphs (vec
<data_reference_p
> drs
)
1854 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1856 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1859 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1860 current_function_name ());
1861 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1862 fclose (file_dimacs
);
1865 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1868 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1869 current_function_name ());
1870 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1874 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1877 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1878 current_function_name ());
1879 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1884 /* Build data references in SCOP. */
1887 build_scop_drs (scop_p scop
)
1891 data_reference_p dr
;
1892 auto_vec
<data_reference_p
, 3> drs
;
1894 /* Remove all the PBBs that do not have data references: these basic
1895 blocks are not handled in the polyhedral representation. */
1896 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1897 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1899 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1901 SCOP_BBS (scop
).ordered_remove (i
);
1905 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1906 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1909 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1910 dr
->aux
= XNEW (base_alias_pair
);
1912 if (!build_alias_set_optimal_p (drs
))
1914 /* TODO: Add support when building alias set is not optimal. */
1918 build_base_obj_set_for_drs (drs
);
1920 /* When debugging, enable the following code. This cannot be used
1921 in production compilers. */
1923 dump_alias_graphs (drs
);
1927 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1928 build_pbb_drs (pbb
);
1931 /* Return a gsi at the position of the phi node STMT. */
1933 static gimple_stmt_iterator
1934 gsi_for_phi_node (gimple stmt
)
1936 gimple_stmt_iterator psi
;
1937 basic_block bb
= gimple_bb (stmt
);
1939 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1940 if (stmt
== gsi_stmt (psi
))
1947 /* Analyze all the data references of STMTS and add them to the
1948 GBB_DATA_REFS vector of BB. */
1951 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1957 sese region
= SCOP_REGION (scop
);
1959 if (!bb_in_sese_p (bb
, region
))
1962 nest
= outermost_loop_in_sese_1 (region
, bb
);
1963 gbb
= gbb_from_bb (bb
);
1965 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1969 if (is_gimple_debug (stmt
))
1972 loop
= loop_containing_stmt (stmt
);
1973 if (!loop_in_sese_p (loop
, region
))
1976 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1977 &GBB_DATA_REFS (gbb
));
1981 /* Insert STMT at the end of the STMTS sequence and then insert the
1982 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1986 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1987 gimple_stmt_iterator insert_gsi
)
1989 gimple_stmt_iterator gsi
;
1990 auto_vec
<gimple
, 3> x
;
1992 gimple_seq_add_stmt (&stmts
, stmt
);
1993 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1994 x
.safe_push (gsi_stmt (gsi
));
1996 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1997 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2000 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2003 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2006 gimple_stmt_iterator gsi
;
2007 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2008 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2009 auto_vec
<gimple
, 3> x
;
2011 gimple_seq_add_stmt (&stmts
, stmt
);
2012 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2013 x
.safe_push (gsi_stmt (gsi
));
2015 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2017 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2018 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2022 gsi
= gsi_for_stmt (after_stmt
);
2023 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2026 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2029 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2032 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2034 vec
<data_reference_p
> drs
;
2036 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2037 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2038 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2039 int index
, n
= SCOP_BBS (scop
).length ();
2041 /* The INDEX of PBB in SCOP_BBS. */
2042 for (index
= 0; index
< n
; index
++)
2043 if (SCOP_BBS (scop
)[index
] == pbb
)
2046 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2047 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2048 isl_id_for_pbb (scop
, pbb1
));
2050 GBB_PBB (gbb1
) = pbb1
;
2051 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2052 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2053 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2056 /* Insert on edge E the assignment "RES := EXPR". */
2059 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2061 gimple_stmt_iterator gsi
;
2062 gimple_seq stmts
= NULL
;
2063 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2064 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2066 auto_vec
<gimple
, 3> x
;
2068 gimple_seq_add_stmt (&stmts
, stmt
);
2069 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2070 x
.safe_push (gsi_stmt (gsi
));
2072 gsi_insert_seq_on_edge (e
, stmts
);
2073 gsi_commit_edge_inserts ();
2074 bb
= gimple_bb (stmt
);
2076 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2079 if (!gbb_from_bb (bb
))
2080 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2082 analyze_drs_in_stmts (scop
, bb
, x
);
2085 /* Creates a zero dimension array of the same type as VAR. */
2088 create_zero_dim_array (tree var
, const char *base_name
)
2090 tree index_type
= build_index_type (integer_zero_node
);
2091 tree elt_type
= TREE_TYPE (var
);
2092 tree array_type
= build_array_type (elt_type
, index_type
);
2093 tree base
= create_tmp_var (array_type
, base_name
);
2095 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2099 /* Returns true when PHI is a loop close phi node. */
2102 scalar_close_phi_node_p (gimple phi
)
2104 if (gimple_code (phi
) != GIMPLE_PHI
2105 || virtual_operand_p (gimple_phi_result (phi
)))
2108 /* Note that loop close phi nodes should have a single argument
2109 because we translated the representation into a canonical form
2110 before Graphite: see canonicalize_loop_closed_ssa_form. */
2111 return (gimple_phi_num_args (phi
) == 1);
2114 /* For a definition DEF in REGION, propagates the expression EXPR in
2115 all the uses of DEF outside REGION. */
2118 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2120 imm_use_iterator imm_iter
;
2123 bool replaced_once
= false;
2125 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2127 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2130 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2131 if (!is_gimple_debug (use_stmt
)
2132 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2135 use_operand_p use_p
;
2137 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2138 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2139 && (replaced_once
= true))
2140 replace_exp (use_p
, expr
);
2142 update_stmt (use_stmt
);
2147 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2148 gsi_commit_edge_inserts ();
2152 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2153 dimension array for it. */
2156 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2158 sese region
= SCOP_REGION (scop
);
2159 gimple phi
= gsi_stmt (*psi
);
2160 tree res
= gimple_phi_result (phi
);
2161 basic_block bb
= gimple_bb (phi
);
2162 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2163 tree arg
= gimple_phi_arg_def (phi
, 0);
2166 /* Note that loop close phi nodes should have a single argument
2167 because we translated the representation into a canonical form
2168 before Graphite: see canonicalize_loop_closed_ssa_form. */
2169 gcc_assert (gimple_phi_num_args (phi
) == 1);
2171 /* The phi node can be a non close phi node, when its argument is
2172 invariant, or a default definition. */
2173 if (is_gimple_min_invariant (arg
)
2174 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2176 propagate_expr_outside_region (res
, arg
, region
);
2181 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2183 propagate_expr_outside_region (res
, arg
, region
);
2184 stmt
= gimple_build_assign (res
, arg
);
2185 remove_phi_node (psi
, false);
2186 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2190 /* If res is scev analyzable and is not a scalar value, it is safe
2191 to ignore the close phi node: it will be code generated in the
2192 out of Graphite pass. */
2193 else if (scev_analyzable_p (res
, region
))
2195 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2198 if (!loop_in_sese_p (loop
, region
))
2200 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2201 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2202 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2205 scev
= scalar_evolution_in_region (region
, loop
, res
);
2207 if (tree_does_not_contain_chrecs (scev
))
2208 propagate_expr_outside_region (res
, scev
, region
);
2215 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2217 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2219 if (TREE_CODE (arg
) == SSA_NAME
)
2220 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2221 SSA_NAME_DEF_STMT (arg
));
2223 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2224 zero_dim_array
, arg
);
2227 remove_phi_node (psi
, false);
2228 SSA_NAME_DEF_STMT (res
) = stmt
;
2230 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2233 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2234 dimension array for it. */
2237 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2240 gimple phi
= gsi_stmt (*psi
);
2241 basic_block bb
= gimple_bb (phi
);
2242 tree res
= gimple_phi_result (phi
);
2243 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2246 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2248 tree arg
= gimple_phi_arg_def (phi
, i
);
2249 edge e
= gimple_phi_arg_edge (phi
, i
);
2251 /* Avoid the insertion of code in the loop latch to please the
2252 pattern matching of the vectorizer. */
2253 if (TREE_CODE (arg
) == SSA_NAME
2254 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2255 && e
->src
== bb
->loop_father
->latch
)
2256 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2257 SSA_NAME_DEF_STMT (arg
));
2259 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2262 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2263 remove_phi_node (psi
, false);
2264 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2267 /* Rewrite the degenerate phi node at position PSI from the degenerate
2268 form "x = phi (y, y, ..., y)" to "x = y". */
2271 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2275 gimple_stmt_iterator gsi
;
2276 gimple phi
= gsi_stmt (*psi
);
2277 tree res
= gimple_phi_result (phi
);
2280 bb
= gimple_bb (phi
);
2281 rhs
= degenerate_phi_result (phi
);
2284 stmt
= gimple_build_assign (res
, rhs
);
2285 remove_phi_node (psi
, false);
2287 gsi
= gsi_after_labels (bb
);
2288 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2291 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2294 rewrite_reductions_out_of_ssa (scop_p scop
)
2297 gimple_stmt_iterator psi
;
2298 sese region
= SCOP_REGION (scop
);
2300 FOR_EACH_BB_FN (bb
, cfun
)
2301 if (bb_in_sese_p (bb
, region
))
2302 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2304 gimple phi
= gsi_stmt (psi
);
2306 if (virtual_operand_p (gimple_phi_result (phi
)))
2312 if (gimple_phi_num_args (phi
) > 1
2313 && degenerate_phi_result (phi
))
2314 rewrite_degenerate_phi (&psi
);
2316 else if (scalar_close_phi_node_p (phi
))
2317 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2319 else if (reduction_phi_p (region
, &psi
))
2320 rewrite_phi_out_of_ssa (scop
, &psi
);
2323 update_ssa (TODO_update_ssa
);
2324 #ifdef ENABLE_CHECKING
2325 verify_loop_closed_ssa (true);
2329 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2330 read from ZERO_DIM_ARRAY. */
2333 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2334 tree def
, gimple use_stmt
)
2339 use_operand_p use_p
;
2341 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2343 name
= copy_ssa_name (def
, NULL
);
2344 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2346 gimple_assign_set_lhs (name_stmt
, name
);
2347 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2349 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2350 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2351 replace_exp (use_p
, name
);
2353 update_stmt (use_stmt
);
2356 /* For every definition DEF in the SCOP that is used outside the scop,
2357 insert a closing-scop definition in the basic block just after this
2361 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2363 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2364 tree new_name
= make_ssa_name (var
, stmt
);
2365 bool needs_copy
= false;
2366 use_operand_p use_p
;
2367 imm_use_iterator imm_iter
;
2369 sese region
= SCOP_REGION (scop
);
2371 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2373 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2375 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2377 SET_USE (use_p
, new_name
);
2379 update_stmt (use_stmt
);
2384 /* Insert in the empty BB just after the scop a use of DEF such
2385 that the rewrite of cross_bb_scalar_dependences won't insert
2386 arrays everywhere else. */
2389 gimple assign
= gimple_build_assign (new_name
, def
);
2390 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2392 update_stmt (assign
);
2393 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2397 /* Rewrite the scalar dependences crossing the boundary of the BB
2398 containing STMT with an array. Return true when something has been
2402 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2404 sese region
= SCOP_REGION (scop
);
2405 gimple stmt
= gsi_stmt (*gsi
);
2406 imm_use_iterator imm_iter
;
2409 tree zero_dim_array
= NULL_TREE
;
2413 switch (gimple_code (stmt
))
2416 def
= gimple_assign_lhs (stmt
);
2420 def
= gimple_call_lhs (stmt
);
2428 || !is_gimple_reg (def
))
2431 if (scev_analyzable_p (def
, region
))
2433 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2434 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2436 if (tree_contains_chrecs (scev
, NULL
))
2439 propagate_expr_outside_region (def
, scev
, region
);
2443 def_bb
= gimple_bb (stmt
);
2445 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2447 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2448 if (gimple_code (use_stmt
) == GIMPLE_PHI
2451 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2453 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2454 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2456 rewrite_phi_out_of_ssa (scop
, &psi
);
2459 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2460 if (gimple_code (use_stmt
) != GIMPLE_PHI
2461 && def_bb
!= gimple_bb (use_stmt
)
2462 && !is_gimple_debug (use_stmt
)
2465 if (!zero_dim_array
)
2467 zero_dim_array
= create_zero_dim_array
2468 (def
, "Cross_BB_scalar_dependence");
2469 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2470 SSA_NAME_DEF_STMT (def
));
2474 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2481 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2484 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2487 gimple_stmt_iterator psi
;
2488 sese region
= SCOP_REGION (scop
);
2489 bool changed
= false;
2491 /* Create an extra empty BB after the scop. */
2492 split_edge (SESE_EXIT (region
));
2494 FOR_EACH_BB_FN (bb
, cfun
)
2495 if (bb_in_sese_p (bb
, region
))
2496 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2497 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2502 update_ssa (TODO_update_ssa
);
2503 #ifdef ENABLE_CHECKING
2504 verify_loop_closed_ssa (true);
2509 /* Returns the number of pbbs that are in loops contained in SCOP. */
2512 nb_pbbs_in_loops (scop_p scop
)
2518 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2519 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2525 /* Return the number of data references in BB that write in
2529 nb_data_writes_in_bb (basic_block bb
)
2532 gimple_stmt_iterator gsi
;
2534 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2535 if (gimple_vdef (gsi_stmt (gsi
)))
2541 /* Splits at STMT the basic block BB represented as PBB in the
2545 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2547 edge e1
= split_block (bb
, stmt
);
2548 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2552 /* Splits STMT out of its current BB. This is done for reduction
2553 statements for which we want to ignore data dependences. */
2556 split_reduction_stmt (scop_p scop
, gimple stmt
)
2558 basic_block bb
= gimple_bb (stmt
);
2559 poly_bb_p pbb
= pbb_from_bb (bb
);
2560 gimple_bb_p gbb
= gbb_from_bb (bb
);
2563 data_reference_p dr
;
2565 /* Do not split basic blocks with no writes to memory: the reduction
2566 will be the only write to memory. */
2567 if (nb_data_writes_in_bb (bb
) == 0
2568 /* Or if we have already marked BB as a reduction. */
2569 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2572 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2574 /* Split once more only when the reduction stmt is not the only one
2575 left in the original BB. */
2576 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2578 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2580 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2583 /* A part of the data references will end in a different basic block
2584 after the split: move the DRs from the original GBB to the newly
2586 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2588 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2592 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2593 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2594 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2602 /* Return true when stmt is a reduction operation. */
2605 is_reduction_operation_p (gimple stmt
)
2607 enum tree_code code
;
2609 gcc_assert (is_gimple_assign (stmt
));
2610 code
= gimple_assign_rhs_code (stmt
);
2612 return flag_associative_math
2613 && commutative_tree_code (code
)
2614 && associative_tree_code (code
);
2617 /* Returns true when PHI contains an argument ARG. */
2620 phi_contains_arg (gimple phi
, tree arg
)
2624 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2625 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2631 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2634 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2638 if (TREE_CODE (arg
) != SSA_NAME
)
2641 stmt
= SSA_NAME_DEF_STMT (arg
);
2643 if (gimple_code (stmt
) == GIMPLE_NOP
2644 || gimple_code (stmt
) == GIMPLE_CALL
)
2647 if (gimple_code (stmt
) == GIMPLE_PHI
)
2649 if (phi_contains_arg (stmt
, lhs
))
2654 if (!is_gimple_assign (stmt
))
2657 if (gimple_num_ops (stmt
) == 2)
2658 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2660 if (is_reduction_operation_p (stmt
))
2662 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2665 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2671 /* Detect commutative and associative scalar reductions starting at
2672 the STMT. Return the phi node of the reduction cycle, or NULL. */
2675 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2679 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2684 in
->safe_push (stmt
);
2685 out
->safe_push (stmt
);
2689 /* Detect commutative and associative scalar reductions starting at
2690 STMT. Return the phi node of the reduction cycle, or NULL. */
2693 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2696 tree lhs
= gimple_assign_lhs (stmt
);
2698 if (gimple_num_ops (stmt
) == 2)
2699 return detect_commutative_reduction_arg (lhs
, stmt
,
2700 gimple_assign_rhs1 (stmt
),
2703 if (is_reduction_operation_p (stmt
))
2705 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2706 gimple_assign_rhs1 (stmt
),
2709 : detect_commutative_reduction_arg (lhs
, stmt
,
2710 gimple_assign_rhs2 (stmt
),
2717 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2720 follow_inital_value_to_phi (tree arg
, tree lhs
)
2724 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2727 stmt
= SSA_NAME_DEF_STMT (arg
);
2729 if (gimple_code (stmt
) == GIMPLE_PHI
2730 && phi_contains_arg (stmt
, lhs
))
2737 /* Return the argument of the loop PHI that is the initial value coming
2738 from outside the loop. */
2741 edge_initial_value_for_loop_phi (gimple phi
)
2745 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2747 edge e
= gimple_phi_arg_edge (phi
, i
);
2749 if (loop_depth (e
->src
->loop_father
)
2750 < loop_depth (e
->dest
->loop_father
))
2757 /* Return the argument of the loop PHI that is the initial value coming
2758 from outside the loop. */
2761 initial_value_for_loop_phi (gimple phi
)
2765 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2767 edge e
= gimple_phi_arg_edge (phi
, i
);
2769 if (loop_depth (e
->src
->loop_father
)
2770 < loop_depth (e
->dest
->loop_father
))
2771 return gimple_phi_arg_def (phi
, i
);
2777 /* Returns true when DEF is used outside the reduction cycle of
2781 used_outside_reduction (tree def
, gimple loop_phi
)
2783 use_operand_p use_p
;
2784 imm_use_iterator imm_iter
;
2785 loop_p loop
= loop_containing_stmt (loop_phi
);
2787 /* In LOOP, DEF should be used only in LOOP_PHI. */
2788 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2790 gimple stmt
= USE_STMT (use_p
);
2792 if (stmt
!= loop_phi
2793 && !is_gimple_debug (stmt
)
2794 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2801 /* Detect commutative and associative scalar reductions belonging to
2802 the SCOP starting at the loop closed phi node STMT. Return the phi
2803 node of the reduction cycle, or NULL. */
2806 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2809 if (scalar_close_phi_node_p (stmt
))
2811 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2812 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2814 if (TREE_CODE (arg
) != SSA_NAME
)
2817 /* Note that loop close phi nodes should have a single argument
2818 because we translated the representation into a canonical form
2819 before Graphite: see canonicalize_loop_closed_ssa_form. */
2820 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2822 def
= SSA_NAME_DEF_STMT (arg
);
2823 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2824 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2827 lhs
= gimple_phi_result (close_phi
);
2828 init
= initial_value_for_loop_phi (loop_phi
);
2829 phi
= follow_inital_value_to_phi (init
, lhs
);
2831 if (phi
&& (used_outside_reduction (lhs
, phi
)
2832 || !has_single_use (gimple_phi_result (phi
))))
2835 in
->safe_push (loop_phi
);
2836 out
->safe_push (close_phi
);
2840 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2841 return detect_commutative_reduction_assign (stmt
, in
, out
);
2846 /* Translate the scalar reduction statement STMT to an array RED
2847 knowing that its recursive phi node is LOOP_PHI. */
2850 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2851 gimple stmt
, gimple loop_phi
)
2853 tree res
= gimple_phi_result (loop_phi
);
2854 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2855 gimple_stmt_iterator gsi
;
2857 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2859 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2860 gsi
= gsi_for_stmt (stmt
);
2862 insert_stmts (scop
, assign
, NULL
, gsi
);
2865 /* Removes the PHI node and resets all the debug stmts that are using
2869 remove_phi (gimple phi
)
2871 imm_use_iterator imm_iter
;
2873 use_operand_p use_p
;
2874 gimple_stmt_iterator gsi
;
2875 auto_vec
<gimple
, 3> update
;
2879 def
= PHI_RESULT (phi
);
2880 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2882 stmt
= USE_STMT (use_p
);
2884 if (is_gimple_debug (stmt
))
2886 gimple_debug_bind_reset_value (stmt
);
2887 update
.safe_push (stmt
);
2891 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2894 gsi
= gsi_for_phi_node (phi
);
2895 remove_phi_node (&gsi
, false);
2898 /* Helper function for for_each_index. For each INDEX of the data
2899 reference REF, returns true when its indices are valid in the loop
2900 nest LOOP passed in as DATA. */
2903 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2906 basic_block header
, def_bb
;
2909 if (TREE_CODE (*index
) != SSA_NAME
)
2912 loop
= *((loop_p
*) data
);
2913 header
= loop
->header
;
2914 stmt
= SSA_NAME_DEF_STMT (*index
);
2919 def_bb
= gimple_bb (stmt
);
2924 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2927 /* When the result of a CLOSE_PHI is written to a memory location,
2928 return a pointer to that memory reference, otherwise return
2932 close_phi_written_to_memory (gimple close_phi
)
2934 imm_use_iterator imm_iter
;
2935 use_operand_p use_p
;
2937 tree res
, def
= gimple_phi_result (close_phi
);
2939 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2940 if ((stmt
= USE_STMT (use_p
))
2941 && gimple_code (stmt
) == GIMPLE_ASSIGN
2942 && (res
= gimple_assign_lhs (stmt
)))
2944 switch (TREE_CODE (res
))
2954 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2955 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2957 /* FIXME: this restriction is for id-{24,25}.f and
2958 could be handled by duplicating the computation of
2959 array indices before the loop of the close_phi. */
2960 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2972 /* Rewrite out of SSA the reduction described by the loop phi nodes
2973 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2976 IN: stmt, loop_n, ..., loop_0
2977 OUT: stmt, close_n, ..., close_0
2979 the first element is the reduction statement, and the next elements
2980 are the loop and close phi nodes of each of the outer loops. */
2983 translate_scalar_reduction_to_array (scop_p scop
,
2988 unsigned int i
= out
.length () - 1;
2989 tree red
= close_phi_written_to_memory (out
[i
]);
2991 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2993 gimple close_phi
= out
[i
];
2997 gimple stmt
= loop_phi
;
2998 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2999 poly_bb_p pbb
= pbb_from_bb (bb
);
3000 PBB_IS_REDUCTION (pbb
) = true;
3001 gcc_assert (close_phi
== loop_phi
);
3004 red
= create_zero_dim_array
3005 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3007 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3011 if (i
== in
.length () - 1)
3013 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3014 unshare_expr (red
), close_phi
);
3015 insert_out_of_ssa_copy_on_edge
3016 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3017 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3020 remove_phi (loop_phi
);
3021 remove_phi (close_phi
);
3025 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3026 true when something has been changed. */
3029 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3033 auto_vec
<gimple
, 10> in
;
3034 auto_vec
<gimple
, 10> out
;
3036 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3037 res
= in
.length () > 1;
3039 translate_scalar_reduction_to_array (scop
, in
, out
);
3044 /* Rewrites all the commutative reductions from LOOP out of SSA.
3045 Returns true when something has been changed. */
3048 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3051 gimple_stmt_iterator gsi
;
3052 edge exit
= single_exit (loop
);
3054 bool changed
= false;
3059 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3060 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3061 && !virtual_operand_p (res
)
3062 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3063 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3064 (scop
, gsi_stmt (gsi
));
3069 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3072 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3075 bool changed
= false;
3076 sese region
= SCOP_REGION (scop
);
3078 FOR_EACH_LOOP (loop
, 0)
3079 if (loop_in_sese_p (loop
, region
))
3080 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3085 gsi_commit_edge_inserts ();
3086 update_ssa (TODO_update_ssa
);
3087 #ifdef ENABLE_CHECKING
3088 verify_loop_closed_ssa (true);
3093 /* Can all ivs be represented by a signed integer?
3094 As CLooG might generate negative values in its expressions, signed loop ivs
3095 are required in the backend. */
3098 scop_ivs_can_be_represented (scop_p scop
)
3101 gimple_stmt_iterator psi
;
3104 FOR_EACH_LOOP (loop
, 0)
3106 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3109 for (psi
= gsi_start_phis (loop
->header
);
3110 !gsi_end_p (psi
); gsi_next (&psi
))
3112 gimple phi
= gsi_stmt (psi
);
3113 tree res
= PHI_RESULT (phi
);
3114 tree type
= TREE_TYPE (res
);
3116 if (TYPE_UNSIGNED (type
)
3117 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3130 /* Builds the polyhedral representation for a SESE region. */
3133 build_poly_scop (scop_p scop
)
3135 sese region
= SCOP_REGION (scop
);
3136 graphite_dim_t max_dim
;
3138 build_scop_bbs (scop
);
3140 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3141 Once CLooG is fixed, remove this guard. Anyways, it makes no
3142 sense to optimize a scop containing only PBBs that do not belong
3144 if (nb_pbbs_in_loops (scop
) == 0)
3147 if (!scop_ivs_can_be_represented (scop
))
3150 if (flag_associative_math
)
3151 rewrite_commutative_reductions_out_of_ssa (scop
);
3153 build_sese_loop_nests (region
);
3154 /* Record all conditions in REGION. */
3155 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3156 find_scop_parameters (scop
);
3158 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3159 if (scop_nb_params (scop
) > max_dim
)
3162 build_scop_iteration_domain (scop
);
3163 build_scop_context (scop
);
3164 add_conditions_to_constraints (scop
);
3166 /* Rewrite out of SSA only after having translated the
3167 representation to the polyhedral representation to avoid scev
3168 analysis failures. That means that these functions will insert
3169 new data references that they create in the right place. */
3170 rewrite_reductions_out_of_ssa (scop
);
3171 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3173 build_scop_drs (scop
);
3175 build_scop_scattering (scop
);
3177 /* This SCoP has been translated to the polyhedral
3179 POLY_SCOP_P (scop
) = true;