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>
30 /* For C++ linkage of C functions.
31 Missing from isl/val_gmp.h in isl 0.12 versions.
32 Appearing in isl/val_gmp.h in isl 0.13.
33 To be removed when passing to isl 0.13. */
34 #if defined(__cplusplus)
37 #include <isl/val_gmp.h>
38 #if defined(__cplusplus)
44 #include "coretypes.h"
52 #include "hard-reg-set.h"
55 #include "dominance.h"
57 #include "basic-block.h"
58 #include "tree-ssa-alias.h"
59 #include "internal-fn.h"
60 #include "gimple-expr.h"
63 #include "gimple-iterator.h"
65 #include "gimplify-me.h"
66 #include "gimple-ssa.h"
68 #include "tree-phinodes.h"
69 #include "ssa-iterators.h"
70 #include "stringpool.h"
71 #include "tree-ssanames.h"
72 #include "tree-ssa-loop-manip.h"
73 #include "tree-ssa-loop-niter.h"
74 #include "tree-ssa-loop.h"
75 #include "tree-into-ssa.h"
76 #include "tree-pass.h"
78 #include "tree-chrec.h"
79 #include "tree-data-ref.h"
80 #include "tree-scalar-evolution.h"
83 #include "tree-ssa-propagate.h"
87 #include "graphite-poly.h"
88 #include "graphite-sese-to-poly.h"
91 /* Assigns to RES the value of the INTEGER_CST T. */
94 tree_int_to_gmp (tree t
, mpz_t res
)
96 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
99 /* Returns the index of the PHI argument defined in the outermost
103 phi_arg_in_outermost_loop (gphi
*phi
)
105 loop_p loop
= gimple_bb (phi
)->loop_father
;
108 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
109 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
111 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
118 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
119 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
122 remove_simple_copy_phi (gphi_iterator
*psi
)
124 gphi
*phi
= psi
->phi ();
125 tree res
= gimple_phi_result (phi
);
126 size_t entry
= phi_arg_in_outermost_loop (phi
);
127 tree init
= gimple_phi_arg_def (phi
, entry
);
128 gassign
*stmt
= gimple_build_assign (res
, init
);
129 edge e
= gimple_phi_arg_edge (phi
, entry
);
131 remove_phi_node (psi
, false);
132 gsi_insert_on_edge_immediate (e
, stmt
);
135 /* Removes an invariant phi node at position PSI by inserting on the
136 loop ENTRY edge the assignment RES = INIT. */
139 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
141 gphi
*phi
= psi
->phi ();
142 loop_p loop
= loop_containing_stmt (phi
);
143 tree res
= gimple_phi_result (phi
);
144 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
145 size_t entry
= phi_arg_in_outermost_loop (phi
);
146 edge e
= gimple_phi_arg_edge (phi
, entry
);
149 gimple_seq stmts
= NULL
;
151 if (tree_contains_chrecs (scev
, NULL
))
152 scev
= gimple_phi_arg_def (phi
, entry
);
154 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
155 stmt
= gimple_build_assign (res
, var
);
156 remove_phi_node (psi
, false);
158 gimple_seq_add_stmt (&stmts
, stmt
);
159 gsi_insert_seq_on_edge (e
, stmts
);
160 gsi_commit_edge_inserts ();
161 SSA_NAME_DEF_STMT (res
) = stmt
;
164 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
167 simple_copy_phi_p (gphi
*phi
)
171 if (gimple_phi_num_args (phi
) != 2)
174 res
= gimple_phi_result (phi
);
175 return (res
== gimple_phi_arg_def (phi
, 0)
176 || res
== gimple_phi_arg_def (phi
, 1));
179 /* Returns true when the phi node at position PSI is a reduction phi
180 node in REGION. Otherwise moves the pointer PSI to the next phi to
184 reduction_phi_p (sese region
, gphi_iterator
*psi
)
187 gphi
*phi
= psi
->phi ();
188 tree res
= gimple_phi_result (phi
);
190 loop
= loop_containing_stmt (phi
);
192 if (simple_copy_phi_p (phi
))
194 /* PRE introduces phi nodes like these, for an example,
195 see id-5.f in the fortran graphite testsuite:
197 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
199 remove_simple_copy_phi (psi
);
203 if (scev_analyzable_p (res
, region
))
205 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
207 if (evolution_function_is_invariant_p (scev
, loop
->num
))
208 remove_invariant_phi (region
, psi
);
215 /* All the other cases are considered reductions. */
219 /* Store the GRAPHITE representation of BB. */
222 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
224 struct gimple_bb
*gbb
;
226 gbb
= XNEW (struct gimple_bb
);
229 GBB_DATA_REFS (gbb
) = drs
;
230 GBB_CONDITIONS (gbb
).create (0);
231 GBB_CONDITION_CASES (gbb
).create (0);
237 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
240 struct data_reference
*dr
;
242 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
245 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
247 free (bap
->alias_set
);
256 free_gimple_bb (struct gimple_bb
*gbb
)
258 free_data_refs_aux (GBB_DATA_REFS (gbb
));
259 free_data_refs (GBB_DATA_REFS (gbb
));
261 GBB_CONDITIONS (gbb
).release ();
262 GBB_CONDITION_CASES (gbb
).release ();
263 GBB_BB (gbb
)->aux
= 0;
267 /* Deletes all gimple bbs in SCOP. */
270 remove_gbbs_in_scop (scop_p scop
)
275 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
276 free_gimple_bb (PBB_BLACK_BOX (pbb
));
279 /* Deletes all scops in SCOPS. */
282 free_scops (vec
<scop_p
> scops
)
287 FOR_EACH_VEC_ELT (scops
, i
, scop
)
289 remove_gbbs_in_scop (scop
);
290 free_sese (SCOP_REGION (scop
));
297 /* Same as outermost_loop_in_sese, returns the outermost loop
298 containing BB in REGION, but makes sure that the returned loop
299 belongs to the REGION, and so this returns the first loop in the
300 REGION when the loop containing BB does not belong to REGION. */
303 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
305 loop_p nest
= outermost_loop_in_sese (region
, bb
);
307 if (loop_in_sese_p (nest
, region
))
310 /* When the basic block BB does not belong to a loop in the region,
311 return the first loop in the region. */
314 if (loop_in_sese_p (nest
, region
))
323 /* Generates a polyhedral black box only if the bb contains interesting
327 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
329 vec
<data_reference_p
> drs
;
331 sese region
= SCOP_REGION (scop
);
332 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
333 gimple_stmt_iterator gsi
;
335 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
337 gimple stmt
= gsi_stmt (gsi
);
340 if (is_gimple_debug (stmt
))
343 loop
= loop_containing_stmt (stmt
);
344 if (!loop_in_sese_p (loop
, region
))
347 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
350 return new_gimple_bb (bb
, drs
);
353 /* Returns true if all predecessors of BB, that are not dominated by BB, are
354 marked in MAP. The predecessors dominated by BB are loop latches and will
355 be handled after BB. */
358 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
363 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
364 if (!bitmap_bit_p (map
, e
->src
->index
)
365 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
371 /* Compare the depth of two basic_block's P1 and P2. */
374 compare_bb_depths (const void *p1
, const void *p2
)
376 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
377 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
378 int d1
= loop_depth (bb1
->loop_father
);
379 int d2
= loop_depth (bb2
->loop_father
);
390 /* Sort the basic blocks from DOM such that the first are the ones at
391 a deepest loop level. */
394 graphite_sort_dominated_info (vec
<basic_block
> dom
)
396 dom
.qsort (compare_bb_depths
);
399 /* Recursive helper function for build_scops_bbs. */
402 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
404 sese region
= SCOP_REGION (scop
);
405 vec
<basic_block
> dom
;
408 if (bitmap_bit_p (visited
, bb
->index
)
409 || !bb_in_sese_p (bb
, region
))
412 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
413 SCOP_BBS (scop
).safe_push (pbb
);
414 bitmap_set_bit (visited
, bb
->index
);
416 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
421 graphite_sort_dominated_info (dom
);
423 while (!dom
.is_empty ())
428 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
429 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
431 build_scop_bbs_1 (scop
, visited
, dom_bb
);
432 dom
.unordered_remove (i
);
440 /* Gather the basic blocks belonging to the SCOP. */
443 build_scop_bbs (scop_p scop
)
445 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
446 sese region
= SCOP_REGION (scop
);
448 bitmap_clear (visited
);
449 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
450 sbitmap_free (visited
);
453 /* Return an ISL identifier for the polyhedral basic block PBB. */
456 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
459 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
460 return isl_id_alloc (s
->ctx
, name
, pbb
);
463 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
464 We generate SCATTERING_DIMENSIONS scattering dimensions.
466 CLooG 0.15.0 and previous versions require, that all
467 scattering functions of one CloogProgram have the same number of
468 scattering dimensions, therefore we allow to specify it. This
469 should be removed in future versions of CLooG.
471 The scattering polyhedron consists of these dimensions: scattering,
472 loop_iterators, parameters.
476 | scattering_dimensions = 5
477 | used_scattering_dimensions = 3
485 | Scattering polyhedron:
487 | scattering: {s1, s2, s3, s4, s5}
488 | loop_iterators: {i}
489 | parameters: {p1, p2}
491 | s1 s2 s3 s4 s5 i p1 p2 1
492 | 1 0 0 0 0 0 0 0 -4 = 0
493 | 0 1 0 0 0 -1 0 0 0 = 0
494 | 0 0 1 0 0 0 0 0 -5 = 0 */
497 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
498 poly_bb_p pbb
, int scattering_dimensions
)
501 int nb_iterators
= pbb_dim_iter_domain (pbb
);
502 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
506 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
508 dc
= isl_set_get_space (pbb
->domain
);
509 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
510 isl_dim_out
, scattering_dimensions
);
511 pbb
->schedule
= isl_map_universe (dm
);
513 for (i
= 0; i
< scattering_dimensions
; i
++)
515 /* Textual order inside this loop. */
518 isl_constraint
*c
= isl_equality_alloc
519 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
521 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
523 val
= isl_val_neg (val
);
524 c
= isl_constraint_set_constant_val (c
, val
);
525 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
526 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
529 /* Iterations of this loop. */
530 else /* if ((i % 2) == 1) */
532 int loop
= (i
- 1) / 2;
533 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
538 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
541 /* Build for BB the static schedule.
543 The static schedule is a Dewey numbering of the abstract syntax
544 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
546 The following example informally defines the static schedule:
565 Static schedules for A to F:
578 build_scop_scattering (scop_p scop
)
582 gimple_bb_p previous_gbb
= NULL
;
583 isl_space
*dc
= isl_set_get_space (scop
->context
);
584 isl_aff
*static_sched
;
586 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
587 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
589 /* We have to start schedules at 0 on the first component and
590 because we cannot compare_prefix_loops against a previous loop,
591 prefix will be equal to zero, and that index will be
592 incremented before copying. */
593 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
595 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
597 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
599 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
602 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
608 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
610 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
613 isl_aff_free (static_sched
);
616 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
618 /* Extract an affine expression from the chain of recurrence E. */
621 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
623 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
624 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
625 isl_local_space
*ls
= isl_local_space_from_space (space
);
626 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
627 isl_aff
*loop
= isl_aff_set_coefficient_si
628 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
629 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
631 /* Before multiplying, make sure that the result is affine. */
632 gcc_assert (isl_pw_aff_is_cst (rhs
)
633 || isl_pw_aff_is_cst (l
));
635 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
638 /* Extract an affine expression from the mult_expr E. */
641 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
643 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
644 isl_space_copy (space
));
645 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
647 if (!isl_pw_aff_is_cst (lhs
)
648 && !isl_pw_aff_is_cst (rhs
))
650 isl_pw_aff_free (lhs
);
651 isl_pw_aff_free (rhs
);
655 return isl_pw_aff_mul (lhs
, rhs
);
658 /* Return an ISL identifier from the name of the ssa_name E. */
661 isl_id_for_ssa_name (scop_p s
, tree e
)
663 const char *name
= get_name (e
);
667 id
= isl_id_alloc (s
->ctx
, name
, e
);
671 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
672 id
= isl_id_alloc (s
->ctx
, name1
, e
);
678 /* Return an ISL identifier for the data reference DR. */
681 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
683 /* Data references all get the same isl_id. They need to be comparable
684 and are distinguished through the first dimension, which contains the
686 return isl_id_alloc (s
->ctx
, "", 0);
689 /* Extract an affine expression from the ssa_name E. */
692 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
699 id
= isl_id_for_ssa_name (s
, e
);
700 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
702 dom
= isl_set_universe (isl_space_copy (space
));
703 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
704 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
705 return isl_pw_aff_alloc (dom
, aff
);
708 /* Extract an affine expression from the gmp constant G. */
711 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
713 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
714 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
715 isl_set
*dom
= isl_set_universe (space
);
719 ct
= isl_aff_get_ctx (aff
);
720 v
= isl_val_int_from_gmp (ct
, g
);
721 aff
= isl_aff_add_constant_val (aff
, v
);
723 return isl_pw_aff_alloc (dom
, aff
);
726 /* Extract an affine expression from the integer_cst E. */
729 extract_affine_int (tree e
, __isl_take isl_space
*space
)
735 tree_int_to_gmp (e
, g
);
736 res
= extract_affine_gmp (g
, space
);
742 /* Compute pwaff mod 2^width. */
744 extern isl_ctx
*the_isl_ctx
;
747 wrap (isl_pw_aff
*pwaff
, unsigned width
)
751 mod
= isl_val_int_from_ui(the_isl_ctx
, width
);
752 mod
= isl_val_2exp (mod
);
753 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
758 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
759 Otherwise returns -1. */
762 parameter_index_in_region_1 (tree name
, sese region
)
767 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
769 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
776 /* When the parameter NAME is in REGION, returns its index in
777 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
778 and returns the index of NAME. */
781 parameter_index_in_region (tree name
, sese region
)
785 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
787 i
= parameter_index_in_region_1 (name
, region
);
791 gcc_assert (SESE_ADD_PARAMS (region
));
793 i
= SESE_PARAMS (region
).length ();
794 SESE_PARAMS (region
).safe_push (name
);
798 /* Extract an affine expression from the tree E in the scop S. */
801 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
803 isl_pw_aff
*lhs
, *rhs
, *res
;
806 if (e
== chrec_dont_know
) {
807 isl_space_free (space
);
811 switch (TREE_CODE (e
))
813 case POLYNOMIAL_CHREC
:
814 res
= extract_affine_chrec (s
, e
, space
);
818 res
= extract_affine_mul (s
, e
, space
);
822 case POINTER_PLUS_EXPR
:
823 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
824 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
825 res
= isl_pw_aff_add (lhs
, rhs
);
829 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
830 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
831 res
= isl_pw_aff_sub (lhs
, rhs
);
836 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
837 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
838 res
= isl_pw_aff_mul (lhs
, rhs
);
842 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
843 res
= extract_affine_name (s
, e
, space
);
847 res
= extract_affine_int (e
, space
);
848 /* No need to wrap a single integer. */
852 case NON_LVALUE_EXPR
:
853 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
861 type
= TREE_TYPE (e
);
862 if (TYPE_UNSIGNED (type
))
863 res
= wrap (res
, TYPE_PRECISION (type
));
868 /* In the context of sese S, scan the expression E and translate it to
869 a linear expression C. When parsing a symbolic multiplication, K
870 represents the constant multiplier of an expression containing
874 scan_tree_for_params (sese s
, tree e
)
876 if (e
== chrec_dont_know
)
879 switch (TREE_CODE (e
))
881 case POLYNOMIAL_CHREC
:
882 scan_tree_for_params (s
, CHREC_LEFT (e
));
886 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
887 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
889 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
893 case POINTER_PLUS_EXPR
:
895 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
896 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
902 case NON_LVALUE_EXPR
:
903 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
907 parameter_index_in_region (e
, s
);
920 /* Find parameters with respect to REGION in BB. We are looking in memory
921 access functions, conditions and loop bounds. */
924 find_params_in_bb (sese region
, gimple_bb_p gbb
)
930 loop_p loop
= GBB_BB (gbb
)->loop_father
;
932 /* Find parameters in the access functions of data references. */
933 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
934 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
935 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
937 /* Find parameters in conditional statements. */
938 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
940 tree lhs
= scalar_evolution_in_region (region
, loop
,
941 gimple_cond_lhs (stmt
));
942 tree rhs
= scalar_evolution_in_region (region
, loop
,
943 gimple_cond_rhs (stmt
));
945 scan_tree_for_params (region
, lhs
);
946 scan_tree_for_params (region
, rhs
);
950 /* Record the parameters used in the SCOP. A variable is a parameter
951 in a scop if it does not vary during the execution of that scop. */
954 find_scop_parameters (scop_p scop
)
958 sese region
= SCOP_REGION (scop
);
962 /* Find the parameters used in the loop bounds. */
963 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
965 tree nb_iters
= number_of_latch_executions (loop
);
967 if (!chrec_contains_symbols (nb_iters
))
970 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
971 scan_tree_for_params (region
, nb_iters
);
974 /* Find the parameters used in data accesses. */
975 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
976 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
978 nbp
= sese_nb_params (region
);
979 scop_set_nb_params (scop
, nbp
);
980 SESE_ADD_PARAMS (region
) = false;
984 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
986 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
987 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
988 isl_id_for_ssa_name (scop
, e
));
990 scop
->context
= isl_set_universe (space
);
994 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
995 the constraints for the surrounding loops. */
998 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1000 isl_set
*outer
, isl_set
**doms
)
1002 tree nb_iters
= number_of_latch_executions (loop
);
1003 sese region
= SCOP_REGION (scop
);
1005 isl_set
*inner
= isl_set_copy (outer
);
1008 int pos
= isl_set_dim (outer
, isl_dim_set
);
1014 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1015 space
= isl_set_get_space (inner
);
1018 c
= isl_inequality_alloc
1019 (isl_local_space_from_space (isl_space_copy (space
)));
1020 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1021 inner
= isl_set_add_constraint (inner
, c
);
1023 /* loop_i <= cst_nb_iters */
1024 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1026 c
= isl_inequality_alloc
1027 (isl_local_space_from_space (isl_space_copy (space
)));
1028 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1029 tree_int_to_gmp (nb_iters
, g
);
1030 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1031 c
= isl_constraint_set_constant_val (c
, v
);
1032 inner
= isl_set_add_constraint (inner
, c
);
1035 /* loop_i <= expr_nb_iters */
1036 else if (!chrec_contains_undetermined (nb_iters
))
1041 isl_local_space
*ls
;
1045 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1047 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1048 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1049 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1050 isl_set_dim (valid
, isl_dim_set
));
1051 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1053 ls
= isl_local_space_from_space (isl_space_copy (space
));
1054 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1055 isl_dim_in
, pos
, 1);
1056 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1057 isl_pw_aff_copy (aff
));
1058 inner
= isl_set_intersect (inner
, le
);
1060 if (max_stmt_executions (loop
, &nit
))
1062 /* Insert in the context the constraints from the
1063 estimation of the number of iterations NIT and the
1064 symbolic number of iterations (involving parameter
1065 names) NB_ITERS. First, build the affine expression
1066 "NIT - NB_ITERS" and then say that it is positive,
1067 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1074 wi::to_mpz (nit
, g
, SIGNED
);
1075 mpz_sub_ui (g
, g
, 1);
1076 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1077 x
= isl_pw_aff_ge_set (approx
, aff
);
1078 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1079 isl_set_dim (x
, isl_dim_set
));
1080 scop
->context
= isl_set_intersect (scop
->context
, x
);
1082 c
= isl_inequality_alloc
1083 (isl_local_space_from_space (isl_space_copy (space
)));
1084 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1085 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1087 c
= isl_constraint_set_constant_val (c
, v
);
1088 inner
= isl_set_add_constraint (inner
, c
);
1091 isl_pw_aff_free (aff
);
1096 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1097 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1098 isl_set_copy (inner
), doms
);
1102 && loop_in_sese_p (loop
->next
, region
))
1103 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1104 isl_set_copy (outer
), doms
);
1106 doms
[loop
->num
] = inner
;
1108 isl_set_free (outer
);
1109 isl_space_free (space
);
1113 /* Returns a linear expression for tree T evaluated in PBB. */
1116 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1118 scop_p scop
= PBB_SCOP (pbb
);
1120 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1121 gcc_assert (!automatically_generated_chrec_p (t
));
1123 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1126 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1127 operator. This allows us to invert the condition or to handle
1131 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1133 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1134 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1140 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1144 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1148 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1152 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1156 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1160 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1164 isl_pw_aff_free (lhs
);
1165 isl_pw_aff_free (rhs
);
1169 cond
= isl_set_coalesce (cond
);
1170 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1171 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1174 /* Add conditions to the domain of PBB. */
1177 add_conditions_to_domain (poly_bb_p pbb
)
1181 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1183 if (GBB_CONDITIONS (gbb
).is_empty ())
1186 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1187 switch (gimple_code (stmt
))
1191 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1192 enum tree_code code
= gimple_cond_code (cond_stmt
);
1194 /* The conditions for ELSE-branches are inverted. */
1195 if (!GBB_CONDITION_CASES (gbb
)[i
])
1196 code
= invert_tree_comparison (code
, false);
1198 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1203 /* Switch statements are not supported right now - fall through. */
1211 /* Traverses all the GBBs of the SCOP and add their constraints to the
1212 iteration domains. */
1215 add_conditions_to_constraints (scop_p scop
)
1220 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1221 add_conditions_to_domain (pbb
);
1224 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1225 edge between BB and its predecessor is not a loop exit edge, and
1226 the last statement of the single predecessor is a COND_EXPR. */
1229 single_pred_cond_non_loop_exit (basic_block bb
)
1231 if (single_pred_p (bb
))
1233 edge e
= single_pred_edge (bb
);
1234 basic_block pred
= e
->src
;
1237 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1240 stmt
= last_stmt (pred
);
1242 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1243 return as_a
<gcond
*> (stmt
);
1249 class sese_dom_walker
: public dom_walker
1252 sese_dom_walker (cdi_direction
, sese
);
1254 virtual void before_dom_children (basic_block
);
1255 virtual void after_dom_children (basic_block
);
1258 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1262 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1263 : dom_walker (direction
), m_region (region
)
1267 /* Call-back for dom_walk executed before visiting the dominated
1271 sese_dom_walker::before_dom_children (basic_block bb
)
1276 if (!bb_in_sese_p (bb
, m_region
))
1279 stmt
= single_pred_cond_non_loop_exit (bb
);
1283 edge e
= single_pred_edge (bb
);
1285 m_conditions
.safe_push (stmt
);
1287 if (e
->flags
& EDGE_TRUE_VALUE
)
1288 m_cases
.safe_push (stmt
);
1290 m_cases
.safe_push (NULL
);
1293 gbb
= gbb_from_bb (bb
);
1297 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1298 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1302 /* Call-back for dom_walk executed after visiting the dominated
1306 sese_dom_walker::after_dom_children (basic_block bb
)
1308 if (!bb_in_sese_p (bb
, m_region
))
1311 if (single_pred_cond_non_loop_exit (bb
))
1313 m_conditions
.pop ();
1318 /* Add constraints on the possible values of parameter P from the type
1322 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1324 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1325 tree type
= TREE_TYPE (parameter
);
1326 tree lb
= NULL_TREE
;
1327 tree ub
= NULL_TREE
;
1329 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1330 lb
= lower_bound_in_type (type
, type
);
1332 lb
= TYPE_MIN_VALUE (type
);
1334 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1335 ub
= upper_bound_in_type (type
, type
);
1337 ub
= TYPE_MAX_VALUE (type
);
1341 isl_space
*space
= isl_set_get_space (scop
->context
);
1346 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1348 tree_int_to_gmp (lb
, g
);
1349 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1350 v
= isl_val_neg (v
);
1352 c
= isl_constraint_set_constant_val (c
, v
);
1353 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1355 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1360 isl_space
*space
= isl_set_get_space (scop
->context
);
1365 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1368 tree_int_to_gmp (ub
, g
);
1369 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1371 c
= isl_constraint_set_constant_val (c
, v
);
1372 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1374 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1378 /* Build the context of the SCOP. The context usually contains extra
1379 constraints that are added to the iteration domains that constrain
1383 build_scop_context (scop_p scop
)
1385 graphite_dim_t p
, n
= scop_nb_params (scop
);
1387 for (p
= 0; p
< n
; p
++)
1388 add_param_constraints (scop
, p
);
1391 /* Build the iteration domains: the loops belonging to the current
1392 SCOP, and that vary for the execution of the current basic block.
1393 Returns false if there is no loop in SCOP. */
1396 build_scop_iteration_domain (scop_p scop
)
1399 sese region
= SCOP_REGION (scop
);
1402 int nb_loops
= number_of_loops (cfun
);
1403 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1405 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1406 if (!loop_in_sese_p (loop_outer (loop
), region
))
1407 build_loop_iteration_domains (scop
, loop
, 0,
1408 isl_set_copy (scop
->context
), doms
);
1410 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1412 loop
= pbb_loop (pbb
);
1414 if (doms
[loop
->num
])
1415 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1417 pbb
->domain
= isl_set_copy (scop
->context
);
1419 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1420 isl_id_for_pbb (scop
, pbb
));
1423 for (i
= 0; i
< nb_loops
; i
++)
1425 isl_set_free (doms
[i
]);
1430 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1431 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1432 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1436 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1439 int alias_set_num
= 0;
1440 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1442 if (bap
&& bap
->alias_set
)
1443 alias_set_num
= *(bap
->alias_set
);
1445 c
= isl_equality_alloc
1446 (isl_local_space_from_space (isl_map_get_space (acc
)));
1447 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1448 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1450 return isl_map_add_constraint (acc
, c
);
1453 /* Assign the affine expression INDEX to the output dimension POS of
1454 MAP and return the result. */
1457 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1460 int len
= isl_map_dim (map
, isl_dim_out
);
1463 index_map
= isl_map_from_pw_aff (index
);
1464 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1465 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1467 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1468 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1469 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1470 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1472 return isl_map_intersect (map
, index_map
);
1475 /* Add to ACCESSES polyhedron equalities defining the access functions
1476 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1477 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1478 PBB is the poly_bb_p that contains the data reference DR. */
1481 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1483 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1484 scop_p scop
= PBB_SCOP (pbb
);
1486 for (i
= 0; i
< nb_subscripts
; i
++)
1489 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1491 aff
= extract_affine (scop
, afn
,
1492 isl_space_domain (isl_map_get_space (acc
)));
1493 acc
= set_index (acc
, i
+ 1, aff
);
1499 /* Add constrains representing the size of the accessed data to the
1500 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1501 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1505 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1507 tree ref
= DR_REF (dr
);
1508 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1510 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1514 if (TREE_CODE (ref
) != ARRAY_REF
)
1517 low
= array_ref_low_bound (ref
);
1518 high
= array_ref_up_bound (ref
);
1520 /* XXX The PPL code dealt separately with
1521 subscript - low >= 0 and high - subscript >= 0 in case one of
1522 the two bounds isn't known. Do the same here? */
1524 if (tree_fits_shwi_p (low
)
1526 && tree_fits_shwi_p (high
)
1527 /* 1-element arrays at end of structures may extend over
1528 their declared size. */
1529 && !(array_at_struct_end_p (ref
)
1530 && operand_equal_p (low
, high
, 0)))
1534 isl_set
*univ
, *lbs
, *ubs
;
1538 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1539 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1542 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1543 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1544 isl_set_dim (valid
, isl_dim_set
));
1545 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1547 space
= isl_set_get_space (extent
);
1548 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1549 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1550 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1551 index
= isl_pw_aff_alloc (univ
, aff
);
1553 id
= isl_set_get_tuple_id (extent
);
1554 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1555 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1557 /* low <= sub_i <= high */
1558 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1559 ubs
= isl_pw_aff_le_set (index
, ub
);
1560 extent
= isl_set_intersect (extent
, lbs
);
1561 extent
= isl_set_intersect (extent
, ubs
);
1568 /* Build data accesses for DR in PBB. */
1571 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1573 int dr_base_object_set
;
1576 scop_p scop
= PBB_SCOP (pbb
);
1579 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1580 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1581 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1582 isl_dim_out
, nb_out
);
1584 acc
= isl_map_universe (space
);
1585 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1588 acc
= pdr_add_alias_set (acc
, dr
);
1589 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1592 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1593 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1594 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1595 int alias_set_num
= 0;
1596 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1598 if (bap
&& bap
->alias_set
)
1599 alias_set_num
= *(bap
->alias_set
);
1601 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1602 extent
= isl_set_nat_universe (space
);
1603 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1604 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1607 gcc_assert (dr
->aux
);
1608 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1610 new_poly_dr (pbb
, dr_base_object_set
,
1611 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1612 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1615 /* Write to FILE the alias graph of data references in DIMACS format. */
1618 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1619 vec
<data_reference_p
> drs
)
1621 int num_vertex
= drs
.length ();
1623 data_reference_p dr1
, dr2
;
1626 if (num_vertex
== 0)
1629 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1630 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1631 if (dr_may_alias_p (dr1
, dr2
, true))
1634 fprintf (file
, "$\n");
1637 fprintf (file
, "c %s\n", comment
);
1639 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1641 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1642 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1643 if (dr_may_alias_p (dr1
, dr2
, true))
1644 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1649 /* Write to FILE the alias graph of data references in DOT format. */
1652 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1653 vec
<data_reference_p
> drs
)
1655 int num_vertex
= drs
.length ();
1656 data_reference_p dr1
, dr2
;
1659 if (num_vertex
== 0)
1662 fprintf (file
, "$\n");
1665 fprintf (file
, "c %s\n", comment
);
1667 /* First print all the vertices. */
1668 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1669 fprintf (file
, "n%d;\n", i
);
1671 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1672 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1673 if (dr_may_alias_p (dr1
, dr2
, true))
1674 fprintf (file
, "n%d n%d\n", i
, j
);
1679 /* Write to FILE the alias graph of data references in ECC format. */
1682 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1683 vec
<data_reference_p
> drs
)
1685 int num_vertex
= drs
.length ();
1686 data_reference_p dr1
, dr2
;
1689 if (num_vertex
== 0)
1692 fprintf (file
, "$\n");
1695 fprintf (file
, "c %s\n", comment
);
1697 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1698 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1699 if (dr_may_alias_p (dr1
, dr2
, true))
1700 fprintf (file
, "%d %d\n", i
, j
);
1705 /* Check if DR1 and DR2 are in the same object set. */
1708 dr_same_base_object_p (const struct data_reference
*dr1
,
1709 const struct data_reference
*dr2
)
1711 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1714 /* Uses DFS component number as representative of alias-sets. Also tests for
1715 optimality by verifying if every connected component is a clique. Returns
1716 true (1) if the above test is true, and false (0) otherwise. */
1719 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1721 int num_vertices
= drs
.length ();
1722 struct graph
*g
= new_graph (num_vertices
);
1723 data_reference_p dr1
, dr2
;
1725 int num_connected_components
;
1726 int v_indx1
, v_indx2
, num_vertices_in_component
;
1729 struct graph_edge
*e
;
1730 int this_component_is_clique
;
1731 int all_components_are_cliques
= 1;
1733 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1734 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1735 if (dr_may_alias_p (dr1
, dr2
, true))
1741 all_vertices
= XNEWVEC (int, num_vertices
);
1742 vertices
= XNEWVEC (int, num_vertices
);
1743 for (i
= 0; i
< num_vertices
; i
++)
1744 all_vertices
[i
] = i
;
1746 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1748 for (i
= 0; i
< g
->n_vertices
; i
++)
1750 data_reference_p dr
= drs
[i
];
1751 base_alias_pair
*bap
;
1753 gcc_assert (dr
->aux
);
1754 bap
= (base_alias_pair
*)(dr
->aux
);
1756 bap
->alias_set
= XNEW (int);
1757 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1760 /* Verify if the DFS numbering results in optimal solution. */
1761 for (i
= 0; i
< num_connected_components
; i
++)
1763 num_vertices_in_component
= 0;
1764 /* Get all vertices whose DFS component number is the same as i. */
1765 for (j
= 0; j
< num_vertices
; j
++)
1766 if (g
->vertices
[j
].component
== i
)
1767 vertices
[num_vertices_in_component
++] = j
;
1769 /* Now test if the vertices in 'vertices' form a clique, by testing
1770 for edges among each pair. */
1771 this_component_is_clique
= 1;
1772 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1774 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1776 /* Check if the two vertices are connected by iterating
1777 through all the edges which have one of these are source. */
1778 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1781 if (e
->src
== vertices
[v_indx1
])
1787 this_component_is_clique
= 0;
1791 if (!this_component_is_clique
)
1792 all_components_are_cliques
= 0;
1796 free (all_vertices
);
1799 return all_components_are_cliques
;
1802 /* Group each data reference in DRS with its base object set num. */
1805 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1807 int num_vertex
= drs
.length ();
1808 struct graph
*g
= new_graph (num_vertex
);
1809 data_reference_p dr1
, dr2
;
1813 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1814 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1815 if (dr_same_base_object_p (dr1
, dr2
))
1821 queue
= XNEWVEC (int, num_vertex
);
1822 for (i
= 0; i
< num_vertex
; i
++)
1825 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1827 for (i
= 0; i
< g
->n_vertices
; i
++)
1829 data_reference_p dr
= drs
[i
];
1830 base_alias_pair
*bap
;
1832 gcc_assert (dr
->aux
);
1833 bap
= (base_alias_pair
*)(dr
->aux
);
1835 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1842 /* Build the data references for PBB. */
1845 build_pbb_drs (poly_bb_p pbb
)
1848 data_reference_p dr
;
1849 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1851 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1852 build_poly_dr (dr
, pbb
);
1855 /* Dump to file the alias graphs for the data references in DRS. */
1858 dump_alias_graphs (vec
<data_reference_p
> drs
)
1861 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1863 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1866 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1867 current_function_name ());
1868 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1869 fclose (file_dimacs
);
1872 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1875 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1876 current_function_name ());
1877 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1881 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1884 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1885 current_function_name ());
1886 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1891 /* Build data references in SCOP. */
1894 build_scop_drs (scop_p scop
)
1898 data_reference_p dr
;
1899 auto_vec
<data_reference_p
, 3> drs
;
1901 /* Remove all the PBBs that do not have data references: these basic
1902 blocks are not handled in the polyhedral representation. */
1903 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1904 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1906 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1908 SCOP_BBS (scop
).ordered_remove (i
);
1912 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1913 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1916 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1917 dr
->aux
= XNEW (base_alias_pair
);
1919 if (!build_alias_set_optimal_p (drs
))
1921 /* TODO: Add support when building alias set is not optimal. */
1925 build_base_obj_set_for_drs (drs
);
1927 /* When debugging, enable the following code. This cannot be used
1928 in production compilers. */
1930 dump_alias_graphs (drs
);
1934 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1935 build_pbb_drs (pbb
);
1938 /* Return a gsi at the position of the phi node STMT. */
1940 static gphi_iterator
1941 gsi_for_phi_node (gphi
*stmt
)
1944 basic_block bb
= gimple_bb (stmt
);
1946 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1947 if (stmt
== psi
.phi ())
1954 /* Analyze all the data references of STMTS and add them to the
1955 GBB_DATA_REFS vector of BB. */
1958 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1964 sese region
= SCOP_REGION (scop
);
1966 if (!bb_in_sese_p (bb
, region
))
1969 nest
= outermost_loop_in_sese_1 (region
, bb
);
1970 gbb
= gbb_from_bb (bb
);
1972 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1976 if (is_gimple_debug (stmt
))
1979 loop
= loop_containing_stmt (stmt
);
1980 if (!loop_in_sese_p (loop
, region
))
1983 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1984 &GBB_DATA_REFS (gbb
));
1988 /* Insert STMT at the end of the STMTS sequence and then insert the
1989 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1993 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1994 gimple_stmt_iterator insert_gsi
)
1996 gimple_stmt_iterator gsi
;
1997 auto_vec
<gimple
, 3> x
;
1999 gimple_seq_add_stmt (&stmts
, stmt
);
2000 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2001 x
.safe_push (gsi_stmt (gsi
));
2003 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2004 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2007 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2010 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2013 gimple_stmt_iterator gsi
;
2014 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2015 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2016 auto_vec
<gimple
, 3> x
;
2018 gimple_seq_add_stmt (&stmts
, stmt
);
2019 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2020 x
.safe_push (gsi_stmt (gsi
));
2022 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2024 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2025 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2029 gsi
= gsi_for_stmt (after_stmt
);
2030 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2033 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2036 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2039 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2041 vec
<data_reference_p
> drs
;
2043 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2044 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2045 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2046 int index
, n
= SCOP_BBS (scop
).length ();
2048 /* The INDEX of PBB in SCOP_BBS. */
2049 for (index
= 0; index
< n
; index
++)
2050 if (SCOP_BBS (scop
)[index
] == pbb
)
2053 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2054 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2055 isl_id_for_pbb (scop
, pbb1
));
2057 GBB_PBB (gbb1
) = pbb1
;
2058 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2059 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2060 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2063 /* Insert on edge E the assignment "RES := EXPR". */
2066 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2068 gimple_stmt_iterator gsi
;
2069 gimple_seq stmts
= NULL
;
2070 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2071 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2073 auto_vec
<gimple
, 3> x
;
2075 gimple_seq_add_stmt (&stmts
, stmt
);
2076 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2077 x
.safe_push (gsi_stmt (gsi
));
2079 gsi_insert_seq_on_edge (e
, stmts
);
2080 gsi_commit_edge_inserts ();
2081 bb
= gimple_bb (stmt
);
2083 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2086 if (!gbb_from_bb (bb
))
2087 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2089 analyze_drs_in_stmts (scop
, bb
, x
);
2092 /* Creates a zero dimension array of the same type as VAR. */
2095 create_zero_dim_array (tree var
, const char *base_name
)
2097 tree index_type
= build_index_type (integer_zero_node
);
2098 tree elt_type
= TREE_TYPE (var
);
2099 tree array_type
= build_array_type (elt_type
, index_type
);
2100 tree base
= create_tmp_var (array_type
, base_name
);
2102 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2106 /* Returns true when PHI is a loop close phi node. */
2109 scalar_close_phi_node_p (gimple phi
)
2111 if (gimple_code (phi
) != GIMPLE_PHI
2112 || virtual_operand_p (gimple_phi_result (phi
)))
2115 /* Note that loop close phi nodes should have a single argument
2116 because we translated the representation into a canonical form
2117 before Graphite: see canonicalize_loop_closed_ssa_form. */
2118 return (gimple_phi_num_args (phi
) == 1);
2121 /* For a definition DEF in REGION, propagates the expression EXPR in
2122 all the uses of DEF outside REGION. */
2125 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2127 imm_use_iterator imm_iter
;
2130 bool replaced_once
= false;
2132 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2134 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2137 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2138 if (!is_gimple_debug (use_stmt
)
2139 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2142 use_operand_p use_p
;
2144 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2145 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2146 && (replaced_once
= true))
2147 replace_exp (use_p
, expr
);
2149 update_stmt (use_stmt
);
2154 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2155 gsi_commit_edge_inserts ();
2159 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2160 dimension array for it. */
2163 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2165 sese region
= SCOP_REGION (scop
);
2166 gimple phi
= gsi_stmt (*psi
);
2167 tree res
= gimple_phi_result (phi
);
2168 basic_block bb
= gimple_bb (phi
);
2169 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2170 tree arg
= gimple_phi_arg_def (phi
, 0);
2173 /* Note that loop close phi nodes should have a single argument
2174 because we translated the representation into a canonical form
2175 before Graphite: see canonicalize_loop_closed_ssa_form. */
2176 gcc_assert (gimple_phi_num_args (phi
) == 1);
2178 /* The phi node can be a non close phi node, when its argument is
2179 invariant, or a default definition. */
2180 if (is_gimple_min_invariant (arg
)
2181 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2183 propagate_expr_outside_region (res
, arg
, region
);
2188 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2190 propagate_expr_outside_region (res
, arg
, region
);
2191 stmt
= gimple_build_assign (res
, arg
);
2192 remove_phi_node (psi
, false);
2193 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2197 /* If res is scev analyzable and is not a scalar value, it is safe
2198 to ignore the close phi node: it will be code generated in the
2199 out of Graphite pass. */
2200 else if (scev_analyzable_p (res
, region
))
2202 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2205 if (!loop_in_sese_p (loop
, region
))
2207 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2208 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2209 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2212 scev
= scalar_evolution_in_region (region
, loop
, res
);
2214 if (tree_does_not_contain_chrecs (scev
))
2215 propagate_expr_outside_region (res
, scev
, region
);
2222 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2224 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2226 if (TREE_CODE (arg
) == SSA_NAME
)
2227 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2228 SSA_NAME_DEF_STMT (arg
));
2230 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2231 zero_dim_array
, arg
);
2234 remove_phi_node (psi
, false);
2235 SSA_NAME_DEF_STMT (res
) = stmt
;
2237 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2240 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2241 dimension array for it. */
2244 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2247 gphi
*phi
= psi
->phi ();
2248 basic_block bb
= gimple_bb (phi
);
2249 tree res
= gimple_phi_result (phi
);
2250 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2253 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2255 tree arg
= gimple_phi_arg_def (phi
, i
);
2256 edge e
= gimple_phi_arg_edge (phi
, i
);
2258 /* Avoid the insertion of code in the loop latch to please the
2259 pattern matching of the vectorizer. */
2260 if (TREE_CODE (arg
) == SSA_NAME
2261 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2262 && e
->src
== bb
->loop_father
->latch
)
2263 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2264 SSA_NAME_DEF_STMT (arg
));
2266 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2269 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2270 remove_phi_node (psi
, false);
2271 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2274 /* Rewrite the degenerate phi node at position PSI from the degenerate
2275 form "x = phi (y, y, ..., y)" to "x = y". */
2278 rewrite_degenerate_phi (gphi_iterator
*psi
)
2282 gimple_stmt_iterator gsi
;
2283 gphi
*phi
= psi
->phi ();
2284 tree res
= gimple_phi_result (phi
);
2287 bb
= gimple_bb (phi
);
2288 rhs
= degenerate_phi_result (phi
);
2291 stmt
= gimple_build_assign (res
, rhs
);
2292 remove_phi_node (psi
, false);
2294 gsi
= gsi_after_labels (bb
);
2295 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2298 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2301 rewrite_reductions_out_of_ssa (scop_p scop
)
2305 sese region
= SCOP_REGION (scop
);
2307 FOR_EACH_BB_FN (bb
, cfun
)
2308 if (bb_in_sese_p (bb
, region
))
2309 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2311 gphi
*phi
= psi
.phi ();
2313 if (virtual_operand_p (gimple_phi_result (phi
)))
2319 if (gimple_phi_num_args (phi
) > 1
2320 && degenerate_phi_result (phi
))
2321 rewrite_degenerate_phi (&psi
);
2323 else if (scalar_close_phi_node_p (phi
))
2324 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2326 else if (reduction_phi_p (region
, &psi
))
2327 rewrite_phi_out_of_ssa (scop
, &psi
);
2330 update_ssa (TODO_update_ssa
);
2331 #ifdef ENABLE_CHECKING
2332 verify_loop_closed_ssa (true);
2336 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2337 read from ZERO_DIM_ARRAY. */
2340 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2341 tree def
, gimple use_stmt
)
2346 use_operand_p use_p
;
2348 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2350 name
= copy_ssa_name (def
, NULL
);
2351 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2353 gimple_assign_set_lhs (name_stmt
, name
);
2354 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2356 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2357 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2358 replace_exp (use_p
, name
);
2360 update_stmt (use_stmt
);
2363 /* For every definition DEF in the SCOP that is used outside the scop,
2364 insert a closing-scop definition in the basic block just after this
2368 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2370 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2371 tree new_name
= make_ssa_name (var
, stmt
);
2372 bool needs_copy
= false;
2373 use_operand_p use_p
;
2374 imm_use_iterator imm_iter
;
2376 sese region
= SCOP_REGION (scop
);
2378 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2380 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2382 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2384 SET_USE (use_p
, new_name
);
2386 update_stmt (use_stmt
);
2391 /* Insert in the empty BB just after the scop a use of DEF such
2392 that the rewrite of cross_bb_scalar_dependences won't insert
2393 arrays everywhere else. */
2396 gimple assign
= gimple_build_assign (new_name
, def
);
2397 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2399 update_stmt (assign
);
2400 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2404 /* Rewrite the scalar dependences crossing the boundary of the BB
2405 containing STMT with an array. Return true when something has been
2409 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2411 sese region
= SCOP_REGION (scop
);
2412 gimple stmt
= gsi_stmt (*gsi
);
2413 imm_use_iterator imm_iter
;
2416 tree zero_dim_array
= NULL_TREE
;
2420 switch (gimple_code (stmt
))
2423 def
= gimple_assign_lhs (stmt
);
2427 def
= gimple_call_lhs (stmt
);
2435 || !is_gimple_reg (def
))
2438 if (scev_analyzable_p (def
, region
))
2440 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2441 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2443 if (tree_contains_chrecs (scev
, NULL
))
2446 propagate_expr_outside_region (def
, scev
, region
);
2450 def_bb
= gimple_bb (stmt
);
2452 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2454 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2455 if (gimple_code (use_stmt
) == GIMPLE_PHI
2458 gphi_iterator psi
= gsi_start_phis (gimple_bb (use_stmt
));
2460 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2461 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2463 rewrite_phi_out_of_ssa (scop
, &psi
);
2466 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2467 if (gimple_code (use_stmt
) != GIMPLE_PHI
2468 && def_bb
!= gimple_bb (use_stmt
)
2469 && !is_gimple_debug (use_stmt
)
2472 if (!zero_dim_array
)
2474 zero_dim_array
= create_zero_dim_array
2475 (def
, "Cross_BB_scalar_dependence");
2476 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2477 SSA_NAME_DEF_STMT (def
));
2481 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2488 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2491 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2494 gimple_stmt_iterator psi
;
2495 sese region
= SCOP_REGION (scop
);
2496 bool changed
= false;
2498 /* Create an extra empty BB after the scop. */
2499 split_edge (SESE_EXIT (region
));
2501 FOR_EACH_BB_FN (bb
, cfun
)
2502 if (bb_in_sese_p (bb
, region
))
2503 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2504 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2509 update_ssa (TODO_update_ssa
);
2510 #ifdef ENABLE_CHECKING
2511 verify_loop_closed_ssa (true);
2516 /* Returns the number of pbbs that are in loops contained in SCOP. */
2519 nb_pbbs_in_loops (scop_p scop
)
2525 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2526 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2532 /* Return the number of data references in BB that write in
2536 nb_data_writes_in_bb (basic_block bb
)
2539 gimple_stmt_iterator gsi
;
2541 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2542 if (gimple_vdef (gsi_stmt (gsi
)))
2548 /* Splits at STMT the basic block BB represented as PBB in the
2552 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2554 edge e1
= split_block (bb
, stmt
);
2555 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2559 /* Splits STMT out of its current BB. This is done for reduction
2560 statements for which we want to ignore data dependences. */
2563 split_reduction_stmt (scop_p scop
, gimple stmt
)
2565 basic_block bb
= gimple_bb (stmt
);
2566 poly_bb_p pbb
= pbb_from_bb (bb
);
2567 gimple_bb_p gbb
= gbb_from_bb (bb
);
2570 data_reference_p dr
;
2572 /* Do not split basic blocks with no writes to memory: the reduction
2573 will be the only write to memory. */
2574 if (nb_data_writes_in_bb (bb
) == 0
2575 /* Or if we have already marked BB as a reduction. */
2576 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2579 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2581 /* Split once more only when the reduction stmt is not the only one
2582 left in the original BB. */
2583 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2585 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2587 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2590 /* A part of the data references will end in a different basic block
2591 after the split: move the DRs from the original GBB to the newly
2593 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2595 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2599 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2600 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2601 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2609 /* Return true when stmt is a reduction operation. */
2612 is_reduction_operation_p (gimple stmt
)
2614 enum tree_code code
;
2616 gcc_assert (is_gimple_assign (stmt
));
2617 code
= gimple_assign_rhs_code (stmt
);
2619 return flag_associative_math
2620 && commutative_tree_code (code
)
2621 && associative_tree_code (code
);
2624 /* Returns true when PHI contains an argument ARG. */
2627 phi_contains_arg (gphi
*phi
, tree arg
)
2631 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2632 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2638 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2641 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2645 if (TREE_CODE (arg
) != SSA_NAME
)
2648 stmt
= SSA_NAME_DEF_STMT (arg
);
2650 if (gimple_code (stmt
) == GIMPLE_NOP
2651 || gimple_code (stmt
) == GIMPLE_CALL
)
2654 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2656 if (phi_contains_arg (phi
, lhs
))
2661 if (!is_gimple_assign (stmt
))
2664 if (gimple_num_ops (stmt
) == 2)
2665 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2667 if (is_reduction_operation_p (stmt
))
2670 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2673 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2679 /* Detect commutative and associative scalar reductions starting at
2680 the STMT. Return the phi node of the reduction cycle, or NULL. */
2683 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2687 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2692 in
->safe_push (stmt
);
2693 out
->safe_push (stmt
);
2697 /* Detect commutative and associative scalar reductions starting at
2698 STMT. Return the phi node of the reduction cycle, or NULL. */
2701 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2704 tree lhs
= gimple_assign_lhs (stmt
);
2706 if (gimple_num_ops (stmt
) == 2)
2707 return detect_commutative_reduction_arg (lhs
, stmt
,
2708 gimple_assign_rhs1 (stmt
),
2711 if (is_reduction_operation_p (stmt
))
2713 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2714 gimple_assign_rhs1 (stmt
),
2717 : detect_commutative_reduction_arg (lhs
, stmt
,
2718 gimple_assign_rhs2 (stmt
),
2725 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2728 follow_inital_value_to_phi (tree arg
, tree lhs
)
2732 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2735 stmt
= SSA_NAME_DEF_STMT (arg
);
2737 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2738 if (phi_contains_arg (phi
, lhs
))
2745 /* Return the argument of the loop PHI that is the initial value coming
2746 from outside the loop. */
2749 edge_initial_value_for_loop_phi (gphi
*phi
)
2753 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2755 edge e
= gimple_phi_arg_edge (phi
, i
);
2757 if (loop_depth (e
->src
->loop_father
)
2758 < loop_depth (e
->dest
->loop_father
))
2765 /* Return the argument of the loop PHI that is the initial value coming
2766 from outside the loop. */
2769 initial_value_for_loop_phi (gphi
*phi
)
2773 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2775 edge e
= gimple_phi_arg_edge (phi
, i
);
2777 if (loop_depth (e
->src
->loop_father
)
2778 < loop_depth (e
->dest
->loop_father
))
2779 return gimple_phi_arg_def (phi
, i
);
2785 /* Returns true when DEF is used outside the reduction cycle of
2789 used_outside_reduction (tree def
, gimple loop_phi
)
2791 use_operand_p use_p
;
2792 imm_use_iterator imm_iter
;
2793 loop_p loop
= loop_containing_stmt (loop_phi
);
2795 /* In LOOP, DEF should be used only in LOOP_PHI. */
2796 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2798 gimple stmt
= USE_STMT (use_p
);
2800 if (stmt
!= loop_phi
2801 && !is_gimple_debug (stmt
)
2802 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2809 /* Detect commutative and associative scalar reductions belonging to
2810 the SCOP starting at the loop closed phi node STMT. Return the phi
2811 node of the reduction cycle, or NULL. */
2814 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2817 if (scalar_close_phi_node_p (stmt
))
2820 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2821 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2823 if (TREE_CODE (arg
) != SSA_NAME
)
2826 /* Note that loop close phi nodes should have a single argument
2827 because we translated the representation into a canonical form
2828 before Graphite: see canonicalize_loop_closed_ssa_form. */
2829 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2831 def
= SSA_NAME_DEF_STMT (arg
);
2832 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2833 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2836 lhs
= gimple_phi_result (close_phi
);
2837 init
= initial_value_for_loop_phi (loop_phi
);
2838 phi
= follow_inital_value_to_phi (init
, lhs
);
2840 if (phi
&& (used_outside_reduction (lhs
, phi
)
2841 || !has_single_use (gimple_phi_result (phi
))))
2844 in
->safe_push (loop_phi
);
2845 out
->safe_push (close_phi
);
2849 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2850 return detect_commutative_reduction_assign (stmt
, in
, out
);
2855 /* Translate the scalar reduction statement STMT to an array RED
2856 knowing that its recursive phi node is LOOP_PHI. */
2859 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2860 gimple stmt
, gphi
*loop_phi
)
2862 tree res
= gimple_phi_result (loop_phi
);
2863 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2864 gimple_stmt_iterator gsi
;
2866 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2868 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2869 gsi
= gsi_for_stmt (stmt
);
2871 insert_stmts (scop
, assign
, NULL
, gsi
);
2874 /* Removes the PHI node and resets all the debug stmts that are using
2878 remove_phi (gphi
*phi
)
2880 imm_use_iterator imm_iter
;
2882 use_operand_p use_p
;
2883 gimple_stmt_iterator gsi
;
2884 auto_vec
<gimple
, 3> update
;
2888 def
= PHI_RESULT (phi
);
2889 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2891 stmt
= USE_STMT (use_p
);
2893 if (is_gimple_debug (stmt
))
2895 gimple_debug_bind_reset_value (stmt
);
2896 update
.safe_push (stmt
);
2900 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2903 gsi
= gsi_for_phi_node (phi
);
2904 remove_phi_node (&gsi
, false);
2907 /* Helper function for for_each_index. For each INDEX of the data
2908 reference REF, returns true when its indices are valid in the loop
2909 nest LOOP passed in as DATA. */
2912 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2915 basic_block header
, def_bb
;
2918 if (TREE_CODE (*index
) != SSA_NAME
)
2921 loop
= *((loop_p
*) data
);
2922 header
= loop
->header
;
2923 stmt
= SSA_NAME_DEF_STMT (*index
);
2928 def_bb
= gimple_bb (stmt
);
2933 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2936 /* When the result of a CLOSE_PHI is written to a memory location,
2937 return a pointer to that memory reference, otherwise return
2941 close_phi_written_to_memory (gphi
*close_phi
)
2943 imm_use_iterator imm_iter
;
2944 use_operand_p use_p
;
2946 tree res
, def
= gimple_phi_result (close_phi
);
2948 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2949 if ((stmt
= USE_STMT (use_p
))
2950 && gimple_code (stmt
) == GIMPLE_ASSIGN
2951 && (res
= gimple_assign_lhs (stmt
)))
2953 switch (TREE_CODE (res
))
2963 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2964 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2966 /* FIXME: this restriction is for id-{24,25}.f and
2967 could be handled by duplicating the computation of
2968 array indices before the loop of the close_phi. */
2969 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2981 /* Rewrite out of SSA the reduction described by the loop phi nodes
2982 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2985 IN: stmt, loop_n, ..., loop_0
2986 OUT: stmt, close_n, ..., close_0
2988 the first element is the reduction statement, and the next elements
2989 are the loop and close phi nodes of each of the outer loops. */
2992 translate_scalar_reduction_to_array (scop_p scop
,
2997 unsigned int i
= out
.length () - 1;
2998 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
3000 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
3002 gimple close_stmt
= out
[i
];
3006 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
3007 poly_bb_p pbb
= pbb_from_bb (bb
);
3008 PBB_IS_REDUCTION (pbb
) = true;
3009 gcc_assert (close_stmt
== loop_stmt
);
3012 red
= create_zero_dim_array
3013 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3015 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3016 as_a
<gphi
*> (in
[1]));
3020 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3021 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3023 if (i
== in
.length () - 1)
3025 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3026 unshare_expr (red
), close_phi
);
3027 insert_out_of_ssa_copy_on_edge
3028 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3029 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3032 remove_phi (loop_phi
);
3033 remove_phi (close_phi
);
3037 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3038 true when something has been changed. */
3041 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3045 auto_vec
<gimple
, 10> in
;
3046 auto_vec
<gimple
, 10> out
;
3048 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3049 res
= in
.length () > 1;
3051 translate_scalar_reduction_to_array (scop
, in
, out
);
3056 /* Rewrites all the commutative reductions from LOOP out of SSA.
3057 Returns true when something has been changed. */
3060 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3064 edge exit
= single_exit (loop
);
3066 bool changed
= false;
3071 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3072 if ((res
= gimple_phi_result (gsi
.phi ()))
3073 && !virtual_operand_p (res
)
3074 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3075 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3081 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3084 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3087 bool changed
= false;
3088 sese region
= SCOP_REGION (scop
);
3090 FOR_EACH_LOOP (loop
, 0)
3091 if (loop_in_sese_p (loop
, region
))
3092 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3097 gsi_commit_edge_inserts ();
3098 update_ssa (TODO_update_ssa
);
3099 #ifdef ENABLE_CHECKING
3100 verify_loop_closed_ssa (true);
3105 /* Can all ivs be represented by a signed integer?
3106 As CLooG might generate negative values in its expressions, signed loop ivs
3107 are required in the backend. */
3110 scop_ivs_can_be_represented (scop_p scop
)
3116 FOR_EACH_LOOP (loop
, 0)
3118 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3121 for (psi
= gsi_start_phis (loop
->header
);
3122 !gsi_end_p (psi
); gsi_next (&psi
))
3124 gphi
*phi
= psi
.phi ();
3125 tree res
= PHI_RESULT (phi
);
3126 tree type
= TREE_TYPE (res
);
3128 if (TYPE_UNSIGNED (type
)
3129 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3142 /* Builds the polyhedral representation for a SESE region. */
3145 build_poly_scop (scop_p scop
)
3147 sese region
= SCOP_REGION (scop
);
3148 graphite_dim_t max_dim
;
3150 build_scop_bbs (scop
);
3152 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3153 Once CLooG is fixed, remove this guard. Anyways, it makes no
3154 sense to optimize a scop containing only PBBs that do not belong
3156 if (nb_pbbs_in_loops (scop
) == 0)
3159 if (!scop_ivs_can_be_represented (scop
))
3162 if (flag_associative_math
)
3163 rewrite_commutative_reductions_out_of_ssa (scop
);
3165 build_sese_loop_nests (region
);
3166 /* Record all conditions in REGION. */
3167 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3168 find_scop_parameters (scop
);
3170 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3171 if (scop_nb_params (scop
) > max_dim
)
3174 build_scop_iteration_domain (scop
);
3175 build_scop_context (scop
);
3176 add_conditions_to_constraints (scop
);
3178 /* Rewrite out of SSA only after having translated the
3179 representation to the polyhedral representation to avoid scev
3180 analysis failures. That means that these functions will insert
3181 new data references that they create in the right place. */
3182 rewrite_reductions_out_of_ssa (scop
);
3183 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3185 build_scop_drs (scop
);
3187 build_scop_scattering (scop
);
3189 /* This SCoP has been translated to the polyhedral
3191 POLY_SCOP_P (scop
) = true;