1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2015 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/>. */
24 /* Workaround for GMP 5.1.3 bug, see PR56019. */
29 #include <isl/union_map.h>
30 #include <isl/constraint.h>
34 /* Since ISL-0.13, the extern is in val_gmp.h. */
35 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
38 #include <isl/val_gmp.h>
39 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
45 #include "coretypes.h"
50 #include "fold-const.h"
53 #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"
62 #include "gimple-iterator.h"
64 #include "gimplify-me.h"
65 #include "gimple-ssa.h"
67 #include "tree-phinodes.h"
68 #include "ssa-iterators.h"
69 #include "stringpool.h"
70 #include "tree-ssanames.h"
71 #include "tree-ssa-loop-manip.h"
72 #include "tree-ssa-loop-niter.h"
73 #include "tree-ssa-loop.h"
74 #include "tree-into-ssa.h"
75 #include "tree-pass.h"
77 #include "tree-chrec.h"
78 #include "tree-data-ref.h"
79 #include "tree-scalar-evolution.h"
82 #include "tree-ssa-propagate.h"
87 #include "insn-config.h"
96 #include "graphite-poly.h"
97 #include "graphite-sese-to-poly.h"
100 /* Assigns to RES the value of the INTEGER_CST T. */
103 tree_int_to_gmp (tree t
, mpz_t res
)
105 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
108 /* Returns the index of the PHI argument defined in the outermost
112 phi_arg_in_outermost_loop (gphi
*phi
)
114 loop_p loop
= gimple_bb (phi
)->loop_father
;
117 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
118 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
120 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
127 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
128 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
131 remove_simple_copy_phi (gphi_iterator
*psi
)
133 gphi
*phi
= psi
->phi ();
134 tree res
= gimple_phi_result (phi
);
135 size_t entry
= phi_arg_in_outermost_loop (phi
);
136 tree init
= gimple_phi_arg_def (phi
, entry
);
137 gassign
*stmt
= gimple_build_assign (res
, init
);
138 edge e
= gimple_phi_arg_edge (phi
, entry
);
140 remove_phi_node (psi
, false);
141 gsi_insert_on_edge_immediate (e
, stmt
);
144 /* Removes an invariant phi node at position PSI by inserting on the
145 loop ENTRY edge the assignment RES = INIT. */
148 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
150 gphi
*phi
= psi
->phi ();
151 loop_p loop
= loop_containing_stmt (phi
);
152 tree res
= gimple_phi_result (phi
);
153 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
154 size_t entry
= phi_arg_in_outermost_loop (phi
);
155 edge e
= gimple_phi_arg_edge (phi
, entry
);
158 gimple_seq stmts
= NULL
;
160 if (tree_contains_chrecs (scev
, NULL
))
161 scev
= gimple_phi_arg_def (phi
, entry
);
163 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
164 stmt
= gimple_build_assign (res
, var
);
165 remove_phi_node (psi
, false);
167 gimple_seq_add_stmt (&stmts
, stmt
);
168 gsi_insert_seq_on_edge (e
, stmts
);
169 gsi_commit_edge_inserts ();
170 SSA_NAME_DEF_STMT (res
) = stmt
;
173 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
176 simple_copy_phi_p (gphi
*phi
)
180 if (gimple_phi_num_args (phi
) != 2)
183 res
= gimple_phi_result (phi
);
184 return (res
== gimple_phi_arg_def (phi
, 0)
185 || res
== gimple_phi_arg_def (phi
, 1));
188 /* Returns true when the phi node at position PSI is a reduction phi
189 node in REGION. Otherwise moves the pointer PSI to the next phi to
193 reduction_phi_p (sese region
, gphi_iterator
*psi
)
196 gphi
*phi
= psi
->phi ();
197 tree res
= gimple_phi_result (phi
);
199 loop
= loop_containing_stmt (phi
);
201 if (simple_copy_phi_p (phi
))
203 /* PRE introduces phi nodes like these, for an example,
204 see id-5.f in the fortran graphite testsuite:
206 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
208 remove_simple_copy_phi (psi
);
212 if (scev_analyzable_p (res
, region
))
214 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
216 if (evolution_function_is_invariant_p (scev
, loop
->num
))
217 remove_invariant_phi (region
, psi
);
224 /* All the other cases are considered reductions. */
228 /* Store the GRAPHITE representation of BB. */
231 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
233 struct gimple_bb
*gbb
;
235 gbb
= XNEW (struct gimple_bb
);
238 GBB_DATA_REFS (gbb
) = drs
;
239 GBB_CONDITIONS (gbb
).create (0);
240 GBB_CONDITION_CASES (gbb
).create (0);
246 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
249 struct data_reference
*dr
;
251 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
254 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
256 free (bap
->alias_set
);
265 free_gimple_bb (struct gimple_bb
*gbb
)
267 free_data_refs_aux (GBB_DATA_REFS (gbb
));
268 free_data_refs (GBB_DATA_REFS (gbb
));
270 GBB_CONDITIONS (gbb
).release ();
271 GBB_CONDITION_CASES (gbb
).release ();
272 GBB_BB (gbb
)->aux
= 0;
276 /* Deletes all gimple bbs in SCOP. */
279 remove_gbbs_in_scop (scop_p scop
)
284 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
285 free_gimple_bb (PBB_BLACK_BOX (pbb
));
288 /* Deletes all scops in SCOPS. */
291 free_scops (vec
<scop_p
> scops
)
296 FOR_EACH_VEC_ELT (scops
, i
, scop
)
298 remove_gbbs_in_scop (scop
);
299 free_sese (SCOP_REGION (scop
));
306 /* Same as outermost_loop_in_sese, returns the outermost loop
307 containing BB in REGION, but makes sure that the returned loop
308 belongs to the REGION, and so this returns the first loop in the
309 REGION when the loop containing BB does not belong to REGION. */
312 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
314 loop_p nest
= outermost_loop_in_sese (region
, bb
);
316 if (loop_in_sese_p (nest
, region
))
319 /* When the basic block BB does not belong to a loop in the region,
320 return the first loop in the region. */
323 if (loop_in_sese_p (nest
, region
))
332 /* Generates a polyhedral black box only if the bb contains interesting
336 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
338 vec
<data_reference_p
> drs
;
340 sese region
= SCOP_REGION (scop
);
341 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
342 gimple_stmt_iterator gsi
;
344 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
346 gimple stmt
= gsi_stmt (gsi
);
349 if (is_gimple_debug (stmt
))
352 loop
= loop_containing_stmt (stmt
);
353 if (!loop_in_sese_p (loop
, region
))
356 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
359 return new_gimple_bb (bb
, drs
);
362 /* Returns true if all predecessors of BB, that are not dominated by BB, are
363 marked in MAP. The predecessors dominated by BB are loop latches and will
364 be handled after BB. */
367 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
372 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
373 if (!bitmap_bit_p (map
, e
->src
->index
)
374 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
380 /* Compare the depth of two basic_block's P1 and P2. */
383 compare_bb_depths (const void *p1
, const void *p2
)
385 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
386 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
387 int d1
= loop_depth (bb1
->loop_father
);
388 int d2
= loop_depth (bb2
->loop_father
);
399 /* Sort the basic blocks from DOM such that the first are the ones at
400 a deepest loop level. */
403 graphite_sort_dominated_info (vec
<basic_block
> dom
)
405 dom
.qsort (compare_bb_depths
);
408 /* Recursive helper function for build_scops_bbs. */
411 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
413 sese region
= SCOP_REGION (scop
);
414 vec
<basic_block
> dom
;
417 if (bitmap_bit_p (visited
, bb
->index
)
418 || !bb_in_sese_p (bb
, region
))
421 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
422 SCOP_BBS (scop
).safe_push (pbb
);
423 bitmap_set_bit (visited
, bb
->index
);
425 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
430 graphite_sort_dominated_info (dom
);
432 while (!dom
.is_empty ())
437 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
438 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
440 build_scop_bbs_1 (scop
, visited
, dom_bb
);
441 dom
.unordered_remove (i
);
449 /* Gather the basic blocks belonging to the SCOP. */
452 build_scop_bbs (scop_p scop
)
454 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
455 sese region
= SCOP_REGION (scop
);
457 bitmap_clear (visited
);
458 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
459 sbitmap_free (visited
);
462 /* Return an ISL identifier for the polyhedral basic block PBB. */
465 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
468 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
469 return isl_id_alloc (s
->ctx
, name
, pbb
);
472 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
473 We generate SCATTERING_DIMENSIONS scattering dimensions.
475 CLooG 0.15.0 and previous versions require, that all
476 scattering functions of one CloogProgram have the same number of
477 scattering dimensions, therefore we allow to specify it. This
478 should be removed in future versions of CLooG.
480 The scattering polyhedron consists of these dimensions: scattering,
481 loop_iterators, parameters.
485 | scattering_dimensions = 5
486 | used_scattering_dimensions = 3
494 | Scattering polyhedron:
496 | scattering: {s1, s2, s3, s4, s5}
497 | loop_iterators: {i}
498 | parameters: {p1, p2}
500 | s1 s2 s3 s4 s5 i p1 p2 1
501 | 1 0 0 0 0 0 0 0 -4 = 0
502 | 0 1 0 0 0 -1 0 0 0 = 0
503 | 0 0 1 0 0 0 0 0 -5 = 0 */
506 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
507 poly_bb_p pbb
, int scattering_dimensions
)
510 int nb_iterators
= pbb_dim_iter_domain (pbb
);
511 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
515 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
517 dc
= isl_set_get_space (pbb
->domain
);
518 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
519 isl_dim_out
, scattering_dimensions
);
520 pbb
->schedule
= isl_map_universe (dm
);
522 for (i
= 0; i
< scattering_dimensions
; i
++)
524 /* Textual order inside this loop. */
527 isl_constraint
*c
= isl_equality_alloc
528 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
530 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
532 val
= isl_val_neg (val
);
533 c
= isl_constraint_set_constant_val (c
, val
);
534 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
535 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
538 /* Iterations of this loop. */
539 else /* if ((i % 2) == 1) */
541 int loop
= (i
- 1) / 2;
542 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
547 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
550 /* Build for BB the static schedule.
552 The static schedule is a Dewey numbering of the abstract syntax
553 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
555 The following example informally defines the static schedule:
574 Static schedules for A to F:
587 build_scop_scattering (scop_p scop
)
591 gimple_bb_p previous_gbb
= NULL
;
592 isl_space
*dc
= isl_set_get_space (scop
->context
);
593 isl_aff
*static_sched
;
595 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
596 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
598 /* We have to start schedules at 0 on the first component and
599 because we cannot compare_prefix_loops against a previous loop,
600 prefix will be equal to zero, and that index will be
601 incremented before copying. */
602 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
604 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
606 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
608 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
611 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
617 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
619 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
622 isl_aff_free (static_sched
);
625 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
627 /* Extract an affine expression from the chain of recurrence E. */
630 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
632 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
633 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
634 isl_local_space
*ls
= isl_local_space_from_space (space
);
635 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
636 isl_aff
*loop
= isl_aff_set_coefficient_si
637 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
638 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
640 /* Before multiplying, make sure that the result is affine. */
641 gcc_assert (isl_pw_aff_is_cst (rhs
)
642 || isl_pw_aff_is_cst (l
));
644 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
647 /* Extract an affine expression from the mult_expr E. */
650 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
652 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
653 isl_space_copy (space
));
654 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
656 if (!isl_pw_aff_is_cst (lhs
)
657 && !isl_pw_aff_is_cst (rhs
))
659 isl_pw_aff_free (lhs
);
660 isl_pw_aff_free (rhs
);
664 return isl_pw_aff_mul (lhs
, rhs
);
667 /* Return an ISL identifier from the name of the ssa_name E. */
670 isl_id_for_ssa_name (scop_p s
, tree e
)
672 const char *name
= get_name (e
);
676 id
= isl_id_alloc (s
->ctx
, name
, e
);
680 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
681 id
= isl_id_alloc (s
->ctx
, name1
, e
);
687 /* Return an ISL identifier for the data reference DR. */
690 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
692 /* Data references all get the same isl_id. They need to be comparable
693 and are distinguished through the first dimension, which contains the
695 return isl_id_alloc (s
->ctx
, "", 0);
698 /* Extract an affine expression from the ssa_name E. */
701 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
708 id
= isl_id_for_ssa_name (s
, e
);
709 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
711 dom
= isl_set_universe (isl_space_copy (space
));
712 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
713 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
714 return isl_pw_aff_alloc (dom
, aff
);
717 /* Extract an affine expression from the gmp constant G. */
720 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
722 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
723 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
724 isl_set
*dom
= isl_set_universe (space
);
728 ct
= isl_aff_get_ctx (aff
);
729 v
= isl_val_int_from_gmp (ct
, g
);
730 aff
= isl_aff_add_constant_val (aff
, v
);
732 return isl_pw_aff_alloc (dom
, aff
);
735 /* Extract an affine expression from the integer_cst E. */
738 extract_affine_int (tree e
, __isl_take isl_space
*space
)
744 tree_int_to_gmp (e
, g
);
745 res
= extract_affine_gmp (g
, space
);
751 /* Compute pwaff mod 2^width. */
753 extern isl_ctx
*the_isl_ctx
;
756 wrap (isl_pw_aff
*pwaff
, unsigned width
)
760 mod
= isl_val_int_from_ui(the_isl_ctx
, width
);
761 mod
= isl_val_2exp (mod
);
762 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
767 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
768 Otherwise returns -1. */
771 parameter_index_in_region_1 (tree name
, sese region
)
776 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
778 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
785 /* When the parameter NAME is in REGION, returns its index in
786 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
787 and returns the index of NAME. */
790 parameter_index_in_region (tree name
, sese region
)
794 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
796 i
= parameter_index_in_region_1 (name
, region
);
800 gcc_assert (SESE_ADD_PARAMS (region
));
802 i
= SESE_PARAMS (region
).length ();
803 SESE_PARAMS (region
).safe_push (name
);
807 /* Extract an affine expression from the tree E in the scop S. */
810 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
812 isl_pw_aff
*lhs
, *rhs
, *res
;
815 if (e
== chrec_dont_know
) {
816 isl_space_free (space
);
820 switch (TREE_CODE (e
))
822 case POLYNOMIAL_CHREC
:
823 res
= extract_affine_chrec (s
, e
, space
);
827 res
= extract_affine_mul (s
, e
, space
);
831 case POINTER_PLUS_EXPR
:
832 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
833 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
834 res
= isl_pw_aff_add (lhs
, rhs
);
838 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
839 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
840 res
= isl_pw_aff_sub (lhs
, rhs
);
845 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
846 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
847 res
= isl_pw_aff_mul (lhs
, rhs
);
851 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
852 res
= extract_affine_name (s
, e
, space
);
856 res
= extract_affine_int (e
, space
);
857 /* No need to wrap a single integer. */
861 case NON_LVALUE_EXPR
:
862 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
870 type
= TREE_TYPE (e
);
871 if (TYPE_UNSIGNED (type
))
872 res
= wrap (res
, TYPE_PRECISION (type
));
877 /* In the context of sese S, scan the expression E and translate it to
878 a linear expression C. When parsing a symbolic multiplication, K
879 represents the constant multiplier of an expression containing
883 scan_tree_for_params (sese s
, tree e
)
885 if (e
== chrec_dont_know
)
888 switch (TREE_CODE (e
))
890 case POLYNOMIAL_CHREC
:
891 scan_tree_for_params (s
, CHREC_LEFT (e
));
895 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
896 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
898 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
902 case POINTER_PLUS_EXPR
:
904 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
905 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
911 case NON_LVALUE_EXPR
:
912 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
916 parameter_index_in_region (e
, s
);
929 /* Find parameters with respect to REGION in BB. We are looking in memory
930 access functions, conditions and loop bounds. */
933 find_params_in_bb (sese region
, gimple_bb_p gbb
)
939 loop_p loop
= GBB_BB (gbb
)->loop_father
;
941 /* Find parameters in the access functions of data references. */
942 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
943 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
944 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
946 /* Find parameters in conditional statements. */
947 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
949 tree lhs
= scalar_evolution_in_region (region
, loop
,
950 gimple_cond_lhs (stmt
));
951 tree rhs
= scalar_evolution_in_region (region
, loop
,
952 gimple_cond_rhs (stmt
));
954 scan_tree_for_params (region
, lhs
);
955 scan_tree_for_params (region
, rhs
);
959 /* Record the parameters used in the SCOP. A variable is a parameter
960 in a scop if it does not vary during the execution of that scop. */
963 find_scop_parameters (scop_p scop
)
967 sese region
= SCOP_REGION (scop
);
971 /* Find the parameters used in the loop bounds. */
972 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
974 tree nb_iters
= number_of_latch_executions (loop
);
976 if (!chrec_contains_symbols (nb_iters
))
979 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
980 scan_tree_for_params (region
, nb_iters
);
983 /* Find the parameters used in data accesses. */
984 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
985 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
987 nbp
= sese_nb_params (region
);
988 scop_set_nb_params (scop
, nbp
);
989 SESE_ADD_PARAMS (region
) = false;
993 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
995 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
996 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
997 isl_id_for_ssa_name (scop
, e
));
999 scop
->context
= isl_set_universe (space
);
1003 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
1004 the constraints for the surrounding loops. */
1007 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
1009 isl_set
*outer
, isl_set
**doms
)
1011 tree nb_iters
= number_of_latch_executions (loop
);
1012 sese region
= SCOP_REGION (scop
);
1014 isl_set
*inner
= isl_set_copy (outer
);
1017 int pos
= isl_set_dim (outer
, isl_dim_set
);
1023 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1024 space
= isl_set_get_space (inner
);
1027 c
= isl_inequality_alloc
1028 (isl_local_space_from_space (isl_space_copy (space
)));
1029 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1030 inner
= isl_set_add_constraint (inner
, c
);
1032 /* loop_i <= cst_nb_iters */
1033 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1035 c
= isl_inequality_alloc
1036 (isl_local_space_from_space (isl_space_copy (space
)));
1037 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1038 tree_int_to_gmp (nb_iters
, g
);
1039 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1040 c
= isl_constraint_set_constant_val (c
, v
);
1041 inner
= isl_set_add_constraint (inner
, c
);
1044 /* loop_i <= expr_nb_iters */
1045 else if (!chrec_contains_undetermined (nb_iters
))
1050 isl_local_space
*ls
;
1054 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1056 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1057 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1058 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1059 isl_set_dim (valid
, isl_dim_set
));
1060 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1062 ls
= isl_local_space_from_space (isl_space_copy (space
));
1063 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1064 isl_dim_in
, pos
, 1);
1065 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1066 isl_pw_aff_copy (aff
));
1067 inner
= isl_set_intersect (inner
, le
);
1069 if (max_stmt_executions (loop
, &nit
))
1071 /* Insert in the context the constraints from the
1072 estimation of the number of iterations NIT and the
1073 symbolic number of iterations (involving parameter
1074 names) NB_ITERS. First, build the affine expression
1075 "NIT - NB_ITERS" and then say that it is positive,
1076 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1083 wi::to_mpz (nit
, g
, SIGNED
);
1084 mpz_sub_ui (g
, g
, 1);
1085 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1086 x
= isl_pw_aff_ge_set (approx
, aff
);
1087 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1088 isl_set_dim (x
, isl_dim_set
));
1089 scop
->context
= isl_set_intersect (scop
->context
, x
);
1091 c
= isl_inequality_alloc
1092 (isl_local_space_from_space (isl_space_copy (space
)));
1093 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1094 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1096 c
= isl_constraint_set_constant_val (c
, v
);
1097 inner
= isl_set_add_constraint (inner
, c
);
1100 isl_pw_aff_free (aff
);
1105 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1106 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1107 isl_set_copy (inner
), doms
);
1111 && loop_in_sese_p (loop
->next
, region
))
1112 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1113 isl_set_copy (outer
), doms
);
1115 doms
[loop
->num
] = inner
;
1117 isl_set_free (outer
);
1118 isl_space_free (space
);
1122 /* Returns a linear expression for tree T evaluated in PBB. */
1125 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1127 scop_p scop
= PBB_SCOP (pbb
);
1129 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1130 gcc_assert (!automatically_generated_chrec_p (t
));
1132 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1135 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1136 operator. This allows us to invert the condition or to handle
1140 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1142 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1143 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1149 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1153 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1157 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1161 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1165 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1169 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1173 isl_pw_aff_free (lhs
);
1174 isl_pw_aff_free (rhs
);
1178 cond
= isl_set_coalesce (cond
);
1179 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1180 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1183 /* Add conditions to the domain of PBB. */
1186 add_conditions_to_domain (poly_bb_p pbb
)
1190 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1192 if (GBB_CONDITIONS (gbb
).is_empty ())
1195 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1196 switch (gimple_code (stmt
))
1200 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1201 enum tree_code code
= gimple_cond_code (cond_stmt
);
1203 /* The conditions for ELSE-branches are inverted. */
1204 if (!GBB_CONDITION_CASES (gbb
)[i
])
1205 code
= invert_tree_comparison (code
, false);
1207 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1212 /* Switch statements are not supported right now - fall through. */
1220 /* Traverses all the GBBs of the SCOP and add their constraints to the
1221 iteration domains. */
1224 add_conditions_to_constraints (scop_p scop
)
1229 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1230 add_conditions_to_domain (pbb
);
1233 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1234 edge between BB and its predecessor is not a loop exit edge, and
1235 the last statement of the single predecessor is a COND_EXPR. */
1238 single_pred_cond_non_loop_exit (basic_block bb
)
1240 if (single_pred_p (bb
))
1242 edge e
= single_pred_edge (bb
);
1243 basic_block pred
= e
->src
;
1246 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1249 stmt
= last_stmt (pred
);
1251 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1252 return as_a
<gcond
*> (stmt
);
1258 class sese_dom_walker
: public dom_walker
1261 sese_dom_walker (cdi_direction
, sese
);
1263 virtual void before_dom_children (basic_block
);
1264 virtual void after_dom_children (basic_block
);
1267 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1271 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1272 : dom_walker (direction
), m_region (region
)
1276 /* Call-back for dom_walk executed before visiting the dominated
1280 sese_dom_walker::before_dom_children (basic_block bb
)
1285 if (!bb_in_sese_p (bb
, m_region
))
1288 stmt
= single_pred_cond_non_loop_exit (bb
);
1292 edge e
= single_pred_edge (bb
);
1294 m_conditions
.safe_push (stmt
);
1296 if (e
->flags
& EDGE_TRUE_VALUE
)
1297 m_cases
.safe_push (stmt
);
1299 m_cases
.safe_push (NULL
);
1302 gbb
= gbb_from_bb (bb
);
1306 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1307 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1311 /* Call-back for dom_walk executed after visiting the dominated
1315 sese_dom_walker::after_dom_children (basic_block bb
)
1317 if (!bb_in_sese_p (bb
, m_region
))
1320 if (single_pred_cond_non_loop_exit (bb
))
1322 m_conditions
.pop ();
1327 /* Add constraints on the possible values of parameter P from the type
1331 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1333 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1334 tree type
= TREE_TYPE (parameter
);
1335 tree lb
= NULL_TREE
;
1336 tree ub
= NULL_TREE
;
1338 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1339 lb
= lower_bound_in_type (type
, type
);
1341 lb
= TYPE_MIN_VALUE (type
);
1343 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1344 ub
= upper_bound_in_type (type
, type
);
1346 ub
= TYPE_MAX_VALUE (type
);
1350 isl_space
*space
= isl_set_get_space (scop
->context
);
1355 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1357 tree_int_to_gmp (lb
, g
);
1358 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1359 v
= isl_val_neg (v
);
1361 c
= isl_constraint_set_constant_val (c
, v
);
1362 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1364 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1369 isl_space
*space
= isl_set_get_space (scop
->context
);
1374 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1377 tree_int_to_gmp (ub
, g
);
1378 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1380 c
= isl_constraint_set_constant_val (c
, v
);
1381 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1383 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1387 /* Build the context of the SCOP. The context usually contains extra
1388 constraints that are added to the iteration domains that constrain
1392 build_scop_context (scop_p scop
)
1394 graphite_dim_t p
, n
= scop_nb_params (scop
);
1396 for (p
= 0; p
< n
; p
++)
1397 add_param_constraints (scop
, p
);
1400 /* Build the iteration domains: the loops belonging to the current
1401 SCOP, and that vary for the execution of the current basic block.
1402 Returns false if there is no loop in SCOP. */
1405 build_scop_iteration_domain (scop_p scop
)
1408 sese region
= SCOP_REGION (scop
);
1411 int nb_loops
= number_of_loops (cfun
);
1412 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1414 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1415 if (!loop_in_sese_p (loop_outer (loop
), region
))
1416 build_loop_iteration_domains (scop
, loop
, 0,
1417 isl_set_copy (scop
->context
), doms
);
1419 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1421 loop
= pbb_loop (pbb
);
1423 if (doms
[loop
->num
])
1424 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1426 pbb
->domain
= isl_set_copy (scop
->context
);
1428 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1429 isl_id_for_pbb (scop
, pbb
));
1432 for (i
= 0; i
< nb_loops
; i
++)
1434 isl_set_free (doms
[i
]);
1439 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1440 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1441 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1445 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1448 int alias_set_num
= 0;
1449 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1451 if (bap
&& bap
->alias_set
)
1452 alias_set_num
= *(bap
->alias_set
);
1454 c
= isl_equality_alloc
1455 (isl_local_space_from_space (isl_map_get_space (acc
)));
1456 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1457 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1459 return isl_map_add_constraint (acc
, c
);
1462 /* Assign the affine expression INDEX to the output dimension POS of
1463 MAP and return the result. */
1466 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1469 int len
= isl_map_dim (map
, isl_dim_out
);
1472 index_map
= isl_map_from_pw_aff (index
);
1473 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1474 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1476 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1477 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1478 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1479 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1481 return isl_map_intersect (map
, index_map
);
1484 /* Add to ACCESSES polyhedron equalities defining the access functions
1485 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1486 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1487 PBB is the poly_bb_p that contains the data reference DR. */
1490 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1492 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1493 scop_p scop
= PBB_SCOP (pbb
);
1495 for (i
= 0; i
< nb_subscripts
; i
++)
1498 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1500 aff
= extract_affine (scop
, afn
,
1501 isl_space_domain (isl_map_get_space (acc
)));
1502 acc
= set_index (acc
, i
+ 1, aff
);
1508 /* Add constrains representing the size of the accessed data to the
1509 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1510 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1514 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1516 tree ref
= DR_REF (dr
);
1517 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1519 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1523 if (TREE_CODE (ref
) != ARRAY_REF
)
1526 low
= array_ref_low_bound (ref
);
1527 high
= array_ref_up_bound (ref
);
1529 /* XXX The PPL code dealt separately with
1530 subscript - low >= 0 and high - subscript >= 0 in case one of
1531 the two bounds isn't known. Do the same here? */
1533 if (tree_fits_shwi_p (low
)
1535 && tree_fits_shwi_p (high
)
1536 /* 1-element arrays at end of structures may extend over
1537 their declared size. */
1538 && !(array_at_struct_end_p (ref
)
1539 && operand_equal_p (low
, high
, 0)))
1543 isl_set
*univ
, *lbs
, *ubs
;
1547 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1548 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1551 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1552 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1553 isl_set_dim (valid
, isl_dim_set
));
1554 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1556 space
= isl_set_get_space (extent
);
1557 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1558 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1559 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1560 index
= isl_pw_aff_alloc (univ
, aff
);
1562 id
= isl_set_get_tuple_id (extent
);
1563 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1564 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1566 /* low <= sub_i <= high */
1567 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1568 ubs
= isl_pw_aff_le_set (index
, ub
);
1569 extent
= isl_set_intersect (extent
, lbs
);
1570 extent
= isl_set_intersect (extent
, ubs
);
1577 /* Build data accesses for DR in PBB. */
1580 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1582 int dr_base_object_set
;
1585 scop_p scop
= PBB_SCOP (pbb
);
1588 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1589 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1590 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1591 isl_dim_out
, nb_out
);
1593 acc
= isl_map_universe (space
);
1594 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1597 acc
= pdr_add_alias_set (acc
, dr
);
1598 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1601 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1602 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1603 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1604 int alias_set_num
= 0;
1605 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1607 if (bap
&& bap
->alias_set
)
1608 alias_set_num
= *(bap
->alias_set
);
1610 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1611 extent
= isl_set_nat_universe (space
);
1612 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1613 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1616 gcc_assert (dr
->aux
);
1617 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1619 new_poly_dr (pbb
, dr_base_object_set
,
1620 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1621 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1624 /* Write to FILE the alias graph of data references in DIMACS format. */
1627 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1628 vec
<data_reference_p
> drs
)
1630 int num_vertex
= drs
.length ();
1632 data_reference_p dr1
, dr2
;
1635 if (num_vertex
== 0)
1638 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1639 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1640 if (dr_may_alias_p (dr1
, dr2
, true))
1643 fprintf (file
, "$\n");
1646 fprintf (file
, "c %s\n", comment
);
1648 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1650 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1651 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1652 if (dr_may_alias_p (dr1
, dr2
, true))
1653 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1658 /* Write to FILE the alias graph of data references in DOT format. */
1661 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1662 vec
<data_reference_p
> drs
)
1664 int num_vertex
= drs
.length ();
1665 data_reference_p dr1
, dr2
;
1668 if (num_vertex
== 0)
1671 fprintf (file
, "$\n");
1674 fprintf (file
, "c %s\n", comment
);
1676 /* First print all the vertices. */
1677 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1678 fprintf (file
, "n%d;\n", i
);
1680 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1681 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1682 if (dr_may_alias_p (dr1
, dr2
, true))
1683 fprintf (file
, "n%d n%d\n", i
, j
);
1688 /* Write to FILE the alias graph of data references in ECC format. */
1691 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1692 vec
<data_reference_p
> drs
)
1694 int num_vertex
= drs
.length ();
1695 data_reference_p dr1
, dr2
;
1698 if (num_vertex
== 0)
1701 fprintf (file
, "$\n");
1704 fprintf (file
, "c %s\n", comment
);
1706 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1707 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1708 if (dr_may_alias_p (dr1
, dr2
, true))
1709 fprintf (file
, "%d %d\n", i
, j
);
1714 /* Check if DR1 and DR2 are in the same object set. */
1717 dr_same_base_object_p (const struct data_reference
*dr1
,
1718 const struct data_reference
*dr2
)
1720 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1723 /* Uses DFS component number as representative of alias-sets. Also tests for
1724 optimality by verifying if every connected component is a clique. Returns
1725 true (1) if the above test is true, and false (0) otherwise. */
1728 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1730 int num_vertices
= drs
.length ();
1731 struct graph
*g
= new_graph (num_vertices
);
1732 data_reference_p dr1
, dr2
;
1734 int num_connected_components
;
1735 int v_indx1
, v_indx2
, num_vertices_in_component
;
1738 struct graph_edge
*e
;
1739 int this_component_is_clique
;
1740 int all_components_are_cliques
= 1;
1742 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1743 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1744 if (dr_may_alias_p (dr1
, dr2
, true))
1750 all_vertices
= XNEWVEC (int, num_vertices
);
1751 vertices
= XNEWVEC (int, num_vertices
);
1752 for (i
= 0; i
< num_vertices
; i
++)
1753 all_vertices
[i
] = i
;
1755 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1757 for (i
= 0; i
< g
->n_vertices
; i
++)
1759 data_reference_p dr
= drs
[i
];
1760 base_alias_pair
*bap
;
1762 gcc_assert (dr
->aux
);
1763 bap
= (base_alias_pair
*)(dr
->aux
);
1765 bap
->alias_set
= XNEW (int);
1766 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1769 /* Verify if the DFS numbering results in optimal solution. */
1770 for (i
= 0; i
< num_connected_components
; i
++)
1772 num_vertices_in_component
= 0;
1773 /* Get all vertices whose DFS component number is the same as i. */
1774 for (j
= 0; j
< num_vertices
; j
++)
1775 if (g
->vertices
[j
].component
== i
)
1776 vertices
[num_vertices_in_component
++] = j
;
1778 /* Now test if the vertices in 'vertices' form a clique, by testing
1779 for edges among each pair. */
1780 this_component_is_clique
= 1;
1781 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1783 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1785 /* Check if the two vertices are connected by iterating
1786 through all the edges which have one of these are source. */
1787 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1790 if (e
->src
== vertices
[v_indx1
])
1796 this_component_is_clique
= 0;
1800 if (!this_component_is_clique
)
1801 all_components_are_cliques
= 0;
1805 free (all_vertices
);
1808 return all_components_are_cliques
;
1811 /* Group each data reference in DRS with its base object set num. */
1814 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1816 int num_vertex
= drs
.length ();
1817 struct graph
*g
= new_graph (num_vertex
);
1818 data_reference_p dr1
, dr2
;
1822 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1823 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1824 if (dr_same_base_object_p (dr1
, dr2
))
1830 queue
= XNEWVEC (int, num_vertex
);
1831 for (i
= 0; i
< num_vertex
; i
++)
1834 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1836 for (i
= 0; i
< g
->n_vertices
; i
++)
1838 data_reference_p dr
= drs
[i
];
1839 base_alias_pair
*bap
;
1841 gcc_assert (dr
->aux
);
1842 bap
= (base_alias_pair
*)(dr
->aux
);
1844 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1851 /* Build the data references for PBB. */
1854 build_pbb_drs (poly_bb_p pbb
)
1857 data_reference_p dr
;
1858 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1860 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1861 build_poly_dr (dr
, pbb
);
1864 /* Dump to file the alias graphs for the data references in DRS. */
1867 dump_alias_graphs (vec
<data_reference_p
> drs
)
1870 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1872 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1875 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1876 current_function_name ());
1877 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1878 fclose (file_dimacs
);
1881 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1884 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1885 current_function_name ());
1886 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1890 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1893 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1894 current_function_name ());
1895 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1900 /* Build data references in SCOP. */
1903 build_scop_drs (scop_p scop
)
1907 data_reference_p dr
;
1908 auto_vec
<data_reference_p
, 3> drs
;
1910 /* Remove all the PBBs that do not have data references: these basic
1911 blocks are not handled in the polyhedral representation. */
1912 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1913 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1915 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1917 SCOP_BBS (scop
).ordered_remove (i
);
1921 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1922 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1925 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1926 dr
->aux
= XNEW (base_alias_pair
);
1928 if (!build_alias_set_optimal_p (drs
))
1930 /* TODO: Add support when building alias set is not optimal. */
1934 build_base_obj_set_for_drs (drs
);
1936 /* When debugging, enable the following code. This cannot be used
1937 in production compilers. */
1939 dump_alias_graphs (drs
);
1943 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1944 build_pbb_drs (pbb
);
1947 /* Return a gsi at the position of the phi node STMT. */
1949 static gphi_iterator
1950 gsi_for_phi_node (gphi
*stmt
)
1953 basic_block bb
= gimple_bb (stmt
);
1955 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1956 if (stmt
== psi
.phi ())
1963 /* Analyze all the data references of STMTS and add them to the
1964 GBB_DATA_REFS vector of BB. */
1967 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1973 sese region
= SCOP_REGION (scop
);
1975 if (!bb_in_sese_p (bb
, region
))
1978 nest
= outermost_loop_in_sese_1 (region
, bb
);
1979 gbb
= gbb_from_bb (bb
);
1981 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1985 if (is_gimple_debug (stmt
))
1988 loop
= loop_containing_stmt (stmt
);
1989 if (!loop_in_sese_p (loop
, region
))
1992 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1993 &GBB_DATA_REFS (gbb
));
1997 /* Insert STMT at the end of the STMTS sequence and then insert the
1998 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2002 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
2003 gimple_stmt_iterator insert_gsi
)
2005 gimple_stmt_iterator gsi
;
2006 auto_vec
<gimple
, 3> x
;
2008 gimple_seq_add_stmt (&stmts
, stmt
);
2009 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2010 x
.safe_push (gsi_stmt (gsi
));
2012 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2013 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2016 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2019 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2022 gimple_stmt_iterator gsi
;
2023 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2024 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2025 auto_vec
<gimple
, 3> x
;
2027 gimple_seq_add_stmt (&stmts
, stmt
);
2028 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2029 x
.safe_push (gsi_stmt (gsi
));
2031 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2033 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2034 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2038 gsi
= gsi_for_stmt (after_stmt
);
2039 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2042 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2045 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2048 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2050 vec
<data_reference_p
> drs
;
2052 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2053 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2054 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2055 int index
, n
= SCOP_BBS (scop
).length ();
2057 /* The INDEX of PBB in SCOP_BBS. */
2058 for (index
= 0; index
< n
; index
++)
2059 if (SCOP_BBS (scop
)[index
] == pbb
)
2062 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2063 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2064 isl_id_for_pbb (scop
, pbb1
));
2066 GBB_PBB (gbb1
) = pbb1
;
2067 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2068 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2069 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2072 /* Insert on edge E the assignment "RES := EXPR". */
2075 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2077 gimple_stmt_iterator gsi
;
2078 gimple_seq stmts
= NULL
;
2079 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2080 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2082 auto_vec
<gimple
, 3> x
;
2084 gimple_seq_add_stmt (&stmts
, stmt
);
2085 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2086 x
.safe_push (gsi_stmt (gsi
));
2088 gsi_insert_seq_on_edge (e
, stmts
);
2089 gsi_commit_edge_inserts ();
2090 bb
= gimple_bb (stmt
);
2092 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2095 if (!gbb_from_bb (bb
))
2096 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2098 analyze_drs_in_stmts (scop
, bb
, x
);
2101 /* Creates a zero dimension array of the same type as VAR. */
2104 create_zero_dim_array (tree var
, const char *base_name
)
2106 tree index_type
= build_index_type (integer_zero_node
);
2107 tree elt_type
= TREE_TYPE (var
);
2108 tree array_type
= build_array_type (elt_type
, index_type
);
2109 tree base
= create_tmp_var (array_type
, base_name
);
2111 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2115 /* Returns true when PHI is a loop close phi node. */
2118 scalar_close_phi_node_p (gimple phi
)
2120 if (gimple_code (phi
) != GIMPLE_PHI
2121 || virtual_operand_p (gimple_phi_result (phi
)))
2124 /* Note that loop close phi nodes should have a single argument
2125 because we translated the representation into a canonical form
2126 before Graphite: see canonicalize_loop_closed_ssa_form. */
2127 return (gimple_phi_num_args (phi
) == 1);
2130 /* For a definition DEF in REGION, propagates the expression EXPR in
2131 all the uses of DEF outside REGION. */
2134 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2136 imm_use_iterator imm_iter
;
2139 bool replaced_once
= false;
2141 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2143 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2146 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2147 if (!is_gimple_debug (use_stmt
)
2148 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2151 use_operand_p use_p
;
2153 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2154 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2155 && (replaced_once
= true))
2156 replace_exp (use_p
, expr
);
2158 update_stmt (use_stmt
);
2163 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2164 gsi_commit_edge_inserts ();
2168 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2169 dimension array for it. */
2172 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2174 sese region
= SCOP_REGION (scop
);
2175 gimple phi
= gsi_stmt (*psi
);
2176 tree res
= gimple_phi_result (phi
);
2177 basic_block bb
= gimple_bb (phi
);
2178 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2179 tree arg
= gimple_phi_arg_def (phi
, 0);
2182 /* Note that loop close phi nodes should have a single argument
2183 because we translated the representation into a canonical form
2184 before Graphite: see canonicalize_loop_closed_ssa_form. */
2185 gcc_assert (gimple_phi_num_args (phi
) == 1);
2187 /* The phi node can be a non close phi node, when its argument is
2188 invariant, or a default definition. */
2189 if (is_gimple_min_invariant (arg
)
2190 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2192 propagate_expr_outside_region (res
, arg
, region
);
2197 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2199 propagate_expr_outside_region (res
, arg
, region
);
2200 stmt
= gimple_build_assign (res
, arg
);
2201 remove_phi_node (psi
, false);
2202 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2206 /* If res is scev analyzable and is not a scalar value, it is safe
2207 to ignore the close phi node: it will be code generated in the
2208 out of Graphite pass. */
2209 else if (scev_analyzable_p (res
, region
))
2211 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2214 if (!loop_in_sese_p (loop
, region
))
2216 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2217 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2218 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2221 scev
= scalar_evolution_in_region (region
, loop
, res
);
2223 if (tree_does_not_contain_chrecs (scev
))
2224 propagate_expr_outside_region (res
, scev
, region
);
2231 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2233 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2235 if (TREE_CODE (arg
) == SSA_NAME
)
2236 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2237 SSA_NAME_DEF_STMT (arg
));
2239 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2240 zero_dim_array
, arg
);
2243 remove_phi_node (psi
, false);
2244 SSA_NAME_DEF_STMT (res
) = stmt
;
2246 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2249 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2250 dimension array for it. */
2253 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2256 gphi
*phi
= psi
->phi ();
2257 basic_block bb
= gimple_bb (phi
);
2258 tree res
= gimple_phi_result (phi
);
2259 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2262 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2264 tree arg
= gimple_phi_arg_def (phi
, i
);
2265 edge e
= gimple_phi_arg_edge (phi
, i
);
2267 /* Avoid the insertion of code in the loop latch to please the
2268 pattern matching of the vectorizer. */
2269 if (TREE_CODE (arg
) == SSA_NAME
2270 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2271 && e
->src
== bb
->loop_father
->latch
)
2272 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2273 SSA_NAME_DEF_STMT (arg
));
2275 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2278 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2279 remove_phi_node (psi
, false);
2280 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2283 /* Rewrite the degenerate phi node at position PSI from the degenerate
2284 form "x = phi (y, y, ..., y)" to "x = y". */
2287 rewrite_degenerate_phi (gphi_iterator
*psi
)
2291 gimple_stmt_iterator gsi
;
2292 gphi
*phi
= psi
->phi ();
2293 tree res
= gimple_phi_result (phi
);
2296 bb
= gimple_bb (phi
);
2297 rhs
= degenerate_phi_result (phi
);
2300 stmt
= gimple_build_assign (res
, rhs
);
2301 remove_phi_node (psi
, false);
2303 gsi
= gsi_after_labels (bb
);
2304 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2307 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2310 rewrite_reductions_out_of_ssa (scop_p scop
)
2314 sese region
= SCOP_REGION (scop
);
2316 FOR_EACH_BB_FN (bb
, cfun
)
2317 if (bb_in_sese_p (bb
, region
))
2318 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2320 gphi
*phi
= psi
.phi ();
2322 if (virtual_operand_p (gimple_phi_result (phi
)))
2328 if (gimple_phi_num_args (phi
) > 1
2329 && degenerate_phi_result (phi
))
2330 rewrite_degenerate_phi (&psi
);
2332 else if (scalar_close_phi_node_p (phi
))
2333 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2335 else if (reduction_phi_p (region
, &psi
))
2336 rewrite_phi_out_of_ssa (scop
, &psi
);
2339 update_ssa (TODO_update_ssa
);
2340 #ifdef ENABLE_CHECKING
2341 verify_loop_closed_ssa (true);
2345 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2346 read from ZERO_DIM_ARRAY. */
2349 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2350 tree def
, gimple use_stmt
)
2355 use_operand_p use_p
;
2357 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2359 name
= copy_ssa_name (def
);
2360 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2362 gimple_assign_set_lhs (name_stmt
, name
);
2363 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2365 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2366 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2367 replace_exp (use_p
, name
);
2369 update_stmt (use_stmt
);
2372 /* For every definition DEF in the SCOP that is used outside the scop,
2373 insert a closing-scop definition in the basic block just after this
2377 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2379 tree var
= create_tmp_reg (TREE_TYPE (def
));
2380 tree new_name
= make_ssa_name (var
, stmt
);
2381 bool needs_copy
= false;
2382 use_operand_p use_p
;
2383 imm_use_iterator imm_iter
;
2385 sese region
= SCOP_REGION (scop
);
2387 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2389 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2391 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2393 SET_USE (use_p
, new_name
);
2395 update_stmt (use_stmt
);
2400 /* Insert in the empty BB just after the scop a use of DEF such
2401 that the rewrite of cross_bb_scalar_dependences won't insert
2402 arrays everywhere else. */
2405 gimple assign
= gimple_build_assign (new_name
, def
);
2406 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2408 update_stmt (assign
);
2409 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2413 /* Rewrite the scalar dependences crossing the boundary of the BB
2414 containing STMT with an array. Return true when something has been
2418 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2420 sese region
= SCOP_REGION (scop
);
2421 gimple stmt
= gsi_stmt (*gsi
);
2422 imm_use_iterator imm_iter
;
2425 tree zero_dim_array
= NULL_TREE
;
2429 switch (gimple_code (stmt
))
2432 def
= gimple_assign_lhs (stmt
);
2436 def
= gimple_call_lhs (stmt
);
2444 || !is_gimple_reg (def
))
2447 if (scev_analyzable_p (def
, region
))
2449 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2450 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2452 if (tree_contains_chrecs (scev
, NULL
))
2455 propagate_expr_outside_region (def
, scev
, region
);
2459 def_bb
= gimple_bb (stmt
);
2461 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2463 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2464 if (gimple_code (use_stmt
) == GIMPLE_PHI
2467 gphi_iterator psi
= gsi_start_phis (gimple_bb (use_stmt
));
2469 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2470 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2472 rewrite_phi_out_of_ssa (scop
, &psi
);
2475 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2476 if (gimple_code (use_stmt
) != GIMPLE_PHI
2477 && def_bb
!= gimple_bb (use_stmt
)
2478 && !is_gimple_debug (use_stmt
)
2481 if (!zero_dim_array
)
2483 zero_dim_array
= create_zero_dim_array
2484 (def
, "Cross_BB_scalar_dependence");
2485 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2486 SSA_NAME_DEF_STMT (def
));
2490 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2497 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2500 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2503 gimple_stmt_iterator psi
;
2504 sese region
= SCOP_REGION (scop
);
2505 bool changed
= false;
2507 /* Create an extra empty BB after the scop. */
2508 split_edge (SESE_EXIT (region
));
2510 FOR_EACH_BB_FN (bb
, cfun
)
2511 if (bb_in_sese_p (bb
, region
))
2512 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2513 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2518 update_ssa (TODO_update_ssa
);
2519 #ifdef ENABLE_CHECKING
2520 verify_loop_closed_ssa (true);
2525 /* Returns the number of pbbs that are in loops contained in SCOP. */
2528 nb_pbbs_in_loops (scop_p scop
)
2534 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2535 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2541 /* Return the number of data references in BB that write in
2545 nb_data_writes_in_bb (basic_block bb
)
2548 gimple_stmt_iterator gsi
;
2550 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2551 if (gimple_vdef (gsi_stmt (gsi
)))
2557 /* Splits at STMT the basic block BB represented as PBB in the
2561 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2563 edge e1
= split_block (bb
, stmt
);
2564 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2568 /* Splits STMT out of its current BB. This is done for reduction
2569 statements for which we want to ignore data dependences. */
2572 split_reduction_stmt (scop_p scop
, gimple stmt
)
2574 basic_block bb
= gimple_bb (stmt
);
2575 poly_bb_p pbb
= pbb_from_bb (bb
);
2576 gimple_bb_p gbb
= gbb_from_bb (bb
);
2579 data_reference_p dr
;
2581 /* Do not split basic blocks with no writes to memory: the reduction
2582 will be the only write to memory. */
2583 if (nb_data_writes_in_bb (bb
) == 0
2584 /* Or if we have already marked BB as a reduction. */
2585 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2588 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2590 /* Split once more only when the reduction stmt is not the only one
2591 left in the original BB. */
2592 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2594 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2596 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2599 /* A part of the data references will end in a different basic block
2600 after the split: move the DRs from the original GBB to the newly
2602 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2604 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2608 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2609 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2610 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2618 /* Return true when stmt is a reduction operation. */
2621 is_reduction_operation_p (gimple stmt
)
2623 enum tree_code code
;
2625 gcc_assert (is_gimple_assign (stmt
));
2626 code
= gimple_assign_rhs_code (stmt
);
2628 return flag_associative_math
2629 && commutative_tree_code (code
)
2630 && associative_tree_code (code
);
2633 /* Returns true when PHI contains an argument ARG. */
2636 phi_contains_arg (gphi
*phi
, tree arg
)
2640 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2641 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2647 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2650 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2654 if (TREE_CODE (arg
) != SSA_NAME
)
2657 stmt
= SSA_NAME_DEF_STMT (arg
);
2659 if (gimple_code (stmt
) == GIMPLE_NOP
2660 || gimple_code (stmt
) == GIMPLE_CALL
)
2663 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2665 if (phi_contains_arg (phi
, lhs
))
2670 if (!is_gimple_assign (stmt
))
2673 if (gimple_num_ops (stmt
) == 2)
2674 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2676 if (is_reduction_operation_p (stmt
))
2679 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2682 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2688 /* Detect commutative and associative scalar reductions starting at
2689 the STMT. Return the phi node of the reduction cycle, or NULL. */
2692 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2696 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2701 in
->safe_push (stmt
);
2702 out
->safe_push (stmt
);
2706 /* Detect commutative and associative scalar reductions starting at
2707 STMT. Return the phi node of the reduction cycle, or NULL. */
2710 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2713 tree lhs
= gimple_assign_lhs (stmt
);
2715 if (gimple_num_ops (stmt
) == 2)
2716 return detect_commutative_reduction_arg (lhs
, stmt
,
2717 gimple_assign_rhs1 (stmt
),
2720 if (is_reduction_operation_p (stmt
))
2722 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2723 gimple_assign_rhs1 (stmt
),
2726 : detect_commutative_reduction_arg (lhs
, stmt
,
2727 gimple_assign_rhs2 (stmt
),
2734 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2737 follow_inital_value_to_phi (tree arg
, tree lhs
)
2741 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2744 stmt
= SSA_NAME_DEF_STMT (arg
);
2746 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2747 if (phi_contains_arg (phi
, lhs
))
2754 /* Return the argument of the loop PHI that is the initial value coming
2755 from outside the loop. */
2758 edge_initial_value_for_loop_phi (gphi
*phi
)
2762 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2764 edge e
= gimple_phi_arg_edge (phi
, i
);
2766 if (loop_depth (e
->src
->loop_father
)
2767 < loop_depth (e
->dest
->loop_father
))
2774 /* Return the argument of the loop PHI that is the initial value coming
2775 from outside the loop. */
2778 initial_value_for_loop_phi (gphi
*phi
)
2782 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2784 edge e
= gimple_phi_arg_edge (phi
, i
);
2786 if (loop_depth (e
->src
->loop_father
)
2787 < loop_depth (e
->dest
->loop_father
))
2788 return gimple_phi_arg_def (phi
, i
);
2794 /* Returns true when DEF is used outside the reduction cycle of
2798 used_outside_reduction (tree def
, gimple loop_phi
)
2800 use_operand_p use_p
;
2801 imm_use_iterator imm_iter
;
2802 loop_p loop
= loop_containing_stmt (loop_phi
);
2804 /* In LOOP, DEF should be used only in LOOP_PHI. */
2805 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2807 gimple stmt
= USE_STMT (use_p
);
2809 if (stmt
!= loop_phi
2810 && !is_gimple_debug (stmt
)
2811 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2818 /* Detect commutative and associative scalar reductions belonging to
2819 the SCOP starting at the loop closed phi node STMT. Return the phi
2820 node of the reduction cycle, or NULL. */
2823 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2826 if (scalar_close_phi_node_p (stmt
))
2829 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2830 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2832 if (TREE_CODE (arg
) != SSA_NAME
)
2835 /* Note that loop close phi nodes should have a single argument
2836 because we translated the representation into a canonical form
2837 before Graphite: see canonicalize_loop_closed_ssa_form. */
2838 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2840 def
= SSA_NAME_DEF_STMT (arg
);
2841 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2842 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2845 lhs
= gimple_phi_result (close_phi
);
2846 init
= initial_value_for_loop_phi (loop_phi
);
2847 phi
= follow_inital_value_to_phi (init
, lhs
);
2849 if (phi
&& (used_outside_reduction (lhs
, phi
)
2850 || !has_single_use (gimple_phi_result (phi
))))
2853 in
->safe_push (loop_phi
);
2854 out
->safe_push (close_phi
);
2858 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2859 return detect_commutative_reduction_assign (stmt
, in
, out
);
2864 /* Translate the scalar reduction statement STMT to an array RED
2865 knowing that its recursive phi node is LOOP_PHI. */
2868 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2869 gimple stmt
, gphi
*loop_phi
)
2871 tree res
= gimple_phi_result (loop_phi
);
2872 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2873 gimple_stmt_iterator gsi
;
2875 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2877 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2878 gsi
= gsi_for_stmt (stmt
);
2880 insert_stmts (scop
, assign
, NULL
, gsi
);
2883 /* Removes the PHI node and resets all the debug stmts that are using
2887 remove_phi (gphi
*phi
)
2889 imm_use_iterator imm_iter
;
2891 use_operand_p use_p
;
2892 gimple_stmt_iterator gsi
;
2893 auto_vec
<gimple
, 3> update
;
2897 def
= PHI_RESULT (phi
);
2898 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2900 stmt
= USE_STMT (use_p
);
2902 if (is_gimple_debug (stmt
))
2904 gimple_debug_bind_reset_value (stmt
);
2905 update
.safe_push (stmt
);
2909 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2912 gsi
= gsi_for_phi_node (phi
);
2913 remove_phi_node (&gsi
, false);
2916 /* Helper function for for_each_index. For each INDEX of the data
2917 reference REF, returns true when its indices are valid in the loop
2918 nest LOOP passed in as DATA. */
2921 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2924 basic_block header
, def_bb
;
2927 if (TREE_CODE (*index
) != SSA_NAME
)
2930 loop
= *((loop_p
*) data
);
2931 header
= loop
->header
;
2932 stmt
= SSA_NAME_DEF_STMT (*index
);
2937 def_bb
= gimple_bb (stmt
);
2942 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2945 /* When the result of a CLOSE_PHI is written to a memory location,
2946 return a pointer to that memory reference, otherwise return
2950 close_phi_written_to_memory (gphi
*close_phi
)
2952 imm_use_iterator imm_iter
;
2953 use_operand_p use_p
;
2955 tree res
, def
= gimple_phi_result (close_phi
);
2957 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2958 if ((stmt
= USE_STMT (use_p
))
2959 && gimple_code (stmt
) == GIMPLE_ASSIGN
2960 && (res
= gimple_assign_lhs (stmt
)))
2962 switch (TREE_CODE (res
))
2972 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2973 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2975 /* FIXME: this restriction is for id-{24,25}.f and
2976 could be handled by duplicating the computation of
2977 array indices before the loop of the close_phi. */
2978 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2990 /* Rewrite out of SSA the reduction described by the loop phi nodes
2991 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2994 IN: stmt, loop_n, ..., loop_0
2995 OUT: stmt, close_n, ..., close_0
2997 the first element is the reduction statement, and the next elements
2998 are the loop and close phi nodes of each of the outer loops. */
3001 translate_scalar_reduction_to_array (scop_p scop
,
3006 unsigned int i
= out
.length () - 1;
3007 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
3009 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
3011 gimple close_stmt
= out
[i
];
3015 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
3016 poly_bb_p pbb
= pbb_from_bb (bb
);
3017 PBB_IS_REDUCTION (pbb
) = true;
3018 gcc_assert (close_stmt
== loop_stmt
);
3021 red
= create_zero_dim_array
3022 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3024 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3025 as_a
<gphi
*> (in
[1]));
3029 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3030 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3032 if (i
== in
.length () - 1)
3034 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3035 unshare_expr (red
), close_phi
);
3036 insert_out_of_ssa_copy_on_edge
3037 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3038 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3041 remove_phi (loop_phi
);
3042 remove_phi (close_phi
);
3046 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3047 true when something has been changed. */
3050 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3054 auto_vec
<gimple
, 10> in
;
3055 auto_vec
<gimple
, 10> out
;
3057 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3058 res
= in
.length () > 1;
3060 translate_scalar_reduction_to_array (scop
, in
, out
);
3065 /* Rewrites all the commutative reductions from LOOP out of SSA.
3066 Returns true when something has been changed. */
3069 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3073 edge exit
= single_exit (loop
);
3075 bool changed
= false;
3080 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3081 if ((res
= gimple_phi_result (gsi
.phi ()))
3082 && !virtual_operand_p (res
)
3083 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3084 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3090 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3093 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3096 bool changed
= false;
3097 sese region
= SCOP_REGION (scop
);
3099 FOR_EACH_LOOP (loop
, 0)
3100 if (loop_in_sese_p (loop
, region
))
3101 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3106 gsi_commit_edge_inserts ();
3107 update_ssa (TODO_update_ssa
);
3108 #ifdef ENABLE_CHECKING
3109 verify_loop_closed_ssa (true);
3114 /* Can all ivs be represented by a signed integer?
3115 As CLooG might generate negative values in its expressions, signed loop ivs
3116 are required in the backend. */
3119 scop_ivs_can_be_represented (scop_p scop
)
3125 FOR_EACH_LOOP (loop
, 0)
3127 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3130 for (psi
= gsi_start_phis (loop
->header
);
3131 !gsi_end_p (psi
); gsi_next (&psi
))
3133 gphi
*phi
= psi
.phi ();
3134 tree res
= PHI_RESULT (phi
);
3135 tree type
= TREE_TYPE (res
);
3137 if (TYPE_UNSIGNED (type
)
3138 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3151 /* Builds the polyhedral representation for a SESE region. */
3154 build_poly_scop (scop_p scop
)
3156 sese region
= SCOP_REGION (scop
);
3157 graphite_dim_t max_dim
;
3159 build_scop_bbs (scop
);
3161 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3162 Once CLooG is fixed, remove this guard. Anyways, it makes no
3163 sense to optimize a scop containing only PBBs that do not belong
3165 if (nb_pbbs_in_loops (scop
) == 0)
3168 if (!scop_ivs_can_be_represented (scop
))
3171 if (flag_associative_math
)
3172 rewrite_commutative_reductions_out_of_ssa (scop
);
3174 build_sese_loop_nests (region
);
3175 /* Record all conditions in REGION. */
3176 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3177 find_scop_parameters (scop
);
3179 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3180 if (scop_nb_params (scop
) > max_dim
)
3183 build_scop_iteration_domain (scop
);
3184 build_scop_context (scop
);
3185 add_conditions_to_constraints (scop
);
3187 /* Rewrite out of SSA only after having translated the
3188 representation to the polyhedral representation to avoid scev
3189 analysis failures. That means that these functions will insert
3190 new data references that they create in the right place. */
3191 rewrite_reductions_out_of_ssa (scop
);
3192 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3194 build_scop_drs (scop
);
3196 build_scop_scattering (scop
);
3198 /* This SCoP has been translated to the polyhedral
3200 POLY_SCOP_P (scop
) = true;