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>
32 #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE
33 #include <isl/deprecated/int.h>
34 #include <isl/deprecated/aff_int.h>
35 #include <isl/deprecated/constraint_int.h>
40 #include "coretypes.h"
41 #include "tree-flow.h"
42 #include "tree-pass.h"
44 #include "tree-chrec.h"
45 #include "tree-data-ref.h"
46 #include "tree-scalar-evolution.h"
51 #include "graphite-poly.h"
52 #include "graphite-sese-to-poly.h"
55 /* Assigns to RES the value of the INTEGER_CST T. */
58 tree_int_to_gmp (tree t
, mpz_t res
)
60 double_int di
= tree_to_double_int (t
);
61 mpz_set_double_int (res
, di
, TYPE_UNSIGNED (TREE_TYPE (t
)));
64 /* Returns the index of the PHI argument defined in the outermost
68 phi_arg_in_outermost_loop (gimple phi
)
70 loop_p loop
= gimple_bb (phi
)->loop_father
;
73 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
74 if (!flow_bb_inside_loop_p (loop
, gimple_phi_arg_edge (phi
, i
)->src
))
76 loop
= gimple_phi_arg_edge (phi
, i
)->src
->loop_father
;
83 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
84 PSI by inserting on the loop ENTRY edge assignment "RES = INIT". */
87 remove_simple_copy_phi (gimple_stmt_iterator
*psi
)
89 gimple phi
= gsi_stmt (*psi
);
90 tree res
= gimple_phi_result (phi
);
91 size_t entry
= phi_arg_in_outermost_loop (phi
);
92 tree init
= gimple_phi_arg_def (phi
, entry
);
93 gimple stmt
= gimple_build_assign (res
, init
);
94 edge e
= gimple_phi_arg_edge (phi
, entry
);
96 remove_phi_node (psi
, false);
97 gsi_insert_on_edge_immediate (e
, stmt
);
98 SSA_NAME_DEF_STMT (res
) = stmt
;
101 /* Removes an invariant phi node at position PSI by inserting on the
102 loop ENTRY edge the assignment RES = INIT. */
105 remove_invariant_phi (sese region
, gimple_stmt_iterator
*psi
)
107 gimple phi
= gsi_stmt (*psi
);
108 loop_p loop
= loop_containing_stmt (phi
);
109 tree res
= gimple_phi_result (phi
);
110 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
111 size_t entry
= phi_arg_in_outermost_loop (phi
);
112 edge e
= gimple_phi_arg_edge (phi
, entry
);
115 gimple_seq stmts
= NULL
;
117 if (tree_contains_chrecs (scev
, NULL
))
118 scev
= gimple_phi_arg_def (phi
, entry
);
120 var
= force_gimple_operand (scev
, &stmts
, true, NULL_TREE
);
121 stmt
= gimple_build_assign (res
, var
);
122 remove_phi_node (psi
, false);
124 gimple_seq_add_stmt (&stmts
, stmt
);
125 gsi_insert_seq_on_edge (e
, stmts
);
126 gsi_commit_edge_inserts ();
127 SSA_NAME_DEF_STMT (res
) = stmt
;
130 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)". */
133 simple_copy_phi_p (gimple phi
)
137 if (gimple_phi_num_args (phi
) != 2)
140 res
= gimple_phi_result (phi
);
141 return (res
== gimple_phi_arg_def (phi
, 0)
142 || res
== gimple_phi_arg_def (phi
, 1));
145 /* Returns true when the phi node at position PSI is a reduction phi
146 node in REGION. Otherwise moves the pointer PSI to the next phi to
150 reduction_phi_p (sese region
, gimple_stmt_iterator
*psi
)
153 gimple phi
= gsi_stmt (*psi
);
154 tree res
= gimple_phi_result (phi
);
156 loop
= loop_containing_stmt (phi
);
158 if (simple_copy_phi_p (phi
))
160 /* PRE introduces phi nodes like these, for an example,
161 see id-5.f in the fortran graphite testsuite:
163 # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
165 remove_simple_copy_phi (psi
);
169 if (scev_analyzable_p (res
, region
))
171 tree scev
= scalar_evolution_in_region (region
, loop
, res
);
173 if (evolution_function_is_invariant_p (scev
, loop
->num
))
174 remove_invariant_phi (region
, psi
);
181 /* All the other cases are considered reductions. */
185 /* Store the GRAPHITE representation of BB. */
188 new_gimple_bb (basic_block bb
, vec
<data_reference_p
> drs
)
190 struct gimple_bb
*gbb
;
192 gbb
= XNEW (struct gimple_bb
);
195 GBB_DATA_REFS (gbb
) = drs
;
196 GBB_CONDITIONS (gbb
).create (0);
197 GBB_CONDITION_CASES (gbb
).create (0);
203 free_data_refs_aux (vec
<data_reference_p
> datarefs
)
206 struct data_reference
*dr
;
208 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
211 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
213 free (bap
->alias_set
);
222 free_gimple_bb (struct gimple_bb
*gbb
)
224 free_data_refs_aux (GBB_DATA_REFS (gbb
));
225 free_data_refs (GBB_DATA_REFS (gbb
));
227 GBB_CONDITIONS (gbb
).release ();
228 GBB_CONDITION_CASES (gbb
).release ();
229 GBB_BB (gbb
)->aux
= 0;
233 /* Deletes all gimple bbs in SCOP. */
236 remove_gbbs_in_scop (scop_p scop
)
241 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
242 free_gimple_bb (PBB_BLACK_BOX (pbb
));
245 /* Deletes all scops in SCOPS. */
248 free_scops (vec
<scop_p
> scops
)
253 FOR_EACH_VEC_ELT (scops
, i
, scop
)
255 remove_gbbs_in_scop (scop
);
256 free_sese (SCOP_REGION (scop
));
263 /* Same as outermost_loop_in_sese, returns the outermost loop
264 containing BB in REGION, but makes sure that the returned loop
265 belongs to the REGION, and so this returns the first loop in the
266 REGION when the loop containing BB does not belong to REGION. */
269 outermost_loop_in_sese_1 (sese region
, basic_block bb
)
271 loop_p nest
= outermost_loop_in_sese (region
, bb
);
273 if (loop_in_sese_p (nest
, region
))
276 /* When the basic block BB does not belong to a loop in the region,
277 return the first loop in the region. */
280 if (loop_in_sese_p (nest
, region
))
289 /* Generates a polyhedral black box only if the bb contains interesting
293 try_generate_gimple_bb (scop_p scop
, basic_block bb
)
295 vec
<data_reference_p
> drs
;
297 sese region
= SCOP_REGION (scop
);
298 loop_p nest
= outermost_loop_in_sese_1 (region
, bb
);
299 gimple_stmt_iterator gsi
;
301 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
303 gimple stmt
= gsi_stmt (gsi
);
306 if (is_gimple_debug (stmt
))
309 loop
= loop_containing_stmt (stmt
);
310 if (!loop_in_sese_p (loop
, region
))
313 graphite_find_data_references_in_stmt (nest
, loop
, stmt
, &drs
);
316 return new_gimple_bb (bb
, drs
);
319 /* Returns true if all predecessors of BB, that are not dominated by BB, are
320 marked in MAP. The predecessors dominated by BB are loop latches and will
321 be handled after BB. */
324 all_non_dominated_preds_marked_p (basic_block bb
, sbitmap map
)
329 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
330 if (!bitmap_bit_p (map
, e
->src
->index
)
331 && !dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
337 /* Compare the depth of two basic_block's P1 and P2. */
340 compare_bb_depths (const void *p1
, const void *p2
)
342 const_basic_block
const bb1
= *(const_basic_block
const*)p1
;
343 const_basic_block
const bb2
= *(const_basic_block
const*)p2
;
344 int d1
= loop_depth (bb1
->loop_father
);
345 int d2
= loop_depth (bb2
->loop_father
);
356 /* Sort the basic blocks from DOM such that the first are the ones at
357 a deepest loop level. */
360 graphite_sort_dominated_info (vec
<basic_block
> dom
)
362 dom
.qsort (compare_bb_depths
);
365 /* Recursive helper function for build_scops_bbs. */
368 build_scop_bbs_1 (scop_p scop
, sbitmap visited
, basic_block bb
)
370 sese region
= SCOP_REGION (scop
);
371 vec
<basic_block
> dom
;
374 if (bitmap_bit_p (visited
, bb
->index
)
375 || !bb_in_sese_p (bb
, region
))
378 pbb
= new_poly_bb (scop
, try_generate_gimple_bb (scop
, bb
));
379 SCOP_BBS (scop
).safe_push (pbb
);
380 bitmap_set_bit (visited
, bb
->index
);
382 dom
= get_dominated_by (CDI_DOMINATORS
, bb
);
387 graphite_sort_dominated_info (dom
);
389 while (!dom
.is_empty ())
394 FOR_EACH_VEC_ELT (dom
, i
, dom_bb
)
395 if (all_non_dominated_preds_marked_p (dom_bb
, visited
))
397 build_scop_bbs_1 (scop
, visited
, dom_bb
);
398 dom
.unordered_remove (i
);
406 /* Gather the basic blocks belonging to the SCOP. */
409 build_scop_bbs (scop_p scop
)
411 sbitmap visited
= sbitmap_alloc (last_basic_block
);
412 sese region
= SCOP_REGION (scop
);
414 bitmap_clear (visited
);
415 build_scop_bbs_1 (scop
, visited
, SESE_ENTRY_BB (region
));
416 sbitmap_free (visited
);
419 /* Return an ISL identifier for the polyhedral basic block PBB. */
422 isl_id_for_pbb (scop_p s
, poly_bb_p pbb
)
425 snprintf (name
, sizeof (name
), "S_%d", pbb_index (pbb
));
426 return isl_id_alloc (s
->ctx
, name
, pbb
);
429 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
430 We generate SCATTERING_DIMENSIONS scattering dimensions.
432 CLooG 0.15.0 and previous versions require, that all
433 scattering functions of one CloogProgram have the same number of
434 scattering dimensions, therefore we allow to specify it. This
435 should be removed in future versions of CLooG.
437 The scattering polyhedron consists of these dimensions: scattering,
438 loop_iterators, parameters.
442 | scattering_dimensions = 5
443 | used_scattering_dimensions = 3
451 | Scattering polyhedron:
453 | scattering: {s1, s2, s3, s4, s5}
454 | loop_iterators: {i}
455 | parameters: {p1, p2}
457 | s1 s2 s3 s4 s5 i p1 p2 1
458 | 1 0 0 0 0 0 0 0 -4 = 0
459 | 0 1 0 0 0 -1 0 0 0 = 0
460 | 0 0 1 0 0 0 0 0 -5 = 0 */
463 build_pbb_scattering_polyhedrons (isl_aff
*static_sched
,
464 poly_bb_p pbb
, int scattering_dimensions
)
467 int nb_iterators
= pbb_dim_iter_domain (pbb
);
468 int used_scattering_dimensions
= nb_iterators
* 2 + 1;
472 gcc_assert (scattering_dimensions
>= used_scattering_dimensions
);
476 dc
= isl_set_get_space (pbb
->domain
);
477 dm
= isl_space_add_dims (isl_space_from_domain (dc
),
478 isl_dim_out
, scattering_dimensions
);
479 pbb
->schedule
= isl_map_universe (dm
);
481 for (i
= 0; i
< scattering_dimensions
; i
++)
483 /* Textual order inside this loop. */
486 isl_constraint
*c
= isl_equality_alloc
487 (isl_local_space_from_space (isl_map_get_space (pbb
->schedule
)));
489 if (0 != isl_aff_get_coefficient (static_sched
, isl_dim_in
,
493 isl_int_neg (val
, val
);
494 c
= isl_constraint_set_constant (c
, val
);
495 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, i
, 1);
496 pbb
->schedule
= isl_map_add_constraint (pbb
->schedule
, c
);
499 /* Iterations of this loop. */
500 else /* if ((i % 2) == 1) */
502 int loop
= (i
- 1) / 2;
503 pbb
->schedule
= isl_map_equate (pbb
->schedule
, isl_dim_in
, loop
,
510 pbb
->transformed
= isl_map_copy (pbb
->schedule
);
513 /* Build for BB the static schedule.
515 The static schedule is a Dewey numbering of the abstract syntax
516 tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
518 The following example informally defines the static schedule:
537 Static schedules for A to F:
550 build_scop_scattering (scop_p scop
)
554 gimple_bb_p previous_gbb
= NULL
;
555 isl_space
*dc
= isl_set_get_space (scop
->context
);
556 isl_aff
*static_sched
;
558 dc
= isl_space_add_dims (dc
, isl_dim_set
, number_of_loops());
559 static_sched
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
561 /* We have to start schedules at 0 on the first component and
562 because we cannot compare_prefix_loops against a previous loop,
563 prefix will be equal to zero, and that index will be
564 incremented before copying. */
565 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
, 0, -1);
567 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
569 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
571 int nb_scat_dims
= pbb_dim_iter_domain (pbb
) * 2 + 1;
574 prefix
= nb_common_loops (SCOP_REGION (scop
), previous_gbb
, gbb
);
580 static_sched
= isl_aff_add_coefficient_si (static_sched
, isl_dim_in
,
582 build_pbb_scattering_polyhedrons (static_sched
, pbb
, nb_scat_dims
);
585 isl_aff_free (static_sched
);
588 static isl_pw_aff
*extract_affine (scop_p
, tree
, __isl_take isl_space
*space
);
590 /* Extract an affine expression from the chain of recurrence E. */
593 extract_affine_chrec (scop_p s
, tree e
, __isl_take isl_space
*space
)
595 isl_pw_aff
*lhs
= extract_affine (s
, CHREC_LEFT (e
), isl_space_copy (space
));
596 isl_pw_aff
*rhs
= extract_affine (s
, CHREC_RIGHT (e
), isl_space_copy (space
));
597 isl_local_space
*ls
= isl_local_space_from_space (space
);
598 unsigned pos
= sese_loop_depth ((sese
) s
->region
,
599 get_loop (CHREC_VARIABLE (e
))) - 1;
600 isl_aff
*loop
= isl_aff_set_coefficient_si
601 (isl_aff_zero_on_domain (ls
), isl_dim_in
, pos
, 1);
602 isl_pw_aff
*l
= isl_pw_aff_from_aff (loop
);
604 /* Before multiplying, make sure that the result is affine. */
605 gcc_assert (isl_pw_aff_is_cst (rhs
)
606 || isl_pw_aff_is_cst (l
));
608 return isl_pw_aff_add (lhs
, isl_pw_aff_mul (rhs
, l
));
611 /* Extract an affine expression from the mult_expr E. */
614 extract_affine_mul (scop_p s
, tree e
, __isl_take isl_space
*space
)
616 isl_pw_aff
*lhs
= extract_affine (s
, TREE_OPERAND (e
, 0),
617 isl_space_copy (space
));
618 isl_pw_aff
*rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
620 if (!isl_pw_aff_is_cst (lhs
)
621 && !isl_pw_aff_is_cst (rhs
))
623 isl_pw_aff_free (lhs
);
624 isl_pw_aff_free (rhs
);
628 return isl_pw_aff_mul (lhs
, rhs
);
631 /* Return an ISL identifier from the name of the ssa_name E. */
634 isl_id_for_ssa_name (scop_p s
, tree e
)
636 const char *name
= get_name (e
);
640 id
= isl_id_alloc (s
->ctx
, name
, e
);
644 snprintf (name1
, sizeof (name1
), "P_%d", SSA_NAME_VERSION (e
));
645 id
= isl_id_alloc (s
->ctx
, name1
, e
);
651 /* Return an ISL identifier for the data reference DR. */
654 isl_id_for_dr (scop_p s
, data_reference_p dr ATTRIBUTE_UNUSED
)
656 /* Data references all get the same isl_id. They need to be comparable
657 and are distinguished through the first dimension, which contains the
659 return isl_id_alloc (s
->ctx
, "", 0);
662 /* Extract an affine expression from the ssa_name E. */
665 extract_affine_name (scop_p s
, tree e
, __isl_take isl_space
*space
)
672 id
= isl_id_for_ssa_name (s
, e
);
673 dimension
= isl_space_find_dim_by_id (space
, isl_dim_param
, id
);
675 dom
= isl_set_universe (isl_space_copy (space
));
676 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
677 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_param
, dimension
, 1);
678 return isl_pw_aff_alloc (dom
, aff
);
681 /* Extract an affine expression from the gmp constant G. */
684 extract_affine_gmp (mpz_t g
, __isl_take isl_space
*space
)
686 isl_local_space
*ls
= isl_local_space_from_space (isl_space_copy (space
));
687 isl_aff
*aff
= isl_aff_zero_on_domain (ls
);
688 isl_set
*dom
= isl_set_universe (space
);
692 isl_int_set_gmp (v
, g
);
693 aff
= isl_aff_add_constant (aff
, v
);
696 return isl_pw_aff_alloc (dom
, aff
);
699 /* Extract an affine expression from the integer_cst E. */
702 extract_affine_int (tree e
, __isl_take isl_space
*space
)
708 tree_int_to_gmp (e
, g
);
709 res
= extract_affine_gmp (g
, space
);
715 /* Compute pwaff mod 2^width. */
718 wrap (isl_pw_aff
*pwaff
, unsigned width
)
723 isl_int_set_si (mod
, 1);
724 isl_int_mul_2exp (mod
, mod
, width
);
726 pwaff
= isl_pw_aff_mod (pwaff
, mod
);
733 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
734 Otherwise returns -1. */
737 parameter_index_in_region_1 (tree name
, sese region
)
742 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
744 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, p
)
751 /* When the parameter NAME is in REGION, returns its index in
752 SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
753 and returns the index of NAME. */
756 parameter_index_in_region (tree name
, sese region
)
760 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
762 i
= parameter_index_in_region_1 (name
, region
);
766 gcc_assert (SESE_ADD_PARAMS (region
));
768 i
= SESE_PARAMS (region
).length ();
769 SESE_PARAMS (region
).safe_push (name
);
773 /* Extract an affine expression from the tree E in the scop S. */
776 extract_affine (scop_p s
, tree e
, __isl_take isl_space
*space
)
778 isl_pw_aff
*lhs
, *rhs
, *res
;
781 if (e
== chrec_dont_know
) {
782 isl_space_free (space
);
786 switch (TREE_CODE (e
))
788 case POLYNOMIAL_CHREC
:
789 res
= extract_affine_chrec (s
, e
, space
);
793 res
= extract_affine_mul (s
, e
, space
);
797 case POINTER_PLUS_EXPR
:
798 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
799 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
800 res
= isl_pw_aff_add (lhs
, rhs
);
804 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
805 rhs
= extract_affine (s
, TREE_OPERAND (e
, 1), space
);
806 res
= isl_pw_aff_sub (lhs
, rhs
);
811 lhs
= extract_affine (s
, TREE_OPERAND (e
, 0), isl_space_copy (space
));
812 rhs
= extract_affine (s
, integer_minus_one_node
, space
);
813 res
= isl_pw_aff_mul (lhs
, rhs
);
817 gcc_assert (-1 != parameter_index_in_region_1 (e
, SCOP_REGION (s
)));
818 res
= extract_affine_name (s
, e
, space
);
822 res
= extract_affine_int (e
, space
);
823 /* No need to wrap a single integer. */
827 case NON_LVALUE_EXPR
:
828 res
= extract_affine (s
, TREE_OPERAND (e
, 0), space
);
836 type
= TREE_TYPE (e
);
837 if (TYPE_UNSIGNED (type
))
838 res
= wrap (res
, TYPE_PRECISION (type
));
843 /* In the context of sese S, scan the expression E and translate it to
844 a linear expression C. When parsing a symbolic multiplication, K
845 represents the constant multiplier of an expression containing
849 scan_tree_for_params (sese s
, tree e
)
851 if (e
== chrec_dont_know
)
854 switch (TREE_CODE (e
))
856 case POLYNOMIAL_CHREC
:
857 scan_tree_for_params (s
, CHREC_LEFT (e
));
861 if (chrec_contains_symbols (TREE_OPERAND (e
, 0)))
862 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
864 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
868 case POINTER_PLUS_EXPR
:
870 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
871 scan_tree_for_params (s
, TREE_OPERAND (e
, 1));
877 case NON_LVALUE_EXPR
:
878 scan_tree_for_params (s
, TREE_OPERAND (e
, 0));
882 parameter_index_in_region (e
, s
);
895 /* Find parameters with respect to REGION in BB. We are looking in memory
896 access functions, conditions and loop bounds. */
899 find_params_in_bb (sese region
, gimple_bb_p gbb
)
905 loop_p loop
= GBB_BB (gbb
)->loop_father
;
907 /* Find parameters in the access functions of data references. */
908 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
909 for (j
= 0; j
< DR_NUM_DIMENSIONS (dr
); j
++)
910 scan_tree_for_params (region
, DR_ACCESS_FN (dr
, j
));
912 /* Find parameters in conditional statements. */
913 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
915 tree lhs
= scalar_evolution_in_region (region
, loop
,
916 gimple_cond_lhs (stmt
));
917 tree rhs
= scalar_evolution_in_region (region
, loop
,
918 gimple_cond_rhs (stmt
));
920 scan_tree_for_params (region
, lhs
);
921 scan_tree_for_params (region
, rhs
);
925 /* Record the parameters used in the SCOP. A variable is a parameter
926 in a scop if it does not vary during the execution of that scop. */
929 find_scop_parameters (scop_p scop
)
933 sese region
= SCOP_REGION (scop
);
937 /* Find the parameters used in the loop bounds. */
938 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
940 tree nb_iters
= number_of_latch_executions (loop
);
942 if (!chrec_contains_symbols (nb_iters
))
945 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
946 scan_tree_for_params (region
, nb_iters
);
949 /* Find the parameters used in data accesses. */
950 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
951 find_params_in_bb (region
, PBB_BLACK_BOX (pbb
));
953 nbp
= sese_nb_params (region
);
954 scop_set_nb_params (scop
, nbp
);
955 SESE_ADD_PARAMS (region
) = false;
959 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, nbp
, 0);
961 FOR_EACH_VEC_ELT (SESE_PARAMS (region
), i
, e
)
962 space
= isl_space_set_dim_id (space
, isl_dim_param
, i
,
963 isl_id_for_ssa_name (scop
, e
));
965 scop
->context
= isl_set_universe (space
);
969 /* Builds the constraint polyhedra for LOOP in SCOP. OUTER_PH gives
970 the constraints for the surrounding loops. */
973 build_loop_iteration_domains (scop_p scop
, struct loop
*loop
,
975 isl_set
*outer
, isl_set
**doms
)
977 tree nb_iters
= number_of_latch_executions (loop
);
978 sese region
= SCOP_REGION (scop
);
980 isl_set
*inner
= isl_set_copy (outer
);
983 int pos
= isl_set_dim (outer
, isl_dim_set
);
990 inner
= isl_set_add_dims (inner
, isl_dim_set
, 1);
991 space
= isl_set_get_space (inner
);
994 c
= isl_inequality_alloc
995 (isl_local_space_from_space (isl_space_copy (space
)));
996 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, 1);
997 inner
= isl_set_add_constraint (inner
, c
);
999 /* loop_i <= cst_nb_iters */
1000 if (TREE_CODE (nb_iters
) == INTEGER_CST
)
1002 c
= isl_inequality_alloc
1003 (isl_local_space_from_space(isl_space_copy (space
)));
1004 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1005 tree_int_to_gmp (nb_iters
, g
);
1006 isl_int_set_gmp (v
, g
);
1007 c
= isl_constraint_set_constant (c
, v
);
1008 inner
= isl_set_add_constraint (inner
, c
);
1011 /* loop_i <= expr_nb_iters */
1012 else if (!chrec_contains_undetermined (nb_iters
))
1017 isl_local_space
*ls
;
1021 nb_iters
= scalar_evolution_in_region (region
, loop
, nb_iters
);
1023 aff
= extract_affine (scop
, nb_iters
, isl_set_get_space (inner
));
1024 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff
));
1025 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1026 isl_set_dim (valid
, isl_dim_set
));
1027 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1029 ls
= isl_local_space_from_space (isl_space_copy (space
));
1030 al
= isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls
),
1031 isl_dim_in
, pos
, 1);
1032 le
= isl_pw_aff_le_set (isl_pw_aff_from_aff (al
),
1033 isl_pw_aff_copy (aff
));
1034 inner
= isl_set_intersect (inner
, le
);
1036 if (max_stmt_executions (loop
, &nit
))
1038 /* Insert in the context the constraints from the
1039 estimation of the number of iterations NIT and the
1040 symbolic number of iterations (involving parameter
1041 names) NB_ITERS. First, build the affine expression
1042 "NIT - NB_ITERS" and then say that it is positive,
1043 i.e., NIT approximates NB_ITERS: "NIT >= NB_ITERS". */
1050 mpz_set_double_int (g
, nit
, false);
1051 mpz_sub_ui (g
, g
, 1);
1052 approx
= extract_affine_gmp (g
, isl_set_get_space (inner
));
1053 x
= isl_pw_aff_ge_set (approx
, aff
);
1054 x
= isl_set_project_out (x
, isl_dim_set
, 0,
1055 isl_set_dim (x
, isl_dim_set
));
1056 scop
->context
= isl_set_intersect (scop
->context
, x
);
1058 c
= isl_inequality_alloc
1059 (isl_local_space_from_space (isl_space_copy (space
)));
1060 c
= isl_constraint_set_coefficient_si (c
, isl_dim_set
, pos
, -1);
1061 isl_int_set_gmp (v
, g
);
1063 c
= isl_constraint_set_constant (c
, v
);
1064 inner
= isl_set_add_constraint (inner
, c
);
1067 isl_pw_aff_free (aff
);
1072 if (loop
->inner
&& loop_in_sese_p (loop
->inner
, region
))
1073 build_loop_iteration_domains (scop
, loop
->inner
, nb
+ 1,
1074 isl_set_copy (inner
), doms
);
1078 && loop_in_sese_p (loop
->next
, region
))
1079 build_loop_iteration_domains (scop
, loop
->next
, nb
,
1080 isl_set_copy (outer
), doms
);
1082 doms
[loop
->num
] = inner
;
1084 isl_set_free (outer
);
1085 isl_space_free (space
);
1090 /* Returns a linear expression for tree T evaluated in PBB. */
1093 create_pw_aff_from_tree (poly_bb_p pbb
, tree t
)
1095 scop_p scop
= PBB_SCOP (pbb
);
1097 t
= scalar_evolution_in_region (SCOP_REGION (scop
), pbb_loop (pbb
), t
);
1098 gcc_assert (!automatically_generated_chrec_p (t
));
1100 return extract_affine (scop
, t
, isl_set_get_space (pbb
->domain
));
1103 /* Add conditional statement STMT to pbb. CODE is used as the comparison
1104 operator. This allows us to invert the condition or to handle
1108 add_condition_to_pbb (poly_bb_p pbb
, gimple stmt
, enum tree_code code
)
1110 isl_pw_aff
*lhs
= create_pw_aff_from_tree (pbb
, gimple_cond_lhs (stmt
));
1111 isl_pw_aff
*rhs
= create_pw_aff_from_tree (pbb
, gimple_cond_rhs (stmt
));
1117 cond
= isl_pw_aff_lt_set (lhs
, rhs
);
1121 cond
= isl_pw_aff_gt_set (lhs
, rhs
);
1125 cond
= isl_pw_aff_le_set (lhs
, rhs
);
1129 cond
= isl_pw_aff_ge_set (lhs
, rhs
);
1133 cond
= isl_pw_aff_eq_set (lhs
, rhs
);
1137 cond
= isl_pw_aff_ne_set (lhs
, rhs
);
1141 isl_pw_aff_free(lhs
);
1142 isl_pw_aff_free(rhs
);
1146 cond
= isl_set_coalesce (cond
);
1147 cond
= isl_set_set_tuple_id (cond
, isl_set_get_tuple_id (pbb
->domain
));
1148 pbb
->domain
= isl_set_intersect (pbb
->domain
, cond
);
1151 /* Add conditions to the domain of PBB. */
1154 add_conditions_to_domain (poly_bb_p pbb
)
1158 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
1160 if (GBB_CONDITIONS (gbb
).is_empty ())
1163 FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb
), i
, stmt
)
1164 switch (gimple_code (stmt
))
1168 enum tree_code code
= gimple_cond_code (stmt
);
1170 /* The conditions for ELSE-branches are inverted. */
1171 if (!GBB_CONDITION_CASES (gbb
)[i
])
1172 code
= invert_tree_comparison (code
, false);
1174 add_condition_to_pbb (pbb
, stmt
, code
);
1179 /* Switch statements are not supported right now - fall through. */
1187 /* Traverses all the GBBs of the SCOP and add their constraints to the
1188 iteration domains. */
1191 add_conditions_to_constraints (scop_p scop
)
1196 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1197 add_conditions_to_domain (pbb
);
1200 /* Structure used to pass data to dom_walk. */
1204 vec
<gimple
> *conditions
, *cases
;
1208 /* Returns a COND_EXPR statement when BB has a single predecessor, the
1209 edge between BB and its predecessor is not a loop exit edge, and
1210 the last statement of the single predecessor is a COND_EXPR. */
1213 single_pred_cond_non_loop_exit (basic_block bb
)
1215 if (single_pred_p (bb
))
1217 edge e
= single_pred_edge (bb
);
1218 basic_block pred
= e
->src
;
1221 if (loop_depth (pred
->loop_father
) > loop_depth (bb
->loop_father
))
1224 stmt
= last_stmt (pred
);
1226 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1233 /* Call-back for dom_walk executed before visiting the dominated
1237 build_sese_conditions_before (struct dom_walk_data
*dw_data
,
1240 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1241 vec
<gimple
> *conditions
= data
->conditions
;
1242 vec
<gimple
> *cases
= data
->cases
;
1246 if (!bb_in_sese_p (bb
, data
->region
))
1249 stmt
= single_pred_cond_non_loop_exit (bb
);
1253 edge e
= single_pred_edge (bb
);
1255 conditions
->safe_push (stmt
);
1257 if (e
->flags
& EDGE_TRUE_VALUE
)
1258 cases
->safe_push (stmt
);
1260 cases
->safe_push (NULL
);
1263 gbb
= gbb_from_bb (bb
);
1267 GBB_CONDITIONS (gbb
) = conditions
->copy ();
1268 GBB_CONDITION_CASES (gbb
) = cases
->copy ();
1272 /* Call-back for dom_walk executed after visiting the dominated
1276 build_sese_conditions_after (struct dom_walk_data
*dw_data
,
1279 struct bsc
*data
= (struct bsc
*) dw_data
->global_data
;
1280 vec
<gimple
> *conditions
= data
->conditions
;
1281 vec
<gimple
> *cases
= data
->cases
;
1283 if (!bb_in_sese_p (bb
, data
->region
))
1286 if (single_pred_cond_non_loop_exit (bb
))
1293 /* Record all conditions in REGION. */
1296 build_sese_conditions (sese region
)
1298 struct dom_walk_data walk_data
;
1299 vec
<gimple
> conditions
;
1300 conditions
.create (3);
1305 data
.conditions
= &conditions
;
1306 data
.cases
= &cases
;
1307 data
.region
= region
;
1309 walk_data
.dom_direction
= CDI_DOMINATORS
;
1310 walk_data
.initialize_block_local_data
= NULL
;
1311 walk_data
.before_dom_children
= build_sese_conditions_before
;
1312 walk_data
.after_dom_children
= build_sese_conditions_after
;
1313 walk_data
.global_data
= &data
;
1314 walk_data
.block_local_data_size
= 0;
1316 init_walk_dominator_tree (&walk_data
);
1317 walk_dominator_tree (&walk_data
, SESE_ENTRY_BB (region
));
1318 fini_walk_dominator_tree (&walk_data
);
1320 conditions
.release ();
1324 /* Add constraints on the possible values of parameter P from the type
1328 add_param_constraints (scop_p scop
, graphite_dim_t p
)
1330 tree parameter
= SESE_PARAMS (SCOP_REGION (scop
))[p
];
1331 tree type
= TREE_TYPE (parameter
);
1332 tree lb
= NULL_TREE
;
1333 tree ub
= NULL_TREE
;
1335 if (POINTER_TYPE_P (type
) || !TYPE_MIN_VALUE (type
))
1336 lb
= lower_bound_in_type (type
, type
);
1338 lb
= TYPE_MIN_VALUE (type
);
1340 if (POINTER_TYPE_P (type
) || !TYPE_MAX_VALUE (type
))
1341 ub
= upper_bound_in_type (type
, type
);
1343 ub
= TYPE_MAX_VALUE (type
);
1347 isl_space
*space
= isl_set_get_space (scop
->context
);
1352 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1355 tree_int_to_gmp (lb
, g
);
1356 isl_int_set_gmp (v
, g
);
1359 c
= isl_constraint_set_constant (c
, v
);
1361 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, 1);
1363 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1368 isl_space
*space
= isl_set_get_space (scop
->context
);
1373 c
= isl_inequality_alloc (isl_local_space_from_space (space
));
1377 tree_int_to_gmp (ub
, g
);
1378 isl_int_set_gmp (v
, g
);
1380 c
= isl_constraint_set_constant (c
, v
);
1382 c
= isl_constraint_set_coefficient_si (c
, isl_dim_param
, p
, -1);
1384 scop
->context
= isl_set_add_constraint (scop
->context
, c
);
1388 /* Build the context of the SCOP. The context usually contains extra
1389 constraints that are added to the iteration domains that constrain
1393 build_scop_context (scop_p scop
)
1395 graphite_dim_t p
, n
= scop_nb_params (scop
);
1397 for (p
= 0; p
< n
; p
++)
1398 add_param_constraints (scop
, p
);
1401 /* Build the iteration domains: the loops belonging to the current
1402 SCOP, and that vary for the execution of the current basic block.
1403 Returns false if there is no loop in SCOP. */
1406 build_scop_iteration_domain (scop_p scop
)
1409 sese region
= SCOP_REGION (scop
);
1412 int nb_loops
= number_of_loops ();
1413 isl_set
**doms
= XCNEWVEC (isl_set
*, nb_loops
);
1415 FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region
), i
, loop
)
1416 if (!loop_in_sese_p (loop_outer (loop
), region
))
1417 build_loop_iteration_domains (scop
, loop
, 0,
1418 isl_set_copy (scop
->context
), doms
);
1420 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1422 loop
= pbb_loop (pbb
);
1424 if (doms
[loop
->num
])
1425 pbb
->domain
= isl_set_copy (doms
[loop
->num
]);
1427 pbb
->domain
= isl_set_copy (scop
->context
);
1429 pbb
->domain
= isl_set_set_tuple_id (pbb
->domain
,
1430 isl_id_for_pbb (scop
, pbb
));
1433 for (i
= 0; i
< nb_loops
; i
++)
1435 isl_set_free (doms
[i
]);
1440 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1441 data reference DR. ACCESSP_NB_DIMS is the dimension of the
1442 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1446 pdr_add_alias_set (isl_map
*acc
, data_reference_p dr
)
1449 int alias_set_num
= 0;
1450 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1452 if (bap
&& bap
->alias_set
)
1453 alias_set_num
= *(bap
->alias_set
);
1455 c
= isl_equality_alloc
1456 (isl_local_space_from_space (isl_map_get_space (acc
)));
1457 c
= isl_constraint_set_constant_si (c
, -alias_set_num
);
1458 c
= isl_constraint_set_coefficient_si (c
, isl_dim_out
, 0, 1);
1460 return isl_map_add_constraint (acc
, c
);
1463 /* Assign the affine expression INDEX to the output dimension POS of
1464 MAP and return the result. */
1467 set_index (isl_map
*map
, int pos
, isl_pw_aff
*index
)
1470 int len
= isl_map_dim (map
, isl_dim_out
);
1473 index_map
= isl_map_from_pw_aff (index
);
1474 index_map
= isl_map_insert_dims (index_map
, isl_dim_out
, 0, pos
);
1475 index_map
= isl_map_add_dims (index_map
, isl_dim_out
, len
- pos
- 1);
1477 id
= isl_map_get_tuple_id (map
, isl_dim_out
);
1478 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_out
, id
);
1479 id
= isl_map_get_tuple_id (map
, isl_dim_in
);
1480 index_map
= isl_map_set_tuple_id (index_map
, isl_dim_in
, id
);
1482 return isl_map_intersect (map
, index_map
);
1485 /* Add to ACCESSES polyhedron equalities defining the access functions
1486 to the memory. ACCESSP_NB_DIMS is the dimension of the ACCESSES
1487 polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1488 PBB is the poly_bb_p that contains the data reference DR. */
1491 pdr_add_memory_accesses (isl_map
*acc
, data_reference_p dr
, poly_bb_p pbb
)
1493 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1494 scop_p scop
= PBB_SCOP (pbb
);
1496 for (i
= 0; i
< nb_subscripts
; i
++)
1499 tree afn
= DR_ACCESS_FN (dr
, nb_subscripts
- 1 - i
);
1501 aff
= extract_affine (scop
, afn
,
1502 isl_space_domain (isl_map_get_space (acc
)));
1503 acc
= set_index (acc
, i
+ 1, aff
);
1509 /* Add constrains representing the size of the accessed data to the
1510 ACCESSES polyhedron. ACCESSP_NB_DIMS is the dimension of the
1511 ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1515 pdr_add_data_dimensions (isl_set
*extent
, scop_p scop
, data_reference_p dr
)
1517 tree ref
= DR_REF (dr
);
1518 int i
, nb_subscripts
= DR_NUM_DIMENSIONS (dr
);
1520 for (i
= nb_subscripts
- 1; i
>= 0; i
--, ref
= TREE_OPERAND (ref
, 0))
1524 if (TREE_CODE (ref
) != ARRAY_REF
)
1527 low
= array_ref_low_bound (ref
);
1528 high
= array_ref_up_bound (ref
);
1530 /* XXX The PPL code dealt separately with
1531 subscript - low >= 0 and high - subscript >= 0 in case one of
1532 the two bounds isn't known. Do the same here? */
1534 if (host_integerp (low
, 0)
1536 && host_integerp (high
, 0)
1537 /* 1-element arrays at end of structures may extend over
1538 their declared size. */
1539 && !(array_at_struct_end_p (ref
)
1540 && operand_equal_p (low
, high
, 0)))
1544 isl_set
*univ
, *lbs
, *ubs
;
1548 isl_pw_aff
*lb
= extract_affine_int (low
, isl_set_get_space (extent
));
1549 isl_pw_aff
*ub
= extract_affine_int (high
, isl_set_get_space (extent
));
1552 valid
= isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub
));
1553 valid
= isl_set_project_out (valid
, isl_dim_set
, 0,
1554 isl_set_dim (valid
, isl_dim_set
));
1555 scop
->context
= isl_set_intersect (scop
->context
, valid
);
1557 space
= isl_set_get_space (extent
);
1558 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (space
));
1559 aff
= isl_aff_add_coefficient_si (aff
, isl_dim_in
, i
+ 1, 1);
1560 univ
= isl_set_universe (isl_space_domain (isl_aff_get_space (aff
)));
1561 index
= isl_pw_aff_alloc (univ
, aff
);
1563 id
= isl_set_get_tuple_id (extent
);
1564 lb
= isl_pw_aff_set_tuple_id (lb
, isl_dim_in
, isl_id_copy (id
));
1565 ub
= isl_pw_aff_set_tuple_id (ub
, isl_dim_in
, id
);
1567 /* low <= sub_i <= high */
1568 lbs
= isl_pw_aff_ge_set (isl_pw_aff_copy (index
), lb
);
1569 ubs
= isl_pw_aff_le_set (index
, ub
);
1570 extent
= isl_set_intersect (extent
, lbs
);
1571 extent
= isl_set_intersect (extent
, ubs
);
1578 /* Build data accesses for DR in PBB. */
1581 build_poly_dr (data_reference_p dr
, poly_bb_p pbb
)
1583 int dr_base_object_set
;
1586 scop_p scop
= PBB_SCOP (pbb
);
1589 isl_space
*dc
= isl_set_get_space (pbb
->domain
);
1590 int nb_out
= 1 + DR_NUM_DIMENSIONS (dr
);
1591 isl_space
*space
= isl_space_add_dims (isl_space_from_domain (dc
),
1592 isl_dim_out
, nb_out
);
1594 acc
= isl_map_universe (space
);
1595 acc
= isl_map_set_tuple_id (acc
, isl_dim_out
, isl_id_for_dr (scop
, dr
));
1598 acc
= pdr_add_alias_set (acc
, dr
);
1599 acc
= pdr_add_memory_accesses (acc
, dr
, pbb
);
1602 isl_id
*id
= isl_id_for_dr (scop
, dr
);
1603 int nb
= 1 + DR_NUM_DIMENSIONS (dr
);
1604 isl_space
*space
= isl_space_set_alloc (scop
->ctx
, 0, nb
);
1605 int alias_set_num
= 0;
1606 base_alias_pair
*bap
= (base_alias_pair
*)(dr
->aux
);
1608 if (bap
&& bap
->alias_set
)
1609 alias_set_num
= *(bap
->alias_set
);
1611 space
= isl_space_set_tuple_id (space
, isl_dim_set
, id
);
1612 extent
= isl_set_nat_universe (space
);
1613 extent
= isl_set_fix_si (extent
, isl_dim_set
, 0, alias_set_num
);
1614 extent
= pdr_add_data_dimensions (extent
, scop
, dr
);
1617 gcc_assert (dr
->aux
);
1618 dr_base_object_set
= ((base_alias_pair
*)(dr
->aux
))->base_obj_set
;
1620 new_poly_dr (pbb
, dr_base_object_set
,
1621 DR_IS_READ (dr
) ? PDR_READ
: PDR_WRITE
,
1622 dr
, DR_NUM_DIMENSIONS (dr
), acc
, extent
);
1625 /* Write to FILE the alias graph of data references in DIMACS format. */
1628 write_alias_graph_to_ascii_dimacs (FILE *file
, char *comment
,
1629 vec
<data_reference_p
> drs
)
1631 int num_vertex
= drs
.length ();
1633 data_reference_p dr1
, dr2
;
1636 if (num_vertex
== 0)
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))
1644 fprintf (file
, "$\n");
1647 fprintf (file
, "c %s\n", comment
);
1649 fprintf (file
, "p edge %d %d\n", num_vertex
, edge_num
);
1651 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1652 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1653 if (dr_may_alias_p (dr1
, dr2
, true))
1654 fprintf (file
, "e %d %d\n", i
+ 1, j
+ 1);
1659 /* Write to FILE the alias graph of data references in DOT format. */
1662 write_alias_graph_to_ascii_dot (FILE *file
, char *comment
,
1663 vec
<data_reference_p
> drs
)
1665 int num_vertex
= drs
.length ();
1666 data_reference_p dr1
, dr2
;
1669 if (num_vertex
== 0)
1672 fprintf (file
, "$\n");
1675 fprintf (file
, "c %s\n", comment
);
1677 /* First print all the vertices. */
1678 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1679 fprintf (file
, "n%d;\n", i
);
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
, "n%d n%d\n", i
, j
);
1689 /* Write to FILE the alias graph of data references in ECC format. */
1692 write_alias_graph_to_ascii_ecc (FILE *file
, char *comment
,
1693 vec
<data_reference_p
> drs
)
1695 int num_vertex
= drs
.length ();
1696 data_reference_p dr1
, dr2
;
1699 if (num_vertex
== 0)
1702 fprintf (file
, "$\n");
1705 fprintf (file
, "c %s\n", comment
);
1707 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1708 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1709 if (dr_may_alias_p (dr1
, dr2
, true))
1710 fprintf (file
, "%d %d\n", i
, j
);
1715 /* Check if DR1 and DR2 are in the same object set. */
1718 dr_same_base_object_p (const struct data_reference
*dr1
,
1719 const struct data_reference
*dr2
)
1721 return operand_equal_p (DR_BASE_OBJECT (dr1
), DR_BASE_OBJECT (dr2
), 0);
1724 /* Uses DFS component number as representative of alias-sets. Also tests for
1725 optimality by verifying if every connected component is a clique. Returns
1726 true (1) if the above test is true, and false (0) otherwise. */
1729 build_alias_set_optimal_p (vec
<data_reference_p
> drs
)
1731 int num_vertices
= drs
.length ();
1732 struct graph
*g
= new_graph (num_vertices
);
1733 data_reference_p dr1
, dr2
;
1735 int num_connected_components
;
1736 int v_indx1
, v_indx2
, num_vertices_in_component
;
1739 struct graph_edge
*e
;
1740 int this_component_is_clique
;
1741 int all_components_are_cliques
= 1;
1743 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1744 for (j
= i
+1; drs
.iterate (j
, &dr2
); j
++)
1745 if (dr_may_alias_p (dr1
, dr2
, true))
1751 all_vertices
= XNEWVEC (int, num_vertices
);
1752 vertices
= XNEWVEC (int, num_vertices
);
1753 for (i
= 0; i
< num_vertices
; i
++)
1754 all_vertices
[i
] = i
;
1756 num_connected_components
= graphds_dfs (g
, all_vertices
, num_vertices
,
1758 for (i
= 0; i
< g
->n_vertices
; i
++)
1760 data_reference_p dr
= drs
[i
];
1761 base_alias_pair
*bap
;
1763 gcc_assert (dr
->aux
);
1764 bap
= (base_alias_pair
*)(dr
->aux
);
1766 bap
->alias_set
= XNEW (int);
1767 *(bap
->alias_set
) = g
->vertices
[i
].component
+ 1;
1770 /* Verify if the DFS numbering results in optimal solution. */
1771 for (i
= 0; i
< num_connected_components
; i
++)
1773 num_vertices_in_component
= 0;
1774 /* Get all vertices whose DFS component number is the same as i. */
1775 for (j
= 0; j
< num_vertices
; j
++)
1776 if (g
->vertices
[j
].component
== i
)
1777 vertices
[num_vertices_in_component
++] = j
;
1779 /* Now test if the vertices in 'vertices' form a clique, by testing
1780 for edges among each pair. */
1781 this_component_is_clique
= 1;
1782 for (v_indx1
= 0; v_indx1
< num_vertices_in_component
; v_indx1
++)
1784 for (v_indx2
= v_indx1
+1; v_indx2
< num_vertices_in_component
; v_indx2
++)
1786 /* Check if the two vertices are connected by iterating
1787 through all the edges which have one of these are source. */
1788 e
= g
->vertices
[vertices
[v_indx2
]].pred
;
1791 if (e
->src
== vertices
[v_indx1
])
1797 this_component_is_clique
= 0;
1801 if (!this_component_is_clique
)
1802 all_components_are_cliques
= 0;
1806 free (all_vertices
);
1809 return all_components_are_cliques
;
1812 /* Group each data reference in DRS with its base object set num. */
1815 build_base_obj_set_for_drs (vec
<data_reference_p
> drs
)
1817 int num_vertex
= drs
.length ();
1818 struct graph
*g
= new_graph (num_vertex
);
1819 data_reference_p dr1
, dr2
;
1823 FOR_EACH_VEC_ELT (drs
, i
, dr1
)
1824 for (j
= i
+ 1; drs
.iterate (j
, &dr2
); j
++)
1825 if (dr_same_base_object_p (dr1
, dr2
))
1831 queue
= XNEWVEC (int, num_vertex
);
1832 for (i
= 0; i
< num_vertex
; i
++)
1835 graphds_dfs (g
, queue
, num_vertex
, NULL
, true, NULL
);
1837 for (i
= 0; i
< g
->n_vertices
; i
++)
1839 data_reference_p dr
= drs
[i
];
1840 base_alias_pair
*bap
;
1842 gcc_assert (dr
->aux
);
1843 bap
= (base_alias_pair
*)(dr
->aux
);
1845 bap
->base_obj_set
= g
->vertices
[i
].component
+ 1;
1852 /* Build the data references for PBB. */
1855 build_pbb_drs (poly_bb_p pbb
)
1858 data_reference_p dr
;
1859 vec
<data_reference_p
> gbb_drs
= GBB_DATA_REFS (PBB_BLACK_BOX (pbb
));
1861 FOR_EACH_VEC_ELT (gbb_drs
, j
, dr
)
1862 build_poly_dr (dr
, pbb
);
1865 /* Dump to file the alias graphs for the data references in DRS. */
1868 dump_alias_graphs (vec
<data_reference_p
> drs
)
1871 FILE *file_dimacs
, *file_ecc
, *file_dot
;
1873 file_dimacs
= fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1876 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1877 current_function_name ());
1878 write_alias_graph_to_ascii_dimacs (file_dimacs
, comment
, drs
);
1879 fclose (file_dimacs
);
1882 file_ecc
= fopen ("/tmp/dr_alias_graph_ecc", "ab");
1885 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1886 current_function_name ());
1887 write_alias_graph_to_ascii_ecc (file_ecc
, comment
, drs
);
1891 file_dot
= fopen ("/tmp/dr_alias_graph_dot", "ab");
1894 snprintf (comment
, sizeof (comment
), "%s %s", main_input_filename
,
1895 current_function_name ());
1896 write_alias_graph_to_ascii_dot (file_dot
, comment
, drs
);
1901 /* Build data references in SCOP. */
1904 build_scop_drs (scop_p scop
)
1908 data_reference_p dr
;
1909 vec
<data_reference_p
> drs
;
1912 /* Remove all the PBBs that do not have data references: these basic
1913 blocks are not handled in the polyhedral representation. */
1914 for (i
= 0; SCOP_BBS (scop
).iterate (i
, &pbb
); i
++)
1915 if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).is_empty ())
1917 free_gimple_bb (PBB_BLACK_BOX (pbb
));
1919 SCOP_BBS (scop
).ordered_remove (i
);
1923 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1924 for (j
= 0; GBB_DATA_REFS (PBB_BLACK_BOX (pbb
)).iterate (j
, &dr
); j
++)
1927 FOR_EACH_VEC_ELT (drs
, i
, dr
)
1928 dr
->aux
= XNEW (base_alias_pair
);
1930 if (!build_alias_set_optimal_p (drs
))
1932 /* TODO: Add support when building alias set is not optimal. */
1936 build_base_obj_set_for_drs (drs
);
1938 /* When debugging, enable the following code. This cannot be used
1939 in production compilers. */
1941 dump_alias_graphs (drs
);
1945 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
1946 build_pbb_drs (pbb
);
1949 /* Return a gsi at the position of the phi node STMT. */
1951 static gimple_stmt_iterator
1952 gsi_for_phi_node (gimple stmt
)
1954 gimple_stmt_iterator psi
;
1955 basic_block bb
= gimple_bb (stmt
);
1957 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
1958 if (stmt
== gsi_stmt (psi
))
1965 /* Analyze all the data references of STMTS and add them to the
1966 GBB_DATA_REFS vector of BB. */
1969 analyze_drs_in_stmts (scop_p scop
, basic_block bb
, vec
<gimple
> stmts
)
1975 sese region
= SCOP_REGION (scop
);
1977 if (!bb_in_sese_p (bb
, region
))
1980 nest
= outermost_loop_in_sese_1 (region
, bb
);
1981 gbb
= gbb_from_bb (bb
);
1983 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
1987 if (is_gimple_debug (stmt
))
1990 loop
= loop_containing_stmt (stmt
);
1991 if (!loop_in_sese_p (loop
, region
))
1994 graphite_find_data_references_in_stmt (nest
, loop
, stmt
,
1995 &GBB_DATA_REFS (gbb
));
1999 /* Insert STMT at the end of the STMTS sequence and then insert the
2000 statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2004 insert_stmts (scop_p scop
, gimple stmt
, gimple_seq stmts
,
2005 gimple_stmt_iterator insert_gsi
)
2007 gimple_stmt_iterator gsi
;
2011 gimple_seq_add_stmt (&stmts
, stmt
);
2012 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2013 x
.safe_push (gsi_stmt (gsi
));
2015 gsi_insert_seq_before (&insert_gsi
, stmts
, GSI_SAME_STMT
);
2016 analyze_drs_in_stmts (scop
, gsi_bb (insert_gsi
), x
);
2020 /* Insert the assignment "RES := EXPR" just after AFTER_STMT. */
2023 insert_out_of_ssa_copy (scop_p scop
, tree res
, tree expr
, gimple after_stmt
)
2026 gimple_stmt_iterator gsi
;
2027 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2028 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2032 gimple_seq_add_stmt (&stmts
, stmt
);
2033 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2034 x
.safe_push (gsi_stmt (gsi
));
2036 if (gimple_code (after_stmt
) == GIMPLE_PHI
)
2038 gsi
= gsi_after_labels (gimple_bb (after_stmt
));
2039 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
2043 gsi
= gsi_for_stmt (after_stmt
);
2044 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
2047 analyze_drs_in_stmts (scop
, gimple_bb (after_stmt
), x
);
2051 /* Creates a poly_bb_p for basic_block BB from the existing PBB. */
2054 new_pbb_from_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
)
2056 vec
<data_reference_p
> drs
;
2058 gimple_bb_p gbb
= PBB_BLACK_BOX (pbb
);
2059 gimple_bb_p gbb1
= new_gimple_bb (bb
, drs
);
2060 poly_bb_p pbb1
= new_poly_bb (scop
, gbb1
);
2061 int index
, n
= SCOP_BBS (scop
).length ();
2063 /* The INDEX of PBB in SCOP_BBS. */
2064 for (index
= 0; index
< n
; index
++)
2065 if (SCOP_BBS (scop
)[index
] == pbb
)
2068 pbb1
->domain
= isl_set_copy (pbb
->domain
);
2070 GBB_PBB (gbb1
) = pbb1
;
2071 GBB_CONDITIONS (gbb1
) = GBB_CONDITIONS (gbb
).copy ();
2072 GBB_CONDITION_CASES (gbb1
) = GBB_CONDITION_CASES (gbb
).copy ();
2073 SCOP_BBS (scop
).safe_insert (index
+ 1, pbb1
);
2076 /* Insert on edge E the assignment "RES := EXPR". */
2079 insert_out_of_ssa_copy_on_edge (scop_p scop
, edge e
, tree res
, tree expr
)
2081 gimple_stmt_iterator gsi
;
2082 gimple_seq stmts
= NULL
;
2083 tree var
= force_gimple_operand (expr
, &stmts
, true, NULL_TREE
);
2084 gimple stmt
= gimple_build_assign (unshare_expr (res
), var
);
2089 gimple_seq_add_stmt (&stmts
, stmt
);
2090 for (gsi
= gsi_start (stmts
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2091 x
.safe_push (gsi_stmt (gsi
));
2093 gsi_insert_seq_on_edge (e
, stmts
);
2094 gsi_commit_edge_inserts ();
2095 bb
= gimple_bb (stmt
);
2097 if (!bb_in_sese_p (bb
, SCOP_REGION (scop
)))
2100 if (!gbb_from_bb (bb
))
2101 new_pbb_from_pbb (scop
, pbb_from_bb (e
->src
), bb
);
2103 analyze_drs_in_stmts (scop
, bb
, x
);
2107 /* Creates a zero dimension array of the same type as VAR. */
2110 create_zero_dim_array (tree var
, const char *base_name
)
2112 tree index_type
= build_index_type (integer_zero_node
);
2113 tree elt_type
= TREE_TYPE (var
);
2114 tree array_type
= build_array_type (elt_type
, index_type
);
2115 tree base
= create_tmp_var (array_type
, base_name
);
2117 return build4 (ARRAY_REF
, elt_type
, base
, integer_zero_node
, NULL_TREE
,
2121 /* Returns true when PHI is a loop close phi node. */
2124 scalar_close_phi_node_p (gimple phi
)
2126 if (gimple_code (phi
) != GIMPLE_PHI
2127 || virtual_operand_p (gimple_phi_result (phi
)))
2130 /* Note that loop close phi nodes should have a single argument
2131 because we translated the representation into a canonical form
2132 before Graphite: see canonicalize_loop_closed_ssa_form. */
2133 return (gimple_phi_num_args (phi
) == 1);
2136 /* For a definition DEF in REGION, propagates the expression EXPR in
2137 all the uses of DEF outside REGION. */
2140 propagate_expr_outside_region (tree def
, tree expr
, sese region
)
2142 imm_use_iterator imm_iter
;
2145 bool replaced_once
= false;
2147 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
2149 expr
= force_gimple_operand (unshare_expr (expr
), &stmts
, true,
2152 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2153 if (!is_gimple_debug (use_stmt
)
2154 && !bb_in_sese_p (gimple_bb (use_stmt
), region
))
2157 use_operand_p use_p
;
2159 FOR_EACH_PHI_OR_STMT_USE (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2160 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0)
2161 && (replaced_once
= true))
2162 replace_exp (use_p
, expr
);
2164 update_stmt (use_stmt
);
2169 gsi_insert_seq_on_edge (SESE_ENTRY (region
), stmts
);
2170 gsi_commit_edge_inserts ();
2174 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2175 dimension array for it. */
2178 rewrite_close_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2180 sese region
= SCOP_REGION (scop
);
2181 gimple phi
= gsi_stmt (*psi
);
2182 tree res
= gimple_phi_result (phi
);
2183 basic_block bb
= gimple_bb (phi
);
2184 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2185 tree arg
= gimple_phi_arg_def (phi
, 0);
2188 /* Note that loop close phi nodes should have a single argument
2189 because we translated the representation into a canonical form
2190 before Graphite: see canonicalize_loop_closed_ssa_form. */
2191 gcc_assert (gimple_phi_num_args (phi
) == 1);
2193 /* The phi node can be a non close phi node, when its argument is
2194 invariant, or a default definition. */
2195 if (is_gimple_min_invariant (arg
)
2196 || SSA_NAME_IS_DEFAULT_DEF (arg
))
2198 propagate_expr_outside_region (res
, arg
, region
);
2203 else if (gimple_bb (SSA_NAME_DEF_STMT (arg
))->loop_father
== bb
->loop_father
)
2205 propagate_expr_outside_region (res
, arg
, region
);
2206 stmt
= gimple_build_assign (res
, arg
);
2207 remove_phi_node (psi
, false);
2208 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2209 SSA_NAME_DEF_STMT (res
) = stmt
;
2213 /* If res is scev analyzable and is not a scalar value, it is safe
2214 to ignore the close phi node: it will be code generated in the
2215 out of Graphite pass. */
2216 else if (scev_analyzable_p (res
, region
))
2218 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (res
));
2221 if (!loop_in_sese_p (loop
, region
))
2223 loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2224 scev
= scalar_evolution_in_region (region
, loop
, arg
);
2225 scev
= compute_overall_effect_of_inner_loop (loop
, scev
);
2228 scev
= scalar_evolution_in_region (region
, loop
, res
);
2230 if (tree_does_not_contain_chrecs (scev
))
2231 propagate_expr_outside_region (res
, scev
, region
);
2238 tree zero_dim_array
= create_zero_dim_array (res
, "Close_Phi");
2240 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2242 if (TREE_CODE (arg
) == SSA_NAME
)
2243 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2244 SSA_NAME_DEF_STMT (arg
));
2246 insert_out_of_ssa_copy_on_edge (scop
, single_pred_edge (bb
),
2247 zero_dim_array
, arg
);
2250 remove_phi_node (psi
, false);
2251 SSA_NAME_DEF_STMT (res
) = stmt
;
2253 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2256 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2257 dimension array for it. */
2260 rewrite_phi_out_of_ssa (scop_p scop
, gimple_stmt_iterator
*psi
)
2263 gimple phi
= gsi_stmt (*psi
);
2264 basic_block bb
= gimple_bb (phi
);
2265 tree res
= gimple_phi_result (phi
);
2266 tree zero_dim_array
= create_zero_dim_array (res
, "phi_out_of_ssa");
2269 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2271 tree arg
= gimple_phi_arg_def (phi
, i
);
2272 edge e
= gimple_phi_arg_edge (phi
, i
);
2274 /* Avoid the insertion of code in the loop latch to please the
2275 pattern matching of the vectorizer. */
2276 if (TREE_CODE (arg
) == SSA_NAME
2277 && e
->src
== bb
->loop_father
->latch
)
2278 insert_out_of_ssa_copy (scop
, zero_dim_array
, arg
,
2279 SSA_NAME_DEF_STMT (arg
));
2281 insert_out_of_ssa_copy_on_edge (scop
, e
, zero_dim_array
, arg
);
2284 stmt
= gimple_build_assign (res
, unshare_expr (zero_dim_array
));
2285 remove_phi_node (psi
, false);
2286 SSA_NAME_DEF_STMT (res
) = stmt
;
2287 insert_stmts (scop
, stmt
, NULL
, gsi_after_labels (bb
));
2290 /* Rewrite the degenerate phi node at position PSI from the degenerate
2291 form "x = phi (y, y, ..., y)" to "x = y". */
2294 rewrite_degenerate_phi (gimple_stmt_iterator
*psi
)
2298 gimple_stmt_iterator gsi
;
2299 gimple phi
= gsi_stmt (*psi
);
2300 tree res
= gimple_phi_result (phi
);
2303 bb
= gimple_bb (phi
);
2304 rhs
= degenerate_phi_result (phi
);
2307 stmt
= gimple_build_assign (res
, rhs
);
2308 remove_phi_node (psi
, false);
2309 SSA_NAME_DEF_STMT (res
) = stmt
;
2311 gsi
= gsi_after_labels (bb
);
2312 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2315 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2318 rewrite_reductions_out_of_ssa (scop_p scop
)
2321 gimple_stmt_iterator psi
;
2322 sese region
= SCOP_REGION (scop
);
2325 if (bb_in_sese_p (bb
, region
))
2326 for (psi
= gsi_start_phis (bb
); !gsi_end_p (psi
);)
2328 gimple phi
= gsi_stmt (psi
);
2330 if (virtual_operand_p (gimple_phi_result (phi
)))
2336 if (gimple_phi_num_args (phi
) > 1
2337 && degenerate_phi_result (phi
))
2338 rewrite_degenerate_phi (&psi
);
2340 else if (scalar_close_phi_node_p (phi
))
2341 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2343 else if (reduction_phi_p (region
, &psi
))
2344 rewrite_phi_out_of_ssa (scop
, &psi
);
2347 update_ssa (TODO_update_ssa
);
2348 #ifdef ENABLE_CHECKING
2349 verify_loop_closed_ssa (true);
2353 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2354 read from ZERO_DIM_ARRAY. */
2357 rewrite_cross_bb_scalar_dependence (scop_p scop
, tree zero_dim_array
,
2358 tree def
, gimple use_stmt
)
2363 use_operand_p use_p
;
2365 gcc_assert (gimple_code (use_stmt
) != GIMPLE_PHI
);
2367 name
= copy_ssa_name (def
, NULL
);
2368 name_stmt
= gimple_build_assign (name
, zero_dim_array
);
2370 gimple_assign_set_lhs (name_stmt
, name
);
2371 insert_stmts (scop
, name_stmt
, NULL
, gsi_for_stmt (use_stmt
));
2373 FOR_EACH_SSA_USE_OPERAND (use_p
, use_stmt
, iter
, SSA_OP_ALL_USES
)
2374 if (operand_equal_p (def
, USE_FROM_PTR (use_p
), 0))
2375 replace_exp (use_p
, name
);
2377 update_stmt (use_stmt
);
2380 /* For every definition DEF in the SCOP that is used outside the scop,
2381 insert a closing-scop definition in the basic block just after this
2385 handle_scalar_deps_crossing_scop_limits (scop_p scop
, tree def
, gimple stmt
)
2387 tree var
= create_tmp_reg (TREE_TYPE (def
), NULL
);
2388 tree new_name
= make_ssa_name (var
, stmt
);
2389 bool needs_copy
= false;
2390 use_operand_p use_p
;
2391 imm_use_iterator imm_iter
;
2393 sese region
= SCOP_REGION (scop
);
2395 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2397 if (!bb_in_sese_p (gimple_bb (use_stmt
), region
))
2399 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
2401 SET_USE (use_p
, new_name
);
2403 update_stmt (use_stmt
);
2408 /* Insert in the empty BB just after the scop a use of DEF such
2409 that the rewrite of cross_bb_scalar_dependences won't insert
2410 arrays everywhere else. */
2413 gimple assign
= gimple_build_assign (new_name
, def
);
2414 gimple_stmt_iterator psi
= gsi_after_labels (SESE_EXIT (region
)->dest
);
2416 SSA_NAME_DEF_STMT (new_name
) = assign
;
2417 update_stmt (assign
);
2418 gsi_insert_before (&psi
, assign
, GSI_SAME_STMT
);
2422 /* Rewrite the scalar dependences crossing the boundary of the BB
2423 containing STMT with an array. Return true when something has been
2427 rewrite_cross_bb_scalar_deps (scop_p scop
, gimple_stmt_iterator
*gsi
)
2429 sese region
= SCOP_REGION (scop
);
2430 gimple stmt
= gsi_stmt (*gsi
);
2431 imm_use_iterator imm_iter
;
2434 tree zero_dim_array
= NULL_TREE
;
2438 switch (gimple_code (stmt
))
2441 def
= gimple_assign_lhs (stmt
);
2445 def
= gimple_call_lhs (stmt
);
2453 || !is_gimple_reg (def
))
2456 if (scev_analyzable_p (def
, region
))
2458 loop_p loop
= loop_containing_stmt (SSA_NAME_DEF_STMT (def
));
2459 tree scev
= scalar_evolution_in_region (region
, loop
, def
);
2461 if (tree_contains_chrecs (scev
, NULL
))
2464 propagate_expr_outside_region (def
, scev
, region
);
2468 def_bb
= gimple_bb (stmt
);
2470 handle_scalar_deps_crossing_scop_limits (scop
, def
, stmt
);
2472 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2473 if (gimple_code (use_stmt
) == GIMPLE_PHI
2476 gimple_stmt_iterator psi
= gsi_for_stmt (use_stmt
);
2478 if (scalar_close_phi_node_p (gsi_stmt (psi
)))
2479 rewrite_close_phi_out_of_ssa (scop
, &psi
);
2481 rewrite_phi_out_of_ssa (scop
, &psi
);
2484 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, def
)
2485 if (gimple_code (use_stmt
) != GIMPLE_PHI
2486 && def_bb
!= gimple_bb (use_stmt
)
2487 && !is_gimple_debug (use_stmt
)
2490 if (!zero_dim_array
)
2492 zero_dim_array
= create_zero_dim_array
2493 (def
, "Cross_BB_scalar_dependence");
2494 insert_out_of_ssa_copy (scop
, zero_dim_array
, def
,
2495 SSA_NAME_DEF_STMT (def
));
2499 rewrite_cross_bb_scalar_dependence (scop
, zero_dim_array
,
2506 /* Rewrite out of SSA all the reduction phi nodes of SCOP. */
2509 rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop
)
2512 gimple_stmt_iterator psi
;
2513 sese region
= SCOP_REGION (scop
);
2514 bool changed
= false;
2516 /* Create an extra empty BB after the scop. */
2517 split_edge (SESE_EXIT (region
));
2520 if (bb_in_sese_p (bb
, region
))
2521 for (psi
= gsi_start_bb (bb
); !gsi_end_p (psi
); gsi_next (&psi
))
2522 changed
|= rewrite_cross_bb_scalar_deps (scop
, &psi
);
2527 update_ssa (TODO_update_ssa
);
2528 #ifdef ENABLE_CHECKING
2529 verify_loop_closed_ssa (true);
2534 /* Returns the number of pbbs that are in loops contained in SCOP. */
2537 nb_pbbs_in_loops (scop_p scop
)
2543 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
2544 if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb
)), SCOP_REGION (scop
)))
2550 /* Return the number of data references in BB that write in
2554 nb_data_writes_in_bb (basic_block bb
)
2557 gimple_stmt_iterator gsi
;
2559 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2560 if (gimple_vdef (gsi_stmt (gsi
)))
2566 /* Splits at STMT the basic block BB represented as PBB in the
2570 split_pbb (scop_p scop
, poly_bb_p pbb
, basic_block bb
, gimple stmt
)
2572 edge e1
= split_block (bb
, stmt
);
2573 new_pbb_from_pbb (scop
, pbb
, e1
->dest
);
2577 /* Splits STMT out of its current BB. This is done for reduction
2578 statements for which we want to ignore data dependences. */
2581 split_reduction_stmt (scop_p scop
, gimple stmt
)
2583 basic_block bb
= gimple_bb (stmt
);
2584 poly_bb_p pbb
= pbb_from_bb (bb
);
2585 gimple_bb_p gbb
= gbb_from_bb (bb
);
2588 data_reference_p dr
;
2590 /* Do not split basic blocks with no writes to memory: the reduction
2591 will be the only write to memory. */
2592 if (nb_data_writes_in_bb (bb
) == 0
2593 /* Or if we have already marked BB as a reduction. */
2594 || PBB_IS_REDUCTION (pbb_from_bb (bb
)))
2597 e1
= split_pbb (scop
, pbb
, bb
, stmt
);
2599 /* Split once more only when the reduction stmt is not the only one
2600 left in the original BB. */
2601 if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb
)))
2603 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2605 e1
= split_pbb (scop
, pbb
, bb
, gsi_stmt (gsi
));
2608 /* A part of the data references will end in a different basic block
2609 after the split: move the DRs from the original GBB to the newly
2611 FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb
), i
, dr
)
2613 basic_block bb1
= gimple_bb (DR_STMT (dr
));
2617 gimple_bb_p gbb1
= gbb_from_bb (bb1
);
2618 GBB_DATA_REFS (gbb1
).safe_push (dr
);
2619 GBB_DATA_REFS (gbb
).ordered_remove (i
);
2627 /* Return true when stmt is a reduction operation. */
2630 is_reduction_operation_p (gimple stmt
)
2632 enum tree_code code
;
2634 gcc_assert (is_gimple_assign (stmt
));
2635 code
= gimple_assign_rhs_code (stmt
);
2637 return flag_associative_math
2638 && commutative_tree_code (code
)
2639 && associative_tree_code (code
);
2642 /* Returns true when PHI contains an argument ARG. */
2645 phi_contains_arg (gimple phi
, tree arg
)
2649 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2650 if (operand_equal_p (arg
, gimple_phi_arg_def (phi
, i
), 0))
2656 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2659 follow_ssa_with_commutative_ops (tree arg
, tree lhs
)
2663 if (TREE_CODE (arg
) != SSA_NAME
)
2666 stmt
= SSA_NAME_DEF_STMT (arg
);
2668 if (gimple_code (stmt
) == GIMPLE_NOP
2669 || gimple_code (stmt
) == GIMPLE_CALL
)
2672 if (gimple_code (stmt
) == GIMPLE_PHI
)
2674 if (phi_contains_arg (stmt
, lhs
))
2679 if (!is_gimple_assign (stmt
))
2682 if (gimple_num_ops (stmt
) == 2)
2683 return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2685 if (is_reduction_operation_p (stmt
))
2687 gimple res
= follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt
), lhs
);
2690 follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt
), lhs
);
2696 /* Detect commutative and associative scalar reductions starting at
2697 the STMT. Return the phi node of the reduction cycle, or NULL. */
2700 detect_commutative_reduction_arg (tree lhs
, gimple stmt
, tree arg
,
2704 gimple phi
= follow_ssa_with_commutative_ops (arg
, lhs
);
2709 in
->safe_push (stmt
);
2710 out
->safe_push (stmt
);
2714 /* Detect commutative and associative scalar reductions starting at
2715 STMT. Return the phi node of the reduction cycle, or NULL. */
2718 detect_commutative_reduction_assign (gimple stmt
, vec
<gimple
> *in
,
2721 tree lhs
= gimple_assign_lhs (stmt
);
2723 if (gimple_num_ops (stmt
) == 2)
2724 return detect_commutative_reduction_arg (lhs
, stmt
,
2725 gimple_assign_rhs1 (stmt
),
2728 if (is_reduction_operation_p (stmt
))
2730 gimple res
= detect_commutative_reduction_arg (lhs
, stmt
,
2731 gimple_assign_rhs1 (stmt
),
2734 : detect_commutative_reduction_arg (lhs
, stmt
,
2735 gimple_assign_rhs2 (stmt
),
2742 /* Return a loop phi node that corresponds to a reduction containing LHS. */
2745 follow_inital_value_to_phi (tree arg
, tree lhs
)
2749 if (!arg
|| TREE_CODE (arg
) != SSA_NAME
)
2752 stmt
= SSA_NAME_DEF_STMT (arg
);
2754 if (gimple_code (stmt
) == GIMPLE_PHI
2755 && phi_contains_arg (stmt
, lhs
))
2762 /* Return the argument of the loop PHI that is the initial value coming
2763 from outside the loop. */
2766 edge_initial_value_for_loop_phi (gimple phi
)
2770 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2772 edge e
= gimple_phi_arg_edge (phi
, i
);
2774 if (loop_depth (e
->src
->loop_father
)
2775 < loop_depth (e
->dest
->loop_father
))
2782 /* Return the argument of the loop PHI that is the initial value coming
2783 from outside the loop. */
2786 initial_value_for_loop_phi (gimple phi
)
2790 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2792 edge e
= gimple_phi_arg_edge (phi
, i
);
2794 if (loop_depth (e
->src
->loop_father
)
2795 < loop_depth (e
->dest
->loop_father
))
2796 return gimple_phi_arg_def (phi
, i
);
2802 /* Returns true when DEF is used outside the reduction cycle of
2806 used_outside_reduction (tree def
, gimple loop_phi
)
2808 use_operand_p use_p
;
2809 imm_use_iterator imm_iter
;
2810 loop_p loop
= loop_containing_stmt (loop_phi
);
2812 /* In LOOP, DEF should be used only in LOOP_PHI. */
2813 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2815 gimple stmt
= USE_STMT (use_p
);
2817 if (stmt
!= loop_phi
2818 && !is_gimple_debug (stmt
)
2819 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
2826 /* Detect commutative and associative scalar reductions belonging to
2827 the SCOP starting at the loop closed phi node STMT. Return the phi
2828 node of the reduction cycle, or NULL. */
2831 detect_commutative_reduction (scop_p scop
, gimple stmt
, vec
<gimple
> *in
,
2834 if (scalar_close_phi_node_p (stmt
))
2836 gimple def
, loop_phi
, phi
, close_phi
= stmt
;
2837 tree init
, lhs
, arg
= gimple_phi_arg_def (close_phi
, 0);
2839 if (TREE_CODE (arg
) != SSA_NAME
)
2842 /* Note that loop close phi nodes should have a single argument
2843 because we translated the representation into a canonical form
2844 before Graphite: see canonicalize_loop_closed_ssa_form. */
2845 gcc_assert (gimple_phi_num_args (close_phi
) == 1);
2847 def
= SSA_NAME_DEF_STMT (arg
);
2848 if (!stmt_in_sese_p (def
, SCOP_REGION (scop
))
2849 || !(loop_phi
= detect_commutative_reduction (scop
, def
, in
, out
)))
2852 lhs
= gimple_phi_result (close_phi
);
2853 init
= initial_value_for_loop_phi (loop_phi
);
2854 phi
= follow_inital_value_to_phi (init
, lhs
);
2856 if (phi
&& (used_outside_reduction (lhs
, phi
)
2857 || !has_single_use (gimple_phi_result (phi
))))
2860 in
->safe_push (loop_phi
);
2861 out
->safe_push (close_phi
);
2865 if (gimple_code (stmt
) == GIMPLE_ASSIGN
)
2866 return detect_commutative_reduction_assign (stmt
, in
, out
);
2871 /* Translate the scalar reduction statement STMT to an array RED
2872 knowing that its recursive phi node is LOOP_PHI. */
2875 translate_scalar_reduction_to_array_for_stmt (scop_p scop
, tree red
,
2876 gimple stmt
, gimple loop_phi
)
2878 tree res
= gimple_phi_result (loop_phi
);
2879 gimple assign
= gimple_build_assign (res
, unshare_expr (red
));
2880 gimple_stmt_iterator gsi
;
2882 insert_stmts (scop
, assign
, NULL
, gsi_after_labels (gimple_bb (loop_phi
)));
2884 assign
= gimple_build_assign (unshare_expr (red
), gimple_assign_lhs (stmt
));
2885 gsi
= gsi_for_stmt (stmt
);
2887 insert_stmts (scop
, assign
, NULL
, gsi
);
2890 /* Removes the PHI node and resets all the debug stmts that are using
2894 remove_phi (gimple phi
)
2896 imm_use_iterator imm_iter
;
2898 use_operand_p use_p
;
2899 gimple_stmt_iterator gsi
;
2905 def
= PHI_RESULT (phi
);
2906 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2908 stmt
= USE_STMT (use_p
);
2910 if (is_gimple_debug (stmt
))
2912 gimple_debug_bind_reset_value (stmt
);
2913 update
.safe_push (stmt
);
2917 FOR_EACH_VEC_ELT (update
, i
, stmt
)
2922 gsi
= gsi_for_phi_node (phi
);
2923 remove_phi_node (&gsi
, false);
2926 /* Helper function for for_each_index. For each INDEX of the data
2927 reference REF, returns true when its indices are valid in the loop
2928 nest LOOP passed in as DATA. */
2931 dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED
, tree
*index
, void *data
)
2934 basic_block header
, def_bb
;
2937 if (TREE_CODE (*index
) != SSA_NAME
)
2940 loop
= *((loop_p
*) data
);
2941 header
= loop
->header
;
2942 stmt
= SSA_NAME_DEF_STMT (*index
);
2947 def_bb
= gimple_bb (stmt
);
2952 return dominated_by_p (CDI_DOMINATORS
, header
, def_bb
);
2955 /* When the result of a CLOSE_PHI is written to a memory location,
2956 return a pointer to that memory reference, otherwise return
2960 close_phi_written_to_memory (gimple close_phi
)
2962 imm_use_iterator imm_iter
;
2963 use_operand_p use_p
;
2965 tree res
, def
= gimple_phi_result (close_phi
);
2967 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
2968 if ((stmt
= USE_STMT (use_p
))
2969 && gimple_code (stmt
) == GIMPLE_ASSIGN
2970 && (res
= gimple_assign_lhs (stmt
)))
2972 switch (TREE_CODE (res
))
2982 tree arg
= gimple_phi_arg_def (close_phi
, 0);
2983 loop_p nest
= loop_containing_stmt (SSA_NAME_DEF_STMT (arg
));
2985 /* FIXME: this restriction is for id-{24,25}.f and
2986 could be handled by duplicating the computation of
2987 array indices before the loop of the close_phi. */
2988 if (for_each_index (&res
, dr_indices_valid_in_loop
, &nest
))
3000 /* Rewrite out of SSA the reduction described by the loop phi nodes
3001 IN, and the close phi nodes OUT. IN and OUT are structured by loop
3004 IN: stmt, loop_n, ..., loop_0
3005 OUT: stmt, close_n, ..., close_0
3007 the first element is the reduction statement, and the next elements
3008 are the loop and close phi nodes of each of the outer loops. */
3011 translate_scalar_reduction_to_array (scop_p scop
,
3016 unsigned int i
= out
.length () - 1;
3017 tree red
= close_phi_written_to_memory (out
[i
]);
3019 FOR_EACH_VEC_ELT (in
, i
, loop_phi
)
3021 gimple close_phi
= out
[i
];
3025 gimple stmt
= loop_phi
;
3026 basic_block bb
= split_reduction_stmt (scop
, stmt
);
3027 poly_bb_p pbb
= pbb_from_bb (bb
);
3028 PBB_IS_REDUCTION (pbb
) = true;
3029 gcc_assert (close_phi
== loop_phi
);
3032 red
= create_zero_dim_array
3033 (gimple_assign_lhs (stmt
), "Commutative_Associative_Reduction");
3035 translate_scalar_reduction_to_array_for_stmt (scop
, red
, stmt
, in
[1]);
3039 if (i
== in
.length () - 1)
3041 insert_out_of_ssa_copy (scop
, gimple_phi_result (close_phi
),
3042 unshare_expr (red
), close_phi
);
3043 insert_out_of_ssa_copy_on_edge
3044 (scop
, edge_initial_value_for_loop_phi (loop_phi
),
3045 unshare_expr (red
), initial_value_for_loop_phi (loop_phi
));
3048 remove_phi (loop_phi
);
3049 remove_phi (close_phi
);
3053 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI. Returns
3054 true when something has been changed. */
3057 rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop
,
3066 detect_commutative_reduction (scop
, close_phi
, &in
, &out
);
3067 res
= in
.length () > 1;
3069 translate_scalar_reduction_to_array (scop
, in
, out
);
3076 /* Rewrites all the commutative reductions from LOOP out of SSA.
3077 Returns true when something has been changed. */
3080 rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop
,
3083 gimple_stmt_iterator gsi
;
3084 edge exit
= single_exit (loop
);
3086 bool changed
= false;
3091 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3092 if ((res
= gimple_phi_result (gsi_stmt (gsi
)))
3093 && !virtual_operand_p (res
)
3094 && !scev_analyzable_p (res
, SCOP_REGION (scop
)))
3095 changed
|= rewrite_commutative_reductions_out_of_ssa_close_phi
3096 (scop
, gsi_stmt (gsi
));
3101 /* Rewrites all the commutative reductions from SCOP out of SSA. */
3104 rewrite_commutative_reductions_out_of_ssa (scop_p scop
)
3108 bool changed
= false;
3109 sese region
= SCOP_REGION (scop
);
3111 FOR_EACH_LOOP (li
, loop
, 0)
3112 if (loop_in_sese_p (loop
, region
))
3113 changed
|= rewrite_commutative_reductions_out_of_ssa_loop (scop
, loop
);
3118 gsi_commit_edge_inserts ();
3119 update_ssa (TODO_update_ssa
);
3120 #ifdef ENABLE_CHECKING
3121 verify_loop_closed_ssa (true);
3126 /* Can all ivs be represented by a signed integer?
3127 As CLooG might generate negative values in its expressions, signed loop ivs
3128 are required in the backend. */
3131 scop_ivs_can_be_represented (scop_p scop
)
3135 gimple_stmt_iterator psi
;
3138 FOR_EACH_LOOP (li
, loop
, 0)
3140 if (!loop_in_sese_p (loop
, SCOP_REGION (scop
)))
3143 for (psi
= gsi_start_phis (loop
->header
);
3144 !gsi_end_p (psi
); gsi_next (&psi
))
3146 gimple phi
= gsi_stmt (psi
);
3147 tree res
= PHI_RESULT (phi
);
3148 tree type
= TREE_TYPE (res
);
3150 if (TYPE_UNSIGNED (type
)
3151 && TYPE_PRECISION (type
) >= TYPE_PRECISION (long_long_integer_type_node
))
3158 FOR_EACH_LOOP_BREAK (li
);
3164 /* Builds the polyhedral representation for a SESE region. */
3167 build_poly_scop (scop_p scop
)
3169 sese region
= SCOP_REGION (scop
);
3170 graphite_dim_t max_dim
;
3172 build_scop_bbs (scop
);
3174 /* FIXME: This restriction is needed to avoid a problem in CLooG.
3175 Once CLooG is fixed, remove this guard. Anyways, it makes no
3176 sense to optimize a scop containing only PBBs that do not belong
3178 if (nb_pbbs_in_loops (scop
) == 0)
3181 if (!scop_ivs_can_be_represented (scop
))
3184 if (flag_associative_math
)
3185 rewrite_commutative_reductions_out_of_ssa (scop
);
3187 build_sese_loop_nests (region
);
3188 build_sese_conditions (region
);
3189 find_scop_parameters (scop
);
3191 max_dim
= PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS
);
3192 if (scop_nb_params (scop
) > max_dim
)
3195 build_scop_iteration_domain (scop
);
3196 build_scop_context (scop
);
3197 add_conditions_to_constraints (scop
);
3199 /* Rewrite out of SSA only after having translated the
3200 representation to the polyhedral representation to avoid scev
3201 analysis failures. That means that these functions will insert
3202 new data references that they create in the right place. */
3203 rewrite_reductions_out_of_ssa (scop
);
3204 rewrite_cross_bb_scalar_deps_out_of_ssa (scop
);
3206 build_scop_drs (scop
);
3208 build_scop_scattering (scop
);
3210 /* This SCoP has been translated to the polyhedral
3212 POLY_SCOP_P (scop
) = true;