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. */
201 static gimple_poly_bb_p
202 new_gimple_poly_bb (basic_block bb
, vec
<data_reference_p
> drs
)
204 gimple_poly_bb_p gbb
;
206 gbb
= XNEW (struct gimple_poly_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
)
222 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
225 base_alias_pair_p bap
= (base_alias_pair_p
)(dr
->aux
);
227 free (bap
->alias_set
);
236 free_gimple_poly_bb (gimple_poly_bb_p 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_poly_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 /* Generates a polyhedral black box only if the bb contains interesting
280 static gimple_poly_bb_p
281 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
283 vec
<data_reference_p
> drs
;
285 sese region
= SCOP_REGION (scop
);
287 loop_p nest
= outermost_loop_in_sese (region
, bb
);
288 loop_p loop
= bb
->loop_father
;
289 if (!loop_in_sese_p (loop
, region
))
292 gimple_stmt_iterator gsi
;
293 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
295 gimple
*stmt
= gsi_stmt (gsi
);
296 if (is_gimple_debug (stmt
))
299 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
302 return new_gimple_poly_bb (bb
, drs
);
305 /* Returns true if all predecessors of BB, that are not dominated by BB, are
306 marked in MAP. The predecessors dominated by BB are loop latches and will
307 be handled after BB. */
310 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
315 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
316 if (!bitmap_bit_p (map
, e
->src
->index
)
317 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
323 /* Compare the depth of two basic_block's P1 and P2. */
326 compare_bb_depths (const void *p1
, const void *p2
)
328 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
329 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
330 int d1
= loop_depth (bb1
->loop_father
);
331 int d2
= loop_depth (bb2
->loop_father
);
342 /* Sort the basic blocks from DOM such that the first are the ones at
343 a deepest loop level. */
346 graphite_sort_dominated_info (vec
<basic_block
> dom
)
348 dom
.qsort (compare_bb_depths
);
351 /* Recursive helper function for build_scops_bbs. */
354 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
356 sese region
= SCOP_REGION (scop
);
357 vec
<basic_block
> dom
;
360 if (bitmap_bit_p (visited
, bb
->index
)
361 || !bb_in_sese_p (bb
, region
))
364 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
365 SCOP_BBS (scop
).safe_push (pbb
);
366 bitmap_set_bit (visited
, bb
->index
);
368 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
373 graphite_sort_dominated_info (dom
);
375 while (!dom
.is_empty ())
380 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
381 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
383 build_scop_bbs_1 (scop
, visited
, dom_bb
);
384 dom
.unordered_remove (i
);
392 /* Gather the basic blocks belonging to the SCOP. */
395 build_scop_bbs (scop_p scop
)
397 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
398 sese region
= SCOP_REGION (scop
);
400 bitmap_clear (visited
);
401 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
402 sbitmap_free (visited
);
405 /* Return an ISL identifier for the polyhedral basic block PBB. */
408 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
411 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
412 return isl_id_alloc (s
->ctx
, name
, pbb
);
415 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
416 We generate SCATTERING_DIMENSIONS scattering dimensions.
418 The scattering polyhedron consists of these dimensions: scattering,
419 loop_iterators, parameters.
423 | scattering_dimensions = 5
431 | Scattering polyhedron:
433 | scattering: {s1, s2, s3, s4, s5}
434 | loop_iterators: {i}
435 | parameters: {p1, p2}
437 | s1 s2 s3 s4 s5 i p1 p2 1
438 | 1 0 0 0 0 0 0 0 -4 = 0
439 | 0 1 0 0 0 -1 0 0 0 = 0
440 | 0 0 1 0 0 0 0 0 -5 = 0 */
443 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
450 int scattering_dimensions
= isl_set_dim (pbb
->domain
, isl_dim_set
) * 2 + 1;
452 dc
= isl_set_get_space (pbb
->domain
);
453 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
454 isl_dim_out
, scattering_dimensions
);
455 pbb
->schedule
= isl_map_universe (dm
);
457 for (i
= 0; i
< scattering_dimensions
; i
++)
459 /* Textual order inside this loop. */
462 isl_constraint
*c
= isl_equality_alloc
463 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
465 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
466 gcc_assert (val
&& isl_val_is_int (val
));
468 val
= isl_val_neg (val
);
469 c
= isl_constraint_set_constant_val (c
, val
);
470 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
471 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
474 /* Iterations of this loop. */
475 else /* if ((i % 2) == 1) */
477 int loop
= (i
- 1) / 2;
478 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
483 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
486 /* Build for BB the static schedule.
488 The static schedule is a Dewey numbering of the abstract syntax
489 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
491 The following example informally defines the static schedule:
510 Static schedules for A to F:
523 build_scop_scattering (scop_p scop
)
527 gimple_poly_bb_p previous_gbb
= NULL
;
528 isl_space
*dc
= isl_set_get_space (scop
->context
);
529 isl_aff
*static_sched
;
531 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
532 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
534 /* We have to start schedules at 0 on the first component and
535 because we cannot compare_prefix_loops against a previous loop,
536 prefix will be equal to zero, and that index will be
537 incremented before copying. */
538 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
540 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
542 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
546 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
552 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
554 build_pbb_scattering_polyhedrons (static_sched
, pbb
);
557 isl_aff_free (static_sched
);
560 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
562 /* Extract an affine expression from the chain of recurrence E. */
565 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
567 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
568 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
569 isl_local_space
*ls
= isl_local_space_from_space (space
);
570 unsigned pos
= sese_loop_depth (SCOP_REGION (s
), get_chrec_loop (e
)) - 1;
571 isl_aff
*loop
= isl_aff_set_coefficient_si
572 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
573 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
575 /* Before multiplying, make sure that the result is affine. */
576 gcc_assert (isl_pw_aff_is_cst (rhs
)
577 || isl_pw_aff_is_cst (l
));
579 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
582 /* Extract an affine expression from the mult_expr E. */
585 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
587 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
588 isl_space_copy (space
));
589 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
591 if (!isl_pw_aff_is_cst (lhs
)
592 && !isl_pw_aff_is_cst (rhs
))
594 isl_pw_aff_free (lhs
);
595 isl_pw_aff_free (rhs
);
599 return isl_pw_aff_mul (lhs
, rhs
);
602 /* Return an ISL identifier from the name of the ssa_name E. */
605 isl_id_for_ssa_name (scop_p s
, tree e
)
607 const char *name
= get_name (e
);
611 id
= isl_id_alloc (s
->ctx
, name
, e
);
615 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
616 id
= isl_id_alloc (s
->ctx
, name1
, e
);
622 /* Return an ISL identifier for the data reference DR. */
625 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
627 /* Data references all get the same isl_id. They need to be comparable
628 and are distinguished through the first dimension, which contains the
630 return isl_id_alloc (s
->ctx
, "", 0);
633 /* Extract an affine expression from the ssa_name E. */
636 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
643 id
= isl_id_for_ssa_name (s
, e
);
644 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
646 dom
= isl_set_universe (isl_space_copy (space
));
647 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
648 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
649 return isl_pw_aff_alloc (dom
, aff
);
652 /* Extract an affine expression from the gmp constant G. */
655 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
657 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
658 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
659 isl_set
*dom
= isl_set_universe (space
);
663 ct
= isl_aff_get_ctx (aff
);
664 v
= isl_val_int_from_gmp (ct
, g
);
665 aff
= isl_aff_add_constant_val (aff
, v
);
667 return isl_pw_aff_alloc (dom
, aff
);
670 /* Extract an affine expression from the integer_cst E. */
673 extract_affine_int (tree e
, __isl_take isl_space
*space
)
679 tree_int_to_gmp (e
, g
);
680 res
= extract_affine_gmp (g
, space
);
686 /* Compute pwaff mod 2^width. */
689 wrap (isl_pw_aff
*pwaff
, unsigned width
)
693 mod
= isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff
), width
);
694 mod
= isl_val_2exp (mod
);
695 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
700 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
701 Otherwise returns -1. */
704 parameter_index_in_region_1 (tree name
, sese region
)
709 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
711 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
718 /* When the parameter NAME is in REGION, returns its index in
719 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
720 and returns the index of NAME. */
723 parameter_index_in_region (tree name
, sese region
)
727 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
729 /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
730 if (TREE_CODE (TREE_TYPE (name
)) != INTEGER_TYPE
)
733 if (!invariant_in_sese_p_rec (name
, region
))
736 i
= parameter_index_in_region_1 (name
, region
);
740 gcc_assert (SESE_ADD_PARAMS (region
));
742 i
= SESE_PARAMS (region
).length ();
743 SESE_PARAMS (region
).safe_push (name
);
747 /* Extract an affine expression from the tree E in the scop S. */
750 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
752 isl_pw_aff
*lhs
, *rhs
, *res
;
755 if (e
== chrec_dont_know
) {
756 isl_space_free (space
);
760 switch (TREE_CODE (e
))
762 case POLYNOMIAL_CHREC
:
763 res
= extract_affine_chrec (s
, e
, space
);
767 res
= extract_affine_mul (s
, e
, space
);
771 case POINTER_PLUS_EXPR
:
772 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
773 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
774 res
= isl_pw_aff_add (lhs
, rhs
);
778 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
779 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
780 res
= isl_pw_aff_sub (lhs
, rhs
);
785 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
786 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
787 res
= isl_pw_aff_mul (lhs
, rhs
);
791 gcc_assert (-1 != parameter_index_in_region_1 (e
, s
->region
)
792 || !invariant_in_sese_p_rec (e
, s
->region
));
793 res
= extract_affine_name (s
, e
, space
);
797 res
= extract_affine_int (e
, space
);
798 /* No need to wrap a single integer. */
802 case NON_LVALUE_EXPR
:
803 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
811 type
= TREE_TYPE (e
);
812 if (TYPE_UNSIGNED (type
))
813 res
= wrap (res
, TYPE_PRECISION (type
));
818 /* In the context of sese S, scan the expression E and translate it to
819 a linear expression C. When parsing a symbolic multiplication, K
820 represents the constant multiplier of an expression containing
824 scan_tree_for_params (sese s
, tree e
)
826 if (e
== chrec_dont_know
)
829 switch (TREE_CODE (e
))
831 case POLYNOMIAL_CHREC
:
832 scan_tree_for_params (s
, CHREC_LEFT (e
));
836 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
837 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
839 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
843 case POINTER_PLUS_EXPR
:
845 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
846 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
852 case NON_LVALUE_EXPR
:
853 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
857 parameter_index_in_region (e
, s
);
873 /* Find parameters with respect to REGION in BB. We are looking in memory
874 access functions, conditions and loop bounds. */
877 find_params_in_bb (sese region
, gimple_poly_bb_p gbb
)
883 loop_p loop
= GBB_BB (gbb
)->loop_father
;
885 /* Find parameters in the access functions of data references. */
886 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
887 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
888 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
890 /* Find parameters in conditional statements. */
891 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
893 tree lhs
= scalar_evolution_in_region (region
, loop
,
894 gimple_cond_lhs (stmt
));
895 tree rhs
= scalar_evolution_in_region (region
, loop
,
896 gimple_cond_rhs (stmt
));
898 scan_tree_for_params (region
, lhs
);
899 scan_tree_for_params (region
, rhs
);
903 /* Record the parameters used in the SCOP. A variable is a parameter
904 in a scop if it does not vary during the execution of that scop. */
907 find_scop_parameters (scop_p scop
)
911 sese region
= SCOP_REGION (scop
);
915 /* Find the parameters used in the loop bounds. */
916 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
918 tree nb_iters
= number_of_latch_executions (loop
);
920 if (!chrec_contains_symbols (nb_iters
))
923 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
924 scan_tree_for_params (region
, nb_iters
);
927 /* Find the parameters used in data accesses. */
928 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
929 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
931 nbp
= sese_nb_params (region
);
932 scop_set_nb_params (scop
, nbp
);
933 SESE_ADD_PARAMS (region
) = false;
937 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
939 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
940 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
941 isl_id_for_ssa_name (scop
, e
));
943 scop
->context
= isl_set_universe (space
);
947 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
948 the constraints for the surrounding loops. */
951 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
953 isl_set
*outer
, isl_set
**doms
)
955 tree nb_iters
= number_of_latch_executions (loop
);
956 sese region
= SCOP_REGION (scop
);
958 isl_set
*inner
= isl_set_copy (outer
);
961 int pos
= isl_set_dim (outer
, isl_dim_set
);
967 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
968 space
= isl_set_get_space (inner
);
971 c
= isl_inequality_alloc
972 (isl_local_space_from_space (isl_space_copy (space
)));
973 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
974 inner
= isl_set_add_constraint (inner
, c
);
976 /* loop_i <= cst_nb_iters */
977 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
979 c
= isl_inequality_alloc
980 (isl_local_space_from_space (isl_space_copy (space
)));
981 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
982 tree_int_to_gmp (nb_iters
, g
);
983 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
984 c
= isl_constraint_set_constant_val (c
, v
);
985 inner
= isl_set_add_constraint (inner
, c
);
988 /* loop_i <= expr_nb_iters */
989 else if (!chrec_contains_undetermined (nb_iters
))
998 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1000 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1001 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1002 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1003 isl_set_dim (valid
, isl_dim_set
));
1004 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1006 ls
= isl_local_space_from_space (isl_space_copy (space
));
1007 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1008 isl_dim_in
, pos
, 1);
1009 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1010 isl_pw_aff_copy (aff
));
1011 inner
= isl_set_intersect (inner
, le
);
1013 if (max_stmt_executions (loop
, &nit
))
1015 /* Insert in the context the constraints from the
1016 estimation of the number of iterations NIT and the
1017 symbolic number of iterations (involving parameter
1018 names) NB_ITERS. First, build the affine expression
1019 "NIT - NB_ITERS" and then say that it is positive,
1020 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1027 wi::to_mpz (nit
, g
, SIGNED
);
1028 mpz_sub_ui (g
, g
, 1);
1029 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1030 x
= isl_pw_aff_ge_set (approx
, aff
);
1031 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1032 isl_set_dim (x
, isl_dim_set
));
1033 scop
->context
= isl_set_intersect (scop
->context
, x
);
1035 c
= isl_inequality_alloc
1036 (isl_local_space_from_space (isl_space_copy (space
)));
1037 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1038 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1040 c
= isl_constraint_set_constant_val (c
, v
);
1041 inner
= isl_set_add_constraint (inner
, c
);
1044 isl_pw_aff_free (aff
);
1049 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1050 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1051 isl_set_copy (inner
), doms
);
1055 && loop_in_sese_p (loop
->next
, region
))
1056 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1057 isl_set_copy (outer
), doms
);
1059 doms
[loop
->num
] = inner
;
1061 isl_set_free (outer
);
1062 isl_space_free (space
);
1066 /* Returns a linear expression for tree T evaluated in PBB. */
1069 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1071 scop_p scop
= PBB_SCOP (pbb
);
1073 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1074 gcc_assert (!automatically_generated_chrec_p (t
));
1076 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1079 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1080 operator. This allows us to invert the condition or to handle
1084 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1086 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1087 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1093 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1097 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1101 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1105 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1109 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1113 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1117 isl_pw_aff_free (lhs
);
1118 isl_pw_aff_free (rhs
);
1122 cond
= isl_set_coalesce (cond
);
1123 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1124 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1127 /* Add conditions to the domain of PBB. */
1130 add_conditions_to_domain (poly_bb_p pbb
)
1134 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1136 if (GBB_CONDITIONS (gbb
).is_empty ())
1139 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1140 switch (gimple_code (stmt
))
1144 /* Don't constrain on anything else than INTEGER_TYPE. */
1145 if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt
))) != INTEGER_TYPE
)
1148 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1149 enum tree_code code
= gimple_cond_code (cond_stmt
);
1151 /* The conditions for ELSE-branches are inverted. */
1152 if (!GBB_CONDITION_CASES (gbb
)[i
])
1153 code
= invert_tree_comparison (code
, false);
1155 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1160 /* Switch statements are not supported right now - fall through. */
1168 /* Traverses all the GBBs of the SCOP and add their constraints to the
1169 iteration domains. */
1172 add_conditions_to_constraints (scop_p scop
)
1177 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1178 add_conditions_to_domain (pbb
);
1181 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1182 edge between BB and its predecessor is not a loop exit edge, and
1183 the last statement of the single predecessor is a COND_EXPR. */
1186 single_pred_cond_non_loop_exit (basic_block bb
)
1188 if (single_pred_p (bb
))
1190 edge e
= single_pred_edge (bb
);
1191 basic_block pred
= e
->src
;
1194 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1197 stmt
= last_stmt (pred
);
1199 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1200 return as_a
<gcond
*> (stmt
);
1206 class sese_dom_walker
: public dom_walker
1209 sese_dom_walker (cdi_direction
, sese
);
1211 virtual void before_dom_children (basic_block
);
1212 virtual void after_dom_children (basic_block
);
1215 auto_vec
<gimple
*, 3> m_conditions
, m_cases
;
1219 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1220 : dom_walker (direction
), m_region (region
)
1224 /* Call-back for dom_walk executed before visiting the dominated
1228 sese_dom_walker::before_dom_children (basic_block bb
)
1230 gimple_poly_bb_p gbb
;
1233 if (!bb_in_sese_p (bb
, m_region
))
1236 stmt
= single_pred_cond_non_loop_exit (bb
);
1240 edge e
= single_pred_edge (bb
);
1242 m_conditions
.safe_push (stmt
);
1244 if (e
->flags
& EDGE_TRUE_VALUE
)
1245 m_cases
.safe_push (stmt
);
1247 m_cases
.safe_push (NULL
);
1250 gbb
= gbb_from_bb (bb
);
1254 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1255 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1259 /* Call-back for dom_walk executed after visiting the dominated
1263 sese_dom_walker::after_dom_children (basic_block bb
)
1265 if (!bb_in_sese_p (bb
, m_region
))
1268 if (single_pred_cond_non_loop_exit (bb
))
1270 m_conditions
.pop ();
1275 /* Add constraints on the possible values of parameter P from the type
1279 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1281 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1282 tree type
= TREE_TYPE (parameter
);
1283 tree lb
= NULL_TREE
;
1284 tree ub
= NULL_TREE
;
1286 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1287 lb
= lower_bound_in_type (type
, type
);
1289 lb
= TYPE_MIN_VALUE (type
);
1291 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1292 ub
= upper_bound_in_type (type
, type
);
1294 ub
= TYPE_MAX_VALUE (type
);
1298 isl_space
*space
= isl_set_get_space (scop
->context
);
1303 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1305 tree_int_to_gmp (lb
, g
);
1306 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1307 v
= isl_val_neg (v
);
1309 c
= isl_constraint_set_constant_val (c
, v
);
1310 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1312 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1317 isl_space
*space
= isl_set_get_space (scop
->context
);
1322 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1325 tree_int_to_gmp (ub
, g
);
1326 v
= isl_val_int_from_gmp (scop
->ctx
, g
);
1328 c
= isl_constraint_set_constant_val (c
, v
);
1329 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1331 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1335 /* Build the context of the SCOP. The context usually contains extra
1336 constraints that are added to the iteration domains that constrain
1340 build_scop_context (scop_p scop
)
1342 graphite_dim_t p
, n
= scop_nb_params (scop
);
1344 for (p
= 0; p
< n
; p
++)
1345 add_param_constraints (scop
, p
);
1348 /* Build the iteration domains: the loops belonging to the current
1349 SCOP, and that vary for the execution of the current basic block.
1350 Returns false if there is no loop in SCOP. */
1353 build_scop_iteration_domain (scop_p scop
)
1356 sese region
= SCOP_REGION (scop
);
1359 int nb_loops
= number_of_loops (cfun
);
1360 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1362 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1363 if (!loop_in_sese_p (loop_outer (loop
), region
))
1364 build_loop_iteration_domains (scop
, loop
, 0,
1365 isl_set_copy (scop
->context
), doms
);
1367 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1369 loop
= pbb_loop (pbb
);
1371 if (doms
[loop
->num
])
1372 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1374 pbb
->domain
= isl_set_copy (scop
->context
);
1376 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1377 isl_id_for_pbb (scop
, pbb
));
1380 for (i
= 0; i
< nb_loops
; i
++)
1382 isl_set_free (doms
[i
]);
1387 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1388 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1389 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1393 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1396 int alias_set_num
= 0;
1397 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1399 if (bap
&& bap
->alias_set
)
1400 alias_set_num
= *(bap
->alias_set
);
1402 c
= isl_equality_alloc
1403 (isl_local_space_from_space (isl_map_get_space (acc
)));
1404 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1405 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1407 return isl_map_add_constraint (acc
, c
);
1410 /* Assign the affine expression INDEX to the output dimension POS of
1411 MAP and return the result. */
1414 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1417 int len
= isl_map_dim (map
, isl_dim_out
);
1420 index_map
= isl_map_from_pw_aff (index
);
1421 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1422 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1424 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1425 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1426 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1427 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1429 return isl_map_intersect (map
, index_map
);
1432 /* Add to ACCESSES polyhedron equalities defining the access functions
1433 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1434 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1435 PBB is the poly_bb_p that contains the data reference DR. */
1438 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1440 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1441 scop_p scop
= PBB_SCOP (pbb
);
1443 for (i
= 0; i
< nb_subscripts
; i
++)
1446 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1448 aff
= extract_affine (scop
, afn
,
1449 isl_space_domain (isl_map_get_space (acc
)));
1450 acc
= set_index (acc
, i
+ 1, aff
);
1456 /* Add constrains representing the size of the accessed data to the
1457 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1458 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1462 pdr_add_data_dimensions (isl_set
*subscript_sizes
, scop_p scop
,
1463 data_reference_p dr
)
1465 tree ref
= DR_REF (dr
);
1467 int nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1468 for (int i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1470 if (TREE_CODE (ref
) != ARRAY_REF
)
1471 return subscript_sizes
;
1473 tree low
= array_ref_low_bound (ref
);
1474 tree high
= array_ref_up_bound (ref
);
1476 /* XXX The PPL code dealt separately with
1477 subscript - low >= 0 and high - subscript >= 0 in case one of
1478 the two bounds isn't known. Do the same here? */
1480 if (tree_fits_shwi_p (low
)
1482 && tree_fits_shwi_p (high
)
1483 /* 1-element arrays at end of structures may extend over
1484 their declared size. */
1485 && !(array_at_struct_end_p (ref
)
1486 && operand_equal_p (low
, high
, 0)))
1490 isl_set
*univ
, *lbs
, *ubs
;
1493 isl_space
*space
= isl_set_get_space (subscript_sizes
);
1494 isl_pw_aff
*lb
= extract_affine_int (low
, isl_space_copy (space
));
1495 isl_pw_aff
*ub
= extract_affine_int (high
, isl_space_copy (space
));
1498 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1499 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1500 isl_set_dim (valid
, isl_dim_set
));
1501 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1503 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1504 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1505 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1506 index
= isl_pw_aff_alloc (univ
, aff
);
1508 id
= isl_set_get_tuple_id (subscript_sizes
);
1509 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1510 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1512 /* low <= sub_i <= high */
1513 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1514 ubs
= isl_pw_aff_le_set (index
, ub
);
1515 subscript_sizes
= isl_set_intersect (subscript_sizes
, lbs
);
1516 subscript_sizes
= isl_set_intersect (subscript_sizes
, ubs
);
1520 return subscript_sizes
;
1523 /* Build data accesses for DR in PBB. */
1526 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1528 int dr_base_object_set
;
1530 isl_set
*subscript_sizes
;
1531 scop_p scop
= PBB_SCOP (pbb
);
1534 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1535 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1536 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1537 isl_dim_out
, nb_out
);
1539 acc
= isl_map_universe (space
);
1540 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1543 acc
= pdr_add_alias_set (acc
, dr
);
1544 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1547 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1548 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1549 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1550 int alias_set_num
= 0;
1551 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1553 if (bap
&& bap
->alias_set
)
1554 alias_set_num
= *(bap
->alias_set
);
1556 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1557 subscript_sizes
= isl_set_nat_universe (space
);
1558 subscript_sizes
= isl_set_fix_si (subscript_sizes
, isl_dim_set
, 0,
1560 subscript_sizes
= pdr_add_data_dimensions (subscript_sizes
, scop
, dr
);
1563 gcc_assert (dr
->aux
);
1564 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1566 new_poly_dr (pbb
, dr_base_object_set
,
1567 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1568 dr
, DR_NUM_DIMENSIONS (dr
), acc
, subscript_sizes
);
1571 /* Write to FILE the alias graph of data references in DIMACS format. */
1574 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1575 vec
<data_reference_p
> drs
)
1577 int num_vertex
= drs
.length ();
1579 data_reference_p dr1
, dr2
;
1582 if (num_vertex
== 0)
1585 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1586 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1587 if (dr_may_alias_p (dr1
, dr2
, true))
1590 fprintf (file
, "$\n");
1593 fprintf (file
, "c %s\n", comment
);
1595 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1597 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1598 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1599 if (dr_may_alias_p (dr1
, dr2
, true))
1600 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1605 /* Write to FILE the alias graph of data references in DOT format. */
1608 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1609 vec
<data_reference_p
> drs
)
1611 int num_vertex
= drs
.length ();
1612 data_reference_p dr1
, dr2
;
1615 if (num_vertex
== 0)
1618 fprintf (file
, "$\n");
1621 fprintf (file
, "c %s\n", comment
);
1623 /* First print all the vertices. */
1624 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1625 fprintf (file
, "n%d;\n", i
);
1627 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1628 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1629 if (dr_may_alias_p (dr1
, dr2
, true))
1630 fprintf (file
, "n%d n%d\n", i
, j
);
1635 /* Write to FILE the alias graph of data references in ECC format. */
1638 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1639 vec
<data_reference_p
> drs
)
1641 int num_vertex
= drs
.length ();
1642 data_reference_p dr1
, dr2
;
1645 if (num_vertex
== 0)
1648 fprintf (file
, "$\n");
1651 fprintf (file
, "c %s\n", comment
);
1653 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1654 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1655 if (dr_may_alias_p (dr1
, dr2
, true))
1656 fprintf (file
, "%d %d\n", i
, j
);
1661 /* Check if DR1 and DR2 are in the same object set. */
1664 dr_same_base_object_p (const struct data_reference
*dr1
,
1665 const struct data_reference
*dr2
)
1667 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1670 /* Uses DFS component number as representative of alias-sets. Also tests for
1671 optimality by verifying if every connected component is a clique. Returns
1672 true (1) if the above test is true, and false (0) otherwise. */
1675 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1677 int num_vertices
= drs
.length ();
1678 struct graph
*g
= new_graph (num_vertices
);
1679 data_reference_p dr1
, dr2
;
1681 int num_connected_components
;
1682 int v_indx1
, v_indx2
, num_vertices_in_component
;
1685 struct graph_edge
*e
;
1686 int this_component_is_clique
;
1687 int all_components_are_cliques
= 1;
1689 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1690 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1691 if (dr_may_alias_p (dr1
, dr2
, true))
1697 all_vertices
= XNEWVEC (int, num_vertices
);
1698 vertices
= XNEWVEC (int, num_vertices
);
1699 for (i
= 0; i
< num_vertices
; i
++)
1700 all_vertices
[i
] = i
;
1702 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1704 for (i
= 0; i
< g
->n_vertices
; i
++)
1706 data_reference_p dr
= drs
[i
];
1707 base_alias_pair
*bap
;
1709 gcc_assert (dr
->aux
);
1710 bap
= (base_alias_pair
*)(dr
->aux
);
1712 bap
->alias_set
= XNEW (int);
1713 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1716 /* Verify if the DFS numbering results in optimal solution. */
1717 for (i
= 0; i
< num_connected_components
; i
++)
1719 num_vertices_in_component
= 0;
1720 /* Get all vertices whose DFS component number is the same as i. */
1721 for (j
= 0; j
< num_vertices
; j
++)
1722 if (g
->vertices
[j
].component
== i
)
1723 vertices
[num_vertices_in_component
++] = j
;
1725 /* Now test if the vertices in 'vertices' form a clique, by testing
1726 for edges among each pair. */
1727 this_component_is_clique
= 1;
1728 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1730 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1732 /* Check if the two vertices are connected by iterating
1733 through all the edges which have one of these are source. */
1734 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1737 if (e
->src
== vertices
[v_indx1
])
1743 this_component_is_clique
= 0;
1747 if (!this_component_is_clique
)
1748 all_components_are_cliques
= 0;
1752 free (all_vertices
);
1755 return all_components_are_cliques
;
1758 /* Group each data reference in DRS with its base object set num. */
1761 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1763 int num_vertex
= drs
.length ();
1764 struct graph
*g
= new_graph (num_vertex
);
1765 data_reference_p dr1
, dr2
;
1769 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1770 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1771 if (dr_same_base_object_p (dr1
, dr2
))
1777 queue
= XNEWVEC (int, num_vertex
);
1778 for (i
= 0; i
< num_vertex
; i
++)
1781 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1783 for (i
= 0; i
< g
->n_vertices
; i
++)
1785 data_reference_p dr
= drs
[i
];
1786 base_alias_pair
*bap
;
1788 gcc_assert (dr
->aux
);
1789 bap
= (base_alias_pair
*)(dr
->aux
);
1791 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1798 /* Build the data references for PBB. */
1801 build_pbb_drs (poly_bb_p pbb
)
1804 data_reference_p dr
;
1805 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1807 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1808 build_poly_dr (dr
, pbb
);
1811 /* Dump to file the alias graphs for the data references in DRS. */
1814 dump_alias_graphs (vec
<data_reference_p
> drs
)
1817 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1819 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1822 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1823 current_function_name ());
1824 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1825 fclose (file_dimacs
);
1828 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1831 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1832 current_function_name ());
1833 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1837 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1840 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1841 current_function_name ());
1842 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1847 /* Build data references in SCOP. */
1850 build_scop_drs (scop_p scop
)
1854 data_reference_p dr
;
1855 auto_vec
<data_reference_p
, 3> drs
;
1857 /* Remove all the PBBs that do not have data references: these basic
1858 blocks are not handled in the polyhedral representation. */
1859 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1860 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1862 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
1864 SCOP_BBS (scop
).ordered_remove (i
);
1868 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1869 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1872 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1873 dr
->aux
= XNEW (base_alias_pair
);
1875 if (!build_alias_set_optimal_p (drs
))
1877 /* TODO: Add support when building alias set is not optimal. */
1881 build_base_obj_set_for_drs (drs
);
1883 /* When debugging, enable the following code. This cannot be used
1884 in production compilers. */
1886 dump_alias_graphs (drs
);
1890 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1891 build_pbb_drs (pbb
);
1894 /* Analyze all the data references of STMTS and add them to the
1895 GBB_DATA_REFS vector of BB. */
1898 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
*> stmts
)
1901 gimple_poly_bb_p gbb
;
1904 sese region
= SCOP_REGION (scop
);
1906 if (!bb_in_sese_p (bb
, region
))
1909 nest
= outermost_loop_in_sese (region
, bb
);
1911 loop_p loop
= bb
->loop_father
;
1912 if (!loop_in_sese_p (loop
, region
))
1915 gbb
= gbb_from_bb (bb
);
1917 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1919 if (is_gimple_debug (stmt
))
1922 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1923 &GBB_DATA_REFS (gbb
));
1927 /* Insert STMT at the end of the STMTS sequence and then insert the
1928 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1932 insert_stmts (scop_p scop
, gimple
*stmt
, gimple_seq stmts
,
1933 gimple_stmt_iterator insert_gsi
)
1935 gimple_stmt_iterator gsi
;
1936 auto_vec
<gimple
*, 3> x
;
1938 gimple_seq_add_stmt (&stmts
, stmt
);
1939 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1940 x
.safe_push (gsi_stmt (gsi
));
1942 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1943 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1946 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1949 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple
*after_stmt
)
1952 gimple_stmt_iterator gsi
;
1953 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1954 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
1955 auto_vec
<gimple
*, 3> x
;
1957 gimple_seq_add_stmt (&stmts
, stmt
);
1958 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1959 x
.safe_push (gsi_stmt (gsi
));
1961 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
1963 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
1964 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
1968 gsi
= gsi_for_stmt (after_stmt
);
1969 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1972 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
1975 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
1978 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
1980 vec
<data_reference_p
> drs
;
1982 gimple_poly_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1983 gimple_poly_bb_p gbb1
= new_gimple_poly_bb (bb
, drs
);
1984 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
1985 int index
, n
= SCOP_BBS (scop
).length ();
1987 /* The INDEX of PBB in SCOP_BBS. */
1988 for (index
= 0; index
< n
; index
++)
1989 if (SCOP_BBS (scop
)[index
] == pbb
)
1992 pbb1
->domain
= isl_set_copy (pbb
->domain
);
1993 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
1994 isl_id_for_pbb (scop
, pbb1
));
1996 GBB_PBB (gbb1
) = pbb1
;
1997 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
1998 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
1999 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2002 /* Insert on edge E the assignment "RES := EXPR". */
2005 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2007 gimple_stmt_iterator gsi
;
2008 gimple_seq stmts
= NULL
;
2009 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2010 gimple
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2012 auto_vec
<gimple
*, 3> x
;
2014 gimple_seq_add_stmt (&stmts
, stmt
);
2015 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2016 x
.safe_push (gsi_stmt (gsi
));
2018 gsi_insert_seq_on_edge (e
, stmts
);
2019 gsi_commit_edge_inserts ();
2020 bb
= gimple_bb (stmt
);
2022 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2025 if (!gbb_from_bb (bb
))
2026 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2028 analyze_drs_in_stmts (scop
, bb
, x
);
2031 /* Creates a zero dimension array of the same type as VAR. */
2034 create_zero_dim_array (tree var
, const char *base_name
)
2036 tree index_type
= build_index_type (integer_zero_node
);
2037 tree elt_type
= TREE_TYPE (var
);
2038 tree array_type
= build_array_type (elt_type
, index_type
);
2039 tree base
= create_tmp_var (array_type
, base_name
);
2041 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2045 /* Returns true when PHI is a loop close phi node. */
2048 scalar_close_phi_node_p (gimple
*phi
)
2050 if (gimple_code (phi
) != GIMPLE_PHI
2051 || virtual_operand_p (gimple_phi_result (phi
)))
2054 /* Note that loop close phi nodes should have a single argument
2055 because we translated the representation into a canonical form
2056 before Graphite: see canonicalize_loop_closed_ssa_form. */
2057 return (gimple_phi_num_args (phi
) == 1);
2060 /* For a definition DEF in REGION, propagates the expression EXPR in
2061 all the uses of DEF outside REGION. */
2064 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2066 imm_use_iterator imm_iter
;
2069 bool replaced_once
= false;
2071 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2073 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2076 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2077 if (!is_gimple_debug (use_stmt
)
2078 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2081 use_operand_p use_p
;
2083 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2084 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2085 && (replaced_once
= true))
2086 replace_exp (use_p
, expr
);
2088 update_stmt (use_stmt
);
2093 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2094 gsi_commit_edge_inserts ();
2098 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2099 dimension array for it. */
2102 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2104 sese region
= SCOP_REGION (scop
);
2105 gimple
*phi
= gsi_stmt (*psi
);
2106 tree res
= gimple_phi_result (phi
);
2107 basic_block bb
= gimple_bb (phi
);
2108 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2109 tree arg
= gimple_phi_arg_def (phi
, 0);
2112 /* Note that loop close phi nodes should have a single argument
2113 because we translated the representation into a canonical form
2114 before Graphite: see canonicalize_loop_closed_ssa_form. */
2115 gcc_assert (gimple_phi_num_args (phi
) == 1);
2117 /* The phi node can be a non close phi node, when its argument is
2118 invariant, or a default definition. */
2119 if (is_gimple_min_invariant (arg
)
2120 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2122 propagate_expr_outside_region (res
, arg
, region
);
2127 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2129 propagate_expr_outside_region (res
, arg
, region
);
2130 stmt
= gimple_build_assign (res
, arg
);
2131 remove_phi_node (psi
, false);
2132 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2136 /* If res is scev analyzable and is not a scalar value, it is safe
2137 to ignore the close phi node: it will be code generated in the
2138 out of Graphite pass. */
2139 else if (scev_analyzable_p (res
, region
))
2141 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2144 if (!loop_in_sese_p (loop
, region
))
2146 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2147 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2148 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2151 scev
= scalar_evolution_in_region (region
, loop
, res
);
2153 if (tree_does_not_contain_chrecs (scev
))
2154 propagate_expr_outside_region (res
, scev
, region
);
2161 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2163 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2165 if (TREE_CODE (arg
) == SSA_NAME
)
2166 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2167 SSA_NAME_DEF_STMT (arg
));
2169 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2170 zero_dim_array
, arg
);
2173 remove_phi_node (psi
, false);
2174 SSA_NAME_DEF_STMT (res
) = stmt
;
2176 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2179 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2180 dimension array for it. */
2183 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2186 gphi
*phi
= psi
->phi ();
2187 basic_block bb
= gimple_bb (phi
);
2188 tree res
= gimple_phi_result (phi
);
2189 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2192 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2194 tree arg
= gimple_phi_arg_def (phi
, i
);
2195 edge e
= gimple_phi_arg_edge (phi
, i
);
2197 /* Avoid the insertion of code in the loop latch to please the
2198 pattern matching of the vectorizer. */
2199 if (TREE_CODE (arg
) == SSA_NAME
2200 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2201 && e
->src
== bb
->loop_father
->latch
)
2202 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2203 SSA_NAME_DEF_STMT (arg
));
2205 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2208 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2209 remove_phi_node (psi
, false);
2210 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2213 /* Rewrite the degenerate phi node at position PSI from the degenerate
2214 form "x = phi (y, y, ..., y)" to "x = y". */
2217 rewrite_degenerate_phi (gphi_iterator
*psi
)
2221 gimple_stmt_iterator gsi
;
2222 gphi
*phi
= psi
->phi ();
2223 tree res
= gimple_phi_result (phi
);
2226 bb
= gimple_bb (phi
);
2227 rhs
= degenerate_phi_result (phi
);
2230 stmt
= gimple_build_assign (res
, rhs
);
2231 remove_phi_node (psi
, false);
2233 gsi
= gsi_after_labels (bb
);
2234 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2237 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2240 rewrite_reductions_out_of_ssa (scop_p scop
)
2244 sese region
= SCOP_REGION (scop
);
2246 FOR_EACH_BB_FN (bb
, cfun
)
2247 if (bb_in_sese_p (bb
, region
))
2248 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2250 gphi
*phi
= psi
.phi ();
2252 if (virtual_operand_p (gimple_phi_result (phi
)))
2258 if (gimple_phi_num_args (phi
) > 1
2259 && degenerate_phi_result (phi
))
2260 rewrite_degenerate_phi (&psi
);
2262 else if (scalar_close_phi_node_p (phi
))
2263 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2265 else if (reduction_phi_p (region
, &psi
))
2266 rewrite_phi_out_of_ssa (scop
, &psi
);
2269 update_ssa (TODO_update_ssa
);
2270 #ifdef ENABLE_CHECKING
2271 verify_loop_closed_ssa (true);
2275 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2276 read from ZERO_DIM_ARRAY. */
2279 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2280 tree def
, gimple
*use_stmt
)
2285 use_operand_p use_p
;
2287 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2289 name
= copy_ssa_name (def
);
2290 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2292 gimple_assign_set_lhs (name_stmt
, name
);
2293 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2295 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2296 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2297 replace_exp (use_p
, name
);
2299 update_stmt (use_stmt
);
2302 /* For every definition DEF in the SCOP that is used outside the scop,
2303 insert a closing-scop definition in the basic block just after this
2307 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple
*stmt
)
2309 tree var
= create_tmp_reg (TREE_TYPE (def
));
2310 tree new_name
= make_ssa_name (var
, stmt
);
2311 bool needs_copy
= false;
2312 use_operand_p use_p
;
2313 imm_use_iterator imm_iter
;
2315 sese region
= SCOP_REGION (scop
);
2317 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2319 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2321 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2323 SET_USE (use_p
, new_name
);
2325 update_stmt (use_stmt
);
2330 /* Insert in the empty BB just after the scop a use of DEF such
2331 that the rewrite of cross_bb_scalar_dependences won't insert
2332 arrays everywhere else. */
2335 gimple
*assign
= gimple_build_assign (new_name
, def
);
2336 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2338 update_stmt (assign
);
2339 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2343 /* Rewrite the scalar dependences crossing the boundary of the BB
2344 containing STMT with an array. Return true when something has been
2348 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2350 sese region
= SCOP_REGION (scop
);
2351 gimple
*stmt
= gsi_stmt (*gsi
);
2352 imm_use_iterator imm_iter
;
2355 tree zero_dim_array
= NULL_TREE
;
2359 switch (gimple_code (stmt
))
2362 def
= gimple_assign_lhs (stmt
);
2366 def
= gimple_call_lhs (stmt
);
2374 || !is_gimple_reg (def
))
2377 if (scev_analyzable_p (def
, region
))
2379 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2380 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2382 if (tree_contains_chrecs (scev
, NULL
))
2385 propagate_expr_outside_region (def
, scev
, region
);
2389 def_bb
= gimple_bb (stmt
);
2391 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2393 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2394 if (gphi
*phi
= dyn_cast
<gphi
*> (use_stmt
))
2397 gphi_iterator psi
= gsi_for_phi (phi
);
2399 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2400 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2402 rewrite_phi_out_of_ssa (scop
, &psi
);
2405 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2406 if (gimple_code (use_stmt
) != GIMPLE_PHI
2407 && def_bb
!= gimple_bb (use_stmt
)
2408 && !is_gimple_debug (use_stmt
)
2411 if (!zero_dim_array
)
2413 zero_dim_array
= create_zero_dim_array
2414 (def
, "Cross_BB_scalar_dependence");
2415 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2416 SSA_NAME_DEF_STMT (def
));
2420 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2424 update_ssa (TODO_update_ssa
);
2429 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2432 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2435 gimple_stmt_iterator psi
;
2436 sese region
= SCOP_REGION (scop
);
2437 bool changed
= false;
2439 /* Create an extra empty BB after the scop. */
2440 split_edge (SESE_EXIT (region
));
2442 FOR_EACH_BB_FN (bb
, cfun
)
2443 if (bb_in_sese_p (bb
, region
))
2444 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2445 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2450 update_ssa (TODO_update_ssa
);
2451 #ifdef ENABLE_CHECKING
2452 verify_loop_closed_ssa (true);
2457 /* Returns the number of pbbs that are in loops contained in SCOP. */
2460 nb_pbbs_in_loops (scop_p scop
)
2466 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2467 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2473 /* Builds the polyhedral representation for a SESE region. */
2476 build_poly_scop (scop_p scop
)
2478 sese region
= SCOP_REGION (scop
);
2479 graphite_dim_t max_dim
;
2481 build_scop_bbs (scop
);
2483 /* Do not optimize a scop containing only PBBs that do not belong
2485 if (nb_pbbs_in_loops (scop
) == 0)
2488 build_sese_loop_nests (region
);
2489 /* Record all conditions in REGION. */
2490 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
2491 find_scop_parameters (scop
);
2493 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
2494 if (scop_nb_params (scop
) > max_dim
)
2497 build_scop_iteration_domain (scop
);
2498 build_scop_context (scop
);
2499 add_conditions_to_constraints (scop
);
2501 /* Rewrite out of SSA only after having translated the
2502 representation to the polyhedral representation to avoid scev
2503 analysis failures. That means that these functions will insert
2504 new data references that they create in the right place. */
2505 rewrite_reductions_out_of_ssa (scop
);
2506 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
2508 build_scop_drs (scop
);
2509 build_scop_scattering (scop
);
2511 /* This SCoP has been translated to the polyhedral
2513 POLY_SCOP_P (scop
) = true;
2515 #endif /* HAVE_isl */