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. */
27 #include <isl/constraint.h>
30 #include <isl/union_map.h>
31 #include <isl/constraint.h>
35 /* Since ISL-0.13, the extern is in val_gmp.h. */
36 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
39 #include <isl/val_gmp.h>
40 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
45 #include "coretypes.h"
52 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "gimplify-me.h"
57 #include "tree-ssa-loop-manip.h"
58 #include "tree-ssa-loop-niter.h"
59 #include "tree-ssa-loop.h"
60 #include "tree-into-ssa.h"
61 #include "tree-pass.h"
63 #include "tree-data-ref.h"
64 #include "tree-scalar-evolution.h"
66 #include "graphite-poly.h"
67 #include "tree-ssa-propagate.h"
68 #include "graphite-sese-to-poly.h"
71 /* Assigns to RES the value of the INTEGER_CST T. */
74 tree_int_to_gmp (tree t
, mpz_t res
)
76 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
79 /* Returns the index of the PHI argument defined in the outermost
83 phi_arg_in_outermost_loop (gphi
*phi
)
85 loop_p loop
= gimple_bb (phi
)->loop_father
;
88 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
89 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
91 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
98 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
99 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
102 remove_simple_copy_phi (gphi_iterator
*psi
)
104 gphi
*phi
= psi
->phi ();
105 tree res
= gimple_phi_result (phi
);
106 size_t entry
= phi_arg_in_outermost_loop (phi
);
107 tree init
= gimple_phi_arg_def (phi
, entry
);
108 gassign
*stmt
= gimple_build_assign (res
, init
);
109 edge e
= gimple_phi_arg_edge (phi
, entry
);
111 remove_phi_node (psi
, false);
112 gsi_insert_on_edge_immediate (e
, stmt
);
115 /* Removes an invariant phi node at position PSI by inserting on the
116 loop ENTRY edge the assignment RES = INIT. */
119 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
121 gphi
*phi
= psi
->phi ();
122 loop_p loop
= loop_containing_stmt (phi
);
123 tree res
= gimple_phi_result (phi
);
124 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
125 size_t entry
= phi_arg_in_outermost_loop (phi
);
126 edge e
= gimple_phi_arg_edge (phi
, entry
);
129 gimple_seq stmts
= NULL
;
131 if (tree_contains_chrecs (scev
, NULL
))
132 scev
= gimple_phi_arg_def (phi
, entry
);
134 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
135 stmt
= gimple_build_assign (res
, var
);
136 remove_phi_node (psi
, false);
138 gimple_seq_add_stmt (&stmts
, stmt
);
139 gsi_insert_seq_on_edge (e
, stmts
);
140 gsi_commit_edge_inserts ();
141 SSA_NAME_DEF_STMT (res
) = stmt
;
144 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
147 simple_copy_phi_p (gphi
*phi
)
151 if (gimple_phi_num_args (phi
) != 2)
154 res
= gimple_phi_result (phi
);
155 return (res
== gimple_phi_arg_def (phi
, 0)
156 || res
== gimple_phi_arg_def (phi
, 1));
159 /* Returns true when the phi node at position PSI is a reduction phi
160 node in REGION. Otherwise moves the pointer PSI to the next phi to
164 reduction_phi_p (sese region
, gphi_iterator
*psi
)
167 gphi
*phi
= psi
->phi ();
168 tree res
= gimple_phi_result (phi
);
170 loop
= loop_containing_stmt (phi
);
172 if (simple_copy_phi_p (phi
))
174 /* PRE introduces phi nodes like these, for an example,
175 see id-5.f in the fortran graphite testsuite:
177 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
179 remove_simple_copy_phi (psi
);
183 if (scev_analyzable_p (res
, region
))
185 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
187 if (evolution_function_is_invariant_p (scev
, loop
->num
))
188 remove_invariant_phi (region
, psi
);
195 /* All the other cases are considered reductions. */
199 /* Store the GRAPHITE representation of BB. */
202 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
204 struct gimple_bb
*gbb
;
206 gbb
= XNEW (struct gimple_bb
);
209 GBB_DATA_REFS (gbb
) = drs
;
210 GBB_CONDITIONS (gbb
).create (0);
211 GBB_CONDITION_CASES (gbb
).create (0);
217 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
220 struct data_reference
*dr
;
222 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
225 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
227 free (bap
->alias_set
);
236 free_gimple_bb (struct gimple_bb
*gbb
)
238 free_data_refs_aux (GBB_DATA_REFS (gbb
));
239 free_data_refs (GBB_DATA_REFS (gbb
));
241 GBB_CONDITIONS (gbb
).release ();
242 GBB_CONDITION_CASES (gbb
).release ();
243 GBB_BB (gbb
)->aux
= 0;
247 /* Deletes all gimple bbs in SCOP. */
250 remove_gbbs_in_scop (scop_p scop
)
255 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
256 free_gimple_bb (PBB_BLACK_BOX (pbb
));
259 /* Deletes all scops in SCOPS. */
262 free_scops (vec
<scop_p
> scops
)
267 FOR_EACH_VEC_ELT (scops
, i
, scop
)
269 remove_gbbs_in_scop (scop
);
270 free_sese (SCOP_REGION (scop
));
277 /* Same as outermost_loop_in_sese, returns the outermost loop
278 containing BB in REGION, but makes sure that the returned loop
279 belongs to the REGION, and so this returns the first loop in the
280 REGION when the loop containing BB does not belong to REGION. */
283 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
285 loop_p nest
= outermost_loop_in_sese (region
, bb
);
287 if (loop_in_sese_p (nest
, region
))
290 /* When the basic block BB does not belong to a loop in the region,
291 return the first loop in the region. */
294 if (loop_in_sese_p (nest
, region
))
303 /* Generates a polyhedral black box only if the bb contains interesting
307 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
309 vec
<data_reference_p
> drs
;
311 sese region
= SCOP_REGION (scop
);
312 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
313 gimple_stmt_iterator gsi
;
315 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
317 gimple
*stmt
= gsi_stmt (gsi
);
320 if (is_gimple_debug (stmt
))
323 loop
= loop_containing_stmt (stmt
);
324 if (!loop_in_sese_p (loop
, region
))
327 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
330 return new_gimple_bb (bb
, drs
);
333 /* Returns true if all predecessors of BB, that are not dominated by BB, are
334 marked in MAP. The predecessors dominated by BB are loop latches and will
335 be handled after BB. */
338 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
343 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
344 if (!bitmap_bit_p (map
, e
->src
->index
)
345 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
351 /* Compare the depth of two basic_block's P1 and P2. */
354 compare_bb_depths (const void *p1
, const void *p2
)
356 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
357 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
358 int d1
= loop_depth (bb1
->loop_father
);
359 int d2
= loop_depth (bb2
->loop_father
);
370 /* Sort the basic blocks from DOM such that the first are the ones at
371 a deepest loop level. */
374 graphite_sort_dominated_info (vec
<basic_block
> dom
)
376 dom
.qsort (compare_bb_depths
);
379 /* Recursive helper function for build_scops_bbs. */
382 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
384 sese region
= SCOP_REGION (scop
);
385 vec
<basic_block
> dom
;
388 if (bitmap_bit_p (visited
, bb
->index
)
389 || !bb_in_sese_p (bb
, region
))
392 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
393 SCOP_BBS (scop
).safe_push (pbb
);
394 bitmap_set_bit (visited
, bb
->index
);
396 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
401 graphite_sort_dominated_info (dom
);
403 while (!dom
.is_empty ())
408 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
409 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
411 build_scop_bbs_1 (scop
, visited
, dom_bb
);
412 dom
.unordered_remove (i
);
420 /* Gather the basic blocks belonging to the SCOP. */
423 build_scop_bbs (scop_p scop
)
425 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
426 sese region
= SCOP_REGION (scop
);
428 bitmap_clear (visited
);
429 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
430 sbitmap_free (visited
);
433 /* Return an ISL identifier for the polyhedral basic block PBB. */
436 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
439 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
440 return isl_id_alloc (s
->ctx
, name
, pbb
);
443 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
444 We generate SCATTERING_DIMENSIONS scattering dimensions.
446 The scattering polyhedron consists of these dimensions: scattering,
447 loop_iterators, parameters.
451 | scattering_dimensions = 5
459 | Scattering polyhedron:
461 | scattering: {s1, s2, s3, s4, s5}
462 | loop_iterators: {i}
463 | parameters: {p1, p2}
465 | s1 s2 s3 s4 s5 i p1 p2 1
466 | 1 0 0 0 0 0 0 0 -4 = 0
467 | 0 1 0 0 0 -1 0 0 0 = 0
468 | 0 0 1 0 0 0 0 0 -5 = 0 */
471 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
478 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
480 dc
= isl_set_get_space (pbb
->domain
);
481 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
482 isl_dim_out
, scattering_dimensions
);
483 pbb
->schedule
= isl_map_universe (dm
);
485 for (i
= 0; i
< scattering_dimensions
; i
++)
487 /* Textual order inside this loop. */
490 isl_constraint
*c
= isl_equality_alloc
491 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
493 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
494 gcc_assert (val
&& isl_val_is_int (val
));
496 val
= isl_val_neg (val
);
497 c
= isl_constraint_set_constant_val (c
, val
);
498 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
499 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
502 /* Iterations of this loop. */
503 else /* if ((i % 2) == 1) */
505 int loop
= (i
- 1) / 2;
506 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
511 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
514 /* Build for BB the static schedule.
516 The static schedule is a Dewey numbering of the abstract syntax
517 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
519 The following example informally defines the static schedule:
538 Static schedules for A to F:
551 build_scop_scattering (scop_p scop
)
555 gimple_bb_p previous_gbb
= NULL
;
556 isl_space
*dc
= isl_set_get_space (scop
->context
);
557 isl_aff
*static_sched
;
559 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
560 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
562 /* We have to start schedules at 0 on the first component and
563 because we cannot compare_prefix_loops against a previous loop,
564 prefix will be equal to zero, and that index will be
565 incremented before copying. */
566 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
568 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
570 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
574 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
580 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
582 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
585 isl_aff_free (static_sched
);
588 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
590 /* Extract an affine expression from the chain of recurrence E. */
593 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
595 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
596 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
597 isl_local_space
*ls
= isl_local_space_from_space (space
);
598 unsigned pos
= sese_loop_depth (SCOP_REGION (s
), get_chrec_loop (e
)) - 1;
599 isl_aff
*loop
= isl_aff_set_coefficient_si
600 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
601 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
603 /* Before multiplying, make sure that the result is affine. */
604 gcc_assert (isl_pw_aff_is_cst (rhs
)
605 || isl_pw_aff_is_cst (l
));
607 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
610 /* Extract an affine expression from the mult_expr E. */
613 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
615 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
616 isl_space_copy (space
));
617 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
619 if (!isl_pw_aff_is_cst (lhs
)
620 && !isl_pw_aff_is_cst (rhs
))
622 isl_pw_aff_free (lhs
);
623 isl_pw_aff_free (rhs
);
627 return isl_pw_aff_mul (lhs
, rhs
);
630 /* Return an ISL identifier from the name of the ssa_name E. */
633 isl_id_for_ssa_name (scop_p s
, tree e
)
635 const char *name
= get_name (e
);
639 id
= isl_id_alloc (s
->ctx
, name
, e
);
643 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
644 id
= isl_id_alloc (s
->ctx
, name1
, e
);
650 /* Return an ISL identifier for the data reference DR. */
653 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
655 /* Data references all get the same isl_id. They need to be comparable
656 and are distinguished through the first dimension, which contains the
658 return isl_id_alloc (s
->ctx
, "", 0);
661 /* Extract an affine expression from the ssa_name E. */
664 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
671 id
= isl_id_for_ssa_name (s
, e
);
672 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
674 dom
= isl_set_universe (isl_space_copy (space
));
675 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
676 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
677 return isl_pw_aff_alloc (dom
, aff
);
680 /* Extract an affine expression from the gmp constant G. */
683 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
685 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
686 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
687 isl_set
*dom
= isl_set_universe (space
);
691 ct
= isl_aff_get_ctx (aff
);
692 v
= isl_val_int_from_gmp (ct
, g
);
693 aff
= isl_aff_add_constant_val (aff
, v
);
695 return isl_pw_aff_alloc (dom
, aff
);
698 /* Extract an affine expression from the integer_cst E. */
701 extract_affine_int (tree e
, __isl_take isl_space
*space
)
707 tree_int_to_gmp (e
, g
);
708 res
= extract_affine_gmp (g
, space
);
714 /* Compute pwaff mod 2^width. */
717 wrap (isl_pw_aff
*pwaff
, unsigned width
)
721 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
722 mod
= isl_val_2exp (mod
);
723 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
728 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
729 Otherwise returns -1. */
732 parameter_index_in_region_1 (tree name
, sese region
)
737 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
739 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
746 /* When the parameter NAME is in REGION, returns its index in
747 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
748 and returns the index of NAME. */
751 parameter_index_in_region (tree name
, sese region
)
755 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
757 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
758 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
761 if (!invariant_in_sese_p_rec (name
, region
))
764 i
= parameter_index_in_region_1 (name
, region
);
768 gcc_assert (SESE_ADD_PARAMS (region
));
770 i
= SESE_PARAMS (region
).length ();
771 SESE_PARAMS (region
).safe_push (name
);
775 /* Extract an affine expression from the tree E in the scop S. */
778 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
780 isl_pw_aff
*lhs
, *rhs
, *res
;
783 if (e
== chrec_dont_know
) {
784 isl_space_free (space
);
788 switch (TREE_CODE (e
))
790 case POLYNOMIAL_CHREC
:
791 res
= extract_affine_chrec (s
, e
, space
);
795 res
= extract_affine_mul (s
, e
, space
);
799 case POINTER_PLUS_EXPR
:
800 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
801 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
802 res
= isl_pw_aff_add (lhs
, rhs
);
806 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
807 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
808 res
= isl_pw_aff_sub (lhs
, rhs
);
813 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
814 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
815 res
= isl_pw_aff_mul (lhs
, rhs
);
819 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->region
)
820 || !invariant_in_sese_p_rec (e
, s
->region
));
821 res
= extract_affine_name (s
, e
, space
);
825 res
= extract_affine_int (e
, space
);
826 /* No need to wrap a single integer. */
830 case NON_LVALUE_EXPR
:
831 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
839 type
= TREE_TYPE (e
);
840 if (TYPE_UNSIGNED (type
))
841 res
= wrap (res
, TYPE_PRECISION (type
));
846 /* In the context of sese S, scan the expression E and translate it to
847 a linear expression C. When parsing a symbolic multiplication, K
848 represents the constant multiplier of an expression containing
852 scan_tree_for_params (sese s
, tree e
)
854 if (e
== chrec_dont_know
)
857 switch (TREE_CODE (e
))
859 case POLYNOMIAL_CHREC
:
860 scan_tree_for_params (s
, CHREC_LEFT (e
));
864 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
865 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
867 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
871 case POINTER_PLUS_EXPR
:
873 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
874 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
880 case NON_LVALUE_EXPR
:
881 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
885 parameter_index_in_region (e
, s
);
901 /* Find parameters with respect to REGION in BB. We are looking in memory
902 access functions, conditions and loop bounds. */
905 find_params_in_bb (sese region
, gimple_bb_p gbb
)
911 loop_p loop
= GBB_BB (gbb
)->loop_father
;
913 /* Find parameters in the access functions of data references. */
914 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
915 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
916 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
918 /* Find parameters in conditional statements. */
919 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
921 tree lhs
= scalar_evolution_in_region (region
, loop
,
922 gimple_cond_lhs (stmt
));
923 tree rhs
= scalar_evolution_in_region (region
, loop
,
924 gimple_cond_rhs (stmt
));
926 scan_tree_for_params (region
, lhs
);
927 scan_tree_for_params (region
, rhs
);
931 /* Record the parameters used in the SCOP. A variable is a parameter
932 in a scop if it does not vary during the execution of that scop. */
935 find_scop_parameters (scop_p scop
)
939 sese region
= SCOP_REGION (scop
);
943 /* Find the parameters used in the loop bounds. */
944 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
946 tree nb_iters
= number_of_latch_executions (loop
);
948 if (!chrec_contains_symbols (nb_iters
))
951 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
952 scan_tree_for_params (region
, nb_iters
);
955 /* Find the parameters used in data accesses. */
956 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
957 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
959 nbp
= sese_nb_params (region
);
960 scop_set_nb_params (scop
, nbp
);
961 SESE_ADD_PARAMS (region
) = false;
965 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
967 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
968 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
969 isl_id_for_ssa_name (scop
, e
));
971 scop
->context
= isl_set_universe (space
);
975 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
976 the constraints for the surrounding loops. */
979 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
981 isl_set
*outer
, isl_set
**doms
)
983 tree nb_iters
= number_of_latch_executions (loop
);
984 sese region
= SCOP_REGION (scop
);
986 isl_set
*inner
= isl_set_copy (outer
);
989 int pos
= isl_set_dim (outer
, isl_dim_set
);
995 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
996 space
= isl_set_get_space (inner
);
999 c
= isl_inequality_alloc
1000 (isl_local_space_from_space (isl_space_copy (space
)));
1001 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1002 inner
= isl_set_add_constraint (inner
, c
);
1004 /* loop_i <= cst_nb_iters */
1005 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1007 c
= isl_inequality_alloc
1008 (isl_local_space_from_space (isl_space_copy (space
)));
1009 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1010 tree_int_to_gmp (nb_iters
, g
);
1011 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1012 c
= isl_constraint_set_constant_val (c
, v
);
1013 inner
= isl_set_add_constraint (inner
, c
);
1016 /* loop_i <= expr_nb_iters */
1017 else if (!chrec_contains_undetermined (nb_iters
))
1022 isl_local_space
*ls
;
1026 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1028 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1029 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1030 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1031 isl_set_dim (valid
, isl_dim_set
));
1032 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1034 ls
= isl_local_space_from_space (isl_space_copy (space
));
1035 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1036 isl_dim_in
, pos
, 1);
1037 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1038 isl_pw_aff_copy (aff
));
1039 inner
= isl_set_intersect (inner
, le
);
1041 if (max_stmt_executions (loop
, &nit
))
1043 /* Insert in the context the constraints from the
1044 estimation of the number of iterations NIT and the
1045 symbolic number of iterations (involving parameter
1046 names) NB_ITERS. First, build the affine expression
1047 "NIT - NB_ITERS" and then say that it is positive,
1048 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1055 wi::to_mpz (nit
, g
, SIGNED
);
1056 mpz_sub_ui (g
, g
, 1);
1057 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1058 x
= isl_pw_aff_ge_set (approx
, aff
);
1059 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1060 isl_set_dim (x
, isl_dim_set
));
1061 scop
->context
= isl_set_intersect (scop
->context
, x
);
1063 c
= isl_inequality_alloc
1064 (isl_local_space_from_space (isl_space_copy (space
)));
1065 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1066 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1068 c
= isl_constraint_set_constant_val (c
, v
);
1069 inner
= isl_set_add_constraint (inner
, c
);
1072 isl_pw_aff_free (aff
);
1077 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1078 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1079 isl_set_copy (inner
), doms
);
1083 && loop_in_sese_p (loop
->next
, region
))
1084 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1085 isl_set_copy (outer
), doms
);
1087 doms
[loop
->num
] = inner
;
1089 isl_set_free (outer
);
1090 isl_space_free (space
);
1094 /* Returns a linear expression for tree T evaluated in PBB. */
1097 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1099 scop_p scop
= PBB_SCOP (pbb
);
1101 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1102 gcc_assert (!automatically_generated_chrec_p (t
));
1104 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1107 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1108 operator. This allows us to invert the condition or to handle
1112 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1114 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1115 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1121 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1125 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1133 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1137 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1141 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1145 isl_pw_aff_free (lhs
);
1146 isl_pw_aff_free (rhs
);
1150 cond
= isl_set_coalesce (cond
);
1151 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1152 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1155 /* Add conditions to the domain of PBB. */
1158 add_conditions_to_domain (poly_bb_p pbb
)
1162 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1164 if (GBB_CONDITIONS (gbb
).is_empty ())
1167 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1168 switch (gimple_code (stmt
))
1172 /* Don't constrain on anything else than INTEGER_TYPE. */
1173 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1176 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1177 enum tree_code code
= gimple_cond_code (cond_stmt
);
1179 /* The conditions for ELSE-branches are inverted. */
1180 if (!GBB_CONDITION_CASES (gbb
)[i
])
1181 code
= invert_tree_comparison (code
, false);
1183 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1188 /* Switch statements are not supported right now - fall through. */
1196 /* Traverses all the GBBs of the SCOP and add their constraints to the
1197 iteration domains. */
1200 add_conditions_to_constraints (scop_p scop
)
1205 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1206 add_conditions_to_domain (pbb
);
1209 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1210 edge between BB and its predecessor is not a loop exit edge, and
1211 the last statement of the single predecessor is a COND_EXPR. */
1214 single_pred_cond_non_loop_exit (basic_block bb
)
1216 if (single_pred_p (bb
))
1218 edge e
= single_pred_edge (bb
);
1219 basic_block pred
= e
->src
;
1222 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1225 stmt
= last_stmt (pred
);
1227 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1228 return as_a
<gcond
*> (stmt
);
1234 class sese_dom_walker
: public dom_walker
1237 sese_dom_walker (cdi_direction
, sese
);
1239 virtual void before_dom_children (basic_block
);
1240 virtual void after_dom_children (basic_block
);
1243 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1247 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1248 : dom_walker (direction
), m_region (region
)
1252 /* Call-back for dom_walk executed before visiting the dominated
1256 sese_dom_walker::before_dom_children (basic_block bb
)
1261 if (!bb_in_sese_p (bb
, m_region
))
1264 stmt
= single_pred_cond_non_loop_exit (bb
);
1268 edge e
= single_pred_edge (bb
);
1270 m_conditions
.safe_push (stmt
);
1272 if (e
->flags
& EDGE_TRUE_VALUE
)
1273 m_cases
.safe_push (stmt
);
1275 m_cases
.safe_push (NULL
);
1278 gbb
= gbb_from_bb (bb
);
1282 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1283 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1287 /* Call-back for dom_walk executed after visiting the dominated
1291 sese_dom_walker::after_dom_children (basic_block bb
)
1293 if (!bb_in_sese_p (bb
, m_region
))
1296 if (single_pred_cond_non_loop_exit (bb
))
1298 m_conditions
.pop ();
1303 /* Add constraints on the possible values of parameter P from the type
1307 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1309 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1310 tree type
= TREE_TYPE (parameter
);
1311 tree lb
= NULL_TREE
;
1312 tree ub
= NULL_TREE
;
1314 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1315 lb
= lower_bound_in_type (type
, type
);
1317 lb
= TYPE_MIN_VALUE (type
);
1319 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1320 ub
= upper_bound_in_type (type
, type
);
1322 ub
= TYPE_MAX_VALUE (type
);
1326 isl_space
*space
= isl_set_get_space (scop
->context
);
1331 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1333 tree_int_to_gmp (lb
, g
);
1334 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1335 v
= isl_val_neg (v
);
1337 c
= isl_constraint_set_constant_val (c
, v
);
1338 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1340 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1345 isl_space
*space
= isl_set_get_space (scop
->context
);
1350 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1353 tree_int_to_gmp (ub
, g
);
1354 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1356 c
= isl_constraint_set_constant_val (c
, v
);
1357 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1359 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1363 /* Build the context of the SCOP. The context usually contains extra
1364 constraints that are added to the iteration domains that constrain
1368 build_scop_context (scop_p scop
)
1370 graphite_dim_t p
, n
= scop_nb_params (scop
);
1372 for (p
= 0; p
< n
; p
++)
1373 add_param_constraints (scop
, p
);
1376 /* Build the iteration domains: the loops belonging to the current
1377 SCOP, and that vary for the execution of the current basic block.
1378 Returns false if there is no loop in SCOP. */
1381 build_scop_iteration_domain (scop_p scop
)
1384 sese region
= SCOP_REGION (scop
);
1387 int nb_loops
= number_of_loops (cfun
);
1388 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1390 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1391 if (!loop_in_sese_p (loop_outer (loop
), region
))
1392 build_loop_iteration_domains (scop
, loop
, 0,
1393 isl_set_copy (scop
->context
), doms
);
1395 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1397 loop
= pbb_loop (pbb
);
1399 if (doms
[loop
->num
])
1400 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1402 pbb
->domain
= isl_set_copy (scop
->context
);
1404 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1405 isl_id_for_pbb (scop
, pbb
));
1408 for (i
= 0; i
< nb_loops
; i
++)
1410 isl_set_free (doms
[i
]);
1415 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1416 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1417 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1421 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1424 int alias_set_num
= 0;
1425 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1427 if (bap
&& bap
->alias_set
)
1428 alias_set_num
= *(bap
->alias_set
);
1430 c
= isl_equality_alloc
1431 (isl_local_space_from_space (isl_map_get_space (acc
)));
1432 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1433 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1435 return isl_map_add_constraint (acc
, c
);
1438 /* Assign the affine expression INDEX to the output dimension POS of
1439 MAP and return the result. */
1442 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1445 int len
= isl_map_dim (map
, isl_dim_out
);
1448 index_map
= isl_map_from_pw_aff (index
);
1449 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1450 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1452 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1453 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1454 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1455 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1457 return isl_map_intersect (map
, index_map
);
1460 /* Add to ACCESSES polyhedron equalities defining the access functions
1461 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1462 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1463 PBB is the poly_bb_p that contains the data reference DR. */
1466 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1468 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1469 scop_p scop
= PBB_SCOP (pbb
);
1471 for (i
= 0; i
< nb_subscripts
; i
++)
1474 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1476 aff
= extract_affine (scop
, afn
,
1477 isl_space_domain (isl_map_get_space (acc
)));
1478 acc
= set_index (acc
, i
+ 1, aff
);
1484 /* Add constrains representing the size of the accessed data to the
1485 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1486 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1490 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1491 data_reference_p dr
)
1493 tree ref
= DR_REF (dr
);
1495 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1496 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1498 if (TREE_CODE (ref
) != ARRAY_REF
)
1499 return subscript_sizes
;
1501 tree low
= array_ref_low_bound (ref
);
1502 tree high
= array_ref_up_bound (ref
);
1504 /* XXX The PPL code dealt separately with
1505 subscript - low >= 0 and high - subscript >= 0 in case one of
1506 the two bounds isn't known. Do the same here? */
1508 if (tree_fits_shwi_p (low
)
1510 && tree_fits_shwi_p (high
)
1511 /* 1-element arrays at end of structures may extend over
1512 their declared size. */
1513 && !(array_at_struct_end_p (ref
)
1514 && operand_equal_p (low
, high
, 0)))
1518 isl_set
*univ
, *lbs
, *ubs
;
1521 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1522 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1523 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1526 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1527 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1528 isl_set_dim (valid
, isl_dim_set
));
1529 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1531 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1532 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1533 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1534 index
= isl_pw_aff_alloc (univ
, aff
);
1536 id
= isl_set_get_tuple_id (subscript_sizes
);
1537 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1538 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1540 /* low <= sub_i <= high */
1541 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1542 ubs
= isl_pw_aff_le_set (index
, ub
);
1543 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1544 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1548 return subscript_sizes
;
1551 /* Build data accesses for DR in PBB. */
1554 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1556 int dr_base_object_set
;
1558 isl_set
*subscript_sizes
;
1559 scop_p scop
= PBB_SCOP (pbb
);
1562 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1563 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1564 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1565 isl_dim_out
, nb_out
);
1567 acc
= isl_map_universe (space
);
1568 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1571 acc
= pdr_add_alias_set (acc
, dr
);
1572 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1575 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1576 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1577 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1578 int alias_set_num
= 0;
1579 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1581 if (bap
&& bap
->alias_set
)
1582 alias_set_num
= *(bap
->alias_set
);
1584 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1585 subscript_sizes
= isl_set_nat_universe (space
);
1586 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1588 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1591 gcc_assert (dr
->aux
);
1592 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1594 new_poly_dr (pbb
, dr_base_object_set
,
1595 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1596 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1599 /* Write to FILE the alias graph of data references in DIMACS format. */
1602 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1603 vec
<data_reference_p
> drs
)
1605 int num_vertex
= drs
.length ();
1607 data_reference_p dr1
, dr2
;
1610 if (num_vertex
== 0)
1613 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1614 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1615 if (dr_may_alias_p (dr1
, dr2
, true))
1618 fprintf (file
, "$\n");
1621 fprintf (file
, "c %s\n", comment
);
1623 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1625 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1626 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1627 if (dr_may_alias_p (dr1
, dr2
, true))
1628 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1633 /* Write to FILE the alias graph of data references in DOT format. */
1636 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1637 vec
<data_reference_p
> drs
)
1639 int num_vertex
= drs
.length ();
1640 data_reference_p dr1
, dr2
;
1643 if (num_vertex
== 0)
1646 fprintf (file
, "$\n");
1649 fprintf (file
, "c %s\n", comment
);
1651 /* First print all the vertices. */
1652 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1653 fprintf (file
, "n%d;\n", i
);
1655 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1656 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1657 if (dr_may_alias_p (dr1
, dr2
, true))
1658 fprintf (file
, "n%d n%d\n", i
, j
);
1663 /* Write to FILE the alias graph of data references in ECC format. */
1666 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1667 vec
<data_reference_p
> drs
)
1669 int num_vertex
= drs
.length ();
1670 data_reference_p dr1
, dr2
;
1673 if (num_vertex
== 0)
1676 fprintf (file
, "$\n");
1679 fprintf (file
, "c %s\n", comment
);
1681 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1682 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1683 if (dr_may_alias_p (dr1
, dr2
, true))
1684 fprintf (file
, "%d %d\n", i
, j
);
1689 /* Check if DR1 and DR2 are in the same object set. */
1692 dr_same_base_object_p (const struct data_reference
*dr1
,
1693 const struct data_reference
*dr2
)
1695 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1698 /* Uses DFS component number as representative of alias-sets. Also tests for
1699 optimality by verifying if every connected component is a clique. Returns
1700 true (1) if the above test is true, and false (0) otherwise. */
1703 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1705 int num_vertices
= drs
.length ();
1706 struct graph
*g
= new_graph (num_vertices
);
1707 data_reference_p dr1
, dr2
;
1709 int num_connected_components
;
1710 int v_indx1
, v_indx2
, num_vertices_in_component
;
1713 struct graph_edge
*e
;
1714 int this_component_is_clique
;
1715 int all_components_are_cliques
= 1;
1717 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1718 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1719 if (dr_may_alias_p (dr1
, dr2
, true))
1725 all_vertices
= XNEWVEC (int, num_vertices
);
1726 vertices
= XNEWVEC (int, num_vertices
);
1727 for (i
= 0; i
< num_vertices
; i
++)
1728 all_vertices
[i
] = i
;
1730 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1732 for (i
= 0; i
< g
->n_vertices
; i
++)
1734 data_reference_p dr
= drs
[i
];
1735 base_alias_pair
*bap
;
1737 gcc_assert (dr
->aux
);
1738 bap
= (base_alias_pair
*)(dr
->aux
);
1740 bap
->alias_set
= XNEW (int);
1741 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1744 /* Verify if the DFS numbering results in optimal solution. */
1745 for (i
= 0; i
< num_connected_components
; i
++)
1747 num_vertices_in_component
= 0;
1748 /* Get all vertices whose DFS component number is the same as i. */
1749 for (j
= 0; j
< num_vertices
; j
++)
1750 if (g
->vertices
[j
].component
== i
)
1751 vertices
[num_vertices_in_component
++] = j
;
1753 /* Now test if the vertices in 'vertices' form a clique, by testing
1754 for edges among each pair. */
1755 this_component_is_clique
= 1;
1756 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1758 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1760 /* Check if the two vertices are connected by iterating
1761 through all the edges which have one of these are source. */
1762 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1765 if (e
->src
== vertices
[v_indx1
])
1771 this_component_is_clique
= 0;
1775 if (!this_component_is_clique
)
1776 all_components_are_cliques
= 0;
1780 free (all_vertices
);
1783 return all_components_are_cliques
;
1786 /* Group each data reference in DRS with its base object set num. */
1789 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1791 int num_vertex
= drs
.length ();
1792 struct graph
*g
= new_graph (num_vertex
);
1793 data_reference_p dr1
, dr2
;
1797 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1798 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1799 if (dr_same_base_object_p (dr1
, dr2
))
1805 queue
= XNEWVEC (int, num_vertex
);
1806 for (i
= 0; i
< num_vertex
; i
++)
1809 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1811 for (i
= 0; i
< g
->n_vertices
; i
++)
1813 data_reference_p dr
= drs
[i
];
1814 base_alias_pair
*bap
;
1816 gcc_assert (dr
->aux
);
1817 bap
= (base_alias_pair
*)(dr
->aux
);
1819 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1826 /* Build the data references for PBB. */
1829 build_pbb_drs (poly_bb_p pbb
)
1832 data_reference_p dr
;
1833 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1835 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1836 build_poly_dr (dr
, pbb
);
1839 /* Dump to file the alias graphs for the data references in DRS. */
1842 dump_alias_graphs (vec
<data_reference_p
> drs
)
1845 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1847 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1850 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1851 current_function_name ());
1852 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1853 fclose (file_dimacs
);
1856 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1859 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1860 current_function_name ());
1861 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1865 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1868 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1869 current_function_name ());
1870 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1875 /* Build data references in SCOP. */
1878 build_scop_drs (scop_p scop
)
1882 data_reference_p dr
;
1883 auto_vec
<data_reference_p
, 3> drs
;
1885 /* Remove all the PBBs that do not have data references: these basic
1886 blocks are not handled in the polyhedral representation. */
1887 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1888 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1890 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1892 SCOP_BBS (scop
).ordered_remove (i
);
1896 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1897 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1900 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1901 dr
->aux
= XNEW (base_alias_pair
);
1903 if (!build_alias_set_optimal_p (drs
))
1905 /* TODO: Add support when building alias set is not optimal. */
1909 build_base_obj_set_for_drs (drs
);
1911 /* When debugging, enable the following code. This cannot be used
1912 in production compilers. */
1914 dump_alias_graphs (drs
);
1918 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1919 build_pbb_drs (pbb
);
1922 /* Return a gsi at the position of the phi node STMT. */
1924 static gphi_iterator
1925 gsi_for_phi_node (gphi
*stmt
)
1928 basic_block bb
= gimple_bb (stmt
);
1930 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1931 if (stmt
== psi
.phi ())
1938 /* Analyze all the data references of STMTS and add them to the
1939 GBB_DATA_REFS vector of BB. */
1942 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1948 sese region
= SCOP_REGION (scop
);
1950 if (!bb_in_sese_p (bb
, region
))
1953 nest
= outermost_loop_in_sese_1 (region
, bb
);
1954 gbb
= gbb_from_bb (bb
);
1956 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1960 if (is_gimple_debug (stmt
))
1963 loop
= loop_containing_stmt (stmt
);
1964 if (!loop_in_sese_p (loop
, region
))
1967 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1968 &GBB_DATA_REFS (gbb
));
1972 /* Insert STMT at the end of the STMTS sequence and then insert the
1973 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1977 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1978 gimple_stmt_iterator insert_gsi
)
1980 gimple_stmt_iterator gsi
;
1981 auto_vec
<gimple
*, 3> x
;
1983 gimple_seq_add_stmt (&stmts
, stmt
);
1984 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1985 x
.safe_push (gsi_stmt (gsi
));
1987 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1988 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1991 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1994 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1997 gimple_stmt_iterator gsi
;
1998 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1999 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2000 auto_vec
<gimple
*, 3> x
;
2002 gimple_seq_add_stmt (&stmts
, stmt
);
2003 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2004 x
.safe_push (gsi_stmt (gsi
));
2006 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2008 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2009 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2013 gsi
= gsi_for_stmt (after_stmt
);
2014 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2017 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2020 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2023 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2025 vec
<data_reference_p
> drs
;
2027 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2028 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2029 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2030 int index
, n
= SCOP_BBS (scop
).length ();
2032 /* The INDEX of PBB in SCOP_BBS. */
2033 for (index
= 0; index
< n
; index
++)
2034 if (SCOP_BBS (scop
)[index
] == pbb
)
2037 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2038 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2039 isl_id_for_pbb (scop
, pbb1
));
2041 GBB_PBB (gbb1
) = pbb1
;
2042 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2043 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2044 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2047 /* Insert on edge E the assignment "RES := EXPR". */
2050 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2052 gimple_stmt_iterator gsi
;
2053 gimple_seq stmts
= NULL
;
2054 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2055 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2057 auto_vec
<gimple
*, 3> x
;
2059 gimple_seq_add_stmt (&stmts
, stmt
);
2060 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2061 x
.safe_push (gsi_stmt (gsi
));
2063 gsi_insert_seq_on_edge (e
, stmts
);
2064 gsi_commit_edge_inserts ();
2065 bb
= gimple_bb (stmt
);
2067 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2070 if (!gbb_from_bb (bb
))
2071 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2073 analyze_drs_in_stmts (scop
, bb
, x
);
2076 /* Creates a zero dimension array of the same type as VAR. */
2079 create_zero_dim_array (tree var
, const char *base_name
)
2081 tree index_type
= build_index_type (integer_zero_node
);
2082 tree elt_type
= TREE_TYPE (var
);
2083 tree array_type
= build_array_type (elt_type
, index_type
);
2084 tree base
= create_tmp_var (array_type
, base_name
);
2086 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2090 /* Returns true when PHI is a loop close phi node. */
2093 scalar_close_phi_node_p (gimple
*phi
)
2095 if (gimple_code (phi
) != GIMPLE_PHI
2096 || virtual_operand_p (gimple_phi_result (phi
)))
2099 /* Note that loop close phi nodes should have a single argument
2100 because we translated the representation into a canonical form
2101 before Graphite: see canonicalize_loop_closed_ssa_form. */
2102 return (gimple_phi_num_args (phi
) == 1);
2105 /* For a definition DEF in REGION, propagates the expression EXPR in
2106 all the uses of DEF outside REGION. */
2109 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2111 imm_use_iterator imm_iter
;
2114 bool replaced_once
= false;
2116 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2118 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2121 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2122 if (!is_gimple_debug (use_stmt
)
2123 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2126 use_operand_p use_p
;
2128 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2129 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2130 && (replaced_once
= true))
2131 replace_exp (use_p
, expr
);
2133 update_stmt (use_stmt
);
2138 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2139 gsi_commit_edge_inserts ();
2143 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2144 dimension array for it. */
2147 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2149 sese region
= SCOP_REGION (scop
);
2150 gimple
*phi
= gsi_stmt (*psi
);
2151 tree res
= gimple_phi_result (phi
);
2152 basic_block bb
= gimple_bb (phi
);
2153 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2154 tree arg
= gimple_phi_arg_def (phi
, 0);
2157 /* Note that loop close phi nodes should have a single argument
2158 because we translated the representation into a canonical form
2159 before Graphite: see canonicalize_loop_closed_ssa_form. */
2160 gcc_assert (gimple_phi_num_args (phi
) == 1);
2162 /* The phi node can be a non close phi node, when its argument is
2163 invariant, or a default definition. */
2164 if (is_gimple_min_invariant (arg
)
2165 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2167 propagate_expr_outside_region (res
, arg
, region
);
2172 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2174 propagate_expr_outside_region (res
, arg
, region
);
2175 stmt
= gimple_build_assign (res
, arg
);
2176 remove_phi_node (psi
, false);
2177 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2181 /* If res is scev analyzable and is not a scalar value, it is safe
2182 to ignore the close phi node: it will be code generated in the
2183 out of Graphite pass. */
2184 else if (scev_analyzable_p (res
, region
))
2186 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2189 if (!loop_in_sese_p (loop
, region
))
2191 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2192 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2193 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2196 scev
= scalar_evolution_in_region (region
, loop
, res
);
2198 if (tree_does_not_contain_chrecs (scev
))
2199 propagate_expr_outside_region (res
, scev
, region
);
2206 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2208 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2210 if (TREE_CODE (arg
) == SSA_NAME
)
2211 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2212 SSA_NAME_DEF_STMT (arg
));
2214 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2215 zero_dim_array
, arg
);
2218 remove_phi_node (psi
, false);
2219 SSA_NAME_DEF_STMT (res
) = stmt
;
2221 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2224 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2225 dimension array for it. */
2228 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2231 gphi
*phi
= psi
->phi ();
2232 basic_block bb
= gimple_bb (phi
);
2233 tree res
= gimple_phi_result (phi
);
2234 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2237 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2239 tree arg
= gimple_phi_arg_def (phi
, i
);
2240 edge e
= gimple_phi_arg_edge (phi
, i
);
2242 /* Avoid the insertion of code in the loop latch to please the
2243 pattern matching of the vectorizer. */
2244 if (TREE_CODE (arg
) == SSA_NAME
2245 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2246 && e
->src
== bb
->loop_father
->latch
)
2247 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2248 SSA_NAME_DEF_STMT (arg
));
2250 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2253 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2254 remove_phi_node (psi
, false);
2255 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2258 /* Rewrite the degenerate phi node at position PSI from the degenerate
2259 form "x = phi (y, y, ..., y)" to "x = y". */
2262 rewrite_degenerate_phi (gphi_iterator
*psi
)
2266 gimple_stmt_iterator gsi
;
2267 gphi
*phi
= psi
->phi ();
2268 tree res
= gimple_phi_result (phi
);
2271 bb
= gimple_bb (phi
);
2272 rhs
= degenerate_phi_result (phi
);
2275 stmt
= gimple_build_assign (res
, rhs
);
2276 remove_phi_node (psi
, false);
2278 gsi
= gsi_after_labels (bb
);
2279 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2282 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2285 rewrite_reductions_out_of_ssa (scop_p scop
)
2289 sese region
= SCOP_REGION (scop
);
2291 FOR_EACH_BB_FN (bb
, cfun
)
2292 if (bb_in_sese_p (bb
, region
))
2293 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2295 gphi
*phi
= psi
.phi ();
2297 if (virtual_operand_p (gimple_phi_result (phi
)))
2303 if (gimple_phi_num_args (phi
) > 1
2304 && degenerate_phi_result (phi
))
2305 rewrite_degenerate_phi (&psi
);
2307 else if (scalar_close_phi_node_p (phi
))
2308 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2310 else if (reduction_phi_p (region
, &psi
))
2311 rewrite_phi_out_of_ssa (scop
, &psi
);
2314 update_ssa (TODO_update_ssa
);
2315 #ifdef ENABLE_CHECKING
2316 verify_loop_closed_ssa (true);
2320 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2321 read from ZERO_DIM_ARRAY. */
2324 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2325 tree def
, gimple
*use_stmt
)
2330 use_operand_p use_p
;
2332 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2334 name
= copy_ssa_name (def
);
2335 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2337 gimple_assign_set_lhs (name_stmt
, name
);
2338 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2340 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2341 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2342 replace_exp (use_p
, name
);
2344 update_stmt (use_stmt
);
2347 /* For every definition DEF in the SCOP that is used outside the scop,
2348 insert a closing-scop definition in the basic block just after this
2352 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
2354 tree var
= create_tmp_reg (TREE_TYPE (def
));
2355 tree new_name
= make_ssa_name (var
, stmt
);
2356 bool needs_copy
= false;
2357 use_operand_p use_p
;
2358 imm_use_iterator imm_iter
;
2360 sese region
= SCOP_REGION (scop
);
2362 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2364 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2366 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2368 SET_USE (use_p
, new_name
);
2370 update_stmt (use_stmt
);
2375 /* Insert in the empty BB just after the scop a use of DEF such
2376 that the rewrite of cross_bb_scalar_dependences won't insert
2377 arrays everywhere else. */
2380 gimple
*assign
= gimple_build_assign (new_name
, def
);
2381 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2383 update_stmt (assign
);
2384 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2388 /* Rewrite the scalar dependences crossing the boundary of the BB
2389 containing STMT with an array. Return true when something has been
2393 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2395 sese region
= SCOP_REGION (scop
);
2396 gimple
*stmt
= gsi_stmt (*gsi
);
2397 imm_use_iterator imm_iter
;
2400 tree zero_dim_array
= NULL_TREE
;
2404 switch (gimple_code (stmt
))
2407 def
= gimple_assign_lhs (stmt
);
2411 def
= gimple_call_lhs (stmt
);
2419 || !is_gimple_reg (def
))
2422 if (scev_analyzable_p (def
, region
))
2424 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2425 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2427 if (tree_contains_chrecs (scev
, NULL
))
2430 propagate_expr_outside_region (def
, scev
, region
);
2434 def_bb
= gimple_bb (stmt
);
2436 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2438 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2439 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2442 gphi_iterator psi
= gsi_for_phi (phi
);
2444 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2445 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2447 rewrite_phi_out_of_ssa (scop
, &psi
);
2450 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2451 if (gimple_code (use_stmt
) != GIMPLE_PHI
2452 && def_bb
!= gimple_bb (use_stmt
)
2453 && !is_gimple_debug (use_stmt
)
2456 if (!zero_dim_array
)
2458 zero_dim_array
= create_zero_dim_array
2459 (def
, "Cross_BB_scalar_dependence");
2460 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2461 SSA_NAME_DEF_STMT (def
));
2465 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2469 update_ssa (TODO_update_ssa
);
2474 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2477 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2480 gimple_stmt_iterator psi
;
2481 sese region
= SCOP_REGION (scop
);
2482 bool changed
= false;
2484 /* Create an extra empty BB after the scop. */
2485 split_edge (SESE_EXIT (region
));
2487 FOR_EACH_BB_FN (bb
, cfun
)
2488 if (bb_in_sese_p (bb
, region
))
2489 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2490 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2495 update_ssa (TODO_update_ssa
);
2496 #ifdef ENABLE_CHECKING
2497 verify_loop_closed_ssa (true);
2502 /* Returns the number of pbbs that are in loops contained in SCOP. */
2505 nb_pbbs_in_loops (scop_p scop
)
2511 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2512 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2518 /* Return the number of data references in BB that write in
2522 nb_data_writes_in_bb (basic_block bb
)
2525 gimple_stmt_iterator gsi
;
2527 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2528 if (gimple_vdef (gsi_stmt (gsi
)))
2534 /* Splits at STMT the basic block BB represented as PBB in the
2538 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple
*stmt
)
2540 edge e1
= split_block (bb
, stmt
);
2541 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2545 /* Splits STMT out of its current BB. This is done for reduction
2546 statements for which we want to ignore data dependences. */
2549 split_reduction_stmt (scop_p scop
, gimple
*stmt
)
2551 basic_block bb
= gimple_bb (stmt
);
2552 poly_bb_p pbb
= pbb_from_bb (bb
);
2553 gimple_bb_p gbb
= gbb_from_bb (bb
);
2556 data_reference_p dr
;
2558 /* Do not split basic blocks with no writes to memory: the reduction
2559 will be the only write to memory. */
2560 if (nb_data_writes_in_bb (bb
) == 0
2561 /* Or if we have already marked BB as a reduction. */
2562 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2565 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2567 /* Split once more only when the reduction stmt is not the only one
2568 left in the original BB. */
2569 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2571 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2573 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2576 /* A part of the data references will end in a different basic block
2577 after the split: move the DRs from the original GBB to the newly
2579 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2581 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2585 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2586 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2587 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2595 /* Return true when stmt is a reduction operation. */
2598 is_reduction_operation_p (gimple
*stmt
)
2600 enum tree_code code
;
2602 gcc_assert (is_gimple_assign (stmt
));
2603 code
= gimple_assign_rhs_code (stmt
);
2605 if (!commutative_tree_code (code
)
2606 || !associative_tree_code (code
))
2609 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2611 if (FLOAT_TYPE_P (type
))
2612 return flag_associative_math
;
2614 if (ANY_INTEGRAL_TYPE_P (type
))
2615 return (TYPE_OVERFLOW_WRAPS (type
)
2616 || !operation_can_overflow (code
));
2621 /* Returns true when PHI contains an argument ARG. */
2624 phi_contains_arg (gphi
*phi
, tree arg
)
2628 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2629 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2635 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2638 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2642 if (TREE_CODE (arg
) != SSA_NAME
)
2645 stmt
= SSA_NAME_DEF_STMT (arg
);
2647 if (gimple_code (stmt
) == GIMPLE_NOP
2648 || gimple_code (stmt
) == GIMPLE_CALL
)
2651 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2653 if (phi_contains_arg (phi
, lhs
))
2658 if (!is_gimple_assign (stmt
))
2661 if (gimple_num_ops (stmt
) == 2)
2662 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2664 if (is_reduction_operation_p (stmt
))
2667 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2670 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2676 /* Detect commutative and associative scalar reductions starting at
2677 the STMT. Return the phi node of the reduction cycle, or NULL. */
2680 detect_commutative_reduction_arg (tree lhs
, gimple
*stmt
, tree arg
,
2684 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2689 in
->safe_push (stmt
);
2690 out
->safe_push (stmt
);
2694 /* Detect commutative and associative scalar reductions starting at
2695 STMT. Return the phi node of the reduction cycle, or NULL. */
2698 detect_commutative_reduction_assign (gimple
*stmt
, vec
<gimple
*> *in
,
2701 tree lhs
= gimple_assign_lhs (stmt
);
2703 if (gimple_num_ops (stmt
) == 2)
2704 return detect_commutative_reduction_arg (lhs
, stmt
,
2705 gimple_assign_rhs1 (stmt
),
2708 if (is_reduction_operation_p (stmt
))
2710 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2711 gimple_assign_rhs1 (stmt
),
2714 : detect_commutative_reduction_arg (lhs
, stmt
,
2715 gimple_assign_rhs2 (stmt
),
2722 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2725 follow_inital_value_to_phi (tree arg
, tree lhs
)
2729 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2732 stmt
= SSA_NAME_DEF_STMT (arg
);
2734 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2735 if (phi_contains_arg (phi
, lhs
))
2742 /* Return the argument of the loop PHI that is the initial value coming
2743 from outside the loop. */
2746 edge_initial_value_for_loop_phi (gphi
*phi
)
2750 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2752 edge e
= gimple_phi_arg_edge (phi
, i
);
2754 if (loop_depth (e
->src
->loop_father
)
2755 < loop_depth (e
->dest
->loop_father
))
2762 /* Return the argument of the loop PHI that is the initial value coming
2763 from outside the loop. */
2766 initial_value_for_loop_phi (gphi
*phi
)
2770 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2772 edge e
= gimple_phi_arg_edge (phi
, i
);
2774 if (loop_depth (e
->src
->loop_father
)
2775 < loop_depth (e
->dest
->loop_father
))
2776 return gimple_phi_arg_def (phi
, i
);
2782 /* Returns true when DEF is used outside the reduction cycle of
2786 used_outside_reduction (tree def
, gimple
*loop_phi
)
2788 use_operand_p use_p
;
2789 imm_use_iterator imm_iter
;
2790 loop_p loop
= loop_containing_stmt (loop_phi
);
2792 /* In LOOP, DEF should be used only in LOOP_PHI. */
2793 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2795 gimple
*stmt
= USE_STMT (use_p
);
2797 if (stmt
!= loop_phi
2798 && !is_gimple_debug (stmt
)
2799 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2806 /* Detect commutative and associative scalar reductions belonging to
2807 the SCOP starting at the loop closed phi node STMT. Return the phi
2808 node of the reduction cycle, or NULL. */
2811 detect_commutative_reduction (scop_p scop
, gimple
*stmt
, vec
<gimple
*> *in
,
2814 if (scalar_close_phi_node_p (stmt
))
2817 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2818 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2820 if (TREE_CODE (arg
) != SSA_NAME
)
2823 /* Note that loop close phi nodes should have a single argument
2824 because we translated the representation into a canonical form
2825 before Graphite: see canonicalize_loop_closed_ssa_form. */
2826 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2828 def
= SSA_NAME_DEF_STMT (arg
);
2829 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2830 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2833 lhs
= gimple_phi_result (close_phi
);
2834 init
= initial_value_for_loop_phi (loop_phi
);
2835 phi
= follow_inital_value_to_phi (init
, lhs
);
2837 if (phi
&& (used_outside_reduction (lhs
, phi
)
2838 || !has_single_use (gimple_phi_result (phi
))))
2841 in
->safe_push (loop_phi
);
2842 out
->safe_push (close_phi
);
2846 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2847 return detect_commutative_reduction_assign (stmt
, in
, out
);
2852 /* Translate the scalar reduction statement STMT to an array RED
2853 knowing that its recursive phi node is LOOP_PHI. */
2856 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2857 gimple
*stmt
, gphi
*loop_phi
)
2859 tree res
= gimple_phi_result (loop_phi
);
2860 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2861 gimple_stmt_iterator gsi
;
2863 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2865 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2866 gsi
= gsi_for_stmt (stmt
);
2868 insert_stmts (scop
, assign
, NULL
, gsi
);
2871 /* Removes the PHI node and resets all the debug stmts that are using
2875 remove_phi (gphi
*phi
)
2877 imm_use_iterator imm_iter
;
2879 use_operand_p use_p
;
2880 gimple_stmt_iterator gsi
;
2881 auto_vec
<gimple
*, 3> update
;
2885 def
= PHI_RESULT (phi
);
2886 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2888 stmt
= USE_STMT (use_p
);
2890 if (is_gimple_debug (stmt
))
2892 gimple_debug_bind_reset_value (stmt
);
2893 update
.safe_push (stmt
);
2897 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2900 gsi
= gsi_for_phi_node (phi
);
2901 remove_phi_node (&gsi
, false);
2904 /* Helper function for for_each_index. For each INDEX of the data
2905 reference REF, returns true when its indices are valid in the loop
2906 nest LOOP passed in as DATA. */
2909 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2912 basic_block header
, def_bb
;
2915 if (TREE_CODE (*index
) != SSA_NAME
)
2918 loop
= *((loop_p
*) data
);
2919 header
= loop
->header
;
2920 stmt
= SSA_NAME_DEF_STMT (*index
);
2925 def_bb
= gimple_bb (stmt
);
2930 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2933 /* When the result of a CLOSE_PHI is written to a memory location,
2934 return a pointer to that memory reference, otherwise return
2938 close_phi_written_to_memory (gphi
*close_phi
)
2940 imm_use_iterator imm_iter
;
2941 use_operand_p use_p
;
2943 tree res
, def
= gimple_phi_result (close_phi
);
2945 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2946 if ((stmt
= USE_STMT (use_p
))
2947 && gimple_code (stmt
) == GIMPLE_ASSIGN
2948 && (res
= gimple_assign_lhs (stmt
)))
2950 switch (TREE_CODE (res
))
2960 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2961 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2963 /* FIXME: this restriction is for id-{24,25}.f and
2964 could be handled by duplicating the computation of
2965 array indices before the loop of the close_phi. */
2966 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2978 /* Rewrite out of SSA the reduction described by the loop phi nodes
2979 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2982 IN: stmt, loop_n, ..., loop_0
2983 OUT: stmt, close_n, ..., close_0
2985 the first element is the reduction statement, and the next elements
2986 are the loop and close phi nodes of each of the outer loops. */
2989 translate_scalar_reduction_to_array (scop_p scop
,
2994 unsigned int i
= out
.length () - 1;
2995 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
2997 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
2999 gimple
*close_stmt
= out
[i
];
3003 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
3004 poly_bb_p pbb
= pbb_from_bb (bb
);
3005 PBB_IS_REDUCTION (pbb
) = true;
3006 gcc_assert (close_stmt
== loop_stmt
);
3009 red
= create_zero_dim_array
3010 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3012 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3013 as_a
<gphi
*> (in
[1]));
3017 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3018 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3020 if (i
== in
.length () - 1)
3022 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3023 unshare_expr (red
), close_phi
);
3024 insert_out_of_ssa_copy_on_edge
3025 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3026 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3029 remove_phi (loop_phi
);
3030 remove_phi (close_phi
);
3034 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3035 true when something has been changed. */
3038 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3042 auto_vec
<gimple
*, 10> in
;
3043 auto_vec
<gimple
*, 10> out
;
3045 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3046 res
= in
.length () > 1;
3048 translate_scalar_reduction_to_array (scop
, in
, out
);
3053 /* Rewrites all the commutative reductions from LOOP out of SSA.
3054 Returns true when something has been changed. */
3057 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3061 edge exit
= single_exit (loop
);
3063 bool changed
= false;
3068 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3069 if ((res
= gimple_phi_result (gsi
.phi ()))
3070 && !virtual_operand_p (res
)
3071 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3072 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3078 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3081 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3084 bool changed
= false;
3085 sese region
= SCOP_REGION (scop
);
3087 FOR_EACH_LOOP (loop
, 0)
3088 if (loop_in_sese_p (loop
, region
))
3089 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3094 gsi_commit_edge_inserts ();
3095 update_ssa (TODO_update_ssa
);
3096 #ifdef ENABLE_CHECKING
3097 verify_loop_closed_ssa (true);
3102 /* Can all ivs be represented by a signed integer?
3103 As ISL might generate negative values in its expressions, signed loop ivs
3104 are required in the backend. */
3107 scop_ivs_can_be_represented (scop_p scop
)
3113 FOR_EACH_LOOP (loop
, 0)
3115 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3118 for (psi
= gsi_start_phis (loop
->header
);
3119 !gsi_end_p (psi
); gsi_next (&psi
))
3121 gphi
*phi
= psi
.phi ();
3122 tree res
= PHI_RESULT (phi
);
3123 tree type
= TREE_TYPE (res
);
3125 if (TYPE_UNSIGNED (type
)
3126 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3139 /* Builds the polyhedral representation for a SESE region. */
3142 build_poly_scop (scop_p scop
)
3144 sese region
= SCOP_REGION (scop
);
3145 graphite_dim_t max_dim
;
3147 build_scop_bbs (scop
);
3149 /* Do not optimize a scop containing only PBBs that do not belong
3151 if (nb_pbbs_in_loops (scop
) == 0)
3154 if (!scop_ivs_can_be_represented (scop
))
3157 rewrite_commutative_reductions_out_of_ssa (scop
);
3159 build_sese_loop_nests (region
);
3160 /* Record all conditions in REGION. */
3161 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3162 find_scop_parameters (scop
);
3164 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3165 if (scop_nb_params (scop
) > max_dim
)
3168 build_scop_iteration_domain (scop
);
3169 build_scop_context (scop
);
3170 add_conditions_to_constraints (scop
);
3172 /* Rewrite out of SSA only after having translated the
3173 representation to the polyhedral representation to avoid scev
3174 analysis failures. That means that these functions will insert
3175 new data references that they create in the right place. */
3176 rewrite_reductions_out_of_ssa (scop
);
3177 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3179 build_scop_drs (scop
);
3180 build_scop_scattering (scop
);
3182 /* This SCoP has been translated to the polyhedral
3184 POLY_SCOP_P (scop
) = true;
3186 #endif /* HAVE_isl */