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 i
= parameter_index_in_region_1 (name
, region
);
765 gcc_assert (SESE_ADD_PARAMS (region
));
767 i
= SESE_PARAMS (region
).length ();
768 SESE_PARAMS (region
).safe_push (name
);
772 /* Extract an affine expression from the tree E in the scop S. */
775 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
777 isl_pw_aff
*lhs
, *rhs
, *res
;
780 if (e
== chrec_dont_know
) {
781 isl_space_free (space
);
785 switch (TREE_CODE (e
))
787 case POLYNOMIAL_CHREC
:
788 res
= extract_affine_chrec (s
, e
, space
);
792 res
= extract_affine_mul (s
, e
, space
);
796 case POINTER_PLUS_EXPR
:
797 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
798 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
799 res
= isl_pw_aff_add (lhs
, rhs
);
803 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
804 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
805 res
= isl_pw_aff_sub (lhs
, rhs
);
810 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
811 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
812 res
= isl_pw_aff_mul (lhs
, rhs
);
816 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
817 res
= extract_affine_name (s
, e
, space
);
821 res
= extract_affine_int (e
, space
);
822 /* No need to wrap a single integer. */
826 case NON_LVALUE_EXPR
:
827 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
835 type
= TREE_TYPE (e
);
836 if (TYPE_UNSIGNED (type
))
837 res
= wrap (res
, TYPE_PRECISION (type
));
842 /* In the context of sese S, scan the expression E and translate it to
843 a linear expression C. When parsing a symbolic multiplication, K
844 represents the constant multiplier of an expression containing
848 scan_tree_for_params (sese s
, tree e
)
850 if (e
== chrec_dont_know
)
853 switch (TREE_CODE (e
))
855 case POLYNOMIAL_CHREC
:
856 scan_tree_for_params (s
, CHREC_LEFT (e
));
860 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
861 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
863 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
867 case POINTER_PLUS_EXPR
:
869 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
870 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
876 case NON_LVALUE_EXPR
:
877 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
881 parameter_index_in_region (e
, s
);
897 /* Find parameters with respect to REGION in BB. We are looking in memory
898 access functions, conditions and loop bounds. */
901 find_params_in_bb (sese region
, gimple_bb_p gbb
)
907 loop_p loop
= GBB_BB (gbb
)->loop_father
;
909 /* Find parameters in the access functions of data references. */
910 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
911 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
912 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
914 /* Find parameters in conditional statements. */
915 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
917 tree lhs
= scalar_evolution_in_region (region
, loop
,
918 gimple_cond_lhs (stmt
));
919 tree rhs
= scalar_evolution_in_region (region
, loop
,
920 gimple_cond_rhs (stmt
));
922 scan_tree_for_params (region
, lhs
);
923 scan_tree_for_params (region
, rhs
);
927 /* Record the parameters used in the SCOP. A variable is a parameter
928 in a scop if it does not vary during the execution of that scop. */
931 find_scop_parameters (scop_p scop
)
935 sese region
= SCOP_REGION (scop
);
939 /* Find the parameters used in the loop bounds. */
940 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
942 tree nb_iters
= number_of_latch_executions (loop
);
944 if (!chrec_contains_symbols (nb_iters
))
947 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
948 scan_tree_for_params (region
, nb_iters
);
951 /* Find the parameters used in data accesses. */
952 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
953 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
955 nbp
= sese_nb_params (region
);
956 scop_set_nb_params (scop
, nbp
);
957 SESE_ADD_PARAMS (region
) = false;
961 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
963 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
964 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
965 isl_id_for_ssa_name (scop
, e
));
967 scop
->context
= isl_set_universe (space
);
971 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
972 the constraints for the surrounding loops. */
975 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
977 isl_set
*outer
, isl_set
**doms
)
979 tree nb_iters
= number_of_latch_executions (loop
);
980 sese region
= SCOP_REGION (scop
);
982 isl_set
*inner
= isl_set_copy (outer
);
985 int pos
= isl_set_dim (outer
, isl_dim_set
);
991 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
992 space
= isl_set_get_space (inner
);
995 c
= isl_inequality_alloc
996 (isl_local_space_from_space (isl_space_copy (space
)));
997 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
998 inner
= isl_set_add_constraint (inner
, c
);
1000 /* loop_i <= cst_nb_iters */
1001 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1003 c
= isl_inequality_alloc
1004 (isl_local_space_from_space (isl_space_copy (space
)));
1005 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1006 tree_int_to_gmp (nb_iters
, g
);
1007 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1008 c
= isl_constraint_set_constant_val (c
, v
);
1009 inner
= isl_set_add_constraint (inner
, c
);
1012 /* loop_i <= expr_nb_iters */
1013 else if (!chrec_contains_undetermined (nb_iters
))
1018 isl_local_space
*ls
;
1022 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1024 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1025 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1026 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1027 isl_set_dim (valid
, isl_dim_set
));
1028 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1030 ls
= isl_local_space_from_space (isl_space_copy (space
));
1031 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1032 isl_dim_in
, pos
, 1);
1033 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1034 isl_pw_aff_copy (aff
));
1035 inner
= isl_set_intersect (inner
, le
);
1037 if (max_stmt_executions (loop
, &nit
))
1039 /* Insert in the context the constraints from the
1040 estimation of the number of iterations NIT and the
1041 symbolic number of iterations (involving parameter
1042 names) NB_ITERS. First, build the affine expression
1043 "NIT - NB_ITERS" and then say that it is positive,
1044 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1051 wi::to_mpz (nit
, g
, SIGNED
);
1052 mpz_sub_ui (g
, g
, 1);
1053 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1054 x
= isl_pw_aff_ge_set (approx
, aff
);
1055 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1056 isl_set_dim (x
, isl_dim_set
));
1057 scop
->context
= isl_set_intersect (scop
->context
, x
);
1059 c
= isl_inequality_alloc
1060 (isl_local_space_from_space (isl_space_copy (space
)));
1061 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1062 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1064 c
= isl_constraint_set_constant_val (c
, v
);
1065 inner
= isl_set_add_constraint (inner
, c
);
1068 isl_pw_aff_free (aff
);
1073 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1074 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1075 isl_set_copy (inner
), doms
);
1079 && loop_in_sese_p (loop
->next
, region
))
1080 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1081 isl_set_copy (outer
), doms
);
1083 doms
[loop
->num
] = inner
;
1085 isl_set_free (outer
);
1086 isl_space_free (space
);
1090 /* Returns a linear expression for tree T evaluated in PBB. */
1093 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1095 scop_p scop
= PBB_SCOP (pbb
);
1097 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1098 gcc_assert (!automatically_generated_chrec_p (t
));
1100 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1103 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1104 operator. This allows us to invert the condition or to handle
1108 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1110 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1111 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1117 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1121 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1125 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1133 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1137 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1141 isl_pw_aff_free (lhs
);
1142 isl_pw_aff_free (rhs
);
1146 cond
= isl_set_coalesce (cond
);
1147 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1148 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1151 /* Add conditions to the domain of PBB. */
1154 add_conditions_to_domain (poly_bb_p pbb
)
1158 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1160 if (GBB_CONDITIONS (gbb
).is_empty ())
1163 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1164 switch (gimple_code (stmt
))
1168 /* Don't constrain on anything else than INTEGER_TYPE. */
1169 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1172 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1173 enum tree_code code
= gimple_cond_code (cond_stmt
);
1175 /* The conditions for ELSE-branches are inverted. */
1176 if (!GBB_CONDITION_CASES (gbb
)[i
])
1177 code
= invert_tree_comparison (code
, false);
1179 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1184 /* Switch statements are not supported right now - fall through. */
1192 /* Traverses all the GBBs of the SCOP and add their constraints to the
1193 iteration domains. */
1196 add_conditions_to_constraints (scop_p scop
)
1201 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1202 add_conditions_to_domain (pbb
);
1205 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1206 edge between BB and its predecessor is not a loop exit edge, and
1207 the last statement of the single predecessor is a COND_EXPR. */
1210 single_pred_cond_non_loop_exit (basic_block bb
)
1212 if (single_pred_p (bb
))
1214 edge e
= single_pred_edge (bb
);
1215 basic_block pred
= e
->src
;
1218 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1221 stmt
= last_stmt (pred
);
1223 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1224 return as_a
<gcond
*> (stmt
);
1230 class sese_dom_walker
: public dom_walker
1233 sese_dom_walker (cdi_direction
, sese
);
1235 virtual void before_dom_children (basic_block
);
1236 virtual void after_dom_children (basic_block
);
1239 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1243 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1244 : dom_walker (direction
), m_region (region
)
1248 /* Call-back for dom_walk executed before visiting the dominated
1252 sese_dom_walker::before_dom_children (basic_block bb
)
1257 if (!bb_in_sese_p (bb
, m_region
))
1260 stmt
= single_pred_cond_non_loop_exit (bb
);
1264 edge e
= single_pred_edge (bb
);
1266 m_conditions
.safe_push (stmt
);
1268 if (e
->flags
& EDGE_TRUE_VALUE
)
1269 m_cases
.safe_push (stmt
);
1271 m_cases
.safe_push (NULL
);
1274 gbb
= gbb_from_bb (bb
);
1278 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1279 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1283 /* Call-back for dom_walk executed after visiting the dominated
1287 sese_dom_walker::after_dom_children (basic_block bb
)
1289 if (!bb_in_sese_p (bb
, m_region
))
1292 if (single_pred_cond_non_loop_exit (bb
))
1294 m_conditions
.pop ();
1299 /* Add constraints on the possible values of parameter P from the type
1303 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1305 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1306 tree type
= TREE_TYPE (parameter
);
1307 tree lb
= NULL_TREE
;
1308 tree ub
= NULL_TREE
;
1310 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1311 lb
= lower_bound_in_type (type
, type
);
1313 lb
= TYPE_MIN_VALUE (type
);
1315 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1316 ub
= upper_bound_in_type (type
, type
);
1318 ub
= TYPE_MAX_VALUE (type
);
1322 isl_space
*space
= isl_set_get_space (scop
->context
);
1327 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1329 tree_int_to_gmp (lb
, g
);
1330 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1331 v
= isl_val_neg (v
);
1333 c
= isl_constraint_set_constant_val (c
, v
);
1334 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1336 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1341 isl_space
*space
= isl_set_get_space (scop
->context
);
1346 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1349 tree_int_to_gmp (ub
, g
);
1350 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1352 c
= isl_constraint_set_constant_val (c
, v
);
1353 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1355 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1359 /* Build the context of the SCOP. The context usually contains extra
1360 constraints that are added to the iteration domains that constrain
1364 build_scop_context (scop_p scop
)
1366 graphite_dim_t p
, n
= scop_nb_params (scop
);
1368 for (p
= 0; p
< n
; p
++)
1369 add_param_constraints (scop
, p
);
1372 /* Build the iteration domains: the loops belonging to the current
1373 SCOP, and that vary for the execution of the current basic block.
1374 Returns false if there is no loop in SCOP. */
1377 build_scop_iteration_domain (scop_p scop
)
1380 sese region
= SCOP_REGION (scop
);
1383 int nb_loops
= number_of_loops (cfun
);
1384 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1386 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1387 if (!loop_in_sese_p (loop_outer (loop
), region
))
1388 build_loop_iteration_domains (scop
, loop
, 0,
1389 isl_set_copy (scop
->context
), doms
);
1391 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1393 loop
= pbb_loop (pbb
);
1395 if (doms
[loop
->num
])
1396 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1398 pbb
->domain
= isl_set_copy (scop
->context
);
1400 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1401 isl_id_for_pbb (scop
, pbb
));
1404 for (i
= 0; i
< nb_loops
; i
++)
1406 isl_set_free (doms
[i
]);
1411 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1412 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1413 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1417 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1420 int alias_set_num
= 0;
1421 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1423 if (bap
&& bap
->alias_set
)
1424 alias_set_num
= *(bap
->alias_set
);
1426 c
= isl_equality_alloc
1427 (isl_local_space_from_space (isl_map_get_space (acc
)));
1428 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1429 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1431 return isl_map_add_constraint (acc
, c
);
1434 /* Assign the affine expression INDEX to the output dimension POS of
1435 MAP and return the result. */
1438 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1441 int len
= isl_map_dim (map
, isl_dim_out
);
1444 index_map
= isl_map_from_pw_aff (index
);
1445 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1446 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1448 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1449 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1450 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1451 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1453 return isl_map_intersect (map
, index_map
);
1456 /* Add to ACCESSES polyhedron equalities defining the access functions
1457 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1458 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1459 PBB is the poly_bb_p that contains the data reference DR. */
1462 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1464 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1465 scop_p scop
= PBB_SCOP (pbb
);
1467 for (i
= 0; i
< nb_subscripts
; i
++)
1470 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1472 aff
= extract_affine (scop
, afn
,
1473 isl_space_domain (isl_map_get_space (acc
)));
1474 acc
= set_index (acc
, i
+ 1, aff
);
1480 /* Add constrains representing the size of the accessed data to the
1481 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1482 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1486 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1487 data_reference_p dr
)
1489 tree ref
= DR_REF (dr
);
1491 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1492 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1494 if (TREE_CODE (ref
) != ARRAY_REF
)
1495 return subscript_sizes
;
1497 tree low
= array_ref_low_bound (ref
);
1498 tree high
= array_ref_up_bound (ref
);
1500 /* XXX The PPL code dealt separately with
1501 subscript - low >= 0 and high - subscript >= 0 in case one of
1502 the two bounds isn't known. Do the same here? */
1504 if (tree_fits_shwi_p (low
)
1506 && tree_fits_shwi_p (high
)
1507 /* 1-element arrays at end of structures may extend over
1508 their declared size. */
1509 && !(array_at_struct_end_p (ref
)
1510 && operand_equal_p (low
, high
, 0)))
1514 isl_set
*univ
, *lbs
, *ubs
;
1517 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1518 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1519 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1522 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1523 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1524 isl_set_dim (valid
, isl_dim_set
));
1525 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1527 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1528 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1529 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1530 index
= isl_pw_aff_alloc (univ
, aff
);
1532 id
= isl_set_get_tuple_id (subscript_sizes
);
1533 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1534 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1536 /* low <= sub_i <= high */
1537 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1538 ubs
= isl_pw_aff_le_set (index
, ub
);
1539 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1540 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1544 return subscript_sizes
;
1547 /* Build data accesses for DR in PBB. */
1550 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1552 int dr_base_object_set
;
1554 isl_set
*subscript_sizes
;
1555 scop_p scop
= PBB_SCOP (pbb
);
1558 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1559 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1560 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1561 isl_dim_out
, nb_out
);
1563 acc
= isl_map_universe (space
);
1564 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1567 acc
= pdr_add_alias_set (acc
, dr
);
1568 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1571 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1572 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1573 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1574 int alias_set_num
= 0;
1575 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1577 if (bap
&& bap
->alias_set
)
1578 alias_set_num
= *(bap
->alias_set
);
1580 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1581 subscript_sizes
= isl_set_nat_universe (space
);
1582 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1584 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1587 gcc_assert (dr
->aux
);
1588 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1590 new_poly_dr (pbb
, dr_base_object_set
,
1591 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1592 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1595 /* Write to FILE the alias graph of data references in DIMACS format. */
1598 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1599 vec
<data_reference_p
> drs
)
1601 int num_vertex
= drs
.length ();
1603 data_reference_p dr1
, dr2
;
1606 if (num_vertex
== 0)
1609 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1610 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1611 if (dr_may_alias_p (dr1
, dr2
, true))
1614 fprintf (file
, "$\n");
1617 fprintf (file
, "c %s\n", comment
);
1619 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1621 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1622 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1623 if (dr_may_alias_p (dr1
, dr2
, true))
1624 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1629 /* Write to FILE the alias graph of data references in DOT format. */
1632 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1633 vec
<data_reference_p
> drs
)
1635 int num_vertex
= drs
.length ();
1636 data_reference_p dr1
, dr2
;
1639 if (num_vertex
== 0)
1642 fprintf (file
, "$\n");
1645 fprintf (file
, "c %s\n", comment
);
1647 /* First print all the vertices. */
1648 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1649 fprintf (file
, "n%d;\n", i
);
1651 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1652 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1653 if (dr_may_alias_p (dr1
, dr2
, true))
1654 fprintf (file
, "n%d n%d\n", i
, j
);
1659 /* Write to FILE the alias graph of data references in ECC format. */
1662 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1663 vec
<data_reference_p
> drs
)
1665 int num_vertex
= drs
.length ();
1666 data_reference_p dr1
, dr2
;
1669 if (num_vertex
== 0)
1672 fprintf (file
, "$\n");
1675 fprintf (file
, "c %s\n", comment
);
1677 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1678 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1679 if (dr_may_alias_p (dr1
, dr2
, true))
1680 fprintf (file
, "%d %d\n", i
, j
);
1685 /* Check if DR1 and DR2 are in the same object set. */
1688 dr_same_base_object_p (const struct data_reference
*dr1
,
1689 const struct data_reference
*dr2
)
1691 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1694 /* Uses DFS component number as representative of alias-sets. Also tests for
1695 optimality by verifying if every connected component is a clique. Returns
1696 true (1) if the above test is true, and false (0) otherwise. */
1699 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1701 int num_vertices
= drs
.length ();
1702 struct graph
*g
= new_graph (num_vertices
);
1703 data_reference_p dr1
, dr2
;
1705 int num_connected_components
;
1706 int v_indx1
, v_indx2
, num_vertices_in_component
;
1709 struct graph_edge
*e
;
1710 int this_component_is_clique
;
1711 int all_components_are_cliques
= 1;
1713 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1714 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1715 if (dr_may_alias_p (dr1
, dr2
, true))
1721 all_vertices
= XNEWVEC (int, num_vertices
);
1722 vertices
= XNEWVEC (int, num_vertices
);
1723 for (i
= 0; i
< num_vertices
; i
++)
1724 all_vertices
[i
] = i
;
1726 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1728 for (i
= 0; i
< g
->n_vertices
; i
++)
1730 data_reference_p dr
= drs
[i
];
1731 base_alias_pair
*bap
;
1733 gcc_assert (dr
->aux
);
1734 bap
= (base_alias_pair
*)(dr
->aux
);
1736 bap
->alias_set
= XNEW (int);
1737 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1740 /* Verify if the DFS numbering results in optimal solution. */
1741 for (i
= 0; i
< num_connected_components
; i
++)
1743 num_vertices_in_component
= 0;
1744 /* Get all vertices whose DFS component number is the same as i. */
1745 for (j
= 0; j
< num_vertices
; j
++)
1746 if (g
->vertices
[j
].component
== i
)
1747 vertices
[num_vertices_in_component
++] = j
;
1749 /* Now test if the vertices in 'vertices' form a clique, by testing
1750 for edges among each pair. */
1751 this_component_is_clique
= 1;
1752 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1754 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1756 /* Check if the two vertices are connected by iterating
1757 through all the edges which have one of these are source. */
1758 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1761 if (e
->src
== vertices
[v_indx1
])
1767 this_component_is_clique
= 0;
1771 if (!this_component_is_clique
)
1772 all_components_are_cliques
= 0;
1776 free (all_vertices
);
1779 return all_components_are_cliques
;
1782 /* Group each data reference in DRS with its base object set num. */
1785 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1787 int num_vertex
= drs
.length ();
1788 struct graph
*g
= new_graph (num_vertex
);
1789 data_reference_p dr1
, dr2
;
1793 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1794 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1795 if (dr_same_base_object_p (dr1
, dr2
))
1801 queue
= XNEWVEC (int, num_vertex
);
1802 for (i
= 0; i
< num_vertex
; i
++)
1805 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1807 for (i
= 0; i
< g
->n_vertices
; i
++)
1809 data_reference_p dr
= drs
[i
];
1810 base_alias_pair
*bap
;
1812 gcc_assert (dr
->aux
);
1813 bap
= (base_alias_pair
*)(dr
->aux
);
1815 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1822 /* Build the data references for PBB. */
1825 build_pbb_drs (poly_bb_p pbb
)
1828 data_reference_p dr
;
1829 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1831 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1832 build_poly_dr (dr
, pbb
);
1835 /* Dump to file the alias graphs for the data references in DRS. */
1838 dump_alias_graphs (vec
<data_reference_p
> drs
)
1841 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1843 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1846 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1847 current_function_name ());
1848 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1849 fclose (file_dimacs
);
1852 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1855 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1856 current_function_name ());
1857 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1861 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1864 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1865 current_function_name ());
1866 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1871 /* Build data references in SCOP. */
1874 build_scop_drs (scop_p scop
)
1878 data_reference_p dr
;
1879 auto_vec
<data_reference_p
, 3> drs
;
1881 /* Remove all the PBBs that do not have data references: these basic
1882 blocks are not handled in the polyhedral representation. */
1883 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1884 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1886 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1888 SCOP_BBS (scop
).ordered_remove (i
);
1892 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1893 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1896 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1897 dr
->aux
= XNEW (base_alias_pair
);
1899 if (!build_alias_set_optimal_p (drs
))
1901 /* TODO: Add support when building alias set is not optimal. */
1905 build_base_obj_set_for_drs (drs
);
1907 /* When debugging, enable the following code. This cannot be used
1908 in production compilers. */
1910 dump_alias_graphs (drs
);
1914 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1915 build_pbb_drs (pbb
);
1918 /* Return a gsi at the position of the phi node STMT. */
1920 static gphi_iterator
1921 gsi_for_phi_node (gphi
*stmt
)
1924 basic_block bb
= gimple_bb (stmt
);
1926 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1927 if (stmt
== psi
.phi ())
1934 /* Analyze all the data references of STMTS and add them to the
1935 GBB_DATA_REFS vector of BB. */
1938 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1944 sese region
= SCOP_REGION (scop
);
1946 if (!bb_in_sese_p (bb
, region
))
1949 nest
= outermost_loop_in_sese_1 (region
, bb
);
1950 gbb
= gbb_from_bb (bb
);
1952 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1956 if (is_gimple_debug (stmt
))
1959 loop
= loop_containing_stmt (stmt
);
1960 if (!loop_in_sese_p (loop
, region
))
1963 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1964 &GBB_DATA_REFS (gbb
));
1968 /* Insert STMT at the end of the STMTS sequence and then insert the
1969 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1973 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1974 gimple_stmt_iterator insert_gsi
)
1976 gimple_stmt_iterator gsi
;
1977 auto_vec
<gimple
*, 3> x
;
1979 gimple_seq_add_stmt (&stmts
, stmt
);
1980 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1981 x
.safe_push (gsi_stmt (gsi
));
1983 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1984 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1987 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1990 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1993 gimple_stmt_iterator gsi
;
1994 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1995 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1996 auto_vec
<gimple
*, 3> x
;
1998 gimple_seq_add_stmt (&stmts
, stmt
);
1999 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2000 x
.safe_push (gsi_stmt (gsi
));
2002 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2004 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2005 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2009 gsi
= gsi_for_stmt (after_stmt
);
2010 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2013 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2016 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2019 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2021 vec
<data_reference_p
> drs
;
2023 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2024 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2025 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2026 int index
, n
= SCOP_BBS (scop
).length ();
2028 /* The INDEX of PBB in SCOP_BBS. */
2029 for (index
= 0; index
< n
; index
++)
2030 if (SCOP_BBS (scop
)[index
] == pbb
)
2033 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2034 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2035 isl_id_for_pbb (scop
, pbb1
));
2037 GBB_PBB (gbb1
) = pbb1
;
2038 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2039 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2040 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2043 /* Insert on edge E the assignment "RES := EXPR". */
2046 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2048 gimple_stmt_iterator gsi
;
2049 gimple_seq stmts
= NULL
;
2050 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2051 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2053 auto_vec
<gimple
*, 3> x
;
2055 gimple_seq_add_stmt (&stmts
, stmt
);
2056 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2057 x
.safe_push (gsi_stmt (gsi
));
2059 gsi_insert_seq_on_edge (e
, stmts
);
2060 gsi_commit_edge_inserts ();
2061 bb
= gimple_bb (stmt
);
2063 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2066 if (!gbb_from_bb (bb
))
2067 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2069 analyze_drs_in_stmts (scop
, bb
, x
);
2072 /* Creates a zero dimension array of the same type as VAR. */
2075 create_zero_dim_array (tree var
, const char *base_name
)
2077 tree index_type
= build_index_type (integer_zero_node
);
2078 tree elt_type
= TREE_TYPE (var
);
2079 tree array_type
= build_array_type (elt_type
, index_type
);
2080 tree base
= create_tmp_var (array_type
, base_name
);
2082 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2086 /* Returns true when PHI is a loop close phi node. */
2089 scalar_close_phi_node_p (gimple
*phi
)
2091 if (gimple_code (phi
) != GIMPLE_PHI
2092 || virtual_operand_p (gimple_phi_result (phi
)))
2095 /* Note that loop close phi nodes should have a single argument
2096 because we translated the representation into a canonical form
2097 before Graphite: see canonicalize_loop_closed_ssa_form. */
2098 return (gimple_phi_num_args (phi
) == 1);
2101 /* For a definition DEF in REGION, propagates the expression EXPR in
2102 all the uses of DEF outside REGION. */
2105 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2107 imm_use_iterator imm_iter
;
2110 bool replaced_once
= false;
2112 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2114 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2117 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2118 if (!is_gimple_debug (use_stmt
)
2119 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2122 use_operand_p use_p
;
2124 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2125 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2126 && (replaced_once
= true))
2127 replace_exp (use_p
, expr
);
2129 update_stmt (use_stmt
);
2134 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2135 gsi_commit_edge_inserts ();
2139 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2140 dimension array for it. */
2143 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2145 sese region
= SCOP_REGION (scop
);
2146 gimple
*phi
= gsi_stmt (*psi
);
2147 tree res
= gimple_phi_result (phi
);
2148 basic_block bb
= gimple_bb (phi
);
2149 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2150 tree arg
= gimple_phi_arg_def (phi
, 0);
2153 /* Note that loop close phi nodes should have a single argument
2154 because we translated the representation into a canonical form
2155 before Graphite: see canonicalize_loop_closed_ssa_form. */
2156 gcc_assert (gimple_phi_num_args (phi
) == 1);
2158 /* The phi node can be a non close phi node, when its argument is
2159 invariant, or a default definition. */
2160 if (is_gimple_min_invariant (arg
)
2161 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2163 propagate_expr_outside_region (res
, arg
, region
);
2168 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2170 propagate_expr_outside_region (res
, arg
, region
);
2171 stmt
= gimple_build_assign (res
, arg
);
2172 remove_phi_node (psi
, false);
2173 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2177 /* If res is scev analyzable and is not a scalar value, it is safe
2178 to ignore the close phi node: it will be code generated in the
2179 out of Graphite pass. */
2180 else if (scev_analyzable_p (res
, region
))
2182 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2185 if (!loop_in_sese_p (loop
, region
))
2187 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2188 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2189 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2192 scev
= scalar_evolution_in_region (region
, loop
, res
);
2194 if (tree_does_not_contain_chrecs (scev
))
2195 propagate_expr_outside_region (res
, scev
, region
);
2202 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2204 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2206 if (TREE_CODE (arg
) == SSA_NAME
)
2207 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2208 SSA_NAME_DEF_STMT (arg
));
2210 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2211 zero_dim_array
, arg
);
2214 remove_phi_node (psi
, false);
2215 SSA_NAME_DEF_STMT (res
) = stmt
;
2217 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2220 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2221 dimension array for it. */
2224 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2227 gphi
*phi
= psi
->phi ();
2228 basic_block bb
= gimple_bb (phi
);
2229 tree res
= gimple_phi_result (phi
);
2230 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2233 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2235 tree arg
= gimple_phi_arg_def (phi
, i
);
2236 edge e
= gimple_phi_arg_edge (phi
, i
);
2238 /* Avoid the insertion of code in the loop latch to please the
2239 pattern matching of the vectorizer. */
2240 if (TREE_CODE (arg
) == SSA_NAME
2241 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2242 && e
->src
== bb
->loop_father
->latch
)
2243 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2244 SSA_NAME_DEF_STMT (arg
));
2246 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2249 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2250 remove_phi_node (psi
, false);
2251 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2254 /* Rewrite the degenerate phi node at position PSI from the degenerate
2255 form "x = phi (y, y, ..., y)" to "x = y". */
2258 rewrite_degenerate_phi (gphi_iterator
*psi
)
2262 gimple_stmt_iterator gsi
;
2263 gphi
*phi
= psi
->phi ();
2264 tree res
= gimple_phi_result (phi
);
2267 bb
= gimple_bb (phi
);
2268 rhs
= degenerate_phi_result (phi
);
2271 stmt
= gimple_build_assign (res
, rhs
);
2272 remove_phi_node (psi
, false);
2274 gsi
= gsi_after_labels (bb
);
2275 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2278 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2281 rewrite_reductions_out_of_ssa (scop_p scop
)
2285 sese region
= SCOP_REGION (scop
);
2287 FOR_EACH_BB_FN (bb
, cfun
)
2288 if (bb_in_sese_p (bb
, region
))
2289 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2291 gphi
*phi
= psi
.phi ();
2293 if (virtual_operand_p (gimple_phi_result (phi
)))
2299 if (gimple_phi_num_args (phi
) > 1
2300 && degenerate_phi_result (phi
))
2301 rewrite_degenerate_phi (&psi
);
2303 else if (scalar_close_phi_node_p (phi
))
2304 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2306 else if (reduction_phi_p (region
, &psi
))
2307 rewrite_phi_out_of_ssa (scop
, &psi
);
2310 update_ssa (TODO_update_ssa
);
2311 #ifdef ENABLE_CHECKING
2312 verify_loop_closed_ssa (true);
2316 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2317 read from ZERO_DIM_ARRAY. */
2320 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2321 tree def
, gimple
*use_stmt
)
2326 use_operand_p use_p
;
2328 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2330 name
= copy_ssa_name (def
);
2331 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2333 gimple_assign_set_lhs (name_stmt
, name
);
2334 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2336 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2337 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2338 replace_exp (use_p
, name
);
2340 update_stmt (use_stmt
);
2343 /* For every definition DEF in the SCOP that is used outside the scop,
2344 insert a closing-scop definition in the basic block just after this
2348 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
2350 tree var
= create_tmp_reg (TREE_TYPE (def
));
2351 tree new_name
= make_ssa_name (var
, stmt
);
2352 bool needs_copy
= false;
2353 use_operand_p use_p
;
2354 imm_use_iterator imm_iter
;
2356 sese region
= SCOP_REGION (scop
);
2358 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2360 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2362 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2364 SET_USE (use_p
, new_name
);
2366 update_stmt (use_stmt
);
2371 /* Insert in the empty BB just after the scop a use of DEF such
2372 that the rewrite of cross_bb_scalar_dependences won't insert
2373 arrays everywhere else. */
2376 gimple
*assign
= gimple_build_assign (new_name
, def
);
2377 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2379 update_stmt (assign
);
2380 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2384 /* Rewrite the scalar dependences crossing the boundary of the BB
2385 containing STMT with an array. Return true when something has been
2389 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2391 sese region
= SCOP_REGION (scop
);
2392 gimple
*stmt
= gsi_stmt (*gsi
);
2393 imm_use_iterator imm_iter
;
2396 tree zero_dim_array
= NULL_TREE
;
2400 switch (gimple_code (stmt
))
2403 def
= gimple_assign_lhs (stmt
);
2407 def
= gimple_call_lhs (stmt
);
2415 || !is_gimple_reg (def
))
2418 if (scev_analyzable_p (def
, region
))
2420 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2421 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2423 if (tree_contains_chrecs (scev
, NULL
))
2426 propagate_expr_outside_region (def
, scev
, region
);
2430 def_bb
= gimple_bb (stmt
);
2432 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2434 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2435 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2438 gphi_iterator psi
= gsi_for_phi (phi
);
2440 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2441 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2443 rewrite_phi_out_of_ssa (scop
, &psi
);
2446 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2447 if (gimple_code (use_stmt
) != GIMPLE_PHI
2448 && def_bb
!= gimple_bb (use_stmt
)
2449 && !is_gimple_debug (use_stmt
)
2452 if (!zero_dim_array
)
2454 zero_dim_array
= create_zero_dim_array
2455 (def
, "Cross_BB_scalar_dependence");
2456 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2457 SSA_NAME_DEF_STMT (def
));
2461 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2468 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2471 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2474 gimple_stmt_iterator psi
;
2475 sese region
= SCOP_REGION (scop
);
2476 bool changed
= false;
2478 /* Create an extra empty BB after the scop. */
2479 split_edge (SESE_EXIT (region
));
2481 FOR_EACH_BB_FN (bb
, cfun
)
2482 if (bb_in_sese_p (bb
, region
))
2483 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2484 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2489 update_ssa (TODO_update_ssa
);
2490 #ifdef ENABLE_CHECKING
2491 verify_loop_closed_ssa (true);
2496 /* Returns the number of pbbs that are in loops contained in SCOP. */
2499 nb_pbbs_in_loops (scop_p scop
)
2505 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2506 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2512 /* Return the number of data references in BB that write in
2516 nb_data_writes_in_bb (basic_block bb
)
2519 gimple_stmt_iterator gsi
;
2521 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2522 if (gimple_vdef (gsi_stmt (gsi
)))
2528 /* Splits at STMT the basic block BB represented as PBB in the
2532 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple
*stmt
)
2534 edge e1
= split_block (bb
, stmt
);
2535 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2539 /* Splits STMT out of its current BB. This is done for reduction
2540 statements for which we want to ignore data dependences. */
2543 split_reduction_stmt (scop_p scop
, gimple
*stmt
)
2545 basic_block bb
= gimple_bb (stmt
);
2546 poly_bb_p pbb
= pbb_from_bb (bb
);
2547 gimple_bb_p gbb
= gbb_from_bb (bb
);
2550 data_reference_p dr
;
2552 /* Do not split basic blocks with no writes to memory: the reduction
2553 will be the only write to memory. */
2554 if (nb_data_writes_in_bb (bb
) == 0
2555 /* Or if we have already marked BB as a reduction. */
2556 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2559 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2561 /* Split once more only when the reduction stmt is not the only one
2562 left in the original BB. */
2563 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2565 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2567 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2570 /* A part of the data references will end in a different basic block
2571 after the split: move the DRs from the original GBB to the newly
2573 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2575 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2579 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2580 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2581 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2589 /* Return true when stmt is a reduction operation. */
2592 is_reduction_operation_p (gimple
*stmt
)
2594 enum tree_code code
;
2596 gcc_assert (is_gimple_assign (stmt
));
2597 code
= gimple_assign_rhs_code (stmt
);
2599 if (!commutative_tree_code (code
)
2600 || !associative_tree_code (code
))
2603 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2605 if (FLOAT_TYPE_P (type
))
2606 return flag_associative_math
;
2608 if (ANY_INTEGRAL_TYPE_P (type
))
2609 return (TYPE_OVERFLOW_WRAPS (type
)
2610 || !operation_can_overflow (code
));
2615 /* Returns true when PHI contains an argument ARG. */
2618 phi_contains_arg (gphi
*phi
, tree arg
)
2622 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2623 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2629 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2632 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2636 if (TREE_CODE (arg
) != SSA_NAME
)
2639 stmt
= SSA_NAME_DEF_STMT (arg
);
2641 if (gimple_code (stmt
) == GIMPLE_NOP
2642 || gimple_code (stmt
) == GIMPLE_CALL
)
2645 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2647 if (phi_contains_arg (phi
, lhs
))
2652 if (!is_gimple_assign (stmt
))
2655 if (gimple_num_ops (stmt
) == 2)
2656 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2658 if (is_reduction_operation_p (stmt
))
2661 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2664 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2670 /* Detect commutative and associative scalar reductions starting at
2671 the STMT. Return the phi node of the reduction cycle, or NULL. */
2674 detect_commutative_reduction_arg (tree lhs
, gimple
*stmt
, tree arg
,
2678 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2683 in
->safe_push (stmt
);
2684 out
->safe_push (stmt
);
2688 /* Detect commutative and associative scalar reductions starting at
2689 STMT. Return the phi node of the reduction cycle, or NULL. */
2692 detect_commutative_reduction_assign (gimple
*stmt
, vec
<gimple
*> *in
,
2695 tree lhs
= gimple_assign_lhs (stmt
);
2697 if (gimple_num_ops (stmt
) == 2)
2698 return detect_commutative_reduction_arg (lhs
, stmt
,
2699 gimple_assign_rhs1 (stmt
),
2702 if (is_reduction_operation_p (stmt
))
2704 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2705 gimple_assign_rhs1 (stmt
),
2708 : detect_commutative_reduction_arg (lhs
, stmt
,
2709 gimple_assign_rhs2 (stmt
),
2716 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2719 follow_inital_value_to_phi (tree arg
, tree lhs
)
2723 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2726 stmt
= SSA_NAME_DEF_STMT (arg
);
2728 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2729 if (phi_contains_arg (phi
, lhs
))
2736 /* Return the argument of the loop PHI that is the initial value coming
2737 from outside the loop. */
2740 edge_initial_value_for_loop_phi (gphi
*phi
)
2744 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2746 edge e
= gimple_phi_arg_edge (phi
, i
);
2748 if (loop_depth (e
->src
->loop_father
)
2749 < loop_depth (e
->dest
->loop_father
))
2756 /* Return the argument of the loop PHI that is the initial value coming
2757 from outside the loop. */
2760 initial_value_for_loop_phi (gphi
*phi
)
2764 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2766 edge e
= gimple_phi_arg_edge (phi
, i
);
2768 if (loop_depth (e
->src
->loop_father
)
2769 < loop_depth (e
->dest
->loop_father
))
2770 return gimple_phi_arg_def (phi
, i
);
2776 /* Returns true when DEF is used outside the reduction cycle of
2780 used_outside_reduction (tree def
, gimple
*loop_phi
)
2782 use_operand_p use_p
;
2783 imm_use_iterator imm_iter
;
2784 loop_p loop
= loop_containing_stmt (loop_phi
);
2786 /* In LOOP, DEF should be used only in LOOP_PHI. */
2787 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2789 gimple
*stmt
= USE_STMT (use_p
);
2791 if (stmt
!= loop_phi
2792 && !is_gimple_debug (stmt
)
2793 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2800 /* Detect commutative and associative scalar reductions belonging to
2801 the SCOP starting at the loop closed phi node STMT. Return the phi
2802 node of the reduction cycle, or NULL. */
2805 detect_commutative_reduction (scop_p scop
, gimple
*stmt
, vec
<gimple
*> *in
,
2808 if (scalar_close_phi_node_p (stmt
))
2811 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2812 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2814 if (TREE_CODE (arg
) != SSA_NAME
)
2817 /* Note that loop close phi nodes should have a single argument
2818 because we translated the representation into a canonical form
2819 before Graphite: see canonicalize_loop_closed_ssa_form. */
2820 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2822 def
= SSA_NAME_DEF_STMT (arg
);
2823 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2824 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2827 lhs
= gimple_phi_result (close_phi
);
2828 init
= initial_value_for_loop_phi (loop_phi
);
2829 phi
= follow_inital_value_to_phi (init
, lhs
);
2831 if (phi
&& (used_outside_reduction (lhs
, phi
)
2832 || !has_single_use (gimple_phi_result (phi
))))
2835 in
->safe_push (loop_phi
);
2836 out
->safe_push (close_phi
);
2840 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2841 return detect_commutative_reduction_assign (stmt
, in
, out
);
2846 /* Translate the scalar reduction statement STMT to an array RED
2847 knowing that its recursive phi node is LOOP_PHI. */
2850 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2851 gimple
*stmt
, gphi
*loop_phi
)
2853 tree res
= gimple_phi_result (loop_phi
);
2854 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2855 gimple_stmt_iterator gsi
;
2857 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2859 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2860 gsi
= gsi_for_stmt (stmt
);
2862 insert_stmts (scop
, assign
, NULL
, gsi
);
2865 /* Removes the PHI node and resets all the debug stmts that are using
2869 remove_phi (gphi
*phi
)
2871 imm_use_iterator imm_iter
;
2873 use_operand_p use_p
;
2874 gimple_stmt_iterator gsi
;
2875 auto_vec
<gimple
*, 3> update
;
2879 def
= PHI_RESULT (phi
);
2880 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2882 stmt
= USE_STMT (use_p
);
2884 if (is_gimple_debug (stmt
))
2886 gimple_debug_bind_reset_value (stmt
);
2887 update
.safe_push (stmt
);
2891 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2894 gsi
= gsi_for_phi_node (phi
);
2895 remove_phi_node (&gsi
, false);
2898 /* Helper function for for_each_index. For each INDEX of the data
2899 reference REF, returns true when its indices are valid in the loop
2900 nest LOOP passed in as DATA. */
2903 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2906 basic_block header
, def_bb
;
2909 if (TREE_CODE (*index
) != SSA_NAME
)
2912 loop
= *((loop_p
*) data
);
2913 header
= loop
->header
;
2914 stmt
= SSA_NAME_DEF_STMT (*index
);
2919 def_bb
= gimple_bb (stmt
);
2924 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2927 /* When the result of a CLOSE_PHI is written to a memory location,
2928 return a pointer to that memory reference, otherwise return
2932 close_phi_written_to_memory (gphi
*close_phi
)
2934 imm_use_iterator imm_iter
;
2935 use_operand_p use_p
;
2937 tree res
, def
= gimple_phi_result (close_phi
);
2939 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2940 if ((stmt
= USE_STMT (use_p
))
2941 && gimple_code (stmt
) == GIMPLE_ASSIGN
2942 && (res
= gimple_assign_lhs (stmt
)))
2944 switch (TREE_CODE (res
))
2954 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2955 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2957 /* FIXME: this restriction is for id-{24,25}.f and
2958 could be handled by duplicating the computation of
2959 array indices before the loop of the close_phi. */
2960 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2972 /* Rewrite out of SSA the reduction described by the loop phi nodes
2973 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2976 IN: stmt, loop_n, ..., loop_0
2977 OUT: stmt, close_n, ..., close_0
2979 the first element is the reduction statement, and the next elements
2980 are the loop and close phi nodes of each of the outer loops. */
2983 translate_scalar_reduction_to_array (scop_p scop
,
2988 unsigned int i
= out
.length () - 1;
2989 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
2991 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
2993 gimple
*close_stmt
= out
[i
];
2997 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
2998 poly_bb_p pbb
= pbb_from_bb (bb
);
2999 PBB_IS_REDUCTION (pbb
) = true;
3000 gcc_assert (close_stmt
== loop_stmt
);
3003 red
= create_zero_dim_array
3004 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3006 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3007 as_a
<gphi
*> (in
[1]));
3011 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3012 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3014 if (i
== in
.length () - 1)
3016 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3017 unshare_expr (red
), close_phi
);
3018 insert_out_of_ssa_copy_on_edge
3019 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3020 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3023 remove_phi (loop_phi
);
3024 remove_phi (close_phi
);
3028 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3029 true when something has been changed. */
3032 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3036 auto_vec
<gimple
*, 10> in
;
3037 auto_vec
<gimple
*, 10> out
;
3039 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3040 res
= in
.length () > 1;
3042 translate_scalar_reduction_to_array (scop
, in
, out
);
3047 /* Rewrites all the commutative reductions from LOOP out of SSA.
3048 Returns true when something has been changed. */
3051 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3055 edge exit
= single_exit (loop
);
3057 bool changed
= false;
3062 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3063 if ((res
= gimple_phi_result (gsi
.phi ()))
3064 && !virtual_operand_p (res
)
3065 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3066 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3072 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3075 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3078 bool changed
= false;
3079 sese region
= SCOP_REGION (scop
);
3081 FOR_EACH_LOOP (loop
, 0)
3082 if (loop_in_sese_p (loop
, region
))
3083 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3088 gsi_commit_edge_inserts ();
3089 update_ssa (TODO_update_ssa
);
3090 #ifdef ENABLE_CHECKING
3091 verify_loop_closed_ssa (true);
3096 /* Can all ivs be represented by a signed integer?
3097 As ISL might generate negative values in its expressions, signed loop ivs
3098 are required in the backend. */
3101 scop_ivs_can_be_represented (scop_p scop
)
3107 FOR_EACH_LOOP (loop
, 0)
3109 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3112 for (psi
= gsi_start_phis (loop
->header
);
3113 !gsi_end_p (psi
); gsi_next (&psi
))
3115 gphi
*phi
= psi
.phi ();
3116 tree res
= PHI_RESULT (phi
);
3117 tree type
= TREE_TYPE (res
);
3119 if (TYPE_UNSIGNED (type
)
3120 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3133 /* Builds the polyhedral representation for a SESE region. */
3136 build_poly_scop (scop_p scop
)
3138 sese region
= SCOP_REGION (scop
);
3139 graphite_dim_t max_dim
;
3141 build_scop_bbs (scop
);
3143 /* Do not optimize a scop containing only PBBs that do not belong
3145 if (nb_pbbs_in_loops (scop
) == 0)
3148 if (!scop_ivs_can_be_represented (scop
))
3151 rewrite_commutative_reductions_out_of_ssa (scop
);
3153 build_sese_loop_nests (region
);
3154 /* Record all conditions in REGION. */
3155 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3156 find_scop_parameters (scop
);
3158 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3159 if (scop_nb_params (scop
) > max_dim
)
3162 build_scop_iteration_domain (scop
);
3163 build_scop_context (scop
);
3164 add_conditions_to_constraints (scop
);
3166 /* Rewrite out of SSA only after having translated the
3167 representation to the polyhedral representation to avoid scev
3168 analysis failures. That means that these functions will insert
3169 new data references that they create in the right place. */
3170 rewrite_reductions_out_of_ssa (scop
);
3171 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3173 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 */