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);
500 gcc_assert (val
&& isl_val_is_int (val
));
502 val
= isl_val_neg (val
);
503 c
= isl_constraint_set_constant_val (c
, val
);
504 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
505 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
508 /* Iterations of this loop. */
509 else /* if ((i % 2) == 1) */
511 int loop
= (i
- 1) / 2;
512 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
517 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
520 /* Build for BB the static schedule.
522 The static schedule is a Dewey numbering of the abstract syntax
523 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
525 The following example informally defines the static schedule:
544 Static schedules for A to F:
557 build_scop_scattering (scop_p scop
)
561 gimple_bb_p previous_gbb
= NULL
;
562 isl_space
*dc
= isl_set_get_space (scop
->context
);
563 isl_aff
*static_sched
;
565 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
566 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
568 /* We have to start schedules at 0 on the first component and
569 because we cannot compare_prefix_loops against a previous loop,
570 prefix will be equal to zero, and that index will be
571 incremented before copying. */
572 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
574 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
576 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
578 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
581 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
587 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
589 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
592 isl_aff_free (static_sched
);
595 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
597 /* Extract an affine expression from the chain of recurrence E. */
600 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
602 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
603 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
604 isl_local_space
*ls
= isl_local_space_from_space (space
);
605 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
606 isl_aff
*loop
= isl_aff_set_coefficient_si
607 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
608 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
610 /* Before multiplying, make sure that the result is affine. */
611 gcc_assert (isl_pw_aff_is_cst (rhs
)
612 || isl_pw_aff_is_cst (l
));
614 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
617 /* Extract an affine expression from the mult_expr E. */
620 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
622 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
623 isl_space_copy (space
));
624 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
626 if (!isl_pw_aff_is_cst (lhs
)
627 && !isl_pw_aff_is_cst (rhs
))
629 isl_pw_aff_free (lhs
);
630 isl_pw_aff_free (rhs
);
634 return isl_pw_aff_mul (lhs
, rhs
);
637 /* Return an ISL identifier from the name of the ssa_name E. */
640 isl_id_for_ssa_name (scop_p s
, tree e
)
642 const char *name
= get_name (e
);
646 id
= isl_id_alloc (s
->ctx
, name
, e
);
650 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
651 id
= isl_id_alloc (s
->ctx
, name1
, e
);
657 /* Return an ISL identifier for the data reference DR. */
660 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
662 /* Data references all get the same isl_id. They need to be comparable
663 and are distinguished through the first dimension, which contains the
665 return isl_id_alloc (s
->ctx
, "", 0);
668 /* Extract an affine expression from the ssa_name E. */
671 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
678 id
= isl_id_for_ssa_name (s
, e
);
679 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
681 dom
= isl_set_universe (isl_space_copy (space
));
682 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
683 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
684 return isl_pw_aff_alloc (dom
, aff
);
687 /* Extract an affine expression from the gmp constant G. */
690 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
692 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
693 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
694 isl_set
*dom
= isl_set_universe (space
);
698 ct
= isl_aff_get_ctx (aff
);
699 v
= isl_val_int_from_gmp (ct
, g
);
700 aff
= isl_aff_add_constant_val (aff
, v
);
702 return isl_pw_aff_alloc (dom
, aff
);
705 /* Extract an affine expression from the integer_cst E. */
708 extract_affine_int (tree e
, __isl_take isl_space
*space
)
714 tree_int_to_gmp (e
, g
);
715 res
= extract_affine_gmp (g
, space
);
721 /* Compute pwaff mod 2^width. */
724 wrap (isl_pw_aff
*pwaff
, unsigned width
)
728 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
729 mod
= isl_val_2exp (mod
);
730 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
735 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
736 Otherwise returns -1. */
739 parameter_index_in_region_1 (tree name
, sese region
)
744 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
746 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
753 /* When the parameter NAME is in REGION, returns its index in
754 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
755 and returns the index of NAME. */
758 parameter_index_in_region (tree name
, sese region
)
762 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
764 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
765 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
768 i
= parameter_index_in_region_1 (name
, region
);
772 gcc_assert (SESE_ADD_PARAMS (region
));
774 i
= SESE_PARAMS (region
).length ();
775 SESE_PARAMS (region
).safe_push (name
);
779 /* Extract an affine expression from the tree E in the scop S. */
782 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
784 isl_pw_aff
*lhs
, *rhs
, *res
;
787 if (e
== chrec_dont_know
) {
788 isl_space_free (space
);
792 switch (TREE_CODE (e
))
794 case POLYNOMIAL_CHREC
:
795 res
= extract_affine_chrec (s
, e
, space
);
799 res
= extract_affine_mul (s
, e
, space
);
803 case POINTER_PLUS_EXPR
:
804 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
805 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
806 res
= isl_pw_aff_add (lhs
, rhs
);
810 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
811 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
812 res
= isl_pw_aff_sub (lhs
, rhs
);
817 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
818 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
819 res
= isl_pw_aff_mul (lhs
, rhs
);
823 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
824 res
= extract_affine_name (s
, e
, space
);
828 res
= extract_affine_int (e
, space
);
829 /* No need to wrap a single integer. */
833 case NON_LVALUE_EXPR
:
834 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
842 type
= TREE_TYPE (e
);
843 if (TYPE_UNSIGNED (type
))
844 res
= wrap (res
, TYPE_PRECISION (type
));
849 /* In the context of sese S, scan the expression E and translate it to
850 a linear expression C. When parsing a symbolic multiplication, K
851 represents the constant multiplier of an expression containing
855 scan_tree_for_params (sese s
, tree e
)
857 if (e
== chrec_dont_know
)
860 switch (TREE_CODE (e
))
862 case POLYNOMIAL_CHREC
:
863 scan_tree_for_params (s
, CHREC_LEFT (e
));
867 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
868 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
870 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
874 case POINTER_PLUS_EXPR
:
876 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
883 case NON_LVALUE_EXPR
:
884 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
888 parameter_index_in_region (e
, s
);
904 /* Find parameters with respect to REGION in BB. We are looking in memory
905 access functions, conditions and loop bounds. */
908 find_params_in_bb (sese region
, gimple_bb_p gbb
)
914 loop_p loop
= GBB_BB (gbb
)->loop_father
;
916 /* Find parameters in the access functions of data references. */
917 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
918 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
919 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
921 /* Find parameters in conditional statements. */
922 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
924 tree lhs
= scalar_evolution_in_region (region
, loop
,
925 gimple_cond_lhs (stmt
));
926 tree rhs
= scalar_evolution_in_region (region
, loop
,
927 gimple_cond_rhs (stmt
));
929 scan_tree_for_params (region
, lhs
);
930 scan_tree_for_params (region
, rhs
);
934 /* Record the parameters used in the SCOP. A variable is a parameter
935 in a scop if it does not vary during the execution of that scop. */
938 find_scop_parameters (scop_p scop
)
942 sese region
= SCOP_REGION (scop
);
946 /* Find the parameters used in the loop bounds. */
947 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
949 tree nb_iters
= number_of_latch_executions (loop
);
951 if (!chrec_contains_symbols (nb_iters
))
954 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
955 scan_tree_for_params (region
, nb_iters
);
958 /* Find the parameters used in data accesses. */
959 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
960 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
962 nbp
= sese_nb_params (region
);
963 scop_set_nb_params (scop
, nbp
);
964 SESE_ADD_PARAMS (region
) = false;
968 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
970 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
971 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
972 isl_id_for_ssa_name (scop
, e
));
974 scop
->context
= isl_set_universe (space
);
978 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
979 the constraints for the surrounding loops. */
982 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
984 isl_set
*outer
, isl_set
**doms
)
986 tree nb_iters
= number_of_latch_executions (loop
);
987 sese region
= SCOP_REGION (scop
);
989 isl_set
*inner
= isl_set_copy (outer
);
992 int pos
= isl_set_dim (outer
, isl_dim_set
);
998 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
999 space
= isl_set_get_space (inner
);
1002 c
= isl_inequality_alloc
1003 (isl_local_space_from_space (isl_space_copy (space
)));
1004 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1005 inner
= isl_set_add_constraint (inner
, c
);
1007 /* loop_i <= cst_nb_iters */
1008 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1010 c
= isl_inequality_alloc
1011 (isl_local_space_from_space (isl_space_copy (space
)));
1012 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1013 tree_int_to_gmp (nb_iters
, g
);
1014 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1015 c
= isl_constraint_set_constant_val (c
, v
);
1016 inner
= isl_set_add_constraint (inner
, c
);
1019 /* loop_i <= expr_nb_iters */
1020 else if (!chrec_contains_undetermined (nb_iters
))
1025 isl_local_space
*ls
;
1029 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1031 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1032 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1033 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1034 isl_set_dim (valid
, isl_dim_set
));
1035 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1037 ls
= isl_local_space_from_space (isl_space_copy (space
));
1038 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1039 isl_dim_in
, pos
, 1);
1040 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1041 isl_pw_aff_copy (aff
));
1042 inner
= isl_set_intersect (inner
, le
);
1044 if (max_stmt_executions (loop
, &nit
))
1046 /* Insert in the context the constraints from the
1047 estimation of the number of iterations NIT and the
1048 symbolic number of iterations (involving parameter
1049 names) NB_ITERS. First, build the affine expression
1050 "NIT - NB_ITERS" and then say that it is positive,
1051 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1058 wi::to_mpz (nit
, g
, SIGNED
);
1059 mpz_sub_ui (g
, g
, 1);
1060 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1061 x
= isl_pw_aff_ge_set (approx
, aff
);
1062 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1063 isl_set_dim (x
, isl_dim_set
));
1064 scop
->context
= isl_set_intersect (scop
->context
, x
);
1066 c
= isl_inequality_alloc
1067 (isl_local_space_from_space (isl_space_copy (space
)));
1068 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1069 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1071 c
= isl_constraint_set_constant_val (c
, v
);
1072 inner
= isl_set_add_constraint (inner
, c
);
1075 isl_pw_aff_free (aff
);
1080 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1081 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1082 isl_set_copy (inner
), doms
);
1086 && loop_in_sese_p (loop
->next
, region
))
1087 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1088 isl_set_copy (outer
), doms
);
1090 doms
[loop
->num
] = inner
;
1092 isl_set_free (outer
);
1093 isl_space_free (space
);
1097 /* Returns a linear expression for tree T evaluated in PBB. */
1100 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1102 scop_p scop
= PBB_SCOP (pbb
);
1104 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1105 gcc_assert (!automatically_generated_chrec_p (t
));
1107 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1110 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1111 operator. This allows us to invert the condition or to handle
1115 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1117 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1118 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1124 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1128 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1132 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1136 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1140 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1144 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1148 isl_pw_aff_free (lhs
);
1149 isl_pw_aff_free (rhs
);
1153 cond
= isl_set_coalesce (cond
);
1154 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1155 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1158 /* Add conditions to the domain of PBB. */
1161 add_conditions_to_domain (poly_bb_p pbb
)
1165 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1167 if (GBB_CONDITIONS (gbb
).is_empty ())
1170 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1171 switch (gimple_code (stmt
))
1175 /* Don't constrain on anything else than INTEGER_TYPE. */
1176 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1179 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1180 enum tree_code code
= gimple_cond_code (cond_stmt
);
1182 /* The conditions for ELSE-branches are inverted. */
1183 if (!GBB_CONDITION_CASES (gbb
)[i
])
1184 code
= invert_tree_comparison (code
, false);
1186 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1191 /* Switch statements are not supported right now - fall through. */
1199 /* Traverses all the GBBs of the SCOP and add their constraints to the
1200 iteration domains. */
1203 add_conditions_to_constraints (scop_p scop
)
1208 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1209 add_conditions_to_domain (pbb
);
1212 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1213 edge between BB and its predecessor is not a loop exit edge, and
1214 the last statement of the single predecessor is a COND_EXPR. */
1217 single_pred_cond_non_loop_exit (basic_block bb
)
1219 if (single_pred_p (bb
))
1221 edge e
= single_pred_edge (bb
);
1222 basic_block pred
= e
->src
;
1225 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1228 stmt
= last_stmt (pred
);
1230 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1231 return as_a
<gcond
*> (stmt
);
1237 class sese_dom_walker
: public dom_walker
1240 sese_dom_walker (cdi_direction
, sese
);
1242 virtual void before_dom_children (basic_block
);
1243 virtual void after_dom_children (basic_block
);
1246 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1250 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1251 : dom_walker (direction
), m_region (region
)
1255 /* Call-back for dom_walk executed before visiting the dominated
1259 sese_dom_walker::before_dom_children (basic_block bb
)
1264 if (!bb_in_sese_p (bb
, m_region
))
1267 stmt
= single_pred_cond_non_loop_exit (bb
);
1271 edge e
= single_pred_edge (bb
);
1273 m_conditions
.safe_push (stmt
);
1275 if (e
->flags
& EDGE_TRUE_VALUE
)
1276 m_cases
.safe_push (stmt
);
1278 m_cases
.safe_push (NULL
);
1281 gbb
= gbb_from_bb (bb
);
1285 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1286 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1290 /* Call-back for dom_walk executed after visiting the dominated
1294 sese_dom_walker::after_dom_children (basic_block bb
)
1296 if (!bb_in_sese_p (bb
, m_region
))
1299 if (single_pred_cond_non_loop_exit (bb
))
1301 m_conditions
.pop ();
1306 /* Add constraints on the possible values of parameter P from the type
1310 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1312 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1313 tree type
= TREE_TYPE (parameter
);
1314 tree lb
= NULL_TREE
;
1315 tree ub
= NULL_TREE
;
1317 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1318 lb
= lower_bound_in_type (type
, type
);
1320 lb
= TYPE_MIN_VALUE (type
);
1322 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1323 ub
= upper_bound_in_type (type
, type
);
1325 ub
= TYPE_MAX_VALUE (type
);
1329 isl_space
*space
= isl_set_get_space (scop
->context
);
1334 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1336 tree_int_to_gmp (lb
, g
);
1337 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1338 v
= isl_val_neg (v
);
1340 c
= isl_constraint_set_constant_val (c
, v
);
1341 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1343 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1348 isl_space
*space
= isl_set_get_space (scop
->context
);
1353 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1356 tree_int_to_gmp (ub
, g
);
1357 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1359 c
= isl_constraint_set_constant_val (c
, v
);
1360 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1362 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1366 /* Build the context of the SCOP. The context usually contains extra
1367 constraints that are added to the iteration domains that constrain
1371 build_scop_context (scop_p scop
)
1373 graphite_dim_t p
, n
= scop_nb_params (scop
);
1375 for (p
= 0; p
< n
; p
++)
1376 add_param_constraints (scop
, p
);
1379 /* Build the iteration domains: the loops belonging to the current
1380 SCOP, and that vary for the execution of the current basic block.
1381 Returns false if there is no loop in SCOP. */
1384 build_scop_iteration_domain (scop_p scop
)
1387 sese region
= SCOP_REGION (scop
);
1390 int nb_loops
= number_of_loops (cfun
);
1391 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1393 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1394 if (!loop_in_sese_p (loop_outer (loop
), region
))
1395 build_loop_iteration_domains (scop
, loop
, 0,
1396 isl_set_copy (scop
->context
), doms
);
1398 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1400 loop
= pbb_loop (pbb
);
1402 if (doms
[loop
->num
])
1403 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1405 pbb
->domain
= isl_set_copy (scop
->context
);
1407 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1408 isl_id_for_pbb (scop
, pbb
));
1411 for (i
= 0; i
< nb_loops
; i
++)
1413 isl_set_free (doms
[i
]);
1418 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1419 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1420 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1424 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1427 int alias_set_num
= 0;
1428 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1430 if (bap
&& bap
->alias_set
)
1431 alias_set_num
= *(bap
->alias_set
);
1433 c
= isl_equality_alloc
1434 (isl_local_space_from_space (isl_map_get_space (acc
)));
1435 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1436 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1438 return isl_map_add_constraint (acc
, c
);
1441 /* Assign the affine expression INDEX to the output dimension POS of
1442 MAP and return the result. */
1445 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1448 int len
= isl_map_dim (map
, isl_dim_out
);
1451 index_map
= isl_map_from_pw_aff (index
);
1452 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1453 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1455 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1456 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1457 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1458 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1460 return isl_map_intersect (map
, index_map
);
1463 /* Add to ACCESSES polyhedron equalities defining the access functions
1464 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1465 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1466 PBB is the poly_bb_p that contains the data reference DR. */
1469 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1471 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1472 scop_p scop
= PBB_SCOP (pbb
);
1474 for (i
= 0; i
< nb_subscripts
; i
++)
1477 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1479 aff
= extract_affine (scop
, afn
,
1480 isl_space_domain (isl_map_get_space (acc
)));
1481 acc
= set_index (acc
, i
+ 1, aff
);
1487 /* Add constrains representing the size of the accessed data to the
1488 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1489 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1493 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1494 data_reference_p dr
)
1496 tree ref
= DR_REF (dr
);
1498 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1499 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1501 if (TREE_CODE (ref
) != ARRAY_REF
)
1502 return subscript_sizes
;
1504 tree low
= array_ref_low_bound (ref
);
1505 tree high
= array_ref_up_bound (ref
);
1507 /* XXX The PPL code dealt separately with
1508 subscript - low >= 0 and high - subscript >= 0 in case one of
1509 the two bounds isn't known. Do the same here? */
1511 if (tree_fits_shwi_p (low
)
1513 && tree_fits_shwi_p (high
)
1514 /* 1-element arrays at end of structures may extend over
1515 their declared size. */
1516 && !(array_at_struct_end_p (ref
)
1517 && operand_equal_p (low
, high
, 0)))
1521 isl_set
*univ
, *lbs
, *ubs
;
1524 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1525 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1526 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1529 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1530 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1531 isl_set_dim (valid
, isl_dim_set
));
1532 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1534 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1535 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1536 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1537 index
= isl_pw_aff_alloc (univ
, aff
);
1539 id
= isl_set_get_tuple_id (subscript_sizes
);
1540 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1541 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1543 /* low <= sub_i <= high */
1544 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1545 ubs
= isl_pw_aff_le_set (index
, ub
);
1546 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1547 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1551 return subscript_sizes
;
1554 /* Build data accesses for DR in PBB. */
1557 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1559 int dr_base_object_set
;
1561 isl_set
*subscript_sizes
;
1562 scop_p scop
= PBB_SCOP (pbb
);
1565 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1566 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1567 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1568 isl_dim_out
, nb_out
);
1570 acc
= isl_map_universe (space
);
1571 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1574 acc
= pdr_add_alias_set (acc
, dr
);
1575 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1578 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1579 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1580 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1581 int alias_set_num
= 0;
1582 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1584 if (bap
&& bap
->alias_set
)
1585 alias_set_num
= *(bap
->alias_set
);
1587 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1588 subscript_sizes
= isl_set_nat_universe (space
);
1589 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1591 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1594 gcc_assert (dr
->aux
);
1595 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1597 new_poly_dr (pbb
, dr_base_object_set
,
1598 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1599 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1602 /* Write to FILE the alias graph of data references in DIMACS format. */
1605 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1606 vec
<data_reference_p
> drs
)
1608 int num_vertex
= drs
.length ();
1610 data_reference_p dr1
, dr2
;
1613 if (num_vertex
== 0)
1616 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1617 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1618 if (dr_may_alias_p (dr1
, dr2
, true))
1621 fprintf (file
, "$\n");
1624 fprintf (file
, "c %s\n", comment
);
1626 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1628 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1629 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1630 if (dr_may_alias_p (dr1
, dr2
, true))
1631 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1636 /* Write to FILE the alias graph of data references in DOT format. */
1639 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1640 vec
<data_reference_p
> drs
)
1642 int num_vertex
= drs
.length ();
1643 data_reference_p dr1
, dr2
;
1646 if (num_vertex
== 0)
1649 fprintf (file
, "$\n");
1652 fprintf (file
, "c %s\n", comment
);
1654 /* First print all the vertices. */
1655 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1656 fprintf (file
, "n%d;\n", i
);
1658 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1659 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1660 if (dr_may_alias_p (dr1
, dr2
, true))
1661 fprintf (file
, "n%d n%d\n", i
, j
);
1666 /* Write to FILE the alias graph of data references in ECC format. */
1669 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1670 vec
<data_reference_p
> drs
)
1672 int num_vertex
= drs
.length ();
1673 data_reference_p dr1
, dr2
;
1676 if (num_vertex
== 0)
1679 fprintf (file
, "$\n");
1682 fprintf (file
, "c %s\n", comment
);
1684 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1685 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1686 if (dr_may_alias_p (dr1
, dr2
, true))
1687 fprintf (file
, "%d %d\n", i
, j
);
1692 /* Check if DR1 and DR2 are in the same object set. */
1695 dr_same_base_object_p (const struct data_reference
*dr1
,
1696 const struct data_reference
*dr2
)
1698 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1701 /* Uses DFS component number as representative of alias-sets. Also tests for
1702 optimality by verifying if every connected component is a clique. Returns
1703 true (1) if the above test is true, and false (0) otherwise. */
1706 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1708 int num_vertices
= drs
.length ();
1709 struct graph
*g
= new_graph (num_vertices
);
1710 data_reference_p dr1
, dr2
;
1712 int num_connected_components
;
1713 int v_indx1
, v_indx2
, num_vertices_in_component
;
1716 struct graph_edge
*e
;
1717 int this_component_is_clique
;
1718 int all_components_are_cliques
= 1;
1720 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1721 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1722 if (dr_may_alias_p (dr1
, dr2
, true))
1728 all_vertices
= XNEWVEC (int, num_vertices
);
1729 vertices
= XNEWVEC (int, num_vertices
);
1730 for (i
= 0; i
< num_vertices
; i
++)
1731 all_vertices
[i
] = i
;
1733 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1735 for (i
= 0; i
< g
->n_vertices
; i
++)
1737 data_reference_p dr
= drs
[i
];
1738 base_alias_pair
*bap
;
1740 gcc_assert (dr
->aux
);
1741 bap
= (base_alias_pair
*)(dr
->aux
);
1743 bap
->alias_set
= XNEW (int);
1744 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1747 /* Verify if the DFS numbering results in optimal solution. */
1748 for (i
= 0; i
< num_connected_components
; i
++)
1750 num_vertices_in_component
= 0;
1751 /* Get all vertices whose DFS component number is the same as i. */
1752 for (j
= 0; j
< num_vertices
; j
++)
1753 if (g
->vertices
[j
].component
== i
)
1754 vertices
[num_vertices_in_component
++] = j
;
1756 /* Now test if the vertices in 'vertices' form a clique, by testing
1757 for edges among each pair. */
1758 this_component_is_clique
= 1;
1759 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1761 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1763 /* Check if the two vertices are connected by iterating
1764 through all the edges which have one of these are source. */
1765 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1768 if (e
->src
== vertices
[v_indx1
])
1774 this_component_is_clique
= 0;
1778 if (!this_component_is_clique
)
1779 all_components_are_cliques
= 0;
1783 free (all_vertices
);
1786 return all_components_are_cliques
;
1789 /* Group each data reference in DRS with its base object set num. */
1792 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1794 int num_vertex
= drs
.length ();
1795 struct graph
*g
= new_graph (num_vertex
);
1796 data_reference_p dr1
, dr2
;
1800 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1801 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1802 if (dr_same_base_object_p (dr1
, dr2
))
1808 queue
= XNEWVEC (int, num_vertex
);
1809 for (i
= 0; i
< num_vertex
; i
++)
1812 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1814 for (i
= 0; i
< g
->n_vertices
; i
++)
1816 data_reference_p dr
= drs
[i
];
1817 base_alias_pair
*bap
;
1819 gcc_assert (dr
->aux
);
1820 bap
= (base_alias_pair
*)(dr
->aux
);
1822 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1829 /* Build the data references for PBB. */
1832 build_pbb_drs (poly_bb_p pbb
)
1835 data_reference_p dr
;
1836 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1838 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1839 build_poly_dr (dr
, pbb
);
1842 /* Dump to file the alias graphs for the data references in DRS. */
1845 dump_alias_graphs (vec
<data_reference_p
> drs
)
1848 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1850 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1853 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1854 current_function_name ());
1855 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1856 fclose (file_dimacs
);
1859 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1862 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1863 current_function_name ());
1864 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1868 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1871 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1872 current_function_name ());
1873 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1878 /* Build data references in SCOP. */
1881 build_scop_drs (scop_p scop
)
1885 data_reference_p dr
;
1886 auto_vec
<data_reference_p
, 3> drs
;
1888 /* Remove all the PBBs that do not have data references: these basic
1889 blocks are not handled in the polyhedral representation. */
1890 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1891 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1893 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1895 SCOP_BBS (scop
).ordered_remove (i
);
1899 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1900 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1903 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1904 dr
->aux
= XNEW (base_alias_pair
);
1906 if (!build_alias_set_optimal_p (drs
))
1908 /* TODO: Add support when building alias set is not optimal. */
1912 build_base_obj_set_for_drs (drs
);
1914 /* When debugging, enable the following code. This cannot be used
1915 in production compilers. */
1917 dump_alias_graphs (drs
);
1921 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1922 build_pbb_drs (pbb
);
1925 /* Return a gsi at the position of the phi node STMT. */
1927 static gphi_iterator
1928 gsi_for_phi_node (gphi
*stmt
)
1931 basic_block bb
= gimple_bb (stmt
);
1933 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1934 if (stmt
== psi
.phi ())
1941 /* Analyze all the data references of STMTS and add them to the
1942 GBB_DATA_REFS vector of BB. */
1945 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1951 sese region
= SCOP_REGION (scop
);
1953 if (!bb_in_sese_p (bb
, region
))
1956 nest
= outermost_loop_in_sese_1 (region
, bb
);
1957 gbb
= gbb_from_bb (bb
);
1959 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1963 if (is_gimple_debug (stmt
))
1966 loop
= loop_containing_stmt (stmt
);
1967 if (!loop_in_sese_p (loop
, region
))
1970 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1971 &GBB_DATA_REFS (gbb
));
1975 /* Insert STMT at the end of the STMTS sequence and then insert the
1976 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1980 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1981 gimple_stmt_iterator insert_gsi
)
1983 gimple_stmt_iterator gsi
;
1984 auto_vec
<gimple
, 3> x
;
1986 gimple_seq_add_stmt (&stmts
, stmt
);
1987 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1988 x
.safe_push (gsi_stmt (gsi
));
1990 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1991 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1994 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1997 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2000 gimple_stmt_iterator gsi
;
2001 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2002 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2003 auto_vec
<gimple
, 3> x
;
2005 gimple_seq_add_stmt (&stmts
, stmt
);
2006 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2007 x
.safe_push (gsi_stmt (gsi
));
2009 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2011 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2012 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2016 gsi
= gsi_for_stmt (after_stmt
);
2017 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2020 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2023 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2026 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2028 vec
<data_reference_p
> drs
;
2030 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2031 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2032 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2033 int index
, n
= SCOP_BBS (scop
).length ();
2035 /* The INDEX of PBB in SCOP_BBS. */
2036 for (index
= 0; index
< n
; index
++)
2037 if (SCOP_BBS (scop
)[index
] == pbb
)
2040 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2041 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2042 isl_id_for_pbb (scop
, pbb1
));
2044 GBB_PBB (gbb1
) = pbb1
;
2045 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2046 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2047 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2050 /* Insert on edge E the assignment "RES := EXPR". */
2053 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2055 gimple_stmt_iterator gsi
;
2056 gimple_seq stmts
= NULL
;
2057 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2058 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2060 auto_vec
<gimple
, 3> x
;
2062 gimple_seq_add_stmt (&stmts
, stmt
);
2063 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2064 x
.safe_push (gsi_stmt (gsi
));
2066 gsi_insert_seq_on_edge (e
, stmts
);
2067 gsi_commit_edge_inserts ();
2068 bb
= gimple_bb (stmt
);
2070 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2073 if (!gbb_from_bb (bb
))
2074 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2076 analyze_drs_in_stmts (scop
, bb
, x
);
2079 /* Creates a zero dimension array of the same type as VAR. */
2082 create_zero_dim_array (tree var
, const char *base_name
)
2084 tree index_type
= build_index_type (integer_zero_node
);
2085 tree elt_type
= TREE_TYPE (var
);
2086 tree array_type
= build_array_type (elt_type
, index_type
);
2087 tree base
= create_tmp_var (array_type
, base_name
);
2089 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2093 /* Returns true when PHI is a loop close phi node. */
2096 scalar_close_phi_node_p (gimple phi
)
2098 if (gimple_code (phi
) != GIMPLE_PHI
2099 || virtual_operand_p (gimple_phi_result (phi
)))
2102 /* Note that loop close phi nodes should have a single argument
2103 because we translated the representation into a canonical form
2104 before Graphite: see canonicalize_loop_closed_ssa_form. */
2105 return (gimple_phi_num_args (phi
) == 1);
2108 /* For a definition DEF in REGION, propagates the expression EXPR in
2109 all the uses of DEF outside REGION. */
2112 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2114 imm_use_iterator imm_iter
;
2117 bool replaced_once
= false;
2119 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2121 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2124 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2125 if (!is_gimple_debug (use_stmt
)
2126 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2129 use_operand_p use_p
;
2131 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2132 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2133 && (replaced_once
= true))
2134 replace_exp (use_p
, expr
);
2136 update_stmt (use_stmt
);
2141 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2142 gsi_commit_edge_inserts ();
2146 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2147 dimension array for it. */
2150 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2152 sese region
= SCOP_REGION (scop
);
2153 gimple phi
= gsi_stmt (*psi
);
2154 tree res
= gimple_phi_result (phi
);
2155 basic_block bb
= gimple_bb (phi
);
2156 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2157 tree arg
= gimple_phi_arg_def (phi
, 0);
2160 /* Note that loop close phi nodes should have a single argument
2161 because we translated the representation into a canonical form
2162 before Graphite: see canonicalize_loop_closed_ssa_form. */
2163 gcc_assert (gimple_phi_num_args (phi
) == 1);
2165 /* The phi node can be a non close phi node, when its argument is
2166 invariant, or a default definition. */
2167 if (is_gimple_min_invariant (arg
)
2168 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2170 propagate_expr_outside_region (res
, arg
, region
);
2175 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2177 propagate_expr_outside_region (res
, arg
, region
);
2178 stmt
= gimple_build_assign (res
, arg
);
2179 remove_phi_node (psi
, false);
2180 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2184 /* If res is scev analyzable and is not a scalar value, it is safe
2185 to ignore the close phi node: it will be code generated in the
2186 out of Graphite pass. */
2187 else if (scev_analyzable_p (res
, region
))
2189 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2192 if (!loop_in_sese_p (loop
, region
))
2194 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2195 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2196 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2199 scev
= scalar_evolution_in_region (region
, loop
, res
);
2201 if (tree_does_not_contain_chrecs (scev
))
2202 propagate_expr_outside_region (res
, scev
, region
);
2209 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2211 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2213 if (TREE_CODE (arg
) == SSA_NAME
)
2214 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2215 SSA_NAME_DEF_STMT (arg
));
2217 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2218 zero_dim_array
, arg
);
2221 remove_phi_node (psi
, false);
2222 SSA_NAME_DEF_STMT (res
) = stmt
;
2224 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2227 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2228 dimension array for it. */
2231 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2234 gphi
*phi
= psi
->phi ();
2235 basic_block bb
= gimple_bb (phi
);
2236 tree res
= gimple_phi_result (phi
);
2237 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2240 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2242 tree arg
= gimple_phi_arg_def (phi
, i
);
2243 edge e
= gimple_phi_arg_edge (phi
, i
);
2245 /* Avoid the insertion of code in the loop latch to please the
2246 pattern matching of the vectorizer. */
2247 if (TREE_CODE (arg
) == SSA_NAME
2248 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2249 && e
->src
== bb
->loop_father
->latch
)
2250 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2251 SSA_NAME_DEF_STMT (arg
));
2253 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2256 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2257 remove_phi_node (psi
, false);
2258 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2261 /* Rewrite the degenerate phi node at position PSI from the degenerate
2262 form "x = phi (y, y, ..., y)" to "x = y". */
2265 rewrite_degenerate_phi (gphi_iterator
*psi
)
2269 gimple_stmt_iterator gsi
;
2270 gphi
*phi
= psi
->phi ();
2271 tree res
= gimple_phi_result (phi
);
2274 bb
= gimple_bb (phi
);
2275 rhs
= degenerate_phi_result (phi
);
2278 stmt
= gimple_build_assign (res
, rhs
);
2279 remove_phi_node (psi
, false);
2281 gsi
= gsi_after_labels (bb
);
2282 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2285 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2288 rewrite_reductions_out_of_ssa (scop_p scop
)
2292 sese region
= SCOP_REGION (scop
);
2294 FOR_EACH_BB_FN (bb
, cfun
)
2295 if (bb_in_sese_p (bb
, region
))
2296 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2298 gphi
*phi
= psi
.phi ();
2300 if (virtual_operand_p (gimple_phi_result (phi
)))
2306 if (gimple_phi_num_args (phi
) > 1
2307 && degenerate_phi_result (phi
))
2308 rewrite_degenerate_phi (&psi
);
2310 else if (scalar_close_phi_node_p (phi
))
2311 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2313 else if (reduction_phi_p (region
, &psi
))
2314 rewrite_phi_out_of_ssa (scop
, &psi
);
2317 update_ssa (TODO_update_ssa
);
2318 #ifdef ENABLE_CHECKING
2319 verify_loop_closed_ssa (true);
2323 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2324 read from ZERO_DIM_ARRAY. */
2327 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2328 tree def
, gimple use_stmt
)
2333 use_operand_p use_p
;
2335 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2337 name
= copy_ssa_name (def
);
2338 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2340 gimple_assign_set_lhs (name_stmt
, name
);
2341 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2343 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2344 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2345 replace_exp (use_p
, name
);
2347 update_stmt (use_stmt
);
2350 /* For every definition DEF in the SCOP that is used outside the scop,
2351 insert a closing-scop definition in the basic block just after this
2355 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2357 tree var
= create_tmp_reg (TREE_TYPE (def
));
2358 tree new_name
= make_ssa_name (var
, stmt
);
2359 bool needs_copy
= false;
2360 use_operand_p use_p
;
2361 imm_use_iterator imm_iter
;
2363 sese region
= SCOP_REGION (scop
);
2365 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2367 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2369 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2371 SET_USE (use_p
, new_name
);
2373 update_stmt (use_stmt
);
2378 /* Insert in the empty BB just after the scop a use of DEF such
2379 that the rewrite of cross_bb_scalar_dependences won't insert
2380 arrays everywhere else. */
2383 gimple assign
= gimple_build_assign (new_name
, def
);
2384 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2386 update_stmt (assign
);
2387 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2391 /* Rewrite the scalar dependences crossing the boundary of the BB
2392 containing STMT with an array. Return true when something has been
2396 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2398 sese region
= SCOP_REGION (scop
);
2399 gimple stmt
= gsi_stmt (*gsi
);
2400 imm_use_iterator imm_iter
;
2403 tree zero_dim_array
= NULL_TREE
;
2407 switch (gimple_code (stmt
))
2410 def
= gimple_assign_lhs (stmt
);
2414 def
= gimple_call_lhs (stmt
);
2422 || !is_gimple_reg (def
))
2425 if (scev_analyzable_p (def
, region
))
2427 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2428 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2430 if (tree_contains_chrecs (scev
, NULL
))
2433 propagate_expr_outside_region (def
, scev
, region
);
2437 def_bb
= gimple_bb (stmt
);
2439 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2441 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2442 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2445 gphi_iterator psi
= gsi_for_phi (phi
);
2447 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2448 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2450 rewrite_phi_out_of_ssa (scop
, &psi
);
2453 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2454 if (gimple_code (use_stmt
) != GIMPLE_PHI
2455 && def_bb
!= gimple_bb (use_stmt
)
2456 && !is_gimple_debug (use_stmt
)
2459 if (!zero_dim_array
)
2461 zero_dim_array
= create_zero_dim_array
2462 (def
, "Cross_BB_scalar_dependence");
2463 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2464 SSA_NAME_DEF_STMT (def
));
2468 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2475 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2478 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2481 gimple_stmt_iterator psi
;
2482 sese region
= SCOP_REGION (scop
);
2483 bool changed
= false;
2485 /* Create an extra empty BB after the scop. */
2486 split_edge (SESE_EXIT (region
));
2488 FOR_EACH_BB_FN (bb
, cfun
)
2489 if (bb_in_sese_p (bb
, region
))
2490 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2491 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2496 update_ssa (TODO_update_ssa
);
2497 #ifdef ENABLE_CHECKING
2498 verify_loop_closed_ssa (true);
2503 /* Returns the number of pbbs that are in loops contained in SCOP. */
2506 nb_pbbs_in_loops (scop_p scop
)
2512 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2513 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2519 /* Return the number of data references in BB that write in
2523 nb_data_writes_in_bb (basic_block bb
)
2526 gimple_stmt_iterator gsi
;
2528 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2529 if (gimple_vdef (gsi_stmt (gsi
)))
2535 /* Splits at STMT the basic block BB represented as PBB in the
2539 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2541 edge e1
= split_block (bb
, stmt
);
2542 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2546 /* Splits STMT out of its current BB. This is done for reduction
2547 statements for which we want to ignore data dependences. */
2550 split_reduction_stmt (scop_p scop
, gimple stmt
)
2552 basic_block bb
= gimple_bb (stmt
);
2553 poly_bb_p pbb
= pbb_from_bb (bb
);
2554 gimple_bb_p gbb
= gbb_from_bb (bb
);
2557 data_reference_p dr
;
2559 /* Do not split basic blocks with no writes to memory: the reduction
2560 will be the only write to memory. */
2561 if (nb_data_writes_in_bb (bb
) == 0
2562 /* Or if we have already marked BB as a reduction. */
2563 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2566 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2568 /* Split once more only when the reduction stmt is not the only one
2569 left in the original BB. */
2570 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2572 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2574 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2577 /* A part of the data references will end in a different basic block
2578 after the split: move the DRs from the original GBB to the newly
2580 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2582 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2586 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2587 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2588 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2596 /* Return true when stmt is a reduction operation. */
2599 is_reduction_operation_p (gimple stmt
)
2601 enum tree_code code
;
2603 gcc_assert (is_gimple_assign (stmt
));
2604 code
= gimple_assign_rhs_code (stmt
);
2606 return flag_associative_math
2607 && commutative_tree_code (code
)
2608 && associative_tree_code (code
);
2611 /* Returns true when PHI contains an argument ARG. */
2614 phi_contains_arg (gphi
*phi
, tree arg
)
2618 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2619 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2625 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2628 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2632 if (TREE_CODE (arg
) != SSA_NAME
)
2635 stmt
= SSA_NAME_DEF_STMT (arg
);
2637 if (gimple_code (stmt
) == GIMPLE_NOP
2638 || gimple_code (stmt
) == GIMPLE_CALL
)
2641 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2643 if (phi_contains_arg (phi
, lhs
))
2648 if (!is_gimple_assign (stmt
))
2651 if (gimple_num_ops (stmt
) == 2)
2652 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2654 if (is_reduction_operation_p (stmt
))
2657 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2660 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2666 /* Detect commutative and associative scalar reductions starting at
2667 the STMT. Return the phi node of the reduction cycle, or NULL. */
2670 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2674 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2679 in
->safe_push (stmt
);
2680 out
->safe_push (stmt
);
2684 /* Detect commutative and associative scalar reductions starting at
2685 STMT. Return the phi node of the reduction cycle, or NULL. */
2688 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2691 tree lhs
= gimple_assign_lhs (stmt
);
2693 if (gimple_num_ops (stmt
) == 2)
2694 return detect_commutative_reduction_arg (lhs
, stmt
,
2695 gimple_assign_rhs1 (stmt
),
2698 if (is_reduction_operation_p (stmt
))
2700 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2701 gimple_assign_rhs1 (stmt
),
2704 : detect_commutative_reduction_arg (lhs
, stmt
,
2705 gimple_assign_rhs2 (stmt
),
2712 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2715 follow_inital_value_to_phi (tree arg
, tree lhs
)
2719 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2722 stmt
= SSA_NAME_DEF_STMT (arg
);
2724 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2725 if (phi_contains_arg (phi
, lhs
))
2732 /* Return the argument of the loop PHI that is the initial value coming
2733 from outside the loop. */
2736 edge_initial_value_for_loop_phi (gphi
*phi
)
2740 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2742 edge e
= gimple_phi_arg_edge (phi
, i
);
2744 if (loop_depth (e
->src
->loop_father
)
2745 < loop_depth (e
->dest
->loop_father
))
2752 /* Return the argument of the loop PHI that is the initial value coming
2753 from outside the loop. */
2756 initial_value_for_loop_phi (gphi
*phi
)
2760 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2762 edge e
= gimple_phi_arg_edge (phi
, i
);
2764 if (loop_depth (e
->src
->loop_father
)
2765 < loop_depth (e
->dest
->loop_father
))
2766 return gimple_phi_arg_def (phi
, i
);
2772 /* Returns true when DEF is used outside the reduction cycle of
2776 used_outside_reduction (tree def
, gimple loop_phi
)
2778 use_operand_p use_p
;
2779 imm_use_iterator imm_iter
;
2780 loop_p loop
= loop_containing_stmt (loop_phi
);
2782 /* In LOOP, DEF should be used only in LOOP_PHI. */
2783 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2785 gimple stmt
= USE_STMT (use_p
);
2787 if (stmt
!= loop_phi
2788 && !is_gimple_debug (stmt
)
2789 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2796 /* Detect commutative and associative scalar reductions belonging to
2797 the SCOP starting at the loop closed phi node STMT. Return the phi
2798 node of the reduction cycle, or NULL. */
2801 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2804 if (scalar_close_phi_node_p (stmt
))
2807 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2808 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2810 if (TREE_CODE (arg
) != SSA_NAME
)
2813 /* Note that loop close phi nodes should have a single argument
2814 because we translated the representation into a canonical form
2815 before Graphite: see canonicalize_loop_closed_ssa_form. */
2816 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2818 def
= SSA_NAME_DEF_STMT (arg
);
2819 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2820 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2823 lhs
= gimple_phi_result (close_phi
);
2824 init
= initial_value_for_loop_phi (loop_phi
);
2825 phi
= follow_inital_value_to_phi (init
, lhs
);
2827 if (phi
&& (used_outside_reduction (lhs
, phi
)
2828 || !has_single_use (gimple_phi_result (phi
))))
2831 in
->safe_push (loop_phi
);
2832 out
->safe_push (close_phi
);
2836 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2837 return detect_commutative_reduction_assign (stmt
, in
, out
);
2842 /* Translate the scalar reduction statement STMT to an array RED
2843 knowing that its recursive phi node is LOOP_PHI. */
2846 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2847 gimple stmt
, gphi
*loop_phi
)
2849 tree res
= gimple_phi_result (loop_phi
);
2850 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2851 gimple_stmt_iterator gsi
;
2853 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2855 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2856 gsi
= gsi_for_stmt (stmt
);
2858 insert_stmts (scop
, assign
, NULL
, gsi
);
2861 /* Removes the PHI node and resets all the debug stmts that are using
2865 remove_phi (gphi
*phi
)
2867 imm_use_iterator imm_iter
;
2869 use_operand_p use_p
;
2870 gimple_stmt_iterator gsi
;
2871 auto_vec
<gimple
, 3> update
;
2875 def
= PHI_RESULT (phi
);
2876 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2878 stmt
= USE_STMT (use_p
);
2880 if (is_gimple_debug (stmt
))
2882 gimple_debug_bind_reset_value (stmt
);
2883 update
.safe_push (stmt
);
2887 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2890 gsi
= gsi_for_phi_node (phi
);
2891 remove_phi_node (&gsi
, false);
2894 /* Helper function for for_each_index. For each INDEX of the data
2895 reference REF, returns true when its indices are valid in the loop
2896 nest LOOP passed in as DATA. */
2899 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2902 basic_block header
, def_bb
;
2905 if (TREE_CODE (*index
) != SSA_NAME
)
2908 loop
= *((loop_p
*) data
);
2909 header
= loop
->header
;
2910 stmt
= SSA_NAME_DEF_STMT (*index
);
2915 def_bb
= gimple_bb (stmt
);
2920 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2923 /* When the result of a CLOSE_PHI is written to a memory location,
2924 return a pointer to that memory reference, otherwise return
2928 close_phi_written_to_memory (gphi
*close_phi
)
2930 imm_use_iterator imm_iter
;
2931 use_operand_p use_p
;
2933 tree res
, def
= gimple_phi_result (close_phi
);
2935 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2936 if ((stmt
= USE_STMT (use_p
))
2937 && gimple_code (stmt
) == GIMPLE_ASSIGN
2938 && (res
= gimple_assign_lhs (stmt
)))
2940 switch (TREE_CODE (res
))
2950 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2951 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2953 /* FIXME: this restriction is for id-{24,25}.f and
2954 could be handled by duplicating the computation of
2955 array indices before the loop of the close_phi. */
2956 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2968 /* Rewrite out of SSA the reduction described by the loop phi nodes
2969 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2972 IN: stmt, loop_n, ..., loop_0
2973 OUT: stmt, close_n, ..., close_0
2975 the first element is the reduction statement, and the next elements
2976 are the loop and close phi nodes of each of the outer loops. */
2979 translate_scalar_reduction_to_array (scop_p scop
,
2984 unsigned int i
= out
.length () - 1;
2985 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
2987 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
2989 gimple close_stmt
= out
[i
];
2993 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
2994 poly_bb_p pbb
= pbb_from_bb (bb
);
2995 PBB_IS_REDUCTION (pbb
) = true;
2996 gcc_assert (close_stmt
== loop_stmt
);
2999 red
= create_zero_dim_array
3000 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3002 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3003 as_a
<gphi
*> (in
[1]));
3007 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3008 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3010 if (i
== in
.length () - 1)
3012 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3013 unshare_expr (red
), close_phi
);
3014 insert_out_of_ssa_copy_on_edge
3015 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3016 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3019 remove_phi (loop_phi
);
3020 remove_phi (close_phi
);
3024 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3025 true when something has been changed. */
3028 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3032 auto_vec
<gimple
, 10> in
;
3033 auto_vec
<gimple
, 10> out
;
3035 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3036 res
= in
.length () > 1;
3038 translate_scalar_reduction_to_array (scop
, in
, out
);
3043 /* Rewrites all the commutative reductions from LOOP out of SSA.
3044 Returns true when something has been changed. */
3047 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3051 edge exit
= single_exit (loop
);
3053 bool changed
= false;
3058 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3059 if ((res
= gimple_phi_result (gsi
.phi ()))
3060 && !virtual_operand_p (res
)
3061 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3062 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3068 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3071 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3074 bool changed
= false;
3075 sese region
= SCOP_REGION (scop
);
3077 FOR_EACH_LOOP (loop
, 0)
3078 if (loop_in_sese_p (loop
, region
))
3079 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3084 gsi_commit_edge_inserts ();
3085 update_ssa (TODO_update_ssa
);
3086 #ifdef ENABLE_CHECKING
3087 verify_loop_closed_ssa (true);
3092 /* Can all ivs be represented by a signed integer?
3093 As CLooG might generate negative values in its expressions, signed loop ivs
3094 are required in the backend. */
3097 scop_ivs_can_be_represented (scop_p scop
)
3103 FOR_EACH_LOOP (loop
, 0)
3105 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3108 for (psi
= gsi_start_phis (loop
->header
);
3109 !gsi_end_p (psi
); gsi_next (&psi
))
3111 gphi
*phi
= psi
.phi ();
3112 tree res
= PHI_RESULT (phi
);
3113 tree type
= TREE_TYPE (res
);
3115 if (TYPE_UNSIGNED (type
)
3116 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3129 /* Builds the polyhedral representation for a SESE region. */
3132 build_poly_scop (scop_p scop
)
3134 sese region
= SCOP_REGION (scop
);
3135 graphite_dim_t max_dim
;
3137 build_scop_bbs (scop
);
3139 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3140 Once CLooG is fixed, remove this guard. Anyways, it makes no
3141 sense to optimize a scop containing only PBBs that do not belong
3143 if (nb_pbbs_in_loops (scop
) == 0)
3146 if (!scop_ivs_can_be_represented (scop
))
3149 if (flag_associative_math
)
3150 rewrite_commutative_reductions_out_of_ssa (scop
);
3152 build_sese_loop_nests (region
);
3153 /* Record all conditions in REGION. */
3154 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3155 find_scop_parameters (scop
);
3157 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3158 if (scop_nb_params (scop
) > max_dim
)
3161 build_scop_iteration_domain (scop
);
3162 build_scop_context (scop
);
3163 add_conditions_to_constraints (scop
);
3165 /* Rewrite out of SSA only after having translated the
3166 representation to the polyhedral representation to avoid scev
3167 analysis failures. That means that these functions will insert
3168 new data references that they create in the right place. */
3169 rewrite_reductions_out_of_ssa (scop
);
3170 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3172 build_scop_drs (scop
);
3174 build_scop_scattering (scop
);
3176 /* This SCoP has been translated to the polyhedral
3178 POLY_SCOP_P (scop
) = true;
3180 #endif /* HAVE_isl */