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)
44 #include "coretypes.h"
50 #include "fold-const.h"
51 #include "gimple-iterator.h"
53 #include "gimplify-me.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop-niter.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-into-ssa.h"
59 #include "tree-pass.h"
61 #include "tree-data-ref.h"
62 #include "tree-scalar-evolution.h"
64 #include "graphite-poly.h"
65 #include "tree-ssa-propagate.h"
66 #include "graphite-sese-to-poly.h"
69 /* Assigns to RES the value of the INTEGER_CST T. */
72 tree_int_to_gmp (tree t
, mpz_t res
)
74 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
77 /* Returns the index of the PHI argument defined in the outermost
81 phi_arg_in_outermost_loop (gphi
*phi
)
83 loop_p loop
= gimple_bb (phi
)->loop_father
;
86 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
87 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
89 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
96 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
97 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
100 remove_simple_copy_phi (gphi_iterator
*psi
)
102 gphi
*phi
= psi
->phi ();
103 tree res
= gimple_phi_result (phi
);
104 size_t entry
= phi_arg_in_outermost_loop (phi
);
105 tree init
= gimple_phi_arg_def (phi
, entry
);
106 gassign
*stmt
= gimple_build_assign (res
, init
);
107 edge e
= gimple_phi_arg_edge (phi
, entry
);
109 remove_phi_node (psi
, false);
110 gsi_insert_on_edge_immediate (e
, stmt
);
113 /* Removes an invariant phi node at position PSI by inserting on the
114 loop ENTRY edge the assignment RES = INIT. */
117 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
119 gphi
*phi
= psi
->phi ();
120 loop_p loop
= loop_containing_stmt (phi
);
121 tree res
= gimple_phi_result (phi
);
122 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
123 size_t entry
= phi_arg_in_outermost_loop (phi
);
124 edge e
= gimple_phi_arg_edge (phi
, entry
);
127 gimple_seq stmts
= NULL
;
129 if (tree_contains_chrecs (scev
, NULL
))
130 scev
= gimple_phi_arg_def (phi
, entry
);
132 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
133 stmt
= gimple_build_assign (res
, var
);
134 remove_phi_node (psi
, false);
136 gimple_seq_add_stmt (&stmts
, stmt
);
137 gsi_insert_seq_on_edge (e
, stmts
);
138 gsi_commit_edge_inserts ();
139 SSA_NAME_DEF_STMT (res
) = stmt
;
142 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
145 simple_copy_phi_p (gphi
*phi
)
149 if (gimple_phi_num_args (phi
) != 2)
152 res
= gimple_phi_result (phi
);
153 return (res
== gimple_phi_arg_def (phi
, 0)
154 || res
== gimple_phi_arg_def (phi
, 1));
157 /* Returns true when the phi node at position PSI is a reduction phi
158 node in REGION. Otherwise moves the pointer PSI to the next phi to
162 reduction_phi_p (sese region
, gphi_iterator
*psi
)
165 gphi
*phi
= psi
->phi ();
166 tree res
= gimple_phi_result (phi
);
168 loop
= loop_containing_stmt (phi
);
170 if (simple_copy_phi_p (phi
))
172 /* PRE introduces phi nodes like these, for an example,
173 see id-5.f in the fortran graphite testsuite:
175 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
177 remove_simple_copy_phi (psi
);
181 if (scev_analyzable_p (res
, region
))
183 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
185 if (evolution_function_is_invariant_p (scev
, loop
->num
))
186 remove_invariant_phi (region
, psi
);
193 /* All the other cases are considered reductions. */
197 /* Store the GRAPHITE representation of BB. */
200 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
202 struct gimple_bb
*gbb
;
204 gbb
= XNEW (struct gimple_bb
);
207 GBB_DATA_REFS (gbb
) = drs
;
208 GBB_CONDITIONS (gbb
).create (0);
209 GBB_CONDITION_CASES (gbb
).create (0);
215 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
218 struct data_reference
*dr
;
220 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
223 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
225 free (bap
->alias_set
);
234 free_gimple_bb (struct gimple_bb
*gbb
)
236 free_data_refs_aux (GBB_DATA_REFS (gbb
));
237 free_data_refs (GBB_DATA_REFS (gbb
));
239 GBB_CONDITIONS (gbb
).release ();
240 GBB_CONDITION_CASES (gbb
).release ();
241 GBB_BB (gbb
)->aux
= 0;
245 /* Deletes all gimple bbs in SCOP. */
248 remove_gbbs_in_scop (scop_p scop
)
253 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
254 free_gimple_bb (PBB_BLACK_BOX (pbb
));
257 /* Deletes all scops in SCOPS. */
260 free_scops (vec
<scop_p
> scops
)
265 FOR_EACH_VEC_ELT (scops
, i
, scop
)
267 remove_gbbs_in_scop (scop
);
268 free_sese (SCOP_REGION (scop
));
275 /* Same as outermost_loop_in_sese, returns the outermost loop
276 containing BB in REGION, but makes sure that the returned loop
277 belongs to the REGION, and so this returns the first loop in the
278 REGION when the loop containing BB does not belong to REGION. */
281 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
283 loop_p nest
= outermost_loop_in_sese (region
, bb
);
285 if (loop_in_sese_p (nest
, region
))
288 /* When the basic block BB does not belong to a loop in the region,
289 return the first loop in the region. */
292 if (loop_in_sese_p (nest
, region
))
301 /* Generates a polyhedral black box only if the bb contains interesting
305 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
307 vec
<data_reference_p
> drs
;
309 sese region
= SCOP_REGION (scop
);
310 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
311 gimple_stmt_iterator gsi
;
313 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
315 gimple stmt
= gsi_stmt (gsi
);
318 if (is_gimple_debug (stmt
))
321 loop
= loop_containing_stmt (stmt
);
322 if (!loop_in_sese_p (loop
, region
))
325 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
328 return new_gimple_bb (bb
, drs
);
331 /* Returns true if all predecessors of BB, that are not dominated by BB, are
332 marked in MAP. The predecessors dominated by BB are loop latches and will
333 be handled after BB. */
336 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
341 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
342 if (!bitmap_bit_p (map
, e
->src
->index
)
343 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
349 /* Compare the depth of two basic_block's P1 and P2. */
352 compare_bb_depths (const void *p1
, const void *p2
)
354 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
355 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
356 int d1
= loop_depth (bb1
->loop_father
);
357 int d2
= loop_depth (bb2
->loop_father
);
368 /* Sort the basic blocks from DOM such that the first are the ones at
369 a deepest loop level. */
372 graphite_sort_dominated_info (vec
<basic_block
> dom
)
374 dom
.qsort (compare_bb_depths
);
377 /* Recursive helper function for build_scops_bbs. */
380 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
382 sese region
= SCOP_REGION (scop
);
383 vec
<basic_block
> dom
;
386 if (bitmap_bit_p (visited
, bb
->index
)
387 || !bb_in_sese_p (bb
, region
))
390 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
391 SCOP_BBS (scop
).safe_push (pbb
);
392 bitmap_set_bit (visited
, bb
->index
);
394 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
399 graphite_sort_dominated_info (dom
);
401 while (!dom
.is_empty ())
406 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
407 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
409 build_scop_bbs_1 (scop
, visited
, dom_bb
);
410 dom
.unordered_remove (i
);
418 /* Gather the basic blocks belonging to the SCOP. */
421 build_scop_bbs (scop_p scop
)
423 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
424 sese region
= SCOP_REGION (scop
);
426 bitmap_clear (visited
);
427 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
428 sbitmap_free (visited
);
431 /* Return an ISL identifier for the polyhedral basic block PBB. */
434 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
437 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
438 return isl_id_alloc (s
->ctx
, name
, pbb
);
441 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
442 We generate SCATTERING_DIMENSIONS scattering dimensions.
444 CLooG 0.15.0 and previous versions require, that all
445 scattering functions of one CloogProgram have the same number of
446 scattering dimensions, therefore we allow to specify it. This
447 should be removed in future versions of CLooG.
449 The scattering polyhedron consists of these dimensions: scattering,
450 loop_iterators, parameters.
454 | scattering_dimensions = 5
455 | used_scattering_dimensions = 3
463 | Scattering polyhedron:
465 | scattering: {s1, s2, s3, s4, s5}
466 | loop_iterators: {i}
467 | parameters: {p1, p2}
469 | s1 s2 s3 s4 s5 i p1 p2 1
470 | 1 0 0 0 0 0 0 0 -4 = 0
471 | 0 1 0 0 0 -1 0 0 0 = 0
472 | 0 0 1 0 0 0 0 0 -5 = 0 */
475 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
476 poly_bb_p pbb
, int scattering_dimensions
)
479 int nb_iterators
= pbb_dim_iter_domain (pbb
);
480 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
484 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
486 dc
= isl_set_get_space (pbb
->domain
);
487 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
488 isl_dim_out
, scattering_dimensions
);
489 pbb
->schedule
= isl_map_universe (dm
);
491 for (i
= 0; i
< scattering_dimensions
; i
++)
493 /* Textual order inside this loop. */
496 isl_constraint
*c
= isl_equality_alloc
497 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
499 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
501 val
= isl_val_neg (val
);
502 c
= isl_constraint_set_constant_val (c
, val
);
503 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
504 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
507 /* Iterations of this loop. */
508 else /* if ((i % 2) == 1) */
510 int loop
= (i
- 1) / 2;
511 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
516 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
519 /* Build for BB the static schedule.
521 The static schedule is a Dewey numbering of the abstract syntax
522 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
524 The following example informally defines the static schedule:
543 Static schedules for A to F:
556 build_scop_scattering (scop_p scop
)
560 gimple_bb_p previous_gbb
= NULL
;
561 isl_space
*dc
= isl_set_get_space (scop
->context
);
562 isl_aff
*static_sched
;
564 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
565 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
567 /* We have to start schedules at 0 on the first component and
568 because we cannot compare_prefix_loops against a previous loop,
569 prefix will be equal to zero, and that index will be
570 incremented before copying. */
571 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
573 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
575 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
577 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
580 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
586 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
588 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
591 isl_aff_free (static_sched
);
594 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
596 /* Extract an affine expression from the chain of recurrence E. */
599 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
601 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
602 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
603 isl_local_space
*ls
= isl_local_space_from_space (space
);
604 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
605 isl_aff
*loop
= isl_aff_set_coefficient_si
606 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
607 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
609 /* Before multiplying, make sure that the result is affine. */
610 gcc_assert (isl_pw_aff_is_cst (rhs
)
611 || isl_pw_aff_is_cst (l
));
613 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
616 /* Extract an affine expression from the mult_expr E. */
619 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
621 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
622 isl_space_copy (space
));
623 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
625 if (!isl_pw_aff_is_cst (lhs
)
626 && !isl_pw_aff_is_cst (rhs
))
628 isl_pw_aff_free (lhs
);
629 isl_pw_aff_free (rhs
);
633 return isl_pw_aff_mul (lhs
, rhs
);
636 /* Return an ISL identifier from the name of the ssa_name E. */
639 isl_id_for_ssa_name (scop_p s
, tree e
)
641 const char *name
= get_name (e
);
645 id
= isl_id_alloc (s
->ctx
, name
, e
);
649 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
650 id
= isl_id_alloc (s
->ctx
, name1
, e
);
656 /* Return an ISL identifier for the data reference DR. */
659 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
661 /* Data references all get the same isl_id. They need to be comparable
662 and are distinguished through the first dimension, which contains the
664 return isl_id_alloc (s
->ctx
, "", 0);
667 /* Extract an affine expression from the ssa_name E. */
670 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
677 id
= isl_id_for_ssa_name (s
, e
);
678 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
680 dom
= isl_set_universe (isl_space_copy (space
));
681 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
682 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
683 return isl_pw_aff_alloc (dom
, aff
);
686 /* Extract an affine expression from the gmp constant G. */
689 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
691 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
692 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
693 isl_set
*dom
= isl_set_universe (space
);
697 ct
= isl_aff_get_ctx (aff
);
698 v
= isl_val_int_from_gmp (ct
, g
);
699 aff
= isl_aff_add_constant_val (aff
, v
);
701 return isl_pw_aff_alloc (dom
, aff
);
704 /* Extract an affine expression from the integer_cst E. */
707 extract_affine_int (tree e
, __isl_take isl_space
*space
)
713 tree_int_to_gmp (e
, g
);
714 res
= extract_affine_gmp (g
, space
);
720 /* Compute pwaff mod 2^width. */
722 extern isl_ctx
*the_isl_ctx
;
725 wrap (isl_pw_aff
*pwaff
, unsigned width
)
729 mod
= isl_val_int_from_ui(the_isl_ctx
, width
);
730 mod
= isl_val_2exp (mod
);
731 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
736 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
737 Otherwise returns -1. */
740 parameter_index_in_region_1 (tree name
, sese region
)
745 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
747 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
754 /* When the parameter NAME is in REGION, returns its index in
755 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
756 and returns the index of NAME. */
759 parameter_index_in_region (tree name
, sese region
)
763 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
765 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
766 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
769 i
= parameter_index_in_region_1 (name
, region
);
773 gcc_assert (SESE_ADD_PARAMS (region
));
775 i
= SESE_PARAMS (region
).length ();
776 SESE_PARAMS (region
).safe_push (name
);
780 /* Extract an affine expression from the tree E in the scop S. */
783 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
785 isl_pw_aff
*lhs
, *rhs
, *res
;
788 if (e
== chrec_dont_know
) {
789 isl_space_free (space
);
793 switch (TREE_CODE (e
))
795 case POLYNOMIAL_CHREC
:
796 res
= extract_affine_chrec (s
, e
, space
);
800 res
= extract_affine_mul (s
, e
, space
);
804 case POINTER_PLUS_EXPR
:
805 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
806 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
807 res
= isl_pw_aff_add (lhs
, rhs
);
811 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
812 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
813 res
= isl_pw_aff_sub (lhs
, rhs
);
818 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
819 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
820 res
= isl_pw_aff_mul (lhs
, rhs
);
824 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
825 res
= extract_affine_name (s
, e
, space
);
829 res
= extract_affine_int (e
, space
);
830 /* No need to wrap a single integer. */
834 case NON_LVALUE_EXPR
:
835 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
843 type
= TREE_TYPE (e
);
844 if (TYPE_UNSIGNED (type
))
845 res
= wrap (res
, TYPE_PRECISION (type
));
850 /* In the context of sese S, scan the expression E and translate it to
851 a linear expression C. When parsing a symbolic multiplication, K
852 represents the constant multiplier of an expression containing
856 scan_tree_for_params (sese s
, tree e
)
858 if (e
== chrec_dont_know
)
861 switch (TREE_CODE (e
))
863 case POLYNOMIAL_CHREC
:
864 scan_tree_for_params (s
, CHREC_LEFT (e
));
868 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
869 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
871 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
875 case POINTER_PLUS_EXPR
:
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
878 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
884 case NON_LVALUE_EXPR
:
885 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
889 parameter_index_in_region (e
, s
);
905 /* Find parameters with respect to REGION in BB. We are looking in memory
906 access functions, conditions and loop bounds. */
909 find_params_in_bb (sese region
, gimple_bb_p gbb
)
915 loop_p loop
= GBB_BB (gbb
)->loop_father
;
917 /* Find parameters in the access functions of data references. */
918 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
919 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
920 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
922 /* Find parameters in conditional statements. */
923 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
925 tree lhs
= scalar_evolution_in_region (region
, loop
,
926 gimple_cond_lhs (stmt
));
927 tree rhs
= scalar_evolution_in_region (region
, loop
,
928 gimple_cond_rhs (stmt
));
930 scan_tree_for_params (region
, lhs
);
931 scan_tree_for_params (region
, rhs
);
935 /* Record the parameters used in the SCOP. A variable is a parameter
936 in a scop if it does not vary during the execution of that scop. */
939 find_scop_parameters (scop_p scop
)
943 sese region
= SCOP_REGION (scop
);
947 /* Find the parameters used in the loop bounds. */
948 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
950 tree nb_iters
= number_of_latch_executions (loop
);
952 if (!chrec_contains_symbols (nb_iters
))
955 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
956 scan_tree_for_params (region
, nb_iters
);
959 /* Find the parameters used in data accesses. */
960 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
961 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
963 nbp
= sese_nb_params (region
);
964 scop_set_nb_params (scop
, nbp
);
965 SESE_ADD_PARAMS (region
) = false;
969 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
971 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
972 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
973 isl_id_for_ssa_name (scop
, e
));
975 scop
->context
= isl_set_universe (space
);
979 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
980 the constraints for the surrounding loops. */
983 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
985 isl_set
*outer
, isl_set
**doms
)
987 tree nb_iters
= number_of_latch_executions (loop
);
988 sese region
= SCOP_REGION (scop
);
990 isl_set
*inner
= isl_set_copy (outer
);
993 int pos
= isl_set_dim (outer
, isl_dim_set
);
999 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1000 space
= isl_set_get_space (inner
);
1003 c
= isl_inequality_alloc
1004 (isl_local_space_from_space (isl_space_copy (space
)));
1005 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1006 inner
= isl_set_add_constraint (inner
, c
);
1008 /* loop_i <= cst_nb_iters */
1009 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1011 c
= isl_inequality_alloc
1012 (isl_local_space_from_space (isl_space_copy (space
)));
1013 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1014 tree_int_to_gmp (nb_iters
, g
);
1015 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1016 c
= isl_constraint_set_constant_val (c
, v
);
1017 inner
= isl_set_add_constraint (inner
, c
);
1020 /* loop_i <= expr_nb_iters */
1021 else if (!chrec_contains_undetermined (nb_iters
))
1026 isl_local_space
*ls
;
1030 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1032 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1033 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1034 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1035 isl_set_dim (valid
, isl_dim_set
));
1036 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1038 ls
= isl_local_space_from_space (isl_space_copy (space
));
1039 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1040 isl_dim_in
, pos
, 1);
1041 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1042 isl_pw_aff_copy (aff
));
1043 inner
= isl_set_intersect (inner
, le
);
1045 if (max_stmt_executions (loop
, &nit
))
1047 /* Insert in the context the constraints from the
1048 estimation of the number of iterations NIT and the
1049 symbolic number of iterations (involving parameter
1050 names) NB_ITERS. First, build the affine expression
1051 "NIT - NB_ITERS" and then say that it is positive,
1052 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1059 wi::to_mpz (nit
, g
, SIGNED
);
1060 mpz_sub_ui (g
, g
, 1);
1061 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1062 x
= isl_pw_aff_ge_set (approx
, aff
);
1063 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1064 isl_set_dim (x
, isl_dim_set
));
1065 scop
->context
= isl_set_intersect (scop
->context
, x
);
1067 c
= isl_inequality_alloc
1068 (isl_local_space_from_space (isl_space_copy (space
)));
1069 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1070 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1072 c
= isl_constraint_set_constant_val (c
, v
);
1073 inner
= isl_set_add_constraint (inner
, c
);
1076 isl_pw_aff_free (aff
);
1081 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1082 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1083 isl_set_copy (inner
), doms
);
1087 && loop_in_sese_p (loop
->next
, region
))
1088 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1089 isl_set_copy (outer
), doms
);
1091 doms
[loop
->num
] = inner
;
1093 isl_set_free (outer
);
1094 isl_space_free (space
);
1098 /* Returns a linear expression for tree T evaluated in PBB. */
1101 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1103 scop_p scop
= PBB_SCOP (pbb
);
1105 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1106 gcc_assert (!automatically_generated_chrec_p (t
));
1108 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1111 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1112 operator. This allows us to invert the condition or to handle
1116 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1118 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1119 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1125 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1133 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1137 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1141 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1145 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1149 isl_pw_aff_free (lhs
);
1150 isl_pw_aff_free (rhs
);
1154 cond
= isl_set_coalesce (cond
);
1155 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1156 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1159 /* Add conditions to the domain of PBB. */
1162 add_conditions_to_domain (poly_bb_p pbb
)
1166 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1168 if (GBB_CONDITIONS (gbb
).is_empty ())
1171 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1172 switch (gimple_code (stmt
))
1176 /* Don't constrain on anything else than INTEGER_TYPE. */
1177 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1180 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1181 enum tree_code code
= gimple_cond_code (cond_stmt
);
1183 /* The conditions for ELSE-branches are inverted. */
1184 if (!GBB_CONDITION_CASES (gbb
)[i
])
1185 code
= invert_tree_comparison (code
, false);
1187 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1192 /* Switch statements are not supported right now - fall through. */
1200 /* Traverses all the GBBs of the SCOP and add their constraints to the
1201 iteration domains. */
1204 add_conditions_to_constraints (scop_p scop
)
1209 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1210 add_conditions_to_domain (pbb
);
1213 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1214 edge between BB and its predecessor is not a loop exit edge, and
1215 the last statement of the single predecessor is a COND_EXPR. */
1218 single_pred_cond_non_loop_exit (basic_block bb
)
1220 if (single_pred_p (bb
))
1222 edge e
= single_pred_edge (bb
);
1223 basic_block pred
= e
->src
;
1226 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1229 stmt
= last_stmt (pred
);
1231 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1232 return as_a
<gcond
*> (stmt
);
1238 class sese_dom_walker
: public dom_walker
1241 sese_dom_walker (cdi_direction
, sese
);
1243 virtual void before_dom_children (basic_block
);
1244 virtual void after_dom_children (basic_block
);
1247 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1251 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1252 : dom_walker (direction
), m_region (region
)
1256 /* Call-back for dom_walk executed before visiting the dominated
1260 sese_dom_walker::before_dom_children (basic_block bb
)
1265 if (!bb_in_sese_p (bb
, m_region
))
1268 stmt
= single_pred_cond_non_loop_exit (bb
);
1272 edge e
= single_pred_edge (bb
);
1274 m_conditions
.safe_push (stmt
);
1276 if (e
->flags
& EDGE_TRUE_VALUE
)
1277 m_cases
.safe_push (stmt
);
1279 m_cases
.safe_push (NULL
);
1282 gbb
= gbb_from_bb (bb
);
1286 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1287 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1291 /* Call-back for dom_walk executed after visiting the dominated
1295 sese_dom_walker::after_dom_children (basic_block bb
)
1297 if (!bb_in_sese_p (bb
, m_region
))
1300 if (single_pred_cond_non_loop_exit (bb
))
1302 m_conditions
.pop ();
1307 /* Add constraints on the possible values of parameter P from the type
1311 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1313 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1314 tree type
= TREE_TYPE (parameter
);
1315 tree lb
= NULL_TREE
;
1316 tree ub
= NULL_TREE
;
1318 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1319 lb
= lower_bound_in_type (type
, type
);
1321 lb
= TYPE_MIN_VALUE (type
);
1323 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1324 ub
= upper_bound_in_type (type
, type
);
1326 ub
= TYPE_MAX_VALUE (type
);
1330 isl_space
*space
= isl_set_get_space (scop
->context
);
1335 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1337 tree_int_to_gmp (lb
, g
);
1338 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1339 v
= isl_val_neg (v
);
1341 c
= isl_constraint_set_constant_val (c
, v
);
1342 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1344 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1349 isl_space
*space
= isl_set_get_space (scop
->context
);
1354 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1357 tree_int_to_gmp (ub
, g
);
1358 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1360 c
= isl_constraint_set_constant_val (c
, v
);
1361 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1363 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1367 /* Build the context of the SCOP. The context usually contains extra
1368 constraints that are added to the iteration domains that constrain
1372 build_scop_context (scop_p scop
)
1374 graphite_dim_t p
, n
= scop_nb_params (scop
);
1376 for (p
= 0; p
< n
; p
++)
1377 add_param_constraints (scop
, p
);
1380 /* Build the iteration domains: the loops belonging to the current
1381 SCOP, and that vary for the execution of the current basic block.
1382 Returns false if there is no loop in SCOP. */
1385 build_scop_iteration_domain (scop_p scop
)
1388 sese region
= SCOP_REGION (scop
);
1391 int nb_loops
= number_of_loops (cfun
);
1392 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1394 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1395 if (!loop_in_sese_p (loop_outer (loop
), region
))
1396 build_loop_iteration_domains (scop
, loop
, 0,
1397 isl_set_copy (scop
->context
), doms
);
1399 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1401 loop
= pbb_loop (pbb
);
1403 if (doms
[loop
->num
])
1404 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1406 pbb
->domain
= isl_set_copy (scop
->context
);
1408 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1409 isl_id_for_pbb (scop
, pbb
));
1412 for (i
= 0; i
< nb_loops
; i
++)
1414 isl_set_free (doms
[i
]);
1419 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1420 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1421 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1425 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1428 int alias_set_num
= 0;
1429 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1431 if (bap
&& bap
->alias_set
)
1432 alias_set_num
= *(bap
->alias_set
);
1434 c
= isl_equality_alloc
1435 (isl_local_space_from_space (isl_map_get_space (acc
)));
1436 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1437 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1439 return isl_map_add_constraint (acc
, c
);
1442 /* Assign the affine expression INDEX to the output dimension POS of
1443 MAP and return the result. */
1446 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1449 int len
= isl_map_dim (map
, isl_dim_out
);
1452 index_map
= isl_map_from_pw_aff (index
);
1453 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1454 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1456 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1457 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1458 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1459 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1461 return isl_map_intersect (map
, index_map
);
1464 /* Add to ACCESSES polyhedron equalities defining the access functions
1465 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1466 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1467 PBB is the poly_bb_p that contains the data reference DR. */
1470 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1472 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1473 scop_p scop
= PBB_SCOP (pbb
);
1475 for (i
= 0; i
< nb_subscripts
; i
++)
1478 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1480 aff
= extract_affine (scop
, afn
,
1481 isl_space_domain (isl_map_get_space (acc
)));
1482 acc
= set_index (acc
, i
+ 1, aff
);
1488 /* Add constrains representing the size of the accessed data to the
1489 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1490 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1494 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1496 tree ref
= DR_REF (dr
);
1497 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1499 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1503 if (TREE_CODE (ref
) != ARRAY_REF
)
1506 low
= array_ref_low_bound (ref
);
1507 high
= array_ref_up_bound (ref
);
1509 /* XXX The PPL code dealt separately with
1510 subscript - low >= 0 and high - subscript >= 0 in case one of
1511 the two bounds isn't known. Do the same here? */
1513 if (tree_fits_shwi_p (low
)
1515 && tree_fits_shwi_p (high
)
1516 /* 1-element arrays at end of structures may extend over
1517 their declared size. */
1518 && !(array_at_struct_end_p (ref
)
1519 && operand_equal_p (low
, high
, 0)))
1523 isl_set
*univ
, *lbs
, *ubs
;
1527 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1528 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1531 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1532 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1533 isl_set_dim (valid
, isl_dim_set
));
1534 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1536 space
= isl_set_get_space (extent
);
1537 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1538 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1539 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1540 index
= isl_pw_aff_alloc (univ
, aff
);
1542 id
= isl_set_get_tuple_id (extent
);
1543 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1544 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1546 /* low <= sub_i <= high */
1547 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1548 ubs
= isl_pw_aff_le_set (index
, ub
);
1549 extent
= isl_set_intersect (extent
, lbs
);
1550 extent
= isl_set_intersect (extent
, ubs
);
1557 /* Build data accesses for DR in PBB. */
1560 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1562 int dr_base_object_set
;
1565 scop_p scop
= PBB_SCOP (pbb
);
1568 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1569 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1570 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1571 isl_dim_out
, nb_out
);
1573 acc
= isl_map_universe (space
);
1574 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1577 acc
= pdr_add_alias_set (acc
, dr
);
1578 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1581 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1582 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1583 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1584 int alias_set_num
= 0;
1585 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1587 if (bap
&& bap
->alias_set
)
1588 alias_set_num
= *(bap
->alias_set
);
1590 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1591 extent
= isl_set_nat_universe (space
);
1592 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1593 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1596 gcc_assert (dr
->aux
);
1597 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1599 new_poly_dr (pbb
, dr_base_object_set
,
1600 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1601 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1604 /* Write to FILE the alias graph of data references in DIMACS format. */
1607 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1608 vec
<data_reference_p
> drs
)
1610 int num_vertex
= drs
.length ();
1612 data_reference_p dr1
, dr2
;
1615 if (num_vertex
== 0)
1618 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1619 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1620 if (dr_may_alias_p (dr1
, dr2
, true))
1623 fprintf (file
, "$\n");
1626 fprintf (file
, "c %s\n", comment
);
1628 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1630 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1631 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1632 if (dr_may_alias_p (dr1
, dr2
, true))
1633 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1638 /* Write to FILE the alias graph of data references in DOT format. */
1641 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1642 vec
<data_reference_p
> drs
)
1644 int num_vertex
= drs
.length ();
1645 data_reference_p dr1
, dr2
;
1648 if (num_vertex
== 0)
1651 fprintf (file
, "$\n");
1654 fprintf (file
, "c %s\n", comment
);
1656 /* First print all the vertices. */
1657 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1658 fprintf (file
, "n%d;\n", i
);
1660 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1661 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1662 if (dr_may_alias_p (dr1
, dr2
, true))
1663 fprintf (file
, "n%d n%d\n", i
, j
);
1668 /* Write to FILE the alias graph of data references in ECC format. */
1671 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1672 vec
<data_reference_p
> drs
)
1674 int num_vertex
= drs
.length ();
1675 data_reference_p dr1
, dr2
;
1678 if (num_vertex
== 0)
1681 fprintf (file
, "$\n");
1684 fprintf (file
, "c %s\n", comment
);
1686 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1687 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1688 if (dr_may_alias_p (dr1
, dr2
, true))
1689 fprintf (file
, "%d %d\n", i
, j
);
1694 /* Check if DR1 and DR2 are in the same object set. */
1697 dr_same_base_object_p (const struct data_reference
*dr1
,
1698 const struct data_reference
*dr2
)
1700 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1703 /* Uses DFS component number as representative of alias-sets. Also tests for
1704 optimality by verifying if every connected component is a clique. Returns
1705 true (1) if the above test is true, and false (0) otherwise. */
1708 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1710 int num_vertices
= drs
.length ();
1711 struct graph
*g
= new_graph (num_vertices
);
1712 data_reference_p dr1
, dr2
;
1714 int num_connected_components
;
1715 int v_indx1
, v_indx2
, num_vertices_in_component
;
1718 struct graph_edge
*e
;
1719 int this_component_is_clique
;
1720 int all_components_are_cliques
= 1;
1722 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1723 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1724 if (dr_may_alias_p (dr1
, dr2
, true))
1730 all_vertices
= XNEWVEC (int, num_vertices
);
1731 vertices
= XNEWVEC (int, num_vertices
);
1732 for (i
= 0; i
< num_vertices
; i
++)
1733 all_vertices
[i
] = i
;
1735 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1737 for (i
= 0; i
< g
->n_vertices
; i
++)
1739 data_reference_p dr
= drs
[i
];
1740 base_alias_pair
*bap
;
1742 gcc_assert (dr
->aux
);
1743 bap
= (base_alias_pair
*)(dr
->aux
);
1745 bap
->alias_set
= XNEW (int);
1746 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1749 /* Verify if the DFS numbering results in optimal solution. */
1750 for (i
= 0; i
< num_connected_components
; i
++)
1752 num_vertices_in_component
= 0;
1753 /* Get all vertices whose DFS component number is the same as i. */
1754 for (j
= 0; j
< num_vertices
; j
++)
1755 if (g
->vertices
[j
].component
== i
)
1756 vertices
[num_vertices_in_component
++] = j
;
1758 /* Now test if the vertices in 'vertices' form a clique, by testing
1759 for edges among each pair. */
1760 this_component_is_clique
= 1;
1761 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1763 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1765 /* Check if the two vertices are connected by iterating
1766 through all the edges which have one of these are source. */
1767 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1770 if (e
->src
== vertices
[v_indx1
])
1776 this_component_is_clique
= 0;
1780 if (!this_component_is_clique
)
1781 all_components_are_cliques
= 0;
1785 free (all_vertices
);
1788 return all_components_are_cliques
;
1791 /* Group each data reference in DRS with its base object set num. */
1794 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1796 int num_vertex
= drs
.length ();
1797 struct graph
*g
= new_graph (num_vertex
);
1798 data_reference_p dr1
, dr2
;
1802 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1803 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1804 if (dr_same_base_object_p (dr1
, dr2
))
1810 queue
= XNEWVEC (int, num_vertex
);
1811 for (i
= 0; i
< num_vertex
; i
++)
1814 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1816 for (i
= 0; i
< g
->n_vertices
; i
++)
1818 data_reference_p dr
= drs
[i
];
1819 base_alias_pair
*bap
;
1821 gcc_assert (dr
->aux
);
1822 bap
= (base_alias_pair
*)(dr
->aux
);
1824 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1831 /* Build the data references for PBB. */
1834 build_pbb_drs (poly_bb_p pbb
)
1837 data_reference_p dr
;
1838 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1840 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1841 build_poly_dr (dr
, pbb
);
1844 /* Dump to file the alias graphs for the data references in DRS. */
1847 dump_alias_graphs (vec
<data_reference_p
> drs
)
1850 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1852 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1855 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1856 current_function_name ());
1857 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1858 fclose (file_dimacs
);
1861 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1864 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1865 current_function_name ());
1866 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1870 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1873 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1874 current_function_name ());
1875 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1880 /* Build data references in SCOP. */
1883 build_scop_drs (scop_p scop
)
1887 data_reference_p dr
;
1888 auto_vec
<data_reference_p
, 3> drs
;
1890 /* Remove all the PBBs that do not have data references: these basic
1891 blocks are not handled in the polyhedral representation. */
1892 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1893 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1895 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1897 SCOP_BBS (scop
).ordered_remove (i
);
1901 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1902 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1905 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1906 dr
->aux
= XNEW (base_alias_pair
);
1908 if (!build_alias_set_optimal_p (drs
))
1910 /* TODO: Add support when building alias set is not optimal. */
1914 build_base_obj_set_for_drs (drs
);
1916 /* When debugging, enable the following code. This cannot be used
1917 in production compilers. */
1919 dump_alias_graphs (drs
);
1923 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1924 build_pbb_drs (pbb
);
1927 /* Return a gsi at the position of the phi node STMT. */
1929 static gphi_iterator
1930 gsi_for_phi_node (gphi
*stmt
)
1933 basic_block bb
= gimple_bb (stmt
);
1935 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1936 if (stmt
== psi
.phi ())
1943 /* Analyze all the data references of STMTS and add them to the
1944 GBB_DATA_REFS vector of BB. */
1947 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1953 sese region
= SCOP_REGION (scop
);
1955 if (!bb_in_sese_p (bb
, region
))
1958 nest
= outermost_loop_in_sese_1 (region
, bb
);
1959 gbb
= gbb_from_bb (bb
);
1961 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1965 if (is_gimple_debug (stmt
))
1968 loop
= loop_containing_stmt (stmt
);
1969 if (!loop_in_sese_p (loop
, region
))
1972 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1973 &GBB_DATA_REFS (gbb
));
1977 /* Insert STMT at the end of the STMTS sequence and then insert the
1978 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1982 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1983 gimple_stmt_iterator insert_gsi
)
1985 gimple_stmt_iterator gsi
;
1986 auto_vec
<gimple
, 3> x
;
1988 gimple_seq_add_stmt (&stmts
, stmt
);
1989 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1990 x
.safe_push (gsi_stmt (gsi
));
1992 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1993 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1996 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1999 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2002 gimple_stmt_iterator gsi
;
2003 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2004 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2005 auto_vec
<gimple
, 3> x
;
2007 gimple_seq_add_stmt (&stmts
, stmt
);
2008 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2009 x
.safe_push (gsi_stmt (gsi
));
2011 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2013 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2014 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2018 gsi
= gsi_for_stmt (after_stmt
);
2019 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2022 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2025 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2028 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2030 vec
<data_reference_p
> drs
;
2032 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2033 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2034 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2035 int index
, n
= SCOP_BBS (scop
).length ();
2037 /* The INDEX of PBB in SCOP_BBS. */
2038 for (index
= 0; index
< n
; index
++)
2039 if (SCOP_BBS (scop
)[index
] == pbb
)
2042 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2043 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2044 isl_id_for_pbb (scop
, pbb1
));
2046 GBB_PBB (gbb1
) = pbb1
;
2047 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2048 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2049 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2052 /* Insert on edge E the assignment "RES := EXPR". */
2055 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2057 gimple_stmt_iterator gsi
;
2058 gimple_seq stmts
= NULL
;
2059 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2060 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2062 auto_vec
<gimple
, 3> x
;
2064 gimple_seq_add_stmt (&stmts
, stmt
);
2065 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2066 x
.safe_push (gsi_stmt (gsi
));
2068 gsi_insert_seq_on_edge (e
, stmts
);
2069 gsi_commit_edge_inserts ();
2070 bb
= gimple_bb (stmt
);
2072 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2075 if (!gbb_from_bb (bb
))
2076 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2078 analyze_drs_in_stmts (scop
, bb
, x
);
2081 /* Creates a zero dimension array of the same type as VAR. */
2084 create_zero_dim_array (tree var
, const char *base_name
)
2086 tree index_type
= build_index_type (integer_zero_node
);
2087 tree elt_type
= TREE_TYPE (var
);
2088 tree array_type
= build_array_type (elt_type
, index_type
);
2089 tree base
= create_tmp_var (array_type
, base_name
);
2091 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2095 /* Returns true when PHI is a loop close phi node. */
2098 scalar_close_phi_node_p (gimple phi
)
2100 if (gimple_code (phi
) != GIMPLE_PHI
2101 || virtual_operand_p (gimple_phi_result (phi
)))
2104 /* Note that loop close phi nodes should have a single argument
2105 because we translated the representation into a canonical form
2106 before Graphite: see canonicalize_loop_closed_ssa_form. */
2107 return (gimple_phi_num_args (phi
) == 1);
2110 /* For a definition DEF in REGION, propagates the expression EXPR in
2111 all the uses of DEF outside REGION. */
2114 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2116 imm_use_iterator imm_iter
;
2119 bool replaced_once
= false;
2121 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2123 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2126 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2127 if (!is_gimple_debug (use_stmt
)
2128 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2131 use_operand_p use_p
;
2133 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2134 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2135 && (replaced_once
= true))
2136 replace_exp (use_p
, expr
);
2138 update_stmt (use_stmt
);
2143 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2144 gsi_commit_edge_inserts ();
2148 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2149 dimension array for it. */
2152 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2154 sese region
= SCOP_REGION (scop
);
2155 gimple phi
= gsi_stmt (*psi
);
2156 tree res
= gimple_phi_result (phi
);
2157 basic_block bb
= gimple_bb (phi
);
2158 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2159 tree arg
= gimple_phi_arg_def (phi
, 0);
2162 /* Note that loop close phi nodes should have a single argument
2163 because we translated the representation into a canonical form
2164 before Graphite: see canonicalize_loop_closed_ssa_form. */
2165 gcc_assert (gimple_phi_num_args (phi
) == 1);
2167 /* The phi node can be a non close phi node, when its argument is
2168 invariant, or a default definition. */
2169 if (is_gimple_min_invariant (arg
)
2170 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2172 propagate_expr_outside_region (res
, arg
, region
);
2177 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2179 propagate_expr_outside_region (res
, arg
, region
);
2180 stmt
= gimple_build_assign (res
, arg
);
2181 remove_phi_node (psi
, false);
2182 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2186 /* If res is scev analyzable and is not a scalar value, it is safe
2187 to ignore the close phi node: it will be code generated in the
2188 out of Graphite pass. */
2189 else if (scev_analyzable_p (res
, region
))
2191 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2194 if (!loop_in_sese_p (loop
, region
))
2196 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2197 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2198 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2201 scev
= scalar_evolution_in_region (region
, loop
, res
);
2203 if (tree_does_not_contain_chrecs (scev
))
2204 propagate_expr_outside_region (res
, scev
, region
);
2211 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2213 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2215 if (TREE_CODE (arg
) == SSA_NAME
)
2216 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2217 SSA_NAME_DEF_STMT (arg
));
2219 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2220 zero_dim_array
, arg
);
2223 remove_phi_node (psi
, false);
2224 SSA_NAME_DEF_STMT (res
) = stmt
;
2226 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2229 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2230 dimension array for it. */
2233 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2236 gphi
*phi
= psi
->phi ();
2237 basic_block bb
= gimple_bb (phi
);
2238 tree res
= gimple_phi_result (phi
);
2239 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2242 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2244 tree arg
= gimple_phi_arg_def (phi
, i
);
2245 edge e
= gimple_phi_arg_edge (phi
, i
);
2247 /* Avoid the insertion of code in the loop latch to please the
2248 pattern matching of the vectorizer. */
2249 if (TREE_CODE (arg
) == SSA_NAME
2250 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2251 && e
->src
== bb
->loop_father
->latch
)
2252 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2253 SSA_NAME_DEF_STMT (arg
));
2255 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2258 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2259 remove_phi_node (psi
, false);
2260 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2263 /* Rewrite the degenerate phi node at position PSI from the degenerate
2264 form "x = phi (y, y, ..., y)" to "x = y". */
2267 rewrite_degenerate_phi (gphi_iterator
*psi
)
2271 gimple_stmt_iterator gsi
;
2272 gphi
*phi
= psi
->phi ();
2273 tree res
= gimple_phi_result (phi
);
2276 bb
= gimple_bb (phi
);
2277 rhs
= degenerate_phi_result (phi
);
2280 stmt
= gimple_build_assign (res
, rhs
);
2281 remove_phi_node (psi
, false);
2283 gsi
= gsi_after_labels (bb
);
2284 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2287 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2290 rewrite_reductions_out_of_ssa (scop_p scop
)
2294 sese region
= SCOP_REGION (scop
);
2296 FOR_EACH_BB_FN (bb
, cfun
)
2297 if (bb_in_sese_p (bb
, region
))
2298 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2300 gphi
*phi
= psi
.phi ();
2302 if (virtual_operand_p (gimple_phi_result (phi
)))
2308 if (gimple_phi_num_args (phi
) > 1
2309 && degenerate_phi_result (phi
))
2310 rewrite_degenerate_phi (&psi
);
2312 else if (scalar_close_phi_node_p (phi
))
2313 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2315 else if (reduction_phi_p (region
, &psi
))
2316 rewrite_phi_out_of_ssa (scop
, &psi
);
2319 update_ssa (TODO_update_ssa
);
2320 #ifdef ENABLE_CHECKING
2321 verify_loop_closed_ssa (true);
2325 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2326 read from ZERO_DIM_ARRAY. */
2329 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2330 tree def
, gimple use_stmt
)
2335 use_operand_p use_p
;
2337 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2339 name
= copy_ssa_name (def
);
2340 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2342 gimple_assign_set_lhs (name_stmt
, name
);
2343 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2345 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2346 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2347 replace_exp (use_p
, name
);
2349 update_stmt (use_stmt
);
2352 /* For every definition DEF in the SCOP that is used outside the scop,
2353 insert a closing-scop definition in the basic block just after this
2357 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2359 tree var
= create_tmp_reg (TREE_TYPE (def
));
2360 tree new_name
= make_ssa_name (var
, stmt
);
2361 bool needs_copy
= false;
2362 use_operand_p use_p
;
2363 imm_use_iterator imm_iter
;
2365 sese region
= SCOP_REGION (scop
);
2367 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2369 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2371 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2373 SET_USE (use_p
, new_name
);
2375 update_stmt (use_stmt
);
2380 /* Insert in the empty BB just after the scop a use of DEF such
2381 that the rewrite of cross_bb_scalar_dependences won't insert
2382 arrays everywhere else. */
2385 gimple assign
= gimple_build_assign (new_name
, def
);
2386 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2388 update_stmt (assign
);
2389 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2393 /* Rewrite the scalar dependences crossing the boundary of the BB
2394 containing STMT with an array. Return true when something has been
2398 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2400 sese region
= SCOP_REGION (scop
);
2401 gimple stmt
= gsi_stmt (*gsi
);
2402 imm_use_iterator imm_iter
;
2405 tree zero_dim_array
= NULL_TREE
;
2409 switch (gimple_code (stmt
))
2412 def
= gimple_assign_lhs (stmt
);
2416 def
= gimple_call_lhs (stmt
);
2424 || !is_gimple_reg (def
))
2427 if (scev_analyzable_p (def
, region
))
2429 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2430 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2432 if (tree_contains_chrecs (scev
, NULL
))
2435 propagate_expr_outside_region (def
, scev
, region
);
2439 def_bb
= gimple_bb (stmt
);
2441 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2443 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2444 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2447 gphi_iterator psi
= gsi_for_phi (phi
);
2449 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2450 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2452 rewrite_phi_out_of_ssa (scop
, &psi
);
2455 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2456 if (gimple_code (use_stmt
) != GIMPLE_PHI
2457 && def_bb
!= gimple_bb (use_stmt
)
2458 && !is_gimple_debug (use_stmt
)
2461 if (!zero_dim_array
)
2463 zero_dim_array
= create_zero_dim_array
2464 (def
, "Cross_BB_scalar_dependence");
2465 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2466 SSA_NAME_DEF_STMT (def
));
2470 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2477 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2480 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2483 gimple_stmt_iterator psi
;
2484 sese region
= SCOP_REGION (scop
);
2485 bool changed
= false;
2487 /* Create an extra empty BB after the scop. */
2488 split_edge (SESE_EXIT (region
));
2490 FOR_EACH_BB_FN (bb
, cfun
)
2491 if (bb_in_sese_p (bb
, region
))
2492 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2493 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2498 update_ssa (TODO_update_ssa
);
2499 #ifdef ENABLE_CHECKING
2500 verify_loop_closed_ssa (true);
2505 /* Returns the number of pbbs that are in loops contained in SCOP. */
2508 nb_pbbs_in_loops (scop_p scop
)
2514 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2515 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2521 /* Return the number of data references in BB that write in
2525 nb_data_writes_in_bb (basic_block bb
)
2528 gimple_stmt_iterator gsi
;
2530 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2531 if (gimple_vdef (gsi_stmt (gsi
)))
2537 /* Splits at STMT the basic block BB represented as PBB in the
2541 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2543 edge e1
= split_block (bb
, stmt
);
2544 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2548 /* Splits STMT out of its current BB. This is done for reduction
2549 statements for which we want to ignore data dependences. */
2552 split_reduction_stmt (scop_p scop
, gimple stmt
)
2554 basic_block bb
= gimple_bb (stmt
);
2555 poly_bb_p pbb
= pbb_from_bb (bb
);
2556 gimple_bb_p gbb
= gbb_from_bb (bb
);
2559 data_reference_p dr
;
2561 /* Do not split basic blocks with no writes to memory: the reduction
2562 will be the only write to memory. */
2563 if (nb_data_writes_in_bb (bb
) == 0
2564 /* Or if we have already marked BB as a reduction. */
2565 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2568 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2570 /* Split once more only when the reduction stmt is not the only one
2571 left in the original BB. */
2572 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2574 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2576 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2579 /* A part of the data references will end in a different basic block
2580 after the split: move the DRs from the original GBB to the newly
2582 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2584 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2588 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2589 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2590 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2598 /* Return true when stmt is a reduction operation. */
2601 is_reduction_operation_p (gimple stmt
)
2603 enum tree_code code
;
2605 gcc_assert (is_gimple_assign (stmt
));
2606 code
= gimple_assign_rhs_code (stmt
);
2608 return flag_associative_math
2609 && commutative_tree_code (code
)
2610 && associative_tree_code (code
);
2613 /* Returns true when PHI contains an argument ARG. */
2616 phi_contains_arg (gphi
*phi
, tree arg
)
2620 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2621 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2627 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2630 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2634 if (TREE_CODE (arg
) != SSA_NAME
)
2637 stmt
= SSA_NAME_DEF_STMT (arg
);
2639 if (gimple_code (stmt
) == GIMPLE_NOP
2640 || gimple_code (stmt
) == GIMPLE_CALL
)
2643 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2645 if (phi_contains_arg (phi
, lhs
))
2650 if (!is_gimple_assign (stmt
))
2653 if (gimple_num_ops (stmt
) == 2)
2654 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2656 if (is_reduction_operation_p (stmt
))
2659 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2662 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2668 /* Detect commutative and associative scalar reductions starting at
2669 the STMT. Return the phi node of the reduction cycle, or NULL. */
2672 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2676 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2681 in
->safe_push (stmt
);
2682 out
->safe_push (stmt
);
2686 /* Detect commutative and associative scalar reductions starting at
2687 STMT. Return the phi node of the reduction cycle, or NULL. */
2690 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2693 tree lhs
= gimple_assign_lhs (stmt
);
2695 if (gimple_num_ops (stmt
) == 2)
2696 return detect_commutative_reduction_arg (lhs
, stmt
,
2697 gimple_assign_rhs1 (stmt
),
2700 if (is_reduction_operation_p (stmt
))
2702 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2703 gimple_assign_rhs1 (stmt
),
2706 : detect_commutative_reduction_arg (lhs
, stmt
,
2707 gimple_assign_rhs2 (stmt
),
2714 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2717 follow_inital_value_to_phi (tree arg
, tree lhs
)
2721 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2724 stmt
= SSA_NAME_DEF_STMT (arg
);
2726 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2727 if (phi_contains_arg (phi
, lhs
))
2734 /* Return the argument of the loop PHI that is the initial value coming
2735 from outside the loop. */
2738 edge_initial_value_for_loop_phi (gphi
*phi
)
2742 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2744 edge e
= gimple_phi_arg_edge (phi
, i
);
2746 if (loop_depth (e
->src
->loop_father
)
2747 < loop_depth (e
->dest
->loop_father
))
2754 /* Return the argument of the loop PHI that is the initial value coming
2755 from outside the loop. */
2758 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
))
2768 return gimple_phi_arg_def (phi
, i
);
2774 /* Returns true when DEF is used outside the reduction cycle of
2778 used_outside_reduction (tree def
, gimple loop_phi
)
2780 use_operand_p use_p
;
2781 imm_use_iterator imm_iter
;
2782 loop_p loop
= loop_containing_stmt (loop_phi
);
2784 /* In LOOP, DEF should be used only in LOOP_PHI. */
2785 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2787 gimple stmt
= USE_STMT (use_p
);
2789 if (stmt
!= loop_phi
2790 && !is_gimple_debug (stmt
)
2791 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2798 /* Detect commutative and associative scalar reductions belonging to
2799 the SCOP starting at the loop closed phi node STMT. Return the phi
2800 node of the reduction cycle, or NULL. */
2803 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2806 if (scalar_close_phi_node_p (stmt
))
2809 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2810 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2812 if (TREE_CODE (arg
) != SSA_NAME
)
2815 /* Note that loop close phi nodes should have a single argument
2816 because we translated the representation into a canonical form
2817 before Graphite: see canonicalize_loop_closed_ssa_form. */
2818 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2820 def
= SSA_NAME_DEF_STMT (arg
);
2821 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2822 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2825 lhs
= gimple_phi_result (close_phi
);
2826 init
= initial_value_for_loop_phi (loop_phi
);
2827 phi
= follow_inital_value_to_phi (init
, lhs
);
2829 if (phi
&& (used_outside_reduction (lhs
, phi
)
2830 || !has_single_use (gimple_phi_result (phi
))))
2833 in
->safe_push (loop_phi
);
2834 out
->safe_push (close_phi
);
2838 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2839 return detect_commutative_reduction_assign (stmt
, in
, out
);
2844 /* Translate the scalar reduction statement STMT to an array RED
2845 knowing that its recursive phi node is LOOP_PHI. */
2848 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2849 gimple stmt
, gphi
*loop_phi
)
2851 tree res
= gimple_phi_result (loop_phi
);
2852 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2853 gimple_stmt_iterator gsi
;
2855 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2857 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2858 gsi
= gsi_for_stmt (stmt
);
2860 insert_stmts (scop
, assign
, NULL
, gsi
);
2863 /* Removes the PHI node and resets all the debug stmts that are using
2867 remove_phi (gphi
*phi
)
2869 imm_use_iterator imm_iter
;
2871 use_operand_p use_p
;
2872 gimple_stmt_iterator gsi
;
2873 auto_vec
<gimple
, 3> update
;
2877 def
= PHI_RESULT (phi
);
2878 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2880 stmt
= USE_STMT (use_p
);
2882 if (is_gimple_debug (stmt
))
2884 gimple_debug_bind_reset_value (stmt
);
2885 update
.safe_push (stmt
);
2889 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2892 gsi
= gsi_for_phi_node (phi
);
2893 remove_phi_node (&gsi
, false);
2896 /* Helper function for for_each_index. For each INDEX of the data
2897 reference REF, returns true when its indices are valid in the loop
2898 nest LOOP passed in as DATA. */
2901 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2904 basic_block header
, def_bb
;
2907 if (TREE_CODE (*index
) != SSA_NAME
)
2910 loop
= *((loop_p
*) data
);
2911 header
= loop
->header
;
2912 stmt
= SSA_NAME_DEF_STMT (*index
);
2917 def_bb
= gimple_bb (stmt
);
2922 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2925 /* When the result of a CLOSE_PHI is written to a memory location,
2926 return a pointer to that memory reference, otherwise return
2930 close_phi_written_to_memory (gphi
*close_phi
)
2932 imm_use_iterator imm_iter
;
2933 use_operand_p use_p
;
2935 tree res
, def
= gimple_phi_result (close_phi
);
2937 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2938 if ((stmt
= USE_STMT (use_p
))
2939 && gimple_code (stmt
) == GIMPLE_ASSIGN
2940 && (res
= gimple_assign_lhs (stmt
)))
2942 switch (TREE_CODE (res
))
2952 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2953 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2955 /* FIXME: this restriction is for id-{24,25}.f and
2956 could be handled by duplicating the computation of
2957 array indices before the loop of the close_phi. */
2958 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2970 /* Rewrite out of SSA the reduction described by the loop phi nodes
2971 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2974 IN: stmt, loop_n, ..., loop_0
2975 OUT: stmt, close_n, ..., close_0
2977 the first element is the reduction statement, and the next elements
2978 are the loop and close phi nodes of each of the outer loops. */
2981 translate_scalar_reduction_to_array (scop_p scop
,
2986 unsigned int i
= out
.length () - 1;
2987 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
2989 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
2991 gimple close_stmt
= out
[i
];
2995 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
2996 poly_bb_p pbb
= pbb_from_bb (bb
);
2997 PBB_IS_REDUCTION (pbb
) = true;
2998 gcc_assert (close_stmt
== loop_stmt
);
3001 red
= create_zero_dim_array
3002 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3004 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3005 as_a
<gphi
*> (in
[1]));
3009 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3010 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3012 if (i
== in
.length () - 1)
3014 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3015 unshare_expr (red
), close_phi
);
3016 insert_out_of_ssa_copy_on_edge
3017 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3018 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3021 remove_phi (loop_phi
);
3022 remove_phi (close_phi
);
3026 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3027 true when something has been changed. */
3030 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3034 auto_vec
<gimple
, 10> in
;
3035 auto_vec
<gimple
, 10> out
;
3037 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3038 res
= in
.length () > 1;
3040 translate_scalar_reduction_to_array (scop
, in
, out
);
3045 /* Rewrites all the commutative reductions from LOOP out of SSA.
3046 Returns true when something has been changed. */
3049 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3053 edge exit
= single_exit (loop
);
3055 bool changed
= false;
3060 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3061 if ((res
= gimple_phi_result (gsi
.phi ()))
3062 && !virtual_operand_p (res
)
3063 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3064 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3070 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3073 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3076 bool changed
= false;
3077 sese region
= SCOP_REGION (scop
);
3079 FOR_EACH_LOOP (loop
, 0)
3080 if (loop_in_sese_p (loop
, region
))
3081 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3086 gsi_commit_edge_inserts ();
3087 update_ssa (TODO_update_ssa
);
3088 #ifdef ENABLE_CHECKING
3089 verify_loop_closed_ssa (true);
3094 /* Can all ivs be represented by a signed integer?
3095 As CLooG might generate negative values in its expressions, signed loop ivs
3096 are required in the backend. */
3099 scop_ivs_can_be_represented (scop_p scop
)
3105 FOR_EACH_LOOP (loop
, 0)
3107 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3110 for (psi
= gsi_start_phis (loop
->header
);
3111 !gsi_end_p (psi
); gsi_next (&psi
))
3113 gphi
*phi
= psi
.phi ();
3114 tree res
= PHI_RESULT (phi
);
3115 tree type
= TREE_TYPE (res
);
3117 if (TYPE_UNSIGNED (type
)
3118 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3131 /* Builds the polyhedral representation for a SESE region. */
3134 build_poly_scop (scop_p scop
)
3136 sese region
= SCOP_REGION (scop
);
3137 graphite_dim_t max_dim
;
3139 build_scop_bbs (scop
);
3141 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3142 Once CLooG is fixed, remove this guard. Anyways, it makes no
3143 sense to optimize a scop containing only PBBs that do not belong
3145 if (nb_pbbs_in_loops (scop
) == 0)
3148 if (!scop_ivs_can_be_represented (scop
))
3151 if (flag_associative_math
)
3152 rewrite_commutative_reductions_out_of_ssa (scop
);
3154 build_sese_loop_nests (region
);
3155 /* Record all conditions in REGION. */
3156 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3157 find_scop_parameters (scop
);
3159 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3160 if (scop_nb_params (scop
) > max_dim
)
3163 build_scop_iteration_domain (scop
);
3164 build_scop_context (scop
);
3165 add_conditions_to_constraints (scop
);
3167 /* Rewrite out of SSA only after having translated the
3168 representation to the polyhedral representation to avoid scev
3169 analysis failures. That means that these functions will insert
3170 new data references that they create in the right place. */
3171 rewrite_reductions_out_of_ssa (scop
);
3172 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3174 build_scop_drs (scop
);
3176 build_scop_scattering (scop
);
3178 /* This SCoP has been translated to the polyhedral
3180 POLY_SCOP_P (scop
) = true;
3182 #endif /* HAVE_isl */