1 /* Conversion of SESE regions to Polyhedra.
2 Copyright (C) 2009-2013 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>
29 #include <cloog/cloog.h>
30 #include <cloog/cloog.h>
31 #include <cloog/isl/domain.h>
35 #include "coretypes.h"
38 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "tree-ssanames.h"
43 #include "tree-ssa-loop-manip.h"
44 #include "tree-ssa-loop-niter.h"
45 #include "tree-ssa-loop.h"
46 #include "tree-into-ssa.h"
47 #include "tree-pass.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
54 #include "tree-ssa-propagate.h"
57 #include "graphite-poly.h"
58 #include "graphite-sese-to-poly.h"
61 /* Assigns to RES the value of the INTEGER_CST T. */
64 tree_int_to_gmp (tree t
, mpz_t res
)
66 double_int di
= tree_to_double_int (t
);
67 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
70 /* Returns the index of the PHI argument defined in the outermost
74 phi_arg_in_outermost_loop (gimple phi
)
76 loop_p loop
= gimple_bb (phi
)->loop_father
;
79 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
80 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
82 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
89 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
90 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
93 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
95 gimple phi
= gsi_stmt (*psi
);
96 tree res
= gimple_phi_result (phi
);
97 size_t entry
= phi_arg_in_outermost_loop (phi
);
98 tree init
= gimple_phi_arg_def (phi
, entry
);
99 gimple stmt
= gimple_build_assign (res
, init
);
100 edge e
= gimple_phi_arg_edge (phi
, entry
);
102 remove_phi_node (psi
, false);
103 gsi_insert_on_edge_immediate (e
, stmt
);
106 /* Removes an invariant phi node at position PSI by inserting on the
107 loop ENTRY edge the assignment RES = INIT. */
110 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
112 gimple phi
= gsi_stmt (*psi
);
113 loop_p loop
= loop_containing_stmt (phi
);
114 tree res
= gimple_phi_result (phi
);
115 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
116 size_t entry
= phi_arg_in_outermost_loop (phi
);
117 edge e
= gimple_phi_arg_edge (phi
, entry
);
120 gimple_seq stmts
= NULL
;
122 if (tree_contains_chrecs (scev
, NULL
))
123 scev
= gimple_phi_arg_def (phi
, entry
);
125 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
126 stmt
= gimple_build_assign (res
, var
);
127 remove_phi_node (psi
, false);
129 gimple_seq_add_stmt (&stmts
, stmt
);
130 gsi_insert_seq_on_edge (e
, stmts
);
131 gsi_commit_edge_inserts ();
132 SSA_NAME_DEF_STMT (res
) = stmt
;
135 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
138 simple_copy_phi_p (gimple phi
)
142 if (gimple_phi_num_args (phi
) != 2)
145 res
= gimple_phi_result (phi
);
146 return (res
== gimple_phi_arg_def (phi
, 0)
147 || res
== gimple_phi_arg_def (phi
, 1));
150 /* Returns true when the phi node at position PSI is a reduction phi
151 node in REGION. Otherwise moves the pointer PSI to the next phi to
155 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
158 gimple phi
= gsi_stmt (*psi
);
159 tree res
= gimple_phi_result (phi
);
161 loop
= loop_containing_stmt (phi
);
163 if (simple_copy_phi_p (phi
))
165 /* PRE introduces phi nodes like these, for an example,
166 see id-5.f in the fortran graphite testsuite:
168 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
170 remove_simple_copy_phi (psi
);
174 if (scev_analyzable_p (res
, region
))
176 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
178 if (evolution_function_is_invariant_p (scev
, loop
->num
))
179 remove_invariant_phi (region
, psi
);
186 /* All the other cases are considered reductions. */
190 /* Store the GRAPHITE representation of BB. */
193 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
195 struct gimple_bb
*gbb
;
197 gbb
= XNEW (struct gimple_bb
);
200 GBB_DATA_REFS (gbb
) = drs
;
201 GBB_CONDITIONS (gbb
).create (0);
202 GBB_CONDITION_CASES (gbb
).create (0);
208 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
211 struct data_reference
*dr
;
213 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
216 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
218 free (bap
->alias_set
);
227 free_gimple_bb (struct gimple_bb
*gbb
)
229 free_data_refs_aux (GBB_DATA_REFS (gbb
));
230 free_data_refs (GBB_DATA_REFS (gbb
));
232 GBB_CONDITIONS (gbb
).release ();
233 GBB_CONDITION_CASES (gbb
).release ();
234 GBB_BB (gbb
)->aux
= 0;
238 /* Deletes all gimple bbs in SCOP. */
241 remove_gbbs_in_scop (scop_p scop
)
246 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
247 free_gimple_bb (PBB_BLACK_BOX (pbb
));
250 /* Deletes all scops in SCOPS. */
253 free_scops (vec
<scop_p
> scops
)
258 FOR_EACH_VEC_ELT (scops
, i
, scop
)
260 remove_gbbs_in_scop (scop
);
261 free_sese (SCOP_REGION (scop
));
268 /* Same as outermost_loop_in_sese, returns the outermost loop
269 containing BB in REGION, but makes sure that the returned loop
270 belongs to the REGION, and so this returns the first loop in the
271 REGION when the loop containing BB does not belong to REGION. */
274 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
276 loop_p nest
= outermost_loop_in_sese (region
, bb
);
278 if (loop_in_sese_p (nest
, region
))
281 /* When the basic block BB does not belong to a loop in the region,
282 return the first loop in the region. */
285 if (loop_in_sese_p (nest
, region
))
294 /* Generates a polyhedral black box only if the bb contains interesting
298 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
300 vec
<data_reference_p
> drs
;
302 sese region
= SCOP_REGION (scop
);
303 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
304 gimple_stmt_iterator gsi
;
306 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
308 gimple stmt
= gsi_stmt (gsi
);
311 if (is_gimple_debug (stmt
))
314 loop
= loop_containing_stmt (stmt
);
315 if (!loop_in_sese_p (loop
, region
))
318 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
321 return new_gimple_bb (bb
, drs
);
324 /* Returns true if all predecessors of BB, that are not dominated by BB, are
325 marked in MAP. The predecessors dominated by BB are loop latches and will
326 be handled after BB. */
329 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
334 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
335 if (!bitmap_bit_p (map
, e
->src
->index
)
336 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
342 /* Compare the depth of two basic_block's P1 and P2. */
345 compare_bb_depths (const void *p1
, const void *p2
)
347 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
348 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
349 int d1
= loop_depth (bb1
->loop_father
);
350 int d2
= loop_depth (bb2
->loop_father
);
361 /* Sort the basic blocks from DOM such that the first are the ones at
362 a deepest loop level. */
365 graphite_sort_dominated_info (vec
<basic_block
> dom
)
367 dom
.qsort (compare_bb_depths
);
370 /* Recursive helper function for build_scops_bbs. */
373 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
375 sese region
= SCOP_REGION (scop
);
376 vec
<basic_block
> dom
;
379 if (bitmap_bit_p (visited
, bb
->index
)
380 || !bb_in_sese_p (bb
, region
))
383 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
384 SCOP_BBS (scop
).safe_push (pbb
);
385 bitmap_set_bit (visited
, bb
->index
);
387 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
392 graphite_sort_dominated_info (dom
);
394 while (!dom
.is_empty ())
399 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
400 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
402 build_scop_bbs_1 (scop
, visited
, dom_bb
);
403 dom
.unordered_remove (i
);
411 /* Gather the basic blocks belonging to the SCOP. */
414 build_scop_bbs (scop_p scop
)
416 sbitmap visited
= sbitmap_alloc (last_basic_block
);
417 sese region
= SCOP_REGION (scop
);
419 bitmap_clear (visited
);
420 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
421 sbitmap_free (visited
);
424 /* Return an ISL identifier for the polyhedral basic block PBB. */
427 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
430 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
431 return isl_id_alloc (s
->ctx
, name
, pbb
);
434 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
435 We generate SCATTERING_DIMENSIONS scattering dimensions.
437 CLooG 0.15.0 and previous versions require, that all
438 scattering functions of one CloogProgram have the same number of
439 scattering dimensions, therefore we allow to specify it. This
440 should be removed in future versions of CLooG.
442 The scattering polyhedron consists of these dimensions: scattering,
443 loop_iterators, parameters.
447 | scattering_dimensions = 5
448 | used_scattering_dimensions = 3
456 | Scattering polyhedron:
458 | scattering: {s1, s2, s3, s4, s5}
459 | loop_iterators: {i}
460 | parameters: {p1, p2}
462 | s1 s2 s3 s4 s5 i p1 p2 1
463 | 1 0 0 0 0 0 0 0 -4 = 0
464 | 0 1 0 0 0 -1 0 0 0 = 0
465 | 0 0 1 0 0 0 0 0 -5 = 0 */
468 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
469 poly_bb_p pbb
, int scattering_dimensions
)
472 int nb_iterators
= pbb_dim_iter_domain (pbb
);
473 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
477 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
481 dc
= isl_set_get_space (pbb
->domain
);
482 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
483 isl_dim_out
, scattering_dimensions
);
484 pbb
->schedule
= isl_map_universe (dm
);
486 for (i
= 0; i
< scattering_dimensions
; i
++)
488 /* Textual order inside this loop. */
491 isl_constraint
*c
= isl_equality_alloc
492 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
494 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
498 isl_int_neg (val
, val
);
499 c
= isl_constraint_set_constant (c
, val
);
500 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
501 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
504 /* Iterations of this loop. */
505 else /* if ((i % 2) == 1) */
507 int loop
= (i
- 1) / 2;
508 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
515 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
518 /* Build for BB the static schedule.
520 The static schedule is a Dewey numbering of the abstract syntax
521 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
523 The following example informally defines the static schedule:
542 Static schedules for A to F:
555 build_scop_scattering (scop_p scop
)
559 gimple_bb_p previous_gbb
= NULL
;
560 isl_space
*dc
= isl_set_get_space (scop
->context
);
561 isl_aff
*static_sched
;
563 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops (cfun
));
564 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
566 /* We have to start schedules at 0 on the first component and
567 because we cannot compare_prefix_loops against a previous loop,
568 prefix will be equal to zero, and that index will be
569 incremented before copying. */
570 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
572 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
574 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
576 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
579 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
585 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
587 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
590 isl_aff_free (static_sched
);
593 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
595 /* Extract an affine expression from the chain of recurrence E. */
598 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
600 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
601 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
602 isl_local_space
*ls
= isl_local_space_from_space (space
);
603 unsigned pos
= sese_loop_depth ((sese
) s
->region
, get_chrec_loop (e
)) - 1;
604 isl_aff
*loop
= isl_aff_set_coefficient_si
605 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
606 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
608 /* Before multiplying, make sure that the result is affine. */
609 gcc_assert (isl_pw_aff_is_cst (rhs
)
610 || isl_pw_aff_is_cst (l
));
612 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
615 /* Extract an affine expression from the mult_expr E. */
618 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
620 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
621 isl_space_copy (space
));
622 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
624 if (!isl_pw_aff_is_cst (lhs
)
625 && !isl_pw_aff_is_cst (rhs
))
627 isl_pw_aff_free (lhs
);
628 isl_pw_aff_free (rhs
);
632 return isl_pw_aff_mul (lhs
, rhs
);
635 /* Return an ISL identifier from the name of the ssa_name E. */
638 isl_id_for_ssa_name (scop_p s
, tree e
)
640 const char *name
= get_name (e
);
644 id
= isl_id_alloc (s
->ctx
, name
, e
);
648 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
649 id
= isl_id_alloc (s
->ctx
, name1
, e
);
655 /* Return an ISL identifier for the data reference DR. */
658 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
660 /* Data references all get the same isl_id. They need to be comparable
661 and are distinguished through the first dimension, which contains the
663 return isl_id_alloc (s
->ctx
, "", 0);
666 /* Extract an affine expression from the ssa_name E. */
669 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
676 id
= isl_id_for_ssa_name (s
, e
);
677 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
679 dom
= isl_set_universe (isl_space_copy (space
));
680 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
681 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
682 return isl_pw_aff_alloc (dom
, aff
);
685 /* Extract an affine expression from the gmp constant G. */
688 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
690 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
691 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
692 isl_set
*dom
= isl_set_universe (space
);
696 isl_int_set_gmp (v
, g
);
697 aff
= isl_aff_add_constant (aff
, v
);
700 return isl_pw_aff_alloc (dom
, aff
);
703 /* Extract an affine expression from the integer_cst E. */
706 extract_affine_int (tree e
, __isl_take isl_space
*space
)
712 tree_int_to_gmp (e
, g
);
713 res
= extract_affine_gmp (g
, space
);
719 /* Compute pwaff mod 2^width. */
722 wrap (isl_pw_aff
*pwaff
, unsigned width
)
727 isl_int_set_si (mod
, 1);
728 isl_int_mul_2exp (mod
, mod
, width
);
730 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
737 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
738 Otherwise returns -1. */
741 parameter_index_in_region_1 (tree name
, sese region
)
746 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
748 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
755 /* When the parameter NAME is in REGION, returns its index in
756 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
757 and returns the index of NAME. */
760 parameter_index_in_region (tree name
, sese region
)
764 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
766 i
= parameter_index_in_region_1 (name
, region
);
770 gcc_assert (SESE_ADD_PARAMS (region
));
772 i
= SESE_PARAMS (region
).length ();
773 SESE_PARAMS (region
).safe_push (name
);
777 /* Extract an affine expression from the tree E in the scop S. */
780 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
782 isl_pw_aff
*lhs
, *rhs
, *res
;
785 if (e
== chrec_dont_know
) {
786 isl_space_free (space
);
790 switch (TREE_CODE (e
))
792 case POLYNOMIAL_CHREC
:
793 res
= extract_affine_chrec (s
, e
, space
);
797 res
= extract_affine_mul (s
, e
, space
);
801 case POINTER_PLUS_EXPR
:
802 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
803 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
804 res
= isl_pw_aff_add (lhs
, rhs
);
808 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
809 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
810 res
= isl_pw_aff_sub (lhs
, rhs
);
815 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
816 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
817 res
= isl_pw_aff_mul (lhs
, rhs
);
821 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
822 res
= extract_affine_name (s
, e
, space
);
826 res
= extract_affine_int (e
, space
);
827 /* No need to wrap a single integer. */
831 case NON_LVALUE_EXPR
:
832 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
840 type
= TREE_TYPE (e
);
841 if (TYPE_UNSIGNED (type
))
842 res
= wrap (res
, TYPE_PRECISION (type
));
847 /* In the context of sese S, scan the expression E and translate it to
848 a linear expression C. When parsing a symbolic multiplication, K
849 represents the constant multiplier of an expression containing
853 scan_tree_for_params (sese s
, tree e
)
855 if (e
== chrec_dont_know
)
858 switch (TREE_CODE (e
))
860 case POLYNOMIAL_CHREC
:
861 scan_tree_for_params (s
, CHREC_LEFT (e
));
865 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
866 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
868 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
872 case POINTER_PLUS_EXPR
:
874 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
875 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
881 case NON_LVALUE_EXPR
:
882 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
886 parameter_index_in_region (e
, s
);
899 /* Find parameters with respect to REGION in BB. We are looking in memory
900 access functions, conditions and loop bounds. */
903 find_params_in_bb (sese region
, gimple_bb_p gbb
)
909 loop_p loop
= GBB_BB (gbb
)->loop_father
;
911 /* Find parameters in the access functions of data references. */
912 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
913 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
914 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
916 /* Find parameters in conditional statements. */
917 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
919 tree lhs
= scalar_evolution_in_region (region
, loop
,
920 gimple_cond_lhs (stmt
));
921 tree rhs
= scalar_evolution_in_region (region
, loop
,
922 gimple_cond_rhs (stmt
));
924 scan_tree_for_params (region
, lhs
);
925 scan_tree_for_params (region
, rhs
);
929 /* Record the parameters used in the SCOP. A variable is a parameter
930 in a scop if it does not vary during the execution of that scop. */
933 find_scop_parameters (scop_p scop
)
937 sese region
= SCOP_REGION (scop
);
941 /* Find the parameters used in the loop bounds. */
942 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
944 tree nb_iters
= number_of_latch_executions (loop
);
946 if (!chrec_contains_symbols (nb_iters
))
949 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
950 scan_tree_for_params (region
, nb_iters
);
953 /* Find the parameters used in data accesses. */
954 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
955 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
957 nbp
= sese_nb_params (region
);
958 scop_set_nb_params (scop
, nbp
);
959 SESE_ADD_PARAMS (region
) = false;
963 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
965 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
966 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
967 isl_id_for_ssa_name (scop
, e
));
969 scop
->context
= isl_set_universe (space
);
973 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
974 the constraints for the surrounding loops. */
977 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
979 isl_set
*outer
, isl_set
**doms
)
981 tree nb_iters
= number_of_latch_executions (loop
);
982 sese region
= SCOP_REGION (scop
);
984 isl_set
*inner
= isl_set_copy (outer
);
987 int pos
= isl_set_dim (outer
, isl_dim_set
);
994 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
995 space
= isl_set_get_space (inner
);
998 c
= isl_inequality_alloc
999 (isl_local_space_from_space (isl_space_copy (space
)));
1000 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
1001 inner
= isl_set_add_constraint (inner
, c
);
1003 /* loop_i <= cst_nb_iters */
1004 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1006 c
= isl_inequality_alloc
1007 (isl_local_space_from_space (isl_space_copy (space
)));
1008 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1009 tree_int_to_gmp (nb_iters
, g
);
1010 isl_int_set_gmp (v
, g
);
1011 c
= isl_constraint_set_constant (c
, v
);
1012 inner
= isl_set_add_constraint (inner
, c
);
1015 /* loop_i <= expr_nb_iters */
1016 else if (!chrec_contains_undetermined (nb_iters
))
1021 isl_local_space
*ls
;
1025 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1027 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1028 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1029 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1030 isl_set_dim (valid
, isl_dim_set
));
1031 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1033 ls
= isl_local_space_from_space (isl_space_copy (space
));
1034 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1035 isl_dim_in
, pos
, 1);
1036 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1037 isl_pw_aff_copy (aff
));
1038 inner
= isl_set_intersect (inner
, le
);
1040 if (max_stmt_executions (loop
, &nit
))
1042 /* Insert in the context the constraints from the
1043 estimation of the number of iterations NIT and the
1044 symbolic number of iterations (involving parameter
1045 names) NB_ITERS. First, build the affine expression
1046 "NIT - NB_ITERS" and then say that it is positive,
1047 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1054 mpz_set_double_int (g
, nit
, false);
1055 mpz_sub_ui (g
, g
, 1);
1056 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1057 x
= isl_pw_aff_ge_set (approx
, aff
);
1058 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1059 isl_set_dim (x
, isl_dim_set
));
1060 scop
->context
= isl_set_intersect (scop
->context
, x
);
1062 c
= isl_inequality_alloc
1063 (isl_local_space_from_space (isl_space_copy (space
)));
1064 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1065 isl_int_set_gmp (v
, g
);
1067 c
= isl_constraint_set_constant (c
, v
);
1068 inner
= isl_set_add_constraint (inner
, c
);
1071 isl_pw_aff_free (aff
);
1076 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1077 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1078 isl_set_copy (inner
), doms
);
1082 && loop_in_sese_p (loop
->next
, region
))
1083 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1084 isl_set_copy (outer
), doms
);
1086 doms
[loop
->num
] = inner
;
1088 isl_set_free (outer
);
1089 isl_space_free (space
);
1094 /* Returns a linear expression for tree T evaluated in PBB. */
1097 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1099 scop_p scop
= PBB_SCOP (pbb
);
1101 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1102 gcc_assert (!automatically_generated_chrec_p (t
));
1104 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1107 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1108 operator. This allows us to invert the condition or to handle
1112 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1114 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1115 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1121 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1125 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1133 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1137 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1141 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1145 isl_pw_aff_free (lhs
);
1146 isl_pw_aff_free (rhs
);
1150 cond
= isl_set_coalesce (cond
);
1151 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1152 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1155 /* Add conditions to the domain of PBB. */
1158 add_conditions_to_domain (poly_bb_p pbb
)
1162 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1164 if (GBB_CONDITIONS (gbb
).is_empty ())
1167 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1168 switch (gimple_code (stmt
))
1172 enum tree_code code
= gimple_cond_code (stmt
);
1174 /* The conditions for ELSE-branches are inverted. */
1175 if (!GBB_CONDITION_CASES (gbb
)[i
])
1176 code
= invert_tree_comparison (code
, false);
1178 add_condition_to_pbb (pbb
, stmt
, code
);
1183 /* Switch statements are not supported right now - fall through. */
1191 /* Traverses all the GBBs of the SCOP and add their constraints to the
1192 iteration domains. */
1195 add_conditions_to_constraints (scop_p scop
)
1200 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1201 add_conditions_to_domain (pbb
);
1204 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1205 edge between BB and its predecessor is not a loop exit edge, and
1206 the last statement of the single predecessor is a COND_EXPR. */
1209 single_pred_cond_non_loop_exit (basic_block bb
)
1211 if (single_pred_p (bb
))
1213 edge e
= single_pred_edge (bb
);
1214 basic_block pred
= e
->src
;
1217 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1220 stmt
= last_stmt (pred
);
1222 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1229 class sese_dom_walker
: public dom_walker
1232 sese_dom_walker (cdi_direction
, sese
);
1234 virtual void before_dom_children (basic_block
);
1235 virtual void after_dom_children (basic_block
);
1238 stack_vec
<gimple
, 3> m_conditions
, m_cases
;
1242 sese_dom_walker::sese_dom_walker (cdi_direction direction
, sese region
)
1243 : dom_walker (direction
), m_region (region
)
1247 /* Call-back for dom_walk executed before visiting the dominated
1251 sese_dom_walker::before_dom_children (basic_block bb
)
1256 if (!bb_in_sese_p (bb
, m_region
))
1259 stmt
= single_pred_cond_non_loop_exit (bb
);
1263 edge e
= single_pred_edge (bb
);
1265 m_conditions
.safe_push (stmt
);
1267 if (e
->flags
& EDGE_TRUE_VALUE
)
1268 m_cases
.safe_push (stmt
);
1270 m_cases
.safe_push (NULL
);
1273 gbb
= gbb_from_bb (bb
);
1277 GBB_CONDITIONS (gbb
) = m_conditions
.copy ();
1278 GBB_CONDITION_CASES (gbb
) = m_cases
.copy ();
1282 /* Call-back for dom_walk executed after visiting the dominated
1286 sese_dom_walker::after_dom_children (basic_block bb
)
1288 if (!bb_in_sese_p (bb
, m_region
))
1291 if (single_pred_cond_non_loop_exit (bb
))
1293 m_conditions
.pop ();
1298 /* Add constraints on the possible values of parameter P from the type
1302 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1304 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1305 tree type
= TREE_TYPE (parameter
);
1306 tree lb
= NULL_TREE
;
1307 tree ub
= NULL_TREE
;
1309 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1310 lb
= lower_bound_in_type (type
, type
);
1312 lb
= TYPE_MIN_VALUE (type
);
1314 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1315 ub
= upper_bound_in_type (type
, type
);
1317 ub
= TYPE_MAX_VALUE (type
);
1321 isl_space
*space
= isl_set_get_space (scop
->context
);
1326 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1329 tree_int_to_gmp (lb
, g
);
1330 isl_int_set_gmp (v
, g
);
1333 c
= isl_constraint_set_constant (c
, v
);
1335 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1337 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1342 isl_space
*space
= isl_set_get_space (scop
->context
);
1347 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1351 tree_int_to_gmp (ub
, g
);
1352 isl_int_set_gmp (v
, g
);
1354 c
= isl_constraint_set_constant (c
, v
);
1356 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1358 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1362 /* Build the context of the SCOP. The context usually contains extra
1363 constraints that are added to the iteration domains that constrain
1367 build_scop_context (scop_p scop
)
1369 graphite_dim_t p
, n
= scop_nb_params (scop
);
1371 for (p
= 0; p
< n
; p
++)
1372 add_param_constraints (scop
, p
);
1375 /* Build the iteration domains: the loops belonging to the current
1376 SCOP, and that vary for the execution of the current basic block.
1377 Returns false if there is no loop in SCOP. */
1380 build_scop_iteration_domain (scop_p scop
)
1383 sese region
= SCOP_REGION (scop
);
1386 int nb_loops
= number_of_loops (cfun
);
1387 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1389 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1390 if (!loop_in_sese_p (loop_outer (loop
), region
))
1391 build_loop_iteration_domains (scop
, loop
, 0,
1392 isl_set_copy (scop
->context
), doms
);
1394 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1396 loop
= pbb_loop (pbb
);
1398 if (doms
[loop
->num
])
1399 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1401 pbb
->domain
= isl_set_copy (scop
->context
);
1403 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1404 isl_id_for_pbb (scop
, pbb
));
1407 for (i
= 0; i
< nb_loops
; i
++)
1409 isl_set_free (doms
[i
]);
1414 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1415 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1416 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1420 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1423 int alias_set_num
= 0;
1424 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1426 if (bap
&& bap
->alias_set
)
1427 alias_set_num
= *(bap
->alias_set
);
1429 c
= isl_equality_alloc
1430 (isl_local_space_from_space (isl_map_get_space (acc
)));
1431 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1432 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1434 return isl_map_add_constraint (acc
, c
);
1437 /* Assign the affine expression INDEX to the output dimension POS of
1438 MAP and return the result. */
1441 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1444 int len
= isl_map_dim (map
, isl_dim_out
);
1447 index_map
= isl_map_from_pw_aff (index
);
1448 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1449 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1451 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1452 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1453 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1454 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1456 return isl_map_intersect (map
, index_map
);
1459 /* Add to ACCESSES polyhedron equalities defining the access functions
1460 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1461 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1462 PBB is the poly_bb_p that contains the data reference DR. */
1465 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1467 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1468 scop_p scop
= PBB_SCOP (pbb
);
1470 for (i
= 0; i
< nb_subscripts
; i
++)
1473 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1475 aff
= extract_affine (scop
, afn
,
1476 isl_space_domain (isl_map_get_space (acc
)));
1477 acc
= set_index (acc
, i
+ 1, aff
);
1483 /* Add constrains representing the size of the accessed data to the
1484 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1485 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1489 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1491 tree ref
= DR_REF (dr
);
1492 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1494 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1498 if (TREE_CODE (ref
) != ARRAY_REF
)
1501 low
= array_ref_low_bound (ref
);
1502 high
= array_ref_up_bound (ref
);
1504 /* XXX The PPL code dealt separately with
1505 subscript - low >= 0 and high - subscript >= 0 in case one of
1506 the two bounds isn't known. Do the same here? */
1508 if (host_integerp (low
, 0)
1510 && host_integerp (high
, 0)
1511 /* 1-element arrays at end of structures may extend over
1512 their declared size. */
1513 && !(array_at_struct_end_p (ref
)
1514 && operand_equal_p (low
, high
, 0)))
1518 isl_set
*univ
, *lbs
, *ubs
;
1522 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1523 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1526 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1527 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1528 isl_set_dim (valid
, isl_dim_set
));
1529 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1531 space
= isl_set_get_space (extent
);
1532 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1533 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1534 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1535 index
= isl_pw_aff_alloc (univ
, aff
);
1537 id
= isl_set_get_tuple_id (extent
);
1538 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1539 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1541 /* low <= sub_i <= high */
1542 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1543 ubs
= isl_pw_aff_le_set (index
, ub
);
1544 extent
= isl_set_intersect (extent
, lbs
);
1545 extent
= isl_set_intersect (extent
, ubs
);
1552 /* Build data accesses for DR in PBB. */
1555 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1557 int dr_base_object_set
;
1560 scop_p scop
= PBB_SCOP (pbb
);
1563 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1564 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1565 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1566 isl_dim_out
, nb_out
);
1568 acc
= isl_map_universe (space
);
1569 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1572 acc
= pdr_add_alias_set (acc
, dr
);
1573 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1576 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1577 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1578 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1579 int alias_set_num
= 0;
1580 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1582 if (bap
&& bap
->alias_set
)
1583 alias_set_num
= *(bap
->alias_set
);
1585 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1586 extent
= isl_set_nat_universe (space
);
1587 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1588 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1591 gcc_assert (dr
->aux
);
1592 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1594 new_poly_dr (pbb
, dr_base_object_set
,
1595 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1596 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1599 /* Write to FILE the alias graph of data references in DIMACS format. */
1602 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1603 vec
<data_reference_p
> drs
)
1605 int num_vertex
= drs
.length ();
1607 data_reference_p dr1
, dr2
;
1610 if (num_vertex
== 0)
1613 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1614 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1615 if (dr_may_alias_p (dr1
, dr2
, true))
1618 fprintf (file
, "$\n");
1621 fprintf (file
, "c %s\n", comment
);
1623 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1625 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1626 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1627 if (dr_may_alias_p (dr1
, dr2
, true))
1628 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1633 /* Write to FILE the alias graph of data references in DOT format. */
1636 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1637 vec
<data_reference_p
> drs
)
1639 int num_vertex
= drs
.length ();
1640 data_reference_p dr1
, dr2
;
1643 if (num_vertex
== 0)
1646 fprintf (file
, "$\n");
1649 fprintf (file
, "c %s\n", comment
);
1651 /* First print all the vertices. */
1652 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1653 fprintf (file
, "n%d;\n", i
);
1655 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1656 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1657 if (dr_may_alias_p (dr1
, dr2
, true))
1658 fprintf (file
, "n%d n%d\n", i
, j
);
1663 /* Write to FILE the alias graph of data references in ECC format. */
1666 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1667 vec
<data_reference_p
> drs
)
1669 int num_vertex
= drs
.length ();
1670 data_reference_p dr1
, dr2
;
1673 if (num_vertex
== 0)
1676 fprintf (file
, "$\n");
1679 fprintf (file
, "c %s\n", comment
);
1681 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1682 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1683 if (dr_may_alias_p (dr1
, dr2
, true))
1684 fprintf (file
, "%d %d\n", i
, j
);
1689 /* Check if DR1 and DR2 are in the same object set. */
1692 dr_same_base_object_p (const struct data_reference
*dr1
,
1693 const struct data_reference
*dr2
)
1695 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1698 /* Uses DFS component number as representative of alias-sets. Also tests for
1699 optimality by verifying if every connected component is a clique. Returns
1700 true (1) if the above test is true, and false (0) otherwise. */
1703 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1705 int num_vertices
= drs
.length ();
1706 struct graph
*g
= new_graph (num_vertices
);
1707 data_reference_p dr1
, dr2
;
1709 int num_connected_components
;
1710 int v_indx1
, v_indx2
, num_vertices_in_component
;
1713 struct graph_edge
*e
;
1714 int this_component_is_clique
;
1715 int all_components_are_cliques
= 1;
1717 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1718 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1719 if (dr_may_alias_p (dr1
, dr2
, true))
1725 all_vertices
= XNEWVEC (int, num_vertices
);
1726 vertices
= XNEWVEC (int, num_vertices
);
1727 for (i
= 0; i
< num_vertices
; i
++)
1728 all_vertices
[i
] = i
;
1730 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1732 for (i
= 0; i
< g
->n_vertices
; i
++)
1734 data_reference_p dr
= drs
[i
];
1735 base_alias_pair
*bap
;
1737 gcc_assert (dr
->aux
);
1738 bap
= (base_alias_pair
*)(dr
->aux
);
1740 bap
->alias_set
= XNEW (int);
1741 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1744 /* Verify if the DFS numbering results in optimal solution. */
1745 for (i
= 0; i
< num_connected_components
; i
++)
1747 num_vertices_in_component
= 0;
1748 /* Get all vertices whose DFS component number is the same as i. */
1749 for (j
= 0; j
< num_vertices
; j
++)
1750 if (g
->vertices
[j
].component
== i
)
1751 vertices
[num_vertices_in_component
++] = j
;
1753 /* Now test if the vertices in 'vertices' form a clique, by testing
1754 for edges among each pair. */
1755 this_component_is_clique
= 1;
1756 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1758 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1760 /* Check if the two vertices are connected by iterating
1761 through all the edges which have one of these are source. */
1762 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1765 if (e
->src
== vertices
[v_indx1
])
1771 this_component_is_clique
= 0;
1775 if (!this_component_is_clique
)
1776 all_components_are_cliques
= 0;
1780 free (all_vertices
);
1783 return all_components_are_cliques
;
1786 /* Group each data reference in DRS with its base object set num. */
1789 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1791 int num_vertex
= drs
.length ();
1792 struct graph
*g
= new_graph (num_vertex
);
1793 data_reference_p dr1
, dr2
;
1797 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1798 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1799 if (dr_same_base_object_p (dr1
, dr2
))
1805 queue
= XNEWVEC (int, num_vertex
);
1806 for (i
= 0; i
< num_vertex
; i
++)
1809 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1811 for (i
= 0; i
< g
->n_vertices
; i
++)
1813 data_reference_p dr
= drs
[i
];
1814 base_alias_pair
*bap
;
1816 gcc_assert (dr
->aux
);
1817 bap
= (base_alias_pair
*)(dr
->aux
);
1819 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1826 /* Build the data references for PBB. */
1829 build_pbb_drs (poly_bb_p pbb
)
1832 data_reference_p dr
;
1833 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1835 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1836 build_poly_dr (dr
, pbb
);
1839 /* Dump to file the alias graphs for the data references in DRS. */
1842 dump_alias_graphs (vec
<data_reference_p
> drs
)
1845 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1847 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1850 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1851 current_function_name ());
1852 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1853 fclose (file_dimacs
);
1856 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1859 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1860 current_function_name ());
1861 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1865 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1868 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1869 current_function_name ());
1870 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1875 /* Build data references in SCOP. */
1878 build_scop_drs (scop_p scop
)
1882 data_reference_p dr
;
1883 stack_vec
<data_reference_p
, 3> drs
;
1885 /* Remove all the PBBs that do not have data references: these basic
1886 blocks are not handled in the polyhedral representation. */
1887 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1888 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1890 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1892 SCOP_BBS (scop
).ordered_remove (i
);
1896 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1897 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1900 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1901 dr
->aux
= XNEW (base_alias_pair
);
1903 if (!build_alias_set_optimal_p (drs
))
1905 /* TODO: Add support when building alias set is not optimal. */
1909 build_base_obj_set_for_drs (drs
);
1911 /* When debugging, enable the following code. This cannot be used
1912 in production compilers. */
1914 dump_alias_graphs (drs
);
1918 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1919 build_pbb_drs (pbb
);
1922 /* Return a gsi at the position of the phi node STMT. */
1924 static gimple_stmt_iterator
1925 gsi_for_phi_node (gimple stmt
)
1927 gimple_stmt_iterator psi
;
1928 basic_block bb
= gimple_bb (stmt
);
1930 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1931 if (stmt
== gsi_stmt (psi
))
1938 /* Analyze all the data references of STMTS and add them to the
1939 GBB_DATA_REFS vector of BB. */
1942 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1948 sese region
= SCOP_REGION (scop
);
1950 if (!bb_in_sese_p (bb
, region
))
1953 nest
= outermost_loop_in_sese_1 (region
, bb
);
1954 gbb
= gbb_from_bb (bb
);
1956 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1960 if (is_gimple_debug (stmt
))
1963 loop
= loop_containing_stmt (stmt
);
1964 if (!loop_in_sese_p (loop
, region
))
1967 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1968 &GBB_DATA_REFS (gbb
));
1972 /* Insert STMT at the end of the STMTS sequence and then insert the
1973 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
1977 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
1978 gimple_stmt_iterator insert_gsi
)
1980 gimple_stmt_iterator gsi
;
1981 stack_vec
<gimple
, 3> x
;
1983 gimple_seq_add_stmt (&stmts
, stmt
);
1984 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1985 x
.safe_push (gsi_stmt (gsi
));
1987 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
1988 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
1991 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
1994 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
1997 gimple_stmt_iterator gsi
;
1998 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
1999 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2000 stack_vec
<gimple
, 3> x
;
2002 gimple_seq_add_stmt (&stmts
, stmt
);
2003 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2004 x
.safe_push (gsi_stmt (gsi
));
2006 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2008 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2009 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2013 gsi
= gsi_for_stmt (after_stmt
);
2014 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2017 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2020 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2023 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2025 vec
<data_reference_p
> drs
;
2027 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2028 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2029 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2030 int index
, n
= SCOP_BBS (scop
).length ();
2032 /* The INDEX of PBB in SCOP_BBS. */
2033 for (index
= 0; index
< n
; index
++)
2034 if (SCOP_BBS (scop
)[index
] == pbb
)
2037 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2039 GBB_PBB (gbb1
) = pbb1
;
2040 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2041 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2042 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2045 /* Insert on edge E the assignment "RES := EXPR". */
2048 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2050 gimple_stmt_iterator gsi
;
2051 gimple_seq stmts
= NULL
;
2052 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2053 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2055 stack_vec
<gimple
, 3> x
;
2057 gimple_seq_add_stmt (&stmts
, stmt
);
2058 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2059 x
.safe_push (gsi_stmt (gsi
));
2061 gsi_insert_seq_on_edge (e
, stmts
);
2062 gsi_commit_edge_inserts ();
2063 bb
= gimple_bb (stmt
);
2065 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2068 if (!gbb_from_bb (bb
))
2069 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2071 analyze_drs_in_stmts (scop
, bb
, x
);
2074 /* Creates a zero dimension array of the same type as VAR. */
2077 create_zero_dim_array (tree var
, const char *base_name
)
2079 tree index_type
= build_index_type (integer_zero_node
);
2080 tree elt_type
= TREE_TYPE (var
);
2081 tree array_type
= build_array_type (elt_type
, index_type
);
2082 tree base
= create_tmp_var (array_type
, base_name
);
2084 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2088 /* Returns true when PHI is a loop close phi node. */
2091 scalar_close_phi_node_p (gimple phi
)
2093 if (gimple_code (phi
) != GIMPLE_PHI
2094 || virtual_operand_p (gimple_phi_result (phi
)))
2097 /* Note that loop close phi nodes should have a single argument
2098 because we translated the representation into a canonical form
2099 before Graphite: see canonicalize_loop_closed_ssa_form. */
2100 return (gimple_phi_num_args (phi
) == 1);
2103 /* For a definition DEF in REGION, propagates the expression EXPR in
2104 all the uses of DEF outside REGION. */
2107 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2109 imm_use_iterator imm_iter
;
2112 bool replaced_once
= false;
2114 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2116 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2119 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2120 if (!is_gimple_debug (use_stmt
)
2121 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2124 use_operand_p use_p
;
2126 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2127 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2128 && (replaced_once
= true))
2129 replace_exp (use_p
, expr
);
2131 update_stmt (use_stmt
);
2136 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2137 gsi_commit_edge_inserts ();
2141 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2142 dimension array for it. */
2145 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2147 sese region
= SCOP_REGION (scop
);
2148 gimple phi
= gsi_stmt (*psi
);
2149 tree res
= gimple_phi_result (phi
);
2150 basic_block bb
= gimple_bb (phi
);
2151 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2152 tree arg
= gimple_phi_arg_def (phi
, 0);
2155 /* Note that loop close phi nodes should have a single argument
2156 because we translated the representation into a canonical form
2157 before Graphite: see canonicalize_loop_closed_ssa_form. */
2158 gcc_assert (gimple_phi_num_args (phi
) == 1);
2160 /* The phi node can be a non close phi node, when its argument is
2161 invariant, or a default definition. */
2162 if (is_gimple_min_invariant (arg
)
2163 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2165 propagate_expr_outside_region (res
, arg
, region
);
2170 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2172 propagate_expr_outside_region (res
, arg
, region
);
2173 stmt
= gimple_build_assign (res
, arg
);
2174 remove_phi_node (psi
, false);
2175 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2179 /* If res is scev analyzable and is not a scalar value, it is safe
2180 to ignore the close phi node: it will be code generated in the
2181 out of Graphite pass. */
2182 else if (scev_analyzable_p (res
, region
))
2184 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2187 if (!loop_in_sese_p (loop
, region
))
2189 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2190 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2191 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2194 scev
= scalar_evolution_in_region (region
, loop
, res
);
2196 if (tree_does_not_contain_chrecs (scev
))
2197 propagate_expr_outside_region (res
, scev
, region
);
2204 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2206 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2208 if (TREE_CODE (arg
) == SSA_NAME
)
2209 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2210 SSA_NAME_DEF_STMT (arg
));
2212 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2213 zero_dim_array
, arg
);
2216 remove_phi_node (psi
, false);
2217 SSA_NAME_DEF_STMT (res
) = stmt
;
2219 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2222 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2223 dimension array for it. */
2226 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2229 gimple phi
= gsi_stmt (*psi
);
2230 basic_block bb
= gimple_bb (phi
);
2231 tree res
= gimple_phi_result (phi
);
2232 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2235 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2237 tree arg
= gimple_phi_arg_def (phi
, i
);
2238 edge e
= gimple_phi_arg_edge (phi
, i
);
2240 /* Avoid the insertion of code in the loop latch to please the
2241 pattern matching of the vectorizer. */
2242 if (TREE_CODE (arg
) == SSA_NAME
2243 && e
->src
== bb
->loop_father
->latch
)
2244 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2245 SSA_NAME_DEF_STMT (arg
));
2247 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2250 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2251 remove_phi_node (psi
, false);
2252 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2255 /* Rewrite the degenerate phi node at position PSI from the degenerate
2256 form "x = phi (y, y, ..., y)" to "x = y". */
2259 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2263 gimple_stmt_iterator gsi
;
2264 gimple phi
= gsi_stmt (*psi
);
2265 tree res
= gimple_phi_result (phi
);
2268 bb
= gimple_bb (phi
);
2269 rhs
= degenerate_phi_result (phi
);
2272 stmt
= gimple_build_assign (res
, rhs
);
2273 remove_phi_node (psi
, false);
2275 gsi
= gsi_after_labels (bb
);
2276 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2279 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2282 rewrite_reductions_out_of_ssa (scop_p scop
)
2285 gimple_stmt_iterator psi
;
2286 sese region
= SCOP_REGION (scop
);
2289 if (bb_in_sese_p (bb
, region
))
2290 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2292 gimple phi
= gsi_stmt (psi
);
2294 if (virtual_operand_p (gimple_phi_result (phi
)))
2300 if (gimple_phi_num_args (phi
) > 1
2301 && degenerate_phi_result (phi
))
2302 rewrite_degenerate_phi (&psi
);
2304 else if (scalar_close_phi_node_p (phi
))
2305 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2307 else if (reduction_phi_p (region
, &psi
))
2308 rewrite_phi_out_of_ssa (scop
, &psi
);
2311 update_ssa (TODO_update_ssa
);
2312 #ifdef ENABLE_CHECKING
2313 verify_loop_closed_ssa (true);
2317 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2318 read from ZERO_DIM_ARRAY. */
2321 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2322 tree def
, gimple use_stmt
)
2327 use_operand_p use_p
;
2329 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2331 name
= copy_ssa_name (def
, NULL
);
2332 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2334 gimple_assign_set_lhs (name_stmt
, name
);
2335 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2337 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2338 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2339 replace_exp (use_p
, name
);
2341 update_stmt (use_stmt
);
2344 /* For every definition DEF in the SCOP that is used outside the scop,
2345 insert a closing-scop definition in the basic block just after this
2349 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2351 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2352 tree new_name
= make_ssa_name (var
, stmt
);
2353 bool needs_copy
= false;
2354 use_operand_p use_p
;
2355 imm_use_iterator imm_iter
;
2357 sese region
= SCOP_REGION (scop
);
2359 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2361 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2363 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2365 SET_USE (use_p
, new_name
);
2367 update_stmt (use_stmt
);
2372 /* Insert in the empty BB just after the scop a use of DEF such
2373 that the rewrite of cross_bb_scalar_dependences won't insert
2374 arrays everywhere else. */
2377 gimple assign
= gimple_build_assign (new_name
, def
);
2378 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2380 update_stmt (assign
);
2381 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2385 /* Rewrite the scalar dependences crossing the boundary of the BB
2386 containing STMT with an array. Return true when something has been
2390 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2392 sese region
= SCOP_REGION (scop
);
2393 gimple stmt
= gsi_stmt (*gsi
);
2394 imm_use_iterator imm_iter
;
2397 tree zero_dim_array
= NULL_TREE
;
2401 switch (gimple_code (stmt
))
2404 def
= gimple_assign_lhs (stmt
);
2408 def
= gimple_call_lhs (stmt
);
2416 || !is_gimple_reg (def
))
2419 if (scev_analyzable_p (def
, region
))
2421 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2422 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2424 if (tree_contains_chrecs (scev
, NULL
))
2427 propagate_expr_outside_region (def
, scev
, region
);
2431 def_bb
= gimple_bb (stmt
);
2433 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2435 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2436 if (gimple_code (use_stmt
) == GIMPLE_PHI
2439 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2441 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2442 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2444 rewrite_phi_out_of_ssa (scop
, &psi
);
2447 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2448 if (gimple_code (use_stmt
) != GIMPLE_PHI
2449 && def_bb
!= gimple_bb (use_stmt
)
2450 && !is_gimple_debug (use_stmt
)
2453 if (!zero_dim_array
)
2455 zero_dim_array
= create_zero_dim_array
2456 (def
, "Cross_BB_scalar_dependence");
2457 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2458 SSA_NAME_DEF_STMT (def
));
2462 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2469 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2472 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2475 gimple_stmt_iterator psi
;
2476 sese region
= SCOP_REGION (scop
);
2477 bool changed
= false;
2479 /* Create an extra empty BB after the scop. */
2480 split_edge (SESE_EXIT (region
));
2483 if (bb_in_sese_p (bb
, region
))
2484 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2485 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2490 update_ssa (TODO_update_ssa
);
2491 #ifdef ENABLE_CHECKING
2492 verify_loop_closed_ssa (true);
2497 /* Returns the number of pbbs that are in loops contained in SCOP. */
2500 nb_pbbs_in_loops (scop_p scop
)
2506 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2507 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2513 /* Return the number of data references in BB that write in
2517 nb_data_writes_in_bb (basic_block bb
)
2520 gimple_stmt_iterator gsi
;
2522 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2523 if (gimple_vdef (gsi_stmt (gsi
)))
2529 /* Splits at STMT the basic block BB represented as PBB in the
2533 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2535 edge e1
= split_block (bb
, stmt
);
2536 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2540 /* Splits STMT out of its current BB. This is done for reduction
2541 statements for which we want to ignore data dependences. */
2544 split_reduction_stmt (scop_p scop
, gimple stmt
)
2546 basic_block bb
= gimple_bb (stmt
);
2547 poly_bb_p pbb
= pbb_from_bb (bb
);
2548 gimple_bb_p gbb
= gbb_from_bb (bb
);
2551 data_reference_p dr
;
2553 /* Do not split basic blocks with no writes to memory: the reduction
2554 will be the only write to memory. */
2555 if (nb_data_writes_in_bb (bb
) == 0
2556 /* Or if we have already marked BB as a reduction. */
2557 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2560 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2562 /* Split once more only when the reduction stmt is not the only one
2563 left in the original BB. */
2564 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2566 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2568 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2571 /* A part of the data references will end in a different basic block
2572 after the split: move the DRs from the original GBB to the newly
2574 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2576 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2580 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2581 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2582 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2590 /* Return true when stmt is a reduction operation. */
2593 is_reduction_operation_p (gimple stmt
)
2595 enum tree_code code
;
2597 gcc_assert (is_gimple_assign (stmt
));
2598 code
= gimple_assign_rhs_code (stmt
);
2600 return flag_associative_math
2601 && commutative_tree_code (code
)
2602 && associative_tree_code (code
);
2605 /* Returns true when PHI contains an argument ARG. */
2608 phi_contains_arg (gimple phi
, tree arg
)
2612 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2613 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2619 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2622 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2626 if (TREE_CODE (arg
) != SSA_NAME
)
2629 stmt
= SSA_NAME_DEF_STMT (arg
);
2631 if (gimple_code (stmt
) == GIMPLE_NOP
2632 || gimple_code (stmt
) == GIMPLE_CALL
)
2635 if (gimple_code (stmt
) == GIMPLE_PHI
)
2637 if (phi_contains_arg (stmt
, lhs
))
2642 if (!is_gimple_assign (stmt
))
2645 if (gimple_num_ops (stmt
) == 2)
2646 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2648 if (is_reduction_operation_p (stmt
))
2650 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2653 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2659 /* Detect commutative and associative scalar reductions starting at
2660 the STMT. Return the phi node of the reduction cycle, or NULL. */
2663 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2667 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2672 in
->safe_push (stmt
);
2673 out
->safe_push (stmt
);
2677 /* Detect commutative and associative scalar reductions starting at
2678 STMT. Return the phi node of the reduction cycle, or NULL. */
2681 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2684 tree lhs
= gimple_assign_lhs (stmt
);
2686 if (gimple_num_ops (stmt
) == 2)
2687 return detect_commutative_reduction_arg (lhs
, stmt
,
2688 gimple_assign_rhs1 (stmt
),
2691 if (is_reduction_operation_p (stmt
))
2693 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2694 gimple_assign_rhs1 (stmt
),
2697 : detect_commutative_reduction_arg (lhs
, stmt
,
2698 gimple_assign_rhs2 (stmt
),
2705 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2708 follow_inital_value_to_phi (tree arg
, tree lhs
)
2712 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2715 stmt
= SSA_NAME_DEF_STMT (arg
);
2717 if (gimple_code (stmt
) == GIMPLE_PHI
2718 && phi_contains_arg (stmt
, lhs
))
2725 /* Return the argument of the loop PHI that is the initial value coming
2726 from outside the loop. */
2729 edge_initial_value_for_loop_phi (gimple phi
)
2733 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2735 edge e
= gimple_phi_arg_edge (phi
, i
);
2737 if (loop_depth (e
->src
->loop_father
)
2738 < loop_depth (e
->dest
->loop_father
))
2745 /* Return the argument of the loop PHI that is the initial value coming
2746 from outside the loop. */
2749 initial_value_for_loop_phi (gimple phi
)
2753 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2755 edge e
= gimple_phi_arg_edge (phi
, i
);
2757 if (loop_depth (e
->src
->loop_father
)
2758 < loop_depth (e
->dest
->loop_father
))
2759 return gimple_phi_arg_def (phi
, i
);
2765 /* Returns true when DEF is used outside the reduction cycle of
2769 used_outside_reduction (tree def
, gimple loop_phi
)
2771 use_operand_p use_p
;
2772 imm_use_iterator imm_iter
;
2773 loop_p loop
= loop_containing_stmt (loop_phi
);
2775 /* In LOOP, DEF should be used only in LOOP_PHI. */
2776 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2778 gimple stmt
= USE_STMT (use_p
);
2780 if (stmt
!= loop_phi
2781 && !is_gimple_debug (stmt
)
2782 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2789 /* Detect commutative and associative scalar reductions belonging to
2790 the SCOP starting at the loop closed phi node STMT. Return the phi
2791 node of the reduction cycle, or NULL. */
2794 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2797 if (scalar_close_phi_node_p (stmt
))
2799 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2800 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2802 if (TREE_CODE (arg
) != SSA_NAME
)
2805 /* Note that loop close phi nodes should have a single argument
2806 because we translated the representation into a canonical form
2807 before Graphite: see canonicalize_loop_closed_ssa_form. */
2808 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2810 def
= SSA_NAME_DEF_STMT (arg
);
2811 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2812 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2815 lhs
= gimple_phi_result (close_phi
);
2816 init
= initial_value_for_loop_phi (loop_phi
);
2817 phi
= follow_inital_value_to_phi (init
, lhs
);
2819 if (phi
&& (used_outside_reduction (lhs
, phi
)
2820 || !has_single_use (gimple_phi_result (phi
))))
2823 in
->safe_push (loop_phi
);
2824 out
->safe_push (close_phi
);
2828 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2829 return detect_commutative_reduction_assign (stmt
, in
, out
);
2834 /* Translate the scalar reduction statement STMT to an array RED
2835 knowing that its recursive phi node is LOOP_PHI. */
2838 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2839 gimple stmt
, gimple loop_phi
)
2841 tree res
= gimple_phi_result (loop_phi
);
2842 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2843 gimple_stmt_iterator gsi
;
2845 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2847 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2848 gsi
= gsi_for_stmt (stmt
);
2850 insert_stmts (scop
, assign
, NULL
, gsi
);
2853 /* Removes the PHI node and resets all the debug stmts that are using
2857 remove_phi (gimple phi
)
2859 imm_use_iterator imm_iter
;
2861 use_operand_p use_p
;
2862 gimple_stmt_iterator gsi
;
2863 stack_vec
<gimple
, 3> update
;
2867 def
= PHI_RESULT (phi
);
2868 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2870 stmt
= USE_STMT (use_p
);
2872 if (is_gimple_debug (stmt
))
2874 gimple_debug_bind_reset_value (stmt
);
2875 update
.safe_push (stmt
);
2879 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2882 gsi
= gsi_for_phi_node (phi
);
2883 remove_phi_node (&gsi
, false);
2886 /* Helper function for for_each_index. For each INDEX of the data
2887 reference REF, returns true when its indices are valid in the loop
2888 nest LOOP passed in as DATA. */
2891 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2894 basic_block header
, def_bb
;
2897 if (TREE_CODE (*index
) != SSA_NAME
)
2900 loop
= *((loop_p
*) data
);
2901 header
= loop
->header
;
2902 stmt
= SSA_NAME_DEF_STMT (*index
);
2907 def_bb
= gimple_bb (stmt
);
2912 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2915 /* When the result of a CLOSE_PHI is written to a memory location,
2916 return a pointer to that memory reference, otherwise return
2920 close_phi_written_to_memory (gimple close_phi
)
2922 imm_use_iterator imm_iter
;
2923 use_operand_p use_p
;
2925 tree res
, def
= gimple_phi_result (close_phi
);
2927 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2928 if ((stmt
= USE_STMT (use_p
))
2929 && gimple_code (stmt
) == GIMPLE_ASSIGN
2930 && (res
= gimple_assign_lhs (stmt
)))
2932 switch (TREE_CODE (res
))
2942 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2943 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2945 /* FIXME: this restriction is for id-{24,25}.f and
2946 could be handled by duplicating the computation of
2947 array indices before the loop of the close_phi. */
2948 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
2960 /* Rewrite out of SSA the reduction described by the loop phi nodes
2961 IN, and the close phi nodes OUT. IN and OUT are structured by loop
2964 IN: stmt, loop_n, ..., loop_0
2965 OUT: stmt, close_n, ..., close_0
2967 the first element is the reduction statement, and the next elements
2968 are the loop and close phi nodes of each of the outer loops. */
2971 translate_scalar_reduction_to_array (scop_p scop
,
2976 unsigned int i
= out
.length () - 1;
2977 tree red
= close_phi_written_to_memory (out
[i
]);
2979 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
2981 gimple close_phi
= out
[i
];
2985 gimple stmt
= loop_phi
;
2986 basic_block bb
= split_reduction_stmt (scop
, stmt
);
2987 poly_bb_p pbb
= pbb_from_bb (bb
);
2988 PBB_IS_REDUCTION (pbb
) = true;
2989 gcc_assert (close_phi
== loop_phi
);
2992 red
= create_zero_dim_array
2993 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
2995 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
2999 if (i
== in
.length () - 1)
3001 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3002 unshare_expr (red
), close_phi
);
3003 insert_out_of_ssa_copy_on_edge
3004 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3005 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3008 remove_phi (loop_phi
);
3009 remove_phi (close_phi
);
3013 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3014 true when something has been changed. */
3017 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3021 stack_vec
<gimple
, 10> in
;
3022 stack_vec
<gimple
, 10> out
;
3024 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3025 res
= in
.length () > 1;
3027 translate_scalar_reduction_to_array (scop
, in
, out
);
3032 /* Rewrites all the commutative reductions from LOOP out of SSA.
3033 Returns true when something has been changed. */
3036 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3039 gimple_stmt_iterator gsi
;
3040 edge exit
= single_exit (loop
);
3042 bool changed
= false;
3047 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3048 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3049 && !virtual_operand_p (res
)
3050 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3051 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3052 (scop
, gsi_stmt (gsi
));
3057 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3060 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3064 bool changed
= false;
3065 sese region
= SCOP_REGION (scop
);
3067 FOR_EACH_LOOP (li
, loop
, 0)
3068 if (loop_in_sese_p (loop
, region
))
3069 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3074 gsi_commit_edge_inserts ();
3075 update_ssa (TODO_update_ssa
);
3076 #ifdef ENABLE_CHECKING
3077 verify_loop_closed_ssa (true);
3082 /* Can all ivs be represented by a signed integer?
3083 As CLooG might generate negative values in its expressions, signed loop ivs
3084 are required in the backend. */
3087 scop_ivs_can_be_represented (scop_p scop
)
3091 gimple_stmt_iterator psi
;
3094 FOR_EACH_LOOP (li
, loop
, 0)
3096 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3099 for (psi
= gsi_start_phis (loop
->header
);
3100 !gsi_end_p (psi
); gsi_next (&psi
))
3102 gimple phi
= gsi_stmt (psi
);
3103 tree res
= PHI_RESULT (phi
);
3104 tree type
= TREE_TYPE (res
);
3106 if (TYPE_UNSIGNED (type
)
3107 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3114 FOR_EACH_LOOP_BREAK (li
);
3120 /* Builds the polyhedral representation for a SESE region. */
3123 build_poly_scop (scop_p scop
)
3125 sese region
= SCOP_REGION (scop
);
3126 graphite_dim_t max_dim
;
3128 build_scop_bbs (scop
);
3130 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3131 Once CLooG is fixed, remove this guard. Anyways, it makes no
3132 sense to optimize a scop containing only PBBs that do not belong
3134 if (nb_pbbs_in_loops (scop
) == 0)
3137 if (!scop_ivs_can_be_represented (scop
))
3140 if (flag_associative_math
)
3141 rewrite_commutative_reductions_out_of_ssa (scop
);
3143 build_sese_loop_nests (region
);
3144 /* Record all conditions in REGION. */
3145 sese_dom_walker (CDI_DOMINATORS
, region
).walk (cfun
->cfg
->x_entry_block_ptr
);
3146 find_scop_parameters (scop
);
3148 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3149 if (scop_nb_params (scop
) > max_dim
)
3152 build_scop_iteration_domain (scop
);
3153 build_scop_context (scop
);
3154 add_conditions_to_constraints (scop
);
3156 /* Rewrite out of SSA only after having translated the
3157 representation to the polyhedral representation to avoid scev
3158 analysis failures. That means that these functions will insert
3159 new data references that they create in the right place. */
3160 rewrite_reductions_out_of_ssa (scop
);
3161 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3163 build_scop_drs (scop
);
3165 build_scop_scattering (scop
);
3167 /* This SCoP has been translated to the polyhedral
3169 POLY_SCOP_P (scop
) = true;