1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2014 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/>. */
26 #include <isl/union_map.h>
27 #include <isl/constraint.h>
31 /* Since ISL-0.13, the extern is in val_gmp.h. */
32 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
35 #include <isl/val_gmp.h>
36 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
42 #include "coretypes.h"
50 #include "hard-reg-set.h"
53 #include "dominance.h"
55 #include "basic-block.h"
56 #include "tree-ssa-alias.h"
57 #include "internal-fn.h"
58 #include "gimple-expr.h"
61 #include "gimple-iterator.h"
63 #include "gimplify-me.h"
64 #include "gimple-ssa.h"
66 #include "tree-phinodes.h"
67 #include "ssa-iterators.h"
68 #include "stringpool.h"
69 #include "tree-ssanames.h"
70 #include "tree-ssa-loop-manip.h"
71 #include "tree-ssa-loop-niter.h"
72 #include "tree-ssa-loop.h"
73 #include "tree-into-ssa.h"
74 #include "tree-pass.h"
76 #include "tree-chrec.h"
77 #include "tree-data-ref.h"
78 #include "tree-scalar-evolution.h"
81 #include "tree-ssa-propagate.h"
85 #include "graphite-poly.h"
86 #include "graphite-sese-to-poly.h"
89 /* Assigns to RES the value of the INTEGER_CST T. */
92 tree_int_to_gmp (tree t
, mpz_t res
)
94 wi::to_mpz (t
, res
, TYPE_SIGN (TREE_TYPE (t
)));
97 /* Returns the index of the PHI argument defined in the outermost
101 phi_arg_in_outermost_loop (gphi
*phi
)
103 loop_p loop
= gimple_bb (phi
)->loop_father
;
106 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
107 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
109 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
116 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
117 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
120 remove_simple_copy_phi (gphi_iterator
*psi
)
122 gphi
*phi
= psi
->phi ();
123 tree res
= gimple_phi_result (phi
);
124 size_t entry
= phi_arg_in_outermost_loop (phi
);
125 tree init
= gimple_phi_arg_def (phi
, entry
);
126 gassign
*stmt
= gimple_build_assign (res
, init
);
127 edge e
= gimple_phi_arg_edge (phi
, entry
);
129 remove_phi_node (psi
, false);
130 gsi_insert_on_edge_immediate (e
, stmt
);
133 /* Removes an invariant phi node at position PSI by inserting on the
134 loop ENTRY edge the assignment RES = INIT. */
137 remove_invariant_phi (sese region
, gphi_iterator
*psi
)
139 gphi
*phi
= psi
->phi ();
140 loop_p loop
= loop_containing_stmt (phi
);
141 tree res
= gimple_phi_result (phi
);
142 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
143 size_t entry
= phi_arg_in_outermost_loop (phi
);
144 edge e
= gimple_phi_arg_edge (phi
, entry
);
147 gimple_seq stmts
= NULL
;
149 if (tree_contains_chrecs (scev
, NULL
))
150 scev
= gimple_phi_arg_def (phi
, entry
);
152 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
153 stmt
= gimple_build_assign (res
, var
);
154 remove_phi_node (psi
, false);
156 gimple_seq_add_stmt (&stmts
, stmt
);
157 gsi_insert_seq_on_edge (e
, stmts
);
158 gsi_commit_edge_inserts ();
159 SSA_NAME_DEF_STMT (res
) = stmt
;
162 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
165 simple_copy_phi_p (gphi
*phi
)
169 if (gimple_phi_num_args (phi
) != 2)
172 res
= gimple_phi_result (phi
);
173 return (res
== gimple_phi_arg_def (phi
, 0)
174 || res
== gimple_phi_arg_def (phi
, 1));
177 /* Returns true when the phi node at position PSI is a reduction phi
178 node in REGION. Otherwise moves the pointer PSI to the next phi to
182 reduction_phi_p (sese region
, gphi_iterator
*psi
)
185 gphi
*phi
= psi
->phi ();
186 tree res
= gimple_phi_result (phi
);
188 loop
= loop_containing_stmt (phi
);
190 if (simple_copy_phi_p (phi
))
192 /* PRE introduces phi nodes like these, for an example,
193 see id-5.f in the fortran graphite testsuite:
195 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
197 remove_simple_copy_phi (psi
);
201 if (scev_analyzable_p (res
, region
))
203 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
205 if (evolution_function_is_invariant_p (scev
, loop
->num
))
206 remove_invariant_phi (region
, psi
);
213 /* All the other cases are considered reductions. */
217 /* Store the GRAPHITE representation of BB. */
220 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
222 struct gimple_bb
*gbb
;
224 gbb
= XNEW (struct gimple_bb
);
227 GBB_DATA_REFS (gbb
) = drs
;
228 GBB_CONDITIONS (gbb
).create (0);
229 GBB_CONDITION_CASES (gbb
).create (0);
235 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
238 struct data_reference
*dr
;
240 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
243 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
245 free (bap
->alias_set
);
254 free_gimple_bb (struct gimple_bb
*gbb
)
256 free_data_refs_aux (GBB_DATA_REFS (gbb
));
257 free_data_refs (GBB_DATA_REFS (gbb
));
259 GBB_CONDITIONS (gbb
).release ();
260 GBB_CONDITION_CASES (gbb
).release ();
261 GBB_BB (gbb
)->aux
= 0;
265 /* Deletes all gimple bbs in SCOP. */
268 remove_gbbs_in_scop (scop_p scop
)
273 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
274 free_gimple_bb (PBB_BLACK_BOX (pbb
));
277 /* Deletes all scops in SCOPS. */
280 free_scops (vec
<scop_p
> scops
)
285 FOR_EACH_VEC_ELT (scops
, i
, scop
)
287 remove_gbbs_in_scop (scop
);
288 free_sese (SCOP_REGION (scop
));
295 /* Same as outermost_loop_in_sese, returns the outermost loop
296 containing BB in REGION, but makes sure that the returned loop
297 belongs to the REGION, and so this returns the first loop in the
298 REGION when the loop containing BB does not belong to REGION. */
301 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
303 loop_p nest
= outermost_loop_in_sese (region
, bb
);
305 if (loop_in_sese_p (nest
, region
))
308 /* When the basic block BB does not belong to a loop in the region,
309 return the first loop in the region. */
312 if (loop_in_sese_p (nest
, region
))
321 /* Generates a polyhedral black box only if the bb contains interesting
325 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
327 vec
<data_reference_p
> drs
;
329 sese region
= SCOP_REGION (scop
);
330 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
331 gimple_stmt_iterator gsi
;
333 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
335 gimple stmt
= gsi_stmt (gsi
);
338 if (is_gimple_debug (stmt
))
341 loop
= loop_containing_stmt (stmt
);
342 if (!loop_in_sese_p (loop
, region
))
345 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
348 return new_gimple_bb (bb
, drs
);
351 /* Returns true if all predecessors of BB, that are not dominated by BB, are
352 marked in MAP. The predecessors dominated by BB are loop latches and will
353 be handled after BB. */
356 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
361 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
362 if (!bitmap_bit_p (map
, e
->src
->index
)
363 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
369 /* Compare the depth of two basic_block's P1 and P2. */
372 compare_bb_depths (const void *p1
, const void *p2
)
374 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
375 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
376 int d1
= loop_depth (bb1
->loop_father
);
377 int d2
= loop_depth (bb2
->loop_father
);
388 /* Sort the basic blocks from DOM such that the first are the ones at
389 a deepest loop level. */
392 graphite_sort_dominated_info (vec
<basic_block
> dom
)
394 dom
.qsort (compare_bb_depths
);
397 /* Recursive helper function for build_scops_bbs. */
400 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
402 sese region
= SCOP_REGION (scop
);
403 vec
<basic_block
> dom
;
406 if (bitmap_bit_p (visited
, bb
->index
)
407 || !bb_in_sese_p (bb
, region
))
410 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
411 SCOP_BBS (scop
).safe_push (pbb
);
412 bitmap_set_bit (visited
, bb
->index
);
414 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
419 graphite_sort_dominated_info (dom
);
421 while (!dom
.is_empty ())
426 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
427 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
429 build_scop_bbs_1 (scop
, visited
, dom_bb
);
430 dom
.unordered_remove (i
);
438 /* Gather the basic blocks belonging to the SCOP. */
441 build_scop_bbs (scop_p scop
)
443 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
444 sese region
= SCOP_REGION (scop
);
446 bitmap_clear (visited
);
447 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
448 sbitmap_free (visited
);
451 /* Return an ISL identifier for the polyhedral basic block PBB. */
454 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
457 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
458 return isl_id_alloc (s
->ctx
, name
, pbb
);
461 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
462 We generate SCATTERING_DIMENSIONS scattering dimensions.
464 CLooG 0.15.0 and previous versions require, that all
465 scattering functions of one CloogProgram have the same number of
466 scattering dimensions, therefore we allow to specify it. This
467 should be removed in future versions of CLooG.
469 The scattering polyhedron consists of these dimensions: scattering,
470 loop_iterators, parameters.
474 | scattering_dimensions = 5
475 | used_scattering_dimensions = 3
483 | Scattering polyhedron:
485 | scattering: {s1, s2, s3, s4, s5}
486 | loop_iterators: {i}
487 | parameters: {p1, p2}
489 | s1 s2 s3 s4 s5 i p1 p2 1
490 | 1 0 0 0 0 0 0 0 -4 = 0
491 | 0 1 0 0 0 -1 0 0 0 = 0
492 | 0 0 1 0 0 0 0 0 -5 = 0 */
495 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
496 poly_bb_p pbb
, int scattering_dimensions
)
499 int nb_iterators
= pbb_dim_iter_domain (pbb
);
500 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
504 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
506 dc
= isl_set_get_space (pbb
->domain
);
507 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
508 isl_dim_out
, scattering_dimensions
);
509 pbb
->schedule
= isl_map_universe (dm
);
511 for (i
= 0; i
< scattering_dimensions
; i
++)
513 /* Textual order inside this loop. */
516 isl_constraint
*c
= isl_equality_alloc
517 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
519 val
= isl_aff_get_coefficient_val (static_sched
, isl_dim_in
, i
/ 2);
521 val
= isl_val_neg (val
);
522 c
= isl_constraint_set_constant_val (c
, val
);
523 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
524 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
527 /* Iterations of this loop. */
528 else /* if ((i % 2) == 1) */
530 int loop
= (i
- 1) / 2;
531 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
536 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
539 /* Build for BB the static schedule.
541 The static schedule is a Dewey numbering of the abstract syntax
542 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
544 The following example informally defines the static schedule:
563 Static schedules for A to F:
576 build_scop_scattering (scop_p scop
)
580 gimple_bb_p previous_gbb
= NULL
;
581 isl_space
*dc
= isl_set_get_space (scop
->context
);
582 isl_aff
*static_sched
;
584 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
585 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
587 /* We have to start schedules at 0 on the first component and
588 because we cannot compare_prefix_loops against a previous loop,
589 prefix will be equal to zero, and that index will be
590 incremented before copying. */
591 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
593 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
595 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
597 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
600 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
606 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
608 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
611 isl_aff_free (static_sched
);
614 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
616 /* Extract an affine expression from the chain of recurrence E. */
619 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
621 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
622 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
623 isl_local_space
*ls
= isl_local_space_from_space (space
);
624 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
625 isl_aff
*loop
= isl_aff_set_coefficient_si
626 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
627 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
629 /* Before multiplying, make sure that the result is affine. */
630 gcc_assert (isl_pw_aff_is_cst (rhs
)
631 || isl_pw_aff_is_cst (l
));
633 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
636 /* Extract an affine expression from the mult_expr E. */
639 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
641 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
642 isl_space_copy (space
));
643 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
645 if (!isl_pw_aff_is_cst (lhs
)
646 && !isl_pw_aff_is_cst (rhs
))
648 isl_pw_aff_free (lhs
);
649 isl_pw_aff_free (rhs
);
653 return isl_pw_aff_mul (lhs
, rhs
);
656 /* Return an ISL identifier from the name of the ssa_name E. */
659 isl_id_for_ssa_name (scop_p s
, tree e
)
661 const char *name
= get_name (e
);
665 id
= isl_id_alloc (s
->ctx
, name
, e
);
669 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
670 id
= isl_id_alloc (s
->ctx
, name1
, e
);
676 /* Return an ISL identifier for the data reference DR. */
679 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
681 /* Data references all get the same isl_id. They need to be comparable
682 and are distinguished through the first dimension, which contains the
684 return isl_id_alloc (s
->ctx
, "", 0);
687 /* Extract an affine expression from the ssa_name E. */
690 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
697 id
= isl_id_for_ssa_name (s
, e
);
698 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
700 dom
= isl_set_universe (isl_space_copy (space
));
701 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
702 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
703 return isl_pw_aff_alloc (dom
, aff
);
706 /* Extract an affine expression from the gmp constant G. */
709 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
711 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
712 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
713 isl_set
*dom
= isl_set_universe (space
);
717 ct
= isl_aff_get_ctx (aff
);
718 v
= isl_val_int_from_gmp (ct
, g
);
719 aff
= isl_aff_add_constant_val (aff
, v
);
721 return isl_pw_aff_alloc (dom
, aff
);
724 /* Extract an affine expression from the integer_cst E. */
727 extract_affine_int (tree e
, __isl_take isl_space
*space
)
733 tree_int_to_gmp (e
, g
);
734 res
= extract_affine_gmp (g
, space
);
740 /* Compute pwaff mod 2^width. */
742 extern isl_ctx
*the_isl_ctx
;
745 wrap (isl_pw_aff
*pwaff
, unsigned width
)
749 mod
= isl_val_int_from_ui(the_isl_ctx
, width
);
750 mod
= isl_val_2exp (mod
);
751 pwaff
= isl_pw_aff_mod_val (pwaff
, mod
);
756 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
757 Otherwise returns -1. */
760 parameter_index_in_region_1 (tree name
, sese region
)
765 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
767 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
774 /* When the parameter NAME is in REGION, returns its index in
775 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
776 and returns the index of NAME. */
779 parameter_index_in_region (tree name
, sese region
)
783 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
785 i
= parameter_index_in_region_1 (name
, region
);
789 gcc_assert (SESE_ADD_PARAMS (region
));
791 i
= SESE_PARAMS (region
).length ();
792 SESE_PARAMS (region
).safe_push (name
);
796 /* Extract an affine expression from the tree E in the scop S. */
799 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
801 isl_pw_aff
*lhs
, *rhs
, *res
;
804 if (e
== chrec_dont_know
) {
805 isl_space_free (space
);
809 switch (TREE_CODE (e
))
811 case POLYNOMIAL_CHREC
:
812 res
= extract_affine_chrec (s
, e
, space
);
816 res
= extract_affine_mul (s
, e
, space
);
820 case POINTER_PLUS_EXPR
:
821 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
822 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
823 res
= isl_pw_aff_add (lhs
, rhs
);
827 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
828 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
829 res
= isl_pw_aff_sub (lhs
, rhs
);
834 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
835 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
836 res
= isl_pw_aff_mul (lhs
, rhs
);
840 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
841 res
= extract_affine_name (s
, e
, space
);
845 res
= extract_affine_int (e
, space
);
846 /* No need to wrap a single integer. */
850 case NON_LVALUE_EXPR
:
851 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
859 type
= TREE_TYPE (e
);
860 if (TYPE_UNSIGNED (type
))
861 res
= wrap (res
, TYPE_PRECISION (type
));
866 /* In the context of sese S, scan the expression E and translate it to
867 a linear expression C. When parsing a symbolic multiplication, K
868 represents the constant multiplier of an expression containing
872 scan_tree_for_params (sese s
, tree e
)
874 if (e
== chrec_dont_know
)
877 switch (TREE_CODE (e
))
879 case POLYNOMIAL_CHREC
:
880 scan_tree_for_params (s
, CHREC_LEFT (e
));
884 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
885 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
887 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
891 case POINTER_PLUS_EXPR
:
893 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
894 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
900 case NON_LVALUE_EXPR
:
901 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
905 parameter_index_in_region (e
, s
);
918 /* Find parameters with respect to REGION in BB. We are looking in memory
919 access functions, conditions and loop bounds. */
922 find_params_in_bb (sese region
, gimple_bb_p gbb
)
928 loop_p loop
= GBB_BB (gbb
)->loop_father
;
930 /* Find parameters in the access functions of data references. */
931 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
932 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
933 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
935 /* Find parameters in conditional statements. */
936 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
938 tree lhs
= scalar_evolution_in_region (region
, loop
,
939 gimple_cond_lhs (stmt
));
940 tree rhs
= scalar_evolution_in_region (region
, loop
,
941 gimple_cond_rhs (stmt
));
943 scan_tree_for_params (region
, lhs
);
944 scan_tree_for_params (region
, rhs
);
948 /* Record the parameters used in the SCOP. A variable is a parameter
949 in a scop if it does not vary during the execution of that scop. */
952 find_scop_parameters (scop_p scop
)
956 sese region
= SCOP_REGION (scop
);
960 /* Find the parameters used in the loop bounds. */
961 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
963 tree nb_iters
= number_of_latch_executions (loop
);
965 if (!chrec_contains_symbols (nb_iters
))
968 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
969 scan_tree_for_params (region
, nb_iters
);
972 /* Find the parameters used in data accesses. */
973 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
974 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
976 nbp
= sese_nb_params (region
);
977 scop_set_nb_params (scop
, nbp
);
978 SESE_ADD_PARAMS (region
) = false;
982 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
984 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
985 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
986 isl_id_for_ssa_name (scop
, e
));
988 scop
->context
= isl_set_universe (space
);
992 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
993 the constraints for the surrounding loops. */
996 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
998 isl_set
*outer
, isl_set
**doms
)
1000 tree nb_iters
= number_of_latch_executions (loop
);
1001 sese region
= SCOP_REGION (scop
);
1003 isl_set
*inner
= isl_set_copy (outer
);
1006 int pos
= isl_set_dim (outer
, isl_dim_set
);
1012 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
1013 space
= isl_set_get_space (inner
);
1016 c
= isl_inequality_alloc
1017 (isl_local_space_from_space (isl_space_copy (space
)));
1018 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1019 inner
= isl_set_add_constraint (inner
, c
);
1021 /* loop_i <= cst_nb_iters */
1022 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1024 c
= isl_inequality_alloc
1025 (isl_local_space_from_space (isl_space_copy (space
)));
1026 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1027 tree_int_to_gmp (nb_iters
, g
);
1028 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1029 c
= isl_constraint_set_constant_val (c
, v
);
1030 inner
= isl_set_add_constraint (inner
, c
);
1033 /* loop_i <= expr_nb_iters */
1034 else if (!chrec_contains_undetermined (nb_iters
))
1039 isl_local_space
*ls
;
1043 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1045 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1046 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1047 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1048 isl_set_dim (valid
, isl_dim_set
));
1049 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1051 ls
= isl_local_space_from_space (isl_space_copy (space
));
1052 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1053 isl_dim_in
, pos
, 1);
1054 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1055 isl_pw_aff_copy (aff
));
1056 inner
= isl_set_intersect (inner
, le
);
1058 if (max_stmt_executions (loop
, &nit
))
1060 /* Insert in the context the constraints from the
1061 estimation of the number of iterations NIT and the
1062 symbolic number of iterations (involving parameter
1063 names) NB_ITERS. First, build the affine expression
1064 "NIT - NB_ITERS" and then say that it is positive,
1065 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1072 wi::to_mpz (nit
, g
, SIGNED
);
1073 mpz_sub_ui (g
, g
, 1);
1074 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1075 x
= isl_pw_aff_ge_set (approx
, aff
);
1076 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1077 isl_set_dim (x
, isl_dim_set
));
1078 scop
->context
= isl_set_intersect (scop
->context
, x
);
1080 c
= isl_inequality_alloc
1081 (isl_local_space_from_space (isl_space_copy (space
)));
1082 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1083 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1085 c
= isl_constraint_set_constant_val (c
, v
);
1086 inner
= isl_set_add_constraint (inner
, c
);
1089 isl_pw_aff_free (aff
);
1094 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1095 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1096 isl_set_copy (inner
), doms
);
1100 && loop_in_sese_p (loop
->next
, region
))
1101 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1102 isl_set_copy (outer
), doms
);
1104 doms
[loop
->num
] = inner
;
1106 isl_set_free (outer
);
1107 isl_space_free (space
);
1111 /* Returns a linear expression for tree T evaluated in PBB. */
1114 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1116 scop_p scop
= PBB_SCOP (pbb
);
1118 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1119 gcc_assert (!automatically_generated_chrec_p (t
));
1121 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1124 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1125 operator. This allows us to invert the condition or to handle
1129 add_condition_to_pbb (poly_bb_p pbb
, gcond
*stmt
, enum tree_code code
)
1131 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1132 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1138 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1142 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1146 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1150 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1154 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1158 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1162 isl_pw_aff_free (lhs
);
1163 isl_pw_aff_free (rhs
);
1167 cond
= isl_set_coalesce (cond
);
1168 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1169 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1172 /* Add conditions to the domain of PBB. */
1175 add_conditions_to_domain (poly_bb_p pbb
)
1179 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1181 if (GBB_CONDITIONS (gbb
).is_empty ())
1184 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1185 switch (gimple_code (stmt
))
1189 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
1190 enum tree_code code
= gimple_cond_code (cond_stmt
);
1192 /* The conditions for ELSE-branches are inverted. */
1193 if (!GBB_CONDITION_CASES (gbb
)[i
])
1194 code
= invert_tree_comparison (code
, false);
1196 add_condition_to_pbb (pbb
, cond_stmt
, code
);
1201 /* Switch statements are not supported right now - fall through. */
1209 /* Traverses all the GBBs of the SCOP and add their constraints to the
1210 iteration domains. */
1213 add_conditions_to_constraints (scop_p scop
)
1218 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1219 add_conditions_to_domain (pbb
);
1222 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1223 edge between BB and its predecessor is not a loop exit edge, and
1224 the last statement of the single predecessor is a COND_EXPR. */
1227 single_pred_cond_non_loop_exit (basic_block bb
)
1229 if (single_pred_p (bb
))
1231 edge e
= single_pred_edge (bb
);
1232 basic_block pred
= e
->src
;
1235 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1238 stmt
= last_stmt (pred
);
1240 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1241 return as_a
<gcond
*> (stmt
);
1247 class sese_dom_walker
: public dom_walker
1250 sese_dom_walker (cdi_direction
, sese
);
1252 virtual void before_dom_children (basic_block
);
1253 virtual void after_dom_children (basic_block
);
1256 auto_vec
<gimple
, 3> m_conditions
, m_cases
;
1260 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1261 : dom_walker (direction
), m_region (region
)
1265 /* Call-back for dom_walk executed before visiting the dominated
1269 sese_dom_walker::before_dom_children (basic_block bb
)
1274 if (!bb_in_sese_p (bb
, m_region
))
1277 stmt
= single_pred_cond_non_loop_exit (bb
);
1281 edge e
= single_pred_edge (bb
);
1283 m_conditions
.safe_push (stmt
);
1285 if (e
->flags
& EDGE_TRUE_VALUE
)
1286 m_cases
.safe_push (stmt
);
1288 m_cases
.safe_push (NULL
);
1291 gbb
= gbb_from_bb (bb
);
1295 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1296 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1300 /* Call-back for dom_walk executed after visiting the dominated
1304 sese_dom_walker::after_dom_children (basic_block bb
)
1306 if (!bb_in_sese_p (bb
, m_region
))
1309 if (single_pred_cond_non_loop_exit (bb
))
1311 m_conditions
.pop ();
1316 /* Add constraints on the possible values of parameter P from the type
1320 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1322 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1323 tree type
= TREE_TYPE (parameter
);
1324 tree lb
= NULL_TREE
;
1325 tree ub
= NULL_TREE
;
1327 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1328 lb
= lower_bound_in_type (type
, type
);
1330 lb
= TYPE_MIN_VALUE (type
);
1332 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1333 ub
= upper_bound_in_type (type
, type
);
1335 ub
= TYPE_MAX_VALUE (type
);
1339 isl_space
*space
= isl_set_get_space (scop
->context
);
1344 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1346 tree_int_to_gmp (lb
, g
);
1347 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1348 v
= isl_val_neg (v
);
1350 c
= isl_constraint_set_constant_val (c
, v
);
1351 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1353 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1358 isl_space
*space
= isl_set_get_space (scop
->context
);
1363 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1366 tree_int_to_gmp (ub
, g
);
1367 v
= isl_val_int_from_gmp (the_isl_ctx
, g
);
1369 c
= isl_constraint_set_constant_val (c
, v
);
1370 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1372 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1376 /* Build the context of the SCOP. The context usually contains extra
1377 constraints that are added to the iteration domains that constrain
1381 build_scop_context (scop_p scop
)
1383 graphite_dim_t p
, n
= scop_nb_params (scop
);
1385 for (p
= 0; p
< n
; p
++)
1386 add_param_constraints (scop
, p
);
1389 /* Build the iteration domains: the loops belonging to the current
1390 SCOP, and that vary for the execution of the current basic block.
1391 Returns false if there is no loop in SCOP. */
1394 build_scop_iteration_domain (scop_p scop
)
1397 sese region
= SCOP_REGION (scop
);
1400 int nb_loops
= number_of_loops (cfun
);
1401 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1403 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1404 if (!loop_in_sese_p (loop_outer (loop
), region
))
1405 build_loop_iteration_domains (scop
, loop
, 0,
1406 isl_set_copy (scop
->context
), doms
);
1408 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1410 loop
= pbb_loop (pbb
);
1412 if (doms
[loop
->num
])
1413 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1415 pbb
->domain
= isl_set_copy (scop
->context
);
1417 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1418 isl_id_for_pbb (scop
, pbb
));
1421 for (i
= 0; i
< nb_loops
; i
++)
1423 isl_set_free (doms
[i
]);
1428 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1429 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1430 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1434 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1437 int alias_set_num
= 0;
1438 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1440 if (bap
&& bap
->alias_set
)
1441 alias_set_num
= *(bap
->alias_set
);
1443 c
= isl_equality_alloc
1444 (isl_local_space_from_space (isl_map_get_space (acc
)));
1445 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1446 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1448 return isl_map_add_constraint (acc
, c
);
1451 /* Assign the affine expression INDEX to the output dimension POS of
1452 MAP and return the result. */
1455 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1458 int len
= isl_map_dim (map
, isl_dim_out
);
1461 index_map
= isl_map_from_pw_aff (index
);
1462 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1463 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1465 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1466 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1467 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1468 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1470 return isl_map_intersect (map
, index_map
);
1473 /* Add to ACCESSES polyhedron equalities defining the access functions
1474 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1475 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1476 PBB is the poly_bb_p that contains the data reference DR. */
1479 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1481 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1482 scop_p scop
= PBB_SCOP (pbb
);
1484 for (i
= 0; i
< nb_subscripts
; i
++)
1487 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1489 aff
= extract_affine (scop
, afn
,
1490 isl_space_domain (isl_map_get_space (acc
)));
1491 acc
= set_index (acc
, i
+ 1, aff
);
1497 /* Add constrains representing the size of the accessed data to the
1498 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1499 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1503 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1505 tree ref
= DR_REF (dr
);
1506 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1508 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1512 if (TREE_CODE (ref
) != ARRAY_REF
)
1515 low
= array_ref_low_bound (ref
);
1516 high
= array_ref_up_bound (ref
);
1518 /* XXX The PPL code dealt separately with
1519 subscript - low >= 0 and high - subscript >= 0 in case one of
1520 the two bounds isn't known. Do the same here? */
1522 if (tree_fits_shwi_p (low
)
1524 && tree_fits_shwi_p (high
)
1525 /* 1-element arrays at end of structures may extend over
1526 their declared size. */
1527 && !(array_at_struct_end_p (ref
)
1528 && operand_equal_p (low
, high
, 0)))
1532 isl_set
*univ
, *lbs
, *ubs
;
1536 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1537 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1540 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1541 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1542 isl_set_dim (valid
, isl_dim_set
));
1543 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1545 space
= isl_set_get_space (extent
);
1546 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1547 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1548 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1549 index
= isl_pw_aff_alloc (univ
, aff
);
1551 id
= isl_set_get_tuple_id (extent
);
1552 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1553 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1555 /* low <= sub_i <= high */
1556 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1557 ubs
= isl_pw_aff_le_set (index
, ub
);
1558 extent
= isl_set_intersect (extent
, lbs
);
1559 extent
= isl_set_intersect (extent
, ubs
);
1566 /* Build data accesses for DR in PBB. */
1569 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1571 int dr_base_object_set
;
1574 scop_p scop
= PBB_SCOP (pbb
);
1577 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1578 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1579 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1580 isl_dim_out
, nb_out
);
1582 acc
= isl_map_universe (space
);
1583 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1586 acc
= pdr_add_alias_set (acc
, dr
);
1587 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1590 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1591 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1592 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1593 int alias_set_num
= 0;
1594 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1596 if (bap
&& bap
->alias_set
)
1597 alias_set_num
= *(bap
->alias_set
);
1599 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1600 extent
= isl_set_nat_universe (space
);
1601 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1602 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1605 gcc_assert (dr
->aux
);
1606 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1608 new_poly_dr (pbb
, dr_base_object_set
,
1609 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1610 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1613 /* Write to FILE the alias graph of data references in DIMACS format. */
1616 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1617 vec
<data_reference_p
> drs
)
1619 int num_vertex
= drs
.length ();
1621 data_reference_p dr1
, dr2
;
1624 if (num_vertex
== 0)
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))
1632 fprintf (file
, "$\n");
1635 fprintf (file
, "c %s\n", comment
);
1637 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1639 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1640 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1641 if (dr_may_alias_p (dr1
, dr2
, true))
1642 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1647 /* Write to FILE the alias graph of data references in DOT format. */
1650 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1651 vec
<data_reference_p
> drs
)
1653 int num_vertex
= drs
.length ();
1654 data_reference_p dr1
, dr2
;
1657 if (num_vertex
== 0)
1660 fprintf (file
, "$\n");
1663 fprintf (file
, "c %s\n", comment
);
1665 /* First print all the vertices. */
1666 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1667 fprintf (file
, "n%d;\n", i
);
1669 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1670 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1671 if (dr_may_alias_p (dr1
, dr2
, true))
1672 fprintf (file
, "n%d n%d\n", i
, j
);
1677 /* Write to FILE the alias graph of data references in ECC format. */
1680 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1681 vec
<data_reference_p
> drs
)
1683 int num_vertex
= drs
.length ();
1684 data_reference_p dr1
, dr2
;
1687 if (num_vertex
== 0)
1690 fprintf (file
, "$\n");
1693 fprintf (file
, "c %s\n", comment
);
1695 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1696 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1697 if (dr_may_alias_p (dr1
, dr2
, true))
1698 fprintf (file
, "%d %d\n", i
, j
);
1703 /* Check if DR1 and DR2 are in the same object set. */
1706 dr_same_base_object_p (const struct data_reference
*dr1
,
1707 const struct data_reference
*dr2
)
1709 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1712 /* Uses DFS component number as representative of alias-sets. Also tests for
1713 optimality by verifying if every connected component is a clique. Returns
1714 true (1) if the above test is true, and false (0) otherwise. */
1717 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1719 int num_vertices
= drs
.length ();
1720 struct graph
*g
= new_graph (num_vertices
);
1721 data_reference_p dr1
, dr2
;
1723 int num_connected_components
;
1724 int v_indx1
, v_indx2
, num_vertices_in_component
;
1727 struct graph_edge
*e
;
1728 int this_component_is_clique
;
1729 int all_components_are_cliques
= 1;
1731 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1732 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1733 if (dr_may_alias_p (dr1
, dr2
, true))
1739 all_vertices
= XNEWVEC (int, num_vertices
);
1740 vertices
= XNEWVEC (int, num_vertices
);
1741 for (i
= 0; i
< num_vertices
; i
++)
1742 all_vertices
[i
] = i
;
1744 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1746 for (i
= 0; i
< g
->n_vertices
; i
++)
1748 data_reference_p dr
= drs
[i
];
1749 base_alias_pair
*bap
;
1751 gcc_assert (dr
->aux
);
1752 bap
= (base_alias_pair
*)(dr
->aux
);
1754 bap
->alias_set
= XNEW (int);
1755 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1758 /* Verify if the DFS numbering results in optimal solution. */
1759 for (i
= 0; i
< num_connected_components
; i
++)
1761 num_vertices_in_component
= 0;
1762 /* Get all vertices whose DFS component number is the same as i. */
1763 for (j
= 0; j
< num_vertices
; j
++)
1764 if (g
->vertices
[j
].component
== i
)
1765 vertices
[num_vertices_in_component
++] = j
;
1767 /* Now test if the vertices in 'vertices' form a clique, by testing
1768 for edges among each pair. */
1769 this_component_is_clique
= 1;
1770 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1772 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1774 /* Check if the two vertices are connected by iterating
1775 through all the edges which have one of these are source. */
1776 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1779 if (e
->src
== vertices
[v_indx1
])
1785 this_component_is_clique
= 0;
1789 if (!this_component_is_clique
)
1790 all_components_are_cliques
= 0;
1794 free (all_vertices
);
1797 return all_components_are_cliques
;
1800 /* Group each data reference in DRS with its base object set num. */
1803 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1805 int num_vertex
= drs
.length ();
1806 struct graph
*g
= new_graph (num_vertex
);
1807 data_reference_p dr1
, dr2
;
1811 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1812 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1813 if (dr_same_base_object_p (dr1
, dr2
))
1819 queue
= XNEWVEC (int, num_vertex
);
1820 for (i
= 0; i
< num_vertex
; i
++)
1823 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1825 for (i
= 0; i
< g
->n_vertices
; i
++)
1827 data_reference_p dr
= drs
[i
];
1828 base_alias_pair
*bap
;
1830 gcc_assert (dr
->aux
);
1831 bap
= (base_alias_pair
*)(dr
->aux
);
1833 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1840 /* Build the data references for PBB. */
1843 build_pbb_drs (poly_bb_p pbb
)
1846 data_reference_p dr
;
1847 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1849 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1850 build_poly_dr (dr
, pbb
);
1853 /* Dump to file the alias graphs for the data references in DRS. */
1856 dump_alias_graphs (vec
<data_reference_p
> drs
)
1859 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1861 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1864 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1865 current_function_name ());
1866 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1867 fclose (file_dimacs
);
1870 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1873 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1874 current_function_name ());
1875 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1879 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1882 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1883 current_function_name ());
1884 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1889 /* Build data references in SCOP. */
1892 build_scop_drs (scop_p scop
)
1896 data_reference_p dr
;
1897 auto_vec
<data_reference_p
, 3> drs
;
1899 /* Remove all the PBBs that do not have data references: these basic
1900 blocks are not handled in the polyhedral representation. */
1901 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1902 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1904 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1906 SCOP_BBS (scop
).ordered_remove (i
);
1910 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1911 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1914 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1915 dr
->aux
= XNEW (base_alias_pair
);
1917 if (!build_alias_set_optimal_p (drs
))
1919 /* TODO: Add support when building alias set is not optimal. */
1923 build_base_obj_set_for_drs (drs
);
1925 /* When debugging, enable the following code. This cannot be used
1926 in production compilers. */
1928 dump_alias_graphs (drs
);
1932 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1933 build_pbb_drs (pbb
);
1936 /* Return a gsi at the position of the phi node STMT. */
1938 static gphi_iterator
1939 gsi_for_phi_node (gphi
*stmt
)
1942 basic_block bb
= gimple_bb (stmt
);
1944 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1945 if (stmt
== psi
.phi ())
1952 /* Analyze all the data references of STMTS and add them to the
1953 GBB_DATA_REFS vector of BB. */
1956 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1962 sese region
= SCOP_REGION (scop
);
1964 if (!bb_in_sese_p (bb
, region
))
1967 nest
= outermost_loop_in_sese_1 (region
, bb
);
1968 gbb
= gbb_from_bb (bb
);
1970 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1974 if (is_gimple_debug (stmt
))
1977 loop
= loop_containing_stmt (stmt
);
1978 if (!loop_in_sese_p (loop
, region
))
1981 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1982 &GBB_DATA_REFS (gbb
));
1986 /* Insert STMT at the end of the STMTS sequence and then insert the
1987 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1991 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1992 gimple_stmt_iterator insert_gsi
)
1994 gimple_stmt_iterator gsi
;
1995 auto_vec
<gimple
, 3> x
;
1997 gimple_seq_add_stmt (&stmts
, stmt
);
1998 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1999 x
.safe_push (gsi_stmt (gsi
));
2001 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2002 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2005 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2008 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2011 gimple_stmt_iterator gsi
;
2012 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2013 gassign
*stmt
= gimple_build_assign (unshare_expr (res
), var
);
2014 auto_vec
<gimple
, 3> x
;
2016 gimple_seq_add_stmt (&stmts
, stmt
);
2017 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2018 x
.safe_push (gsi_stmt (gsi
));
2020 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2022 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2023 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2027 gsi
= gsi_for_stmt (after_stmt
);
2028 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2031 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2034 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2037 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2039 vec
<data_reference_p
> drs
;
2041 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2042 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2043 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2044 int index
, n
= SCOP_BBS (scop
).length ();
2046 /* The INDEX of PBB in SCOP_BBS. */
2047 for (index
= 0; index
< n
; index
++)
2048 if (SCOP_BBS (scop
)[index
] == pbb
)
2051 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2052 pbb1
->domain
= isl_set_set_tuple_id (pbb1
->domain
,
2053 isl_id_for_pbb (scop
, pbb1
));
2055 GBB_PBB (gbb1
) = pbb1
;
2056 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2057 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2058 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2061 /* Insert on edge E the assignment "RES := EXPR". */
2064 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2066 gimple_stmt_iterator gsi
;
2067 gimple_seq stmts
= NULL
;
2068 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2069 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2071 auto_vec
<gimple
, 3> x
;
2073 gimple_seq_add_stmt (&stmts
, stmt
);
2074 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2075 x
.safe_push (gsi_stmt (gsi
));
2077 gsi_insert_seq_on_edge (e
, stmts
);
2078 gsi_commit_edge_inserts ();
2079 bb
= gimple_bb (stmt
);
2081 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2084 if (!gbb_from_bb (bb
))
2085 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2087 analyze_drs_in_stmts (scop
, bb
, x
);
2090 /* Creates a zero dimension array of the same type as VAR. */
2093 create_zero_dim_array (tree var
, const char *base_name
)
2095 tree index_type
= build_index_type (integer_zero_node
);
2096 tree elt_type
= TREE_TYPE (var
);
2097 tree array_type
= build_array_type (elt_type
, index_type
);
2098 tree base
= create_tmp_var (array_type
, base_name
);
2100 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2104 /* Returns true when PHI is a loop close phi node. */
2107 scalar_close_phi_node_p (gimple phi
)
2109 if (gimple_code (phi
) != GIMPLE_PHI
2110 || virtual_operand_p (gimple_phi_result (phi
)))
2113 /* Note that loop close phi nodes should have a single argument
2114 because we translated the representation into a canonical form
2115 before Graphite: see canonicalize_loop_closed_ssa_form. */
2116 return (gimple_phi_num_args (phi
) == 1);
2119 /* For a definition DEF in REGION, propagates the expression EXPR in
2120 all the uses of DEF outside REGION. */
2123 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2125 imm_use_iterator imm_iter
;
2128 bool replaced_once
= false;
2130 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2132 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2135 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2136 if (!is_gimple_debug (use_stmt
)
2137 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2140 use_operand_p use_p
;
2142 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2143 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2144 && (replaced_once
= true))
2145 replace_exp (use_p
, expr
);
2147 update_stmt (use_stmt
);
2152 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2153 gsi_commit_edge_inserts ();
2157 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2158 dimension array for it. */
2161 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2163 sese region
= SCOP_REGION (scop
);
2164 gimple phi
= gsi_stmt (*psi
);
2165 tree res
= gimple_phi_result (phi
);
2166 basic_block bb
= gimple_bb (phi
);
2167 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2168 tree arg
= gimple_phi_arg_def (phi
, 0);
2171 /* Note that loop close phi nodes should have a single argument
2172 because we translated the representation into a canonical form
2173 before Graphite: see canonicalize_loop_closed_ssa_form. */
2174 gcc_assert (gimple_phi_num_args (phi
) == 1);
2176 /* The phi node can be a non close phi node, when its argument is
2177 invariant, or a default definition. */
2178 if (is_gimple_min_invariant (arg
)
2179 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2181 propagate_expr_outside_region (res
, arg
, region
);
2186 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2188 propagate_expr_outside_region (res
, arg
, region
);
2189 stmt
= gimple_build_assign (res
, arg
);
2190 remove_phi_node (psi
, false);
2191 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2195 /* If res is scev analyzable and is not a scalar value, it is safe
2196 to ignore the close phi node: it will be code generated in the
2197 out of Graphite pass. */
2198 else if (scev_analyzable_p (res
, region
))
2200 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2203 if (!loop_in_sese_p (loop
, region
))
2205 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2206 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2207 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2210 scev
= scalar_evolution_in_region (region
, loop
, res
);
2212 if (tree_does_not_contain_chrecs (scev
))
2213 propagate_expr_outside_region (res
, scev
, region
);
2220 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2222 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2224 if (TREE_CODE (arg
) == SSA_NAME
)
2225 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2226 SSA_NAME_DEF_STMT (arg
));
2228 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2229 zero_dim_array
, arg
);
2232 remove_phi_node (psi
, false);
2233 SSA_NAME_DEF_STMT (res
) = stmt
;
2235 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2238 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2239 dimension array for it. */
2242 rewrite_phi_out_of_ssa (scop_p scop
, gphi_iterator
*psi
)
2245 gphi
*phi
= psi
->phi ();
2246 basic_block bb
= gimple_bb (phi
);
2247 tree res
= gimple_phi_result (phi
);
2248 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2251 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2253 tree arg
= gimple_phi_arg_def (phi
, i
);
2254 edge e
= gimple_phi_arg_edge (phi
, i
);
2256 /* Avoid the insertion of code in the loop latch to please the
2257 pattern matching of the vectorizer. */
2258 if (TREE_CODE (arg
) == SSA_NAME
2259 && !SSA_NAME_IS_DEFAULT_DEF (arg
)
2260 && e
->src
== bb
->loop_father
->latch
)
2261 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2262 SSA_NAME_DEF_STMT (arg
));
2264 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2267 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2268 remove_phi_node (psi
, false);
2269 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2272 /* Rewrite the degenerate phi node at position PSI from the degenerate
2273 form "x = phi (y, y, ..., y)" to "x = y". */
2276 rewrite_degenerate_phi (gphi_iterator
*psi
)
2280 gimple_stmt_iterator gsi
;
2281 gphi
*phi
= psi
->phi ();
2282 tree res
= gimple_phi_result (phi
);
2285 bb
= gimple_bb (phi
);
2286 rhs
= degenerate_phi_result (phi
);
2289 stmt
= gimple_build_assign (res
, rhs
);
2290 remove_phi_node (psi
, false);
2292 gsi
= gsi_after_labels (bb
);
2293 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2296 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2299 rewrite_reductions_out_of_ssa (scop_p scop
)
2303 sese region
= SCOP_REGION (scop
);
2305 FOR_EACH_BB_FN (bb
, cfun
)
2306 if (bb_in_sese_p (bb
, region
))
2307 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2309 gphi
*phi
= psi
.phi ();
2311 if (virtual_operand_p (gimple_phi_result (phi
)))
2317 if (gimple_phi_num_args (phi
) > 1
2318 && degenerate_phi_result (phi
))
2319 rewrite_degenerate_phi (&psi
);
2321 else if (scalar_close_phi_node_p (phi
))
2322 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2324 else if (reduction_phi_p (region
, &psi
))
2325 rewrite_phi_out_of_ssa (scop
, &psi
);
2328 update_ssa (TODO_update_ssa
);
2329 #ifdef ENABLE_CHECKING
2330 verify_loop_closed_ssa (true);
2334 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2335 read from ZERO_DIM_ARRAY. */
2338 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2339 tree def
, gimple use_stmt
)
2344 use_operand_p use_p
;
2346 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2348 name
= copy_ssa_name (def
);
2349 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2351 gimple_assign_set_lhs (name_stmt
, name
);
2352 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2354 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2355 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2356 replace_exp (use_p
, name
);
2358 update_stmt (use_stmt
);
2361 /* For every definition DEF in the SCOP that is used outside the scop,
2362 insert a closing-scop definition in the basic block just after this
2366 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2368 tree var
= create_tmp_reg (TREE_TYPE (def
));
2369 tree new_name
= make_ssa_name (var
, stmt
);
2370 bool needs_copy
= false;
2371 use_operand_p use_p
;
2372 imm_use_iterator imm_iter
;
2374 sese region
= SCOP_REGION (scop
);
2376 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2378 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2380 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2382 SET_USE (use_p
, new_name
);
2384 update_stmt (use_stmt
);
2389 /* Insert in the empty BB just after the scop a use of DEF such
2390 that the rewrite of cross_bb_scalar_dependences won't insert
2391 arrays everywhere else. */
2394 gimple assign
= gimple_build_assign (new_name
, def
);
2395 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2397 update_stmt (assign
);
2398 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2402 /* Rewrite the scalar dependences crossing the boundary of the BB
2403 containing STMT with an array. Return true when something has been
2407 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2409 sese region
= SCOP_REGION (scop
);
2410 gimple stmt
= gsi_stmt (*gsi
);
2411 imm_use_iterator imm_iter
;
2414 tree zero_dim_array
= NULL_TREE
;
2418 switch (gimple_code (stmt
))
2421 def
= gimple_assign_lhs (stmt
);
2425 def
= gimple_call_lhs (stmt
);
2433 || !is_gimple_reg (def
))
2436 if (scev_analyzable_p (def
, region
))
2438 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2439 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2441 if (tree_contains_chrecs (scev
, NULL
))
2444 propagate_expr_outside_region (def
, scev
, region
);
2448 def_bb
= gimple_bb (stmt
);
2450 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2452 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2453 if (gimple_code (use_stmt
) == GIMPLE_PHI
2456 gphi_iterator psi
= gsi_start_phis (gimple_bb (use_stmt
));
2458 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2459 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2461 rewrite_phi_out_of_ssa (scop
, &psi
);
2464 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2465 if (gimple_code (use_stmt
) != GIMPLE_PHI
2466 && def_bb
!= gimple_bb (use_stmt
)
2467 && !is_gimple_debug (use_stmt
)
2470 if (!zero_dim_array
)
2472 zero_dim_array
= create_zero_dim_array
2473 (def
, "Cross_BB_scalar_dependence");
2474 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2475 SSA_NAME_DEF_STMT (def
));
2479 rewrite_cross_bb_scalar_dependence (scop
, unshare_expr (zero_dim_array
),
2486 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2489 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2492 gimple_stmt_iterator psi
;
2493 sese region
= SCOP_REGION (scop
);
2494 bool changed
= false;
2496 /* Create an extra empty BB after the scop. */
2497 split_edge (SESE_EXIT (region
));
2499 FOR_EACH_BB_FN (bb
, cfun
)
2500 if (bb_in_sese_p (bb
, region
))
2501 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2502 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2507 update_ssa (TODO_update_ssa
);
2508 #ifdef ENABLE_CHECKING
2509 verify_loop_closed_ssa (true);
2514 /* Returns the number of pbbs that are in loops contained in SCOP. */
2517 nb_pbbs_in_loops (scop_p scop
)
2523 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2524 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2530 /* Return the number of data references in BB that write in
2534 nb_data_writes_in_bb (basic_block bb
)
2537 gimple_stmt_iterator gsi
;
2539 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2540 if (gimple_vdef (gsi_stmt (gsi
)))
2546 /* Splits at STMT the basic block BB represented as PBB in the
2550 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2552 edge e1
= split_block (bb
, stmt
);
2553 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2557 /* Splits STMT out of its current BB. This is done for reduction
2558 statements for which we want to ignore data dependences. */
2561 split_reduction_stmt (scop_p scop
, gimple stmt
)
2563 basic_block bb
= gimple_bb (stmt
);
2564 poly_bb_p pbb
= pbb_from_bb (bb
);
2565 gimple_bb_p gbb
= gbb_from_bb (bb
);
2568 data_reference_p dr
;
2570 /* Do not split basic blocks with no writes to memory: the reduction
2571 will be the only write to memory. */
2572 if (nb_data_writes_in_bb (bb
) == 0
2573 /* Or if we have already marked BB as a reduction. */
2574 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2577 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2579 /* Split once more only when the reduction stmt is not the only one
2580 left in the original BB. */
2581 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2583 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2585 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2588 /* A part of the data references will end in a different basic block
2589 after the split: move the DRs from the original GBB to the newly
2591 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2593 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2597 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2598 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2599 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2607 /* Return true when stmt is a reduction operation. */
2610 is_reduction_operation_p (gimple stmt
)
2612 enum tree_code code
;
2614 gcc_assert (is_gimple_assign (stmt
));
2615 code
= gimple_assign_rhs_code (stmt
);
2617 return flag_associative_math
2618 && commutative_tree_code (code
)
2619 && associative_tree_code (code
);
2622 /* Returns true when PHI contains an argument ARG. */
2625 phi_contains_arg (gphi
*phi
, tree arg
)
2629 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2630 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2636 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2639 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2643 if (TREE_CODE (arg
) != SSA_NAME
)
2646 stmt
= SSA_NAME_DEF_STMT (arg
);
2648 if (gimple_code (stmt
) == GIMPLE_NOP
2649 || gimple_code (stmt
) == GIMPLE_CALL
)
2652 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2654 if (phi_contains_arg (phi
, lhs
))
2659 if (!is_gimple_assign (stmt
))
2662 if (gimple_num_ops (stmt
) == 2)
2663 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2665 if (is_reduction_operation_p (stmt
))
2668 = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2671 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2677 /* Detect commutative and associative scalar reductions starting at
2678 the STMT. Return the phi node of the reduction cycle, or NULL. */
2681 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2685 gphi
*phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2690 in
->safe_push (stmt
);
2691 out
->safe_push (stmt
);
2695 /* Detect commutative and associative scalar reductions starting at
2696 STMT. Return the phi node of the reduction cycle, or NULL. */
2699 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2702 tree lhs
= gimple_assign_lhs (stmt
);
2704 if (gimple_num_ops (stmt
) == 2)
2705 return detect_commutative_reduction_arg (lhs
, stmt
,
2706 gimple_assign_rhs1 (stmt
),
2709 if (is_reduction_operation_p (stmt
))
2711 gphi
*res
= detect_commutative_reduction_arg (lhs
, stmt
,
2712 gimple_assign_rhs1 (stmt
),
2715 : detect_commutative_reduction_arg (lhs
, stmt
,
2716 gimple_assign_rhs2 (stmt
),
2723 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2726 follow_inital_value_to_phi (tree arg
, tree lhs
)
2730 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2733 stmt
= SSA_NAME_DEF_STMT (arg
);
2735 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
2736 if (phi_contains_arg (phi
, lhs
))
2743 /* Return the argument of the loop PHI that is the initial value coming
2744 from outside the loop. */
2747 edge_initial_value_for_loop_phi (gphi
*phi
)
2751 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2753 edge e
= gimple_phi_arg_edge (phi
, i
);
2755 if (loop_depth (e
->src
->loop_father
)
2756 < loop_depth (e
->dest
->loop_father
))
2763 /* Return the argument of the loop PHI that is the initial value coming
2764 from outside the loop. */
2767 initial_value_for_loop_phi (gphi
*phi
)
2771 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2773 edge e
= gimple_phi_arg_edge (phi
, i
);
2775 if (loop_depth (e
->src
->loop_father
)
2776 < loop_depth (e
->dest
->loop_father
))
2777 return gimple_phi_arg_def (phi
, i
);
2783 /* Returns true when DEF is used outside the reduction cycle of
2787 used_outside_reduction (tree def
, gimple loop_phi
)
2789 use_operand_p use_p
;
2790 imm_use_iterator imm_iter
;
2791 loop_p loop
= loop_containing_stmt (loop_phi
);
2793 /* In LOOP, DEF should be used only in LOOP_PHI. */
2794 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2796 gimple stmt
= USE_STMT (use_p
);
2798 if (stmt
!= loop_phi
2799 && !is_gimple_debug (stmt
)
2800 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2807 /* Detect commutative and associative scalar reductions belonging to
2808 the SCOP starting at the loop closed phi node STMT. Return the phi
2809 node of the reduction cycle, or NULL. */
2812 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2815 if (scalar_close_phi_node_p (stmt
))
2818 gphi
*loop_phi
, *phi
, *close_phi
= as_a
<gphi
*> (stmt
);
2819 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2821 if (TREE_CODE (arg
) != SSA_NAME
)
2824 /* Note that loop close phi nodes should have a single argument
2825 because we translated the representation into a canonical form
2826 before Graphite: see canonicalize_loop_closed_ssa_form. */
2827 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2829 def
= SSA_NAME_DEF_STMT (arg
);
2830 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2831 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2834 lhs
= gimple_phi_result (close_phi
);
2835 init
= initial_value_for_loop_phi (loop_phi
);
2836 phi
= follow_inital_value_to_phi (init
, lhs
);
2838 if (phi
&& (used_outside_reduction (lhs
, phi
)
2839 || !has_single_use (gimple_phi_result (phi
))))
2842 in
->safe_push (loop_phi
);
2843 out
->safe_push (close_phi
);
2847 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2848 return detect_commutative_reduction_assign (stmt
, in
, out
);
2853 /* Translate the scalar reduction statement STMT to an array RED
2854 knowing that its recursive phi node is LOOP_PHI. */
2857 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2858 gimple stmt
, gphi
*loop_phi
)
2860 tree res
= gimple_phi_result (loop_phi
);
2861 gassign
*assign
= gimple_build_assign (res
, unshare_expr (red
));
2862 gimple_stmt_iterator gsi
;
2864 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2866 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2867 gsi
= gsi_for_stmt (stmt
);
2869 insert_stmts (scop
, assign
, NULL
, gsi
);
2872 /* Removes the PHI node and resets all the debug stmts that are using
2876 remove_phi (gphi
*phi
)
2878 imm_use_iterator imm_iter
;
2880 use_operand_p use_p
;
2881 gimple_stmt_iterator gsi
;
2882 auto_vec
<gimple
, 3> update
;
2886 def
= PHI_RESULT (phi
);
2887 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2889 stmt
= USE_STMT (use_p
);
2891 if (is_gimple_debug (stmt
))
2893 gimple_debug_bind_reset_value (stmt
);
2894 update
.safe_push (stmt
);
2898 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2901 gsi
= gsi_for_phi_node (phi
);
2902 remove_phi_node (&gsi
, false);
2905 /* Helper function for for_each_index. For each INDEX of the data
2906 reference REF, returns true when its indices are valid in the loop
2907 nest LOOP passed in as DATA. */
2910 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2913 basic_block header
, def_bb
;
2916 if (TREE_CODE (*index
) != SSA_NAME
)
2919 loop
= *((loop_p
*) data
);
2920 header
= loop
->header
;
2921 stmt
= SSA_NAME_DEF_STMT (*index
);
2926 def_bb
= gimple_bb (stmt
);
2931 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2934 /* When the result of a CLOSE_PHI is written to a memory location,
2935 return a pointer to that memory reference, otherwise return
2939 close_phi_written_to_memory (gphi
*close_phi
)
2941 imm_use_iterator imm_iter
;
2942 use_operand_p use_p
;
2944 tree res
, def
= gimple_phi_result (close_phi
);
2946 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2947 if ((stmt
= USE_STMT (use_p
))
2948 && gimple_code (stmt
) == GIMPLE_ASSIGN
2949 && (res
= gimple_assign_lhs (stmt
)))
2951 switch (TREE_CODE (res
))
2961 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2962 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2964 /* FIXME: this restriction is for id-{24,25}.f and
2965 could be handled by duplicating the computation of
2966 array indices before the loop of the close_phi. */
2967 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2979 /* Rewrite out of SSA the reduction described by the loop phi nodes
2980 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2983 IN: stmt, loop_n, ..., loop_0
2984 OUT: stmt, close_n, ..., close_0
2986 the first element is the reduction statement, and the next elements
2987 are the loop and close phi nodes of each of the outer loops. */
2990 translate_scalar_reduction_to_array (scop_p scop
,
2995 unsigned int i
= out
.length () - 1;
2996 tree red
= close_phi_written_to_memory (as_a
<gphi
*> (out
[i
]));
2998 FOR_EACH_VEC_ELT (in
, i
, loop_stmt
)
3000 gimple close_stmt
= out
[i
];
3004 basic_block bb
= split_reduction_stmt (scop
, loop_stmt
);
3005 poly_bb_p pbb
= pbb_from_bb (bb
);
3006 PBB_IS_REDUCTION (pbb
) = true;
3007 gcc_assert (close_stmt
== loop_stmt
);
3010 red
= create_zero_dim_array
3011 (gimple_assign_lhs (loop_stmt
), "Commutative_Associative_Reduction");
3013 translate_scalar_reduction_to_array_for_stmt (scop
, red
, loop_stmt
,
3014 as_a
<gphi
*> (in
[1]));
3018 gphi
*loop_phi
= as_a
<gphi
*> (loop_stmt
);
3019 gphi
*close_phi
= as_a
<gphi
*> (close_stmt
);
3021 if (i
== in
.length () - 1)
3023 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3024 unshare_expr (red
), close_phi
);
3025 insert_out_of_ssa_copy_on_edge
3026 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3027 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3030 remove_phi (loop_phi
);
3031 remove_phi (close_phi
);
3035 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3036 true when something has been changed. */
3039 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3043 auto_vec
<gimple
, 10> in
;
3044 auto_vec
<gimple
, 10> out
;
3046 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3047 res
= in
.length () > 1;
3049 translate_scalar_reduction_to_array (scop
, in
, out
);
3054 /* Rewrites all the commutative reductions from LOOP out of SSA.
3055 Returns true when something has been changed. */
3058 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3062 edge exit
= single_exit (loop
);
3064 bool changed
= false;
3069 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3070 if ((res
= gimple_phi_result (gsi
.phi ()))
3071 && !virtual_operand_p (res
)
3072 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3073 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3079 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3082 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3085 bool changed
= false;
3086 sese region
= SCOP_REGION (scop
);
3088 FOR_EACH_LOOP (loop
, 0)
3089 if (loop_in_sese_p (loop
, region
))
3090 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3095 gsi_commit_edge_inserts ();
3096 update_ssa (TODO_update_ssa
);
3097 #ifdef ENABLE_CHECKING
3098 verify_loop_closed_ssa (true);
3103 /* Can all ivs be represented by a signed integer?
3104 As CLooG might generate negative values in its expressions, signed loop ivs
3105 are required in the backend. */
3108 scop_ivs_can_be_represented (scop_p scop
)
3114 FOR_EACH_LOOP (loop
, 0)
3116 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3119 for (psi
= gsi_start_phis (loop
->header
);
3120 !gsi_end_p (psi
); gsi_next (&psi
))
3122 gphi
*phi
= psi
.phi ();
3123 tree res
= PHI_RESULT (phi
);
3124 tree type
= TREE_TYPE (res
);
3126 if (TYPE_UNSIGNED (type
)
3127 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3140 /* Builds the polyhedral representation for a SESE region. */
3143 build_poly_scop (scop_p scop
)
3145 sese region
= SCOP_REGION (scop
);
3146 graphite_dim_t max_dim
;
3148 build_scop_bbs (scop
);
3150 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3151 Once CLooG is fixed, remove this guard. Anyways, it makes no
3152 sense to optimize a scop containing only PBBs that do not belong
3154 if (nb_pbbs_in_loops (scop
) == 0)
3157 if (!scop_ivs_can_be_represented (scop
))
3160 if (flag_associative_math
)
3161 rewrite_commutative_reductions_out_of_ssa (scop
);
3163 build_sese_loop_nests (region
);
3164 /* Record all conditions in REGION. */
3165 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3166 find_scop_parameters (scop
);
3168 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3169 if (scop_nb_params (scop
) > max_dim
)
3172 build_scop_iteration_domain (scop
);
3173 build_scop_context (scop
);
3174 add_conditions_to_constraints (scop
);
3176 /* Rewrite out of SSA only after having translated the
3177 representation to the polyhedral representation to avoid scev
3178 analysis failures. That means that these functions will insert
3179 new data references that they create in the right place. */
3180 rewrite_reductions_out_of_ssa (scop
);
3181 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3183 build_scop_drs (scop
);
3185 build_scop_scattering (scop
);
3187 /* This SCoP has been translated to the polyhedral
3189 POLY_SCOP_P (scop
) = true;